[curves] PAKE questions

[Robert Ransom]

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)