ECC - 无法生成整个循环组

Question

我正在阅读有关Christoffer Paares一书（“Understanding Cryptography”）中有关椭圆曲线密码的章节。我决定我将实现一个椭圆曲线点加法和python点加倍的函数。对于我的测试，我使用了本书中的示例，以便测试结果。

在例子中使用的曲线为：y^2 = X^3 + 2X + 2模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）

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的inverse。 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的链接。 随意使用或改进。