SET 39 Call For Papers

¿Eres un hacker? Si deseas pasar a formar parte de la historia del hacking hispano, colabora con la próxima edición de SET 39 enviándonos un artículo. No esperes más, esta es tu oportunidad de demostrar lo que sabes. Ayúdanos a construir una revista de hackers para hackers. SET Staff

SET 16

109231 visitas

El algoritmo RSA

      7062

Autor: Leandro Caniglia
-[ 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 <stain@iname.com>

..FINALE..