Best way to attack a small e and small m RSA problem?

Question

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!

Answer 1

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).

Answer 2

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.