Elements of Cryptanalysis: From Al-Kindi to Post-Quantum Standards

Elements of Cryptanalysis: From Al-Kindi to Post-Quantum Standards#

“One way to solve an encrypted message, if we know its language, is to find a different plaintext of the same language long enough to fill one sheet or so, and then we count the occurrences of each letter.” — Abu Yusuf Ya’qub ibn Ishaq al-Kindi, Risalah fi Istikhraj al-Mu’amma, c. 850 AD

Welcome#

Cryptanalysis — the science of breaking ciphers — is as old as cryptography itself. From Al-Kindi’s pioneering frequency analysis in ninth-century Baghdad to the polynomial-time quantum algorithms that threaten today’s public-key infrastructure, the history of cryptanalysis is a story of ingenuity, mathematical depth, and an unending arms race between code-makers and code-breakers.

This course traces the intellectual arc of cryptanalysis across twelve centuries. We begin with the classical substitution ciphers and their statistical vulnerabilities, advance through the electromechanical Enigma and the birth of information theory, examine the powerful techniques of linear and differential cryptanalysis that shaped modern block cipher design, and culminate with the post-quantum revolution — lattice-based and code-based cryptosystems designed to withstand the computational power of quantum machines.

Every technique is implemented from scratch in Python using only NumPy and Matplotlib. You will not merely read about cryptanalysis — you will perform it, breaking real ciphers, computing approximation tables, and implementing the very algorithms that have shaped the modern security landscape.

What You Will Learn#

Part I: Foundations of Cryptanalysis (~850 AD – 1920s)#

Kerckhoffs’s principle, attack taxonomies, permutations, substitution ciphers, and Al-Kindi’s frequency analysis.

Part II: Classical Polyalphabetic Ciphers (1553 – 1863)#

Monoalphabetic and polyalphabetic cryptanalysis, the Vigenère cipher, Kasiski examination, and Friedman’s index of coincidence.

Part III: Polygraphic Ciphers (1854 – 1929)#

The Hill cipher, Playfair cipher, and automated cryptanalysis using n-gram scoring and hill climbing.

Part IV: The Enigma Machine (1918 – 1945)#

The Enigma’s electromechanical design, Rejewski’s mathematical reconstruction, and Turing’s Bombe at Bletchley Park.

Part V: Information Theory and Block Cipher Design (1945 – 1977)#

Shannon’s theory of secrecy systems, confusion and diffusion, Feistel networks, and the Data Encryption Standard.

Part VI: Linear Cryptanalysis (1993)#

Matsui’s method: linear approximations, the piling-up lemma, and a complete attack on a substitution-permutation network.

Part VII: Differential Cryptanalysis (1990)#

Biham and Shamir’s technique: input-output differentials, difference distribution tables, and chosen-plaintext key recovery.

Part VIII: The Advanced Encryption Standard (1997 – 2001)#

Finite field arithmetic in GF(2⁸), the Rijndael design, and the wide trail strategy for resistance to known attacks.

Part IX: RSA and Integer Factorization (1977 – present)#

The RSA cryptosystem, common implementation attacks, and factoring algorithms from trial division to the number field sieve.

Part X: Diffie-Hellman and Discrete Logarithms (1976 – present)#

Key exchange, the ElGamal cryptosystem, baby-step giant-step, Pohlig-Hellman, and index calculus.

Part XI: Elliptic Curve Cryptography (1985 – present)#

The group law on elliptic curves, Hasse’s theorem, ECDH, ECDSA, and the MOV attack.

Part XII: Algebraic Cryptanalysis (2000s)#

Gröbner bases, algebraic modeling of S-boxes, and the XSL attack on block ciphers.

Part XIII: The Quantum Threat (1994 – 2024)#

Quantum computing foundations, Shor’s algorithm for factoring and discrete logarithms, and Grover’s search speedup.

Part XIV: Lattice-Based Cryptography (1996 – 2024)#

Lattice problems (SVP, CVP, LWE), ML-KEM (Kyber) design and implementation, and attacks on lattice schemes.

Part XV: Code-Based Cryptography and Frontiers (1978 – 2025)#

McEliece encryption with Goppa codes, Patterson’s decoding, NIST post-quantum standards, and open problems.

Course Rules#


Course type	AMUPIE (06-DELCLI0-E)
Semester	2025/2026 (summer)
ECTS	5
Duration	60 hours
Faculty	Faculty of Mathematics and Computer Science, Adam Mickiewicz University
Instructor	dr Bartosz Naskręcki (bartnas@amu.edu.pl)
Schedule	Thursdays, 13:45–15:15 and 15:30–17:00
Office hours	B1-15, Tuesdays, 12:00–13:00

Flipped Classroom

This course uses the flipped classroom model. Each week you will have reading material and exercises to work through before class. The live sessions are devoted to discussions, case analysis, and collaborative problem-solving.

Course Evaluation#

Your final grade is determined by accumulating points across three components:

Component	Weight
In-class activities	30%
Home Moodle activities	30%
Projects	40%

Grading scale (percentage of total points):

Threshold	Grade
90%	bardzo dobry (5)
85%	dobry plus (4.5)
80%	dobry (4)
75%	dostateczny plus (3.5)
60%	dostateczny (3)
< 60%	niedostateczny (2)

Prerequisites#

Number theory: Modular arithmetic, primes, Euler’s totient function, Chinese Remainder Theorem
Linear algebra: Matrices, vector spaces, eigenvalues, operations over finite fields
Probability: Basic distributions, conditional probability, expectation, variance
Programming: Python (NumPy, Matplotlib) — all code is written from scratch
Mathematical maturity: Comfort with proofs, formal definitions, and theorems

How to Use This Book#

Each chapter contains:

Historical context — who, when, why
Mathematical theory — definitions, theorems, complete proofs
Python implementations — working code you can run and modify
Experiments — parameter exploration, visualization, empirical verification
Exercises and challenges — from routine to research-level

The code cells are meant to be executed interactively. Modify the parameters, change the data, break things — that is how you learn.

Dual Track: Python and SageMath#

This course provides two parallel computational tracks:

Python/NumPy chapters — every chapter (ch01–ch45) contains implementations built from scratch using only NumPy and Matplotlib. These are self-contained and require no special setup beyond standard Python.
SageMath companion chapters — for 24 chapters (Parts I–XII), a companion notebook marked (SageMath) provides the same material implemented in SageMath. SageMath offers built-in support for finite fields (GF()), polynomial rings (PolynomialRing), elliptic curves (EllipticCurve), Gröbner bases, and other algebraic structures that make certain cryptanalytic computations more natural and concise.

Running SageMath notebooks

To run the SageMath companion chapters, activate your SageMath environment and launch Jupyter:

conda activate sage
sage -n jupyter

The SageMath notebooks use the sagemath kernel. If you do not have SageMath installed, you can still follow the course using the Python/NumPy chapters exclusively.

Key Papers#

Shannon, C. E. (1949). Communication Theory of Secrecy Systems. Bell System Technical Journal, 28(4), 656–715.
Diffie, W. and Hellman, M. E. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644–654.
Rivest, R. L., Shamir, A., and Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126.
Biham, E. and Shamir, A. (1991). Differential Cryptanalysis of DES-like Cryptosystems. Journal of Cryptology, 4(1), 3–72.
Matsui, M. (1994). Linear Cryptanalysis Method for DES Cipher. EUROCRYPT ‘93, LNCS 765, 386–397.
Shor, P. W. (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5), 1484–1509.
Regev, O. (2005). On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. STOC ‘05, 84–93.
McEliece, R. J. (1978). A Public-Key Cryptosystem Based on Algebraic Coding Theory. DSN Progress Report 42-44, JPL/Caltech.

Technical Setup#

Python track:

pip install numpy matplotlib jupyter-book sympy

SageMath track (optional):

conda activate sage
sage -n jupyter

The Python chapters use only NumPy and Matplotlib — no frameworks. The SageMath chapters use SageMath’s built-in algebraic and number-theoretic tools.