ハッシュ化 / SHA-256 をアルゴリズムからきちんと理解する

1. はじめに

1-1. なにをする記事か

ハッシュ化とはそもそも何か、その代表格 SHA-256 がどのようなアルゴリズムで動いているのか、を具体例を用いて理解していきます。
説明の流れは、

1. 概要：そもそも何なのか
2. 理論：どのように動いているのか
3. 実装：それをどう実装するのか

を順に解説します。

1-2. 学ぼうと思った動機

ブロックチェーン技術について興味があり、その信頼性を支える根幹技術の1つが「ハッシュ化」であることを知ったからです。

2. 概要

2-1. ハッシュ化とは

一言でいうと、データを一方通行の暗号のようにして、元に戻せなくしちゃおう！な処理です。
もう少し詳細にいうと、特定の計算（ハッシュ関数）に基づいて、元のデータを不規則な文字列に（実質的に）不可逆変換する処理、のことです。
変換後の値をハッシュ値といいます。ハッシュ値は長ければ長いほど安全です。

使われている場面は、

1. パスワードをハッシュ化して保存・管理
2. チェックサム（ある時点でデータが改ざんされていないかを確認）
   などがあります。

1 について、第三者が不正にパスワードへアクセスしたとしても、ランダムな文字列に変換されていることで、悪用されるのを防ぐことができます。
2 について、元のデータが返られたらそのハッシュ値も変わるので、改ざんされたかどうかを検知できます。電子署名、電子メール、暗号資産などで使われます。

暗号化との違いは「不可逆性」です。暗号は元に戻せますが、ハッシュ化はもとに戻せません。（正確には、原理的には戻せますが、途中で行う作業が複雑すぎて、現代の計算速度では戻すのには時間が足りません。）

2-2. ハッシュ関数とは

元のデータから、ハッシュ値を返す関数です。その性質は、

1. 同じ元データからは同じ値が得られる
2. 異なる元データからは別のハッシュ値が生成される
   です。

例として、MD5、SHA-1、SHA-2、SHA-3、bcirpt があります。

1. MD5
   ・128ビットの長さのハッシュ値をだします。
   ・高速に出力できます。
   ・チェックサムによる改ざんの確認に使用されます。（github のファイルの改ざん検知にも使われているそうです。）

2. SHA-1
   ・1995年に発表された規格です。
   ・160ビットのハッシュ値を生成します。
   ・衝突攻撃（異なるデータからハッシュ値が同じになることを利用した攻撃）のリスクがあるため、現在は利用が非推奨となっています。

3. SHA-2
   ・SHA-1を改良し、2001年 NIST（米国標準技術研究所）によって標準化された規格です。
   ・ハッシュ値の長さに応じて、SHA-224、SHA-256、SHA-384、SHA-512 などが定義されています。
   ・現在の主流は、SHA-256 や SHA-512 です。

4. SHA-3
   ・SHA-2よりも安全性を向上させるために、2015年に公開された後継の規格です。
   ・名称は引き継いでいるが、内部構造などが異なるなど、SHA-2とは別系統として設計されています。

5. bcript
   ・パスワードハッシュ化に特化したアルゴリズムです。
   ・salt を内部で自動的に生成・管理し、レインボーテーブル攻撃に対する耐性があります。

ここで今出てきた salt 、レインボーテーブル攻撃について解説をします。

3-3. salt と pepper

ハッシュ化にも脆弱性があります。それは、「可逆変換とはいえ、入力値に対して出力されるハッシュ値は決まっている」という点です。

例えば、パスワードに password という値をいれ、SHA256 でハッシュ化すると 5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8 という値になります。この値さえ事前に知っておけば元の値が password であったことは簡単に知られてしまいます。
攻撃者は、このようなよく使われる文字列とそのハッシュ値の対応表を準備し、元の値を割り出します。これを「レインボーテーブル攻撃」といいます。

