On 1/21/15, Trevor Perrin <[email protected]> wrote: > On Wed, Jan 21, 2015 at 3:07 PM, Robert Ransom <[email protected]> > wrote: >> On 1/21/15, Trevor Perrin <[email protected]> wrote: >> >>> C) Full-format keys everywhere >>> All public keys include the sign bit, so this is a true "unified >>> format". [...] Montgomery-ladder-only implementation will require >>> an extra inversion, so key generation would be slowed by ~10%. >> >> It's not an extra inversion -- remember that inversions can easily be >> batched using 'Montgomery's trick'. > > Good point, and Jivsov also described this [1]. > > So the Montgomery ladder function could be modified to recover the > Edwards x sign bit at very low cost.
Having to implement the formulas to recover a second coordinate is not a 'very low' cost. > Would you prefer this for a unified format, instead of using a > single-coordinate format with the sign bit implied as zero (Jivsov) or > encoded into signatures (your idea)? If Mike Hamburg's single-coordinate point formats are ruled out for whatever reason (backwards compatibility with an existing system or existing keypairs, incompatibility of the sgn(y)/sqrt(x) format with 5mod8 fields, etc.), the best point format depends on the system in which it will be used. Since TextSecure had already deployed Curve25519 ECDH and its users had already published public keys without the sign bit, the choice was between adjusting each existing private key (as Jivsov suggested, but done every time the private key is used for signing) and transmitting the sign bit in some location other than the existing public-key strings (either in each signature, where there is room for it, or in a copy of the public key which accompanies the signature). Tor provides two other examples of how to choose a point format well: * Each Tor relay currently publishes a medium-term Curve25519 ECDH public key in the 'ntor-onion-key' field of its relay descriptor. If Tor ever switches to a new circuit-extension protocol which relies on the sign bit of a Curve25519 public key, the simplest way to transmit that sign bit is for each relay which supports that new protocol to begin including the sign bit of its key in the high bit of that same field. There would be no disadvantage to making relay implementations which include that high bit distinguishable from others (since the protocol would identify those relays in other ways), and there is no need to support use of an ECDH public key published by an old implementation with the new protocol. * Tor's future hidden service protocol will need to contain enough of an ECC public key in each HS address that a client can perform a scalar multiplication on that public key; accordingly, it must at least contain something from which a Montgomery-form x coordinate can be computed. Each HS descriptor must contain a full blinded public key sufficient to verify a signature, as well as a signature of the descriptor. For Curve25519, I suggested using the Montgomery-form x coordinate *only* as the HS address, since (a) that coordinate can be represented in only 51 base32 characters, and including another bit in the address would have increased that to 52 characters; (b) there is existing software to perform scalar multiplication on a Montgomery-form x coordinate, much of which is faster than anything I could have written for the purpose; and (c) the HS address, and the blinded address sent to the server in order to request the HS's current descriptor, only need to be sufficient to recognize the HS's full blinded public key. (My advice was ignored.) I hope that Mike Hamburg's new point format will eliminate the need for this level of careful design, at least for new systems. Robert Ransom _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
