Registros de logaritmos discretos

Los registros de logaritmo discreto son los mejores resultados obtenidos hasta la fecha en la resolución del problema del logaritmo discreto , que es el problema de encontrar soluciones.${\displaystyle x}$a la ecuación${\displaystyle g^{x}=h}$elementos dados${\displaystyle g}$y${\displaystyle h}$de un grupo cíclico finito${\displaystyle G}$La dificultad de este problema es la base de la seguridad de varios sistemas criptográficos , incluyendo el acuerdo de clave Diffie-Hellman , el cifrado ElGamal , el esquema de firma ElGamal , el algoritmo de firma digital y los análogos de criptografía de curva elíptica de estos. Opciones comunes para${\displaystyle G}$Los algoritmos utilizados incluyen el grupo multiplicativo de enteros módulo${\displaystyle p}$, el grupo multiplicativo de un cuerpo finito , y el grupo de puntos en una curva elíptica sobre un cuerpo finito.

La corrienteEl récord para enteros módulo números primos , establecido en diciembre de 2019, es un cálculo de logaritmo discreto módulo un primo con 240 dígitos. Para característica 2, el récord actual para campos finitos, establecido en julio de 2019, es un logaritmo discreto sobre${\displaystyle \mathrm {GF} (2^{30750})}$Cuando se restringe a exponentes primos , el récord actual, establecido en octubre de 2014, supera${\displaystyle \mathrm {GF} (2^{1279})}$. Para la característica 3, el récord actual, establecido en julio de 2016, es superior${\displaystyle \mathrm {GF} (3^{6*509})}$. Para los campos de extensión de Kummer de característica "moderada" , el récord actual, establecido en enero de 2013, es superior a${\displaystyle \mathrm {GF} (33341353^{57})}$. Para campos de característica "moderada" (que no son necesariamente extensiones de Kummer), el registro actual, publicado en 2022, supera${\displaystyle \mathrm {GF} (2111023^{50})}$.

Los récords anteriores para enteros módulo p incluyen:

• 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 logaritmo discreto módulo el primo de 240 dígitos (795 bits) RSA-240 + 49204 (el primer 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 cálculo del logaritmo discreto tardó aproximadamente 3100 años-núcleo, utilizando como referencia las CPU Intel Xeon Gold 6130 (2,1  GHz). Los investigadores estiman que las mejoras en los algoritmos y el software hicieron que este cálculo fuera tres veces más rápido de lo que se esperaría de los récords anteriores, teniendo en cuenta las mejoras en el hardware. ^{[ 1 ] [ 2 ]}
• El 16 de junio de 2016, Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra , Christine Priplata y Colin Stahlke anunciaron el cálculo de un logaritmo discreto módulo un primo seguro de 232 dígitos (768 bits), utilizando el método de criba de cuerpos numéricos. El cálculo se inició en febrero de 2015 y tardó aproximadamente 6600 años de núcleo, escalado a un procesador 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 logaritmo discreto módulo un 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 criba de campos numéricos . ^{[ 4 ]}
• El 5 de febrero de 2007, Thorsten Kleinjung anunció el cálculo de un logaritmo discreto módulo un número primo seguro de 160 dígitos (530 bits), utilizando nuevamente el método de criba de cuerpos numéricos. La mayor parte del cálculo se realizó aprovechando el tiempo de inactividad de varios ordenadores y de un clúster de computación paralela . ^{[ 5 ]}
• El 11 de junio de 2014, Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli y Emmanuel Thomé anunciaron el cálculo de un logaritmo discreto módulo un primo seguro de 180 dígitos (596 bits) utilizando el algoritmo de criba de campos numéricos. ^{[ 6 ]}

Cabe destacar también que, en julio de 2016, Joshua Fried, Pierrick Gaudry, Nadia Heninger y Emmanuel Thome publicaron su cálculo de logaritmo discreto en un número primo de 1024 bits. ^{[ 7 ]} Generaron un número primo susceptible al cribado de campos numéricos especiales , utilizando el algoritmo especializado en un subgrupo relativamente pequeño (160 bits). Si bien este es un subgrupo pequeño, era el tamaño de subgrupo estandarizado utilizado con el algoritmo de firma digital (DSA) de 1024 bits.

El registro actual ( a julio de 2019)) 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 ³⁰⁷⁵⁰ ) utilizando 25 481 219 horas de núcleo 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 cuasipolinomial. ^{[ 9 ]}

Los récords anteriores en un campo finito de característica 2 fueron anunciados por:

