]> git.codecow.com Git - Monocypher.git/commit
Tweaked EdDSA signature pre-computed table
authorLoup Vaillant <loup@loup-vaillant.fr>
Fri, 4 Dec 2020 22:21:02 +0000 (23:21 +0100)
committerLoup Vaillant <loup@loup-vaillant.fr>
Fri, 4 Dec 2020 23:15:44 +0000 (00:15 +0100)
commit76496b4cd286a493afdc2cc74b7ff5bb467dbff4
tree74a213816b96c7c005d1f97755b39acc093af9c1
parentfb0f4df38cb7ee029f8feacd2971173458d9ffcd
Tweaked EdDSA signature pre-computed table

Moved from a single 5-bit comb to a dual 4-bit comb.  The size of the
comb is unchanged, but we perform fewer operations.

Before:
- 50 doublings, 51 additions (101 operations)
- 51 16-way constant time lookups
After:
- 30 doublings, 62 additions (92 operations)
- 62 8-way constant time lookups

Note: I hoped for a 6% speedup, barely observed 3.5%. I suspect this is
because additions, even from pre-computed tables, cost a little more
than doublings.

Note: we could save an additional addition by assuming scalars modulo L
all fit in 252 bits.  They do not, but if we pick one at random, they
will in practice (with 2^-128 probability of being wrong, i.e. never).

This would work well in EdDSA, where the scalar is a hash of the private
key.  Finding a private key that makes the scalar overflow 252 bits is
about as hard as breaking a 128-bit key, which we can safely assume will
never happen by accident.

However, this scalar multiplication is also used in the dirty public key
generation, which we use to create hidden X25519 keys with Elligator
(from Edwards, because it's twice as fast as the Montgomery ladder).
Here, users provide the scalar directly. Overflowing 252 bits *can*
happen by accident, if users shoot themselves in the foot with a
non-random scalar.

The risk is small, but a measly 1% performance is not worth leaving
ourselves open to subtle corner cases like that.
src/monocypher.c