Grote priemgetallen. Hoe bepaal je die?

[Onbekend]

Voor een RSA-encryptie heb ik een publieke en geheime sleutel moeten genereren. De basis hiervan bestaat uit twee verschillende priemgetallen waaruit deze sleutels worden bepaalt.
Hiervoor had ik in C# met de functie RSACryptoServiceProvider een programma geschreven waarmee binnen 1 seconde een publieke en geheime sleutel uit komt rollen.
Dit werkt goed, maar hoe komt deze functie zo snel aan twee verschillende priemgetallen die ook nog redelijk groot moeten zijn?

Als ik Wikipedia volg, dient het product van de twee priemgetallen minimaal 1024 bits te zijn. Dat betekent dat een priemgetal rond de 512 bits (=64 bytes) groot is.

Je kunt natuurlijk een willekeurig getal nemen en de Zeef van Eratosthenes gebruiken, maar voor een 512 bits getal is dat natuurlijk niet te doen.

Een Mersennepriemgetal bepalen leek mij beter aangezien je dan een getal echt gaat uitrekenen. Echter, volgens mij zijn dan maar een beperkt aantal combinaties mogelijk aangezien tussen twee opeenvolgende getallen een grote hoeveelheid ligt.

Een andere (onwaarschijnlijke) oplossing is dat vooraf al allerlei priemgetallen zijn gegenereerd, en deze (ingepakt) in deze classe verborgen zittten om te kunnen gebruiken. Maar gezien het aantal priemgetallen lijkt dit mij onwaarschijnlijk aangezien er aardig wat priemgetallen bestaan.

Volgens deze pagina zijn er ook andere testen om te controleren of een getal een priemgetal is, maar die geven als resultaat dat het getal "waarschijnlijk" priem is, maar is dus niet gegarandeerd priem.


Met veel zoeken ben ik wel wijzer geworden maar ik heb het antwoord (of de richting daar naar toe) op mijn vraag nog niet gevonden: Hoe kan de functie RSACryptoServiceProvider van Microsoft zo snel 2 priemgetallen kan vinden?

[F_J_K]

Pak een lijstje als http://www.bigprimes.net/downloads - best kans dat er wat tussen zit. Al is een dergelijk kort lijstje natuurlijk juist vast eenvoudig te kraken, juist omdat het er zo weinig zijn.

Een willekeurig 512b getal pakken en dan steeds 1 optellen tot je een priemgetal hebt lijkt me juist wel het beste.

quote: http://en.wikipedia.org/wiki/Prime_number_theorem

Informally speaking, the prime number theorem states that if a random integer is selected in the range of zero to some large integer N, the probability that the selected integer is prime is about 1 / ln(N), where ln(N) is the natural logarithm of N. For example, among the positive integers up to and including N = 103 about one in seven numbers is prime, whereas up to and including N = 1010 about one in 23 numbers is prime (where ln(103)= 6.90775528. and ln(1010)=23.0258509). In other words, the average gap between consecutive prime numbers among the first N integers is roughly ln(N).[1]

De verwachting is dat je dus maar ln(2^512) = 355 getallen hoeft te testen. (Nou ja, keer 2).

[Soultaker]

Onbekend schreef op zondag 22 juli 2012 @ 22:40:
Een Mersennepriemgetal bepalen leek mij beter aangezien je dan een getal echt gaat uitrekenen. Echter, volgens mij zijn dan maar een beperkt aantal combinaties mogelijk aangezien tussen twee opeenvolgende getallen een grote hoeveelheid ligt.

Precies, dat is dus een slecht idee, want je wil juist dat je uit zo veel mogelijk van de 2⁵¹² mogelijk getallen kan kiezen. Sowieso voldoen Mersennepriemgetallen absoluut niet aan de karakteristieken van stong primes, die het factoriseren van een RSA public key bemoeilijken.

Volgens deze pagina zijn er ook andere testen om te controleren of een getal een priemgetal is, maar die geven als resultaat dat het getal "waarschijnlijk" priem is, maar is dus niet gegarandeerd priem.

Het klinkt misschien stom, maar hoogwaardige libraries zoals OpenSSL gebruiken inderdaad deze probabilistische algoritmen om priemgetaltesten uit te voeren. Dat het resultaat slechts “waarschijnlijk” geldt is praktisch gezien geen onoverkomelijk probleem, als de kans op niet-priem-zijn voldoende klein is.

Met veel zoeken ben ik wel wijzer geworden maar ik heb het antwoord (of de richting daar naar toe) op mijn vraag nog niet gevonden: Hoe kan de functie RSACryptoServiceProvider van Microsoft zo snel 2 priemgetallen kan vinden?

Het klinkt misschien suf, maar gecombineerd met F_J_K zijn we er al: door simpelweg random getallen te nemen en er genoeg Miller-Rabin tests op los te laten totdat 'ie voldoende zeker is dat een getal daadwerkelijk priem is.

F_J_K schreef op zondag 22 juli 2012 @ 23:01:
De verwachting is dat je dus maar ln(2^512) = 355 getallen hoeft te testen. (Nou ja, keer 2).

