miércoles, 19 de noviembre de 2008

El Ataque Rho de Pollard


Actualizado 19-11-2008

En un artículo anterior hablamos de la Criptografía de Curva Elíptica, dando una breve introducción al tema.

La revista hakin9 ha publicado en su web un artículo que escribí para la edición de Julio de 2007. El artículo, titulado "Criptografía de Curva Elíptica: Ataque Rho de Pollard" explica la teoría de las curvas elípticas e implementa un ataque en C++.

Se puede descargar el artículo directamente de la web de la revista, o obtener el enlace de mi web.

En cualquier caso, ahí va un enlace directo.

9 comentarios:

Anónimo dijo...

Hola, me gustaría ayuda para poder hacer correr el código GNFS que ya tengo pero no puedo compilar, me sirve la información de cualquiera que domine C (creo)Si alguién esta leyendo esto que responda, por favor.

Daniel Lerch dijo...

Hola,
He factorizado números mas o menos "gordos" con GGNFS, msieve (algoritmo gnfs) y con una implementación propia sencilla de GNFS en la que trabajo en mis ratos libres. Por lo que podría ayudarte si me das más detalles.

Puedes postear aquí el SO que usas y la implementación de GNFS con la que juegas.

Con GGNFS y msieve no es demasiado complicado.
El primero tiene un script en perl que facilita mucho el trabajo, aunque si quieres hacerlo por fases necesitas algunos conocimientos más profundos del algoritmo. Con el segundo es más sencillo aunque está más verde y quizás te quedes con la factorización a medias.

Saludos!

Anónimo dijo...

Pues mi sistema operativo es Windows Vista (preinstalado, ya sabes). El problema es que yo de programación sólo domino escasamente Phyton y ahora estoy empezando con tutoriales en C por eso al intentar compilar código faltan librerías, carpeta NT y muchos más problemas. Del algoritmo, la parte matemática la estoy leyendo en inglés y un poco de idea sobre escoger dos polinomios de grado tal, etc... si tengo pero la informática me trae de cabeza. Aquí te dejo un programa que igual tienes pero si no te puede interesar; http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/
el "factor" combina varios métodos y va sacando artillería más pesada cuanto más grande es el número. Varias Rho de Pollard, Curvas elípticas, Criba Cuadrática que se puede parar y luego volver a reiniciar.

Daniel Lerch dijo...

Hoy por hoy, lo más rápido que hay (libre) para factorizar números grandes es msieve:
http://www.boo.net/~jasonp/qs.html

y te proporciona un binario windows que evitará que tengas que pelear con el compilador. Por tu post, entiendo que solo quieres factorizar, no desarrollar, por lo que esta opción me parece la más indicada.

Por otra parte, si quieres compilar el soft que comentas, tendrás que instalarte un entorno de desarrollo y las librerías necesarias. Hay versiones de gcc para windows que te pueden servir y entornos de desarrollo como Dev-C++:
http://www.bloodshed.net/devcpp.html

Saludos.

Anónimo dijo...

Sí, pero el Dev-C ++ es justamente en el que intentaba hacerlo, en realidad no me interesa desarrollar porque no tengo los conocimientos necesarios de programación, tan solo estoy empezando por mi cuenta y ya he entendido que no puedo ponerme desde el principio con una implementación de GNFS, así que ya lo tengo olvidado. En el programa que me nombras no puedo abrirlo, cuando lo intento lo hace muy rápido y he podido leer creo; "cannot open file work to do" No se puede abrir el documento que está trabajando o algo así.

Saludos para ti también.

Daniel Lerch dijo...

Tranquilo, es normal.
Lo que dice realmente es "cannot open input file 'worktodo,ini". Esto es por que espera encontrar este ficherito con los datos a factorizar en su interior.

Primero, tienes que saber que no es una herramienta grafica, tienes que llamarla desde un terminal.
Después, para que no busque el 'worktodo.ini' solo tienes que pasar la opción -v i el número a factorizar.

Por ejemplo, si tienes el msieve.exe en c:/, tendrías que ejecutar "cmd" y ir a ese directorio con "cd c:\"

Una vez allí, ejecutarías algo como "msieve -v 987654321".

Saludos.

Anónimo dijo...

La ubicación es; C:\Users\MiCarpeta\Desktop\Factorizaje\msieve, he probado a hacerlo como dices desde la terminal del MSDOS, al final el único resultado que consigo es un "msieve no se reconoce como comando...", lo que siempre sale en los errores de comandos en batch. Voy a seguir intentándolo hasta que salga encontrando el directorio aunque lo tenga delante de las narices, estoy tan torpe estos días que pido más ayuda de la que me gustaría. Gracias por todo y sigue así con la página que está genial, es sinceramente la mejor que he visto sobre estos temas.

Hasta luego!

Anónimo dijo...

Existe un error en el articulo del algoritmo de FERMAT cuando se mete por segunda vez al mientras, la variable s debe elevarse al cuadrado y no al cubo. La respuesta esta correcta pero el procedimiento no

dlerch dijo...

mmm
no veo donde dices que se eleva al cubo ...
Además, te refieres al artículo de hakin9? o otro artículo que no es este?

si me das más pistas intentaré verificar el error y corregirlo.

saludos.