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

[Unknown INPUT type]

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]

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 &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 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),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

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)

  1. Se obtiene su producto (n):
    n = p * q

  2. Se calcula la funcion de euler del producto (o el producto de cada numero-1) (phi)
    phi = (p - 1) * (q - 1)

  3. 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)
  1. Se obtiene un numero (d) que multiplicado por esea 1 modulo modulophi:
    d = inverse_mod(e, phi)

La clave pública 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 &amp; 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

untagged

Introduccion a la criptografia, con Python: ARC4 (I) » « Música en HTML5