RSA Tutorial

What is RSA?

RSA is a type of Public Key Infrastructure (PKI) Encryption. Also known as assymetric encryption, PKI uses one key (a fancy word for a number used to encrypt or decrypt) to encrypt a message, and a separate, secret key to decrypt it. Thus, anyone can encrypt a certain message, but only the holder of the private key can decrypt it. RSA was developed in 1978 Ron Rivest, Adi Shamir, and Leonard Adleman, hence the name RSA. Currently, it is one of the best, if not the best encryption algorithm in use. The next sections will explain why RSA is such a good algorithm.

How Does RSA Work?

When RSA was first explained to me, it was described as an algorithm that could be explained in front of an "enemy" and still not be cracked. And indeed, this is true. RSA does not take the direct path of representing certain characters with other characters, like the cryptographs one finds in the newspaper. RSA is a math based algorithm. It is based on the assumption that there is no easy way to factor really big numbers (300+ digits). As of yet, this assumption is "true" in the sense that no one has found an easy way.

In order to implement RSA, several numbers are needed. Here is a list of variables that will be used.

1: P and Q, 2 really big (300+ digit) prime numbers.
2: E, a number less than PQ and which has no common prime factors with (P-1)(Q-1).
3: D, such that (DE-1) % [(P-1)(Q-1)] = 0.

One more important note: Because this is Public Key Infrastructure Encryption (= asymmetric), one or more of the numbers above is kept secret. They are known ONLY to the person decoding the message. Those numbers are D, P, and Q. You will see why further down the page. The pair (PQ, E) is the public key. It doesn't matter who sees these numbers.

At first glance, it seems that these numbers may be very hard to come up with - the algorithms to find them look very computationally expensive to say the least. However, the toughest part is probably coming up with huge prime numbers. Fortunately, there are several algorithms that can be used to find those numbers. Click on this link for a site that explains how to find prime numbers and how to test whether a number is prime or not. Once the primes are out of the way, the other two numbers simply require an algorithm that will eventually come up with them. The only problem is that it may take a while to run.

So far, all you know are the variables needed to implement RSA. And boy, are those helpful! Right. Anyway, next is an explanation of how each variable is used in RSA. The implementation is surprisingly simple and yet at the same time rather complex as well. Here goes:

C = the encoded value
T = the original value (% = modulus, the remainder after division)

Encryption Decryption
C = T^E % PQ T = C^D % PQ

These formulas are based on Fermat's Little Theorem.

OK, so that's the basics, but why oh why must D, P, and Q be kept secret? Do you really want to know? Really? Really really? OK.

Obviously, D has to be secret because it is the one number needed to decode RSA. P and Q must be kept secret, though, because the smaller they are, the easier it is to factor PQ. And because PQ is "almost prime" (it is the product of 2 prime numbers and thus has 4 factors - 1, itself, P, and Q), if it is factored, the code cracker has found P and Q. If P and Q are known, D can be found using the formula given above. That doesn't bode well for an important secret message, especially because ANY D can be used to decode RSA. Any value for D that fits the above formula can be used. As a last note on factoring, if P and Q are both 300+ digits long, the sun will burn out before today's fastest computers can factor PQ. Makes you feel quite safe using this algorithm, doesn't it?

Finally...

There is one more thing to mention before this little tutorial wraps up. How does RSA work when put into practice? It's actually relatively simple. I, as a person who needs to be sent secret information, come up with P and Q. From those two numbers, I determine PQ, D, and E. Then I destroy P and Q, and give to others (those who want to send me encrypted data) the pair (PQ, E). I keep D secret and use it to decrypt any incoming messages.

If you want to know how I am coding RSA, see my Project Development page.

One more linkL: Proving Primes

TECHLAB HOME | HOME | SUPERCOMP PAGE