RSA para no iniciados

[Unravel]

Cualquiera que tenga el mínimo interés en sistemas de cifrado de clave pública/privada, como PGP, se habrá preguntado alguna vez que por qué son necesarios números primos muy grandes, o que cuantas parejas de claves salen de dos de esos números primos, o que como será el sistema
para que lo que se cifra con una clave se descifre solo con la otra, o que por qué es tan dificil obtener la clave privada a partir de la pública, etc.

Si alguno además se ha preocupado de leer lo que hay publicado por ahí, y no es matemático, supongo que lo habrá dado por imposible con tanto phi, numeros primos relativos, modulos, etc.

El propósito de este artículo es explicar como va esto de la manera más fácil posible, empezando desde cero y pasito a pasito.

Así veremos que no es tan difícil como parece.



Artimética modular:

Aunque el nombre asuste, es bien sencillo. Supongamos que nos ponemos a sumar o restar horas, en un reloj de esfera de 12 horas, nada de digitales. Si son las 8 y le sumamos 6 horas, nos quedan las 2. O sea, cuando pasamos de 12 empezamos por el 1.

Pues eso es aritmética modular. En este caso sería módulo 12.
Así podemos decir que 8 + 6 mod 12 = 2

La única diferencia es que en la aritmética modular incluimos el cero. Entonces en nuestro caso del reloj los números que existirían serían del 0 al 11. No habría por ejemplo el 12, porque "daría la vuelta" y pasaría a ser cero, o el 13 que pasaría a ser 1. Solo existen esos números.

Ahora en módulo 7. Nuestro universo de números sería {0,1,2,3,4,5,6}.
Si hiceramos 3*5, en los número reales sería 15, pero en módulo 7 serían 2 vueltas (7+7) y uno mas. O sea, 3*5 mod 7 = 1.

Como vemos, en realidad lo que hacemos para calcular el módulo es dividir 15 entre 7 y quedarnos con el resto, que es 1.
De esta misma forma, si dividimos 64 entre 7, nos sigue quedando que el resto es 1 (lo único que hemos hecho es "darle mas vueltas" al reloj), así que podemos decir que 64 = k*7 + 1. K nos da igual porque es el número de vueltas que le vamos a dar al reloj.

De forma genérica, si un número a (el 64) mod n (el 7) = resto (el 1), a = k*n + resto.

Bien, ahora vamos a fijarnos en este mismo ejemplo. Vemos que en mod 7, 3*5 = 1. Al igual que con los números reales, si dos números se multiplican y dan 1, es que son inversos (5 * 1/5 = 1).

Así podemos decir que 3 y 5 son inversos en módulo 7.

Hasta aquí claro? Es fácil verdad?


Seguimos,
Hay una propiedad, que os la teneis que creer, que dice que un número a tiene inversa módulo n, si no existe ningún número (excepto 1) menor que a y menor que n que los divida de forma exacta.
Esto es a lo que se llama primos relativos. 8 y 5 serían primos relativos, porque no hay ningún número que los divida, aunque 8 no sea primo. Su máximo común divisor es 1.

En el ejemplo del módulo 7, vemos que todos los números (el cero no cuenta) tienen que tener inversa, porque 7 es primo absoluto y no va a existir ningún número que lo divida.

* La inversa del 1 es el 1:  1 * 1 = 1 que dividido entre 7 es igual a cero y resto 1, (1*1 mod 7 =1)
* La inversa del 2 es el 4:  2 * 4 = 8 que dividido entre 7 es igual a 1 y de resto 0, (2*4 mod 7 = 1)
etc...



Esto también es fácil no?
Vale, vamos a entrar ahora con el temido número phi.

El número phi nos dice la cantidad de números que tienen inversa para un módulo.

Me explico, en nuestro caso, vemos que en el módulo 7 todo su conjunto de números, menos el cero, tienen inversa, porque 7 es un número primo y nos lo dice la propiedad anterior. O sea, hay 6 números (del 1 al 6) que tienen inversa, y si phi(7) nos dice la cantidad de números que tienen inversa, queda que phi(7) = 6.

