October 2016

## 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:

M^{phi(n)} = 1 mod(n)

*Phi(n)* being the totient function and in the present example worth

*(p-1)*(q-1)*.

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 = M^{e} 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 = M^{e*d} mod(n) = c^{d} mod(n)