Can Anyone Read This?

Suppose you want to send a friend a private message over the internet. Someone else may be able to copy the data as it travels. Encryption transforms the message before you send it; your friend uses a key to recover the original words. The aim is to let your friend read the message while keeping it private from someone who intercepts the data. This article explains what the key does, how the calculations work and why some methods protect a message while others fail.

You only need everyday arithmetic to begin. I explain fractions, powers, symbols, binary notation, arithmetic with remainders and probability as they appear. You don’t need a maths degree, programming experience or calculus. We use equations because guessing one key among a thousand possibilities is a different problem from guessing one among a billion. Numbers let us say how different.

The main explanation comes first, in words and diagrams. The worked calculations are there if you want to check the numbers; you can leave them closed and still follow why a method works or fails. If a symbol is unfamiliar, keep reading for what Alice, Bob and Eve actually do.

We start with simple ciphers, learn why they fail and build towards modern encryption. Public keys then let us ask how two people can communicate privately without first sharing a secret. Signatures and zero-knowledge proofs extend the question: what can one person convince another of, and what must they reveal? At each step, we check what the recipient can do and what an outsider could learn or change.

1. What does it mean to understand cryptography?

Alice wants to send Bob the words “pay ten pounds”. Someone else can copy the message while it travels between them. If Alice sends those words unchanged, that person can read the amount too.

Alice wants to send a different version of the message: one Bob can turn back into the original, while someone observing the exchange cannot discover the amount. How can Alice and Bob arrange that?

1.1 A message and an opponent

We shall call the observer Eve. Alice, Bob and Eve are conventional names in cryptography; they can stand for people or for their computers. Alice’s original message, “pay ten pounds”, is the plaintext. A plaintext can also be a photograph, a medical record or any other data.

Alice uses encryption to transform the plaintext into a ciphertext, which she sends to Bob. Bob uses decryption to recover the original message. Each procedure follows an algorithm: a precise set of steps for a calculation.

Encryption takes both the message and a key as inputs. The key is a value that determines how the algorithm transforms the message. For this first example, assume Alice and Bob already share a secret key. Bob uses it to decrypt the ciphertext. Eve may know the algorithm, but she does not have their key. We will examine how much this difference helps them.

Eve can observe the exchange. If she sees the ciphertext but cannot learn the amount Alice wants to pay, the exchange provides a form of confidentiality. Eve may still see who sent the message, when they sent it and roughly how long it was. Hiding the contents does not automatically hide the communication.

Suppose Eve can also change what Bob receives. Detecting a change from “pay ten pounds” to “pay ninety pounds” concerns integrity. Checking that Alice authorised the instruction concerns authenticity. We often need both. Neither follows from secrecy: some encryption methods let Eve make a predictable change to hidden contents without first reading them.

Eve could instead record Alice’s genuine instruction and send it again tomorrow. The contents and their source remain genuine, but Bob should not pay twice. This is a replay. Bob needs a way to tell a new instruction from an old one, such as a checked counter or a fresh challenge.

1.2 What an analogy can tell us

Picture Alice putting a message in a locked box and sending it through a place where strangers can inspect it. Bob holds a key. The box makes one useful distinction visible: an object can travel publicly while the means to open it stays secret. It also raises a practical question. How did Bob obtain his key?

Digital messages differ from boxes in ways that matter to an attacker. Eve can copy a ciphertext without taking the original away, keep it for years and test candidate keys later. She need not break a seal or leave evidence of the attempt. Our security argument must allow these actions.

A digital key can be copied too. Two computers can hold identical copies, each with the same mathematical effect. If Eve obtains a third copy, Alice’s and Bob’s copies still work. Successful decryption tells Bob that his key works; it does not tell him that nobody else has it.

We shall use physical pictures when they clarify a particular feature. To judge a security claim, though, we need rules about copying information, performing calculations and checking messages.

1.3 Correctness and security

Bob must get back exactly the message Alice sent. Using the same key to decrypt what she encrypted should restore her original message. That is correctness; it does not yet show that Eve cannot read it.

For example, Alice could add 1 to each number in a message and Bob could subtract 1. They would recover every message correctly. Eve, knowing the procedure, could subtract 1 as well. To claim security, we also need an argument about what Eve can learn or do with the information she has.

We shall normally assume that Eve knows the algorithm. Designers may publish it; users receive copies of programmes that implement it; attackers can inspect their behaviour. Relying on all these copies to remain mysterious makes a fragile secret. A programme can instead keep its key separate and replace that key when needed.

Eve may also know something about the message. A payment has predictable fields, and a picture file identifies its format. Alice should not have to invent unpredictable messages to communicate privately. Later we shall even let Eve obtain encryptions of messages she chooses and ask what protection remains for Alice’s other messages.

1.4 Certainty, evidence, and assumptions

With strict conditions on its key, a ciphertext can reveal no additional information about its fixed-length message, even to an attacker with unlimited computing power. We shall examine a method whose key contains as much fresh random information as its message and is never reused.

Most practical encryption offers a different kind of protection. Eve might be able to recover a message in principle, yet need more computation than she can carry out. To assess that claim, we must specify her resources and the assumptions behind the estimate. “Very difficult” gives us too little to check.

Those assumptions also mark the limits of a proof. A theorem about an algorithm does not prevent someone from stealing its key, introducing a programming error or persuading Bob to accept an impostor’s public key. We need to check both the construction and the system that uses it [1, 2].

For Alice’s payment, the questions are now concrete: can Eve read the amount, change it, impersonate Alice or make Bob pay twice? We shall build the mathematical tools needed to answer each question separately.

2. Some elementary mathematics

The string 1011 can represent the number eleven. A clock can turn eleven plus three into two. Neither calculation is difficult once you know the rule. Cryptography uses these ways of representing and manipulating numbers, along with a few rules for probability. We shall work through each before using it to encrypt a message.

2.1 Bits and binary numbers

A bit has one of two values, written 0 and 1. A sequence of bits is called a bit string. There are two one-bit strings, four two-bit strings, and eight three-bit strings: $$000,\quad001,\quad010,\quad011,\quad100,\quad101,\quad110,\quad111.$$ Each extra position doubles the number of possible strings, because either 0 or 1 can occupy it. There are therefore $2^n$ strings of length $n$. The expression $2^n$ means multiplying $n$ copies of 2. For three positions, that is 2 × 2 × 2 = 8 possible strings, exactly the eight listed above. This notation lets us count possible keys without listing them.

We can interpret a bit string as a number using binary notation. In ordinary decimal notation the positions, read from the right, stand for units, tens, hundreds, and so on. In binary they stand for 1, 2, 4, 8, and so on. Thus $$1011_2=1\times8+0\times4+1\times2+1\times1=11.$$ The small 2 marks binary notation. Leading zeroes do not change the number: $0011_2$ and $11_2$ both represent 3. They are nevertheless different strings, because one has four positions and the other two. We shall specify length when it matters. Eight bits make a byte, with $2^8=256$ possible values.

2.2 An operation which undoes itself

The operation exclusive OR, abbreviated XOR and written $\oplus$, takes two bits and returns 1 exactly when they differ: $$\begin{array}{c|cc} \oplus&0&1\\\hline 0&0&1\\ 1&1&0 \end{array}$$ For equal-length strings, perform the operation separately in each position. For example, $$\begin{array}{rcl} 101101& &\\[-2pt] 011010&\oplus&\\\hline 110111& & \end{array} \qquad\text{or, more briefly,}\qquad 101101\oplus011010=110111.$$ Unlike ordinary binary addition, XOR produces no carries between positions. In particular, $1\oplus1=0$, whereas adding the binary numbers 1 and 1 gives the binary number 10.

XOR has one especially useful property: applying the same key twice restores the original bits. This is why Bob can undo Alice’s encryption with the same key.

2.3 Remainders and clocks

If 17 objects are divided into groups of 5, there are three complete groups and 2 left over. We write $$17\bmod5=2.$$ The operation returns the remainder after division. We shall use non-negative remainders smaller than the number by which we divide. Arithmetic using these remainders is called modular arithmetic. A clock is a familiar example: three hours after 11 o’clock is 2 o’clock, because $11+3=14$ and $14\bmod12=2$.

Two integers are congruent modulo $n$ if division by $n$ gives the same remainder. The notation $$17\equiv2\pmod5$$ says that 17 and 2 differ by a whole multiple of 5. They are not equal as ordinary integers, but we can substitute one for the other when calculating remainders modulo 5.

We can reduce numbers along the way when adding or multiplying. To calculate $17\times19$ modulo 5, we could find the full product, 323, then take its remainder, 3. Or replace 17 by 2 and 19 by 4, multiply to get 8, then take its remainder, also 3. Keeping the intermediate numbers small saves work when the original numbers have hundreds of digits.

When we keep only remainders, ordinary division is not the right operation. Instead, we multiply by a number that undoes the earlier multiplication. For example, 7 multiplied by 15 leaves remainder 1 after division by 26, so 15 undoes multiplication by 7 in that setting. Some numbers have no such partner.

2.4 Powers without enormous intermediate numbers

Repeated squaring finds a large power without doing every multiplication in order. In the worked example, dividing 3 multiplied by itself thirteen times by 17 leaves remainder 12. The steps below show how smaller saved results lead to 12.

Each additional key bit doubles the possible keys. Ten extra bits multiply the number by about a thousand. This is why a small change in key length can make a very large difference to a brute-force search.

2.5 Probability and information

If a fair coin is tossed, each outcome has probability $1/2$. For two independent tosses, each particular ordered outcome, such as heads followed by tails, has probability $(1/2)(1/2)=1/4$. Independence means that learning one outcome does not change the probabilities of the other. A fair bit produced once and then copied twice gives three individually balanced bits, but only two possible strings, 000 and 111. Balanced positions are not enough to make a uniformly random string.

The conditional probability of an event is its probability after some information has been supplied. Suppose that a number is chosen uniformly from 1 to 6. Its probability of being 6 is $1/6$. If we learn that it is even, the remaining possibilities are 2, 4, and 6, so the conditional probability becomes $1/3$. In a secrecy question, the information supplied will often be a ciphertext. We ask whether learning it changes the probabilities of the possible messages.

Matches appear sooner than a single target guess suggests because every new value can match every earlier one. With 23 people, a shared birthday is already slightly more likely than not. The same effect matters for random nonces and hash outputs.

3. Ciphers that revealed the problem

