Código para llevar

jueves, 22 de abril de 2010

Introduccion a la criptografia, con Python: MD5 (III)

Siguendo con el tema, en esta parte veremos como funciona la funcion de hash MD5:

¿Que es una funcion HASH?

En informática, Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo. [Wikipedia]

Es decir, es una funcion de un solo sentido (a partir del resultado no se puede recuperar el original) que identifica un "objeto" con precision, si cambia un byte, cambia todo el resultado.

Esto se suele utilizar (por ejemplo) para comprobar que las descargas se realizaron correctamente, comparando el hash del archivo original y el del archivo descargado, si son iguales, todo fue bien :)

MD5 es una funcion de hash, pero presenta debilidades, como colisiones, por eso se deberia evitar usar en el futuro, de todas formas, aun se utiliza y servira de introduccion para este tipo de funciones.
Vamos alla...

class md5:
    def __init__(self,s):

        ln=len(s)*8
        self.padd(s)

        self.attach_len(ln)
        self.buff_init()
        self.update(ln)

        self.final()

El primer paso es añadir un bit '1' a lo que se quere hashear, y despues añadir '0's hasta que el tamaño en bits sea igual a 448, siendo modulo 512 (o 56, modulo 64, en bytes):

    def padd(self,s):

        self.stream=s+"\x80"
        while ((len(self.stream)%64)!=56):

            self.stream+="\x00"

Despues hay que añadir a continuacion el tamaño en bits (al principio, antes del paso anterior) del archivo/mensaje/etc..., con un numero de 64 bits(8 bytes):

    def attach_len(self,ln):
        ln%=1<<64
        i=7

        l=[]
        while i>=0:
            k=256**i

            aux=ln/k
            l.append(aux)
            ln-=aux*(k)

            i-=1
        while len(l)>0:
            self.stream+=chr(l.pop(len(l)-1))

Se inicializan cuatro buffers (A,B,C y D) (de 32 bits) que se utilizan en el algoritmo:

    def buff_init(self):
        self.a = 0x67452301
        self.b = 0xefcdab89
        self.c = 0x98badcfe
        self.d = 0x10325476

Se procesa el objeto/archivo/..., esto es la parte mas "opaca" del algoritmo...
Para comenzar se divide el objeto en partes de 64 bytes, concretamente en arrays de 16 elementos, con 4 bytes cada uno:

    def update(self,ln):

        i=0

        while i<(len(self.stream)/64):
            j=0

            x=[]
            while j<16:
                t=((ord(self.stream[(i*64)+(j*4)+0]))|

                 (ord(self.stream[(i*64)+(j*4)+1])<< 8)|

                 (ord(self.stream[(i*64)+(j*4)+2])<< 16)|

                 (ord(self.stream[(i*64)+(j*4)+3])<< 24))

                x.append(t)
                j+=1
            self.transform(x)

            i+=1

Despues, con cada division se obtienen los valores de los buffer's:

    def transform(self,x):

        AA=self.a
        BB=self.b
        CC=self.c

        DD=self.d