この攻撃を防ぐのが salt や pepper という手法です。
salt は、元データに任意の文字列を加えてハッシュ化します。例えば、password に、Random という文字列を加えた値 PasswordRamdom を作りそれをハッシュ化します。するとこのハッシュ値は 47ccae85a6c71a910d5c5fe6ac8a780de6a0d3d7751961b4f049ebd2b6ff4b2a となり、レインボーテーブルから簡単に推測できなくなります。

salt の安全性をさらに強化したものが pepper です。
salt の課題は、「パスワードのハッシュ値と salt の値が同じテーブルに保存されることが多い」ということです。パスワードのハッシュ値と salt の値が知られたら、passwordRandom、Randompassword などを調べることで、目的のハッシュ値にたどり着かれてしまいます。
そのため、別の変数 （pepper と呼びます）を準備し、それを別の階層 (.env 等）に保存します。たとえば、Ice という pepeer を準備し、passwordRamdomIce という文字列を作成します。このハッシュ値はこれまでとは別物であり、データベースから salt が盗まれても元の値がわかることはありません。

さらなる対策として、任意の回数ハッシュ化を繰り返す」ことで安全性を高める「ストレッチング」という方法も存在します。ここでの説明は省略します。

3. SHA-256のアルゴリズム

SHA-256 のアルゴリズムの理解をします。

3-1. ふるまいと性質

$ hello
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

$ good morning
cdf71dea7d7741a2b6f021f3dd344f75c8333988f547866a8fbf28f064cf7c78

$ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
6bd5e5034855a11241f0dee8fc72850ffd9955b28347a86428b5fa19119f6ad0

入力データの長さにかかわらず、常に256 ビットの数が返ってきます。(SHA-256 の '256' の意味です。)
16進数の数が 32 個なので、$4 ビット \times 32 = 256 ビット$ です。下は 16 進数と 2 進数の対応表です。

0 (16進数) = 0000 (2進数)
1 (16進数) = 0001 (2進数)
2 (16進数) = 0010 (2進数)
3 (16進数) = 0011 (2進数)
4 (16進数) = 0100 (2進数)
5 (16進数) = 0101 (2進数)
6 (16進数) = 0110 (2進数)
7 (16進数) = 0111 (2進数)
8 (16進数) = 1000 (2進数)
9 (16進数) = 1001 (2進数)
a (16進数) = 1010 (2進数)
b (16進数) = 1011 (2進数)
c (16進数) = 1100 (2進数)
d (16進数) = 1101 (2進数)
e (16進数) = 1110 (2進数)
f (16進数) = 1111 (2進数)

メッセージの長さの上限は、$2^{64}$ です。これは アルファベットで、約2,305京文字 (ASCII文字：1文字あたり1バイトで換算)です。1ページあたり500単語、1単語あたり 5文字とすると、約11,525 億冊の 200 ページの本に相当します。よって元のデータの大きさは気にする必要はありません。

3-2. 事前処理1: メッセージのパディング

SHA-256 のハッシュ化がどのように行われるかを、文字列 hello を例にとって説明します。
ここでは、今後の計算で扱いやすいように、メッセージデータのビット数を 512 の倍数に直します。

1. 文字を ASCII コードに変換

# hello の場合
# 8 ビット * 5 = 40 ビット

01101000 01100101 01101100 01101100 01101111 (2進数)

まず、入力された ASCII 文字を ASCII コードに変換します。
バイト単位で処理することがあるため、8ビット (1バイト) ずつで区切っています。

2. 1 を追加する

# hello の場合

01101000 0110010 101101100 01101100 
01101111 1

次のステップで、0 を追加するのですが、いきなり 0 を追加すると、ASCII 文字から出た 0 と 後から追加された 0 の区別がつかないため、1を追加します。

3. 0 を追加する

# hello の場合
# 512 - 64 = 448　ビットになるまで 0 を敷き詰める
# つまり、448 - (40 + 1) = 407 ビット分、0 を足す

01101000 01100101 01101100 01101100 
01101111 10000000 00000000 00000000
00000000 00000000 00000000 00000000
...
00000000 00000000 00000000 00000000 (448 ビット)

文字列の長さの合計が、512 の倍数から 64 引いた数にします。
余らせた最後の 64 ビットは、次のステップで使用します。

1. 文字列が 40 ビットの場合 (hello の場合)
   448 (= 512 - 64) ビットになるまで 0を敷き詰めます。
2. 文字列が 500 ビットの場合
   512 ビットでは残り 64 ビットもありません。そのため、512 * 2 = 1024 ビットまで長さを延長し、960 (= 1024 - 64) ビットになるまで、0を敷き詰めます。

4. メッセージ長を付け足す

# hello の場合
# メッセージ長さ：40 ビット
# 40 (10進数) = 101000 (2進数) なので以下のようになる

01101000 01100101 01101100 01101100 
01101111 10000000 00000000 00000000
00000000 00000000 00000000 00000000
...
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00101000 (512 ビット)

最後の 64 ビットは、メッセージの長さを 2進数で表現した値を追加します。

最終的に事前処理を終えた hello は以下のようになります。

# hello の場合

01101000 01100101 01101100 01101100 
01101111 10000000 00000000 00000000
00000000 00000000 00000000 00000000
...
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00101000 (512 ビット)

3-3. 事前処理 2：ブロックの作成と分割

ここでは、メッセージデータを、512ビットごとに分割し名前をつけていきます。
512ビットごとに分けたデータのことを、**ブロック(Block)**と呼びます。

1. ブロックごとに分ける

# hello の場合
# ブロックは 1 つのみ

01101000 01100101 01101100 01101100 
01101111 10000000 00000000 00000000
00000000 00000000 00000000 00000000
...
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00101000 (512 ビット)

SHA-256のアルゴリズムでは、512 ビット (64 バイト) の単位で計算を行うため、ブロックに分けます。
複数のブロックがある場合、$M^{(1)}, M^{(2)}, … ,M^{(N)}$ と添え字を付けます。hello の場合、1ブロックしかないため、表記の簡易さを取って $M$ としておきます。

2. ブロックをワードに分割する
512 ビットのブロックを、32 ビット * 16 のかたまりにわけます。
この 32 ビットのかたまりを ワード (Word) といいます。

# hello の場合
# 各ブロックを M_t と名前をつける (0 ≦ t ≦ 15)

M_0  = 01101000 01100101 01101100 01101100 
M_1  = 01101111 10000000 00000000 00000000
M_2  = 00000000 00000000 00000000 00000000
...
M_13 = 00000000 00000000 00000000 00000000
M_14 = 00000000 00000000 00000000 00000000
M_15 = 00000000 00000000 00000000 00101000

各 ブロックを、16個のワードに分割し、$M_0, M_1, …, M_{15}$ と名前を付けます。
これで事前処理はおしまいです。

3-4. 使用する定数：H, K

次のアルゴリズム計算の過程で使用する定数 (SHA-256 の初期ハッシュ値) が2種類あるので紹介します。
1. $H$

H_0 = 0x6a09e667 = 0110 1010 0000 1001 1110 0110 0110 0111
H_1 = 0xbb67ae85 = 1011 1011 0110 0111 1010 1110 1000 0101
H_2 = 0x3c6ef372 = 0011 1100 0110 1110 1111 0011 0111 0010
H_3 = 0xa54ff53a = 1010 0101 0100 1111 1111 0101 0011 1010
H_4 = 0x510e527f = 0101 0001 0000 1110 0101 0010 0111 1111
H_5 = 0x9b05688c = 1001 1011 0000 0101 0110 1000 1000 1100
H_6 = 0x1f83d9ab = 0001 1111 1000 0011 1101 1001 1010 1011
H_7 = 0x5be0cd19 = 0101 1011 1110 0000 1100 1101 0001 1001

$H_0, \dots, H_8$の合計 8 個あります。それぞれ 32ビットです。
(0xは16進数であることを表します。0x6a09e667なら、6a09e667という16進数です。)
この定数の作られ方は以下の通りです。

1) 最初の8個の素数を取ります（$2, 3, 5, 7, 11, 13, 17, 19$）
2) それぞれのルートをとります
・2の場合：$\sqrt{2} = 1.41421356237309…$
3) 各小数部分を取り出します
・2の場合：$0.41421356237309…$
4) 各小数部分を32ビットの整数に変換します
・2の場合 ：

