python - ECC - 无法生成整个循环组

Question

我正在阅读 Christoffer Paares 书中关于椭圆曲线密码学的部分(“理解密码学”)。我决定在 python 中实现一个用于椭圆曲线点加法和点加倍的函数。对于我的测试，我使用了书中的示例，因此我可以测试我的结果。

例子中使用的曲线是:y^2 = x^3 + 2x + 2 mod 17

使用的生成器是:p = (5,1)

因此循环变成:

1p = (5,1)

2p = (6,3)

3p = (10,6)

4p = (3,1)

5p = (9,16)

6p = (16,13)

7p = (0,6)

8p = (13,7)

9p = (7,6)

10p = (7,1)

11p = (13,10)

12p = (0,11)

13p = (16,4)

14p = (9,1)

15p = (3,16)

16p = (10,11)

17p = (6,14)

18p = (5,16)

19p = 中性元素(无限远点)

20p = (5,1)

...

我写这段代码是为了重现结果:

def add(a,p,P,Q):
   #Check For Neutral Element
   if P == (0,0) or Q == (0,0):
       return (P[0]+Q[0],P[1]+Q[1])

   #Check For Inverses (Return Neutral Element - Point At Infinity)
   if P[0] == Q[0]:
       if (-P[1])%p == Q[1] or (-Q[1])%p == P[1]:
           return (0,0)

   #Calculate Slope
   if P != Q:
       s = (Q[1]-P[1]) / (Q[0]-P[0])
   else:
       s = ((3*(P[0]*P[0])+a)%p) ** (2*P[1])

   #Calculate Third Intersection
   x = s*s - P[0] - Q[0]
   y = (s*(P[0]-x)) - P[1]

   y = y%p
   x = x%p

   return (x,y)

r = (5,1)
for i in range(1,20):
   print i,':',r
   r = add(2,17,r,(5,1))

但是输出是:

1. : (5, 1)
2. : (6, 3)
3. : (10, 6)
4. : (3, 1)
5. : (9, 16)
6. : (12, 9)
7. : (1, 2)
8. : (12, 9)
9. : (1, 2)
10. : (12, 9)
11. : (1, 2)
12. : (12, 9)
13. : (1, 2)
14. : (12, 9)
15. : (1, 2)
16. : (12, 9)
17. : (1, 2)
18. : (12, 9)
19. : (1, 2)

如您所见，它遵循预期结果直到 6p，然后进入一个长度为 2 的循环。我已经盯着它看了好几个小时了，但我仍然不知道为什么它不起作用(毕竟:这有多难...它是 30 行 python)。

Answer 1

我不太了解这个话题，但这里有一个链接到实现 ECC 的存储库:github

编辑: 实际问题是除法模 p。您不能只使用整数算术 (15/4 == 3) 进行除法，而是需要乘以 4 模 17 的逆。4 模 17 的倒数是 13，因为 4 * 13 % 17 == 1。你的分数变成 15*13，相当于说 »15 * 1/4 模 17«。只需在斜率计算周围放置一些调试打印，您就会看到反演何时开始不同于简单的整数除法。

def euclid(a, b):
    '''Solve x*a + y*b = ggt(a, b) and return (x, y, ggt(a, b))'''
    # Non-recursive approach hence suitable for large numbers
    x = yy = 0
    y = xx = 1
    while b:
        q = a // b
        a, b = b, a % b
        x, xx = xx - q * x, x
        y, yy = yy - q * y, y
    return xx, yy, a

def inv(a, n):
    '''Perform inversion 1/a modulo n. a and n should be COPRIME.'''
    # coprimality is not checked here in favour of performance
    i = euclid(a, n)[0]
    while i < 0:
        i += n
    return i

def add(a,p,P,Q):
   #Check For Neutral Element
   if P == (0,0) or Q == (0,0):
       return (P[0]+Q[0],P[1]+Q[1])

   #Check For Inverses (Return Neutral Element - Point At Infinity)
   if P[0] == Q[0]:
       if (-P[1])%p == Q[1] or (-Q[1])%p == P[1]:
           return (0,0)

   #Calculate Slope 
   if P != Q:

       # perform multiplication with the inverse modulo p
       s = (Q[1]-P[1]) * inv(Q[0]-P[0], p)
   else:
       s = ((3*(P[0]*P[0])+a)%p) ** (2*P[1])

   #Calculate Third Intersection
   x = s*s - P[0] - Q[0]
   y = (s*(P[0]-x)) - P[1]

   y = y%p
   x = x%p

   return (x,y)

r = (5,1)
for i in range(1,20):
   print i,':',r
   r = add(2,17,r,(5,1))

打印

1 : (5, 1)
2 : (6, 3)
3 : (10, 6)
4 : (3, 1)
5 : (9, 16)
6 : (16, 13)
7 : (0, 6)
8 : (13, 7)
9 : (7, 6)
10 : (7, 11)
11 : (13, 10)
12 : (0, 11)
13 : (16, 4)
14 : (9, 1)
15 : (3, 16)
16 : (10, 11)
17 : (6, 14)
18 : (5, 16)
19 : (0, 0)

这里是 pypi 的链接.请随意使用或改进它。