Give each letter in HELLO a fixed substitute, and the double L still leaves a clue. Changing symbols can preserve the patterns that betray a message. Three simple ciphers will show why even a large collection of keys may fail to protect ordinary prose.

We shall use 26 capital letters and ignore spaces and punctuation. These choices make the calculations easy to follow. They also show that we must decide how to represent a message before we can encrypt it.

3.1 Moving along the alphabet

A shift cipher moves each letter the same number of places through the alphabet, wrapping after Z. Moving every letter three places turns HELLO into KHOOR; moving back three places restores it. Eve can try every possible shift.

Eve has only 26 possible shifts to try, including zero. Trying candidate keys directly is a brute-force attack. Several shifts might produce plausible readings of a very short message, but a longer piece of ordinary prose will usually reveal which shift Alice used.

Eve recognises the result because she knows something about the plaintext: Alice is more likely to send normal English than a random sequence of letters. For a uniformly chosen single letter, that clue disappears. We want encryption to protect Alice’s ordinary messages, including their predictable words.

3.2 Replacing every letter differently

A substitution cipher can rearrange the whole alphabet in an enormous number of ways, but it always replaces a given letter with the same letter. HELLO keeps its repeated-letter pattern. Eve can use repetitions and letter frequencies to narrow the choices without trying every key.

The larger key space does not remove the patterns. Identical plaintext letters still produce identical ciphertext letters, so HELLO always becomes five letters with the third and fourth equal. If Alice retains spaces, Eve also sees the word lengths. Removing spaces removes that clue but leaves the repeated letters.

Eve can also count letters. Some occur much more often than others in English, although their frequencies vary with the subject and sample. If Alice replaces E with Q, the many occurrences of E become many occurrences of Q. Frequency analysis uses these counts to propose substitutions, then checks them against letter pairs, repeated words and grammar.

Short messages can remain ambiguous, and specialised vocabulary can hinder Eve. But she need not try every key independently: the patterns let her rule out many choices at once. Counting keys alone would miss this attack.

3.3 Changing the substitution as we proceed

The Vigenère example repeats the keyword LEMON under the message ATTACKATDAWN. Each keyword letter supplies a different shift, so the same message letter can produce different ciphertext letters. Repeating the keyword still leaves a pattern Eve can study.

Now A can encrypt to different letters, depending on its position in the key. Counting the whole ciphertext mixes several substitutions together, so Eve cannot apply the earlier attack directly.

The repetition still gives her a route in. For a five-letter key, positions $1,6,11,\ldots$ share one shift; positions $2,7,12,\ldots$ share another, and so on. If Eve finds the period—the five-position repeat of LEMON—she can split the ciphertext into five interleaved shift ciphers. Given enough text, she can analyse each one’s letter frequencies.

How might the period be guessed? Repeated pieces of plaintext sometimes occur at positions separated by a multiple of the key length and then produce repeated ciphertext pieces. The distances between such repetitions give clues. Other methods compare the rate of equal letters at different offsets. No individual repeated piece proves a particular period, because coincidences occur. Evidence accumulates across a longer sample.

An unusual keyword does not repair this weakness. Eve is attacking the pattern caused by repetition, so she need not guess the word directly.

3.4 The lesson for a modern construction

The shift cipher fails because Eve can try its few keys. Substitution gives her more keys but leaves clues that save her from trying them all. A repeating key spreads those clues across positions. To judge a new cipher, we must ask which shortcut an attacker could use, as well as how many keys it has.

Modern encryption must work for binary files as well as prose. Its security should not depend on whether an opponent knows the language or the format. Indeed, predictable formats are so common that we should explicitly allow the opponent to know some plaintexts and their corresponding ciphertexts. This is called a known-plaintext setting. In a chosen-plaintext setting, the opponent can obtain encryptions of messages they select. Neither ability need disclose the unknown messages of legitimate participants when a suitable modern scheme is used.

These settings turn that question into something we can test: does the construction still hide Alice’s other messages when Eve has this information? [1] The next chapter removes the repeating key entirely. Alice will use a fresh, independent key bit at every position, then discard it.

4. Perfect secrecy

Eve sees the ciphertext 110111. It could conceal 000000, 111111 or any other six-bit message. Under the conditions we shall establish, seeing it gives her no reason to change her guess. This is possible if Alice and Bob share a uniformly random secret key as long as the message and never reuse it.

4.1 The one-time pad

A one-time pad combines each message bit with one fresh, equally likely secret key bit. Bob combines the result with that same key to recover the message. Every possible message fits the ciphertext under some key, provided the whole key was chosen uniformly and is never reused.

4.2 Why all the keys matter

A possible message is not necessarily a likely one. If Alice preferred some keys over others, Eve could favour the messages requiring those keys. The secrecy argument therefore needs every key to have the same probability, $1/2^n$, and its choice to be independent of the message.

Seeing the ciphertext does not improve Eve’s guess about the message. For any candidate message there is exactly one matching pad, and all pads are equally likely. Even if Alice sends one message much more often than another, the ciphertext itself does not change those prior odds.

4.3 Why the pad must be used once

Reusing a one-time pad gives Eve a shortcut. By combining the two ciphertexts, she can cancel the reused key and learn how the two messages differ. If she knows one message, she can recover the other. The diagram shows the cancellation; the bit-by-bit example is optional.

Alice and Bob may use non-overlapping portions of a long pad if the portions are independently random. Overlapping portions can expose the matching message positions. They must therefore track the bits they have consumed, including after a failure or a restored backup.

4.4 The price of the guarantee

To send one gigabyte, Alice and Bob must first share one gigabyte of secret random key material. They cannot send the pad beside the ciphertext over the channel Eve observes: she would decrypt the message too. Distributing and tracking pads may be manageable in a small setting, but becomes a major obstacle for billions of Internet exchanges.

Could a programme expand a short secret seed into the pad? Practical methods do this, but they offer a different guarantee. A deterministic programme always gives the same output from the same seed. It therefore cannot produce more distinct output streams than it has possible seeds. With a 128-bit seed, it can produce at most $2^{128}$ output strings of a specified length. There are $2^{1\,000\,000}$ million-bit strings, so most are beyond its reach. Its output cannot be uniformly distributed over all possible million-bit pads.

Instead, we ask whether Eve can distinguish its output from fresh random bits with feasible computation. That is a computational claim, not perfect secrecy. Sections 8 and 17 examine the assumptions it needs.

4.5 What remains visible?

The theorem has been stated for messages of a fixed length $n$. If Alice sends a pad-encrypted message of ten bits on one occasion and a thousand bits on another, the ciphertext lengths reveal which length was used. This may itself be useful information. A short answer and a long report can sometimes be distinguished without reading either.

One remedy is to place messages inside fixed-size records, adding padding to fill the unused space. Bob needs a protected way to distinguish actual contents from padding. Making every record the same size hides distinctions within that size, but longer messages may still require more records. Hiding lengths, timing, and the number of records is a larger task than encrypting their contents.

There is also a counting reason why the pad’s long key is not merely an unfortunate feature of the XOR construction. Suppose that every message of a fixed length is initially possible, that decryption is unambiguous, and that we demand perfect secrecy. After an observed ciphertext, every one of those messages must remain possible. For each candidate message there must therefore be a key under which that ciphertext decrypts to it. One fixed key cannot supply two different answers to the same decryption. There must consequently be at least as many possible keys as possible messages. For a two-bit message, that means at least four possible keys to keep all four messages possible after one ciphertext. For $n$ unrestricted message bits, this means at least $2^n$ keys. More general information-theoretic statements also account for probability distributions, but this simple counting argument already explains the obstacle. If we want short keys to protect arbitrary long messages, we must change the sort of secrecy we ask for, or introduce other assumptions and resources.

4.6 Secrecy does not detect alteration

A one-time pad hides a message, but it cannot tell Bob whether Eve changed the ciphertext. Eve can flip selected encrypted bits, which flips the matching bits when Bob decrypts. Alice and Bob need a separate check for alteration.

The secrecy theorem concerns what Eve learns by observing a ciphertext. It does not make Bob reject her modified one. To protect Alice’s instruction against both reading and alteration, they need an authenticity mechanism as well, or a construction that supplies both properties.

5. What is a cryptographic key?

A key stored in 128 binary positions might have only 10 000 possible values. Its printed length cannot tell you how hard it is to guess. Nor does the word “key” tell you whether it should be secret: some keys are public. To assess a key, we need to know how it was chosen and which job it performs.

5.1 A choice from a collection

In shared-key encryption, Alice and Bob use the key to select one pair of encryption and decryption operations. A different key selects a different pair. The permitted choices form the key space; software usually selects a key randomly rather than choosing one a person can remember.

Each added bit doubles a uniformly chosen key’s possibilities, and an attacker testing keys one by one expects to search about half of them. A 40-bit key is too small for this defence: at an imagined rate of a billion guesses per second, the full search would take about 18 minutes. A random 128-bit key is vastly harder to search, though a weakness in the algorithm could give Eve a shortcut.

We also need to know what the bits describe. A 256-bit shared secret and a 256-bit public-key parameter are different mathematical objects. Public information may give Eve attacks other than trying each possible secret.

5.2 Length is not unpredictability

Suppose that a programme writes a 128-bit key by choosing a four-digit decimal number and placing it in a fixed binary field. The stored key has 128 positions, but there are only 10 000 possibilities, including numbers with leading zeroes. An opponent who knows the process can enumerate those possibilities. The unused width of the field provides no protection.

A field that stores 128 bits may still hold a key chosen from only 10,000 possibilities. The attacker searches those 10,000 choices, not every possible 128-bit string. That is roughly 13 bits of uncertainty, far below 128.

The broad idea is called entropy. Our numerical claims will mainly concern explicitly uniform choices, where counting gives a clear answer. For a password a person invents, we cannot infer the entropy from its length alone.

5.3 Keys and passwords

A password is normally something a person can remember and enter. A cryptographic key need not be memorable at all. When encryption is protected by a password, a programme usually feeds the password into a password-based key derivation function. This converts the input into a key of the required form while deliberately making each password guess costly. Some such functions also require substantial working memory, which can make large parallel attacks more expensive.

Eve can run the same derivation on each password she guesses. The function makes those trials costlier; it cannot add secret uncertainty to the password Alice chose. Making the output longer does not enlarge a small collection of plausible passwords.

The derivation also takes a salt, normally generated afresh for each stored password or encrypted object. It need not be secret. With different salts, identical passwords will ordinarily produce different derived values, so Eve must repeat her calculations for each salt. She cannot use one unsalted table of precomputed results against them all.

