There is a deep relationship between prime numbers and public key encryption using RSA algorithm. In this post, we will understand why prime numbers are important for encryption. We will work with small prime numbers as shown in the below example and some of those will be our public and private keys. In actual reality, these prime numbers are not small prime numbers such as 11 and 17. They are in reality very very large prime numbers stored in 128 bit or 256 bit, meaning they are 2^128 or 2^256 sized prime numbers. The number itself would be 30 or 40 digits long.
Zoom the below picture and check each step one by one.
Let’s start with deciding the message that we want to encrypt, let’s say we want to encrypt the number 99. Let’s say 99 is a secret number of an Area 99 on Mars that is expected to be very rich in many natural resources that are useful for countries who will claim that area.
So, message to be encrypted is: 99
Step 1: To do this, the first step is to choose two prime numbers ‘p’ and ‘q’.
Step 2: Once you choose the ‘p’ and ‘q’, then you compute ‘N’ by multiplying ‘p’ and ‘q’. This is one of your public keys that you’ll distribute to others who want to send encrypted messages to you.
Step 3: It is simple until now. The next number you’ve to compute is the second number that works as your public key. This is called as ‘e’. There are some restrictions to choose ‘e’ and they are as follows:
Step 4: Now, I am the person who wants to send you an encrypted message of “99”. So, I will look for your public key, which is N – 187 and e – 7. So, I have to encrypt the message using this public key.
- Firstly, the plain text “99” should be raised to the power of ‘e’ – 7. So, 99^7.
- Secondly, divide that with the number N – 187
- The remainder of this is our encrypted or cipher text: Remainder of (99^7/187)
In this case, the remainder is 176 (You can check with this calculator)
- Firstly, the plain text “99” should be raised to the power of ‘e’ – 7. So, 99^7.
- Secondly, divide that with the number N – 187
- The remainder of this is our encrypted or cipher text: Remainder of (99^7/187)
- In this case, the remainder is 176 (You can check with this calculator)
Step 5: So, you received the encrypted text “176” from a secret ally of yours. Now you have to decrypt it. So, when you initially published the public key ‘e’, you’ll also have another number ‘d’ which you don’t tell to anybody. This acts as your private key. Refer the above picture to understand how ‘d’ is calculated. In our case the private key (N,d) is (187, 23)
Step 6: You’ll have to use your private key (N,d) to decrypt this cipher message 176.
- So, to decrypt 176, you have to get the remainder of (176^d)/N = remainder(176^23)/187
- In this case it will be 99, you can check with this calculator
Another simple example of encryption with public-private key is also the use of rotational ciphers. Rotational Ciphers are the most common way to introduce encryption to newbies. For example, if the original message is “PLUTO” then we shift it by one alphabet to right, so the message will become “QMRUP”. This is a rotational cipher of 1. On the same lines, here’s an application of encryption using public key and private key with rotations.
Example:
If a ‘public’ key is 33 then the ‘private’ key is 3 and 11 which can be written as 311. This can be used to code words, for example, ‘HELLO’ would be written as KFMOP. H has been shifted forward 3 spaces to K. E is shifted 1 space to F. L is shifted 1 space to M (we have now completed one cycle of 311 so we start again). The second L is shifted 3 spaces to O and the O is shifted 1 space to P. Write a short phrase and choose two prime numbers as a ‘private’ key. Use the key, as shown above, to write your phrase in code. Swap your message with a friend, giving them only the ‘public’ key to decipher it.
Join our Summer Course in Awareness of Ethical Hacking & Computer Networks and learn a bunch of cool stuff in just 4 weeks.
You may like to read: How Internet runs on under-sea cables, Cyber Law & Protection in India, and How Waves are used in Communications?
