C
= 88
7
(mod 187)
(7) Working this out directly on a calculator is not straightforward, because the display cannot cope with such large numbers. However, there is a neat trick for calculating exponentials in modular arithmetic. We know that, since 7 = 4 + 2 + 1,
88
7
(mod 187) = [88
4
(mod 187) × 88
2
(mod 187) × 88
1
(mod 187)] (mod 187)
88
1
= 88 = 88 (mod 187)
88
2
= 7,744 = 77 (mod 187)
88
4
= 59,969,536 = 132 (mod 187)
88
7
= 88
1
× 88
2
× 88
4
= 88 × 77 × 132 = 894,432 = 11 (mod 187)
Bob now sends the ciphertext,
C
= 11, to Alice.
(8) We know that exponentials in modular arithmetic are one-way functions, so it is very difficult to work backward from
C
= 11 and recover the original message,
M
. Hence, Eve cannot decipher the message.
(9) However, Alice can decipher the message because she has some special information: she knows the values of
p
and
q
. She calculates a special number,
d
, the decryption key, otherwise known as her private key. The number
d
is calculated according to the following formula
e
×
d
= 1 (mod (
p
-1) × (
q
-1))
7 ×
d
= 1 (mod 16 × 10)
7 ×
d
= 1 (mod 160)
d
= 23
(Deducing the value of
d
is not straightforward, but a technique known as Euclid’s algorithm allows Alice to find
d
quickly and easily.)
(10) To decrypt the message, Alice simply uses the following formula,
M
=
C
d
(mod 187)
M
= 11
23
(mod 187)
M
= [11
1
(mod 187) × 11
2
(mod 187) × 11
4
(mod 187) × 11
16
(mod 187)] (mod 187)
M
= 11 × 121 × 55 × 154 (mod 187)
M
= 88 =
X
in ASCII.
Rivest, Shamir and Adleman had created a special one-way function, one that could be reversed only by somebody with access to privileged information, namely the values of
p
and q. Each function can be personalized by choosing
p
and
q
, which multiply together to give
N
. The function allows everybody to encrypt messages to a particular person by using that person’s choice of
N
, but only the intended recipient can decrypt the message because the recipient is the only person who knows
p
and
q
, and hence the only person who knows the decryption key,
d
.
Glossary
ASCII
American Standard Code for Information Interchange, a standard for turning alphabetic and other characters into numbers.
asymmetric key cryptography
A form of cryptography in which the key required for encrypting is not the same as the key required for decrypting. Describes public key cryptography systems, such as RSA.
Caesar-shift substitution cipher
Originally a cipher in which each letter in the message is replaced with the letter three places further on in the alphabet. More generally, it is a cipher in which each letter in the message is replaced with the letter
x
places further on in the alphabet, where
x
is a number between 1 and 25.
cipher
Any general system for hiding the meaning of a message by replacing each letter in the original message with another letter. The system should have some built-in flexibility, known as the key.
cipher alphabet
The rearrangement of the ordinary (or plain) alphabet, which then determines how each letter in the original message is enciphered. The cipher alphabet can also consist of numbers or any other characters, but in all cases it dictates the replacements for letters in the original message.
ciphertext
The message (or plaintext) after encipherment.
code
A system for hiding the meaning of a message by replacing each word or phrase in the original message with another character or set of characters. The list of replacements is contained in a codebook. (An alternative definition of a code is any form of encryption which has no built-in flexibility, i.e., there is only one key, namely the codebook.)
codebook
A list of replacements for words or phrases in the original message.
cryptanalysis
The science of deducing the plaintext from a ciphertext, without knowledge of the key.
cryptography
The science of encrypting a message, or the science of concealing the meaning of a message. Sometimes the term is used more generally to mean the science of anything connected with ciphers, and is an alternative to the term cryptology.
cryptology
The science of secret writing in all its forms, covering both cryptography and cryptanalysis.
decipher
To turn an enciphered message back into the original message. Formally, the term refers only to the intended receiver who knows the key required to obtain the plaintext, but informally it also refers to the process of cryptanalysis, in which the decipherment is performed by an enemy interceptor.
decode
To turn an encoded message back into the original message.
decrypt
To decipher or to decode.
DES
Data Encryption Standard, developed by IBM and adopted in 1976.
Diffie-Hellman-Merkle key exchange
A process by which a sender and receiver can establish a secret key via public discussion. Once the key has been agreed, the sender can use a cipher such as DES to encrypt a message.
digital signature
A method for proving the authorship of an electronic document. Often this is generated by the author encrypting the document with his or her private key.
encipher
To turn the original message into the enciphered message.
encode
To turn the original message into the encoded message.
encrypt
To encipher or encode.
encryption algorithm
Any general encryption process which can be specified exactly by choosing a key.
homophonic substitution cipher
A cipher in which there are several potential substitutions for each plaintext letter. Crucially, if there are, say, six potential substitutions for the plaintext letter a, then these six characters can only represent the letter a. This is a type of monoalphabetic substitution cipher.
key
The element that turns the general encryption algorithm into a specific method for encryption. In general, the enemy may be aware of the encryption algorithm being used by the sender and receiver, but the enemy must not be allowed to know the key.
key distribution
The process of ensuring that both sender and receiver have access to the key required to encrypt and decrypt a message, while making sure that the key does not fall into enemy hands. Key distribution was a major problem in terms of logistics and security before the invention of public key cryptography.
key escrow
A scheme in which users lodge copies of their secret keys with a trusted third party, the escrow agent, who will pass on keys to law enforcers only under certain circumstances, for example if a court order is issued.
key length
Computer encryption involves keys which are numbers. The key length refers to the number of digits or bits in the key, and thus indicates the biggest number that can be used as a key, thereby defining the number of possible keys. The longer the key length (or the greater the number of possible keys), the longer it will take a cryptanalyst to test all the keys.
monoalphabetic substitution cipher
A substitution cipher in which the cipher alphabet is fixed throughout encryption.
National Security Agency (NSA)
A branch of the U.S. Department of Defense, responsible for ensuring the security of American communications and for breaking into the communications of other countries.
onetime pad
The only known form of encryption that is unbreakable. It relies on a random key that is the same length as the message. Each key can be used once and only once.
plaintext
The original message before encryption.
polyalphabetic substitution cipher
A substitution cipher in which the cipher alphabet changes during the encryption, for example the Vigenère cipher. The change is defined by a key.
Pretty Good Privacy (PGP)
A computer encryption algorithm developed by Phil Zimmermann, based on RSA.
private key
The key used by the receiver to decrypt messages in a system of public key cryptography. The private key must be kept secret.
public key
The key used by the sender to encrypt messages in a system of public key cryptography. The public key is available to the public.
public key cryptography
A system of cryptography which overcomes the problems of key distribution. Public key cryptography requires an asymmetric cipher, so that each user can create a public encryption key and a private decryption key.
quantum computer
An immensely powerful computer that exploits quantum theory, in particular the theory that an object can be in many states at once (superposition), or the theory that an object can be in many universes at once. If scientists could build a quantum computer on any reasonable scale, it would jeopardize the security of all current ciphers except the onetime pad cipher.
quantum cryptography
An unbreakable form of cryptography that exploits quantum theory, in particular the uncertainty principle-which states that it is impossible to measure all aspects of an object with absolute certainty. Quantum cryptography guarantees the secure exchange of a random series of bits, which is then used as the basis for a onetime pad cipher.
RSA
The first system that fitted the requirements of public key cryptography, invented by Ron Rivest, Adi Shamir and Leonard Adleman in 1977.
steganography
The science of hiding the existence of a message, as opposed to cryptography, which is the science of hiding the meaning of a message.
substitution cipher
A system of encryption in which each letter of a message is replaced with another character, but retains its position within the message.
symmetric key cryptography
A form of cryptography in which the key required for encrypting is the same as the key required for decrypting. The term describes all traditional forms of encryption, i.e. those in use before the 1970s.
transposition cipher
A system of encryption in which each letter of a message changes its position within the message, but retains its identity.
Vigenère cipher
A polyalphabetic cipher which was developed around 1500. The Vigenère square contains 26 separate cipher alphabets, each one a Caesar-shifted alphabet, and a keyword defines which cipher alphabet should be used to encrypt each letter of a message.
Acknowledgments
While writing this book I have had the privilege of meeting some of the world’s greatest living codemakers and codebreakers, ranging from those who worked at Bletchley Park to those who are developing the ciphers that will enrich the Information Age. I would like to thank Whitfield Diffie and Martin Hellman, who took the time to describe their work to me while I was in sunny California. Similarly, Clifford Cocks, Malcolm Williamson and Richard Walton were enormously helpful during my visit to cloudy Cheltenham. In particular, I am grateful to the Information Security Group at Royal Holloway College, London, who allowed me to attend the M.Sc. course on information security. Professor Fred Piper, Simon Blackburn, Jonathan Tuliani, and Fauzan Mirza all taught me valuable lessons about codes and ciphers.
While I was in Virginia, I was fortunate to be given a guided tour of the Beale treasure trail by Peter Viemeister, an expert on the mystery. Furthermore, the Bedford County Museum and Stephen Cowart of the Beale Cypher and Treasure Association helped me to research the subject. I am also grateful to David Deutsch and Michele Mosca of the Oxford Centre for Quantum Computation, Charles Bennett and his research group at IBM’s Thomas J. Watson Laboratories, Stephen Wiesner, Leonard Adleman, Ronald Rivest, Paul Rothemund, Jim Gillogly, Paul Leyland and Neil Barrett.