On 1/29/14, Mike Hamburg <[email protected]> wrote: > > On Jan 29, 2014, at 12:20 AM, Robert Ransom <[email protected]> wrote:
>> I don't think there's any real need to distinguish encoded points with >> a sign bit from those which do not have a meaningful sign bit, though. >> The party who generates a public key is likely to know which >> protocols it will be used in, and there isn't too much harm if someone >> else tries to use it in a protocol that its owner doesn't want to >> participate in. > > Right. I just meant that we'd have to spec at a protocol level, "this > protocol doesn't use the sign bit, so don't generate one or send it, and in > particular don't throw one into the hash at the end". If the sign bit were > free, we could just have a single "serializePoint" function, but it's not > free. So, fine. This really only matters for shared secrets, and in that case, it's probably better to always discard the sign bit. If a point is transmitted over the network, the recipient can just hash it as is. >> The bigger question is “Which Edwards curve?”. As long as the only >> Montgomery-form coordinate encoded is x, Montgomery curves are fairly >> well-defined given Montgomery A. But the Edwards form has a >> two-dimensional parameter space (a, d), and in many cases there are >> multiple reasonable choices of a. > > Good point. > >> I would choose a=-1 as the encoded form for every curve in every >> coordinate field in which -1 is a square, and a=1 otherwise. This is >> consistent with Ed25519; it makes safe, reasonably efficient >> implementations more convenient without adversely affecting more >> highly optimized implementations (e.g. implementations which use an >> a=-1 form of a curve specified with a=1 over a 3mod4 coordinate >> field); and it keeps the non-affine coordinates which arise when d/a >> is a square away from the point encoding/decoding operations. > > > In the 3 mod 4 cases, we're starting with an Edwards curve, and the > Montgomery curve is isomorphic or isogenous to it, at least in the 3 mod 4 > cases. So I guess we have to choose there, isomorphic or isogenous? It's > probably gotta be isomorphic, right? Do you know how point compression > would interact with the isogeny, or should I try to work it out? The > advantage of the isogenous ones is that d = (A+2)/4 so you can use the > well-known formulas, but there are obvious advantages to an isomorphism. I would prefer the isomorphism Ed(1, d) -> Mont(*, 4/d - 2), since the conversion is both conceptually and technically simpler and there is no performance cost to using that Montgomery curve in Montgomery form. > In the 5 mod 8 cases, it's the reverse. I don't especially care whether > it's +1 or -1 here. Talking with Watson and Trevor, we might end up cutting > all the 5 mod 8 cases except Curve25519, because they were generated under a > mistaken idea of how Elligator2 works, and they aren't particularly better > than the 3 mod 4 curves. In the mean time, I dunno, your suggestion of -1 > because that's how Ed25519 works is fine by me. My main problem with the ‘Brazil’ curves is that all of them except M-221 (even the E-* curves) have really *ugly* coordinate fields. They make the NSA fields look nice by comparison (and at least those would have the advantage of requiring less extra hardware within a TPM, as someone mentioned on one of the IETF lists). The fact that they're choosing new curves to have small-integer Montgomery parameter instead of small-integer Edwards parameter is a secondary, though significant, problem. Robert Ransom _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
