Laatst ben ik mij gaan interesseren voor de Zodiac Killer. Het verhaal is dat een moordenaar gecodeerde berichten naar de politie stuurde. Een eerste brief is snel ontcijferd, maar een latere lange brief is nooit ontcijferd. Dit soort puzzels heeft altijd een bepaalde aantrekkingskracht. Bovendien is het een mooi excuus om een beetje met C# te spelen, wat te verdiepen in encryptie en gewoon leuk te puzzelen. Het nadeel is dat alle moeite waarschijnlijk voor niks is.

Het eerste bericht dat ontcijferd werd bleek een monoalfabetische encrypte bericht te zijn. Iedere letter werd vervangen door een ander teken. Hier kom je redelijk snel op een spoor doordat het meest voorkomende teken waarschijnlijk vervangen moet worden door een 'e'. Dit bericht heeft echter veel meer verschillende tekens. Het is dus maar zeer de vraag of er genoeg informatie is om een bericht te reconstrueren. Wat ook niet helpt is dat er gecodeerde berichten zijn met bijvoorbeeld 10 tekens wat de naam van de moordenaar moet zijn. Dit kan natuurlijk van alles zijn. Dus er is een behoorlijke kans dat de brief een pesterij is.

Voordat we deze tekst gaan analyseren is het handig een analyse te maken van de Engelse taal.

1. Frequentie analyse van letters.

De frequentie analyse van letters is de meest eenvoudige vorm van analyse. Voor een Engelse brief is het mogelijk een voorspelling te maken hoe vaak een bepaalde letter voorkomt. Hiervoor heb ik een Engels boek genomen, Oliver Twist van Charles Dickens. De letters in volgorde van frequentie zijn:

De vraag is nu hoe dit geïnterpreteerd dient te worden. In een brief van 340 tekens kan een grote afwijking voorkomen ten opzichte van deze frequenties. Iedere letter vertegenwoordigt een frequentie van 0.3%. Meer dan een hele grove schatting levert dit dus niet op.

Een extreem voorbeeld hoe een concrete tekst kan afwijken van een gemiddelde is de roman La Disparution, geschreven door Georges Perec in 1969. In de gehele roman komt de letter 'e' niet voor. Wat het nog bijzonderder maakt is dat deze roman vertaald is naar meerdere andere talen. Iedere keer word de meest voorkomende letter in die taal weggelaten. Het leek mij onmogelijk dat het in het Nederlands vertaald zou kunnen worden. Vooral omdat alle Nederlandse lidwoorden een 'e' bevatten. Het blijkt toch vertaald te zijn: 't_Manco. Dit is ook een manier om geen 'e' te gebruiken.

2. Frequentie analyse van digrammen.

Om nog meer informatie te gebruiken kan het nuttig zijn om te kijken naar digrammen, 2 opeenvolgende letters. Op het internet kun je verschillende tabellen vinden van digrammen in het Engels. Wat opvalt is dat er veel verschillende frequentietabellen te vinden zijn. De methodiek om digrammen te berekenen kan van invloed zijn. Bijvoorbeeld de frequentietabel uit Modern Cryptanalysis :

Deze tabel is gemaakt met het complete werk van Shakespear. Is het mogelijk om deze tabel te reproduceren met behulp van Oliver Twist? Een mogelijkheid is om alle unieke woorden uit de roman te analyseren op digrammen. Dit komt min of meer overeen met alle digrammen uit een woordenboek te berekenen. Alhoewel in dit geval sommige obscure woorden zullen ontbreken. Dit geeft de volgende frequentietabel:

Deze tabel lijkt niet op de voorgaande tabel. Hoofdoorzaak voor het verschil is dat veel voorkomende woorden zoals 'the', met digrammen 'th' en 'he', maar een keer geteld word. Een andere methode is eigenlijk veel eenvoudiger, namelijk de digrammen van alle woorden berekenen. Dit geeft de volgende frequentietabel:

Dit is wat gebruikt is in Modern Cryptanalysis. Er is blijkbaar een behoorlijk verschil tussen Shakespear en Charles Dickens. In Modern Cryptanalysis staat later de waarschuwing dat deze tabel niet de digrammen tussen woorden meeneemt. Dat maakt dit niet de meest handige tabel. In het gecodeerde bericht zijn immers alle woorden aan elkaar geplakt. Alle digrammen van de laatste letter van een woord met de eerste letter van het volgende woord ontbreken. Als de gehele tekst aan elkaar geplakt word, met weglating van all speciale karakters, dan ontstaat de volgende frequentietabel:

Zolang het onbekend is waar woorden beginnen en ophouden, is deze tabel die het bruikbaarst voor de analyse van de tekst.

3. Frequentie analyse van trigrammen.

Een soortgelijk idee is  een frequentieanalyse van trigrammen. Zoals hierboven aangegeven, zal ik deze tabel berekenen door de gehele tekst aan elkaar te plakken. De gevonden frequentietabel is:

Hierbij treed een merkwaardig effect op. Stel we gokken drie opeenvolgende letters. Om te bepalen of onze gok waarschijnlijk was kijken we in de frequentietabel van trigrammen. In deze tabel is de frequentie zeer laag. Een conclusie zou kunnen zijn dat onze gok zeer onwaarschijnlijk was, maar dit is onterecht. Wat er namelijk gebeurt is dat er veel meer trigrammen zijn dan er in de brief voor zouden kunnen komen. Er zijn 17576 mogelijke trigrammen (26x26x26), maar er kunnen er maar 338 in deze brief voorkomen.  Aangezien de som toch 100% is, lijken de in de tekst voorkomende trigrammen altijd oververtegenwoordigd. Anders gezegd, de frequentie van niet voorkomende trigrammen worden opgeteld bij de frequenties van de aanwezige trigrammen.

4. Woordenlijsten.

Een laatste belangrijke analyse bron is het gebruik van woordenlijsten. Woordenlijsten kunnen zeer nuttig zijn om te bepalen waar woorden beginnen en eindigen. Bijvoorbeeld de letter combinatie 'ngp' wijst op een woord dat eindigt op 'ng' gevolgd door een woord dat begint met een 'p'. Het gevaarlijke van een woordenlijst is dat namen ontbreken. Een van de verdachten heet Gakoiwski. Die naam bevat meerdere letter combinaties die onwaarschijnlijk zijn in een Engels woord.