De forma genérica, si n es un número primo, phi(n) = n - 1. (El menos 1 es porque no contamos con cero).

Por la misma razón, si n está formado por la multiplicación de dos números primos, n = p * q, entonces phi(n) = (p-1) * (q-1).


Generación de claves.

Ahora entramos ya en el meollo del artículo.
Para la generación de las claves pública y privadas, vamos a basarnos en phi(n).

Ahora creeros el por qué se hace esto, que luego lo entendereis.

Lo que hacemos es coger dos números primos muy muy grandes, que serán el p y q de antes, y multiplicarlos para calcular n.
Vale, ya tenemos n, lo dejamos apartado a un lado.

Calculamos el phi(n) que es (p-1)*(q-1).
Vale ya tenemos por otro lado phi(n).

Y ahora escogemos las claves.
La clave pública será un número aleatorio que sea primo relativo con phi(n). Esto es para que tenga inversa, recordad que si no hay ningún número menor que los divida es que tiene inversa. A ese númerro le llamamos e y la clave pública será la pareja (e,n).
A la inversa le llamamos d, y será la clave privada.

En este momento tenemos un número e, que sale de phi(n), un número d, que sale de phi(n) y el módulo n. Como ahora veremos, con e y n podemos cifrar y con d y n podemos descifrar, con lo que podemos tirar phi(n) a la basura.

Así que tiramos phi(n), que es el generador de nuestras claves.
Si alguien quisiera generar nuestra clave privada de nuevo, tendría que recuperar phi(n), no?

Y aquí está una de las cosas que siempre oimos, lo de la imposibilidad de factorizar.
El que quiera recuperar phi(n) para sacar la clave privada calculando la inversa de la pública, solo conoce n, no conoce p ni q. Así que tendría que empezar a dividir n entre números primos gigantes para adivinar p y q y luego poder hacer el (p-1)*(q-1) que es phi(n).
Y aquí hay dos dificultades, una es que ir dividiendo requiere muchos recursos, y otra es que saber si el número por el que divide es primo, por lo que la factorización de n (que así se llama a encontrar p y q) se vuelve un problema intratable.

Cifrar y descifrar.
1- Para cifrar, lo único que hacemos es elevar lo que queremos cifrar a e (el exponente de la clave pública).

2- Para descifrar es un poco más complicado.

Como hemos visto, las claves vienen calculadas en módulo phi(n), y nada tienen que ver a priori con n, son dos "segmentos" de números distintos.

Entonces como lo hacemos?

Hay una propiedad que dice que si multiplicamos un número a (distinto de cero) por si mismo phi(n) veces, o sea, a^phi(n), el resultado nos da 1 en módulo n.

En el ejemplo del módulo 7, donde phi(7) = 6, si multiplicamos por ejemplo el 2 por si mismo 6 veces (2^6) nos da 64 que como vimos 64 mod 7 = 1.

En esta propiedad es la que se basa todo el algoritmo RSA.



Vamos a calcular m^e (cifrar m) y luego elevarlo a d (descifralo) para ver si nos sigue quedando m.

Lo hacemos paso a paso.
* Elevar m a e y luego a d (m^(e^d)) es lo mismo que hacer m^(e*d). se multiplican los exponentes.
* D y e vienen de phi(n), y son inversas, o sea que d*e mod phi(n) = 1
* Según vimos al principio, d*e mod phi(n) = 1 es lo mismo que decir que d*e = k*phi(n) + 1.
* Resumiendo, tenemos que elevar m a phi(n), el resultado elevarlo a k y todo ello multiplicarlo luego por m otra vez. Recordad que es m elevado a k*phi(n) + 1, si aplicamos las reglas de la matemática normal podemos hacer (m^phi(n))^k * (m^1).
* Y hasta aquí hemos llegado en principio, como podemos ver, tenemos en medio a phi(n), el cual desconocemos porque lo hemos tirado al generar las claves, y sin conocerlo no podremos seguir, y no vamos a factorizar n claro. Pero entonces hacemos caso de la última propiedad, que nos permite poner phi(n) en factor de n.
* Si elevamos m a phi(n) nos da que m mod n = 1. Por lo cual sustituimos en la anterior fórmula y nos quedaría (1^k)(m^1) = m

