Math 511, Public Key Encryption

Public Key Encryption

Trying to sell things on the World Wide Web has some interesting problems. You want people to be able to click and buy things. This means you need to have their credit card number. How can you make it safe for people to send you their credit card number over the web? Any information sent over the Internet passes through a variety of computers that neither you nor your customers have any control over. Any privileged user of one of those intermediate computers could read the message your customer sends. If you want to provide a secure method of sending information, you will need to provide some method of encrypting the data.

How can you set up a secure encryption system for your customers? If you make them call for instructions, they are likely to just click on to the next site. But any message you send them over the Internet is no safer than the messages they send you. We need a way to tell them how to encrypt a message so the message is safe even from someone who overhears the encryption instructions. This is the miracle of public key encryption.

For most (if not all) public key encryption systems, the key is to carry out computations in some carefully chosen algebraic structure. If you have a structure in which everyone can carry out arithmetic computations, but only you know how to do algebra, then it is easy to design a public key encryption system. Suppose your friend is thinking of a number and wants to tell you the number secretly, but can't talk to you without anyone listening in. You just tell your friend to multiply the number they are thinking of by 3, add 7, and tell you the result. your friend can do this since everyone knows how to do arithmetic. Once you get the result, r, you solve the algebra problem 3x+7 = r to find the original number x. If you are the only one who knows how to do algebra, you are the only one who can figure out the original number, so the number has been passed secretly, even though other people may have heard all of your conversation.

The first practical public key encryption system was developed in the 70s by Rivest, Shamir, and Adleman. It is called RSA public key encryption and is patented and marketed by RSA Date Security Incorporated. If you click on the Help-About menu in Netscape Navigator, you will find a reference to RSA Data Security, as RSA public key encryption is part of the secure socket layer that is used transmit information securely over the World Wide Web. We will talk more about the details of the secure socket layer next week. For today, we will just go over the basics of how RSA public key encryption works. We will want to define two functions, an encryption function f(x) which takes a plaintext message x and converts it to a coded ciphertext r and a decryption function f ^-1(r) which recovers the plaintext message from the ciphertext.

To set up the encryption system:

Pick two large primes p and q (we will discuss how large is "large" later).
Example: Let p = 13 and q = 19.
Let n = p ´ q.
Example: n = 247.
Compute j(n) = (p – 1) ´ (q – 1).
Example: j(247) = 216.
Pick an encryption key e such that gcd(e,j(n)) = 1.
Example: Pick e = 7 (a small prime is usually easiest to work with when you are setting things up by hand).
Compute d = e^-1 (mod j(n)).
Example: We have done this sort of problem before. The inverse of 7 (mod 216) is 31. So we take d = 31.
The encryption function is f(x) = x^e (mod n). This is public information (tell everyone this). The decryption function is f^-1(x) = x^d (mod n). This is private information (keep this secret).
Example: The encryption function is f(x) = x⁷ (mod 247). This is public. The decryption function is f^-1(x) = x³¹ (mod 247). This is private. To send the message x = 21, I compute f(21) = 21⁷ º 109 (mod 247). I then send the encrypted message 109. When you receive my encrypted message 109, you compute f^-1(109) = 109³¹ º 21 (mod 247), and so you recover my original message.

Why this works:

The key to RSA public key encryption is Euler’s theorem, that a^j(n) º 1 (mod n) if gcd(a,n) = 1. When we say e and d are inverses (mod j(n)), we are saying that e ´ d = 1 + j(n)´y for some y. Then using the rules of exponents we get f^-1(f(x)) = (x^e)^d = x^e´d = x^1+j(n)´y = x ´ (x^{j
(n)})^y º x ´ 1^y = x. Of course, you should be a little worried about the requirement in Euler’s theorem that gcd(a,n) = 1. This turns out not to cause any problems, because you can prove that while the relation in Euler’s theorem won’t hold, the functions are still inverses even if gcd(x,n) ¹ 1, The proof for this more general case is rather complicated so we won’t worry about that for now. For the homework, set up your own RSA public key encryption system. Pick your own p and q (of two or three digits) and work out the n, e, and d. You should turn in both the public function f(x) = x^e (mod n) and the private function f^-1(x) = x^d (mod n) and you should note which is which.

Digital signatures and other applications

Encryption schemes can be useful for applications other than sending secret messages. One common problem with email and other forms of digital communication is verifying exactly who sent the message. Forging a signature is at least a little challenging (though I don't know a secretary who can't forge the boss's signature), but typing someone else's name is a piece of cake. Spoofing address headers in an email message isn't much more difficult. Public key encryption can be reversed in order to provide digital signatures. Instead of messages that only one person can read, you get messages that only one person could have written.

Suppose I have the same RSA encryption system developed above, with f(x) = x⁷ (mod 247) the public key and f^-1(x) = x³¹ (mod 247). (Note: due to a typographical error, I wrote 347 instead of 247 in the last handout). I want to send the message "Hi" in such a way that you can verify the message came from me. A capital "H" is code 72 and a lowercase "i" is code 105 in ASCII, the American Standard Code for Information Interchange. So I want to send the two numbers 72 and 105. I use my private key to compute f^-1(72) = 162 (mod 247), and f^-1(105) = 222 (mod 247). Then I send the message 162, 222. Anyone who receives the message can decode the message using the public key (which everyone knows), f(162) = 72 (mod 247) and f(222) = 105 (mod 247), which any ASCII based computer will recognize as "Hi." This message must have been written by me, because only someone who knows f^-1(x) can find the values 162 and 222 which solve f(x) = 72 (mod 247) and f(x) = 105 (mod 247) respectively, and I’m the only one who knows f^-1(x), my private key.

Digital signatures can be used along with regular public key encryption to produce messages that only one person can write and only one person can read. If I want to send you a secure and private message, I first use my public key and then your private key to encrypt the message. When you receive the message, you then decrypt it with your private key and my public key. Only I can send the message, because only I know my private key. Only you can read the message, because only you know your private key. So I know that no one else can listen in on my message and you can be sure the message comes from me and not some imposter.

Of course, email also travels over a computer network where hackers can intercept messages and encryption systems can be useful here as well. Indeed, some authorities worry it could be too useful, enabling terrorists and other criminals to outwit electronic surveillance. Because of "national security" concerns, the National Security Agency tried to classify the RSA scheme. When that failed, encryption schemese were declared "munitions" and subject to export control like any other weapon. The main effect of this was to prevent U.S. companies from competing with foreign companies ihn offering effective encryption systems. Over the last few years, the government has been slowly liberalizing export controls in response to business pressure. This summer, for example, export controls on encryption were lifted for exports to European allies (along with Japan and New Zealand).

Note that while RSA public key encryption is the basis for the Secure Socket Layer on the Internet, there are some implementation issues, especially concerning efficiency, that we haven't covered yet. Those will be the topic of the next lecture.