🦈

フルスクラッチでSHA-256を作る

2021/01/21に公開

2件

ハッシュ値の利用者として中身のアルゴリズムを知っておきたいと思ったのでTypeScriptで1からSHA-256を作ろうと思います。SHA-256は名前そのまま、どんな長さのメッセージでも256bitsのハッシュ値を返す関数です。

完成版はこちら

前提知識

論理演算（論理積とか論理和とか排他的論理和とか）とシフト演算が分かっていれば大体いけます。

論理積はAND。数式上では $\land$ 、コードでは&で表します。
論理和はOR。数式上では $\lor$ 、コードでは|で表します。
排他的論理和はXOR。数式上では $\oplus$ 、コードでは^で表します。

左シフト演算はビット列を左にnビット動かすやつです。値は $2^n$ 倍になります。数式上では $\ll$ 、コードでは<<で表します。
右シフト演算はビット列を右にnビット動かすやつです。値は $2^{-n}$ 倍になります。数式上では $\gg$ 、コードでは符号なしの右シフト演算を使用するので>>>で表します。

下準備

SHA256のハッシュ関数ではメッセージを512bitsのブロックに分けてハッシュ値を算出します。その際に余りや不足が出ては困るので、プリプロセスとして平文のPadding処理を行います。

Padding関数

このPadding処理ではメッセージを512bitsの倍数にして返します。実際の実装ではbyte単位で考えるので512bits = 64byte、64の倍数に拡張して返すという処理になります。

手順

具体的にはメッセージの末尾に0x80(bit単位の1)を加え、残りをメッセージのサイズを表すbyte列と0で埋めるという関数を書くことになります。メッセージサイズを表すbyte列は8bytesで、64bytesからその8bytesを引き、メッセージ分のbyteと0x80の1byteを引いた残りのbyteは0で埋めます。

実装

padding関数ではメッセージの文字列を引数にとって、64bytesの倍数にした16進数のbyte列を文字列の型で返すものです。

let sizeLastBlock: number = 64; // Mの末尾のブロックサイズ
const sizeMLengthBuffer: number = 8; // 最終的なメッセージの末尾8bytesはMのサイズを記述する
const sizeDivision: number = 1; // メッセージバイトと余りの0byteの区切り（0x80）
const sizeMaxBlock: number = sizeLastBlock - sizeMLengthBuffer - sizeDivision; // メッセージバイトは55bytes以下であれば良い

ここは上で説明したサイズをbyteで表したものです。最後のsizeMaxBlockは、メッセージを入れられるbyte数を算出しています。

const sizeM: number = encodeURI(M).replace(/%../g, "*").length;

ここではメッセージのbyte数を取得しています。M.lengthだと全角文字や絵文字の場合正確に取得できないため一度UTF-8でエンコードして長さを測ります。

const sizeLastM: number = sizeM % 64;
const isOverflow: boolean = sizeMaxBlock < sizeLastM;

if (isOverflow) sizeLastBlock = 128; // Mの最後のブロックのバイトサイズが55bytesを超えていると1ブロックに格納できないため１ブロック追加する

最後のブロックは末尾にメッセージサイズのバイトと区切りの0x80が入るので $64-8-1=55$ bytesになります。なので64bytesに切り刻んだ最後のブロックが $55 < x \le 64$ bytesだった場合、もう一つブロックを増やす=最後のブロックを128bytesにしておく必要があります。

const hexStringM: string = Array.from((new TextEncoder()).encode(M)).map(v => v.toString(16)).join("");

文字列を16進数に変換しています。一回メッセージをUTF-8でエンコードし、それを一文字ずつ16進数文字列に変換しています。

const sizeExtra: number = (sizeLastBlock - sizeMLengthBuffer - sizeDivision - sizeLastM) * 2;
const hexExtraString: string = Array(sizeExtra).fill(0).join("");

0を入れる余りのbyte数をsizeExtraに代入し、hexExtraStringに実際の文字列を入れています。sizeExtraの最後で2倍しているのは、のちに文字列を16進数の数値に変換した際に1文字の0だとその次の0と結合して16進数の0x00が生成されてしまうためです。

