Registros del logaritmo discreto son los mejores resultados obtenidos hasta la fecha en la solución del logaritmo discreto problema, que es el problema de encontrar soluciones de x a la ecuación g x = h dado elementos g y h de un finito grupo cíclico G . La dificultad de este problema es la base para la seguridad de varios sistemas criptográficos , incluido el acuerdo de claves Diffie-Hellman , el cifrado ElGamal , el esquema de firma ElGamal , el algoritmo de firma digital y la criptografía de curva elíptica.análogos de estos. Las opciones comunes para G utilizadas en estos algoritmos incluyen el grupo multiplicativo de números enteros módulo p , el grupo multiplicativo de un campo finito y el grupo de puntos en una curva elíptica sobre un campo finito .
Enteros módulo p
- El 2 de diciembre de 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger , Emmanuel Thomé y Paul Zimmermann anunciaron el cálculo de un módulo de logaritmo discreto de 240 dígitos (795 bits) primo RSA-240 + 49204 (el primer número primo seguro por encima de RSA-240). Este cálculo se realizó simultáneamente con la factorización de RSA-240, utilizando el algoritmo Number Field Sieve y el software de código abierto CADO-NFS. La parte del logaritmo discreto del cálculo tomó aproximadamente 3100 años-núcleo, usando CPUs Intel Xeon Gold 6130 como referencia (2.1GHz). Los investigadores estiman que las mejoras en los algoritmos y el software hicieron que este cálculo sea tres veces más rápido de lo que se esperaría de los registros anteriores después de tener en cuenta las mejoras en el hardware. [1] [2]
Los registros anteriores para números enteros módulo p incluyen:
- El 16 de junio de 2016, Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra , Christine Priplata y Colin Stahlke anunciaron el cálculo de un módulo de logaritmo discreto un número primo seguro de 232 dígitos (768 bits) , utilizando el tamiz de campo numérico. El cálculo se inició en febrero de 2015 y tomó aproximadamente 6600 años de núcleo escalado a un Intel Xeon E5-2660 a 2,2 GHz. [3]
- El 18 de junio de 2005, Antoine Joux y Reynald Lercier anunciaron el cálculo de un módulo de logaritmo discreto, un número primo fuerte de 130 dígitos (431 bits) en tres semanas, utilizando una computadora HP AlphaServer GS1280 de 1.15 GHz y 16 procesadores y un algoritmo de tamiz de campo numérico. . [4]
- El 5 de febrero de 2007, esto fue reemplazado por el anuncio de Thorsten Kleinjung del cálculo de un módulo de logaritmo discreto, un número primo seguro de 160 dígitos (530 bits) , nuevamente utilizando el tamiz de campo numérico. La mayor parte del cálculo se realizó utilizando tiempo de inactividad en varias PC y en un clúster de computación en paralelo. [5]
- El 11 de junio de 2014, Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli y Emmanuel Thomé anunciaron el cálculo de un módulo de logaritmo discreto un número primo seguro de 180 dígitos (596 bits) utilizando el algoritmo de tamiz de campo numérico. [6]
También es de destacar que en julio de 2016, Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome publicaron su cálculo de logaritmo discreto en un número primo de 1024 bits. [7] Generaron un primo susceptible al tamiz de campo numérico especial, utilizando el algoritmo especializado en un subgrupo comparativamente pequeño (160 bits). Si bien este es un subgrupo pequeño, fue el tamaño de subgrupo estandarizado utilizado con el algoritmo de firma digital (DSA) de 1024 bits.
Campos finitos
El récord actual (a julio de 2019[actualizar]) en un campo finito de característica 2 fue anunciado por Robert Granger, Thorsten Kleinjung, Arjen Lenstra, Benjamin Wesolowski y Jens Zumbrägel el 10 de julio de 2019. [8] Este equipo pudo calcular logaritmos discretos en GF (2 30750 ) usando 25,481,219 horas centrales en clústeres basados en la arquitectura Intel Xeon. Este cálculo fue el primer ejemplo a gran escala que utilizó el paso de eliminación del algoritmo cuasi-polinomial. [9]
Los registros anteriores en un campo finito de la característica 2 fueron anunciados por:
- Robert Granger, Thorsten Kleinjung y Jens Zumbrägel el 31 de enero de 2014. Este equipo pudo calcular logaritmos discretos en GF (2 9234 ) utilizando aproximadamente 400.000 horas centrales. Las nuevas características de este cálculo incluyen un método modificado para obtener los logaritmos de los elementos de grado dos y una estrategia de descenso optimizada sistemáticamente. [10]
- Antoine Joux el 21 de mayo de 2013. Su equipo pudo calcular logaritmos discretos en el campo con 2 6168 = (2 257 ) 24 elementos usando menos de 550 horas de CPU. Este cálculo se realizó utilizando el mismo algoritmo de cálculo de índices que en el cálculo reciente en el campo con 2 4080 elementos. [11]
- Robert Granger, Faruk Göloğlu, Gary McGuire y Jens Zumbrägel el 11 de abril de 2013. El nuevo cálculo se refería al campo con 2 6120 elementos y tomó 749,5 horas-núcleo.
- Antoine Joux el 22 de marzo de 2013. Este utilizó el mismo algoritmo [12] para campos característicos pequeños que el cálculo anterior en el campo con 2 1778 elementos. El nuevo cálculo se refería al campo con 2 4080 elementos, representado como una extensión de grado 255 del campo con 2 16 elementos. El cálculo tomó menos de 14100 horas centrales. [13]
- Robert Granger, Faruk Göloğlu, Gary McGuire y Jens Zumbrägel el 19 de febrero de 2013. Utilizaron una nueva variante del tamiz de campo de función de campo base de tamaño mediano , para campos binarios, para calcular un logaritmo discreto en un campo de 2 1971 elementos. Para utilizar un campo base de tamaño mediano, representaron el campo como una extensión de grado 73 del campo de 2 27 elementos. El cálculo tomó 3132 horas centrales en un clúster SGI Altix ICE 8200EX utilizando procesadores Intel (Westmere) Xeon E5650 de núcleo hexagonal. [14]
- Antoine Joux el 11 de febrero de 2013. Este utilizó un nuevo algoritmo para pequeños campos característicos. El cálculo se refería a un campo de 2 1778 elementos, representado como una extensión de grado 127 del campo con 2 14 elementos. El cálculo tomó menos de 220 horas centrales. [15]
El récord actual (a partir de 2014[actualizar]) en un campo finito de característica 2 de primer grado fue anunciado por Thorsten Kleinjung el 17 de octubre de 2014. El cálculo se realizó en un campo de 2 1279 elementos y siguió esencialmente el camino trazado paraen [16] con dos excepciones principales en el cálculo del álgebra lineal y la fase de descenso. El tiempo total de ejecución fue de menos de cuatro años centrales. [17] El registro anterior en un campo finito de característica 2 de primer grado fue anunciado por el grupo CARAMEL el 6 de abril de 2013. Usaron el campo de función tamiz para calcular un logaritmo discreto en un campo de 2 809 elementos. [18]
El récord actual (a julio de 2016[actualizar]) para un campo de característica 3 fue anunciado por Gora Adj, Isaac Canales-Martínez, Nareli Cruz-Cortés, Alfred Menezes, Thomaz Oliveira, Francisco Rodríguez-Henriquez y Luis Rivera-Zamarripa el 18 de julio de 2016. El cálculo se realizó en el Campo finito de 4841 bits con 3 6 · 509 elementos y se realizó en varias computadoras en CINVESTAV y la Universidad de Waterloo . En total, se gastaron alrededor de 200 años centrales de tiempo de computación en la computación. [19]
Se anunciaron registros anteriores en un campo finito de característica 3:
- en la versión completa del artículo de Asiacrypt 2014 de Joux y Pierrot (diciembre de 2014). [20] El DLP se resuelve en el campo GF (3 5 · 479 ), que es un campo de 3796 bits. Este trabajo no explotó ningún aspecto "especial" del campo, como las propiedades de Kummer o twisted-Kummer. El cálculo total tomó menos de 8600 horas de CPU.
- por Gora Adj, Alfred Menezes, Thomaz Oliveira y Francisco Rodríguez-Henríquez el 26 de febrero de 2014, actualizando un anuncio anterior el 27 de enero de 2014. El cálculo resuelve DLP en el campo GF de 1551 bits (3 6 · 163 ), tomando 1201 CPU horas. [21] [22]
- en 2012 por un equipo conjunto de Fujitsu, NICT y la Universidad de Kyushu, que calculó un logaritmo discreto en el campo de 3 6 · 97 elementos y un tamaño de 923 bits, [23] usando una variación en el tamiz del campo de función y superando el anterior registro en un campo de 3 6 · 71 elementos y tamaño de 676 bits por un amplio margen. [24]
En los campos de característica de tamaño "moderado", los cálculos notables a partir de 2005 incluyeron los de un campo de 65537 25 elementos (401 bits) anunciado el 24 de octubre de 2005, y en un campo de 370801 30 elementos (556 bits) anunciado el 9 de noviembre de 2005 . [25] El récord actual (a partir de 2013) para un campo finito de característica "moderada" se anunció el 6 de enero de 2013. El equipo utilizó una nueva variación del tamiz de campo de función para el caso medio principal para calcular un logaritmo discreto en un campo de 33341353 57 elementos (un campo finito de 1425 bits). [26] [27] La misma técnica se había utilizado unas semanas antes para calcular un logaritmo discreto en un campo de 33553771 47 elementos (un campo finito de 1175 bits). [27] [28]
El 25 de junio de 2014, Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic y François Morain anunciaron un nuevo cálculo de un logaritmo discreto en un campo finito cuyo orden tiene 160 dígitos y es una extensión de grado 2 de un campo primo. [29] El algoritmo utilizado fue el tamiz de campo numérico (NFS), con varias modificaciones. El tiempo total de computación fue equivalente a 68 días en un núcleo de CPU (tamizado) y 30 horas en una GPU (álgebra lineal).
Curvas elípticas
Certicom Corp. ha publicado una serie de desafíos de criptografía de curva elíptica. El nivel I implica campos de tamaños de 109 y 131 bits. El nivel II incluye tamaños de 163, 191, 239 y 359 bits. Actualmente se cree que todos los desafíos de Nivel II son computacionalmente inviables. [30]
Los desafíos de Nivel I que se han superado son: [31]
- ECC2K-108, que implica tomar un logaritmo discreto en una curva de Koblitz sobre un campo de 2 108 elementos. El premio fue otorgado el 4 de abril de 2000 a un grupo de aproximadamente 1300 personas representadas por Robert Harley. Utilizaron un método de Pollard rho paralelizado con aceleración.
- ECC2-109, que implica tomar un logaritmo discreto en una curva sobre un campo de 2 109 elementos. El premio fue otorgado el 8 de abril de 2004 a un grupo de unas 2600 personas representadas por Chris Monico. También utilizaron una versión de un método rho de Pollard en paralelo , que tomaba 17 meses de tiempo calendario.
- ECCp-109, que implica tomar un logaritmo discreto en un módulo de curva con un número primo de 109 bits. El premio fue otorgado el 15 de abril de 2002 a un grupo de aproximadamente 10308 personas representadas por Chris Monico. Una vez más, utilizaron una versión de un método rho de Pollard paralelizado , tomando 549 días de tiempo calendario.
Ninguno de los desafíos de 131 bits (o más grandes) se ha cumplido a partir de 2019[actualizar].
En julio de 2009, Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra y Peter L. Montgomery anunciaron que habían realizado un cálculo de logaritmo discreto en una curva elíptica (conocida como secp112r1 [32] ) módulo a Prima de 112 bits. El cálculo se realizó en un grupo de más de 200 consolas de juegos PlayStation 3 durante aproximadamente 6 meses. Utilizaron la versión paralelizada común del método rho de Pollard . [33]
En abril de 2014, Erich Wenger y Paul Wolfger de la Universidad de Tecnología de Graz resolvieron el logaritmo discreto de una curva de Koblitz de 113 bits en 24 días extrapolados utilizando un clúster FPGA Virtex-6 de 18 núcleos . [34] En enero de 2015, los mismos investigadores resolvieron el logaritmo discreto de una curva elíptica definida sobre un campo binario de 113 bits. El tiempo de ejecución promedio es de alrededor de 82 días usando un clúster FPGA Kintex-7 de 10 núcleos . [35]
El 2 de diciembre de 2016, Daniel J. Bernstein , Susanne Engels , Tanja Lange , Ruben Niederhagen , Christof Paar , Peter Schwabe y Ralf Zimmermann anunciaron la solución de un problema genérico de logaritmos discretos de curva elíptica de 117,35 bits en una curva binaria, utilizando un método optimizado Implementación FPGA de una versión paralela del algoritmo rho de Pollard . El ataque duró unos seis meses en 64 a 576 FPGA en paralelo. [36]
El 23 de agosto de 2017, Takuya Kusaka, Sho Joichi, Ken Ikuta, Md. Al-Amin Khandaker, Yasuyuki Nogami, Satoshi Uehara, Nariyoshi Yamai y Sylvain Duquesne anunciaron que habían resuelto un problema de logaritmo discreto en un emparejamiento de 114 bits. amigable "curva de Barreto-Naehrig (BN), [37] utilizando la propiedad especial de torsión sextica de la curva BN para llevar a cabo de manera eficiente la caminata aleatoria del método rho de Pollard. La implementación usó 2000 núcleos de CPU y tomó alrededor de 6 meses resolver el problema. [38]
El 16 de junio de 2020, Aleksander Zieniewicz (zielar) y Jean Luc Pons ( JeanLucPons ) anunciaron la solución de un problema de logaritmo discreto de curva elíptica de intervalo de 114 bits en la curva secp256k1 al resolver una clave privada de 114 bits en Bitcoin Puzzle Transactions Challenge. Para establecer un nuevo récord, utilizaron su propio software [39] basado en Pollard Kangaroo en un procesador GPU NVIDIA Tesla V100 de 256x y les llevó 13 días. Dos semanas antes: utilizaron la misma cantidad de tarjetas gráficas para resolver un ECDLP de intervalo de 109 bits en solo 3 días.
Referencias
- ^ Emmanuel Thomé, "factorización de 795 bits y logaritmos discretos" , 2 de diciembre de 2019.
- ^ F. Boudot et al, "Comparación de la dificultad de la factorización y el logaritmo discreto: un experimento de 240 dígitos" , 10 de junio de 2020.
- ^ Thorsten Kleinjung, "Logaritmos discretos en GF ( p ) - 768 bits" , 16 de junio de 2016.
- ^ Antoine Joux, "Logaritmos discretos en GF ( p ) - 130 dígitos" , 18 de junio de 2005.
- ^ Thorsten Kleinjung, "Logaritmos discretos en GF ( p ) - 160 dígitos" , 5 de febrero de 2007.
- ^ Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli y Emmanuel Thomé, "Logaritmos discretos en GF ( p ) - 180 dígitos"
- ^ Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome, "A kilobit hidden snfs discrete logarithm computation" , IACR spring, julio de 2016
- ^ Jens Zumbrägel, "Discrete Logarithms in GF (2 ^ 30750)", 10 de julio de 2019, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;62ab27f0.1907 .
- ^ R. Granger, T. Kleinjung, J. Zumbragel. Sobre el problema del logaritmo discreto en campos finitos de característica fija. Trans. Amer. Matemáticas. Soc. 370, no. 5 (2018), págs. 3129-3145.
- ^ Jens Zumbrägel, "Discrete Logarithms in GF (2 ^ 9234)", 31 de enero de 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;9aa2b043.1401 .
- ^ Antoine Joux, "Logaritmos discretos en GF (2 6168 ) [= GF ((2 257 ) 24 )]", 21 de mayo de 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2 = ind1305 & L = NMBRTHRY & F = & S = & P = 3034 .
- ^ Antoine Joux. Un nuevo algoritmo de cálculo de índices con complejidad $ L (1/4 + o (1)) $ en característica muy pequeña, 2013, http://eprint.iacr.org/2013/095
- ^ Antoine Joux, "Logaritmos discretos en GF (2 4080 )", 22 de marzo de 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1303&L=NMBRTHRY&F=&S=&P=13682 .
- ^ Faruk Gologlu et al., Sobre el tamiz de campo de función y el impacto de mayores probabilidades de división: aplicación a logaritmos discretos en, 2013, http://eprint.iacr.org/2013/074 .
- ^ Antoine Joux, "Logaritmos discretos en GF (2 1778 )", 11 de febrero de 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1302&L=NMBRTHRY&F=&S=&P=2317 .
- ^ Granger, Robert, Thorsten Kleinjung y Jens Zumbrägel. "Rompiendo curvas binarias supersingulares seguras de 128 bits" (o cómo resolver logaritmos discretos en y ). " arXiv: 1402.3668 [cs, Math], 15 de febrero de 2014. https://arxiv.org/abs/1402.3668 .
- ^ Thorsten Kleinjung, 17 de octubre de 2014, "Logaritmos discretos en GF (2 ^ 1279)", https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;256db68e.1410 .
- ^ El grupo CARAMEL: Razvan Barbulescu y Cyril Bouvier y Jérémie Detrey y Pierrick Gaudry y Hamza Jeljeli y Emmanuel Thomé y Marion Videau y Paul Zimmermann, “Discrete logarithm in GF ( 2809 ) with FFS”, 6 de abril de 2013, http: / /eprint.iacr.org/2013/197 .
- ^ Francisco Rodríguez-Henriquez, 18 de julio de 2016, "Logaritmos discretos en GF (3 ^ {6 * 509})", https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;65bedfc8. 1607 .
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 11 de diciembre de 2014 . Consultado el 11 de diciembre de 2014 .CS1 maint: copia archivada como título ( enlace )
- ↑ Francisco Rodríguez-Henríquez, “Announcement”, 27 de enero de 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;763a9e76.1401 .
- ^ Gora Adj y Alfred Menezes y Thomaz Oliveira y Francisco Rodríguez-Henríquez, "Computación de logaritmos discretos en F_ {3 ^ {6 * 137}} y F_ {3 ^ {6 * 163}} usando Magma", 26 de febrero de 2014, http : //eprint.iacr.org/2014/057 .
- ^ Kyushu University, NICT y Fujitsu Laboratories logran un criptoanálisis récord mundial de criptografía de próxima generación, 2012, http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf .
- ^ Takuya Hayashi et al., Resolver un problema de logaritmo discreto de 676 bits en GF (3 6 n ), 2010, http://eprint.iacr.org/2010/090 .
- ^ A. Durand, "Nuevos registros en cálculos sobre grandes números", The Security Newsletter, enero de 2005, http://eric-diehl.com/letter/Newsletter1_Final.pdf Archivado el 10 de julio de 2011en Wayback Machine .
- ^ Antoine Joux, "Logaritmos discretos en un campo finito de 1425 bits", 6 de enero de 2013, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1301&L=NMBRTHRY&F=&S=&P=2214 .
- ^ a b Cálculo de índices más rápido para el caso principal medio. Aplicación a campos finitos de 1175 bits y 1425 bits, Eprint Archive, http://eprint.iacr.org/2012/720
- ^ Antoine Joux, "Logaritmos discretos en un campo finito de 1175 bits", 24 de diciembre de 2012, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1212&L=NMBRTHRY&F=&S=&P=13902 .
- ^ Razvan Barbulescu, "Logaritmos discretos en GF (p ^ 2) --- 160 dígitos", 24 de junio de 2014, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;2ddabd4c. 1406 .
- ^ Certicom Corp., "El desafío de Certicom ECC", https://www.certicom.com/content/certicom/en/the-certicom-ecc-challenge.html
- ^ Certicom Research, Certicom ECC Challenge (Certicom Research, 10 de noviembre de 2009), "Copia archivada" (PDF) . Archivado desde el original (PDF) el 22 de octubre de 2015 . Consultado el 30 de diciembre de 2010 .CS1 maint: copia archivada como título ( enlace ) .
- ^ Investigación de Certicom, "SEC 2: Parámetros de dominio de curva elíptica recomendados" https://www.secg.org/SEC2-Ver-1.0.pdf
- ^ Joppe W. Bos y Marcelo E. Kaihara, "La informática de PlayStation 3 rompe la barrera 2 ^ 60: ECDLP principal de 112 bits resuelto", Laboratorio de EPFL para algoritmos criptológicos - LACAL, http://lacal.epfl.ch/112bit_prime
- ^ Erich Wenger y Paul Wolfger, "Resolver el logaritmo discreto de una curva de Koblitz de 113 bits con un clúster FPGA" http://eprint.iacr.org/2014/368
- ^ Erich Wenger y Paul Wolfger, "Más duro, mejor, más rápido, más fuerte: cálculos de logaritmos discretos de curva elíptica en FPGA" http://eprint.iacr.org/2015/143/
- ^ Ruben Niederhagen, "ECDLP de 117,35 bits en curva binaria", https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;628a3b51.1612 [ enlace muerto ]
- ^ "Se solucionó el ECDLP de 114 bits en una curva BN" . Consultado el 3 de mayo de 2018 .
- ^ Kusaka, Takuya; Joichi, Sho; Ikuta, Ken; Khandaker, Maryland Al-Amin; Nogami, Yasuyuki; Uehara, Satoshi; Yamai, Nariyoshi; Duquesne, Sylvain (2018). "Resolución de ECDLP de 114 bits para una curva de Barreto-Naehrig" (PDF) . Seguridad de la información y criptología - ICISC 2017 . Saltador. págs. 231–244. doi : 10.1007 / 978-3-319-78556-1_13 .
- ^ Pons, Jean-Luc; Zieniewicz, Aleksander. "Canguro de Pollard para SECPK1" .
enlaces externos
- Cálculos de logaritmos discretos ordenados por fecha