Cryptography

Introduction to the Rivest-Shamir-Adleman (RSA) encryption algorithm

February 3, 2021 by Nitesh Malviya

Encryption and Decryption

Encryption is the process of converting plaintext to encrypted text. Since encrypted text cannot be read by anyone, encrypted text hides the original data from unauthorized users. Decryption is the process of converting encrypted data to plaintext. Basically, it is the reverse of encryption. It is used to decrypt the encrypted data so that only an authorized user can access and read the data. The process entailing encryption and decryption together is called cryptography.

Private and Public Keys in Cryptography

A key is a bit valued string which is used to convert the plaintext into cipher text and vice-versa. A key can be a word, number or phrase. Cryptography makes use of public and private keys. A public key is issued publicly by the organization and it is used by the end user to encrypt the data. The encrypted data, once received by the organization, is decrypted by using a private key and the data is converted to plaintext.

Encryption Types

Cryptography uses symmetric and asymmetric encryption for encryption and decryption of data. If the sender and the recipient of the data use the same key to encrypt and decrypt the data, it’s called symmetric encryption and if the keys are different for encryption and decryption then it’s asymmetric encryption. 

Now the basics are clear, let’s focus on the Rivest-Shamir-Adleman (RSA) algorithm in this post.

Rivest-Shamir-Adleman

Rivest-Shamir-Adleman short form as RSA falls under the Asymmetric Encryption category. Thus, in RSA the sender and the recipient of the data use a different key for encryption and decryption. RSA was invented in 1978 and is considered as the most secure way of encrypting the data.

Working

Following steps need to be performed to implement RSA Algorithm

Key Generation

  1. Choose 2 large prime numbers say x & y. These numbers should be large enough.
  2. Calculate their product n as n=x*y
  3. Calculate the totient function as ϕ(n) =  (x−1)*(y−1)

Derived Number

Let e be the derived number. Number e should be less than (p-1) and (q-1) and greater than 1. Also, there shouldn’t be a common factor of (p-1) and (q-1) except 1.

Public Key

Numbers n and e forms the RSA public key pair and it is made publicly available which is represented as (n,e)

Private Key

Let d be the Private key. Private key is calculated from p,q and e as follows

 

e*d = 1 mod ϕ(n)

 

Private key is represented as (n,d)

Encryption

Suppose a sender wants to send the plain text message to someone having a public key (n,e). 

Plain text can be encrypted as follows

 

C = P^e mod n

Decryption

Using private key pair (n,d) plaintext can be obtained as follows – 

 

P = C^d mod n

Sample Implementation

int x = 61, int y = 53;

int n = x * y; // n = 3233.

 

// computing the totient – phi

int phi = (x-1)*(y-1); // phi = 3120.

 

int e = findCoprime(phi);

// find an ‘e’ which is > 1 and is a co-prime of phi.

// e = 17 satisfies the current values.

 

// Using the extended euclidean algorithm, find ‘d’ 

d = (1 mod (phi))/e; // d = 2753 

 

public_key = (e=17, n=3233);

private_key = (d=2753, n=3233);

 

// Given the plaintext P=123, the ciphertext C is :

C = (123^17) % 3233 = 855;

// To decrypt the ciphertext C:

P = (855^2753) % 3233 = 123;

Hacking RSA Cipher

Hacking an RSA cipher is possible only with small prime numbers. It is considered impossible to hack RSA if it makes use of large numbers. 

Following are the reasons which makes it difficult to hack RSA cipher

  1. Brute force attack is not feasible as there are too many keys to try. This consumes a lot of time and resources.
  2. Dictionary attack is not possible since the keys are numeric and do not make use of any characters.
  3. Since a single encrypted block constitutes various characters, Frequency analysis of the characters is very difficult.

 

Sources 

    1. https://www.geeksforgeeks.org/rsa-algorithm-cryptography/ 
    2. https://www.educative.io/edpresso/what-is-the-rsa-algorithm 
    3. https://www.tutorialspoint.com/cryptography_with_python/cryptography_with_python_understanding_rsa_algorithm.htm 
    4. https://www.di-mgt.com.au/rsa_alg.html 
Posted: February 3, 2021
Articles Author
Nitesh Malviya
View Profile

Nitesh Malviya is a Security Consultant. He has prior experience in Web Appsec, Mobile Appsec and VAPT. At present he works on IoT, Radio and Cloud Security and open to explore various domains of CyberSecurity. He can be reached on his personal blog – https://nitmalviya03.wordpress.com/ and Linkedin – https://www.linkedin.com/in/nitmalviya03/.