[Next] [Up] [Previous] [Index]

Rivest-Shamir-Adleman

The RSA method, ever since the knapsack method was shown to be insecure, along with some variants of it, is almost the only "true" public-key method, in that it directly encrypts messages with the public key.

It was described to the public in August 1977, and was the invention of Ronald Rivest, Adi Shamir, and Leonard Adleman. However, it was recently revealed that this method was originally invented in 1973 within GCHQ by Clifford Cocks.

The RSA method is based on the following mathematical facts:

If you raise a number to a power (d), modulo a prime, you can get the original number by raising the result to another power (e). And it can be easily determined, knowing the prime modulus, and the one power, what the other power is.

If the modulus (M) is not a prime, there is still another power which reverses exponentiation by any power. But finding it depends on knowing the factorization of the modulus, or, which is equivalent, knowing something called the "Euler Totient Function" of the modulus.

(Actually, although the name "Euler Totient Function" sounds pretty forbidding, it isn't that bad. For a prime number p, the ETF of it is p-1. For the product of two prime numbers, p and q, which is the sort of number used as a modulus in RSA, the ETF is p-1 times q-1.)

Choose for e a number that is relatively prime to (p-1) and (q-1). Then, d is the reciprocal of e modulo (p-1)(q-1). As long as neither p nor q is 2, (p-1)(q-1)/2 will also work just as well, and if (p-1) and (q-1) have any other common factors, they too can be divided out so that they will only appear only once. (The resulting number is called the Carmichael function of pq. The book Decrypted Secrets from Springer-Verlag is one of the few references noting this important fact about RSA.)

Actually using RSA, of course, requires more than the brief description of it that we have already seen. Several questions need to be answered.

How do I choose two very large prime numbers?

How do I calculate reciprocals modulo (p-1)(q-1)?

How do I do exponentiation modulo pq?


[Next] [Up] [Previous] [Index]

Next Section
Chapter Start
Table of Contents
Home Page