Récords en logaritmos discretos - Wikipedia, la enciclopedia libre Ir al contenido

Récords en logaritmos discretos

De Wikipedia, la enciclopedia libre
El texto que sigue es una traducción defectuosa. Si quieres colaborar con Wikipedia, busca el artículo original y mejora esta traducción.
Copia y pega el siguiente código en la página de discusión del autor de este artículo: {{subst:Aviso mal traducido|Récords en logaritmos discretos}} ~~~~

Los récords en logaritmos discretos son los mejores resultados obtenidos hasta la fecha en la resolución del problema del logaritmo discreto, consistente en encontrar soluciones de x para la ecuación gx = h, dados dos elementos g y h pertenecientes a un grupo cíclico finito G. La dificultad de resolver el problema es la base de la seguridad de numerosos sistemas criptográficos, entre ellos el protocolo Diffie-Hellman, el cifrado ElGamal, el Algoritmo de Firma Digital (DSA), o la criptografía de curvas elípticas. La elección más habitual de G utilizada en esos algoritmos incluye el grupo multiplicativo de enteros módulo p, el grupo multiplicativo de un cuerpo finito, y el conjunto de puntos de una curva elíptica sobre un cuerpo finito.

Enteros módulo p

[editar]

El 18 de junio de 2005, Antoine Joux y Reynald Lercier anunciaron la computación de un logaritmo discreto módulo un número primo fuerte de 130 dígitos (431 bits) en tres semanas, utilizando para ello un ordenador HP AlphaServer GS1280 con 16 procesadores a 1.15 GHz ejecutando un algoritmo de criba general del cuerpo de números (GNFS).[1]​

El 5 de febrero de 2007, fue superado con el anuncio de Thorsten Kleinjung de la computación de un logaritmo discreto módulo un número primo fuerte de 160 dígitos (530 bits), usando de nuevo la criba general del cuerpo de números. La mayor parte de la computación fue realizada utilizando tiempo muerto de CPU en varios ordenadores de un clúster de computación en paralelo.[2]​

Cuerpos finitos

[editar]

El récord actual (a fecha de 2013) en un cuerpo finito de característica 2 fue anunciado por Antoine Joux el 21 de mayo de 2013. Su equipo fue capaz de computar logaritmos discretos en el cuerpo de 26168 = (2257)24 elementos usando para ello menos de 550 horas de CPU. Esta computación fue realizada utilizando el mismo algoritmo de cálculo empleado en la computación reciente del cuerpo con 24080 elementos.[3]​

Los récords anteriores en cuerpos finitios de característica 2 fueron anunciados por:

  • Robert Granger, Faruk Göloğlu, Gary McGuire, y Jens Zumbragel el 11 de abril 2013. La nueva computación trataba con el cuerpo de 26120 elementos y demoró 749,5 horas de CPU.
  • Antoine Joux el 22 de marzo de 2013. Utilizó el mismo algoritmo[4]​ para cuerpos de característica pequeña que en la anterior computación del cuerpo de 21778 elementos. Se computó en el cuerpo con 24080 elementos, representado como una extensión de grado 255 del cuerpo con 216 elementos, utilizando para ello menos de 14100 horas de CPU.[5]​
  • Robert Granger, Faruk Göloğlu, Gary McGuire, y Jens Zumbragel el 19 de febrero de 2013. Utilizaron una nueva variante de la criba general del cuerpo de números con un cuerpo base de tamaño medio, para cuerpos binarios, para computar un logaritmo discreto en un cuerpo de 21971 elementos. Para poder usar un cuerpo base de tamaño medio representaron el cuerpo como una extensión de grado 73 del cuerpo de 227 elementos. La computación demoró 3132 horas de CPU en un clúster SGI Altix ICE 8200EX utilizando procesadores de 6 núcleos Intel (Westmere) Xeon E5650.[6]​
  • Antoine Joux el 11 de febrero de 2013. Utilizaba un nuevo algoritmo para cuerpos de característica pequeña. Se computó en un cuerpo de 21778 elementos, representedo como una extensión de grado 127 del cuerpo con 214 elementos. El cómputo se realizó en menos de 220 horas de CPU.[7]​

