# NIST elliptic curves behaving anamolous in OPENSSL benchmark

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?

• One reason is probably that the P-256 implementation has undergone a lot of optimization to be fast for exponentiation... – SEJPM May 30 at 13:30
• 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...) – poncho May 30 at 13:43

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.

• Nice answer. I didn't understand the difference between affine coordinates and projective coordinates. If you don't mind, can you please explain that. – satya May 30 at 14:17
• 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? – satya May 30 at 14:23
• @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... – poncho May 30 at 16:11
• @satya: As for P-192, P-384, maybe they (for whatever reason) keep those points in affine coordinates? – poncho May 30 at 16:11
• 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 . – dave_thompson_085 May 31 at 0:01