• Saturday July 4, 2009 - 4:45:58 pm BST
• registered : 1501950
• online : 51233
• questions/day : 4530
• Answer rate : 76%

the RSA system

The first public-key encryption (asymmetric encryption) algorithm was developed by R.Merckle and M.Hellman in 1977. It was quickly made obsolete thanks to the work of Shamir, Zippel and Herlestman, famous cryptanalysts.

In 1978, the public key algorithm by Rivest, Shamir and Adelman (hence its name, RSA) appeared. This algorithm was still used in 2002 to protect the American and Russian armies' nuclear codes.

how RSA works

The functioning of the RSA cryptosystem is based on the difficulty factoring large integers.

Let p and q be two prime numbers, and d an integer such that d is coprime to (p-1)*(q-1)). The triplet (p,q,d) thus represents theprivate key.

The public key is then the doublet (n,e) created with the private key through the following transformations:

n = p * q
e = 1/d mod((p-1)(q-1))

Let M be the message to be sent. The message M needs to be coprime to the key n. Decryption is based on Euler's theorem, which stipulates that if M and n are coprime, then:

Mphi(n) = 1 mod(n)

It is therefore necessary that M not be a multiple of p, q , or n. One solution involves breaking down the message M into bits M_i such that the amount of numbers in each M_i is strictly inferior to that of p and q. This supposes then that p and q are large, which is the case in practice since the principle of RSA lies in the difficulty finding p and q in a reasonable amount of time when n is known, which supposes that p and q are large.

In practice...

Suppose that a user (named Bob) wants to send a message M to a person (let's call her Alice). He simply needs to obtain her public key (n,e) and then calculate the encrypted message c:

c = Me mod(n)

Bob then sends the encrypted message c to Alice, who is able to decrypt it with her private key (p,q,d):

M =  Me*d mod(n) = cd mod(n)