なでしこさんで本物の SHA-256 ハッシュ値を求める

謎仕様の命令

Webブラウザ向けなでしこ3ランタイムには、sha-256/sha-384/sha-512 のハッシュ値を計算できると主張している命令「ハッシュ値計算時」がある。

利用例では文字列「こんにちは」などの sha-256 ハッシュ値を求めようとしているようであるが、v3.6.39 におけるその出力は「df9b3a2da66f4a6c」などと、SHA-256 にしては明らかに短い。

そこで、今回はこの謎仕様の命令を使わず、なでしこさんで本物の SHA-256 ハッシュ値を求めてみる。

本物の SHA-256 ハッシュ値を求める

文字列を表すバイト列を求める

文字列の SHA-256 ハッシュ値を求める準備として、文字列をバイト列に変換する。
今回は、文字列を「BASE64エンコード」し、その結果を Base64 の仕様に沿ってデコードすることで、これを行う。

●(文字の)BASE64ビット列取得とは
　文字コードを文字のASCに定める。
　もし、(文字コードが0x41以上)かつ(文字コードが0x5A以下)ならば
　　文字コードから0x41を引いて戻す。
　違えば、もし、(文字コードが0x61以上)かつ(文字コードが0x7A以下)ならば
　　文字コードから0x61を引いて26を足して戻す。
　違えば、もし、(文字コードが0x30以上)かつ(文字コードが0x39以下)ならば
　　文字コードから0x30を引いて52を足して戻す。
　違えば、もし、文字が「+」ならば
　　62を戻す。
　違えば、もし、文字が「/」ならば
　　63を戻す。
　違えば
　　-1を戻す。
　ここまで
ここまで

●(文字列の)バイト列取得とは
　デコード結果を[]に定める。
　変数のビット数は0。
　変数の残ビットは0。
　文字列をBASE64エンコードして文字列分解して反復
　　変数の今ビット列は対象のBASE64ビット列取得。
　　もし、今ビット列が0以上ならば
　　　ビット数を6増やす。
　　　残ビットは(残ビット<<6)に今ビット列を足す。
　　　もし、ビット数が8以上ならば
　　　　ビット数を8減らす。
　　　　デコード結果に(残ビット>>ビット数)を配列追加。
　　　　残ビットは残ビットを(1<<ビット数)で割った余り。
　　　ここまで
　　ここまで
　ここまで
　デコード結果を戻す。
ここまで

SHA-256 の計算で用いる定数と関数を用意する

SHA-256 の定義に沿って、定数 K および関数 CH・MAJ・BSIG0・BSIG1・SSIG0・SSIG1 を定義する。

●ROTR(xをnで)
　OR(x>>>n,x<<(32-n))を戻す。
ここまで

●CH(xにyとzの)
　XOR(AND(x,y),AND(NOT(x),z))を戻す。
ここまで

●MAJ(xにyとzの)
　XOR(XOR(AND(x,y),AND(x,z)),AND(y,z))を戻す。
ここまで

●BSIG0(xの)
　XOR(XOR(ROTR(x,2),ROTR(x,13)),ROTR(x,22))を戻す。
ここまで

●BSIG1(xの)
　XOR(XOR(ROTR(x,6),ROTR(x,11)),ROTR(x,25))を戻す。
ここまで

●SSIG0(xの)
　XOR(XOR(ROTR(x,7),ROTR(x,18)),SHIFT_UR(x,3))を戻す。
ここまで

●SSIG1(xの)
　XOR(XOR(ROTR(x,17),ROTR(x,19)),SHIFT_UR(x,10))を戻す。
ここまで

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
]。

なでしこさんにおけるビット演算は32ビットの整数を扱い、これは SHA-256 の計算と相性が良い。
SHA-384 および SHA-512 では64ビットの整数を扱うため、処理はより複雑になるだろう。

SHA-256 におけるブロックの処理を行う

SHA-256 では、入力のバイト列を64バイトのブロックに分割し、これらのブロックごとに処理を行う。
ブロックの処理では、32ビットの整数8個が格納された配列 H を、ブロックのデータに基づいて更新する。

●(Hにブロックの)SHA256ブロック処理とは
　それは戻り値無し。
　変数のaはH[0]。
　変数のbはH[1]。
　変数のcはH[2]。
　変数のdはH[3]。
　変数のeはH[4]。
　変数のfはH[5]。
　変数のgはH[6]。
　変数のhはH[7]。
　Wを[]に定める。
　tを0から15まで繰り返す
　　ワードをブロックの(t×4)から(t×4+3)の範囲を配列範囲コピーに定める。
　　WにOR(OR(OR(ワード[0]<<24,ワード[1]<<16),ワード[2]<<8),ワード[3])を配列追加。
　ここまで
　tを16から63まで繰り返す
　　Wに(SSIG1(W[t-2])+W[t-7]+SSIG0(W[t-15])+W[t-16])を配列追加。
　ここまで
　tを0から63まで繰り返す
　　定数のT1はh+BSIG1(e)+CH(e,f,g)+K[t]+W[t]。
　　定数のT2はBSIG0(a)+MAJ(a,b,c)。
　　hはg。
　　gはf。
　　fはe。
　　eはd+T1。
　　dはc。
　　cはb。
　　bはa。
　　aはT1+T2。
　ここまで
　H[0]はSHIFT_UR(a+H[0],0)。
　H[1]はSHIFT_UR(b+H[1],0)。
　H[2]はSHIFT_UR(c+H[2],0)。
　H[3]はSHIFT_UR(d+H[3],0)。
　H[4]はSHIFT_UR(e+H[4],0)。
　H[5]はSHIFT_UR(f+H[5],0)。
　H[6]はSHIFT_UR(g+H[6],0)。
　H[7]はSHIFT_UR(h+H[7],0)。
ここまで

