デジタル署名


デジタル署名の機能

デジタル署名は

メッセージの真正性を、誰もが検証できる形で、保証する電子データ
である。

各自は自分用の署名鍵と検証鍵の組をもつ。

署名鍵はメッセージの署名を生成するのに用い、検証鍵は署名を検証するに用いる。
署名鍵は秘密に保管し、検証鍵は公開する。

実際にメッセージに署名を添付して送るには、以下のようにする。

  1.  送信者 Alice は自分の検証鍵 pkA を公開しておく。
  2.  Alice は、自身の署名鍵 skA を用い、メッセージ m の署名 σ を生成し、メッセージ m とともに受信者 Bob に送る。
  3.  メッセージと署名の対 (m, σ)を受け取った Bob は、Aliceの検証鍵 pkA を入手し、それを用いて対 (m, σ)の正当性を確認する。

Aliceの署名鍵 skA は秘密に保管され、検証鍵 pkA は公開されているので、
  • 署名検証は Bob を含めてだれにでもできる。
  • 署名生成は、署名鍵を知っている、Alice にしかできない。
ということが期待される。

これが本当に正しいのなら、
  • 受信者 Bob から見て、受け取ったメッセージは確かに Alice が署名したと確信でき、
  • 送信者 Alice から見ると、メッセージに署名したという事実を、Bobのみならず第3者に対しても否定できないことになる。



デジタル署名の定義

デジタル署名は、鍵生成アルゴリズム Gen、署名生成アルゴリズム Sign そして署名検証アルゴリズム Vrfy の3つの効率的なアルゴリズムの組である。

鍵生成アルゴリズム Genは、セキュリティパラメータ k を入力すると検証鍵 pk と署名鍵 sk の組を出力する:
(pk, sk)  ←  Gen(k).

署名生成アルゴリズム Signは、署名鍵 sk とメッセージ m を入力すると署名σを出力する:
σ ← Sign(sk, m).

署名検証アルゴリズム Vrfy は、検証鍵 pk とメッセージ m と署名σを入力とし、0または1を出力する(0はNG、1はOK):
0/1 ← Vrfy(pk, m, σ).

ただし、

完遂性:

Gen によって生成された任意の鍵ペア (pk, sk) と任意のメッセージ m に対して
  • Vrfy(pk, m, Sign(sk, m))  =  1
でなければならない。

また、安全性条件として

偽造不可能性:

どのような効率的なアルゴリズム F も、(署名鍵 sk を知らずに)検証鍵 pk だけを用いて、与えられたメッセージ m に対して妥当な署名σをつくることはできない
ことが必要である。

デジタル署名を作るとは、完全性と偽造不可能性を同時に満たす3つのアルゴリズムの組 (Gen, Sign, Vrfy) を求めることに他ならない。



RSA 署名

RSA 署名 RSA = (Gen, Sign, Vrfy) は、RSA 関数
  • y = RSAn,e(x) = xe mod n
を利用して、以下のように構成される。


鍵生成アルゴリズム Gen(k) :

それぞれ k ビットの異なる素数 p, q を生成する。
  • n = p・q,  l = φ(n) = (p-1)・(q-1)
とし、
  • e・d ≡ 1 (mod l)
となる e, d を生成する。
(n, e) を検証鍵 pk とし、(n, d) を署名鍵 sk とする。


署名生成アルゴリズム Sign(sk=(n,d), m) :

署名鍵 sk から n, d を取り出して、
  • σ = md mod n
を計算し、σを出力する。


署名検証アルゴリズム Vrfy(pk=(n,e), m, σ) :

検証鍵 pk から n, e を取り出して、
  • m' = σe mod n
を計算する。結果 m' が m に等しければ 1 を、異なれば 0 を出力する。

RSA署名の完遂性はオイラーの定理から、偽造不可能性は、RSA仮定そのものである。




RSA 署名の問題点

上に見たように、RSA 署名は与えられたメッセージ m に対して偽造不可能性をもつ。すなわち、どのような(署名鍵をもたない、効率的な)敵も与えられた m に対して
  • σe ≡ m   (mod n)
となるσを生成することはできない。

しかし、

与えられた m に限らず、とにかく検証式 σe ≡ m   (mod n) を満足するような対 (m,σ) ならすべて偽造と認めるならば(このような偽造を存在的偽造と呼ぶ)、RSA 署名はいくらでも偽造可能である。

実際、
  • σをランダムに生成し、
  • m = σe mod n を計算し、
  • 対 (m,σ) を出力
すればよい。

また、アプリケーションによっては、

敵が自ら選んだいくつかのメッセージに対する正当な署名を何らかの手段で入手できるような場合
があり得る。このような状況における攻撃(選択メッセージ攻撃)では、RSA署名は与えられた m に対してさえ偽造可能である。

実際、

RSA署名に対し、敵 F は次にようにして、(自分で選んだ)たった 2 つのメッセージ m1, m2 に対する署名σ12を入手すれば、与えられたメッセージ m の署名σを偽造できる。

敵 F は検証鍵 pk=(n,e) とメッセージ m を入力として受け取り、次のように動作する:

  • まず、乱数 r を生成し、m1 = m・r mod n を求め、
  • m1 の正当な署名 σ1を入手する。
  • 次に、m2 = r-1 mod n を計算し、
  • m2 の正当な署名 σ2 を入手する。
  • 最後に、積 σ = σ1・σ2 mod nを計算し、対 (m, σ) を出力する。

