橢圓曲線密碼

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

例如:在 上, (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)

Pointx, 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

results matching ""

    No results matching ""