はじめに(Introduction)
SHA-256のロジックを理解する必要が出てきたので、仕様を確認しつつjavascriptで実装してみます。
また、ビット単位ではなく、バイト単位でのSHA-256を想定します。
サイズ(Size)
SHA-256では、ブロックサイズ(Block Size)512bits(64bytes)、ワードサイズ(Word Size)32bits(4bytes)、メッセージダイジェストサイズ(Message Digest Size)256bits(32bytes)となっています。(参考文献1 p.3)
メッセージのパディング(Padding the Message)
(参考文献1 p.13)
あるメッセージが与えられた場合、ハッシュの計算をするためにはブロックサイズの倍数である必要があります。
したがって、64byteの倍数でなければなりません。
単純に0x00で埋めると元々0x00が入っているメッセージと区別がつかなくなる為、
メッセージに区切り用のバイト(0x80)とサイズ(ビット長)を加えます。
※：仕様では区切りは1ビットですが、ここではバイト単位で考えるので、100000002=0x80となります。
例えば、メッセージが次の場合
01
メッセージの区切りに「80」を入れ、メッセージのビット長「00000000 00000008」(1byte * 8bit/byte = 8bits)を設定します。
01800000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000008
function padding(msg) {
let len = msg.length;
let tmp = Array(64);
tmp.fill(0);
tmp[0] = 0x80;
let bs = msg.concat();
if (len % 64 < 56) {
bs = bs.concat(tmp.slice(0, 56 - len % 64));
} else {
bs = bs.concat(tmp.slice(0, 64 + 56 - len % 64));
}
let bits = len * 8;
let size = [0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00];
size[4] = (bits & 0xff000000) >> 24;
size[5] = (bits & 0x00ff0000) >> 16;
size[6] = (bits & 0x0000ff00) >> 8;
size[7] = (bits & 0x000000ff);
bs = bs.concat(size);
return bs;
}
区切りと0x00埋めは最大で64bytesなので、tmpとして64byteの配列を作成します。
先頭は0x80の区切りバイトとします。
長さを64で割ったあまりを考えます。
区切りと0x00埋めの後に、サイズが8bytes付加されるので、64-8=56bytesより小さいか判定します。
小さい場合、ブロックサイズを満たすまでに、区切りとサイズが収まりますが、
大きい場合、さらにブロックサイズ(64bytes)を加える必要があります。
サイズはビットの長さなので、バイト数の8倍となります。
javascriptの配列長が32bit長しか対応していないのと、ビット演算が32bitしか対応してないなどにより
サイズは32bit長までの対応とします。したがって、後半の4bytesだけサイズを設定します。
例：メッセージが55bytesの場合
01020304 05060708 090a0b0c 0d0e0f10 11121314 15161718 191a1b1c 1d1e1f20
21222324 25262728 292a2b2c 2d2e2f30 31323334 35363780 00000000 000001b8
例：メッセージが56bytesの場合
01020304 05060708 090a0b0c 0d0e0f10 11121314 15161718 191a1b1c 1d1e1f20
21222324 25262728 292a2b2c 2d2e2f30 31323334 35363738 80000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 000001c0
変数(Parameters)
(参考文献1 p.4-5)
計算で使用される変数です。
ループやビット演算で使われます。
| 変数 | 概要 |
|---|---|
| $a,b,c,d,e,f,g,h$ | 32-bitの変数です。ハッシュ値を求める時に使います。 |
| $N$ | パディングされたメッセージのブロック数です。 要するに、パディングされたメッセージのバイト数をブロックサイズ(64bytes)で割った数です。 |
| $H^{(i)}$ | $i$番目のハッシュ値です。 |
| $H^{(i)}_j$ | $i$番目のハッシュ値の$\ j$番目のワードです。 要するに、ハッシュ値は32bytes、ワードは4bytesなので、8個のワードを持ちます。 |
| $M^{(i)}$ | $i$番目のメッセージブロックです。 |
| $M^{(i)}_j$ | $i$番目のメッセージブロックの$\ j$番目のワードです。 要するに、メッセージブロックは64bytes、ワードは4bytesなので、16個のワードを持ちます。 |
| $K_t$ | ハッシュ計算で使われる固定値です。$t$個あります。 SHA-256は64個です。 |
記号(Symbols)
(参考文献1 p.5-6)
ビット演算の記号です。
| 演算子 | 概要 |
|---|---|
| $\quad\land\quad$ | AND演算子です。javascriptでは&になります。 |
| $\lor$ | OR演算子です。javascriptでは | になります。 |
| $\oplus$ | XOR演算子です。javascriptでは^になります。 |
| $\lnot$ | NOT演算子です。javascriptでは~になります。 |
| $+$ | 加算です。ただし、ワード長(32bits)のみの有効となりますので、0xffffffffの剰余となります。 |
| $\ll$ | 左ビットシフトです。$x\ll n$で$x$の値を左へ$n$ビットシフトします。シフトされた部分は0で埋められます。javascriptでは<<になります。 |
| $\gg$ | 右ビットシフトです。$x\gg n$で$x$の値を右へ$n$ビットシフトします。シフトされた部分は0で埋められます。javascriptでは>>>になります。 |
※：javascriptでは、ビット演算は32bitsで行われます。
したがって、左ビットシフトをしても32bits長を超えたビットは無視(削除)されます。
ここまでは、通常のビット演算ですが、ちょっとローテーションの関数を定義します。
| 操作 | 概要 |
|---|---|
| $\text{ROTR}^{n}(x)$ | 右に$\ n$ビット巡回する操作です。 定義としては、次のようになります。 $0\le n < w$ $\text{ROTR}^{n}(x)=(x\gg n)\lor (x \ll w - n)\ $ $w$はワード長となりますので、SHA-256では、 $0\le n < 32$ $\text{ROTR}^{n}(x)=(x\gg n)\lor (x \ll (32 - n))$ となります。 |
| $\text{SHR}^{n}(x)$ | 右に$\ n$ビット巡回する操作です。 定義としては、次のようになります。 $0\le n < w$ $\text{SHR}^{n}(x)=x\gg n\ $ $w$はワード長となりますので、SHA-256では、 $0\le n < 32$となります。 |
実装はいかのとおりです。
function ROTR(x, n) {
return (x >>> n) | (x << (32 - n));
}
function SHR(x, n) {
return x >>> n;
}
関数(Function)
(参考文献1 p.10)
SHA-256では6個の関数を使用します。
いずれも、ワード長の32bitsで動作します。
$x,y,z$は32bitsのワードとなります。
要するに、32bitsでのビット演算関連の関数となります。
\begin{align*}
\text{Ch}(x,y,z) &= (x \land y)\oplus(\lnot x \land z) \\
\text{Maj}(x,y,z) &= (x \land y)\oplus(x \land z)\oplus(y \land z) \\
\Sigma^{\{256\}}_0(x) &= \text{ROTR}^{2}(x)\oplus\text{ROTR}^{13}(x)\oplus\text{ROTR}^{22}(x) \\
\Sigma^{\{256\}}_1(x) &= \text{ROTR}^{6}(x)\oplus\text{ROTR}^{11}(x)\oplus\text{ROTR}^{25}(x) \\
\sigma^{\{256\}}_0(x) &= \text{ROTR}^{7}(x)\oplus\text{ROTR}^{18}(x)\oplus\text{SHR}^{3}(x) \\
\sigma^{\{256\}}_1(x) &= \text{ROTR}^{17}(x)\oplus\text{ROTR}^{19}(x)\oplus\text{SHR}^{10}(x) \\
\end{align*}
実装はいかのとおりです。
function Ch(x, y, z) {
return (x & y) ^ (~x & z);
}
function Maj(x, y, z) {
return (x & y) ^ (x & z) ^ (y & z);
}
function SIGMA0(x) {
return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22);
}
function SIGMA1(x) {
return ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25);
}
function sigma0(x) {
return ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3);
}
function sigma1(v) {
return ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10);
}
固定値(Constants)
ハッシュ計算を行うときに使う値です。
(参考文献1 p.11)
\begin{align*}
K_{0}^{\{256\}}=\texttt{428a2f98}\ ,\ K_{1}^{\{256\}}=\texttt{71374491}\ ,\ K_{2}^{\{256\}}=\texttt{b5c0fbcf}\ ,\ K_{3}^{\{256\}}=\texttt{e9b5dba5} \\
K_{4}^{\{256\}}=\texttt{3956c25b}\ ,\ K_{5}^{\{256\}}=\texttt{59f111f1}\ ,\ K_{6}^{\{256\}}=\texttt{923f82a4}\ ,\ K_{7}^{\{256\}}=\texttt{ab1c5ed5} \\
K_{8}^{\{256\}}=\texttt{d807aa98}\ ,\ K_{9}^{\{256\}}=\texttt{12835b01}\ ,\ K_{10}^{\{256\}}=\texttt{243185be}\ ,\ K_{11}^{\{256\}}=\texttt{550c7dc3} \\
K_{12}^{\{256\}}=\texttt{72be5d74}\ ,\ K_{13}^{\{256\}}=\texttt{80deb1fe}\ ,\ K_{14}^{\{256\}}=\texttt{9bdc06a7}\ ,\ K_{15}^{\{256\}}=\texttt{c19bf174} \\
K_{16}^{\{256\}}=\texttt{e49b69c1}\ ,\ K_{17}^{\{256\}}=\texttt{efbe4786}\ ,\ K_{18}^{\{256\}}=\texttt{0fc19dc6}\ ,\ K_{19}^{\{256\}}=\texttt{240ca1cc} \\
K_{20}^{\{256\}}=\texttt{2de92c6f}\ ,\ K_{21}^{\{256\}}=\texttt{4a7484aa}\ ,\ K_{22}^{\{256\}}=\texttt{5cb0a9dc}\ ,\ K_{23}^{\{256\}}=\texttt{76f988da} \\
K_{24}^{\{256\}}=\texttt{983e5152}\ ,\ K_{25}^{\{256\}}=\texttt{a831c66d}\ ,\ K_{26}^{\{256\}}=\texttt{b00327c8}\ ,\ K_{27}^{\{256\}}=\texttt{bf597fc7} \\
K_{28}^{\{256\}}=\texttt{c6e00bf3}\ ,\ K_{29}^{\{256\}}=\texttt{d5a79147}\ ,\ K_{30}^{\{256\}}=\texttt{06ca6351}\ ,\ K_{31}^{\{256\}}=\texttt{14292967} \\
K_{32}^{\{256\}}=\texttt{27b70a85}\ ,\ K_{33}^{\{256\}}=\texttt{2e1b2138}\ ,\ K_{34}^{\{256\}}=\texttt{4d2c6dfc}\ ,\ K_{35}^{\{256\}}=\texttt{53380d13} \\
K_{36}^{\{256\}}=\texttt{650a7354}\ ,\ K_{37}^{\{256\}}=\texttt{766a0abb}\ ,\ K_{38}^{\{256\}}=\texttt{81c2c92e}\ ,\ K_{39}^{\{256\}}=\texttt{92722c85} \\
K_{40}^{\{256\}}=\texttt{a2bfe8a1}\ ,\ K_{41}^{\{256\}}=\texttt{a81a664b}\ ,\ K_{42}^{\{256\}}=\texttt{c24b8b70}\ ,\ K_{43}^{\{256\}}=\texttt{c76c51a3} \\
K_{44}^{\{256\}}=\texttt{d192e819}\ ,\ K_{45}^{\{256\}}=\texttt{d6990624}\ ,\ K_{46}^{\{256\}}=\texttt{f40e3585}\ ,\ K_{47}^{\{256\}}=\texttt{106aa070} \\
K_{48}^{\{256\}}=\texttt{19a4c116}\ ,\ K_{49}^{\{256\}}=\texttt{1e376c08}\ ,\ K_{50}^{\{256\}}=\texttt{2748774c}\ ,\ K_{51}^{\{256\}}=\texttt{34b0bcb5} \\
K_{52}^{\{256\}}=\texttt{391c0cb3}\ ,\ K_{53}^{\{256\}}=\texttt{4ed8aa4a}\ ,\ K_{54}^{\{256\}}=\texttt{5b9cca4f}\ ,\ K_{55}^{\{256\}}=\texttt{682e6ff3} \\
K_{56}^{\{256\}}=\texttt{748f82ee}\ ,\ K_{57}^{\{256\}}=\texttt{78a5636f}\ ,\ K_{58}^{\{256\}}=\texttt{84c87814}\ ,\ K_{59}^{\{256\}}=\texttt{8cc70208} \\
K_{60}^{\{256\}}=\texttt{90befffa}\ ,\ K_{61}^{\{256\}}=\texttt{a4506ceb}\ ,\ K_{62}^{\{256\}}=\texttt{bef9a3f7}\ ,\ K_{63}^{\{256\}}=\texttt{c67178f2} \\
\end{align*}
ちなみに、これらは素数の小さい順で64個の数を、立方根した少数部分の32bitsの値です。
実際に計算してみると、0番目の値と$\sqrt[3]{2}$の少数部分が同じであることがわかります。
> console.log(Math.cbrt(2).toString(16));
1.428a2f98d728b
実装は以下のとおりです。
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];
ハッシュ初期値(Initial Hash Value)
(参考文献1 p.15)
ハッシュ値の初期値です。8個のワード(32bits)が設定されます。
値は16進数表記です。
\begin{align*}
H_0^{(0)} &= \texttt{6a09e667} \\
H_1^{(0)} &= \texttt{bb67ae85} \\
H_2^{(0)} &= \texttt{3c6ef372} \\
H_3^{(0)} &= \texttt{a54ff53a} \\
H_4^{(0)} &= \texttt{510e527f} \\
H_5^{(0)} &= \texttt{9b05688c} \\
H_6^{(0)} &= \texttt{1f83d9ab} \\
H_7^{(0)} &= \texttt{5be0cd19} \\
\end{align*}
ちなみに、これらは素数の小さい順で8個の数を、平方根した少数部分の32bitsの値です。
実際に計算してみると、0番目の値と$\sqrt{2}$の少数部分が同じであることがわかります。
> console.log(Math.sqrt(2).toString(16));
1.6a09e667f3bcd
実装は以下のとおりです。
const H0 = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19];
SHA256ハッシュ計算(SHA-256 Hash Computation)
(参考文献1 p.22-23)
メッセージを$N$個のメッセージブロック、$M^{(0)},M^{(1)},\cdots,M^{(N)}$に分割します。
※：パディング処理で64bytesの倍数になるので、各メッセージブロックは64bytesとなります。
加算($+$)は、0xffffffffの剰余となります。
各メッセージブロックに対し次のステップを行います。
$\text{For}\ i=1\ \text{to}\ N \text{:}$
{
let N = msg.length / 64;
let W = [];
let H = [];
for (let i = 0; i < H0.length; i++) {
H[i] = H0[i];
}
for (let i = 1; i <= N; i++) {
メッセージ数$N$を計算したあと、メッセージスケジュール変数を作成し、
ハッシュ値に初期値を設定します。
それから、メッセージ数分ループします。
1.メッセージスケジュールを準備します。
\begin{eqnarray}
W_t=\left\{ \begin{array}{ll}
M_t^{(i)} & 0 \le t \le 15 \\
\\
\sigma^{\{256\}}_1(W_{t-2})+W_{t-7}+\sigma^{\{256\}}_0(W_{t-15})+W_{t-16} & 16 \le t \le 63 \\
\end{array} \right.
\end{eqnarray}
for (let t = 0; t < 64; t++) {
if (t < 16) {
let p = (i - 1) * 64 + t * 4;
W[t] = (msg[p] << 24) + (msg[p + 1] << 16) + (msg[p + 2] << 8) + msg[p + 3];
} else {
W[t] = (sigma1(W[t - 2]) + W[t - 7] + sigma0(W[t - 15]) + W[t - 16]) & 0xffffffff;
}
}
メッセージはbyte配列なので、4byte毎の数値にします。
17個以降は計算で求めます。本来は剰余ですがjavascriptのビット演算で32bitsとなるので、
&で剰余と同じ演算を行っています。
2.$(i-1)$番目のハッシュ値で $a,b,c,d,e,f,g,h$ を初期化します。
\begin{align*}
a &= H_0^{(i-1)} \\
b &= H_1^{(i-1)} \\
c &= H_2^{(i-1)} \\
d &= H_3^{(i-1)} \\
e &= H_4^{(i-1)} \\
f &= H_5^{(i-1)} \\
g &= H_6^{(i-1)} \\
h &= H_7^{(i-1)} \\
\end{align*}
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];
$a,b,c,d,e,f,g,h$を初期化します。
3.$\ a,b,c,d,e,f,g,h$の計算
\begin{align*}
& \text{For}\ t=1\ \text{to}\ 63\ \text{:} \\
& \{ \\
& \qquad T_1 = h + \Sigma^{\{256\}}_1(e) + \text{Ch}(e,f,g) + K_t^{\{256\}} + W_t \\
& \qquad T_2 = \Sigma^{\{256\}}_0(a) + \text{Maj}(a,b,c)\\
& \qquad h = g \\
& \qquad g = f \\
& \qquad f = e \\
& \qquad e = d + T_1 \\
& \qquad d = c \\
& \qquad c = b \\
& \qquad b = a \\
& \qquad a = T_1 + T_2 \\
& \} \\
\end{align*}
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;
}
剰余は&で計算しています。
4.$(i-1)$番目のハッシュ値を計算
\begin{align*}
H_0^{(i)} &= a + H_0^{(i-1)} \\
H_1^{(i)} &= b + H_1^{(i-1)} \\
H_2^{(i)} &= c + H_2^{(i-1)} \\
H_3^{(i)} &= d + H_3^{(i-1)} \\
H_4^{(i)} &= e + H_4^{(i-1)} \\
H_5^{(i)} &= f + H_5^{(i-1)} \\
H_6^{(i)} &= g + H_6^{(i-1)} \\
H_7^{(i)} &= h + H_7^{(i-1)} \\
\end{align*}
}
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 H;
剰余は&で計算しています。
テスト(Test Vectors)
「参考文献2」の「SHA Test Vectors for Hashing Byte-Oriented Messages」
にあるテストを実施して実装が正しいか判断します。
さいごに(Conclusions)
javascriptの制限により完全ではありませんが、実装できました。
メッセージブロック毎に一周するので、64バイトづつ計算する事ができます。
したがって、工夫すれば、もう少し効率よく計算出来るかもしれません。
今回のソースコードは、githubにあります。
参考文献(Reference)
-
Secure Hash Standard (SHS)
NISTが公表しているSHA-256などの仕様です。 -
Cryptographic Algorithm Validation Program
SHA-256のTest Vectorsです。