RSA Encryption

[attachment=17906]

Public Key Cryptography
One of the biggest problems in cryptography is the distribution of keys. Suppose you
live in the United States and want to pass information secretly to your friend in Europe.
If you truly want to keep the information secret, you need to agree on some sort of key
that you and he can use to encode/decode messages. But you don’t want to keep using
the same key, or you will make it easier and easier for others to crack your cipher.
But it’s also a pain to get keys to your friend. If you mail them, they might be stolen. If
you send them cryptographically, and someone has broken your code, that person will
also have the next key. If you have to go to Europe regularly to hand-deliver the next
key, that is also expensive. If you hire some courier to deliver the new key, you have to
trust the courier, et cetera.

1.1 Trap-Door Ciphers
But imagine the following situation. Suppose you have a special method of encoding
and decoding that is “one way” in a sense. Imagine that the encoding is easy to do, but
decoding is very difficult. Then anyone in the world can encode a message, but only
one person can decode it. Such methods exist, and they are called “one way ciphers”
or “trap door ciphers”.
Here’s how they work. For each cipher, there is a key for encoding and a different key
for decoding. If you know the key for decoding, it is very easy to make the key for
encoding, but it is almost impossible to do the opposite—to start with the encoding key
and work out the decoding key.



1.2 Certification
There is, of couse, a problem with the scheme above. Since the public keys are really
public, anyone can “forge” a message to you. So your enemy can pretend to be your
friend and send you a message just like your friend can—they both have access to the
public key. Your enemy’s information can completely mislead you. So how can you be
certain that a message that says it is from your friend is really from your friend?
Here is one way to do it, assuming that you both have the public and private keys Ea,
Eb, Da, and Db as discussed in the previous section. Suppose I wish to send my friend
a message that only he can read, but in such a way that he is certain that the message is
from me. Here’s how to do it.



2 RSA Encryption
OK, in the previous section we described what is meant by a trap-door cipher, but how
do youmake one? One commonly used cipher of this formis called “RSA Encryption”,
where “RSA” are the initials of the three creators: “Rivest, Shamir, and Adleman”. It
is based on the following idea:
It is very simply to multiply numbers together, especially with computers. But it can
be very difficult to factor numbers. For example, if I ask you to multiply together
34537 and 99991, it is a simple matter to punch those numbers into a calculator and
3453389167. But the reverse problem is much harder.