2
$\begingroup$

I'm trying to understand the math outlined in this paper on a RSA signature forgery attack. I understand it except for one aspect of how the cube root (that makes the forged signature) is computed.

On page 8, it's shown that this expression (the forged block that needs to be cube-rooted): $\sqrt[3]{2^{3057} - N*2^{2072} + G}$

is supposed to be equivalent this one after its simplified: $2^{1019} - (N * 2^{34}/3)$

It's not clear to me how the $2^{34}$ was determined in the second expression. It looks like everything's being divided by 3, but since the exponent $2072$ doesn't divide perfectly by 3, something was done to it. Can anyone explain?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The paper explains how it got this number immediately after the expression you are quoting. See equations (7) and (8) and the surrounding text (continuing onto the top of the next page). $\endgroup$
    – D.W.
    Aug 21, 2013 at 2:40
  • $\begingroup$ It's still not clear to me; don't I need the $2^{34}$ value to compute (7) and (8) at all? $\endgroup$
    – hlh
    Aug 21, 2013 at 3:04
  • $\begingroup$ hlh, sorry, I don't understand your question. The paper explains why the answer is $2^{1019} - (N * 2^{34}/3)$. They've already given you this answer (magically) and are now explaining how you can verify that this answer is correct. Plug in $A=2^{1019}$, $B=N*2^{34}/3$ into (7), exactly as the paper tells you do, and then simplify, and then the paper tells you why the cube of $2^{1019} - (N * 2^{34}/3)$ is $2^{3057}-N*2^{2072}+G$. $\endgroup$
    – D.W.
    Aug 21, 2013 at 3:06
  • $\begingroup$ I'm sorry, is there a way I can re-phrase anything so it's clearer? I'm trying to adapt the math to a modulus of a different length and want to understand the generalization for how the cube root is computed. Either I'm missing something (likely) or it's not in the realm of the paper... $\endgroup$
    – hlh
    Aug 21, 2013 at 3:13

1 Answer 1

Reset to default
3
$\begingroup$

Look at it this way; consider the value of:

$(2^{1019} - N * 2^{34} / 3)^3$

Using the binomial expansion, we see that it equal to:

$(2^{1019})^3 - 3 * (2^{1019})^2 * N * 2^{34}/3 + 3 * 2^{1019} * (N * 2^{34} / 3)^2 - (N * 2^{34} / 3)^3$

or (simplifying):

$2^{3057} - N * 2^{2072} + G$

where $G = N^2/3 * 2^{1087} - N^3/27 * 2^{102} < 2^{2072}$ for the value of $N$ we are interested in.

And, so, because the cube of $2^{1019} - N * 2^{34} / 3$ is $2^{3057} - N * 2^{2072} + G$, that means the cube root of $2^{3057} - N * 2^{2072} + G$ is $2^{1019} - N * 2^{34} / 3$

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Sorry, but how does this show how $2^{34}$ was derived? $\endgroup$
    – orlp
    Aug 21, 2013 at 10:18
  • 1
    $\begingroup$ @nightcracker: well, they wanted to place at starting at bit position 2072 of the post-RSA value. Because of the second term of $(a-b)^3$ which is $-3a^2b$, then need to place $N/3$ at bit position $p$ which satisifies $2^{2072} = (2^{1019})^2 \times 2^{p}$ or $2072 = 2 \times 1019 + p$ or $p=34$ $\endgroup$
    – poncho
    Aug 21, 2013 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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