• Robert Granger, Thorsten Kleinjung y Jens Zumbrägel, el 31 de enero de 2014. Este equipo logró calcular logaritmos discretos en GF(2 ⁹²³⁴ ) utilizando aproximadamente 400 000 horas de núcleo. Las nuevas características de este cálculo incluyen un método modificado para obtener los logaritmos de elementos de grado dos y una estrategia de descenso sistemáticamente optimizada. ^{[ 10 ]}
• Antoine Joux, el 21 de mayo de 2013. Su equipo logró calcular logaritmos discretos en el campo con 2 ⁶¹⁶⁸ = (2 ²⁵⁷ ) ²⁴ elementos utilizando 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 ⁴⁰⁸⁰ 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 ⁶¹²⁰ elementos y requirió 749,5 horas de procesamiento.
• Antoine Joux, 22 de marzo de 2013. Se utilizó el mismo algoritmo ^{[ 12 ]} para campos de características pequeñas que el cálculo anterior en el campo con ^2¹⁷⁷⁸ elementos. El nuevo cálculo se refería al campo con ^{2¹⁶⁰⁸⁰} elementos, representado como una extensión de grado 255 del campo con ^2¹⁶ elementos. El cálculo requirió menos de 14 100 horas de núcleo. ^{[ 13 ]}
• Robert Granger, Faruk Göloğlu, Gary McGuire y Jens Zumbrägel, el 19 de febrero de 2013, utilizaron una nueva variante de la función de tamiz de campo base de tamaño medio , para campos binarios, para calcular un logaritmo discreto en un campo de ^2¹⁹⁷¹ elementos. Para utilizar un campo base de tamaño medio, representaron el campo como una extensión de grado 73 del campo de 2²⁷ ^elementos . El cálculo requirió 3132 horas de núcleo en un clúster SGI Altix ICE 8200EX con procesadores Intel (Westmere) Xeon E5650 de seis núcleos. ^{[ 14 ]}
• Antoine Joux, 11 de febrero de 2013. Este trabajo utilizó un nuevo algoritmo para campos de características pequeñas. El cálculo se realizó sobre un campo de ^2¹⁷⁷⁸ elementos, representado como una extensión de grado 127 del campo con 2¹⁴ ^elementos . El cálculo requirió menos de 220 horas de núcleo. ^{[ 15 ]}

El registro actual ( a partir de 2014)) en un campo finito de característica 2 de grado primo fue anunciado por Thorsten Kleinjung el 17 de octubre de 2014. El cálculo se realizó en un campo de 2 ¹²⁷⁹ elementos y siguió esencialmente el camino esbozado para${\displaystyle \mathrm {GF} (2^{4\cdot 1223})}$en ^{[ 16 ]} con dos excepciones principales en el cálculo de álgebra lineal y la fase de descenso. El tiempo total de ejecución fue inferior a cuatro años de núcleo. ^{[ 17 ]} El récord anterior en un campo finito de característica 2 de grado primo fue anunciado por el grupo CARAMEL el 6 de abril de 2013. Utilizaron la criba de campos de funciones para calcular un logaritmo discreto en un campo de 2 ⁸⁰⁹ elementos. ^{[ 18 ]}

El registro actual ( a julio de 2016)El cálculo para un campo de característica 3 fue anunciado por Gora Adj, Isaac Canales-Martinez, Nareli Cruz-Cortés, Alfred Menezes, Thomaz Oliveira, Francisco Rodriguez-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 llevó a cabo en varias computadoras del CINVESTAV y la Universidad de Waterloo . En total, se emplearon aproximadamente 200 años de tiempo de computación de núcleo en el cálculo. ^{[ 19 ]}

Se anunciaron récords previos 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 del 27 de enero de 2014. El cálculo resuelve el DLP en el campo de 1551 bits GF(3 ^{6 · 163} ), tomando 1201 horas de CPU. ^{[ 21 ] [ 22 ]}
• En 2012, un equipo conjunto de Fujitsu, NICT y la Universidad de Kyushu calculó un logaritmo discreto en un campo de 3 ^{6 · 97} elementos y un tamaño de 923 bits, ^{[ 23 ]} utilizando una variación de la función de criba de campo y superando el récord anterior en un campo de 3 ^{6 · 71} elementos y un tamaño de 676 bits por un amplio margen. ^{[ 24 ]}

