259 views

Skip to first unread message

May 5, 2009, 6:25:15 PM5/5/09

to crypto-op...@googlegroups.com

I've been doing an x86/SSE2 implementation of curve25519 using ideas similar

to the ones in "Fast elliptic-curve cryptography on the Cell Broadband

Engine" (http://www.cryptojedi.org/papers/celldh-20090331.pdf).

(It currently takes less than 260,000 cycles on Core 2 32-bit mode for a

scalar multiplication using Montgomery form, not counting the final modular

division.)

to the ones in "Fast elliptic-curve cryptography on the Cell Broadband

Engine" (http://www.cryptojedi.org/papers/celldh-20090331.pdf).

(It currently takes less than 260,000 cycles on Core 2 32-bit mode for a

scalar multiplication using Montgomery form, not counting the final modular

division.)

The modular division is posing a bit of a problem. Existing curve25519

implementations that I've seen do modular inverses as a^(p-2) mod p, which

takes O(n^3) time and can't be parallelized easily.

So, I'm thinking about implementing a potentially faster constant-time (i.e.

resistant to side-channel analysis)

algorithm for modular inverse, based on the algorithm and worst-case

analysis in "An Analysis of Lehmer's Euclidean GCD Algorithm"

(http://www.csie.nuk.edu.tw/~cychen/gcd/An%20analysis%20of%20Lehmer%27s%20Euclidean%20GCD%20algorithm.pdf).

Does anyone know of an existing constant-time modular inverse

implementation, or other ideas for doing this? Converting the

left-shift binary extended GCD algorithm to constant time seems much easier,

but I'd like something a bit faster, if possible. The only research or

discussion of this topic I've been able to find is this Usenet thread, which

didn't get very far:

http://groups.google.com/group/sci.crypt/browse_thread/thread/214668f23815b247/.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu