On 2/9/15, Mike Hamburg <m...@shiftleft.org> wrote: > > On 2/7/2015 4:45 PM, Michael Hamburg wrote: >>> On Feb 7, 2015, at 4:30 PM, Brian Warner <war...@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
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)
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves