橢圓曲線密碼

有限體也遵守橢圓曲線的特性，也就是加減乘除的結果也會落在曲線上，並且在有限體範圍內

例如：在 $y^2 = x^3 + 7 : F_{137}$ 上， (73, 128) + (46, 22) = ?

從上一章知道

s = (128 - 22) / (73 - 46) = 106/27 = 106 * $27^{135}$ = 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( $73^2$ ) / (_2 *_128) = 95 / 119 (mod 137) = 95 * $119^{135}$ = 48 (mod 37)

x = $48^2 - 2*73 = 103 (mod 137)$

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 = 2G, G + G + G = 3G, ..... nG = 0

=> {0, G, 2G, 3G ..... (n-1)G } 就是集合

想像一下如果集合是 ~ $~ 2^{256}$

那這個集合P = sG 非常非常大

在知道 s 的狀況下找到 P 很簡單，

但是要從 P 知道 s 幾乎是不可能的事，

就好像撞球，sG 的過程就是求一直在曲線上來回撞擊，Ｐ是最後位置

如果給你撞球最後位置和初始位置，我們不知道到底撞了幾次(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 是私鑰，Ｐ是公鑰，Ｇ是 scep256k1的產生點，

之後會得到一組座標(x, y)

然後用 SEC 格式組合出公鑰，

SEC 是用來壓縮公鑰的方式，因為在有曲線的情況下，知道 x 就一定知道 y，因此只要記住 x 就可以

SEC 格式是：如果 y是偶數，則02+x ，如果是奇數，則 03+x

例如：(x, y) = (5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC, 6AEBCA40BA255960A3178D6D861A54DBA813D0B813FDE7B5A5082628087264DA)

那麼 SEC 就是： 025CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC

3. 橢圓曲線密碼

橢圓曲線密碼

results matching ""

No results matching ""