In Discrete Log based Cryptography, one of the core operations that one, has to perform is modulo exponentiation. There are many algorithms to choose from, especially, when considering my point of interest "scalar multiplication" of a point (generator) of an Elliptic Curve. The most fundamental algorithm is the double and add method, that runs in logarithmic time. But since, the cost of point doubling is different, from the cost of point addition, branching based on secret bits will cause, the secret bit to be leaked to the adversary. As a mitigation to this, we could do a sort of, dummy addition every iteration and hence the "double and add always" algorithm ! This will camouflage the time difference, I guess. I realize, that there are other algorithms like Montgomery Ladder but Wikipedia says that there exists FLUSH+RELOAD attack on an OpenSSL implementation that uses it. But are there better algorithms ? Will there be performance/ security benefits if we migrate to a different coordinate system?
I'm asking this, because I coded an Elliptic Curve implementation from scratch using my custom multiprecision library written in C
as a learning project. But in my library, I use extended euclidean algorithm for calculating modulo inverses (for performance sake) in $F_{p}$. And also, my multiprecision division algorithm is not constant time, it runs in logarithmic time depending on the dividend bit length. These are some bottlenecks that I think is difficult to overcome as far as multiprecision is concerned ! Still my overall working implementation is no way as fast / secure as OpenSSL or other amazing libraries out there and it is not intended to be! But, I would love to know more about secure & fast implementation!
if/else
$S$ is the true value for if and $A$ and $B$ theif
and theelse
cases. $\endgroup$ – kelalaka Sep 28 '20 at 12:53