\begin{align*}
& ~~~~~~~~0.41421356237309  \\
&→ \phantom{0} 0.01101010000010011110011001100111 \\ 
&→ \phantom{0} 0110 ~ 1010 ~ 0000 ~ 1001 ~ 1110 ~ 0110 ~  0110 ~ 0111 \\ 
&→ \phantom{0}6a09e667
\end{align*}

2. $H$

K = [
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
];

$K_0, \dots, K_{63}$ の合計64 個定義します。左上から右に行くと${K_0, K_1, K_2,...}$となります。
H と作り方はほぼ同様です。違いは、

1. 最初の 64 個の素数を取ること
2. それぞれの三乗根を取ること

です。次からやっと、アルゴリズムの計算に入ります。

3-5. 計算1：W

$W_0, \dots, W_{63}$ の合計64 個を以下の式で定義します。

W_t = \begin{cases} 
M_t & 0 \leq t \leq 15 \\ 
\sigma_1(W_{t-2}) + \sigma_0(W_{t-15}) + W_{t-16} & 16 \leq t \leq 63 
\end{cases}

最初の 15 個は、$M_t$ とおなじ です。

# hello の場合

W_0  = M_0  = 01101000 01100101	01101100 01101100 
W_1  = M_1  = 01101111 10000000 00000000 00000000
W_2  = M_2  = 00000000 00000000 00000000 00000000
...
W_13 = M_13 = 00000000 00000000 00000000 00000000
W_14 = M_14 = 00000000 00000000 00000000 00000000
W_15 = M_15 = 00000000 00000000 00000000 00101000

 残りの 39 個 $W_{16}, …W_{63}$は、$W_0, … ,W_{15}$ を使って求めます。
たとえば、$W_{16} = \sigma_1(W_{14}) + W_{t-7} + \sigma_0(W_{1}) + W_{0}$ のように求めます。

ここでナゾの $\sigma_0,\ \sigma_1$ について説明します。

$\sigma_0$ について

4段階の操作によって定義されます。

1. 右回りに7つローテーション
2. 右回りに18つローテーション
3. 右に3つシフト
4. それぞれのケタに対し、1の個数が奇数個 (1個) だったら 1を、そうでなかったら 0 を返す

最後のケタを1つ右にローテーションしたら、一番左の位にきます。
最後のケタを1つ右シフトしたらいなくなります。その代わり一番左の位に 0 が追加されます。

具体例 $W_1 = 01101111 ~10000000 ~ 00000000 ~ 00000000$ で見ていきます。

01101111 10000000 00000000 00000000　(元のビット列)

00000001 10111110 00000000 00000000  (7ビット右循環シフト)
00000000 00000011 01111100 00000000  (18ビット右循環シフト)
00001101 11110000 00000000 00000000  (3ビット右シフト)
------------------------------------ (XOR)
00001100 01001101 01111100 00000000  (結果)

7ビット右循環シフトでは、すべてのケタが7つローテーションしていること、
3ビット右シフトでは、すべてのケタが3つ右にシフトいていることがわかると思います。

参考：
ローテーションを定式化すると$~ROTR^n(x) = (x >>n)  \lor (x << 32 - n)$、
シフト演算を定式化すると$~SHR^n(x) = x>>n$
となります。
これを用いると、$\sigma_0(x) = ROTR^7(x) \oplus ROTR^18(x) \oplus SHR^3(x)$ と定式化できます。
ここで、演算子について復習です。

