Foro de elhacker.net

Seguridad Informática => Criptografía => Mensaje iniciado por: Unravel en 20 Abril 2005, 02:49 am



Título: RSA para no iniciados
Publicado por: Unravel en 20 Abril 2005, 02:49 am
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.


Título: Re: RSA para no iniciados
Publicado por: Rojodos en 20 Abril 2005, 08:44 am
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  ;D).

Un gran doc unravel :)


Título: Re: RSA para no iniciados
Publicado por: TaN€R en 22 Abril 2005, 18:55 pm
 
Citar
Un gran doc unravel

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

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

saludos


Título: Re: RSA para no iniciados
Publicado por: Unravel en 23 Abril 2005, 01:16 am
Coño Taner,
Pos gracias ;


Título: Re: RSA para no iniciados
Publicado por: + enrique ZP en 1 Junio 2005, 17:12 pm
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.
Citar
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  :)


Título: Re: RSA para no iniciados
Publicado por: Isirius en 17 Noviembre 2005, 14:45 pm
Buena informacion Gracias.


Título: Re: RSA para no iniciados
Publicado por: Neobius en 24 Diciembre 2005, 11:29 am
Citar
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


Título: Re: RSA para no iniciados
Publicado por: [Addam] en 28 Enero 2006, 04:26 am
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.



Título: Re: RSA para no iniciados
Publicado por: Perpetron en 31 Marzo 2006, 14:03 pm
Ampliando información:
http://www.daniellerch.com/sources/doc/algoritmo_rsa.html


Título: Re: RSA para no iniciados
Publicado por: n3o07 en 4 Abril 2006, 20:40 pm
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... ;D

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:
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 :o.

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

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

saludos :D


by n3o07



“Believe in the Unbelievable”


Título: Re: RSA para no iniciados
Publicado por: ..SnIgCiO.. en 12 Abril 2006, 15:23 pm
con rsa es posible tener una clave superior a 4096 bits? ya se que 4096 bits es mas que suficiente pero es por curiosidad nada mas  :P


Título: Re: RSA para no iniciados
Publicado por: TaN€R en 13 Abril 2006, 01:56 am
Citar
Poruqe no puedo imprimir el PDF

Porque el que escribe lo protejió adecuadamente, para que no lo puedan copiar modificar la fuente y el autor

Ese articulo está escrito desde cero por Unravel.
Si quiere que le quite las restricciones se las quito, pero debe decirlo él..


Título: Re: RSA para no iniciados
Publicado por: Crack_X en 13 Abril 2006, 02:43 am
con rsa es posible tener una clave superior a 4096 bits? ya se que 4096 bits es mas que suficiente pero es por curiosidad nada mas  :P

Estuve leyendo algunos textos de RSA y no vi que dijeran que no se podia, simplemente decian que era lo mayor o considerado mas seguro pero en verdad no se si se puede pasar de 4096 bits. Tendriamos que esperar al unravel.


Título: Re: RSA para no iniciados
Publicado por: nhaalclkiemr en 12 Enero 2007, 22:30 pm
Esta muy bien, pero no entiendo unas cosas.

Segun tengo entendido es muy dificil descifrar algo cifrado en RSA pork los numeros primos usados son muy grandes y no existen oredenadores tan potentes.

Ahora bien, segun tu manual parece mas facil descifrarlo.

¿Es el algoritmo RSA de los mas seguros (como yo creía) o es uno bastante facil realmente?


Título: Re: RSA para no iniciados
Publicado por: Neobius en 13 Enero 2007, 08:52 am
El algoritmo en si es sencillo, el problema radica en descomponer un numero de mas de 10100 cifras, el dia que eso sea posible estara roto el RSA. Por eso el RSA teme tanto a los ordenadores cuanticos, teoricamente con uno de ellos se podra descomponer con facilidad esos numeros.


Título: Re: RSA para no iniciados
Publicado por: nhaalclkiemr en 14 Enero 2007, 16:43 pm
Entonces que inconveniente tiene RSA??. Tiene que tener alguno para que no sea muy utilizado como por ejemplo el MD5.


Título: Re: RSA para no iniciados
Publicado por: Cobac en 22 Enero 2007, 07:31 am
Son dos cosas distintas.

El MD5 es una función de hash, se emplea para dar autenticidad a un programa (principalmente)

Me explico, tu te bajas un programa con un hash X, si en el sitio de donde te lo has bajado pone que ese archivo tiene otro hash, dirás, "mierd*!, alguien ha modificado el archivo!".

