-[ 0x04 ]-------------------------------------------------------------------- -[ EL ALGORITMO RSA ]-------------------------------------------------------- -[ by Leandro Caniglia ]----------------------------------------------SET-16- Una introduccion al algoritmo RSA por Leandro Caniglia [donado por Stain] [*][*][*][*][*][*][*][*][*][*][*][*] Algunas aclaraciones anted de seguir: [*][*][*][*][*][*][*][*][*][*][*][*] - Hola, soy Stain y les traigo un articulo muy interesante escrito por Leandro Caniglia sobre el algoritmo RSA y algunas cosas mas. - El articulo original esta escrito en PS por lo que algunas cosas fueron medio complicadas de representar (como el simbolo de sumatoria). Para que no quede ninguna duda: m^d -> significa m elevado a la d potencias (p) -> esto es un solo parentesis que cubre las letras p i en forma vertical (i) (ver punto D(E(m)) = m[m^-t]^[(p-1)(q-1)] mod pq -> significa D(E(m)) igual a m por m elevado a la -t y todo eso elevado a la (p-1)(q-1), luego mod pq Se sabe que un numero no se eleva a la mod algo. Es decir que m^d mod c no significa que m este elevado a la "d mod c" sino solo a la "d". Cualquier duda o si piensan que debe haber algun error al pasarlo a Ascii (nadie es perfecto), busquen el archivo original en PostScript de este articulo en la Web de SET. Nos vemos, Stain -------------------------------------------------------------------------------- 1.0 La Magia 2.0 El Algoritmo de Euclides 3.0 Un teorema de Fermat 4.0 Euclides + Fermat = RSA 5.0 Un ejemplo concreto 6.0 Apendice A. La otra version del Algoritmo de Euclides 7.0 Apendice B. Una demostracion del Teorema de Fermat 7.1 Lema 7.2 Teorema (Fermat) 7.3 Corolario 7.4 Teorema (Una variante usada por el RSA) 8.0 Apendice C. Potencias modulares 9.0 Apendice D. Demostracion del funcionamiento del RSA 1. La Magia Ni bien empezamos a introducirnos en el mundo que PGP pone al alcance de todos leemos la siguiente aclaracion: "Neither volume explains the underlying technology details of cryptographic algorithms and data structures." Con esta oracion, extraida del primer volumen del manual, el autor del PGP nos advierte que la documentacion que acompa¤a al programa no entra en explicaciones sobre los detalles tecnicos de los algoritmos y las estructuras de datos utilizadas. Con el correr del tiempo cada vez nos vamos acostumbrando mas a usar cosas que en realidad no comprendemos y nos resulta natural y para nada chocante pasar por alto aspectos tecnicos que, comparados con lo impresionante de los resultados visibles, suenan innecesarios y aburridos cuando no inalcanzables. Magicamente los programas funcionan o dejan de funcionar; en algun lugar alguien esta programando un virus; otro intenta quebrar las barreras de seguridad de una computadora de la NASA; alguno inventa un nuevo algoritmo de encriptacion; etc, etc. Es decir, hay otra gente trabajando por nosotros, es como si la magia de estos tiempos viniera con certificado de garantia. Para colmo, sabemos por experiencia que cuando un mago nos revela su truco, sufrimos una desilusion. La llamada tecnologia de la "clave publica-clave privada" se basa en un algoritmo conocido como RSA (por Rivest-Shamir-Adleman). En su forma mas pura este algoritmo combina resultados provinientes de la matematica, mas precisamente de la Teoria de Numeros. Cualquiera que haya estudiado un primer curso de Algebra esta en condiciones de entender el funcionamiento del algoritmo. Deciamos que el RSA utiliza resultados de la Teoria de Numeros, cuales?, simplemente dos: un algoritmo debido a Euclides y un teorema debido a Fermat. En las secciones que siguen vamos a dar las ideas centrales de este algoritmo criptografico en el que se basa el PGP. Creo que ese lado oscuro de los detalles tecnicos no es menos colorido que el de los resultados espectaculares. 2. El Algoritmo de Euclides El Algoritmo de Euclides es, en el sentido moderno del termino, el primer algoritmo de la historia. Tengamos en cuenta que estamos hablando de alguien que vivio en Grecia entre 450 y 377 (AC). Resulta que el sistema de numeracion que utilizaban los griegos era, por lo primitivo, poco propicio para hacer cuentas, incluso aquellas que solamente involucraban las operaciones mas elementales de suma, resta y multiplicacion. Ni hablar de la division. Para Euclides era fundamental contar con procedimientos de calculo que le insumieran la menor cantidad posible de cuentas, porque cada cuenta le llevaba mucho tiempo. Euclides conocia la nocion de minimo divisor comun entre dos numeros. Muchas veces necesitaba calcular el entero mas grande que dividiera exactamente a dos numeros dados. Para resolver este problema fue que dise¤o su famoso algoritmo. Lo increible del asunto es que este algoritmo es tan bueno que lo seguimos utilizando hoy en dia, incluso lo utilizan internamente los programas de computadora cuando necesitan calcular estos divisores comunes maximos como es el caso del PGP. Recordemos primero la nocion de divisor comun maximo de dos numeros. Los divisores de un numero entero son aquellos numeros enteros que lo dividen exactamente; esto es, el resto de la division entera de un numero por uno de sus divisores es cero. El maximo divisor comun entre dos numeros es entonces el entero mas grande que divide (exactamente) a ambos numeros. Por ejemplo Los divisores de 36 son 1, 2, 3, 4, 6, 9, 12, 18, 24 y 36. Los de 20 son 1, 2, 4, 5, 10 y 20. Los divisores comunes son 1, 2 y 4. El mas grande de los divisores comunes a 36 y 20 es por lo tanto 4. Digamos tambien que dos numeros son coprimos cuando su maximo divisor comun es igual a 1. Euclides dio dos versiones de su algoritmo. La primera version simplemente calcula el maximo divisor comun de dos numeros a y b. Funciona del siguiente modo: [Division] 1. Calcule r como el resto de la division de a por b. [Fin?] 2. Si r=0, fin del algoritmo; respuesta en b. [Intercambio] 3. Redefina a:= b, b:= r. [Vuelta] 4. Vuelva a 1. Si lo aplicamos al caso a = 36, b = 20 las sucesivas divisiones son: |a |b |cociente|resto r| |--|--|--------|-------| |36|20| 1 | 16 | |20|16| 1 | 4 | |16| 4| 4 | 0 | Como vemos, a la salida del algoritmo, -b- contiene el valor de maximo divisor comun. Dijimos que Euclides dio dos versiones de su algoritmo. La segunda introduce dos variables mas, las llamaremos s y t. Lo que hace esta version del algoritmo es calcular valores para las variables s y t de modo que el maximo divisor comun entre a y b se pueda calcular como: s x a + t x b Por ejemplo, para a = 36 y b = 20, los valores de s y t que resultan son -1 y 2: (-1) x 36+2 x 20 = 4 Los detalles de esta version del Algoritmo de Euclides los damos en un apendice. 3. Un Teorema de Fermat Pierre Fermat vivio en Francia entre 1601 y 1665. Aunque estudio derecho y trabajo como Consejero del Parlamento, se ha convertido en uno de los matematicos mas famosos de la historia. Los origenes del calculo infinitesimal diputado por Leibniz y Newton se encuentran en trabajos suyos. La memoria de Leibniz sobre calculo diferencial fue publicada cinco a¤os mas tarde que las memorias postumas de Fermat en donde estan esos trabajos que Leibniz habia leido. Poca gente conoce estos y otros hechos sorprendentes que revelan la verdadera importancia de sus aportes cientificos. Por ejemplo, Fermat, encontro las leyes de la refraccion de la luz y compartio con Pascal la creacion del Circulo de Probabilidades. Sin embargo la fama de Fermat se debe a un teorema suyo de 1637 cuya dilucidacion se ha erigido en un verdadero desafio; por mas de tres siglos y medio el llamado "Ultimo Teorema de Fermat" resistio los esfuerzos que una multitud de matematicos le dedicaron sin exito. Fermat estaba revisando la obra de Diofanto de Alejandria, un matematico del siglo IV, cuando encontro un problema que tenia relacion con el Teorema de Pitagoras: el problema proponia encontrar todos los triangulos rectangulos cuyos lados tuvieran medidas expresadas por numeros enteros. Teniendo en cuenta que en un triangulo rectangulo la suma de los cuadrados de dos catetos es igual al cuadrado de la hipotenusa, el problema se podia reformular como la resolucion completa de la ecuacion: x^2 + y^2 = z^2 cuando las variables x, y, z toman valores enteros. A proposito de este problema, Fermat se pregunto si un cubo se podria expresar como suma de dos cubos y mas generalmente si una potencia cualquiera podria ser escrita como suma de dos potencias del mismo grado. La respuesta que el mismo Fermat dio a estas preguntas fue negativa. En el margen del libro de Diofanto escribio en latin: "Cuburn in duos cubos aut quadrato-quadratum in duos quadrato-quadratos et nullam inifinitum, ultra quadratum, potestatem in generalister duas ejusdem nominis fas est dividere. Cujus rei demostrationem, mirabilem sane, detexi; hane marginis xiguitas non caperet." Lo que significa: "No es posible dividir un cubo en dos cubos, un bicuadrado en dos bicuadrados y de manera general, una potencia cualquiera de exponente superior a dos en dos potencias de la misma especie. He descubierto una demostracion bastante notable de esta proposicion, pero no cabria en este margen." Hasta el dia de hoy este enunciado no se ha podido demostrar. Los esfuerzos hechos han sido formidables. El estudio de este problema ha dado origen a teorias completas en algebra y teoria de numeros. Pero el resultado de Fermat que nos interesa ahora es otro. Fermat descubrio que para cualquier numero natural m, la diferencia m^p-m es divisible exactamente por p, si p es un numero primo. Una variante de este teorema tiene relacion con el algoritmo RSA que nos ocupa. La variante dice que si p y q son dos primos distintos entre si y m es un numero natural cualquiera, coprimo con p y con q, la diferencia m^(p-1)(q-1)-1 es divisible exactamente por el producto pq. En la seccion siguiente vamos a volver sobre este teorema. 4. Euclides + Fermat = RSA El algoritmo RSA tiene dos partes: la encriptacion y la desencriptacion. El nudo de la cuestion se basa en elegir dos numeros primos p y q suficientemente grandes y formar el producto n = p x q Cuanto mas grandes sean estos numeros mas dificil va a ser encontrarlos a partir de n. El proceso de calcular p y q dado n se llama factorizacion. Existen modernos algoritmos de factorizacion, sin embargo tienen un problema: no son eficientes cuando n es un numero grande. Para dar una idea, digamos que si los primos p y q tiene aproximadamente 100 cifras cada uno, entonces los algoritmos conocidos tardarian mas de mil a¤os en factorizar el numero n. Es justamente este problema, la dificultad en encontrar la factorizacion, el que aprovecha el RSA como veremos a continuacion. La clave publica es un par (c, n); la clave privada es un par (d, n). Los numeros c, d y n son naturales, y n es el mismo en las dos claves e igual al producto p x q. Cada mensaje se puede representar mediante un entero m entre 0 y n - 1. Esta transformacion de un mensaje en un numero entero impone una limitacion en la longitud del mensaje original; sin embargo, un mensaje largo podria romperse en varios mensajes mas cortos, cada uno de ellos en correpondencia con un entero menor que n. Las funciones E de encriptacion y D de desencriptacion se definen como sigue: E(m) = m^e mod n = C D(C) = C^d mod n La cuestion fundamental es la eleccion de las claves de encriptacion y desencriptacion e y d. El valor de d se lo elige al azar, como un numero coprimo con el producto (p-1)(q-1). Esto es, d no tiene divisores en comun con p-1 ni con q-1. El entero e se calcula a partir de p, q y d mediante el Algoritmo de Euclides. Lo que se hace es aplicar dicho algoritmo a las entradas d y (p-1)(q-1). Ese algoritmo devuelve dos enteros s y t tales que: sd + t(p-1)(q-1) es el maximo divisor comun entre d y (p-1)(q-1). Pero debido a que d se lo eligio coprimo con (p-1)(q-1), resulta que el maximo divisor comun es igual a 1. Es decir: sd + t(p-1)(q-1)= 1 Es importante tener en cuenta que aunque n es publicamente conocido, los primos p y q no lo son. La dificultad inherente a la factorizacion hace imposible que existan algoritmos eficientes para calcular p y q partiendo de n. Por este motivo resulta practicamente imposible calcular el valor de d aun conociendo el de e y el de n. La idea completa del algoritmo es la siguiente. Primero el mensaje a encriptar se transforma en un numero m menor que n. La clave de encriptacion (e; n) es publica y por lo tanto el mensaje se encripta tomando el resto de la division de m^e por n. El resultado obtenido, que llamaremos C es el mensaje encriptado, este es el que se transmite al destinatario. Si se mantiene en secreto la clave de desencriptacion d (y los valores de los primos p y q), solamente la persona que conozca esa clave va a poder recuperar el mensaje original m a partir de C. Lo que va a tener que hacer es calcular el resto de la division entera de C^d por n. Y como sabemos que al hacer esta cuenta vamos a obtener nuevamente m? Respuesta: por el Teorema de Fermat. Una vez que uno ha comprendido el funcionamiento del RSA, puede entender tambien su propiedad de autentificacion. Si Juan recibe un mensaje supuestamente encriptado con la clave secreta de Pedro, entonces para autentificarlo Juan solamente tiene que aplicarle la clave publica de Pedro. Si lo desencripta, el mensaje era efectivamente de Pedro, si no lo desencripta, no lo es. Esto se debe a que los algoritmos de encriptacion y desencriptacion son inversos uno del otro y una clave sirve para desencriptar lo que la otra ha encriptado. 5. Un ejemplo concreto Vamos a ilustrar el funcionamiento del RSA en un ejemplo concreto. Para simplificar los calculos vamos a tomar dos primos chicos: p = 5 y q = 11. El producto nos da n = 55. Ahora calculamos (p - 1)(q - 1) y obtenemos 4 x 10 = 40. Para la clave e podemos elegir cualquier numero coprimo con 40, por ejemplo e = 3. Ahora aplicamos el Algoritmo de Euclides para calcular la clave de desencriptacion. Siguiendo los detalles del Apendice A encontramos: 27 x 3 + (-2) x 40 = 1 Por lo tanto d = 27. Esto significa que para encriptar un numero m tenemos que calcular: E(m) = m^3 mod 55 y para desencriptar un mensaje cifrado C: D(C) = C^27 mod 55 Vamos a tomar un mensaje muy corto: mensaje "M" Si numeramos las letras A, B, C, D, ... de 1 en adelante, a la letra "M" le va a corresponder 13. Luego, para encriptar "M" calculamos: E(13) = 13^3 mod 55 = [(169 mod 55)(13 mod 55)] mod 55 = (4 mod 55)(13 mod 55) mod 55 = 52 mod 55 = 52 Y en lugar de enviar 13, enviamos el valor encriptado 52. E1 receptor, si conoce la clave de desencriptacion d = 27, tiene que calcular: D(52) = 52^27 mod 56 Al hacerlo va a obtener como resultado 13. En un apendice damos un algoritmo para hacer estas cuentas en forma eficiente. 6. Apendice A. La otra version del Algoritmo de Eulides El siguiente algoritmo, debido a Euclides, toma como entradas dos enteros no negativos A y B, B no puede ser igual a 0. A la salida devuelve otros dos enteros s y t tales que sA + tB es el maximo divisor comun entre los valores originales de A y B. El algoritmo tambien devuelve el valor del maximo divisor comun en una variable b. [Inicializacion] 1. a := A; b := B; s := 0; t := 1; s':= 1; t':= 0. [Division] 2. q := a div b; r := a mod b. [Fin?] 3. Si r = 0, fin del algoritmo. [Actualizacion] 4. u := s; s := s' - uq; s':= u. u := t; t := t' - uq; t':= u. a:=b; b:=r. [Vuelta] 5. Vaya a 2. La demostracion de que el algoritmo funciona se debe a que al ingresar al paso 2 (Division), siempre se verifican las siguientes relaciones: i) b = sa + tb ii) a = s'a + t'b iii) mdc(a; b) = mdc(A; B) Por eso, cuando se produce la condicion de fin, r = 0, el valor de b al dividir a es igual al mdc(A; B). 7. Apendice B. Una demostracion del Teorema de Fermat 7.1 Lema Si p es un numero primo y i es un entero positivo menor que p, entonces el numero combinatorio (p) es divisible por p. (i) DEMOSTRACION. Por induccion en i. Caso i = 1. Es trivial porque (p) = p (1) Paso inductivo. Supongamos que (p) es divisible por p y probemos que en ese (i) caso ( p ) cambien lo es cuando i + 1 es menor que p. (i+1) Es facil comprobar que: ( p )(i+1) = (p)(p-i) (i+1) (i) Por la hipotesis inductiva, p divide al miembro derecho. Por lo tanto divide al miembro izquierdo. Pero como i + 1 < p y p es primo, ambos numeros resultan coprimos. Por lo tanto p debe dividir a ( p ) (i+1) 7.2 Teorema (Fermat) Si p es un numero primo, cualquiera sea d entero m, la diferencia m^p - m es divisible por p. DEMOSTRACION. Por induccion en m. Caso m = 1. Es trivial puesto que 1^p - 1 = 0 y 0 es divisible por p. Paso inductivo. Supongamos que el resultado es cierto para m y probemoslo para m + 1. Aplicando la formula del binomio tenemos __p__ \ (m+1)^p = \ (p) m^i / (i) /____ i=0 __p-1_ \ = 1 + \ (p) + m^p / (i) /____ i=0 Restando m + 1, __p__ \ (m+1)^p - (m + 1) = \ (p) + (m^p - m) / (i) /____ i=0 Por la hipotesis inductiva vemos que seria suficiente demostrar que la sumatoria es divisible por p, pero eso es cierto porque cada numero combinatorio es divisible por p en virtud del Lema anterior. 7.3 Corolario Si p es un numero primo y m es coprimo con p, entonces la diferencia m^p-1 - 1 es divisible por p. DEMOSTRACION. Por el teorema m(m^p-1 - 1) = m^p - m es divisible por p. Como m y p son coprimos, debe ser m^p-1 - 1 divisible por p. 7.4 Teorema (Variante usada por el RSA) Si p y q son dos numeros primos distintos y m es un entero coprimo con p y con q, la diferencia m^(p-1)(q-1) - 1 es divisible por el producto pq. DEMOSTRACION. Es suficiente demostrar que la diferencia es divisible por p y por q. Por razones de simetria basta demostrar que la diferencia es divisible por p porque un razonamiento analogo demostraria que es divisible por q. Como m^[(p-l)(q-l)] = [m^(q-l)]^(p-1), por el corolario anterior, aplicado a m^(q-1) en lugar de m tenemos que [m^(q-1)]^(p-1) - 1 es divisible por p, como queriamos demostrar. 8. Apendice C. Potencias modulares El siguiente algoritmo se puede usar para calcular C = m^e mod n. Los algoritmos que usa el PGP son mas eficientes, pero incluimos este solo a titulo ilustrativo. [Inicializacion] 1. i := 0; C := 1 [Fin?] 2. Si i = e, fin del algoritmo [Multiplicacion] 3. C := C . m mod n [Avance] 4. i := i + 1 [Vuelta] 5. Vaya a 2 9. Apendice D. Demostracion del funcionamiento del RSA Si los enteros e, d y n se eligen como indicamos en la descripcion del algoritmo, entonces todo m < n verifica: D(E(m)) = m y E(D(m)) = m Por razones de simetria es suficiente demostrar la primera de estas igualdades porque un razonamiento analogo demostraria la segunda. D(E(m)) =D(m^e mod pq) =(m^e mod pq)^d mod pq = m^ed mod pq Ahora, de la relacion ed + t(p - 1 )( q - 1 ) = 1 obtenemos ed = 1 - t(p - 1 )( q - 1 ) Aclaremos que si e y d los elegimos positivos, entonces t va a ser negativo; es decir -t es un numero positivo. Ahora: D(E(m)) = m m^[(-t)(p-1)(q-1)] mod pq = m[m^-t]^[(p-1)(q-1)] mod pq = m . 1 mod pq = m mod pq = m En la tercera igualdad hemos usado el Teorema de Fermat aplicado a m^-t en lugar de m y en la ultima el hecho de que m es menor que pq. Stain ..FINALE..