Y se le aplican una serie de transformaciones (veremos despues en detalle como funcionan esas transformaciones):

        #Ronda 1
        AA=FF (AA, BB, CC, DD, x[ 0], S11, 0xd76aa478) # 1

        DD=FF (DD, AA, BB, CC, x[ 1], S12, 0xe8c7b756) # 2

        CC=FF (CC, DD, AA, BB, x[ 2], S13, 0x242070db) # 3

        BB=FF (BB, CC, DD, AA, x[ 3], S14, 0xc1bdceee) # 4

        AA=FF (AA, BB, CC, DD, x[ 4], S11, 0xf57c0faf) # 5

        DD=FF (DD, AA, BB, CC, x[ 5], S12, 0x4787c62a) # 6

        CC=FF (CC, DD, AA, BB, x[ 6], S13, 0xa8304613) # 7

        BB=FF (BB, CC, DD, AA, x[ 7], S14, 0xfd469501) # 8

        AA=FF (AA, BB, CC, DD, x[ 8], S11, 0x698098d8) # 9

        DD=FF (DD, AA, BB, CC, x[ 9], S12, 0x8b44f7af) # 10

        CC=FF (CC, DD, AA, BB, x[10], S13, 0xffff5bb1) # 11

        BB=FF (BB, CC, DD, AA, x[11], S14, 0x895cd7be) # 12

        AA=FF (AA, BB, CC, DD, x[12], S11, 0x6b901122) # 13

        DD=FF (DD, AA, BB, CC, x[13], S12, 0xfd987193) # 14

        CC=FF (CC, DD, AA, BB, x[14], S13, 0xa679438e) # 15

        BB=FF (BB, CC, DD, AA, x[15], S14, 0x49b40821) # 16

        # Round 2
        AA=GG (AA, BB, CC, DD, x[ 1], S21, 0xf61e2562) # 17

        DD=GG (DD, AA, BB, CC, x[ 6], S22, 0xc040b340) # 18

        CC=GG (CC, DD, AA, BB, x[11], S23, 0x265e5a51) # 19

        BB=GG (BB, CC, DD, AA, x[ 0], S24, 0xe9b6c7aa) # 20

        AA=GG (AA, BB, CC, DD, x[ 5], S21, 0xd62f105d) # 21

        DD=GG (DD, AA, BB, CC, x[10], S22, 0x2441453) # 22

        CC=GG (CC, DD, AA, BB, x[15], S23, 0xd8a1e681) # 23

        BB=GG (BB, CC, DD, AA, x[ 4], S24, 0xe7d3fbc8) # 24

        AA=GG (AA, BB, CC, DD, x[ 9], S21, 0x21e1cde6) # 25

        DD=GG (DD, AA, BB, CC, x[14], S22, 0xc33707d6) # 26

        CC=GG (CC, DD, AA, BB, x[ 3], S23, 0xf4d50d87) # 27

        BB=GG (BB, CC, DD, AA, x[ 8], S24, 0x455a14ed) # 28

        AA=GG (AA, BB, CC, DD, x[13], S21, 0xa9e3e905) # 29

        DD=GG (DD, AA, BB, CC, x[ 2], S22, 0xfcefa3f8) # 30

        CC=GG (CC, DD, AA, BB, x[ 7], S23, 0x676f02d9) # 31

        BB=GG (BB, CC, DD, AA, x[12], S24, 0x8d2a4c8a) # 32

        # Round 3
        AA=HH (AA, BB, CC, DD, x[ 5], S31, 0xfffa3942) # 33

        DD=HH (DD, AA, BB, CC, x[ 8], S32, 0x8771f681) # 34

        CC=HH (CC, DD, AA, BB, x[11], S33, 0x6d9d6122) # 35

        BB=HH (BB, CC, DD, AA, x[14], S34, 0xfde5380c) # 36

        AA=HH (AA, BB, CC, DD, x[ 1], S31, 0xa4beea44) # 37

        DD=HH (DD, AA, BB, CC, x[ 4], S32, 0x4bdecfa9) # 38

        CC=HH (CC, DD, AA, BB, x[ 7], S33, 0xf6bb4b60) # 39

        BB=HH (BB, CC, DD, AA, x[10], S34, 0xbebfbc70) # 40

        AA=HH (AA, BB, CC, DD, x[13], S31, 0x289b7ec6) # 41

        DD=HH (DD, AA, BB, CC, x[ 0], S32, 0xeaa127fa) # 42

        CC=HH (CC, DD, AA, BB, x[ 3], S33, 0xd4ef3085) # 43

        BB=HH (BB, CC, DD, AA, x[ 6], S34, 0x4881d05) # 44

        AA=HH (AA, BB, CC, DD, x[ 9], S31, 0xd9d4d039) # 45

        DD=HH (DD, AA, BB, CC, x[12], S32, 0xe6db99e5) # 46

        CC=HH (CC, DD, AA, BB, x[15], S33, 0x1fa27cf8) # 47

        BB=HH (BB, CC, DD, AA, x[ 2], S34, 0xc4ac5665) # 48

        # Round 4
        AA=II (AA, BB, CC, DD, x[ 0], S41, 0xf4292244) # 49

        DD=II (DD, AA, BB, CC, x[ 7], S42, 0x432aff97) # 50

        CC=II (CC, DD, AA, BB, x[14], S43, 0xab9423a7) # 51

        BB=II (BB, CC, DD, AA, x[ 5], S44, 0xfc93a039) # 52

        AA=II (AA, BB, CC, DD, x[12], S41, 0x655b59c3) # 53

        DD=II (DD, AA, BB, CC, x[ 3], S42, 0x8f0ccc92) # 54

        CC=II (CC, DD, AA, BB, x[10], S43, 0xffeff47d) # 55

        BB=II (BB, CC, DD, AA, x[ 1], S44, 0x85845dd1) # 56

        AA=II (AA, BB, CC, DD, x[ 8], S41, 0x6fa87e4f) # 57

        DD=II (DD, AA, BB, CC, x[15], S42, 0xfe2ce6e0) # 58

        CC=II (CC, DD, AA, BB, x[ 6], S43, 0xa3014314) # 59

        BB=II (BB, CC, DD, AA, x[13], S44, 0x4e0811a1) # 60

        AA=II (AA, BB, CC, DD, x[ 4], S41, 0xf7537e82) # 61

        DD=II (DD, AA, BB, CC, x[11], S42, 0xbd3af235) # 62

        CC=II (CC, DD, AA, BB, x[ 2], S43, 0x2ad7d2bb) # 63

        BB=II (BB, CC, DD, AA, x[ 9], S44, 0xeb86d391) # 64

