デジタル署名スキームの内部（RSA-PSS・ECDSA・EdDSA）

署名スキームが満たすべき安全性ゴール

デジタル署名は「秘密鍵を持つ本人だけが作れ、公開鍵を持つ誰もが検証できる」短いデータです。暗号の基礎 で触れたとおり、署名は完全性・認証・否認防止を一度に与えます。ただし「破られない」をきちんと定義しないと、どのスキームが安全かを論じられません。現代暗号の標準的なゴールが EUF-CMA（Existential Unforgeability under adaptive Chosen-Message Attack、適応的選択文書攻撃下での存在的偽造不可能性）です。

ゲームで表すと次のようになります。攻撃者は公開鍵を受け取り、自分の選んだ任意の文書について署名を作ってもらえる（署名オラクルへのアクセス）。それを好きなだけ、前の結果を見て次を選ぶ形（適応的）で繰り返してよい。それでもなお、一度も署名を要求していない新しい文書 m* に対する有効な署名 (m*, σ*) を作れないなら、そのスキームは EUF-CMA 安全です。

RSA-PSS：確率的パディングで安全性を証明可能に

RSA の数理 で見たとおり、素の RSA 署名 σ = m^d mod n には準同型性（σ1·σ2 ≡ (m1·m2)^d）があり、署名の掛け合わせで偽造ができてしまいます。これを潰す古典的方法が PKCS#1 v1.5 の決定的パディングですが、安全性の形式証明がつきません。現在推奨されるのが RSA-PSS（Probabilistic Signature Scheme）です。

PSS の核心は 署名ごとにランダムなソルト（salt）を混ぜて、エンコード結果を確率的にする ことです。流れはこうです。

