Tijdens de zomer van 1940 eiste Duitsland toegang tot de Zweedse telefoonkabels om gecodeerde berichten te versturen vanuit het bezette Noorwegen naar het thuisland. Zweden kon niet anders dan toegeven, maar begon meteen de lijnen af te luisteren. Al snel ontdekten ze dat er een nieuw cryptografisch systeem gebruikt werd. De T52 Geheimschreiber (of kortweg G-schreiber) — een machine met meer dan 8 biljard verschillende instellingen — verzond geheime informatie die maar niet gekraakt leek te kunnen worden.

De Zweedse inlichtingendiensten gaven wiskundige Arne Beurling opdracht om de code te kraken op basis van slechts een handvol gecodeerde berichten en zonder enige voorkennis over het mechanisme dat gebruikt was bij het coderen. Na twee weken puzzelen met enkel potlood en papier, slaagde Beurling erin de berichten te ontcijferen. Hij kon ook beschrijven hoe ze een complementaire machine konden bouwen om berichten te decoderen.

Dankzij deze doorbraak konden Zweedse ambtenaren berichten onderscheppen waarin sprake was van een nakende invasie van de Sovjet-Unie. Helaas sloeg het personeel van Stalin hun waarschuwingen in de wind. Het boek The Codebreakers¹ van Bengt Beckman brengt relaas van het hele verhaal. In zijn voorwoord voor het boek schrijft Peter Jones:

Tot op heden weet niemand welke redenering Beurling maakte tijdens die twee weken dat hij zijn zinnen zette op de G-schreiber. In 1976 werd hij door een afdeling van het Zweedse leger ondervraagd, en raakte daarbij zeer geïrriteerd toen ze hem onder druk zetten om zijn werkmethode uit de doeken te doen. Uiteindelijk antwoordde hij: "Een goochelaar legt toch ook niet uit hoe zijn trucs werken." Het lijkt erop dat de enige aanwijzing die Beurling ooit gaf, verscholen zat in de cryptische (of wat had je gedacht) opmerking dat drieën en vijven belangrijk waren.

Opgave

Uiteindelijk bleek de procedure die de T52 Geheimschreiber gebruikte helemaal niet zo ingewikkeld. Er wordt gewerkt met een alfabet van $$m$$ symbolen die allemaal verschillend zijn en een vaste volgorde hebben. De posities van de symbolen in het alfabet worden genummerd van 0 tot en met $$m - 1$$.

