ECDSA

ellipticcurve r,_sからp=dgを求める

#EllipticCurve

ベースポイント G （位数 n）

秘密鍵 d

公開鍵 P = dG

署名

  • h = Hash(m)

  • k \leftarrow \lbrack 1, n-1 \rbrack

  • r =

    kG のx座標とする

  • s = k^{-1}(h + rd) \mod n

  • で (r, s) が署名

検証

  • u_1 = hs^{-1} \mod n , u_2 = rs^{-1} \mod n とする

  • u_1G + u_2P = s^{-1}(hG + rdG) = k(h + rd)^{-1}(h + rd)G = kG \mod n なので、この kG のx座標が r と等しいことを確認する

r, sからP=dGを求める

  • r は kG のx座標なので kG を復元して R とすると

  • r^{-1}(sR - hG) = r^{-1}(k^{-1}(h + rd)kG - hG) = r^{-1}((h + rd)G - hG) = r^{-1}(rdG) = dG