- @ThothChildren
- 2018.8.5
- PV 175
ハッシュ関数とは
ー 概要 ー
ハッシュ関数とは与えられたデータを別の小さな値に変換する関数です.どのような変換を行うかについては自身で関数を選択する必要があります.幾らか求められる特徴があり、元の入力データが異なれば出力も異なることが期待されます.検索の高速化やデータ構造、データの一致、データの改竄検出など幅広く用いられる.
この章を学ぶ前に必要な知識
条件
- 入力となるデータ
効果
- 特定の規則で変換された出力を与える
ポイント
- どのような変換を行うかは用途に合わせて選ぶ
- 入力が異なるのに出力が同じになることを衝突といい、よいハッシュ関数は衝突する可能性が低い
- 同じ入力がきたら同じ出力を出す
- 用途によっては元の入力が簡単にわからないことも必要
- データ構造、検索、データの要約、データの一致、データの改竄などに用いられる.
- 多くの場合は入力データが大きく、出力はかなり小さい
- 入力データが異なれば出力が異なるので、簡単に二つのデータが一致しているかわかる.(ただし衝突はありうる)
- MD5やSHA-1, SHA-2などが有名なハッシュ関数
- 出力される値をハッシュ値と呼ぶ
- パスワードの保管時にもハッシュ値を計算して保存します.
解 説
ハッシュ関数とは、入力されたデータを固定長の全く異なる他のデータに変換する関数.データの要約の役割を持ち、データが一致するときの確認やデータの検索の高速化、データの改竄検出に用いられます.
ハッシュ関数では以下のような特徴を持ちます.
・固定長の不規則なハッシュ値を出力する
・入力が同じなら出力する値(ハッシュ値)は常に同じ
・入力が異なったなら出力する値は異なるべき
・入力が異なってもハッシュ値が一致することを衝突と言う.他の手法で補完してやる必要がある.
・入力が簡単に想像つかない
| ハッシュ関数とは |
入力するデータサイズがハッシュ値より大きい場合が多く、ハッシュ値は元のデータの値を生かして生成した要約データのようなものとみなせます. | ハッシュ関数の要約 |
ハッシュ関数の様子.
似ている入力でも全く異なった値を出すようにしている.
どのような値が出るかは選んだハッシュ関数に依存する. | |
ハッシュ関数でデータが一致することを確認します.
データAが"abc111....11de"、データBが"abc111....11df"とします.違いは末尾のeとfだけとします.
このときにそれぞれのハッシュ値を計算すると、「入力が異なると出力が異なる」ため、データAのハッシュ値"9182ac7"、データBのハッシュ値"f24l91po"のように全く異なった値になります.これらのハッシュ値を比較すると、データが異なっていることが用意にわかります. | ハッシュ関数でデータの一致することを確認する |
データの一致を確認する場合. |
この章を学んで新たに学べる
Comments