ECDSA
有了橢圓曲線密碼的基礎,就可以進行簽章
簽章分成簽名和驗證
簽名:
有公私鑰 private key = dA, public key = Qa,
要簽名的資料的 hash 值 z,
先產生出一個點 P = k * G, 座標 ()
s = (mod N), 簽名即為 sig = ( )
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
,(原因)
驗證:
= = =
由簽名時可知 ,
所以產生出來的座標如果跟簽名時一樣,表示驗證成功
這裡可以這樣想, 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))