Chapter 1 — Introduction to Cryptography

Cryptography is the science of secret writing — the discipline that lets two parties communicate so that an adversary listening on the channel cannot read the message, cannot alter it without being detected, and cannot impersonate either party. It is older than the alphabet most languages use today, and it is more important to a modern digital economy than any other branch of mathematics in practical use. Every HTTPS connection, every eSewa payment, every Khalti OTP, every WhatsApp message, every Telegram channel, every banking-app login, every signed driver update on a Windows laptop in Nepal rests on cryptography. This chapter establishes the field — where it came from, the vocabulary that the rest of the subject depends on, the foundational principle (Kerckhoff's law) under which modern cryptosystems are designed, the special class of zero-knowledge proofs, the four classical goals the field is trying to achieve, the classical ciphers that show what fails when those goals are pursued naively, and the cryptanalysis techniques used to break them.

1.1 History and evolution of cryptography

The history is usually told in three eras — classical, mechanical, and modern. Each era was defined by the tools available to the cryptographer and the cryptanalyst, and each transition happened because the previous era's systems collapsed in a way that demanded something fundamentally new.

The classical era (c. 1900 BCE — c. 1900 CE)

The oldest documented encryption is on an Egyptian tomb wall from around 1900 BCE, where the scribe used non-standard hieroglyphs in place of the usual ones — likely for ceremony rather than secrecy, but the technique is unmistakable. Around 600 BCE the Spartans used the scytha — a rod of a particular diameter around which a strip of parchment was wound, and the message written along the rod. The message could be read only when wound around another rod of the same diameter. This is the first known transposition cipher.

The first cipher named after its inventor is the Caesar cipher, used by Julius Caesar around 50 BCE for military dispatches. Each letter of the message was replaced by the letter three positions later in the alphabet — A became D, B became E, and so on. It was effective only because most of Caesar's enemies were illiterate.

The Arab scholar al-Kindi, working in 9th-century Baghdad, wrote the first known treatise on cryptanalysis. He observed that letters in any natural language appear with characteristic frequencies — E is the most common letter in English, T the second most common — and that a substitution cipher preserves these frequencies. Counting letter frequencies in the ciphertext therefore reveals the substitution. This is frequency analysis, and it broke the Caesar cipher and every monoalphabetic substitution that followed.

The European Renaissance produced the polyalphabetic cipher, defended by Alberti (1467), refined by Trithemius and finally by Blaise de Vigenère in 1586. The Vigenère cipher uses a keyword to choose a different Caesar shift for each successive letter of the plaintext, defeating simple frequency analysis. It was called the chiffre indéchiffrable — the unbreakable cipher — for nearly three centuries. Then in 1854 Charles Babbage broke it (his work was kept secret), and independently in 1863 Friedrich Kasiski published the method. Frequency analysis still worked, just on each position of the keyword's cycle separately.

The 19th century also gave us the Playfair cipher (Charles Wheatstone, 1854), used by the British in the Boer War and the First World War. The cipher operated on pairs of letters via a 5×5 grid, partially obscuring single-letter frequencies. The 1880s saw the first treatments of cryptography as a mathematical subject, including Kerckhoffs's principle (1883), which we cover in Section 1.3.

The mechanical era (c. 1900 — 1945)

The First and Second World Wars industrialised cryptography. The volume of military traffic — radio communications, telegraphs, naval signals — was too high for hand ciphers. Cryptographers built machines.

The most famous is the German Enigma machine, designed by Arthur Scherbius in 1918, adopted by the German military in the 1920s. Enigma was a polyalphabetic cipher implemented by rotors — three or four spinning discs that scrambled the alphabet at each keystroke. The key space was around $10^{114}$ for the full naval Enigma. Yet Enigma fell, broken first by Polish mathematicians (Marian Rejewski, Jerzy Różycki, Henryk Zygalski) in the early 1930s and then on industrial scale by the British Government Code and Cypher School at Bletchley Park under Alan Turing's intellectual leadership. The break depended partly on cryptographic flaws (a letter could never encipher to itself, plaintext was often predictable), partly on operational errors by the Germans, and partly on the mechanical computers (the "Bombe") Turing's team built to test rotor settings. The work was kept secret until the 1970s; estimates suggest it shortened the European war by one to two years.

The Allies had their own machines — the British TypeX, the American SIGABA (which the Germans and Japanese never broke), the Japanese Purple (which the Americans broke and read throughout the war). The Soviets used one-time pads heavily; American codebreakers in the VENONA project later broke fragments of Soviet traffic where the same pad had been used twice — a violation of the one-time-pad's only security requirement, as Chapter 2 will show.

The modern era (1945 — present)

Three milestones define the modern era.

Shannon, 1949. Claude Shannon's paper Communication Theory of Secrecy Systems gave cryptography a mathematical foundation. Shannon defined perfect secrecy (the ciphertext gives no information about the plaintext), proved that perfect secrecy requires a key as long as the message (the one-time pad), and introduced confusion and diffusion as the two design principles for practical ciphers.

The publication of DES, 1977. The US National Bureau of Standards (now NIST) published the Data Encryption Standard, the first publicly specified, widely deployed cipher. DES used a 56-bit key and a 64-bit block, with a structure (the Feistel network) that became the template for the next two decades of block-cipher design. Cryptography moved from a military and diplomatic secret to a public engineering discipline.

Public-key cryptography, 1976. Whitfield Diffie and Martin Hellman's paper New Directions in Cryptography proposed that two parties could agree on a shared secret over a public channel — without ever exchanging it. The construction (Diffie-Hellman key exchange) was the first published example. Ron Rivest, Adi Shamir, and Leonard Adleman followed in 1977 with RSA, the first practical public-key encryption and signature system. These ideas had been independently discovered at GCHQ in the UK by James Ellis, Clifford Cocks, and Malcolm Williamson between 1969 and 1973, but their work was classified until 1997. The 1976–77 breakthrough turned cryptography into something that could secure commerce, banking, and consumer software, not just military communications.

Three further milestones from 1990 to the present:

• AES, 2001. The Advanced Encryption Standard replaced DES after a five-year open competition. AES is the worldwide default for symmetric encryption in 2026.
• TLS, mid-1990s onwards. Netscape's SSL (1995), then the IETF's TLS (1999, then 1.1, 1.2, 1.3 in 2018) made encrypted Internet communication universal. Over 95% of web traffic globally is now TLS-encrypted.
• The NIST post-quantum standardisation, 2016–2024. With large quantum computers in long-term view, NIST ran an open competition to select cryptographic algorithms believed secure against quantum attack. The first standards — ML-KEM (FIPS 203), ML-DSA (FIPS 204), and SLH-DSA (FIPS 205) — were published in August 2024.

The arc of the modern era is clear: cryptography became public, became mathematical, and became infrastructure. It is no longer the preserve of governments. A teenager in Bharatpur can use the same algorithms that protect classified diplomatic cables.

1.2 Basic cryptographic terminologies and concepts

The vocabulary in this section is non-negotiable. Every later chapter assumes it.

The cast of characters

The literature uses fixed names for the parties in any cryptographic scenario:

• Alice — the sender of a message.
• Bob — the intended recipient.
• Eve — a passive eavesdropper who listens but does not modify.
• Mallory — an active attacker, the malicious adversary, who can also modify, inject, and delete messages.
• Trent — a trusted third party.
• Carol, Dave — additional honest parties in multi-party scenarios.

These names are standard in textbooks and academic papers. A descriptive answer that names the parties is taken more seriously than one that uses bare letters.

Plaintext, ciphertext, and the encryption function

The plaintext is the message in its original, readable form. The ciphertext is the same message after it has been transformed by an encryption algorithm. The encryption function takes a plaintext and a key and produces a ciphertext; the decryption function takes a ciphertext and a key and recovers the plaintext.

Formally:

$$C = E_K(P) \quad \text{and} \quad P = D_K(C)$$

where $P$ is the plaintext, $C$ is the ciphertext, $K$ is the key, $E$ is the encryption function, and $D$ is the decryption function. For a correctly designed scheme, $D_K(E_K(P)) = P$ for all valid $P$ and $K$.

Symmetric vs asymmetric keys

A symmetric (or secret-key) cryptosystem uses the same key for encryption and decryption. An asymmetric (or public-key) cryptosystem uses a pair of related keys — a public key, which anyone may know, and a private key, which only the owner holds.

In a symmetric system, the key must be shared between Alice and Bob before they communicate. The challenge is how to share it securely. In an asymmetric system, Alice can encrypt a message to Bob using Bob's public key, which she can look up freely; only Bob's private key can decrypt it.

Symmetric ciphers are fast — typically several orders of magnitude faster than asymmetric ciphers. Real systems use both: asymmetric cryptography to establish a fresh symmetric key (the "session key"), then symmetric encryption for the bulk traffic. TLS, SSH, and IPsec all follow this pattern.

Block ciphers and stream ciphers

A block cipher processes plaintext in fixed-size blocks (typically 64 or 128 bits) and applies a key-dependent transformation to each block. AES is a block cipher with 128-bit blocks.

A stream cipher generates a key-dependent pseudorandom stream of bits and XORs it bit-by-bit (or byte-by-byte) with the plaintext. RC4 is a classical stream cipher; ChaCha20 is a modern one.

Block ciphers are more common in practice because they support a wider range of operational modes; stream ciphers tend to be used where their speed and the simplicity of XOR matter (older mobile networks, some lightweight IoT contexts).

Keys, key space, and key length

The key space of a cryptosystem is the set of all possible keys. The key length, expressed in bits, determines the size of the key space — a $k$-bit key gives $2^k$ possible keys.

Key length matters because the simplest attack on any cryptosystem is to try every possible key — brute force. A 56-bit key (DES) gives $2^{56} \approx 7.2 \times 10^{16}$ keys; modern hardware can search this space in hours. A 128-bit key gives $2^{128} \approx 3.4 \times 10^{38}$ keys; even with all of humanity's computing power, this would take longer than the age of the universe.

Length thresholds in current use:

• Symmetric ciphers: 128 bits is the floor; 256 bits is the long-term standard.
• RSA: 2048 bits is the current minimum; 3072 or 4096 bits for long-term security.
• Elliptic-curve cryptography: 256-bit curves give security comparable to 128-bit symmetric and 3072-bit RSA. P-256 (NIST), Curve25519, and Curve448 are the current standards.

Cryptographic primitives, schemes, and protocols

These three words mean different things:

• A primitive is a basic cryptographic building block. AES is a primitive. SHA-256 is a primitive. RSA is a primitive.
• A scheme combines primitives into something more useful. AES-GCM is a scheme that uses AES as its primitive and provides authenticated encryption. RSA-OAEP is a scheme for public-key encryption built from RSA.
• A protocol is a sequence of messages between two or more parties that uses schemes to achieve a goal. TLS is a protocol. IKEv2 is a protocol. The Diffie-Hellman exchange is a protocol.

A protocol can be secure only if its underlying schemes are secure, and the schemes can be secure only if their underlying primitives are. Errors at any layer break the whole stack.

Other essential terms

• Cryptosystem — a complete scheme, including key generation, encryption, decryption, and any associated parameters.
• Cipher — used interchangeably with cryptosystem in informal contexts; more strictly, refers to the algorithm itself.
• Key schedule — the algorithm that expands a master key into the per-round subkeys a block cipher needs.
• Nonce — a number used once, typically to ensure that encrypting the same plaintext twice produces different ciphertexts.
• IV (Initialisation Vector) — a non-secret random or pseudorandom value used by certain modes of operation to randomise the encryption.
• Salt — a random value added to a password before hashing, to prevent precomputed-table attacks (Chapter 3).
• Pad — extra data added to a plaintext to make its length match the block size.
• Padding oracle — an attack class against schemes that reveal whether padding is valid; the source of the 2014 POODLE attack on SSL 3.0 and many other practical breaks.
• MAC (Message Authentication Code) — a short tag computed from a message and a shared secret, used to verify authenticity and integrity. HMAC is the standard construction.
• Digital signature — the asymmetric analogue of a MAC; Alice signs a message with her private key, anyone can verify with her public key.
• One-way function — a function easy to compute in one direction, computationally infeasible to invert. Hash functions and public-key operations both rest on one-way functions.
• Trapdoor function — a one-way function that is easy to invert if you have a secret (the trapdoor). RSA is built on a trapdoor function.
• Negligible probability — a probability that decreases faster than any inverse polynomial in the security parameter. In modern cryptography, we accept "secure" to mean "any attacker has only negligible probability of success."

1.3 Kerckhoffs's law (Kerckhoff's principle)

