Diskreta logaritmposter

Diskreta logaritmposter är de bästa resultaten som hittills uppnåtts för att lösa det diskreta logaritmproblemet , vilket är problemet med att hitta lösningar x till ekvationen $g^{x}=h$ givna element g och h i en ändlig cyklisk grupp G . Svårigheten med detta problem är grunden för säkerheten för flera kryptografiska system, inklusive Diffie–Hellman- nyckelavtal, ElGamal-kryptering , ElGamal-signaturschemat , Digital Signature Algorithm och de elliptiska kurvornas kryptografiska analoger av dessa. Vanliga val för G som används i dessa algoritmer inkluderar den multiplikativa gruppen av heltal modulo p , den multiplikativa gruppen för ett ändligt fält och gruppen av punkter på en elliptisk kurva över ett ändligt fält .

Den aktuella ^{[ behovsuppdatering ]} -posten för heltal modulo primtal , som sattes i december 2019, är en diskret logaritmberäkning modulo ett primtal med 240 siffror. För egenskap 2 är det aktuella rekordet för finita fält , satt i juli 2019, en diskret logaritm över ${\displaystyle GF(2^{30750})$ . När det är begränsat till högsta möjliga grad ^{[ förtydligande behövs ]} är det nuvarande rekordet, satt i oktober 2014, över ${\displaystyle GF(2^{1279})$ . För egenskap 3 är det aktuella rekordet, satt i juli 2016, över ${\displaystyle GF(3^{6*509})$ . För fält med egenskapen "moderat" ^{[ förtydligande behövs ]} är det aktuella rekordet, satt i januari 2013, över $GF(33341353^{57})$ .

Heltal modulo sid

Den 2 december 2019 tillkännagav Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger , Emmanuel Thomé och Paul Zimmermann beräkningen av en diskret logaritmmodulo den 240-siffriga (795 bitars) prime RSA-240 + 49204 (den första säkra primtal) . ovan RSA-240). Denna beräkning utfördes samtidigt med faktoriseringen av RSA-240, med hjälp av Number Field Sieve-algoritmen och CADO-NFS-programvaran med öppen källkod. Den diskreta logaritmdelen av beräkningen tog cirka 3100 kärnår, med Intel Xeon Gold 6130-processorer som referens (2,1GHz). Forskarna uppskattar att förbättringar av algoritmerna och mjukvaran gjorde denna beräkning tre gånger snabbare än vad som skulle förväntas från tidigare rekord efter att ha redovisat förbättringar i hårdvara.

Tidigare poster för heltal modulo p inkluderar:

Den 16 juni 2016 tillkännagav Thorsten Kleinjung, Claus Diem, Arjen K. Lenstra , Christine Priplata och Colin Stahlke beräkningen av en diskret logaritm modulo ett 232-siffrigt (768-bitars) säkert primtal , med hjälp av talfältssikten. Beräkningen startades i februari 2015 och tog cirka 6600 kärnår skalat till en Intel Xeon E5-2660 vid 2,2 GHz.

Den 18 juni 2005 tillkännagav Antoine Joux och Reynald Lercier beräkningen av en diskret logaritmmodulo ett 130-siffrigt (431-bitars) starkt primtal på tre veckor, med hjälp av en 1,15 GHz 16-processor HP AlphaServer GS1280 - dator och en talfältsalgoritm .
Den 5 februari 2007 ersattes detta av tillkännagivandet av Thorsten Kleinjung om beräkningen av en diskret logaritm modulo ett 160-siffrigt (530-bitars) säkert primtal , återigen med hjälp av talfältssikten. Det mesta av beräkningen gjordes med vilotid på olika datorer och på ett parallellt beräkningskluster.
Den 11 juni 2014 tillkännagav Cyril Bouvier, Pierrick Gaudry, Laurent Imbert, Hamza Jeljeli och Emmanuel Thomé beräkningen av en diskret logaritm modulo ett 180-siffrigt (596-bitars) säkert primtal med hjälp av talfältssiktalgoritmen.

Också att notera, i juli 2016 publicerade Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome sin diskreta logaritmberäkning på ett 1024-bitars primtal. De genererade ett primtal som är känsligt för specialnummerfältsilen, med hjälp av den specialiserade algoritmen på en jämförelsevis liten undergrupp (160-bitar). Även om detta är en liten undergrupp, var det den standardiserade undergruppsstorleken som användes med 1024-bitars digital signaturalgoritm (DSA).

Diskret logaritm registrerar moduloprimtal
Storlek på prime	Typ av primtal	Datum meddelat	Meddelat av	Algoritm	Hårdvara	Anteckningar
240-siffriga (795-bitars)	säker prime	2 december 2019	Fabrice Boudot Pierrick Gaudry Aurore Guillevic Nadia Heninger Emmanuel Thomé Paul Zimmermann	nummerfältsåll		Det primtal som användes var RSA-240 + 49204 (den första säkra primeringen ovanför RSA-240). Denna beräkning utfördes samtidigt ^{[ hur? ]} med faktorisering av RSA-240, med hjälp av Number Field Sieve-algoritmen och CADO-NFS-programvaran med öppen källkod. Förbättringar i algoritmerna och mjukvaran ^{[ vilken? ]} gjorde denna beräkning ungefär tre gånger snabbare än vad som kunde förväntas från tidigare poster efter att ha tagit hänsyn till förbättringar i hårdvara.
1024-bitars		juli 2016	Joshua Fried Pierrick Gaudry Nadia Heninger Emmanuel Thome	specialnummerfältsåll		Forskarna genererade en prime mottaglig ^{[ varför? ]} till specialnummerfältet silen ^{[ hur? ]} med hjälp av en specialiserad algoritm ^{[ vilken? ]} på en jämförelsevis liten undergrupp (160-bitar).
232-siffriga (768-bitars)	säker prime	16 juni 2016	Thorsten Kleinjung Claus Diem Arjen K. Lenstra Christine Priplata Colin Stahlke	nummerfältsåll		Denna beräkning startade i februari 2015.
180 siffror (596-bitars)	säker prime	11 juni 2014	Cyril Bouvier Pierrick Gaudry Laurent Imbert Hamza Jeljeli Emmanuel Thomé	nummerfältsåll
160-siffriga (530-bitars)	säker prime	5 februari 2007	Thorsten Kleinjung	nummerfältsåll	olika datorer, ett parallellt datorkluster ^{[ vilket? ]}
130-siffriga (431-bitars)	stark prime	18 juni 2005	Antoine Joux Reynald Lercier	nummerfältssil	1,15 GHz 16-processor HP AlphaServer GS1280

Finita fält

Det aktuella rekordet (från och med juli 2019) i ett ändligt fält med karakteristik 2 tillkännagavs av Robert Granger, Thorsten Kleinjung, Arjen Lenstra, Benjamin Wesolowski och Jens Zumbrägel den 10 juli 2019. Detta team kunde beräkna diskreta logaritmer i GF( 2 ³⁰⁷⁵⁰ ) med 25 481 219 kärntimmar på kluster baserade på Intel Xeon-arkitekturen. Denna beräkning var det första exemplet i stor skala som använde elimineringssteget för kvasipolynomalgoritmen.

Tidigare rekord i ett ändligt fält av egenskap 2 tillkännagavs av:

Robert Granger, Thorsten Kleinjung och Jens Zumbrägel den 31 januari 2014. Detta team kunde beräkna diskreta logaritmer i GF(2 ⁹²³⁴ ) med cirka 400 000 kärntimmar. Nya funktioner i denna beräkning inkluderar en modifierad metod för att erhålla logaritmerna för grad två element och en systematiskt optimerad nedstigningsstrategi.
Antoine Joux den 21 maj 2013. Hans team kunde beräkna diskreta logaritmer i fält med 2 ⁶¹⁶⁸ = (2 ²⁵⁷ ) ²⁴ element med mindre än 550 CPU-timmar. Denna beräkning utfördes med samma indexkalkylalgoritm som i den senaste beräkningen i fält med 2 ⁴⁰⁸⁰ element.
Robert Granger, Faruk Göloğlu, Gary McGuire och Jens Zumbrägel den 11 april 2013. Den nya beräkningen gällde fältet med 2 ⁶¹²⁰ element och tog 749,5 kärntimmar.
Antoine Joux den 22 mars 2013. Denna använde samma algoritm för små karakteristiska fält som den tidigare beräkningen i fältet med 2 ¹⁷⁷⁸ element. Den nya beräkningen gällde fältet med 2 ⁴⁰⁸⁰ element, representerat som en grad 255 förlängning av fältet med 2 ¹⁶ element. Beräkningen tog mindre än 14100 kärntimmar.
Robert Granger, Faruk Göloğlu, Gary McGuire och Jens Zumbrägel den 19 februari 2013. De använde en ny variant av den medelstora basfältsfunktionsfältsikten för binära fält för att beräkna en diskret logaritm i ett fält med 2 ¹⁹⁷¹ element. För att använda ett medelstort basfält representerade de fältet som en grad 73 förlängning av fältet med 2 ²⁷ element. Beräkningen tog 3132 kärntimmar på ett SGI Altix ICE 8200EX-kluster med Intel (Westmere) Xeon E5650 hex-core-processorer.
Antoine Joux den 11 februari 2013. Detta använde en ny algoritm för små karakteristiska fält. Beräkningen gällde ett fält med 2 ¹⁷⁷⁸ element, representerat som en grad 127 förlängning av fältet med 2 ¹⁴ element. Beräkningen tog mindre än 220 kärntimmar.

Det aktuella rekordet (från och med 2014) i ett ändligt fält med karakteristik 2 av högsta grad tillkännagavs av Thorsten Kleinjung den 17 oktober 2014. Beräkningen gjordes i ett fält med 2 1279 element och följde i huvudsak den skisserade ^vägen för $\mathbb {F} _{2^{4\cdot 1223}}$ in med två huvudsakliga undantag i linjär algebraberäkning och nedstigningsfasen. Den totala körtiden var mindre än fyra kärnår. Det tidigare rekordet i ett ändligt fält med karakteristik 2 av prime grad tillkännagavs av CARAMEL-gruppen den 6 april 2013. De använde funktionsfältsilen för att beräkna en diskret logaritm i ett fält med 2 ⁸⁰⁹ element.

Det aktuella rekordet (från och med juli 2016) för ett fält med karakteristisk 3 tillkännagavs av Gora Adj, Isaac Canales-Martinez, Nareli Cruz-Cortés, Alfred Menezes, Thomaz Oliveira, Francisco Rodriguez-Henriquez och Luis Rivera-Zamarripa den 18 juli 2016. Beräkningen gjordes i det 4841-bitars finita fältet med 3 ^{6 · 509} element och utfördes på flera datorer vid CINVESTAV och University of Waterloo . Totalt har cirka 200 kärnår av beräkningstid lagts ner på beräkningen.

Tidigare rekord i ett ändligt fält av karakteristik 3 tillkännagavs:

i den fullständiga versionen av Asiacrypt 2014-tidningen av Joux och Pierrot (december 2014). DLP löses i fältet GF(3 ^{5 · 479} ), vilket är ett 3796-bitars fält. Detta arbete utnyttjade inte några "speciella" aspekter av fältet såsom Kummer eller twisted-Kummer-egenskaper. Den totala beräkningen tog mindre än 8600 CPU-timmar.
av Gora Adj, Alfred Menezes, Thomaz Oliveira och Francisco Rodríguez-Henríquez den 26 februari 2014, uppdatering av ett tidigare tillkännagivande den 27 januari 2014. Beräkningen löser DLP i 1551-bitarsfältet GF(3 6 · 163 ), med ¹²⁰¹ CPU timmar.
2012 av ett gemensamt team från Fujitsu, NICT och Kyushu University, som beräknade en diskret logaritm i fältet 3 ^{6 · 97} element och en storlek på 923 bitar, med hjälp av en variant av funktionsfältssikten och slog det tidigare rekordet i en fält på 3 ^{6 · 71} element och storlek på 676 bitar med bred marginal.

Över fält av "måttlig" storlek karakteristika, anmärkningsvärda beräkningar från 2005 inkluderade de ett fält på 65537 ²⁵ element (401 bitar) som tillkännagavs den 24 oktober 2005 och i ett fält på 370801 ³⁰ element (556 bitar) som tillkännagavs den 9 november 2005 Det aktuella rekordet (från och med 2013) för ett ändligt fält med "måttlig" karakteristik tillkännagavs den 6 januari 2013. Teamet använde en ny variant av funktionsfältsilen för det medelstora fallet för att beräkna en diskret logaritm i ett fält av 33341353 ⁵⁷ element (ett 1425-bitars ändligt fält). Samma teknik hade använts några veckor tidigare för att beräkna en diskret logaritm i ett fält med 33553771 ⁴⁷ element (ett 1175-bitars ändligt fält).

Den 25 juni 2014 tillkännagav Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic och François Morain en ny beräkning av en diskret logaritm i ett ändligt fält vars ordning har 160 siffror och är en grad 2 förlängning av ett primfält. Algoritmen som användes var nummerfältssilen (NFS), med olika modifieringar. Den totala beräkningstiden motsvarade 68 dagar på en kärna av CPU (siktning) och 30 timmar på en GPU (linjär algebra).

Diskreta logaritmposter över ändliga fält
Röding.	Fältstorlek	Datum meddelat	Meddelat av	Hårdvara	Beräkna	Anteckningar
2	2 ³⁰⁷⁵⁰	10 juli 2019	Robert Granger Thorsten Kleinjung Arjen Lenstra Benjamin Wesolowski Jens Zumbrägel	Intel Xeon- arkitektur	25 481 219 kärntimmar	Denna beräkning var det första exemplet i stor skala som använde elimineringssteget för kvasipolynomalgoritmen. ^{[ förtydligande behövs ]}
	2 ¹²⁷⁹	17 oktober 2014	Thorsten Kleinjung		<4 kärnår
	2 ⁹²³⁴	31 januari 2014	Robert Granger Thorsten Kleinjung Jens Zumbrägel		~400 000 kärntimmar	Nya funktioner i denna beräkning inkluderar en modifierad metod för att erhålla logaritmerna för grad två element och en systematiskt optimerad nedstigningsstrategi. ^{[ förtydligande behövs ]}
	2 ⁶¹⁶⁸	21 maj 2013	Antoine Joux		<550 CPU-timmar ^{[ kvantifiera ]}
	2 ⁶¹²⁰	11 april 2013	Robert Granger Faruk Göloğlu Gary McGuire Jens Zumbrägel		749,5 kärntimmar
	2 ⁸⁰⁹	6 april 2013	CARAMEL-gruppen ^{[ vem? ]}
	2 ⁴⁰⁸⁰	22 mars 2013	Antoine Joux		<14 100 kärntimmar ^{[ kvantifiera ]}
	2 ¹⁹⁷¹	19 februari 2013	Robert Granger Faruk Göloğlu Gary McGuire Jens Zumbrägel	SGI Altix ICE 8200EX kluster Intel (Westmere) Xeon E5650 hex-core-processorer	3 132 kärntimmar
	2 ¹⁷⁷⁸	11 februari 2013	Antoine Joux		<220 kärntimmar ^{[ kvantifiera ]}
3	3 ^{6 · 509}	18 juli 2016	Gora Adj Isaac Canales-Martinez Nareli Cruz-Cortés Alfred Menezes Thomaz Oliveira Francisco Rodriguez-Henriquez Luis Rivera-Zamarripa	flera datorer ^{[ vilken? ]} vid CINVESTAV och University of Waterloo	~200 kärnår
	3 ^{5 · 479}	december 2014	Antoine Joux Cecile Pierrot		<8600 CPU-timmar ^{[ kvantifiera ]}
	3 ^{6 · 163}	27 januari 2014	Gora Adj Alfred Menezes Thomaz Oliveira Francisco Rodríguez-Henríquez		1201 CPU-timmar
	3 ^{6 · 97}	2012	ett gemensamt team från Fujitsu, NICT och Kyushu University ^{[ vem? ]}
	3 ^{6 · 71}
"måttlig"	p ²	25 juni 2014	Razvan Barbulescu Pierrick Gaudry Aurore Guillevic François Morain		68 CPU-dagar + 30 GPU-timmar	Detta fält är en grad-2 förlängning av ett primtalsfält, där p är ett primtal med 80 siffror.
	33341353 ⁵⁷	6 januari 2013
	33553771 ⁴⁷
	370801 ³⁰	9 november 2005
	65537 ²⁵	24 oktober 2005

Elliptiska kurvor

Certicom Corp. har utfärdat en serie utmaningar för elliptisk kurvkryptering. Nivå I involverar fält av 109-bitars och 131-bitars storlekar. Nivå II innehåller 163, 191, 239, 359-bitars storlekar. Alla nivå II-utmaningar anses för närvarande vara beräkningsmässigt omöjliga.

Nivå I-utmaningarna som har uppfyllts är:

ECC2K-108, som innebär att man tar en diskret logaritm på en Koblitz-kurva över ett fält med 2 ¹⁰⁸ element. Priset delades ut den 4 april 2000 till en grupp på cirka 1300 personer representerade av Robert Harley. De använde en parallelliserad Pollard rho-metod med speedup.
ECC2-109, som innebär att man tar en diskret logaritm på en kurva över ett fält med 2 ¹⁰⁹ element. Priset delades ut den 8 april 2004 till en grupp på cirka 2600 personer representerade av Chris Monico. De använde också en version av en parallelliserad Pollard rho-metod , som tog 17 månaders kalendertid.
ECCp-109, involverar att ta en diskret logaritm på en kurva modulo en 109-bitars primtal. Priset delades ut den 15 april 2002 till en grupp på cirka 10 308 personer representerade av Chris Monico. Återigen använde de en version av en parallelliserad Pollard rho-metod , som tog 549 dagars kalendertid.

Ingen av 131-bitars (eller större) utmaningar har uppfyllts 2019.

I juli 2009 meddelade Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra och Peter L. Montgomery att de hade utfört en diskret logaritmberäkning på en elliptisk kurva (känd som secp112r1) modulo en 112-bitars främsta. Beräkningen gjordes på ett kluster av över 200 PlayStation 3- spelkonsoler under cirka 6 månader. De använde den vanliga parallelliserade versionen av Pollard rho - metoden .

löste Erich Wenger och Paul Wolfger från Graz University of Technology den diskreta logaritmen för en 113-bitars Koblitz-kurva på extrapolerade 24 dagar med hjälp av ett 18-kärnigt Virtex-6 FPGA - kluster. I januari 2015 löste samma forskare den diskreta logaritmen för en elliptisk kurva definierad över ett 113-bitars binärt fält. Den genomsnittliga körtiden är cirka 82 dagar med ett 10-kärnigt Kintex-7 FPGA- kluster.

Den 2 december 2016 tillkännagav Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar, Peter Schwabe och Ralf Zimmermann lösningen av ett generiskt 117,35-bitars elliptisk kurva diskret logaritmproblem på en binär kurva, med hjälp av en optimerad FPGA-implementering av en parallell version av Pollards rho-algoritm . Attacken pågick i ungefär sex månader på 64 till 576 FPGA parallellt.

Den 23 augusti 2017 meddelade Takuya Kusaka, Sho Joichi, Ken Ikuta, Md. Al-Amin Khandaker, Yasuyuki Nogami, Satoshi Uehara, Nariyoshi Yamai och Sylvain Duquesne att de hade löst ett diskret logaritmproblem på ett 114-bitars "par vänlig" Barreto–Naehrig (BN) kurva, som använder den speciella sextiska vridningsegenskapen för BN-kurvan för att effektivt utföra den slumpmässiga vandringen av Pollards rho-metod. Implementeringen använde 2000 CPU-kärnor och tog cirka 6 månader att lösa problemet.

Den 16 juni 2020 tillkännagav Aleksander Zieniewicz (zielar) och Jean Luc Pons ( JeanLucPons ) lösningen av ett diskret logaritmproblem med 114-bitars elliptisk kurva på secp256k1-kurvan genom att lösa en 114-bitars privat nyckel i Bitcoin Puzzle Transactions Challenge. För att sätta ett nytt rekord använde de sin egen mjukvara baserad på Pollard Kangaroo på 256x NVIDIA Tesla V100 GPU-processor och det tog dem 13 dagar. Två veckor tidigare - De använde samma antal grafikkort för att lösa ett 109-bitars ECDLP på bara 3 dagar.

Diskreta logaritmposter för elliptiska kurvor
Kurvans namn	Fältstorlek	Datum meddelat	Meddelat av	Algoritm	Beräkna tid
ECC2K-108	2 ¹⁰⁸	2000	cirka 1300 personer representerade av Robert Harley	Pollard rho-metoden
ECCp-109	en 109-bitars prime	2002	cirka 10308 personer representerade av Chris Monico	parallelliserad Pollard rho-metod	549 dagar
ECC2-109	2 ¹⁰⁹	2004	cirka 2600 personer representerade av Chris Monico	parallelliserad Pollard rho-metod	17 månader
secp112r1	en 112-bitars prime	juli 2009	Joppe W. Bos Marcelo E. Kaihara Thorsten Kleinjung Arjen K. Lenstra Peter L. Montgomery	den vanliga parallelliserade versionen av Pollard rho-metoden ^{[ vilken? ]}	6 månader
	2 ¹¹³	april 2014	Erich Wenger Paul Wolfger		47 dagar
	2 ¹¹³	januari 2015	Erich Wenger Paul Wolfger		82 dagar ^{[ verifiering krävs ]}
	2 ¹²⁷ Intervallsökning storlek 2 ^117,35	2 december 2016	Daniel J. Bernstein Susanne Engels Tanja Lange Ruben Niederhagen Christof Paar Peter Schwabe Ralf Zimmermann	parallell version av Pollards rho-algoritm	6 månader med 64 till 576 FPGA
		23 augusti 2017	Takuya Kusaka Sho Joichi Ken Ikuta Md. Al-Amin Khandaker Yasuyuki Nogami Satoshi Uehara Nariyoshi Yamai Sylvain Duquesne
secp256k1	2 ²⁵⁶ Intervallsökning storlek 2 ¹¹⁴	16 augusti 2020	Aleksander Zieniewicz Jean Luc Pons	parallell version av Pollards rho-algoritm	13 dagar på 256xTesla V100

Anteckningar

externa länkar

Beräkningar av diskreta logaritmer sorterade efter datum