RSA is the main cryptographic algorithm on which asymmetric cryptography and most modern applications, including computer security, are based, especially web applications and, more generally, network applications.

Basic Principles

The RSA algorithm was invented in 1977 by three MIT engineers, Ronald Rivest, Adi Shamir, and Leonard Adleman – the acronym RSA comes from the authors' initials. Asymmetric cryptography, or public-key cryptography, is based on RSA, which we introduced in this post.

Explaining how the algorithm works in a simple way is not easy. by no means trivial, as it is based on quite complex mathematical principles. If we wanted to summarize the basic mathematics, we could start from the following principle: given a number n, it is very difficult to find the two prime numbers p and q that are factors of n. Based on this principle, the number n can be made public without fear that, starting from n, it will be possible to factor p and q, on which the private key depends. In asymmetric cryptography, in fact, there is a public key and a private key, which must be used together to encrypt and decrypt the secret message.

RSA Algorithm

The steps of the RSA cryptographic algorithm can be summarized as follows:

1. Choose p and q as many large prime numbers as you like.

2. Calculate n=pq and z=(p−1)(q−1)

3. You choose e<n|MCD(e,z)=1

4. We find d such that edmodz=1 from which it follows that d=(km+1)/e

5. You will find the public key K⁺ and the key private K⁻:
   K⁺:pair (e,n)
   
   K⁻:pair (d,n)

6. The message is encrypted by obtaining the encrypted message c (encryption operation) with c=m^emodn

7. You decrypt the message by obtaining the message original m (decryption operation) with m=c^dmodn.

For example, try this exercise. Given p=7, q=13 and e=11, choosing a k=9, which will be d? You will have which d=59. In this way we have calculated the public and private key pair.