Kerckhoffs's principle is the foundational design rule of modern cryptography, stated by Auguste Kerckhoffs in 1883, that a cryptosystem must remain secure even if everything about the system except the key is publicly known.

Auguste Kerckhoffs was a Dutch linguist and cryptographer who published a series of articles on military cryptography in the Journal des Sciences Militaires in January and February 1883. He listed six design requirements for a practical military cipher. The second of these — that the system should not require secrecy, and would not be a problem if it fell into enemy hands — is the principle that bears his name.

In modern phrasing: the algorithm is public, only the key is secret.

Why the principle matters

Several practical reasons make Kerckhoffs's principle essential.

Algorithms cannot stay secret. A cipher used in any real deployment will, eventually, be reverse-engineered. Cipher hardware can be captured. Software can be decompiled. Engineers leave. Specifications leak. Once the algorithm is known, a cipher that depended on secrecy of its algorithm is broken.

Public review catches mistakes. A cipher that thousands of cryptographers have examined is more trustworthy than one that the inventor reviewed alone. AES was selected after a five-year open competition with submissions from around the world; every candidate was attacked publicly. The selected design (Rijndael) was the one that survived.

Keys are easier to manage than algorithms. A key is a few hundred or few thousand bits; it can be replaced. An algorithm, once embedded in deployed devices, is much harder to change. Tying security to the key, which is replaceable, is more robust than tying it to the algorithm.

