[curves] New curve25519/ed25519 library

[Peter Schwabe]

Mehdi Sotoodeh <mehdisotoodeh at gmail.com> wrote:

Dear Mehdi,

> I would like to introduce a remarkable implementation of x25519 and ed25519
> library. The sources are hosted at: https://github.com/msotoodeh/curve25519
> 
> The code is experimental but rather stable. It is compact, portable
> and uses simple design logic.  On the security front, it employs
> several measures for side-channel security.

I only took a quick look at the software, but two things immediately
caught my eye. 

The first aspect is that the Curve25519 implementation uses secretly
indexed memory access which is a possible source for timing attacks.
State-of-the-art Curve25519 implementations avoid this by using
constant-time conditional swaps.
Similar statements apply to the table lookup in the fixed-basepoint
scalar multiplication, but those would be much more expensive to
protect.

> But the most remarkable feature is speed. This library sets new speed
> records. It uses a new technique I call it FOLDING for achieving this goal.
> FOLDING chops the scalar multiplier into n pieces (or folds) and operates
> on the folds simultaneously reducing number of point operations by a factor
> of 4 or 8. For example, ed25519 signature takes 31 point doubling and 31
> point additions.

The second thing is: It's great to hear about new speed records!
Are you planning to support the SUPERCOP API and submit to eBATS so that
the software can be publicly benchmarked on a large bunch of computers?
My understanding is that the technique that you call folding is only
efficient for signing; the verification part needs a precomputation
which is just way too expensive: it needs 384 point doublings! You will
probably answer that the ed25519_Verify_Init needs to be done just once
for many verifications, but then a huge expanded public key is sitting
around in memory and if I'm not totally mistaken, a sliding-window
method would still be faster. 

Best regards,

Peter
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 173 bytes
Desc: Digital signature
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20150630/4553d1ea/attachment.sig>