RSA (Rivest–Shamir–Adleman) is a Public-Key cryptographic algorithm. It involves a public key to encrypt and corresponding private key to decrypt data to transmit securely and to verify digital signature.
Step 1: Generate the key
- Take any 2 large prime numbers p and q
- Let n = p*q
- Find the totient of n
(Totient of n means the count of the numbers which are less than n and each of the numbers are relatively prime to n.
So, for example totient of 11 is 11 , because there are 11 numbers 1,2,3,4,5,6.7,8,9,10 , these are relatively prime to 11.
Same way Totient of 12 is 4, because 1,5,7,11 , these 4 numbers are relatively prime to 12, and there is no common factor of 12 and any of these numbers. Easy way to find totient of p*q = (p-1)*(q-1))
)
Step 2: Do the math to encrypt/decrypt
If your message is m and cypher is c , then
- c = m^e mod n — This is encryption
- m = c^d mod n — This is decryption
Example
Let p = 7 and q = 17 , so n = 7 x 17 = 119
The totient of n (119) = (p-1)(q-1) = (7-1)(17-1) = 96
Choose integer e (public exponent) which is < 96 and relatively prime to 96 . Let us choose the number 53 which satisfies this condition.
Choose the 2nd integer d (private exponent) , which will satisfy (e*d) mod totient(n) = 1 . j = 29 satisfies this.
(53 * 29) mod 96 = 1)
so public key = 53 and private key = 29 .
Let us encrypt the Letter H (Which is 7 as integer, A=0, B=1 , C=2 ….Z=25) and decrypt back.)
- c = m^e mod n = 7^53 mod 119 = 28 Encrypted
- m = c^d mod n = 28^29 mod 119 = 7 Decrypted (Which is back to H)
Why is it secure
- In our example we used very small prime integers (7 and 17). But in real use, the prime integers are big to enhance security. It is not only knowing the public exponent e and the value of n to crack this, the totient is needed too.
- If it is said that 2048 bit RSA signature means the n is of 2048 bits (Max integer value 2^2048 – 1). So, if the value of n is a 2048 bit number, it is almost impossible to crack it.
Implementation
I’ve implemented a simple version of this in Java so you can play with the logic yourself.
GitHub: Supporting Java code and Readme
Common Risks
Size
- Problem: If the value of n (p*q) is small, it is easy to detect the factors (p and q) quickly.
- Solution: Use 2048 bit numbers
Determinism Attack
- Problem: When attacker could guess the message, because as per the theory the encrypted value of the same TEXT would be the same. If “Hi” is encrypted with the public key twice it would give the same encrypted value.
- Solution: Using Padding like OAEP . Here random data are added to the message before encrypting it to make the text of the message look different before encrypting.
Mathematical Attack
- Problem: when m is small , it could be easy for the attacker to find the value of c = m^e mod n , without knowing the private exponent d.
- Solution: Same as before, use padding OAEP.