De Econometrist

De Econometrist neemt een statistische kijk op de wereld.

Geschiedenis Statistiek

Enigma: een gigantisch Enigma

Bij een enigma denkt men al vrij snel aan een moeilijk raadsel waar je even voor moet gaan zitten. Met de komst van de film The Imitation Game eind 2014 werd ineens ook een andere betekenis van het woord bij het grote publiek bekend, namelijk die van de Enigma als elektromechanische codeermachine uit de Tweede Wereldoorlog, zoals die gebruikt werd door de Duitsers.

Historie

De eigenlijke definitie van de Enigma als codeermachine beslaat een breder begrip dan alleen het apparaat dat door de Duitsers gebruikt werd tijdens de Tweede Wereldoorlog. Het eerste apparaat dat Enigma werd genoemd, kwam uit 1918 en werd gepatenteerd door de Duitse ingenieur Arthur Scherbius. Het apparaat, de Enigma A, maakte gebruik van rotoren om berichten te versleutelen, waarbij de rotoren steeds een slag doordraaien, en eenzelfde letter dus steeds anders versleuteld wordt, afhankelijk van de stand van de rotoren. Het initiële apparaat was te groot en zwaar om in de praktijk gebruikt te worden. Dit resulteerde erin dat de Enigma A werd opgevolgd door de Enigma’s B, C en D, allen geproduceerd door het bedrijf van Scherbius, Chiffriermaschinen-AG.

De Enigma D was een lichtere en commerciëlere versie van zijn voorgangers en deze werd gebruikt door Italië en Spanje.  Zwitserland en Japan gebruikten aangepaste versies van deze Enigma D. Uiteindelijk werden al deze Enigma’s al redelijk snel gekraakt. In 1932 paste het Duitse leger de Enigma D aan tot een versie die uiteindelijk Wehrmacht Enigma genoemd werd. Het stekkerbord werd toegevoegd. Deze Enigma had eerst drie,maar vanaf 1939 vijf rotoren. Deze versie werd gebruikt door de luchtmacht, grondtroepen en door veel andere overheidsaangelegenheden. Ondertussen trok de Duitse marine haar eigen plan en deze ontwikkelde in 1934 een eigen Enigma, voorzien van acht rotoren, waarvan er drie tegelijkertijd gebruikt konden worden. De overige vijf waren voor speciale gelegenheden. Dit apparaat heette de Funkschlüssel M3 of Enigma M3. In 1941 werd, ondanks verzekeringen van de Duitsers dat de M3 onbreekbaar was, deze M3 vervangen door de M4 op aandringen van de Duitse admiraal Karl Donitz. De M4 gebruikte vier rotoren tegelijkertijd.

Bron: D. Rijmenants - http://users.telenet.be/d.rijmenants
De Kriegsmarine M4

Werking

Om een idee te krijgen van de werking van de Enigma, moet men onderscheid maken tussen vier delen:

  • Het toetsenbord: Deze werd gebruikt om de te coderen boodschap in te toetsen. Een druk op een toets sluit een elektrisch circuit.
  • Lampenbord: Een bord met lampjes, geplaatst boven het toetsenbord. Ieder lampje werd gemarkeerd met een letter. Wanneer er een toets op het toetsenbord ingedrukt wordt, geeft het lampbord de gecodeerde letter weer.
  • Rotoren en reflector  een Enigma bevatte 3 of 4 rotoren en een reflector. Iedere rotor bevatte 26 contactpuntjes aan beide zijden, die de rotoren met elkaar, de reflector en het toetsen/stekkerbord verbindt. De reflector bevatte aan een zijde 26 contactpuntjes,  en deze bevatte een interne bedrading die ieder contactpuntje met een ander verbond. Voor de rotoren gold dat de interne bedrading kon draaien ten opzichte van de letters op de buitenkant.
  • Stekkerbord: deze gaf de optie om twee letters onderling met elkaar te verbinden. Als bijvoorbeeld de ‘a’ en de ‘s’ verbonden waren, werd de ‘a’ gecodeerd door de letter waar anders de ‘s’ door gecodeerd zou worden.
