Diskreetti logaritmi
Diskreetti logaritmi on matemaattinen objekti käytetään kryptologiasta . Se on todellisen logaritmin analogi, joka on eksponentin vastavuoroinen , mutta rajallisessa syklisessä ryhmässä G.
Diskreettiä logaritmia käytetään julkisen avaimen salaukseen , tyypillisesti Diffie-Hellman-avaimenvaihdossa ja El Gamalin salauksessa . Syynä on se, että tietyn ryhmän ryhmille emme tiedä tehokasta algoritmia diskreetin logaritmin laskemiseksi, kun taas vastavuoroisen, eksponention, algoritmi suoritetaan useissa logaritmisissa kerrannaisissa argumentti (katso nopea eksponentti ),
Määritelmä
Tarkastellaan syklinen ryhmä G on äärellinen, jotta n (laki on kirjoitettu moninkertaistavana) ja generaattorin b ja G . Sitten jokainen elementti x on G , voidaan kirjoittaa muotoon x = b k joidenkin kokonaislukuja k ; lisäksi mikä tahansa näistä kahdesta kokonaisluvusta on välttämättä yhtenevä modulo n . Diskreetti logaritmi voidaan määritellä pienimpänä luonnollisena kokonaislukuna k, joka täyttää tämän ominaisuuden (on vain yksi sellainen, että 0 ≤ k <n). Siksi se on eksponention k ↦ b k vastavuoroinen kartoitus .
Esimerkki
Tarkastellaan rajallista syklistä ryhmää (ℤ 7 * , ×) ja generaattoria 3.
| 3 0 | 3 1 | 3 2 | 3 3 | 3 4 | 3 5 |
|---|---|---|---|---|---|
| 1 | 3 | 2 | 6 | 4 | 5 |
Meillä on peräkkäin 3 2 ≡ 2 mod 7, 3 3 ≡ 2 × 3 ≡ 6 mod 7, 3 4 ≡ 6 × 3 ≡ 4 mod 7. Vuonna ℤ 7 * meillä on siis log 3 4 = 4. Yleensä, tämä ryhmä ja samalla generaattorilla, diskreetti logaritmi x on pienin kokonaisluku k siten, että 3 k ≡ x (mod 7).
| x | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| log 3 x | 0 | 2 | 1 | 4 | 5 | 3 |
Diskreetti logaritmi ryhmien isomorfismina
Diskreetti logaritmi voidaan määritellä myös funktiona log- b ja G on ℤ n (jossa ℤ n tarkoittaa kokonaislukujen rengas modulo n ) liittämällä minkä tahansa elementin x ja G luokan yhdenmukaisuutta k modulo n . Tämä funktio on ryhmien isomorfismi , jota kutsutaan erilliseksi logaritmiksi, jonka perusta b .
Esimerkiksi emäksen 3 erillinen logaritmi on äärellisen syklisen ryhmän (ℤ 7 * , ×) kartta (ℤ 6 , +).
Ominaisuudet
Perusmuutoskaava tavallisille logaritmeille pysyy voimassa: jos c on G: n toinen generaattori , niin
Joillekin ryhmille erillisten logaritmien laskeminen on vaikeaa, kun taas käänteinen ongelma, diskreetti eksponentio, ei ole ( nopean eksponentointialgoritmin ansiosta ); Tämä epäsymmetria hyödynnetään kryptologian , sillä julkisen avaimen salausta . Käytimme ensin syklisiä ryhmiä ℤ p * (jotka koostuvat luvuista {1, ..., p - 1}, jotka on annettu kertomodulolla alkuluku p ) p: lle riittävän suurille (vähintään 300 bittiä) ja p - 1: lle vähintään yhdellä "suurella" alkutekijällä. Olemme myös käyttäneet, jonkin aikaa , Syklinen alaryhmiä ryhmä liittyy elliptisellä käyrällä on äärellisen kentän (Katso kryptologian ellipsinmuotoinen käyrät ).
Algoritmit
Diskreettiä logaritmia varten on useita algoritmeja, jotka voivat olla tehokkaampia kuin tyhjentävä haku, mutta yksikään niistä ei ole tiedossa polynomiajassa tulojen koossa.
Esimerkiksi Silver-Pohlig-Hellman -algoritmia voidaan käyttää diskreetin logaritmin laskemiseen syklisessä ryhmässä, jos p - 1 on pienten alkioiden tulo, minkä vuoksi on välttämätöntä välttää sitä tällaisissa sovelluksissa. Indeksi laskenta-algoritmi (fi) toimii ryhmissä ℤ s *.
Tässä on muutama lisää:
- Vauva-askel jättiläinen-askel
- Pollardin Rho-algoritmi
- Pohlig-Hellman-algoritmi
- Special Number Field -näyttö (SNFS)
- Algebrallinen seula , jota kutsutaan myös yleisnumerokenttäseulaksi (GNFS)
9. toukokuuta 2014, CNRS julkaisi lehdistötiedotteen, jossa ilmoitettiin erillisen logaritmiongelman osan ratkaisemisesta. Vastaavan tutkimusartikkelin johtopäätös on, että salausteknisten sovellusten perustaminen tämän ongelman vaikeudelle on mahdotonta perustaa erityistapauksessa, jossa nämä edistykset ovat tapahtuneet (kun olemme rajallisessa pienten ominaisuuksien kentässä ). Tämä tulos ei kuitenkaan vaikuta valtaosaan salaustekniikoista ( esimerkiksi RSA-salausta käytetään ℤ / nℤ-renkaassa, jonka ominaisuus on n , vuonna 2016 suositeltu pituus on 2048 bittiä).
Huomautuksia ja viitteitä
(fr) Tämä artikkeli on osittain tai kokonaan peräisin englanninkielisestä Wikipedia- artikkelista " Diskreetti logaritmi " ( katso kirjoittajaluettelo ) .- Stinson2006 , s. 234.
- Uusi algoritmi ravistaa salausta .
- Heuristinen kvasi-polynomialgoritmi erilliselle logaritmille pienten ominaisuuksien äärellisissä kentissä .
- Tämän tuloksen pääasiallinen seuraus oli kieltää ylikuormitettujen elliptisten käyrien (en) käyttö kytkennöissä .
- Katso NIST : n suositukset : (in) " Key Key "
Liitteet
Bibliografia
- (en) Douglas Robert Stinson , Salaus: teoria ja käytäntö , Lontoo, CRC Press ,2006, 3 ja toim. , 616 Sivumäärä ( ISBN 978-1-58488-508-5 , lue verkossa )
- Gilles Zémor , Cryptography tietenkin , Pariisi, Cassini,15. joulukuuta 2000, 227 Sivumäärä ( ISBN 2-84225-020-6 , OCLC 45915497 )
Aiheeseen liittyvät artikkelit
Ulkoiset linkit
- " " Diskreetti logaritmiongelma "salauksessa " , Images des Mathsissa ,14. maaliskuuta 2015.