橢圓曲線密碼
有限體也遵守橢圓曲線的特性,也就是加減乘除的結果也會落在曲線上,並且在有限體範圍內
例如:在 上, (73, 128) + (46, 22) = ?
從上一章知道
s = (128 - 22) / (73 - 46) = 106/27 = 106 * = 9 (mod 137)
x = 81 -73 - 46 = 99 (mod 137)
y = 9(73 - 99) - 128 = 49 (mod 137) . ==> (73, 128) + (46, 22) = (99, 49)
兩一樣的點的相加也符合規範,
例如: 2*(73, 128)
s = 3() / (_2 *_128) = 95 / 119 (mod 137) = 95 * = 48 (mod 37)
x =
y = 48 (73 - 103) = 76 (mod 137) . ==> 2*(73, 128) = (103, 76)
讓 Point
的 x
, y
都是 FieldElement
,那麼結果結果就會是在有限體裡面(感謝 python 的無型態才能這麼方便)
下面測試各個點和相加是否在曲線上
@staticmethod
def exercise2_1():
prime = 223
a = FieldElement(0, prime)
b = FieldElement(7, prime)
additions = ((192, 105, 17, 56), (47, 71, 117, 141), (143, 98, 76, 66))
for x1_raw, y1_raw, x2_raw, y2_raw in additions:
x1 = FieldElement(x1_raw, prime)
y1 = FieldElement(y1_raw, prime)
x2 = FieldElement(x2_raw, prime)
y2 = FieldElement(y2_raw, prime)
p1 = Point(x1, y1, a, b)
p2 = Point(x2, y2, a, b)
print('{} + {} = {}'.format(p1, p2, p1+p2))
Point(FieldElement_223(192), FieldElement_223(105)) + Point(FieldElement_223(17), FieldElement_223(56)) = Point(FieldElement_223(170), FieldElement_223(142))
Point(FieldElement_223(47), FieldElement_223(71)) + Point(FieldElement_223(117), FieldElement_223(141)) = Point(FieldElement_223(60), FieldElement_223(139))
Point(FieldElement_223(143), FieldElement_223(98)) + Point(FieldElement_223(76), FieldElement_223(66)) = Point(FieldElement_223(47), FieldElement_223(71))
===========================================================================================
從這裡我們可以定義一個集合:
- 加法運算
- if A, B in G, A + B in G
- (A+B)+C = A+(B+C)
- A+B = B+A
- if A in G, there is a -A in G
- identity exists (point at infinity)
===========================================================================================
產生方法為
選一個產生點G
一直加 G 直到結果為無限遠點
=> G + G = 2G, G + G + G = 3G, ..... nG = 0
=> {0, G, 2G, 3G ..... (n-1)G } 就是集合
想像一下如果集合是 ~
那這個集合P = sG 非常非常大
在知道 s 的狀況下找到 P 很簡單,
但是要從 P 知道 s 幾乎是不可能的事,
就好像撞球,sG 的過程就是求一直在曲線上來回撞擊,P是最後位置
如果給你撞球最後位置和初始位置,我們不知道到底撞了幾次(s)吧?
這就是橢圓曲線密碼的原理
以下演示從 G = (47, 71) 加到無窮遠點
@staticmethod
def exercise4_1():
Exercise2.print_divider()
prime = 223
a = FieldElement(0, prime)
b = FieldElement(7, prime)
x = FieldElement(47, prime)
y = FieldElement(71, prime)
p = Point(x, y, a, b)
product = Point(x, y, a, b)
inf = Point(None, None, a, b)
count = 1
while product != inf:
product += p
count = count + 1
print(count)
這個集合的階(n) 即是 21
現在就可以來產生公鑰了
P = s*G ,s 是私鑰,P是公鑰,G是 scep256k1的產生點,
之後會得到一組座標(x, y)
然後用 SEC 格式組合出公鑰,
SEC 是用來壓縮公鑰的方式,因為在有曲線的情況下,知道 x 就一定知道 y,因此只要記住 x 就可以
SEC 格式是:如果 y是偶數,則02+x ,如果是奇數,則 03+x
例如:(x, y) = (5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC, 6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA)
那麼 SEC 就是: 025CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC