Textos básicos‎ > ‎El sistema RSA‎ > ‎

Ejemplo RSA

publicado a la‎(s)‎ 30 sept. 2012 17:19 por lu cipher   [ actualizado el 30 sept. 2012 18:32 ]
Ejemplo de la pagina  137 del libro "Seguridad Practica en UNIX e Internet"
Utilizando el modulo "numtheory" de maple

Uno de los grandes problemas de la criptografía es el intercambio de claves entre dos
 personas que van a sostener correspondencia cifrada.  Este problema se resuelve
mediante el uso del método de clave publica (del que RSA es uno de los procedimientos 
mas interesantes).  El algoritmo RSA (Rivest, Shamir, y Adleman, 1977)  trata de un 
sistema de codificación y decodificación,  que no requiere del intercambio de claves. 
Un sistema que ademas es casi imposible de romper. Cada individuo crea dos claves, 
una privada que mantiene en secreto y una publica que divulga.

RSA se basa en las muy conocidas propiedades número-teóricas de la aritmética modular y
los números enteros y en la dificultad de factorizar números muy grandes (mayores de 15 cifras). Esta soportado sobre dos pilares fundamentales: 

1) Es relativamente fácil encontrar dos números primos grandes y multiplicarlos para dar un numero   que sirva para una clave de cifrado (n  = p . q).
2) El proceso inverso, esto es, la determinación de p y q a partir de un numero grande n es imposible   de realizar en un tiempo aceptable y un costo razonable, que no supere el valor de la información    codificada.

Cuan aceptable? Dado la disponibilidad de todos los computadores del presente (eventualmente un billón de computadoras haciendo un billón de corroboraciones por segundo),  no es posible descifrar el resultado de un poderoso encriptamiento (utilizando un numero primo seguro); antes del fin del Universo.
La seguridad del sistema depende de la dificultad en descomponer la clave publica de encritamiento (factorizarla), si esto requiere varios siglos de computador, el sistema puede considerarse seguro; aunque en teoría se sepa como hacerlo.

Suponga que p y q son dos números primos de aproximadamente el mismo tamaño, elegidos utilizando un método apropiado. Estos números deben ser grandes -en el orden de varios cientos de dígitos- y deben mantenerse secretos.  No vale para estos fines cualquier par de primos, porque hay sistemas abreviados de factorización de un numero que podrían ser utilizados, para romper la clave.  Se trata de utilizar primos que obliguen a que el único sistema aplicable de factorización sea el genérico.  Para ello  basta con elegir los primos seguros  p y q , tales que q = (p-1)/2 sea también primo o utilizar una función que calcule primos seguros mas cercanos como la función 

> safeprime, de Maple.

> with(numtheory):
Como ejemplo se eligieron dos pequeños números primos seguros p y q.
> p:=251;
> q:= safeprime(p);

                               p := 251


                               q := 263


Se calcula n = p.q (p y q deben permanecer en secreto) y n se debe compartir mediante algún canal confiable.

> n:=p.q;  

                              n := 66013


Se calcula la función de Euler Totient 
> phi(n);: para todo entero positivo n, el numero de números positivos menores que n y primos con n se denota por 
> phi(n);
Para el caso de que n sea el producto de dos primos:      
> phi(p.q); = (p-1)(q-1) = 
> phi(n) .

> phi(n);

                                65500


Se selecciona un valor que sea relativamente primo a 
> phi(n);. Una buena elección seria escoger algo en el intervalo
max (p + 1, q + 1) < e < 
> phi(n);. 

En nuestro caso una e arbitraria (aleatoria), proveniente de la palabra "MA" en ASCII (M=4D, A=41): 

> e:=19777;

                              e := 19777

Se calcula d (inverso modular de e mod[ phi(n)]),  tal que: e.d mod ( phi(n);) = 1:

> d:=e^(-1)mod(phi(n));

                              d := 21713

Si d resulta ser demaciado pequeño (por ejemplo, aproximadamente menor que el log(base2)(n)),
se eligen otro d y e.
 
Ahora tenemos una clave d (PRIVADA)  para descifrar un mensaje m, codificado con la clave e (PUBLICA).

ejemplo: "RSA work!";


Se divide m en enteros de longitud fija M menores que m.

ASCII(M)       hexa       decimal
      RS------   5253       21075
      Ab------   4120       16672
      wo------   776f        30575
      rk ------   726b       29291
      s!-------   7321       29473

Para cada valor de M decimal se calcula su correspondiente valor cifrado s : Para "RS"

> m:=21075;

                              m := 21075

> s:=(m**e)mod(n);

                              s := 4600

Cuando se calcula s para todo los M, se obtiene el mensaje m cifrado: 
m(cifrado) =  48467  15579  26195  58004  30141 

Para descifrar, se eleva cada uno de estos números s a la potencia d y se toma el residuo mod(n).

> t:=(s**d)mod(n);

                              t := 21075

Este valor t en decimal se expresa en ASCII, para construir el mensaje original.
21075d = 5253h = RS
> convert(t,hex);

                                 5253

Este numero hexadecimal expresado en ASCII representan los caracteres del mensaje original m.

“If all the personal computers in the world—260 million—were put to work on a
single PGP-encrypted message, it would still take an estimated 12 million times the
age of the universe, on average, to break a single message.”
--William Crowell, Deputy Director, National Security Agency, March 20,
1997.

Comments