DE MATHEMAAT

DE MATHEMAAT

.....

Wiskunde als dagelijkse ervaring 😉

Geheimschrift (2)

GeheimschriftPosted by Hans Schipper Tue, October 30, 2018 21:15:30

Cryptografie is wiskunde die dagelijks door onze vingers gaat. Van smartphone tot bankzaken, van belasting tot verzekering, van email tot ov-kaart, van ELO* tot BOL … het is allemaal sterk afhankelijk van cryptografie om uw informatie te bewaken en uw leefomstandigheden veilig te stellen. Cryptografie is een 2500 jaar oud onderdeel van de wiskunde dat in onze moderne leven een niet weg te denken plaats is gaan innemen.

Helaas gaan veel mensen er als gevolg van de schijnbare complexiteit van cryptografie van uit dat het beter is dit onderwerp over te laten aan de AIVD, computerwizards, zwarte hoed tovenaars, hightech bedrijven en de NSA. Ik wilde in een aantal blogs de beginselen van de cryptografie beschrijven hier en daar voorzien van een historisch sausje.

Sinds de dageraad van de menselijke beschaving is informatie een van de meest gekoesterde troeven. In staten en staatjes heeft het vermogen (of onvermogen) om geheimen te bewaren en informatie te verbergen politieke partijen geëlimineerd, het tij van de oorlogen verschoven en hele regeringen omvergeworpen.

U kunt zich het volgende historische voorbeeld van cryptografie in de praktijk wel voorstellen. In de Amerikaanse Revolutionaire Oorlog werd waardevolle informatie over het plan van het Britse leger om een Amerikaans kampement aan te vallen door lokale milities onderschept.

In 1776 kon generaal Washington niet zomaar een snel appen naar de bevelhebbers van het kampement in kwestie. Hij moest een boodschapper sturen die ofwel een of andere vorm van schriftelijke correspondentie ging vervoeren, ofwel het bericht uit het hoofd had geleerd. Tricky business, om het maar eens in Amerikaanse termen te schrijven.

De boodschapper moest immers vaak door vijandelijk gebied reizen om de boodschap over te brengen. Wat als hij werd onderschept? Slecht nieuws voor de aandelen George Washington ...

Boodschapper zijn hoort tot de risicovolle beroepen en bij gevangenneming door de Britten volgt vastzetten, marteling, de strop en wellicht nog andere onaangenaamheden. De communicatie tussen George en zijn commandant te velde is in ieder geval voortijdig beëindigd.

Maar er is meer. De Britten hadden de boodschapper kunnen "overhalen" om de inhoud van het bericht te delen, waardoor de informatie nutteloos zou worden. Of, als de boodschapper nog wat speelschulden af te lossen had, was omkoping om valse informatie te verspreiden, met als gevolg de dood van duizenden Amerikaanse milities, niet onwaarschijnlijk.

Echter, met zorgvuldig gebruik van cryptografie kon Washington de inhoud van het bericht veilig stellen door een methode die bekend staat als versleuteling.

afbeelding 2 Jeffersons cilinder cipher

Ervan uitgaande dat hij de versleuteling alleen aan zijn trouwste officieren toevertrouwde, zou deze tactiek ervoor zorgen dat zelfs als de boodschap werd onderschept, de boodschapper geen kennis zou hebben van de inhoud ervan. De gegevens worden dus onleesbaar en nutteloos voor de vijand. Goed voor de aandelen George Washington.

In mijn post “Numb3rs aflevering 102 Sabotage” vertelde ik hoe mijn brugklasleerlingen met de methode Caesar de eerste schreden op het cryptopad zetten. Caesar is helaas makkelijk te breken. Je zou daarom op een andere methode kunnen overstappen, maar je kunt ook een al met Caesar versleuteld bericht nog verder verwarren. Dit kan bijvoorbeeld met de Hebreeuwse Geheimschrift Methode. Zoals U misschien weet gaat het Hebreeuwse schrift van rechts naar links. De Hebreeuwse Geheimschrift Methode doet iets soortgelijks, maar dan wel zo gestructureerd dat je er in dit verband iets aan hebt.

Stel de “plaintext” is: zoals afgesproken, bezoek ik jou

