Mostrar Mensajes
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:
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”
y gracias por la respuesta "octalh"