令和4年度秋期午前Ⅰ 問３についての考察と解法 - IPA（情報技術者試験）の午前対策

テーマ：ハッシュ表におけるデータ衝突条件

正解はこちら

解答：イ

[この問題が言いたいことを一言でいうと]

以下の式において、ハッシュ値が衝突する条件を求めよ。

デジタル署名など、改ざん検知の根幹を支える値だぜ！

自然数・・・・正の整数、０を超える数で有限であると説かれることが多いです。

ハッシュ・・・(データを)細切れにする(hash)を起源にする説が有力です。ちなみにハッシュドビーフは細切れにされた肉を入れている。

ハッシュ関数・・入力データを一定の手順で計算し、入力値のデータの長さに関わらず、決まった長さの文字列を出力する関数。今回の場合は x1=aを10、x2=bを101、 nを5としたときにh(x1) =0, h(x2) =1 となり、文字列としての長さは変わりません。

ハッシュの衝突が起きることを前提で考え、回答を導きます。

衝突発生状況を洗い出します。

a mod n = b mod n　（衝突発生時の状況）

ここでハッシュ値を　r　と置くと

a mod n = b mod n = r となります。

また、aを割ったときの商をp、bを割った時の商をqとするとaとbは以下のように表記可能です。

a=n×ｐ+r aをnで割ると商がp余りがrになる→aはnとpをかけrを足すことによって求められる　①

b=n×q+r bをnで割ると商がq余りがrになる→bはnとqをかけrを足すことによって求められる　②

①‐②を行います。

a-b=n×(p-q)

この式を見るとa-bがnの倍数であることがわかります。つまり、nがa-bの倍数であるときにハッシュ値が衝突するということになります。

したがって回答は「エ」となります。

「この問題の式をハッシュ関数にすると、正解のようなパターンが出たときに困りますよね。だから別の式を採用するか、この値に対するさらなるアクションが必要です。」と言わせるのがこの問題の意図、、、らしいです。

実は理論上は衝突しないハッシュ値は作れないらしいわよ。ただ、衝突率を無視できるレベルにまで低くすれば問題ないということみたいね。

ここまで読んでくれてありがとう！！

感謝！