ECDSA の nonce 再利用：1 つの数の重複が秘密鍵を明らかにする仕組み

決して繰り返してはならない数

ECDSA の署名は整数の組 (r, s) です。署名の生成には 3 つの入力が必要です。秘密鍵 d、メッセージハッシュ z、そして新しい秘密の整数 k です。これが nonce で、「number used once」（一度だけ使われる数）の略です。署名者は k を [1, n−1] の範囲から選び（n は曲線のベースポイント G の位数）、次の計算を行います。

R = k * G                      (a point on the curve)
r = x-coordinate of R  mod n
s = k^-1 * (z + r * d) mod n

signature = (r, s)

それぞれの出力が何から得られるのかに注目してください。s には nonce、ハッシュ、鍵のすべてが混ざっています。しかし r は k だけから導出されます。これは kG の x 座標であり、nonce と曲線だけで決まる関数です。メッセージは関与しません。秘密鍵も関与しません。

一文で言えば、これが問題のすべてです。同じ k で生成された 2 つの署名は同じ r を持ち、r はすべての署名とともに公開されます。nonce の重複は、誰かが見つけ出さなければならない隠れた欠陥ではありません。すべての検証者が読み取り、すべてのブロックエクスプローラーが永久に保存するフィールドに、誰の目にも見える形で自ら姿を現します。

2 つの署名、2 つの未知数

署名者が、ハッシュが z1 と z2 である 2 つの異なるメッセージに、同じ k と同じ鍵 d を使ったとします。2 つの署名は同じ r を共有するので、次の式が得られます。

s1 = k^-1 * (z1 + r * d) mod n
s2 = k^-1 * (z2 + r * d) mod n

ここに出てくる値は、k と d を除いてすべて公開されています。式が 2 つ、未知数が 2 つです。逆元を消すため、それぞれの式の両辺に k を掛けます。

k * s1 = z1 + r * d mod n
k * s2 = z2 + r * d mod n

同じ鍵で両方のメッセージに署名し、同じ nonce から同じ r が生成されたため、r * d の項は 2 行で同一です。1 つ目の式から 2 つ目の式を引くとこの項が打ち消され、秘密鍵は式から完全に消えます。

k * s1 - k * s2 = z1 - z2      mod n
k * (s1 - s2)   = z1 - z2      mod n

k = (z1 - z2) * (s1 - s2)^-1   mod n

これで nonce が復元できます。これをステップ 2 のどちらかの式に代入すると、鍵が求まります。この時点で d に掛かっているのは r だけだからです。

k * s1     = z1 + r * d        mod n
r * d      = k * s1 - z1       mod n

d = (s1 * k - z1) * r^-1       mod n

4 ステップで、探索も推測も要りません。必要なのは 2 回のモジュラー逆元の計算と数回の乗算だけで、すでに公開されているデータから、どんなマシンでもマイクロ秒単位で計算できます。

実用上の注意点が 1 つあります。エンコーディングは、署名者が計算した s をそのまま保持するとは限りません。Bitcoin といくつかのライブラリは、値が範囲の上半分に入った場合に s を n − s に置き換えて、「low-S」形式に正規化します。これは BIP-62 で提案され、BIP-146 でリレールールとして規定された展性の対策で、nonce とは無関係ですが、この計算とは重なります。その場合、復元した値は k ではなく −k に対応することがあり、数値を合わせるには先に符号を確定させる必要があります。難しさは何も変わりません。エンコーディングについては ECDSA 署名の形式で別途解説しています。

机上の空論ではない

これは現実の ECDSA の破綻のなかで最も多くの事例を生んできた類型ですが、数学が原因だったものは 1 つもありません。どの事例も、実装が本来与えてはならない nonce を与えたものです。

• PlayStation 3（2010年）：Sony のファームウェア署名の実装は、k を使うべき箇所に定数を使っていました。この実装が生成した署名はすべて同一の r を持ち、どの 2 つの署名からでもゲーム機のマスター署名鍵が求められてしまいました。この欠陥は、27C3 の講演 Console Hacking 2010 で公開の場で実証されました。これ以上ないほど純粋な実例です。アルゴリズムは、決して変わることのなかった 1 つの変数を除いて、正しく実装されていました。
• Android のウォレット（2013年）：2013年8月14日、Android Developers Blog は Some SecureRandom Thoughts を公開しました。記事の表現によれば、「8月11日に複数の Bitcoin アプリケーションのアップデートにつながった、bitcoin トランザクションの侵害」を調査した結果です。根本原因は、Java Cryptography Architecture を使うアプリケーションが「基盤となる PRNG の初期化が不適切なため、Android デバイス上で暗号論的に強い値を受け取れない可能性がある」ことでした。影響を受けたデバイスで署名していたウォレットは、何度も同じ状態で初期化されうる生成器から nonce を取得していました。Google は API レベル 16〜18 向けに PRNGFixes という回避策を提供し、プラットフォームにもパッチを適用しました。何が壊れていたのかに注意してください。ウォレットの暗号コードでも曲線でもなく、その両方の土台にある OS のプリミティブです。
• より広い類型（偏った nonce）：完全な重複は、目立つほうの形です。目立たないほうは、nonce が偏っているだけの場合です。生成器がわずかにずれた範囲の値を返す、値を切り詰める、タイミング情報を漏らすといった理由で、いくつかのビットが一様に分布していない状態です。この場合はきれいな代数的近道はありませんが、問題を格子の短いベクトルを見つける問題に置き換えることができ、格子基底簡約で解けます。Breitner と Heninger の Biased Nonce Sense（Financial Cryptography 2019）は、これを公開ブロックチェーンとインターネット全体のスキャンに適用し、数百の Bitcoin の鍵に加えて、数十の Ethereum、Ripple、SSH、HTTPS の鍵を復元しました。いずれも、一度も重複していない、不完全なだけの nonce からです。教訓は厳しいものです。「ほぼランダム」は防御になりません。

どの事例も ECDSA の欠陥を必要としておらず、より大きな曲線を使っても防げません。このアルゴリズムは署名ごとに完全に一様な秘密を要求し、それが得られなかったときにも何の警告も出しません。

現在のチェーンが示すもの

ブロックチェーンは忘れないため、重複した r の値は今も Bitcoin のブロックチェーンに永久に残っています。このサイトの nonce 再利用チェッカーは、mempool.space の API からアドレスの最近のトランザクションを取得し、そのアドレスから資金を使用している入力から DER 署名を抽出して、公開鍵と r の組ごとにグループ化します。2026年8月20日に 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm について返された結果は次のとおりです。

address                 1BFhrfTTZP3Nw4BNy4eX4KFLsn9ZeijcMm  (P2PKH)
transactions returned   50      <- API cap, not the full history
  spending from it      30
inputs from address     110
signatures parsed       110     (unattributed 0, taproot 0, unparsed 0)
distinct public keys    1
distinct r values       73      <- 110 signatures, only 73 nonces
repeated-r groups       6
identical duplicates    0

鍵は 1 つ、署名は 110 件、異なる nonce は 73 個です。この差がすべてを物語っています。110 件の署名のうち 43 件が、少なくとも 1 つの別の署名と r を共有するグループに属しています。しかも 6 つのグループのいずれでも s の値は異なっており、同じ署名が重複しただけという無害な説明は成り立ちません。最大のグループは次のとおりです。

r = d47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
pubkey = 04dbd0c6...49c5ff (uncompressed)

ad698b53bbba9e7d807559ec7d3a466fccb669dd3659a1604a206eeb9965c527  vin 0  2012-12-21
b4922bc8cc3624487cdcf4b0ed5a98a21a4552a48dfe495490a7443dd546821e  vin 0  2012-12-21
8ab813e5a4039eb79484c315e9c0e201c9d80385c3f3650a4c4b974db9172148  vin 0  2012-12-21
0b5315f4d472a22a6937a20a8d44b8e77099f2a951b65c53c9ebf912352504fa  vin 0  2012-12-19
952d8301780ca74fca5f6541db44ba49e47e8514dfdef36bc7e3d534085dbbf6  vin 0  2012-12-19
    ... 5 more, the oldest on 2012-08-16

