Ask Your Question
1

Why is exponentiation of points on elliptic curve so fast?

asked 2019-05-30 05:50:46 +0200

panther gravatar image

updated 2019-06-20 13:09:58 +0200

FrédéricC gravatar image

I am working on elliptic curves in sagemath. I was trying to collect benchmarks for group operation and exponentiation of points on NIST P-256 elliptic curve. When I tried to perform a group operation on 2 points on the curve, it takes roughly 2 micro seconds. When I tried to perform exponentiation on a point in elliptic curve with a random exponent, it takes only 3 micro seconds. How is this even possible? Since I am exponentiating with a 256 bit value, this should at least take time required for 256 group operations, which is more than 1ms. I am worried if my code is wrong!

p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369 
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b 
F = GF(p) 
E = EllipticCurve(F, [-3,b]) 
runs = 10000 
G = E.abelian_group()

F2 = GF(order) 
exponent = [F2.random_element() for i in range(runs)]

t1 = time() 
for i in range(runs):   
      e = Integer(exponent[i])*e2[i] 
t2 = time() 
print  "Time per operation = ", (t2 - t1)/runs , " seconds"

e1 = [G.random_element() for i in range(runs)] 
e2 = [G.random_element() for i in range(runs)] 
t1 = time() 
for i in range(runs):   
         e = e1[i]+e2[i] 
t2 = time() 
print  "Time per operation = ", (t2 - t1)/runs , " seconds"
edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
0

answered 2019-05-30 08:00:08 +0200

ortollj gravatar image

updated 2019-05-30 08:20:26 +0200

Hi

maybe there exist cells where variables are declared elsewhere in your notebook. because I have to modify slightly your code !. anyway now the time is about 3 or 4 seconds for my PC.[edited I misplaced the first t1 ;-) , but maybe what I did it's not what you wanted to evaluate ?]

import time
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 
order = 115792089210356248762697446949407573529996955224135760342422259061068512044369 
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b 
F = GF(p) 
E = EllipticCurve(F, [-3,b]) 
runs = 10000 
G = E.abelian_group()

F2 = GF(order) 
exponent = [F2.random_element() for i in range(runs)]

e=0
e1 = [G.random_element() for i in range(runs)] 
e2 = [G.random_element() for i in range(runs)] 
t1 = time.time()
for i in range(runs):   
      e = Integer(exponent[i])*e2[i] 
t2 = time.time() 
print  "Time per operation = ", (t2 - t1)/runs , " seconds"

t1 = time.time() 
for i in range(runs):   
         e = e1[i]+e2[i] 
t2 = time.time() 
print  "Time per operation = ", (t2 - t1)/runs , " seconds"
edit flag offensive delete link more

Comments

It took around 5 seconds for executing G = E.abelian_group(). But after that is done, for the exponentiation is taking very less time. I don't see any reason how exponentiation could be done so fast. Here is my output for your code. Time per operation = 2.93278694153e-06 seconds Time per operation = 2.42040157318e-06 seconds

panther gravatar imagepanther ( 2019-05-30 15:36:51 +0200 )edit

If yo upick random points on E rather than random elements of the abelian group then I think you will find that the time taken is longer. In your code you are only doing group operations in an abstract abelian group (either cyclic or possibly with two cyclic factors) so the operation is just one (or at most 2) integer modular multiplcations.

John Cremona gravatar imageJohn Cremona ( 2020-05-29 10:18:09 +0200 )edit
1

answered 2019-05-30 20:48:10 +0200

nbruin gravatar image

Note that by constructing the group in the way you do, you get a group that is explicitly represented as an additive cyclic group (with an explicit generator). When you create random elements, the system probably just takes an appropriate random element by taking a random multiple of the generator and store it as such.

As a consequence, if you then compute a multiple of THAT point, the system only has to multiply two integers and take it mod the order of the group to represent the element as a multiple of the generator. You're basically avoiding the discrete log problem by never taking "discrete exponentials". When you print the element, it looks like sage does perform the "discrete exp" (i.e., find the coordinate representation of the point).

If you take the use of the wrapper out and time something like

Integer(exponent[i])*E.gen(0)

you get something more realistic, like 0.01 seconds per operation.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2019-05-30 05:50:46 +0200

Seen: 565 times

Last updated: May 30 '19