Encryption appeared in 0004.b as one digital safeguard among several, but it underlies many of the others, from HTTPS to the protection of a stolen laptop, so it deserves a closer look. This section first sets out the vocabulary every cipher shares. It then follows cryptography roughly as it developed. Classical ciphers show how encryption can fail, and the lessons drawn from those failures, about secret keys, key length, and human procedure, still govern modern design. Modern cryptography then solves two problems, keeping data secret and proving who sent it, using two kinds of key arrangement. The section ends with a related use of hashing, storing passwords, and with the limits of encryption, including the one that quantum computers may someday pose.

The building blocks#

Encryption uses an algorithm, a published procedure, and a key, a secret value, to convert readable plaintext into unreadable ciphertext. Decryption reverses the process using the appropriate key.¹ Suppose two teachers use the same encryption program, the algorithm, on the same exam file, each with a different key. The key changes how the algorithm transforms the data, so their ciphertexts differ, and neither teacher's key will decrypt the other's file. Trying the wrong key doesn't damage anything; it simply produces meaningless output and leaves the stored ciphertext intact, so the correct key will still work.

The key is what distinguishes encryption from encoding, which changes the form of data without any secret. Hexadecimal, described under 0003.h, is an encoding, and so is Base64, which represents binary data as text. Anyone can convert encoded data back, so a message that has only been encoded is not protected at all.

Classical ciphers and what they teach#

The oldest ciphers make these ideas concrete. The Caesar cipher shifts each letter forward by the same fixed number of positions in the alphabet. With a shift of 3, A becomes D, C becomes F, and T becomes W, so HELLO becomes KHOOR and ATTACK becomes DWWDFN.¹ In a program, letters are often numbered from 0 for A to 25 for Z, and the shift must wrap around from the end of the alphabet to the start, which is done with the remainder after dividing by 26: msg[i] = (msg[i] + shift) % 26. For Z shifted by 3, 25 + 3 is 28, and 28 % 26 is 2, which is C.

The Caesar cipher is easily broken, in two ways. The first is brute force: there are only 25 useful shifts, so an attacker can try each and look for readable text. The second, frequency analysis, works even on ciphers with many more possible keys. Any cipher that always substitutes the same ciphertext letter for the same plaintext letter preserves how often each letter occurs. In English, E is the most common letter, at about 12 percent of ordinary text, so if Q makes up about 12 percent of a long ciphertext, Q probably stands for E or another common letter. Polyalphabetic ciphers resist simple frequency analysis by using a sequence of shifts, so that the same plaintext letter is enciphered differently at different positions. If the shifts alternate between 1 and 5, a run of four Es becomes F, J, F, J, and spreading each letter across several ciphertext letters in this way flattens the frequencies an attacker would look for.

History shows that even a much stronger design can fail. During World War II, Germany used the Enigma machine, which had an enormous number of possible settings, and Allied codebreakers at Bletchley Park broke it anyway.¹ They succeeded partly through sustained analysis and partly through the German operators' procedural errors, such as reusing keys and sending predictable messages. Daily weather reports, for instance, contained predictable phrases, which gave the codebreakers known plaintext: a guessed fragment of a message let them test candidate settings and rule out those that didn't turn the ciphertext into the guessed words. The intelligence from decrypted messages influenced Allied military operations during the war. The lesson is that a vast number of settings doesn't ensure security when procedures are poor, and reused keys and predictable message headers repeat the same kind of weakness today.

A second lesson concerns what should be secret. Under Kerckhoffs's principle, a system's security should depend on keeping the key secret, not the algorithm. A design known to many people, such as everyone who builds or uses a product, is hard to keep secret, and if it leaks it can't easily be changed, whereas a key can be protected and replaced. Open algorithms have another advantage: published ciphers get scrutiny from experts, so their flaws are more likely to be found before attackers exploit them. Strong open algorithms are used with random keys and random seed values, and that requirement matters. If a program generates keys with predictable random numbers, or if its key is written into source code that the public can read, the cipher may be sound but anyone can obtain the key, and the strength of the algorithm offers no protection.

