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

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.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Private and public keys in cryptography

A key is a bit-valued string that is used to convert the plaintext into ciphertext 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 the most secure way of encrypting data.

The 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. The private key is calculated from p,q and e as follows

e*d = 1 mod ϕ(n)

The 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. 

The following are the reasons which make it difficult to hack RSA cipher

1. A brute force attack is not feasible as there are too many keys to try. This consumes a lot of time and resources.
2. A 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.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Sources 

• https://www.geeksforgeeks.org/rsa-algorithm-cryptography/ 
• https://www.educative.io/edpresso/what-is-the-rsa-algorithm 
• https://www.tutorialspoint.com/cryptography_with_python/cryptography_with_python_understanding_rsa_algorithm.htm 
• https://www.di-mgt.com.au/rsa_alg.html