We know that Common Modulus Attacks work with coprime public exponents $(e',s)$ such that $${e_1}s+{e_2}t=\gcd(e_1,e_2)=1$$

I am reading Hinek and Lam's Paper: Common Modulus Attacks on Small Private Exponent RSA and Some Fast Variants (in Practice). Got confused, it seems they proved that Common Modulus Attacks would work with non-coprime public exponents, with the condition of "Small Private Exponent RSA".

Is my understanding correct? Is there some example for this?

  • $\begingroup$ BTW this is related to an ongoing CTF ctf.dicega.ng $\endgroup$
    – Fractalice
    Feb 6 at 22:39
  • $\begingroup$ Mmm..., good to know this is related to CTF challenge happening now. I did not know that, I was just writing some blog for my RSA attack survey and got puzzle on this. $\endgroup$
    – Zixi Sean
    Feb 7 at 6:36

The first common modulus attack is described by G. J. Simmons

and if there is a common modulus and the public exponents are relatively prime (i.e. $\gcd(e_1,e_2)=1$) then recovering the message is easy ( no factoring).

As pointed in section 5 of your linked article;

Howgrave-Graham and Seifert’s small private exponent attack on common modulus RSA [1] improves upon Guo’s attack in several ways. In particular, the attack can be mounted with only two instances of RSA (although it gets stronger with more), the problems associated with relatively prime quantities are not a concern and, most importantly, the attack (even with only two instances) is much stronger.

So your understanding is correct.

  • $\begingroup$ Thanks @kelalaka, wonder if there is any Sage Python coding example for this. $\endgroup$
    – Zixi Sean
    Feb 6 at 19:30
  • $\begingroup$ @ZixiSean the best way is asking to the authors, They may have some implementation, however, these are generally theoretic works so that you may not found one. $\endgroup$
    – kelalaka
    Feb 6 at 19:34

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.