Tijdens de zomer van 1940 eiste Duitsland toegang tot de Zweedse telefoonkabels om gecodeerde berichten te kunnen versturen vanuit het bezette Noorwegen naar het thuisland. Zweden kon niet anders dan toegeven, maar begon meteen de lijnen af te luisteren en ontdekte al snel 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.

T52
De Siemens & Halske T52 — ook gekend als de Geheimfernschreiber of Schlüsselfernschreibmaschine (SFM) — was een codeermachine die Duitsland gebruikte tijdens de Tweede Wereldoorlog. De machine en zijn gecodeerde berichten kregen van de Britse geheime dienst de codenaam Sturgeon.

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 Codebreakers1 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 konden gekraakt worden, 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)$$.

Gevraagd wordt om een klasse T52 te schrijven waarvan de objecten T52 Geheimschreiber machines voorstellen waarmee berichten kunnen gecodeerd en gedecodeerd worden volgens de procedures die hierboven beschreven werden. Deze klasse moet minstens de volgende methoden ondersteunen:

Bovendien moet het mogelijk zijn om twee objecten van de klasse T52 bij elkaar op te tellen aan de hand van de + operator. Het resultaat moet opnieuw een object zijn van de klasse T52, dat een T52 Geheimschreiber machine voorstelt die hetzelfde resultaat oplevert dan wanneer we eerst berichten zouden coderen met de machine links van de + operator en die daarna nog eens zouden coderen met de machine rechts van de + operator. Indien de twee T52 objecten die bij elkaar opgeteld worden niet hetzelfde alfabet gebruiken, dan moet een AssertionError opgeworpen worden met de boodschap alfabetten zijn verschillend.

Voorbeeld

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

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

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

>>> 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, 'ABCDEFGHIJKLMMLKJIHGFEDCBA')
Traceback (most recent call last):
AssertionError: alfabet bevat herhaalde symbolen

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

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