SHA-256 って何をしているの？

n-ozawan

2023年10月18日

皆さん、こんにちは。技術開発グループのn-ozawanです。
霜降り肉を見ると「うわぁ！美味しそう」から「うわぁ…胃がもたれそう」になりました。

本題です。
データが改ざんされたかどうかを確認する方法としてハッシュ関数があります。前回、ハッシュ関数の概要についてお話ししましたので、今回はハッシュ関数のアルゴリズムの１つである「SHA-256」が、どのようにして任意のデータからハッシュ値を算出しているのかをお話しします。

SHA-256

ハッシュ関数のインプットとなるデータのことを「メッセージ」と呼びます。SHA-256の全体の流れは以下の通りとなります。

上記の図で黄色くしている個所は後ほど詳しく見ていきます。

SHA-256ではメッセージを512ビットに分割して処理していきます。メッセージの長さは任意なので、必ずしも512ビットで分割することは出来ません。なので、メッセージが512ビットで分割できるようにパディング（詰め物）をしてあげる必要があります。

分割された512ビットのデータから、64個の32ビットのワードを算出します。512ビットを単純に32ビットで分割すると16個までしか算出されません。なので17個以降は特別な計算により算出することになります。

繰り返しになりますが、W₀ ～ W₁₅ までは単純に512ビットのデータを32ビットで分割したものになります。W₁₆ 以降は以下の計算式により求めます。

W_t = σ₁(W_t-2) + W_t-7 + σ₀(W_t-15) + W_t-16

逃げ出したくなる計算式ですね。１つずつ見ていきましょう。
式中のtというのは、ラウンド数になります。この場合、tは16 ～ 63のいずれかになります。例えば、W₁₆ を求めたい場合は以下のようになります。

W₁₆ = σ₁(W₁₄) + W₉ + σ₀(W₁) + W₀

σ₀ と σ₁は関数です。インプットとなる値（上の式ではW₁₄もしくはW₁）を、右回転もしくは右シフトして、それぞれをxorした結果を出力します。右回転というのは、循環右シフトのことです。

W₀ ～ W₆₃ を算出したら、続いてはブロック処理を行います。ハッシュ値の長さは常に固定で、SHA-256 であればハッシュ値の長さは256ビットになります。ブロック処理は任意長のメッセージを固定長にする処理になります。

ブロック処理では、いずれハッシュ値となる256ビットを8個の32ビットのワードに分割し、それらを内部状態として保持します。内部状態はAバッファからHバッファの8個で構成されおり、初期状態として特定の固定値が指定されています。（内部状態の初期値は前述の全体フローの図に記載しています）

内部状態のA～Hに対して、先ほど算出したW₀ ～ W₆₃ のそれぞれでステップ処理を64回繰り返し行います。最後に64回繰り返し行った結果と、ステップ処理をする以前の状態を加算します。加算した結果が新しい内部状態となり、次の512ビットの処理に引き継がれます。

ブロック処理で行われているステップ処理は以下の図ようになります。

基本的にはAバッファをBバッファへ、BバッファをCバッファへ、などのようにバッファごとシフトします。しかし、AバッファとDバッファに関しては、特別な処理が挟みます。

AバッファとEバッファに対して、Σ₀ と Σ₁ の処理が行われます。Σ₀ と Σ₁ は関数です。σ₀ と σ₁ と同じように、与えられた値に対して右回転を行い、それぞれをxorした結果を返します。

図中にある「ステップ依存の定数K_t」ですが、これはSHA-256の仕様で決められている定数を使います。

すべてのブロック処理を行い、内部状態の8個のA～Hを結合した結果がハッシュ値となります。

SHA-256で何をやっているのかをお話ししました。ハッシュ値を求めたいときは、ライブラリが標準で用意されているか、公開されていると思いますので、自作せずにそちらを使うようにしましょう。

SHA-1およびSHA-2を定めている PUB 180-4 を見れば、何をやっているのかは分かるのですが、これらの定数や処理が、なぜ衝突耐性を担保出来るのか分かりませんね。数学に強い人なら分かるのでしょうか。

ではまた。

暗号化処理

ハッシュ関数