Con lo que vemos como podemos descifrar mediante claves generadas por un módulo (phi(n)) usando otro módulo distinto, n.

Ejemplo real.

- Por un lado tenemos que n = 5 * 11.
- Y por otro lado tenemos que phi(n) = 4 * 10 = 40
- Elegimos e=7 que es primo relativo con 40.
- Calculamos su inversa módulo 40, que es 23. 7*23 = 161 = 1 mod 40. Tenemos que d = 23

Tenemos que la clave pública es (55, 7) y la privada (55, 23).

Si queremos cifrar el número 2, bastará con calcular 2^7 = 128 = 18 mod 55.
Si queremos descifrar, elevamos 18 a 23 módulo 55 y nos da 2.


Bueno, esto es todo.
Si lo leeis por encima os parecera dificil, pero si le dedicais algo de tiempo vereis lo sencillo que es.

Tened en cuenta que probablemente no haya otro documento donde se explique tan "lento", y si lo hay yo no lo he encontrado después de buscar mucho tiempo. Además estoy seguro de que muy poca gente lo entiende de forma tan clara a como aquí está espuesto, y eso es un privilegio del que ahora disponeis, así que aprovechadlo, porque es mi último artículo de criptografía en el foro.

Salu2

Postead vuestras dudas aquí, y poco a poco lo iremos acalrando más si cabe.

[Rojodos]

Chintetazo al canto, aunque habria que ir pensando en recoger estos docs en una chincheta, "centralizarlos".

Por lo demas, gran articulo. En la facultad ya nos explicaron mas o menos el funcionamiento de este algoritmo, aunque tardamos bastante mas de 30minutos, y tuvimos que hacer varias cuentas.

Es decir, el articulo esta genial, no hace falta ser matematico para entenderlo (solo dedicarle unos cuandos ciclos de cerebro  ).

Un gran doc unravel

[TaN€R]

 

Un gran doc unravel

Un gran doc , y ahora un mejor "pdf".

http://www.iespana.es/telefoniafacil/RSA_Novatos.pdf

saludos

[Unravel]

Coño Taner,
Pos gracias ;

[+ enrique ZP]

Bueno ya lo lei jeje al principio tenia miedo de no entenderle pero pues ya me e fijado mas.

Algo que me a quedado en duda es.

Cualquiera que tenga el mínimo interés en sistemas de cifrado de clave pública/privada, como PGP,

Al igual que el PGP podemos incluir el cifrado WEP y WPA?

Digo sobre el WEP ya que este utiliza el algoritmo de encriptacion RC4 el cual fue proporcionado por RSA Security.

Pues no se si me equivoque.

Una cosa mas.

Es decir todos estos cifrados bienen a ayudarse entre si, ya que el TKIP ayuda al WEP. Osea todos estos cifrados trabajan en conjunto para mejorar la codificacion y hacer mas dificil la decodificacion.

Adios 

[Isirius]

Buena informacion Gracias.

[Neobius]

Un gran doc unravel

Un gran doc , y ahora un mejor "pdf".

http://www.iespana.es/telefoniafacil/RSA_Novatos.pdf

saludos

Poruqe no puedo imprimir el PDF

[[Addam]]

Hola unravel, taner y los demas soy nuevo en este tema pues no se nada de criptografia y tengo muchas ganas de aprender. Acabo de leer el articulo y solo me quedo cono un 10%, pero no me preocupo solo es cuestion de echarle otra o varias leidas mas, en fin.
Supongo que este es el tema para principiantes me refiero para los que empiezan de cero como yo, pero siempre tiene su grado de dificultad esto pero las ganas de aprender son mas grandes asi que no crea que sea obstaculo.

