miércoles, 26 de octubre de 2016

Criptografía (XXXV): el algoritmo RSA (I)

En este post me propongo contar, como siempre de la forma más comprensible de la que sea capaz, lo que voy aprendido sobre RSA, un algoritmo de cifrado asimétrico que debe su nombre a las iniciales de los apellidos de sus tres inventores: Ronald Rivest, Adi Shamir y Leonard Adleman, que lo desarrollaron en 1977.

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.
Es decir, el texto en claro se cifra mediante una clave de sesión, correspondiente a cada mensaje particular y generada aleatoriamente, y la clave de sesión se cifra utilizando la clave pública del receptor, de tal manera que sólo el receptor puede descifrar la clave de sesión mediante su clave privada (criptografía asimétrica) y posteriormente descifrar el texto en claro mediante la clave de sesión (criptografía simética).

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 < ej(n)que sea coprimo o primo relativo con j(n), es decir, de forma que el máximo común divisor de ej(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).

2.- Y ahora voy intentar ver si los resultados obtenidos me permiten cifrar y descifrar un mensaje (M) con ese par de claves. Hay que recordar lo que he dicho anteriormente sobre criptografía híbrida, es decir, que RSA se utiliza sólo para cifrar la clave de sesión y no para cifrar el texto en claro, porque en la práctica es un sistema mucho más lento que la criptografía simétrica. Por tanto, aunque sería posible cifrar también el propio texto en claro siempre que se transforme previamente la información de éste en un conjunto de números, lo que voy a hacer no pasa de ser un mero ejercicio teórico para ver si lo he comprendido correctamente.

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:

c1 = 17.2257 mod 52.841 = 1.855.
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.

No hay comentarios:

Publicar un comentario