De interne bedrading van de Enigma
Een versimpeld schema van de werking van de Enigma

De figuur hierboven geeft een versimpeld schema weer van hoe de Enigma werkt, met alleen de letters ‘a’, ‘s’, ‘d’ en ‘f’. Wanneer de letter ‘a’ ingedrukt wordt (2), loopt er een stroom vanaf de bron (1). De stroom loopt door het stekkerbord (3), waar deze omgeleid zou worden naar een andere letter als de ‘a’ verbonden was met een andere letter, in dit geval is dat niet zo. De stroom loopt vervolgens naar de ingangsstator(4), deze bevat enerzijds de draden afkomstig van het stekkerbord, anderzijds 26 contactpuntjes, die in contact staan met de rotoren (5). Naar welk contactpunt van de eerste rotor de stroom geleid wordt, ligt aan de stand van eerste rotor. Naar welk contactpunt van de tweede rotor de eerste rotor de stroom leidt, ligt aan de interne bedrading van de eerste rotor en de stand van de tweede rotor. Dit gaat zo door tot de laatste rotor, waarna de stroom via de reflector (6) terug gezonden wordt naar de laatste rotor, waarbij de interne bedrading van de reflector bepaalt door welk contactpunt van de laatste rotor de stroom terug gaat. De stroom gaat via de rotoren en de ingangsstator terug naar het stekkerbord (7). Hier blijkt dat, in ons geval, we bij de ‘s’ zijn aanbeland. De ‘s’ is op zijn beurt verbonden met de ‘d’ via het stekkerbord. Dit betekent dat de ‘a’ gecodeerd wordt door de ‘d’ in plaats van de ‘s’.  De stroom loopt vanaf het stekkerbord terug naar het toetsenbord, waar de toets ‘d’ niet ingedrukt is en de stroom dus door kan lopen naar het lampje voor de ‘d’. Het circuit is gesloten en het lampje dat bij de letter ‘d’ hoort, brand. Als we ervoor hadden gekozen de ‘d’ in te drukken, dan zou het lampje van de ‘a’ oplichten.

Wanneer een toets in is gedrukt, en deze vervolgens weer wordt losgelaten, draait de meest rechter rotor een slag door. Na 25 toetsaanslagen staat de rechter rotor dus op de positie voor zijn initiële positie. Bij de volgende toetsaanslag draait de tweede rotor van rechts dan óók een slag door. Wanneer de tweede rotor van rechts 26 slagen heeft gemaakt, draait de derde rotor van rechts een slag door. Dit werkt hetzelfde voor een eventuele vierde rotor.

Doordat bij een gelijke instelling van de rotoren twee letters voor elkaar coderen, hoeft iemand die een bericht codeert met een enigma alleen van te voren af stemmen met de ontvanger dat ze beiden de initiële instelling van de rotoren kennen en weten welke letters onderling verbonden zijn via het schakelbord. Daarnaast moeten ze beiden een enigma gebruiken waarvan de interne bedrading van de rotoren en de reflector hetzelfde is. Voor belangrijke berichten volgden de Duitsers soms andere procedures. Dan werden rotoren of reflectoren met een andere interne bedrading dan gebruikelijk gebruikt.  De Duitsers hadden codeboekjes die iedere dag een andere code voorschreven.

 

Het kraken van de Enigma

Het kraken van de Enigma begon in Polen. De wiskundigen Marian Rejewski, Henryk Zygalski en Jerzy Rozicki van het Poolse cijfer bureau ‘Biuro Szyfrów’, geloofden als een van de weinigen dat de Enigma gekraakt kon worden met analytische methoden. Ze ontwikkelden een machine die de Bomba heette, een elektromechanisch apparaat dat gebruik maakte van de gebrekkige codeerprocedures van de Duitsers. Tot 1939 maakten de Duitsers de fout dat ze ieder bericht begonnen met twee keer de letters van de sleutel van de dag. De Duitsers deden dit om fouten te voorkomen. De Polen wisten nu dus twee verschillende versleutelde berichten voor de sleutel, bij opeenvolgende rotorstanden. De Bomba die zij ontwikkeld hadden, maakte hier van gebruik en kon zo binnen twee uur de sleutel achterhalen. In 1939 werd het voor de Polen onmogelijk om verder te gaan met het kraken van de Enigma door betere procedures van de Duitsers. Voordat de oorlog in Polen uitbrak, deelden zij de informatie die zij vergaard hadden over het kraken van de Enigma met Franse en Britse veiligheidsdiensten.

