CIFRADO RSA
¿Qué es RSA?
El sistema criptográfico con
clave pública RSA es un algoritmo asimétrico cifrado de bloques, que utiliza
una clave pública, la cual se distribuye (en forma autenticada
preferentemente), y otra privada, la cual es guardada en secreto por su
propietario.
Emplea expresiones exponenciales
en aritmética modular.
La seguridad de este algoritmo
radica en que no hay maneras rápidas conocidas de factorizar un número grande
en sus factores primos utilizando computadoras tradicionales. La computación cuántica podría
proveer una solución a este problema de factorización. El algoritmo RSA es un algoritmo
de clave pública desarrollado en 1977 en el MIT por Ronald Rivest, Adi Shamir y
Leonard Adelman. Fue registrado el 20 de
Septiembre de 1983. El 20 de Septiembre del 2000, tras 17 años, expiró la
patente RSA, pasando a ser un algoritmo de dominio público. Este popular sistema se basa en
el problema matemático de la factorización de números grandes.
El algoritmo RSA funciona de la
siguiente manera:
1. Inicialmente es necesario generar
aleatoriamente dos números primos grandes, a los que llamaremos p y q.
2. A continuación calcularemos n
como producto de p y q: n = p * q
3. Se calcula fi: fi(n)=(p-1)(q-1)
4. Se calcula un número natural e de
manera que MCD(e, fi(n))=1 , es decir e debe ser primo relativo de fi(n).
Es lo mismo que buscar un numero
impar por el que dividir fi(n) que de cero como resto.
5. Mediante el algoritmo extendido
de Euclides se calcula d: e.d mod fi(n)=1
Puede calcularse d=((Y*fi(n))+1)/e
para Y=1,2,3,… hasta encontrar un d entero.
6. El par de números (e,n) son la
clave pública.
7. El par de números (d,n) son la
clave privada.
8. Cifrado: La función de cifrado es
C = M^e mod n
9. Descifrado: La función de
descifrado es M = C^d mod n
Ejemplo con números pequeños:
1. Escogemos dos números primos, por
ejemplo p=3 y q=11.
2. n = 3 * 11 = 33
3. fi(n) = (3-1) * (11-1) = 20
4. Buscamos e: 20/1=0, 20/3=6.67.
e=3
5. Calculamos d como el inverso
multiplicativo módulo z de e, por ejemplo, sustituyendo Y por 1,2,3,… hasta que
se obtenga un valor entero en la expresión: d = ((Y * fi(n)) + 1) / e = ( Y *
20 + 1) / 3 = 21 / 3 = 7
6. e=3 y n=33 son la clave pública
7. d=7 y n=33 son la clave privada
8. Cifrado: Mensaje = 5, C = M^e mod
n = 5^3 mod 33 = 26
9. Descifrado: M = C^d mod n = 26^7
mod 33 = 8031810176 mod 33 = 5
Ejemplo visual de RSA:
Un ejemplo pedagógico trivial del
algoritmo RSA se muestra en la siguiente animación. Para este ejemplo hemos
seleccionado p=3 y q=11, dando n=11 y z=20. Un valor adecuado de d es d=7,
puesto que 7 y 20 no tienen factores comunes.
Con estas selecciones, e puede
encontrarse resolviendo la ecuación 7e=1(mod 20), que produce e=3.El texto
cifrado, C, de un mensaje de texto normal, P, se da por la regla C=P3(mod 33).
El texto cifrado lo descifra el receptor de acuerdo con la regla P= C7(mod 33).
Observe la animación tanto en el emisor como en el receptor, donde se muestra
el cifrado-descifrado del texto normal “CASA”.
Dado que los números primos
escogidos para este ejemplo son tan pequeños, P debe ser menor que 33, por lo
que cada bloque de texto normal puede contener sólo un carácter. El resultado
es un cifrado por sustitución mono alfabética, no muy impresionante. En cambio
si hubiéramos seleccionado p y q 10100, podríamos
tener n 10200, para que cada bloque
pueda ser de hasta 664 bits (s644 10200)
u 83 caracteres de 8 bits, contra 8 caracteres para el DES.
Más información de algoritmos de clave pública,
de criptosistemas, de ataques a RSA y por supuesto el infaltable libro de
criptografía del profesor Jorge Ramio Aguirre y de Manuel Lucena, todos ellos
descargables de nuestra sección de libros de seguridad.
.:Enlace:.
Fuentes:
http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/ejmrsa.html
https://seguinfo.wordpress.com/2007/09/14/%C2%BFque-es-rsa/
http://daniellerch.com/sources/doc/algoritmo_rsa.html
0 comentarios:
Publicar un comentario