Introduccion a la criptografia, con Python: RSA (II) (original) (raw)

Segunda parte de la series, vamos con el cifrado asimetrico, con el algoritmo RSA

Una cosa... oculte el codigo(solo hay que pulsar los botones) por que sino ocupaba mucho mas el post y era ilegible, ahora si...

¿Que es un cifrado asimetrico? (o de clave publica)

A diferencia de un cifrado "tradicional" simetrico, uno asimetrico usa claves distintas para cifrar y para descifrar el mensaje, la publica y la privada, respectivamente.

[Mensaje]----->[Clave publica]----->[Mensaje cifrado]----->[Clave privada]----->[Mensaje]

La idea es que solo se necesite una clave para todas las transferencias, pues aunque se puede cifrar el mensaje con la clave publica, no se puede descifrar en un tiempo razonable (muuuchos años), para esto se utilizan "funciones trampa", en este caso (RSA), se basa en la dificultad de factorizar numeros primos grandes (de hecho, ya hay un algoritmo que permite romperlo, pero require ordenadores cuánticos [ http://es.wikipedia.org/wiki/Algoritmo_de_Shor ], asi que aun queda bastante tiempo para que sea factible ;) )

Nota: Para usos reales se recomienda una clave de al menos 2048 bits, si lo intentas con esta implementacion mejor que vayas a tomar algo mientras descifra, mejor utiliza alguna libreria, como OpenSSL, de todas formas el codigo es un ejemplo, no lo utilizeis para algo real ;)

Todo el cifrado se basa en los numeros primos, asi que necesitamos una forma para generar grandes numeros primos (y para manejar numeros grandes), esta esta basada en la que se utiliza en GnuPGP [ Sistema de generacion de numeros primos ] :

Generando claves
Ahora vamos con el cifrado, empezemos por generar las claves:

1. Se generan dos numeros primos (p y q):

2. Se obtiene su producto (n):

3. Se calcula la funcion de euler del producto (o el producto de cada numero-1) (phi)

4. Se escoge un numero positivo menor que el valor anterior, coprimo con el (e)

5. Se obtiene un numero (d) que multiplicado por e sea 1 modulo modulo phi:

La clave publica sera:

Siendo e el exponente publico (de cifrado).

Y la privada:

Siendo d el exponente privado (de descifrado).

Una vez hecho esto, hay que guardarlas, normalmente en un archivo, y las claves privadas se suelen cifrar con una clave simetrica (ARC4,AES) para evitar que alguien que acceda al ordenador pueda utilizarlas.

Cifrando y descifrando

Lo primero es convertir el mensaje en un numero, esto se puede hacer simplemente asi:

Para cifrar se toma el numero anterior y se eleva al exponente publico (e), se toma el resultado modulo m (la parte comun de la clave publica y privada):

Para descifrar, se eleva el texto cifrado al exponente privado (d), el resultado otra vez modulo m:

El ultimo paso es volver a convertir el numero a la cadena de carateres:

Un ejemplo:

>>> from rsa import * >>> pub,priv=genkeys(1024) >>> c=cipher("Hola, mundo!",pub) >>> c 183215522837810002107700876969735529389493038469612725641521270049540496303272607832412047089313799446261344625002151478850713512831666391610794754851545494854088049502335086495398269215345855951430580323584979357245922370591677561398443291468057571704494588641900823474912235810200636472311878653680796408805448142892464375376781848071141950146031602419546250920247985212916382049760380405462501755652797147986070890777660883097434217644246926897533470979996434774462080930799214080819242539075626831561500260516129063545191746796195304824471913283515780268359676534982131595723581406851722034274215203834932748601L >>> plain=decipher(c,priv) >>> plain 'Hola, mundo!' >>>

Firmando mensajes:

Ademas de cifrar y descifrar, RSA permite firmar mensajes, el proceso es similar al de cifrado (pero por motivos de seguridad no se debe usar la misma clave para las dos cosas):

A partir del mensaje se genera un hash:

El hash se multiplica por el exponente privado (d) modulo n, el resultado es la firma:

Para comprobar la firma, se siguen los pasos hacia atras:
La firma se multiplica por el exponente publico (e) modulo n:

Si el resultado coincide con el hash del archivo, la firma es correcta

Y ya esta... aqui RSA.py teneis el codigo fuente completo (si lo ejecutais directamente hara unas pruebas para ver si funciona)

[Referencias]
http://en.wikipedia.org/wiki/RSA
http://en.wikipedia.org/wiki/Fermat_primality_test
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
http://www.gnupg.org/documentation/manuals/gcrypt/Prime_002dNumber_002dGenerator-Subsystem-Architecture.html