ECDSA

有了橢圓曲線密碼的基礎，就可以進行簽章

簽章分成簽名和驗證

簽名：

有公私鑰 private key = dA, public key = Qa,

要簽名的資料的 hash 值 z,

先產生出一個點 P = k * G, 座標 ($x_{r}, y_{r}$)

s = $\frac {z + x_{r}*dA}{k}$ (mod N)， 簽名即為 sig = ($x_{r}, s$ )

signature 傳送時是用 DER 格式：

def der(self):
    rbin = self.r.to_bytes(32, byteorder='big')

    # because if highest bit is set, it means it's negative
    # (which means the leading bit of the byte is 1 -> >= 128)
    # so we need to put a '00' to prevent it becoming negative
    if rbin[0] >= 128:
        rbin = b'\x00' + rbin

    # add length
    result = bytes([2, len(rbin)]) + rbin

    sbin = self.s.to_bytes(32, byteorder='big')
    if sbin[0] >= 128:
        sbin = b'\x00' + sbin

    result += bytes([2, len(sbin)]) + sbin
    return bytes([0x30, len(result)]) + result

要注意一下當 r 的第一個 byte 超過 128，要加上前綴 00 ，(原因)

驗證：

$\frac {z}{s} * G + \frac {x_{r}}{s} * Q_{a}$ = $\frac {z}{s} * G + \frac {x_{r} * d_{A}}{s} * G$ = $\frac {z + x_{r}*d_{A}}{s} * G$ = $(x_{r}, y_{r})$

由簽名時可知 $k = \frac{z+x_{r}*d_{A}}{s}$ ，

所以產生出來的座標如果跟簽名時一樣，表示驗證成功

這裡可以這樣想， signature 是由私鑰產生，私鑰和公鑰是一對，

所以當我們在驗證時用公鑰產生出的座標與私鑰一樣，那簽名可以被認定為是真的，

真的是由私鑰者簽名。

定義 Signature ：

class Signature:

    def __init__(self, r, s):
        self.r = r
        self.s = s

    def __repr__(self):
        return 'Signature({:x}, {:x})'.format(self.r, self.s)

    @classmethod
    def parse(cls, sig_bin):
        s = BytesIO(sig_bin)
        compound = s.read(1)[0]

        if compound != 0x30:
            raise RuntimeError('Bad Signature')

        length = s.read(1)[0]
        if length + 2 != len(sig_bin):
            raise RuntimeError('Bad Signature Length')

        marker = s.read(1)[0]
        if marker != 0x02:
            raise RuntimeError('Bad Signature')

        rlength = s.read(1)[0]
        r = int(s.read(rlength).hex(), 16)

        marker = s.read(1)[0]
        if marker != 0x02:
            raise RuntimeError('Bad Signature')

        slength = s.read(1)[0]
        s = int(s.read(slength).hex(), 16)

        if len(sig_bin) != 6 + rlength + slength:
            raise RuntimeError('Signature too long')

        return cls(r, s)

有 r, s 兩個成員

在 S256Point 裡定義 verify 、parse 函式

def verify(self, z, sig):
    s_inv = pow(sig.s, N-2, N)

    u = z * s_inv % N
    v = sig.r * s_inv % N
    total = u*G + v*self
    return total.x.num == sig.r

試著驗證:

從 der 可以得到 signature (Signature.parse)，從 sec 可以得到 public point (S256Point.parse)

接著用 S256Point.verify 來驗證訊息是否正確

@staticmethod
def exercise2_1():
    Exercise3.print_divider()
    der = bytes.fromhex('304402201f62993ee03fca342fcb45929993fa6ee885e00ddad8de154f268d98f083991402201e1ca12ad140c04e0e022c38f7ce31da426b8009d02832f0b44f39a6b178b7a1')
    sec = bytes.fromhex('0204519fac3d910ca7e7138f7013706f619fa8f033e6ec6e09370ea38cee6a7574')

    z = int.from_bytes(double_sha256(b'ECDSA is awesome!'), 'big')

    sig = Signature.parse(der)
    point = S256Point.parse(sec)
    print(point.verify(z, sig))