Standardisation and interoperability. Two parties using the same standard algorithm can communicate even if neither trusts the other beyond the standard. Telephones, web browsers, banking systems, government communications all rely on this property.

Shannon's restatement

Claude Shannon, in his 1949 paper, restated Kerckhoffs's principle as: the enemy knows the system. This formulation is now part of the standard cryptographic worldview. Any modern cryptosystem is designed under the assumption that the attacker has read the specification, knows the implementation, and possibly possesses the same hardware. The only thing the attacker does not have is the key.

Violations and the term "security through obscurity"

A system that relies on the secrecy of its algorithm rather than on the strength of its keys is said to depend on security through obscurity. This is a term of disapproval in the cryptographic community, and the literature is full of examples that demonstrate why.

A5/1, A5/2 (GSM voice encryption). The cellular encryption algorithms that protected GSM voice calls from the late 1980s onwards were kept secret. They were eventually reverse-engineered in 1999, and the cryptanalytic weaknesses were publicly described shortly after. A5/1 was broken in real time on cheap hardware by 2009; A5/2 had been deliberately weakened for export and was breakable in milliseconds.

Mifare Classic (contactless smart cards). The Crypto-1 cipher used in millions of building-access cards, transit cards, and proximity tokens was proprietary and kept secret. Reverse-engineering in 2007–2008 by researchers at Radboud University exposed multiple weaknesses, and the cipher fell rapidly. Every Mifare Classic-protected card became cloneable with cheap equipment.