演算子	説明
$\land$	AND 演算子
$\lor$	OR 演算子
$\oplus$	XOR 演算子
>>	右ビットシフト. $x>>n$ で、$x$ は $n$ 分右にシフト
<<	左ビットシフト. $x<<n$ で、$x$ は $n$ 分左にシフト

$\sigma_1$ について

$\sigma_0$ とほぼ同様の操作が、4段階で定義されます。

1. 右回りに17つローテーション
2. 右回りに19つローテーション
3. 右に10つシフト
4. それぞれのケタに対し、1の個数が奇数個 (1個) だったら 1を、そうでなかったら 0 を返す

同様の例 $W_1 = 01101111 ~10000000 ~ 00000000 ~ 00000000$ でみていきます。

01101111 10000000 00000000 00000000  (元のビット列)

00000000 00000001 10111110 00000000  (17ビット右循環シフト)
00000000 00000110 11111000 00000000  (19ビット右循環シフト)
00000000 00011011 11100000 00000000  (10ビット右シフト)
------------------------------------ (XOR)
00000000 00011100 10000110 00000000  (結果)

参考：$\sigma_1(x) = ROTR^{17}(x) \oplus ROTR^{19}(x) \oplus SHR^{10}(x)$ と定式化できます

この 2つの関数、$\sigma_0, ~ \sigma_1$ によって、$W_{16}, …W_{63}$ が計算されます。

3-6. 計算2：a,b,c…,h

8つの値 $a,b,c,…,h$ を計算します。(この8つの値を、作業変数(Working variables)といいます。)
まず、定数 $H_0, …H_7$ を使って初期化します。

\displaylines{
a = H_0 \\ b= H_1 \\c = H_2 \\d = H_3 \\e = H_4 \\f = H_5 \\g = H_6 \\h = H_7 
}

そして、$a,b,c,…,h$ を以下のループで更新します。

For $t = 0$ to $63$:

\begin{array}{lcl}\{ 
\\T_1 = h + \sum_1(e) + Ch(e,f,g) + K_t + W_t 
\\T_2 = \sum_0(a) + Maj(a,b,c) 
\\h = g \\g = f \\f = e \\e = d + T_1 \\d = c \\c = b \\b = a \\a = T_1 + T_2 \\\}\end{array}

ここで新しい関数 $\sum_0, \sum_1, Ch(e,f,g), Maj(a,b,c)$ がでてきました。

$\sum_0, ~ \sum_1$ について

$\sum_0, \sum_1$は 小文字 $\sigma_0, \sigma_1$ と似た処理をします。

$\sum_0$の動作

1. 右回りに2つローテーション
2. 右回りに13つローテーション
3. 右回りに22つローテーション
4. それぞれのケタに対し、1の個数が奇数個 (1個) だったら 1を、そうでなかったら 0 を返す

$\sum_1$の動作

1. 右回りに6つローテーション
2. 右回りに11つローテーション
3. 右回りに25つローテーション
4. それぞれのケタに対し、1の個数が奇数個 (1個) だったら 1を、そうでなかったら 0 を返す

参考：$\sum_0, \sum_1$はそれぞれ以下のように定式化できます。
$\sum_0(x) = ROTR^{2}(x) \oplus ROTR^{13}(x) \oplus ROTR^{22}(x)$
$\sum_1(x) = ROTR^{6}(x) \oplus ROTR^{11}(x) \oplus ROTR^{25}(x)$


$Ch(e,f,g)$ について

$Ch(e,f,g)$は変わった動きをします。
具体例で説明します。

e = 0101 0001 0000 1110 0101 0010 0111 1111
f = 1001 1011 0000 0101 0110 1000 1000 1100
g = 0001 1111 1000 0011 1101 1001 1010 1011

上の $e, f, g$において、$e$ の数字が、

1. 1 であった場合は、同じ位 の $f$ を参照し、
2. 0 であった場合は、同じ位 の $g$ を参照します

