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.
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.
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 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
- Choose 2 large prime numbers — say x & y. These numbers should be large enough.
- Calculate their product n as n=x*y
- Calculate the totient function as ϕ(n) = (x−1)*(y−1)
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.
Numbers n and e forms the RSA public key pair and it is made publicly available which is represented as (n,e)
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)
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
Using private key pair (n,d) plaintext can be obtained as follows –
P = C^d mod n
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
- A brute force attack is not feasible as there are too many keys to try. This consumes a lot of time and resources.
- A dictionary attack is not possible since the keys are numeric and do not make use of any characters.
- Since a single encrypted block constitutes various characters, Frequency analysis of the characters is very difficult.