[curves] New curve25519/ed25519 library

[Gregory Maxwell]

On Tue, Jun 30, 2015 at 11:42 PM, Mehdi Sotoodeh
<mehdisotoodeh at gmail.com> wrote:
> Is this is good enough approach? Does it need to be updated time to time?
> Please note that I am a software engineer and relying on crypto experts like
> you to evaluate the security level and come up with recommendations.

When there is a leak it's very hard to say what defenses are "good
enough", especially not without analyzing the specifics of the
application. It's best to eliminate the leak.

>     >3) Using multiple tables (so the inner loop is double; add; add; add)
> lets you reduce the number of doubles without making the tables too wide.
>
> Can you elaborate on this? Based on the pre-calculations, it is
> double-add(P)-add(Q). Are you considering 8 vs 4 combs here?

Imagine splitting the number into two 128 bit numbers, and the upper
you use your table with its entries multiplied by 2^128. This lets you
halve the number of doublings while just doubling the table size...

Carried to its logical conclusion you can eliminate doubling entirely;
e.g. do a 256 bit scalar,point multiply with just 64 adds, zero
doubles, and a table of 1024 (or 512, if a subtractive form is used)
affine points.


As an example: we do this in libsecp256k1, along with the uniform
memory accesses:

https://github.com/bitcoin/secp256k1/blob/master/src/ecmult_gen_impl.h#L104