Encryption with RSA

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)
Ask a question
CCM is a leading international tech website. Our content is written in collaboration with IT experts, under the direction of Jean-François Pillou, founder of CCM.net. CCM reaches more than 50 million unique visitors per month and is available in 11 languages.

Related

This document, titled « Encryption with RSA », is available under the Creative Commons license. Any copy, reuse, or modification of the content should be sufficiently credited to CCM (ccm.net).