DVD CSS (Content Scramble System). The encryption protecting DVDs from unauthorised copying used a 40-bit key and an undisclosed cipher. The cipher was reverse-engineered in 1999, the key length was insufficient anyway, and decryption tools became widely available.

Many vendor-proprietary "encryption" products through the 1990s and 2000s. The pattern was the same: marketing claimed strong protection, the algorithm was secret, independent analysis was forbidden, and a few years later the system was broken.

The lesson is uniform. Designs that depend on the algorithm staying secret fail when the algorithm becomes known, and the algorithm always becomes known. The only designs that survive are the ones built under Kerckhoffs's principle.

What Kerckhoffs's principle does not say

Kerckhoffs does not say that every implementation detail must be published. It says that security must not depend on keeping them secret. An operator may not publish their device's key derivation parameters, may keep their hardware tamper-resistant, may decline to disclose specific deployment details. None of this violates Kerckhoffs as long as the security guarantee would still hold if those details were public.

The distinction is between "secret as a defence in depth" — fine, possibly useful — and "secret as the load-bearing wall of the security" — not fine, will fail.

1.4 Zero-knowledge proof

A zero-knowledge proof is a cryptographic protocol in which one party, the prover, convinces another party, the verifier, that a statement is true, without revealing any information about why the statement is true beyond the fact of its truth.

The concept was introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in 1985. Their paper The Knowledge Complexity of Interactive Proof Systems defined zero-knowledge formally and proved that many useful statements have zero-knowledge proofs. The work earned Goldwasser and Micali the Turing Award in 2012.

What a zero-knowledge proof must satisfy

A zero-knowledge proof for a statement $S$ must have three properties:

Completeness. If $S$ is true and the prover follows the protocol, the verifier always accepts.

Soundness. If $S$ is false, then no prover (no matter how clever or computationally powerful, depending on the strength of the soundness definition) can convince an honest verifier to accept, except with negligible probability.

Zero-knowledge. Whatever the verifier learns from the interaction, the verifier could have produced without talking to the prover — meaning the interaction reveals nothing beyond the bare truth of $S$.

The zero-knowledge property is formalised through a simulator: a hypothetical algorithm that, given only the statement $S$, can produce a transcript indistinguishable from a real proof transcript. Since the simulator does not know the secret, anything in the transcript that the simulator can produce cannot have revealed the secret.

The Ali Baba cave — a classical illustration

The classical worked example, from Jean-Jacques Quisquater's 1990 paper, is the Ali Baba cave. The cave is shaped like a ring with a magic door at the back that opens only with a secret word. Peggy claims to know the word and wants to prove it to Victor without telling him what it is.

The protocol:

1. Victor waits outside while Peggy enters the cave and randomly chooses one of the two paths (left or right).
2. Victor enters to the fork and shouts which path he wants Peggy to come back from.
3. If Peggy has the word, she can come back from either side (passing through the magic door if necessary). If she does not have the word, she can only come back from the side she entered, so she succeeds with probability 1/2.
4. Repeat $n$ times. If Peggy succeeds every time, the probability she does not have the word is $1/2^n$ — for $n = 40$ this is about $10^{-12}$, negligible.

This shows all three properties:

• Completeness. A real Peggy succeeds every time.
• Soundness. A fake Peggy succeeds with probability $1/2^n$, which goes to zero.
• Zero-knowledge. Victor sees only that Peggy comes back from the requested side. He learns nothing about the magic word; in particular, he could simulate the whole transcript himself by deciding in advance which side Peggy will come from, recording it, and showing it to someone else, who would not be able to tell whether it was a real transcript or a faked one.

