RSA (Justificación matemática)



Antes de nada, pediré disculpas y comprensión por la poca calidad del siguiente texto. Esta baja calidad se debe a que todo lo expuesto en el Hackmeeting fue fruto de la más absoluta y sorprendente (también para el propio autor) improvisación. Considero éste, un documento abierto donde no sólo no está todo bien dicho (espero que las incorrecciones sean pocas) sino que, además, falta mucho por decir.

Correcciones, comentarios y críticas constructivas a topi@phreaker.net



Índice

Criptografía
Criptografía de clave pública
Álgebra modular
Algoritmo de creación de claves
Creación de claves RSA6 y codificación de un mensaje de longitud ridícula
¿Cómo se 'podría' romper RSA?
¿Por qué no se puede romper RSA?




1.- Criptografía

    A diferencia de la criptografía tradicional (o criptografía de clave secreta), en la criptografía de clave pública no existe una única clave con la que codificar y descodificar. Existen dos, cada una de las cuales invertirá el proceso que realize la otra.

    Si entendemos que los mensajes pueden ser codificados como números, por ejemplo, sustituyendo los carácteres por su correspondiente codigo ASCII, podemos equiparar la codificación a una operación matemática simple (com podría ser la multiplicación):

Si el mensaje a transmitir es, por ejemplo, 5
y la clave de codificación es (multiplicar por 3)
entonces el mensaje codificado será 15

como vemos, nadie que no sepa que la clave de decodificación es una multiplicación por 3, podrá deducir que 15 corresponde a 5 (tras la decodificación) y el mensaje podrá viajar seguro por canales inseguros. Por suerte, o por desgracia, el RSA es un poco más difícil que una simple multiplicación, aunque no mucho más.



2.- Criptografía de clave pública

   Ahora expondremos el esquema de un criptosistema de clave pública, que es como sigue:

Alicia crea m
aplica la clave pública de Benito
envía c
Benito recibe c
aplica la clave privada de Benito
obtiene m

m: mensaje en claro (antes de la codificación)
c: mensaje codificado


   La clave pública de Benito que utiliza Alicia, estará disponible para cualquier persona, mientras la privada la conservará Benito (de la manera más segura posible). Los principios citados por Diffie y Hellman, en 1976, aseguran la imposibilidad de deducir la clave privada a partir de la clave pública; esto en el RSA queda garantizado por la imposibilidad de factorizar eficientemente (como se ve en el apartado ¿Por qué no se puede romper RSA?)



3.- Álgebra modular

   Para poder hacer comprensible, posteriormente, el razonamiento que justifica la eficacia del RSA, es necesario que mencionemos unas cuantas definiciones, empezad a quitar el polvo de los viejos libros de matemáticas de EGB (¿quién decía que hay cosas que sólo pertenecen al pasado?). De todos modos, no hacen falta grandes conocimientos matemáticos para entenderlo, muy probablemente si volvéis a este apartado después de leer todo el documento lo veréis mucho más claro.

operación módulo (mod) resto de la división entera entre dos números, es decir, 5 mod 3=2 (ya que 5 dividido entre 3 cabe a 1 y nos sobran 2 unidades como resto)
máximo común divisor (MCD) dados dos números, el MCD es el número más grande que divide de manera entera a los dos
número primo número que no puede ser descompuesto en factores, es decir, sólo es divisible entre 1 y él mismo (el contrario es ‘número compuesto’)
números coprimos dos números son coprimos cuando no tienen factores comunes diferentes de 1, es decir, su MCD es igual a 1 (también se llaman 'primos uno respecto al otro')
Z={···, -1, 0, 1, 2, ···} conjunto de todos los números enteros, sin decimales
Zn={0, 1, 2, ···, n-1} subconjunto de Z, conjunto de números enteros entre 0 y n-1
Z*n subconjunto de Zn, incluye los números menores que n y coprimos con él

Aplicando los conceptos anteriores a números concretos, tendremos:

