2
$\begingroup$

I am in high school and I am writing a paper on RSA. I want to show that low values of the public key exponent can make it easy to 'invert' the function so that the encrypted message can be recovered. How is this done? I have tried to read the Handbook of Applied Cryptography but it's not making sense...

Would this be inversion: Taking cipher text, and continuously adding the modulus, then taking the eth root of the sum. If the result is an integer, then it is the plaintext message.

$\endgroup$
  • $\begingroup$ PS. My paper is just covering plain old RSA, no padding or anything :) $\endgroup$ – EVELYN Oct 9 '15 at 2:32
  • $\begingroup$ I suppose it should be the private key and not the public one. $\endgroup$ – user27950 Oct 9 '15 at 4:54
  • $\begingroup$ RSA without padding is vulnerable, and should not be presented in introductory material without mention that it must not be used for serious purposes (except for random messages almost as wide as the modulus). Combined with low value of the public exponent, RSA without padding is even more vulnerable, but usually not because it is easier to invert the public function (the exception to that being in the end of poncho's answer) $\endgroup$ – fgrieu Oct 9 '15 at 13:09
4
$\begingroup$

I want to show that low values of the public key exponent can make it easy to 'invert' the function so that the encrypted message can be recovered.

That is not known to be true; as long as the modulus is large enough to make factorization infeasible, there is no known way to compute e-th roots in general.

Now, if the plaintext $p$ is small enough that $p^e < N$, then it is easy to recover $p$ (just take the e-th root over the integers, which is an easy problem). That's as close as we know to the result you're trying to get.

Would this be inversion: Taking cipher text, and continuously adding the modulus, then taking the eth root of the sum. If the result is an integer, then it is the plaintext message.

If $N$ is small enough to make work in a practical amount of time, then $N$ is small enough to factor.

$\endgroup$
  • $\begingroup$ I'm reading the last paragraph of the question as a simple extension of the e-th root attack, working when $p^e<k\cdot N$ for moderate $k$. I'm sure $k\approx2^{20}$ is feasible. I wish I knew how large $k$ needs to be in order to avoid a more sophisticated attack. This answer to a significantly different question does not tell. $\endgroup$ – fgrieu Oct 9 '15 at 16:26
  • $\begingroup$ Hello, could you please explain k? I have not encountered a constant or variable k in my readings. $\endgroup$ – EVELYN Oct 10 '15 at 9:57
  • $\begingroup$ @EVELYN : $\:$ k is a positive integer, and in this case that's all it is. $\;\;\;\;$ $\endgroup$ – user991 Oct 11 '15 at 8:39
0
$\begingroup$

While Poncho's answer is fully valid I'll hereby extend the part on the proposed idea being inferior to factoring.

I want to show that low values of the public key exponent can make it easy to 'invert' the function so that the encrypted message can be recovered.

As poncho said this is only feasible if the message's length is smaller than the modulus length divided by e, i.e. when no modular reduction takes place.

Would this be inversion: Taking cipher text, and continuously adding the modulus, then taking the eth root of the sum. If the result is an integer, then it is the plaintext message.

The problem of this approach is the run-time. For this approach to be viable you need to beat the General Number Field Sieve (GNFS) in terms of performance at least for some messages. So let's assume the best case scenario, where your algorithm starts operating: if $||m||\geq ||N||/e$, so for example for a 1025-bit message for 3072-bit RSA with $e=3$. To be beat the GNFS, you need to be able to carry out the attack on less than $2^{256}$ operations for this scenario. Clearly, the ciphertext will have length $||c||=3072$ bits with high probability and the term you're looking for $m^e$ has $1025*3=3075$ bits. So you have to test every single (or at least half) of all the multiples of $N$ in the 3075 bit range, which are $2^3=8$, which is indeed feasible. But which area of messages can you break using this technique? You can break any message for which the above equation holds and for which $(||m||-||N||/e)*e<2^{60}$, meaning for $e=3$ you "can break 20 more bits" (f.ex. 1025-1045). If you consider your technique "good" if it stays below factoring, you can even extend that to 80 bits. But in practice this kind of attack is already countered by randomized padding.

$\endgroup$
  • $\begingroup$ The approach in the question remains feasible when the message's length is slightly higher than the modulus length divided by $e$, at least up to $20/e$ extra bits, with modest means. I do not know what the upper limit is; this answer to a significantly different question does not tell. $\endgroup$ – fgrieu Oct 9 '15 at 16: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.