ハッシュの暗号性の「第2原像計算困難性・衝突困難性」の違いを調べた
auです。
ハッシュについて勉強してみて、理想的なハッシュ関数の性質として、3つあることが分かりました。
Wikipediaにはそれぞれ、こう書いてあります。(強衝突耐性は衝突困難性に変更してます)
- 原像計算困難性: ハッシュ値 h が与えられたとき、そこから h = hash(m) となるような任意のメッセージ m を探すことが困難でなければならない。これは一方向性関数の原像計算困難性に関連している。この特性がない関数は（第1）原像攻撃に対して脆弱である。
- 第2原像計算困難性: 入力 m1 が与えられたとき、hash(m1) = hash(m2) となる（すなわち、衝突する）ような別の入力 m2（m1とは異なる入力）を見つけることが困難でなければならない。これを「弱衝突耐性」ともいう。この特性がない関数は、第2原像攻撃に対して脆弱である。
- 衝突困難性: hash(m1) = hash(m2) となるような2つの異なるメッセージ m1 と m2 を探し出すことが困難でなければならない。一般に誕生日のパラドックスによって、衝突困難性を持つためには、原像計算困難性を持つために必要なハッシュ値の2倍の長さのハッシュ値が必要である。
この3つです。
色々なサイトを見ても、2番目と3番目の違いがよくわからなかったのですが、理解できたので自分なりに要約してみます。ついでに1番も。
- 原像計算困難性: ハッシュ値から入力値を求めることが困難でなければならない
- 第2原像計算困難性: m1からのハッシュ値h1から、同じハッシュ値h1になるm2を求めることが困難でなければならない
- 衝突困難性: 同じハッシュ値になるm1とm2を求めるのは困難でなければならない
自分の解釈では、
第2原像計算困難性は、「m1が既知であり、未知のm2を求めることが困難」
衝突困難性は、「ハッシュ値が既知であり、未知のm1とm2を求めることが困難」
と思うことで、理解することができました。