Zero-knowledge in modern systems

The cave is a teaching example. Real ZK protocols use number-theoretic constructions. Several modern systems use them at scale.

Identification and authentication. The Schnorr identification scheme is a discrete-log-based ZK proof of knowledge of a private key. The Feige-Fiat-Shamir scheme, based on quadratic residues, was an early ZK identification.

zk-SNARKs and zk-STARKs. A zk-SNARK (Zero-Knowledge Succinct Non-interactive Argument of Knowledge) is a ZK proof that is short (kilobytes), fast to verify, and does not require interaction after a one-time setup. zk-STARKs avoid the setup phase and are post-quantum-secure but produce larger proofs. Both are used in privacy-preserving blockchains, anonymous credentials, and confidential computation systems. Zcash (since 2016), Ethereum L2 rollups like zkSync and StarkNet, and several confidential-transaction systems use SNARKs or STARKs in production.

Anonymous credentials. Systems like Microsoft U-Prove and IBM Idemix let a user prove they hold a credential satisfying certain conditions (e.g., "I am over 18") without revealing the credential itself.

Privacy-preserving authentication. Modern proposals for digital identity — the EU Digital Identity Wallet, several national e-ID systems — use ZK proofs to let a user authenticate to a service while disclosing only what is strictly necessary.

Why ZK matters

Zero-knowledge captures a counter-intuitive but practically essential idea: it is possible to convince someone of something without giving them the means to convince anyone else. In an age of pervasive data collection, the ability to prove facts without yielding the underlying information is one of the most important cryptographic primitives we have.

1.5 Goals of cryptography: confidentiality, integrity, authentication, non-repudiation

The four goals are the canonical objectives cryptography seeks to achieve. A secure system usually needs more than one of them at once, but it is useful to define them separately because the cryptographic mechanisms that provide each are different.

Confidentiality

Confidentiality is the property that information is not disclosed to unauthorised parties; in cryptographic terms, that the ciphertext reveals no useful information about the plaintext to anyone without the decryption key.

Confidentiality is what most people associate with cryptography — keeping secrets secret. It is achieved by encryption. Examples in the Nepali context:

• TLS protects the contents of a session between an eSewa user and the eSewa server. Anyone intercepting the traffic — a malicious Wi-Fi access point at a Thamel café, an ISP technician with packet-capture tools — sees only ciphertext.
• An IPsec tunnel between a head office in Kathmandu and a branch in Pokhara protects all traffic flowing between them.
• Disk encryption on a journalist's laptop protects the contents if the laptop is seized.

Confidentiality alone is not enough. An attacker who cannot read the message can sometimes still modify it usefully, can replay an old message, or can impersonate one of the parties. The other three goals address these.

Integrity

Integrity is the property that information has not been altered in an unauthorised or undetected way; in cryptographic terms, that the recipient can verify the message they received is exactly what the sender sent.

Integrity is achieved by message authentication codes (MACs), digital signatures, or authenticated encryption modes. A bare encryption scheme often provides confidentiality without integrity — and the gap is dangerous.

A canonical example: an attacker who knows the structure of an encrypted bank transfer instruction can sometimes flip specific ciphertext bits to change the amount or the destination account, even without being able to decrypt the message. The famous POODLE attack and the Bit-Flipping attacks on CBC-encrypted-without-MAC traffic are real demonstrations of this.

Modern systems use authenticated encryption modes — AES-GCM, ChaCha20-Poly1305 — that provide both confidentiality and integrity in a single operation. TLS 1.3 only allows authenticated-encryption modes.

Authentication

Authentication is the property that the recipient can verify the identity of the sender; in cryptographic terms, that the message came from the claimed source and not from someone impersonating them.

Authentication is achieved by digital signatures (for public-verifiability), MACs (for shared-secret verifiability), or password-based or certificate-based mechanisms in protocols.

There are two related but distinct kinds:

Entity authentication. Confirming who you are talking to right now. The TLS handshake authenticates the server (via its certificate) before any application data is sent. Mutual TLS additionally authenticates the client.

Data origin authentication. Confirming that a piece of data was produced by a specific source. A signed software update is authenticated as coming from the vendor — the signature on the update file is checked against the vendor's public key embedded in the operating system.

Authentication and integrity are often achieved by the same mechanism (a signature verifies both that the message has not been altered and that it came from the signer), but they are conceptually distinct.

Non-repudiation

Non-repudiation is the property that the sender of a message cannot later credibly deny having sent it; in cryptographic terms, that the recipient can prove to a third party that the message originated with the claimed sender.

Non-repudiation requires digital signatures. A MAC does not provide non-repudiation, because both sides hold the same key — either could have produced the MAC, so neither can prove to a third party that the other did.

