secp256k1

後來密碼學家發明了 secp256k1

在曲線 $y^2 = x^3 + 7$ 上 (a = 0, b = 7)

有限體質數為 $p = 2^{256} - 2^{32} - 977$

產生點 Ｇ = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

集合個數為 n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

這是一個非常大的數字

對於擔心比特幣會被攻破的人，這個集合個數約莫是 $10^{77}$

我們銀河系原子個數為 ～ $10^{68}$

所以你找到別人私鑰的機率比在銀河系找到兩個標記為一樣的原子還低.....

實作：

證明 n 這個數字真的是這個集合的階

@staticmethod
def exercise4_4():
    # this exercise is confirming n*G = 0
    Exercise2.print_divider()
    n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
    print(n * G)

>>> Point(infinity) # 得證

這裡會用到 S256Point 的 __rmul__

def __rmul__(self, coefficient):
    # 因為最大是 2^256
    # 所以把 N 取 mod 後剩下的數一定可以用 256 bits 表示
    # 那麼只要將 mod 後的數對每個位元看是否是1來判斷要不要累加即可得到結果

    coef = coefficient % N
    current = self

    # result is what we return, starts at 0
    result = S256Point(None, None)

    # we double 256 times and add where there is a 1 in the binary
    # representation of coefficient
    for i in range(self.bits):
        if coef & 1:
            result += current

        current += current
        # we shift the coefficient to the right
        coef >>= 1
    return result

要把一個 S256Point 加 coefficient 次，

先將 coefficient 取 N 的模數，因為此集合不會超過 N 個，

然後我們 loop 256 次，每次把 coefficient 右移一位，如果這位是1

則把結果加上 current，

current 則是每次都加上自己，因為在橢圓曲線密碼那邊說過，

G + G => 2G, 所以我們這樣 loop 256 次，在每一位時都可以得到應該該相加的 current值

之後就可以拿 Ｇ 去產生各式的「點」

這些點可以用來簽名和驗證