ハッシュ関数とは？

ハッシュ関数の意味

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

ハッシュ関数の具体例

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

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

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

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

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

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

• データベースで管理されるデータの暗号化に用いることができ、かつ、暗号化と復号とで同じ鍵を使用する暗号化方式はどれか。

  正解：AES

  要点：AESは同じ鍵で暗号化と復号を行う共通鍵暗号

  暗号化と復号に同じ鍵を使うのは共通鍵暗号方式で、その代表がAESです。処理が高速なため、データベースに格納する大量のデータの暗号化に適しています。RSAは公開鍵暗号方式で鍵が異なり、SHA-256はハッシュ関数で復号できず、PKIは公開鍵を運用するための基盤で暗号アルゴリズムではありません。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問39（IPA）

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

  正解：199

  要点：剰余が等しいキーどうしの差は除数の倍数になる。

  剰余が等しい値どうしは差が除数の倍数になる。三つのキー値の差は1168−571=597、1566−1168=398、1566−571=995であり、これらの最大公約数は199である。597=199×3、398=199×2、995=199×5と割り切れるため、除数は199とわかる。

  出典：平成30年度 秋期 応用情報技術者試験 午前 問27（IPA）

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

  正解：a-bがnの倍数

  要点：同じ剰余になる条件は、2つのキーの差がnの倍数であること

  衝突とは異なるキーのハッシュ値が一致することなので、a mod n = b mod n が条件です。これは a と b を n で割った余りが等しい、すなわち a-b が n で割り切れる（nの倍数である）ことと同値です。合同式で書けば a≡b (mod n) です。

  出典：令和1年度 秋期 応用情報技術者試験 午前 問7（IPA）

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

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

  要点：一方向性はハッシュ値から元のメッセージを求められない性質

  原像計算困難性（一方向性）とは、あるハッシュ値が与えられたときに、それを出力する元のメッセージを現実的な計算量では求められないという性質である。この性質があるため、パスワードをハッシュ値で保管しても元のパスワードを逆算されにくい。

  出典：令和3年度 春期 応用情報技術者試験 午前 問40（IPA）

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

  正解：a－bがnの倍数

  要点：ハッシュ衝突は差がハッシュ表サイズの倍数になるとき

  衝突するのは h(a) = h(b)、つまり a と b を n で割った余りが等しいときです。余りが等しいことは差 a − b が n で割り切れることと同値なので、a − b が n の倍数であることが条件になります。

  出典：令和4年度 秋期 応用情報技術者試験 午前 問5（IPA）