署名（EMSA-PSS エンコード）:
  mHash = Hash(m)
  salt  = ランダムバイト列（毎回新規）
  M'    = (0x00 を8バイト) || mHash || salt   # 内部メッセージ
  H     = Hash(M')
  DB    = padding || 0x01 || salt
  maskedDB = DB XOR MGF1(H)                    # MGF でマスク
  EM    = maskedDB || H || 0xbc
  σ     = EM^d mod n                           # ここで初めて RSA 冪乗

検証側は σ^e mod n で EM を復元し、H と maskedDB から salt を取り出し、同じ手順で H を再計算して一致を確認します。重要な性質が二つあります。第一に、同じ文書でも salt が毎回違うため 署名は毎回変わる（確率的）。第二に、PSS はランダムオラクルモデルで EUF-CMA 安全性が証明されており、その帰着が PKCS#1 v1.5 よりタイトです。MGF1 は ハッシュ関数の内部 で扱うハッシュを使ったマスク生成関数で、出力を擬似ランダムに広げる役割を担います。

ECDSA：署名生成・検証と nonce の役割

楕円曲線上の署名が ECDSA です。楕円曲線暗号（ECC）の原理 の群演算の上に載ります。曲線の生成点 G、その位数 n、秘密鍵 d、公開鍵 Q = dG を前提に、文書 m への署名 (r, s) を次で作ります。

署名（秘密鍵 d で）:
  e = Hash(m) を整数化（先頭 bits を使う）
  k = 1 .. n-1 のランダムな秘密値（nonce, 毎回新規）
  R = kG                       # 曲線上の点
  r = R.x mod n                # R の x 座標
  s = k^(-1) * (e + r*d) mod n
  署名 = (r, s)                # r=0 や s=0 なら k を引き直す

検証（公開鍵 Q で）:
  w  = s^(-1) mod n
  u1 = e*w mod n
  u2 = r*w mod n
  P  = u1*G + u2*Q             # 点演算
  有効 ⇔ P.x mod n == r

検証が成立する理由は代入で追えます。s = k^(-1)(e + r d) を変形すると k = s^(-1)(e + r d) = u1 + u2·d（mod n）。両辺に G を掛けると kG = u1·G + u2·(dG) = u1·G + u2·Q = P。よって P = kG = R となり、P.x mod n が r に一致します。ここで決定的に重要なのが k（nonce）が文書ごとに秘密かつランダムでなければならない 点です。s の式に k と d が同居しており、k が漏れると d が一発で解けてしまいます。

nonce 漏洩の致命性：方程式一本で秘密鍵が解ける

ECDSA の s の式を d について解くと、k さえ分かれば秘密鍵が即座に求まります。

s = k^(-1)(e + r*d) mod n
⇔ d = (s*k - e) * r^(-1) mod n      # k が既知なら d が確定

つまり たった一つの署名でも、その k が漏れれば秘密鍵 d は終わり です。さらに恐ろしいのは、k の値そのものを知らなくても、同じ k を二つの異なる文書で再利用 すると d が解けることです。(r, s1) と (r, s2)（r が同じなら同じ k）について、

s1 = k^(-1)(e1 + r*d),  s2 = k^(-1)(e2 + r*d)
s1 - s2 = k^(-1)(e1 - e2)
⇒ k = (e1 - e2) / (s1 - s2) mod n   # まず k が求まり
⇒ d = (s1*k - e1) * r^(-1) mod n    # 次に d が求まる

未知数2つ（k, d）に対し独立な式が2本立つので、連立方程式として解けてしまうわけです。

EdDSA：決定論的 nonce という設計判断

ECDSA の弱点は「毎回、高品質な乱数で k を作れること」に安全性が全面依存する点にあります。乱数源は壊れやすく（VM クローン、低エントロピー起動、実装バグ）、しかも壊れても署名は正常に見えるため事故に気づけません。EdDSA（Edwards-curve Digital Signature Algorithm、RFC 8032、代表が Ed25519）は、この依存そのものを設計で取り除きました。

中心的な判断が nonce を乱数で引かず、秘密鍵と文書から決定論的に導出する ことです。

鍵: 秘密シード sk から Hash で (a, prefix) を派生（a がスカラー秘密鍵）
署名:
  r = Hash(prefix || M) を整数化     # nonce を「決定論的に」生成
  R = r * B                          # B は基点
  k = Hash(R || A || M) を整数化     # A は公開鍵
  S = (r + k*a) mod L
  署名 = (R, S)                      # 64 バイト
検証:
  Hash(R || A || M) を整数化して k を再計算
  有効 ⇔ S*B == R + k*A

r が prefix（秘密鍵由来）と文書 M のハッシュで決まるため、同じ秘密鍵で同じ文書に署名すれば必ず同じ署名が出ます。乱数生成器が一切要りません。これにより ECDSA の k 再利用・低エントロピー事故が 原理的に発生不能 になります。異なる文書には異なる r が出るので再利用にもなりません。

三方式の設計思想を並べて見る

同じ「デジタル署名」でも、依存する困難性・乱数への態度・失敗モードが大きく異なります。

注意したいのは、EdDSA は ECDSA より「数学的に強い」わけではなく、同じ ECDLP に依存している 点です。違いは運用上の壊れにくさにあります。ECDSA は正しく乱数を扱えば安全ですが、その「正しく」が現場で守られにくい。EdDSA はその落とし穴を仕様レベルで塞いだ、いわば 誤用しにくい API としての設計勝利 です。資格試験でも「EdDSA の利点は決定論的 nonce による再利用事故の排除」と問われます。

まとめ

デジタル署名の安全性ゴールは EUF-CMA（任意文書の署名を取れても未署名文書を偽造できない）です。RSA-PSS は素の RSA の準同型性を確率的パディング（salt + MGF1）で潰し、ランダムオラクルモデルで証明可能な安全性を得ます。ECDSA は ECDLP に依存して短い鍵・署名を実現しますが、署名ごとの秘密 nonce k が漏洩・再利用・偏ると、s = k^(-1)(e + rd) の式から秘密鍵 d が方程式一本で解けてしまう致命的な弱点を持ちます。EdDSA は k を秘密鍵と文書から決定論的に導くことでこの事故を原理的に封じ、加えて定数時間実装の容易さや検証の高速化も得た総合設計です。

困難性の土台は RSA の数理 と ECC の原理、署名に使うハッシュは ハッシュ関数の内部、実装の堅牢さに直結する サイドチャネル攻撃 と合わせて押さえると、署名スキームの選定が原理から判断できるようになります。