What are the different plausible ways to decrypt encrypted data, encrypted using RSA algorithm without using a private key?

Since my childhood, I am really fascinated with internet. At a younger age, I used to wonder on how on computers we can get all sort of data in fraction of seconds. I was always mesmerized with beautiful designs of webpages and all sorts of animations that used to come while scrolling down the webpages. Personally, cartoons and animated videos never gained much value in my mind as the animations on webpages have gained. I always wanted to learn how these webpages work and how to design such beautiful websites. But as there was lack of knowledge as well as programming skills, I was unable to achieve my dreams of designing beautiful webpages. Day by day, I have started to learn programming language and finally in last summer, I had successfully completed a course on Webpage Development. Initially I was very much interested in webpage development but very soon my happy days in developing animated webpages turned gloomy. Whenever I launched any webpage on the internet, either it got attacked by some unidentified user or whatever data transmission happened between my website and any user, the data got leaked. In the days of my childhood, I always thought about the animation and designs of the websites but never thought about the security of the website. Once we were having a video chat with relatives who reside in the US over Skype and suddenly a thought crossed my mind. I was worried that whatever data gets transferred to and from my website gets leaked I had never seen any case of cross connection in Skype. This thought led my interest to learn more about Cyber Security and Ethical Hacking. After attending three sessions, I was completely able to hack my router and was able to access every packet of data that was getting transferred through that router. But I was unable to crack the information present in the packets of the data whereas whenever I tried to use my own website as a user, I could access the information that were transferred from my website to the user as I hacked my home router. Later on, I got to know from my Cyber Security tutorial classes that data transmitted and received to and from my website was getting leaked as there was no encryption of data in my website. Moreover, there was no certification of my website as well which led to continuous cyber-attacks in my website.

 

As a web-developer I would like to put forward different ways to deal with the cyber-attacks so that the users of website designers may include such procedures to keep their website safe from hackers and also the users can get assured that their data will not get leaked under any circumstances. In this IA, I would like to discuss two algorithms for data encryption so that even if one’s data gets leaked, then how that encrypted data packet can be decrypted without any key by the hacker in order to increase the efficiency of the algorithm and also, I would do a comparative study based on the two algorithms.

The main motive of this IA is to explore mathematical operations that are used to design the RSA Algorithm and ECC Algorithm which are used to encrypt and decrypt data in various ends of any network. The webpage development’s front end and backend activities remaining the same, we have to add an encryption and decryption method in the server. Our primary objective is to decrypt the data that needs to be sent from the user to the server or vice versa without private key so that we can find the loopholes of the RSA Algorithm. Furthermore, we will do a comparative study on different perspectives of RSA Algorithm and ECC Algorithm.

Encryption is a procedure of converting the message data into some codes using a key. It can be considered as locking the actual message data using the key and that message cannot be accessed unless and until the key is used to unlock the data. The process of unlocking the encrypted message data is called Decryption. Encrypted message is called cipher data. To make the long story short, when any user sends some data to the website, firstly the browser that has been used by the user encrypts the data and converts into a cipher text. This cipher text is then transferred to the website or server. The server or website decrypts the cipher text into actual message to perform the request that has been done by the user and same process is followed while any data is sent from website to the user. But, in order to encrypt or decrypt the message data or cipher data, one must require the key.

 

Thus, there are two types of encryption procedures. They are –

• Symmetric Encryption: In case of symmetric encryption, same key is used to encrypt and decrypt the data. Now, this process is less secured as after encryption from one end, the cipher data along with the key must be sent to the other side of the network to decrypt the data. Thus, while transferring the key, if any hacker gets the key then he/she will be able to decrypt the data the get the actual message.

• Asymmetric Encryption: In this type of encryption, a pair of keys are allocated to each user and server/ website. They are – Public Key and Private Key. Public Key is used to encrypt the data while private key is used to decrypt the data. Public Key, as the name suggests is available for every user and server in the network but private key is not made public. Every user and server have one public key and one private key.

 

For example, if Computer A wants to send any information to Computer B, firstly Computer A will fetch the Public Key of Computer B and then encrypt the data using the public key of Computer B. After encryption, the cipher data will be transmitted to Computer B. On receiving the cipher data, Computer B will decrypt the cipher data using its own Private Key. As a result, even if any hacker gets the cipher data from the network while transferring from Computer A to Computer B, then also he/ she will not be able to decrypt the data as its decryption can only be done using Private Key of B.

 

