Véletlenszerű prímszám

A kriptográfiában véletlen prímszám alatt olyan prímszámot értünk, amely adott számú bitet tartalmaz bináris jelöléssel , és amelynek generálási algoritmusára bizonyos korlátozások vonatkoznak. A véletlenszerű prímszámok generálása számos kriptográfiai algoritmusban, köztük az RSA -ban és az ElGamal -ban a kulcslevezetési eljárások szerves részét képezi .

Tekintettel arra, hogy a nagy számok egyszerűségének tesztelése jelentős időköltséget igényel, a kapott szám egyszerűségének követelménye több véletlenszerű ok miatt gyakran erős pszeudo -egyszerűségre gyengül. A létező erős pszeudoegyszerűség-tesztelő algoritmusok nagyságrendekkel gyorsabbak, mint a legismertebb primalitástesztelő algoritmusok. Ugyanakkor azok a számok, amelyek több véletlenszerű bázison sikeresen teljesítik az erős pszeudoegyszerűségi tesztet, nagy valószínűséggel prímszámmal bírnak, és ez a valószínűség növekszik a teszt végrehajtásának alapjainak számával.

Az algoritmussal és megvalósításával szemben támasztott követelmények

A véletlen prímszámok generálására szolgáló algoritmusok követelményei a következő kettőre csapódnak le:

• Az eredményül kapott prímek eloszlásának közel egyenletesnek kell lennie az összes k bites prím halmazán. Ennek a követelménynek a teljesülése többféleképpen is biztosítható.
• Egy adott véletlen prímszám generálásának folyamata még az algoritmus részleteinek és megvalósításának ismeretében sem reprodukálható. Ennek a követelménynek általában egy olyan biztonságos PRNG használatával lehet eleget tenni, amely valamilyen kívülről kapott kulccsal inicializálódik (vagyis nem része az algoritmusnak vagy annak megvalósításának). A kulcs lehet például a kriptográfiai hash függvény értéke a felhasználótól kért titkos kifejezésből.

Tipikus algoritmusok véletlen prímszámok generálására

Az alábbiakban mindenhol feltételezzük, hogy titkos kulccsal inicializált kriptográfiailag erős PRNG -t használnak (a részletek a használt PRNG-től és a kulcs beszerzésének és bemutatásának módjától függenek).

Egyszerűség tesztelése

A k bitet tartalmazó p szám (valószínű) prímságát így ellenőrizheti :

1. Győződjön meg arról , hogy p nem osztható kis prímszámokkal 3, 5, 7, 11 stb. valami kis határig (pl. 256). Egy ilyen ellenőrzés lehetővé teszi, hogy hatékonyan levágjon sok nyilvánvalóan összetett számot, mielőtt időigényesebb algoritmusokkal ellenőrizné őket. Tehát annak ellenőrzése, hogy p osztható -e a 2, 3, 5 és 7 prímszámokkal, kiszűri az összes páros számot és a páratlan számok 54%-át, és annak ellenőrzése, hogy p osztható -e minden prímszámmal 100-ig, a páratlan számok 76%-át kiszűri. , és annak ellenőrzése, hogy p osztható -e minden prímszámmal 256-ig, kigyomlálja a páratlan számok 80%-át.
2. Futtassa le a Miller-Rabin tesztet legalább k körrel .

Ha a p szám legalább egy ellenőrzést megbukik, akkor nem prímszám. Egyébként nagy valószínűséggel (a körök számától függően) a p szám prím.

Közvetlen konstrukció

1. Véletlenszerű biteket állítson elő, és állítsa be őket egy k bites p számba , amelynek legjelentősebb bitje 1.
2. Növelje p -t 1-gyel, és ellenőrizze, hogy prím-e. Addig ismételje ezt a lépést, amíg meg nem talál egy prímszámot.

A második lépést felgyorsíthatjuk, ha csak páratlan vagy 1-hez és 5-höz hasonló számokat vesszük figyelembe modulo 6 stb.

( n - 1)-módszerek

Az ( n -1)-prím konstrukciós módszerek az n -1 prímosztóinak ismeretét használják annak ellenőrzésére , hogy n prím-e a Lucas- primalitásteszt segítségével . [egy]

A módszerek ezen osztályának tipikus képviselőjét a V. V. Yashchenko által szerkesztett "Bevezetés a kriptográfiába" című könyv írja le. [2]

Prímszám-generáció Sophie Germain

A Sophie Germain  prímek p prímek, így a 2p + 1 is prím.

Jegyzetek

1. ↑ Cheryomushkin A.V. Előadások a kriptográfiai aritmetikai algoritmusokról. - M. : MTSNMO , 2002. - 104 p. — ISBN 5-94057-060-7 .
2. ↑ Yu. V. Neszterenko. fejezet 4.5. Hogyan készítsünk nagy prímszámokat // Bevezetés a kriptográfiába / Szerk. V. V. Jascsenko. - Péter, 2001. - 288 p. - ISBN 5-318-00443-1 . Archivált másolat (nem elérhető link) . Hozzáférés időpontja: 2008. február 18. Az eredetiből archiválva : 2008. február 25. (határozatlan)