8.3. Public Key Cryptography

^[2] James Ellis, a cryptographer working for the British government's Communications-Electronics Security Group, said "he showed proof of concept in a January 1970 CESG report titled 'The Possibility of Secure Non-Secret Digital Encryption.'" Two of his colleagues found practical implementations. This work remained classified until 1997 ([244], p. 299).

Because one key is public, and its complementary key must remain secret, a public key cryptosystem must meet the following three conditions.

The RSA cipher provides both secrecy and authentication.

8.3.1. RSA

RSA [756] is an exponentiation cipher. Choose two large prime numbers p and q, and let n = pq. The totient ff(n) of n is the number of numbers less than n with no factors in common with n.^[3]

^[3] Our examples will use small numbers for pedagogical purposes. Actual RSA primes should be at least 512 bits each, giving a modulus of at least 1,024 bits. In practice, RSA is combined with cryptographic hash functions to prevent rearrangement of blocks (see Section 10.1.2).

EXAMPLE: Let n = 10. The numbers that are less than 10 and are relatively prime to (have no factors in common with) n are 1, 3, 7, and 9. Hence, ff(10) = 4. Similarly, if n = 21, the numbers that are relatively prime to n are 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, and 20. So f(21) = 12.

Choose an integer e < n that is relatively prime to ff(n). Find a second integer d such that ed mod ff(n) = 1. The public key is (e, n), and the private key is d.

Let m be a message. Then:

c = m^e mod n

and

m = c^d mod n

EXAMPLE: Let p = 7 and q = 11. Then n = 77 and f(n) = 60. Alice chooses e = 17, so her private key is d = 53. In this cryptosystem, each plaintext character is represented by a number between 00 (A) and 25 (Z); 26 represents a blank. Bob wants to send Alice the message "HELLO WORLD." Using the representation above, the plaintext is 07 04 11 11 14 26 22 14 17 11 03. Using Alice's public key, the ciphertext is 0717 mod 77 = 28 0417 mod 77 = 16 1117 mod 77 = 44 ... 0317 mod 77 = 75 or 28 16 44 44 42 38 22 42 19 44 75.

In addition to confidentiality, RSA can provide data and origin authentication. If Alice enciphers her message using her private key, anyone can read it, but if anyone alters it, the (altered) ciphertext cannot be deciphered correctly.

EXAMPLE: Suppose Alice wishes to send Bob the message "HELLO WORLD" in such a way that Bob will be sure that Alice sent it. She enciphers the message with her private key and sends it to Bob. As indicated above, the plaintext is represented as 07 04 11 11 14 26 22 14 17 11 03. Using Alice's private key, the ciphertext is 0753 mod 77 = 35 0453 mod 77 = 09 1153 mod 77 = 44 ... 0353 mod 77 = 05 or 35 09 44 44 93 12 24 94 04 05. In addition to origin authenticity, Bob can be sure that no letters were altered. Providing both confidentiality and authentication requires enciphering with the sender's private key and the recipient's public key.

EXAMPLE: Suppose Alice wishes to send Bob the message "HELLO WORLD" in confidence and authenticated. Again, assume that Alice's private key is 53. Take Bob's public key to be 37 (making his private key 13). The plaintext is represented as 07 04 11 11 14 26 22 14 17 11 03. The encipherment is (0753 mod 77)37 mod 77 = 07 (0453 mod 77)37 mod 77 = 37 (1153 mod 77)37 mod 77 = 44 ... (0353 mod 77)37 mod 77 = 47 or 07 37 44 44 14 59 22 14 61 44 47. The recipient uses the recipient's private key to decipher the message and the sender's public key to authenticate it.

EXAMPLE: Bob receives the ciphertext above, 07 37 44 44 14 59 22 14 61 44 47. The decipherment is (0713 mod 77)17 mod 77 = 07 (3713 mod 77)17 mod 77 = 04 (4413 mod 77)17 mod 77 = 11 ... (4713 mod 77)17 mod 77 = 03 or 07 04 11 11 14 26 22 14 17 11 03. This corresponds to the message "HELLO WORLD" from the preceding example.

The use of a public key system provides a technical type of nonrepudiation of origin. The message is deciphered using Alice's public key. Because the public key is the inverse of the private key, only the private key could have enciphered the message. Because Alice is the only one who knows this private key, only she could have enciphered the message. The underlying assumption is that Alice's private key has not been compromised, and that the public key bearing her name really does belong to her.

In practice, no one would use blocks of the size presented here. The issue is that, even if n is very large, if one character per block is enciphered, RSA can be broken using the techniques used to break classical substitution ciphers (see Sections 8.2.2 and 10.1.3). Furthermore, although no individual block can be altered without detection (because the attacker presumably does not have access to the private key), an attacker can rearrange blocks and change the meaning of the message.

EXAMPLE: A general sends a message to headquarters asking if the attack is on. Headquarters replies with the message "ON" enciphered using an RSA cipher with a 1,024-bit modulus, but each letter is enciphered separately. An attacker intercepts the message and swaps the order of the blocks. When the general deciphers the message, it will read "NO," the opposite of the original plaintext. Moreover, if the attacker knows that headquarters will send one of two messages (here, "NO" or "ON"), the attacker can use a technique called "forward search" or "precomputation" to break the cipher (see Section 10.1.1). For this reason, plaintext is usually padded with random data to make up a block. This can eliminate the problem of forward searching, because the set of possible plaintexts becomes too large to precompute feasibly. A different general sends the same request as in the example above. Again, headquarters replies with the message "ON" enciphered using an RSA cipher with a 1,024-bit modulus. Each letter is enciphered separately, but the first six bits of each block contain the number of the block, the next eight bits contain the character, and the remaining 1,010 bits contain random data. If the attacker rearranges the blocks, the general will detect that block 2 arrived before block 1 (as a result of the number in the first six bits) and rearrange them. The attacker also cannot precompute the blocks to determine which contains "O," because she would have to compute 21010 blocks, which is computationally infeasible.