Enigma, Hitler's Crypto-Machine. Part One

On the occasion of his new film Morten Tyldum, The Imitation Game ( Το παιγνίδι της Μίμησης) που βασίζεται στο βιβλίο του Andrew Hodges "Alan Turing, The Enigma" και βγήκε στις Ελληνικές κινηματογραφικές αίθουσες στις 8 Ιανουαρίου του 2015, θα κάνουμε μια αναδρομή σε μία όχι και τόσο γνωστή πτυχή του δευτέρου παγκοσμίου πολέμου (ΒΠΠ). Η πτυχή αυτή δεν είναι άλλη από την αποκρυπτογράφηση του μυστικού code επικοινωνιών των Ναζί (Enigma) από τους Πολωνούς αρχικά που θα το δούμε σαν "Μέρος Πρώτο" και τους Άγγλους στο Bletchley Park "Part two" , που οδήγησε όπως λένε αναλυτές τους ΒΠΠ στην πρόωρη λήξη του πολέμου. Πολλοί λένε πως, η αποκρυπτογράφηση των μυστικών επικοινωνιών των Γερμανών από τους Άγγλους, οδήγησε στη λήξη του πολέμου, τουλάχιστον 2 χρόνια γρηγορότερα, γλυτώνοντας τον θάνατο περίπου 14 εκατομμυρίων ανθρώπων.

 The beginning

The idea for the most impressive encryption and decryption engine was born 500 years ago. Arthur Scherbius (1878‑1929), patented a cryptographic machine that used disks similar to those of Alberti. It is no coincidence that the machine was named Enigma inspired by the Greek word, riddle.

 Leon Battista Alberti

 

Ο μελετητής της κρυπτογραφίας David Kahn στο βιβλίο του «The code breakers: The story of secret writing» που εκδόθηκε στην Νέα Υόρκη τo 1967, παρουσιάζει τον Leon Battista Alberti (1404 ‑ 1472) ως τον "πατέρα της Δυτικής κρυπτογραφίας". Αναγνώρισε στο πρόσωπό του την ταχεία πρόοδο της Δύσης στην κρυπτανάλυση, την εφεύρεση της πολυαλφαβητικής υποκατάστασης και του κρυπτογραφημένου κλειδιού, τα οποία καθόρισαν στον μεγαλύτερο βαθμό τις εξελίξεις στην κρυπτογραφία. Ιταλός στην καταγωγή και πολυτάλαντος αρχιτέκτων ο Αλμπέρτι επινόησε τον κρυπτογραφικό δίσκο που όπως φαίνεται, έμελλε να είναι ουσιαστικά η πρώτη κρυπτογραφική μηχανή. Ωστόσο η κατασκευή του αν και ιδιαίτερα απλή, μπορούσε να χρησιμοποιηθεί με περίπλοκο τρόπο και αργότερα σε συνδυασμό με την τεχνολογική ωρίμανση να αποτελέσει την καρδιά πολύπλοκων συσκευών.

History of the Alberti album

When Leonardo Dao confided to Alberti that the Vatican had to send encrypted messages, Alberti offered to help. 1467 wrote an essay that laid the foundations in a whole new way of cryptography. Alberto's essay included a clear interpretation of the frequency analysis (ie, how many times we will encounter a character in the text depending on the language of the original text) and offered various ways of resolving the encryption.

He also described the encryption system using two concentric copper discs whose regions were divided into 24 equal parts.

To send an encrypted letter, the letters or numbers were read on the external disk and encrypted inside. The sender and recipient had identical disks and simply decided on the original position of the two disks.

Μέχρι το σημείο αυτό, το σύστημα ήταν μια απλά μονοαλφαβητική αντικατάσταση, αλλά αυτό που έγραψε στη συνέχεια ο Αλμπέρτι, έφερε την καινοτομία. "Αφού γραφτούν 3-4 λέξεις, αλλάζουμε την διάταξη περιστρέφοντας τον έναν δίσκο". Οπότε αλλάζει όλο το σύστημα, εκεί που στην αρχική θέση το γράμμα "k" αντιστοιχούσε στο "f", τώρα το "k" αντιστοιχεί στο "t". Αυτόματα με μια απλή ρύθμιση, η δουλειά του αποκωδικοποιητή έγινε πολύ δύσκολη. Έτσι η χρησιμότητα της ανάλυσης συχνότητας, περιορίστηκε κατα πολύ. Επίσης ο Αλμπέρτι χρησιμοποίησε τους αριθμούς στον εξωτερικό δίσκο ως ένα είδος κρυπτογραφικού κώδικα. Δηλαδή, πριν κρυπτογραφήσει ολόκληρο το κείμενο, αντικαθιστούσε λέξεις με νούμερα με συνδυασμούς των αριθμών 1 - 4. Στη συνέχεια αυτοί οι αριθμοί κρυπτογραφούνταν μαζί με το κείμενο.

Code analysis

Let the text that was to be encrypted was as follows: "ΠΕΙΤΕ ΣΤΟΝ ΠΑΠΑ ΑΜΕΣΩΣ ΈΝΔΕΚΑ ΠΛΟΙΑ ΘΑ ΑΠΟΠΛΕΥΣΟΥΝ ΤΟ ΠΡΩΙ".

Αρχικά αντικαθιστούσε ορισμένες λέξεις όπως είπαμε με νούμερα σύμφωνα με προκαθορισμένο βιβλίο κωδικών. Ας πούμε πως το 14 σημαίνει "ΠΛΟΙΑ ΘΑ ΑΠΟΠΛΕΥΣΟΥΝ ΤΟ ΠΡΩΙ"  και το 342 σημαίνει "ΣΤΟΝ ΠΑΠΑ".

Αμέσως το μήνυμα απο "TICK IN PAPA IMMEDIATELY EASTERN SHIPS WILL FALL ON THE MOON" έγινε "TELL 342 IMMEDIATELY 14".

Then encrypting the entire phrase the final encrypted message would look something like this: THURSER FOX FROZBZ WEDNESDAY The recipient, with the appropriate disk settings and the codebook, could decrypt the message in a very short space of time. If the message was intercepted, it was virtually impossible to read, or if read, it might have been meaningless.

Arthur Scherbius and the Enigma machine

What happens when you complicate and reshape the idea of ​​Leon Battista Alberti, a Renaissance genius who lived to 15^ο century, with rules and techniques of 20^th century?

On April 18, 1918, Serbius delivered the original military version to the German Navy but expectations of a supplier did not materialize and his company ran out of funds until 1923. In a show of perseverance, he co-founded with Richard, a close friend of his. company under the name Chiffriermaschinen AG which dealt with various constructions in addition to Enigma and proceeded to the implementation of its plans.

The Enigma A version appeared on the market in 1923. Being large and heavy compared to the original, since with a built-in typewriter it weighed about fifty kilos, it was considered expensive for the time and was replaced by the Enigma B, without any of the two attract the interest of military services. Serbius promoted it for use by accounting firms, large companies and diplomats who needed to exchange confidential information without ever stopping to eye sales in the military. In the same year, he presented it at the World Postal Congress in Bern, but there was no particular buying interest. With sales down, the next Enigma C model follows, based on an idea from Willi Korn partner. It was much lighter and smaller but its commercial fortunes remained the same.

Finally in 1926 the German army, government agencies and organizations finally procured the Enigma in a variant of its commercial version. In 1927 he launched the Enigma D version with which he managed to find buyers, in military and diplomatic services in the rest of Europe. In the two decades that followed, the Serbius machine sold more than thirty thousand units to the military, making it the most secure encryption system in the world. In total, more than one hundred thousand machines with various variants were sold, even without the Enigma logo, from other manufacturers. Of course, the reputation that preceded the sales did not include the weaknesses of the seemingly impenetrable construction, which are worth noting that was not due to its own defect. What forced the Germans to reconsider their position on the Enigma were two events in England: a text by Winston Churchill, The Global Crisis, published in 1923 describing how the British had gained access to German cryptographic material that had helped Analysts in Room 40 read the German cryptograms and the official version of World War I history published by the British Royal Navy, which highlighted the Allied advantage of spying on and intercepting German communications.

