この記事では、ハッシュ関数について基本的な概念を説明し、Pythonを用いた実装を通じてその動作を確認する。
ハッシュ関数とは、任意のビット長のデータから固定されたビット長のデータへの写像（関数）のことである。代表的なハッシュ関数の１つである SHA-256 では、任意のビット長を256ビットのデータに変換する。ハッシュ値を生成することをハッシュ化と呼ぶ。
固定長の出力は、（理論上では）入力に対して常に同じハッシュ値を返すという性質を持つ。一方で、ハッシュ関数は一方向性関数であり、出力から元の入力を求めるのは計算的に困難であるこのため、ハッシュ関数は改竄の検出、データの比較処理、パスワードの保護などの用途に利用される。
※一方向性関数とは、入力から出力を求めるのが簡単だが、出力から入力を求めるのが困難である関数のことを指す。素因数分解がこれに当てはまる。
暗号システムに利用されるハッシュ関数には、以下の3つの要件が期待される。
- 原像計算困難性
- 強衝突耐性
- 第二原像計算困難性
ここでは、これらの3つの要件について解説していく。
3.1. 原像計算困難性
原像計算困難性とは、一方向性とも呼ばれ、ハッシュ値 $h$ から、$h = H(m)$となるメッセージ $m$ を見つけることが困難であることを保証するもの。
簡単に言うと、出力から入力が求められないということをハッシュ関数は期待される。
3.2. 強衝突耐性
強衝突耐性とは、$H(m_1) = H(m_2)$となる$m_1 \ne m_2$を見つけるのが困難であることを保証するもの。
簡単に言うと、異なるメッセージから異なるハッシュ値が生成されるべきであることを意味する。異なるメッセージから同じハッシュ値が生成されることを「ハッシュの衝突」という。
3.3. 第二原像計算困難性
第二原像計算困難性とは、与えられた$m_1$に対して、$H(m_1) = H(m_2)$、$m_2 \ne m_1$となる$m_2$を見つけるのが困難であることを保証するもの。
簡単に言うと、ある特定のメッセージと同じハッシュ値を持つ、別のメッセージを見つけることが難しいということである。
3.2. 強衝突耐性と、3.3. 第二原像計算困難性は一見すると似ているが異なる概念である。
強衝突耐性では、任意に選んだ2つの異なるメッセージが、同じハッシュ値にならないことが要求される。
一方で、第二原像計算困難性では、一方のメッセージが固定されており、そのハッシュ値と一致する別のメッセージを見つけることが困難であることを要求される。
強衝突耐性は第二原像計算困難性よりも強い性質である
$\longrightarrow$
強衝突耐性は、第二原像計算困難性を保証するものであるが、原像計算困難性はその限りでない。
例として恒等写像について考えてみる。恒等写像というのは、入力をそのまま出力する写像[関数]である。
この時、この写像は強衝突耐性をもつ。なぜなら強衝突耐性の条件である異なるメッセージを入れたら、返ってくる結果は明らかに異なるからである。
しかし、この写像は原像計算困難性を持たない。なぜなら、入力と出力が一対一であるため、原像計算困難性が要求する出力から入力が推測されないというものに反する。
ハッシュ関数は競技プログラミングで出てくることがある。
A56 – String Hash
問題文
長さ $N$ の文字列 $S$ が与えられます。以下の $Q$ 個のクエリを処理してください。
- $i$ 番目のクエリ：$S[a_i, b_i]$ と $S[c_i, d_i]$ は一致するか？
ただし、$S[l, r]$ は $S$ の $l$ 文字目から $r$ 文字目までの連続部分文字列とする
制約
- $N$, $Q$, $a_i$, $b_i$, $c_i$, $d_i$は正数である
- $S$は英小文字からなる文字列である
- $1 \leq N \leq 200000$
- $1 \leq Q \leq 200000$
- $|S| = N$
- $1 \leq a_i \leq b_i \leq N$
- $1 \leq c_i \leq d_i \leq N$
- $b_i – a_i = d_i – c_i$
問題の制約から、クエリごとに指定された範囲を切り取って探索するのは不可能であることがわかる。
ここで出てくるのが、問題文にもある通りハッシュ関数である。ハッシュ関数を利用して、累積的に部分のハッシュ値を計算し配列に保存する。そして、クエリごとに$O(1)$の探索で答えを求める。
Pythonで行った実装は以下の通りである。
from sys import stdin
input = stdin.readline
B = 515
MOD = pow(10, 8) + 13
def string_to_num(char):
return ord(char) - ord('a') + 1
def cal_hash(power, H, left, right):
res = (H[right] - H[left - 1] * power[right - left + 1]) % MOD
return res + MOD if res 0 else res
def main():
N, Q = map(int, input().split())
S = input()
power = [1] * (N + 1)
Hash = [0] * (N + 1)
for i in range(N):
power[i + 1] = (power[i] * B) % MOD
for i in range(N):
num = string_to_num(S[i])
Hash[i + 1] = (Hash[i] * B + num) % MOD
for _ in range(Q):
a, b, c, d = map(int, input().split())
hash1 = cal_hash(power, Hash, a, b)
hash2 = cal_hash(power, Hash, c, d)
if hash1 == hash2:
print("Yes")
else:
print("No")
if __name__ == '__main__':
main()
実装はローリングハッシュを用いて行われている。
この手法では、文字列を多項式のように見立て、各文字を数値に変換したうえで、基数 $B$ の累乗を係数とした総和として部分文字列のハッシュを構成する。
事前に全体のハッシュ値と累乗値を $O(N)$ で前計算しておくことで、各クエリに対する判定を $O(1)$ で行うことが可能となる。
今回はハッシュ関数の基本的な概念から始まり、その性質、Pythonでの実装、そして競技プログラミングにおける応用例までを紹介した。
Views: 0
