q q 情報セキュリティ 第10回:2004年6月11日(金) の補足 q q 一方向ハッシュ関数の持つべき性質 一方向性 弱衝突耐性 強衝突耐性 2 準備 表記 q q q h : ハッシュ関数 m, n, x : メッセージ(ハッシュ関数の入力) h(m), h(n), h(x) : ハッシュ値(ハッシュ関数の出力) メッセージとハッシュ値について q q メッセージは一般に無限集合 ハッシュ値は無限集合でもよいが,実用上は 有限集合(ビット長が有限)とする. 3 一方向性とは 任意のメッセージmに対してh(m)を計算するのは容易である が,任意に与えられたh(m)から,mを求めることができない. q 集合 Hm={x | h(m)=h(x)} を求めることは原理的に可能である が,無限集合かもしれないし,mそのものを求めることは不可能. Hmの要素を一つ求めることは,弱衝突耐性に関する話. メッセージ 空間 ハッシュ値 空間 Hm= {x | h(m)=h(x)} m h(m) 4 弱衝突耐性とは 与えられたh(m)から,h(m)=h(n)を満たすメッセージnを求め ることができない. q q m=nか否かは問わない. 原理的に求めることができるので,実用上は「計算量的に困 難」であることを示せばよい. 5 弱衝突耐性を破る攻撃(教科書pp.184-186) Hm= {x | h(m)=h(x)} m:百万円契約書 (アリス作成) メッセージ 空間 一億円契約書 (マロリー作成,たくさん) マロリーが目標とする 一億円契約書 n ハッシュ値 空間 h(m)=h(n) 6 強衝突耐性とは m≠nかつh(m)=h(n)を満たすメッセージm,nを求めることがで きない. q hが単射でなければ,原理的に求めることができるので,実用 上は「計算量的に困難」であることを示せばよい. (参考:hが単射 ⇔ Hm={m}) 7 強衝突耐性を破る攻撃(教科書pp.186-188) メッセージ 空間 百万円契約書 (マロリー作成,たくさん) 一億円契約書 (マロリー作成,たくさん) m,n:マロリーが目標と する契約書 ハッシュ値 空間 h(m)=h(n) 8
© Copyright 2025 ExpyDoc