Deel dit artikel

de jacht op nieuwe, steeds grotere priemgetallen is ongetwijfeld het meest mediagenieke onderzoeksterrein uit de wiskunde. dat het daarbij om meer gaat dan het behalen van wetenschappelijke records is minder geweten. grote priemgetallen vervullen een voor de leek onzichtbare, maar essentiële rol in de veiligheid van elektronische communicatie. een rekenoefening in de cryptografie van uw digitale identiteit.

Signeren met priemgetallen

Willem Veys

Af en toe vernemen we in de media dat eindelijk het grootste priemgetal ontdekt is. Dat is dan een ongelukkige formulering van de journalist of nieuwslezer. Er bestaan namelijk oneindig veel priemgetallen, en daarom is er geen grootste. Een kort en mooi argument om dit in te zien was al gevonden door Euclides rond 300 voor Christus. U kan alvast zelf even proberen, of de redenering van Euclides lezen aan het eind van dit artikel. Misschien toch even opfrissen wat we allen in de lagere school geleerd hebben: een priemgetal is een natuurlijk getal dat groter is dan 1 en slechts deelbaar door 1 en zichzelf. De priemgetallen kleiner dan 20 zijn dus 2, 3, 5, 7, 11, 13, 17 en 19. Grotere exemplaren zijn bijvoorbeeld 101, 2003, 100 003 = 105 + 3 en 2216091 − 1. De kwakkel in het nieuwsbericht heeft te maken met de moeilijkheid om te verifiëren of een getal al dan niet een priemgetal is. Vermoedelijk hebt u met 101 niet veel moeite maar 2216091 − 1 is een lastiger geval (dit is een getal van 65 050 cijfers). Tegenwoordig kan men dit efficiënt nagaan voor heel grote getallen van bijvoorbeeld honderdvijftig cijfers: op een serieuze PC kan dit al in een milliseconde. Maar voor gigantisch grote getallen van bijvoorbeeld tienduizend cijfers blijft het enorm moeilijk, en kent men enkel methodes voor getallen van een heel speciale vorm. Sinds mei 2004 is 224036583 − 1 de recordhouder. Wat dus soms in het nieuws komt, is dat er een nieuw grootste gekendpriemgetal is.Grote priemgetallen van ongeveer honderdvijftig cijfers zijn al een tijd heel nuttig in cryptografie bij het coderen en decoderen van berichten en bij het zetten en verifiëren van digitale handtekeningen. Onze nieuwe elektronische identiteitskaart bijvoorbeeld zal een dergelijke digitale handtekening kunnen aanmaken. Het basisidee hiervoor dateert al van 1978 toen Ronald Rivest, Adi Shamir en Leonard Adleman met behulp van grote priemgetallen een bruikbaar concept ontwikkelden voor zogenaamde asymmetrische of publieke sleutelcryptografie in plaats van de traditionele symmetrische cryptografie (traditioneel gebruiken zender en ontvanger één gemeenschappelijke geheime sleutel; bij asymmetrische cryptografie spelen er twee sleutels mee, een geheime en een publiek gekende). Dit concept, nu bekend als RSA, blijft ontzettend belangrijk en actueel en is nog steeds de internationale standaard. Regelmatig verschijnen er boeken met nieuwe ontwikkelingen en toepassingen. Zo wordt in RSA and public-key cryptography van Richard Mollin, naast de volledige beschrijving van RSA, uitgelegd hoe men elektronisch betalen via het internet en draadloos communiceren beveiligt met RSA. Maar waar komen die grote priemgetallen daar nu bij kijken? De basis van RSA is een publiek gekend getal van driehonderd cijfers dat het product is van twee geheime priemgetallen van elk honderdvijftig cijfers. Om het concept verder uit te leggen, moeten we eerst even stilstaan bij drie belangrijke elementen: de onmogelijkheid om in het algemeen een gegeven groot getal concreet te ontbinden als een product van priemgetallen, de mogelijkheid om wel snel en efficiënt grote priemgetallen te vinden, en de techniek van het modulo-rekenen.

Een getal van twintig cijfers vereist al tien miljard deelbaarheidstesten