Bletchley Park

De informatie die de Polen aan de Britten gaven, gaf ze het vertrouwen om zelf ook een poging te wagen de ‘onkraakbare’ Enigma te kraken. Bletchley Park, bij Milton Keynes, werd het thuis van de United Kingdom’s Government Code and Cipher School (GC&CS).  Hier werkten onder anderen de wiskundigen Alan Turing and Gordon Welchman. Het personeel van Bletchley Park bestond niet alleen uit wiskundigen; ook schaakgrootmeesters en kruiswoordpuzzelaars werden benaderd om te helpen. De werving van personeel ging zelfs zo ver dat in 1941 The Daily Telegraph gevraagd werd om een kruiswoordpuzzelwedstrijd te organiseren, waarna deelnemers die goed scoorden benaderd werden om ‘een bijdrage te leveren aan de oorlog’.

Bij goed gebruik, dat wil zeggen goede gebruiksvoorschriften, is de Enigma onkraakbaar. De Polen waren er in geslaagd de Enigma te kraken, door gebruik te maken van de fout die de Duitsers maakten door de sleutel twee maal te coderen aan het begin van ieder bericht. De Duitsers schreven in 1939 betere procedures en er kon geen gebruik meer worden gemaakt van deze fout. In Bletchley Park werd een andere fout ontdekt. Namelijk dat veel berichten hetzelfde waren. Dit waren standaard berichten die een Duitse U-Boot dagelijks verzond, zoals “Keine besondere Ereignisse” –  hetgeen “geen bijzondere gebeurtenissen” betekent. Andere veel voorkomende groepen woorden waren “An der Oberbefehlshaber” of  “Es Lebe Den Führer“.  Dit waren zogenaamde cribs.

Het vinden van een crib kon lastig zijn. De Engelsen gebruikten onder anderen dat een letter nooit met zichzelf gecodeerd kon worden. De tekst  “lejzi drofgrlmj dijofeljsd” kon dus geen crib zijn met “keinebesondereereignisse” omdat de ‘e’ in beide stukken op positie 2 staat. Een crib werd dus gevonden door het fragment waarvan verwacht wordt dat het in het bericht zit, “keine besondere erignisse”, langs de gecodeerde tekst te halen totdat er geen letters meer overeen kwamen. Dit leverde vaak meerdere mogelijkheden op.

Maar hoe kon dit vervolgens een oplossing geven? Het aantal mogelijk initiële instellingen van Enigma was, bij drie rotoren, 10^{23}. Het stekkerbord leverde een bijdrage van 1,5 * 10^{14}, het aantal startposities van de rotoren was 26^{3} = 17576. Bij vijf rotoren waarvan er drie gebruikt werden, waren er zestig mogelijke combinaties.  Bij instelbare interne bedrading van de rotoren gaf dit nog eens 26^{2} = 676 opties (slechts 2 van de 3 rotoren hadden instelbare bedrading). Voor een afleiding van deze getallen verwijs ik naar The Cryptographic Mathematics of enigma. NSA, 2001.

Een crib van 26 letters kan gedeeld worden door twee stukken van elk 13 letters, waarbij een van de delen zo gecodeerd is dat de tweede rotor en derde geen slag is doorgedraaid tijdens het coderen. Hierdoor verandert de positie van de interne bedrading niet, dit scheelt een factor 676. Turing ontdekte dat het stekkerbord en de stand van de rotoren los van elkaar gezien konden worden. Neem bijvoorbeeld de crib:

crib

