楕円曲線による署名

ecdsa

#ECDSA

楕円曲線を用いた署名schema

ある楕円曲線 Eと、適当な元 Gを事前に決めておく。ここで n = order(G)

署名者

dを適当に選び、 Q = d*Gとして公開おく

h = Hash(m)とする。ただし nbits(h) < nbits(n)となるようにLSBを捨てる

kを適当に選び、 R= k*Gを計算する

r = R.x \mod n, s = k^{-1}(h + rd) \mod nとして (r,s)が署名

検証者

同じ様に h = Hash(m)をとってきて、 X = s^{-1}h*G + s^{-1}r*Qを計算する。 r \equiv X.x \mod nとなることを確認する

s^{-1}h*G + s^{-1}r*Q = s^{-1}h*G + s^{-1}rd*G

= (s^{-1}h + s^{-1}rd)*G = s^{-1}(h + rd)*G

= (k^{-1}(h + rd))^{-1}(h + rd)*G = k*G = R

kの再利用

をしてはだめという話。

h, h'があって、 r = r' = R.x, s = k^{-1}(h + rd), s' = k^{-1}(h' + rd)

から s - s' = k^{-1}(h - h')なので、 k^{-1} = \frac{s - s'}{h - h'}として kが手に入る。 kが手に入れば sk = h + rdで、 h , rは既知より dがわかる

hの再利用

再利用……？ 特にできることなかった