En campos de características de tamaño "moderado", los cálculos notables hasta 2005 incluyeron aquellos en un campo de 65537 ²⁵ elementos (401 bits) anunciado el 24 de octubre de 2005, y en un campo de 370801 ³⁰ elementos (556 bits) anunciado el 9 de noviembre de 2005. ^{[ 25 ]} El récord actual (hasta 2013) para un campo finito de extensión de Kummer de características "moderadas" se anunció el 6 de enero de 2013. El equipo utilizó una nueva variación de la criba de campos de funciones para el caso primo medio para calcular un logaritmo discreto en un campo de extensión de Kummer de 33341353 ⁵⁷ 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 extensión de Kummer de 33553771 ⁴⁷ elementos (un campo finito de 1175 bits). ^{[ 27 ] [ 28 ]} El récord actual (a partir de 2022) para un campo finito de característica "moderada" (que no es necesariamente una extensión de Kummer) es el cálculo del logaritmo discreto en un campo de 2111023 ⁵⁰ elementos (un campo finito de 1051 bits); ^{[ 29 ]} el récord anterior ^{[ 30 ]} de cálculos de logaritmo discreto sobre tales campos fue sobre campos que tenían 297079 ⁴⁰ elementos (un campo finito de 728 bits) y 64373 ³⁷ elementos (un campo finito de 592 bits). Estos cálculos se realizaron utilizando nuevas ideas para acelerar el proceso de cribado de campos funcionales.

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 cuerpo finito cuyo orden tiene 160 dígitos y es una extensión de grado 2 de un cuerpo primo. ^{[ 31 ]} El algoritmo utilizado fue el cribado de cuerpos numéricos (NFS), con varias modificaciones. El tiempo total de cálculo fue equivalente a 68 días en un núcleo de CPU (cribado) y 30 horas en una GPU (álgebra lineal).

Certicom Corp. ha publicado una serie de desafíos de criptografía de curva elíptica . El Nivel I involucra campos de 109 y 131 bits. El Nivel II incluye campos de 163, 191, 239 y 359 bits. Actualmente se considera que todos los desafíos del Nivel II son computacionalmente inviables. ^{[ 32 ]}

Los desafíos de Nivel I que se han superado son: ^{[ 33 ]}

• ECC2K-108, que consiste en calcular un logaritmo discreto en una curva de Koblitz sobre un campo de 2 ^{× 10⁸ elementos. El premio se otorgó el 4 de abril de 2000 a un grupo de aproximadamente 1300 personas, representado por Robert Harley. Utilizaron un} método rho de Pollard paralelizado con aceleración.
• ECC2-109, que consiste en calcular un logaritmo discreto sobre una curva en un campo de ^2¹⁰⁹ elementos. El premio se otorgó el 8 de abril de 2004 a un grupo de aproximadamente 2600 personas, representado por Chris Monico. También utilizaron una versión paralelizada del método rho de Pollard, que requirió 17 meses de tiempo calendario.
• ECCp-109, que consiste en calcular un logaritmo discreto sobre una curva módulo un número primo de 109 bits. El premio se otorgó el 15 de abril de 2002 a un grupo de aproximadamente 10 308 personas, representado por Chris Monico. Una vez más, utilizaron una versión paralelizada del método rho de Pollard, que requirió 549 días de tiempo calendario.

Ninguno de los desafíos de 131 bits (o mayores) se ha superado hasta 2019..

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 ^{[ 34 ]} ) módulo un número primo de 112 bits. El cálculo se realizó en un clúster 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. ^{[ 35 ]}

En abril de 2014, Erich Wenger y Paul Wolfger de la Universidad Tecnológica de Graz resolvieron el logaritmo discreto de una curva de Koblitz de 113 bits en 24 días extrapolados ^{[ nota 1 ]} utilizando un clúster FPGA Virtex-6 de 18 núcleos . ^{[ 36 ]} 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 utilizando un clúster FPGA Kintex-7 de 10 núcleos . ^{[ 37 ]}

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 logaritmo discreto en una curva elíptica de 117,35 bits sobre una curva binaria, utilizando una implementación optimizada en FPGA de una versión paralela del método rho de Pollard. El ataque se ejecutó durante aproximadamente seis meses en entre 64 y 576 FPGA en paralelo. ^{[ 38 ]}

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 una curva de Barreto-Naehrig (BN) de 114 bits "amigable con el emparejamiento", ^{[ 39 ]} utilizando la propiedad especial de torsión séxtica de la curva BN para llevar a cabo eficientemente el paseo aleatorio del método rho de Pollard. La implementación utilizó 2000 núcleos de CPU y tardó aproximadamente 6 meses en resolver el problema. ^{[ 40 ]}

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 resolviendo una clave privada de 114 bits en el Bitcoin Puzzle Transactions Challenge. Para establecer un nuevo récord, utilizaron su propio software ^{[ 41 ]} basado en el Pollard Kangaroo en un procesador GPU NVIDIA Tesla V100 de 256x y les tomó 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.

• Cálculos de logaritmos discretos ordenados por fecha