Presentation is loading. Please wait.

Presentation is loading. Please wait.

Q q 情報セキュリティ 第7回:2006年6月2日(金) q q.

Similar presentations


Presentation on theme: "Q q 情報セキュリティ 第7回:2006年6月2日(金) q q."— Presentation transcript:

1 q q 情報セキュリティ 第7回:2006年6月2日(金) q q

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

3 本日の授業で学ぶ語句 一方向ハッシュ関数,指紋,完全性,ハッシュ値,衝突, 弱衝突耐性,強衝突耐性,一方向性,メッセージダイジェスト,MD5,SHA-1,誕生日攻撃 メッセージ認証コード(MAC),なりすまし,HMAC ディジタル署名,署名と検証,署名文復号法,認証子照合法,第三者検証,否認防止 一方向ハッシュ関数,メッセージ認証コード,ディジタル署名は改竄を検出できる. メッセージ認証コードは,鍵を共有する当事者間で(のみ) メッセージの完全性を検証できる. ディジタル署名は第三者による検証ができる.

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

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

6 一方向性とは 任意のメッセージ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)

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

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

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

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

11 一方向ハッシュの利用例(MD5)(1) ここをクリックで ファイルを ダウンロード ここをクリックで MD5のハッシュ値 が入手できる

12 一方向ハッシュの利用例(MD5)(2) 確認方法(LinuxまたはCygwin)
httpd tar.gz をダウンロードし,適当なディレクトリに置く. 端末(シェル)を起動し,上記のディレクトリに移動する. 「md5sum httpd tar.gz」を実行すると,ハッシュ値として,32文字(128ビット)の16進文字列が出力される. ブラウザで[MD5]をクリックして,ハッシュ値を比較する. 同じならば,誤りなく送信できたと推定できる. 異なっていれば,ダウンロードに失敗した恐れがあり,最初からやり直す. この方法でファイルの完全性を確認できるが,改竄されている可能性は否定できない. man-in-the-middle攻撃により,http tar.gzとハッシュ値の両方を他のデータに取り替えているかもしれない!

13 公開鍵暗号とディジタル署名の数式表現 RSA暗号方式 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など,他の暗号アルゴリズムでは必ずしも成立しない.

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

15 ディジタル署名の方法1(2) 教科書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))

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

17 ディジタル署名の方法2 教科書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))

18 ディジタル署名の方法3 教科書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)))

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

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

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

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


Download ppt "Q q 情報セキュリティ 第7回:2006年6月2日(金) q q."

Similar presentations


Ads by Google