ハッシュ関数とは？

ハッシュ関数の意味

キーの値から格納位置（ハッシュ値）を計算する関数。同じキーからは必ず同じ値が得られ、異なるキーはできるだけ均等に散らばることが望ましい。剰余（mod）を使う方式が代表的で、FEでは与えられた式で位置を計算させる問題が頻出。

ハッシュ関数の具体例

「キーを配列サイズ13で割った余り」を位置とすると、キー100は100÷13の余り9で位置9に入る。配列サイズには2の累乗より素数を選ぶほうが偏りにくい。文字列キーなら各文字コードの和を取ってから剰余を取る方式が使われる。

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

ハッシュ値からは元のキーを復元できないが、これは暗号学的な一方向性とは別の話で、探索用ハッシュに求められるのは「速さと均等な分散」である。異なるキーが同じ値になること自体は避けられない、という点も重要。

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

• ハッシュ探索
• シノニム
• チェイン法

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

• メッセージ認証符号におけるメッセージダイジェストの利用目的はどれか。

  正解：メッセージが改ざんされていないことを確認する。

  要点：メッセージダイジェストはハッシュ値の照合で改ざんを検出する

  メッセージダイジェストは、メッセージ全体をハッシュ関数にかけて得られる固定長の値である。内容が1ビットでも変わればダイジェストも変わるので、送受信の両側で計算した値を突き合わせれば改ざんの有無を検出できる。メッセージ認証符号はこの性質を鍵と組み合わせて利用する。

  出典：平成28年度 秋期 基本情報技術者試験 午前 問38（IPA）

• 公開鍵暗号方式の暗号アルゴリズムはどれか。

  正解：RSA

  要点：RSAは公開鍵暗号、AESは共通鍵、SHA-256はハッシュ

  RSAは大きな整数の素因数分解が困難であることを安全性の根拠とする公開鍵暗号方式で、暗号化と復号に別々の鍵を使います。共通鍵暗号は暗号化と復号に同じ鍵を使う方式、ハッシュ関数は元に戻せない要約値を作る関数であり、いずれも公開鍵暗号ではありません。

  出典：平成29年度 春期 基本情報技術者試験 午前 問40（IPA）

• 表探索におけるハッシュ法の特徴はどれか。

  正解：キーの関数値によって格納場所を決める。

  要点：ハッシュ法はキーの関数値で格納位置を決め、衝突対策が要る

  ハッシュ法は、キーにハッシュ関数を適用して得た値から格納位置を直接決める方式である。キーを比較しながら探すのではなく計算で位置が求まるため、理想的にはデータ件数によらず一定時間で探索できる。ただし異なるキーが同じ位置に割り当てられる衝突（シノニム）は起こり得るので、チェイン法やオープンアドレス法などの対策が必要になる。

  出典：平成30年度 春期 基本情報技術者試験 午前 問7（IPA）

• 10進法で5桁の数a1 a2 a3 a4 a5を、ハッシュ法を用いて配列に格納したい。ハッシュ関数をmod(a1＋a2＋a3＋a4＋a5, 13)とし、求めたハ…

  正解：2

  要点：ハッシュ値は「桁の総和 mod 除数」で機械的に求める

  ハッシュ関数は各桁の数字の合計を13で割った余りと定義されている。54321の各桁は5、4、3、2、1なので合計は15、15を13で割ると商1・余り2となる。したがって格納位置は2である。

  出典：令和1年度 秋期 基本情報技術者試験 午前 問10（IPA）

• ファイルの提供者は、ファイルの作成者が作成したファイルAを受け取り、ファイルAと、ファイルAにSHA-256を適用して算出した値Bとを利用者に送信する。そのとき…

  正解：ファイルAにSHA-256を適用して値を算出し、その値と値Bを比較することによって、ファイルAの内容が改ざんされていないかどうかを検証できる。

  要点：ハッシュ値の突合せで分かるのは改ざんの有無だけ

  SHA-256はハッシュ関数であり、同じ入力からは必ず同じ値が得られ、内容が少しでも変われば値が大きく変わる。値Bが正しいものだと電話で確認できているので、受け取ったファイルから自分でハッシュ値を計算し、値Bと一致するかを見れば改ざんの有無が分かる。ただしハッシュ値だけでは作成者が誰かは分からず、また元の内容を復元する能力も無い。

  出典：令和1年度 秋期 基本情報技術者試験 午前 問40（IPA）