Damián Miércoles 18 de Octubre del 2006

Este es el primer artículo de tres artículos que serán publicados con la finalidad de explicar de una manera general el fundamento matemático del sistema criptográfico RSA. La finalidad de esto es que cualquiera pueda hacer una implementación correcta y segura de este criptosistema en el lenguaje de programación que prefiera sin temor a equivocarse.

Si alguien necesita alguna demostración de los teoremas que se enunciarán aquí porque no puede dormir consulte un libro de teoría de números. A partir de este momento todo lo que se diga está referido a los números enteros.

Primero se van a definir varios conceptos y se van a mostrar resultados importantes para familiarizar al lector con la teoría de números, al final de la saga de artículos se mostrará el algoritmo del sistema RSA.

Nota: i.e. se lee como “es decir”.

Introducción

Este algoritmo fue publicado en 1977 por Ron Rivest, Adi Shamir y Len Adleman del MIT, su fortaleza se basa en que no existe un algoritmo eficiente que pueda encontrar los factores primos de un número entero cualquiera (en el último artículo se verá exactamente en donde se usa esto), así que en las implementaciones reales de este algoritmo se usan números muy pero muy grandes para propiciar que la factorización sea muy tardada. Aunque finalmente se podrá hacer la factorización con una computadora lo que se busca es que, para cuando se termine de factorizar, la información que contenía el mensaje ya sea obsoleta (este es el principal objetivo de la criptografía, ya que de ninguna manera se puede idear un método tal que no exista un método inverso).

La aproximación matemática al algoritmo se hace con el fin de familiarizar al lector con la notación y algunos resultados de teoría de números para que sea capaz de entender otros algoritmos criptográficos que se basen en ese conocimiento (y son bastantes).

Cabe señalar que todo “certificado seguro” para Web hace uso de RSA, así como SSH, SSL y casi todo tipo de comunicación segura en medio electrónicos. Normalmente no es transparente el uso de este algoritmo porque sería muy complicado que todos manejaran los conceptos, operaciones y tamaños de las claves que implica, por lo que el proceso pasa oculto y automatizado cuando se requiere un servicio de los antes mencionados.

Divisibilidad

Def. Se dice que a divide a b y se denota a|b si existe un número entero c tal que
ac = b. (i.e. b es múltiplo de a)

Ejemplos sencillos de esto es -1|9, 5|12785, 0|0, -19123783|0, etc…

Números Primos

Def. Un número entero p se dice que es primo si es distinto de cero y sus únicos divisores son los elementos del conjunto {1,-1,p,-p}. (i.e. que ningún otro número que no sea él mismo lo divide)

Notación. a⧷b denota que a no divide a b (i.e. no existe un número entero c tal que ac=b o b no es un múltiplo de a).

Ejemplo: 3⧷23

Para demostrar que no existe c tal que 3c=23 se supone que sí existe y luego se llega a una contradicción con el teorema fundamental de la aritmética. El teorema fundamental de la aritmética es muy importante pero no será necesario que lo conozcan para llegar a donde queremos llegar.

Máximo Común Divisor

Consideremos todos los números enteros que dividen a unos ciertos números a y b, ahora tomemos el elemento máximo de ese conjunto (que a fuerza es positivo ya que al menos está el 1 que divide a todos los números), ese es exactamene el máximo común divisor de a y b.

Notación. El máximo común divisor de dos números a y b se denota (a,b).

Def. Se dice que d es el máximo común divisor de a y b (i.e. d = (a,b)) si d es un número natural que cumple:

1. d|a y d|b (i.e. d divide a los dos números)
2. si c|a y c|b entonces c|d (i.e. que para todo número que sea común divisor de a y b entonces ese divisor común divide al máximo común divisor)

Esta definición es equivalente con la definición inutuitiva y nos proporciona una información que normalmente no se enseña sobre comunes divisores de dos números, que es el inciso (2).

Def. Si (a,b) = 1 se dice que a y b son primos relativos.

Notación. El mínimo común múltiplo de dos números a y b se denota [a,b].

Teorema. ab = (a,b)[a,b]

Este teorema no viene al caso para el RSA pero quizá alguien algún día lo ocupe para evitarse hacer muchas cuentas.

Imagínemos que nos piden ociosamente calcular el [5478,63343], entonces a ojo de buen cubero (jajaja) nos damos cuenta que (5478,63343)=1, entonces por el teorema anterior deducimos que [5478,63343] = 5478*63343. ¿A poco no es más fácil que hacer la clásica tablita?

Continuará…

• Seguridad en Información
•