De simpele magie van priemgetallen in geheimschrift

Priemgetallen zijn magische getallen, die door de eeuwen heen al bewust en onbewust zijn gebruikt en nu met groot succes worden ingezet om internetverkeer, banktransacties en ook e-mails te coderen. Wat is het geheim achter deze getallen? Hoe gaan priemgetallen volstrekte privacy garanderen?

door

Iedereen kent de uitspraak “YHQL, YLGL, YLFL” van Julius Caesar. Tenminste, zodra die ontcijferd is. Julius Caesar gebruikte geheimschrift om zijn leger te informeren: het naar hem genoemde Caesar-Cipher. Dit was vrij eenvoudig, elke letter van het originele bericht werd in het alfabet 3 plaatsen naar voren geschoven. A werd D, B werd E enzovoort. Een op deze manier gecodeerde boodschap is snel ontcijferbaar en het Caesar-Cipher is tegenwoordig dan ook geen gebruikte methode meer.

Als u een geheim bericht naar een vriend wil sturen, is er dan geen mogelijkheid om dit volstrekt veilig te doen? De Duitsers dachten in de tweede wereldoorlog dat ze de oplossing hadden. Ze gebruikte een aangepaste typemachine, de Enigma.

Enigma

De Enigma-machine was gebaseerd op een systeem van drie rotors die er voor zorgden dat de tekst werd gecodeerd (zie afbeelding 1). Die rotors draaiden ten opzichte van elkaar. Eerst werd via een geheim codeboek de begininstelling van de Enigma gekozen, per dag een andere. Die begininstelling zorgde er bijvoorbeeld voor dat een ingetypte W door de eerste rotor veranderde in een P, waarna door de tweede de P in een M en door de derde de M in een A. Dus uiteindelijk wordt de W een A. Het grote voordeel ten opzichte van het Caesar-Cipher was dat na elke letter de rotors draaiden. De volgende W werd weer gecodeerd tot een andere letter.

Het probleem was dat iedereen, die de begininstelling kende, het bericht kon ontcijferen. Er moest een afspraak gemaakt worden over de manier van coderen en die afspraak kon ook onderschept worden. Elke maand moest men het codeboek met alle sleutels voor die maand over het hele Duitse leger, inclusief duikboten, verspreiden. Dit vormde een enorm logistiek probleem en als er één sleutelboek onderschept werd door de Britten, konden de Britten een maand lang alle Duitse berichten zonder enig probleem ontcijferen.

De Enigma-coderingsmachine. De Duitsers vertrouwden er tot het einde van de Tweede Wereldoorlog op dat de berichten, die door deze machine gecodeerd waren, volstrekt veilig verzonden konden worden. Een fout, die hen fataal is geworden. Velen zien het breken van de enigma-codering door de Britten en Polen als het grote keerpunt in de Tweede Wereldoorlog.

De Duitsers hadden met de hulp van priemgetallen misschien wel de oorlog in hun voordeel kunnen beslissen. Het geheim van de hedendaagse codering met behulp van priemgetallen was alleen nog niet door hen ontdekt. Maar wat zijn nu precies priemgetallen? Waarom is 7 wel speciaal en 8 niet? Rond 400 v. Chr. openbaarden priemgetallen zich voor het eerst aan de wereld.

Priemgetallen en Pythagoreërs

Pythagoras staat bekend als Grieks wijsgeer en hervormer, een van de meest raadselachtige figuren uit de geschiedenis van het Griekse denken. Rond 530 voor Christus stichtte hij in Crotona (Zuid-Italië) een gemeenschap, die zich bezighield met religie, wijsbegeerte, wiskunde en politiek. De Pythagoreërs (de volgelingen van Pythagoras) hadden een bijzondere interesse in natuurlijke getallen (1,2,3,4 … enzovoorts) en hun eigenschappen. Ze geloofden dat de natuurlijke getallen en hun verhoudingen de basis waren van alle leven en van het heelal.

Dankzij hun grote interesse in de natuurlijke getallen, ontdekten de Pythagoreërs al voor 400 voor Christus iets bijzonders over bepaalde getallen. De Pythagoreërs ontdekten dit bij het rangschikken van een aantal stenen. Dit kunnen er één zijn, twee, drie, vier of meer. Het viel de Pythagoreërs op dat met sommige aantallen steentjes het mogelijk was een rechthoek te leggen en dat sommige getallen slechts als een lijn gelegd konden worden.

Bepaalde aantallen steentjes kunnen op geen enkele manier in de vorm van een rechthoek gelegd worden

Zes steentjes bijvoorbeeld kunnen als een rechthoek van 2 bij 3 gelegd worden. Zestien als 4 bij 4. Maar bij 7 of 13 is geen rechthoek of vierkant mogelijk.. Alleen een rechte lijn. De Pythagoreërs noemden getallen zoals 7 en 13 daarom rechtlijnige getallen; tegenwoordig heten deze getallen priemgetallen.

Priemgetallen zijn getallen, die alleen door één en zichzelf deelbaar zijn. Acht is geen priemgetal want 8 is deelbaar door 2. Het getal 17 is wel een priemgetal. Er is geen getal denkbaar waar 17 door te delen is zonder dat er een getal achter de komma ontstaat.

De getallen onder de 100, die alleen door zichzelf en 1 deelbaar zijn: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 en 97. Hierbij wordt 1 niet meegeteld, 2 is het eerste priemgetal. Deze lijst gaat eeuwig door. Er is daarom niet zoiets als “het grootste priemgetal”. Wel bestaat het grootst bekende priemgetal op dit moment. Dit getal bestaat uit 7.816.230 cijfers en werd pas maart 2005 ontdekt. Dit haalde wereldwijd de voorpagina’s en leverde de ontdekker 50.000 dollar op. Het Great Internet Mersenne Prime Search-project, een Amerikaanse organisatie, betaalt 50.000 dollar voor elk nieuw record. Mocht u een nieuw priemrecord vinden van meer dan 10.000.000 cijfers, dan levert u dit zelfs 100.000 dollar op.

In de ideale codeersituatie is maar één keer dataverkeer nodig en hoeft daarvoor geen sleutel uitgewisseld te worden. Geen geheime sleutel. Dit is precies waar priemgetallen voor kunnen zorgen. Maar met welke magie krijgen priemgetallen dit voor elkaar?

De magie van de priemgetallen
De truc van de priemgetallen wordt toegepast in de zogenaamde asymmetrische cryptografie. Hierbij is er niet één sleutel, maar zijn er twee. Een publieke sleutel en een geheime sleutel. De publieke sleutel kan door iedereen gebruikt worden om een bericht te coderen, maar alleen de ontvanger, die de publieke sleutel bekend heeft gemaakt, kan deze gecodeerde berichten ontcijferen. Het is als een hangslot. Iedereen kan het dichtklikken, maar alleen degene met de sleutel kan het weer openen.

Een uitleg met een voorbeeld maakt dit duidelijk. In dit voorbeeld worden kleine priemgetallen gebruikt, maar voor echte codering worden priemgetallen van honderden cijfers gebruikt.

Priemgetallen hebben een speciale eigenschap: Euclides bewees in zijn boek ‘De Elementen’ dat elk natuurlijk getal (1,2,3,4 …) op juist één manier kan ontbonden worden in priemfactoren. Met andere woorden, elk natuurlijk getal kan gemaakt worden door bepaalde priemgetallen te vermenigvuldigen. Dit kan maar op één manier. Zo bestaat 42 uit 2 × 3 × 7. Er is geen andere combinatie van priemgetallen denkbaar om 42 te vormen. En dit is precies het magische hangslot voor coderingen. Er is een wiskundige methode waarbij voor het coderen het natuurlijke getal (bijvoorbeeld 42) nodig is, maar voor het ontcijferen de unieke priemgetallen (2, 3 en 7) waaruit dit natuurlijke getal bestaat nodig zijn. Dus 42 klikt het slot dicht en 2,3 en 7 maken het open.

Het “dichtklikken” is vrij makkelijk. Neem twee priemgetallen, bijvoorbeeld 19 en 29. De publieke sleutel is nu 551, want 19 × 29 is 551. Iedereen kan nu met deze publieke sleutel een bericht coderen. Maar om dit bericht vervolgens te ontcijferen zijn 19 en 29 nodig. En die weet alleen de maker.

Dit is een goede beveiliging, want twee grote priemgetallen zijn vrij makkelijk te vermenigvuldigen, maar om een groot getal te ontbinden in priemgetallen is heel moeilijk. Daarvoor voldoen op dit moment de beste computers niet eens. De boodschap is dus volstrekt veilig zolang de twee priemgetallen maar groot genoeg gekozen worden.

Waarom u dit niet had mogen lezen

Diverse geheime diensten en veiligheidsorganisaties, zoals de Amerikaanse NSA ( National Security Agency) verzetten zich om deze reden hevig tegen codering met priemgetallen. De sterke encryptie kan immers ook gebruikt worden voor illegale doeleinden zoals terrorisme, drugshandel en belastingontduiking. De Verenigde Staten besteden miljarden dollars aan het ‘aftappen’ van onder andere telefoon- en e-mailverkeer, om zo bijvoorbeeld terroristische aanslagen te verhinderen. Maar als terroristen hun e-mails gaan versleutelen, hebben de terroristen vrij spel voor hun communicatie.

Kennis kan gevaarlijk zijn. U bent nu ook in het bezit van de globale kennis om bijna onkraakbare codes te maken. Er is goede kans dat om die reden uw internetverkeer op dit moment scherp in de gaten wordt gehouden door een overheidsdienst. U bent vrij om voor nog meer informatie op één van de onderstaande links te klikken, maar hou wel die zwarte auto aan de overkant van de straat in de gaten.