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)
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
Está malo el link a rsa.py
ResponderEliminarA mi me funciona bien... sera el host que no va del todo bien, a veces hay que volver a intentarlo ;)
ResponderEliminar