受理された署名は、何も証明していない――Schnorr と nonce 再利用

zk-tokyo のAdvanced Cryptography Program 2026を受講しています。Week 3 のテーマは楕円曲線と Schnorr プロトコルで、課題schnorr-from-scratchでは有限体の逆元から始めて楕円曲線の群演算を組み、その上にシグマプロトコルと Fiat-Shamir 変換を積んで、最後は Bitcoin と同じ曲線 secp256k1 上で署名を作りました。

今回の収穫は、検証に通ったという事実そのものには、何の証明力もないと体で理解できたことです。

自習ノート: 知っていることだけを、渡す
週ごとの目次: Advanced Cryptography 2026 自習ノート
リポジトリ: susumutomita/advanced-cryptography-note

3 手のやりとり

公開鍵P = xGについて「秘密鍵 x を知っている」ことを示すプロトコルは、たった 3 手です。証明者がランダムなrを選んでR = rGを送り、検証者がランダムなチャレンジeを返し、証明者がs = r + e·xを返す。検証者はsG = R + ePを確かめます。

正直に計算したsなら検証式は必ず成り立ちます。展開すればsG = (r + e·x)G = rG + e·(xG) = R + ePで、たった 1 行です。

秘密鍵を使わずに、同じ会話を作る

ところが、この会話は秘密鍵なしでも作れます。順番を逆にするだけです。先にeとsをランダムに決めておき、検証式から逆算してR := sG - ePと置く。すると検証式は定義上成り立ちます。

自習ノートに載せたラボで実際に走らせると、こうなります。

x を使わずに作った会話:
  (R, e, s) = ((146, 214), 190, 284)
検証者はこれを受理するか: True

つまり「受理された記録が 1 本ある」ことは、秘密を知っている証拠になりません。本物との違いは中身ではなく順番だけです。本物はRを先に出し、そのあとでチャレンジを受け取る。偽物はチャレンジを知ってからRを作る。

証明者が先にコミットし、チャレンジを後から受け取るという順番が、健全性の全部を担いでいます。ここが今週いちばん腑に落ちた部分でした。

抽出器と攻撃は、同じ 1 本の式

では「知っている」ことは何で保証されるのか。使う道具は抽出器と呼ばれるもので、証明者を巻き戻して同じ R のまま別のチャレンジを投げます。2 つの応答が得られたなら、そこから秘密鍵を計算して取り出せる。取り出せた以上、秘密鍵は最初から証明者の中にあった、という論法です。

s1 = r + e1·x
s2 = r + e2·x
s1 - s2 = (e1 - e2)·x        ← r が消える
x = (s1 - s2)·(e1 - e2)^-1

この式は、そのまま nonce 再利用攻撃の中身でもあります。安全性の根拠と攻撃手順が同じ 1 本の式である、というのがきれいでした。

本物の曲線でも、署名 2 本で鍵が出る

トイの曲線だからではありません。課題の実装で、secp256k1 上の 256 ビットの秘密鍵に対して、同じ nonce で 2 回署名した結果です。

署名1: R.x = 0xb44cf0c87f8f960c...  s1 = 0x28807ada8ee210bd...
署名2: R.x = 0xb44cf0c87f8f960c...  s2 = 0x24da65e7523016c0...
R が一致している: True

復元した x = 0x1b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
本物の  x = 0x1b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
一致: True

攻撃者が使ったのは公開値だけです。しかもRが一致しているかどうかは誰でも見えるので、再利用が起きたこと自体が公開情報から分かります。乱数を毎回変えるのは運用上の注意ではなく、安全性の前提そのものでした。

壊して分かった、実装の細部

課題は Part 1 から Part 3 まで一本につながっていて、下が間違っていると上が動きません。わざと壊して採点器に通すと、失敗の形がそれぞれ違うのが面白いところでした。

壊し方	失敗の形
逆元を 0..p-1 に正規化しない	値は正しいのに「正規化して返してください」で落ちる
y 座標の符号を逆にする	点が曲線から外れる。`is_on_curve`が即座に捕まえる
スカラー倍を素朴に k 回足す	落ちるのではなく終わらない。約 3.0×10^63 年かかる
スカラーの mod を n でなく p にする	値が法より小さいケースだけ通り、それ以外で失敗する
ハッシュの引数順を入れ替える	自分の署名は自分で検証できてしまう

最後の 2 つが特に厄介です。どちらも自己完結したテストなら通ってしまう種類の間違いで、外部の期待値と突き合わせて初めて表面化します。

持ち帰った問い

Week 1 の問いは「この信号を縛っている式はどれか」、Week 2 は「この値を隠している乱数は何か」でした。Week 3 ではこうなります。この値を隠しているのは何で、その条件は何本あるか。

noncerがランダムであること、毎回違うこと、ハッシュに正しい文脈が入っていること。1 本でも欠ければ、静かに壊れます。Beaver triple を使い回した瞬間、OT の乱数範囲から 0 を除いた瞬間、そして nonce を再利用した瞬間。3 週続けて同じ教訓を別の形で見ました。

自習ノートを公開しました

知っていることだけを、渡す

単一の HTML ファイルで、外部への通信はありません。正直な証明者と simulator を切り替えて 3 手を回せるラボと、nonce 再利用から秘密鍵を復元する攻撃ラボが付いています。検問クイズは有限体・楕円曲線・レスポンス計算・受理判定・鍵復元・原理の 6 分野から毎回その場で出題され、判定はラボと同じ計算器が行います。