4.4 Een zwakke plek

Opgave 3

De boodschap:
'je gele kanariepak ok, als je je duikbril maar meeneemt' wordt vercijferd met Vigenère tot
ESMIW ZYGRL MWKTL FCQEW NXKNP YIOOM MWRQL VFSIP JSKQE
Achterhaal het sleutelwoord. Leg duidelijk uit hoe je dit hebt aangepakt. Maak gebruik van deVigenère tabel. 

Vigenère tabel

Men heeft lang gedacht dat het Vigenère systeem niet te kraken was tot in 1863 de Pruisische legerofficier Friedrich Kasiski een methode ontwikkelde om de sleutellengte te achterhalen. Als je de sleutellengte kent kun je de letters die met hetzelfde schuifsysteem vercijferd zijn eruit lichten, daar een frequentieanalyse op toepassen en zo de sleutel achterhalen. De Britse wiskundige Charles Babbage had enkele jaren eerder dezelfde methode ontwikkeld, maar had dit niet gepubliceerd.

Het achterhalen van de sleutellengte kan op verschillende manieren. We bekijken eerst een andere methode en de methode van Babbage en Kasiski bespreken we in les 5.
De frequentieanalyse berust op het principe dat in een taal bepaalde letters vaker voorkomen.
De eerste letter van de cijfertekst kan in principe elke letter van het alfabet zijn. Het hangt af van de vraag wat de eerste letter van de klare tekst en de eerste letter van het codewoord is. Hetzelfde geldt voor de tweede letter van de cijfertekst.

Laten we de eerste vijf letters nemen van een cijfertekst die in het voorbeeld 'chinese eetstokjes' verder wordt gebruikt: DSOEU

De eerste letter van het codewoord is een D. Dit is bepaald door de eerste letter van de klare tekst en de eerste letter van het codewoord. De tweede letter van het codewoord is een S en had net zo goed ook een D kunnen zijn. Dit is bepaald door de tweede letter van het codewoord en de tweede letter van de klare tekst. Het codewoord zal van invloed zijn op de vraag welke cijferletters er worden gevormd. Als het codewoord vijf verschillende letters heeft zullen de 19% E's in de klare tekst op vijf verschillende manieren worden versleuteld. De hoge frequentie van de E's wordt daardoor gespreid over vijf cijferletters. En deze cijferletters ontstaan ook nog uit andere combinaties: de letter E wordt door de codeletter P vercijferd als een T (want E is 4, P is 15 en T is 19). De letter L wordt door de codeletter I óók vercijferd als een T (want L is 11, I is 8 en T is 19). 
Eenzelfde redenatie geldt voor alle andere letters waardoor de frequenties van de letters op meerdere manieren worden verdeeld over de cijferletters en de frequenties van de cijferletters minder zullen verschillen dan in de klare tekst. Het maakt wel duidelijk dat het belangrijk is een codewoord uit verschillende letters te kiezen en ook nog willekeurig bepaald.

De gebeurtenis dat de eerste en de tweede letter hetzelfde zijn hangt af van het codewoord en de letters van de klare tekst, maar is onvoorspelbaar. Als alle cijferletters dezelfde frequentie hebben is de kans daarop is 1/26 of 0,038 (3,8%). We verwachten daarom dat 1 op de zesentwintig codeletters hetzelfde zal zijn als de volgende letter. Voor een cijfertekst van bijvoorbeeld 330 letters levert dat 12 of 13 overeenkomsten op. 
Hetzelfde gebeurt als we de cijfertekst verder opschuiven onder de originele cijfertekst, maar als we de letter D verder doorschuiven dan zal het ooit een keer voorkomen dat hij terechtkomt onder een letter die ook versleuteld is volgens hetzelfde schuifsysteem. Om precies te zijn duurt dat net zo lang als de lengte van het sleutelwoord. 
De kans dat de letters dan hetzelfde zijn hangt alleen af van de vraag wat de klare letter is: 
6,72% van de letters in de klare tekst is een a. De kans dat een a weer onder een a terechtkomt is 6,72%.
0,11% van de letters in de klare tekst is een x. De kans dat een x weer onder een x terechtkomt is 0,11%. 
De kans dat een e onder een terechtkomt is maar liefst 19,06%.

 
 

Doordenker

De kans dat een a weer onder een a terecht komt is 6,72%, 

de kans dat een x onder een x terechtkomt is slechts 0,11%, 
maar de kans dat een e onder een terechtkomt is maar liefst 19,06%. 
Bovendien komt het veel vaker voor dat de letter die verschoven wordt een is, namelijk in 19,06% van de gevallen, 
terwijl het maar zelden voorkomt dat het een x is die verschoven wordt, namelijk in 0,11% van de gevallen.

Waarom is dat zo?

klik hier

 

Opgave 4

a) Laat met behulp van de letterfrequentietabel uit les 3 zien dat de kans dat twee willekeurige letters in een Nederlandse tekst hetzelfde zijn ongeveer gelijk is aan 0,077.
b) In een cijfertekst die vercijferd is met een willekeurig sleutelwoord van 6 letters, dat dus geen bestaand woord hoeft te zijn en meerdere keren dezelfde letter mag bevatten, bekijken we twee letters die niet op 6, 12, 18, ... plaatsen uit elkaar liggen. Wat is de kans dat deze twee letters hetzelfde zijn?
c) Leg uit waarom de kans op twee dezelfde letters groter is als de letters een veelvoud van de sleutellengte uit elkaar staan.

