miércoles, 4 de agosto de 2010

Eso pasa por no leer

La historia viene de atrás, intentando programar el módulo de la siguiente parte de Introducción a la criptografía, me di de frente con una parte del algoritmo en cuestion  (DSA), que dice así
Toma un primo p de una longitud dada (muy grande, para entendernos), y otro q, de 160 que sea divisor de p-1
Y ahí se armó el follon. Dejando a un script que buscase al tan ansiado q durante un tiempo no produjo resultados, ya es pesado de por si buscar primos de 160 bits cuanto más comprobar si son divisibles por, otro de como mínimo 512 bits... y no, 2 no vale, porque el otro divisor sería de 511 bits ;).

Siendo la epoca en la que fue, con poco tiempo, no me preocupe mucho de esto, pero puse un script a buscar ese número y que de paso hiciera una lista de todos los números primos que se fuera encontrando.
El script, después de 3 dias funcionando y más de millon y medio de números primos no dio con q , pero resulta que el propio FIPS 186 (la "especificación" de DSA) dice en el Apéndice 2 como obtener este par de números (p y q), tanto tiempo de CPU en vano... ¿o no?

La lista de primos en forma de módulo de python (está en la variable dumplist) se puede descargar aquí [dumped.py], no se que uso se le puede dar pero al fin y al cabo son millon y medio de primos a partir de 2^159 y hay gente con mucha imaginación :)

ps: La primera vez tarda un poco en importar, pero en cuanto hace el .pyc funciona relativamente rápido
ps2: Ahora que lo pienso... ¿este será el módulo de python más pesado?

Y eso es todo por hoy...
[Referencias]
FIPS 186

No hay comentarios:

Publicar un comentario