November 2015

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.

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)

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

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)

For unlimited offline reading, you can download this article for free in PDF format:

Encryption-with-rsa .pdf

Cifrado por medio de RSA

Verschlüsselung durch RSA

Algorithme de chiffrement RSA

La codificazione con RSA

A codificação com RSA