RSA algorithm is a cryptosystem for public-key encryption that is widely used for securing sensitive data when being sent over an insecure network such as the internet.
The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977.
The basic idea had been discovered in 1973 by Clifford Cocks of CESG, but remained a secret until 1997.
It is asymmetric meaning that it works on two different keys.
Public key and private key.
The public key is given to everyone while the private key is kept private.
In RSA cryptography, both the public and the private keys can encrypt a message, the opposite key from the one used to encrypt a message is used to decrypt it.
- Read: Intro to Cryptography.
This is the reason why RSA is widely used asymmetric algorithm.
It provides means of assuring the confidentiality, integrity, authenticity and non-reputability of electronic communications and data storage.
Another advantage of RSA algorithm is that it can be used to encrypt a message without the need to exchange a secret key separately.
It is used for both public key cryptography and digital signatures.
RSA draws its strength from difficulty of factoring large integers.
The only drawback of RSA is that it’s rather slow so it’s hardly used to encrypt data, it’s often used to encrypt and pass around symmetric keys which can actually deal with encryption at a faster speed.
Here are protocols that rely on RSA for encryption and digital signature functions: SSH, OpenPGP, S/MIME, and SSL/TSL.
In this guide I will be discussing the following:
- How does RSA work.
- RSA algorithm example with solution.
How does RSA work
The public key consists of two numbers where one number is multiplication of two large prime numbers.
Multiplying these two numbers is easy, but determining the original prime numbers from the total (factoring), is considered very difficult due to the time it would take even for most powerful computers today.
Also the private key is derived from the same two prime numbers.
This means that the strength of the encryption depends on the key size. RSA keys are generally 1024 or 2048 bits long.
How to generate an RSA key pair
First step is to generate a Public key.
Here is an example:
Select two prime no's. Suppose P = 53 and Q = 59. Now First part of the Public key : n = P*Q = 3127. You also need a small exponent say e : But e Must be An integer. Not be a factor of n. 1 < e < Φ(n) [Φ(n) is discussed below], Let us now consider it to be equal to 3. Our Public Key is made of n and e
The next step is to generate Private key.
You need to calculate Φ(n) : Such that Φ(n) = (P-1)(Q-1) so, Φ(n) = 3016 Now calculate Private Key, d : d = (k*Φ(n) + 1) / e for some integer k For k = 2, value of d is 2011.
Thus, Public key (n): 3127.
And, Private Key (d): 2011.
RSA algorithm example with solution
How to encrypt using RSA algorithm
First convert letters to numbers : H = 8 and I = 9 Thus Encrypted Data c = 89e mod n. Thus my Encrypted Data comes out to be 1394
How to decrypt RSA algorithm
Now I will decrypt 1394 : Decrypted Data = cd mod n. Thus our Encrypted Data comes out to be 89 8 = H and I = 9 i.e. "HI".
Here is more advanced guide you should take a look at.
Now I want to hear from you.
What do you think of RSA algorithm?
Or maybe I missed an important aspect of this encryption scheme.
Either way, let me know by leaving a comment below.