Deze tekst wordt als volgt bewerkt (rechtsboven beginnen):

De “ciphertext” wordt dan (linksboven beginnen): egfaslaozebnekorpsuojkikeoz

Als de plaintext een gewoon Nederlands zinnetje is, dan is het niet zo moeilijk de code te breken, maar als de plaintext de uitkomst is van een andere versleuteling, dan wordt ontcijferen toch een hele puzzel.

Er zijn natuurlijk variaties mogelijk:

Variatie 1 (rechtsonder beginnen)

De “ciphertext” wordt dan: uojkikeozebnekorpsegfaslaoz

Een andere variatie is de slangmethode, ook wel de zigzagmethode genoemd:

Variatie 2

De ciphertext wordt dan: egfaslaozsprokenbeuojkikeoz

En zo kan het natuurlijk ook:

Variatie 3

De ciphertext wordt: uojkikeozsprokenbeegfaslaoz

Variatie 4

Steeds de letter na de volgende (of de 3e of de 4e volgende) is geldig, terwijl de andere letters ertussenin slechts als misleidende nieten moeten worden behandeld. De nieten zijn hier gearceerd.

Ciphertext: sdlkalofzsrebg enzovoorts

Deze variatie is natuurlijk met de eerder genoemd variaties te combineren.

De ontvanger kan de ciphertext zonder problemen ontcijferen als hij de procedure van de uitgevoerde versleuteling kent en als hij de letters van het ontvangen bericht (zoals hierboven) in de velden van de gegeven rechthoek invoert.

Een klas kan hier leuk aan puzzelen door bijvoorbeeld bij een versleuteld bericht meerdere rechthoeken te leveren.

bronnen en noten

1) Amerikaanse burgeroorlog: klik hier

2) Cryptografie: klik hier

3) Boek: Hans Schneickert - Moderne Geheimschriften

4) ELO = Elektronische Leer Omgeving



De vader, de zoon en de crypto-som

GeheimschriftPosted by Hans Schipper Wed, October 24, 2018 12:52:40

Pythagoras

Het septembernummer van het altijd weer boeiende tijdschrift Pythagoras (voor jongeren van geest 🙂) heeft bij de kleine nootjes een zogenaamde crypto-som staan. Met een beetje redeneren en een gelukkige gok is het me gelukt hem op te lossen. Meestal lukt het deze puzzels met puur redeneren op te lossen. Hieronder beschrijf ik een mooie oplossing van de crypto-som der crypto-sommen.

Meer dan veertig jaar geleden maakte ik tijdens mijn militaire diensttijd kennis met dit type puzzels, waarvan er nu dus een in Pythagoras verscheen. “HET WAS EEN HETE ZOMER” is een exemplaar uit een hele familie. Tijdens mijn soldaat zijn ben ik er vaardig in geworden, maar … dat wil niet zeggen dat het me nu nog altijd zo snel lukt als toen. Soms zit ik er uren aan. Op een gegeven moment heb ik dan een gevoel van “ik tegen de puzzel” en dan voel ik me des te trotser als ik hem resolveer. Van mijn zus ontving ik voor mijn drieëntwintigste verjaardag een van de hoofdwerken uit de Nederlandse spellen- en puzzelcultuur van de hand van Pieter van Delft en Jack Botermans getiteld “Spelen en Puzzels” en ook daarin staan ze vermeld. De crypto-som wordt beschreven als een berekening waarbij enkele of alle cijfers door letters of punten worden vervangen. De bedoeling is dat U erachter probeert te komen welke cijfers daarvoor in de plaats moeten komen te staan om de berekening kloppend te maken. Crypto-sommen kunnen bijna altijd door logisch denken worden opgelost. Er is alleen enige elementaire kennis van de eigenschappen der getallen voor nodig, bijvoorbeeld, dat het laatste cijfer van een vermenigvuldiging met 5 altijd 5 of 0 moet zijn. Maar soms moet U het steeds opnieuw proberen door op een bepaalde plaats telkens een ander cijfer in te vullen.

