我正在閱讀有關Christoffer Paares一書(「Understanding Cryptography」)中有關橢圓曲線密碼的章節。我決定我將實現一個橢圓曲線點加法和python點加倍的函數。對於我的測試,我使用了本書中的示例,以便測試結果。ECC - 無法生成整個循環組
在例子中使用的曲線爲: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))
然而輸出爲::
- :(5,1)
- :(6,3)
- :(10,6)
- :(3,1)
- :(9,16)
- :(12,9)
- :(1,2)
- :(12,9)
- :(1,2)
- :(12,9)
- :( 1,2)
- :(12,9)
- :(1,2)
- :(12,9)
- :(1,2)
- :(12,9)
- :(1,2)
- :(12,9)
- :(1,2)
我在試圖再現該結果寫這個代碼
正如你可能會看到它遵循直到6P預期的結果然後進入一個長度爲2的週期。我一直盯着這幾個小時,但我仍然不知道它爲什麼不起作用(畢竟:它有多難...它是30行python )。
在你的實現中永遠不會有任何浮點或舍入,該部分被截斷(在Python 2中)。這是有意的,因爲算法決定它或者它可能是錯誤所在? –
不應該需要浮點操作。一般來說,你永遠不會在加密中使用浮點數。 – Cshark