Priemgetallen en geheimschrift

 Al eeuwenlang zijn de 'ondeelbare getallen' onderzocht. Daarbij gaat het om precies te zijn om natuurlijke getallen (meestal vanaf de 2) die alleen door zichzelf en door 1 zijn te delen. Ze heten priemgetallen en hebben bijzondere eigenschappen. Bovendien worden ze tegenwoordig ingezet bij het versleutelen van internetverkeer...

Inhoud:

Priemgetallen

 Een priemgetal is een getal dat alleen deelbaar is door 1 en door zichzelf.
7 is een voorbeeld van een priemgetal.
1 wordt niet meegeteld, 2 is het eerste priemgetal.
8 is een voorbeeld van een getal dat niet priem is: het is ook deelbaar door 2 en 4.
De eerste priemgetallen zijn 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, …
Priemgetallen zijn al heel lang bekend. Ze werden beschouwd als de 'onbreekbare bouwstenen' van de getallen. Dat komt omdat elk natuurlijk getal groter dan 1 op precies één manier als product van priemgetallen te schrijven is.

Bijvoorbeeld: 5208 = 23 · 3 · 7 · 31.

Elk natuurlijk getal bestaat uit zo'n product van priemfactoren. Je kunt de priemfactoren van een getal vinden door het telkens door de priemgetallen 2, 3, 5, 7, 11, 13, enz., te delen tot er een priemgetal over blijft.
De grote Griekse wiskundige Euklides bewees dit al zo'n 2200 jaar geleden in zijn beroemde boek 'De Elementen'.
Hij stelde ook dat er oneindig veel priemgetallen zijn.
Het bewijs van die stelling is een klassiek voorbeeld van een 'indirect bewijs'.

De grote zoektocht

 Priemgetallen hebben de mens altijd gefascineerd vanwege hun bijzondere eigenschappen en omdat ze moeilijk te vinden zijn. Van heel grote getallen is het namelijk heel tijdrovend om vast te stellen of het priemgetallen zijn of niet. Om er achter te komen of bijvoorbeeld een getal als 40.432.171 een priemgetal is, moet je onderzoeken of er een kleiner getal is (maar groter dan 1) waar je het door kunt delen.
De meest gebruikelijke manier om priemgetallen te vinden is de zeef van Erathostenes. Daarbij zet je eerst alle natuurlijke getallen vanaf 2 op een rijtje. Vervolgens 'zeef' je alle getallen die je kunt delen door 2 er uit, vervolgens alle getallen die je kunt delen door 3, daarna alle getallen die je kunt delen door 5 (4 is al weggezeefd!), enzovoort. En hoewel een computer dat tegenwoordig behoorlijk snel kan, blijft het voor grote getallen onbegonnen werk. Want ze lijken wel steeds verder uit elkaar te liggen naarmat je bij grotere getallen komt.
Hier een paar prangende vragen rond priemgetallen: Maar waarom is het interessant genoeg om een hele zoektocht is naar zo groot mogelijke priemgetallen te houden dat heel wat computerrekentijd aan wordt besteed?
Dat heeft te maken met de manieren waarop het tegenwoordige internetverkeer in elkaar zit. Allerlei instellingen en bedrijven willen berichten en transacties naar elkaar en van hun klanten geheim houden voor derden. En daarbij spelen priemgetallen een rol.

Modulo rekenen

 Het modulo rekenen is een uitbreiding van 'klokrekenen'.
Op de klok reken je namelijk met uren door weglaten van 12-vouden: 9 uur + 7 uur = 4 uur (eigenlijk 16 uur). Er bestaan ttrouwens zoals je hiernaast ziet ook 24-uurs klokken en trein-, bus- en tramdienstregelingen rekenen modulo 24.

Zo kun je ook met andere natuurlijke getallen modulo rekenen. Je laat dan de veelvouden van dat getal weg.
Zo is 13 = 1 (mod.12) en 36 = 0 (mod.12).
Daarin betekent ‘mod.12’ dat je veelvouden van 12 weglaat.
Ga na dat:
7 + 8 (= 15) = 3 (mod.12)
37 – 18 (= 19) = 7 (mod.12)
7 · 8 (= 56) = 8 (mod.12)

Je ziet dat optellen, aftrekken en vermenigvuldigen modulo 12 goed is te doen. Ook kun je aantonen dat je bij grote getallen eerst de 12-vouden mag weglaten en dan pas één van deze bewerkingen uitvoeren. Bijvoorbeeld:
37 – 18 =13(mod.12) – 6(mod.12) = 7 (mod.12)
Bewijs zelf dat dit algemeen voor deze drie bewerkingen opgaat.
Het betekent dat je voor rekenen mod.12 alleen tabellen nodig hebt voor de getallen 0, 1, 2, ..., 11. Je krijgt zo een heel overzichtelijke vermenigvuldigtabel.