Y por ultimo, se devuelven los valores que se tomaron de los buffer a ellos:

        self.a=(self.a+AA)&0xFFFFFFFF
        self.b=(self.b+BB)&0xFFFFFFFF

        self.c=(self.c+CC)&0xFFFFFFFF
        self.d=(self.d+DD)&0xFFFFFFFF

Una cosa... el hacer and con 0xFFFFFFFF a las variables es para evitar que ocupen mas de 32 bytes, otra forma seria hacerlo modulo 0x100000000, pero esta es mas rapida.
Bien, veamos en que consisten las transformaciones... para empezar, S11,S12,S.. son constantes predefinidas, sus valores son estos:

S11=7
S12=12

S13=17
S14=22
S21=5
S22=9
S23=14

S24=20
S31=4
S32=11
S33=16
S34=23

S41=6
S42=10
S43=15
S44=21

Ademas en las transformaciones se utilizan unas funciones basicas:
def F(x,y,z):

    return (x&y)|((~x&0xFFFFFFFF)&z)

def G(x,y,z):
    return (x&z)|(y&(~z&0xFFFFFFFF))

def H(x,y,z):
    return x^y^z

def I(x,y,z):
    return y^(x|(~z&0xFFFFFFFF))

# Rotacion
def rotate_left(x,y):
    return ((x<<y)|(x>>(32-y)))

Una vez definido eso, las transformaciones no son demasiado complejas:
def FF(a,b,c,d,x,s,ac):

    a=(a+(F(b,c,d)+x+ac))&0xFFFFFFFF

    a= rotate_left(a,s)&0xFFFFFFFF
    a=(a+b)&0xFFFFFFFF

    return a

def GG(a,b,c,d,x,s,ac):

    a=(a+(G(b,c,d)+x+ac))&0xFFFFFFFF

    a= rotate_left(a,s)&0xFFFFFFFF
    a=(a+b)&0xFFFFFFFF

    return a

def HH(a,b,c,d,x,s,ac):

    a=(a+(H(b,c,d)+x+ac))&0xFFFFFFFF

    a= rotate_left(a,s)&0xFFFFFFFF
    a=(a+b)&0xFFFFFFFF

    return a

def II(a,b,c,d,x,s,ac):

    a=(a+(I(b,c,d)+x+ac))&0xFFFFFFFF

    a= rotate_left(a,s)&0xFFFFFFFF
    a=(a+b)&0xFFFFFFFF

    return a

Como se puede ver, el patron es bastante obvio:

def XX(a,b,c,d,x,s,ac):

    a=(a+(X(b,c,d)+x+ac))

    a= rotate_left(a,s)
    a=(a+b)

    return a

El resto solo sirve para evitar que los valores se salgan de los 32 bits

Y por ultimo, se presenta como resultado lo que hay en los buffers, comenzando por el byte menos significativo de A y acabando por el mas significativo de D, normalmente se hace directamente en la representacion hexadecimal:

    def final(self):

        self.digest=[]
        for some in [self.a,self.b,self.c,self.d]:

            t=uint4tochar(some)
            while len(t)>0:

                thing=t.pop(len(t)-1)
                self.digest.append(myhex(thing)[2:4])

    def hexdigest(self):
        from string import join

        return join(self.digest,'')

Las funciones utilizadas son estas:

#Pasa un entero de 4 bytes a un array de 4 bytes
def uint4tochar(s):
    i=0
    t=[0,0,0,0]

    while i<4:
        aux=(s>>(8*i))&0xFF

        t[3-i]=int(aux)
        i+=1

    return t