For one selected record, Eve can still try likely passwords against its visible salt. The salt separates her work across records; it does not make Alice’s password harder to guess within that record.

5.4 Values which should be different

Many encryption schemes require a nonce, a value used to distinguish one encryption from another under the same key. The name suggests “number used once”. Depending on the construction, the nonce must be unique, or must be chosen under a more specific rule. It often travels openly with the ciphertext. Keeping it secret is generally not its job.

A secret key alone may not distinguish repeated uses. A deterministic algorithm gives the same output for identical inputs; a suitable new nonce lets it encrypt repeated messages differently. Some constructions generate the masking stream from the key and nonce. Repeating both can repeat that stream, exposing the message relation we saw with pad reuse in Section 4.

A counter can provide distinct nonces if it is managed correctly and never wraps or restarts under the same key. Randomly selecting nonces avoids some coordination problems but introduces a chance of collision. For $q$ independent uniform $b$-bit nonces, the rare-collision estimate is approximately $q(q-1)/2^{b+1}$. The point of the formula is that each new random nonce could repeat any earlier one, so collision opportunities grow as messages accumulate. The birthday effect therefore matters long before every possible nonce has been used. The required rule is specified by the scheme, and should not be improvised.

Some constructions use the term initialisation vector, or IV, for an auxiliary input. Its requirements depend on the construction; uniqueness alone is not sufficient in every case. We shall avoid treating nonce, salt, and IV as interchangeable words merely because each may refer to a public string of bits.

5.5 Public, private, and temporary

In symmetric cryptography, the participants use shared secret information. In public-key cryptography, a participant has a related pair: a public key, which can be distributed openly, and a private key, which must be kept secret. The mathematical relationship allows specified operations with the public key without revealing the private one. Different public-key schemes support different tasks; we must not assume that every key pair can be used for encryption, signatures, and key agreement alike.

A public key beside the name “Bob” is still only a claim about ownership. If Eve can replace the name and key in transit, Alice may perform every calculation correctly while communicating with Eve. Alice needs grounds for trusting the association between Bob and his key.

A session key protects a particular conversation or limited period of activity. A long-term key may establish identity or help create many sessions. Separating these roles limits how much information depends on any one key, and makes replacement more manageable. It also allows systems to aim for a property called forward secrecy, in which later exposure of a long-term key does not by itself reveal past session keys. Achieving that property requires an appropriate protocol and erasure of temporary secrets; naming a key “temporary” does not establish it.

Alice and Bob also need to manage the key’s copies, including those in backups and temporary memory. Section 16 follows that work from generation to erasure. Labelling a value “secret” or “temporary” will not make forgotten copies disappear.

6. Algorithms and protocols

Bob can decrypt a payment instruction correctly and still pay twice. The decryption algorithm recovers the contents; it does not decide whether Bob has already acted on them. A protocol specifies the exchange around the calculation: who sends what, in which order, what each side checks and what they do next.

6.1 The algorithm is public

Suppose Alice and Bob rely on keeping their programme secret. Eve obtains a copy, examines its instructions and may discover keys stored inside it. If their only defence was that she would never learn how it worked, they must now replace the programme wherever they installed it. Keeping the key separate makes replacement easier.

In the nineteenth century, Auguste Kerckhoffs articulated principles for military cryptography which included the ability of a system to remain secure even if it fell into an opponent’s hands.[3] Modern designers assume that an attacker knows the algorithm and protocol, and keep selected keys secret. Publishing the construction also lets others examine it. Publication does not prove security, but obscurity alone gives Alice and Bob no dependable replacement for a security argument.

Alice need not reveal her key, internal random choices or computer state. We must specify which values Eve knows and which remain secret.

6.2 What is the opponent allowed to do?

A threat model states what we want to protect and what Eve can do. A passive opponent listens. An active opponent may replace, delay, delete, insert or replay messages. On a network, Eve could control a route or impersonate an endpoint without first breaking the cipher, so we normally need to consider active attacks.

“Allowed” means permitted by the mathematical experiment, not by law. We give Eve specified capabilities and ask whether she can succeed. Choosing an artificially weak Eve would tell us little about an actual network attacker.

In a chosen-plaintext setting, Eve can request encryptions of messages she selects. She might use a service that encrypts user-supplied data, or control one field in a message Alice encrypts. Eve gets the ciphertexts, not the secret key. The security definition asks whether this access helps her learn protected information in other encryptions.

In a chosen-ciphertext setting, the opponent can obtain decryptions of selected ciphertexts, subject to restrictions in the security experiment. One essential restriction excludes simply requesting decryption of the particular test ciphertext, called the challenge, whose secrecy is being tested. Otherwise the test would ask for an impossible property. More subtle queries remain allowed, such as modifying that ciphertext and observing the response.

A programme might return only success or failure rather than decrypted text. Eve can still learn from repeated queries. If different malformed inputs produce distinguishable errors, she may use the responses to narrow her guesses. A callable source of such answers is often called an oracle.

6.3 An authentic instruction can still be old

Alice sends Bob an authenticated instruction to pay ten pounds. Assume for now that the authentication mechanism detects alteration and prevents Eve from making new valid instructions; later we shall examine how to achieve that protection. Bob checks the instruction and pays.

Eve records the transmitted object and sends it again tomorrow. Because she has changed nothing, its authentication still checks. If Bob acts on every valid instruction, he pays twice. Eve has neither found the key nor forged an authentication value.

One repair is to include a sequence number inside the authenticated contents. Alice sends instruction 41, then 42, then 43. Bob retains the last number accepted and rejects duplicates or numbers outside the permitted policy. In the simplest strictly ordered example, Bob expects 42 and accepts only 42, then updates his stored expectation to 43.

Alice must authenticate the number along with the instruction. Otherwise Eve could change an unprotected outer number from 42 to 43 and resend the same authenticated payment. Bob must check the protected number.

Networks lose and reorder messages, so Bob may allow a window of sequence numbers and record which have arrived. He must also preserve the right state after a restart. Restoring an old counter backup can make an old instruction appear new.

6.4 Asking a fresh question

Another approach is challenge–response. Bob generates a new, unpredictable value and asks Alice to authenticate a response containing it. An old response to yesterday’s challenge will not match today’s. The unpredictable value is often also called a nonce, with requirements appropriate to this protocol.

Bob also needs to know what Alice has authorised. If she authenticates only the string 7319, her response may prove possession of a key without approving any payment. The protected contents should connect the participants, the challenge and the intended action or conversation. Otherwise Eve may carry a response from one context into another.

Eve can still discard the messages, preventing Bob from receiving any response. Keeping a service usable concerns availability. Cryptography can help Bob reject fraudulent requests, but encryption alone cannot make a severed cable carry traffic.

6.5 Agreeing on the meaning of bytes

The participants must also interpret an authenticated string in the same way. Suppose that an application forms a message by writing an account number immediately followed by an amount, without a separator or a length rule. The pairs “account 12, amount 345” and “account 123, amount 45” both produce the string 12345. Authenticating that string does not resolve which pair was intended.

A proper encoding makes the boundaries unambiguous, for example by using specified field lengths or explicit lengths checked by the receiver. The receiver must reject malformed representations and agree with the sender about units, character encodings, and permitted values. Authentication proves something about the protected bytes; the application must give those bytes one well-defined interpretation.

If Alice and Bob give the same valid string different meanings, a stronger cipher cannot resolve their disagreement. Protocols must therefore specify message formats as well as the equations applied to them.

6.6 Combining components

Even when an encryption method and an authentication method are sound individually, their combination needs analysis. The order of operations can matter, along with which information is authenticated and whether the same key serves incompatible purposes.

Modern authenticated encryption schemes define confidentiality and integrity together and specify exactly which inputs are protected. Some also authenticate visible contextual information, called associated data. A visible record type or sequence number can then be bound to the encrypted contents without itself being hidden. We shall examine this in Section 8.

Public-key exchanges need the same care. A calculation that gives two participants the same secret does not by itself identify them. A signature made with a key does not establish who owns that key. The protocol must connect these checks to the participants and the exchange they intend [2, 1].

The timing of a check also matters. Bob must complete the required authenticity check before releasing tentative decrypted data to the application. Otherwise it may act on a forged payment before the cryptographic code rejects it. Checking later would not undo that payment.

7. Security as a calculation

Alice wants to encrypt a collection of photographs with one short key. A one-time pad would require as much fresh secret material as the photographs themselves. Using a short key instead requires a different kind of guarantee.

Perfect secrecy withstands unlimited computation. Computational security instead asks what an attacker with specified computing resources can learn. A calculation may recover the message in principle yet take too long to be useful.

To judge that claim, we need to know the attacker’s resources, the information available to them and their chance of success. Counting possible keys answers only part of the question.

7.1 Trying every key

Brute force means trying possible keys until one works. A truly random 128-bit key has so many possibilities that even a hypothetical machine testing a trillion keys each second would take far longer than any useful time. At that same imagined speed, a 40-bit key would take roughly half a second on average.

7.2 What a bit of security measures

If the best known attack needs roughly $2^s$ operations, we often describe the task as having about $s$ bits of security. One extra bit doubles the work; ten multiply it by $2^{10}=1024$. To compare estimates, we must also ask what counts as an operation, how much memory the attack needs and how many machines can share the work.

Key length alone does not establish a security level. A weakness in a cipher with a 256-bit key might give an attacker a much cheaper route than key search. Known attacks on public-key systems also exploit their mathematical structure, so their key lengths cannot be compared directly with symmetric key lengths. And a long password may be easy to guess if a person chose it from a familiar pattern.

The number of targets matters too. An attacker trying to break any one of a million accounts has more opportunities than an attacker targeting one account. An estimate must describe which task it measures.

7.3 Giving the attacker a fair test

Suppose a ciphertext contains either YES or NO, and the shorter word always produces a shorter ciphertext. An observer can recognise the answer without recovering the key. Even an enormous key space would not conceal the message.

A useful test therefore gives an attacker two messages of equal length. A challenger chooses one at random, encrypts it and supplies the ciphertext. The attacker guesses which message was chosen. A guess without useful information succeeds half the time. Under the test’s stated conditions, secure encryption should prevent an efficient attacker from doing appreciably better.

The equal-length condition allows for the length information that ordinary encryption commonly reveals. Padding can hide more by making different messages the same size, at a cost in storage or communication.

We can also let the attacker request encryptions of chosen messages. This models an adversary who can make a service encrypt known data. If the deployed system allows such requests, the test should allow them too. Stronger tests add restricted decryption queries. Chapter 13 defines these experiments more precisely.