Delen is een heel ander verhaal...
Dat komt niet altijd op een geheel getal uit, dus heb je er in veel gevallen niet veel aan. Maar soms toch wel:
bij gewoon rekenen kun je een vermenigvuldiging met bijvoorbeeld 8 ongedaan maken door terugrekenen, dus delen door 8. Maar bij modulorekenen gaat dat niet zo simpel:
7 · 8 (= 56) = 8 (mod.12),
maar hoe kom je van 8 (mod.12) weer terug naar die 7?

Je moet daarvoor op een andere manier tegen terugrekenen aankijken:
het terugrekenen vanuit een vermenigvuldiging met 8 doe je door vermenigvuldigen met het omgekeerde van 8, namelijk 1/8.
Je noemt 1/8 wel de inverse van 8.
Die inverse van 8 is het getal dat vermenigvuldigd met 8 precies 1 oplevert: 8 · 1/8 = 1.
Daarom krijg je uit 7 · 8 = 56 ook de 7 terug door met de inverse van 8 te vermenigvuldigen: 7 · 8 · 1/8 =7 · 1 = 7.

Maar hoe moet je nu terugrekenen in het modulosysteem?
Je moet dan dus de inverse van een getal x vinden.
En dat is het getal y dat vermenigvuldigt met x precies 1 oplevert:
als x · y = 1 (mod.12),
dan zijn x en y elkaars inverse bij rekenen modulo 12.

Als je de vermenigvuldigtabel mod.12 nog eens bekijkt zie je dat de meeste getallen helemaal geen inverse hebben. Alleen 5, 7 en 11 hebben een inverse en (toevallig) is de inverse van 5 gelijk aan 5, die van 7 gelijk aan 7 en die van 11 gelijk aan 11.
Zoek zelf maar eens uit welke getallen een inverse hebben bij bijvoorbeeld rekenen mod.8.
Je zult zien dat het getallen zijn die geen delers gemeen hebben met 8.
En dat geldt in het algemeen: bij rekenen mod.z hebben alleen getallen die geen delers gemeen hebben met z en groter zijn dan 3 een inverse. Je kunt die bepalen uit een vermenigvuldigtabel, al is dat wel veel werk bij grote getallen. (Misschien kun je een slimmere manier opzoeken of zelf bedenken?)

De zogenaamde Eulerfunctie j(n) geeft voor elk natuurlijk getal weer hoeveel kleinere natuurlijke getallen er zijn die geen priemfactor met n gemeen hebben.
Bijvoorbeeld: j(8) = 4 want 1, 3, 5 en 7 hebben geen priemfactoren met 8 gemeen en 2, 4 en 6 wel.
Voor een priemgetal p geldt natuurlijk j(p) = p – 1.
Voor een product van twee priemgetallen p · q geldt: j(p · q) = p · q – p – q + 1 = (p – 1)(q – 1).
(Dat kun je vast wel zelf bewijzen!)

Geheimschriften

 Al heel lang worden geheimschriften gebruikt. De studie ervan heet cryptologie. Het schrijven van geheimschrift is cryptografie.

Eenvoudige codes

Julius Caesar had een gemakkelijk systeem ontdekt: hij verving elke letter door een letter die drie plaatsen verderop in het alfabet staat.

Je ziet dat elke letter zo wordt vervangen door één andere letter. Caesar had geen andere tekens nodig: de Romeinse cijfers zijn ook letters: 1 = I, 5 = V, 10 = X, 50 = L, 100 = C, 500 = D en 1000 = M. de andere getallen zijn combinaties van die letters.

Je noemt dit opschuiven van drie letters wel Caesarcode C3. Je kunt natuurlijk ook afspreken dat je steeds 5 letters opschuift: Caesarcode C5. En zo zijn er allerlei afspraken mogelijk.
In C3 wordt WISKUNDEWEB vertaalt in ZLVNXQGHZHE.
Dit noem je coderen, vercijferen, of versleutelen. De sleutel is de afspraak dat je C3 gebruikt.
Het weer terugvertalen naar de oorspronkelijke tekst (die heet wel klare tekst) noem je decoderen, ontcijferen, of ontsleutelen. Hier doe je dat door alle letters van de code weer 3 plaatsen terug te schuiven, Caesarcode C–3.

Omdat alleen de verzender van het bericht en de ontvanger ervan weten welke sleutel is gebruikt, kunnen zij decoderen. Derden die de sleutel niet weten moeten moeite voor doen om te achterhalen wat de sleutel is. Dat noem je het kraken van een code.

De Caesarmethode is een voorbeeld van een code waarbij elk teken wordt vervangen door telkens hetzelfde andere teken. Dat heet monosyllabische substitutie.
Een ander voorbeeld daarvan is de zogenaamde Pigpen-code, waarvan je hier zowel de sleutel als WISKUNDEWEB in geheimschrift ziet.

Frequentie-analyse

Elke taal heeft een belangrijke eigenschap: niet alle letters komen even vaak voor.
Bijvoorbeeld in het Nederlands komt de E komt het meest voor, gevolgd door de A, enzovoorts. Alleen als spaties ook worden gecodeerd moet je er rekening mee houden dat die nog vaker voorkomen (na bijna elk woord).
Omdat de E het vaakst voorkomt zal bij monosyllabische substitutie in het geheimschrift het teken dat het vaakst voorkomt waarschijnlijk een E zijn (of een spatie!). Dus zoek je eerst naar het teken dat in je code het vaakst voorkomt. Het aantal keren dat een teken voorkomt heet de frequentie van dat teken. Het tellen van het aantal keren dat de verschillende tekens in een tekst voorkomen heet een frequentieanalyse van die tekst. Je legt er dan een frequentieverdeling van de Nederlandse letters naast en vergelijkt de frequenties met elkaar. Je hebt er wel een behoorlijk grote lap tekst in code voor nodig, want anders zullen de frequenties niet overeenkomen. Bijvoorbeeld WISKUNDEWEB telt evenveel W's als E's en alle andere letters hebben een frequentie van 1; dat schiet niet op bij frequentieanalyse.

De Vigenère-code

Monosyllabische substitutie is dus bij grotere berichten niet erg veilig want gemakkelijk te kraken. In 1585 werd er een veiliger geheimschrift uitgevonden. De uitvinding van het nieuwe geheimschrift wordt toegeschreven aan de Fransman Blaise de Vigenère, je spreekt van Vigenèrecode.
Daarbij wordt het Vigenèrevierkant gebruikt. De sleutel is een afgesproken woord, het sleutelwoord.

Hoe codeer je nu WISKUNDEWEB?

Enzovoort...
Je vindt: YWVOWBGEYSE.

Toevallig (omdat WISKUNDE 8 letters is en het codewoord 4 letters is) worden hier beide W's door dezelfde letter Y vervangen. Maar dat is vrijwel nooit het geval, een letter kan nu worden vervangen door steeds verschillende letters omdat je van meerdere alfabets gebruikt maakt. Probeer het maar uit...
Dit heet polyalfabetische substitutie.
Met frequentieanalyse alleen kun je deze code niet kraken, dus vele jaren dacht men dat hij onbreekbaar was. Het decoderen lukt alleen met behulp van het codewoord, ga zelf na hoe je dit moet doen.

In de negentiende eeuw werd een manier gevonden om de Vigenèrecode te kraken. Aan de codering van het woord WISKUNDEWEB met het sleutelwoord CODE kun je zien hoe dit in zijn werk zou moeten gaan. Juist omdat het codewoord steeds opnieuw wordt gebruikt, krijgt de letters W die 4, of 8, of 16, of ... (veelvoud van 4) verder zitten dezelfde code.
In 1863 bedacht de Pruissische majoor Kasiski een systematische manier om deze code te kraken.
Hij gokte de lengte van het sleutelwoord, bijvoorbeeld vier tekens. Hij bekeek dan de frequentieverdeling van de letters om de vier tekens. Als het sleutelwoord inderdaad vier tekens is, vind je voor die letters ongeveer de frequentieverdeling die voor de taal in kwestie normaal is. Als het sleutelwoord niet vier tekens is, wordt de frequentieverdeling van die letters gelijkmatig: alle tekens ongeveer evenveel. En zo kun je door proberen de lengte van het sleutelwoord te weten komen en na wat puzzelen de code kraken.

Enigma

 Na het kraken van de Vigenèrecode was een nieuw systeem nodig.
In 1920 kwam de Amerikaan Edward Hebern met iets nieuws. Hij voorzag een typemachine van een draaiend wiel, dat er voor zorgt dat bij het intypen van een bepaalde letter een andere letter wordt afgedrukt. Hier zie je zijn prototype.

