Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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