Z15={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}
Z*15={1, 2, 4, 7, 8, 11, 13, 14}

como se ve los números comunes a Z*15 y Z15 son todos coprimos con 15, el resto no

Así pues, tenemos las siguientes expresiones:

Suma 14 + 27=18 (mod 23) de un modo más simple es como si realizásemos una operación y cuando excedemos n-1, pasamos a 0... una especie de círculo vicioso (porque se repite, no porque tenga vicios, eh!)
Resta 4 - 27=0 (mod 23)
Multiplicación 8 · 27=9 (mod 23)

vemos que si n es un número primo:

Z13={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Z*13={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} como se ve la única diferencia es que el 0 no está

   El indicador de Euler, fi(n), representa la cantidad de números naturales menores o iguales a n y coprimos con n. fi(n) coincide con la cantidad de elementos del conjunto Z*n.

El indicador de Euler tiene las siguientes propiedades:

  1. Si p es un número primo
    fi(p)=p-1
  2. Si p y q son números primos distintos
    fi(p·q)=fi(pfi(q)=(p-1)·(q-1)

Entonces, puesto que en el algoritmo RSA, n es producto de dos números primos se cumplirá la relación fi(n)=(p-1)·(q-1)

   Y sin más preámbulos, citaremos lo que constituye la base teórica del RSA: el Pequeño Teorema de Fermat. Según este teorema dados dos números x y n coprimos entre sí (mira qué son los números coprimos si no lo recuerdas), se cumple que:

ax mod n=1 si MCD(x,n)=1


4.- Algoritmo de creación de claves

   El proceso de creación de claves (a parte de ser EEUU-patentable) es muy simple. Se basa en la correcta elección de dos números primos que permitirán generar otros, con unas características éstos últimos tales que sea mútuamente reversible la transformación hecha por el otro. Antes de empezar a ver el algoritmo, es necesario hacer un apunte (esperemos que obvio): una clave RSA puede tener cualquier longitud (de hecho, y a modo de ejemplo, crearemos una clave RSA6... que no se ría nadie, una clave de 6 bits también es muy digna!)

Paso a paso:

  1. Se generan dos números primos p y q
  2. Se calcula n=p·q
    fi(n)=(p-1)·(q-1)
  3. Se elige un número natural e, perteneciente al conjunto Z*fi(n). Para esto, se generarán valores aleatoriamente hasta que el MCD de e y fi(n) sea igual a 1 (cosa que indicará que e es coprimo con fi(n) y por tanto, perteneciente a Z*fi(n))
  4. Se calcula d, también perteneciente a Z*fi(n) tal que e·d mod fi(n)=1. Este proceso se realiza con un algoritmo llamado 'Algoritmo Extendido de Euclides', cuya explicación queda fuera del alcance de este texto.

   A partir de los datos calculados en el proceso anterior tenemos que el par de números (e,n) es la clave pública y el par (d,n) es la clave privada.



5.- Creación de claves RSA6 y codificación de un mensaje de longitud ridícula

   En este ejemplo, por razones obvias, utilizamos números primos realmente pequeños respecto a los usados en las aplicaciones reales pero que servirán a nuestro propósito de la misma manera; por ejemplo,

p=5 y q=11

de donde

n=p·q=5·11=55

el indicador de Euler,

fi(n)=(p-1)·(q-1)=4·10=40

   Ahora generamos un valor para e que sea primo respecto a fi(n), por ejemplo e=23. Podemos comprobar que 23 no tiene factores comunes con 40, ya que MCD(23,40)=1.

   Usando el Algoritmo Extendido de Euclides calculamos d, que en este caso vale 7, y verificamos que 23·7 mod 40=1.

  Por tanto, tenemos el siguiente par de claves: clave Pública (23,55)
clave Privada (7,55)

   Ahora codificaremos un mensaje, para comprobar visualmente que el RSA no es ningún timo:

Supongamos que el mensaje a codificar es: m=43,

4323 mod 55=26

el valor 26 sería el mensaje codificado para nuestro mensaje original. Nadie (ni siquiera los que hemos codificado el mensaje) podrá recuperar el valor original; sólo lo podrá hacer la persona destinataria que conserva (esperamos que bien escondida) su clave privada.

Pero ahora situémonos en la parte de esta persona destinataria: ¿qué debemos hacer para convertir el valor 26 en el valor original? Pues el mismo procedimiento que antes se ha hecho para codificarlo pero con la clave privada.

267 mod 55=43

Nuevamente la magia de Fermat se muestra ante nuestros incredulos ojos!



6.- ¿Cómo se 'podría' romper RSA?

   Con el objectivo fijo en dar confianza (y confiar) en el algoritmo que garantiza la privacitat a todas las personas con independencia de su extracción social, cultural, política, racial, sexual, etc; estudiemos los pasos necesarios para deducir la clave privada a partir de la clave pública. Como sabemos, la clave pública nos la ofrecen de diferentes modos (servidores de claves, páginas web, correo electrónico, CD-ROM, disquet, papel y boli, etc) para poder comunicar seguramente. Ahora, si fuese posible deducir la clave de decodificación a partir de la de codificación?

Piano, piano... como dirían los compañeros italianos. Los pasos a seguir son tan simples como esto:

  1. Factorizamos n, cosa que nos da acceso a los valores p y q.
  2. A partir de p y q obtenemos fi(n). Notemos que esto se hace del mismo modo que se hacía cuando éramos legítimos creadores de la clave.
  3. Afortunadamente, ahora no tenemos que elegir el valor de la clave pública porque el valor n ya venía acompañado de éste.
  4. A partir de e y fi(n) y utilizando el Algoritmo Extendido de Euclides, encontraríamos d. Nuevamente, notemos que el proceso se hace del mismo modo que se hacía cuando éramos legítimos creadores de la clave.

   Parece evidente que el proceso es, incluso, tan fácil com el de creación de las claves pero... tiene que haber algún problema que explique por qué no se puede romper RSA?


7.- ¿Por qué no se puede romper RSA?

   Como se ha visto, el proceso de creación de claves, la codificación y decodificación son procesos que utilizan operaciones simples (multiplicaciones, números aleatorios, divisiones enteras, etc). Estos procesos se pueden realizar con algoritmos que tienen tiempos de ejecución polinomiales.

Un algoritmo tiene un tiempo de ejecución polinomial cuando en función de su entrada el tiempo en que es ejecutado varía con la relación:

t(n)=a·nb, sean a y b cualesquiera valores constantes

En cambio, un algoritmo tiene un tiempo de ejecución exponencial cuando en función de su entrada el tiempo en que es ejecutado varía con la relación:

t(n)=ab·n, sean a y b cualesquiera valores constantes

Afortunadamente, después de muchos años de mantener a matemáticos trabajando día y noche, todavía no se ha encontrado un algoritmo de factorización que trabaje en tiempo polinomial. Por tanto, con longitudes de clave grandes, mientras el proceso de creación de claves se realiza en pocos minutos (o incluso menos) la factorización requiere muuuuuuuuchos años como se observa en la siguiente tabla (por cierto, como todos los datos, éstos no son diferentes, al pasar de unas manos a otras, nadie puede asegurar que la fuente es fiable... pero bueno, cosas peores se han visto!)

Tamaño de la clave MIPS-año necesarios para la factorización
512 30 000
768 200 000 000
1024 300 000 000 000
2048 300 000 000 000 000 000 000

Nota: Un MIPS-año es la cantidad de cálculo que llevaría a cabo un ordenador capaz de ejecutar un millón de instrucciones por segundo, en un año.

   Haciendo un último intento de sintetizar las dificultades de romper RSA podríamos decir:

'si no hay factorización polinomial/eficiente/barata/rápida, no hay rotura de RSA'