[curves] PAKE questions
Robert Ransom
rransom.8774 at gmail.com
Mon Feb 9 02:35:18 PST 2015
On 2/9/15, Mike Hamburg <mike at shiftleft.org> wrote:
>
> On 2/7/2015 4:45 PM, Michael Hamburg wrote:
>>> On Feb 7, 2015, at 4:30 PM, Brian Warner <warner at lothar.com> wrote:
>>>
>>> On 2/7/15 2:21 PM, Michael Hamburg wrote:
>>>> *Shameless plug*:
>>>> If you’d like, I can get Decaf up and running on TwistEd25519 in
>>>> Python. Decaf divides the cofactor by 4, and also conveniently
>>>> implements a hash to the curve.
>>> That'd be fun :).
>> OK, I’ll see what I can do.
>>
> Actually this will take a while. I'm pretty busy this week, but I was
> going to just cut and paste the code with different constants. I forgot
> something though: the twist of Curve25519 is a *twisted* Montgomery
> curve, and over a 1-mod-4 field that's actually a different thing (I
> think? Other EC folks please correct me if I'm wrong). The strategy
> still works but a bunch of the formulas need adjustment.
Curve25519 is isomorphic to an Edwards curve with a=1, d non-square;
therefore, its non-trivial quadratic twist is isomorphic to the
Edwards curve with a'=1, d'=1/d. That's enough to apply the Decaf
formulas as-is, as long as you don't care about having large
constants. (I've also worked out the details, including the twist map
(defined over the quadratic-extension field), for a != 1; see attached
for my notes. Though I haven't tested the formulas properly yet.)
But I would still recommend Curve1174, so that Montgomery-ladder
implementations can't plausibly leak the least significant bit of
scalars. (I don't want any system's security to rely on people adding
an explicit check for zero outputs with non-zero inputs.)
Robert Ransom
-------------- next part --------------
Ed(a, d) := (a x^2 + y^2 = 1 + d x^2 y^2)
Given a, d with d/a non-square, find d' and non-trivial quadratic
twist map Ed(a, d) -> Ed(a, d')
Maps from twisted-20080313:
f: Ed(a, d) -> Ed(1, d/a) = (x, y) |-> (x/sqrt(a), y)
g: Ed(a, d) -> Ed(d, a) = (x, y) |-> (x, 1/y)
Ed(a, d) -f> Ed(1, d/a) -g> Ed(d/a, 1) -f> Ed(1, a/d) = Ed(1, (a^2/d)/a)
-finv> Ed(a, a^2/d)
d' := a^2/d
Ed(a, d) -f> Ed(1, d/a) -g> Ed(d/a, 1)
(x, y) |-> (x/sqrt(a), y) |-> (x/sqrt(a), 1/y)
Ed(d/a, 1) -f> Ed(1, a/d) = Ed(1, (a^2/d)/a)
(x/sqrt(a), 1/y) |-> (x/(sqrt(a)*sqrt(d/a)), 1/y)
Ed(1, a/d) = Ed(1, (a^2/d)/a) -finv> Ed(a, a^2/d) = Ed(a, d')
(x/(sqrt(a)*sqrt(d/a)), 1/y) |----> (x/sqrt(d/a), 1/y)
More information about the Curves
mailing list