Frequentieanalyse uitgelegd
Eeuwenlang was de beste manier om een bericht te verbergen elke letter van het alfabet te verwisselen voor een andere. Het aantal mogelijke sleutels is astronomisch, dus het cijfer leek onkraakbaar. Toch had een geleerde in Bagdad in de negende eeuw de zwakke plek al gevonden: een taal gebruikt sommige letters veel vaker dan andere, en geen enkele verwisseling verbergt dat. Frequentieanalyse maakte van codekraken een methode in plaats van giswerk, en het is nog altijd het eerste wat iedereen op een nieuw cijfer probeert.
Het substitutiecijfer
Een eenvoudig substitutiecijfer vervangt elke letter van het alfabet door een andere, volgens een vaste tabel: A wordt bijvoorbeeld Q, B wordt W, enzovoort, waarbij elke letter één keer wordt gebruikt. De tabel is de sleutel. Anders dan het caesarcijfer, dat het alfabet alleen verschuift en 25 sleutels heeft, kan het substitutiecijfer elke volgorde van de letters gebruiken: 26! sleutels, ongeveer 4 × 10²⁶. Zelfs een computer die een miljard sleutels per seconde test, zou meer dan tien miljard jaar nodig hebben om ze allemaal te proberen.
De ontdekking van al-Kindi
Rond het jaar 850 schreef de Arabische filosoof Abu Yusuf al-Kindi een verhandeling over het ontcijferen van geheime berichten, de oudste bekende beschrijving van frequentieanalyse. Zijn advies: neem een lange tekst in dezelfde taal, tel hoe vaak elke letter voorkomt, tel dan de letters van het geheime bericht en koppel ze aan elkaar, de vaakst voorkomende aan de vaakst voorkomende, de volgende aan de volgende. Geleerden die de Koran bestudeerden, telden al generaties lang letters en woorden, en misschien is het idee zo ontstaan.
Letters, paren en woorden
In het Engels is ongeveer 12,7% van de letters een E, 9% een T en 8% een A, terwijl Z minder dan één keer per duizend letters voorkomt. Losse tellingen wijzen alleen de goede richting aan, vooral in korte teksten, dus codekrakers gebruiken elk patroon dat ze kunnen vinden. Een woord van één letter is A of I. De meest voorkomende letterparen zijn TH, HE, IN en ER, en de meest voorkomende dubbele letters LL, EE, SS en OO. Op Q volgt bijna altijd U. Een veelvoorkomend woord van drie letters is waarschijnlijk THE, en zodra T, H en E bekend zijn, vallen woorden als THAT en THERE op hun plaats. Elke taal heeft haar eigen vingerafdruk: in het Duits en het Nederlands overheerst E nog sterker, terwijl in het Portugees A voorop gaat.
Het fatale cijfer van een koningin
In 1586 wisselde Maria Stuart, koningin van Schotland, die in Engeland gevangenzat, versleutelde brieven uit met Anthony Babington, die van plan was haar te bevrijden en koningin Elizabeth I te vermoorden. De brieven werden in biervaten naar buiten gesmokkeld, maar gingen door de handen van Elizabeths spionnenchef Francis Walsingham, wiens codekraker Thomas Phelippes het cijfer, een substitutie met enkele extra symbolen voor veelvoorkomende woorden, met frequentieanalyse kraakte. De ontsleutelde brieven bewezen Maria's aandeel in het complot, en ze werd in februari 1587 terechtgesteld.
De frequenties verbergen
Cijfermakers sloegen terug. Homofone cijfers gaven veelvoorkomende letters elk meerdere symbolen, zodat elk symbool ongeveer even vaak voorkwam. Nullen, betekenisloze symbolen, werden door de tekst gestrooid om de tellingen te verstoren. Het echte antwoord kwam met polyalfabetische cijfers zoals het vigenèrecijfer uit de 16e eeuw, die onderweg wisselen tussen verschillende alfabetten, zodat één klare letter veel verschillende geheimletters wordt. Het hield stand tot Charles Babbage en Friedrich Kasiski in de 19e eeuw lieten zien hoe je de lengte van de sleutel vindt en daarna frequentieanalyse op elk alfabet afzonderlijk toepast.
Hoe computers geheimschriften oplossen
Ook een programma kan niet elke sleutel proberen, maar het kan klimmen. Het begint bij een gok, beoordeelt het resultaat op hoeveel het op de taal lijkt, meestal op hoe gewoon de groepjes van twee tot vier letters zijn, en verwisselt dan letterparen in de sleutel, waarbij het elke verwisseling houdt die de score verhoogt. Als geen enkele verwisseling meer helpt, schudt het de sleutel door elkaar en begint het opnieuw te klimmen, waarbij het het beste resultaat bewaart. Deze methode, heuvelklimmen (hill climbing) genoemd, lost een substitutiecijfer van een paar honderd letters op in een fractie van een seconde, en varianten ervan hebben historische cijfers gekraakt die mensen eeuwenlang weerstonden.
Frequentieanalyse vandaag
Moderne cijfers zoals AES zijn zo ontworpen dat de cijfertekst er volkomen willekeurig uitziet: elke bytewaarde komt even vaak voor, en hetzelfde bericht wordt elke keer anders versleuteld. Frequentieanalyse heeft er geen vat op. Toch leeft het idee voort: taalstatistiek helpt herkennen wanneer een ontsleuteling klopt, de cijfers van puzzels en escaperooms te kraken en oude versleutelde brieven uit archieven te lezen. In 2023 werden eeuwenlang verloren gewaande brieven van Maria Stuart met hulp van de computer ontcijferd.
Ontdek het zelf
Open de frequentieanalyse-tool voor een versleutelde alinea in het Engels, Duits, Frans, Spaans, Italiaans, Portugees of Nederlands. Vergelijk in de grafiek de lettertellingen met de taal, gebruik de aanwijzingen van letterparen, dubbele letters en korte woorden, en vul de sleutel letter voor letter in. Hint en Controleren helpen als je vastzit, en de oplosser laat zien hoe heuvelklimmen het werk afmaakt.
Veelgestelde vragen
Waarom is E de meest voorkomende letter in het Engels?
Omdat de letter voorkomt in veel van de meest gebruikte Engelse woorden, zoals THE, BE, HE, WE en ARE, en in gangbare uitgangen als -ED en -ES. De meeste Europese talen delen dit: ook in het Frans, Duits, Nederlands en Spaans gaat E voorop.
Kan frequentieanalyse elk cijfer kraken?
Nee. Ze kraakt cijfers waarin elke klare letter altijd door hetzelfde symbool wordt vervangen. Cijfers die de vervanging onderweg veranderen, of moderne cijfers die met bits werken in plaats van met letters, vragen om andere methoden of zijn helemaal niet te kraken.
Wat is een geheimschriftpuzzel?
Een citaat of zin die met een eenvoudige substitutie is versleuteld en wordt afgedrukt zodat lezers hem met de hand kunnen oplossen; in het Engels heet zo'n puzzel een cryptogram. Ze verschijnen sinds de 19e eeuw in kranten en worden precies zo opgelost als de tool laat zien: begin met de korte woorden en de meest voorkomende letters.
Hoe zijn de verloren brieven van Maria Stuart ontcijferd?
In 2023 identificeerden George Lasry, Norbert Biermann en Satoshi Tomokiyo 57 versleutelde brieven in een Franse bibliotheek als de hare. Het cijfer gebruikte bijna 200 symbolen, dus combineerden ze heuvelklimmen met de computer, dat de waarschijnlijke betekenis van veel symbolen voorstelde, met zorgvuldig handwerk voor de rest.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Open de frequentieanalyse-tool