SHA-256 の計算における加算 (+) は和を $2^{32}$ で割った余りとして定義されているが、この剰余操作によって切り捨てられる上位のビットは計算に影響しない。
また、計算の回数が少ないため、桁数が足りなくなるほど大きな値にもならない。
よって、計算中は上位のビットをそのまま残しておき、最後に SHIFT_UR で符号なし32ビット整数に変換すればよい。

入力のバイト列をブロックに分割し、処理を行う

入力のバイト列を先頭から64バイトずつのブロックに分割し、それぞれについて計算処理を行う。
なお、SHA-256 の計算においては、入力のバイト列の最後に以下を追加したバイト列を処理することになっている。
そのため、これを追加する処理も行う。

• 0x80 (1バイト)
• 0x00 (全体の長さが64バイトの倍数になる最小の個数)
• 入力のビット数 (8バイト)

●(値の)十六進数八桁変換とは
　「0000000{値を16進数変換}」で8文字右部分を戻す。
ここまで

●(バイト列の)バイト配列真SHA256ハッシュ値計算とは
　入力長をバイト列の要素数に定める。
　変数の作業用入力長は入力長に8を掛ける。
　入力長配列を[]に定める。
　8回、繰り返す
　　作業用入力長を256で割った余りを入力長配列に配列追加。
　　作業用入力長は作業用入力長を256で割って切り捨て。
　ここまで
　入力長配列を配列逆順。
　Hを[
　　0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
　　0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
　]に定める。
　変数の計算位置は0。
　計算位置が入力長以下の間、繰り返す
　　ブロックをバイト列の計算位置から(計算位置+63)の範囲を配列範囲コピーに定める。
　　もし、ブロックの要素数が(64-9)以下ならば
　　　ブロックに0x80を配列追加。
　　　(64-8-(ブロックの要素数))回、ブロックに0を配列追加。
　　　ブロックに入力長配列を配列足してHにSHA256ブロック処理。
　　違えば、もし、ブロックの要素数が64未満ならば
　　　ブロックに0x80を配列追加。
　　　(64-(ブロックの要素数))回、ブロックに0を配列追加。
　　　HにブロックのSHA256ブロック処理。
　　　最終ブロックを[]に定める。
　　　(64-8)回、最終ブロックに0を配列追加。
　　　最終ブロックに入力長配列を配列足してHにSHA256ブロック処理。
　　違えば
　　　HにブロックのSHA256ブロック処理。
　　ここまで
　　計算位置を64増やす。
　ここまで
　{関数}十六進数八桁変換をHに配列マップして配列只結合して戻す。
ここまで

●(文字列の)真SHA256ハッシュ値計算とは
　文字列のバイト列取得してバイト配列真SHA256ハッシュ値計算して戻す。
ここまで

いくつかの入力について計算を行ってみる

本物の SHA-256 ハッシュ値を求める処理を実装したので、いくつかの入力について実際に計算を行ってみる。
NAKO3プラグインの作り方に沿い、「プラグイン名」が「メイン」のときのみこの処理を行う。
入力とその SHA-256 ハッシュ値を、「テーブル作成」でテーブルにまとめて表示する。

もし、プラグイン名が「メイン」と等しいならば
　結果は[["入力","SHA-256ハッシュ値"]]
　[
　　「こんにちは」,
　　「絵文字👨‍👩‍👧‍👦を含む文字列」,
　　「UTF-8で表すとちょうど64バイトで表される文字列」,
　　「パディングが複数ブロックにまたがる文字列」,
　　「複数ブロックにまたがる程度に長い文字列ですよ」,
　　「SHA-256の8文字目から0になる文字列59250504」,
　　「1,000,000円」
　]を反復
　　結果に[対象,対象の真SHA256ハッシュ値計算]を配列追加。
　ここまで
　結果のテーブル作成。
ここまで

得られた結果を CyberChef による計算結果と比較すると、今回用意した入力に対する出力は全て一致した。
本物の SHA-256 ハッシュ値が正しく計算できていそうである。

Fork, 6 more - CyberChef

まとめ

なでしこさんで、Base64 を経由することで文字列をバイト列に変換できた。
そして、定義に沿って計算処理を実装することで、「ハッシュ値計算時」命令が返す謎の短い文字列ではなく、一般的な定義に基づく SHA-256 ハッシュ値を計算することができた。

なでしこ3貯蔵庫：本物の SHA-256 ハッシュ値を求める