The RSA method is based on mathematics (number theory) and is elegantly simple. The method employs related public and private keys. The public keys, as well as the encryption/decryption methods, are made known to everyone. The private key is always in the possession of the receiver and never has to be transmitted to anyone else.
The public key consists of a pair of integers. The private key is yet another integer. One of the public keys is a very large number which is the product of two large prime numbers. Discovering, or breaking, the private key requires that this large public key be factored into its two prime factors. While this is a simple process theoretically, if the numbers chosen are large enough, it is virtually impossible from a practical perspective. And therein lies the strength and simplicity of the RSA public key method. Only one thing (the private key -- an integer) need be kept secret and it is never necessary to transmit it anywhere. There is no opportunity for the codebreaker to "discover" anything that will aid his or her codebreaking. The codebreaker knows exactly what must be done -- find the prime factors of the public key -- but this is impossible practically speaking.
Below is an example of how to use RSA encryption. Of course, we'll use very small numbers to illustrate.
Step 1: Choose 2 prime numbers P and Q at random.
As an example, suppose we choose:
P = 11
Q = 3
Step 2: Compute the value of Z (one of the
public keys) using the formula Z = P * Q
For our example:
Z = 11 * 3
Z = 33
Step 3: Now we must find a value for the other public key, N. The number N is chosen so that N < Z-1 and has no common factors with the product (P-1) * (Q-1). There will typically be more than one possible value for N, although we only need one. Here's one easy way to find a value for N:
Compute M = (P-1) * (Q-1)
In our example:
M = (11-1) * (3-1) = 10 * 2
M = 20
Now, start dividing M by the primes: first 2, then 3, then 5 etc. until you get a nonzero remainder (that is until you get a decimal value).
20 / 2 = 10
20 / 3 = 6.67
6.67 is our 1st decimal value and the divisor that produced this result (3 in this case) is our value for N. So we choose N = 3. [Note that 7, 11, 13, and several other numbers less than 32 (= Z - 1) would have worked just as well for N in this case.].
We have just generated our public key (the pair of numbers Z = 33 and N = 3).
Step 4: Now we must compute S, the private key. A theorem from elementary number theory tells us that there is a unique number S such that when the product N * S is divided by M = (P-1) * (Q - 1), the remainder will be 1.
Here's how we can go about finding this unique value S. Use the formula ((Y *
M) + 1) / N to compute successive values for Y = 1, 2, 3, etc. When you get a
whole number for a result, that whole number will be S.
In our example, M = 20 and N = 3. We don't have to have to make many calculations to find S. In fact, when Y = 1, we get a whole number as the result of our calculation:
(Y * 20 + 1) / 3 = 21 / 3 = 7
So we have found S = 7 which is our private key.
Here's how we use these keys to encrypt and decrypt messages. First we convert the block of plaintext to be transmitted into an integer. The method for doing this doesn't matter as long as it is known to the receiver and can be relatively easily reversed to get back the original text. For example, we might transmit each byte as its ASCII code value. In practice we usually transmit longer blocks of text than one byte at one time, but the idea is the same.
Before looking at the encryption and decryption formulas, we need to
understand how modular arithmetic works. The value X MOD Y is the remainder left
after we divide X by Y. For example, 10 MOD 4 would be 2, 14 MOD 7 would be 0,
12 MOD 20 would be 12 (when we divide 12 by 20, we get 0 with 12 left over), and
so on.
Now, to encrypt, we use the formula:
C = A N MOD Z
Where A = the numerical value of the plaintext and C = the encrypted numerical value.
For example, suppose we wish to encrypt the value A = 2.
C = 2 N MOD Z
C = 2 3 MOD 33
C = 8 MOD 33
C = 8
So we would transmit the value C = 8.
To decrypt on the receiver's end, we use the formula:
A = C S MOD Z
We just computed C to be 8 (the encrpyted text) and we'll know that S = 7, assuming we're the receiver of the message.
So A = C S MOD Z becomes...
A = 87 MOD 33
A = 2,097,152 MOD 33
A = 2 or the numerical value of the original message, which the receiver can then translate back to the plaintext.
What is required to break a public key cipher? Consider what a would-be codebreaker already knows. The public key is, of course, public, so the coderbreaker would know both Z and N. He or she would also know the formulas to be used in the encryption and decryption. All is left is to break the code is the value of S. And S can be computed (as above) if you know the two prime numbers P and Q. So the bottom line is that you can break the code if you can factor the value Z into its two prime factors P and Q.
This is easy enough to do theoretically. You just start dividing Z by prime numbers until you find one that divides into Z evenly. That value will be the smaller of P and Q and the other factor will be the number of times the first one divides into Z. So, theoretically, the problem is easy. However, if P and Q are chosen to be very large primes, factoring their product Z becomes a very time-consuming task. The brute force method just described is close to the best method known for doing this. Even the fastest computers imaginable will take eons of time to complete this task if the numbers are chosen to be large enough (hundreds of digits each). So the code is essentially unbreakable except by blind luck (which is unlikely enough to be totally ignored in this case).