Use cases where non-repudiation matters:

• Signed contracts. A digitally signed contract can be shown to a court; the signer cannot later deny signing without breaking the underlying cryptography.
• Signed transactions. A Bitcoin transaction is signed with the spender's private key; the spender cannot deny having authorised it.
• Signed software releases. A vendor signs each release; the vendor cannot later deny having published a specific version.
• Audit trails in regulated industries. Banking, healthcare, and government systems often require signed log entries that the operator cannot subsequently alter or deny.

Non-repudiation has limits. A signer can argue that their key was stolen and used by someone else; the cryptography proves only that the right key was used, not that the right person used it. Operational practices around key management (Chapter 4) determine how strong the legal non-repudiation actually is.

The four goals together

Most real systems need more than one goal. A typical interaction — say, a user submitting a digitally signed payment instruction to a bank — needs all four:

• Confidentiality. Other parties on the network must not see the instruction.
• Integrity. The bank must detect any modification of the instruction.
• Authentication. The bank must verify the instruction came from the legitimate user.
• Non-repudiation. Later, if the user disputes the payment, the bank must be able to show a signed instruction the user cannot disown.

A few common additional goals are sometimes added:

• Availability — the service is reachable when needed. Cryptography helps (by defending against tampering and denial of service), but availability is largely a systems and network problem.
• Authorisation — the user is allowed to do what they are trying to do. This is policy, not pure cryptography.
• Forward secrecy — even if long-term keys are later compromised, previously recorded sessions cannot be decrypted. Achieved by ephemeral key exchanges (TLS 1.3, Signal protocol).
• Privacy — beyond confidentiality of the message contents, hiding metadata about who is communicating with whom and when. Tor, mixnets, and anonymous-credential systems address this.

1.6 Classical cryptography: substitution and transposition ciphers

The classical ciphers are studied not because anyone uses them today, but because they show how each goal fails when pursued naively, and they introduce the cryptanalytic techniques that the rest of the field is built on.

Two categories cover almost all classical ciphers: substitution (each letter or block of letters is replaced by another) and transposition (the letters are rearranged but their identities are preserved).

Substitution ciphers

The Caesar cipher. Each letter shifts by a fixed number of positions in the alphabet. With shift 3, HELLO becomes KHOOR. The key space is 25 (shifts 1 to 25; shift 0 would give plaintext). A brute-force search through 25 keys reveals the message. The Caesar cipher is the simplest possible monoalphabetic substitution.

General monoalphabetic substitution. Replace each letter with another according to a fixed permutation of the alphabet. The key space is $26! \approx 4 \times 10^{26}$. Brute force is impossible. But frequency analysis is straightforward: E is the most common letter in English (about 12%), T is next (about 9%), A and O next (about 8% each), and so on. The most common ciphertext letter is likely the substitute for E; the second most common is likely for T. Bigram and trigram frequencies (TH is the most common pair; THE is the most common triple) further reduce the search. A short ciphertext of a few hundred letters can be broken in under an hour by hand.

Polyalphabetic substitution — the Vigenère cipher. A keyword chosen from the alphabet provides different Caesar shifts for successive letters of the plaintext.

Suppose the keyword is KEY and the plaintext is HELLO:

Plaintext:  H E L L O
Keyword:    K E Y K E
Shift:      10 4 24 10 4
Ciphertext: R I J V S

(H shifted by 10 is R; E shifted by 4 is I; and so on.)

The Vigenère cipher defeats simple frequency analysis because the same plaintext letter encrypts to different ciphertext letters in different positions. But the attack of Kasiski (1863) and Babbage (1854, kept secret) exploits the fact that the same plaintext bigram, encrypted at positions that happen to align with the same place in the key cycle, gives the same ciphertext bigram. By looking for repeated ciphertext substrings and measuring the distances between them, the cryptanalyst recovers the key length. Once the key length is known, the ciphertext can be broken into groups (every 1st letter, every 2nd, every 3rd, ... up to the key length) and frequency analysis applied to each group separately.

The index of coincidence (Friedman, 1922) provides a statistical method for estimating the key length without needing repeated substrings.

The Playfair cipher. Wheatstone's invention, used by the British military through the early 20th century. The key is a 5×5 grid filled with the alphabet (I and J share a cell). The plaintext is divided into pairs of letters. Each pair is encrypted according to its position in the grid:

• If both letters are in the same row, replace each with the letter to its right (wrapping around).
• If both letters are in the same column, replace each with the letter below it (wrapping around).
• Otherwise, replace each letter with the letter at the corner of the rectangle they form, on its own row.

Playfair defeats single-letter frequency analysis (because it works on pairs), but bigram frequency analysis still works — TH and HE are still the most common bigrams in English plaintext, and they will leave statistical traces in Playfair ciphertext.

