ハッシュ関数とは？

ハッシュ関数の意味

任意長のデータから固定長の値を生成する一方向性の関数。同じ入力からは常に同じ値が得られ、ハッシュ値から元のデータを逆算することは計算量的に困難。改ざん検知やパスワードの保存に使う。

ハッシュ関数の具体例

SHA-256が代表。ファイルの配布時にハッシュ値を併記し、受け取り側で再計算して一致を確認する。

ハッシュ関数は試験でどう引っ掛けられる？

一方向性＝「ハッシュ値から元のメッセージを求められない」、衝突困難性＝「同じハッシュ値になる別のメッセージを見つけられない」。定義の入替えに注意。レインボーテーブル攻撃は事前計算した対応表でハッシュを逆引きする手口で、ソルトの付加が対策になる。

ハッシュ関数と関連する用語

• ディジタル署名
• ソルト

ハッシュ関数が出た過去問

• 自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571, 1168, 1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したとこ…

  正解：199

  要点：同じ剰余になる除数は、キー値の差の公約数から求める

  三つのキー値が同じ除数nで同じ剰余になるということは、それらの差がすべてnの倍数になるということである。差を取ると1168-571＝597、1566-1168＝398、1566-571＝995となる。597＝3×199、398＝2×199、995＝5×199なので、最大公約数は199であり、これが使用した除数である。

  出典：平成30年度 秋期 高度共通_午前I試験 am1 問9（IPA）

• 暗号学的ハッシュ関数における原像計算困難性、つまり一方向性の性質はどれか。

  正解：あるハッシュ値が与えられたとき、そのハッシュ値を出力するメッセージを見つけることが計算量的に困難であるという性質

  要点：一方向性＝ハッシュ値から元のメッセージを逆算できない

  原像計算困難性（一方向性）とは、ハッシュ値だけが与えられたときに、そのハッシュ値になる入力メッセージを求めることが計算量的に困難であるという性質をいう。ハッシュ関数は求めるのは容易でも逆算はできないという一方向性を持つため、パスワードの保存などに利用される。

  出典：令和3年度 春期 高度共通_午前I試験 am1 問12（IPA）

• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x)＝x mod n とすると、任意のキーaとbが衝突する条件はどれ…

  正解：a－bがnの倍数

  要点：h(x)=x mod n の衝突条件は a−b が n の倍数

  ハッシュ関数がh(x)＝x mod nのとき、キーaとbが衝突するのはa mod n＝b mod n、すなわちaとbをnで割った余りが等しいときである。これはa−bがnで割り切れること、つまりa−bがnの倍数であることと同値である。

  出典：令和4年度 秋期 高度共通_午前I試験 am1 問3（IPA）

• ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで、複数のデータが同じハッシュ値になることはないものとする。

  正解：表の中のデータの個数によらず、データ1個当たりの探索時間が一定（横一直線）のグラフ

  要点：衝突のないハッシュ表の探索はデータ数によらずO(1)

  衝突が起こらない理想的なハッシュ表では、キーからハッシュ関数で格納位置を直接計算できるため、格納されているデータの個数に関係なく一定回数のアクセスで目的のデータに到達できる。すなわち計算量はO(1)であり、グラフは横軸に対して水平な直線になる。

  出典：令和5年度 春期 高度共通_午前I試験 am1 問6（IPA）

• 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n とすると、任意のキーaとbが衝突する条件は…

  正解：a-bがnの倍数

  要点：同じ剰余になる条件は二数の差が除数の倍数であること

  衝突するのはa mod n ＝ b mod n となるときである。両者をnで割った余りが等しいということは、その差a－bがnで割り切れる、すなわちnの倍数であることと同値である。

  出典：令和6年度 秋期 高度共通_午前I試験 am1 問3（IPA）