Later kwam ik de crypto-som der crypto-sommen tegen in het leuke boekje “Wiskunde voor je plezier” van de Amerikaanse bridgespeler, backgammonspecialist en schrijver Oswald Jacoby. Jacoby was een kleurrijke figuur. In Brooklyn leerde hij op zesjarige leeftijd whist spelen. Tijdens de Eerste Wereldoorlog loog hij zich op vijftienjarige leeftijd het leger in. De jonge blaag besteedde er zijn tijd grotendeels aan het spelen van poker. Later verliet hij voortijdig de Columbia-universiteit om actuaris te worden.

Gezien zijn bravourverleden, vermoed ik dat het onderwerp van de volgende puzzel hem deugd zal hebben gedaan. De puzzel is vele, vele malen gepikt en weer in andere boeken terecht gekomen. Het is me niet bekend wie de oervader is.

Stuur meer geld

Een vader die zich ergerde aan de herhaalde verzoeken van zijn studerende zoon om meer geld, was helemaal obstinaat toen hij op één dag met de post zo’n verzoek kreeg tegelijk met een verslag van de armzalige resultaten van zijn zoon.

De volgende brief van de vader was kort en ter zake:

Geliefde zoon,

Als je dan voor je professoren niets wilt uitvoeren, wil je het dan misschien wel voor mij doen. In ieder geval zal je geen geld meer krijgen eer je me de oplossing geeft van het volgende:

Verschillende letters is verschillende cijfers en gelijke letters is gelijke cijfers.

Met hartelijke groet,

Je vader

Kunt U de zoon helpen met de oplossing?

Ik ben altijd gaarne bereid een zoon te helpen …

De eerste denkstap voor de zoon is om op te merken dat het antwoord meer letters bevat (vijf letters) dan de vraag (per rij vier letters). Als de som van twee getallen met vier cijfers een getal met vijf cijfers is, dan begint het getal met vijf cijfers met een 1.


Nu staat er op de plaats van de duizendtallen een 1, dus de enige waarde die S kan hebben is S = 9. Ga maar na: als S < 9 dan is de som van de getallen kleiner dan 10 000. Gevolg daarvan is dat O = nul.

De puzzel is nu gereduceerd tot:

Kijk nu eens naar de kolom van de honderdtallen (E0N). Als er geen “1” wordt overgedragen vanuit de tientallen, dan zou E = N. Maar dat mag niet want verschillende letters = verschillende cijfers. Dus er moet een “1” worden overgedragen vanuit de tientallen.

Hieruit volgt: E + 1 = N

Over de kolom voor de tientallen kunnen we zeggen dat

1) N + R = E + 10 als er geen overdracht vanuit de eenheden heeft plaatsgevonden of

2) 1 + N + R = E + 10 als er wel een overdracht vanuit de eenheden heeft plaats gevonden.

We gaan het maar eens even uitproberen en we nemen aan dat er geen overdacht vanuit de eenheden heeft plaats gevonden.

N+R = E+10 en 1+E = N

(1+E)+R = E+10

1+R = 10

R = 10-1

R = 9

Maar oh, oh, oh … 9 is al in gebruik voor S, dus R kan niet 9 zijn. Dat betekent dat er een overdracht is vanuit de eenheden.

1+N+R = E+10 en 1+E = N

1+(1+E)+R = E+10

2+R = 10

R = 10-2

R = 8

Zo ver zijn we tot nu toe gekomen:


N kan niet 0 of 1 zijn omdat 0 en 1 al worden gebruikt.

N kan niet 2 zijn, want 1+2+8 = 11 en dan zou E = 1, maar dat mag niet want 1 is al in gebruik.

N kan niet 8 of 9 zijn, want die zijn al in gebruik.

Blijft over voor N: 3,4,5,6 of 7 en dan moet E moet 2,3,4,5 of 6 zijn omdat het 1 kleiner is dan N.

Stel E = 2. Dan zou D 8 of 9 moeten zijn om “1” te kunnen overdragen naar de tientallen. Maar 8 en 9 zijn al in gebruik.

Conclusie: E kan niet 2 zijn (en N kan niet 3 zijn).

Stel E = 3. Dan zou D 7 of 8 moeten zijn om “1” te kunnen overdragen naar de tientallen. D kan niet 7 zijn, want dan zou Y nul worden en die is al in gebruik. D kan niet 8 zijn, maar dat hadden we al gezien.