Eerst dus het ontbinden van een getal. In de lagere school leerden we dat elk (natuurlijk) getal op juist één manier het product is van priemgetallen. Zo is bijvoorbeeld 575 = 5 · 5 · 23 en 2004 = 2 · 2 · 3 · 167. De klassieke manier om deze ontbinding in priemfactoren te vinden is de ‘zeef van Erathostenes’ (rond 240 voor Christus): men test achtereenvolgens of 2, 3, 5, 7 … een deler is van het gegeven getal. Voor 1045 vinden we zo als eerste priemfactor 5; dan testen we verder of 1045 : 5 = 209 deelbaar is door 5, 7, 11, 13 …. Nu komt 11 als eerste uit de bus en 209 : 11 = 19 is zelf een priemgetal. Dus 1045 = 5 · 11 · 19 is de gezochte ontbinding. Het probleem is echter dat bij grote getallen van bijvoorbeeld driehonderd cijfers deze methode in de praktijk niet werkt omdat men te veel testen moet uitvoeren: voor een getal n zijn er, ruw afgeschat, ongeveer deelbaarheidstesten nodig. Nu kan één zo’n test wel enorm snel, zeg in een honderdduizendste van een seconde. In totaal zijn er dus voor een getal van tien cijfers ongeveer 105 = 100 000 testen nodig, die al afgelopen zijn na één seconde. Maar verder loopt het uit de hand. Een getal van twintig cijfers vereist al tien miljard testen. Dit duurt meer dan een dag. En voor een getal van honderd cijfers moeten we veel langer wachten dan de leeftijd van het heelal. Gelukkig bestaan er ingenieuze manieren om sneller delers te vinden. Zo kan men met behulp van gevorderde algebra een getal van honderd cijfers wel ontbinden in priemfactoren met behulp van zeer krachtige computers in een paar maanden. Maar voor een willekeurig getal van ongeveer driehonderd cijfers gaat men ervan uit dat een concrete ontbinding in priemfactoren nog lang onmogelijk zal blijven. Voor wie van een uitdaging en een grote beloning houdt:

1350664108659952233496032162788059699388814756056670275244851438515265106048595338339402871505719094417982072821644715513736804197039
6419174304649658927425623934102086438320211037295872576235850964311056407350150818751067659462920556368552947521350085287941637732853
3906109750544334999811150056977236890927563

Dit is het product van twee priemgetallen, die zorgvuldig geheim gehouden worden door de RSA-firma. Wie deze priemgetallen kan vinden, strijkt honderdduizend dollar op.

Een tweede feit, misschien op het eerste zicht wat eigenaardig in vergelijking met het vorige ontbindingsprobleem, is dat men wel gemakkelijk en snel voor een groot getal van bijvoorbeeld honderdvijftig cijfers kan testen of het al dan niet een priemgetal is, en dat er voldoende priemgetallen zijn om via trial and error zeer snel een priemgetal van honderdvijftig cijfers te vinden. Er zijn verscheidene dergelijke priemtesten op de markt, allemaal gebaseerd op de speciale eigenschappen van priemgetallen. Een voorbeeld van zo’n eigenschap is dat elk priemgetal p een deler is van 2p − 2; als p geen priemgetal is, geldt deze eigenschap meestal niet. Tot nog toe waren de meeste priemtesten probabilistisch: het resultaat van zo’n test is dat ofwel het getal zeker geen priemgetal is, ofwel het getal hoogst waarschijnlijk een priemgetal is (met een verwaarloosbare kans op een fout, bijvoorbeeld één op een miljard). Een vanuit wiskundig standpunt recente cruciale doorbraak hier is de nieuwe priemtest van Manindra Agrawal, Neeraj Kayal en Nitin Saxena. Dit is de eerste priemtest die tegelijk altijd een exact antwoord geeft én ‘wiskundig aantoonbaar snel’ is. Een mooi aspect van dit resultaat is dat het zowaar het bachelorproject was van de studenten Kayal en Saxena onder leiding van Agrawal, en dat tevoren vele specialisten vruchteloos naar zo’n test gezocht hebben. Wél is het zo dat in de praktijk de vroegere testen nog sneller zijn. Concreet duurt het gemiddeld een milliseconde om te testen of een getal van honderdvijftig cijfers een priemgetal is. Door te blijven proberen, vindt men zo zeer snel een priemgetal van honderdvijftig cijfers omdat er ‘voldoende’ priemgetallen zijn. Dit volgt namelijk uit de beroemde priemgetallenstelling uit 1896, bewezen door Jacques Hadamard en (de Leuvense) Charles de la Vallée Poussin. Ruwweg zegt die dat het aantal priemgetallen dat kleiner is dan een gegeven getal x ongeveer gelijk is aan x/ln x. Dit geeft bijvoorbeeld als kans dat een (oneven) gegokt getal van honderdvijftig cijfers een priemgetal is ongeveer 1 op 173. Na minder dan een seconde zal er dus wel een priemgetal uit de bus komen.

