q q 情報セキュリティ 第８回：２００５年６月３日（金） q q

本日学ぶこと メッセージ認証 一方向ハッシュ関数 メッセージ認証コード ディジタル署名（デジタル署名） いずれも，正真性・完全性に関する技術

機密性・正真性と暗号技術 機密性 正真性（完全性） アルゴリズム秘匿 による暗号 鍵なし 一方向ハッシュ関数 共通鍵 対称暗号 メッセージ認証コード 非対称鍵 公開鍵暗号 ディジタル署名

一方向ハッシュ関数：準備 表記 メッセージとハッシュ値について h : ハッシュ関数 m, n, x : メッセージ（ハッシュ関数の入力） h(m), h(n), h(x) : ハッシュ値（ハッシュ関数の出力） メッセージとハッシュ値について メッセージ空間は一般に無限集合 ハッシュ値空間は有限集合 ビット長を固定とすることが多い SHA1なら，160ビットのビット列なので， ハッシュ値空間の大きさは 2160

一方向性とは 任意のメッセージmに対してh(m)を計算するのは容易であるが，任意に与えられたh(m)から，mを求めることができない． 集合 Hm={x | h(x)=h(m)} を求めることは原理的に可能であるが，無限集合かもしれないし，mそのものを求めることは不可能．Hmの要素を一つ求めることは，弱衝突耐性に関する話． Hm= {x | h(x)=h(m)} メッセージ 空間 m hとh(m)によって決まる集合 ハッシュ値 空間 h(m)

弱衝突耐性とは 与えられたh(m)から，h(m)=h(n)を満たすメッセージnを求めることができない． m=nか否かは問わない． 原理的に求めることができるので，実用上は「計算量的に困難」であることを示せばよい．

弱衝突耐性を破る攻撃（教科書pp.184-186） Hm= {x | h(x)=h(m)} m:百万円契約書 （アリス作成） メッセージ 空間 一億円契約書 （マロリー作成，たくさん） マロリーが目標とする 一億円契約書 n ハッシュ値 空間 h(m)=h(n)

強衝突耐性とは m≠nかつh(m)=h(n)を満たすメッセージm,nを求めることができない． hが単射 ⇔ Hm={m} 通常使う一方向ハッシュ関数では，メッセージ空間（の部分集合）はハッシュ値空間よりも大きいので，単射とならない．

強衝突耐性を破る攻撃（教科書pp.186-188） 百万円契約書 （マロリー作成，たくさん） 一億円契約書 （マロリー作成，たくさん） メッセージ 空間 m,n：マロリーが目標と する契約書 ハッシュ値 空間 h(m)=h(n)

公開鍵暗号とディジタル署名の数式表現 RSA暗号方式 RSAディジタル署名方式 暗号化：C = Enc(pub, M) = ME mod N 復号：M = Dec(pri, C) = CD mod N RSAディジタル署名方式 署名：S = Sign(pri, M) = MD mod N 検証：M = Ver(pub, S) = SE mod N RSAでは，暗号化も復号も署名も検証も「メッセージをべき乗して剰余を求める」 ElGamalなど，他の暗号アルゴリズムでは必ずしも成立しない．

プライベート鍵で署名した署名文は 対応する公開鍵でのみ正しく検証できる ディジタル署名の方法１（１） 署名文復元法 教科書Fig.9-2（p.214）の，より適切な図 プライベート鍵で署名した署名文は 対応する公開鍵でのみ正しく検証できる （署名文の検証） （ディジタル署名） （署名文の作成） メッセージ 公開鍵で 復元 署名文 プライベート 鍵で署名 メッセージ 公開鍵 公開鍵ペア プライベート 鍵

ディジタル署名の方法１（２） 教科書Fig.9-2（p.214）に数式を当てはめる M' Verify S Sign M pub pri （署名文の検証） （ディジタル署名） （署名文の作成） M' Verify S Sign M pub 公開鍵ペア pri S = Sign(pri, M) M' = Verify(pub, S) = Verify(pub, Sign(pri, M))

ディジタル署名をどう活用する？ 復元の結果，意味のあるメッセージが得られたら，この署名文は適切な鍵で署名されたと判断する． ⇒ 署名文復元法 復元の結果と，公開もしくは送信されたメッセージとを照合し，同じ内容ならば，この署名文は適切な鍵で署名されたと判断する． ⇒ 認証子照合法 認証子照合法では，メッセージはランダムな値でもよい． 「署名文の送信者はプライベート鍵（秘密鍵）を所有している」と考えてはいけない． 再生攻撃の可能性あり！

ディジタル署名の方法２ 教科書Fig.9-5（p.217）に数式を当てはめる M M pri S S pub M' = M? M' 認証子照合法 教科書Fig.9-5（p.217）に数式を当てはめる M M 等しくなかったら， 適切なプライベート鍵で署名されていない 通信路中で改ざんが起こった pri Sign S S pub Verify M' = M? M' S = Sign(pri, M) M' = Verify(pub, S) = Verify(pub, Sign(pri, M))

ディジタル署名の方法３ 教科書Fig.9-6（p.219）に数式を当てはめる M M S pri pub S M' M' = h(M)? これも，認証子照合法 教科書Fig.9-6（p.219）に数式を当てはめる M M 等しくなかったら， 適切なプライベート鍵で署名されていない 通信路中で改ざんが起こった h h h(M) S h(M) pri Sign pub Verify M' = h(M)? S M' S = Sign(pri, h(M)) M' = Verify(pub, S) = Verify(pub, Sign(pri, h(M)))

以下余談 知ってほしいこと 無限集合といっても，一般にその各要素は「有限の長さで記述できる」こと 解を求めることが「原理的に可能」な実例 「原理的に可能」と言うときはたいてい，「現実的には困難」と続く．

0, 1, 00, 01, 10, 11, 100, 101, … ビット列が無限集合であるとは とビット列を並べることで 1ビット 2ビット 3ビット とビット列を並べることで 重複なくビット列を列挙できる． この系列のx番目のビット列を求めることができる． ビット列mが，この系列の何番目にあるかを求めることも できる． この系列はいくらでも書くことができる． ⇒ 無限集合 しかしこの系列に出現するどの要素も，長さ有限のビット列 である．

一方向性・弱衝突耐性の破り方 入力： ハッシュ関数h，ハッシュ値M = h(m) 出力： 集合 {x | h(x) = M}，またはその要素の一つ 方針 ビット列の（無限）系列の各要素を小さいものから順に取り出し（xとする），h(x) を求め，それが M と等しいか判定する． 等しければ，その x を出力する．（一つだけでいいなら，ここで終了） 計算できる？ 計算理論では，「帰納的可算」と呼ばれる（ただし「帰納的」ではない）． 一方向ハッシュ関数では，終了するまでの時間はハッシュ値空間に比例するので，この空間を大きくすればよい．

強衝突耐性の破り方 入力： ハッシュ関数h 出力： 集合 {x,y | x≠y, h(x)=h(y)}，またはその要素の一つ 方針 自然数の集合をNと書くとき，N×N = {(a,b) | a∈N, b∈N} は N と１対１に対応する．すなわち，N×Nの各要素を順に漏れ なく列挙可能． そこで，N×Nの要素(a,b)を順に漏れなく取り出し， ビット列の系列のa番目の要素xおよびb番目の要素yに対して， x≠y かつ h(x)=h(y)であるかを評価すればよい． 計算できる？ 計算理論としては，これも帰納的可算． 実用上は，ビット列x,yをランダムに生成するほうが簡便．