search

miracl / MIRACL

MIRACL Cryptographic SDK: Multiprecision Integer and Rational Arithmetic Cryptographic Library is a C software library that is widely regarded by developers as the gold standard open source SDK for elliptic curve cryptography (ECC).
https://miracl.com
654 stars 242 forks source link

Why does "epoint_set()" with point compression take longer time for secp224 than secp256? #53

Closed k3coby closed 7 years ago

k3coby commented 7 years ago

I’m trying to do a lot of point calculations on secp192, 224, 256, 384 and 521 using this library. However, when I tried to measure running times, I noticed that “epoint_set ()” with point compression enabled took much longer in secp224 than in secp256. It's weird because the implementation remained unchanged for different curves and other curves (160, 192, 384, 521) worked fine. Can anyone help me figure out why? Is it possible that there's some special optimizations for secp256 in this library? Thank you so much!

screen shot 2017-10-03 at 15 19 35

mcarrickscott commented 7 years ago

Sure. It actually depends on what the remainder is when the prime p is divided by 8.

Obviously (since the prime is odd), the remainder will be 1, 3, 5 or 7

Now to set a point on the curve y*2=x^3+Ax+B, we generate x, and then calculate y=sqrt(x^3+Ax+B), where sqrt() is the square root modulo p.

Its the calculation of this square root modulo p which takes time. If the remainder is 3 or 7, its fast. If its 5 its a bit slower. Unfortunately if its 1, its very much slower.

And for secp224 the prime p=2^224-2^96+1, which leaves a remainder of 1 when divided by 8. In this case the best modular square rooting algorithm is very slow.

Which explains what you have observed.!

Mike

On Tue, Oct 3, 2017 at 8:23 PM, k3coby notifications@github.com wrote:

I’m trying to do a lot of point calculations on secp192, 224, 256, 384 and 521 using this library. However, when I tried to measure running times, I noticed that “epoint_set ()” with point compression enabled took much longer in secp224 than in secp256. It's weird because the implementation remained unchanged for different curves and other curves (160, 192, 384, 521) worked fine. Can anyone help me figure out why? Is it possible that there's some special optimizations for secp256 in this library? Thank you so much!

[image: screen shot 2017-10-03 at 15 19 35] https://user-images.githubusercontent.com/8734578/31144305-577c8c92-a84e-11e7-9835-fc4b810ae123.png

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/miracl/MIRACL/issues/53, or mute the thread https://github.com/notifications/unsubscribe-auth/ACm8jj-w0sFq1FItI8gJWIcAnpoH2Nq5ks5soomlgaJpZM4Pso64 .

k3coby commented 7 years ago

I see what you mean. When p is an odd prime and p = -1 mod 4, there's a direct way to calculate the square root modulo p, based on "quadratic reciprocity". However, if p = 1 mod 4, we have to use other algorithms to find that square root, which is much slower. It does make sense.

Thanks, Mike. I really appreciate your help!

Coby