Pues seguimos con la introduccion a la criptografia... acababamos de ver el cifrado usando ElGamal y quedaba pendiente el algoritmo de firmado usando DSA para pasar a la sexta parte ( hashes de nuevo ), así que ahí vamos, documentación y código intercalado:
¿Que es DSA?
DSA (Digital Signature Algorithm, en español Algoritmo de Firma digital) es un estándar del Gobierno Federal de los Estados Unidos de América o FIPS para firmas digitales. Fue un Algoritmo propuesto por el Instituto Nacional de Normas y Tecnología de los Estados Unidos para su uso en su Estándar de Firma Digital(DSS), especificado en el FIPS 186. DSA se hizo público el 30 de agosto de 1991, este algoritmo como su nombre lo indica, sirve para firmar y no para cifrar información. Una desventaja de este algoritmo es que requiere mucho más tiempo de cómputo que RSA o ElGamal, pero a cambió las claves no tienen que ser tan grandes. [wikipedia]Antes de empezar una cosa: el FIPS186 define un algoritmo para comprobar la primalidad, es bastante sencillo y hasta lo tenía implementado por ahí, peeeero... la lata dejó de funcionar y adiós. Enfin, que por ahora tiraremos con el mismo que el usado con RSA, que al fin y al cabo es solo ligeramente más lento pero da menos falsos negativos, con un poco de suerte mañana subo el código del test del FIPS186.
Para no variar, primero un trozo de código común con la implementación de RSA que se encarga de las mátematicas de forma eficiente, no es parte del protocolo pero es necesario para no desesperarse mientras firma algo.
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
Copyright 2011 kenkeiras <kenkeiras@gmail.com>
Bajo la licencia WTFPL
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
Version 2, December 2004
Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.
DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
0. You just DO WHAT THE FUCK YOU WANT TO.
"""
import random
import sys
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]
# Comprobación 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
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 int(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
Nota: el archivo bien formateado y completo al final, que al meterlo en blogger hace una carnicería con los saltos de línea
Generación de claves
Según todos los sitios que hablan de este algoritmo, los dos primeros pasos son:
- 1. p = a prime modulus, where 2L-1 < p < 2L for 512 = < L = <1024 and L a multiple of 64
- 2. q = a prime divisor of p - 1, where 2159 < q < 2160
Trola! Si intentas hacer esto, intentando conseguir un par puedes ir a dar la vuelta al mundo mientras esperas, prueba de ello es este antiguo post [ "Eso pasa por no leer" ]
Vamos, que lo primero que hay que hacer es obtener un q primo de 160 bits y después obtener un p a partir de p = q * 2 * n, en bonito:
def genP(q,bitn):
i = (bitn-1)-len(bin(q)[2:])
n = random.randint(1,1<<i)
qn = q * n
curr = (qn * (2*(bitn-len(bin(qn)[2:]))))
while len(bin(curr)[2:]) < bitn:
curr <<= 1
return curr + 1
def genkeys(bitn):
p = q = None
while True:
q = genprime(160)
p = genP(q,bitn)
if (checkprime(p)):
break
Después de esto todo es razonable:
3. g = h(p-1)/q mod p, where h is any integer with 1 < h < p - 1 such that h(p-1)/q mod p > 1 (g has order q mod p)
g = h = None
pq = ((p-1)/q) # Precalculado, puede ser necesario
# usarlo varias veces
while True:
h = random.randint(2,p-2)
g = modex(h,pq,p)
if g > 1:
break
4. x = a randomly or pseudorandomly generated integer with 0 < x < q
x = random.randint(2,q-1)
5. y = gx mod p
y = modex(g,x,p)
En la documentación hablan de un sexto paso, generar un k aleatorio entre 0 y q, que no se incluirá en la clave privada ni en la pública, y que hay que regenerar cada vez que se firme algo ( en resumen, que es parte del proceso de firma pero a alguien se le cruzaron las neuronas )
La generación de claves ya está solo queda devolver los valores, la clave pública es y , la privada es x y otros datos genéricos ( que pueden ser compartidos por ciertos usuarios ) son: g, p y q
public = y
private = x
generic = (g,p,q)
return public, private, generic
Generación de firmas
Como con RSA, el documento se hasheará para firmarlo, así que utilizaremos esta función para obtener el hash como un número ( hace falta importar hashlib )
def SHA(msg):
return int(hashlib.sha1(msg).hexdigest(),16)
Vamos entonces con la generación de la firma:
def sign(msg,private,generic):
r = s = None
g = generic[0]
p = generic[1]
q = generic[2]
while True:
k = a randomly or pseudorandomly generated integer with 0 < k < q
k = random.randint(1,q-1) # Necesaria la mayor aleatoriedad
r = (gk mod p) mod q
r = modex(g,k,p) % q
s = (k-1(SHA(M) + xr)) mod qNota: ese k-1 se refiere al inverso de k en q, (k * k-1) % q = 1
s = (inverse_mod(k,q)*(SHA(msg) + (private*r))) % q
Y se comprueba que r y s sean distintos de 0
if ( r != 0 ) and ( s != 0 ):
break
La firma la componen r y s
return (r,s)
Comprobación de firmas
Toca entonces comprobar si nos han dado del palo, así comienza la comprobación de firmas (boilerplate-code):
def checksign(msg,sign,pub,generic):
r = sign[0]
s = sign[1]
g = generic[0]
p = generic[1]
q = generic[2]
if ( r == 0 ) or ( s == 0 ):
return False
Entonces, para las comprobaciones hacemos:
w = (s')-1 mod q
w = inverse_mod(s,q)
u1 = ((SHA(M')w) mod q
u1 = (SHA(msg)*w) % q
u2 = ((r')w) mod q
u2 = (r*w) % q
v = (((g)ul (y)u2) mod p) mod q
v = ((modex(g,u1,p)*modex(pub,u2,p)) % p ) % q
Y la firma será correcta si v == r
return v == r
El código completo [ dsa.py ], si se ejecuta directamente hará algunas comprobaciones
Saludos
[Referencias]
FIPS 186
http://cryptodox.com/DSS
http://es.wikipedia.org/wiki/Digital_Signature_Algorithm
http://en.wikipedia.org/wiki/Digital_Signature_Algorithm
No hay comentarios:
Publicar un comentario