Si tiene el mismo hash quiere decir que es el mismo archivo (de ahí que si se puede encontrar dos archivos con el mismo hash es peligroso, imaginate que yo logro hacer un troyano con el hash anterior, y lo pongo en esa web -u otra- y la gente se lo descarga con confianza, ya que tiene el mismo hash que el auténtico)

Más información -> http://es.wikipedia.org/wiki/MD5

Y dado las vulnerabilidades que se le han encontrado, se empiezan a recomendar SHA-1 y demás (aunque al SHA-1 tampoco le queda mucho, y ya se estan buscando otras funciones de hash)

salu2!


Título: Re: RSA para no iniciados
Publicado por: nhaalclkiemr en 23 Enero 2007, 20:45 pm
Aunke SHA1 es algo mas fuerte tambien se le hayaron colisiones.

Lo mejor es SHA2-512 ;D ;D

Me confundi con el RSA.

Gracias.

un saludo ;)


Título: Re: RSA para no iniciados
Publicado por: tetiviri en 27 Marzo 2008, 20:27 pm
Hola a todos,
a pesar de leer y leer no me queda claro como descifrar una vez que tengo la clave publica ya que si n es mayor que el resultado de cifrado no podria divirlos. Para ser mas claro os pondré el ejemplo siguiente que es un ejercicio que tengo que hacer y no se por donde entrar. :-\

Un mensaje es cifrado usando RSA con clave pública n=70757 y e=19 dando como resultado
{41822, 60864, 1, 60864, 13931, 39153, 1, 38703, 11991, 38652, 13931, 38703,
13931, 60864, 13931, 59079, 55099, 41822, 9478, 36994, 1, 41822, 1, 36994,
41822, 38652, 39153, 9478, 60864, 60864, 55099, 52388, 38652, 6985, 38652,
6985, 38652, 13931, 38703, 11991, 13931, 39153, 13931, 38703, 11991, 13931,
60864, 59079, 41822, 1, 38703, 51989, 13931, 60864} donde cada número se corresponde
al cifrado de un sólo carácter.

Teniendo en cuenta que cada carácter del alfabeto es codificado antes de cifrar como A->1,B->2,C->3,etc...,
¿cuál es el mensaje original?.

Lo que tendria que hacer segun he entendido seria dividir 41822/70757, pero claro en los ejemplos que he visto el numerador es superior al denominador y con el resto que obtenemos sustituimos en el alfabeto en mi caso.

Si alguien pudiera aclararme algo le estaria muy agradecido pues como veis estoy totalmente perdido... :-[

Un saludo y gracias por vuestro tiempo!


Título: Re: RSA para no iniciados
Publicado por: ghastlyX en 27 Marzo 2008, 21:40 pm
Descifrado: RSASEMANTIENESEGUROPARAPRIMOSSUFICICIENTEMENTESGRANDES

Con números:
{19, 20, 1, 20, 5, 13, 1, 14, 21, 9, 5, 14, 5, 20, 5, 7, 22, 19, 16, 17, 1, 19, 1, 17, 19, 9, 13, 16, 20, 20, 22, 6, 9, 3, 9, 3, 9, 5, 14, 21, 5, 13, 5, 14, 21, 5, 20, 7, 19, 1, 14, 4, 5, 20}

Datos:

d = 7387

p = 173

q = 409

Un saludo de ghastlyX ;)


Título: Re: RSA para no iniciados
Publicado por: tetiviri en 28 Marzo 2008, 01:48 am
MUCHISIMAS MUCHISIMAS GRACIAS!!!
Me has hecho un favor enorme. ¿Me podrias explicar un poco como lo has hecho?

Lo dicho, ha sido todo un detalle que hayas respondido en cuestion de una hora.
Gracias!


Título: Re: RSA para no iniciados
Publicado por: ghastlyX en 28 Marzo 2008, 15:16 pm
Primero factorizas n y obtienes p = 173 y q = 409.

Calculas d, tal que d * e (mod phi(n)) = 1. Recuerda que phi(n) = (p - 1) * (q - 1). Para calcular d hice este código en C:
Código
  1. #define E 19
  2. #define PHI_N 70176 //(p - 1) * (q - 1)
  3.  
  4. #include <stdio.h>
  5.  
  6. int main()
  7. {
  8.    int i;
  9.    for(i = 0; i < 70757; i++)
  10.    {
  11.          if(((i * E) % PHI_N) == 1) printf("d = %d\n", i);
  12.    }
  13.    return 0;
  14. }