const hexSizeM : string= (sizeM * 8).toString(16);
const hex8bytesLengthM: string = Array(16 - hexSizeM.length).fill(0).concat(hexSizeM).join("");

メッセージの末尾に挿入するメッセージサイズの8bytesを生成しています。hexSizeMにサイズを表す16進数文字列を代入し、hex8bytesLengthMで8bytes内で使われなかったbytesに加える0とhexSizeMを結合しています。

const resultString: string = hexStringM + "80" + hexExtraString + hex8bytesLengthM;

最終的に戻り値となる文字列を生成しています。

Divide関数

Padding処理によって64bytesの倍数になったメッセージを、64bytesごとに切り分けます。わざわざ関数に分けるほどでもありませんがPreprocessなので一応。

const divideM = (M: string): string[] => {
  // 文字列として扱っているので64bytesは128文字
  const arrayM: RegExpMatchArray | null = M.match(/.{128}/g);

  if (!arrayM) throw new Error("Failed to divide message");

  return arrayM;
};

使用する関数を定義しちゃう

下準備が終わったら、いよいよハッシュ値の算出に移ります。その際に繰り返し使用する関数をここで定義しておきます。

$\text{ROTR}^{n}(x)=(x\gg n)\lor (x \ll (32 - n))$
$\text{SHR}^{n}(x)=x\gg n$
$\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)$

// ROTR関数の定義
const rotr = (x: number, n: number): number => ((x >>> n) | (x << (32 - n))) >>> 0;
// SHR関数の定義
const shr = (x: number, n: number): number => (x >>> n) >>> 0;

const ch = (x: number, y: number, z: number): number => ((x & y) ^ (~x & z)) >>> 0;

const maj = (x: number, y: number, z: number): number => ((x & y) ^ (x & z) ^ (y & z)) >>> 0;

const upperSigma0 = (x: number): number => (rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22)) >>> 0;

const upperSigma1 = (x: number): number => (rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25)) >>> 0;

const lowerSigma0 = (x: number): number => (rotr(x, 7) ^ rotr(x, 18) ^ shr(x, 3)) >>> 0;

const lowerSigma1 = (x: number): number => (rotr(x, 17) ^ rotr(x, 19) ^ shr(x, 10)) >>> 0;

定数を定義しちゃう

ハッシュ値算出の際に使う定数も定義しておきましょう。といっても定数が64個入る配列を一つ作るだけです。
配列の中身は、小さい方から64個の素数の立方根の小数点以下4bytesです。例えば配列のいちばん最初は最初の素数である2の立方根 $\sqrt[3]{2}=1.2599210498=\text{1.428a2f986ed84}...$ の小数点以下4bytes $\text{428a2f98}$ になります。なんでこんな値を取ってくるのでしょうか。僕にも分かりません。

const K: number[] = [
  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
];

定数ですので実行するたびに「小さい方から64個の素数の立方根の小数点以下4byteを取ってきて配列に入れて...」とかやる必要はありません。

ハッシュ値を算出していく

いよいよ本題です。ハッシュ値の算出手順は、まず先ほど64bytesごとに切り分けたメッセージブロックをさらに4bytesのブロック、つまり半角文字1文字ずつに切り分けます。そしてそのWord一つ一つに対してローテーションという処理を行っていきます。

（↑コメントありがとうございます！）

ハッシュ値を入れる配列を定義する

まずはローテーション処理の肝となる配列を定義します

const H: number[] = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19];

これは後々ハッシュ値が格納され、ローテーション処理に使われる配列です。上の初期値は小さい方から8個の素数の平方根の小数点以下32bitsです。先ほどの定数 $K_{0},K_{1},K_{2}...K_{63}$ は立方根でしたが今回は平方根です。ほんとなんなんでしょうねこれ。

ブロックをさらに切り分ける

const paddedString: string = padding(M);
const dividedM: string[] = divideM(paddedString);

  for (let i = 0; i < dividedM.length; i++) {
    const Mi: RegExpMatchArray | null = dividedM[i].match(/.{8}/g); // 64bytesのブロックをさらに4byteずつ刻んでいく

    if (!Mi) throw new Error("Failed to divide dividedM");
    const W: number[] = mapW(Array(64), Mi);
    ...

先述のdivideM関数で切り分けた64bytesのブロック一つ一つについて、Miに4bytesづつ切り分けた変数を格納しています。ここで正規表現で8文字ずつ切り出しているのはPadding関数の時と同じく、後々数値に変換する際に2文字ごとに１６進数として読んでもらう必要があるからです。
最後のmapW関数では $W$ という64個の要素を持つ配列を生成します。それではmapW関数の中身をみてみましょう

Wを作る

ハッシュ値の算出に必要なメッセージスケジュールなるものをmapW関数で生成します。

const mapW = (array64: number[], Mi: string[]): number[] => {
  for (let i = 0; i < 64; i++) {
    const hexNum: number = parseInt(Mi[i], 16);

    if (i < 16) {
      array64[i] = hexNum;
      continue;
    }
    const tmp: number = lowerSigma1(array64[i - 2]) + array64[i - 7] + lowerSigma0(array64[i - 15]) + array64[i - 16];

    array64[i] = (tmp & 0xffffffff) >>> 0;
  }
  return array64;
};

第一引数には64個の空要素を持つ配列、第二引数にはブロックを4bytesに切り刻んだ配列をとります。

const hexNum: number = parseInt(Mi[i], 16);

この数値化部分で、これまで0をbyte×2個生成したりbyte×2文字でブロックを切り分けたりしていたことが生きてきます。そうやって半ば強引に生成した擬似的な16進数文字列のおかげで論理演算やシフト演算が円滑に行えるのです。

if (i < 16) {
  array64[i] = hexNum;
  continue;
}

$W$ の1~16番目には数値化したメッセージブロック4bytesを格納します。
それ以降のインデックスには以下の式で算出した値を格納します。
$W_{t}=\sigma^{256}_1(W_{t-2})+W_{t-7}+\sigma^{256}_0(W_{t-15})+W_{t-16}$
かなりややこしいですが先ほど定義しておいた関数に当てはめるだけなので実装自体は単純です。

  const tmp: number = lowerSigma1(array64[i - 2]) + array64[i - 7] + lowerSigma0(array64[i - 15]) + array64[i - 16];

  array64[i] = (tmp & 0xffffffff) >>> 0;
}
  return array64; // Wを返してmapW関数は終了

途中の(tmp & 0xffffffff) >>> 0の最後の符号なし右シフトは何をしているのかというと、tmpの値と $\text{0xffffffff}$ の剰余を強制的に符号なし、つまりプラスの値に変換しているのです。他の言語であればこんなことしなくても符号なしの演算はできるのですが、JavaScriptはこの符号なし右シフト以外で確実に非負の数であると保証する方法はありません。(tmp & 0xffffffff)がすでに非負だった場合この演算は無意味ですが、負の数だった場合はこのめんどい作業が必要になります。

前のブロックで生成されたハッシュ値を変数に代入する

メインのハッシュ値算出関数に戻ります。

let a, b, c, d, e, f, g, h;

[a, b, c, d, e, f, g, h] = [...H];

ここで変数a~hにブロックごとのループの最後で生成されるハッシュ値、つまり一つ前のブロックのハッシュ値を代入していきます。

Wを使ったローテーション

先ほどmapW関数で生成したW配列をイテレートして上の変数a~hの値をローテーションしていきます。
イテレートが始まったら、最初に一時的に値を保管す変数 $T_{1}$ と $T_{2}$ を定義します。
$T_{1}=\text{h}+\Sigma^{256}_{1}(e)+\text{Ch}(e,f,g)+K_{t}+W_{t}$
$T_{2}=\Sigma^{256}_{0}(a)+\text{Maj}(a,b,c)$

