Возведение в степень на точке на эллиптической кривой неоправданно быстро в SageMath - PullRequest
Новая
       49

Возведение в степень на точке на эллиптической кривой неоправданно быстро в SageMath

0 голосов
/ 30 мая 2019

Я работаю над эллиптическими кривыми в Sagemath.Я пытался собрать тесты для групповой работы и возведения в степень точек на эллиптической кривой NIST P-256.Когда я попытался выполнить групповую операцию над двумя точками на кривой, это заняло примерно 2 микросекунды.Когда я пытался выполнить возведение в степень в точке на эллиптической кривой со случайным показателем, это заняло всего 3 микросекунды.Как это вообще возможно?Поскольку я возводим в степень с 256-битным значением, это должно по крайней мере занять время, необходимое для 256 групповых операций, что составляет более 0,5 мс.Я беспокоюсь, если мой код неверен! 

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)]
e2 = [G.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"

1 Ответ

1 голос
/ 30 мая 2019

Не используйте E.abelian_group(), если ваша цель - рассчитать время скалярного умножения эллиптической кривой: 

sage: P = G.random_element()
sage: P.parent()
Additive abelian group isomorphic to Z/115792089210356248762697446949407573529996955224135760342422259061068512044369 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 115792089210356248762697446949407573530086143415290314195533631308867097853948*x + 41058363725152142129326129780047268409114441015993725554835256314039467401291 over Finite Field of size 115792089210356248762697446949407573530086143415290314195533631308867097853951
sage: P.__class__
<class 'sage.groups.additive_abelian.additive_abelian_wrapper.AdditiveAbelianGroupWrapper_with_category.element_class'>
sage: Q = E.random_element()
sage: Q.parent()
Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 115792089210356248762697446949407573530086143415290314195533631308867097853948*x + 41058363725152142129326129780047268409114441015993725554835256314039467401291 over Finite Field of size 115792089210356248762697446949407573530086143415290314195533631308867097853951
sage: Q.__class__
<class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>

E.abelian_group() - это дискретное логарифмическое представление E(?_p): один (или более) генератор длягруппа выбрана: 

sage: G.gens()
((20722840521025081260844746572646324413063607211611059363846436737341554936251 : 92859506829486198345561119925850006904261672023969849576492780649068338418688 : 1),)

, а точки представлены в виде векторов показателей степени: 

sage: P.vector()
(115792089210356248762697446949407573529996955224135760342422259061068512044368)

, следовательно, c*P просто умножает показатель степени на c и уменьшает по модулю порядоккривая.

Используйте E.random_element(), чтобы получить точки кривой и выполнить истинные операции эллиптической кривой: 

sage: c = 2^100
sage: %timeit c*Q
100 loops, best of 3: 3.88 ms per loop
sage: c = 2^1000
sage: %timeit c*Q
10 loops, best of 3: 32.4 ms per loop
sage: c = 2^10000
sage: %timeit c*Q
1 loop, best of 3: 321 ms per loop
...