RSA is a cryptosystem, which is known as one of the first practicable public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described the algorithm in 1977.
Working of RSA :
The algorithm involves multiplying two large prime numbers and through additional operations deriving a set of two numbers that constitutes the public key and another set that is the private key. Once the keys have been developed, the original prime numbers are no longer important and can be discarded. Both the public and the private keys are needed for encryption /decryption but only the owner of a private key ever needs to know it. Using the RSA system, the private key never needs to be sent across the Internet.The private key is used to decrypt text that has been encrypted with the public key.
Example :
Select the prime integers q=11, q=3.
n=pq=33; φ(n)=(p-1)(q-1)=20
Choose e=3
Check gcd(3,20)=1
Compute d=7
(3)d ≡ 1 (mod 20)
Therefore the public key is (n, e) = (33, 3) and the private key is (n, d) = (33, 7).
Now say we wanted to encrypt the message M=7
C = Me mod n
C = 73 mod 33
C = 343 mod 33
C = 13
So now the cyphertext C has been found. The decryption of C is performed as follows.
M' = Cd mod n
M' = 137 mod 33
M' = 62,748,517 mod 33
M' = 7
As you can see after the message has been encrypted and decrypted the final message M' is the same as the original message M. A more practical way to use the algorithm is to convert the message to hexadecimal and perform the encryption and decryption steps on each octet individually.
