curved25519_scalarmult primitive should be exposed
Closed this issue · 6 comments
I see curved25519_scalarmult_basepoint in order to generate public keys but the library is missing curved25519_scalarmult.
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
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.
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!+0qqp_Cn176t4(dQ_
http://bernd-paysan.de/
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.
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!+0qqp_Cn176t4(dQ_
http://bernd-paysan.de/
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!+0qqp_Cn176t4(dQ_
http://bernd-paysan.de/