Conclusie: E kan niet 3 zijn (en N kan niet 4 zijn).

Stel E = 4. Om “1” over te kunnen dragen naar de tientallen, moet D

6,7,8, of 9 zijn. Nou ja 8 en 9 zijn nog steeds al in gebruik, hè.

Stel D = 6. Dan wordt Y = 0 en 0 is al in gebruik.

Stel D = 7. Dan wordt Y =1 en 1 is al in gebruik.

Conclusie: E kan niet 4 zijn (en N kan niet 5 zijn).

De enige twee mogelijkheden voor E zijn nu 5 en 6.

Stel E = 6. Dan wordt N eentje groter en dus 7.

Om overdracht vanuit de eenheden naar de tientallen te krijgen neemt D de waarden 4, 5, 6of 7 aan.

Stel D = 4. Dan wordt Y = 0 en dat is al in gebruik.

Stel D = 5. Dan wordt Y = 1 en dat is al in gebruik.

Stel D = 6. Dat is al in gebruik voor E (aanname)

Stel D = 7. Dat is al in gebruik voor N (zie boven)

Er zijn geen oplossingen voor E = 6.

Conclusie: E moet 5 zijn.


Er zijn nu nog twee cijfers voor D en Y, namelijk 2 en 7.
Nemen we voor D = 5, dan vindt er geen overdracht plaats.
Conclusie: D = 7 en Y = 2
Dus het eindresultaat is:

Of de zoon ooit nog geld van zijn vader heeft ontvangen vertelt het verhaal niet …





Engima

GeheimschriftPosted by Hans Schipper Fri, October 12, 2018 09:29:40

De afloop van de Tweede Wereldoorlog is met misschien wel twee jaar versneld door het fantastische werk van de Poolse en Britse codebrekers die werkzaam waren op het landgoed Bletchley Park. Daar kraakten de wiskundigen keer op keer de Duitse code “Enigma”, waarvan gedacht werd dat die onbreekbaar zou zijn. De Duitser gebruikten Enigma om berichten te vercijferen die werden verstuurd om de onderzeevloot in het Noordelijk deel van de Atlantische Oceaan naar zijn positie te dirigeren.

Leden van de Women's Royal Naval Service werken in 1942 op Bletchley Park met Colossus, ‘s werelds eerste elektronische programmeerbare computer. Bron: klik hier

Het coderen door De Duitsers gebeurde aan boord van een duikboot met behulp van een machine, de Enigma. De Britten hadden er een te pakken weten te krijgen, maar het bezit van de machine alleen was niet genoeg. De machine had namelijk een duizelingwekkend groot aantal posities, een slordige 158.962.555.217.826.360.000, en bovendien moest je per dag de startpositie weten, die weer in een boek stond waar je ook nog eens de beschikking over moest hebben. Dat boek werd tot overmaat van ramp iedere maand verwisseld. Voor wie uitleg wil over de wiskunde achter dit apparaat zou eens kunnen kijken naar een aflevering op het Youtube-kanaal Numberphile. Klik hier

De wiskundigen op Bletchley gebruikten doordachte schattingen en eenvoudige vroege computers om te proberen in een bericht door te dringen. De Enigma-machine was op een Duitse U-boot veroverd door het Engelse schip HMS Bulldog op 9 mei 1941.

Enigma, Museo Nazionale Scienza e Tecnologia Leonardo da Vinci

De film rommelt overigens ongegeneerd met de historische feiten: geen melding wordt gemaakt van Alan Turing, de geniale Britse codebreker en grondlegger van de Informatica. Hij was het die uiteindelijk de Enigma code doorbrak. Turing was een homoseksueel die uiteindelijk door de Britse wetgeving de zelfmoord werd ingejaagd. Hij wordt in de film heel hypocriet vervangen door de fictieve en heel erg heteroseksuele held Tom Jericho (Dougray Scott). Eind twintigste eeuw had Groot-Brittannië kennelijk nog steeds grote moeite met de waarheid rondom Alan Turing. Een recentere film, “The imitation game”, schijnt overigens een beter beeld te geven van Turing.

