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
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?
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.
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?)
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:
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:
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:
| Se calcula | n=p·q |
| fi(n)=(p-1)·(q-1) |
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.
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,
de donde
el indicador de Euler,
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,
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.
Nuevamente la magia de Fermat se muestra ante nuestros incredulos ojos!
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:
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?
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:
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:
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 |
Haciendo un último intento de sintetizar las dificultades de romper RSA podríamos decir: