search

dalek-cryptography / curve25519-dalek

A pure-Rust implementation of group operations on Ristretto and Curve25519
Other
894 stars 462 forks source link

X25519 functions #47

Closed mcginty closed 7 years ago

mcginty commented 7 years ago

It would be great to have this library (or possibly a x25519-dalek similar to ed25519-dalek, to keep this one low-level focused) provide the higher-level DH functions curve25519() and curve25519_base() functions found in donna, so people like myself don't find unique and beautiful ways to royally fudge up the scalar multiplication on their own.

burdges commented 7 years ago

If I understand, there is no Montgomery ladder implementation here yet. You could implement x25519 with this library, but the Edwards multiplication here will take at least twice as long, and the conversion to/from Montgomery form will take time too, and not everything is constant time, so they do not plan to do it that way.

isislovecruft commented 7 years ago

Hi @mcginty!

Sorry this took so long to get to, but I hacked on it a bit last weekend and wrote a montgomery ladder in my feature/montgomery-arithmetic branch.

I've also made x25519-dalek which uses the branch (so not published as a crate yet). x25519-dalek passes the testvectors in RFC7748. However, I haven't done anything to optimise it yet; in particular, I estimate we could save about 30-40% if the internal steps to the Montgomery ladder, differential_add() and differential_double() are combined into one another.

All of this is a clean room implementation from RFC7748, Costello and Smith's "Montgomery curves and their arithmetic", and Montgomery's original "Speeding the Pollard and elliptic curve methods of factorization".

isislovecruft commented 7 years ago

The Montgomery arithmetic in #74 was merged, and I'll be pushing the x25519-dalek crate to crates.io later this evening. I still haven't optimised it, but it works. Anyone should feel free to open a ticket for combining differential_add and differetial_double and start working on it.

mcginty commented 7 years ago

@isislovecruft sehr fantastisch 💃 Sorry right back for taking so long to respond to this - just moved back to the bay temporarily and took a convenient coding break in the process.

I'm in the middle of reading the papers you referenced, and will create a dalek branch in snow!