1
$\begingroup$

I tried to collect some benchmarks on NIST elliptic curves using charm library. The charm library is just a wrapper over OPENSSL. I experimented with prime192v1 (P-192), secp224r1 (P-224), prime256v1 (P-256), secp384r1 (P-384) and secp521r1 (P-521) curves. I calculated the time required to

(1) sample one group element,

(2) multiply 2 random group elements and

(3) exponentiate a group element with a random value in range [1, order of group].

Here's my code.

from charm.toolbox.ecgroup import ECGroup, G, ZR
from charm.toolbox.eccurve import prime192v1, secp224r1, prime256v1, secp384r1, secp521r1
from time import time
group = ECGroup(secp521r1)
count = 10000

g = []
a = []
t = time()
for i in range(count):
    g.append(group.random(G))
print("Random in G ", time()- t)

for i in range(count):
    a.append(group.random(ZR))
t = time()
for i in range(count):
    g[i]**a[i]
print("Exp in G ", time() - t)

t = time()
for i in range(count):
    g[i]*g[i-1]
print("Mul in G ", time() - t)

Here are the results. The benchmarks have many anamolies that I could not explain. For P-224 curve, it took unreasonably long time for sampling random element. For P-224 curve, if it takes 2.27microseconds for multiplication, then it should take at least 224*2.27microseconds (roughly 0.5ms) for exponentiation. But exponentiation is much faster. Exponentiation is unreasonably faster even for P-256 and P-521 curves as well. Can anyone please explain why this is the case?

enter image description here

$\endgroup$
  • 1
    $\begingroup$ One reason is probably that the P-256 implementation has undergone a lot of optimization to be fast for exponentiation... $\endgroup$ – SEJPM May 30 at 13:30
  • $\begingroup$ I do note that your code does access an array element out of range in the first iteration of g[i]*g[i-1]; that looks unlikely to end up taking a considerable amount of additional computation time, but it's not impossible (as an additional hundred microseconds would account for the anomaly...) $\endgroup$ – poncho May 30 at 13:43
3
$\begingroup$

Here is what's likely going on:

  • Charm represents Elliptic Curve points in affine coordinates, that is, explicit (x, y) values

  • When doing a single point addition, OpenSSL adds the two points (internally coming up with a point in projective coordinates) and then converts them back into affine coordinates. Then final conversion involves a modular inverse operation, and so is moderately expensive (more expensive than all the other operations combined).

  • When doing an point multiplication, OpenSSL takes the point, and does a series of point additions/doublings, keeping the point in projective coordinates. Then, at the end, it converts the point back into affine coordinates (which involves the modular inverse). However, you end up doing a single modular inverse, even though a number of point additions/doublings were done.

Hence, because the point multiplication avoids the intermediate modular inverses, it runs faster than expected.

$\endgroup$
  • $\begingroup$ Nice answer. I didn't understand the difference between affine coordinates and projective coordinates. If you don't mind, can you please explain that. $\endgroup$ – satya May 30 at 14:17
  • $\begingroup$ Exponentiations for P-224, P-256, P-521 are anamolous, and your answer explains the reason for it. Do you have any reasons why exponentiations for P-192, P-384 are not anamolous? What about sampling a random point on P-224 curve? $\endgroup$ – satya May 30 at 14:23
  • $\begingroup$ @satya: I have no idea what algorithm they're using to select a random point. One would expect the simple expedient of 'select a random x coordinate, perform the squareroot of x^3+ax+b and see if the coordinate is valid' would go considerably faster than what they have listed... $\endgroup$ – poncho May 30 at 16:11
  • $\begingroup$ @satya: As for P-192, P-384, maybe they (for whatever reason) keep those points in affine coordinates? $\endgroup$ – poncho May 30 at 16:11
  • $\begingroup$ OpenSSL also has specialized (and faster) C code for P-224 P-256 P-521, and on some (common) platforms further-optimized assembler for P-256. See the source e.g. github.com/openssl/openssl/tree/master/crypto/ec . $\endgroup$ – dave_thompson_085 May 31 at 0:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.