Moreover, same pair of keys must be used to encrypt and decrypt the data otherwise the process will not work, i.e., if public key of Computer B is used for encryption of data, then private key of Computer B must be used to decrypt it.

RSA Algorithm or Rivest – Shamir – Adleman Algorithm was designed in the year 1977 by Ron Rivest, Adi Shamir and Leonard Adleman. They have designed this algorithm on the basis of few fundamental concepts of mathematics like factors, GCD, modulo operation etc. Two most important theorems that are used in generation of public and private keys of RSA Algorithm are Fermat’s Little Theorem and Eular Totient Theorem.

 

Fermat’s Little Theorem states that, a^p-1 % p = 1 where a is an integer and p is a prime number.

 

Euler’ Totient Theorem gives us the number of coprime factors of any number n is (n-1) where n is a prime number.

 

The process of RSA Algorithm is divided into three parts. They are –

• Key Generation
• Encryption
• Decryption

 

Key Generation is by far the most important step of RSA Algorithm. In this step, Public and Private keys are assigned. Each key has two parts. Public Keys are denoted by (e, n) and Private Keys are denoted by (d, n). As we can see that second part of both the keys are constant. Key Generation is further divided into few steps. They are:

• Choosing the value of n in indirect way: Two prime number p and q are considered such that their product is equal to n. More the value of n, higher will be the security of the encryption.
• Find the value of Φ(n) using Euler Totient Function.
• Find the value of e (for Public Key) such that: (a) 1 < e < n and (b) e is a coprime of Φ(n).
• Find the value of d (for Private Key) such that: d*e % Φ(n) = 1

 

By the above-mentioned steps, we will be able to assign public key as well of private key of any user or server.

 

Encryption is the next process in which the message data is firstly converted into an integer then it is encrypted to cipher text using public key (e, n). Suppose, the equivalent integer value of any text or any other data type is P. Then, the cipher text (C) will be:

 

C = P^e % n

 

Decryption is the next process in which cipher text is converted into the equivalent integral value of text or actual message using private key (d, n). Suppose, the received cipher text be C. Then, the equivalent integral value of actual message (P) will be:

 

P = C^d % n

In the course of demonstration, I have used few software for getting output. They are: Power Modulo Calculator, PyCharm 2020.1 and Desmos.

 

Example 1 -

 

Suppose the equivalent integral value of the actual message be 3. Design public and private key using RSA Algorithm and also find out the cipher text and decrypt the cipher text as well.

 

Solution -

 

Step 1 - Let us assume two prime numbers p and q such that p = 5 and q = 7.

Therefore, n = p x q = 5 x 7 = 35.

So, it is very easy to find the prime factors of n = 35 as 35 is a small value. But, if we take n = 3233, then it would be very difficult to find the values of p and q from n. Without the values of p and q with will be very difficult to find the value of Φ(n). Thus, if we take a larger value of n then it will be almost impossible to crack the key.

 

Step 2 - We have to find the number of co-primes of 35. Let us list up all the co-primes of 35. They are: {1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34}. From the list, we can observe that, there are 24 values. So Φ(n) = 24. But, as we know, the value of n is taken by the user. So, more the value of n, more will be the number of co-primes then for higher values of n, it will be a tedious job to find the number of co-primes making the list of co-primes. That’s why, we have to use Euler Totient Function to find the number of co-primes.

 

From Euler Totient Function, we know that number of co-primes of any prime number (p) is (p-1).

 

Therefore, Φ(n) = (p-1) x (q-1)

 

In this case, p = 5 and q = 7.

 

Therefore, Φ(n) = (5-1) x (7-1) = 4 x 6 = 24

 

Step 3 - Now, value of e will lie between 1 and 24 again, e will be a co-prime of 24. Let us list up the co-primes of 24 that lies between 1 and 24. They are: {5, 7, 11, 13, 17, 19, 23}. Value of e may be any of these numbers. Let’s take e = 5.

 

Now, finally the public key will be (5, 35). This key is visible for all users on the internet.

 