Men weet dat, voor een signaal door de rotoren gaat, deze eerst verwisseld wordt door het stekkerbord. Een letter k wordt dus vervangen door \phi(k).  De relatie in de eerste kolom zegt dus dat de letter \phi(k) de letter phi(d) oplevert op positie 1. Op een zelfde manier is de versleuteling van \phi(d) op positie 10 gelijk aan \phi(n). Deze onderlinge relaties zijn voldoende om de stand van de rotoren uit te herleiden. Men zou dit kunnen vergelijken met een stelselvergelijking waarbij de variabelen in elkaar uit gedrukt worden. Hierdoor hoefde geen rekening meer gehouden te worden met het stekkerbord. En zo vielen er dus nog 1,5 * 10^{14} opties weg. Er blijven dan 60 * 17.526  = 1054560 opties over. Bovendien verschafte de onderlinge relaties tussen de versleutelde letters veel informatie over de mogelijke uitkomsten. Turing ontwikkelde de Bombe, dit apparaat doorliep in groot tempo alle resterende mogelijkheden. Meer onderlinge verbanden zorgden ervoor dat de bombe sneller tot een uitkomst kwam en minder vaak stopte bij een oplossing die verkeerd was. De stand van de stekkertjes op het stekkerbord kon eenvoudiger gevonden worden, bijvoorbeeld door frequentieanalyse.

Het was nu dus mogelijk voor de Britten om de Enigma te kraken. Dit betekende niet dat dit altijd lukte. Het was namelijk niet altijd mogelijk om een crib te vinden. Een ander probleem was de invoering van de D-reflector. Dit was een ander type reflector waarvan de Britten de interne bedrading niet kenden. Het invoeren van deze reflector bleek een logistieke nachtmerrie voor de Duitsers waardoor deze uiteindelijk slechts voor belangrijke berichten gebruikt werd. Doordat de Duitsers wel dezelfde sleutel gebruikten en deze achterhaald werd door een bericht dat met de B-reflector was gecodeerd was te kraken, konden de wiskundigen in Bletchley Park de interne bedrading van de D-reflector uiteindelijk wel afleiden.

Rotor en Reflector. Bron: D. Rijmenants - http://users.telenet.be/d.rijmenants
Rotor en Reflector.

Een tweede probleem was de plotse invoering van de Enigma M4, met 4 rotoren. Turing bedacht dat deze overschakeling ook erg lastig was voor de Duitsers vanuit logistiek oogpunt. Hij redeneerde dat de M4 een aangepaste versie van de M3 moest zijn en vond uit dat als de vierde rotor (van rechts) in positie A stond, deze net zo werkte als de M3. Doordat de vierde rotor slechts iedere 26^{3} slagen zou draaien, en berichten nooit zo lang werden, kon de vierde rotor samen met de reflector gezien worden als een reflector met 26 standen. Toch hadden de Britten de nodige moeite met de M4. Nieuwe bombes moesten ontworpen worden en er waren grote tekorten aan materialen overal in het Verenigd Koninkrijk. Hierop besloten de Britten haar kennis van de bombe te delen met de VS, de VS bouwden zelf een snellere en efficiëntere bombe. Na 1943 nam de VS het grootste deel van het code breken voor haar rekening. Geschat wordt dat de Tweede Wereldoorlog twee tot vier jaar langer had geduurd als de enigma nooit gekraakt was.

 Alan Turing

Alan Turing wordt tegenwoordig gezien als het brein achter de Enigma.  Na de oorlog werkte Turing in het National Physical Laboratory, waar hij een bijdrage leverde aan de eerste computers. In 1952 werd Turing veroordeeld voor homoseksualiteit, wat destijds nog strafbaar was in het Verenigd Koninkrijk. Turing mocht kiezen tussen chemische castratie of een gevangenisstraf. Hij koos chemische castratie. In 1954 overleed Turing, op 41-jarige leeftijd. In 2009 gaf, als gevolg van een internet campagne, de Britse Premier Gordon Brown een officiële verontschuldiging voor de manier waarop Turing is behandeld na de oorlog. In 2013 gaf koningin Elisabeth II hem een postuum pardon. Turing wordt gezien als een van de meest invloedrijke personen van de 20ste eeuw.


 Dit artikel is geschreven door Tim van Schaick.

timvanschaik


Deel dit artikel:

By Daniele Zedda • 18 February

← PREV POST

By Daniele Zedda • 18 February

NEXT POST → 34
Share on