Prehistory of Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 10

Enigma was made to be “unbreakable,” even if the enemy had the specifications
(namely, the above description and ): the number of combination is so high

(namely 26 3 times the number of possible wired permutation

π, α, β, γ

) that the enemy cannot
obtain the key by exhaustive search. Poles reconstructed the Enigma machine before
World War II and started to perform cryptanalysis. Their knowledge was given to the
Allied forces when Poland was invaded.

σ

Cryptanalysis starts with the following observation. The permutation which maps
x i onto y i is an involution without any fixed point, and any two of these permutations
which differ only on the choice of are isomorphic. The attack then starts by finding

known plaintexts: messages always have predictable headers or footers, and we can
rule wrong guesses out by checking that we have no fixed points. Then, we describe
the observed sequence of input-output pairs and we describe it as a graph. If we guess
the initial choice of a , we must obtain an isomorphic graph. An automatic process then
exhaustively tries all possible a combinations (we have 26 3

σ

of them). Handy analysis

then ends up recovering σ .

Interestingly, the first programmable computer which was ever built (even before
the ENIAC) was constructed in order to break ciphers like Enigma. Some dedicated
machines called “bombes” (from the name of a Polish ice cream) were performing
the exhaustive search on a . Alan Turing was a member of the team which built this
machine and so this was indeed the first Turing machine. The reason why textbooks
on computer science refer to ENIAC as the first computer is that the existence of these
activities became to be publicly known only in the seventies. 7

1.2 Roots of Modern Cryptography

1.2.1 Cryptographic Problems: The Fundamental Trilogy

In Anglo-Saxon literature, cryptography is usually illustrated by famous characters:
Alice and Bob (A and B). For biblical reasons, the malicious adversary is usually
female and called Eve. According to the (politically incorrect) folklore, Alice and Bob
want to communicate securely (for instance, confidentially) and to protect against Eve.
A Canadian rock band was even inspired to write a French song about it. 8

Cryptography concentrates on three fundamental paradigms.

Confidentiality. The information should not leak to any unexpected party.
Integrity. The information must be protected against any malicious modification.
(Example: integrity of communications, integrity of backups, etc.)
Authentication. The information should make clear who the author of it is. (Ex-
ample: signature authentication, access control, etc.)

7

For more references, see Ref. [91].

8

“Les Tchigaboux,” see http://www.iro.umontreal.ca/˜crepeau/CRYPTO/Alice-Bob.html.