for (let t = 0; t < 64; t++) {
  const T1: number = ((h + upperSigma1(e) + ch(e, f, g) + K[t] + W[t]) & 0xffffffff) >>> 0;
  const T2: number = ((upperSigma0(a) + maj(a, b, c)) & 0xffffffff) >>> 0;

  h = g;
  g = f;
  f = e;
  e = ((d + T1) & 0xffffffff) >>> 0;
  d = c;
  c = b;
  b = a;
  a = ((T1 + T2) & 0xffffffff) >>> 0;
}

eとa以外はひとつ前のアルファベットの値が代入されるだけで、eは $d+T_{1}$ 、aは $T_{1}+T_{2}$ になります。これをW内の要素全て、つまり64回分行います。
メッセージをabcとしてこのローテーション処理を行った際のa~hの変化が以下です

5d6aebcd 6a09e667 bb67ae85 3c6ef372 fa2a4622 510e527f 9b05688c 1f83d9ab
5a6ad9ad 5d6aebcd 6a09e667 bb67ae85 78ce7989 fa2a4622 510e527f 9b05688c
c8c347a7 5a6ad9ad 5d6aebcd 6a09e667 f92939eb 78ce7989 fa2a4622 510e527f
d550f666 c8c347a7 5a6ad9ad 5d6aebcd 24e00850 f92939eb 78ce7989 fa2a4622
4409a6a d550f666 c8c347a7 5a6ad9ad 43ada245 24e00850 f92939eb 78ce7989
2b4209f5 4409a6a d550f666 c8c347a7 714260ad 43ada245 24e00850 f92939eb
e5030380 2b4209f5 4409a6a d550f666 9b27a401 714260ad 43ada245 24e00850
85a07b5f e5030380 2b4209f5 4409a6a c657a79 9b27a401 714260ad 43ada245
8e04ecb9 85a07b5f e5030380 2b4209f5 32ca2d8c c657a79 9b27a401 714260ad
8c87346b 8e04ecb9 85a07b5f e5030380 1cc92596 32ca2d8c c657a79 9b27a401
4798a3f4 8c87346b 8e04ecb9 85a07b5f 436b23e8 1cc92596 32ca2d8c c657a79
f71fc5a9 4798a3f4 8c87346b 8e04ecb9 816fd6e9 436b23e8 1cc92596 32ca2d8c
87912990 f71fc5a9 4798a3f4 8c87346b 1e578218 816fd6e9 436b23e8 1cc92596
d932eb16 87912990 f71fc5a9 4798a3f4 745a48de 1e578218 816fd6e9 436b23e8
続く...

斜めに値がローテーションし、一番左と左から5行目、つまりaとeで毎度値が変わっているのが分かるはずです。

前のハッシュ値とa~hを足す

  H[0] = ((a + H[0]) & 0xffffffff) >>> 0;
  H[1] = ((b + H[1]) & 0xffffffff) >>> 0;
  H[2] = ((c + H[2]) & 0xffffffff) >>> 0;
  H[3] = ((d + H[3]) & 0xffffffff) >>> 0;
  H[4] = ((e + H[4]) & 0xffffffff) >>> 0;
  H[5] = ((f + H[5]) & 0xffffffff) >>> 0;
  H[6] = ((g + H[6]) & 0xffffffff) >>> 0;
  H[7] = ((h + H[7]) & 0xffffffff) >>> 0;
}// ↖︎次のブロックへ

前のブロックのハッシュ値とa~hの値を加算し、このブロックのハッシュ値が完成します。

ハッシュ値をハッシュ値にする

以上の流れをブロック数回行うと、最後のHには一方向性と耐衝突性を持つハッシュ値が格納された状態になります。しかしこのままでは配列なので、それを結合して文字列の形に直します。
配列を結合するだけなら簡単なのですが、ここでも少し罠があったので紹介します。

let result: string = "";

H.map(b => {
  let hashString: string = b.toString(16);
  if(hashString.length < 8) {
    const extraZeros: string = Array(8 - hashString.length).fill(0).join('');
    hashString = extraZeros + hashString;
  }
  result += hashString;
});
if(result.length !== 64) throw new Error("Hash result is not 32bytes");

return result; // SHA-256完成！

