Home » Cryptography

Rivest-Shamir-Adleman (RSA) in Cryptography

Cryptography | Rivest-Shamir-Adleman (RSA): In this tutorial, we will learn about the Rivest-Shamir-Adleman (RSA), the generation of RSA key pair, RSA encryption and decryption, and RSA analysis. By Monika Sharma Last updated : May 25, 2023

Rivest-Shamir-Adleman (RSA)

The RSA algorithm is an asymmetric cryptography algorithm in cryptography. The Asymmetric eventually means that it implements two different keys i.e. Public Key and Private Key in cryptography. As like, the name tells that the Public Key is given to everyone and the Private key is kept private for others.

As such a cryptosystem, the encryption key is public and it is different from the decryption key which is kept secret or as private. Mainly RSA, this is asymmetry is based on the practical high of the factorization of the multiple of two large prime numbers, the "factoring problem" in the cryptography. Then, the RSA is made of the first letters of the surnames of the publisher i.e. "Ron Rivest", "Adi Shamir" and "Leonard Adleman". It is published in 1977.

Example of Asymmetric Cryptography

1. A second party or client sends its public key to the server and requests for some data in cryptography.
2. One more the server encrypts the data using the client's public key and sends the encrypted data to encrypt a key.
3. Second Party or Client receives this data and decrypts it.

Hence, this is an asymmetric nobody else except client or second party can decrypt the data even if a third party has the public key of the client.

Generation of RSA Key Pair

Every person or a party who describes participating in communication using encryption needs to generate a pair of keys called namely public key and private key in the cryptography. The steps are followed in the generation of keys is described as following,

• Find the RSA modulus (n)
  
  • Let two large primes, p and q.
  • Then, Calculate, n=p*q. For high encryption, let (n) be a large number, typically a minimum of 512 bits of the character.
• Now, Find Derived Number (e)
  
  • Let, Number (e) must be between 1 and (p − 1)(q − 1).
  • Here, there will not be common factor for (e) and (p − 1)(q − 1) only 1. In other words two numbers e and (p – 1)(q – 1) are coprime for each other.
• Now, calculate the public key
  
  • The pair of public key numbers (n, e) form the RSA public key and is made public for everyone.
  • Therefore, though n is part of the public key, changes in factorizing a large prime number ensure that higher attackers cannot find in finite time the two primes (p and q) used to obtain n in this. This is the strength of RSA for cryptography.
• Now, generate the private key
  
  • Now, Private Key (d) is calculated from p, q, and e in this. For given n and e, there is unique number d for private or a key use by the author only.
• Here, number (d) is the inverse of e modulo (p - 1)(q – 1). This means that d is the number less than (p - 1)(q - 1) such that when multiplied by e, it is equal to 1 modulo (p - 1)(q - 1) in this cryptography.
• This function is written mathematically as follows as e*d = 1 *mod (p − 1)(q − 1).

Example

Here, an example of generating RSA Key pair in cryptography is given below.

• Let, two primes be p = 6 and q = 13. Then, n = p*q = 7 x 13 = 91.
• Now, select e = 5, which is a valid since there is no number that is common factor of 5 and (p - 1)(q - 1) = 6 x 12 = 72, except for 1.
• Then, the pair of numbers (n, e) = (91, 5) forms the public key and can be made available to anyone which will be able to send us encrypted messages in the cryptography.

Input p = 7, q = 13, and e = 5 and find d=e^(-1)mod(p-1)(q-1)
The output will be d = .29

• Now, check that the d calculated is correct or not:-d*e = 29 x 5 = 145 = 1 mod 72=1.
• Hence, public key is (n,e) i.e (91, 5) and private keys is(n,d) i.e (91, 29).

RSA Encryption and Decryption

Hence, once the key pair of the private and public key has been generated, the process of encryption and decryption are relatively simple and easy to use by the keys.

Therefore, RSA does not directly operate on strings of bits as in case of symmetric key encryption in more opration. It operates on numbers as n. Here, it is necessary to represent the plaintext or original text as a series of numbers less than n in the RSA.

RSA Encryption

• Now, Suppose the sender message to send some text message to someone whose public key is (n, e) in this.
• Then, the sender represents the plaintext as a series of numbers less than n in the process.
• Now, to encrypt the first plaintext P, which is a number modulo of n. The encryption process is simply done by a formula as C = P^e mod n
• In different words, the ciphertext C is equal to the plaintext P product by itself e times and then reduced modulo n in this. This means that C is also a number less than n in RSA.
• Then, returning to our Key Generation example with plaintext as P = 10, we get ciphertext C: C = 10^5 mod 91=82

RSA Decryption

• Here, the decryption process for RSA is also very simple and easy. Suppose that the receiver of public-key pair (n, e) has received a ciphertext C as shown above.
• Now, the receiver does the C to the power of his private key d. The result n will be the plaintext P as Plaintext = C^(d) mod n.
• Now, returning to our example, the ciphertext as C = 82 would get decrypted to number to 10 using the private key as 29: Plaintext = 82^(29) mod 91 = 10

Image source

RSA Analysis

The safety and security of RSA based on the strengths of two separate functions in it. Thus, the RSA cryptosystem is the most popular public-key cryptosystem in the cryptography strength of which is based on the practical high of factoring the very large numbers in this.

• Encryption Function: This is considered as a single way function of transfer plaintext into ciphertext and it can be opposite only with the knowledge of private key d as private.
• Key Generation: Mainly, the difficulty of determining a private key from an RSA public key is equivalent to factoring the n in RSA. A Hacker attacker thus cannot use knowledge of an RSA public key to determine an RSA private key unless he can factor n as n is large then he will not. It is also a single way function, going from p and q values to modulus n is easy but the reverse is not possible by these values only.

If one of these two functions is proved non-single-way, then RSA will be broken and the attacker can attack. Whereas, if a technique for factoring efficiently is developed then RSA will no longer be safe in the algorithm.

The main strength or power of RSA encryption goes down against attacks if the number of p and q are not large primes or chosen public key e is a small number in this algorithm.