1
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ Does this answer your question? how to use common modulus attack? $\endgroup$ – kelalaka Jan 24 at 20:30
  • $\begingroup$ 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. $\endgroup$ – Zixi Sean Jan 24 at 20:36
  • $\begingroup$ To use the Bezout identity and your question is not clear, too. What is num1 num2! $\endgroup$ – kelalaka Jan 24 at 20:37
  • $\begingroup$ I added the missing part of this function, now it is complete. num1 and num2 are just the exponents of input keys. $\endgroup$ – Zixi Sean Jan 24 at 20:41
1
$\begingroup$

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[3]{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.

or someone is wrong on the internet


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.

$\endgroup$
2
  • $\begingroup$ Thanks!This is the perfect answer. I think we should send this feedback to the book author to fix this. $\endgroup$ – Zixi Sean Jan 24 at 23:16
  • $\begingroup$ That is why GitHub is there. $\endgroup$ – kelalaka Jan 24 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.