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