No me pego tan duro el texto pues ya habia investigado algo al respecto pero superficialmente aca en http://www.htmlweb.net/seguridad/cripto_p/cripto_princ_1.html , pero de no haberlo leido quedaria totalmente perdido.
Y me parece que esta muy bien explicado ahi.

Bueno pues solo queria saludarlos a todo el equipo de criptografia y queria decirles que me van a ver seguido por este subforo., pues como ya les dije me interesa aprender y se que no es un tema facil, pero esta es una razon mas para insistir en esto.

Bueno otra vez les dio un saludo y que me colaboren con las dudas que se me vayan presentando.

[Perpetron]

Ampliando información:
http://www.daniellerch.com/sources/doc/algoritmo_rsa.html

[n3o07]

Hace unos días el profr. de Cripto nos dejo una investigación sobre la
generación de la llave privada para RSA, estuve buscando mucha
informacion para poder hacer la tarea, y me gustaria compartir
con ustedes esta información...

Los ejemplos fueron desarrollados personalmente, solo siguendo
cada método.


CÁLCULO DE LA LLAVE PRIVADA PARA RSA(CALCULO DEL VALOR INVERSO)


0.- Introducción

En el cifrado asimétrico es necesario la generación de un par de llaves
(una pública y otra privada), es por eso que se utilizan diferentes mé-
todos para generar estas llaves. En el caso del cifrado de llave públi-
ca RSA, la generación de llaves se puede utilizar cualquiera de los si-
guientes métodos presentados.  El proceso de creación de claves es muy
simple, se basa en la correcta elección de dos números primos que permi-
tirán generar otros, con unas características éstos últimos tales que
sea mutuamente reversible la transformación hecha por el otro. Existen
tres formas de obtener la llave privada (valor inverso de  ): Teorema
de Euler/Fermat, Teorema de Euclides Extendido y Teorema del Resto Chino.
Dos los primeros métodos son sencillos, en el caso del Teorema del resto
chino las matemáticas son algo complicadas, pero espero que con el ejem-
plo se entienda completamente.


1.- Cifrando/ Descifrando  con RSA

cifrado: C = (M^e) mod n           decifrado M = (C^d) mod n

2.- Teorema de Euler/Fermat

Del teorema de Euler se tiene:

si mcd(a,n)=1   

=>   

( a^phi(n) ) = 1 (mod n) 
( a^phi(n) ) mod n = 1

En el teorema de Fermat:

Si "n" es un número primo:

phi(n)=n-1

Si "n" es la multiplicación de dos números primos "p" y "q":

phi(n)=(p-1)(q-1)

aplicando el teorema de Fermat al teorema de Euler:

( a^(p-1) ) = 1 (mod p)
( a^(p-1) ) mod p = 1

Se puede emplear el teorema de Euler para realizar el cálculo de la inversa
mod n, resolviendo la siguiente ecuación: 

( a^phi(n) ) mod n = 1
( a a^(phi(n)-1) ) mod n = 1

considerando a "x" como el inverso:

x = ( a^(phi(n)-1) ) mod n

cuando "n" es un número primo, (usando el teorema de Fermat):

x = (a^(n-2) ) mod n


cuando "n" es el producto de dos números primos:

x = ( a^((p-1)(q-1)-1) ) mod n

3.- Algoritmo Extendido de Euclides

Se utiliza para calcular el inverso de un número cuando se desconoce phi(n),
Este algoritmo dice que si "a" y "n" son relativamente primos ( mcd(a,n)=1 )
Existe "u","v" tal que:

(n*u)+(a*v) = 1 mod n 

ó

(a*v)=1 mod n

esto debe cumplir:

mcd(a,n)=1

(a*v) = 1 mod n

(a*v) = 1 + (k*n)

(a*v) + (-k)*n = 1