7.4 Evidence, assumptions and proofs

Years of public scrutiny without an effective attack give us one kind of evidence. A mathematical proof gives another. Neither should be described as more than it establishes.

A common proof uses a reduction: it shows how an algorithm that breaks a scheme could be used to solve another problem believed to be hard. We need not possess the attack algorithm to prove this implication. The proof says what we could do if one existed.

For an analogy, imagine a box which can be opened by solving a maze. Showing how to turn any permitted box-opening method into a maze solver would connect the two tasks. It would not prove the maze difficult. Nor would it cover smashing the box with a hammer unless the model included that attack.

A stolen key, leaked timing information or a software error may be the cryptographic equivalent of the hammer. A proof about a mathematical interface covers only the behaviour included in that model. An implementation needs further scrutiny.

The cost of the reduction matters as well. If a fast attack on the scheme would yield only an extremely slow solver for the underlying problem, the resulting numerical guarantee may be weak. Specialists therefore study concrete resource bounds alongside statements about efficient algorithms [1, 2].

7.5 How much uncertainty is acceptable?

A very small chance on one attempt can matter when an attacker gets many attempts. Multiplying the one-attempt upper bound by the number of attempts gives a conservative upper bound for at least one success.

For example, one guess at a uniformly distributed 128-bit value succeeds with probability $2^{-128}$. A billion guesses succeed with probability at most $10^9/2^{128}$ in that model. Bounds for real authentication schemes may also depend on message lengths, the number of users and other features of the construction.

We can now ask more than “Is the key long?” We can ask whether the stated attack costs, success probabilities and excluded events suit the information Alice wants to protect.

8. Symmetric encryption

A short secret key can protect gigabytes of data, but it cannot supply a fresh one-time pad that long. In modern symmetric encryption, Alice and Bob use the key to drive a calculation instead. The guarantee is computational: an attacker without the key should be unable to exploit the resulting patterns within the stated resource limits.

Two common components are block ciphers and stream ciphers. To see why a component is not yet a complete encryption scheme, start with a block cipher.

8.1 A block cipher

A block cipher transforms a fixed-size block of bits into another block of the same size. For each key, it pairs every possible input with a different output, so the transformation can be reversed. Mathematicians call this a permutation of the possible bit strings. It need not merely move the bits within each string.

AES transforms one 16-byte block at a time under a secret key, and the same key lets Bob reverse that transformation. This gives them a useful building block. They still need a specified way to protect messages longer or shorter than one block.

AES repeatedly substitutes values, mixes them and combines them with information derived from the key. These operations spread the influence of input and key bits through the output. The result may look scrambled, but the calculation preserves every bit of information needed for exact reversal.

We can leave AES’s internal round calculations to the standard and examine the next design decision: how to use the block transformation across a whole message.

8.2 Why blocks cannot simply be encrypted separately

Suppose Alice cuts her message into blocks and encrypts each independently with the same key. This is electronic codebook mode, or ECB. Because the transformation is fixed, equal plaintext blocks produce equal ciphertext blocks. Eve can see repetitions without knowing what the blocks contain.

If records contain a fixed-length field at the same position, Eve may learn which records share its value. Other knowledge may let her identify that value. AES can behave exactly as specified while this use of it leaks information.

A mode of operation specifies how a block cipher processes longer messages. Different modes offer different guarantees and impose different conditions. The next mode removes ECB’s direct repetition pattern, but introduces a requirement of its own.

8.3 Making a stream of apparently random bits

Counter mode uses the key, a nonce and a changing counter to make a different mask for each message block. Alice combines each mask with its block using XOR; Bob makes the same masks to undo it. The inputs must never repeat under the same key.

Bob calculates the same keystream and applies XOR again to recover $M_i$. He does not need the block cipher’s inverse, because XOR with the same string undoes itself.

The nonce can travel publicly with the ciphertext, but the same key must never generate a stream from the same counter input twice. A counter can meet that rule if it never restarts or overlaps; randomly chosen nonces need limits because two choices can collide.

If the same masking stream protects two messages, Eve can combine their ciphertexts and make the mask cancel. She then sees a relationship between the messages, just as with a reused one-time pad. A longer key does not repair reuse of the stream.

A dedicated stream cipher generates a keystream without exposing a general-purpose block cipher as its building block. ChaCha20 combines a key, nonce and block counter through specified arithmetic and bit operations [7]. To an efficient observer without the key, its output is intended to be indistinguishable from random data under its security assumptions. Its nonce and usage rules remain essential.

8.4 Concealing a message is not protecting its meaning

Suppose a stream-encrypted message contains a bit meaning “payment approved”. Eve can flip the corresponding ciphertext bit and thereby flip the decrypted bit. She need not read the rest of the message or recover the key.

To reject such changes, Alice and Bob need authenticated encryption, which protects against unauthorised modification as well as disclosure. A common interface accepts a key, nonce, message and additional data, then returns a ciphertext and an authentication tag. Decryption returns either a verified message or failure.

The extra input, called associated data, is authenticated but remains readable. A packet header, protocol version or record identifier may need this treatment. The full name is authenticated encryption with associated data, abbreviated AEAD.

Bob must check the tag before acting on the plaintext. Some low-level interfaces emit tentative bytes before verification; using them early can defeat the protection. Error responses must also avoid leaking secret-dependent details that help Eve refine her next attempt.

8.5 Two common constructions

AES in Galois/Counter Mode, AES-GCM, combines counter-mode encryption with authentication [6]. ChaCha20-Poly1305 combines ChaCha20 with a different authentication calculation [7]. Both protect arbitrary byte messages through an AEAD interface, within their specified limits.

Nonce reuse can be especially damaging in AES-GCM: repeating a nonce under the same key repeats encryption material and may also enable forgery. The standard 96-bit nonce format simplifies the calculation, but its length does not ensure uniqueness. Designers must account for generation, restarts, stored state and key replacement.

These constructions also limit message sizes, total traffic and forgery attempts. Established protocols and maintained libraries specify how to use them within those bounds.

An old message can still pass verification. Stop replays by authenticating sequence numbers with messages and rejecting previously accepted values.

9. Hash functions

A SHA-256 digest takes 64 hexadecimal characters to print, whether its input is a short note or a software file [8]. How can such a short value help check something much larger?

A hash function maps an input byte sequence to a result of a fixed length, called a hash value or digest. The same input always gives the same result. SHA-256 produces 256 bits; hexadecimal notation writes four bits per symbol using 0 through 9 and a through f, hence the 64 characters.

A digest cannot uniquely describe every possible input. SHA-256 has $2^{256}$ possible outputs and far more possible inputs, so different inputs must share outputs. Its usefulness depends on how hard an attacker finds it to locate particular matches.

9.1 Three questions which sound alike

A database hash may aim only to spread records efficiently. A cryptographic hash function must resist an adversary making deliberate searches. Three search tasks matter.

In a preimage search, Eve receives a digest $h$ and seeks any message $M$ for which $H(M)=h$. Here $H$ denotes the hash calculation. In a second-preimage search, she receives a particular message $M$ and seeks a different message $M'$ with the same digest. In a collision search, she can choose both messages and needs any distinct pair with equal digests.

The first search fixes only the digest; the second fixes one message; the third lets Eve choose both messages. That extra freedom makes a collision search easier. Think of birthdays: finding someone who shares your birthday is harder than finding any two people in a room who share one.

For an ideal hash, finding an input for one specified digest takes many more trials than finding any two inputs that share a digest. The birthday effect gives the attacker many possible pairs. These are estimates for an ideal model, not guarantees for every real hash function.

9.2 The birthday calculation

With only 23 people, the chance that any two share a birthday is already just over half. Each new person can match anyone who came before, so the number of possible pairs grows quickly. Hash collisions and random nonce repeats follow the same pattern.

As more hash outputs accumulate, the number of pairs that could collide grows quickly. The formula below estimates the collision chance only while that chance is still small.

9.3 A fingerprint with conditions attached

Suppose a publisher posts a software file and its digest. If Eve can replace both, she can supply a malicious file and calculate its matching digest. Calling the digest a digital fingerprint does not attach the publisher’s identity to it.

Checking the digest helps when the expected value reaches you through a trusted independent route or carries a valid digital signature. It also detects accidental corruption when nobody is trying to replace both values. The hash calculation alone cannot tell you who supplied the bytes.

Nor does it necessarily hide them. If a file contains one of ten standard forms, Eve can hash all ten and compare. Hashing a predictable secret gives her a similar offline guessing test. Resistance to a generic preimage search does not make a small dictionary hard to search.

The exact bytes matter too. A changed space, line ending or character encoding may change the digest even when a document looks identical. The signer, sender and receiver need to agree on which byte sequence they process.

9.4 Adding a secret: message authentication

A message authentication code, or MAC, combines a secret key with a message to produce a tag. Bob checks Alice’s tag with their shared key. An outsider should be unable to produce an acceptable tag for a new message, even after seeing tags on other messages.

HMAC builds a MAC from a cryptographic hash using a specified arrangement of inner and outer keyed calculations [9]. Simply hashing the key followed by the message is not a reliable substitute. Some common hash structures allow extension attacks on such naive constructions.

HMAC authenticates the message without concealing it. And because every holder of the MAC key can generate tags, a tag cannot show an independent observer which key holder created it. Digital signatures use a different arrangement of keys, as Chapter 12 explains.

9.5 Why passwords need a different treatment

Suppose a service stores $H(P)$ for each password $P$. After stealing the database, Eve can hash guesses and compare them with the stored values. SHA-256’s speed helps her test candidates quickly. Password storage needs a calculation designed to make each guess costly.

A salt is a separate value stored with each password record. Usually it is chosen randomly and made long enough that different records are overwhelmingly likely to have different salts. The password-hashing calculation takes the password, salt and cost parameters as inputs. The salt need not be secret.

Different salts prevent Eve from applying one precomputed answer to all accounts that share a password. They also prevent equal passwords from automatically giving equal stored values. Eve can still guess against each record using its own salt, so a salt does not make a weak password hard to guess.

A password-hashing function raises the cost of those trials. Argon2id uses both computation and a configurable amount of memory [10]. The service chooses parameters to suit its resources, response times and current guidance. Memory requirements make some parallel attacks more costly; they do not prevent guessing altogether.

10. Public and private keys

Alice wants to send Bob a secret, but they have never shared a key. If she sends a key over their watched connection, Eve receives it too. Encrypting that key seems to require an earlier one. Where can they start?

In public-key cryptography, Bob generates two related keys. He publishes one and keeps the other private. The public key lets other people perform a useful operation; the private key lets Bob perform a related operation which should be infeasible without it.

Different constructions use this asymmetry for encryption, key establishment or signatures. A pair designed for one job is not automatically suitable for another. First consider encryption.

10.1 An open address for secret messages

Alice encrypts with Bob’s public key; Bob decrypts with his private key. Eve can know the encryption key without gaining a feasible way to decrypt. This differs from a shift cipher, where knowing the shift immediately gives both operations.

An open padlock offers a useful picture. Bob gives Alice a padlock she can close around a message box, while he alone keeps the opening key. The picture separates locking from unlocking. It does not explain the arithmetic, or tell Alice how to check that the padlock came from Bob.

Alice encrypts a message using Bob’s public key and fresh randomness. Bob uses his private key to recover it, or rejects an invalid ciphertext. The symbols below abbreviate those two operations; a secure scheme must define the details.

The keys are mathematically related. The claim is that publishing $pk$ does not give Eve an efficient route to the private operation. Calling the keys unrelated would obscure the calculation on which the system depends.

10.2 Why encryption needs fresh variation

Suppose encryption always gives the same ciphertext for the same message and public key. Eve suspects Alice sent either ACCEPT or REJECT. Because Eve also has the public key, she can encrypt both and compare the results with Alice’s ciphertext. She never needs to decrypt it.

Randomised encryption prevents this comparison by giving one message many possible ciphertexts. Its random choices must be generated and handled as the scheme requires: predictable or repeated choices can break security, and disclosing them may reveal the message.

The construction must also specify message encodings, invalid inputs and the attacker’s permitted interactions. A reversible mathematical operation alone does not settle these questions. RSA in the next chapter gives us a concrete example.

Randomisation does not hide a communication’s length, timing or destination automatically. Eve may still notice that Alice sent a large file just after a particular event. The confidentiality claim must say which information remains exposed.

10.3 Using public keys to establish a shared secret

Alice and Bob can also use public-key methods for key agreement. Each combines public exchanges with a private value to calculate the same shared secret. An observer should find that calculation infeasible from the public exchange alone.

In Diffie–Hellman agreement, both participants contribute to the result. Neither needs to encrypt an ordinary message to the other first. A key derivation function, or KDF, processes the agreed material into keys of the required lengths and roles. It can also bind context, such as the protocol version and the exchange being performed.

A key encapsulation mechanism, or KEM, offers a related interface. Using Bob’s public key, Alice’s encapsulation operation produces a shared secret and a public encapsulation ciphertext. Bob uses his private key to recover the secret from that ciphertext. A KEM supplies key material; it does not itself encrypt an arbitrary file.

In either case, the raw result needs the derivation and validation steps specified by the construction. Calling it a shared secret does not make it ready for every use.

10.4 Hybrid encryption

Public-key operations are generally more expensive, and often more restricted in message size, than symmetric encryption. A hybrid encryption system assigns each its appropriate job.

Alice uses a specified public-key mechanism to establish secret material with Bob. A derivation step produces a symmetric key, then an authenticated symmetric scheme protects her message. Bob recovers or agrees the same material, derives the key and verifies and decrypts the ciphertext.

The components need a security argument as a complete construction [2]. Their encodings, parameters and context must fit together so that Eve cannot substitute an input from another exchange or exploit an ambiguity. Choosing individually sound algorithms does not establish this property.

With that design in place, a small public-key exchange can establish fresh keys for a long conversation. Alice and Bob no longer need to deliver each session’s secret key through a separate private channel.

10.5 The public key must belong to the intended person

But how does Alice know she has Bob’s public key? If Eve intercepts her request and supplies Eve’s own key, Alice encrypts to Eve. Eve can read or change the message and encrypt a replacement under Bob’s actual key.

Every encryption and decryption can succeed while Alice’s confidentiality fails. She needs authentication of the public key: a trustworthy link between that key and the person or service she means to reach.

Alice might check a fingerprint through an independent channel, rely on a previously trusted key, or validate a certificate. Each approach gives her a particular basis for trust. Merely declaring the key public supplies none. Chapter 12 examines certificates, and Chapter 14 follows the interception attack.

Key agreement has the same need. Without authentication, Alice may establish a shared secret with Eve while believing she has reached Bob. Protection against an observer who listens does not by itself stop an adversary who replaces messages.

10.6 A new possibility, with stated conditions

Public-key cryptography lets Alice and Bob communicate confidentially without an earlier shared secret channel. They still need authentic information about each other, sound random choices, secure implementations and suitable computational assumptions. The next chapter shows the arithmetic that makes this possible.

11. Two public-key constructions

Alice publishes 8, Bob publishes 19, and both calculate the shared value 2. We can follow each step of this small Diffie–Hellman exchange to see how a public conversation produces a matching secret. RSA will then show us a different use of public and private operations [11, 12].

These examples use numbers small enough to check by hand, which also makes them easy to break. They demonstrate the arithmetic, rather than supply secure parameters or complete protocols.

11.1 Diffie–Hellman agreement

Alice and Bob each keep a private number and send a public result calculated from it. Alice uses her private number with Bob’s public result; Bob uses his with Alice’s. Both reach the same value, 2 in this toy example. The diagram shows the exchange; the calculation is below if you want to check the numbers.

Alice and Bob can calculate their matching secret from their own private numbers and the public exchange. Eve sees only the public values. With suitable large parameters, working backwards to the private numbers is believed to be impractical. This tiny example is easy to break, and the calculation alone does not prove who sent a public value.

11.2 Temporary secrets and later compromise

Alice and Bob can choose new private exponents for every exchange and erase them afterwards. These short-lived values are ephemeral keys. Separate long-term keys can authenticate a transcript binding the participants and exchanged values, for example through signatures. The long-term keys authenticate the exchange; the ephemeral values establish its secret.

This separation can provide forward secrecy. If Eve records a session and later steals a participant’s long-term authentication key, that key alone should not reveal the earlier session key, provided the ephemeral secrets were erased and the protocol’s assumptions hold. It does not protect plaintext or temporary secrets that malware captures during the session.

If a protocol instead reuses a long-term agreement secret, its later theft may allow Eve to reconstruct old shared secrets from recorded exchanges. Forward secrecy therefore depends on the protocol and secret handling, not just on its use of Diffie–Hellman.

11.3 Elliptic curves: a different place to do the arithmetic

Elliptic-curve key agreement follows the same pattern with points and a different arithmetic. Each person combines their private number with the other person’s public point and reaches the same result. The point equation and addition rule are details of the chosen construction.

11.4 The RSA calculation

RSA uses two large secret primes to make related public and private operations. Bob publishes the information needed for the public operation and keeps the values needed to reverse it. The small numbers below demonstrate that reversal; they are not a secure encryption scheme.

11.5 What makes RSA difficult?

If Eve can split RSA’s public number back into its two secret prime factors, she can reconstruct Bob’s private operation. Large primes make that route difficult. Raw RSA is still unsuitable for messages: it repeats the same result for the same input and permits predictable changes. A secure scheme needs more than hard arithmetic.

11.6 From an operation to a scheme

RSA encryption therefore needs a complete specified encoding, such as RSA-OAEP, with its required randomness, hash functions and input checks [13]. The encoding is part of the security construction. Its assumptions, message-size limits and error behaviour matter.

RSA signatures use a different construction, such as RSA-PSS. OAEP encodes for encryption; PSS encodes for signatures. Applying a raw private exponent to a document implements neither complete scheme.

Neither RSA nor Diffie–Hellman identifies a person through arithmetic alone. When Alice accepts a public value, the surrounding protocol must bind it to the intended participant and the current exchange.

12. Digital signatures

A software publisher wants everyone to check a release, without giving every reader the power to sign one. A shared MAC key cannot do that: anyone who can check the tag with that key can also generate tags.

A digital signature separates these powers. The publisher signs with a private key and distributes a public verification key. Users can then check the release, provided they have an authentic copy of that key and apply the right verification rules.

12.1 Signing and verifying

Signing takes an exact message and a private key and produces signature data. Verification takes that message, the signature and the public key and returns accept or reject. The notation below is a compact description of this interface.

Correctness means that a signature produced honestly with a valid key pair passes verification. Security asks whether an attacker can produce an acceptable signature on a new message. We normally let the attacker obtain signatures on chosen messages first, because a real adversary can see legitimate signatures and may influence what a service signs.

The aim is resistance to forgery. The signature itself is normally public and does not hide the message. A protocol that also needs confidentiality must specify how to combine signing and encryption, or another suitable construction, so that it is clear what each party can read and authenticate.

12.2 A signature is not private-key encryption

Signing is sometimes called “encrypting with the private key”. That description misleads. Ed25519, for example, uses its own signing and verification equations based on elliptic-curve mathematics [14]. Its verifier does not decrypt an ordinary message.

RSA’s reversible exponentiations can encourage the confusion. But an RSA signature scheme also needs specified encoding and verification, as in RSA-PSS [13]. Applying the private exponent to arbitrary bytes does not implement the complete scheme.

Many signature schemes use a hash internally to handle long messages in a fixed-size mathematical calculation. An instruction to “sign the hash” may still omit required encoding, hash identification or separation between different uses. The signing interface must define exactly what its input represents.

Implementations must follow the scheme’s secret-value rules too. Some schemes fail if per-signature secret values repeat or are biased. Deterministic schemes reduce certain dependence on fresh signing randomness; they still require sound key generation, faithful implementation and protection against leakage.

12.3 What exactly has been signed?

A user approves “Pay 10 pounds” on a screen. What bytes does the program sign? Do they include the recipient, currency and date? Does the amount mean ten pounds or ten pence? Could another program interpret those bytes differently?

A valid signature cannot settle these ambiguities. Structured messages need a defined encoding and interpretation. Some systems use canonicalisation: a shared rule that selects one byte representation from several equivalent forms. It must preserve every distinction the application needs.

The signature may also need a bound context. A software-update authorisation must not become a bank-transfer authorisation just because some fields match. The scheme or protocol can bind message types, recipients, versions and other context through signed data or a specified domain-separation mechanism.

A signature does not establish freshness by itself. To reject duplicates, an application can check a unique transaction identifier, challenge or sequence number and keep the state those checks require. An expiry limits when a message is accepted; it does not stop repetition within that window. Likewise, a signed date is only a signed assertion of a date unless a trusted process establishes more.

12.4 Certificates and chains of trust

A browser needs to connect a public key with the hostname in its address bar. A certificate binds a key to identifying information and other fields through an issuer’s signature. On the public web, a certificate authority commonly issues it. The browser starts with trusted authority keys and checks a chain leading to the server’s certificate.

Signature checks alone do not validate that chain. The browser also checks the hostname, validity period, permitted uses, constraints and other rules in its policy. A valid certificate for one hostname cannot authenticate another. A certificate also does not establish that the website’s business is honest.

The server must demonstrate possession of the matching private key within the authenticated protocol. In modern TLS, signatures and other handshake checks bind its use to the current exchange [15]. Copying the public certificate is therefore insufficient to impersonate the server.

If a private key is compromised, a certificate may need to be distrusted before expiry. Revocation mechanisms distribute that information. Whether a verifier receives and enforces it promptly depends on the system and its policy. Short certificate lifetimes and trust-store updates address related problems, but no verifier can simply assume it knows of every compromise.

The chain must start somewhere. A browser receives trusted roots through its software and administration; an organisation may distribute private root keys; two people may compare fingerprints face to face. The arithmetic extends a chosen basis of trust rather than choosing that basis for the verifier.

12.5 Signatures, shared secrets and responsibility

With a MAC, Alice and Bob share the authentication key. Either can produce a tag, so the tag alone cannot settle a later dispute about which of them wrote the message. With a signature, a verifier can check a message without holding the signing key.

This public evidence is sometimes described as non-repudiation. Its meaning needs care. A valid signature is evidence that a key was used, under assumptions about the scheme, key custody and surrounding records. Malware, stolen keys, shared devices or a misleading display can break the link between that event and a human’s approval.

Legal responsibility depends on law, agreements and evidence. A signing service may also act automatically for an organisation: its signature records that service’s process, rather than an individual reading the document. If the user approved “Pay 10 pounds”, the signature’s usefulness still depends on what the software encoded, displayed and authorised.

13. What does a security claim mean?

If Eve can tell that an encrypted order says BUY rather than SELL, she may not care about the rest of the message. A test which asks only whether she can recover every word misses that failure. We need to specify what information she is trying to learn, what help she can obtain and how much work she can do.

Security definitions turn these questions into experiments. A proof can then bound an attacker’s chance of success within the experiment’s rules. To use the result, we must check that those rules cover the attacker and the system we actually have.

13.1 A guessing experiment

BUY and SELL have different lengths. If encryption preserves that difference, Eve can distinguish them by counting the transmitted characters. To test what the encrypted contents reveal, we first remove this clue. Use BUY NOW and SELL IT instead: each has seven characters, counting the space.

The observer chooses two possible messages, labelled $m_0$ and $m_1$. The small numbers are labels, not multipliers. An experimenter tosses a fair coin, writing $b=0$ for one outcome and $b=1$ for the other. The experimenter encrypts $m_b$ with an appropriately generated key and fresh randomness where required, then gives the ciphertext to the observer. The observer must guess $b$.

An attacker who learns nothing can guess which of two messages was encrypted correctly half the time. We measure whether the ciphertext lets them do better. Getting 51 out of 100 right is a small but measurable improvement; always getting it right is a complete break of this test.

Allowing the observer to choose the alternatives makes this a demanding test. One message might contain a word whose presence alone would reveal a valuable fact. If encryption protects against all such choices within the model, it protects much more than the readability of an unknown page.

This property is called indistinguishability: within the allowed resources, the observer cannot reliably tell which alternative was encrypted. The ciphertexts may differ. Their differences must give the observer no useful way to identify the chosen message beyond the allowed advantage. Modern encryption definitions build on this test [1, 2].

13.2 What else may the opponent do?

Suppose a scheme always produces the same ciphertext for the same message under a given key. If Eve can request an encryption of $m_0$ before the challenge, she can compare that result with the challenge ciphertext. The secret key alone does not prevent her from winning. We must specify what requests she may make.

An encryption oracle is an interface which encrypts messages chosen by the attacker. It might represent a server that processes requests, or a user persuaded to send predictable messages. Security against a chosen-plaintext attack allows these requests. Public-key encryption must account for them because anyone with the public key can encrypt.

The rules may allow requests before and after the challenge. They also govern random choices and nonces. For example, a game that requires unique nonces gives no guarantee about an application that repeats them. The application has stepped outside the proof’s conditions.

A decryption oracle processes ciphertexts chosen by the attacker. A service that reports whether a submitted record is acceptable may give the attacker some of this information. In a confidentiality experiment allowing chosen-ciphertext attacks, the attacker must be forbidden to request decryption of the challenge ciphertext itself: its plaintext would give away the answer immediately. The usual adaptive experiment still allows requests involving other ciphertexts, including altered versions of the challenge. The scheme must withstand those requests under the game’s precise rules.

This explains why error handling matters. A service may never print a plaintext but still reveal information through an error message, a timing difference or a different network response. An attacker who repeats such requests may learn much more than any single reply reveals. The model must capture the relevant responses, and the implementation must avoid leaking additional information.

13.3 Privacy and authenticity are separate questions

The guessing experiment tests what Eve can learn. We need another experiment to ask whether she can change a ciphertext and make Bob accept a different instruction. A scheme can pass the privacy test and fail this authenticity test. Authenticated encryption, discussed in Section 8, aims to provide both protections.

An authenticity experiment lets Eve observe valid protected messages, then asks her to produce a new protected record that Bob accepts although the appropriate sender did not produce it. The exact definition must account for the message, nonce, associated data and context. It must also say what counts as new. Replaying a previously valid record may require a separate defence, such as a checked sequence number or a record of requests already accepted.

For digital signatures, unforgeability usually allows Eve to request signatures on messages of her choice. To win, she must produce a valid signature on a message she did not submit for signing. Giving her genuine signatures reflects ordinary use: a key must remain secure while its owner signs documents. A stronger definition also forbids her to produce a different valid signature on an already signed message. The two definitions protect against different outcomes.

We can put a number on a simple authenticity risk. An ideal, uniformly unpredictable 16-bit tag has $2^{16}=65\,536$ possible values. One blind guess succeeds with probability $1/65\,536$; more attempts give Eve more chances. Real schemes commonly use longer tags, and their bounds also depend on data volumes and the construction. A small per-attempt probability must always be read alongside the permitted number of attempts.

13.4 From an experiment to a guarantee

A useful security claim states how much computation, how many queries and how much data the attacker may use, then bounds her advantage. An attack that needs a trillion years and one that succeeds once in a million trials have very different implications for a service handling billions of requests. The quantities determine whether the guarantee suits the application.

Theoretical work often expresses these quantities in terms of a security parameter: a setting that controls key sizes and other parts of the construction. Think of it as a size dial, not a score that by itself certifies a system. The aim is for attacks to become much harder as the parameter grows while legitimate operations remain manageable. A theorem about that growth still needs concrete analysis before it can justify a particular key size.

A security reduction connects breaking the construction with solving another problem believed to be difficult. It shows how an efficient attacker could be used to solve that problem, with stated resources and success probability. The conclusion depends on the problem being difficult in the relevant setting. The reduction’s own resource costs also matter; an extremely inefficient conversion may give little assurance at practical sizes.

Even a strong reduction leaves three questions to check. Does the construction meet a suitable definition under its assumptions? Does the program implement it correctly? Does the service enforce the assumed conditions? A correct encryption library cannot recognise a fraudulent payment instruction sent through an already compromised account.

14. Two revealing thought experiments

In an unauthenticated key exchange, Eve can read Alice and Bob’s encrypted conversation without learning either private exponent. She replaces the public contributions and establishes a separate secret with each of them. Every calculation still works.

We shall follow this attack, then examine a second failure in which an observer cancels the protection of two messages without recovering their encryption key. In each case, the missing condition is small enough to overlook and precise enough to test.

14.1 A stranger between Alice and Bob

Eve can intercept Alice’s and Bob’s public contributions and replace each with her own. She then shares one secret with Alice and a different secret with Bob, while each believes the secret is shared with the other. She never needs to discover their private numbers. The diagram and optional numbers show the substitution.

When Alice encrypts a message with a key derived from her shared value, Eve can derive the same key and read it. Eve then encrypts under the key she shares with Bob and forwards the result. She can relay Bob’s reply in the opposite direction. She may pass the messages on unchanged or alter them; an apparently successful encrypted conversation need not expose her.

This is a man-in-the-middle attack. Eve has changed the parties to the exchange without solving the underlying mathematical problem. To stop her, Alice and Bob must authenticate the exchange.

A suitable protocol binds the participants, their contributions and the exchange’s context together. For example, a trusted signing key can authenticate a transcript containing this information. Bob must verify the signature over the right data under a key he can associate with Alice. A signature on an unrelated message leaves Eve’s substitution unchecked.

Certificates and previously authenticated keys can supply that connection. If Eve can replace the supposed verification key too, her own signature gives Bob no reason to trust her contribution. Protocols can also establish authenticated keys from a shared password, but they need their own carefully analysed construction. Sending a bare password through an unauthenticated exchange does not supply one.

Alice and Bob need both a shared secret and a reason to believe they share it with each other. The protocol must tie both assurances to the same conversation.

14.2 One repeated number

Now suppose Alice and Bob already have an authenticated shared key. Their encryption system generates a stream of bits from that key and a nonce, then combines the stream with the message using exclusive OR. Write $S$ for the required part of the stream, $M$ for the message and $C$ for the ciphertext: $$C=M\oplus S.$$ XOR, written $\oplus$, has two useful properties: combining a string with itself gives zeros, and combining a string with zeros leaves it unchanged.

If Alice repeats both the key and nonce in this stream construction, it repeats the masking stream. Combining the two ciphertexts cancels that repeated mask and exposes a relationship between the messages. If Eve knows one message, she can recover the corresponding part of the other.

A different nonce changes the stream generator’s input. Where the requirement is uniqueness, a counter can supply it, provided it cannot restart under the same key or overlap another sender’s allocation. Randomly generated nonces can collide by accident, so their length and the number of messages matter. Section 17 develops this distinction.

AES-GCM also relies on nonce uniqueness. Reusing a nonce under the same key can compromise confidentiality and enable serious attacks on authenticity [6]. The exact leakage and forgery opportunities depend on the messages available to the attacker. Some constructions tolerate certain kinds of nonce misuse, but their stated guarantees determine what survives. The label “authenticated encryption” alone does not tell us.

14.3 A third problem hidden in a successful delivery

Suppose Bob accepts an authenticated instruction to make a payment. Eve records the encrypted record and sends the same bytes again the next day. She needs no plaintext, key or forged tag. If Bob pays twice, the protocol has accepted a replay.

The record’s authenticity establishes its authorised origin, but Bob still needs to check whether it is a new instruction. He might accept each authenticated sequence number once, or record which unique transaction identifiers he has processed. In either case, he must keep and check state. A timestamp can limit how long a record is valid, but Eve may replay it within that window. Bob needs a rule that prevents a second payment even while the original record remains valid.

15. Proving without revealing

If Alice sends Bob her password to prove she knows it, Bob may be able to log in as Alice. Can she convince him without giving him that ability?

A signature already lets a verifier check evidence of a signing key’s use without receiving the key. Zero knowledge addresses a broader question: can a prover establish a mathematical claim while revealing nothing further about its hidden evidence? That evidence is called a witness. In the example below, Alice’s hidden number is the witness. The verifier learns that the claim is supported; the privacy requirement concerns what else the interaction reveals.

Zero-knowledge proofs began with precise mathematical definitions [17]. We shall use a small modular-arithmetic example to see how such a claim can work. Its security depends on when the participants send each message and how they choose their random values.

15.1 Three requirements

Completeness asks whether an honest prover with the right information can convince an honest verifier. If Alice knows the secret and both follow the rules, the protocol should let her demonstrate it.

Soundness asks whether a verifier might accept a false claim. A sound protocol makes that probability suitably small. For a proof of knowledge, we need a related but different guarantee: a prover who convinces the verifier with sufficient probability must have a way to supply the witness. The formal definition describes an extraction procedure which obtains it from such a prover.

Zero knowledge asks what the verifier learns. Roughly, a procedure called a simulator must be able to generate an indistinguishable view of the interaction without the secret witness. Simply omitting the password from the messages is insufficient: their combined contents might still reveal it.

Each requirement does its own work. Simply refusing to interact hides the secret but fails completeness. One which always accepts gives no useful protection against false claims. Sending the secret may convince Bob but gives up the privacy we wanted. We need all three properties together.

15.2 A small challenge and response

Alice wants to prove she knows a private number related to a public one. She sends a fresh first message before Bob chooses one of two random challenges. Knowing the secret lets her answer either challenge, and Bob can check the one he asks. The small numbers below make this check visible, but are easy to break in practice.

15.3 Why the challenge matters

An impersonator can prepare an answer to one of Bob’s two questions, but must send the first message before learning which question Bob will ask. A fair challenge therefore gives that impostor at most a one-in-two chance per round under the stated assumptions. Answering both questions for the same first message would reveal the secret.

15.4 How can a convincing conversation reveal nothing?

A verifier can see a convincing record without learning Alice’s secret: a simulator can choose a challenge and answer first, then work backward to make a matching first message. A live impostor cannot choose Bob’s challenge after sending that first message. This distinction supports the privacy claim for an honest verifier.

This demonstrates honest-verifier zero knowledge. The calculation assumes Bob chooses his challenge honestly. A claim covering malicious verifiers needs further analysis; this simulation alone does not establish it.

Alice must also make a fresh random choice for every conversation. If she reuses the same choice and Bob asks different challenges, her two answers can reveal her private number. The privacy claim assumes the protocol’s random choices are made correctly.

15.5 Beyond identification

A prover can use modern zero-knowledge systems to establish more complex claims: that a hidden number lies within a range, that a calculation on private inputs was performed correctly, or that a credential meets a rule without exposing all its contents. To judge such a proof, first identify its public statement and private witness. A correct proof of a different statement may give you none of the assurance you need.

Some systems require a live exchange; others produce a proof that can be checked later. Their assumptions may involve hash functions, algebraic problems or setup information whose generation affects security. Their proving and checking costs also differ. Before relying on a proof, you need to know which statement it establishes, what its privacy definition covers and which setup assumptions it requires.

16. Why is managing keys so difficult?

If you encrypt the only copy of a family archive and lose its key, good encryption leaves you with a problem it was designed to create: recovering the files without the secret should be infeasible. The algorithm cannot recognise you as their rightful owner and make an exception. To protect the archive, you must plan both how to keep the key secret and how to recover it when a computer fails.

Key management covers creating, storing, using, replacing and destroying keys. It connects the algorithm’s rules to the people and programs allowed to use them. Even if an attacker cannot feasibly search the key space, they may be able to steal a key, misuse a decryption service or exploit a forgotten backup.

16.1 Making a key and keeping it

For an ordinary symmetric encryption key, we normally want a uniformly chosen bit string of the required length: every permitted string has the same probability. Typing characters that look irregular does not achieve this. A reputable cryptographic library obtains randomness from the operating system’s cryptographic random generator. Section 17 explains how a computer that follows instructions can still supply unpredictable inputs.

The program must also be able to use the key. If it reads an encrypted database every minute, someone cannot realistically type the key before every query. The program needs automatic access, so an attacker who takes over that program may gain access too.

A key file beside the database may protect against theft of a database export alone. It does little against an attacker who copies the whole machine. Putting the secret in source code gives it to everyone who receives that code; hiding the key file’s name offers little protection against someone who can search the disk. Whether the arrangement helps depends on what the attacker can obtain.

A key management service, or KMS, controls requests to use keys. A hardware security module, or HSM, can generate and use keys inside protected equipment, so a key need never leave that boundary in readable form during ordinary use. An application requests an operation; the service checks its authority and may record the request.

An attacker need not extract the key if they can misuse an authorised operation. If a compromised application may ask the service to decrypt a thousand records, the protected equipment may faithfully return all thousand. Access rules, request limits and independent auditing must address that route of attack.

16.2 A small key can protect many larger keys

We can give each file or group of records its own data encryption key. A key encryption key then protects those data keys through an appropriate authenticated wrapping or encryption scheme. Each encrypted data key can travel with its file, while the protected master key stays in special storage. This arrangement is called envelope encryption.

This lets us assign data keys to different users or periods while guarding a much smaller set of master keys. When replacing a master key, we may only need to rewrap the data keys, avoiding the work of decrypting and re-encrypting every large file. The scheme must bind each protected key to its intended context, so an attacker cannot substitute one file’s protected key for another’s.

The master key still concentrates authority. Someone who can use it without restriction may obtain every data key it protects.

Different purposes also need deliberate key separation. Reusing a message-authentication key as an encryption key in another protocol may invalidate the security argument. A cryptographic key derivation function can produce separate keys from suitable shared secret material by using distinct labels and context. Those labels identify the purposes; they are not passwords and need not be secret.

16.3 Losing, replacing and retiring keys

To recover the family archive after losing a computer, you may need a backup of its key. Encryption gives no central authority an automatic means of recovering it. The backup must be available to the right people and protected from everyone else. Keeping several unprotected copies helps recovery by creating several opportunities for theft.

An organisation may require several authorised people to recover a key, using mathematical secret sharing or procedural controls. This can prevent one person’s loss or misuse from deciding everything. The organisation also needs to test recovery under controlled conditions: a stored backup is useful only if the right people can restore it.

Key rotation replaces an old key with a new one. It can limit the new material exposed by a stolen old key and support changes in algorithms or staff responsibilities. But encrypting tomorrow’s files under a new key leaves yesterday’s files exposed to an attacker who copied yesterday’s key. Deleting our copy cannot delete theirs.

Retirement depends on the key’s job. You may need an old decryption key to read an archive. An old signing key should stop creating signatures, while its public verification key may still be needed to check older documents. Establishing when a signature existed can require a timestamp or archival records; the signature alone does not supply that history.

Revocation tells verifiers to stop accepting an authority they previously trusted. An employer might revoke an employee’s access; a certificate authority might revoke a certificate. Every relevant verifier must learn and enforce the change, including machines that were offline or have cached old information. Protocols, time limits and operational policy determine how reliably that happens.

16.4 How a secure connection brings these ideas together

When your browser connects to a website, Transport Layer Security, or TLS, brings several of these jobs together. The following outline describes a typical certificate-authenticated TLS 1.3 connection: key agreement, authentication, key derivation and authenticated encryption. It groups responsibilities rather than reproducing the exact network-message sequence [15].

The browser and server first agree supported algorithms and establish shared secrets, typically using fresh, temporary Diffie–Hellman key shares. The server supplies a certificate chain and a signature binding its identity to the current exchange. The browser checks the chain against trusted authorities, checks the website name and validity information, and verifies the cryptographic evidence. Receiving a certificate without checking it would leave the browser unable to authenticate the server.

Both sides derive traffic keys from the agreed secrets and the recorded handshake context. They exchange verification messages to confirm possession of the appropriate secrets and detect changes to the conversation. They then protect application data with authenticated encryption, using separate keys for each direction. The exact ordering and resumed-session rules add details omitted here.

Temporary key agreement can provide forward secrecy. An attacker who records today’s connection and later steals the server’s long-term signing key should still be unable to recover today’s traffic secrets from that key alone. This depends on the underlying assumptions and proper erasure of the temporary secrets. It cannot protect a session whose own temporary secrets were stolen, or a message read from the browser before encryption.

The browser and server are endpoints: devices and programs where the data originates and is read. TLS protects the traffic between them. A malicious browser extension, a compromised server or an authorised user copying a document can obtain data at an endpoint, where it is already readable.

The archive needs a recoverable key; the website needs keys that the server can use without exposing them to every application. In both cases, someone must decide who may use each key, how to withdraw that permission and what to recover after a failure.

17. Randomness and uncertainty

The strings 0101010101010101 and 1100100111010010 are each one possible outcome. Each has probability 1 out of $2^{16}$ if you generate them by sixteen independent fair coin tosses. One looks orderly; the other looks less so. Their appearance tells you little about how they were chosen. Someone could also copy the second string from a book. An attacker who knows the book would then know the whole secret.

Cryptography needs a way to describe that difference. The algorithm must follow its rules reliably, but some inputs must remain unpredictable to the attacker. We must examine how those inputs were generated and what the attacker already knows.

17.1 Counting possibilities carefully

Throw a fair six-sided die independently six times. One throw has six equally likely outcomes. Two throws have $6\times6=36$ ordered outcomes because any first result can be followed by any of six second results. Six throws have $$6^6=46\,656$$ possible ordered sequences. The sequence $1,1,1,1,1,1$ has exactly the same probability as $2,6,1,4,3,5$. Under this procedure, being memorable does not make a particular sequence more likely.

