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

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 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!

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 '18 at 16:11
• As mentioned in the other answer from @fgrieu, big integer are required, but python integer are big integer ;) – LeoDucas Nov 27 '18 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 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. 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.