The Hill cipher (Lester Hill, 1929). Treats blocks of letters as vectors of numbers (A = 0, B = 1, ..., Z = 25) and multiplies by an invertible matrix modulo 26. The matrix is the key. The Hill cipher was the first cipher to handle blocks larger than two letters using algebra — a forerunner of modern block-cipher design. It is broken by a known-plaintext attack: given enough plaintext-ciphertext pairs, the matrix can be recovered by solving a linear system.

Transposition ciphers

A transposition cipher rearranges the plaintext letters without changing them.

The rail fence cipher. Write the plaintext in a zig-zag pattern across some number of "rails," then read off the ciphertext row by row. With three rails and the plaintext WE ARE DISCOVERED FLEE AT ONCE:

W . . . E . . . C . . . R . . . L . . . T . . . E
. E . R . D . S . O . E . E . F . E . A . O . C .
. . A . . . I . . . V . . . D . . . E . . . N . .

Reading off: WECRLTE ERDSOEEFEAOC AIVDEN. The key is the number of rails.

Columnar transposition. Write the plaintext into a rectangular grid row by row. The key is a permutation of the column numbers. Read off the columns in the permuted order to produce the ciphertext.

Transposition ciphers leave the letter frequencies of the plaintext intact in the ciphertext (since they only rearrange, not substitute). This makes them recognisable — a ciphertext whose letter frequencies match English plaintext frequencies is likely a transposition cipher.

Attacks on transposition ciphers exploit either knowledge of likely plaintext (cribs — "the message probably starts with DEAR SIR") or the constraints that valid plaintext blocks must satisfy (English text has structure that random text does not).

Combined ciphers and the lesson of classical cryptography

The most sophisticated classical ciphers combined substitution and transposition. The ADFGVX cipher used by Germany in 1918 first substituted (replacing each letter with a pair from the set A, D, F, G, V, X) and then transposed the resulting digraphs. It was broken by the French cryptanalyst Georges Painvin during the war, in a feat of analysis the field still admires.

The lesson from classical cryptography is that simple, individually-weak operations can be combined in ways that are stronger than the parts — if the combination is well-designed. Shannon's later formalisation of confusion (making the relationship between key and ciphertext complex; substitution provides this) and diffusion (spreading the influence of each plaintext bit across many ciphertext bits; transposition provides this) reflects exactly this insight. Every modern block cipher, including AES, is built on combined confusion-and-diffusion rounds.

1.7 Cryptanalysis techniques

Cryptanalysis is the study of techniques for analysing cryptographic systems with the goal of recovering the plaintext, the key, or the secret algorithm, given the ciphertext and possibly some additional information.

The discipline classifies attacks by what the attacker has access to, and by what the attacker is trying to learn.

Attack models — what the attacker knows

The standard models, in order of increasing attacker power:

Ciphertext-only attack (COA). The attacker has only ciphertexts. This is the weakest attack model and the most realistic for an eavesdropper without any other access. Any cipher that fails to a ciphertext-only attack is severely broken. Frequency analysis on a monoalphabetic substitution is the canonical example.

Known-plaintext attack (KPA). The attacker has some plaintext-ciphertext pairs, plus other ciphertexts encrypted under the same key. The attacker wants to recover the key or to decrypt the other ciphertexts. Often the attacker knows fragments of the plaintext (a standard greeting, a header, a known file format) without seeing the whole. The break of Enigma at Bletchley exploited known plaintext — the German weather reports always started with similar words.

Chosen-plaintext attack (CPA). The attacker can choose plaintexts and obtain the corresponding ciphertexts. This models a situation where the attacker can inject messages that the victim then encrypts — for example, a website that takes user input and encrypts it before storing. The differential cryptanalysis of DES (Biham and Shamir, 1990) is a chosen-plaintext attack.

Chosen-ciphertext attack (CCA). The attacker can choose ciphertexts and obtain the corresponding plaintexts (or some information about them — typically whether the decryption succeeds). This models situations like padding-oracle attacks, where the attacker submits ciphertexts to a decryption oracle and learns whether the padding was valid. Bleichenbacher's 1998 attack on RSA-PKCS#1v1.5 is a chosen-ciphertext attack that broke real TLS implementations.

Adaptive chosen-ciphertext attack (CCA2). The attacker's choice of ciphertext can depend on the answers to previous queries. This is the strongest standard attack model and the security target for modern asymmetric encryption schemes.

A modern cryptosystem is expected to be secure under at least IND-CPA (indistinguishability under chosen-plaintext attack) and ideally IND-CCA2 (indistinguishability under adaptive chosen-ciphertext attack).

Attack methods — how the attacker breaks the cipher

