Zenn
🙄

ハッシュアルゴリズムの基礎

2023/04/04に公開
Python
アルゴリズム
tech

ハッシュアルゴリズムとは

ハッシュアルゴリズムとは、任意の長さのデータを入力として受け取り、一定の長さのハッシュ値（ハッシュコード）を生成するアルゴリズムのことです。ハッシュ関数は、データ構造のハッシュテーブルや、暗号学的ハッシュ関数として使用されます。

ハッシュアルゴリズムは、次の性質を持っていることが望ましいです。

  1. 一貫性：同じ入力に対しては、常に同じハッシュ値を生成する。
  2. 高速性：ハッシュ値の計算が高速に行われる。
  3. 雪崩効果：入力データが少し変化しても、ハッシュ値が大きく変化する。

以下では、ハッシュアルゴリズムの基本的な種類と、それぞれの特徴について説明します。

非暗号学的ハッシュアルゴリズム

非暗号学的ハッシュアルゴリズムは、一般的なデータ構造（ハッシュテーブル）などで使用されるハッシュアルゴリズムです。これらのアルゴリズムは、高速で計算できることが求められますが、安全性については重要視されません。

例: DJB2

DJB2は、非暗号学的ハッシュアルゴリズムの一つで、Daniel J. Bernsteinによって開発されました。簡単で高速に計算できることが特徴です。

def djb2(data: str) -> int:
    hash_value = 5381
    for char in data:
        hash_value = ((hash_value << 5) + hash_value) + ord(char)
    return hash_value

暗号学的ハッシュアルゴリズム

暗号学的ハッシュアルゴリズムは、セキュリティ上の要求が高いアプリケーション（パスワードハッシュ化、データの改ざん検出など）で使用されます。これらのアルゴリズムは、安全性が重要で、一般的には次の性質が求められます。

  1. 衝突耐性：異なる入力データに対して、同じハッシュ値が生成されることが非常に困難であること。
  2. 事前イメージ耐性：ハッシュ値から元の入力データを特定することが非常に困難であること。
  3. 二次事前イメージ耐性：ある入力データに対するハッシュ値が与えられたとき、そのハッシュ値と同じハッシュ値を持つ別の入力データを見つけることが非常に困難であること。

例: SHA-256

SHA-256は、暗号学的ハッシュアルゴリズムの一つで、Secure Hash Algorithm（SHA）ファミリーに属しています。SHA-256は、256ビットのハッシュ値を生成し、セキュリティ上の要求が高いアプリケーションで広く使用されています。

PythonでSHA-256を使うには、hashlibモジュールを使用します。

import hashlib

def sha256(data: str) -> str:
    hasher = hashlib.sha256()
    hasher.update(data.encode("utf-8"))
    return hasher.hexdigest()

data = "Hello, World!"
hash_value = sha256(data)
print(hash_value)  # 7509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9

まとめ

これらのハッシュアルゴリズムは、それぞれの目的や要件に応じて適切なものが選択されます。非暗号学的ハッシュアルゴリズムは、高速性が求められる一般的なデータ構造で使用されます。一方、暗号学的ハッシュアルゴリズムは、セキュリティ上の要求が高いアプリケーションで使用されます。どちらのタイプのハッシュアルゴリズムも、データの整合性チェックや検索の高速化など、多くの場面で役立ちます。

Discussion