Men kan wel gemakkelijk en snel voor een groot getal testen of het al dan niet een priemgetal is

Ten derde hebben we modulo-rekenen nodig. Dit is een natuurlijk begrip waar we dagelijks mee geconfronteerd worden. Ons uurwerk bijvoorbeeld rekent modulo 12 of 24. Laten we een digitaal exemplaar nemen dat modulo 24 rekent. Als het nu 21u is, hoe laat is het dan binnen 10 uur? Niet 31u, maar wel 7u. We moeten inderdaad niet gewoon 21 + 10 uitrekenen, maar ‘de rest van 21 + 10 bij deling door 24’, en die is 7. Dit heet optellen modulo 24, en we noteren dit symbolisch als 21 + 10 (mod 24) = 7. We kunnen zo ook vermenigvuldigen modulo 24; bijvoorbeeld is 21 · 10 (mod 24) = 18 want de rest van 210 bij deling door 24 is 18. Het is nuttig om te weten dat modulo-rekenen compatibel is met de gewone optelling en vermenigvuldiging. Zo berekent men 196 (mod 17) best niet door eerst de macht 196 uit te rekenen, en daarna de rest hiervan bij deling door 17. Het is eenvoudiger om eerst 19 (mod 17) te zoeken, wat natuurlijk 2 is, en daarna 26 (mod 17) = 13. Om nog maar eens terug te komen op onze lagere school: de negenproef die we daar geleerd hebben om te testen of een getal deelbaar is door 9 is eigenlijk rekenen modulo 9. En de kilometerteller van oude wagens rekent dikwijls modulo 100 000, wat nuttig is voor oneerlijke verkopers van tweedehandswagens met bijvoorbeeld 150 000 gereden kilometers.

Hoe werkt nu een digitale handtekening via het RSA-concept? Men wil een systeem dat een persoon (An) toelaat documenten of berichten digitaal ondertekend naar een willekeurige andere persoon (Bert) te sturen, zodat Bert kan verifiëren dat die handtekening wel degelijk van An is. An kiest twee priemgetallen p en q van honderdvijftig cijfers en houdt die strikt geheim. Ze berekent het product n = p · q en maakt n openbaar. Dit kan gebeuren via een soort ‘telefoonboek’ waar bij An in plaats van haar telefoonnummer haar getal n staat (het is cruciaal dat niemand p en q kan vinden uit n). An heeft ook nog twee andere getallen s en v nodig, beide kleiner dan n. Het getal s is haar private sleutel en dient om haar digitale handtekening aan te maken; ze houdt ook s strikt geheim. Het getal v is haar publieke sleutel en moet door iedereen gebruikt worden om haar digitale handtekening te verifiëren. Ze maakt dus ook v openbaar; v wordt bij n gezet in het ‘telefoonboek’ na de naam van An. Concreet kiest An gewoon v, en berekent ze uit v met behulp van de geheime p en q het getal s. Hoe dit precies gebeurt, en de nuttige eigenschap van s en v die straks gebruikt wordt, is niet zo moeilijk. Dit staat op het programma van de eerste bachelor Wiskunde en Informatica. Laten we An even als eenvoudig (en natuurlijk onrealistisch) voorbeeldje p = 5 en q = 11 kiezen als geheime priemgetallen; dan is n = 55. Kiest ze ook nog v = 3 als haar publieke sleutel, dan blijkt dat s = 27 haar private sleutel wordt. En hoe zet An nu haar digitale handtekening bij een bericht? Het bericht wordt op één of andere standaardmanier omgezet in een reeks getallen die kleiner zijn dan n. Zo’n getal b krijgt de digitale handtekening bs(mod n); dit is dus weer een getal kleiner dan n dat we h zullen noemen. Bij het voorbeeldje krijgt b = 49 dus de digitale handtekening h = 4927(mod 55) = 14. An stuurt dan b naar Bert, samen met h. Bert ontvangt b en h, kijkt in het ‘telefoonboek’ bij An en ziet n en v staan. Hij berekent hv(mod n), en de cruciale eigenschap van de getallen s en v is dat dit b moet zijn. Met b = 49 en h = 14 in het voorbeeldje berekent Bert 143(mod 55) en ziet dat dit inderdaad 49 is. Nu is Bert overtuigd dat het bericht b inderdaad digitaal ondertekend was door An, want de enige manier om een handtekening h te maken zodat hv(mod n) gelijk is aan b, is h te construeren via de geheime s als h = bs(mod n). En een snode bedrieger kan s niet uit v halen want dit kan enkel via de geheime priemgetallen p en q. (Voor wie het precies wil weten: s voldoet aan s · v (mod (p − 1) · (q − 1)) = 1 en dit garandeert dat bsv(mod n) = b indien b niet deelbaar is door p of q.) In 1997 heeft de Britse geheime dienst archieven vrijgegeven waaruit blijkt dat hun cryptografen James Ellis en Clifford Cocks eigenlijk al in 1970 en 1973 respectievelijk het idee van publieke sleutelcryptografie en de essentie van RSA ontdekt hadden. Dat is natuurlijk het nadeel van werken bij een geheime dienst …

