Diskret logaritme
Den diskrete logaritme er et matematisk objekt, der bruges i kryptologi . Det er den analoge af den virkelige logaritme, der er den gensidige af den eksponentielle , men i en endelig cyklisk gruppe G.
Den diskrete logaritme bruges til offentlig nøglekryptografi , typisk i Diffie-Hellman-nøgleudveksling og El Gamal-kryptering . Årsagen er, at vi for et bestemt antal grupper ikke kender en effektiv algoritme til beregning af den diskrete logaritme, mens den for den gensidige eksponentiering udføres i et antal logaritmiske multiplikationer i størrelsen af argument (se hurtig eksponentiering ),
Definition
Overvej en cyklisk gruppe G af endelig orden n (loven er skrevet multiplikativt) og en generator b af G . Derefter kan hvert element x af G skrives i formen x = b k for nogle heltal k ; desuden er et hvilket som helst to af disse heltal nødvendigvis kongruente modulo n . Den diskrete logaritme kan defineres som det mindste naturlige heltal k, der tilfredsstiller denne egenskab (der er kun en sådan, at 0 ≤ k <n). Det er derfor en gensidig kortlægning af eksponentieringen k ↦ b k .
Eksempel
Overvej den endelige cykliske gruppe (ℤ 7 * , ×) og generatoren 3.
| 3 0 | 3 1 | 3 2 | 3 3 | 3 4 | 3 5 |
|---|---|---|---|---|---|
| 1 | 3 | 2 | 6 | 4 | 5 |
Vi har successivt 3 2 ≡ 2 mod 7, 3 3 ≡ 2 × 3 ≡ 6 mod 7, 3 4 ≡ 6 × 3 ≡ 4 mod 7. I ℤ 7 * har vi derfor log 3 4 = 4. Generelt i denne gruppe og for den samme generator er den diskrete logaritme af x det mindste heltal k, således at 3 k ≡ x (mod 7).
| x | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| log 3 x | 0 | 2 | 1 | 4 | 5 | 3 |
Diskret logaritme som isomorfisme af grupper
Den diskrete logaritme kan også defineres som funktionslog b fra G til ℤ n (hvor den n betegner ringen af heltal modulo n ) ved at tilknytte ethvert element x af G kongruensklassen af k modulo n . Denne funktion er en isomorfisme af grupper , kaldet en diskret logaritme med base b .
For eksempel er den diskrete logaritme i base 3 et kort over den endelige cykliske gruppe (ℤ 7 * , ×) i (ℤ 6 , +).
Ejendomme
Basisændringsformlen for almindelige logaritmer forbliver gyldig: hvis c er en anden generator af G , så
For nogle grupper er det svært at beregne diskrete logaritmer, mens det omvendte problem, diskret eksponentiering, ikke er (takket være den hurtige eksponentieringsalgoritme ); denne asymmetri udnyttes i kryptologi til offentlig nøglekryptografi . Anvendte vi først cykliske grupper ℤ p * (bestående af tallene {1, ..., p - 1} forsynet med multiplikation modulo primtal p ) for p tilstrækkeligt stort (mindst 300 bits) og p - 1 med mindst en "stor" primærfaktor. Vi har også brugt i nogen tid De cykliske undergrupper i gruppen, der er forbundet med en elliptisk kurve på et endeligt felt (Se kryptologi om elliptiske kurver ).
Algoritmer
Der er flere algoritmer til den diskrete logaritme, der kan være mere effektive end den udtømmende søgning, men ingen er kendt i polynomisk tid i størrelsen af input.
For eksempel kan Silver-Pohlig-Hellman-algoritmen bruges til at beregne den diskrete logaritme i en cyklisk gruppe, hvis p - 1 er et produkt med små primtal, hvilket gør det nødvendigt at undgå det i sådanne applikationer. Det indeks beregning algoritme (en) arbejder i grupper ℤ p *.
Her er et par flere:
- Baby-trin kæmpe-trin
- Pollards rho-algoritme
- Pohlig-Hellman-algoritme
- Specielt nummerfeltskærm (SNFS)
- Algebraisk sigte , også kaldet General Number Field Sieve (GNFS)
Det 9. maj 2014, offentliggjorde CNRS en pressemeddelelse, der annoncerede løsningen af en del af det diskrete logaritmeproblem. Konklusionen af den tilsvarende forskningsartikel er, at det bliver utænkeligt at basere kryptografiske applikationer på vanskeligheden ved dette problem i det særlige tilfælde, som disse fremskridt har fundet sted (når vi er i et begrænset felt med lille karakteristik ). Imidlertid påvirkes langt størstedelen af krypteringsteknikker ikke af dette resultat ( RSA-kryptering bruges for eksempel på ℤ / nℤ-ringen med karakteristisk n , den anbefalede længde i 2016 er 2048 bit).
Noter og referencer
(fr) Denne artikel er helt eller delvist taget fra den engelske Wikipedia- artikel med titlen " Diskret logaritme " ( se forfatterlisten ) .- Stinson2006 , s. 234.
- Ny algoritme ryster kryptografi .
- En heuristisk kvasi-polynomalgoritme til diskret logaritme i endelige felter med lille karakteristik .
- Den væsentligste konsekvens af dette resultat var at forbyde brugen af overpersingular elliptiske kurver (da) for koblinger .
- Se anbefalingerne fra NIST : (i) " Nøglestørrelse "
Tillæg
Bibliografi
- (en) Douglas Robert Stinson , Cryptography: Theory and Practice , London, CRC Press ,2006, 3 e ed. , 616 s. ( ISBN 978-1-58488-508-5 , læs online )
- Gilles Zémor , Kryptografikursus , Paris, Cassini,15. december 2000, 227 s. ( ISBN 2-84225-020-6 , OCLC 45915497 )
Relaterede artikler
eksterne links
- " Det" diskrete logaritmeproblem "i kryptografi " , på Images des Maths ,14. marts 2015.