En weer gedeeld door twee omdat je alle even getallen makkelijk over kunt slaan. Idem dito voor getallen die deelbaar zijn door andere kleine priemfactoren. Verder kun je niet-priem getallen gemiddeld na een klein aantal tests al verwerpen.

[ Voor 5% gewijzigd door Soultaker op 22-07-2012 23:17 ]

[Onbekend]

Soultaker schreef op zondag 22 juli 2012 @ 23:16:
Het klinkt misschien stom, maar hoogwaardige libraries zoals OpenSSL gebruiken inderdaad deze probabilistische algoritmen om priemgetaltesten uit te voeren. Dat het resultaat slechts “waarschijnlijk” geldt is praktisch gezien geen onoverkomelijk probleem, als de kans op niet-priem-zijn voldoende klein is.

Levert dat geen potentieel gevaar op? Stel dat mijn certificaat om een https-verbinding op te zetten of een sleutel om een document mee te ondertekenen niet uit priemgetallen is voortgekomen, zou een aanvaller relatief snel achter mijn sleutel kunnen komen.

Het klinkt misschien suf, maar gecombineerd met F_J_K zijn we er al: door simpelweg random getallen te nemen en er genoeg Miller-Rabin tests op los te laten totdat 'ie voldoende zeker is dat een getal daadwerkelijk priem is.

Hoeveel procent kans is er dan nodig om voldoende zeker te zijn dat een getal een priemgetal is?
De kans op niet priem is volgens Miller-Rabin 1/(4^k), waarbij k het aantal ronden is.
Stel dat ik die kans op 0,001% wil hebben, dan is dat dus 1/100.000 -> k = 9. Is dat klein genoeg?

[Nick The Heazk]

Volgens een post op StackOverflow zou men een k gebruiken die voldoende groot is zodat 4^{-k} kleiner is dan de kans dat je computer een willekeurige fout maakt. For all intended purposes is dat voldoende.

[ Voor 8% gewijzigd door Nick The Heazk op 23-07-2012 20:01 ]

[Soultaker]

Onbekend schreef op maandag 23 juli 2012 @ 18:07:
Levert dat geen potentieel gevaar op? Stel dat mijn certificaat om een https-verbinding op te zetten of een sleutel om een document mee te ondertekenen niet uit priemgetallen is voortgekomen, zou een aanvaller relatief snel achter mijn sleutel kunnen komen.

Dat klopt, maar praktisch gezien is een kans van (zeg) 2^-100 natuurlijk verwaarloosbaar, vooral ook aangezien het veel waarschijnlijker is dat je processor een rekenfout maakt of dat je random number generator niet genoeg entropie bevat.

Verder is heel RSA gebaseerd op de onbewezen aanname dat priemfactoriseren moeilijk is; daar kun je je dan beter zorgen over maken. Sowieso kan iemand je priemfactor natuurlijk ook gewoon goed gokken; de kans dat dat lukt is ook ongeveer 1/p (wat astronomisch klein is, maar niet nul).

De kans op niet priem is volgens Miller-Rabin 1/(4^k), waarbij k het aantal ronden is.
Stel dat ik die kans op 0,001% wil hebben, dan is dat dus 1/100.000 -> k = 9. Is dat klein genoeg?

De formule die je noemt is een bovengrens; gemiddeld (dus voor random gegenereerde getallen) zijn veel minder tests nodig. Het blijkt dat OpenSSL op 2^-80 kans mikt en slechts enkele iteraties uitvoert. Uit de broncode:

C:

/* number of Miller-Rabin iterations for an error rate  of less than 2^-80
 * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook
 * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996];
 * original paper: Damgaard, Landrock, Pomerance: Average case error estimates
 * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */
#define BN_prime_checks_for_size(b) ((b) >= 1300 ?  2 : \
                                (b) >=  850 ?  3 : \
                                (b) >=  650 ?  4 : \
                                (b) >=  550 ?  5 : \
                                (b) >=  450 ?  6 : \
                                (b) >=  400 ?  7 : \
                                (b) >=  350 ?  8 : \
                                (b) >=  300 ?  9 : \
                                (b) >=  250 ? 12 : \
                                (b) >=  200 ? 15 : \
                                (b) >=  150 ? 18 : \
                                /* b >= 100 */ 27)

Blijkbaar zijn voor grote getallen aanzienlijk minder tests nodig dan voor kleine getallen. Waarom dat is weet ik niet — dit niveau wiskunde gaat mij ook boven de pet, eerlijk gezegd.

Overigens is het belangrijk om in het achterhoofd te houden dat primality testing en prime factorization heel verschillende problemen zijn. Zelfs als Miller-Rabin aangeeft dat een getal niet-priem is, dan heb je het daarmee nog lang niet gefactoriseerd. En aan je public key kan een attacker ook niet direct zien of die per ongeluk meer dan twee priemfactoren heeft.

[Onbekend]

Bedankt voor de antwoorden, want nu is voor mij van alles duidelijker geworden.
Ik was zelf nog niet op het idee gekomen om de source van OpenSSL te bekijken, maar dat zal vast en zeker leerzaam zijn.

En inderdaad, iemand anders weet van tevoren ook niet of de sleutel wel of niet priem is, maar schijnbaar zijn de controletechnieken die nu worden gebruikt van een acceptabel niveau.