RSA encryption is an Algorithm understood by so few people and used by many. In hopes to help that large percentage understand RSA Encryption better I wrote this explanation. If you ever visit a https site chances are you are using RSA encryption to encrypt or scramble the data sent over the internet. Since you could be sending important information like a credit card number it is imperative that you encrypt the data. The important thing is that we want to do this encryption process without requiring secret keys that both the sender and the recipient must posses. That’s where a system that uses a “Public Key” comes in handy.
1. GENERATE A PUBLIC KEY AND PRIVATE KEY
First we need our keys: A private key that the server will keep and a public key that can be given away.
We need 2 prime numbers:
p & q. p = 29, q = 31
Calculate n = p * q = 29 * 31 = 899
Calculate t = (p -1) * (q – 1) = (29 – 1) * (31 – 1) = 840
Choose a prime number e. e needs to be relatively prime to t. (t cannot be divisible by e) Lets pick 11
We now need to find a d. We will use the formula: d * e [=] 1 mod t
This means (d * 11) / t will give us a remainder of one. You have to find the inverse of e mod t. If your interested in how this can be computed please check my other post here. Since we are dealing with such small numbers we can sort of guess our d until we find one that works.
(611 * 11) = 6721, 6721 / 840 = 8 with remainder 1. So 611 works! We now have everything we need for a private and public key to encrypt our data.
p – 29
q – 31
n – 899
t – 840
e – 11
d – 611
Our public key becomes n and e.
Our private key becomes n and d.
2. ENCRYPTING OUR MESSAGE
We give our public key numbers to the person that wants to send us their message. They will encrypt the message with the formula:
C = Me mod n
C is our encrypted Message. So if we took the letter ‘w’ whose ascii value is 119.
C = 11911 mod 899 = 595 ( Please read my post on how to do fast modular exponentiation)
We now send 595 to the server.
3. DECRYPTING OUR MESSAGE
In order to decrypt the message we need our private key. n and d
Keep in mind we don’t give anybody our private key.
We use the formula M = Cd mod n
so M = 595611 mod 899 = 119
M = 119 whose character value is ‘w’ our original message!