Algoritmo de encriptacion RSA

Vista previa del material en texto

CRIPTOSISTEMA RSA
CRIPTOGRAFIA DE CLAVE 
SECRETA
El emisor y el receptor 
conocen y usan la misma clave 
secreta para cifrar y descifrar 
mensajes.
Problemas de este método
• El emisor y el receptor deben 
ponerse de acuerdo sobre la clave 
secreta 
• Deberán confiar en un medio de 
comunicación fiable
• Cualquiera que escuche o 
intercepte la clave podrá leer todos 
los mensajes encriptados.
ADMINISTRACION DE 
CLAVES.
• La criptografía de clave 
secreta con frecuencia 
tiene dificultad para 
proporcionar una 
administración de claves 
que sea segura.
Criptografía de clave pública
• Inventada en 1976 por Whitfiled
y Martin Helman
• Intentan solventar los problemas 
de seguridad que tenían la 
administración de las claves de 
los sistemas anteriores.
Criptografía de clave pública
• Cada usuario obtiene una pareja de 
claves: clave pública y clave secreta.
• La clave publica de cada persona 
puede ser conocida por todos.
• La clave privada es mantenida en 
secreto por el propietario de la 
misma.
- No hay necesidad de compartir la 
clave secreta.
Criptografía de clave pública
• Las comunicaciones implican 
únicamente a las claves públicas, 
mientras que las claves privadas 
nunca son transmitidas o 
compartidas 
• No hace falta disponer canales de 
comunicaciones seguros contra 
escuchas
Utilidades
•Cifrado y Descifrado de 
mensajes (privacidad) 
• Autenticación (firma 
digital).
CRIPTOSISTEMA DE CLAVE 
PUBLICA
A encripta con
la clave pública de B
A envia el mensaje a B
B descifra el mensaje
con su clave privada
MENSAJE ORIGINAL
MENSAJE RECIBIDO
MENSAJE CIFRADO
MENSAJE
Usuario A
Clave DA
Usuario B
Clave DB
Usuario C
Clave DC
FICHERO 
PUBLICO 
DE CLAVES
EA
EB
EC
C = EB(mA)
m A= DB(c)
Mensaje A
mA
• Nadie podrá descifrarlo, ya que no 
poseerá la clave secreta de B . 
• Cualquiera puede enviar un mensaje 
encriptado a B usando su clave pública, 
pero sólo B podrá leerlo. 
• Requerimiento necesario: no se pueda 
descifrar la clave secreta de un usuario a 
partir de su correspondiente clave 
pública.
Ventajas de los criptosistemas de 
clave pública frente a los de clave 
privada
•1. Incremento en la seguridad del 
sistema.
•2. Proporciona método de 
autentificación (firma digital), que 
en los sistemas de clave privada es 
mas complicado de realizar.
Desventaja de la clave pública 
frente a la clave privada
• . Menor velocidad de cifrado y 
descifrado
• Existen métodos basados en clave 
secreta bastantes populares que son 
más rápidos que cualquier sistema de 
clave pública.
La mejor solución
•Combinar ambos métodos para 
obtener las ventajas de ambos
•La seguridad de los crptosistemas de 
clave pública 
•La rapidez de los cripsistemas de clave 
secreta
R.S.A.
• El RSA es un criptosistema de clave 
pública que sirve tanto para 
encriptar mensajes como para 
autenticación de documentos o 
transacciones (firmas digitales).
• Fue inventado en 1977 por Ron 
Rivest, Adi Shamir y Leonard 
Adleman.
SEGURIDAD RSA
• Este criptosistema basa su 
seguridad en que no existe una 
manera rápida y sencilla de 
factorizar cantidades que son 
producto de dos números primos 
largos.
ALGORITMO RSA
•Se seleccionan dos n°
primos largos p y q de 
forma aleatoria y se calcula 
el producto de n=p*q. A 
este n se le denomina 
módulo.
ALGORITMO RSA
•Se elige un número d, 
menor que el valor n
calculado anteriormente y 
que sea relativamente primo 
al producto de (p-l)(q-l).
ALGORITMO RSA
• Calculamos un número entero e que esté 
dentro del rango
• l≤≤≤≤ e ≤≤≤≤(p-l)(q-l) con la siguiente 
operación:
•e d=1 mod[(p-l)(q-l)]
• A d y e se les conoce como los 
exponentes privado y público 
respectivamente.
ALGORITMO RSA
• La clave pública la formarán la 
pareja (n,e).
• La clave privada viene dada por 
(n,d).
• Con la clave pública 
procederíamos a encriptar el 
mensaje deseado y con la clave 
privada se desencriptaría
ALGORITMO RSA
• El factor p y q debe ser 
guardado en secreto o 
destruido, para evitar que 
cualquiera intente reventar el 
sistema, ya que podría obtener 
la clave privada.
ALGORITMO RSA
• Presumiblemente es difícil obtener la 
clave privada, d, a partir de la clave 
pública (n,e).
• Si pudiéramos factorizar n en p y q, 
podríamos obtenerla.
• La seguridad del RSA se basa en la 
idea de que esta factorización es 
sumamente complicada de realizar.
ALGORITMO RSA
• La relación entre e y d asegura 
una correcta reconstrucción de 
los mensajes.
• Debido a que sólo el receptor 
conoce la clave secreta d,
solamente él puede desencriptarlo
• Es responsabilidad suya el 
guardar dicha clave secreta.
ALGORITMO RSA
• El cifrado de mensajes tiene 
lugar sin ningún tipo de 
compartición de claves privadas
• Cada persona usa solamente la 
clave pública del receptor al que 
quiere enviar el mensaje y su 
propia clave privada
ENCRIPTADO
•1°°°°) Encontrar dos primos 
largos p y q de forma 
aleatoria y definir el valor 
de n de la siguiente forma:
•n=p*q 
ENCRIPTADO
•2°°°°) Encontrar un entero largo 
d que sea relativamente 
primo a (p-l) (q-l).
• Se escoge un número primo 
que pertenezca al siguiente 
intervalo:
• [max(p,q)+ 1, n-l]
ENCRIPTADO
• Entonces 
• M.C.D. [d,(p-1)(q-1)] = 1
ENCRIPTADO
•3°°°°) Obtener un número entero 
e que esté dentro del rango
• l ≤≤≤≤ e ≤≤≤≤ (p-l) (q-l)
•aplicando la siguiente fórmula:
•e d=1 mod[[[[(p-l) (q-l)]]]]
ENCRIPTADO
• 4°°°°) Obtenemos la clave 
pública que la forman la 
pareja (n,e).
• La clave privada será 
(n,d).
ENCRIPTADO
•5°°°°) Asociamos a cada 
carácter del alfabeto un valor 
numérico 
•Entonces cifrarnos el 
mensaje m por bloques de la 
misma longitud (M) .
ENCRIPTADO
•El valor numérico está 
comprendido entre un cierto 
rango (1...n)
• 6º Para cifrar cada uno de los 
bloques M realiza:
• C = Me mod n
ENCRIPTADO
• 7º Para descifrar C y 
obtener el mensaje m se 
utiliza la clave privada d
mediante
•M = Cd mod n
EJEMPLO SIMPLE
•1) p=3, q=5 (elección de dos nº 
primos.
•2) n=p*q = 15
•3) ΦΦΦΦ(n) = (3-l)(5-l)=8 
•4)Sea e=3 d=3 ya que
• e*d =3*3 =9 mod 8 =1
ENCRIPTADO-
DESENCRIPTADO
• Clave privada (15,3)
• Clave pública (15,3)
• 5) Si el mensaje m = 2
• 6) El cifrado c = me mod n ; c = 23mod 15 = 8
• 7) Para descifrar m = cd mod n ; m= 83 mod 15 
m= 512 mod 15 = 2 ya que 512/15 = 2 mod 15 
EJEMPLO
• Mensaje = ITS ALL GREEK TO ME (Julio Cesar)
• p = 47; q = 59 ⇒ n = 47*59 = 2773
• d = 157
• e*d = 1 mod (p-1)*(q-1)
• e*157 = 1 mod 2668 ⇒ e = 17
• CLAVE PUBLICA (2773,17)
• CLAVE PRIVADA (2773,157)
Mensaje cifrado
• Alfabeto esp = 00, A = 01 , B= 02, C = 03....
• M0 M1 M2 M3 M4 M5 M6 M7 M8 M9
• I T S φ AL L φ GR EE 
• 0920 1900 0112 1200 0718 0505
• K φ TO φ M E φ
• 1100 2015 0013 0500
• Si tomamos el primer bloque tenemos que:
• C0 = M0l7 = 092017 ( mod 2773 ) = 948
• siendo C0 = 948 que es el primer bloque del 
mensaje cifrado.
Mensaje cifrado
• El mensaje total sería:
• C0 Cl C2 C3 C4 C5 C6 C7 C8 C9
• 0948 2342 1084 1444 2663 2390 0778 0774 0219 1655
• Para descifrar el mensaje:
• Utilizamos el primer bloque la fórrnula de 
descodificación obtendríamos el bloque M0 
original:
• M0 = C0157 = 920( mod 2773 ).
Mensaje Original 
• Consiguiendo al final el mensaje original.
• M0 M1 M2 M3 M4 M5 
• 0920 1900 0112 1200 0718 0505
• I T S φ AL L φ GR EE
• M6 M7 M8 M9
• 1100 2015 0013 0500
• K φ TO φ M E φ
DIAGRAMA DEL
RSA
Cálculo de los parámetros
(n,p,q,e,d)
Mensaje (m)
Mensaje cifrado
c
Mensaje Recibido
Mensaje Original
Clave pública
(n,e)
Clave privada
(n,d)
Envío mensje 
cifrado
Encriptar m
C = me mod n
Desencriptar c
m = cd mod n
Receptor
SEGURIDAD R.S.A.
• La seguridad del criptosistema
depende del tamaño de n.
• Cuanto mayor sea el tamaño del módulo 
mejor será la seguridad del 
criptosistema.
• Pero el tamaño de n influye 
negativamente enla velocidad de las 
operaciones del RSA.
•
SEGURIDAD R.S.A.
• Cuanto más grande sea el 
tamaño del módulo, mucho 
más dif1cil será factorizarlo 
mediante algún algoritmo y 
así obtener los valores de p
y q.
Algoritmo de Schoroeppel
)ln(ln)ln(( pp
e
Tiempo de factorización
• Dígitos N° Op Tiempo
• 50 1,4x109 3,9 horas
• 75 9,Ox1012 104 días
• 100 2,3x1015 74 años
• 200 1 ,2x1023 3,8x109 años
• 300 l ,5x l029 4.9xl015 años
• 500 1 ,3xl039 4 2x1025 años
• Recomendable usar p y p del orden de 100 
dígitos
Seguridad-Rapidez
• Cuanto más mayor es el tamaño de n⇒
mayor seguridad ⇒ mayor lentitud cifrado 
descifrado
n 80 digitos
Seguridad moderada
con la tecnología actual
n 200 dígitos
Margen de seguridad
contra agresiones
de futuras tecnologías
FORMAS DE REVENTAR EL RSA
• 1°) Descubrir la clave secreta 
correspondiente a una clave pública 
dada. Si un usuario almacena su 
clave privada en lugar poco seguro.
• 2°) Factorizar el módulo público n, 
en sus dos factores primos p y q:
FORMAS DE REVENTAR EL RSA
• De p yq y el exponente público e, el 
agresor puede fácilmente obtener la 
clave privada d.
• La parte complicada es factorizar el 
módulo n.
• La seguridad del RSA depende de 
que esta factorización sea lo más 
difícil posible.
FORMAS DE REVENTAR EL RSA
• 3°°°°) Desarrollar alguna técnica para 
computar la operación raíz enésima 
mod n:
• La raíz enésima de c nos dará el 
mensaje m (c=me mod n).
• Este ataque permitiría a cualquiera 
reconstruir los mensajes encriptados
sin tener que conocer la clave privada 
empleada para desencriptar los 
mensajes.
FORMAS DE REVENTAR EL RSA
• Actualmente no se conoce 
ninguna técnica implementada 
de este tipo que sirva para 
reventar el sistema RSA
• * Las formas de ataque al RSA 
vistas anteriormente son las 
únicas de reventar el RSA
OTROS METODOS DE CIFRADO DE 
CLAVE PUBLICA
•a) Un problema matemático 
denominado problema 
Knapsack (Mochila) fue la 
base de varios sistemas.
•Diversas versiones fueron 
reventadas y dejaron de temer 
interés
OTROS METODOS DE CIFRADO 
DE CLAVE PUBLICA
• b) ElGamal está basado en el 
problema del logaritmo discreto. 
El sistema de ElGamal fue en 
parte la base de varios métodos 
de autentificación, como el DSS, 
etc. 
OTROS METODOS DE CIFRADO 
DE CLAVE PUBLICA
• El sistema ElGamal se ha 
utilizado satisfactoriamente en 
muchas aplicaciones.
• Es mucho más lento para 
encriptar y para verificar que el 
RSA 
• Sus firmas son más largas que 
las del R.SA.
OTROS METODOS DE CIFRADO 
DE CLAVE PUBLICA
• c) En 1976 antes del RSA, Diffie y 
Hellman propusieron un sistema de 
intercambio seguro de claves de los 
criptosistemas de clave secreta
• Este método está en uso hoy en dia.
• d) Existen criptosistemas basados en 
operaciones matemáticas sobre 
curvas elípticas.
OTROS METODOS DE CIFRADO 
DE CLAVE PUBLICA
• Criptosistemas basados en la 
exponenciación discreta en los 
campos finitos de Galois (2n).
• También existen algunos métodos de 
encriptación probabilística, que 
tienen la ventaja de ser resistentes a 
algunos de los métodos de reventar 
sistemas vistos, pero con el coste de 
una expansión de los datos.
•
VENTAJAS DEL R.S.A
•La ventaja del RSA sobre 
otros criptosistemas de clave 
pública es que puede ser 
empleado tanto para 
encriptar mensajes como 
para su autentificación.
VENTAJAS DEL R.S.A
• RSA ha recibido mucha más 
atención, estudio y uso que cualquier 
otro criptosistema de clave pública 
• Un gran número de criptosistemas
de clave pública que al principio 
parecían ser muy seguros, luego 
fueron reventados fácilmente
Uso del criptosistema RSA
• Actualmente se emplea en una 
amplia gama de productos, 
plataformas e industrias de todo 
el mundo.
• Se encuentra en bastantes 
productos de software 
comercial. 
Uso del criptosistema RSA
• RSA se instala en los actuales 
sistemas operativos o en los 
proyectados por Microsoft, Apple 
Sun y Novell.
• En hardware RSA se encontra en:
• seguridad para teléfonos. 
• tarjetas de redes Ethernet.
• tarjetas inteligentes.
Uso del criptosistema RSA
• RSA se emplea en:
• Muchas instituciones
• Departamentos del gobierno de los 
Estados Unidos.
• Grandes corporaciones.
• Laboratorios nacionales.
• Universidades.
Comparación RSA - DES
• El RSA no es una alternativa o 
sustituto para el DES.
• Es un complemento y se utiliza 
junto con el DES en entornos de 
comunicación bastantes seguros.
• El RSA proporciona dos funciones 
importantes que no las suministra el 
DES:
Comparación RSA - DES
•1°) Intercambio de claves de 
forma segura sin un previo 
intercambio de secretos.
• 2°°°°) Autentificación (o firma 
digital).
COMBINACION
D.E.S.
Y
R.S.A.
MENSAJE ENCRIPTADO 
CON CLAVE D.E.S.
CLAVE D.E.S SE
ENCRIPTA CON R.S.A.
SE ENVIA MENSAJE
Y CLAVE POR CANAL
SE DESCIFRA LA 
CLAVE D.E.S.
MEDIANTE R.S.A
SE DESCIFRA EL
MENSAJE MEDIANTE
LA CLAVE D.E.S.
COMPARACIÓN DES- RSA
• El DES es mucho más lento 
que el RSA 
• En software el DES es al menos 
100 veces más rápido que el 
RSA. 
COMPARACIÓN DES- RSA
–En hardware, el DES es 
entre 1000 y 10000 veces 
más rápido que el RSA, 
dependiendo del tipo de 
implementación. 
COMPARACIÓN DES- RSA
•Con el paso del tiempo y las 
mejoras en los procedimientos el 
RSA, probablemente, estrechará 
esta brecha existente con el 
DES, pero jamás llegará al 
desarrollo del sistema anterior.
Comparación RSA - DES
• El RSA no es una alternativa o 
sustituto para el DES.
• Es un complemento y se utiliza 
junto con el DES en entornos de 
comunicación bastantes seguros.
• El RSA proporciona dos funciones 
importantes que no las suministra el 
DES:
Comparación RSA - DES
•1°) Intercambio de claves de 
forma segura sin un previo 
intercambio de secretos.
• 2°°°°) Autentificación (o firma 
digital).
PROBLEMA R.S.A.
M..I.T.PASA
• PATENTE 
R.S.A.
PRETTY GOOD PRIVACY
P.G.P.