真ん中のHをイテレートしている部分は何をやっているのかというと、配列の要素ひとつひとつの文字数を測り、8文字に満たない場合はその分0を先頭に追加しています。これは、hashStringで数値を文字列に変換した際に、先頭に0があるとそれは省略されて文字列化されてしまうのです。そうすると結果が256bitsでなくなってしまうので、無理矢理ではありますが省略分の0を加える必要があるのです。

ソースコード

だいぶ細々と説明をしてきたので、最後に全体のソースコードを貼っておきます。これは一番上で貼ったリポジトリでも見ることができます。

// 文字列を引数にとり、64の倍数bytesのHex文字列を返す
const padding = (M: string): string => {
  let sizeLastBlock: number = 64; // Mの末尾のブロックサイズ
  const sizeMLengthBuffer: number = 8; // 最終的なメッセージの末尾8bytesはMのサイズを記述する
  const sizeDivision: number = 1; // メッセージバイトと余りの0バイトの区切り（0x80）
  const sizeMaxBlock: number = sizeLastBlock - sizeMLengthBuffer - sizeDivision; // メッセージバイトは55bytes以下であれば良い
  const sizeM: number = encodeURI(M).replace(/%../g, "*").length;
  const sizeLastM: number = sizeM % 64;
  const isOverflow: boolean = sizeMaxBlock < sizeLastM;

  if (isOverflow) sizeLastBlock = 128; // Mの最後のブロックのバイトサイズが55bytesを超えていると1ブロックに格納できないため１ブロック追加する
  // Mを16進数文字列に変換
  const hexStringM: string = Array.from((new TextEncoder()).encode(M)).map(v => v.toString(16)).join("");
  // 余りの0の配列を生成
  const sizeExtra: number = (sizeLastBlock - sizeMLengthBuffer - sizeDivision - sizeLastM) * 2;
  const hexExtraString: string = Array(sizeExtra).fill(0).join("");
  // Mのサイズを8bytesで表現する
  const hexSizeM : string= (sizeM * 8).toString(16);
  const hex8bytesLengthM: string = Array(16 - hexSizeM.length).fill(0).concat(hexSizeM).join("");
  // 64bytesの倍数になったPaddedStringを生成
  const resultString: string = hexStringM + "80" + hexExtraString + hex8bytesLengthM;

  return resultString;
};

// 64の倍数bytesのHex文字列を引数にとり、64bytesごとに切り分けた配列を返す
const divideM = (M: string): string[] => {
  // 文字列として扱っているので64bytesは128文字
  const arrayM: RegExpMatchArray | null = M.match(/.{128}/g);

  if (!arrayM) throw new Error("Failed to divide message");

  return arrayM;
};

const ch = (x: number, y: number, z: number): number => ((x & y) ^ (~x & z)) >>> 0;

const maj = (x: number, y: number, z: number): number => ((x & y) ^ (x & z) ^ (y & z)) >>> 0;

const rotr = (x: number, n: number): number => ((x >>> n) | (x << (32 - n))) >>> 0;

const shr = (x: number, n: number): number => (x >>> n) >>> 0;

const upperSigma0 = (x: number): number => (rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22)) >>> 0;

const upperSigma1 = (x: number): number => (rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25)) >>> 0;

const lowerSigma0 = (x: number): number => (rotr(x, 7) ^ rotr(x, 18) ^ shr(x, 3)) >>> 0;

const lowerSigma1 = (x: number): number => (rotr(x, 17) ^ rotr(x, 19) ^ shr(x, 10)) >>> 0;

// 小さい方から64個の素数の立方根の小数点以下4bytesの定数
const K: number[] = [
  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
];

const mapW = (array64: number[], Mi: string[]): number[] => {
  for (let i = 0; i < 64; i++) {
    const hexNum: number = parseInt(Mi[i], 16);

    if (i < 16) {
      array64[i] = hexNum;
      continue;
    }
    const tmp: number = lowerSigma1(array64[i - 2]) + array64[i - 7] + lowerSigma0(array64[i - 15]) + array64[i - 16];

    array64[i] = (tmp & 0xffffffff) >>> 0;
  }
  return array64;
};

