ハッシュ関数の攪拌処理と圧縮処理についてメモ

出典:経済産業省
ほかの技術知識

ハッシュ関数について復習したときのメモ

参考:『暗号技術のすべて』(翔泳社)の第5章


ハッシュ関数が何であったかというのは、以前、ブロックチェーンについて調べた流れで、2019年の9月くらいにハッシュ関数の基礎に少し書いたので今回は省略するが、とりあえず、ものすごく大きなサイズの入力値を、ものすごく小さなサイズの出力値に変換するための技術である(と思う)。

ハッシュ関数とは、任意長のビット列から規則性のない固定長のビット列を生成する関数、手順のことをいう。 一般に、ハッシュ関数への入力データは「メッセージ」、ハッシュ関数からの出力データは「ハッシュ値」「メッセージダイジェスト」「フィンガープリント」などと呼ばれる。

@IT

安全なハッシュ関数

さて、このハッシュ関数を作るためには「攪拌処理」と「圧縮処理」が必要らしい。 「攪拌処理」と 「圧縮処理」のやり方や、そのタイミング(同時にやるのか、独立してやるのか)などによって、ハッシュ関数にも種類がある。

歴史的な経緯を大雑把に辿ると、 下表のようになる。

年代 名称 特徴
1990 MD4 後のハッシュ関数の設計に大きな影響を与えた
1991 MD5 衝突困難がすでに破られているので、別の安全なハッシュ関数の利用が望ましい
1995 SHA-1 ・2^64ビット未満の入力値から、160ビットの出力値を生成
・2005年に期待する安全性を保持していないことが判明した
2002 SHA-2 160ビットを超えるサイズの出力値を生成(SHA-224, SHA-256, SHA-312, SHA-512)
2012 SHA-3 ・SHA-1の後継として、コンペティションの結果選定された方法
・攪拌処理と圧縮処理が独立している

また、ブロック暗号が、鍵によって入力値を攪拌処理し、暗号文を作成するのに対して、ハッシュ関数は鍵を用いずに攪拌処理をする。また、公開鍵暗号のような(処理速度が遅い)べき乗計算ではなく、bit演算を使う。

攪拌処理
  • 転置(値の入替え)と換字(別の字に変換する)によって、見かけ上入力値と関係のなさそうな値を出力すること
  • ハッシュ関数では鍵を使わない
  • ブロック暗号では鍵を使う
圧縮処理
  • 入力値が何かわからないように(一方向性を満たすように)、入力値のサイズを調整すること
  • ハッシュ関数専用の圧縮関数を利用した例として、MD族(MD4, MD5, SHA-1, SHA-2,RIPE-MD)Whirlpoolなどがある
  • ブロック暗号を利用した構成として、PGV変換法などがある
  • 数論的安全性を根拠にした方法として、MASH-1, MASH-2がある

公開鍵暗号についての過去記事はこちら

反復型圧縮関数(MD法)について

入力値が固定長の圧縮関数を繰り返して用いる。入力されたデータをブロックと呼ばれる単位に分割するために、その前段階としてパディングする

基本のMD法

  • 圧縮関数(入力:k + n bit,出力:k bit)から、ハッシュ関数(入力:任意長,出力:k bit)を構成する
  • 問題点:パディング前のデータとパディング後のデータが衝突する

一般のMD法

  • 圧縮関数(入力:k + n +1 bit,出力:k bit)から、ハッシュ関数(入力:任意長,出力:k bit)を構成する

図とか入れようと思っていたけれど時間切れにつき、ここまで。そのうち、追記しよう。