Computational Complexity

[Moumi]

Hey, rather than an issue with your code I had a question. You note that you're using Montgomery reduction to achieve a better performance. However, I can't seem to find what exact form of it you are using. Could you comment on this, in terms of multiplication, what is the computational complexity. Thus how many multiplications still take place?

Next, it seems that the signing procedure is a bit slower than verification for secp256k1. Based on how ecdsa works, one would expect that it would be the other way around. Could you comment on how this is achieved?

Thanks in advance!

[AntonKueltz]

Actually the code uses a Montgomery Ladder to do point multiplication in a constant time manner. So the question of how many multiplications take place doesn't really make sense since it is the point multiplication algorithm.

I would guess signature verification is slightly longer because it requires two point multiplications which, even using Shamir's Trick, will make it take a little longer than signing which only requires one point multiplication.

[Moumi]

Thanks for letting me know it uses a Montgomery Ladder, that is helpful. On the performance thing, it seems that signing is, on my machine, 0.0027 seconds while verification is 0,0023 seconds. Like you said, I'd expect verification to be slower due to the two point multiplications. However, it is faster. Any comments on why?

[AntonKueltz]

Ah yes, appears i misread your comment. My guess would be that the Montgomery ladder (used in signing to prevent branching on secret material) is slower than Shamirs Trick (which operates on all public values). You could try profiling the calls on your box to see where the bottlenecks are, the cProfile module can help with that.