// メインの関数
export const computeHash = (M: string): string => {
  // ブロックごとにハッシュ値が格納される配列
  const H: number[] = [0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19];
  const paddedString: string = padding(M);
  const dividedM: string[] = divideM(paddedString);

  for (let i = 0; i < dividedM.length; i++) {
    const Mi: RegExpMatchArray | null = dividedM[i].match(/.{8}/g); // 64bytesのブロックをさらに4byteずつ刻んでいく

    if (!Mi) throw new Error("Failed to divide dividedM");
    const W: number[] = mapW(Array(64), Mi);
    let a, b, c, d, e, f, g, h;

    [a, b, c, d, e, f, g, h] = [...H];
    for (let t = 0; t < 64; t++) {
      const T1: number = ((h + upperSigma1(e) + ch(e, f, g) + K[t] + W[t]) & 0xffffffff) >>> 0;
      const T2: number = ((upperSigma0(a) + maj(a, b, c)) & 0xffffffff) >>> 0;

      h = g;
      g = f;
      f = e;
      e = ((d + T1) & 0xffffffff) >>> 0;
      d = c;
      c = b;
      b = a;
      a = ((T1 + T2) & 0xffffffff) >>> 0;
    }
    H[0] = ((a + H[0]) & 0xffffffff) >>> 0;
    H[1] = ((b + H[1]) & 0xffffffff) >>> 0;
    H[2] = ((c + H[2]) & 0xffffffff) >>> 0;
    H[3] = ((d + H[3]) & 0xffffffff) >>> 0;
    H[4] = ((e + H[4]) & 0xffffffff) >>> 0;
    H[5] = ((f + H[5]) & 0xffffffff) >>> 0;
    H[6] = ((g + H[6]) & 0xffffffff) >>> 0;
    H[7] = ((h + H[7]) & 0xffffffff) >>> 0;
  }

  let result: string = "";

  H.map(b => {
    let hashString: string = b.toString(16);
    if(hashString.length < 8) {
      const extraZeros: string = Array(8 - hashString.length).fill(0).join('');
      hashString = extraZeros + hashString;
    }
    result += hashString;
  });
  if(result.length !== 64) throw new Error("Hash result is not 32bytes");

  return result;
};

最適化とは程遠いコードですが、ひとつアルゴリズムを理解できたというのは嬉しいですね。

さいごに

記事の中でたびたび

なんでこんな値を取ってくるのでしょうか。僕にも分かりません。

といった感じに理屈抜きで脳死実装をする場面がありました。
「理解してねーのに記事書いてんじゃねーよ」と思われる方もいらっしゃるかもしれませんが、今回僕は、あくまでハッシュ関数の利用者としてアルゴリズムを理解するために実装したまでです。新たなハッシュ関数の開発や脆弱性を突きたいといった研究者視点でこのSHA-256を理解するにはもっと掘り下げていかなければならないのでしょうが、僕は正直そこまでは求めていませんでした。なので、もし僕が「なんでなんでしょうね」とか書いている部分が理解できている方がいればコメント欄で教えていただけると嬉しいです。では

参考文献

NISTの論文

Discussion

白山風露

& 0xffffffffの操作は0xffffffffとの剰余ではなく0x100000000との剰余ですね。論文では "performed modulo $2^{32}$ " と書いてありますし。単純に32ビット符号なし整数型の演算を利用れば桁あふれの結果が $2^{32}$ との剰余の結果と等しくなるため、& 0xffffffffの操作をコード上明記する必要はないのですが、TypeScriptによる実装だとnumber型は整数型ではないので必要ですね。

論文で明示してあるのは、単に数式を書いただけではプログラミング言語の整数型を仮定しないので、 $2^{32}$ との剰余をとることで32ビット符号なし整数型での演算であること（計算機科学的には $GF(2^{32})$ 上での演算であること）を示しているのではないでしょうか

kota-yata

なるほど。数式の前提条件を示すための"performed modulo $2^{32}$ "という記述だったのですね。
指摘いただいた剰余の記述間違いは修正しました。ありがとうございます！