El récord actual (a fecha de 2013) para un cuerpo finito de característica 2 de grado primo fue anunciado por el grupo CARAMEL el 6 de abril de 2013. Emplearon la criba general del cuerpo de números para computar un logaritmo discreto en una cuerpo de 2809 elementos.[8]​ El récord anterior en un cuerpo finito de característica 2 de grado primo fue anunciado por Antoine Joux y Reynald Lercier el 23 de septiembre de 2005. Emplearon la criba general del cuerpo de números para computar un logaritmo discreto en un cuerpo de 2613 elementos. El cómputo demoró 17 días en cuatro nodos de 16 procesadores, a 1.3 GHz cada uno, del súper-ordenador Teranova, basado en el Itanium 2.[9]​

El récord actual (a fecha de 2012) para un cuerpo de característica 3 fue anunciado por una asociación entre Fujitsu, NICT y el equipo de la Universidad de Kyushu, que computaron un logaritmo discreto en el cuerpo de 36 · 97 elementos, de 923 bits de tamaño,[10]​ empleando una variante de la criba general del cuerpo de números, superando así el récord anterior en el cuerpo de 36 · 71 elementos de 676 bits [11]​ por un amplio margen.

Respecto a cuerpos de característica de tamaño "moderado", computaciones notables realizadas en 2005 incluyen aquella sobre el cuerpo de 6553725 elementos (401 bits), anunciada el 24 de octubre de 2005, y la del cuerpo de 37080130 elementos (556 bits), anunciada el 9 de noviembre de 2005.[12]​ El récord actual (a fecha de 2013) para un cuerpo finito de característica "moderada" fue anunciada el 6 de enero de 2013. El equipo empleo una nueva variante de la criba general del cuerpo de números para el caso de primos medios para computar un logaritmo discreto en un cuerpo de 3334135357 elementos (un cuerpo finito de 1425 bits).[13]​[14]​ Se había empleado la misma técnica unas semanas antes para computar un logaritmo discreto en un cuerpo de 3355377147 elementos (un cuerpo finito de 1175 bits).[15]​[14]​

Curvas elípticas

[editar]

La corporación Certicom ha propuesto una serie de desafíos relacionados con la Criptografía de curva elíptica. El nivel I involucra cuerpos de 109 y 131 bits. El nivel II incluye los de 163, 191, 239 y 359 bits. Se cree que todos los desafíos de nivel II son computacionalmente inviables.[16]​

Los desafíos de nivel I que han sido superados son:[17]​

  • ECC2K-108, consistente en tomar un logaritmo discreto en una curva de Koblitz sobre un cuerpo de 2108 elementos. El premio fue otorgado el 4 de abril de 2000 a un grupo de unas 1300 personas, representado por Robert Harley. Utilizaron una paralelización del algoritmo rho de Pollard para logaritmos.
  • ECC2-109, que consistía en tomar un logaritmo discreto en una curva sobre un cuerpo de 2109 elementos. El 8 de abril de 2004 se otorgó el premio a un grupo de unas 2600 personas representado por Chris Monico. También emplearon una versión paralelizada del algoritmo rho de Pollard para logaritmos, durando el cáculo 17 meses de tiempo real.
  • ECCp-109, consistente en tomar un logaritmo discreto en una curva módulo un primo de 109 bits. El premio se otorgó el 15 de abril de 2002 a un grupo de 10308 personas, representado por Chris Monico. De nuevo se empleó una variante paralelizada del algoritmo rho de Pollard para logaritmos, demorando 549 días de tiempo real.

Ninguno de los desafíos de 131 bits (o superiores) han sido superados a fecha de 2010.

