Python で SHA-256 をフルスクラッチで実装する
はじめに
この記事では Python で SHA-256 をフルスクラッチで実装したときのソースコードの説明を記載します。
ソースコードは以下のリポジトリにあります。
SHA-256 とは
SHA-256 は、入力データから 256 ビット（32 バイト）の固定長のハッシュ値を生成する暗号学的ハッシュ関数です。
暗号技術、データ改ざん防止、デジタル署名、ブロックチェーン技術などで広く利用されています。
SHA-256 のハッシュ値は openssl コマンドなどで確認することができます。
hello を入力すると 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 という値が生成されます。
$ echo -n hello | openssl dgst -sha256
(stdin)= 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
実装の説明
SHA-256 の処理は大きく分けて、前処理 と ハッシュ値計算 の2つの段階に分かれます。
以下、実装コードをもとに各段階の詳細を説明します。
前処理
前処理では、以下の2つの処理を行っています。
- パディング
- ブロック、ワードへの分割
1. パディング
パディング処理を Python で実装すると以下のようになります。
元の文字列に 0x80 と 0x00 と文字列の長さを加えています。
def padding(byte_string: bytes) -> bytes:
string_length = len(byte_string)
n = 1
while (string_length * 8) >= (1 << (8 * n)):
n += 1
# ブロックサイズは 64 バイトの倍数
# SHA-256 では、現在のブロックに長さフィールドが収まらない場合は新たなブロックを追加する
# ここでは、メッセージ部の長さ m が 56 バイト以上の場合は 長さを 64 の倍数にする
if string_length % 64 < 56:
total_length = ((string_length // 64) + 1) * 64
else:
total_length = ((string_length // 64) + 2) * 64
pad_zero_count = total_length - (string_length+ 1 + n)
return byte_string + b'\x80' + (b'\x00' * pad_zero_count) + (string_length * 8).to_bytes(n, 'big')
2. ブロック、ワードへの分割
パディングされたバイト列を 64 バイト（512 ビット）ずつのブロックに分割し
ブロックの中を 8 バイト（32 ビット）ずつのワードに分割します。
def preprocess(string: str) -> list:
byte_string = string.encode("ascii")
padded = padding(byte_string)
blocks = []
for block in [padded[i:i+64] for i in range(0, len(padded), 64)]:
words = [block[i:i+4] for i in range(0, 64, 4)]
blocks.append(words)
return blocks
ハッシュ値の計算
前処理が終了すると、各ブロックに対してハッシュ値の計算処理を行います。
- 計算で使用する 64 個の値を求める
- 16 個のワードを整数に変換する
- 16個のワードをもとに 16～64 番目以降の値を計算する。
- 64 回のループで、変数 a, b, c, d, e, f, g, h の値を更新する。
- H を更新する
- H の各要素を文字列に変換して、ハッシュ値を返す
def compute_hash(blocks: list) -> str:
ws = [0] * 64
# H の初期値を定義
H = [
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
]
for block in blocks:
# 16 個の word を整数に変換
for t in range(16):
ws[t] = int.from_bytes(block[t])
# 16 番目以降の値を計算する
for t in range(16, 64):
ws[t] = (lower_sigma1(ws[t - 2]) + ws[t - 7] + lower_sigma0(ws[t - 15]) + ws[t - 16]) & 0xffffffff
a, b, c, d, e, f, g, h = H
# 64 回のループ処理で a~h を更新する。
for i in range(64):
t1 = (h + upper_sigma1(e) + ch(e, f, g) + K[i] + ws[i]) & 0xffffffff
t2 = (upper_sigma0(a) + maj(a, b, c)) & 0xffffffff
h = g
g = f
f = e
e = (d + t1) & 0xffffffff
d = c
c = b
b = a
a = (t1 + t2) & 0xffffffff
# ブロックごとに値を更新
H[0] = (a + H[0]) & 0xffffffff
H[1] = (b + H[1]) & 0xffffffff
H[2] = (c + H[2]) & 0xffffffff
H[3] = (d + H[3]) & 0xffffffff
H[4] = (e + H[4]) & 0xffffffff
H[5] = (f + H[5]) & 0xffffffff
H[6] = (g + H[6]) & 0xffffffff
H[7] = (h + H[7]) & 0xffffffff
return "".join([f"{h:08x}" for h in H])
計算の中で使用している lower_sigma, upper_sigma, ch, maj の関数、および内部で使用されている rotr 関数の実装は以下の通りです。
def rtor(data: int, shift: int) -> int:
return data >> shift | data << (32 - shift) & 0xffffffff
def lower_sigma0(int_word: int) -> int:
return rtor(int_word, 7) ^ rtor(int_word, 18) ^ (int_word >> 3)
def lower_sigma1(int_word: int) -> int:
return rtor(int_word, 17) ^ rtor(int_word, 19) ^ (int_word >> 10)
def upper_sigma0(int_word: int) -> int:
return rtor(int_word, 2) ^ rtor(int_word, 13) ^ rtor(int_word, 22)
def upper_sigma1(int_word: int) -> int:
return rtor(int_word, 6) ^ rtor(int_word, 11) ^ rtor(int_word, 25)
def ch(x: int, y: int, z: int) -> int:
return (x & y) ^ ((x ^ 0xffffffff) & z)
def maj(x: int, y: int, z: int) -> int:
return (x & y) ^ (x & z) ^ (y & z)
テスト
ちゃんと実装できているか確認するため hashlib（Pythonの標準ライブラリ） の出力と一致するか、テストしました。
def test_sha256():
# 既存ライブラリの出力と合致することを確認
assert sha256("hello") == hashlib.sha256(b"hello").hexdigest()
他の関数のテストもあるので、11 個となっていますが、
上記のテストを通過しているので、問題なく実装できています。
$ uv run pytest
============================================================== test session starts ===============================================================
platform linux -- Python 3.13.2, pytest-8.3.5, pluggy-1.5.0
rootdir: /path/to/python-sha-256
configfile: pyproject.toml
collected 11 items
tests/test_sha256.py ........... [100%]
=============================================================== 11 passed in 0.17s ===============================================================
おわりに
Python で SHA-256 を実装したきっかけとして、以下の２点がありました。
- 情報処理安全確保支援士の勉強で、ハッシュアルゴリズムの一方向性について学んだが、具体的にイメージが持てなかったこと
- uv や ruff が良いと聞いていて、Python を使って何か作りたかった
Python を使って何か開発をするのは久しぶりでした。
今回の開発は以下の流れで進めていました。
- 自分でテストを作成する
- 「テストが通る関数を実装して」と ChatGPT にお願いする
- 細かいところを修正する
2 で ChatGPT が出してくる関数が、そのままテストを通り、
3 はほぼ微調整のような形が多くて、「俺いる？」状態でした...
AI ってすごい。
Discussion