What are the different plausible ways to decrypt an encrypted data, encrypted using RSA Algorithm without using 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

In the last example, we have taken higher value of n so that it provides higher security as it is impossible to compute mathematically using pen and paper the value of d for such high values of Φ(n).

 

Now, we will develop a computational technique to generate private key from public key so as to decrypt data without having private key for any size of n. We will be using python programming language to achieve private key from public key.

 

The code is as follows:

Example 5:

 

Try of decrypt a cipher data C = 52 which is encrypted using public key (17, 3233).

 

Solution:

 

P = 1589

 

Private Key is (2753, 3233)

 

Let us verify whether we have got the correct value of P or not by encrypting the value to P.

 

C = Pe % n,

 

=> C = 1589¹⁷ % 3233

 

=> C = 52

Example 6:

 

Try of decrypt a cipher data C = 781 which is encrypted using public key (11, 7081).

 

Solution:

 

P = 10

 

Private Key is (5027, 7081)

 

Let us verify whether we have got the correct value of P or not by encrypting the value to P.

 

C = P^e % n,

 

=> C = 10¹¹ % 7081

 

=> C = 781

So, with the help of any programming language, we can build a calculator which can easily provide the encrypted data by deriving the private key. Though security of RSA Algorithm has been increased by taking up to 256-bit value of n.

ECC or Elliptical Curve Cryptography is another algorithm for encryption of data. It is also an asymmetric method of encryption. It is much more secured than RSA Algorithm. It has been studied that 256-bit ‘n’ value key of ECC Algorithm provides the same security as provided by 3072-bit n value key of RSA Algorithm. This is due to the fact that, ECC Algorithm is much more complex than RSA Algorithm. ECC Algorithm takes an elliptical curve for its reference. In an elliptical curve, any two points can intersect at most 3 points on the curve. In ECC Algorithm, a point (A) is taken on the curve a straight line is drawn through another point B to meet C (A ‘dot’ B). Then C is produced vertically in the opposite side of the X-Axis to intersect at another point which is symmetric to the point C’. Then, a straight line is drawn AC’. This straight line will again intersect any point D. Then D is produced vertically in the opposite side of the X-Axis to intersect at another point which is symmetric to the point D’ and this process continues till n times. Whatever the value of the final point will be, will give the value of the key.

In the above-mentioned figure, I have taken the equation of elliptical curve as:

 

y² = x³ – 3x – 3

 

I have taken the first point A (-2, 1) and B (-0.214, 1.898). After 3 iterations (n = 3) I have got the point X (1.57, 1.47) which is my resultant key.

 

We can see that, though the value of n is 3 (I have taken n = 3 for simplicity), still its encryption is much more rigid as compared to RSA Algorithm. Thus, with values of n even more than that, it is practically impossible to compute and get the value of keys.

Mathematics plays a vital role in cyber security and which is evident from this IA. In the course of working on this IA, I have gathered a lot of knowledge regarding Cyber Security threats, different algorithms that helps in encryption and decryption of data packets between sender and receiver to avoid threats of data leakage. Primarily in this IA, I have gone through all the pros and cons of RSA Algorithm and I have tried to find out the different loopholes of this Algorithm. As I have noticed, RSA Algorithm is one of the most stable algorithms that provides cyber security in today’s scenario. With higher values of n in Public and Private keys, it is impossible to crack the private key without complex computational arrangements. Though RSA Algorithm fails drastically with smaller values of n as in that case, private key can be easily identified using simple mathematical operations using pen and paper. Thus, RSA Algorithm is still used in several e-commerce websites but for the websites where network security is more prioritised, such as, online transaction portal, BitCoin trading etc. Elliptical Curve Cryptography is used which offers great security as compared to RSA Algorithm.

• Forouzan, Behrouz A. Cryptography & network security. McGraw-Hill, Inc., 2007.
• Curtmola, Reza, et al. "Searchable symmetric encryption: improved definitions and efficient constructions." Journal of Computer Security 19.5 (2011): 895-934.
• Bellare, Mihir, and Phillip Rogaway. "Optimal asymmetric encryption." Workshop on the Theory and Application of of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1994.
• Zhou, Xin, and Xiaofei Tang. "Research and implementation of RSA algorithm for encryption and decryption." Proceedings of 2011 6th international forum on strategic technology. Vol. 2. IEEE, 2011.
• Matthes, Eric. Python crash course: a hands-on, project-based introduction to programming. No Starch Press, 2015.
• https://www.mtholyoke.edu/courses/quenell/s2003/ma139/js/powermod.html
• https://www.desmos.com/calculator
• Lehmer, D. H. "On Euler’s totient function." Bulletin of the American Mathematical Society 38.10 (1932): 745-751.
• Tirthani, Neha, and R. Ganesan. "Data Security in Cloud Architecture Based on Diffie Hellman and Elliptical Curve Cryptography." IACR Cryptol. ePrint Arch. 2014 (2014): 49.