Tip:
Highlight text to annotate it
X
暗号学的ハッシュ関数は基本的な要素であり
多くの暗号アルゴリズムやプロトコルで 必要になります
情報セキュリティの分野では非常に重要なものです
中でも有名な暗号学的ハッシュ関数といえば MD5とか
その前身であるMD4や
SHA-256というものもあります
その前身のSHA-1というものもありますね
RIPEMDやBLAKE Skeinといった名前を 聞いたことがある人もいるかもしれません
今日 暗号学的ハッシュ関数は 様々に応用されていますが
その歴史の最初期にあるのは 電子署名での使用例でしょう
デジタル署名は多くの分野で使われています Eコマースの基礎部分はもちろん
Bitcoinの生成にも用います
他にもメッセージ認証やランダムな数字の生成
パスワードの保全やある種の暗号化に使われます
Bitcoinのプロトコルの中にも様々な形で 暗号学的ハッシュ関数が現れます
それではまず暗号学的ハッシュ関数とは何かをお話して
1つには その名のとおり これはハッシュ関数の1種です
ハッシュの名のとおり これは入力を受け付けます
数学的関数ですから入力されたものを処理するわけです この入力を「メッセージ」と呼びます
メッセージの長さは任意です
ハッシュ関数はこのメッセージを受け取り 数学的に変形させて1つの出力を得ます
この出力を「ダイジェスト」といいます
この出力は他にもタグとかハッシュとか フィンガープリントと呼ばれます
ダイジェストがもっとも一般的な呼び方でしょうか
実際MD5は「メッセージ・ダイジェスト・5」の 省略形ですからね
MD4も「メッセージ・ダイジェスト・4」の略でした
さてメッセージの長さは任意だと言いました 長くても短くてもかまいません
ただし出力 ダイジェストあるいはタグの 長さは決まっています
例えばSHA-256のダイジェストの長さは 256ビットと決まっています
入力の長さは任意ですが 出力は固定長なのです
また暗号学的ハッシュの特徴としては 決定性のアルゴリズムであることが挙げられます
関数は同じ入力に対して 常に同じ結果を生成します
入力が同じであれば毎回同じ出力が得られるのです
同じ入力が違う出力を返すことはありません
毎回同じなのです
ハッシュ関数は計算機科学で 長い間使われており
様々な形で応用されています
例えば「ハッシュテーブルを構成するハッシュ関数」など 聞いたこともあるのでは
しかしハッシュテーブルで使われているものは 暗号学的ハッシュ関数とは限りません
暗号学的であるには条件があるのです
つまり暗号学的ハッシュの設計においては欠くことのできない要件があり
それがなければ秘匿性が問題となる暗号的アプリケーションに 用いることができないのです
さてそれらの要件についてお話していきますが
暗号学的ハッシュ関数は 計算機的に効率よくなければいけません
入力を処理して出力するのに 時間がかかりすぎてはいけません
メッセージを加工してダイジェストを得るのに 長い時間コンピューターで計算するわけにはいかないのです
ある程度高速である必要があります
明らかなことですが 大事なことなので強調しておきますと
非効率なハッシュ関数を用いる暗号的アプリケーションは 適格なものであるとはいえないのです
2つ目には 特に電子署名においてですが 同じ出力を得る2つの入力は見つけにくくなくてはいけません
別々のメッセージに同じダイジェストが紐づく状態ですね
この要件を「衝突困難性」といいます
衝突する2つの入力が見つけにくいという意味です
たとえばM1とM2という2つのメッセージがあるとしましょう
このメッセージからハッシュ関数で得るダイジェストは 同じであってはいけません
M1とM2 から得られる出力は必ず違うものなのです
常に重複せず違っていなければならないのです
少し戻りましょう メッセージは任意の長さですが ダイジェストの長さは決まっていると言いました
2つのメッセージから得られるダイジェストが 常に違っていると証明するのは数学的に不可能です
現実的には同じ出力となる2つの別の入力を 探すのが困難な仕組みが必要です
原理上メッセージの数よりも ダイジェストの数は少ないですからね
そういうわけで2つのメッセージを探すのに天文学的な時間が 必要なアルゴリズムにしなければいけません
3つ目には ハッシュ関数は 入力に関する情報を隠せないといけません
入力の内容を予想できる情報が 出力されないようにする必要があります
例えば入力が奇数なのか偶数なのかなど あらゆる情報ですね
これらは出力からは排除されるべきです
奇数・偶数のような単純なヒントでもです
4つ目には
出力の分布が広くなければいけません
まったくランダムな出力に見えなければいけません
まるでコインの裏表の分布のように 予想不可能である必要があります
コインをばらまいたときの裏表の分布を 考えてっましょう
それくらいのランダムさが必要です
つまり暗号学的ハッシュというのは 数学的なひき肉ミキサーのようなものです
入力を受け取って数学的に変形させるわけですね
その際の出力はバラバラの ランダムなものに見えるようになります
これらの要件については それぞれに関連があります
例えば出力が入力と無関係に見えてしかもランダムであれば 衝突困難性は非常に高いといえるでしょう
出力から入力が予想できないのであれば 同じ出力を得る2つの入力は見つけにくいといえます
もちろんある要件と要件が矛盾することもあります
また数学的に完璧に見えても 現実世界で常にそれが保証されるわけではありません
衝突困難性において完璧なハッシュ関数を作ることは できるかもしれません
しかし例えば1年後 誰かがそれを覆さないとは言えないのです
総当り以外のエレガントな方法で 衝突を探し出すことができるようになるかもしれないのです
今のところそうした数学的テクニックは 見つかっていません
暗号学的ハッシュ関数の制限は 今のところ回避できないのです
そういうわけで今のところは 「総当りでどれくらい時間がかかるか」が指標となっています
最後に これらの説明は常に数学的に 厳密というわけでもないのです
もっと正確に説明する方法もあります
まずこの動画で暗号学的ハッシュ関数の エッセンスをつかんでください