# Need help to understand this RSA common modulus attack Python code

I am reading Practical Cryptography in Python. I have problem understanding the common_modulus_decrypt() function. I think the prerequisite of RSA Common Modulus Attack is that two public exponents have to be co-prime, meaning $$gcd(e_1,e_2)=1$$, right? That is what I get from how to use common modulus attack?

If this is true, why does it do the following:

def common_modulus_decrypt(c1, c2, key1, key2):
key1_numbers = key1.public_numbers()
key2_numbers = key2.public_numbers()

if key1_numbers.n != key2_numbers.n:
raise ValueError("Common modulus attack requires a common modulus")
n = key1_numbers.n

if key1_numbers.e == key2_numbers.e:
raise ValueError("Common modulus attack requires different public exponents")

e1, e2 = key1_numbers.e, key2_numbers.e
num1, num2 = min(e1, e2), max(e1, e2)
while num2 != 0:
num1, num2 = num2, num1 % num2
gcd = num1

a = gmpy2.invert(key1_numbers.e, key2_numbers.e)
b = float(gcd - (a*e1))/float(e2)

i = gmpy2.invert(c2, n)
mx = pow(c1, a, n)
my = pow(i, int(-b), n)
return mx * my % n


If gcd is always 1, why bothering with the while loop above? Also, I thought it should use the Extended Euclidean algorithm to get a and b. Why is it doing invert with e1 and e2? Why is it using float()?

The last 3 steps for i,mx,my I can understand, as it assumes b is a minus value.

• Does this answer your question? how to use common modulus attack? Jan 24 at 20:30
• No, it does not. As I mentioned, I assume co-prime is a required condition. Why doe does this code try to find gcd, as it should always be 1. Jan 24 at 20:36
• To use the Bezout identity and your question is not clear, too. What is num1 num2! Jan 24 at 20:37
• I added the missing part of this function, now it is complete. num1 and num2 are just the exponents of input keys. Jan 24 at 20:41

Step by step of the code;

1. $$gcd = \gcd(e_1,e_2)$$

2. $$a = e_1^{-1} \bmod e_2$$

3. $$b =gcd - (a\cdot e_1))/e_2 \implies gcd = b \cdot e_2 + a\cdot e_1$$; The Bézout's identity

4. $$i = c_2^{-1} \bmod n$$

5. $$mx = c_1^a \bmod n$$

6. $$my = i^{-b} \bmod n$$

7. $$\text{return } (mx \cdot my) \bmod n$$

Now check \begin{align} mx \cdot my &=c_1^a \cdot i^{-b} \pmod n\\ & = c_1^a \cdot (c_2^{-1})^{-b} \pmod n\\ & =(m^{e_1})^a \cdot (m^{e_2})^{b} \pmod n\\ & =(m^{e_1 a+ e_2 b}) \pmod n\\ & = (m^{gcd}) & & \big[ = m \!\!\!\pmod n \,\textbf{ if } gcd=1\big]\\ \end{align}

The above calculation works for any $$gcd$$. This doesn't mean that we can resolve the message $$m$$ if $$gcd>1$$. What if $$gcd \neq 1$$ then for case 2, it is so-called Rabin Cryptosystem, security is shown to be equal to factoring. if $$gcd =3$$ is the cube-root attack possible and if the textbook RSA is used and the message $$m < \sqrt{n}$$ recovery possible, and so on.

The conclusion is that they forget to write

  if gcd != 1:
return -1


Writing good software is hard, writing good cryptographic software is much harder.

The common modulus attack is performed on Text-Book RSA when Alice and Bob use the same modulus $$n$$ with different public modulus. The first observation is that this is dangerous since Alice can learn Bob's private key, v.s. On the other hand, the eavesdropper ( passive attacker) knows the public keys $$(n,e_1)$$ and $$(n,e_2)$$ and when observed that the same message is sent to Alice and Bob (possibly broadcasting). Then the eavesdropper can resolve the broadcasted message $$m$$ if $$\gcd(e_1,e_2)=1$$. If they are using the same public exponent, this attack doesn't work.

When proper padding is used like PKCS#1 v1.5 and OAEP then this attack is not possible since they use randomization that prevents the equality of the same messages.

• Thanks！This is the perfect answer. I think we should send this feedback to the book author to fix this. Jan 24 at 23:16
• That is why GitHub is there. Jan 24 at 23:22