In de Tweede Wereldoorlog gebruikte de Duitse marine de Enigma codeermachine die erg op de Hebern-machine leek voor hun U-boten (onderzeeboten). Ze typten een bericht op de Enigma en schreven op welke lampjes (letters) er gingen branden. Daarna werd de versleutelde boodschap via een telegraaf doorgeseind.

De Enigma-machine was gebaseerd op een systeem van drie rotors die er voor zorgden dat de klare tekst werd gecodeerd. 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 ingtypte 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. Uiteindelijk werd de W dus een A. Typte je dan een opnieuw een letter W dan draaide de eerste rotor een slag, dus W wordt Q en dan wordt Q door de tweede rotor veranderd in N en N door de derde in B. Dus nu wordt W gecodeerd tot B. Zo wordt een letter elke keer veranderd in een andere letter. De rotors konden 26 · 26 · 26 posities ten opzichte van elkaar hebben.
De Britse geheime dienst was er veel aan gelegen om die code te breken. De wiskundige Alan Turing zat in het team dat zich ermee bezig hield. Dit leidde tot de uitvinding van de computer!
Meer over de Enigma vind je hier:

Een model voor de Enigma

In de Levende tijdlijn vind je (na inloggen) het spel "Geheimschrift".
Daarin zit ook een vereenvoudigd model voor de Enigma-machine dat bestaat uit drie schijven: Je codeert als volgt: Je moet heel goed bijhouden waar je moet aflezen en of je de schijven wel hebt gedraaid.

Onbreekbare code

 Het principe van de volgende versleuteling is al in 1917 bedacht door Gilbert Sandford Vernam, een Amerikaans cryptograaf. In feite is zijn methode hetzelfde als die van Vigenère. Het probleem van het raden van de lengte van het sleutelwoord loste hij eenvoudig op door voor het 'sleutelwoord' een verzameling willekeurige tekens te kiezen die even lang was als de klare tekst. Dit sleutelwoord stuurde hij ook niet mee: hij bedacht het systeem van 'heen-en-weer-sturen' om te decoderen.
Je wilt weer het woord WISKUNDEWEB coderen. Je gebruikt de (geheime) sleutel BZAXDEFKPRW en codeert met het Vigenèrevierkant. Dat levert op: XHSHXRIOLVX. Jij bent nu de verzender V en O is de ontvanger. Speel dit maar even na...

Bij de intrede van de computer is het systeem verder ontwikkeld.
Computers gebruiken vaak voor tekens de zogenaamde ASCII (American Standard Code for Information Interchange). Elk teken (byte) bestaat daarin uit 8 nullen of énen, 8 bits. Hier zie je de ASCII-tabel.
De codering van het woord WISKUNDEWEB doe je nu stap voor stap (zelf doen!).

Deze Vernamcodering is in principe onbreekbaar. Het nadeel is dat je veel handelingen moet verrichten en steeds berichten heen en weer moet sturen: er is veel dataverkeer nodig!

Internetverkeer

 Banken willen niet veel berichten heen en weer sturen als een klant betalingen moet doen. Dat kost tijd en dat vindt de klant hinderlijk en de bank te duur. Daarom gebruiken zij een coderingssysteem waarbij aan de kant van de gebruiker iedereen zijn betalingsopdracht kan vercijferen, maar alleen de bank in staat is om die opdracht ook weer te ontcijferen. De wiskundigen Rivest, Shamir en Adleman bedachten in 1978 een geschikt systeem dat RSA wordt genoemd. Het is gebaseerd op rekenen met priemgetallen en op modulo rekenen.

Hoe werkt nu RSA?

Stel je voor je wilt het woord WISKUNDEWEB coderen. De getallen N en S vormen de publieke sleutel. Die mag iedereen weten, dus zo kan iedereen een bericht versleutelen.

Om het gecodeerde woord weer te decoderen heb je de decodeersleutel D nodig.
Die decodeersleutel moet voldoen aan D · S = 1 (mod.M), dus in dit geval aan D · 5 = 1 (mod.264).
(Bij het modulorekenen kun je nu nalezen waarom S een getal boven de 3 moest zijn en geen gemeenschappelijke delers met M mocht hebben.)
Deze D (hier dus bijvoorbeeld 53) is de geheime sleutel die alleen bekend is aan degene die moet decoderen.

Je decodeert nu door de afzonderlijke cijfers van het geheimschrift tot de macht D te doen en er veelvouden van 299 (= N) van af te trekken.
Decodeer je gecodeerde woord WISKUNDEWEB en ga na dat je dit woord weer terug krijgt.