Satunnainen alkuluku

Krypografiassa satunnainen alkuluku ymmärretään alkuluvuksi , joka sisältää tietyn määrän bittejä binäärimuodossa ja jonka generointialgoritmille on asetettu tiettyjä rajoituksia. Satunnaisalkulukujen luominen on olennainen osa avainten johtamismenettelyjä monissa salausalgoritmeissa, mukaan lukien RSA ja ElGamal .

Koska suurten lukujen yksinkertaisuuden testaus vaatii huomattavia aikakustannuksia, tuloksena olevan luvun yksinkertaisuuden vaatimus heikkenee usein vahvaksi näennäisyksinkertaisuudeksi useista eri satunnaisista syistä. Nykyiset vahvat pseudoyksinkertaisuustestausalgoritmit ovat suuruusluokkaa nopeampia kuin tunnetuimmat primaalisuuden testausalgoritmit. Samalla luvut, jotka läpäisevät onnistuneesti vahvan pseudoyksinkertaisuustestin useilla satunnaiskantoilla, ovat alkulukuja suurella todennäköisyydellä, ja tämä todennäköisyys kasvaa testien suorittamisen emästen lukumäärän myötä.

Vaatimukset algoritmille ja sen toteutukselle

Satunnaisalkulukujen generointialgoritmien vaatimukset tiivistyvät seuraaviin kahteen:

• Saatujen alkulukujen jakauman tulee olla lähes tasainen kaikkien k - bittisten alkulukujen joukossa. On useita tapoja varmistaa, että tämä vaatimus täyttyy.
• Tietyn satunnaisalkuluvun generointiprosessia ei voida toistaa, vaikka tietäisitkin algoritmin ja sen toteutuksen yksityiskohdat. Tyypillisesti tämä vaatimus täytetään käyttämällä suojattua PRNG :tä, joka on alustettu jollakin ulkopuolelta hankitulla avaimella (eli ei osa algoritmia tai sen toteutusta). Avain voi olla esimerkiksi salaushajautusfunktion arvo käyttäjältä pyydetystä salalauseesta.

Tyypillisiä algoritmeja satunnaisten alkulukujen luomiseen

Kaikkialla alla oletetaan käyttävän kryptografisesti vahvaa PRNG :tä, joka on alustettu salaisella avaimella (yksityiskohdat riippuvat käytetystä PRNG:stä ja siitä, kuinka avain hankitaan ja esitetään).

Yksinkertaisuustestaus

Voit tarkistaa k bittiä sisältävän luvun p (todennäköisen) primenessin seuraavasti:

1. Varmista, että p ei ole jaollinen pienillä alkuluvuilla 3, 5, 7, 11 jne. johonkin pieneen rajaan asti (esim. 256). Tällaisen tarkistuksen avulla voit leikata tehokkaasti pois paljon ilmeisen yhdistelmälukuja ennen niiden tarkistamista aikaa vievillä algoritmeilla. Jos siis tarkistetaan, että p on jaollinen alkuluvuilla 2, 3, 5 ja 7, se suodattaa pois kaikki parilliset luvut ja 54 % parittomista luvuista, ja sen tarkistaminen, että p on jaollinen kaikilla alkuluvuilla 100 asti, suodattaa pois 76 % parittomista luvuista. , ja tarkistamalla, että p on jaollinen kaikilla alkuluvuilla 256 asti, karsii pois 80 % parittomista luvuista.
2. Suorita Miller-Rabin-testi vähintään k kierroksella .

Jos luku p ei läpäise vähintään yhtä tarkistusta, se ei ole alkuluku. Muuten suurella todennäköisyydellä (riippuen kierrosten määrästä) luku p on alkuluku.

Suora rakentaminen

1. Luo satunnaisia ​​bittejä ja muodosta ne k -bittiseksi luvuksi p , jonka merkitsevin bitti on 1.
2. Kasvata p :tä yhdellä ja tarkista, onko se alkuluku. Toista tämä vaihe, kunnes alkuluku löytyy.

Toista vaihetta voidaan nopeuttaa, jos huomioidaan vain parittomat numerot tai lukuihin 1 ja 5 verrattavissa olevat luvut modulo 6 jne.

( n - 1)-menetelmät

( n -1)-alkulukukonstruktiomenetelmät käyttävät tietoa n -1:n alkujakajista testatakseen , onko n alkuluku käyttämällä Lucasin primaalisuustestiä . [yksi]

Tyypillinen tämän menetelmäluokan edustaja on kuvattu V. V. Yashchenkon toimittamassa kirjassa "Johdatus kryptografiaan". [2]

Alkulukujen sukupolvi Sophie Germain

Sophie Germainin  alkuluvut ovat alkulukuja p siten, että 2p + 1 on myös alkuluku.

Muistiinpanot

1. ↑ Cheryomushkin A.V. Luennot aritmeettisista algoritmeista kryptografiassa. - M. : MTSNMO , 2002. - 104 s. — ISBN 5-94057-060-7 .
2. ↑ Yu. V. Nesterenko. Luku 4.5. Kuinka rakentaa suuria alkulukuja // Johdatus kryptografiaan / Toim. V. V. Jaštšenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 . Arkistoitu kopio (linkki ei saatavilla) . Käyttöpäivä: 18. helmikuuta 2008. Arkistoitu alkuperäisestä 25. helmikuuta 2008. (määrätön)