[tor-dev] SHA-3 isn't looking so hot to me

[Watson Ladd]

On Fri, Nov 4, 2011 at 9:24 AM, Ian Goldberg <iang at 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 at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin