IchigoJam で SHA-1 ハッシュ値を求めてみた

SHA-1 は、よく用いられるハッシュアルゴリズムの一つである。
MD5や他のSHA系のアルゴリズムと比べて、用いるマジックナンバーが少なく、プログラムの容量制限が厳しくても求めやすそうである。
そこで、今回はそんな SHA-1 のハッシュ値を IchigoJam で求めてみた。

※IchigoJamはjig.jpの登録商標です。

SHA-1 のハッシュ値を求めるアルゴリズム

SHA-1 のハッシュ値は、以下のアルゴリズムで求めることができる。(RFC 3174 の Method 2)

入力データを整数の配列に変換する

今回は、簡単のため、入力データは0バイト以上55バイト以下のバイト列とする。

まず、入力データの後ろに値 0x80 のバイトを1個連結し、その後全体の長さが56バイトになるまで後ろに値 0x00 のバイトを連結する。
そして、その後ろに、入力データのビット数 (バイト数の8倍) を8バイトビッグエンディアンで連結する。
得られた64バイトのバイト列を、前から4バイトずつビッグエンディアンで解釈し、32ビットの整数16個の配列にする。
この配列を W[0] ～ W[15] とする。

本来のアルゴリズムでは、長い入力データは64バイトずつのブロックに分割し、それぞれのブロックについて処理を行う。
今回入力を55バイト以下に制限するとは、1ブロックのみで処理を行うケースのみを扱うということである。

マジックナンバーを用意する

変数 H0 ～ H4 を用意し、以下の値で初期化する。

変数	値 (十六進数)
H0	67452301
H1	EFCDAB89
H2	98BADCFE
H3	10325476
H4	C3D2E1F0

また、処理中に用いる以下のマジックナンバーを用意する。

定数	値 (十六進数)
K[0]	5A827999
K[1]	6ED9EBA1
K[2]	8F1BBCDC
K[3]	CA62C1D6

ブロックを処理する

入力データから変換した配列 W を用いて、以下の擬似コードの処理を行う。
ただし、擬似コード中の変数は32ビット整数である。
また、以下の演算子を用いる。

演算子	意味
x = y	x に y を代入する
x + y	x と y の和 (32ビットを超えた部分は捨てる)
x <<< y	x を y ビット左ローテートした値
x / y	x を y で割った商 (小数点以下は切り捨て)
x % y	x を y で割った余り
x & y	x と y のビット論理積 (AND)
x | y	x と y のビット論理和 (OR)
x ^ y	x と y のビット排他的論理和 (XOR)
~x	x のビット反転 (NOT)
x >= y	x が y 以上なら真、そうでなければ偽

擬似コード

// 変数 A～E に変数 H0～H4 の値をコピーする
A = H0
B = H1
C = H2
D = H3
E = H4
// t の値を0から79まで1ずつ変えて繰り返す (両端を含む)
for (t = 0, ... , 79) {
	// 16要素の中でどれを処理するかを決める
	s = t % 16
	// 2周目以降は、これまでの値から新しい値を生成する
	if (t >= 16) {
		W[s] = (W[(s + 13) % 16] ^ W[(s + 8) % 16] ^ W[(s + 2) % 16] ^ W[s]) <<< 1
	}
	// tの値に応じた計算を行う (tの値が20増えるごとに切り替える)
	switch (t / 20) {
		case 0: f = (B & C) | (~B & D)
		case 1: f = B ^ C ^ D
		case 2: f = (B & C) | (B & D) | (C & D)
		case 3: f = B ^ C ^ D
	}
	// 残りの計算を行う
	temp = (A <<< 5) + f + E + W[s] + K[t / 20]
	E = D
	D = C
	C = B <<< 30
	B = A
	A = temp
}
// 変数 H0～H4 に処理後の変数 A～E の値を加算する
H0 = H0 + A
H1 = H1 + B
H2 = H2 + C
H3 = H3 + D
H4 = H4 + E

最終的なハッシュ値を作成する

最終的なハッシュ値は、ブロックの処理を終えた後の変数 H0～H4 の値をそれぞれ4バイトビッグエンディアンで表し、この順で結合したバイト列である。

IchigoJam での計算

IchigoJam BASIC で扱える変数は、16ビット符号付き整数のみである。
そのため、32ビットの整数を用いる SHA-1 の計算には、工夫が求められる。

32ビット整数の表し方

今回は、配列の連続する2要素を用いて、32ビットの整数を表す。
先の要素 (小さい添字の要素) に下位16ビット、後の要素 (大きい添字の要素) に上位16ビットを格納する。

ビット論理積・論理和・排他的論理和・反転

ビット論理積・論理和・排他的論理和・反転は、各ビットを独立して処理できる。
そのため、配列のそれぞれの要素をそれぞれ処理すればよい。

左ローテート

まず、ローテートするビット数が16以上のときは、下位16ビットと上位16ビットを入れ替え、ローテートするビット数から16を引く。
(入れ替えることで、16ビットローテートした状態になる)
続いて、上位16ビットの上位の部分を下位16ビットの下位に、下位16ビットの上位の部分を上位16ビットの下位に、それぞれ差し込む。

加算

加算を行う際は、下位16ビットから上位16ビットへの繰り上がりがあるかを判定し、処理する必要がある。
この繰り上がりがあるかの判定は、以下のように行うことができる。

• 2個の足す数が両方0以上のときは、繰り上がりは無い
  • 最上位ビット (符号ビット) が2個とも0なので、これらの数を足しても符号ビットの上への繰り上がりは発生しない
• 2個の足す数が両方負のときは、繰り上がりがある
  • 最上位ビット (符号ビット) が2個とも1なので、これらの数を足すと符号ビットの上への繰り上がりが発生する
• 足す数のうち1個が負、もう1個が0以上のときは、それらの和が負なら繰り上がりが無く、0以上なら繰り上がりがある
  • 計算結果が0以上のとき、その符号ビットは0である。もともと1だった符号ビットが加算によって0になったということは、符号ビットに1が足されたということであり、よって繰り上がりが発生する
  • 計算結果が負のとき、その符号ビットは1である。符号ビットが変わっておらず、一方の数の符号ビットは0であることから符号ビットに2以上の数が足されることもないので、符号ビットには0しか加算されていない。よって繰り上がりは発生しない

繰り上がりの判定を行ったあと、上位16ビット・下位16ビットそれぞれの加算を行えばよい。

実装

プログラム

変数 D に格納された文字列 (55文字以下) の SHA-1 ハッシュ値を求める。
計算後、求めたハッシュ値に加え、計算にかかった時間 (TICK() 単位) を出力する。