u = -k

Primero es necesario comprobar que el mcd(a,n)=1, para ello se utiliza el algo-
ritmo de Euclides.

Función del Algoritmo Extendido de Euclides:

Código [Seleccionar] Expandir


mi=n*ui + a*vi

Valores iniciales:  m0=n, m1=a, u0=1, u1=0, v0=0, v1=1

cuando mi=0, m(i-1)=mcd(a,n)=1 y v(i-1) sera la inversa de "a"

int inversa(int a, int n)
{
int i=1,cociente;

m[0]=n;
m[1]=a;
u[0]=1;
u[1]=0;
v[0]=0;
v[1]=1;

while(m[i]!=0){
cociente=m[i-1]/m[i];
m[i+1]=m[i-1]%m[i]; // mcd
u[i+1]=u[i-1]-cociente*u[i];
v[i+1]=v[i-1]-cociente*v[i];
i++;
}
return(v[i-1]%n);
}


4.- Teorema del Resto Chino

Este teorema básicamente dice que es posible reconstruir un entero en un cierto rango
a partir de los residuos de una pareja de factores del entero relativamente primos. De
esta forma se obtiene una representación distinta del número en forma de números más
cortos.

Aporta una forma sencilla de manipular número módulo M muy largos (M > 150 dígitos) en
forma de tuplas de números menores.

Ejemplo: dado el número 10, podemos reconstruir cualquier elemento de Z10(0, ..., 9) a
partir de los residuos de 2 y 5 (factores de 10 relativamente primos dado que
mcd(2,5) = 1).

1 mod 2 = 1      1 mod 5 =1
2 mod 2 = 0      2 mod 5 =2
3 mod 2 = 1      3 mod 5 =3
4 mod 2 = 0      4 mod 5 =4
5 mod 2 = 1      5 mod 5 =0
6 mod 2 = 0      6 mod 5 =1
7 mod 2 = 1      7 mod 5 =2
8 mod 2 = 0      8 mod 5 =3
9 mod 2 = 1      9 mod 5 =4

esto lo podemos representar como:

1 -> (1,1)
2 -> (0,2)
3 -> (1,3)
4 -> (0,4)
5 -> (1,0)
6 -> (0,1)
7 -> (1,2)
8 -> (0,3)
9 -> (1,4)


Si (mi,mj) son parejas de numeros relativamente primos:

mcd(mi,mj)=1 para 1<=i, j<=k, con i!=j.

M=productoria(desde i=1, hasta k) de (mi)

Se puede representar cualquier entero en Zm por una tupla k-tupla en Zm, usando las si-
guientes correspondecias:

A <-> (a1,a2,...,ak)

Donde:

A esta contenido en Zm (0 <= A <= M)

ai esta contenido en Zmi (0 <= ai <= mi)

ai= A mod Zmi (1 <= i <= k)


Propiedades:

   a) Las relación A y (a1,a2,...,ak) es uno a uno en ambos sentidos. Por los tanto
      la transformación es unica.
   
   b) Las operaciones implementadas en los elementos de Zm    son equivalentes a las
      realizadas sobre cada elemento de la k-tupla.

      Si A <-> (a1,a2,...,ak) y B <-> (b1,b2,...,bk). Se representa con **, las
      operaciones +,- ó *.
      
      A ** B mod n <-> ((a1 ** b1)mod n, (a2 ** b2)mod n, ..., (ak ** bk)mod n)

