😺

ECDSAとtryRecoverの原理

に公開
Solidity
Ethereum
ecdsa
DeFi
tech

ECDSA と tryRecover の数学的な原理

ブロックチェーンやウォレットでおなじみの「署名」は、ECDSA（楕円曲線デジタル署名）で作られています。この記事では、なぜ秘密鍵の持ち主にしか署名が作れないのか、そして署名とメッセージから公開鍵（アドレス）を復元できるのかを、数式を交えて説明します。イーサリアムや Solidity の ecrecover / ECDSA ライブラリの「復元」の裏側にある式も扱います。

前提：楕円曲線と「片方向」の関係

ECDSA は楕円曲線上の演算を使います（イーサリアムでは secp256k1）。

  • 曲線上に基準点 G が 1 つ固定されている
  • 秘密鍵 d は、非常に大きなランダムな整数（256 ビット程度）
  • 公開鍵 Q は、Q = d \cdot G で定まる曲線上の点（\cdot は G のスカラー倍）

重要な性質

  • d から Q は容易に計算できる（G を d 回「足す」だけ）
  • Q から d を求めることは、現実的な時間では不可能と信じられている（楕円曲線の離散対数問題）

つまり「秘密鍵 → 公開鍵」は一方向。この一方向性が、「本人だけが署名できる」仕組みの土台です。

署名（sign）で何を計算しているか

メッセージのハッシュを z、秘密鍵を d とします。

ステップ 1・2：乱数と点 R

  1. 乱数 k を 1 つランダムに選ぶ（毎回異なる k が望ましい）。k は曲線の位数 n より小さい正の整数。
  2. 曲線上の点 R = k \cdot G を計算し、R の x 座標を n で割った余りを r とする。これが署名の r。

ステップ 3：s の定義

s は次の式で定義されます。

s = k^{-1} \cdot (z + r \cdot d) \bmod n
記号 意味
k^{-1} k の法 n における逆数（k \cdot k^{-1} \equiv 1 \pmod{n}）
z メッセージのハッシュ（32 バイトを整数とみなす）
r 上で求めた R の x 座標 \bmod n
d 秘密鍵
n 楕円曲線の位数（secp256k1 では約 2^{256} の素数）

k^{-1} は、n が素数なので拡張ユークリッドの互除法やフェルマーの小定理 k^{-1} \equiv k^{n-2} \pmod{n} で多項式時間で求められます。難しいのは「署名から秘密鍵 d を求めること」であり、逆数計算ではありません。

この式に秘密鍵 d が含まれるため、d を知らないと正しい s を作れません。これが「署名は秘密鍵の持ち主にしか作れない」という部分の数学的な理由です。

署名の形：(r, s, v)

署名は (r, s, v) の 3 つで、合計 65 バイトです。

  • r：点 R の x 座標 \bmod n（32 バイト）
  • s：上記の式で決まる 0 以上 n 未満の整数（32 バイト）
  • v（復元用）：楕円曲線では x 座標が r の点は y 座標の正負で 2 つある。署名時に使った点 R = k \cdot G はそのどちらか一方なので、復元側は「どちらの R か」を指定する 1 ビットの情報が必要。それが v（イーサリアムでは 27 または 28 がよく使われる）

v があるおかげで、受け手は (r, s, v) と z だけから、署名者の公開鍵を一意に復元できます。

復元（recover / tryRecover）で何をしているか

受け手が持っているのはメッセージハッシュ z と 署名 (r, s, v) だけです。秘密鍵 d も乱数 k も知りません。

復元の式の導出

署名の式 s = k^{-1}(z + r \cdot d) \bmod n を変形します。

  1. 両辺に k を掛ける：

    k \cdot s \equiv z + r \cdot d \pmod{n}

  2. k について解く：

    k \equiv s^{-1}(z + r \cdot d) \pmod{n}

  3. 署名時に R = k \cdot G だったので、

    R = k \cdot G = s^{-1}(z + r \cdot d) \cdot G = s^{-1} \cdot z \cdot G + s^{-1} \cdot r \cdot d \cdot G

    ここで Q = d \cdot G なので、
    R = s^{-1} \cdot z \cdot G + s^{-1} \cdot r \cdot Q

  4. 両辺に s を掛ける（点のスカラー倍）：

    s \cdot R = z \cdot G + r \cdot Q

  5. r \cdot Q について解く：

    r \cdot Q = s \cdot R - z \cdot G

  6. r の逆数 r^{-1} \pmod{n} を掛ける：

    Q = r^{-1} \cdot (s \cdot R - z \cdot G)

ここで \cdot は、スカラーと点の積（スカラー倍）または点同士の足し引き（楕円曲線の演算）を表します。r^{-1} は法 n における r の逆数（整数の演算）です。

公開鍵 Q を求める式（まとめ）

Q = r^{-1} \cdot (s \cdot R - z \cdot G)
記号 意味 復元時に分かっているか
r^{-1} r の法 n における逆数 ✓ r から計算できる
s 署名の s 成分 ✓ 署名に含まれる
R 曲線上の点。x 座標が r \pmod{p} v で 2 候補のどちらかが決まる
z メッセージハッシュ ✓ 受け手が持っている
G 曲線の基準点（固定） ✓ 曲線の仕様で決まっている

手順の整理

  1. R の決定：x 座標が r \pmod{p} である曲線上の点は、y 座標の正負で 2 つある。v でそのどちらかを選ぶ（署名時に使った R = k \cdot G の点）。
  2. s \cdot R：点 R のスカラー倍
  3. z \cdot G：基準点 G のスカラー倍
  4. s \cdot R - z \cdot G：2 つの点の引き算（楕円曲線の演算）
  5. r^{-1} \cdot (s \cdot R - z \cdot G)：その結果の点を、整数 r^{-1} \pmod{n} でスカラー倍したものが公開鍵 Q
  6. アドレス：Q の座標 (x, y) から、イーサリアムの慣習（keccak256 など）でアドレスを導出する

秘密鍵 d は使わず、z と (r, s, v) だけで Q が一意に決まります。これが ECDSA.tryRecover（や ecrecover）で「誰が署名したか」を復元するときの数学的な中身です。

なぜ「改ざんや別人の署名」だと復元が合わないか

  • メッセージを 1 ビットでも変える → ハッシュ z が変わる → 署名 (r, s) は「別の z」用のものになる → その z と (r, s) から復元する公開鍵は、元の署名者の公開鍵と一致しない（または復元が失敗する）。
  • 別人の秘密鍵で署名した → (r, s) にはその人の d が込められている → 復元される公開鍵は「その別人」のもの。

つまり「正しいメッセージ・正しい署名者」のときだけ、復元されたアドレスが期待した署名者と一致します。

まとめ（数学的な流れ）

段階 数学的な意味
鍵の関係 秘密鍵 d と基準点 G から、公開鍵 Q = d \cdot G。Q から d は実質求まらない（離散対数問題）。
署名 メッセージ z と乱数 k と秘密鍵 d から (r, s) を計算。r は k \cdot G の x 座標、s = k^{-1}(z + r \cdot d) \bmod n。d がないと正しい s が作れない。
復元 z と (r, s, v) から、Q = r^{-1} \cdot (s \cdot R - z \cdot G) で「その署名を生成した公開鍵 Q」を求める。Q からアドレスを導出し、「誰が署名したか」を得る。

ECDSA は楕円曲線の離散対数問題に基づいて「秘密鍵の持ち主だけが署名を作れる」性質を実現し、tryRecover は署名とメッセージから公開鍵を一意に復元することで「誰の署名か」を判定しています。

参考

Discussion