この対 (m, σ) に対し、
  • σe ≡ (σ1 σ2)e ≡ σ1e σ2e ≡ m1 m2 ≡ m ( mod n )
となるので、対 (m, σ) は妥当である。



選択メッセージ攻撃における存在的偽造不可能性


RSA署名は存在的偽造を防げないこと、また、選択メッセージ攻撃においては(存在的とも限らない)偽造そのものを防げないことを見た。

実はRSA署名は、選択メッセージ攻撃において存在的偽造すらもできないよう、強化することができる。

その前に、「選択メッセージ攻撃において存在的偽造すらできない」ということを、敵 F と挑戦者 C との間の署名偽造ゲームで定式化する。


署名偽造ゲーム:

  1. まず、挑戦者 C が 鍵ペア (pk, sk) ← Gen(k) をつくり、 検証鍵 pk のみを敵 F に渡す。
  2. 検証鍵 pk を受け取った敵 F は、何らかの計算をして、メッセージ miを選び、挑戦者 C に渡す。
  3. 挑戦者 C は署名鍵 sk を用いて メッセージ mi の署名 σi ← Sign(sk, mi) を計算し、Fに渡す。
  4. このような メッセージ mi と 署名σi の交換を、敵 F は挑戦者 C との間で好きなだけ繰り返す。
  5. 最後に、敵 F は、何らかのメッセージと偽造署名の対 (m, σ) を出力する。
  6. もしも m がどの mi とも異なり、σが m の妥当な署名ならば、敵 F の勝ち(そうでないなら挑戦者 C の勝ち)とする。

署名偽造ゲームで、どんな敵 F もほとんど 0 に等しい確率でしか勝てないならば、デジタル署名 (Gen, Sign, Vrfy) は 選択メッセージ攻撃において存在的偽造不可能であると呼ぶ。




RSA-FDH 署名


RSA 署名において、メッセージにハッシュ関数
  • H : {0,1}* → Zn
を施すことで、より偽造が困難なRSA-FDH署名が得られる。

RSA-FDH 署名:

鍵生成アルゴリズム Gen(k):
/* RSA署名と同じ */

それぞれ k ビットの異なる素数 p, q を生成する。
  • n = p・q,  l = φ(n) = (p-1)・(q-1)
とし、
  • e・d ≡ 1 (mod l)
となる e, d を生成する。
(n, e) を検証鍵 pk とし、(n, d) を署名鍵 sk とする。


署名生成アルゴリズム Sign(sk=(n,d), m):

署名鍵 sk から n, d を取り出して、
  • σ = H(m)d mod n
を計算し、σを出力する。


署名検証アルゴリズム Vrfy(pk=(n,e), m, σ) :

検証鍵 pk から n, e を取り出して、
  • h' = σe mod n
を計算する。結果 h' が h = H(m) に等しければ 1 を、異なれば 0 を出力する。


RSA-FDH署名には、RSA署名に有効だった先の攻撃はうまくいかない。

まず、存在的偽造について見る。

先と同様に、σをランダムに生成し、h = σeとする。偽造を完成させるにはこの h に対して、さらに
  • h = H(m)
となる m を求める必要がある。

しかし、これはハッシュ関数の原像困難性より不可能。

また、先の選択メッセージ攻撃も、ハッシュ関数の衝突困難性を考慮すると、
  •  H(m) = H(m1) H(m2)
となることは期待できず、うまくいかない。

以上から、RSA-FDH署名に対しては、RSA署名に有効だった先の攻撃は通用しないことがわかった。しかし、だからといって、「どのような選択メッセージ攻撃を受けても存在的な偽造は不可能」と云い切れるだろうか?

ランダムオラクルモデルと呼ばれる仮想的な世界を設定すれば、そういえる:


RSA仮定が正しいならば、RSA-FD H署名は、ランダムオラクルモデルのもとで、選択メッセージ攻撃において存在的偽造不可能である。


ランダムオラクルモデルとは、アルゴリズムの実行モデルであり、各アルゴリズムにおける

ハッシュ関数 H(・) の実行を、ランダムオラクル OH への問い合わせに置き換えてしまう
モデルである。

ここで、ランダムオラクル OH とは、入力 m を受け取ると、m に対して乱数 h (← Zn) を割り当てて値 H(m) として返す、オラクルである。



付録


シュノア署名
シュノア署名は、離散対数ベースのデジタル署名である。

[部品]
  • 群生成アルゴリズム GenG
  • ハッシュ関数 H : {0,1}* → {0,1}l

[スキーム]
鍵生成アルゴリズム Gen(k) :

  • (q, g) ← GenG(1k) 
  • x ← Zq, X = gx
  • vk = (q, g, X), sk = (q, g, x).

署名生成アルゴリズム Sign(sk = (q,g,x), m) :

  • y ← Zq, Y = gy
  • c = H(m, Y), z = y + c x mod q
  • return σ=(c,z).

署名検証アルゴリズム Verify(vk = (q,g,X), m, σ = (c, z)) :

  • Y = gzX-c
  • return c =? H(m, Y).


離散対数仮定が成り立つならば、ランダムオラクルモデルのもとで、シュノア署名は適応的選択文書攻撃に対し存在的偽造不可能。












最終更新:2010年05月27日 15:16