Tilfældigt primtal

I kryptografi forstås et tilfældigt primtal som et primtal, der indeholder et givet antal bits i binær notation , på hvilken genereringsalgoritmen er pålagt visse begrænsninger. Generering af tilfældige primtal er en integreret del af nøgleafledningsprocedurer i mange kryptografiske algoritmer, herunder RSA og ElGamal .

På grund af det faktum, at test af enkeltheden af ​​store tal kræver betydelige tidsomkostninger, er kravet til enkeltheden af ​​det resulterende tal ofte svækket til stærk pseudo -simplicitet af flere forskellige tilfældige årsager. Eksisterende stærke pseudo-enkelhedstestalgoritmer er størrelsesordener hurtigere end de bedst kendte primalitetstestalgoritmer. Samtidig er tal, der med succes består den stærke pseudosimplicitet test på flere tilfældige baser, prime med høj sandsynlighed, og denne sandsynlighed vokser med antallet af baser, som testen udføres på.

Krav til algoritmen og dens implementering

Kravene til algoritmer til generering af tilfældige primtal koger ned til følgende to:

• Fordelingen af ​​de resulterende primtal bør være tæt på ensartet på sættet af alle k -bit primtal. Der er flere måder at sikre, at dette krav er opfyldt.
• Processen med at generere et bestemt tilfældigt primtal kan ikke reproduceres, selv om man kender detaljerne i algoritmen og dens implementering. Typisk opfyldes dette krav ved at bruge en sikker PRNG initialiseret med en eller anden nøgle opnået udefra (det vil sige ikke en del af algoritmen eller dens implementering). Nøglen kan for eksempel være værdien af ​​den kryptografiske hash-funktion fra den hemmelige sætning, der er anmodet om fra brugeren.

Typiske algoritmer til generering af tilfældige primtal

Overalt nedenfor antages det at bruge en kryptografisk stærk PRNG initialiseret med en hemmelig nøgle (detaljer afhænger af den anvendte PRNG og hvordan nøglen opnås og præsenteres).

Simplicity Testing

Du kan kontrollere den (sandsynlige) primehed af et tal p , der indeholder k bits som dette:

1. Sørg for, at p ikke er deleligt med små primtal 3, 5, 7, 11 osv. op til en lille grænse (f.eks. 256). En sådan kontrol giver dig mulighed for effektivt at afskære en masse åbenlyst sammensatte tal, før du tjekker dem med mere tidskrævende algoritmer. Så hvis du kontrollerer, at p er deleligt med primtallene 2, 3, 5 og 7, bortfiltreres alle lige tal og 54 % af ulige tal, og kontrol af, at p er deleligt med alle primtal op til 100, bortfiltrerer 76 % af ulige tal. , og kontrol af at p er deleligt med alle primtal op til 256 luger 80% af ulige tal ud.
2. Kør Miller-Rabin-testen med mindst k runder .

Hvis tallet p ikke består mindst én kontrol, er det ikke primtal. Ellers, med høj sandsynlighed (afhængigt af antallet af runder) er tallet p primtal.

Direkte konstruktion

1. Generer tilfældige bits og komponer dem til et k -bit nummer p med den mest signifikante bit lig med 1.
2. Forøg p med 1 og tjek, om det er prime. Gentag dette trin, indtil et primtal er fundet.

Det andet trin kan accelereres, hvis vi kun betragter ulige tal eller tal, der kan sammenlignes med 1 og 5 modulo 6 osv.

( n - 1)-metoder

( n -1)-primtal konstruktionsmetoderne bruger viden om primtalsdivisorerne for n -1 til at teste, om n er primtal ved hjælp af Lucas primalitetstesten . [en]

En typisk repræsentant for denne klasse af metoder er beskrevet i bogen "Introduktion til kryptografi" redigeret af V. V. Yashchenko. [2]

Primtalsgeneration Sophie Germain

Sophie Germain  primtal er primtal p, således at 2p + 1 også er primtal.

Noter

1. ↑ Cheryomushkin A.V. Forelæsninger om aritmetiske algoritmer i kryptografi. - M .: MTSNMO , 2002. - 104 s. — ISBN 5-94057-060-7 .
2. ↑ Yu. V. Nesterenko. Kapitel 4.5. Sådan bygger du store primtal // Introduktion til kryptografi / Red. V. V. Yashchenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 . Arkiveret kopi (ikke tilgængeligt link) . Dato for adgang: 18. februar 2008. Arkiveret fra originalen 25. februar 2008. (ubestemt)