#Devuelve un hexadecimal con 4 caracteres o mas
def myhex(a):
    r=hex(a)

    if (len(r)==3):
        r="0x0"+r[2]

    return r

El código completo aqui [md5.py]

Si se ejecuta directamente (no importandolo), hace unas pruebas para comprobar que funciona bien, las comprobaciones se hacen contra hashlib:

d41d8cd98f00b204e9800998ecf8427e = d41d8cd98f00b204e9800998ecf8427e True
81dc9bdb52d04dc20036dbd8313ed055 = 81dc9bdb52d04dc20036dbd8313ed055 True
9e107d9d372bb6826bd81d3542a419d6 = 9e107d9d372bb6826bd81d3542a419d6 True
e4d909c290d0fb1ca068ffaddf22cbd0 = e4d909c290d0fb1ca068ffaddf22cbd0 True
6f728eb0a9ef9387cb17dba7cc2116fb = 6f728eb0a9ef9387cb17dba7cc2116fb True

Hasta la proxima ;)

[Referencia]
RFC 1321
MD5 - Wikipedia
Otra implementacion

Web's fantasma

Era un concepto que me gusto, la verdad es que ni siquiera era idea mia, sino que la saque de # Freesoftwareando in the night, la idea era dejar ahí el zip... pero como cerraron el post, pues lo dejo aqui.

Lo que entendi grosso modo (seguramente estaria explicado exactamente lo contrario, pero se hace lo que se puede ), era que estaria bien tener paginas web que una vez se visitaran, al volver no hubiera nada, por aquello de que alguien viendo de donde venia la gente por los Refereer acabaria estrellandose con un 404, bien, lo que pude programar es esto [multiplexor.zip], (hay que ajustar algunos parametros en options.php)

Y basicamente lo que hace es que al navegar dentro de la pagina (para empezar hay que navegar al archivo getticket.php) todas las direcciones son "virtuales", si alguien las ve y intenta visistarlas se encontrara con el conocido 404 Not Found, en la practica lo que hace es cifrar con ARC4 el nombre del archivo de la url usando como contraseña el id de session, y que al descifrar si no encuentra nada, envie un 404.

Obviamente no todo son ventajas (acaso tiene alguna utilidad real? ), el script PHP hace una peticion al servidor por cada una que le hace a el (siendo a localhost no deberia haber gran problema, pero es algo a tener en cuenta), ademas el problema de la implementacion es que seguramente funcione mal en paginas con Ajax, y no se tomo en cuenta la posibilidad de usarlo con formularios (es una Prueba de concepto, no habia ganas de implementar un parser html completo y demas )

ps: Perdon desde ya por el ultimo trozo de codigo, me quedo bastante... poco pythonico

ps2: Para quien no quiera bajarse todo el zip, tiene la implementacion de ARC4 en php, en un zip separado

Eso es todo, hasta la proxima!

martes, 20 de abril de 2010

TestWeb, un queso gruyer de vulnerabilidades

Esta idea viene de un post en HackXCrack en el que se buscaba el codigo de una pagina web con vulnerabilidades para hacer pruebas y a falta de una ya escrita, programe una web pequeña.

Tiene un poco de todo: SQL inyection, XSS y todo lo que se me ocurrio =)

Aqui teneis el zip (TestWeb.zip)

Usa una base de datos MySQL, los datos se pueden configurar en el archivo dbdata.php

ps: como ya comente en el post de HackXCrack, si vas a permitir a cualquiera entrar, mejor que pongas la variable $allowUpload en False, ( $allowUpload=False; ) (esta en el archivo _change_avatar.php ) sino se podria causar un DoS..., y de paso asegurate que los archivos estén en un chroot (las distros basadas en Debian lo hacen por defecto)... yo aviso

Hasta otra!

ps2: La tercera parte de Introduccion a la criptografia esta en camino ;)

lunes, 19 de abril de 2010

Bajando OGG's de Jamendo

[Actualizacion]

Para quien no lo sepa, Jamendo ofrece la opcion de descargar musica en OGG, pero solo por Bittorrent, y... seamos sinceros, el 90% de las descargas no tienen ya seeds, asi que hay que recurrir a la descarga directa y al MP3.

Como esta no es forma de ayudar a la musica libre, con formatos no libres, escribi un pequeño (muuuy pequeño) script de Greasemonkey que permite hacer la descarga directa en OGG, si quereis descargarlo, esta [aqui]... o el codigo:

