On Fri, Nov 4, 2011 at 9:24 AM, Ian Goldberg iang@cs.uwaterloo.ca wrote:
On Fri, Nov 04, 2011 at 01:01:09PM +0000, Robert Ransom wrote:
I have also seen parameters for an Edwards curve equivalent to Curve25519; we will need the Edwards-curve parameters in order to implement point addition efficiently in constant time for our EC signature scheme.
Hmm? curve25519 _is_ an Edwards curve (that's why it has that slightly annoying non-prime order), and djb's implementation, at least, is supposed to be constant-time.
Dear all,
curve25519 is rationally equivalent to ed25519. Point addition isn't defined for curve25519 because public keys do not encode sign, because they are only the x coordinate. This is to take advantage of the special form y^2=x^3+a_2x^2+x. Until recently this was the fastest point exponentiation available, at the cost of making addition impossible.
ed25519 supports point addition, and point compression without patents. This is because Edwards curves have never been discussed in Certicom patents. ed25519 is also faster then curve25519, due to new algorithms. In the future DJB has indicated he will have curve25519 convert into Edwards form for calculation. But signing requires ed25519 be used because addition is not defined on packed curve25519 keys.
P-256 sadly does not support point compression without infringing on patents. So keys will have to be 64 bytes long.
Edwards curves always exist over closures. The problem is that they only exist when the order is divisible by 4. Twisted Edward curves have points of order 2. P-256 could only be put into Edwards form with extension fields, and extension fields are slow.
If we go with curve25519 we should not implement it ourselves. DJB has written an implementation that is quite nice to use in the form of NaCL. Signing is implemented along with batch signature verification (not in NaCL yet, but written). NaCL is also a lot nicer to use then OpenSSL, and is very fast (and ensures it always goes the fastest).
Sincerely, Watson Ladd
- Ian _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev