Grid method

from Wikipedia, the free encyclopedia
A grill with bars and gaps, like the one used for grilling , was Rejewski's namesake for the method he devised.

The grid method (actually: "Der Rost" , Polish Metoda rusztu ( German  literally: "Rust method" ), English grill method , French Méthode du gril ) was a cryptanalytic process devised by the Polish cryptanalyst Marian Rejewski in the early 1930s of the key of the German rotor key machine Enigma .

background

The plug board introduced in 1928 significantly increases the combinational complexity of the encryption and thus the key space of the Enigma machine . In the picture only two of a maximum of thirteen possible cables are plugged in.

Since June 1, 1930, when the Enigma I went into service , the German Reichswehr had an - for the time - exceptionally secure encryption machine . In contrast to its predecessors, such as the Enigma-D , it was strengthened by a secret additional device, the plug board  used exclusively by the military (picture) . This allowed all letters of the Latin alphabet to be exchanged in pairs .

However, the cryptographic potential of the plug board was not fully used. Instead of using all thirteen possible and available letter pairs , in the first few years the company limited itself to exchanging only six of them with double-pole plug-in cables. The remaining fourteen (14 = 26 - 2 × 6) letters remained " unplugged " (were not swapped). The Enigma set in this way was then used to encrypt the message key to be individually selected for each encrypted radio message . Here, the German authorities made another mistake by stipulating that the key to the verdict be doubled .

method

Polish schematic drawing of the German machine
Graphic representation of the "grate" with the hatched slots through which the letters on the sheet below can be viewed. As an example, only two of the actually six horizontal grid columns are shown here.

The prerequisites for the implementation of the grid method are - after the Polish Biuro Szyfrów ( German  "Chiffrenbüro" ) had clarified the functionality of the machine and determined the wiring of the rollers - the above two procedural errors: Use of only six (of the thirteen possible) plug connections and the duplication of the spell key . The Polish cryptanalyst could also assume that "firstly, while the key is being keyed, the central roller only turns about once in 5 cases [exactly 5 out of 26], and secondly that the plug connection leaves a number of letters unchanged."

Under these conditions, it is possible to specify a relation between the left part of the roller set, consisting of the middle and left roller as well as the reversing roller (VHF), and the right part, consisting of the rotating right roller, in the form of a system of equations. Since the doubled saying key consists of a total of six letters, you get six such equations. The respective left-hand side is constant for all six equations with the exception of an “exponent”, which can have one of 26 values. And the respective right side shows the substitution of the right roller. Rejewski called these substitution with the letter F . This can be calculated for each of the 26 assumed cases of the exponent using each of the six equations. In most cases, the six equations different result F , with one exception, the same in all six equations F specify. This is the solution you are looking for, from which you can deduce the rotational position of the right roller.

The method described depends on the fact that none of the six letters of the duplicated slogan key and its encryption are "plugged in", i.e. that they are not mixed up by a cable plugged into the plug board. If this is still the case, then with a little effort it is possible to use the method anyway if only a few letters are affected by "plugging". However, if too many or even all letters are inserted, the method will fail. In other words, the usefulness of the screening method is impaired by the number of letters swapped. If the Germans had swapped all thirteen pairs of letters with plug-in cables, the break-in opportunity described would not have existed.

In practice, the Polish cryptanalysts saved themselves the tedious and time-consuming examinations and calculations that were repeated for each individual daily key . Instead, they devised a mechanical process using two sheets of paper placed one on top of the other. On the lower one, write the possible substitutions made by the left part of the set of rollers in 26 consecutive lines. Each line contains the assumed “scrambled” substitution alphabet. On the upper sheet, write the substitutions given by the six letters of the doubled key in six lines, also as 26 scrambled letters each. Slits were cut below each of the six lines through which one could see the lower sheet  (picture) .

So the top sheet looks like a grate. This grid is placed on the lower sheet and shifted up and down until one discovers identical substitutions on the upper sheet and - through the grid slits - on the lower sheet. As I said, this only applies if you are “lucky” and the letters concerned “happen to be” all unplugged. Otherwise it can still be possible to recognize certain symmetries or analogies between letter pairs and thus even to open up some plug connections. The result is some of the connectors you are looking for and the rotation position of the right roller.

successor

The grid method was rarely used after October 1936. Instead, it created using a now specially built for this purpose electromechanical cryptanalytic auxiliary device, called the cyclometer ( German  literally means "bow knife" ), a so-called " Catalog of characteristics " (Polish: Catalog charakterystyk ). On the basis of this, the key sought could be determined much more easily and quickly. The creation of this cycle catalog, as Rejewski expressed himself, "was laborious and took more than a year, but after it was finished [...] day keys could [be] determined within about 15 minutes".

literature

Web links

Individual evidence

  1. ^ Friedrich L. Bauer: Historical Notes on Computer Science . Springer, Berlin 2009, p. 301. ISBN 3-540-85789-3 .
  2. ↑ Marian Rejewski and Henryk Zygalski: Brief description of the dissolution methods. Bertrand Archive SHD DE 2016 ZB 25/6, Dossiers Nos. 281 and 282, ca.1940, pp. 24-26.
  3. ↑ Craig P. Bauer: Secret History | - The Story of Cryptology . CRC Press, Boca Raton 2013, p. 248. ISBN 978-1-4665-6186-1 .
  4. ↑ Louis Kruh, Cipher Deavours: The Commercial Enigma - Beginnings of Machine Cryptography . Cryptologia, Vol.XXVI, No. 1, January 2002, p. 11. apprendre-en-ligne.net (PDF; 0.8 MB), accessed on March 11, 2019.
  5. ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin a. a. 2000, p. 412.
  6. ↑ Marian Rejewski and Henryk Zygalski: Brief description of the dissolution methods. Bertrand Archive SHD DE 2016 ZB 25/6, Dossiers Nos. 281 and 282, ca.1940, p. 24.
  7. ↑ Marian Rejewski and Henryk Zygalski: Brief description of the dissolution methods. Bertrand Archive SHD DE 2016 ZB 25/6, Dossiers Nos. 281 and 282, ca.1940, p. 26.
  8. ^ Friedrich L. Bauer: Historical Notes on Computer Science . Springer, Berlin 2009, pp. 301-302. ISBN 3-540-85789-3 .
  9. ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin a. a. 2000, p. 417.
  10. ^ Dermot Turing: X, Y & Z - The Real Story of how Enigma was Broken. The History Press, Stroud 2018, ISBN 978-0-75098782-0 , p. 67.