NIST elliptic curves behaving anamolous in OPENSSL benchmark

Question

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?

Answer 1

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.