// ==UserScript==
// @name           Jamendo OGG Redirector
// @namespace      www.jamendo.com
// @description    Redirects Jamendo MP3 download to OGG ones
// @include        http://www.jamendo.com/*/download/
// ==/UserScript==

// http://www.jamendo.com/LANGUAGE/download/album/ALBUM_NUMBER/do
//   |
//   | to
//   v
// http://www.jamendo.com/get/album/id/album/archiverestricted/redirect/ALBUM_NUMBER/?p2pnet=bittorrent&are=ogg3

var url=location.href;

var slices=url.split('/');

if (slices[slices.length-1]=="do"){

    var newUrl="http://www.jamendo.com/get/album/id/album/archiverestricted/redirect/"+slices[slices.length-2]+"/?p2pnet=bittorrent&are=ogg3";

    location.href=newUrl;
}

Y ya esta, vais a la pagina de las descargas, hasta donde pone que esperemos mientras se prepara la descarga (si, tambien esta la opcion de usar la descarga en MP3), se descargara el ZIP con el album en OGG.

Hasta otra!

domingo, 18 de abril de 2010

Musica en HTML5

Actualmente si alguien va a hacer un reproductor de audio o de video, en lo unico que se piensa es en Flash, pero HTML5 tambien permite hacerlo... sin necesidad de un formato que consume muchos recursos y que suele funcionar mal si no se visualiza con software privativo.

HTML5, la nueva version (aun experimental, pero soportada por la mayoria de los navegadores) del lenguaje HTML, añade tags como "audio" o "video", de esta forma, como antes se hacian presentaciones de imagenes mezclando Javascript y HTML, ahora se puede hacer un reproductor completo.

Nota: al menos Firefox no soporta MP3, dado que esta patentado, la mejor alternativa (incluso mejor que MP3) es OGG, totalmente libre.

Nota[2]: ningun musico fue "pirateado"

en el proceso de escritura de este post, podeis encontrar musica libre en sitios como Jamendo

Ahora si, HTML5...

La etiqueta que se usa es:
<audio src="ruta/al/archivo" [controls="controls"] [autoplay="autoplay"] [preload="preload"] > Texto </audio >
(Lo que esta entre '[' y ']' es opcional)
El texto solo se muestra si no se soporta la etiqueta audio ,seria algo asi como la etiqueta noscript

El significado de los atributos es:
src: ruta al archivo (como con la etiqueta img)
controls: se mostraran los controles: boton de reproducir, una barra de progreso..
autoplay: empezara a reproducirse tan pronto como pueda
preload: se empezara a cargar el audio cuando se carge la pagina (se ignora si se utiliza autoplay)

Entonces, con un codigo minimo:
<!DOCTYPE HTML>
<html>
<head>
    <title>Reproductor HTML5</title>
</head>
<body>

    <audio src="music/example.ogg" controls="controls" >

        Tu navegador no soporta el uso de la etiqueta de audio
    </audio>

</body>
</html>

Obtenemos esto:

No esta mal, eh?

y eso usando solo HTML, el navegador hace todo el trabajo,añadiendo algo de Javascript se pueden hacer cosas como listas de reproduccion...
<!DOCTYPE HTML>
<html>
<head>
    <title>Reproductor HTML5</title>
    <script type="text/javascript">
    </script>
</head>
<body>
    <br/>
    <audio id="player" preload="preload" controls="controls" >

        Tu navegador no soporta el uso de la etiqueta de audio
    </audio ><br/>
    <input type="text" readonly="true" id="this_tag" value="">

    <input type="button" onclick="next(player,tag,next_tag)" id="next_tag" value="">
    <script type="text/javascript">
    </script>
</body>
</html>

[Referencias]
Audio - MDC
Media formats supported by the audio and video elements - MDC
Using audio and video in Firefox - MDC
Introduction to the HTML5 audio tag javascript manipulation

lunes, 12 de abril de 2010

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

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 ] :

import random

def genprimelist(t):

    l = [2]
    i = 3
    while i < t :

        prime = True
        for c in l:

            if i % c == 0 :
                prime = False

                break
        if prime :
            l.append(i)

        i += 2
    return l

# Lista de primos precomputada con genprimelist(5000)
global primelist

primelist=[
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,

103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,

211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,

331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,

449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,

587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,

709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,

853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,

991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093,

1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,

1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327,

1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481,

1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,

1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721,

1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867,

1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,

1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113,

2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,

2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381,

2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,

2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671,

2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777,

2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909,

2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061,

3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217,

3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347,

3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499,

3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617,

3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761,

3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,

3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027,

4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,

4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327,

4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481,

4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637,

4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783,

4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933,

4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999]

