From Private to Public Key Ciphers in Three Easy Steps
Cryptography is the attempt to answer the question "How can two parties exchange private information via a public channel?" When the two parties know each another, they may use a traditional private key cryptosystem. What happens when they don't? How can two parties who don't know one another (have never met, never exchanged information) find a way to securely communicate? By public key cryptography. In this article we provide a simple (and, at times, simplistic) introduction to public key cryptography by talking about, in turn, addition, multiplication and exponentiation.
I. Julius Caesar and the invention of cryptography
Cryptography, according to the Roman historian Suetonius, began with Julius Caesar, who "if he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others."
Caesar's method for making his messages secret is thus straightforward, one enciphers a message by replacing every letter with the one three letters down the alphabet: a is replaced by D, b is replaced by E, etc. For example, the plaintext "I came, I saw, I conquered" becomes the ciphertext L FDPH L VDZ L FRQTXHUHG. Deciphering is the reverse process: moving three letters backwards. The crypto-algorithm (moving through the alphabet) and the enciphering key (three forwards) together make a cryptosystem.
As another example, enciphering Brutus with key "move 7", i.e. +7, produces IYBABZ, since we have, naturally enough, counted A as the letter after Z, so B is indeed seven letters after u in the alphabet. To think of the enciphering steps mathematically, we first translate letters to numbers (a→ 1, b → 2, etc.), add 7 modulo 26, and then translate the resulting numbers back to letters. (Of course, for such a simple cipher this not necessary.)
There are at least two problems with Caesar's cipher. As soon as the algorithm is known (Cicero goes from Caesar's friend to his to enemy), the only security left in the system is the secrecy of the key. Because Caesar's cipher has only 25 different keys, to read ESP OTP TD NLDE without the key, that is, to decrypt the ciphertext, takes the enemy at most 25 attempts. This method of decryption is called key exhaustion and constitutes a method for breaking Caesar's cipher system.
The second problem with Caesar's cipher is that enciphering does not rearrange the letters, it only mixes them. If one guesses that P is e (as e is the most common English letter), then O must represent d etc. Hence, via frequency analysis the message is immediately decrypted.
II. Decimation Ciphers and Public Keys
So "adding three" doesn't provide much security. What about "multiplying by three"? Now we must be clear about the conversions from plaintext to plain numbers to ciphernumbers to ciphertext:
| plaintext | I | c | a | m | e | I | S | a | w | I | c | o | n | q | u | e | r | e | d |
| plainnumbers | 9 | 3 | 1 | 13 | 5 | 9 | 19 | 1 | 23 | 9 | 3 | 15 | 14 | 17 | 21 | 5 | 18 | 5 | 4 |
| ciphernumbers | 27 | 9 | 3 | 39 | 15 | 27 | 57 | 3 | 69 | 27 | 9 | 45 | 42 | 51 | 63 | 15 | 54 | 15 | 12 |
| reduced ciphertnumbers | 1 | 9 | 3 | 13 | 15 | 1 | 5 | 3 | 17 | 1 | 9 | 19 | 16 | 25 | 11 | 15 | 2 | 15 | 12 |
| ciphertext | A | I | C | M | O | A | E | C | Q | A | I | S | P | Y | K | O | B | O | L |
This decimation cipher does disorder the plaintext: knowing cipher A = plain I doesn't imply anything about the plain equivalent of cipher I, and in this way decimation ciphers seem an improvement on Caesar's cipher.
To decipher, multiply by the multiplicative inverse of 3 modulo 26, which is 9. (The values e = 3, d = 9 and n = 26 are the parameters of the cipher.) Unfortunately, there are only 12 possible enciphering-deciphering key pairs (as the enciphering key must be relatively prime to the modulus) leaving the cipher open to a key exhaustion attack. What can provide a decimation cipher with more keys? A larger modulus n. For example, if we use the 128 characters of the ASCII character to translate between letters and numbers, we could work modulo 128, giving us Φ(128) = 64 key pairs (here Φ is Euler's totient function). Better, we could turn this into a block cipher by separating the message into five letter blocks : Icame IsawI conqu ered, so Icame = 0903011305 and we'd encipher each block modulo 2626262626. This would give Φ(2626262626) = 1,178,064,000 key pairs, providing some security against key exhaustion.
Decimation ciphers also give us an excuse to discuss Neal Koblitz's toy system, the "Kid-RSA", or KRSA. As set-up, the user first chooses four integers, say a, b, A and B and then computes the four integers M = AB-1, e = aM+A, d = bM+B and n = (ed-1)/M. Then e and d will serve as the enciphering and deciphering keys in a decimation cipher modulo n. (Because we are working modulo n, and n≠ 26, we cannot translate the final ciphernumbers back into letters, so we use the reduced ciphernumbers as the ciphertext.)
We illustrate the payoff for the bit of work involved in the set-up with names. Suppose Alice wishes others to be able to send her private messages. She (secretly) chooses values for a, b, A and B, and then computes M, e, d and n. She makes e and n public, that is, she adds them to her business cards
| Alice Anderson
Phone: 1-800-Call-Alc Email: alice@mymail.com I use Koblitz's KRSA. My public keys are e = 2132843359639, n = 170226494691480298 |
and web page and her company's contact information sheet.
How does this differ from our earlier decimation ciphers? Before Alice and Bob, say, may use a standard decimation cipher they must agree upon e, d and n. And they must keep these values private, for anyone who knows these numbers can read the ciphertext messages. Hence, a decimation cipher is a private key cipher. In particular, Alice and Bob cannot simply send these parameters to one another for fear that someone will eavesdrop on that transmission. This seems to imply that for Alice and Bob to set up a method for exchanging secret messages, they must already be able to secretly exchange messages! A public key cipher avoids this difficulty by cleverly entangling the keys so that the enciphering key(s) may be made public and only the deciphering key(s) need be kept private. So, since Alice uses KRSA, when Bob wants to send her a secret message, he simply uses her public enciphering key to encrypt his message. Since Alice has previously computed the deciphering key, she can quickly decipher the message. Hence KRSA is a public key cryptosystem.
In order for a public key system to be secure it must be computationally infeasible for someone to use the public information to determine the private information. In the case of the KRSA, this is not the case. If Ed, Alice's enemy, has captured a message apparently from Bob, he simply uses Euclid's Extended Algorithm to solve 1 = ex+ny for x = d and deciphers the message.
III. RSA and Modern Public Key Ciphers
After trying "add three" and "multiply by three", the next logical step is "raise to the third power." Unfortunately, if we try this modulo 26 on I came I saw I conquered we get A AAMU A UAY A AUNYEUHUL, a message that obviously cannot be deciphered. So even before we can get to "How to decipher?" and "How secure is it?", we must first address the obvious "How can we make it work?"
The trouble is that e = 3 is not invertible modulo Φ(26). Just as we need gcd(e, n) = 1 for decimation ciphers, for exponentation ciphers (by Euler's theorem) we need gcd(e, Φ(n)) = 1 to guarantee a deciphering exponent d. But remember that we must have a very large number of keys, to guard against key exhaustion, so we must take a very large n. Unfortunately, computing Φ(n) means factoring n, a suprisingly difficult problem. So instead let's take n = p prime, for there are methods for quickly locating immensely large primes and Φ(p) is simply p-1. Choosing e and d so that Φ(n) divides ed-1 then gives use our enciphering and deciphering exponents. This produces a private key block cipher.
A clever tweak then produces the RSA cryptosystem, invented by Ronald L. Rivest, Adi Shamir and Leonard Adelman. As setup, a user picks two prime numbers p and q, and computes n = pq. Then Φ(n) = (p-1)(q-1), so the user may choose an e with gcd(e, Φ(n)) = 1 and then compute d so that ed%Φ(n) = 1. (We use % to denote modular reduction.) To encipher one splits the message into segments M each of which is smaller than n, then computes and sends the numbers Me%n. Deciphering a block E is similar - just compute Ed%n.
Thus RSA is an asymmetrical cryptosystem: the information needed to encipher (e and n) is less than that needed to decipher (d and n.) So Alice may make her e and n public to allow strangers to send her messages. Conversely, Alice keeps p, q, Φ(n) and d all secret. (In fact, she keeps only d and destroys all evidence of p, q and Φ(n).)
To prevent key exhaustion-like attacks, it is recommended that p and q be large primes, about 300 digits each, so n = pq is about 600 digits long. (p and q should satisfy other, simple criteria.) Conversely, it is not uncommon to choose p and q so that 3 does not divide (p-1)(q-1), and then simply use e = 3 for enciphering. (e = 216+1 is another popular choice, due to its simple binary expansion.)
How does one attempt to break RSA? Frequency analysis won't work: for an n of 600 digits there will be 10600 possible ciphertext segments, far too many to keep track of. So instead we look at the specifics of the system itself. The usual argument as to the security of RSA goes something like this. Since n is public the decryptor only needs d. Since e and d are chosen so that ed%Φ(n) = 1, and e is public, the decryptor only needs to discover Φ(n) = (p-1)(q-1). Since (p-1)(q-1) = n-p-q+1 he/she only needs p and q. Since n = pq, the decryptor only needs to factor n. Thus the entire security of the RSA system apparently comes down to factoring n - if we can factor n we can easily decrypt any message enciphered modulo n. Surprisingly, amazingly there is no known method that will factor a carefully chosen n in any reasonable amount of time. For the time being, RSA with well-chosen parameters appears to be quite secure.
RSA has one additional advantage we'll quickly mention. Not only can Bob send Alice a message, he can convince Alice that it was he who sent it via a digital signature. Using a subscript A to denote "Alice's" and B for "Bob's", Bob sends E = (MdB%nB)eA%nA to Alice. (This assumes nB<nA.) She deciphers the message via (EdA%nA)eB%nB. It is clear that Alice is the only one who can read this message (as only she knows dA) and that Bob is the only one who can have sent it (as only he knows dB). Further, Ed the Adversary, even though he knows all of Alice and Bob's public information, cannot read the message; in fact, he cannot even determine if it is actually from Bob! (In real life this process is a bit more complicated.)
In practice, RSA is much slower than private key systems of similar security. So if one was sending a substantial message to a stranger, one would send two parts. In the first, RSA enciphers who you are and what private key method and what key you will use in part two, and the second contains the true message and is enciphered using the method and key you just indicated.
There are now a variety of public key cryptosystems: Diffie-Hellman, the Digital Signature Standard, the knapsack algrorithms, NTRU, as well as elliptic curve-based systems. These systems tend to have a public encryption key and a private decryption key and often rely for their security on some "difficult" problem.
References
There is a great wealth of introductory cryptography online. A person new to the subject could do worse than to begin at Wikipedia
Items directly related to this article.
- Neal Koblitz's article Cryptography as a Teaching Tool.
- The RSA web site.
- Dan Boneh's article, Twenty
Years of Attacks on the RSA Cryptosystem,
Notices
of the AMS, Vol. 46, No. 2, pp. 203--213, 1999.
ABOUT THE AUTHOR: Jim Sauerberg is Professor and Chair of the Department of Mathematics and Computer Science at Saint Mary's College of California He obtained his Ph.D. at Brown University in 1993 with Michael Rosen. His research interests include Algebraic Number Theory, Formal Groups, Cryptography, Reciprocity Laws, Elementary Number Theory, and Function Fields. He has just completed a textbook for use in liberal arts mathematics courses, titled Cryptography: A Historical Approach.