どうしてECDSA署名から公開鍵が復元できるのか？

ECDSAの署名からどうして公開鍵が取得できるの？という聞かれて何でだろうねって話になったので調べてみた。

署名から公開鍵のセットを復元

Rubyではecdsaのgemを使えば以下のように署名と署名対象のメッセージから公開鍵を取得できる。（署名対象のメッセージはどうせなのでBitcoinで使用されているのと同じトランザクションのsighashを使用。そのためbitcoinrbのgemも利用している）

実行すると↓のように2つの公開鍵が抽出できる。

0259f6658325c4e3ca6fb38f657ffcbf4b1c45ef4f0c1dd86d5f6c0cebb0e09520
03a9255e098f4075e9ebfaf7859f459095667879db33e977fc8c91029afa8a2490

↑のコード上の署名はこの内の0259f6658325c4e3ca6fb38f657ffcbf4b1c45ef4f0c1dd86d5f6c0cebb0e09520に対応する秘密鍵で行ったもの。

署名とメッセージから公開鍵を復元する際の計算

ecdsaのgemで署名とメッセージから公開鍵を計算しているのがrecovery_public_key.rbの↓の部分。

module ECDSA
...

  def self.recover_public_key(group, digest, signature)
    return enum_for(:recover_public_key, group, digest, signature) if !block_given?

    digest = normalize_digest(digest, group.bit_length)

    each_possible_temporary_public_key(group, digest, signature) do |point|
      yield calculate_public_key(group, digest, signature, point)
    end

    nil
  end

  private

  def self.each_possible_temporary_public_key(group, digest, signature)
    signature.r.step(group.field.prime - 1, group.order) do |x|
      group.solve_for_y(x).each do |y|
        point = group.new_point [x, y]
        yield point if point.multiply_by_scalar(group.order).infinity?
      end
    end
  end

  def self.calculate_public_key(group, digest, signature, temporary_public_key)
    point_field = PrimeField.new(group.order)

    # public key = (tempPubKey * s - G * e) / r
    rs = temporary_public_key.multiply_by_scalar(signature.s)
    ge = group.generator.multiply_by_scalar(digest)
    r_inv = point_field.inverse(signature.r)

    rs.add_to_point(ge.negate).multiply_by_scalar(r_inv)
  end

end

ここでは以下の計算をしている。

署名データ(r, s)のrを楕円曲線のx座標として、y座標を計算する。
secp256k1の楕円曲線の多項式はy² = x³ + 7なので、rの値をxに入れればyを計算できる。楕円曲線の平面曲線はx軸に対して対称なのでyの取りうる値はx軸を対称に2つある（↑のrecover_public_keyを呼んで2つの公開鍵が返ってきたのはこのため）。ここで計算した2つの点について2以降の計算をして２つの公開鍵を導出する。
rと1で計算したyから[r, y]となる楕円曲線上の点を計算する。
2で計算した点に(r, s)のsを掛けた点rsを計算する。
secp256k1のグループGの生成点にメッセージを掛けた点geを計算する。
3で計算した点rsに4で計算した点geを減算して出来た点に ${r^{-1}}$ を掛けた点を計算する。

5で計算した点が復元した公開鍵になる。

もう少し簡略化してみよう。署名データを(r, s)、1でrを使って計算した2つの点をRとR'とし、メッセージのハッシュ値をe、secp256k1の楕円曲線の生成点をGとした場合、算出している公開鍵は以下の２つだ。

$\frac{sR - eG}{r}$ および $\frac{sR' - eG}{r}$

補足

sec1-v2.pdfの4.1.6章では、Rのx座標としてx = r + jN(j=0～h)となるようでした。
secp256k1ではh=1なので、(r, y), (r, -y), (r+N, y), (r+N, -y)の4種類になりそうです。
(すみません、数学的なことはわかってないです。。)
— nayuta-ueno (@nayuta_ueno) 2018年1月22日

↑の1の計算についてコメントもらったので追記。

1でrをx座標として２つのRとR'を計算すると書いたが、楕円曲線のペーパーには、このx = r + jnでx座標を求めるようになっている。ここでjは ${j \in \{0, 1, ...., h\}}$ の集合でhは各楕円曲線毎に定義されており、secp256k1の場合h = 1だ。つまりx座標の候補はrとr + nの２つになる（nはグループの位数）。r + nがグループの剰余系の素数を超えないようになってるので、実際にその範囲内のr + nが候補に上がるのは、rが剰余系の素数 - 1 - n以下の場合。最初の復元コードの出力結果が２つの公開鍵だったのはr + nがこの範囲外で、rのみの計算となったため。