2
$\begingroup$

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!

| improve this question | |
$\endgroup$
  • 2
    $\begingroup$ Which curve are we talking about? Montgomery ladder has a natural side-channel resistance You should give more information about your curve. Also, one needs a code like $Q = (A * S) + (B * S')$. This removes all infomation on the if/else $S$ is the true value for if and $A$ and $B$ the if and the else cases. $\endgroup$ – kelalaka Sep 28 at 12:53
  • 2
    $\begingroup$ You might want to have a look at BearSSL's commented implementation $\endgroup$ – SEJPM♦ Sep 28 at 13:21
  • 1
    $\begingroup$ I wrote a simple answer for a glimpse of if with python for square-and-multiple. Of course, one should not use it. Even when using the C language don't relay on the compiler. You need to check the result or apply a special desing. There was an answer from @fgrieu about it. $\endgroup$ – kelalaka Sep 28 at 15:19
  • 1
    $\begingroup$ Could you give a link of your implementation? $\endgroup$ – kelalaka Sep 28 at 18:01
  • 1
    $\begingroup$ If the applicable switch to Montgomery representation of the curve? $\endgroup$ – kelalaka Sep 28 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.