Tomas Bradanovic

NULLA DIES SINE LINEA. Filosofía barata, historias, historietas, mecánica, moralejas, chamullos, relatos absurdos, la vida de un vago, cosas de Arica, literatura, música, pornografía, política, física, cocina regional, minas, copete y cosas por el estilo. The awesome, absurd and often bored adventures of our Man of Mistery in Arica, from the trenches, in the Northern Front. Sacar a mil, sacar a mil. Streams of brilliance often springs from boredom. Atendido por su propio dueño, dentre nomás.

El algoritmo RSA para dummies

jueves, 22 de noviembre de 2012


Descomponer un número en sus factores primos es el dolor de cabeza de todo estudiante de primaria, porque no existe un procedimiento fijo (receta, algoritmo) para hacerlo. Recordemos que los números primos solo son divisibles por 1 o por si mismos, por ejemplo 2, 3, 5, 7, 11, 17. En cambio números como 4 (2x2), 12 (2x3x2) etc. no son primos. Como no hay receta fija para encontrar los factorees primos, solo se pueden usar métodos de aproximación sucesiva o sea prueba y error. Con los años esta dificultad adquirió una enorme importancia al convertirse en la base de casi todos los métodos modernos de cifrado conocidos como "de clave pública".

Encontré en la web del Clay Mathematics Institute esta extraordinaria explicación del algoritmo RSA, el más usado en el mundo para encriptar con clave pública. La explicación es simple, fácil de entender y por eso la traduje y la copio a continuación:

RSA asume que hay alguna forma de convertir las letras y símbolos en números y viceversa. Esto lo podemos hacer usando una tabla de conversión como la que se muestra arriba (tabla ASCII), donde A corresponde a 11, B a 12, etc. Por ejemplo la palabra Attack! Sería transformada en 115656373947.

Luego de convertir la palabra en un número entero, encriptar y desencriptar se convierte en un asunto de cálculo simple entre grandes números enteros. 

Sean p y q dos números primos muy grandes, se multiplican obteniendo
N = pq.

Sea e un entero positivo que no tenga factores en común con (p-1)(q-1).

Sea d un entero positivo tal que ed - 1 es divisible por (p-1)(q-1).

Y sean:
f(x) = x^e mod N (esto significa "divida N por  x^e y tome el resto") 
g(x) = x^d mod N (idem)

Use f(x) para encriptar y g(x) para desencriptar.

e es elmensaje encriptado, N es la clave pública que cualquiera puede conocer y puede usarse para encriptar un mensaje, en cambio d es el mensaje desencriptado. p y q son la clave privada que solo conoce el destinatario y le sirve para desencriptar el mensaje.

¿Por que el RSA es tan difícil de romper? Pensemos que hace Alice para recibir mensajes secretos. Primero genera los grandes números primos p y q, luego escoge e. Finalmente resuelve la ecuación para encontrar d:
ed + (p-1)(q-1)y = 1

Donde todas estas variables son números enteros. Alice publica e y N. Es todo lo que necesita para que cualquiera le envíe mensajes secretos.

Ahora veamos al malvado Bob que conoce N y quiere desencriptar los mensajes de Alice. Para esto necesita conocer los factores de N, p y q de modo de resolver la ecuación. Luego resuelve la ecuación para encontrar d, lo que equivale a desencriptar el mensaje de Alice. El problema es que para factorizar (o sea encontrar p y q que multiplicados hacen N) le tomaría una enorme cantidad de tiempo computacional -para valores de p y q suficientemente grandes- podría tomar millones de años con el conocimiento y tecnologías actuales.

Notas de C.M.I.
El hecho que g deshace lo que f  hace, es decir g desencripta mensajes encriptados por f, es consecuencia del pequeño teorema de Fermat

"Si a no es divisible por p, donde p es primo, entonces (a^(p-1))-1 es divisible por p." 

Fermat (1605-1661) fue un matematico francés que fundó la teoría de los números. Ver referencias históricas sobre el último teorema de Fermat. Alrededor de 1630 Fermat escribió al margen de su copia de la Aritmethica de Diophantus que el tenía una prueba maravillosa del hecho que la ecuación x^n + y^n = z^n no tenía soluciones en los enteros positivos para n>2. Esto fue probado 360 años después por Andrew Wiles, en 1993.

Nota mía:
La belleza y popularidad del RSA está en que es simple, se basa en un problema matemático que cualquier alumno de secundaria puede entender y por eso hay mucha más gente en condiciones de tratar de quebrarlo. Su rival es la encriptación de curvas elípticas que se basa en matemáticas mucho más complicadas, por lo que tiene el inconveniente del ser "magia negra" para mucha gente, que la hace menos accesible y menos confiable.

Tuve la suerte de escuchar la historia de la competencia entre RSA y curva elíptica contada por el mismísimo inventor de esta última, el doctor Neal Koblitz que fue uno de los expositores del curso Information Security and Risk Management in Context, todo gracias a Coursera.

También gracias al curso de criptografía entiendo por que se usa  x^e mod N para encriptar, el mod permite hacer la operación XOR que tiene ciertas propiedades "magicas" en términos de encriptación, que hacen imposible aplicar análisis estadísticos para romper el código. No estoy seguro que el mod implique una operación XOR, es una idea mía nomás porque todas las encriptaciones modernas incluyen XOR en algún lado.

En fin, alguno de estos días reemprenderé la tarea de escribir de nuevo mi curso de seguridad informática y criptografía, tengo muchísimos conocimientos nuevos gracias a los cursos online que he tomado, solo tengo que vencer mi irresistible flojera y empezar.

4 Comments:

Anonymous Anónimo said...

Con monitos es mas facil.
http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/ejmrsa.html

22 de noviembre de 2012, 06:18

 
Blogger Tomas Bradanovic said...

jaja ta buena, pero es mejor la explicación general porque permite entender las cosas fundamentales del RSA que lo hacen fuerte. El ejemplo con números solo muestra como funciona pero no por que funciona y cual es la dificultad para quebrarlo.

22 de noviembre de 2012, 09:13

 
Anonymous Anónimo said...

Totalmente de acuerdo, pero fueron los monitos los que me hicieron "volver" a su explicacion e indagar el "por
que". Muy entretenido y bien explicado, Don Tomás. Ademas,
si no fuera por Ud. a uno jamas se le ocurriria indagar sobre estos temas, a pesar de usar esto a cada rato.

22 de noviembre de 2012, 13:59

 
Blogger Tomas Bradanovic said...

Si y con números es más fácil ver como funciona. Lo importante es que la implementación de estos métodos está repleta de problemas de seguridad así es que ni soñar con escribir uno mismo un código para encriptar, ni siquiera en un algoritmo sencillo como el RSA. Siempre hay que usar bibliotecas que estén bien establecidas y hayan pasado las pruebas del tiempo.

Lo más sorprendente de todo es que han pasado más de 20 siglos y todavía nadie ha encontrado un algoritmo general que permita descomponer cualquier entero en sus factores primos. Tal como el último teorema de Fernat que se demoraron más de 360 años en demostrarlo, la matemática al revés de la ciencia avanza a paso de tortuga.

22 de noviembre de 2012, 14:37

 

Publicar un comentario

<< Home

Entradas antiguas Entradas nuevas