constant-time extended GCD?
Wei Dai
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/.