RSA ALGORITHM

The RSA algorithm, named for its creators Ron Rivest, Adi Shamir, and Leonard Adleman, is currently one of the favorite public key encryption methods. Here is the algorithm:

1. Choose two (in practice, large 100 digit) prime numbers p and q and let n = pq.

2. Let Pi be the block of (plain) text to be encrypted. Actually Pi is the numerical equivalent of the text which may either be single letters or blocks of letters, just as long as .

p(i)<(p-1)(q-1)= O(n)

3. Choose a random value E (usually small) such that E is relatively prime to f(n). Then the encrypted text is calculated from.

C(i)~=p(i) mod n

The pair of values (n,E) act as the public key.

4. To decode the ciphertext, we need to find an exponent D, which is known only to the person decoding the message, such that

DE ~= 1 mod((p-1)(q-1))

Note that .

f(n)=f(pq)=(p-1)(q-1)

Then we may calculate