In summer 1940, Germany demanded access to Swedish telephone cables to send encoded messages from occupied Norway back to the homeland. Sweden acceded but tapped the lines and discovered that a new cryptographic system was being used. The T52 Geheimschreiber (or G-schreiber in short), with more than 800 quadrillion settings, was conveying top-secret information but seemed immune to a successful codebreaking attack.

The Siemens & Halske T52 — also known as the Geheimfernschreiber ("secret teleprinter") or Schlüsselfernschreibmaschine (SFM) — was a World War II German cipher machine and teleprinter produced by the electrical engineering firm Siemens & Halske. The instrument and its traffic were codenamed Sturgeon by British cryptanalysts.

The Swedish intelligence service assigned mathematician Arne Beurling to the task, giving him only a pile of coded messages and no knowledge of the mechanism that had been used to encode them. But after two weeks alone with a pencil and paper he announced that he had decoded the messages. He also described how a complementary machine could be built to decode the messages automatically.

Thanks to his work, Swedish officials learned in advance of the impending invasion of the Soviet Union. Unfortunately, Stalin's staff disregarded their warnings. In his book The Codebreakers¹ Bengt Beckman accounts of the exploit. In his foreword to the book, Peter Jones writes:

To this day no one knows exactly how Beurling reasoned during the two weeks he spent on the G-Schreiber. In 1976 he was interviewed about his work by a group from the Swedish military, and became extremely irritated when pressed for an explanation. He finally responded, "A magician does not reveal his tricks." It seems the only clue Beurling ever offered was the remark, cryptic itself, that threes and fives were important.

Assignment

In the end, the procedure used by the T52 Geheimschreiber did not turn out to be all too complicated. It uses an alphabet of $m$ symbols that are all different and have a fixed order. The positions of the symbols in the alphabet are indexed $0, 1, \dots, m - 1$ .

In addition, two integers $a$ and $b$ are used as the key for encoding and decoding. Each symbol at position $x$ in the alphabet is encoded as the symbol at position $E (x)$ in the alphabet, where $E (x) = (a x + b) mod m (0 \leq x < m)$ and the operator $mod$ results in the remainder after integer division. Each symbol at position $x$ in the alphabet is decoded as the symbol at position $D (x)$ in the alphabet, where $D (x) = a^{'} (x - b) mod m (0 \leq x < m)$ and $a^{'}$ is the multiplicative inverse of $a$ modulo $m$ . In other words, $a^{'}$ is the integer in the interval $[0, m [$ that satisfies the equation $1 = a a^{'} mod m$ The multiplicative inverse of $a$ only exists if $a$ and $m$ are coprime. This is the case if the greatest common divisor of $a$ and $m$ equals 1. If this is the case, there is only one integer in the interval $[0, m [$ that satisfies the equation for the multiplicative inverse.

When the Germans noticed that messages sent using the T52 could be easily decoded, they tried to make the encryption procedure more complex. This was done by not encoding a message once but twice. First a message was encoded by a T52 that used keys $a_{1}$ and $b_{1}$ , and the result was encoded again by a T52 that used keys $a_{2}$ and $b_{2}$ . This is only possible if the two machines use the same alphabet. From the observation that $E_{2} (E_{1} (x)) = (a_{2} ((a_{1} x + b_{1}) mod m) + b_{2}) mod m = (a_{1} a_{2} x + (a_{2} b_{1} + b_{2})) mod m$ it follows that this has the same effect as encoding the message only once by a T52 that used keys a_1a_2 $a n d$ (a_2b_1 + b_2)$.

Define a class T52 to represent machines that can be used to encode and decode messages according to the Geheimschreiber cipher. Three argument must be passed when creating a new machine (T52): two integers $a$ and $b$ (int) and an $m$ -character alphabet (str). If $a$ and $m$ are not coprime, an AssertionError must be raised with the message a and m are not coprime whose cursive fragments are filled up with the values $a$ and $m$ . If not all characters of the given alphabet are different, an AssertionError must be raised with the message alphabet has repeated symbols.

Greatest common divisor

Use the function math.gcd² to compute the greatest common divisor of two integers.

A machine $m$ (T52) must support at least the following methods:

A method encode_symbol that takes a single character (str). If the given character occurs in the alphabet of machine $m$ , the method must return the encoded character (str). Otherwise the method must return the given character (str) itself.
A method decode_symbol that takes a single character (str). If the given character occurs in the alphabet of machine $m$ , the method must return the decoded character (str). Otherwise the method must return the given character (str) itself.
A method encode that takes a plaintext $t$ . The method must return the corresponding ciphertext (str): the text $t$ in which all characters that occur in the alphabet of machine $m$ are replaced by their encoded characters. All characters that do not occur in the alphabet of machine $m$ must be retained.
A method decode that takes a ciphertext $t$ . The method must return the corresponding plaintext (str): the text $t$ in which all characters that occur in the alphabet of machine $m$ are replaced by their encoded characters. All characters that do not occur in the alphabet of machine $m$ must be retained.

Make sure the sum (+) of two machines $m_{1}$ and $m_{2}$ (T52) yields a new machine (T52), that encodes messages as if we would first encode the message using the machine to the left of the + operator and then encode the result once more using the machine to the right of the + operator. If the two machines $m_{1}$ and $m_{2}$ (T52) do not use the same alphabet, an AssertionError must be raised with the message alphabets are different.

Example

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

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

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

>>> machine1.encode('G-SCHREIBER')
'X-HLAERDIRE'
>>> machine1.decode('X-HLAERDIRE')
'G-SCHREIBER'

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

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

>>> T52(4, 5, 'ABCDEFGHIJKLMMLKJIHGFEDCBA')
Traceback (most recent call last):
AssertionError: alphabet has repeated symbols

>>> T52(4, 5, 'ABCDEFGHIJKLMNOPQRSTUVWXYZ')
Traceback (most recent call last):
AssertionError: 4 and 26 are not coprime

>>> machine1 + T52(17, 11, 'abcdefghijklmnopqrstuvwxyz')
Traceback (most recent call last):
AssertionError: alphabets are different