ここで注目すべき点が 2 つあります。1 つ目に、2 番目に大きいグループも、別の r を共有する 10 件の署名です。そしてどちらのグループでも、すべての署名がそれぞれのトランザクションの同じ入力インデックスにあります（一方のグループではインデックス 0、もう一方ではインデックス 1）。これは、乱数がたまたま衝突したときの姿ではありません。署名処理を始めるたびに同じ状態に再初期化され、そこから順に値を進めていく生成器の姿です。入力 0 は常に 1 番目の値を、入力 1 は 2 番目の値を受け取ります。2 つ目に、この再利用は 2012年8月から12月にかけて起きています。Android の SecureRandom の問題が公表される、ほぼ 1 年前です。この種の欠陥は、公の名前が付く前から実際に起きていました。こうした公表が示すのは問題が気づかれた時期であって、問題が始まった時期ではないことを、改めて思い出させます。

対策：サイコロを振るのをやめる

根本的な解決策は「より良い乱数生成器を使う」ことではありません。署名の処理経路から乱数生成器を完全に取り除くことです。

RFC 6979、決定的 ECDSA：k をランダムに選ぶのではなく、導出します。秘密鍵とメッセージハッシュを HMAC ベースの決定的ランダムビット生成器（HMAC-DRBG）にシードとして与え、その出力から k を取り出します。値が [1, n−1] の範囲外なら取り直します。得られる値は一様に見え、鍵なしでは予測できず、そして何より重要なことに、メッセージの関数です。異なるメッセージからは必ず異なる k が得られるため、偶発的な再利用は単に起こりにくいのではなく、構造的に起こりえなくなります。同じメッセージに 2 回署名すると同じバイト列が再現されますが、これは無害で、テストに便利な性質も兼ねています。署名時にエントロピー源を参照しないため、エントロピー源が壊れていても影響を受けません。FIPS 186-5 は、ランダム化された方式と並んで決定的 ECDSA も認めています。

RFC 8032、EdDSA：Ed25519 と Ed448 は、同じ考え方を方式そのものに組み込むことで、選択の余地をなくしています。署名ごとの秘密は、鍵から導出したプレフィックスとメッセージをまとめてハッシュすることで導出され、実装者がランダムな値に差し替えられる API はありません。既存の方式を引き継ぐのではなく方式を選べる立場なら、この方式は構造上、この破綻の原因そのものを取り除きます。Bitcoin の Taproot 署名も同じ考え方に従っており、BIP-340 は、任意の補助乱数を伴う決定的な nonce の導出を義務付けています。

ヘッジ付き署名：純粋な決定性には、知っておくべきトレードオフが 1 つあります。署名中に引き起こされたフォールト（スマートカードのクロックや電圧のグリッチ）によって、決定的な署名者が同じメッセージに対し、導出された同じ k で 2 つの異なる署名を生成してしまうことがあります。これは、nonce の再利用とまったく同じ状態です。RFC 6979 は §3.6 でこれを想定しています。ヘッジ付きの方式は、決定的な導出を新しい乱数で置き換えるのではなく、導出に新しい乱数を混ぜ込みます。これにより、導出と乱数生成器のどちらか一方でも健全であれば安全な nonce が得られます。Go の crypto/ecdsa はこの方法で署名し、@noble/curves は extraEntropy オプションとしてこれを提供しています。BIP-340 の補助乱数も同じ考え方です。

主要なライブラリのデフォルトの動作は次のとおりです。

この表の「いいえ」は、バグ報告ではありません。正常な OS の CSPRNG から得たランダムな nonce は、規格に完全に準拠した署名方法であり、FIPS 186 のどの版も規定してきた方式です。FIPS 186-5（2023年）では、これに並ぶ選択肢として決定的な方式が追加されました。この列が示すのは正しさではなく依存関係です。「いいえ」の行では秘密鍵の安全が署名時点のエントロピー源に懸かっており、「はい」の行ではそうではありません。それが問題になるかどうかは、デプロイ環境しだいです。堅牢化されたサーバーと、起動したばかりの組み込みデバイス、クローンされた VM イメージ、2013年のスマートフォンとでは、賭けの条件がまったく違います。ライブラリ相互運用チートシートでは、この違いとデフォルト動作のその他の違いを並べて確認できます。

