Encryption Project

ICMS

Page:

RSA PUBLIC KEY CRYPTOSYSTEM

An overview of the RSA cryptosystem

In 1977, R. Rivest, A. Shamir and L. Adleman designed a public key system called the RSA cryptosystem, which has proven to be virtually unbreakable. This method is based on the fact that factoring large numbers is very difficult.

Let's say Bombaywallah wants to use the RSA cryptosystem for secure communication with his clients. Against his name on a public bulletin board, are displayed two numbers n and e. There is also a secret number d which only Bombaywallah knows.

Arindam wants to send Bombaywallah a message.

He converts the message into a number, and breaks this number into blocks such that each block is a number less than n.
Suppose a particular block is m.
Arindam computes m^e and finds the remainder N when this is divided by n.
This is done for all the blocks and the sequence of block remainders is transmitted to Bombaywallah.

Bombaywallah then computes N^d and finds the remainder when this is divided by n. The choice of n, d and e is such that when Bombaywallah finishes his arithmetic, he recovers the original number m. This m, in turn, gives him one part of the message. This is done for all the blocks and thus the entire message is recovered.

The mathematics of RSA

We now explain how and why the RSA system works.

Choose two large distinct prime numbers p and q.
The number n is the product of p and q.
Choose your decoding key d so that it is coprime to f (n)
(the number of integers less than n and coprime to n).
Calculate the encoding key e to be the (unique) number less than f (n) such that (ed - 1) is a multiple of f (n).

We say that a is congruent to b modulo n if they leave the same remainder on division by n, and write a º b (mod n).

Eulers Theorem states that af ⁽ⁿ⁾ º 1 (mod n) if a and n are coprime. Thus a^{kf (n)+1} º a ´ (a ^{f (n)})^k º a ´1^k º a (mod n). When n is a product of distinct primes, this is true for any a.

Now for a block m, m^e º N(mod n). Also ed=kf (n)+1 for some integer k. Thus

N^d º m^ed º m^{k f (n)+1} º m (mod n).

As m < n, The remainder of N^d is m and hence we have got back our original integer value m.

To find d we need to know f (n). All the known formulae for f (n) use the factorization of n. Thus if p and q are very large, it is impossible to find f (n) (and hence d) in reasonable time. Today, the level of security obtained if p and q have about 300 digits is considered sufficient for all applications.

Send secret messages on our computer display!!