How the RSA Encryption Algorithm Works for Kids
Whenever you see the ‘padlock’ symbol on a website you can be assured the information you send to the website is encrypted in such a way that nobody, including very power computers, can decrypt it. We can easily take it for granted that our data is encrypted as it travels through many computer devices on the internet and is completely safe from even very determined hackers.
But how does it work, and is it really that safe? In this post I will attempt to explain and demonstrate it in very simple terms. The math is extremely simply when broken down.
Introduction
Information is sent from a web server to a website visitor over the internet. The information can be sent in many different formats, but by far the most common format is ‘hyper text mark-up language’, or HTML for short. It really doesn’t matter what we are sending, the server will encrypt everything. Apart from a padlock icon, we can be certain the web server is encrypting the data when the website address begins with ‘https://‘. So how does the web server encrypt the information.
How Does It Work?
The RSA Algorithm works by using two keys to encrypt and decrypt the information. These keys are known as the private key and public key. Information encrypted with private key can only be decrypted with the public key. And information encrypted with the public key can only be decrypted with the private key. Essentially, this is the basis of all public private key encryption.
Before any communication happens, the Web Server had calculated, in advance, its public key, ’33’ and ‘7’ and private key ‘3’.
Now, to initiate the transaction, the Browser sends this message to the server:
Hello Web Server, please send me your public key.
The Server responds by sending it’s public key, ’33’ and ‘7’.
After receiving the Server’s public key, the Browser converts the plain value ’14’ into the encrypted value ’20’ and sends it to the Server. The Server receives this encrypted value ’20’ and using its secret key ‘3’ and publicly known key ’33’, decrypts the encrypted value of ’20’ into its original unencrypted value of ’14’.
What Do We Need To Know?
- How to create the public and private keys.
- How to encrypt the information.
- How to decrypt the information.
Step 1) Generating Public and Private Keys
First pick two different prime numbers.
e.g. PrimeA = 3 and PrimeB = 11.
Then calculate the output of PrimeA * PrimeB
e.g. 3 * 11 = 33
This becomes the first element of our public key. PublicKeyA = 33
Then calculate the output of (PrimeA – 1) * (PrimeB – 1)
e.g. (3 – 1) * (11 – 1) = 20
Then pick a third different prime number which is a coprime of 20.
That is, 20 is not divisible by our third prime number; A coprime.
Note, we cannot not use 5 because 20 is divisible by 5.
e.g. PrimeC = 7
This becomes the second element of our public key. PublicKeyB = 7
Calculating the public key.
Our public key is (PrimeA * PrimeB) and PrimeC.
e.g. public key = 33 and 7.
PublicKeyA = 33
PublicKeyB = 7
Calculating the private key.
To calculate the private key, we use the following calculation:
(PrimeC * PrivateKey) mod((PrimeA – 1) * (PrimeB – 1)) = 1
PrimeC * “something”, then divided by ((PrimeA – 1) * (PrimeB – 1)). The remainder must be equal to 1.
So, using our example values, (7 * PrivateKey) mod(20) = 1
e.g. 7 * 3 = 21. The remainder of (modulo) 21 / 20 = 1.
The modulo operation (abbreviated ‘mod’, or ‘%’ in many programming languages) is the remainder when dividing.
e.g. 5 mod(3) = 2 which means 2 is the remainder when you divide 5 by 3.
Therefore, our private key = 3. We must keep this value secret.
PrivateKey = 3
Step 2) Encrypting our Information
To encrypt our information we do the following calculation:
‘value to be encrypted’ to the power of PrimeC = ‘encrypted value’ mod (PrimeA * PrimeB).
Let’s break this down.
If our unencrypted value is 14, then:
14 ^ 7 = ‘encrypted value’ mod (33).
In English, raise 14 to the power of 7, divide this by 33, giving the remainder of ‘encrypted value’.
Therefore, to encrypt a value of 14.
14 ^ 7 mod (33).
Breaking this down:
14 ^ 7 = 105,413,504
105,413,504 mod (33) = 20
Therefore, ’14’ encrypted value is ’20’.
To calculate the modulo of 105,413,504 mod (33) we can:
First divide 105,413,504 / 33 = 3,194,348.606
Then multiply 3,194,348 * 33 = 105,413,484
Then subtract 105,413,504 – 105,413,484 = 20.
Step 3) Decrypting our Information
To decrypt our information we do the following calculation:
EncryptedValue ^ PrivateKey = DecryptedValue mod(PublicKeyA)
e.g. 20 ^ 3 = DecryptedValue mod(33)
20 ^ 3 = 8000
8000 mod(33) = 14
DecryptedValue = 14
To calculate the modulo of 8000 mod (33) we can:
First divide 8000 / 33 = 242.42424…
Then multiply 242 * 33 = 7986
Then subtract 8000 – 7986 = 14
Summary
I did not discuss the theory behind the RSA Algorithm, but I hope that you now have a basic idea of how the public key cryptography using the RSA algorithm works.
Finally, Cracking the Encryption
The essential requirement of the Public Key Cryptography is that the public and secret keys are mathematically related, but this relationship must be made very hard to determine by an outsider.
Everything starts with the prime numbers, PrimeA, PrimeB and PrimeC from which we calculated the public keys. Crucially, a brute force test could be performed if we could guess which prime numbers were selected to create our public and private keys. Whilst the range of possible prime numbers are known, a brute force calculation would take an incredibly powerful computer. Each prime number can be several hundred digits long, and finding the exact combination of values in a timely way is currently unlikely.