El juego de la vida con Processing [ Java ]
Pues nada, ahí va una implementación del juego_de_la_vida_de_Conway ( ejemplo clásico de automata celular ) hecho con processing [ http://pastebin.com/ MS6ACY4k ]
Lo único que hay que hacer para usar Processing es descargarlo y ejecutarlo.
Nota: en gnome parece que hace logout al user si no se quitan los efectos de ventanas ( Systema > Preferencias > Apariencia > Efectos visuales )
Una vez ejecutado solo hay que pegar el código en el editor y darle a "play".
Haz click en una "célula" para invertir su estado y pulsa un botón del teclado para reanudar/detener la simulación.
En cuanto a Processing, es ( según la web ) "un lenguaje de programación, un entorno de desarrollo y una comunidad online que desde 2001 ha promocionado la "software literacy" (como se traduce eso?) con las artes visuales. Creado inicialmente para servir como un software libro de sketchs y enseñar la programación básica de computadores en un contexto visual, Processing rápidamente se desarrollo como una herramienta para crear también software con un acabado profesional."
Hay unos tutoriales que muestran paso a paso el entorno ( no el lenguaje básico, que es Java, pero tutoriales de Java hay a patadas ) en http:// processing.org/learning/ .
ps: Parece que hay una versión en javascript que promete: http:// processingjs.org/ , con lo que se puede hacer esto, por ejemplo: http:// mariuswatz.com/works/abstract01js/
C'ya
GUI's en python con [ GTK | QT4 ] y [XML | HTML... ]
Hoy traigo una librería que aún no está acabada, pero puede que interese a la gente que no le guste complicarse lo más mínimo con las interfaces, pero que aún así le interese hacer unas GUI para los script [ guiml.zip ].
La idea es simple, le pasas un pedazo de HTML a la "librería" y esta selecciona el Toolkit disponible (por ahora solo soporta Gtk y Qt4, cuando le heche el guante a algo que tenga tk instalado lo añado ) hace una GUI basandose en eso, por ejemplo, para
Intérprete de Tubes
Actualizado: el intérprete tenía un bug en una tabla, ya está
arreglado [ http://pastebin.com/1zQQD0a4 ]
El otro día, rondando por esolang.org me encontré con un lenguaje de esos que hay que probar, Tubes, donde la lógica del programa se escribe en forma de cañerías, por ejemplo, un bucle que va mostrando 012301230123...
◉◆ ║║ ▶┤│ └┘
Pero había un problema, aún no había una implementación, así que hubo que ponerse manos a la obra, y de paso aprovechar para probar Python 3 que se maneja mejor que la versión 2 con las cadenas Unicode (todos los "dibujos" del código son unicode :P), este es el resultado[ http://pastebin.com/1zQQD0a4 ].
Como parámetro necesita el código a ejecutar, pero luce más si se le pasa la opción -d para que muestre el estado actual, se puede regular el retardo entre operaciones especificandolo después de -d (sinó no muestra el estado no hay retardo) y... eso es todo, chim pum!
Nos vemos
Internacionalizando un programa
Hoy veremos como hacer posible que se traduzca un programa a distintas lenguas ( internacionalización ), esto lo haremos con la librería gettext de GNU, para las pruebas usaré este hola mundo {hw.c}
include
int main(void){
printf("Hola, mundo!\n");
return 0;
}
Primero hay que incluir
setlocale(LC_ALL, "");
bindtextdomain("helloworld", ".");
textdomain( "helloworld");
Hecho esto, buscamos todas las cadenas a traducira gettext mandandolas como parámetro (para proyectos grandes se suele usar _ como alias gettext ). Por ahora va más o menos así:
include
include
include
int main(void){
setlocale(LC_ALL, "");
bindtextdomain("helloworld", ".");
textdomain( "helloworld");
printf(gettext("Hola, mundo!\n"));
return 0;
}
Ahora una de dos, nos ponemos a lanzar comandos o automatizamos, optaremos por la segunda, así que a hacer un script: src=hw.c
binary=hw
pot=hw.pot
package_name=helloworld
mo=$package_name.mo
domain=helloworld
if [ -z "$1" ];then
gcc -o $binary $src
xgettext --package-name $package_name --package-version 1 --default-domain $domain --output $pot $src
elif [ "$1" = "gettrad" ];then
if [ -z "$2" ];then
echo "No me has indicado el codigo de idioma { ej: es_ES }"
elif [ -z "$3" ];then
echo "No me has indicado el archivo"
else
msginit --no-translator --locale $2 --output-file $3 --input $pot
fi
elif [ "$1" = "addtrad" ];then
if [ -z "$2" ];then
echo "No me has indicado el codigo de idioma { ej: es_ES }"
elif [ -z "$3" ];then
echo "No me has indicado el archivo"
else
mkdir --parents ./$2.utf8/LC_MESSAGES
msgfmt --check --verbose --output-file ./$2.utf8/LC_MESSAGES/$mo $3
fi
fi
Tiene tres partes, la que se ejecuta cuando no recibe parámetros
gcc -o $binary $src
xgettext --package-name $package_name --package-version 1 --default-domain $domain --output $pot $src
Compila el programa y lanza xgettext, que extrae las cadenas gettext, del código fuente y lo guarda en un archivo .pot
La segunda, cuando recibe como primer parámetro gettrad, (y el código del idioma a traducir y el archivo donde se guardará)
msginit --no-translator --locale $2 --output-file $3 --input $pot
Crea el archivo .pot, donde se realizará la traducción.
Y la tercera, que añadirá la traducción, recibiendo como primer parámetro addtrad (y el código de idioma traducido y el archivo de traducción ) mkdir --parents ./$2.utf8/LC_MESSAGES
msgfmt --check --verbose --output-file ./$2.utf8/LC_MESSAGES/$mo $3
Comprueba que haya un directorio para las traducciones y compila el archivo.
Y ya está, para probarlo podemos hacer
LANGUAGE=es_ES.utf8 ./hw
En esta parte hay que tener en cuenta que hasta ahora el código de lenguage sería es_ES, pero en este último paso se añadiría utf8 al final.
Por último hacer notar que el directorio de traducciones puede estar en . o en /usr/share/locale-langpack/ , esto último es lo que se hace normalmente
Hasta otra
[Referencias] http://www.gnu.org/software/gettext/FAQ.html http://www.gnu.org/software/gettext/manual/gettext.html http://stackoverflow.com/questions/1003360/complete-c-i18n-gettext-hello-world- example/1033337#1033337
Disionario morrasense en fortunes [ desvarío ]
Bue, hoy vamos a dejar de hablar de programación y si me apuras vamos a hacer un cambio temporal de público objetivo, que no creo que nadie de la 5ª provincia lea esto :P así que...
Presentamos la fortune del "Disionario_da_revolusionaria_academia_morrasense_da lingua:morrasense-_jodechincho".
El archivos es este: disionario ( dadle a "download" ) Para instalarlo hay que seguir estos pasos:
1.- Lo descargamos y guardamos como "disionario"
-- Esto se hace desde el terminal, se puede abrir desde Accesorios>Terminal --
2.- Usamos "sudo apt-get install fortunes" para instalar el programa que las muestra 3.- La convertimos a la forma que necesitamos con "strfile disionario" 4.- Los copiamos a la carpeta del programa "sudo cp disionario* /usr/share/ games/fortunes/" 5.- Hacemos que las pueda leer cualquiera "sudo chmod +r/usr/share/games/ fortunes/disionario"
-- Ahora podemos comprobar que funciona haciendo "fortune disionario", si sale algo está todo bien -- 6.- Si queremos que se muestre al abrir un terminal ponemos esto en el archivo ".bashrc" ( en la carpeta de usuario ): "fortune disionario"
Bonus, si queremos que nos lo diga una vaca, haremos esto: 1.- "sudo apt-get install cowsay" 2.- Lo que ponemos en el archivo .bashrc es "fortune disionario|cowsay"
2.1.- Si queremos que lo piense un pato ponemos en el archivo "fortune disionario|cowthink -f /usr/share/cowsay/cows/duck.cow"
Y ya tenemos el cupo de paridas del mes cubierto :P Sí, ya me tomo la medicación que esto no puede ser bueno =_=
Leyendo las cookies y logins de Firefox con Python y SQLite
Aprovecho la oportunidad para decir Felices navidad! / Bo nadal! / Merry christmas!
Ahora sí... recordemos que Firefox guardaba alguna información en forma de bases de datos SQLite (interesantes por el hecho de que no requiere un demonio externo, sino que toda la información lo maneja la librería sobre un archivo), veamos como hacer un script que nos muestre las cookies para dominios concretos.
Las cookies se guardan en el archivo "cookies.sqlite" en la carpeta del perfil del programa, un "file" confirma que es una base de datos sqlite3, se puede abrir con
=============================================================================== sqlite3 cookies.sqlite ===============================================================================
Veamos que tablas tiene
=============================================================================== sqlite> .table moz_cookies sqlite> ===============================================================================
Entonces solo hay una tabla, "moz_cookies", veamos como funciona
=============================================================================== sqlite> .schema moz_cookies CREATE TABLE moz_cookies (id INTEGER PRIMARY KEY, name TEXT, value TEXT, host TEXT, path TEXT,expiry INTEGER, lastAccessed INTEGER, isSecure INTEGER, isHttpOnly INTEGER); sqlite> ===============================================================================
Los nombres de los campos son bastante ilustrativos, probemos buscando campos con "google", por ejemplo, en el host...
=============================================================================== sqlite> select * from moz_cookies where host like '%google%'; 1284819422521617|PREF|ID=9781f1e5d7ff9422:U=e5291c6e5476d7f8:TM=1284819422: LM=1286025562:GM=1:S=yVNr14zH2KpCzPpS|.google.com|/ |1349097562|1286026121306278|0|0 ... sqlite> ===============================================================================
Ya está, ahora a plasmarlo en un script, lo primero es importar sqlite3 (y de paso sys =P)
import sqlite3, sys
La función que muestre las cookies será cookie_f
def cookie_f(fn, host):
Ahora hay que abrir el archivo:
sock = sqlite3.connect(fn)
Y obtener un cursor para manejarlo:
c = sock.cursor()
Lo próximo es hacer la petición, para delegar el esfuerzo de filtrarla, se pondrá una "?" donde se ubicará la cadena de host, y se concatenan después los % del like, el segundo argumento, la cadena de host, tiene que ser una tupla:
c.execute("select * from moz_cookies where host like '%' || ? || '%'", (host, ))
Ahora hay que hacer efectivos los cambios:
sock.commit()
Y mostrar los datos obtenidos:
for res in c.fetchall():
print res
Una vez hecho esto, y dado que no se harán más peticiones, se cierra la base de datos:
c.close()
El resto del código es trivial:
if (len(sys.argv) < 3):
print sys.argv[0], "
exit(0)
cookie_f(sys.argv[1], sys.argv[2])
El código completo: http://pastebin.com/jwt1Apwu
=============================================================================== $ ./firesnake.py cookies.sqlite google (1284819422521617L, u'PREF', u'ID=9781f1e5d7ff9422:U=e5291c6e5476d7f8: TM=1284819422:LM=1286025562:GM=1:S=yVNr14zH2KpCzPpS', u'.google.com', u'/', 1349097562, 1286026121306278L, 0, 0) ... ===============================================================================
Hasta el año que viene ;)
[Referencias] http://docs.python.org/library/sqlite3.html http://www.sqlite.org/sqlite.html
PyLOIC 0.2
Visto lo visto y viniendo lo que viene, hay nueva versión de pyLOIC, entre
otras cosas se añadieron 2 formas de ataque más efectivas:
*
* Uno basado en_Slowloris, un poco más abajo, aquí, están los servidores
a los que afecta (aunque no espereis gran cosa para 10 minutos de
código)
*
- Y otro un clásico, "un Stairway to Heaven casi", un SYN flood... peeeero
necesita Scapy ('sudo apt-get install python-scapy') y permisos de root.
*
Además se añadieron los cambios a la_GUI_de_fanta (tirando de copypaste descarado de su código =P ) para aprovechar lo nuevo [pyloic02.zip].
Actualización: arreglado Bug gracias a Tincho que hacía que nunca cerrase las conexiones -fixed-
Por el camino para intentar que la GUI fuera portable, metí un bug (sin cambiar nada de código, alucina :D ) que hace que solo carge la imágen la primera vez, si alguien se le ocurre como arreglarlo que avise.
Ah, sí, el ataque SYN permite utilizar una IP falsa, así que igual compensa instalar Scapy ('sudo apt-get install python-scapy') para él ;)
Debería funcionar sobre cualquier SO con python (para windows puede que haya que instalar el_intérprete).
En otros SO puede hacer falta dar permisos de ejecución, méte los archivos en una carpeta y en un terminal escribe:
===============================================================================
chmod +x *.py
===============================================================================
Para conseguir permisos de root en Gnu/Linux, *BSD ... (necesarios para SYN) usa
===============================================================================
sudo python gui.py
===============================================================================
Eso es todo...
5 programas que (quizá) no conocias [offtopic]
Vamos a dejar de lado la programación un rato para ver algunos programas (la mayoría solo sirven para Gnu/Linux) que cuando los conozcas te preguntarás, ¿ como vivía yo sin esto?... o quizá no =P
Plowshare
Un gestor de descargas, hijo bastardo de JDownloader y wget, permite descargar de muchos_servicios_de_almacenamiento (por ejemplo Megaupload) lanzando un comando de terminal, especialmente bueno para quien no soporte que JDownloader sea tan pesado, o que busquen algo que ademas permita hacer subidas .
Por su naturaleza el límite es la imaginación, combinado con GNU-screen se puede hacer que descarge de fondo, incluso sin necesidad de estar logueado, y con un poco de scripting aquí y allá puedes montar tu propia GUI o una interfaz web. Y escrito como está con lenguajes de scripting se pueden escribir_módulos_propios utilizando nada más que bash.
https://code.google.com/p/plowshare/
Axel
Si plowshare permitía descargar de sitios "complicados", este amplia las opciones de descarga incluyendo varios hilos a la vez y continuar con otras interrumpidas.
Con solo 46 kb's entra en la categoría de los pesos ligeros, personalmente creo que lo mejor que se puede hacer es combinar este y plowshare, haciendo algo como
===============================================================================
plowshare --run-download="axel \"%url%\""
===============================================================================
http://axel.alioth.debian.org/
GNU Screen
O solo screen, permite hacer virguerías con el terminal, si el terminal sea el interfaz por defecto este no puede faltar. Hay un tutorial en tuxpepino.wordpress.com
http://www.gnu.org/software/screen/
Guake
Muy útil también para quién heche mano del terminal cada dos por tres, hace que sea accesible pulsando F12 al estilo del Quake. Para quien usa KDE la alternativa es Yakuake.
http://guake.org/
Freenet
No puede quedar sin mencionar Freenet, una red P2P concebida para ser resistente a la censura, puede usarse para subir/ver páginas web, archivos, enviar mails... incluso hay tablones de noticias. Este sí que es multiplataforma (está escrito en Java)
http://freenetproject.org/
Esperemos no tener que recurrir a Freenet a partir del martes que viene :S
Casi traducidos los documentos del cablegate que involucran la Ley Sinde [nunca Offtopic]
La gente de Hacktivistas se está currando una traducción de los documentos del cablegate con alguna relación a la Ley Sinde, así que si no los leisteis por no saber donde buscar, por el tema de la comprensión del inglés o algo así, ya no teneis excusa, están aquí: http://wiki.hacktivistas.net/ index.php?title=Accion/Sindegate/traducciones
Aprovecho para decir que la misma gente montó una web muy completa para protestar por como vá todo esto, http://sindegate.net/.
A este paso nos vemos en Freenet
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 & 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:
- Se generan dos numeros primos (p y q): def genkeys(bitn):
p = genprime(bitn)
q = genprime(bitn)
-
Se obtiene su producto (n):
n = p * q -
Se calcula la funcion de euler del producto (o el producto de cada numero-1) (phi)
phi = (p - 1) * (q - 1) -
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)
- 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 & 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