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!
This does not look like basic math I want my money back! 😀
Well you do need to understand what a prime number is. How to multiply, divide, add, and subtract. You also need to understand how the modulo operation works. That’s about it!
Good fill someone in on and this enter helped me alot in my college assignement. Gratefulness you as your information.
Although this helped me understand some of how RSA works, in the end what makes it difficult to find the private key?
In short there is no known efficient factorization algorithm. You don’t know p and q but only know the product of the two “n”.
For more information on prime factorization see here.