読み方：げんぞうけいさんこんなんせい

原像計算困難性

概要

原像計算困難性とは、ハッシュ関数の出力値（ハッシュ値）から元の入力データを逆算することが計算上極めて困難である性質。暗号学的ハッシュ関数が備えるべき基本的な安全性についての要件の一つである。

ハッシュ関数は任意の長さの入力データから固定長のハッシュ値を生成する関数であり、同じ入力からは常に同じハッシュ値が得られる一方、入力が少しでも異なれば結果は大きく変化するよう設計されている。

ハッシュ関数には様々な設計が考えられるが、暗号技術などの一部として利用される「暗号学的ハッシュ関数」には、入力からハッシュ値を求めることは容易である一方、ハッシュ値から元の入力を求めることは現実的な時間内では事実上不可能であるような性質が求められる。これを原像計算困難性と呼ぶ。

例えば、SHA-256というハッシュ関数に「password」という文字列を入力すると、256ビットの「5e88 4898 da28 0471 51d0 e56f 8dc6 2927 7360 3d0d 6aab bdd6 2a11 ef72 1d15 42d8」（2バイトごとに16進表記）というハッシュ値が得られる。このハッシュ値だけを持っている第三者が、「password」という元の文字列を導き出すことは、理論上はありとあらゆる文字列を総当たりするしかなく、現実的な計算資源では不可能とされている。

原像計算困難性が実用上重要な意味を持つ場面の一つがパスワードの保存だ。現代的な認証システムでは登録利用者のパスワードをそのまま保存するのではなく、ハッシュ値として保存することが一般的である。認証時は入力文字列をハッシュ化して容易に照合できる一方、仮に保存されたデータが漏洩してもハッシュ値から元のパスワードを復元することが困難なため、被害を軽減できる。

なお、原像計算困難性に近い概念として「第二原像計算困難性」がある。こちらは特定の入力と同じハッシュ値を持つ別の入力を見つけることの困難性を指す。ハッシュ値は長い入力からも固定長の短い出力を生成するため、同じハッシュ値を持つ入力は複数存在することが前提となる。同じハッシュ値が得られるような複数の入力の「衝突」を人工的に再現するのが困難であるような性質を指す。