Los calculos que se tiene que realizar son:

   a) A => (a1,a2,...ak)

      i) ai=A mod mi      para (1 <= i <= k)

   b) A <= (a1,a2,...ak)
   
      i) realizar Mi=(M / mi)      para (1 <= i <= k)

         Mi=m1*m2*...*m(i-1)*m(i+1)*...*mk
      
         Asi se cumple que Mi=0 (mod j) para j!=i
   
      ii) Haciendo ci = Mi * (Ii mod mi) para (1 <= i <= k), donde Ii es el inverso de Mi

         Por definición Mi es relativamente primo de mi y por lo tanto tiene un
         unico inverso multiplicativo mod mi. Entonces ci es unico. mcd(Mi,mi)=1

      iii) Calcular A

         A = sumatoria(desde i-1 hasta k)  [ (ai*ci) ] mod M

         A = sumatoria(desde i-1 hasta k)  [ (ai*Mi*Ii)] mod M

         Para verificar que a es correcto podemos calcular (ai = A mod mi)
         para (desde i-1 hasta k).

      Notar que:

         cj = Mj = 0 (mod mi)    si j!=i
         
         ci = 1 (mod mi)


5.- Ejemplos de aplicación de los Teoremas.

Alicia desea generar sus llaves, eligen un número n=p*q=7*13=91. Eligiendo una llave pública de a=5
debemos calcular el inverso de a.


   A) Aplicando el Teorema de Euler/Fermat.

   Para aplicar este metodo es necesario calcular que se cumpla mcd(a,n)=1. Esto lo podemos ver
   claramente que se cumple.
   
   Debido a que "n" no es un número primo, pero sabermos que es la multiplicación de dos números
   primos, podemos calcular la función phi(n) de Euler, por medio de:

   phi(n)=(p-1)(q-1)
   phi(n)=(7-1)(6-1)
   phi(n)=6*12
   phi(n)=72

   Ahora solo nos resta aplicar la fórmula, una vez que hemos conocido phi(n).

   x = ( a^(phi(n)-1) ) mod n
   x = ( 5^(72-1) ) mod 91
   x = ( 5^71 ) mod 91
   x = (4,2351647362715016953416125033982e+49) mod 91     <- usando la calculadora cientifica de güindows.
   x = 73

   Por lo tanto la llave pública de Alicia es (5,91), y la llave privada (73,91).


   B) Aplicando el Algoritmo Extendido de Euclides.

   Calcular el inverso de (a mod n), en este caso: (5 mod 91)

   Utilizamos una tabla para mejor explicación:


   |---|---------|--------|--------|--------|
   | i |cociente |   mi   |   ui   |   vi   |
   |---|---------|--------|--------|--------|
   | 0 |    -    |  91(n) |    1   |    0   |
   | 1 |    -    |   5(a) |    0   |    1   |
   | 2 |    18   |   1    |    1   |  -18   |
   | 3 |    -    |   0    |    -   |    -   |
   |---|---------|--------|--------|--------|


   Para i=1
   
   cociente=(mo/m1)=(91/5)=18
   m2=(m0%m1)=(91%5)=1
   u2=u0-(cociente*u1)=1-(18*0)=1
   v2=v0-(cociente*v1)=0-(18*1)=-18

   Debido a que mi ya es 0 terminamos...

   Ahora formamos la ecuación con la penúltima fila (mi=1):

   n*ui + a*vi = 1
   
   (91)(1) + (5)(-18) = 1

   calcular el inverso de a

   5^(-1) = (-18) mod 91
   
   5^(-1) = (-18) + 91

   5^(-1) = 73

   Por lo tanto el valor inverso de a=5, es 73.

   La llave pública de Alicia es (5,91) y la llave privada es (73,91).


   C) Aplicando el Teorema del Resto Chino.

   Para calcular el inverso de a, por medio de este teorema es necesario resolver
   la siguiente ecuación:

   ax mod n = b

   pero para este caso, "b" debe ser uno para que "x" sea el inverso multiplicativo.

   ax mod n = 1

   Utilizando los valores que tenemos:

   5x mod 91 = 1

   El algoritmo dice que debemos factorizar "n", obteniendo:

   n=91
   n=7*13
   
   d1=7
   d2=13

   como n=d2, existen dos soluciones de xi

   (a*x1) mod d1 = b mod d1   =>   (5*x1) mod 7 = 1 mod 7
   (a*x2) mod d2 = b mod d2   =>   (5*x2) mod 13 = 1 mod 13

   resolviendo para xi:

   (5*x1) mod 7 = 1
   (5*x2) mod 13 = 1

   Ahora tenemos que resolver la ecuacion auxiliar del Teorema del Resto Chino:

   yi=inv[(n/di),di]
   
   Procedemos a calcular los dos inversos:

   y1 = inv[ (91/7),7]

   y1 = inv[13,7]

   y2 = inv[(91/13),13]

   y2 = inv[7,13]

   Para calcular estos inversos, aplicamos el Algoritmo Extendido de Euclides.
   Aqui solo muestro la tabla del algoritmo de euclides, si desean pueden aplicar
   el algoritmo y construir la tabla.

      a) y1 = inv[13,7]

         |---|---------|--------|--------|--------|
         | i |cociente |   mi   |   ui   |   vi   |
         |---|---------|--------|--------|--------|
         | 0 |    -    |   7(n) |    1   |    0   |
         | 1 |    -    |  13(a) |    0   |    1   |
         | 2 |    1    |   7    |    1   |    0   |
         | 3 |    1    |   6    |   -1   |    1   |
         | 4 |    1    |   1    |    2   |   -1   |
         | 5 |    -    |   0    |    -   |    -   |
         |---|---------|--------|--------|--------|
   
         De la penúltima fila obtenemos:
         
         n*ui + a*ui = 1
      
         (7)(12) + (13)(-1)=1
      
         13^(-1) = (-1) mod 7
         
         13^(-1) = -1 + 7
      
         13^(-1) = 6
      
         El inverso y1=6
      
      b) y2 = inv[7,13]

         |---|---------|--------|--------|--------|
         | i |cociente |   mi   |   ui   |   vi   |
         |---|---------|--------|--------|--------|
         | 0 |    -    |  13(n) |    1   |    0   |
         | 1 |    -    |   7(a) |    0   |    1   |
         | 2 |    1    |   6    |    1   |   -1   |
         | 3 |    1    |   1    |   -1   |    2   |
         | 4 |    -    |   -    |    -   |    -   |
         |---|---------|--------|--------|--------|

         De la penúltima fila obtenemos:

         n*ui + a*ui = 1

         (13)(-1) + (7)(2) = 1

         y^(-1) = 2 mod 13

         y^(-1) = 2

         El inverso y2=2

   Ahora que ya tenemos los valores inversos, utilizar la ecuación del Resto Chino:

   x=sumatoria(de i=1 hasta t) [(n/di)*yi*xi] mod n

   Recordando:

   a=5
   n=91
   d1=7
   d2=13
   x1=3
   x2=8
   y1=6
   y2=2

   x = [((91/7)*6*3) + ((91/13)*2*8)] mod 91

   x = [234 + 112] mod 91

   x = [346] mod 91

   x = 73

   Por lo tanto, el valor inverso de de x en la ecucacion (5*x)mod 91=1 es:

   x = 73

   La llave pública es (5,91) y la llave privada es (73,91).


nota: En los ejemlos anteriores se han usado numeros pequeños
para una fácil manipulación de estos...


6.- Conclusiones.

Como podemos observar, con los tres métodos obtenemos la misma llave privada
(numero inverso de "a"); pero con los dos primeros es mas fácil de aplicar,
mientras que en el Teorema del Resto Chino, es necesario aplicar otro metodo
para encontrar los inversos Ii.

Llave publica (a,n) => (5,91)

Llave privada (x,n) => (73,91)

El problema radica (como lo meciona unravel) en poder factorizar el numero
muy grande de lla llave pública "e", para tratar de obtener la funcion phi(n),
y encontrar la llave privada "d" utilizando algunos de los métodos anteriores,
pero con numeros enormes .

De hecho existen desafios para factorizar una llave de una
cantidad xxxx de bits, en la página de RSA

http://www.rsasecurity.com/rsalabs/node.asp?id=2093

saludos


by n3o07



"Believe in the Unbelievable"