I am working through a series of crypto exercises to learn a bit more about RSA and crypto in general. In the case where one has a small $e$ AND a small m, would it be correct to say that if $m<N^{1/e}$ then we can attack by calculating the $e$-th square of $m^{e}$?

If that is a correct statement, then what would be the best way to approach such an attack practically? Is there a tool that exists? Or would it be better to code a brute force solution in Python?

Apologize for the basic questions - just beginning to dip into crypto. Any advice is much appreciated. Thank you!

up vote 1 down vote accepted

Yes, computing the e-th root over the integers should work, since $m^e < N$, so their is no 'wrap around', i.e. $m^e \mod N = m^e$.

As for implementation, if $m$ is not too large, say less than $50$ bits, taking a floating point approximation of the root and rounding should do the trick in python: m = int(round(c**(1./e)))

If not, you do not need to resort to bruteforce search though. One simpler way is to start with the above as an initial integer approximation, and then proceed with a binary search, checking whether $m^e > c$ at each step. (There are most likely better algorithms for integral roots, but this should do the trick quite fast already).

  • Thank you! This is incredibly helpful and a great direction to investigate. Much appreciated. – BronzeOtter Nov 26 at 16:11
  • As mentioned in the other answer from @fgrieu, big integer are required, but python integer are big integer ;) – LeoDucas Nov 27 at 17:17

In the case where one has a small $e$ AND a small $m$, would it be correct to say that if $m<N^{1/e}$ then we can attack by calculating the $e$-th square of $m^{e}$?

Yes, in a textbook RSA context, where ciphertext $c$ for the small $m$ is computed as $c=m^e\bmod N$, that is $c=m^e$ if $m<N^{1/e}$. But in RSA as practiced, either $m$ is large and mostly random (RSA-KEM), or a padding step is used (RSAES-OAEP or RSAES-PKCS1-v1_5), so that won't work.

best way to approach such an attack practically?

We want to determine if the $e$-th root of $c$ is an integer, and in the affirmative calculate it, which will be $m$.

It is needed a tool that can compute exactly with large integers. Python, GP/Pari, Mathematica, GMP… have appropriate built-in types, Java comes with a BigInteger package, and it is possible to create one in any Turing-complete language. Some tools have built-in functions to check/compute exact $e^\text{th}$ root. For others an option is to obtain an approximation using floating point, then Newton-Raphson or the less efficient dichotomic search.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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