# Understanding the "cube-root math" behind an RSA signature forgery

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{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?

• 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).
– D.W.
Aug 21 '13 at 2:40
• It's still not clear to me; don't I need the $2^{34}$ value to compute (7) and (8) at all?
– hlh
Aug 21 '13 at 3:04
• 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$.
– D.W.
Aug 21 '13 at 3:06
• 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...
– hlh
Aug 21 '13 at 3:13

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$

• Sorry, but how does this show how $2^{34}$ was derived?
– orlp
Aug 21 '13 at 10:18
• @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$ Aug 21 '13 at 11:38