Als je in Vigenère een sleutelwoord hebt van bijv. 6 letters, dan zijn in de cijfertekst de letters op plaats 1, 7, 13, 19, ... met dezelfde sleutel vercijferd. Volgens opgave 4 is de kans dat de letters hetzelfde zijn wanneer je 6, 12, 18, 24, ... plaatsen verschuift ruim 2x zo groot (7,7%) als bij andere verschuivingen. 
Hetzelfde geldt voor de letters op plaats 2, 8, 14, 20, ... en voor de letters op plaats 3, 9, 15, 21, ... want ook deze zijn met dezelfde sleutel vercijferd. 
IOnder het kopje 'Chinese eetstokjes' verder op deze pagina staat een uitgewerkt voorbeeld, waarin je duidelijk kunt zien dat het verschil opvallend is wanneer je een tekst telkens een letter opschuift en vergelijkt met de oude tekst. 

Het resultaat van het onderzoek op de pagina 'Chinese eetstokjes' zie je terug in opgave 5:

 

Opgave 5

Het resultaat van het onderzoek naar de chinese eetstokjes:

 

Aantal posities verschoven  1
Aantal overeenkomsten 10  22  11  11 12 22 

Je ziet dat de overeenkomsten groter zijn bij 4 posities verschoven en bij 8 posities verschoven.
Welke sleutellengte denk je dat de sleutel heeft die voor de vercijfering in het voorbeeld gebruikt is? Waarom?

Opgave 6 

Zoals je gezien hebt, is er een manier om de sleutellengte te achterhalen.
Hoe kun je de sleutel kiezen als je toch Vigenère zou willen gebruiken en een niet al te groot risico wilt lopen dat je bericht ontcijferd wordt?

Chinese eetstokjes

De volgende tekst over belasting op wegwerpeetstokjes in China is vercijferd met Vigenère:
DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE TKRVF HLREV LRCPH PCGWM PUJIJ SYIPC SIGBD EPHDP DWMDQ BGITS SVQRX GVSQS PRHVF WHTTC GYEHH RXOOP GBGIK BFLKB DENCP ZGFWI ISQAQ CUHKR JIYSJ AGFSI GHVXQ YMIUR HFGZD WVWQK KGHVQ DJITW FLVAH RUSQQ KZLIW PHAWG WITCP XGZDX GBJEC BPIVG FLCOU WGUUS PRVXQ TIIPN RENGK SWHLR EVLRC KRVFH MECFO MLYVX YSHQK ZMSGB NYDWH OGAHX GFKSW HWSVS HXUGW SMXHW XSUAG FNX

We gaan nu proberen de sleutellengte te achterhalen. Als voorbeeld laten we voor een deel van de eerste regel zien hoe je te werk gaat. Dit laten zien voor de hele tekst kost te veel tijd en voegt niets toe. De uitkomst van analyse op de hele tekst is te zien in de tabel onderaan die we door het rekenblad laten uitrekenen. Hoe je dit zelf kunt onderzoeken met gebruik van Excel wordt toegelicht in het volgende filmpje.

Onder de cijfertekst schrijf je de cijfertekst nog een keer op. Je verschuift de onderste tekst één plaats naar rechts en telt hoe vaak dezelfde letters boven elkaar staan. Dan verschuif je de onderste tekst nog een plaats naar rechts en telt weer hoe vaak dezelfde letters boven elkaar staan, enz. Al deze uitkomsten van het tellen houd je bij in een tabel. Wanneer het aantal plaatsen dat de onderste tekst verschoven is een veelvoud van de sleutellengte is, zal het aantal keer dat dezelfde letters boven elkaar staan groter zijn.

We lichten het toe met een voorbeeld door een deel van de tekst te verschuiven. 
In de tabel staat uiteindelijk het resultaat wanneer je dit toepast op de gehele tekst.

DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE
*DSOE UHLRI CSIGH VXQYM IUGLR FGHIP OSVKZ GMVXD
1 positie verschoven, 0 overeenkomsten.
DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE 
**DSO EUHLR ICSIG HVXQY MIUGL RFGHI POSVK ZGMVX
2 posities verschoven, 0 overeenkomsten. 
DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE 
***DS OEUHL RICSI GHVXQ YMIUG LRFGH IPOSV KZGMV
3 posities verschoven, 1 overeenkomst. 
DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE 
****D SOEUH LRICS IGHVX QYMIU GLRFG HIPOS VKZGM
4 posities verschoven, 1 overeenkomst.
DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE
***** DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG 
5 posities verschoven, 1 overeenkomst. 
DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE 
***** *DSOE UHLRI CSIGH VXQYM IUGLR FGHIP OSVKZ 
6 posities verschoven, 0 overeenkomsten.
DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE 
***** **DSO EUHLR ICSIG HVXQY MIUGL RFGHI POSVK 
7 posities verschoven, 0 overeenkomsten.
DSOEU HLRIC SIGHV XQYMI UGLRF GHIPO SVKZG MVXDE 
***** ***DS OEUHL RICSI GHVXQ YMIUG LRFGH IPOSV
8 posities verschoven, 2 overeenkomsten.

Gaan we nu de hele tekst vergelijken met de verschoven tekst, dan vinden we de resultaten met gebruik van een werkblad, die in onderstaande tabel staan.

werkblad

 
Aantal posities verschoven  1
Aantal overeenkomsten 10  22  11  11 12 22 

Je ziet dat de overeenkomsten groter zijn bij 4 posities verschoven en bij 8 posities verschoven.

Activiteit

Ga nu verder met opgave 5 boven op deze pagina.