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:
# Punto de inicio
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:
Tabla de valores utilizados en la funcion
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
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<>(32-y)))
Transformaciones
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
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
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()
===============================================================================