Después de 8 meses de demorar el momento de enfrentarse a DSA, continúa esta introducción a la criptografía ( aaaleluyaaaa... )

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

"""

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

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 &amp; 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),2bitn) #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

Parece simple, verdad?, pues por culpa de esto esta parte tardó tanto tiempo XD

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 q

Nota: ese k-1 se refiere al inverso de k en q, (k * k-1) % q = 1
s = (inverse_mod(k,q)(SHA(msg) + (privater))) % 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

Codigo para llevar [blog]

Introducción a la criptografia, con Python: DSA (V -2)

!/usr/bin/env python

-- encoding: utf-8 --

Lista de primos precomputada con genprimelist(5000)

Comprobación preliminar

Exponenciacion modular

Comprobacion con un test de primalidad de Fermat

http://en.wikipedia.org/wiki/Fermat_primality_test

Comprobacion con el algoritmo de Miller-Rabin

http://snippets.dzone.com/posts/show/4200

Comprueba si es primo

Multiplicacion modular inversa

[ http://en.wikipedia.org/wiki/Modular_multiplicative_inverse ]

Multiplicacion modular inversa

[ http://en.wikipedia.org/wiki/Modular_multiplicative_inverse ]

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