# Comprobacion preliminar
def firstcheck(n):
    global primelist
    for p in primelist:

        if n%p==0:
            if n==p:

                return True
            else:
                return False

    return True

#Exponenciacion modular
def modex(base, exponente, modulo):
    r = 1

    while exponente > 0:
        if exponente & 1:

            r = (r * base) % modulo

        exponente >>= 1
        base = (base * base) % modulo
    return r

# Comprobacion con un test de primalidad de Fermat
# http://en.wikipedia.org/wiki/Fermat_primality_test
def fermattest(n,k=100):
    for i in range (0,k):

        a=random.randint(1,n-1)
        if modex(a,n-1,n) != 1:

            return False
    return True

def toBin(n):

    l = []
    while (n > 0):

    l.append(n % 2)
    n /= 2

    return l

# Comprobacion con el algoritmo de Miller-Rabin
# http://snippets.dzone.com/posts/show/4200
def test(a, n):

    b = toBin(n - 1)
    d = 1

    for i in xrange(len(b) - 1, -1, -1):

    x = d
    d = (d * d) % n

    if d == 1 and x != 1 and x != n - 1:

        return True # Complex
    if b[i] == 1:

        d = (d * a) % n

    if d != 1:
    return True # Complex

    return False # Prime

#Comprueba si es primo con el algoritmo de Miller-Rabin
def checkprime(n,k=100):

    if (not firstcheck(n)):
        return False
    if (not fermattest(n,k)):

        return False
    for iteration in range(0,k):

        i=random.randint(1,n-1)
        if test(i,n):

            return False
    return True

# Multiplicacion modular inversa
# [ http://en.wikipedia.org/wiki/Modular_multiplicative_inverse ]
def extended_gcd(a, b):

    x, last_x = 0, 1
    y, last_y = 1, 0

    while b:
        quotient = a // b

        a, b = b, a % b

        x, last_x = last_x - quotient*x, x

        y, last_y = last_y - quotient*y, y

    return (last_x, last_y, a)

# Multiplicacion modular inversa
# [ http://en.wikipedia.org/wiki/Modular_multiplicative_inverse ]

def inverse_mod(a, m):
    x, q, gcd = extended_gcd(a, m)

    if gcd == 1:
        # x is the inverse, but we want to be sure a positive number is returned.
        return (x + m) % m

    else:
        # if gcd != 1 then a and m are not coprime and the inverse does not exist.
        return None

#Generar un numero primo de "bitn" bits y con una precision de "prec"

def genprime(bitn,k=100):
    prime = random.randint(2**(bitn-1),2**bitn) #Esto se puede sustituir por una lectura a /dev/random, por ejemplo

    prime |= 1 # Hacemos que sea impar
    while not checkprime(prime,k):

        prime += 2
    return prime

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

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

def genkeys(bitn):

p = genprime(bitn)
q = genprime(bitn)

2. Se obtiene su producto (n):

n = p * q

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

phi = (p - 1) * (q - 1)

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

    # Este numero es arbitrario
    # cuanto mas pequenho, mas eficiente(rapido), pero menos seguro
    e=65537
    while (phi%e) == 0:

        e=genprime(17)

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

d = inverse_mod(e, phi)

La clave publica sera:

public = (n, e)

Siendo e el exponente publico (de cifrado).

Y la privada:

private = (n, d)

Siendo d el exponente privado (de descifrado).

return public, private

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:

# Se convierte un string en un numero
def msg2num(s):

    n = 0
    for c in s:

        n <<= 8
        n += ord(c)

    return n

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):

def cipher(s, public):
    n = msg2num(s)

    c = modex(n, public[1], public[0])

    return c

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

def decipher(n, private):

    p = modex(n, private[1], private[0])

    s = num2msg(p)
    return s

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

def num2msg(n):
    s = ""

    while n > 0:
        s = chr(n & 255) + s

        n >>= 8
    return s

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:

try:

    import hashlib
except:
    print "No se ha encontrado el modulo Hashlib, no podras firmar ni comprobar firmas"

def sign(msg,private):

    s=int(hashlib.sha1(msg).hexdigest(),16)

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

return modex(s,private[1],private[0])

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

def checksign(msg,sign,pub):
s=modex(sign,pub[1],pub[0])

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

h=int(hashlib.sha1(msg).hexdigest(),16)
return s==h

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