実際に取るべき対策

• k を自分で指定してはいけません。署名 API が nonce のパラメーターを受け付ける場合、それは機能ではなく、自分の足を撃ちかねない危険な仕掛けだと考えてください。テストで再現可能なバイト列が必要になったからといって、決して使ってはいけません。決定的署名なら、それを安全に得られます。
• 乱数生成器を自作してはいけません。「タイムスタンプとリクエスト ID でシードしています」というのが、まさにこうしたインシデントの始まり方です。プラットフォームの CSPRNG を使うか、CSPRNG を必要としないライブラリを使ってください。
• 実際にどの nonce 生成戦略で動いているかを確認してください。2 行のテストでおおよそはわかります。ただし、このテストではランダムとヘッジ付きを区別できないため、結果は慎重に読んでください。

import { generateKeyPairSync, sign } from "node:crypto";

const { privateKey } = generateKeyPairSync("ec", { namedCurve: "P-256" });
const msg = Buffer.from("same message, twice");

const a = sign("sha256", msg, privateKey);
const b = sign("sha256", msg, privateKey);

console.log(a.equals(b));
// false in node:crypto  -> random or hedged nonce
// true                  -> deterministic derivation (RFC 6979 or EdDSA-style)

バイト列が異なる場合、nonce が純粋にランダムなのかヘッジ付きなのかはわかりません。それを確定できるのはライブラリのドキュメントだけです。一致する場合は、出力を RFC 6979 の付録 A.2 の既知解ベクトルと照合し、独自実装ではなく RFC 6979 であることを確認してください。このサイトの ECDSA テストベクトル生成ツールはシードから P-256、P-384、P-521、secp256k1 の RFC 6979 署名を生成するため、後で同じベクトルをバイト単位で再生成できます。

• エントロピーが少ない場面を疑ってください。組み込みハードウェアの初回起動、共有スナップショットから復元された VM やコンテナ、エントロピープールにシードが供給される前の初期化段階は、ランダムな nonce が最も期待を裏切りやすい場面です。決定的署名なら、この問題自体がなくなります。
• 再利用が見つかったら、その鍵はもう失われています。弱くなったのではなく、その 2 つの署名を一度でも見たことのある人すべてに対して、さかのぼって失われています。資金を移動し、その鍵を使っているすべての場所で鍵をローテーションし、その鍵がこれまでに作成したすべての署名を、第三者が作成したものでありうるとみなしてください。

一次資料

• RFC 6979：DSA と ECDSA の決定的な使用法。HMAC-DRBG による導出、その根拠、付録 A の既知解ベクトル。フォールト攻撃に関する注意点は §3.6 に記載
• RFC 8032：EdDSA（Ed25519、Ed448）。決定的な nonce の導出が、オプションではなく方式の一部
• FIPS 186-5：ECDSA を規定し、決定的な nonce の生成も認める現行のデジタル署名標準
• Some SecureRandom Thoughts：Android Developers Blog、2013年8月14日。プラットフォームの PRNG の初期化の欠陥、Bitcoin ウォレットの侵害との関係、PRNGFixes による回避策
• Biased Nonce Sense：Breitner と Heninger、IACR ePrint 2019/023 / Financial Cryptography 2019。単に偏っているだけの nonce に対する格子攻撃と、実際のブロックチェーンとインターネット全体のデータによるその測定
• Console Hacking 2010：27C3。PlayStation 3 の定数 nonce による欠陥の公開実証
• BIP-62 と BIP-146：low-S 正規化（nonce ではなく展性の対策だが、復元した値に符号の補正が必要になることがある理由）。加えて、Taproot で義務付けられた決定的 nonce については BIP-340
• libsecp256k1 と @noble/curves：デフォルトで RFC 6979 を使う、広く監査された 2 つの実装。そのソースコードは、nonce の導出のあるべき姿を示す最もわかりやすいドキュメント

この nonce の要件が RSA に今も残る数少ない実運用上の利点の 1 つとなっている理由と、その他の点での 2 つのアルゴリズムの比較については、ECDSA と RSA の比較で解説しています。