開発部たより | ハッシュ化を理解する

2024年6月10日 19:45

はじめに

開発部のたかみんです！「ハッシュ化」のお勉強会を開きました。その記録をまとめます。

学ぶにいたるまでの流れ

開発部では、11/23 の文化祭で「ブロックチェーンを使ったゲームを作ろう」と意気込んでいます。そのためには、ブロックチェーンに使われている根幹の技術について、知ったぶりをなくす必要がでてきました。その学ぶの項目の 1 つが、ハッシュ化です。

今回の流れ

ハッシュ化について、以下の流れで理解を深めていきました。

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

順に解説します。理論と実装では、SHA-256 を題材にしました。

1. 概要

ハッシュ化とは

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

使われている場面では、
1) パスワードをハッシュ化して保存・管理
2) チェックサム（ある時点でデータが改ざんされていないかを確認）
などがあります。
1 については、第三者が不正にパスワードへアクセスしたとしても、ランダムな文字列に変換されていることで、悪用されるのを防ぐことができます。
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 (と pepper）、レインボーテーブル攻撃について少し解説をします。

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 が盗まれても元の値がわかることはありません。

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

2. 理論

SHA-256 の理論と実装に取り組みます。

ふるまいと性質

$hello
2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

$ good morning
cdf71dea7d7741a2b6f021f3dd344f75c8333988f547866a8fbf28f064cf7c78

$ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
6bd5e5034855a11241f0dee8fc72850ffd9955b28347a86428b5fa19119f6ad0

入力データの長さにかかわらず、常に256 ビットの数が返ってきます。(SHA-256 の '256' の意味です。)
16進数の数が 32 個なので、4 bits * 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 ページの本に相当します。よって元のデータの大きさは気にする必要はありません。

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

ここからは、SHA-256 のハッシュ化がどのように行われるかを、文字列 'hello' を例にとって説明します。まず下処理をします。

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 引いた数になるようにします。
1) 文字列が 40 ビットの場合 448 (= 512 - 64) ビットになるまで
2) 文字列が 500 ビットの場合、512 ビットでは残り 64 ビットもありません。そのため、512 * 2 = 1024 ビットまで長さを延長し、960 (= 1024 - 64) ビットになるまで、0を敷き詰めます。
余らせた最後の 64 ビットは、次のステップで使用します。

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

# hello の場合
# メッセージ長さ：40 bits
# 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 ビット)

事前処理 2：メッセージのスライス

1. 512 ビットごとのかたまりに分ける

# hello の場合
# 512 bits のブロックは 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 ビット)

ハッシュ化の処理は、512 ビット (64 バイト) の単位で行うため、512 ビットごとに事前処理した数値をわけます。
複数のブロックがある場合、$${M^{(1)}, M^{(2)}, … ,M^{(N)}}$$ と添え字を付けます。hello の場合、一ブロックしかないため $${M}$$ としておきます。

2. 各 512 ビットのブロックを 32 ビット * 16 で分割する

# 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

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

使用する定数：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ビットです。
この定数の作られ方は以下の通りです。
1) 最初の8個の素数を取る（2, 3, 5, 7, 11, 13, 17, 19）
2) それぞれのルートをとる
・2の場合：$${\sqrt{2} = 1.41421356237309…}$$
3) 各小数部分を取り出す
・2の場合：$${0.41421356237309…}$$
4) 各小数部分を32ビットの整数に変換します
・2の場合：$${0.41421356237309 \\ → 0.01101010000010011110011001100111 \\ → 0110 ~ 1010 ~ 0000 ~ 1001 ~ 1110 ~ 0110 ~ 0110 ~ 0111 \\ → 6a09e667}$$

2. K

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 個定義します。
H と作り方はほぼ同様です。
違いは、
1) 最初の 64 個の素数を取ること
2) それぞれの三乗根を取ること
です。

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

計算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}}$$ は $${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 を返す。

ローテーションでは、最後のケタは最初にきます。
シフトでは、最後のケタをシフトしたらいなくなります。その代わ最初に 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  (結果)

参考：ローテーションを定式化すると$${ROTR^n(x) = (x >>n) \lor (x << 32 - n)}$$、
シフト演算を定式化すると$${SHR^n(x) = x>>n}$$となります。

$${\sigma_1}$$ について

$${\sigma_0}$$ とほぼ同様の操作が、4段階で定義されます。
1) 右回りに17つローテーション
2) 右回りに19つローテーション
3) 右に10つシフト
4) それぞれのケタに対し、1の個数が奇数個 (1個) だったら 1を、そうでなかったら 0 を返す。

同様の例でみていきます。

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

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

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

計算2：a,b,c…,h

8つの値 $${a,b,c,…,h}$$ を計算します。
まず、定数 $${H_0, …H_7}$$ を使って初期化します。

$$
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}{lcl}
$$

ここで新しい関数 $${\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 を返す。

$${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) 1 であった場合は、同じ位の 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
--------------------------------------------
    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：H の更新

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

$$
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)}}$$を連結させることで最終的に出力されるハッシュ値が得られます。

たとえば 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. 実装

最後は、上のアルゴリズムがどのように実装されるかを掲載します。
詳細の説明は割愛しますが、コメントアウト部分で適宜、msg=hello の場合、各プロセスでどのような値を格納しているのかを提示しています。
JavaScript で実装しました。

// 定数 (Hash Value)
const H0 = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
];

// 定数
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);
    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]
    size[4] = (bits & 0xff000000) >> 24;  // size[4] = 0
    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);
}

// Computation
// 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) {
                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;
}

おわりに & 次回予告

ハッシュ関数を詳しくながめることで、意地でも復号させないぞ、という気合を感じました。このように note にまとめるのもいい機会になりました。

次回は、Yas tha 松蔭先生によるマイニング講義です。ビットコインらしい話題なので楽しみです！

参考文献

↓ 詳しいSHA系のアルゴリズムの記述があります。

https://helix.stormhub.org/papers/SHA-256.pdf

↓ その論文をもとに、わかりやすく解説してくれています。

↓ JavaScript での実装の手順を記載してくれています。

この記事が気に入ったらサポートをしてみませんか？