RSA Algorithm
What is the RSA Algorithm?
RSA (Rivest Shamir Adleman) algorithm is an asymmetric cryptography algorithm. Asymmetric means it works on two different keys, i.e., Public and Private. As the name describes, the Public Key is given to everyone, and the Private key is kept private.
The inventors are Ron Rivest, Adi Shamir, and Leonard Adleman.
Some Keyword
Factor
The factor of a number is a number that divides the given number without keeping any reminder. It is also known as the divisor.
Example: The factors of 12 are 1, 2, 3, 4, 6, and 12
Prime
A prime number is a number that can only be divided by itself and 1 without remainders.
Example: 2, 3, 5, 7, 11, 13, 17, …….
1 is not a prime number.
Co-Prime
Co-prime numbers are pairs of numbers with no common factor (gcd) other than 1.
For example, 5, 7, and 9 are co-prime.
Semi Prime
A semiprime is a natural number that is the product of precisely two prime numbers. The product of two prime numbers is always a semi-prime.
21 is a semi-prime number because this is a product of 3 and 7. Both are prime numbers.
Modulo
The module (mod) is the reminder when dividing a number.
Example: 24 MOD 5 = 4
RSA Operation
The RSA Algorithm involves four steps.
- Key Generation (Public & Private Key)
- Key Distribution
- Encryption
- Decryption
Key Generation
To generate Public and Private Key follow the following processes:
1. Choose two prime numbers p, q
- To make factoring harder, p and q should be chosen at random, large, and have a significant difference.
- p and q should be kept secret.
2. Calculate, n = p*q
- n is shareable as a public key.
3. Calculate, phi(n) = (p-1)(q-1)
- phi(n) is not shareable with others.
4. Choose a natural number e where 1 < e < phi(n) and e is co-prime of phi(n)
- e is also shareable.
5. Generate Private Key: d = pow(e, -1, phi) or d=inverse(e,phi)
- d is the private key. So, it is personal to everyone.
Key Distribution
If you send a message to anyone with RSA encryption, they share public keys n and e to you. To decrypt the message, he needs a private key d.
Encryption
If the message text is m, the encryption formula is,
c = m^e mod n = pow(m,e,n)
Here, c — Cipher text
Decryption
If the cipher text is c, the decryption formula is,
m = c^d mod n = pow(c,d,n)
Example RSA
- Choose two random prime numbers, p = 61 and q = 53
- Calculate, n = 61*53 = 3233
- Calculate, phi(n) = (61–1)(53–1) = 3120
- Choose e. e = 17.
- Compute, d = e^-1 mod phi = 2753
If message m = 123,
Encryption:
c = m^e mod n = 855
Decryption:
m = c^d mod n = 123
Resources
Online Tool:
https://www.devglan.com/online-tools/rsa-encryption-decryption
