ハッシュ関数とは

正解：C. 入力が同じなら必ず同じハッシュ値になり、入力が1ビット違うだけでも、ハッシュ値は予測できないほど大きく変わる

ハッシュ関数は、任意の長さのデータから、決まった長さの値(ハッシュ値、ダイジェスト)を計算する関数です。例えばSHA-256は、入力の長さによらず256ビットの値を出力します。同じ入力からは必ず同じ値が得られ、入力がわずかでも違うと、出力は予測できないほど大きく変わります。暗号で使うハッシュ関数には、さらに、ハッシュ値から元の入力を求めることが現実的に不可能であること(一方向性、原像計算困難性)や、同じハッシュ値になる異なる2つの入力を見つけることが困難であること(衝突困難性)が求められます。ハッシュ関数は鍵を使わない計算で、暗号化ではないので、復号して元に戻すこともできません。改ざんの検出、デジタル署名、パスワードの保存などに使われます。

正解：A. 原像攻撃は約2^256回、衝突攻撃は約2^128回

出力がnビットの理想的なハッシュ関数では、ハッシュ値は 2^n 通りあり、入力を1つ試すごとに、決められたハッシュ値に一致する確率は 1/2^n です。そのため原像攻撃には、およそ 2^n 回、n = 256 なら約2^256回の計算が必要です。一方、衝突攻撃では、どの2つが一致してもよいので、k個の入力を試すと、比べられる組は約 k^2/2 通りに増えます。k^2/2 が 2^n に近づく、k が 2^(n/2) 程度で衝突が見つかる見込みが高くなり、n = 256 なら約2^128回です。これは「23人いれば、誕生日が同じ2人がいる確率が50%を超える」という誕生日のパラドックスと同じ考え方で、誕生日攻撃と呼ばれます。このため、ハッシュ関数の衝突に対する強さは出力のビット数の半分と見積もられ、128ビット相当の強さを求めるなら256ビットの出力が必要になります。