De door Michael Apted geregisseerde film is gebaseerd op een spannende literaire thriller van Robert Harris, die Bletchley portretteert als een hogedrukketel vol intrige waar Engelands briljantste wiskundigen tegen de klok op werkten aan het breken van Duitse codes zodat de konvooien op de Atlantische Oceaan konden worden gewaarschuwd.

Bij de filmopening hebben de Duitsers net weer hun code gewisseld. Tom Jericho, die na een zenuwinzinking naar huis was gestuurd, wordt naar de enclave terug gehaald, want ook al is hij een geestelijk wrak, met zijn genie kan hij misschien toch helpen.

Waarom had Jericho een zenuwinzinking? Niet omdat hij wiskundig was vastgelopen, maar omdat hij compleet hoteldebotel is van Claire Romilly (Saffron Burrows). De mooie Bletchley collega is op mysterieuze wijze verdwenen zonder gedag te zeggen. Nou zeg.

Filmposter

Terug op zijn baan wordt hij intiem met Claire’s vroegere huisgenote Hester Wallace (Kate Winslet), die wellicht de een of andere sleutel tot de oplossing van het mysterie rondom Claire zou kunnen hebben zonder het zich te realiseren. Op subtiele terloopse wijze worden Tom en Hester steeds intiemer. De hele tijd worden ze door Wigram (Jeremy Northam), een intelligente geheim agent, in de gaten gehouden, omdat hij denkt dat ze meer over Claire weten dan ze willen toegeven. Claire zou geheimen kunnen doorspelen aan de Duitsers.

Wat ik zo interessant vind aan de film is de combinatie van suspense en intelligentie. Het spannende verhaal houd je geboeid en ondertussen komt er ook wiskunde mee. De scene waarin de wiskundigen uren achter elkaar doorwerken, om met druppels informatie die telefonisch binnen sijpelen, de procedure voor het ontrafelen van de code te ontwerpen, is machtig mooi in elkaar gezet. Ook begrijpen we door de film hoe cruciaal het werk van de wiskundigen op Bletchley was. Zo cruciaal dat het 30 jaar lang verborgen werd gehouden.

Toen het feit dat de Britten de code hadden gebroken uiteindelijk bekend werd, moest de geschiedenis worden herschreven. Een recente biografie over Churchill suggereert bijvoorbeeld dat, toen hij stoutmoedig op het dak van de Admiraliteit in Londen schreed, dat alleen maar kon omdat uit ontcijferde Enigma berichten was duidelijk geworden dat er die nacht geen luchtaanvallen zouden plaatsvinden.

De Britten hebben een manier van doen alsof het ze allemaal niet zoveel kan schelen. Hun thrillers zijn er mee doordesemd. Amerikaanse helden zijn stoer, openhartig en gefocust. Britten houden van understatement en sluwheid. De spanning tussen Tom Jericho en Wigram is des te interessanter omdat beide personages soms lijken te acteren in hun eigen kleine toneelstuk. Ze zijn evenzo geïnteresseerd in hun verbale afweer als in de onderliggende onenigheid. Het is een strijd tussen stijlen. De Britse thriller literatuur is rijk aan dit soort persoonlijkheden.

Kate Winslet is erg goed. Ook al is ze dapper, draagt ze degelijke schoenen en heeft ze het verkeerde kapsel, in het juiste licht gezien is ze een kleine proletarische seksbom. Ze wordt mysterieus doordat ze zich gemakkelijk tussen slonzig en sexy in beweegt. Claire, gespeeld door Saffron Burrows, is vergeleken daarmee eendimensionaal: zij is het soort vrouw dat bij iedere heteroseksuele man op het netvlies geëtst blijft staan. Daarom kan ze een masochistische romanticus als Tom Jericho in haar web gevangenhouden.

Met menig bovenbouw klas heb ik geboeid naar dit meesterwerk gekeken. Steeds de laatste tien minuten van de les of op de laatste dag voor de vakantie of tijdens lessen waarin nogal wat leerlingen afwezig waren voor een bezoek aan een van die vermaledijde Open Dagen.

Enigma laat prachtig de impact van de wiskunde op ons bestaan zien.