ハッシュ関数について(前編)

seccamp

はじめに

seccamp2021のグループKのリレーブログの一貫です。
前回はこちら。次回はこちら。

このリレーブログについて、グループとして発表することになりました(宣伝)

www.ipa.go.jp

他の内容も面白そう

今回のお題はハッシュです。

ハッシュ関数(ハッシュ)とは

任意長のビット列から規則性のない固定長のビット列を生成する関数です。
理想的なハッシュ関数は次の特性を備えます。

  1. 同じ引数なら返り値も同じ
  2. 不可逆性
  3. 高速計算
  4. コリジョン(衝突)が少ない

2と4について少し深堀をしていきます。

不可逆性

不可逆性とは、ある状態から変化させることはできるが変化後の状態から元の状態に戻せないことを言います。

ハッシュ関数では上記のように固定長のビットに圧縮または拡張?しますし、規則性がないので復元することができません。例として余りを考えてみます。
余りを用いるというのも一種のハッシュ関数です(多分)。

data = 9
hash_data = data % 5
print(hash_data)

この結果は4ですね。ここで復元することを考えてみましょう。しかし、5で割ったときに余りが4になる数字なんていっぱいあります。そこから9を当てるのなんて難しい話です。これが不可逆性です。

なので、ハッシュ関数は暗号化ではありません。暗号は復号(復元)することが出来ます。

コリジョン(衝突)が少ない

衝突とは、違う引数をハッシュ関数に通した際に結果が同じになることです。先程のコードの例だと、[4, 9, 14]は同じ返り値になります。

これがなぜ少ない方が良いかは用途を例に上げると分かりやすいかもしれません。
例えばハッシュ関数は、改ざんを検知するために使われます。イメージファイルなどをダウンロードする時、ダウンロード後サイトに記載されたハッシュ値と比較することがあると思います。衝突しやすい場合、ダウンロードファイルがもとのファイルと異なっていても同じハッシュ値になってしまうわけです。これでは正しいかチェックした意味がありません。

 

次に少し触れましたがハッシュ関数の用途を考えてみます。

用途

  1. 検索の高速化
  2. 改ざんの検出

2に関しては先程触れたので、1について。ただ、少し自分の解釈も混じって書くので間違った内容もあるかもしれません。
ハッシュ探索という探索アルゴリズムがあります。基本的に計算量はO(1)です。

原理は、データを登録したい時にそのデータをハッシュ関数に渡してハッシュ値を求めます。そのハッシュ値はハッシュ表の位置になります。その位置にデータを登録します。
ハッシュ表は配列みたいなものでハッシュ値が配列のインデックスです。

探索するときは、そのデータのハッシュ値を求めてあげると格納位置が一意に決まります。

ただし、先程説明した衝突が起きるといろいろ問題が起きます。解決法は今はいいでしょう。

 

みなさんも聞いたことがあるであろうsha256について書いていきます。

sha256

sha256はSecure Hash Algorithm 256-bitの略です。

まずは、ハッシュ値を得るまでの流れを箇条書きで

  • sha256には初期ハッシュ値というものがある
  • データを64bitずつに分割する -> メッセージブロック
  • 初期ハッシュ値とメッセージブロックを使ってハッシュ値を生成
    　-> このハッシュ値を使って次のメッセージブロックと...を繰り返す

これを図で。

         f:id:Bigdrea6:20220225155816p:plain

このメッセージブロックに分割するさいですが、全ての入力データが64✕n bitではありませんので調整をするためにパディングを行います。

パディング

パディングは0で埋めるイメージだったんですが、これをしてしまうと元のデータで使用されている0と区別がつかなくなります。sha256では次のようなルールでパディングしているようです。

  • 元のメッセージと調整のメッセージの区切りは0x80で行う
  • メッセージブロックの最後には元のメッセージの長さ(bit数)を入れる
  • 0x80とこの情報の間を0で埋める

 

以上です。

参考資料