Cryptology

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. Classic Ciphers
2. Bitblock Ciphers
3. Asymmetric Ciphers
4. Bitstream Ciphers

This an extended English version of the notes of cryptology courses I gave at Johannes Gutenberg University from 1988 until 2011 (when I retired).

Why this text? There exist already myriads of textbooks on cryptology, many of them excellent. An additional text should exhibit some original features. Here are some offerings of this text:

• Careful discussion of the (mostly mathematical or historical) foundations of cryptographic and cryptanalytic procedures (including the losing game of denoting procedures after their true inventors)
• Systematic treatment of polyalphabetic ciphers (such as cipher disks and cipher cylinders)
• Discussion and practical application of efficient, but not so well-known attacks on classical ciphers (pattern recognition, autocoincidence spectrum, zigzag exhaustion, ...)
• Thorough treatment of the statistical analysis of polyalphabetic ciphers
• Many elaborate examples of cryptanalytic attacks
• Many results on the complexity of modern ciphers, relating Turing complexity, Boolean (circuit) complexity, and shift register complexity
• A systematic approach to complexity via probabilistic Boolean circuits
• Thorough treatment of Boolean functions and their use in bitblock and bitstream ciphers
• A systematic approach at measures for non-linearity of Boolean maps (or S-Boxes)
• A fresh view on RSA, emphasizing the Carmichael function
• RSA for »wrong« primes and products of more than two primes
• Discussion of the order of the RSA permutation and the period of the BBS sequence
• Systematic treatment of shift registers (linear or nonlinear, as well as combinations) and their complexity
• Methods for predicting the output of pseudorandom generators (and thereby for cracking stream ciphers)

Requirements for readers: People without mathematical ambitions may browse the HTML pages—these are informal and hopefully self-contained. The mathematical background is always in PDF files whose substance differs from section to section, so there should be useful information on every level of mathematical sophistication. Large parts of the mathematical content of Chapter I are accessible with a good knowledge of school mathematics (calculating with numbers, naive probability). From Part II on almost all content is mathematical and requires some undergraduate mathematics (basic knowledge in calculus, probability, linear algebra, rings, fields, polynomials, algorithmics). After all, these lectures were given for students of mathematics and computer science. »The methods of cryptography are mathematical.« (David Kahn)

The mathematical formalism (here as elsewhere) is useful for

• expressing facts in a precise and concise way,
• showing the way to possible generalizations by abstraction,
• emphasizing structural similarities,
• giving formal proofs

Hints for mathematicians are on an extra page.

Notation:

• Cryptology = cryptography + cryptanalysis.
• The subject of cryptography is constructing ciphers,
• the subject of cryptanalysis is breaking ciphers.