上のルールをもとに計算すると、$Ch(e,f,g)$ の計算結果は次のような結果になります。
$f,g$に刺されている矢印が、$e$ によって参照されている値になります。

    ↓↓↓↓
e = 0101 0001 0000 1110 0101 0010 0111 1111
     ↓ ↓
f = 1001 1011 0000 0101 0110 1000 1000 1100
    ↓ ↓
g = 0001 1111 1000 0011 1101 1001 1010 1011
--------------------------------------------
    0001 1111 1000 0101 1100 1001 1000 1100

参考：$Ch(x,y,z)$ を定式化すると$Ch(x,y,z) = (x \land y) \oplus (\neg x \land z)$となります。

最後に $Maj(a,b,c)$ の説明です。
この関数は、$a,b,c$ の各位で、多い方の値を採用します。つまり以下のような計算になります。

a = 0110 1010 0000 1001 1110 0110 0110 0111
b = 1011 1011 0110 0111 1010 1110 1000 0101
c = 0011 1100 0110 1110 1111 0011 0111 0010
--------------------------------------------
    0011 1010 0110 1111 1110 0110 0110 0111

参考：$Maj(x,y,z)$ を定式化すると$Maj(x,y,z) = (x \land y) \oplus (x \land z) \oplus (y \land z)$となります。

上で定義した $\sum_0, ~ \sum_1, ~ Ch(e,f,g), ~ Maj(a,b,c)$ を使って 64 回ループすることで、$a,b,…,h$ の値をどんどん更新していきます。

3-7. 計算3：H の更新

最終的に $H$ は以下のように更新されます。

\displaylines {
H_0^{(1)} = a + H_0 \\
H_1^{(1)} = b+ H_1 \\H_2^{(1)} = c + H_2 \\H_3^{(1)} = d + H_3 \\H_4^{(1)} = e + H_4 \\H_5^{(1)} = f + H_5 \\H_6^{(1)} = g + H_6 \\H_7^{(1)} = h + H_7 
}

そして、$H_0^{(1)},…,H_7^{(1)}$を連結させることで最終的に出力されるハッシュ値が得られます。
各$H_t^{(1)}$は 32ビットなので、最終的なビット数は $32 \times 8 = 254$ ビットになります。

hello の場合、最終的な出力は 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 であるので、$H_0^{(1)},…,H_7^{(1)}$ は以下であったと予想できます。

# hello の場合
# 8つ (32ビット) ずつ分割すると以下のようになる
2cf24dba 5fb0a30e 26e83b2a c5b9e29e 1b161e5c 1fa7425e 73043362 938b9824

# よって
H_0^{(1)} = 2cf24dba 
H_1^{(1)} = 5fb0a30e 
H_2^{(1)} = 26e83b2a 
H_3^{(1)} = c5b9e29e 
H_4^{(1)} = 1b161e5c 
H_5^{(1)} = 1fa7425e 
H_6^{(1)} = 73043362 
H_7^{(1)} = 938b9824

以上で SHA-256 のアルゴリズムの説明は終了です。

3-8. 結局なにをしていたのか

あれこれと処理をして、どんな文字列でも512ビットの一意な値に書き換えることができました。
結局何をしてたからそうなったのか、要点はどこなのかを振り返ります。

SHA-256 の核となる部分は、64 ラウンドの圧縮関数です。(作業変数 $a,b,...h$ について　for ループを 64回したところ) ここの複雑さによって、ハッシュ関数の不可逆性が保証されています。具体的に複雑さを増やしている箇所は以下の通りです。

1. $\sigma_0, ~ \sigma_1, ~ \sum_0, ~\sum_1, ~ Ch(x,y,z), ~ Maj(x,y,z)$ という非線形関数を使うことで、複雑さを増やし、少しでも入力の小さな変化が出力の結果を大きく変えています
2. $SHR^n(x)$などのシフト演算は、はみ出た値は消去されてしまうため、一方向
   性があります。これにより、復号がますます困難になっています
