Menu Close
Steve

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 call this ‘end to end encryption’. 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’.

Basic mathematics.

Before you get started, you will only need a very basic understanding of mathematics. You simply need to know how to multiply and divide numbers. A calculator will  be handy as the numbers can get quite big.

Prime Numbers
A prime number is simply a number divisible by 1 and itself.
e.g. 1, 2, 3, 5, 7, 11 are all prime numbers

Exponentiation
Exponentiation, or raising a number ‘to the power of’ simply means multiplying the base number a certain number of times.
2 to the power of 3 would be written as 2 ^ 3. On your calculator it is the xy button.
e.g. 2 ^ 3 is the same as 2 x 2 x 2 = 8

Modulo
The modulo operation (abbreviated ‘mod’, or ‘%’ in many programming languages) is the remainder when dividing.
5 mod (3) means the remainder of 5 divided by 3, which is 2.
e.g. 5 mod (3) = 2

What Do We Need To Know?

  1. How to create the public and private keys.
  2. How to encrypt the information.
  3. How to decrypt the information.

Step 1) Generating Public and Private Keys

Calculating the public key.

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

Our complete 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:
(PublicKeyB * PrivateKey) mod ((PrimeA - 1) * (PrimeB - 1)) = 1
The remainder must be equal to 1.

Using our example values, (7 * PrivateKey) mod(20) = 1.
e.g. 7 * 3 = 21.
The remainder of (modulo) 21 / 20 = 1.

Therefore, our private key = 3. We must keep this value secret.
PrivateKey = 3

Step 2) Encrypting our Information

To encrypt our information we use our public keys using the following calculation:
(value to be encrypted) to the power of PublicKeyB mod (PublicKeyA).

Let’s break this down,
If our unencrypted value is 14, then:
(14 ^ 7) mod (33) = encrypted value.
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 use our private key and public key using 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 calculate the public and private 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 prime numbers in a timely way is currently unlikely. However, many combinations of shorter prime numbers have been pre-calculated, therefore, the use of longer prime numbers is encouraged.