De nieuwe Belgische identiteitskaart kan een digitale handtekening produceren die legale waarde heeft

Digitale handtekeningen via RSA worden intussen intensief gebruikt, en Mollin beschrijft in zijn boek verscheidene concrete toepassingen. De zogenaamde e-commerce bijvoorbeeld heeft als basis digitale cash-systemen, die veilig elektronisch geldverkeer toelaten bij aankoop van goederen en diensten. Zo bestaat een ‘elektronisch muntstuk’ in het concrete systeem Ecash uit getallen b en bs(mod n) als tevoren. Ook draadloze communicatie is een belangrijk toepassingsgebied. Belgacom en co moeten liefst in staat zijn om de kost voor een verbinding vanaf een GSM aan de juiste klant te factureren. Controle van de identiteit van de beller kan met RSA. Zeer actueel is de smart card, een plastic kaart waarin een microprocessorchip geïntegreerd is, zodat de kaart geheugen en rekencapaciteit heeft. Een voor ons heel belangrijk voorbeeld is de nieuwe Belgische identiteitskaart. Deze kan een identiteitsbewijs leveren bij elektronische communicatie en een digitale handtekening produceren die legale waarde heeft, en in die zin equivalent is van een gewone handtekening. Concreet maakt de kaart zelf priemgetallen p en q aan, en berekent ze een private sleutel s in termen van v = 65537. Het is ook nuttig om te weten dat men RSA ‘omgekeerd’ kan gebruiken bij het coderen van berichten, zodat een afluisteraar met het gecodeerde verzonden bericht niets kan aanvangen. Als An zo’n bericht b naar Bert wil versturen codeert ze het eerst met de publieke sleutel v van Bert, als c = bv(mod n). Ze zendt dan c naar Bert, en hij is de enige die c kan decoderen door er zijn eigen private sleutel s op los te laten : cs(mod n) is gelijk aan b. Men kan ook beide versies combineren. Zo is er een RSA-equivalent van een gewone handtekening zetten onder een brief van An aan Bert, en die daarna versturen in een verzegelde omslag. An kan namelijk een digitale handtekening zetten met behulp van haar eigen private sleutel, en daarna alles coderen met de publieke sleutel van Bert.

Als besluit bekijken we alles even vanuit een historisch perspectief. Een klassiek citaat van Carl Friedrich Gauss, wellicht de grootste wiskundige ooit, is dat ‘het probleem om priemgetallen te onderscheiden van samengestelde getallen en de ontbinding van deze laatste in hun priemfactoren één van de belangrijkste en nuttigste problemen is in de getaltheorie’. De huidige concrete toepassingen van dit probleem zijn een mooi voorbeeld van het grote belang van fundamenteel onderzoek op (zeer) lange termijn.

Zoals beloofd komt nu het elegante argument van Euclides om in te zien dat er oneindig veel priemgetallen zijn. Stel dat er maar eindig veel zouden zijn; noem ze p1, p2, … , pk. Kijk nu even naar het getal p1 · p2 · . . ·pk + 1. Dit is, zoals elk getal, te ontbinden in priemfactoren en is dus deelbaar door minstens één priemgetal. Maar dat priemgetal is zeker een deler van p1 · p2 · … · pk. Hieruit halen we dat dan ook (p1p2 ∙ … ∙ pk + 1) − p1p2 ∙ … ∙ pk = 1 deelbaar moet zijn door dat priemgetal. Maar dit kan niet: geen enkel priemgetal deelt 1. Onze veronderstelling moet dus verkeerd zijn, en bijgevolg zijn er oneindig veel priemgetallen.

Richard Mollin, RSA and Public Key Cryptography (Londen: Chapman & Hall/CRC 2003).
Manindra Agrawal, Neeraj Kayal en Nitin Saxena, ‘Primes is in P’, in: Annals of Mathematics (te verschijnen), http://www.cse.iitk.ac.in/news/primality.html (2002).

Willem Veys is als wiskundige verbonden aan de KU Leuven.

Deel dit artikel

Gerelateerde artikelen