Suppose I have the same RSA encryption system developed in the last handout, with f(x) = x7 (mod 247) the public key and f-1(x) = x31 (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.
We have gone over RSA public key encryption. This is the basis for the Secure Socket Layer, but there are some implementation issues, especially concerning efficiency, that we haven’t covered yet. Those will be the topic of the next lecture.