SHA3を実装してみた その4 templateを使ったkeccakの汎用実装 後編

というわけで、前回の続きです。

初期化(Init)

template <class wordtype,size_t hashlength> void CHashKeccak<wordtype,hashlength>::Init(void)
{
	memset(m_anState,0x00,sizeof(m_anState));
	memset(m_anBlock,0x00,sizeof(m_anBlock));
	m_nNumChr = 0;
}

何も言うことのない初期化ルーチンです。

落とし穴になりやすい要素として「内部データブロックバッファはすべて0初期化しなければならない」ということがあります。

これはLoadのルーチンに関連した要素なので注意が必要です。

データロード(Load)

template <class wordtype,size_t hashlength> void CHashKeccak<wordtype,hashlength>::Load(const void *data,size_t len)
{
	unsigned char *block; size_t rsize,i;
	if(data == NULL) return;
	block = (unsigned char *)&(m_anBlock[0]);
	while(len > 0){
		rsize = (len < m_nBlockLength - m_nNumChr) ? len : (m_nBlockLength - m_nNumChr);
		memcpy(block + m_nNumChr,data,rsize);
		m_nNumChr += rsize; data = (unsigned char *)data + rsize; len -= rsize;
		if(m_nNumChr == m_nBlockLength){
			for(i = 0;i < m_nBlockCount;i++){
				m_anState[i] ^= SetLittleEndian(m_anBlock[i]);
			}
			Update(m_anState,m_nRoundCount);
			m_nNumChr = 0;
		}
	}
}

どこにでもあるようなハッシュのデータロードルーチンです。

注意点としてはハッシュの状態バッファにデータブロックを渡すときにXORを使って結合を行いますが、このときにデータブロック長がワード長の倍数でないとき、

0初期化を行っていないと誤ったデータが状態バッファに結合されてしまう、と言うことがおこります。

そのためにInitではブロックバッファをすべて0初期化する必要があるわけです。

最終状態化(Final)

template <class wordtype,size_t hashlength> void CHashKeccak<wordtype,hashlength>::Final(void)
{
	const uint8_t cZero = 0x00; const uint8_t cOne = 0x01; uint8_t cEnd = 0x80;
	if(m_nNumChr + 1 != m_nBlockLength){
		Load(&cOne,sizeof(cOne));
		while(m_nNumChr + 1 != m_nBlockLength){ Load(&cZero,sizeof(cZero)); }
	}
	else{ cEnd ^= cOne; }
	Load(&cEnd,sizeof(cEnd));
}

ちょっと面倒なのがこの処理です。

データのパディングについては以下のような定義になっています。

全体のメッセージをとするとき、データブロック長の倍数となるようにパディングされたメッセージ

となる。

で、これを日本語的に解釈すると

  1. Mに0x01を追加した後、0x00をデータブロック長の倍数になるまで追加する
  2. 最終オクテットに0x80をXORする

となります。が、普通プログラム的に組むとそんなことは出来ません。

なぜなら、ブロック長になるまでパディングするとほとんどの組み方ではその段階で勝手に更新作業を行ってしまうからです。

なので、解釈を変更して

  • Mが(データブロック長の倍数-1)でないときは0x01を追加して、(データブロック長の倍数-1)まで0x00を追加、最後に0x80を追加してデータブロック長の倍数になるようにする
  • Mが(データブロック長の倍数-1)のときは0x01 XOR 0x80 = 0x81を追加してデータブロック長の倍数になるようにする

とするのが妥当だと思います。

そういうわけで、このような書き方になっています。

珍しいのは、keccakではロードされたデータの総ビット数(もしくは総バイト数)を見ていない、と言う点にあります。

だいたいのハッシュアルゴリズム(MD5やSHA1など)では最後にロードされた総ビット数を追加する、と言う手順がありますが、これにはないのですね。

ダイジェスト取得(GetDigest)

template <class wordtype,size_t hashlength> void CHashKeccak<wordtype,hashlength>::GetDigest(void *buf) const
{
	size_t len,size,i; wordtype hashbuf[25],retbuf[25];
	if(buf == NULL) return;
	memcpy(hashbuf,m_anState,sizeof(hashbuf)); len = m_nHashLength;
	do{
		size = len <= m_nBlockLength ? len : m_nBlockLength;
		for(i = 0;i < m_nBlockCount;i++){ retbuf[i] = SetLittleEndian(hashbuf[i]); }
		
		memcpy(buf,retbuf,size);
		if(size >= len) break;
		Update(hashbuf,m_nRoundCount);
		len -= size; buf = (unsigned char *)buf + size;
	} while(1);
}

これもそのまま従って書いています。手順としては

  1. ハッシュデータを空にする(この手順を行う必要はプログラム的にはない)
  2. データブロック長分だけハッシュデータを結合する
  3. ハッシュデータ長に足りればこれで終了
  4. 状態バッファを再撹拌して2.に戻る

となります。通常のSHA3では、データブロック長がハッシュデータ長より短い、と言うことはないので再撹拌という手順にはならないですね。

なお、bufのバッファ長を見てはいませんが、bufに必要なサイズは型を宣言した時点で分かっているはずなので除外しています。

状態更新処理(Update)

#define A(x,y)		state[(x) + (y) * 5]
#define B(x,y)		work[(x) + (y) * 5]
template <class wordtype,size_t hashlength> void CHashKeccak<wordtype,hashlength>::Update(wordtype state[25],size_t rounds)
{
	wordtype C[5],D[5],work[25]; uint64_t n; size_t rnd; uint32_t x,y;
	
	for(rnd = 0;rnd < rounds;rnd++){
		//θ step
		for(x = 0;x < 5;x++){ C[x] = A(x,0) ^ A(x,1) ^ A(x,2) ^ A(x,3) ^ A(x,4); }
		for(x = 0;x < 5;x++){ D[x] = C[_keccak_const::c_anIndexM1M5[x]] ^ RotateLeft(C[_keccak_const::c_anIndexP1M5[x]],1); }
		for(x = 0;x < 5;x++){
			for(n = D[x],y = 0;y < 5;y++){
				A(x,y) ^= n;
			}
		}
		//ρ and π steps
		for(y = 0;y < 5;y++){
			for(x = 0;x < 5;x++){
				B(y,_keccak_const::c_aanIndex2XP3YM5[y][x]) = RotateLeft(A(x,y),_keccak_const::c_aanRotateCount[y][x] & KECCAK_SHIFTMASK);
			}
		}
		//χ step
		for(y = 0;y < 5;y++){
			for(x = 0;x < 5;x++){
				A(x,y) = B(x,y) ^ ((~B(_keccak_const::c_anIndexP1M5[x],y)) & B(_keccak_const::c_anIndexP2M5[x],y));
			}
		}
		//ι step
		A(0,0) ^= (wordtype)_keccak_const::c_anRoundConstant[rnd];
	}
}
#undef B
#undef A

defineによるマクロ置換を使って、実装手順書と同じ書き方になるようにしています。

最適化も何にも考えていないので、コンパイラの最適化任せですね。

説明すべき所は特にないと思います。せいぜい二次元配列のxとyの指定ミスがないように、と言うところですか。

このコードを使ってみたい方はどうぞご自由に

相変わらず著作権は放棄しませんが、改変などは自由です。

といっても、そもそも速度がかなり遅いので結果確認程度にしか使えないのが弱点ですか。

そして追記するならこれはあくまでkeccakの実装でありSHA3とするにはFinalの処理にさらにコードが必要ですので注意を。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

この記事のトラックバック用URL