curved25519_scalarmult primitive should be exposed

[TomMD]

I see curved25519_scalarmult_basepoint in order to generate public keys but the library is missing curved25519_scalarmult.

[floodyberry]

Montgomery ladder is faster than Edwards form for variable point multiplication. That said, I don't know how much faster, and if the gap would be narrow enough to include curved25519_scalarmult for convenience. I could give it a shot and see

[TomMD]

Well I have no real issues with using curve25519-donna as well, thanks to your care in avoiding symbol collisions. I didn't realize this request was non-trivial from either an implementation of design decision stand-point.

[forthy42]

Am Samstag, 11. April 2015, 19:49:50 schrieb Andrew Moon:

Montgomery ladder is faster than Edwards form for variable point multiplication. That said, I don't know how much faster, and if the gap would be narrow enough to include curved25519_scalarmult for convenience. I could give it a shot and see

I did some benchmarks comparing djbs curve25519 with ed25519_scalarmult. I added a constant-time variant in my "forthy42/ed25519-donna" fork of ed25519- donna, and it's 30% faster than djbs curve25519 due to various higher-level optimizations (base-n scalar product with n/2 precomputed table entries instead of always base-2). This optimization is possible due to the regularity of Edwards curves (no special casing of neutral element, no special casing of doubling).

Therefore I use Edward curves for Diffie-Hellman-Exchange; but it requires adding a constant-time single-argument scalar multiplication (instead of the variable time two-argument scalar multiplication provided by ed25519-donna).
This doesn't compute the same shared secret as using curve25519, so if you want to be compatible with a protocol that uses curve25519 for DHE, you can't use this. But if you don't need to, the Edwards curve DHE is just as secure as the Montgomery ladder curve DHE.

Beware that djb, Peter Schwabe and Tanja Lange want to write up recommendations how to securely use the same key for DHE and signing; until they do so, it might be better to use two keys, one for DHE, one for signing.
With ephemeral key exchange, that's easy.

You can find the function in

https://github.com/forthy42/ed25519-donna/blob/master/ed25519-donna-impl-base.h

as ge25519_scalarmult

You can't easily merge my fork, because I ripped out the high-level parts with hash and signature; I want to be able to replace the hashing function, so I don't include the hashing into the library - which means the library has to export primitives, and the top-level is done outside. I also added an automake-based build system.

Bernd Paysan "If you want it done right, you have to do it yourself" net2o ID: kQusJzA;7_?t=uy@X}1GWr!+0qqpCn176t4(dQ http://bernd-paysan.de/

[floodyberry]

Were you measuring ge25519_scalarmult on its own, or with ge25519_pack if you were sending x&y, or with ge25519_pack/unpack if only sending x?

You can also use curve25519 keys, but it requires the equivalent of ge25519_pack and ge25519_unpack.

[forthy42]

Am Dienstag, 14. April 2015, 20:49:27 schrieb Andrew Moon:

Were you measuring ge25519_scalarmult on its own, or with ge25519_pack if you were sending x&y, or with ge25519_pack/unpack if only sending x?

Full DHE with sending only x, i.e. measuring with unpack+pack (for the shared secret).

Since unpack in ed25519-donna negates, a bit toggle is necessary either before unpacking or after packing (the MSB is the sign of y), but that's a cheap operation.

You can also use curve25519 keys, but it requires the equivalent of ge25519_pack and ge25519_unpack.

Bernd Paysan "If you want it done right, you have to do it yourself" net2o ID: kQusJzA;7_?t=uy@X}1GWr!+0qqpCn176t4(dQ http://bernd-paysan.de/

[forthy42]

Am Dienstag, 14. April 2015, 20:49:27 schrieb Andrew Moon:

Were you measuring ge25519_scalarmult on its own, or with ge25519_pack if you were sending x&y, or with ge25519_pack/unpack if only sending x?

You can also use curve25519 keys, but it requires the equivalent of ge25519_pack and ge25519_unpack.

I ran the benchmarks again, to give an illustration about the performance. I use curve25519-donna as curve25519 implementation and your ed25519-donna as ed25519 implementation. x64 Linux, 3.4GHz Core i7, gcc-4.7 (which I found is better on crypto than more recent GCCs):

ed25519 basepoint mult 17�s, ed25519 scalarproduct dh constant time 58�s, ed25519 signature 26�s ed25519 verify 60�s curve25519 scalarproduct dh 80�s.

All Diffie Hellman exchanges include unpack+pack. Signature and Verify include a short hash, but that's much, much faster than the elliptic curve.

So the algorithmic improvements possible with ed25519 take 27.5% less time for Diffie Hellman exchange.

I haven't tested your curve25519 basepoint multiplication.

My suggestion is that new protocols should use ed25519 both forth signing and Diffie Hellman; especially ephemeral key exchange is a lot cheaper with the very fast basepoint mult to generate the ephemeral key.

What could be done to improve speed for Diffie Hellman exchange with a constant key (non-ephemeral key-exchange) is a table generation similar to the basepoint multiplication.

Bernd Paysan "If you want it done right, you have to do it yourself" net2o ID: kQusJzA;7_?t=uy@X}1GWr!+0qqpCn176t4(dQ http://bernd-paysan.de/