Six independent fair die throws give 46,656 equally likely sequences, a little more uncertainty than fifteen fair bits and less than sixteen. If one output occurs half the time, its length still may be sixteen bits, but an attacker’s best guess already succeeds half the time. The calculations below turn those chances into bit counts.

If we announce the first five of our six die throws, only one throw remains unknown. An attacker now has only six possibilities to check. A security argument must account for information the attacker already has.

17.2 Why people make unreliable random generators

People choosing passwords favour words, names, familiar patterns and small changes that meet a password rule. An attacker can try these likely choices first. Counting ninety possible characters at each position would describe uniform selection from that alphabet. It would not describe how those people choose.

Related choices need another adjustment. If you append a website’s name to a base password, an attacker who learns one password may infer the others. Those choices are correlated: learning one changes what the attacker expects from another. We multiplied by six at each step in the die calculation because the throws were independent.

A password manager can generate and store independent random passwords, so you need not invent or remember each one. Its unlocking password and recovery arrangements still need protection. A server that checks passwords should store suitable salted password verifiers, using a method such as appropriately configured Argon2id [10]. Readable passwords expose the secret immediately; a single fast hash lets an attacker test guesses too cheaply. Slowing those guesses helps, but adds no uncertainty to the password you chose.

You can also use independent die throws to select entries from a published word list. The words make random indices easier to remember; the selection procedure supplies the uncertainty. Choosing a pleasing sentence first does not give it the same distribution.

17.3 Where a computer obtains uncertainty

Although a computer follows deterministic instructions, its hardware interacts with the physical world. Devices and operating-system facilities can collect unpredictable variation, assess its uncertainty and use it to initialise a generator. Designers must account for bias, detect failures and combine inputs conservatively. A noisy measurement does not automatically supply independent fair bits.

A cryptographically secure pseudorandom number generator, or CSPRNG, starts from a short secret value called a seed. Its evolving internal information is its state. A deterministic algorithm expands that state into a longer output stream. Under the generator’s assumptions and usage conditions, an efficient attacker without the state should be unable to distinguish the output from appropriate random bits or predict useful future outputs [19].

This gives a computational guarantee, unlike the one-time pad’s perfect secrecy. Each possible seed leads to one initial output stream, so the number of distinct streams cannot exceed the number of seeds. A deterministic generator seeded with $s$ secret bits has at most $2^s$ possible initial output streams, however long they are. It cannot create unlimited information-theoretic secrecy. Its purpose is to make distinguishing a long output stream from random bits computationally difficult without the smaller secret. Section 13 explains this kind of guarantee.

Software must protect that state throughout the generator’s use. Copying a virtual machine may copy its generator state; restoring a snapshot may return a process to an earlier state. Without suitable handling, the system may then repeat keys or nonces. Some generator designs also protect past outputs after a later state compromise, or restore future unpredictability after fresh secret input arrives. These guarantees depend on the particular design.

Application programmers normally obtain random values through a reputable library using the operating system’s documented cryptographic interface. A generator for games or simulations may have no cryptographic prediction resistance. A clock reading changes often, but an attacker may be able to estimate it. Neither is a substitute for the required source.

17.4 Keys, nonces and salts ask different questions

A secret encryption key normally needs to be unpredictable and have the specified length. A nonce, a value used once in the relevant context, often needs to be unique under a key. In a counter-based encryption scheme, a carefully maintained counter can meet that requirement while remaining public and predictable. Other constructions require an unpredictable initial value or impose further restrictions. The scheme’s rule determines what the input must provide.

Randomly chosen nonces can repeat. Each new choice could match any earlier one, so a scheme needs a suitable nonce length and a limit on how many messages use one key. The calculation below estimates the risk while repeats remain rare.

A password-hashing salt separates stored records. Different salts cause the same password to produce different hash results, frustrating a precomputed table intended for many users. The salt is normally stored with the hash, where an attacker can read it. It cannot prevent guessing against one stolen record. A suitable random salt makes accidental repetitions unlikely; hiding it is unnecessary.

Before choosing an input, ask what the scheme needs from it: unpredictability, uniqueness under a key, or separation between records. Then choose the generation procedure and usage limits that meet that requirement.

18. Is cryptography secure and complete?

An attacker may learn a secret from the time a server takes to reject a message, without defeating its encryption formula. A proof about that formula may be sound while leaving this route of attack open. To judge the system, we need both the proof and evidence that the software, hardware and key handling meet its assumptions.

We also need to ask how long those assumptions should hold. A file may need to remain secret after today’s computers and public-key methods have been replaced. The final questions are therefore practical ones: what does our evidence cover, where does it stop, and what happens when the attacker’s capabilities change?

18.1 What a proof does, and what it leaves open

A security proof may show how to turn an efficient attacker on an encryption scheme into a solver for another problem believed to be difficult. This is a reduction. If the difficulty assumption holds and the reduction gives useful quantitative bounds, it supplies a reason to trust the construction: breaking it would also break the more extensively studied assumption [1, 2].

The assumption remains unproved. We must also check how the reduction changes the attacker’s required resources: a large loss can make the resulting bound too weak for a proposed parameter choice. Key size alone may not decide the answer. Numbers of users, messages and attack attempts can also enter the calculation.

The model must match the attacker’s opportunities. A proof allowing chosen plaintexts may say too little about a server that reveals details of failed decryptions. An authentication proof assuming fresh challenges does not cover a program that reuses them. These gaps tell us what to fix in the model or the program. They do not invalidate the result proved under its stated premises.

18.2 The surrounding machine is part of the story

A computer reveals more than an algorithm’s intended output. It takes time, accesses memory and consumes electrical power. An attacker may use those observations as a side channel to learn about a secret. For example, if a calculation’s timing depends on secret values, measuring the time may reveal information that the final result conceals.

Two programs implementing the same formula can therefore offer different protection. Implementers use carefully designed constant-time operations to avoid relevant secret-dependent variation, along with other protections suited to the platform and threat model. The term does not promise that every observation of a real machine is identical. Specialised physical attacks may require further measures.

A server can also leak information by explaining why a ciphertext failed. An attacker who repeatedly submits ciphertexts and compares the errors may learn more than the encryption definition permits. Returning one error message may still leave differences in timing or later behaviour. The protocol and its implementation must handle these observations together.

Other failures bypass the primitive directly. A program may verify a signature on one set of bytes and act on another. An administrator may disable certificate checking; a backup may expose a key; many devices may start with identical generator state. Independent review, maintained libraries, protocol tests and sound operating procedures help detect these failures. A proof of the primitive alone does not.

Encryption also leaves some observations outside its promise. An observer may see which network addresses communicate, when they connect and roughly how much data they send. This is metadata: information about the communication rather than its protected contents. Padding, relays and other techniques can reduce particular disclosures, but hiding message contents does not automatically hide these observations.

Authenticating a statement’s origin does not establish its truth. A person can sign a falsehood, and an intended recipient can disclose a decrypted message. A signature also cannot by itself show that a human understood what they approved. Those judgements require evidence beyond the cryptographic operation.

18.3 What changes if computers change?

The earlier work estimates concerned attackers using ordinary, or classical, computers. A quantum computer processes information differently and could solve some of the relevant problems much more efficiently. Its effect depends on the problem; we cannot replace each earlier estimate by one common speed-up factor.

Shor’s algorithm gives efficient quantum procedures for integer factorisation and the discrete logarithm problems used by standard RSA, Diffie–Hellman and elliptic-curve systems [20]. A large, sufficiently reliable quantum computer running these procedures would threaten those public-key constructions. A modest increase in RSA key size would not remove the underlying problem.

Having the algorithm does not establish that a machine of the required scale and reliability is available. But waiting for such a machine can leave long-lived secrets at risk. An adversary can record traffic now and attempt to recover it later. A decision about protecting information for decades must account for that future attempt as well as today’s attack costs.

A large enough quantum computer could speed up an idealised search for a symmetric key. The improvement is substantial but differs from the attack on RSA and Diffie–Hellman. Key size and the real cost of quantum operations still matter.

The query count is not the full cost of an attack. Carrying out a cryptographic calculation coherently on a quantum machine requires substantial resources. Parallelisation, memory and available hardware affect the estimate too. Hash preimages, collisions, symmetric keys and public-key algebra need separate analyses; saying that quantum computers halve all security would hide these differences.

18.4 Cryptography after the present public-key assumptions

Post-quantum cryptography develops constructions intended to resist both classical and quantum adversaries. These usually run on ordinary computers, without a quantum communication channel. Researchers choose problems for which no comparably destructive quantum algorithm is known, then study the resulting assumptions, constructions and implementations.

In 2024 the US National Institute of Standards and Technology published FIPS 203 for ML-KEM, FIPS 204 for ML-DSA and FIPS 205 for SLH-DSA [22, 23, 24]. ML-KEM is a key encapsulation mechanism: parties use a public key and an encapsulation to establish a shared secret. They can derive keys from that secret and protect messages with authenticated encryption. ML-KEM does not sign messages or directly replace every operation called encryption.

ML-DSA and SLH-DSA provide signatures. ML-KEM and ML-DSA use structured lattice problems, while SLH-DSA uses hash functions. Explaining those constructions would require more mathematics than we have developed here. For the present argument, their different assumptions matter, as do their costs: key, signature and ciphertext sizes, memory use and running time may differ from those of the systems they replace.

Standardisation gives implementers a precise specification backed by substantial public analysis. It cannot promise that nobody will find a weakness. Moving to a new construction still requires correct software, compatible communicating systems, suitable protocols and operational tests. Combining constructions can sometimes improve resilience, but researchers must analyse the combination; appending two algorithms does not automatically preserve every property of both.

Cryptographic agility is the ability to replace algorithms and keys without rebuilding the whole system. To make that useful, operators need to know which algorithms they use, which data depends on them and how to authenticate a change. Allowing unrestricted choices can create configuration errors or let an attacker force a weaker option. A controlled, tested replacement process addresses that risk.

18.5 What we can now understand

You can understand a security claim without being able to design a cipher. The next step, if you want to study the definitions and proofs, is a text such as Katz and Lindell or Boneh and Shoup [1, 2]. TLS 1.3’s specification shows how a protocol connects the constructions [15].

Return to the browser connection from Chapter 16. Its encrypted records protect data in transit, its certificate checks help identify the server, and its temporary key agreement can protect old sessions from a later theft of the signing key. Each claim answers a different question. If you need the website to keep a document secret after receiving it, you must ask what happens at the server too.

References and further reading