It took the Germans almost ten years to realize their failure in this area. When the BPP broke out and they had the Enigma at their disposal, their victory seemed guaranteed. With such an unprecedented security system for their communications, they felt invulnerable, but in the end all that was secured was the fall of Hitler. Unfortunately, Serbius was not going to know the successes and failures of his achievement. He was killed in 1929 in an accident with his carriage.

The Enigma settings

The Enigma, as we have seen above, was a typewriter, the size of a modern computer, consisting of a 26 keypad on the front, at the top of 26 lamps that depicted letters and turned on when the user typed and depicted the replacement letter the user was typing. In the prototype version of the engine there were three revolving discs or reversers. Each reorder has a series of internal wiring with electrical contacts on its surface so that each different position of the reorder has different electrical contacts between the keys and the lamps.

As soon as one letter was struck, the right rearranger rotated by 1/6 of a full spin for a full 26-letter Latin alphabet. After 26 rotations, the middle rearranger would rotate accordingly and after 26 of its own rotations the left would rotate left. The complexity of encryption increased more than a table of plugs on the front of the machine, where special pairs of matched letters alternated with the insertion of the plugs.

It is estimated that there were about 10¹⁵  powerful ways of adjusting the camera. And the number of combinations produced is about 3 x 10¹¹⁴  combinations  (3 followed by 114 zeros that is). These were the chances that the Poles and later the English had to eliminate in order to decipher the messages produced.

The role of the Poles in the decryption of Enigma.

Poland is a country located geographicallygraphics wedged between Germany and the then Soviet Union. After the GPA and in the mid-1920s, German leaders began to talk aggressively about annexing territories granted to Poles by post-war treaties. So it didn't take long for the Poles to realize that they had to gain access and knowledge of the Germans' communications. In 1928 they received mysterious coded messages that defied conventional decryption methods of the time. It is the first contact of Poles with Enigma.

1932 in Warsaw, three young Polish cryptographers and mathematicians, Marian Rezevski, Giersi Rozziski and Henrik Zigalsky, played a key role in breaking the codes used by the German Enigma machine. The machine was operated by letter retooling, the positions of which, as well as any changes, were described in a user manual. The user manual did not say anything about the rotor settings.

(Note that the fourth rotor was added much later by the Navy Navy, the machine we are talking about now consists of 3 rotors).

E.g. on the 4th of the month the rearrangements had to be A,X,N at the top. The user would then send the message: AXNAXN before continuing with the content του μηνύματος. Οι Πολωνοί δεν άργησαν να καταλάβουν πως αυτή η επανάληψη κάθε μέρα σε συγκεκριμένα μηνύματα, μόνο τυχαία δεν ήταν. Ήταν οι ρυθμίσεις των ροτόρων της μηχανής ώστε να αρχίσει η κρυπτογράφηση, ουσιαστικά ήταν τα "κλειδιά" της συγκεκριμένης μέρας. ( Η επανάληψη στην κρυπτογραφία είναι τεράστιο λάθος). Επίσης οι Πολωνοί κατάλαβαν πως θα μπορούσαν να χρησιμοποιήσουν θεωρητικά μαθηματικά "θεωρία ομάδων" προκειμένου να σπάσουν το κρυπτόγραμμα. Συνειδητοποίησαν πως για κάθε δεδομένη ρύθμιση της μηχανής, κάθε εισερχόμενο γράμμα θα κρυπτογραφείτο ως κάποιο διαφορετικό γράμμα. Επειδή η μηχανή ήταν αντιστρέψιμη, δηλαδή κρυπτογραφούσε και αποκρυπτογραφούσε, το κρυπτογραφημένο γράμμα θα κρυπτογραφείτο μετά ως το αρχικά χρησιμοποιημένο. Αυτή η συνειδητοποίηση τους άνοιξε μια οδό προς την Enigma.

We can record how a machine setting shifts characters using group theory.

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

J

R

U

X

A

W

N

S

F

Q

Y

T

B

H

M

D

E

V

G

I

L

P

K

Z

C

O

Στη πρώτη σειρά είναι τα γράμματα του αλφαβήτου και στη δεύτερη τα γράμματα που ανάβουν (με τη βοήθεια των λαμπτήρων) όταν ο χρήστης πληκτρολογεί. Πχ. Όταν ο χρήστης πατά μια φορά "A", η μηχανή ανάλογα με την ρύθμιση του δίνει "J" κοκ.