The third lesson is about key length, which sets how hard brute force is. Each additional bit doubles the number of possible keys, so longer keys are much harder to guess by trying every one. A 40-bit key has 2^40 possible values, so at 2^30 guesses per second an attacker can try them all in 2^10 seconds, about 17 minutes. A 42-bit key at the same speed takes 2^42 / 2^30, or 2^12 seconds, which is 4,096 seconds, a little more than an hour. Adding four more bits multiplies the number of keys, and the time, by 2^4, or 16, so a search that took one day would take 16 days. Modern keys of 128 bits or more are far beyond brute force. Key length addresses only that one attack, though. Attackers often go around encryption instead of through it, and longer keys don't help when they steal passwords.

Keeping data secret: symmetric, asymmetric, and hybrid encryption#

Modern encryption comes in two arrangements of keys. In symmetric encryption, one shared key both encrypts and decrypts. It is fast, as in the Advanced Encryption Standard (AES), which makes it suitable for large amounts of data such as whole disks. Its difficulty is the key itself. The parties must exchange the key securely, and sending the key along with the ciphertext, for example in the same email, gives an interceptor everything needed to decrypt it. Each pair of people who want to communicate privately also needs its own key, so n people need n(n-1)/2 keys, and 10 people need 10 * 9 / 2, or 45. For whole-disk encryption, neither problem arises, since the owner is the only user and no key has to be sent anywhere.

Asymmetric encryption, also called public-key encryption, solves the exchange problem with a mathematically related key pair. Data encrypted with the public key can be decrypted only with the matching private key, so anyone can write to you, and only you can read it.² A newspaper that wants to receive anonymous tips can post its public key online and decrypt tips with its private key. The public key is meant to be shared and is safe to share: someone who copies it can encrypt further messages to its owner but can't read a message encrypted with it, since the public key doesn't reveal the private key. The private key is what must stay private, and if it is stolen, the thief can decrypt every captured message ever encrypted to the matching public key. RSA is a common asymmetric algorithm. It lets parties communicate with no previously shared secret, and its cost is speed, since it is much slower than symmetric encryption. (Not every cryptographic name is a cipher: SHA-256 and bcrypt, which appear below, are hash functions.)

Each kind of encryption has the strength the other lacks, so real systems combine them in hybrid encryption. A web connection using HTTPS typically uses an asymmetric method to establish a shared key securely, then uses fast symmetric encryption such as AES for the rest of the communication, since key-pair operations are too slow for a large, continuous volume of data. Some of these methods let two parties agree on a shared key over an open network, where each side's private value never crosses the network, so an eavesdropper who records the whole exchange still doesn't obtain the shared key. The same idea works for sending a large file: encrypt the file with a new AES key, then encrypt that key with the recipient's public key. The fast cipher handles the large file, the public key protects the shared key on its way, and only the recipient's private key can recover it.

Proving who sent it: signatures and certificates#

Keeping data secret is one problem, and proving where data came from is another. Encryption alone doesn't identify a sender, because anyone can obtain a public key and encrypt a message with it. A digital signature reverses the roles of the keys. It is created with the signer's private key, which only the signer holds, and verified with the signer's public key, which anyone can use.² A valid signature demonstrates authenticity, that the holder of the private key signed it, and integrity, that the content hasn't changed since. Any change to the signed content makes verification fail, which reveals the alteration, though verification doesn't repair it. Software publishers sign their updates for this reason.

A signature shows that a private key was used, not who was holding it. A private key can't be changed or reset once it is created, so losing it or having it compromised is a serious disadvantage of the method. If a software publisher's signing key is stolen, signatures made with it after the theft are suspect, and the publisher must revoke the key pair, replace it, and inform its customers so that they stop trusting signatures made with the stolen key.

Signatures raise a further question: how do you know that a public key really belongs to the person or site it claims to? Public key infrastructure (PKI) answers it with certificates, documents issued by trusted certificate authorities that bind a public key to an identity. This is how browsers verify the sites they connect to using HTTPS: the site presents a certificate, and the browser checks that an authority it trusts has vouched that the key belongs to that site. A certificate says who holds a key, not that the holder is honest or that its systems are secure. Certificates have validity periods, and an expired certificate triggers a browser warning because it can no longer verify the site's identity, which doesn't mean that data was lost or a key stolen. A self-signed certificate, one the site issued to itself, also triggers a warning, since no authority the browser trusts has vouched for it. The whole system depends on trust in the authorities, so a compromised authority is serious: a fraudulent certificate issued in a bank's name binds an attacker's key to the bank, and browsers may accept the attacker's server as the genuine bank without any warning.

Storing passwords#