En julio de 2009, Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra y Peter L. Montgomery anunciaron que habían conseguido computar un logaritmo discreto en una curva elíptica módulo un primo de 112 bits. La computación fue realizada mediante un clúster de 200 PlayStation 3 durante 6 meses, empleando la versión paralelizada más común del algoritmo rho de Pollard para logaritmos.[18]​

Referencias

[editar]
  1. ↑ Antoine Joux, “Discrete logarithms in GF(p) – 130 digits,” June 18, 2005, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0506&L=nmbrthry&T=0&P=20.
  2. ↑ Thorsten Kleinjung, “Discrete logarithms in GF(p) – 160 digits,” February 5, 2007, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0702&L=NMBRTHRY&P=R45&D=0&I=-3&T=0.
  3. ↑ Antoine Joux, "Discrete logarithms in GF(26168) [=GF((2257)24)]", May 21, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1305&L=NMBRTHRY&F=&S=&P=3034.
  4. ↑ Antoine Joux. A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic, 2013, http://eprint.iacr.org/2013/095
  5. ↑ Antoine Joux, "Discrete logarithms in GF(24080)", Mar 22, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682.
  6. ↑ Faruk Gologlu et al., On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in , 2013, http://eprint.iacr.org/2013/074.
  7. ↑ Antoine Joux, "Discrete logarithms in GF(21778)", Feb. 11, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317.
  8. ↑ The CARAMEL group: Razvan Barbulescu and Cyril Bouvier and Jérémie Detrey and Pierrick Gaudry and Hamza Jeljeli and Emmanuel Thomé and Marion Videau and Paul Zimmermann, “Discrete logarithm in GF(2809) with FFS”, April 6, 2013, http://eprint.iacr.org/2013/197.
  9. ↑ Antoine Joux, “Discrete logarithms in GF(2607) and GF(2613),” September 23, 2005, http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0509&L=NMBRTHRY&P=R1490&D=0&I=-3&T=0.
  10. ↑ Kyushu University, NICT and Fujitsu Laboratories Achieve World Record Cryptanalysis of Next-Generation Cryptography, 2012, http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf.
  11. ↑ Takuya Hayashi et al., Solving a 676-bit Discrete Logarithm Problem in GF(36n), 2010, http://eprint.iacr.org/2010/090.
  12. ↑ A. Durand, “New records in computations over large numbers,” The Security Newsletter, January 2005, «Copia archivada». Archivado desde el original el 10 de julio de 2011. Consultado el 30 de diciembre de 2010. .
  13. ↑ Antoine Joux, “Discrete Logarithms in a 1425-bit Finite Field,” January 6, 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1301&L=NMBRTHRY&F=&S=&P=2214.
  14. ↑ a b Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite fields, Eprint Archive, http://eprint.iacr.org/2012/720
  15. ↑ Antoine Joux, “Discrete Logarithms in a 1175-bit Finite Field,” December 24, 2012, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1212&L=NMBRTHRY&F=&S=&P=13902.
  16. ↑ Certicom Corp., “The Certicom ECC Challenge,” «Copia archivada». Archivado desde el original el 20 de noviembre de 2008. Consultado el 19 de noviembre de 2008. .
  17. ↑ Certicom Research, Certicom ECC Challenge (Certicom Research, November 10, 2009), «Copia archivada». Archivado desde el original el 22 de octubre de 2015. Consultado el 30 de diciembre de 2010. .
  18. ↑ 1. Joppe W. Bos and Marcelo E. Kaihara, “PlayStation 3 computing breaks 2^60 barrier: 112-bit prime ECDLP solved,” EPFL Laboratory for cryptologic algorithms - LACAL, http://lacal.epfl.ch/112bit_prime
Obtenido de «https://es.wikipedia.org/w/index.php?title=Récords_en_logaritmos_discretos&oldid=161028686»