Pattern search (cryptology)

from Wikipedia, the free encyclopedia

As a pattern search in the will Cryptology a classic method for deciphering of secret texts referred. It will also "Method of probable word " ( English Probable word method ; French L'attaque par mot probable ) called.

The code breaker knows, suspects or guesses that a certain text fragment (a word or part of a sentence) appears in the ciphertext to be deciphered. If it is possible to determine the exact location (position) of this fragment in the text, then with some encryption methods a break-in is achieved that is often sufficient to break the encryption completely .

example

For example, there is the following ciphertext: 

FVMZM FGMJZ QDGKK RGCRI KJZMR GQQQP LWWZI
JZDVZ AZWQJ GIKZQ DZIMP IZEZM FZVKJ

The text is relatively short (only 65 characters), so that classical attempts at deciphering with the help of statistical methods of cryptanalysis can hardly work properly. A determination of the frequencies of the letters and their distribution allows the conclusion, even with such a short text, that it is possibly a simple monoalphabetic encryption . 

Häufigkeitsreihenfolge:

12  6  6  5  5  5  5  3  3  3  3  3  2  1  1  1  1  0  0  0  0  0  0  0  0  0
 Z  M  Q  G  I  J  K  D  F  R  V  W  P  A  C  E  L  B  H  N  O  S  T  U  X  Y

The attacker also suspects that it is a message from, for or about Max Mustermann , at least that this name appears encrypted in the text. Consequently, he takes MAXMUSTERMANN as a probable word (English: Crib ) and tries to find out its exact position in the text. To do this, he first determines the pattern of the text fragment and consecutively numbers the letters, with the same letters being given the same numbers. How to get the pattern: 

Wahrscheinliches Wort:   M A X M U S T E R M A N N
Muster:                  1 2 3 1 4 5 6 7 8 1 2 9 9

In the next step he examines the ciphertext for every possible position of the crib . The ciphertext is 65 characters long and the Probable word is thirteen characters long. As a result, 65-13 + 1 = 53 layers are possible. For each of these positions he determines  the pattern of the ciphertext fragment in the same way - as above for the probable word . 

Lage 1:                  F V M Z M F G M J Z Q D G
Muster 1:                1 2 3 4 3 1 5 3 6 4 7 8 5

Lage 2:                  V M Z M F G M J Z Q D G K
Muster 2:                1 2 3 2 4 5 2 6 3 7 8 5 9
   .                                 .
   .                                 .
   .                                 .

Lage 16:                 R G C R I K J Z M R G Q Q
Muster 16:               1 2 3 1 4 5 6 7 8 1 2 9 9
   .                                 .
   .                                 .
   .                                 .

Lage 53:                 I M P I Z E Z M F Z V K J
Muster 53:               1 2 3 1 4 5 4 2 6 4 7 8 9

The result of the pattern search is that the pattern matches that of the probable word only at one point in the ciphertext, namely at position 16 . All other positions can be safely excluded as possible locations due to the pattern that does not match there.

In the next step of deciphering, the probable word is now written over the ciphertext in the determined appropriate position: 

..... ..... ..... maxmu sterm ann.. ..... ..... ..... ..... ..... ..... .....
FVMZM FGMJZ QDGKK RGCRI KJZMR GQQQP LWWZI JZDVZ AZWQJ GIKZQ DZIMP IZEZM FZVKJ

The letters identified in this way ( plain text, lower case and ciphertext, upper case) R = m, G = a, C = x, I = u, K = s, J = t, Z = e, M = r, G = a and Q = n can be added over the rest of the ciphertext. 

..rer .arte n.ass maxmu sterm annn. ...eu te..e .e.nt ausen .eur. ue.er .e.st
FVMZM FGMJZ QDGKK RGCRI KJZMR GQQQP LWWZI JZDVZ AZWQJ GIKZQ DZIMP IZEZM FZVKJ

The further decipherment based on the now clearly legible further clear text fragments such as er.arten.ass (= expect that), .eute (= today) and .e.ntausen. (= ten thousand) is no longer difficult for the trained eye of a linguistically experienced cryptanalyst: "We expect Max Mustermann to transfer the ten thousand euros today."

It is even easier to use computer programs for this, which can carry out the pattern search and the subsequent deciphering in fractions of a second.

With the help of the pattern search, it is possible to decipher even such short and seemingly unbreakable ciphertexts which, due to their short length, can hardly be attacked with the help of statistical methods alone.

See also

  • Pattern search when deciphering the Enigma
  • Data mining - (“lifting treasures”) - the systematic application of (mostly statistical-mathematical) methods to a database with the aim of recognizing new patterns

literature

Individual evidence

  1. ↑ Friedrich L. Bauer: Deciphered secrets. Methods and maxims of cryptology. 3rd, revised and expanded edition. Springer, Berlin et al. 2000, p. 276.
  2. ^ Claude Shannon: Communication Theory of Secrecy Systems . Bell System Technical Journal, Vol. 28, 1949 (October), pp. 710f. Accessed: March 31, 2017. PDF; 0.6 MB