Twodimensional Montgomery ladders and ECDSA
From: D. J. Bernstein (djb_at_cr.yp.to)
Date: 10/24/05
 Next message: Joseph Ashwood: "Re: help ragarding licensing keys"
 Previous message: parwal.sandeep_at_gmail.com: "help ragarding licensing keys"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Mon, 24 Oct 2005 07:38:15 +0000 (UTC)
The current speed records for DiffieHellman key exchange, and
specifically for ellipticcurve point multiplication, use two ideas that
Montgomery introduced in 1987:
* You can easily compute x(iP+jP) given x(iP), x(jP), and x(iPjP),
where x(P) means the xcoordinate of point P. This is particularly
fast for curves of the form y^2 = x^3 + Cx^2 + x.
* Starting from P, you can reach nP for a bbit n with a sequence of
b double+add steps, where each addition iP+jP has iPjP = P. For
example, you can reach 51P using 2P,3P,4P,6P,7P,12P,13P,25P,26P.
Putting these ideas together you obtain x(nP) from x(P) at high speed.
Some side advantages: public keys are transmitted as just xcoordinates;
if the curve is chosen carefully then you don't have to spend any time
verifying keys; the computation is easily made immune to timing attacks.
See http://cr.yp.to/talks.html#2005.09.20 for more details.
Now, what happens if you want to compute x(mP+nQ), as required for
verification of ECDSA signatures?
One answer (by, e.g., Okeya and Sakurai) is to compute mP via x(mP),
compute nQ via x(nQ), and then add. Computing x(mP) and x(nQ) by
Montgomery's technique takes 2b xcoordinate double+add steps.
I've noticed that a different technique takes 2b xcoordinate additions
and only b xcoordinate doublings. Specifically, one can reach x(mP+nQ)
with a simple twodimensional addition chain that uses b double+add+add
steps, where each addition has difference P or Q or P+Q or PQ. Example:
P+Q, 2P, 2P+Q,
2P+2Q, 3P+Q, 3P+2Q,
4P+4Q, 5P+3Q, 5P+4Q,
9P+7Q, 9P+8Q, 10P+8Q,
18P+14Q, 18P+15Q, 19P+15Q,
36P+30Q, 37P+29Q, 37P+30Q,
73P+59Q, 74P+58Q, 74P+59Q.
Each line has three of the four pairs aP+bQ, (a+1)P+bQ, aP+(b+1)Q,
(a+1)P+(b+1)Q. The missing element of (a+{0,1},b+{0,1}) is always chosen
as either (even,odd) or (odd,even), where the choice can be described
recursively using the (A,B) for the next line:
* if (a+A,b+B) is (even,odd) then the choice is (odd,even);
* if (a+A,b+B) is (odd,even) then the choice is (even,odd);
* if (a+A,b+B) is (even,even) then the lines have the same choices;
* if (a+A,b+B) is (odd,odd) then the lines have opposite choices.
For smallC Montgomeryshape curves, xcoordinate addition (using affine
difference) takes 5 field operations, and xcoordinate doubling takes 4
field operations, so this twodimensional addition chain takes just 14
field operations per bit, quite possibly the state of the art in ECDSA
verification even if we don't require timingattack protection.
Is this a new observation?
D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago
 Next message: Joseph Ashwood: "Re: help ragarding licensing keys"
 Previous message: parwal.sandeep_at_gmail.com: "help ragarding licensing keys"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