3. $K_t$, $W_t$ という、ループの度に異なる定数を使っていることも複雑さを増す要因です

そして、このループ処理を効率よく行うために、512ビットというブロックわけを行う必要があったのだと思います。

また、512ビットという程よく大きいブロックを採用したり、メッセージ長を情報として含ませたりすることで、異なるメッセージから同じハッシュ値が生まれてきにくくしている（衝突耐性がある）と思います。

アルゴリズムを読み解くこと自体はそこまで難しくありませんが、作者の工夫が詰まった作りになっているのだなあ、と関心しました。

4. 実装

4-1. SHA256 を JavaScript で書く

具体的にコードに落とし込むとどうなるかを見ていきます。
こちらの記事 が参考になりました。(というかほとんどこれに書いてあります。)
上のコードを参考にしながら、hello の場合に、どのように変数に値が格納されていくのかを観察することで、理解を深めていきます。

// 定数 H
const H0 = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
];

// 定数 K
const K = [
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
];

// 文字列のハッシュ化
// msg: ハッシュ化する文字列
function padding(msg) {   // msg = 'hello'

    // メッセージをASCIIコードの配列に変換
    let asciiMsg = msg.split('').map(char => char.charCodeAt(0));  // asciiMsg = [72, 101, 108, 108, 111].
    let len = asciiMsg.length;  // len = 5

    let tmp = Array(64);  // tmp = [0, 0, 0, ..., 0] (64個の0)
    tmp.fill(0);
    // 文字列と000...と続く間の `1`
    tmp[0] = 0x80;  // tmp = [128, 0, 0, ..., 0] (先頭は128, 残りは0) 内部的に整数として正確に表現される.
    let bs = asciiMsg.concat();  // bs = [72, 101, 108, 108, 111]

    if (len % 64 < 56) {  // true (5 % 64 = 5)
        bs = bs.concat(tmp.slice(0, 56 - len % 64));   // bs = [72, 101, 108, 108, 111, 128, 0, 0, ..., 0] (56 bytes)
    } else {
        bs = bs.concat(tmp.slice(0, 64 + 56 - len % 64));
    }

    // メッセージ長をビット数に変換
    let bits = len * 8;  // bits = 40
    // メッセージ長を保存するための配列
    let size = [0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00];  // size = [0, 0, 0, 0, 0, 0, 0, 0]
    // javaScirpt は 32ビットの整数値しか保存できないので、32ビット目から考える
    size[4] = (bits & 0xff000000) >> 24;  // size[4] = 0.  0xff000000 は最初の 8ビットだけ取り出すためのビットマスク
    size[5] = (bits & 0x00ff0000) >> 16;  // size[5] = 0
    size[6] = (bits & 0x0000ff00) >> 8;   // size[6] = 0
    size[7] = (bits & 0x000000ff);        // size[7] = 40
    bs = bs.concat(size);  // size = [0, 0, 0, 0, 0, 0, 0, 40]

    // パディング後の配列
    return bs;  // [72, 101, 108, 108, 111, 128, 0, 0, ..., 0, 0, 0, 0, 40] (64 bytes)
}

// 1. ビット操作に使う関数
// 1-1. 右に n ビット巡回
function ROTR(x, n) {
    return (x >>> n) | (x << (32 - n));
}

// 1-2. 右に nビットシフト
function SHR(x, n) {
    return x >>> n;
}


// 2. SHA256 で使用する 6つの関数
// 2-1. Choose
function Ch(x, y, z) {
    return (x & y) ^ (~x & z);
}

// 2-2. Majority
function Maj(x, y, z) {
    return (x & y) ^ (x & z) ^ (y & z);
}

// 2-3
function sigma0(x) {
    return ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3);
}

// 2-4
function sigma1(x) {
    return ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10);
}

// 2-5
function SIGMA0(x) {
    return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22);
}