De sleutel die gebruikt wordt voor het coderen en decoderen bestaat verder uit twee natuurlijke getallen $$a$$ en $$b$$. Elk symbool op positie $$x$$ in het alfabet wordt gecodeerd als het symbool op positie $$C(x)$$ in het alfabet, waarbij \[C(x) = (ax + b)\ \textrm{mod}\ m \qquad (0 \leq x < m)\] en de operator $$\textrm{mod}$$ geeft de rest na gehele deling. Elk symbool op positie $$x$$ in het alfabet wordt gedecodeerd als het symbool op positie $$D(x)$$ in het alfabet, waarbij \[D(x) = a'(x - b)\ \textrm{mod}\ m \qquad (0 \leq x < m)\] en $$a'$$ staat voor de multiplicatieve inverse van $$a$$ modulo $$m$$. Met andere woorden, $$a'$$ is het natuurlijk getal uit het interval $$[0, m[$$ waarvoor geldt dat \[1 = aa'\ \textrm{mod}\ m\] De multiplicatieve inverse van $$a$$ bestaat enkel als $$a$$ en $$m$$ copriem zijn. Dat is het geval als de grootste gemene deler van $$a$$ en $$m$$ gelijk is aan 1. In dat geval bestaat er ook maar één getal in het interval $$[0, m[$$ dat voldoet aan de voorwaarde van de multiplicatieve inverse.

Toen de Duitsers hoogte begonnen te krijgen van het feit dat de gecodeerde berichten van de T52 makkelijk te kraken waren, probeerden ze die nog complexer te maken. Ze deden dat door een bericht niet één maar twee keer te coderen. Een eerste keer door een T52 met sleutels $$a_1$$ en $$b_1$$ en een tweede keer door een T52 met sleutels $$a_2$$ en $$b_2$$. Dit kan enkel als de twee machines hetzelfde alfabet gebruiken. Uit de vaststelling dat \[C_2(C_1(x)) = (a_2((a_1x + b_1)\ \textrm{mod}\ m) + b_2)\ \textrm{mod}\ m = (a_1a_2x + (a_2b_1 + b_2))\ \textrm{mod}\ m\] volgt echter dat dit dezelfde codering is als deze die gemaakt wordt door één enkele T52 met sleutels $$a_1a_2$$ en $$(a_2b_1 + b_2)$$.

Definieer een klasse T52 om machines voor te stellen waarmee berichten kunnen gecodeerd en gedecodeerd worden volgens de Geheimschreiber codering. Bij het aanmaken van een nieuwe machine (T52) moeten drie argumenten doorgegeven worden: twee natuurlijke getallen $$a$$ en $$b$$ (int) en een alfabet (str) met $$m$$ karakters. Als $$a$$ en $$m$$ niet copriem zijn, dan moet een AssertionError opgeworpen worden met de boodschap a en m zijn niet copriem, waarbij de cursieve fragmenten moeten ingevuld worden met de waarden van $$a$$ en $$m$$. Als niet alle karakters van het alfabet verschillend zijn, dan moet een AssertionError opgeworpen worden met de boodschap alfabet bevat herhaalde symbolen.

Op een machine $$m$$ (T52) moet je minstens de volgende methoden kunnen aanroepen:

• Een methode codeer_symbool waaraan één karakter (str) moet doorgegeven worden. Als het karakter voorkomt in het alfabet van machine $$m$$, dan moet het gecodeerde karakter (str) teruggegeven worden. Anders moet het gegeven karakter (str) zelf teruggegeven worden.

• Een methode decodeer_symbool waaraan één karakter (str) moet doorgegeven worden. Als het karakter voorkomt in het alfabet van machine $$m$$, dan moet het gedecodeerde karakter (str) teruggeven. Anders moet het gegeven karakter (str) zelf teruggegeven worden.

• Een methode codeer waaraan een klare tekst $$t$$ (str) moet doorgegeven worden. De methode moet de corresponderende cijfertekst (str) teruggeven: de tekst $$t$$ waarin alle karakters die voorkomen in het alfabet van machine $$m$$ vervangen werden door hun gecodeerde karakter. Alle karakters die niet voorkomen in het alfabet van machine $$m$$ moeten behouden blijven.

• Een methode decodeer waaraan een cijfertekst $$t$$ (str) moet doorgegeven worden. De methode moet de corresponderende klare tekst (str) teruggeven: de tekst $$t$$ waarin alle karakters die voorkomen in het alfabet van machine $$m$$ vervangen werden door hun gedecodeerde karakter. Alle karakters die niet voorkomen in het alfabet van machine $$m$$ moeten behouden blijven.

Zorg ervoor dat som (+) van twee machines $$m_1$$ en $$m_2$$ (T52) een nieuwe machine (T52) oplevert die werkt alsof we eerst berichten zouden coderen met machine $$m_1$$ en het resultaat daarna nog eens zouden coderen met machine $$m_2$$. Als machines $$m_1$$ en $$m_2$$ niet hetzelfde alfabet gebruiken, dan moet een AssertionError opgeworpen worden met de boodschap alfabetten zijn verschillend.

Voorbeeld

>>> machine1 = T52(3, 5, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')

>>> machine1.codeer_symbool('G')
'X'
>>> machine1.codeer_symbool('S')
'H'
>>> machine1.codeer_symbool('-')
'-'

>>> machine1.decodeer_symbool('X')
'G'
>>> machine1.decodeer_symbool('H')
'S'
>>> machine1.decodeer_symbool('-')
'-'

>>> machine1.codeer('G-SCHREIBER')
'X-HLAERDIRE'
>>> machine1.decodeer('X-HLAERDIRE')
'G-SCHREIBER'

>>> machine2 = T52(17, 11, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')
>>> machine2.codeer('X-HLAERDIRE')
'M-AQLBOKROB'

>>> machine12 = machine1 + machine2
>>> machine12.codeer('G-SCHREIBER')
'M-AQLBOKROB'

>>> T52(4, 5, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')
Traceback (most recent call last):
AssertionError: 4 en 26 zijn niet copriem

>>> T52(3, 5, 'ABCDEFGHIJKLMMLKJIHGFEDCBA')
Traceback (most recent call last):
AssertionError: alfabet bevat herhaalde symbolen

>>> machine1 + T52(17, 11, 'abcdefghijklmnopqrstuvwxyz')
Traceback (most recent call last):
AssertionError: alfabetten zijn verschillend