What is RSA in Cryptography?

In this tutorial, we are going to see What is RSA in Cryptography?

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

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

 

How RSA works

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

Suppose two prime numbers p and q, and d an integer such as d is prime with (p-1)*(q-1)). The triplet (p,q,d) constitutes the private key.

The public key is then the pair (n,e) created with the private key by the following mathematical operations:

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

Consider M, the message to be sent. The message M must be prime with the key n. Indeed, the decryption is based on Euler’s theorem stating that if M and n are prime, then :

Mphi(n) = 1 mod(n)

Phi(n) is the Euler index, and in this case, is (p-1)*(q-1).

It is thus necessary that M is not a multiple of p, of q, or of n. A solution consists in splitting the message M in chunks Mi such that the number of digits of each Mi is strictly lower than p and q. This assumes that p and q are large, which is the case in practice since the whole principle of RSA lies in the difficulty of finding in a reasonable time p and q knowing n, which assumes p and q to be large.
 

 

Example of RSA:

Suppose a user (called Alice) wants to send a message M to a person (called Bob), he simply needs to get the public key (n,e) of the user 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 using her private key (p,q,d):

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

 
^{Image source: https://it.wikipedia.org/wiki/File:Blindsign-RSA.jpg}
 
Computer Security MCQs – Multiple Choice Questions and Answers – Part 1Multiple choice questions and answers (MCQs) on Computer Security to prepare for exams, tests, and certifications. These questions are taken from a real written exam…Read More