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）

10便士=（7,1）

11p=（13,10）

12便士=（0,11）

13p=（16,4）

14p=（9,1）

15便士=（3,16）

16便士=（10,11）

17便士=（6,14）

18便士=（5,16）

19p=中性元素（指向无穷远）

20便士=（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))

印刷品

^{pr2}$

这里是pypi的链接。 随时使用或改进它。在