Como en todo criptosistema de clave pública un usuario dispone de dos claves: una pública, que debe estar en posesión de cualquier persona que pretenda enviarle un mensaje cifrado, y otra privada, que el usuario utilizará para descifrar los mensajes que le envíen y que sólo él posee. Es decir, el emisor cifrará el mensaje con la clave pública del receptor y sólo éste podrá descifrarlo utilizando su clave privada.
El algoritmo RSA sirve también para firmar digitalmente un mensaje, es decir, para que el receptor valide que el emisor es realmente quien lo ha enviado y para comprobar que no ha sido interceptado y alterado por terceros (integridad).
Decía en este post que, debido a que los criptosistemas asimétricos presentan una complejidad de cálculo significativamente mayor que los criptosistemas simétricos, que los hace significativamente más lentos que estos últimos, en la práctica se utilizan sistemas criptográficos híbridos.
Una vez dicho esto, los mensajes a enviar se representan mediante números y la seguridad del algoritmo RSA se basa en el elevado coste computacional de encontrar los dos factores primos de un número muy grande resultado del producto de éstos, y se considera que será seguro hasta que no se conozca una forma eficiente de hallarlos. Por tanto, se trata de un problema que es muy fácil de resolver en un sentido (multiplicar dos número primos), pero cuya resolución en sentido contrario (conocido el producto hallar esos dos factores) se vuelve inabordable en un tiempo razonable para números lo suficientemente grandes, por mucha potencia de cálculo de la que se disponga con los ordenadores actuales.
Como digo, en el algoritmo RSA las cláves pública y privada se calculan a partir del producto de dos números primos grandes, de la siguiente manera:
1.- Se eligen aleatoriamente dos números primos grandes (p y q) y se calcula el producto (n). Es decir, n = pq.
2.- Se calcula la función de Euler del módulo n, que para dos números primos es: j(n) = (p - 1)(q - 1).
3.- Se escoge un número e, en el intervalo 1 < e < j(n), que sea coprimo o primo relativo con j(n), es decir, de forma que el máximo común divisor de e y j(n) sea 1 (mcd(e, j(n))= 1). La clave pública será (e, n).
4.- Se calcula, mediante el algoritmo de Euclides extendido, el inverso mutiplicativo (d) de e módulo j(n), es decir, que satisfaga: de º 1 mod (j(n)). La clave privada será (d, n).
El cifrado del mensaje (m) lo realiza el emisor con la clave pública del receptor mediante la siguiente expresión: c = me mod (n), y el receptor lo descifra con su clave privada mediante la expresión: m = cd mod (n).
¿Fácil, no?, pues yo no me he enterado de nada y como he dicho que lo que voy a intentar explicar de una forma comprensible pongo el siguiente ejemplo para ver si lo entiendo (con números pequeños, para facilitar su comprensión por parte de torpes como yo).
1.- Para generar un par de claves:
1.1.- Elijo dos números primos, por ejemplo: p = 53 y q = 997, y calculo su producto: n = pq = 53 x 997 = 52.841.
1.2.- Calculo j(n) = (p - 1)(q - 1) = (53-1)(997-1) = 52 x 996 = 51.792.
1.3.- Escojo un número natural e que sea primo relativo con 51.792, por ejemplo 7, ya que el máximo común divisor de 7 y 51.792 es 1. La clave pública será (7, 52.841).
1.4.- Calculo el inverso multiplicativo (d) de e módulo j(n):
a) 51.792 = 7.398 x 7 + 6.
b) 7 = 1 x 6 + 1.
c) 1 = 7 - 1 x 6.
d) 6 = 51.792 - 7.398 x 7.
e) 1 = 7 - 1 x (51.792 -7.398 x 7) = -1 x 51.792 + 7.398 x 7 + 7 = -1 x 51.792 + 7.399 x 7.
Por tanto, el inverso multiplicativo (d) de e módulo j(n) es 7.399 y la clave privada será (7.399, 52.841).
a) Texto en claro (M) = "CIFRADORSA".
b) Como el módulo es 52.841, que en binario es: 1100111001101001 ((1 x 20) + (0 x 21) + (0 x 22) + (1 x 23) + (0 x 24) + (1 x 25) + (1 x 26) + (0 x 27) + (0 x 28) + (1 x 29) + (1 x 210) + (1 x 211) + (0 x 212) + (0 x 213) + (1 x 214) + (1 x 215) = 1 + 8 + 32 + 64 + 512 +1.024 +2.048 + 16.384 + 32.768 = 52.841), es decir, 16 bits, deberemos cifrar bloques con una longitud máxima de 16 bits (2 bytes) inferiores a dicho valor. Por ejemplo, cifraremos los siguientes bloques: "CI", "FR", "AD", "OR", "SA" convirtiendo cada uno de ellos en un bloque de 2 bytes (1 byte por cada carácter).
c) Para ello, por ejemplo, transformamos esos bloques a números según el valor decimal de cada uno de ellos en código ASCII, de la siguiente manera:
"CI" = 01000011 01001001 = m1 = 17.225.
"FR" = 01000110 01010010 = m2 = 18.002.
"AD" = 01000001 01000100 = m3 = 16.708.
"OR" = 01001111 01010010 = m4 = 20.306.
"SA" = 01010011 01000001 = m5 = 21.313.
d) Cifrado: el emisor utiliza para ello la clave pública del receptor (7, 52.841), obteniéndose los siguientes bloques del criptograma:
c2 = 18.0027 mod 52.841 = 25.633.
c3 = 16.7087 mod 52.841 = 52.061.
c4 = 20.3067 mod 52.841 = 16.353.
c5 = 21.3137 mod 52.841 = 20.222.
e) Descifrado: el receptor utiliza su clave privada (7.399, 52.841):
m1 = 1.8557.399 mod 52.841 = 17.225 = 01000011 01001001 = "CI".
m2 = 25.6337.399 mod 52.841 = 18.002 = 01000110 01010010 = "FR".
m3 = 52.0617.399 mod 52.841 = 16.708 = 01000001 01000100 = "AD".
m4 = 16.3537.399 mod 52.841 = 20.306 = 01001111 01010010 = "OR".
m5 = 20.2227.399 mod 52.841 = 21.313 = 01010011 01000001 = "SA".Texto en claro (M) = "CIFRADORSA".
En el siguiente post, teniendo en cuenta todo lo comentado en éste, hablaré de cómo puede el receptor validar la autenticidad del mensaje recibido, tanto identidad del emisor como integridad (no modificación) del mensaje.
Quizás también te interese:
.png)
.png)
Muy útil ... ¿Por qué usar el AEE en todos los casos? es decir, si debo hallar un d tal que d.e = 1 mod φ(n) y se cuenta con e y φ(n), no sería suficiente (para #s pequeños) despejar: d = e^-1 mod φ(n)? Muchas gracias !
ResponderEliminarCalcular e^-1 no es fácil. La manera más cómoda es con el AEE. Si fi(n) es pequeño pueden usarse probatinas.
EliminarHola Buenas Noches, me gusto mucho la explicacion, me podrias aclara el punto e) de la generacion de clave privada. Gracias
ResponderEliminarBuenas tardes, tengo una consulta :Si una persona tiene como clave pública (5,91) <>. Encontrar su clave privada indicando las fórmulas y cálculos utilizados. ¿cuales serian los pasos a seguir para resolverlo mediante un ataque de cumpleaños?
ResponderEliminarBuenas tardes Silvana:
ResponderEliminarEn primer lugar pedirte disculpas por no haberte contestado antes, ya que tengo muy abandono el blog respecto a contestar a los comentarios. También pido disculpas a todos aquellos a los que no hayan contestado todavía.
Paso ahora a contestarte.
Como bien sabes, en el criptosistema RSA no es posible obtener la clave privada de un usuario conocida su clave pública, salvo que se pueda realizar con éxito algún ataque al mismo, como por ejemplo el de factorización del módulo (n).
En el caso que planteas, como el módulo (n) es muy pequeño, 91, la factorización es muy fácil, recuerda que la seguridad de este criptosistema, entre otras cosas, se basa en el tamaño de los números primos, p y q cuyo producto es el módulo, n= p x q. En el caso que planteas 91 = 7 x 13.
Una vez factorizado el módulo el cifrado está “roto” ya que obtener la clave privada (d, n) es trivial:
1.- Calculo Phi(n), que para dos números primos es:
Phi(n) = (p-1) (q-1) = (7 -1) (13 -1) = 6 12 = 72
2.- Calculo el exponente de la clave privada (d), que es el inverso multiplicativo modular del exponente de la clave pública (e) módulo Phi(n), d x e congruente 1 mod(Phi(n)). En el caso que planteas e = 5. Como también sabes sólo existe ese inverso multiplicativo modular si e y Phi(n) son coprimos o primos relativos, es decir, si el máximo común divisor de ambos es 1, como es el caso, ya que mcd(5, 72) = 1.
El inverso multiplcativo de 5 mod(72) = 29 y, por tanto, la clave privada es (d, n) = (29, 91)
En un siguiente comentario contestaré a tu segunda pregunta sobre el ataque de cumpleaños.
Buenas tardes Silvana:
ResponderEliminarTe contesto a la segunda pregunta.
Como paso previo establezco los datos de nuestro caso y del ejemplo que utilizaré:
Clave pública del receptor (e, n): (5, 91)
Clave privada del receptor (d, n): (29, 91)
Ejemplo (veamos cómo sería el cifrado y descifrado con los datos de ambas claves):
mensaje (m) = 26
Cifrado y descifrado:
Cifrado (el emisor utiliza la clave pública del receptor): c = m ^ e mod n = 26 ^ 5 mod 91 = 52
Descifrado (el receptor utiliza su clave privada): m = c ^ d mod n = 52 ^ 29 mod 91 = 26.
Conociendo sólo la clave pública del receptor del mensaje (5, 91) y el mensaje cifrado o criptograma (c = 52), el ataque de paradoja del cumpleaños para obtener la clave privada del receptor (d, 91) y poder descifrar con ella el criptograma (c) y obtener el mensaje en claro (m) consistiría en:
1.- Dividimos el módulo en dos mitades o tramos de igual tamaño:
i mayor o igual que 1 - i menor o igual que 45
j mayor o igual que 46 – j menor o igual que 91,
y escogemos un número cualquiera, por ejemplo: k = 85
2.-Hacemos simultáneamente: ci = k ^ i mod n; cj = k ^ j mod n, hasta encontrar una colisión, es decir, que uno de los valores obtenidos en la primera mitad (i) coincida con uno de los obtenidos en la segunda mitad (j), o viceversa. Si esto ocurre el ataque puede haber prosperado de forma que a partir de los valores de i y j sea posible obtener la clave privada del destinatario (d, n), y posteriormente descifrar el criptograma (c) para obtener el texto en claro (m):
c1 = k ^ 1 = 85 ^ 1 mod 91 = 85; c46 = k ^ 46 mod 91 = 85 ^ 46 mod 91 = 43
c2 = k ^ 2 = 85 ^ 2 mod 91 = 36; c47 = k ^ 47 mod 91 = 85 ^ 47 mod 91 = 15
…
C4 = k ^ 4 = 85 ^ 4 mod 91 = 22; c49 = k ^ 49 mod 91 = 85 ^ 49 mod 91 = 85
Como se observa para i = 1 y j = 49 se produce una colisión, por lo que el ataque podría haber prosperado.
3.- Calculo: x = |i - j| / mcd(e, |i - j|) = |1 - 49| / mcd(5, |1 - 49|) = 48 / mcd(5, 48) = 48 / 1 = 48
4.- El exponente de la clave podría ser: inv(e, x) = inv(5, 48) = 29, y, tal y como se puede ver al inicio de este comentario, efectivamente, hemos obtenido el exponente de la clave privada (d) del receptor, por lo que esta última es (29, 91) y podríamos descifrar el mensaje con ella: m = c ^ d mod 91 = 52 ^ 29 mod 91 = 26.