Παρατηρήστε όμως πως το "Α" μετατοπίζεται στο "J", το "J" στο "Q", το "Q" στο "Ε" και το "Ε" στο "Α". (AJQE). Υπάρχουν άλλοι τρεις κύκλοι γραμμάτων:

(GNHS), (BRVPDXZOM), (CULTIFWKY).

That is, two groups of four letters and two groups of nine. This awareness reduced the volume of manual effort required to crack the encryption. They also found that the arrangement of letter pairs did not affect the theory of the groups they applied.

So basically the problem was with the initial machine settings that changed every 12 hours and which were shipped between German cryptographers, months earlier.

The role of Marian Rezevski

 

Marian Rezevski was one of the three Polish mathematicians chosen by Major Maximilian Chianski to work on decrypting the Enigma machine. Resevski was a mathematician, and when he chose what career to follow, that was mathematics. Fortunately, however, he did so to work on decrypting the Enigma machine.

As we said above, the Polish euthanasians (ie those who obstructed the transmission of the Morse code) suffered many messages everyday, Rezevski was slow to observe that every day at 12 at midnight, the Germans sent a specific message twice, settings of the Enigma engine. For example, user A was typing TIM TIM, the machine produced something random, that is, HUW WYT which, for sure, the Germans sent it through Morse signals twice. Rezevski, by analyzing thousands of such messages, manages to make paintings, with every possible shift of letters through 6 powerful algebraic equations.

Rezevski was the one who introduced the solution of variables by permutation, until then no theory had been formulated, he developed it. Using these boards, the Poles managed to decrypt the Enigma machine for some time, but it did not last long. In 1932 in Germany the Nazis achieved significant political victories and finally in 1933 Hitler came to power. And then the decryption of the Enigma machine becomes a major issue in Poland.

Ο ρόλος του Hans - Thilo Schmidt

Δεν θα μπορούσε σε μια ιστορία πολέμου, μυστικών, κρυπτογραφίας - αποκρυπτογραφίας να μην υπάρχει και ένα άτομο με αέρα κατασκοπίας ( ή μάλλον προδοσίας).

Αυτός δεν είναι άλλος από τον εικονιζόμενο Hans - Thilo Schmidt. Ο Ρεζεβσκι δεν θα είχε κάνει την πρόοδο που είχε κάνει με τις εξισώσεις και τους πίνακές του,αν δεν είχε στα χέρια του περισσότερα δεδομένα για να καταφέρουν να αποκρυπτογραφήσουν εντελώς την μηχανή Enigma.

Τον Νοέμβριο του 1931, έναν χρόνο πριν ο Ρεζέβσκι ολοκληρώσει τις έξι εξισώσεις μετάθεσης μεταβλητων, έγινε μια συνάντηση σε ένα ξενοδοχείο του Βελγίου ( Grand Hotel Vervier) στην πόλη Βερβιέρ, όπου ο αξιωματικός Γκουσταβ Μπερτράν της Γαλλικής αντικατασκοπείας, συνάντησε τον δημόσιο λειτουργό Hans - Thilo Schmidt.

There Schmidt sold him copies of the machine settings Enigma. Schmidt's reason for doing this was financial, he made a very rich living, although he was a landlord businesss, however, the money was not enough for the lifestyle he used to lead. His brother got him a job in a ministry that surprisingly came into contact with the documents in question, so he was tempted to sell them. He sells them to the French officer for the sum of ten thousand reichmarks, about twenty thousand today's pounds (about twenty eight thousand euros).

Bertrand soon realizes that he cannot use them and informs the British, who find them too expensive. In an act of desperation Bertrand informs the head of Enigma's cryptography team in Poland Lt. Col. Guido Langer who, naturally, sees them as a godsend and buys them. Later he gives them to Rezewski who draws many information from the specific documents and creates the tables we said above.

This is the end of the first part of the dedication of the Enigma machine. In the next part we will deal with the English side who later enters the game by decrypting the Enigma specifically in the German navy and the Atlantic front, where the war in Europe was finally judged and ended with the allied forces in Normandy.

Part two.