Brute force (exhaustive search). Try every key in the key space. The attack always works given enough time; the question is whether the key space is too large for the available computing power. A 56-bit key (DES) can be brute-forced in hours on a modern GPU farm. A 128-bit key cannot be brute-forced in the lifetime of the universe with current technology.

Frequency analysis. Exploiting the non-uniform distribution of letters, bigrams, and trigrams in natural language. Effective against simple substitution ciphers. The al-Kindi technique.

Kasiski examination and index of coincidence. Techniques for breaking polyalphabetic ciphers by recovering the key length, then reducing to monoalphabetic substitution.

Known-plaintext linearisation. Given enough plaintext-ciphertext pairs, recover the key by solving a system of equations. Effective against the Hill cipher and many algebraic ciphers.

Differential cryptanalysis. Discovered (in the public literature) by Eli Biham and Adi Shamir in the late 1980s. The attacker submits pairs of plaintexts with a chosen difference and observes the resulting ciphertext differences. Patterns in the output differences leak information about the key. DES turned out to have been designed by IBM and the NSA in the 1970s with internal knowledge of this attack — the S-boxes were chosen to resist it — and the attack only became public later.

Linear cryptanalysis. Mitsuru Matsui, 1993. Finds linear approximations of the cipher's operation that hold with probability slightly different from 1/2. With enough known plaintext-ciphertext pairs, the bias reveals the key. Linear cryptanalysis was the first attack to recover a DES key faster than brute force, requiring $2^{43}$ known plaintexts.

Meet-in-the-middle attacks. A time-memory trade-off attack against ciphers composed of two operations with independent keys. The attacker computes possible intermediate values from each end and looks for matches. The classical application is to break 2DES — even though 2DES has effectively a 112-bit key, a meet-in-the-middle attack reduces the work to about $2^{57}$, only twice the work of breaking DES.

Birthday attacks. Based on the birthday paradox — in a room of 23 people, two share a birthday with probability over 50%. For a hash function with $n$-bit output, finding a collision takes about $2^{n/2}$ work, not $2^n$. This is why a hash function with 128-bit output gives only 64-bit collision resistance — the practical reason SHA-1 (160-bit) was deprecated and SHA-256 became the standard.

Side-channel attacks. Exploiting information leaked by the implementation rather than the algorithm. Categories include:

• Timing attacks. The time taken by a cryptographic operation can depend on the secret key — for example, branch decisions in a non-constant-time implementation. Paul Kocher's 1996 paper showed RSA could be broken by carefully timing decryption operations.
• Power-analysis attacks. The instantaneous power consumption of a cryptographic processor depends on what bits it is processing. Simple power analysis (SPA) reads the key by inspecting a single trace; differential power analysis (DPA) extracts secrets by statistical analysis of many traces.
• Cache attacks. Modern CPUs share caches between processes. The pattern of cache hits and misses while a victim performs cryptography can leak secrets. The 2018 Spectre and Meltdown vulnerabilities are extreme examples.
• Electromagnetic emanation attacks. The electromagnetic signals radiated by a device during cryptographic operation can be picked up at a distance and used to recover keys.
• Acoustic attacks. The sound a CPU makes during operation has been used to recover RSA keys (Genkin, Shamir, Tromer, 2014).

Fault attacks. Inducing a fault in the cryptographic computation — by glitching the clock, by laser, by voltage manipulation — and analysing the resulting incorrect output. A single faulty RSA-CRT signature reveals the private key.

Social-engineering attacks. Often the most effective. The attacker convinces a human to reveal the key, or to install software that will steal it, or to use a weak password. Cryptography cannot defend against human compromise on its own.

What "broken" means

In the cryptographic literature, a cipher is considered "broken" if any attack works faster than brute force, even by a small amount. This is a much stricter standard than practical brokenness.

• A theoretical attack with $2^{120}$ work on a 128-bit cipher is a "break" but does not threaten practical deployments.
• A practical attack with $2^{40}$ work is a serious problem and the cipher should not be used.
• A real-time attack on commodity hardware is a catastrophe.

The standard descriptive answer when discussing the strength of a cipher should distinguish among these.

Modern cryptanalysis as an industry

Cryptanalysis today is done in academic research, in industrial security teams (Google Project Zero, Microsoft Security Response Center, Apple's security engineering, NSA's cryptanalytic division and its global counterparts), and in publicly published competitions. The annual CRYPTO, EUROCRYPT, ASIACRYPT, CHES, TCC, and FSE conferences publish the best of public cryptanalytic research. The NIST hash, AES, and post-quantum competitions have been the largest organised cryptanalytic efforts of the public era.

For an MSc student in cybersecurity, the working knowledge to carry into Chapter 2 is: any cipher in serious use must be expected to face all of these attacks. The cipher's designers and the cryptographic community must have considered each one. A cipher's reputation is built only after years of public attack, and a cipher's deployment is justified only when that reputation has been earned.