10 ' SHA-1
20 D="hello, world!"
30 CLT:GOTO70
40 C=[B]<0AND([A]<0OR-[A]<=[B])OR[A]<0AND-[B]<=[A]:[A+1]=[A+1]+[B+1]+C:[A]=[A]+[B]:RETURN
50 C=A+1:IFB>15V=[A]:[A]=[C]:[C]=V:B=B-16
60 U=16-B:V=[A]<<B|[C]>>U:[C]=[C]<<B|[A]>>U:[A]=V:RETURN
70 L=LEN(D):FORI=0TO62:IFI<LV=PEEK(D+I)ELSEV=#80*(I=L)
80 POKE#803+I-I%4*2,V:NEXT:LET[30],L*8,0,#2301,#6745,#AB89,#EFCD,#DCFE,#98BA,#5476,#1032,#E1F0,#C3D2,#7999,#5A82,#EBA1,#6ED9,#BCDC,#8F1B,#C1D6,#CA62:FORI=50TO59:[I]=[I-18]:NEXT:FORT=0TO79:S=T%16*2
90 IFT>15FORR=0TO1:[S+R]=[(S+26)%32+R]^[(S+16)%32+R]^[(S+4)%32+R]^[S+R]:NEXT:A=S:B=1:GOSUB50
100 FORR=0TO1:[60+R]=[50+R]:X=[52+R]:Y=[54+R]:Z=[56+R]:IFT<20W=X&Y|~X&ZELSEIF39<TANDT<60W=X&Y|X&Z|Y&ZELSEW=X^Y^Z
110 [62+R]=W:NEXT:A=60:B=5:GOSUB50:B=62:GOSUB40:B=58:GOSUB40:B=S:GOSUB40:B=42+T/20*2:GOSUB40:A=52:B=30:GOSUB50:FORR=0TO1:[58+R]=[56+R]:[56+R]=[54+R]:[54+R]=[52+R]:[52+R]=[50+R]:[50+R]=[60+R]:NEXT:NEXT
120 FORI=0TO4:A=32+I*2:B=50+I*2:GOSUB40:NEXT
130 E=TICK():?"TIME=";E:FORI=0TO4:?HEX$([33+I*2],4);HEX$([32+I*2],4);:NEXT:?""

このプログラムでは変数 D の値を固定にしているが、様々な入力を試しやすいように INPUT で置き換えてもよい。

メモリの割り当て

このプログラムでは、配列を以下のように用いる。

領域	用途
[0]～[31]	入力由来のデータ W[0]～W[15]
[32]～[41]	変数 H0～H4
[42]～[49]	定数 K[0]～K[3]
[50]～[59]	変数 A, B, C, D, E
[60]～[61]	変数 temp
[62]～[63]	変数 f

各行の処理内容

• 10行目：FILES 対応のタイトル
• 20行目：SHA-1 ハッシュ値を求める入力データ
• 30行目：計算時間の測定を開始する
• 40行目：足し算を行うサブルーチン
  • A からの2要素と B からの2要素を加算し、結果を A からの2要素に格納する
• 50～60行目：左ローテートを行うサブルーチン
  • A からの2要素を B ビット左ローテートし、結果を A からの2要素に格納する
  • B の値を破壊することがある
• 70行目：文字列の内容・値 0x80 のバイト・値 0x00 のバイトを取得する
• 80行目
  • 取得した値および入力の長さを配列に格納する
  • 変数 H0～H4 の初期値および定数 K[0]～K[3] の値を配列に格納する
  • ループを開始し、処理対象の要素の位置を求める
• 90行目：2周目以降の新しい値を求める処理を行う
• 100行目
  • 変数 A の値を変数 temp にコピーする (後でこれを5ビット左ローテートする)
  • tの値に応じた計算を行う
• 110行目
  • tの値に応じた計算の結果を変数 f に格納する
  • 残りの計算を行う
• 120行目：変数 A～E の値を変数 H0～H4 に加算する
• 130行目：計算にかかった時間と求めた SHA-1 ハッシュ値を出力する

計算にかかった時間

今回のプログラムを各機種で1回ずつ実行すると、以下の計算時間 (TICK() 単位) になった。
「Vあり」はビデオ出力ありを、「Vなし」はビデオ出力なしを表す。

機種	バージョン	Vあり 計算時間	Vあり 相対速度	Vなし 計算時間	Vなし 相対速度
MeganeJam	1.2.3	1127	0.6131	623	1.1091
IchigoJam S	1.3.1	704	0.9815	373	1.8525
IchigoKamuy	1.4.1	689	1.0029	452	1.5288
IchigoJam Q	1.4.3	691	1.0000	453	1.5254
IchigoJam R	1.5b	83	8.3253	73	9.4658
IchigoJam P	1.6.0	41	16.8537	37	18.6757

まとめ

1ブロックに収まる程度の短い入力 (55バイト以下) であれば、IchigoJam BASIC で SHA-1 ハッシュ値を求めることができた。