The RSA encryption algorithm explained
| Learn how this powerful encryption algorithm works in this easy to understand tutorial. |
RSA is a very powerful encryption algorithm that is based on the public key encryption method. Public key encryption means that you have two pairs of keys, public and private. You give the public key to everyone and keep the private key to yourself. Then, people can encrypt data using the public key and send it to you. Now comes the good part, only you can decrypt the message as only you have the private key, the message cannot be decrypted using the public key. Luckily, RSA is quite simple and shouldn?t be hard to understand.
Now, let us learn in detail how RSA works, firstly you need two really big prime numbers. Prime numbers are numbers that do not go into anything else other themselves or 1. An example of a prime number is 13. Next, we find the product of the two big prime numbers, let us say it is N, so ?
N = First prime number * Second Prime number
Now, this is one part of the public key. We need to find the second number. To find the second number we must understand what exactly relatively prime numbers are. Relatively prime numbers are numbers which share no factors at all. Numbers 13 and 7 are relatively prime, 15 and 5 are not. Now we have to check whether N ( remember N? ) and the first prime number ? 1 multiplied by the second prime number ? 1 are relatively prime. To do this, we have to find a number E in which gcd( E, First prime number ? 1 * Second prime number ? 1) = 1
Over here, E is a random number. Now, N and E together are the public key pair. Next, let us learn how to find the private key pair. The private key is such ?
P = e^ -1 mod ((First prime number - 1)(Second prime number - 1))
Don?t be terrified if you cant understand this, here, mod means modulus, modulus is the remainder after division and ^ means to the power of, for example 2 ^ 2 is 4, that is 2 * 2 = 4. So, P is the remainder left after e^-1 is divided by the product of the first prime number and the second prime number.
We finally have our private key pair, P and E. In the end, N and E are the public key pair and P and E are our private key pair. So, if I wanted to encrypt a letter A, having S as the encrypted text, I would do so like this ?
S = A ^ E mod N
I already explained what mod stands for so there is no need to go into any detail here. To decrypt the alphabet and obtain the original text I would do ?
A = S ^ P mod N
Conclusion ?
I really hope this tutorial helped you understand encryption a wee bit better.
Bibliography ?
Bruce Schneeirs ?Applied Cryptography?
AND the ?Handbook of applied crptography?
Much thanks to Jared a.k.a. rpc for explaining RSA to me.
| | |
|
| Reader Rating from 1-5 |
|
|
|
|
|
|
 Currently there are no Talkback posted on "The RSA encryption algorithm explained", Click here to be the first to post a talkback.
|
|
|
| |