The cryptographic hash described under 0004.b has a second use, protecting stored passwords, and it fits here because it shows a design that gives attackers as little as possible. A site shouldn't store passwords in a form it can read, because a stolen database would then reveal them directly. Instead, it stores a hash of each password, and when a user logs in, it hashes what was typed and compares the results. Two refinements matter. A salt is a random value, different for each account, combined with the password before hashing, so that identical passwords produce different stored values and an attacker can't crack them all at once. A slow hash function, such as bcrypt, limits how many guesses an attacker can try against a stolen database. A fast hash such as SHA-256 is the wrong tool for this job even with salts, because it is designed for speed and lets an attacker test billions of guesses per second. One consequence is visible to users: a properly designed system can't retrieve your password, only let you reset it, so a site that can email you your current password is storing it in a recoverable form and isn't hashing it.

The limits of encryption#

Encryption is strong where it applies, but it applies only to data in a particular place and state. It doesn't protect data if the key or password is compromised: a burglar who takes an encrypted drive along with the note holding its passphrase has everything needed. It doesn't protect data at an endpoint, where data must be decrypted to be used, so spyware on a phone can read each message as it is displayed without breaking any encryption. It doesn't hide metadata, the records of who contacted whom and when, which can reveal a relationship even when the contents stay secret.² Encryption of a device's storage protects a locked or powered-off device, and it does little once the device is unlocked and running, since the files are then accessible to anyone using it. Finally, HTTPS protects data in transit, on its way to a server, not records stored on that server. Each stage where data exists needs its own protection.

The future may bring a new limit. Large quantum computers could break widely used public-key algorithms such as RSA, which relies on the difficulty of factoring large numbers, because such machines could factor efficiently. This threat motivates post-quantum cryptography, new public-key algorithms designed to resist quantum attack. Planning should begin now for data that must stay secret for decades, because traffic recorded today could be decrypted later when such computers exist. A different technology, Quantum Key Distribution (QKD), uses quantum physics to detect eavesdropping during key exchange, because observing the quantum signal disturbs it. QKD suits high-value links, but it addresses only eavesdropping on key exchange, so it does nothing about, for instance, staff who are tricked into typing their passwords on a fake site. Vendors sometimes advertise products as "quantum-proof," and such claims call for evidence, such as use of openly reviewed algorithms. In keeping with Kerckhoffs's principle, secrecy about an algorithm is a reason for caution, not reassurance. Encryption fails most often through flaws around it, in the software that uses it, and 0004.e turns to those flaws.

• plaintext: readable data before encryption
• ciphertext: encrypted, unreadable data
• algorithm: the procedure used to encrypt and decrypt
• key: the secret value that controls encryption and decryption
• encoding: a change of form, such as hexadecimal or Base64, that needs no key and isn't encryption
• Caesar cipher: a cipher that shifts each letter by a fixed amount
• frequency analysis: breaking a substitution cipher by matching letter frequencies
• polyalphabetic cipher: a cipher that uses a sequence of shifts, so the same letter can be enciphered differently
• known plaintext: a known or guessed piece of a message, used to test candidate keys
• Kerckhoffs's principle: security should depend on keeping the key secret, not the algorithm
• symmetric encryption: one shared key for encryption and decryption, as in AES
• asymmetric (public-key) encryption: a key pair in which data encrypted with the public key can be decrypted only with the private key, as in RSA
• hybrid encryption: using asymmetric methods to establish a shared key, then symmetric encryption for the data
• digital signature: a value created with a private key and verified with the public key, showing authenticity and integrity
• public key infrastructure (PKI): certificates from trusted certificate authorities that bind public keys to identities
• certificate authority: an organization trusted to issue certificates
• self-signed certificate: a certificate not vouched for by a trusted authority
• salt: a random value combined with each password before hashing
• bcrypt: a deliberately slow hash function for storing passwords
• metadata: data about communication, such as who contacted whom and when
• post-quantum cryptography: public-key algorithms designed to resist quantum computers
• Quantum Key Distribution (QKD): using quantum physics to detect eavesdropping during key exchange

Practice: practice questions for 0004.d

1. MWC2, Encryption: Caesar and polyalphabetic ciphers, and keeping secrets beyond the math. ↩ ↩2 ↩3

2. MWC2, Sub Rosa: public and private keys in a messaging system. ↩ ↩2 ↩3