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的鏈接。 隨意使用或改進。