Una vez tenemos d = 7387, desciframos cada letra. Si llamamos c a la letra a descifrar y m la letra original, m = (c ^ d) (mod n). Así ya tendrás el mensaje descifrado en números:
{19, 20, 1, 20, 5, 13, 1, 14, 21, 9, 5, 14, 5, 20, 5, 7, 22, 19, 16, 17, 1, 19, 1, 17, 19, 9, 13, 16, 20, 20, 22, 6, 9, 3, 9, 3, 9, 5, 14, 21, 5, 13, 5, 14, 21, 5, 20, 7, 19, 1, 14, 4, 5, 20}

Así tan sólo te queda sustituirlo por las letras, que no tiene mucho misterio xDD. Hice este programa para que me lo hiciera solo si no te apetece hacerlo a mano:
Código
  1. #include <stdio.h>
  2.  
  3. int main()
  4. {
  5.    int i;
  6.    char abc[] = " ABCDEFGHIJKLMNÑOPQRSTUVWXYZ";
  7.    int cifrado[] = {19, 20, 1, 20, 5, 13, 1, 14, 21, 9, 5, 14, 5, 20, 5, 7, 22, 19, 16, 17, 1, 19, 1, 17, 19, 9, 13, 16, 20, 20, 22, 6, 9, 3, 9, 3, 9, 5, 14, 21, 5, 13, 5, 14, 21, 5, 20, 7, 19, 1, 14, 4, 5, 20};
  8.    for(i = 0; i < 54; i++) printf("%c", abc[cifrado[i]]);
  9.    return 0;
  10. }

Para hacer el paso de descifrar tendrás problemas con elevar a d según qué métode utilices. La calculadora de Windows sorprendentemente parece que lo realiza bien, yo utilizo un sistema de cadenas para estas cuentas tan bestias.

Un saludo de ghastlyX ;)


Título: Re: RSA para no iniciados
Publicado por: cccp2006 en 2 Julio 2014, 12:02 pm
Hola chicos primero muchas gracias por las aportaciones sobre rsa me han ayudado mucho. He tenido problemas con la precisión y errores de desbordamiento cuando trabajaba con exponentes muy grandes. Por si acaso alguien ha tenido el mismo problema, lo he resuelto de la siguiente manera:
Por ejemplo
18^23 mod 55
es equivalente a: (18^5*18^5*18^5*18^5*18^3) mod 55
Haciéndolo así no me da el error de desbordamiento y la precisión es buena.
Por aportar algo aunque debe ser una chorrada.
Un saludo.
 
ejemplo para sql server
El resultado correcto es 2
Select (power(18.0,23.0)) % 55 en este caso me da 5
Select power(18.0,5.0)*power(18.0,5.0)*power(18.0,5.0)*power(18.0,5.0)*power(18.0,3.0))% 55 este me da 2 que es correcto


Título: Re: RSA para no iniciados
Publicado por: garc en 26 Enero 2019, 20:55 pm
No he querido abrir ningun post para este tema porque creo que esta muy extendido y a la vez reducido, como bien pone para principiantes (mi caso), aun no controlo el tema pero.. resulta que como bien dice el compañero del post anterior, cuando elevo 18 a 23 al recorrer el modulo 55 me devuelve como resultado 12. Lo cual no corresponde con el resultado correcto. Alguien puede aclararme esto? mi hipotesis es que el pc *se folla la mente*. No me refiero al pc en si, se que tiene capacidad para eso y mucho mas, pero en mi caso lo he hecho mediante java con la clase Math.pow(18,23) divido 55 el resto me devuelve 12.  :-(


Título: Re: RSA para no iniciados
Publicado por: kub0x en 26 Enero 2019, 21:58 pm
Buenas noches,

el método equivalente a la hora de trabajar con exponenciales modulares es ModPow. En Java debería encontrarse en la clase BigInteger. Por lo que veo 18^23 tiene 95 bits quzia algo se está desbordando.

Aun así compañero, si tratas de obtener 18^23 mod 55, te recomiendo que hagas potencias de 18 y cuando el resultado sea mayor que 55 haces el módulo y sigues multiplicando por 18 al módulo obtenido:

18*18 es mayor que 55 por lo tanto haces el mod, que da 49, ahora 49*18 mod 55 y así 23 veces. Hay mejores métodos si te interesa busca por Modular Exponentiation.


Título: Re: RSA para no iniciados
Publicado por: garc en 28 Enero 2019, 11:46 am
Gracias de antemano, ya pensaba que tenia que iniciarme en otro lenguaje que no se desbordara con esos productos. Probaré tu método, seguiré bicheando.  ;-)