// 2-6
function SIGMA1(x) {
    return ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25);
}


// msg: padding された array
function compute(msg) {
    // メッセージを N 個のメッセージブロック M^(0), ..., M^(N) に分割
    let N = msg.length / 64; // N = 1
    let W = [];
    let H = [];
    for (let i = 0; i < H0.length; i++) {
        H[i] = H0[i];
    }

    // 各メッセージブロックに対して処理
    for (let i = 1; i <= N; i++) {
        for (let t = 0; t < 64; t++) {
            if (t < 16) {
                // W[t] のスタートライン
                let p = (i - 1) * 64 + t * 4;
                // 8 ビットずつ左につめて、32 ビットの M_t^(i) を作成.
                W[t] = (msg[p] << 24) + (msg[p + 1] << 16) + (msg[p + 2] << 8) + msg[p + 3];
                // W[0] = 0x48656c6c (最初の4バイト: "Hell")
                // W[1] = 0x6f800000 (次の4バイト: "o" + padding)
                // W[2] から W[14] = 0x00000000 (padding)
                // W[15] = 0x00000028 (メッセージ長: 40)
            } else {
                W[t] = (sigma1(W[t - 2]) + W[t - 7] + sigma0(W[t - 15]) + W[t - 16]) & 0xffffffff;
            }
        }

        let a = H[0];
        let b = H[1];
        let c = H[2];
        let d = H[3];
        let e = H[4];
        let f = H[5];
        let g = H[6];
        let h = H[7];

        for (let t = 0; t < 64; t++) {
            let T1 = (h + SIGMA1(e) + Ch(e, f, g) + K[t] + W[t]) & 0xffffffff;
            let T2 = (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;
        }

        // ハッシュ値を符号なし32ビット整数に変換
        H[0] = (a + H[0]) >>> 0;
        H[1] = (b + H[1]) >>> 0;
        H[2] = (c + H[2]) >>> 0;
        H[3] = (d + H[3]) >>> 0;
        H[4] = (e + H[4]) >>> 0;
        H[5] = (f + H[5]) >>> 0;
        H[6] = (g + H[6]) >>> 0;
        H[7] = (h + H[7]) >>> 0;
    }

    // ハッシュ値を16進数表現に変換して返す
    return H.map(value => value.toString(16).padStart(8, '0')).join('');
}


// ハッシュ計算のエントリポイント
module.exports = function findHash(msg) {
    let paddedMessage = padding(msg);
    let hash = compute(paddedMessage);
    return hash;
}

4-2. テストをする

実際に正しいコードかは、既存のライブラリを使って以下のようにできます。

const CryptoJS = require('crypto-js');
const findHash = require('./hash');

// テスト用の関数
function testSHA256(message) {
    // crypto-jsを使ってSHA-256ハッシュを計算
    const expectedHash = CryptoJS.SHA256(message).toString();

    // 作成した関数を使ってSHA-256ハッシュを計算
    const computedHash = findHash(message);

    // 結果を比較
    if (computedHash === expectedHash) {
        console.log(`Test passed: ${message}`);
    } else {
        console.log(`Test failed: ${message}`);
        console.log(`Expected: ${expectedHash}`);
        console.log(`Computed: ${computedHash}`);
    }
}

// passed
testSHA256('');
testSHA256('Hello');
testSHA256('The quick brown fox jumps over the lazy dog');
testSHA256('Lorem ipsum dolor sit amet, consectetur adipiscing elit.');
testSHA256('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789');

これで実装のお話は終わります。

5. さいごに

ハッシュ化の概要から、代表的なSHA-256 のアルゴリズムを理解し、実際に実装するところまでを行いました。
不思議だったハッシュ関数というブラックボックスの中身を明らかにし、現代のセキュリティを支えられる強固さの理由も知れて満足です。
最後までお読みいただきありがとうございました！

6. 参考文献

わかりやすく SHA256 アルゴリズムを解説している

実装の記述