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:
Mostrando entradas con la etiqueta cifrado asimetrico. Mostrar todas las entradas
Mostrando entradas con la etiqueta cifrado asimetrico. Mostrar todas las entradas
miércoles, 23 de marzo de 2011
domingo, 6 de junio de 2010
Introduccion a la criptografia, con Python: ElGamal (V -1 )
Y vamos por la quinta parte de Introduccion a la criptografia, se dividira en dos porque ya que hablamos de cifrado asimetrico vale la pena ver un cifrado/descifrado y un algoritmo de firma/comprobacion, el problema es que si bien ElGamal cumple perfectamente su parte en lo primero, no tiene un esquema de firmado con el que comparta la generacion de claves (tambien hay un algoritmo de firma ElGamal, pero no es el mismo, y ademas no se considera del todo seguro), asi que ademas veremos un esquema de solo firma ( DSA ) en la segunda parte.
Sin mas espera...
¿Que es ElGamal?
Ademas ElGamal comparte con RSA el uso de operaciones matematicas como el calculo de la exponenciacion modular y la generacion de numeros primos, que ya estan posteadas en la entrada correspondiente asi que ya no las incluire aqui para evitar saturar el post con informacion repetida (aunque si en el codigo fuente al final y para descargar, que ahi no molesta)
Aviso: como sabreis, esta implementacion (como toda esta serie), no se deberia usar para nada real, no solo porque es mas lento que un i286 (lo dicho, esta en python solo para que sea mas facil de entender), sino porque ademas seguro que los programas y librerias que existen cumplen las funciones que necesarias mejor y con mas seguridad
Generando claves
Para generar las claves se realizan las siguientes operaciones (he intentado mantener el mismo nombre de las variables que la Wikipedia para simplificar)
1. Se genera un numero primo (p), a ser posible con un (p-1) que al factorizarlo se obtengan numeros grandes (aqui simplemente se espera que con un p grande p-1 cumpla su condicion )
def genkeys(bitn):
p = genprime(bitn)
2. Se obtienen dos numeros aleatorios (g y a), g es el generador, parte de la clave publica, mientras que a es la clave privada, g puede ser cualquier numero (aunque se recomienda que se tomen algunas consideraciones de seguridad), mientras que a es un numero entre 0 y p-2 (aunque por seguridad se recomienda usar un numero de 2 a p-2):
g = random.randint(2**(bitn-1),2**bitn)#Esto se puede sustituir por una lectura a /dev/random, por ejemplo
a = random.randint(2,p-2)
3. La ultima variable a generar (a2 , A en la Wikipedia) es el resultado de elevar g a la potencia a, y obtener el resultado modulo p
a2 = modex(g,a,p)
Asi, la clave publica esta formada por las variables p , g y a2 , mientras que la clave privada es a
Por comodidad, la clave publica se carga en un diccionario:
public = {'p':p,'g':g,'a2':a2}
private = a
return public, private
Cifrado y descifrado
De nuevo, el cifrado y descifrado necesitaran convertir el mensaje en un numero, como las funciones ya estan en el post de RSA, no tiene sentido repetirlas
Cifrando...
1. Para cifrar, se convierte el mensaje en un numero n
def cipher(s, public):
n = msg2num(s)
2. Despues se obtiene un numero pseudo-aleatorio b entre 2 y p-2 (recordemos que p forma parte de la clave publica)
b = random.randint(2, (public ['p'] -2) )
3. Se eleva g a b modulo p, para conseguir la variable y1
y1 = modex(public ['g'], b, public['p'])
4. Lo que falta, y2 se obtiene al elevar a2 a b y multiplicarlo por n , el resultado se obtiene modulo p
... o, para evitar dejarse el procesador en la operacion, se eleva a2 a b modulo p, el resultado se multiplica por n y se hace modulo p ( esto aprovecha que hacer la operacion de exponenciacion modular es mas rapida que una exponenciacion normal )
y2 = modex(public ['a2'], b, public['p'])
y2 = ( y2 * n ) % public ['p']
El mensaje cifrado son las variables y1 y y2
return (y1,y2)
Descifrando...
Para descifrar necesitaremos el mensaje cifrado, la clave privada y la publica (al contrario de RSA, que no necesita la clave publica)
1. Recuperamos el numero que corresponde al texto elevando y1 a p - 1 - a , multiplicando el resultado por y2 y obteniendo todo modulo p
... o con exponenciacion modular haciendo y1 elevado a p - 1 - a modulo p, multiplicado por y2, y con el resultado modulo p
def decipher(n, public, private):
d = modex(n[0], public['p'] -1 -private, public['p'])
d = (d * n[1]) % public ['p']
2. Solo queda volver a convertir el numero a texto
s = num2msg(d)
return s
Y ya esta :D, el codigo fuente esta aqui [ elgamal.py ]
[Referencias]
http://es.wikipedia.org/wiki/ElGamal
http://en.wikipedia.org/wiki/ElGamal
Sin mas espera...
¿Que es ElGamal?
El procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en problemas matemáticos de algoritmos discretos. Es un algoritmo de criptografía asimétrica basado en la idea de Diffie-Hellman y que funciona de una forma parecida a este algoritmo discreto.
El algoritmo de ElGamal puede ser utilizado tanto para generar firmas digitales como para cifrar o descifrar.
Fue descrito por Taher Elgamal en 1984 y se usa en software GNU Privacy Guard, versiones recientes de PGP, y otros sistemas criptográficos. Este algoritmo no esta bajo ninguna patente lo que lo hace de uso libre. [wikipedia]
Ademas ElGamal comparte con RSA el uso de operaciones matematicas como el calculo de la exponenciacion modular y la generacion de numeros primos, que ya estan posteadas en la entrada correspondiente asi que ya no las incluire aqui para evitar saturar el post con informacion repetida (aunque si en el codigo fuente al final y para descargar, que ahi no molesta)
Aviso: como sabreis, esta implementacion (como toda esta serie), no se deberia usar para nada real, no solo porque es mas lento que un i286 (lo dicho, esta en python solo para que sea mas facil de entender), sino porque ademas seguro que los programas y librerias que existen cumplen las funciones que necesarias mejor y con mas seguridad
Generando claves
Para generar las claves se realizan las siguientes operaciones (he intentado mantener el mismo nombre de las variables que la Wikipedia para simplificar)
1. Se genera un numero primo (p), a ser posible con un (p-1) que al factorizarlo se obtengan numeros grandes (aqui simplemente se espera que con un p grande p-1 cumpla su condicion )
def genkeys(bitn):
p = genprime(bitn)
2. Se obtienen dos numeros aleatorios (g y a), g es el generador, parte de la clave publica, mientras que a es la clave privada, g puede ser cualquier numero (aunque se recomienda que se tomen algunas consideraciones de seguridad), mientras que a es un numero entre 0 y p-2 (aunque por seguridad se recomienda usar un numero de 2 a p-2):
g = random.randint(2**(bitn-1),2**bitn)#Esto se puede sustituir por una lectura a /dev/random, por ejemplo
a = random.randint(2,p-2)
3. La ultima variable a generar (a2 , A en la Wikipedia) es el resultado de elevar g a la potencia a, y obtener el resultado modulo p
a2 = modex(g,a,p)
Asi, la clave publica esta formada por las variables p , g y a2 , mientras que la clave privada es a
Por comodidad, la clave publica se carga en un diccionario:
public = {'p':p,'g':g,'a2':a2}
private = a
return public, private
Cifrado y descifrado
De nuevo, el cifrado y descifrado necesitaran convertir el mensaje en un numero, como las funciones ya estan en el post de RSA, no tiene sentido repetirlas
Cifrando...
1. Para cifrar, se convierte el mensaje en un numero n
def cipher(s, public):
n = msg2num(s)
2. Despues se obtiene un numero pseudo-aleatorio b entre 2 y p-2 (recordemos que p forma parte de la clave publica)
b = random.randint(2, (public ['p'] -2) )
3. Se eleva g a b modulo p, para conseguir la variable y1
y1 = modex(public ['g'], b, public['p'])
4. Lo que falta, y2 se obtiene al elevar a2 a b y multiplicarlo por n , el resultado se obtiene modulo p
... o, para evitar dejarse el procesador en la operacion, se eleva a2 a b modulo p, el resultado se multiplica por n y se hace modulo p ( esto aprovecha que hacer la operacion de exponenciacion modular es mas rapida que una exponenciacion normal )
y2 = modex(public ['a2'], b, public['p'])
y2 = ( y2 * n ) % public ['p']
El mensaje cifrado son las variables y1 y y2
return (y1,y2)
Descifrando...
Para descifrar necesitaremos el mensaje cifrado, la clave privada y la publica (al contrario de RSA, que no necesita la clave publica)
1. Recuperamos el numero que corresponde al texto elevando y1 a p - 1 - a , multiplicando el resultado por y2 y obteniendo todo modulo p
... o con exponenciacion modular haciendo y1 elevado a p - 1 - a modulo p, multiplicado por y2, y con el resultado modulo p
def decipher(n, public, private):
d = modex(n[0], public['p'] -1 -private, public['p'])
d = (d * n[1]) % public ['p']
2. Solo queda volver a convertir el numero a texto
s = num2msg(d)
return s
Y ya esta :D, el codigo fuente esta aqui [ elgamal.py ]
[Referencias]
http://es.wikipedia.org/wiki/ElGamal
http://en.wikipedia.org/wiki/ElGamal
lunes, 12 de abril de 2010
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 ] :
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)
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 & 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
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 ] :
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
Suscribirse a:
Entradas (Atom)
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