メッセージ認証と電子署名

メッセージ認証と電子署名
濱野 健二
2008 年 12 月 16 日
1 認証
認証は２つに大別される．
• データの正当性の認証する．メッセージの改ざん検出．メッセージ認証（共通鍵暗号ベース）
と電子署名（公開鍵暗号ベース）
．電子署名は，データに対して責任を持つ者（署名作成者）も
認証する．
• 通信相手の正当性を認証する．なりすましの検出．相手認証．
2 メッセージ認証
Alice が Bob にメッセージ M を送るときに，認証子 S を付けて送る．Bob は認証子が正しいかど
うかを確認して，改ざん，なりすましを検出する．メッセージ認証コード（MAC）は，送受信者間
で鍵 K を共有する．Alice は，M を認証子生成関数 EK に通して認証子 S = EK (M ) を作る．Bob
は，メッセージと認証子 (M, S) を受け取る．Bob は Alice と同じ認証子生成関数 EK に M を入力
し，その出力 S ′ = EK (M ) が S に一致するかどうかを確認する．M が改ざんされていなければ，
S ′ = S となる．このとき，S は K を用いて作られたということになる．M が改ざんされているとき
は，S ′ は高確率で S と異なる．
EK の実現方法として，ハッシュ関数を使ったものと共通鍵暗号を使ったものを挙げることがで
きる．
ハッシュ関数 H : {0, 1}∗ → {0, 1}n は，
1. 一方向性：y が与えられたときに y = H(x) なる x を求めることが難しい．
2. 第 2 原像困難性：原像側の x が与えられたときに．H(x) = H(x′ ) なる x′ (̸= x) を求めること
が難しい．
3. 衝突困難性：H(x) = H(x′ ) なる x, x′ を求めることが難しい．
を満たす．攻撃者が最も手をつけやすいのは，衝突困難性である．EK (M ) = H(K||M ) は，安全で
1
ないことが示されている．HMAC は，ipad, opad を固定値としたとき，
EK (M ) = H(K ⊕ opad || H(K ⊕ ipad || M ))
である．
MAC は，次の 2 点が解決できない．
• 送受信者間の共有鍵を使わなければならないので，第３者が検証できない．
• 否認防止機能がない．Alice が，この文書に署名していないと主張しても，だれも Alice の力に
なれない．
よって，「Alice も Bob も絶対に信用できる」という場合にのみ MAC は有効である．
3 電子署名
電子署名は公開鍵暗号ベースである．署名用の鍵 KS と検証用の鍵 KV がある．KS は秘密にし
て，KV は公開する．Alice は，M, KS を署名生成関数に入力して，電子署名 S を作る．Bob は
S, KV を検証関数に入力して，M が改ざんされていないか確認する．
電子署名は，第３者が検証可能で，否認防止機能がある．
電子署名には，落とし戸つき一方向性関数を利用したものと認証方式から変換されるものとがある．
3.1 落とし戸つき一方向性関数を利用した電子署名
落とし戸つき一方向性関数 f の落とし戸は秘密情報なので，落とし戸が署名鍵になる．一方向性
関数の落とし戸を使った逆写像が署名生成関数になり，だれもが容易に行える一方向性関数の順写
像が検証関数になる．署名を σ ，ハッシュ関数を H とすると，σ = f −1 (H(M )) である．Alice は，
(M, σ) を Bob に送り，Bob は，h = H(M ) を計算して，h = f (σ) になるかを確認する．検証関数
のパラメタである KV は公開されているので，だれもが署名を検証できる．RSA 署名では，f −1 が
RSA 暗号の復号処理になり，f が暗号化処理になる．
3.2 認証方式から変換される電子署名
電子署名を使うと，
• 署名者は正しいか？（署名者は秘密鍵を持っているか？）
• メッセージが改ざんされていないか？
を確認することができる．署名者が秘密鍵をちゃんと持っているということは，相手認証に他ならな
い．よって，相手認証にメッセージの改ざん防止機能をつけたタイプの電子署名を考えることがで
きる．
2
3.2.1
Schnorr 署名
素数を p, q とする．ただし，q|(p − 1) とする．署名鍵 s ∈ Zq を定める．Zp∗ で位数が q となる元
g を定め，検証鍵 v = g s mod p を定める．メッセージを m とする．署名作成は次のようにする．ま
ず，r ∈ Zq をランダムに決めて，c = H(m, g r mod p) を計算する．次に，y = r + cs mod q を計算
する．署名を (c, y) とする．署名検証は次のようにする．g r = g y−cs = g y (g s )−c = g y v −c であるの
で，c = H(m, g y v −c mod p) が成り立つかどうかを確認する．
認証的に考えると，電子署名をする Bob と文書を持っている Alice との間のやりとりと考えること
ができる．文書を m，電子署名する人の持っている秘密鍵を s，検証鍵を y(= g s mod p) とする．
1. Bob → Alice: r ∈ Zq をランダムに選び，a = g r mod p を送る．
2. Alice → Bob: c = H(m||a) をチャレンジとして送る．
3. Bob → Alice: 秘密鍵 s を使って b = r − cs を計算して送る．
(c, b) が m に対する電子署名となる．検証するときは，g b = g r (g s )−c = ay −c より，a = g b y c であ
るから，c = H(m||g b y c ) が成り立つかをチェックすればよい．
3.2.2
DSA 署名
素数を p, q とする．ただし，q|(p − 1) とする．Zp∗ で位数が q となる元 g を定める．x ∈ Zq を定
め，y = g x mod p を計算する．秘密鍵は x，公開鍵は y, g, p, q である．署名生成は次のようにする．
k ∈ Zq をランダムに決めて，r = (g k mod p) mod q を計算する．次に，t = (k −1 (H(m)+xr)) mod q
−1
を計算し，(r, t) を署名とする．署名検証は，r = (g H(m)t
y rt
−1
mod p) mod q が成り立つかどうか
を確認する．
参考文献
[1] 岡本，山本, 現代暗号, シリーズ／情報科学の数学, 産業図書, 東京, 2003.
[2] 國廣, 情報符号化理論 II 講義資料.
3