產生公鑰

現在就可以來產生公鑰了

P = s*G ，s 是私鑰，Ｐ是公鑰，Ｇ是 scep256k1的產生點，

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

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

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

SEC 格式是：如果 y是偶數，則前綴 02+x ，如果是奇數，則前綴 03+x，如果要記 x 和 y也可以，前綴是 04

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

那麼 SEC 就是： 025CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC

在 S256Point 裡實作 sec 函式

 def sec(self, compressed=True):
    if compressed:
        if self.y.num % 2 == 0:
            return b'\x02' + self.x.num.to_bytes(32, 'big')
        else:
            return b'\x03' + self.x.num.to_bytes(32, 'big')
    else:
        return b'\x04' + self.x.num.to_bytes(32, 'big') + self.y.num.to_bytes(32, 'big')

Parse SEC

parse SEC 時，先看看第一個 byte，如果第一個 byte 是 4，表示此格式有 x也有 y

如果不是 4，那我們就要從曲線上求出 y，

在求 y 時，是要求 $\sqrt {x^{3} + 7}$，

從費馬小定理我們知道

$a^{p} = a$ (mod p)

=> 所以 $y^{p+1} = y$ (mod p)

=> 假設 $w^{2} = y = y^{p+1}$ (mod p)

=> 則 $w = y^{\frac {(p+1)}{2}} = (y^2)^{\frac {(p+1)}{4}}$ (mod p)

==> 我們要求的 $y^2 = {(x^{3}+ax+b)} => y = \sqrt {x^3 + ax + b}$ (mod p)

==> 套用上面的推導，變成：$y = (x^3 + ax + b)^{\frac {(p+1)}{4}}$ (mod p)

==> 因此用 python 可以寫成

def sqrt(self):
    return self**((P+1)//4)

這樣就求出一個 y 點，另一個 y點則是 P - y (mod p)

實作：

@classmethod
def parse(cls, sec_bin):

    # if the first byte is 4, the SEC has x and y
    if sec_bin[0] == 4:
        x = int(sec_bin[1:33].hex(), 16)
        y = int(sec_bin[33:65].hex(), 16)
        return S256Point(x, y)

    # if the first byte is not 4, we have to compute y
    # note that -y mod p = p - y in finite field
    is_even = sec_bin[0] == 2
    x = S256Field(int(sec_bin[1:].hex(), 16))
    alpha = x**3 + S256Field(B)
    beta = alpha.sqrt()    # the function explained above

    if beta.num % 2 == 0:
        even_beta = beta
        odd_beta = S256Field(P - beta.num)
    else:
        even_beta = S256Field(P - beta.num)
        odd_beta = beta

    if is_even:
        return S256Point(x, even_beta)
    else:
        return S256Point(x, odd_beta)