Step 4 - Now we have to find the value of d for private key using the formula:

 

d*e % Φ(n) = 1

 

In this case, e = 5 and Φ(n) = 24. Now the only way to find the value of d is trial and error. Moreover, just like e, there will be a set of values of d. Out of which we have to choose one.

 

Solving the equation, we get, (d x 5) % 24 = 1

 

Possible values of d are as follows: {5, 29 …}

 

Let’s take, d = 29.

 

So, Private key will be (29, 35).

 

Step 5 - Encryption of data:

 

C = P^e % n,

 

In this case, P = 3, e = 5, n = 35.

 

C = 3⁵ % 35 = 33

Step 6 - Decryption of data:

 

P = C^d % n

 

In this case, C = 33, d = 29, n = 35

 

P = 33²⁹ % 35 = 3

From the algorithm, it is clear that public key values (e, n) are visible to all the users. In order to decrypt, the cipher data, we have to find the value of d for which, we have to find the value of Φ(n). For smaller values of n, Φ(n) can be easily found. This is the only method to crack the private key. If the value of n is high then Φ(n) can be found only using complex computational techniques.

 

In the next few examples, we will try to derive the private key from a given public key whose value of n is low.

 

Example 2 - Try of hack or decrypt a cipher data C = 4 which is encrypted using public key (5,14).

 

Solution -

 

Step 1 - Choose two prime number whose product is equal to n.

 

In this case, as n = 14. We can easily assume p = 2 and q = 7.

 

Step 2 - Φ(n) = (p-1) x (q-1) = 1 x 6 = 6

 

Step 3 - d x e % Φ(n) = 1

 

=> (d x 5) % 6 = 1

 

The possible values of d will be: {5, 11, 17….}

 

Let’s take d = 11.

 

Private key = (11, 14)

 

Step 4 - P = C^d % n

 

=> P = 4¹¹ % 14

 

=> P = 2

We can also verify, whether the decryption is correct or not by converting the integral value of message data into it’s cipher data by the process of encryption.

 

C = P^e % n,

 

=> C = 2⁵ % 14

 

=> C = 4

As, encrypted cipher data and given cipher data are equal, thus we can say that our decryption process is correct. So, by this way we can crack private key using mathematical operations considering the fact that value of n is small.

 

Example 3 - Try of decrypt a cipher data C = 8 which is encrypted using public key (11, 21).

 

Solution -

 

Step 1 - Choose two prime number whose product is equal to n.

 

In this case, as n = 21. We can easily assume p = 3 and q = 7.

 

Step 2 - Φ(n) = (p-1) x (q-1) = 2 x 6 = 12

 

Step 3 - d x e % Φ(n) = 1

 

=> (d x 11) % 12 = 1

 

The possible value of d is 11

 

Private key = (11, 14)

 

Step 4 - P = C^d % n

 

=> P = 8¹¹ % 12

 

=> P = 8

We can also verify, whether the decryption is correct or not by converting the integral value of message data into its cipher data by the process of encryption.

 

C = P^e % n,

 

=> C = 8¹¹ % 12

 

=> C = 8

Now, we will try to design an encryption using RSA with higher value of n so that, it can be more secured.

 

Example 4 -

 

Suppose the equivalent integral value of the actual message be 10. Design public and private key using RSA Algorithm and also find out the cipher text and decrypt the cipher text as well.

 

Solution -

 

Step 1 - Suppose p = 73 and q = 97.

 

Then, value of n = p x q = 73 x 97 = 7081

 

Step 2 - Φ(n) = (p-1) x (q-1) = 72 x 96 = 6912.

 

Step 3 - Value of e will range between 1 and 6912 and e will be a co-prime to 6912.

 

Let us assume, e = 11 as e satisfies the above two conditions.

 

So, Public Key is (11, 7081)

 

Step 4 - d x e % Φ(n) = 1

 

=> d x 11 % 6912 = 1

 

On solving using computational techniques, we will get,

d = 5027

 

So, private key is (5027, 7081).

 

Step 4 - Encryption of data:

 

C = P^e % n,

 

=> C = 10¹¹ % 7081

 

=> C = 781

Step 5 - Decryption of data:

 

P = C^d % n

 

=> P = 781⁵⁰²⁷ % 7081

 

=> P = 10