RSA: Common Modulus attack with extended Euclidean algorithm
RSA common modulus attack using extended euclidean
RSA, a commonly used public key cryptosystem, is very secure if you use sufficiently large numbers for encryption. Even then there are attacks against it. If you are not already familiar with RSA encryption mechanism, I suggest you read more about it before continuing with this article.
Consider a scenario where a person encrypts same plain text, 2 different times, which he sends to 2 different people. Suppose you eavesdropped on the communication and got both the cipher texts (c1, c2) and the exponents(e1, e2) he used. You already know his Modulus N which is public. So is there a way you can decipher this ? Well the answer is yes.
In order to decrypt it, we use an algorithm called extended euclidean which makes our tasks much easier. But another condition we need to decrypt this is that the
gcd(e1, e2) = 1
You must be thinking that why the hell did I just say gcd(e1, e2) should be equal to 1 ? Well here is the answer:
If you already know how the RSA encryption works, then by now you would have understood that
c1 = m^e1 % N and
c2 = m^e2 % N
Assume that we find out a and b such that
(e1 * a) + (e2 * b) = 1 then we can decode the plain text as
(c1 ^ a) + (c2 ^ b). If we substitute how c1 and c2 is calculated to above equation, we can get
m^(e1 * a + e2 * b) = m^1 = m
Let us see how the algorithm works
(e1*a) + (e2*b) = gcd(e1, e2)
where e is exponents.
Now, we need to find a and** b. In order to find a, since gcd(e1, e2) = 1, then we can say that a is the **modular multiplicative inverse of el and e2. After finding a, we can substitute the value to the above equation so that we can successfully obtain b. After getting a and b, we can get back the plain text by applying the equation
plain = (c1^a) * (c2^b) %N
Another issue that can happen here is that, in most of the cases, the value of b will be negative and hence it is difficult to apply in the above equation. So in order to simplify this, we find out another value named i, which is the modular multiplicative inverse of c2 w.r.t N. Then we can say
i^-b = c2^b.
So now the equation becomes
plain = (c1^a) * (i^-b) %N. This is what we need in order to decrypt the plain text. Let us look into a python script that can automate the above process:
So here we deal with 2 function namely extended_euclidean and modular_inverse. The extended_euclidean function will help us in calculating the value of a and b. In almost all the cases, the value of b will be negative and because of that, we will find out i in modular_inverse function and also calculate the plain text from the above explained equation.
In order to successfully launch an attack, the gcd of e1 and e2 must be equal to 1 or else this may not work.
The python script makes use of a library called gmpy2. If you don’t have it already installed on your system, then do this:
sudo apt-get install python3-gmpy2
When you change the exponents e1, e2 for encrypting the messages it also changes the Private/Public Key Pair. In practice we use the same key pairs so there wont be question of e1/e2 that makes decryption of crypt-text difficult.
If you have any issues related to the above tutorial or if you have a better way of scripting, please don’t hesitate to comment below. We would like to hear from you :)