Kioskea
Recherche

Encryption with RSA

February 2015

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)
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 Mi such that the amount of numbers in each Mi 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)
For unlimited offline reading, you can download this article for free in PDF format:
Encryption-with-rsa.pdf

See also


Cifrado por medio de RSA
Cifrado por medio de RSA
Verschlüsselung durch RSA
Verschlüsselung durch RSA
Algorithme de chiffrement RSA
Algorithme de chiffrement RSA
La codificazione con RSA
La codificazione con RSA
A codificação com RSA
A codificação com RSA
This document entitled « Encryption with RSA » from Kioskea (en.kioskea.net) is made available under the Creative Commons license. You can copy, modify copies of this page, under the conditions stipulated by the license, as this note appears clearly.