intel SSE2命令(SIMD)によるAES暗号処理　高速化実験資料

実験プログラム

aes_c.zip　…　Visual C++のみで書いた物。
掛け算とSubByte()を同時に行う。

ちなみに、Visual C++.net 2008 Express Editionでは、Ｃ言語のSSE2命令の最適化は頭良くなかったです。
ＣＰＵの命令デコードの効率化を考えた命令の並べ替え位はしてくれますが、それよりもメモリアクセスが多くて足を引っ張っています。
関数を終わる毎に、演算結果をxmmレジスタからメモリに格納して呼び出し元に渡して、呼び出し元でそのメモリから読み込んでxmmレジスタに代入するとか、そんな無駄な事を結構やっています。
とにかく、メモリアクセスが多い最適化になっていました。
以下、アセンブリ言語で書いたものは、そのような無駄を排除し、書いています。

aes_asm.zip　…　アセンブリ言語で書いて、より高速化を試みた物。
全体（暗号・複合）に共通して施した最適化は以下の通りです。

演算は極力レジスターで済ます事でメモリアクセスを減らし、キャッシュミスによるペナルティーのリスクを低減した（乗算のテーブル参照を除く）。
条件分岐を極力減らし、分岐予測ミスによるペナルティーのリスクを低減した。

その他、暗号部においては、ガロア体GF(2⁸)の乗算とSubByte()を同時に行うテーブルに置き換えました。そのため、ガロア体GF(2⁸)の乗算ルーチンの呼び出しは無くなりましたが、テーブル参照（つまりメモリ読み込み）は増えています。
復号のアルゴリズムを最適化する方法は思い浮かびませんでした。 InvSubByte()とInvAddRound()の順番は入れ替えれないので。

SSE命令で、更に高速化する手法があるかもしれません。もし何か気付いた事がありましたら、教えて頂けると嬉しいです。

実験結果

以下、８[MByte]の暗号・復号に要したクロック数の大まかな計測結果です。
Ｃ言語で書いたもの、アセンブリ言語で書いたもの、何れもSSE2によるベクトル化がなされています。
尚、Visual C++.netのプロジェクト中では、コンパイルオプションを実行速度で最適化するように設定してあります。

Intel(R) Celeron(R) M CPU 430 @ 1.73GHz
(Windows XP (32bit) / Memory 760MByte)
プログラム	暗号	復号
Ｃ言語	約 1,848 Mclk （約 1,643 Mclk … ※）	約 2,943 Mclk
アセンブリ言語	約 1,282 Mclk … ※	約 1,774 Mclk

※ガロア体GF(2⁸)の乗算とSubByte()置換を、同時に行うテーブル置換に置換え時。

セレロンでは、暗号・復号共にアセンブリ言語による効果が出ている。
暗号は、ガロア体GF(2⁸)の乗算ルーチンの呼び出しを排除した事による効果が大きい。
復号ではガロア体GF(2⁸)の乗算ルーチンを呼び出しているが、それ以上にアセンブリ言語による高速化が得られている。

Intel(R) Core(TM)2 Quad CPU Q9450 @ 2.66GHz
(Windows 7 (32bit) / Memory 4GByte)
プログラム	暗号	復号
Ｃ言語	約 973 Mclk	約 1,532 Mclk
アセンブリ言語	約 986 Mclk … ※	約 1,048 Mclk

※ガロア体GF(2⁸)の乗算とSubByte()置換を、同時に行うテーブル置換に置換え時。

Core2 Quadでは、暗号は逆に若干遅くなっている。
アセンブリ言語による高速化に、テーブル参照（メモリ読み込み）の遅さが足を引っ張っていると思われる。
復号は、Ｃ言語で書いたものとほぼ同じアルゴリズムであるが、アセンブリ言語による高速化が得られている。
Core2 Quadの様に動作速度が速いＣＰＵにおいては、メモリ読み込みを行うテーブル参照よりも、ガロア体GF(2⁸)の乗算を計算してしまう方が、更に高速化が見込めるかもしれない。

※この実験での計測結果は、ファイルアクセスの時間、暗号鍵生成の時間を含みません。

Ｃ言語版プログラムコードの説明

鍵スケジュールの生成

鍵スケジュールの生成については、SSE2命令を用いたベクトル化は思い浮かばなかった。
なので、鍵スケジュールの生成方法は、別途"、"fips-197"を参照してもらいたい。
もしかしたら、良い方法があるのかもしれない。
とりあえず、Ｃ++によるソースを以下に書いておく。


//==============================================================
//		fips-197	5.2	Key Expansion
//--------------------------------------------------------------
//	●引数
//		char			cNK	= 4(0100)	: 128bit AES
//						= 6(0110)	: 192bit AES
//						= 8(1000)	: 256bit AES
//		const unsigned char	Key[]			: Cipher Key
//	●返値
//		無し
//==============================================================
void	AES::KeyExpansion(char cNk, const unsigned char *key)
{
	//The round constant word array.
	static	const	unsigned	int	Rcon[10]={
		0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1b,0x36};

	unsigned	int	i;
				int	iR;
				int	iRm;
				int	temp;

	Nk	= cNk & 0xFE;
	Nr	= Nk + 6;

	//高速メモリコピー
	i	= 0;
	do{
		_mm_storel_epi64((__m128i*)&w[i], _mm_loadl_epi64((__m128i*)&key[i*4]));
		i++;
		i++;
	} while (i < Nk);

	i		= Nk;
	temp	= w[i-1];
	do{
		iR	= i/Nk;
		iRm	= i%Nk;		//割り算命令を２つ吐くのは勿体無い。

		if(iRm==0){
			temp = SubWord(RotWord(temp)) ^ Rcon[(iR)-1];
		} else if((Nk > 6) && ( (i%Nk) == 4)){
			temp = SubWord(temp);
		}
		temp	^= w[i-Nk];
		w[i]	 = temp;

		i++;

	} while (i < Nb * (Nr+1));
}

RotWord()

コメントアウトにも書いてあるが、4Byte単位の回転はアセンブリ言語のror命令を使うと効率が良く、
最適化によってror 命令になるように、ソースを書くと早くなる。


//==============================================================
//		fips-197	5.2	RotWord()
//--------------------------------------------------------------
//	●引数
//			unsigned int data	4Byteの数値
//	●返値
//			unsigned int		ror data,8 の結果
//==============================================================
unsigned	int	AES::RotWord(unsigned int data)
{
	return( (data>>8) | (data<<24) );		//つまり	ror data,8
}

SubWord()

Sbox等のテーブル置換は、どうしようもないと思う。
しかしながら、4Byteアライメントされていないメモリ読み込みにはペナルティーがあるので、
『変換しようとするデータ4Byteは同時にメモリから読み込む』コードに最適化される様に、ソースを書く。
"static const unsigned char Sbox[256]"を "static const unsigned int Sbox[256]"に書き直すと、また早くなるかもしれない。
が、CPU内の1次キャッシュに留めさせておくために、テーブルのサイズは小さい方が良いかもしれない。

この関数は、暗号化の際にも呼ばれる。


//==============================================================
//		fips-197	5.2	Sbox()	(4Byte同時に)
//--------------------------------------------------------------
//	●引数
//			unsigned int	data	4Byteの数値
//	●返値
//			unsigned int		SBox適用後
//==============================================================
unsigned	int	AES::SubWord(unsigned int data)
{
//	fips-197	Figure 7
static	const	unsigned	char	Sbox[256]={
	0x63,0x7c,0x77,0x7b,0xf2,0x6b,0x6f,0xc5,0x30,0x01,0x67,0x2b,0xfe,0xd7,0xab,0x76,
	0xca,0x82,0xc9,0x7d,0xfa,0x59,0x47,0xf0,0xad,0xd4,0xa2,0xaf,0x9c,0xa4,0x72,0xc0,
	0xb7,0xfd,0x93,0x26,0x36,0x3f,0xf7,0xcc,0x34,0xa5,0xe5,0xf1,0x71,0xd8,0x31,0x15,
	0x04,0xc7,0x23,0xc3,0x18,0x96,0x05,0x9a,0x07,0x12,0x80,0xe2,0xeb,0x27,0xb2,0x75,
	0x09,0x83,0x2c,0x1a,0x1b,0x6e,0x5a,0xa0,0x52,0x3b,0xd6,0xb3,0x29,0xe3,0x2f,0x84,
	0x53,0xd1,0x00,0xed,0x20,0xfc,0xb1,0x5b,0x6a,0xcb,0xbe,0x39,0x4a,0x4c,0x58,0xcf,
	0xd0,0xef,0xaa,0xfb,0x43,0x4d,0x33,0x85,0x45,0xf9,0x02,0x7f,0x50,0x3c,0x9f,0xa8,
	0x51,0xa3,0x40,0x8f,0x92,0x9d,0x38,0xf5,0xbc,0xb6,0xda,0x21,0x10,0xff,0xf3,0xd2,
	0xcd,0x0c,0x13,0xec,0x5f,0x97,0x44,0x17,0xc4,0xa7,0x7e,0x3d,0x64,0x5d,0x19,0x73,
	0x60,0x81,0x4f,0xdc,0x22,0x2a,0x90,0x88,0x46,0xee,0xb8,0x14,0xde,0x5e,0x0b,0xdb,
	0xe0,0x32,0x3a,0x0a,0x49,0x06,0x24,0x5c,0xc2,0xd3,0xac,0x62,0x91,0x95,0xe4,0x79,
	0xe7,0xc8,0x37,0x6d,0x8d,0xd5,0x4e,0xa9,0x6c,0x56,0xf4,0xea,0x65,0x7a,0xae,0x08,
	0xba,0x78,0x25,0x2e,0x1c,0xa6,0xb4,0xc6,0xe8,0xdd,0x74,0x1f,0x4b,0xbd,0x8b,0x8a,
	0x70,0x3e,0xb5,0x66,0x48,0x03,0xf6,0x0e,0x61,0x35,0x57,0xb9,0x86,0xc1,0x1d,0x9e,
	0xe1,0xf8,0x98,0x11,0x69,0xd9,0x8e,0x94,0x9b,0x1e,0x87,0xe9,0xce,0x55,0x28,0xdf,
	0x8c,0xa1,0x89,0x0d,0xbf,0xe6,0x42,0x68,0x41,0x99,0x2d,0x0f,0xb0,0x54,0xbb,0x16
	};

	//テーブル変換に関するSIMD命令は無い？
	unsigned	char	a0	= Sbox[(data    ) & 0xFF];
	unsigned	char	a1	= Sbox[(data>>8 ) & 0xFF];
	unsigned	char	a2	= Sbox[(data>>16) & 0xFF];
	unsigned	char	a3	= Sbox[(data>>24)];

	return(a0 | a1<<8 | a2<<16 | a3<<24);
}

InvSubWord()

上のSubWord()関数の逆変換をするもの。
この関数は、復号の際に呼ばれるものであるが、ここに書いておく。


//==============================================================
//		fips-197	5.2	InvSbox()	(4Byte同時に)
//--------------------------------------------------------------
//	●引数
//			unsigned int	data	4Byteの数値
//	●返値
//			unsigned int		InvSBox適用後
//==============================================================
unsigned	int	AES::InvSubWord(unsigned int data)
{
//	fips-197	Figure 14
static	const	unsigned	char	InvSbox[256]={
	0x52,0x09,0x6a,0xd5,0x30,0x36,0xa5,0x38,0xbf,0x40,0xa3,0x9e,0x81,0xf3,0xd7,0xfb,
	0x7c,0xe3,0x39,0x82,0x9b,0x2f,0xff,0x87,0x34,0x8e,0x43,0x44,0xc4,0xde,0xe9,0xcb,
	0x54,0x7b,0x94,0x32,0xa6,0xc2,0x23,0x3d,0xee,0x4c,0x95,0x0b,0x42,0xfa,0xc3,0x4e,
	0x08,0x2e,0xa1,0x66,0x28,0xd9,0x24,0xb2,0x76,0x5b,0xa2,0x49,0x6d,0x8b,0xd1,0x25,
	0x72,0xf8,0xf6,0x64,0x86,0x68,0x98,0x16,0xd4,0xa4,0x5c,0xcc,0x5d,0x65,0xb6,0x92,
	0x6c,0x70,0x48,0x50,0xfd,0xed,0xb9,0xda,0x5e,0x15,0x46,0x57,0xa7,0x8d,0x9d,0x84,
	0x90,0xd8,0xab,0x00,0x8c,0xbc,0xd3,0x0a,0xf7,0xe4,0x58,0x05,0xb8,0xb3,0x45,0x06,
	0xd0,0x2c,0x1e,0x8f,0xca,0x3f,0x0f,0x02,0xc1,0xaf,0xbd,0x03,0x01,0x13,0x8a,0x6b,
	0x3a,0x91,0x11,0x41,0x4f,0x67,0xdc,0xea,0x97,0xf2,0xcf,0xce,0xf0,0xb4,0xe6,0x73,
	0x96,0xac,0x74,0x22,0xe7,0xad,0x35,0x85,0xe2,0xf9,0x37,0xe8,0x1c,0x75,0xdf,0x6e,
	0x47,0xf1,0x1a,0x71,0x1d,0x29,0xc5,0x89,0x6f,0xb7,0x62,0x0e,0xaa,0x18,0xbe,0x1b,
	0xfc,0x56,0x3e,0x4b,0xc6,0xd2,0x79,0x20,0x9a,0xdb,0xc0,0xfe,0x78,0xcd,0x5a,0xf4,
	0x1f,0xdd,0xa8,0x33,0x88,0x07,0xc7,0x31,0xb1,0x12,0x10,0x59,0x27,0x80,0xec,0x5f,
	0x60,0x51,0x7f,0xa9,0x19,0xb5,0x4a,0x0d,0x2d,0xe5,0x7a,0x9f,0x93,0xc9,0x9c,0xef,
	0xa0,0xe0,0x3b,0x4d,0xae,0x2a,0xf5,0xb0,0xc8,0xeb,0xbb,0x3c,0x83,0x53,0x99,0x61,
	0x17,0x2b,0x04,0x7e,0xba,0x77,0xd6,0x26,0xe1,0x69,0x14,0x63,0x55,0x21,0x0c,0x7d
	};

	//テーブル変換に関するSIMD命令は無い？
	unsigned	char	a0	= InvSbox[(data    ) & 0xFF];
	unsigned	char	a1	= InvSbox[(data>>8 ) & 0xFF];
	unsigned	char	a2	= InvSbox[(data>>16) & 0xFF];
	unsigned	char	a3	= InvSbox[(data>>24)];

	return(a0 | a1<<8 | a2<<16 | a3<<24);
}

暗号

16Byte単位で暗号化する関数。
このような暗号を『ブロック暗号』と呼び、ブロック単位で暗号／復号される。
この関数および、復号する為の関数を呼ぶ前には、鍵スケジュールを生成しなければならない。

暗号化は、以下の順序で、各関数が繰り返し呼ばれ、処理される。

Round	Function
0 初回ラウンド	AddRoundKey()
1 ～ (Nr-1)	SubBytes() ShiftRows() MixColumns() AddRoundKey()
Nr 最終ラウンド	SubBytes() ShiftRows() AddRoundKey()

ラウンド数は、共通鍵長によって異なる。

共通鍵長	ラウンド数（Nr）
128 bit	10
192 bit	12
256 bit	14


//==============================================================
//		fips-197	5.1	Cipher
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Plain-text 
//	●返値
//			__m128i		Cipher-text
//==============================================================
__m128i	AES::Cipher(__m128i data)
{
	//◆Round [0]
	int	i=0;

	data = AddRoundKey(data, i);
	i++;

	//◆Round (1) ～ (Nr-1)
	do{
		data = AddRoundKey(MixColumns(ShiftRows(SubBytes(data))),i);
		i++;
	} while(i < Nr);

	//◆Round (Nr)
	data = AddRoundKey(ShiftRows(SubBytes(data)),i);

	return(data);
}

SubBytes()

鍵スケジュールの生成でも述べたように、SBoxのテーブル変換については、SIMD化する方法を全く思いつかない。
とりあえず、4Byte毎に変換を行う。


//==============================================================
//		fips-197	5.1.1	SubBytes
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Input
//	●返値
//			__m128i		Output
//==============================================================
__m128i	AES::SubBytes(__m128i data)
{
	//テーブル変換は、SIMD化できない？
	data.m128i_u32[0] = SubWord(data.m128i_u32[0]);
	data.m128i_u32[1] = SubWord(data.m128i_u32[1]);
	data.m128i_u32[2] = SubWord(data.m128i_u32[2]);
	data.m128i_u32[3] = SubWord(data.m128i_u32[3]);

	return(data);
}

ShiftRows()

何をやりたいかというと、

入力
D[ 0]	D[ 4]	D[ 8]	D[12]
D[ 1]	D[ 5]	D[ 9]	D[13]
D[ 2]	D[ 6]	D[10]	D[14]
D[ 3]	D[ 7]	D[11]	D[15]

という入力に対して

出力
D[ 0]	D[ 4]	D[ 8]	D[12]
D[ 5]	D[ 9]	D[13]	D[ 1]
D[10]	D[14]	D[ 2]	D[ 6]
D[15]	D[ 3]	D[ 7]	D[11]

に並べ替えて出力する関数がShiftRows()。この配列を作る方法としては、まず、a0～a3を作る。
このa0～a3は、_mm_shuffle_epi32()によって、入力された配列を32bit単位で入れ替えたもの。

a0 ＝入力

a0
D[ 0]	D[ 4]	D[ 8]	D[12]
D[ 1]	D[ 5]	D[ 9]	D[13]
D[ 2]	D[ 6]	D[10]	D[14]
D[ 3]	D[ 7]	D[11]	D[15]

pshufd a1, 入力, 00111001b

a1
D[ 4]	D[ 8]	D[12]	D[ 0]
D[ 5]	D[ 9]	D[13]	D[ 1]
D[ 6]	D[10]	D[14]	D[ 2]
D[ 7]	D[11]	D[15]	D[ 3]

pshufd a2, 入力, 01001110b

a2
D[ 8]	D[12]	D[ 0]	D[ 4]
D[ 9]	D[13]	D[ 1]	D[ 5]
D[10]	D[14]	D[ 2]	D[ 6]
D[11]	D[15]	D[ 3]	D[ 7]

pshufd a3, 入力, 10010011b

a3
D[12]	D[ 0]	D[ 4]	D[ 8]
D[13]	D[ 1]	D[ 5]	D[ 9]
D[14]	D[ 2]	D[ 6]	D[10]
D[15]	D[ 3]	D[ 7]	D[11]

次に、不要な数値をマスクして、"0"にする。

a0
D[ 0]	D[ 4]	D[ 8]	D[12]
0	0	0	0
0	0	0	0
0	0	0	0

a1
0	0	0	0
D[ 5]	D[ 9]	D[13]	D[ 1]
0	0	0	0
0	0	0	0

a2
0	0	0	0
0	0	0	0
D[10]	D[14]	D[ 2]	D[ 6]
0	0	0	0

a3
0	0	0	0
0	0	0	0
0	0	0	0
D[15]	D[ 3]	D[ 7]	D[11]

このa0～a3を、論理和演算(OR)すると、見事に期待の配列が出来上がる。
出力＝ a0 | a1 | a2 | a3

出力
D[ 0]	D[ 4]	D[ 8]	D[12]
D[ 5]	D[ 9]	D[13]	D[ 1]
D[10]	D[14]	D[ 2]	D[ 6]
D[15]	D[ 3]	D[ 7]	D[11]


//==============================================================
//		fips-197	5.1.2	ShiftRows
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Input
//	●返値
//			__m128i		Output
//==============================================================
__m128i	AES::ShiftRows(__m128i data)
{
__declspec(align(16))	static	const	unsigned	int	mask0[4] = {0x000000FF,0x000000FF,0x000000FF,0x000000FF};
__declspec(align(16))	static	const	unsigned	int	mask1[4] = {0x0000FF00,0x0000FF00,0x0000FF00,0x0000FF00};
__declspec(align(16))	static	const	unsigned	int	mask2[4] = {0x00FF0000,0x00FF0000,0x00FF0000,0x00FF0000};
__declspec(align(16))	static	const	unsigned	int	mask3[4] = {0xFF000000,0xFF000000,0xFF000000,0xFF000000};

	const	__m128i	_mm_mask0 = _mm_load_si128((__m128i*)&mask0);
	const	__m128i	_mm_mask1 = _mm_load_si128((__m128i*)&mask1);
	const	__m128i	_mm_mask2 = _mm_load_si128((__m128i*)&mask2);
	const	__m128i	_mm_mask3 = _mm_load_si128((__m128i*)&mask3);

	__m128i	a0	=	_mm_and_si128(_mm_mask0, data);					//縦方向の回転
	__m128i	a1	=	_mm_and_si128(_mm_mask1, _mm_shuffle_epi32(data, 0x39));	//0011 1001 b
	__m128i	a2	=	_mm_and_si128(_mm_mask2, _mm_shuffle_epi32(data, 0x4E));	//0100 1110 b
	__m128i	a3	=	_mm_and_si128(_mm_mask3, _mm_shuffle_epi32(data, 0x93));	//1001 0011 b

	return(_mm_or_si128(_mm_or_si128(a0,a1),_mm_or_si128(a2,a3)));
}

MixColumns()

4Byte単位で、ガロア体GF(2⁸)における行列の演算を行う。
（ガロア体（有限体）については、数学の専門書を参照の事。）

足し算　…　排他的論理和（XOR）
掛け算　…　以下、mul()関数を参照。

入力された配列をI[0]～I[3]、出力すべき配列をO[0]～O[3]と仮定すると、

　| O[0] |　　　| ２　３　１　１ || I[0] |
　| O[1] |　＝　| １　２　３　１ || I[1] |
　| O[2] |　　　| １　１　２　３ || I[2] |
　| O[3] |　　　| ３　１　１　２ || I[3] |

つまり、

　O[0] ＝ 2I[0] ＋ 3I[1] ＋　I[2] ＋　I[3]
　O[1] ＝　I[0] ＋ 2I[1] ＋ 3I[2] ＋　I[3]
　O[2] ＝　I[0] ＋　I[1] ＋ 2I[2] ＋ 3I[3]
　O[3] ＝ 3I[0] ＋　I[1] ＋　I[2] ＋ 2I[3]

この計算を、行う。
SIMD化するに当たっては、以下のプロセスとした。

入力に対して、２倍された配列（a0）と、１倍された配列を２つ（a1,a2）、３倍された配列（a3）を用意する。

a0 ＝２ × 入力

a0
2D[ 0]	2D[ 4]	2D[ 8]	2D[12]
2D[ 1]	2D[ 5]	2D[ 9]	2D[13]
2D[ 2]	2D[ 6]	2D[10]	2D[14]
2D[ 3]	2D[ 7]	2D[11]	2D[15]

a1 ＝１ × 入力

a0
D[ 0]	D[ 4]	D[ 8]	D[12]
D[ 1]	D[ 5]	D[ 9]	D[13]
D[ 2]	D[ 6]	D[10]	D[14]
D[ 3]	D[ 7]	D[11]	D[15]

a2 ＝１ × 入力

a0
D[ 0]	D[ 4]	D[ 8]	D[12]
D[ 1]	D[ 5]	D[ 9]	D[13]
D[ 2]	D[ 6]	D[10]	D[14]
D[ 3]	D[ 7]	D[11]	D[15]

a3 ＝３ × 入力

a0
3D[ 0]	3D[ 4]	3D[ 8]	3D[12]
3D[ 1]	3D[ 5]	3D[ 9]	3D[13]
3D[ 2]	3D[ 6]	3D[10]	3D[14]
3D[ 3]	3D[ 7]	3D[11]	3D[15]

次にやることは、32bit単位で、a0～a3を回転。

rol a0,0　　（つまり回転しない。）

a0
2D[ 0]	2D[ 4]	2D[ 8]	2D[12]
2D[ 1]	2D[ 5]	2D[ 9]	2D[13]
2D[ 2]	2D[ 6]	2D[10]	2D[14]
2D[ 3]	2D[ 7]	2D[11]	2D[15]

rol a1,8　　（左8bit回転）

a0
D[ 3]	D[ 7]	D[11]	D[15]
D[ 0]	D[ 4]	D[ 8]	D[12]
D[ 1]	D[ 5]	D[ 9]	D[13]
D[ 2]	D[ 6]	D[10]	D[14]

rol a2,16　　（左16bit回転）

a0
D[ 2]	D[ 6]	D[10]	D[14]
D[ 3]	D[ 7]	D[11]	D[15]
D[ 0]	D[ 4]	D[ 8]	D[12]
D[ 1]	D[ 5]	D[ 9]	D[13]

rol a3,24　　（左24bit回転）

a0
3D[ 1]	3D[ 5]	3D[ 9]	3D[13]
3D[ 2]	3D[ 6]	3D[10]	3D[14]
3D[ 3]	3D[ 7]	3D[11]	3D[15]
3D[ 0]	3D[ 4]	3D[ 8]	3D[12]

回転後、このa0～a3を加算すれば、期待値の配列が得られるわけです。
ここでの加算は、ガロア体GF(2⁸)における演算であるので、
期待値＝ a0 ^ a1 ^ a2 ^ a3


//==============================================================
//		fips-197	5.1.3	MixColumns
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Input
//	●返値
//			__m128i		Output
//==============================================================
__m128i	AES::MixColumns(__m128i data)
{
	__m128i		a0 = mul(data, 2);
	__m128i		a1 = data;		//	= mul(data, 1);
	__m128i		a2 = data;		//	= mul(data, 1);
	__m128i		a3 = mul(data, 3);
										//	もしSSE命令にrorがあったら
										//	こういうこと（32bit右回転）
	a1	= _mm_or_si128(_mm_srli_epi32(a1,24),_mm_slli_epi32(a1, 8));	//	prord	a1, 24
	a2	= _mm_or_si128(_mm_srli_epi32(a2,16),_mm_slli_epi32(a2,16));	//	prord	a2, 16
	a3	= _mm_or_si128(_mm_srli_epi32(a3, 8),_mm_slli_epi32(a3,24));	//	prord	a3, 8

	return(_mm_xor_si128(_mm_xor_si128(a0,a1),_mm_xor_si128(a2,a3)));
}

以下は、ガロア体GF(2⁸)における乗算を行う関数。
キャリー（桁上がり）を処理する為、配列要素を偶奇に分けて、8bit幅の配列を16bit幅にし、演算している。
ガロア体GF(2⁸)において、『x⁸ + x⁴ + x³ + x² + 1 ＝ 0』である為、桁上がり時は、この値（0x011B）を加算（XOR）する。


//==============================================================
//		fips-197	4.2	Multiplication
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Input
//			unsigned char n	
//	●返値
//			__m128i		Result (data[0..15] × n)
//==============================================================
__m128i	AES::mul(__m128i data, unsigned char n)
{
__declspec(align(16))	static	const	unsigned	__int16	_FF00[8] = {0xFF00,0xFF00,0xFF00,0xFF00, 0xFF00,0xFF00,0xFF00,0xFF00};
__declspec(align(16))	static	const	unsigned	__int16	_00FF[8] = {0x00FF,0x00FF,0x00FF,0x00FF, 0x00FF,0x00FF,0x00FF,0x00FF};
__declspec(align(16))	static	const	unsigned	__int16	_011B[8] = {0x011B,0x011B,0x011B,0x011B, 0x011B,0x011B,0x011B,0x011B};

	const	__m128i	_mm_FF00 = _mm_load_si128((__m128i*)&_FF00);
	const	__m128i	_mm_00FF = _mm_load_si128((__m128i*)&_00FF);
	const	__m128i	_mm_011B = _mm_load_si128((__m128i*)&_011B);

	__m128i	data1	=	_mm_srli_epi16(	_mm_and_si128(data, _mm_FF00), 8);
	__m128i	data2	=			_mm_and_si128(data, _mm_00FF);

	__m128i	result1	=	_mm_setzero_si128();
	__m128i	result2	=	_mm_setzero_si128();

	unsigned	char	i = 0x08;

	do{
		result1	= _mm_slli_epi16(result1, 1);
		result2	= _mm_slli_epi16(result2, 1);

		result1	= _mm_xor_si128(result1, _mm_and_si128(_mm_cmpgt_epi16(result1, _mm_00FF), _mm_011B));
		result2	= _mm_xor_si128(result2, _mm_and_si128(_mm_cmpgt_epi16(result2, _mm_00FF), _mm_011B));

		if(i & n){
			result1 = _mm_xor_si128(result1, data1);
			result2 = _mm_xor_si128(result2, data2);
		}
		i >>= 1;
	} while (i>0);

	return(_mm_or_si128(_mm_slli_epi16(result1, 8), result2));
}

AddRoundKey()

ラウンド数に応じた鍵スケジュールと、排他的論理和(XOR)するだけ。


//==============================================================
//		fips-197	5.1.4	AddRoundKey
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Input
//			int	i	Round
//	●返値
//			__m128i		Output
//==============================================================
__m128i	AES::AddRoundKey(__m128i data, int i)
{
	return(_mm_xor_si128(data, _mm_load_si128((__m128i*)&w[i*4])));
}

復号

暗号化の逆の順番となる。

Round	Function
Nr 初回ラウンド	InvAddRoundKey()
(Nr-1) ～ 1	InvShiftRows() InvSubBytes() InvAddRoundKey() InvMixColumns()
0 最終ラウンド	InvShiftRows() InvSubBytes() InvAddRoundKey()


//==============================================================
//		fips-197	5.3	InvCipher
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Cipher-text
//	●返値
//			__m128i		Plain-text
//==============================================================
__m128i	AES::InvCipher(__m128i data)
{
	//◆Round (Nr)
	int	i=Nr;

	data = InvAddRoundKey(data, i);
	i--;

	//◆Round (Nr-1) ～ (1)
	do{
		data = InvMixColumns(InvAddRoundKey(InvSubBytes(InvShiftRows(data)),i));
		i--;
	} while(i > 0);

	//◆Round (0)
	data = InvAddRoundKey(InvSubBytes(InvShiftRows(data)), i);

	return(data);
}

InvShiftRows()

何をやりたいかというと、ShiftRows()の逆の回転。

入力
D[ 0]	D[ 4]	D[ 8]	D[12]
D[ 1]	D[ 5]	D[ 9]	D[13]
D[ 2]	D[ 6]	D[10]	D[14]
D[ 3]	D[ 7]	D[11]	D[15]

という入力に対して

出力
D[ 0]	D[ 4]	D[ 8]	D[12]
D[13]	D[ 1]	D[ 5]	D[ 9]
D[10]	D[14]	D[ 2]	D[ 6]
D[ 7]	D[11]	D[15]	D[ 3]

に並べ替えて出力する関数がInvShiftRows()。
ShiftRows()と、同様の方法で回転できる。


//==============================================================
//		fips-197	5.3.1	InvShiftRows
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Input
//	●返値
//			__m128i		Output
//==============================================================
__m128i	AES::InvShiftRows(__m128i data)
{
__declspec(align(16))	static	const	unsigned	int	mask0[4] = {0x000000FF,0x000000FF,0x000000FF,0x000000FF};
__declspec(align(16))	static	const	unsigned	int	mask1[4] = {0x0000FF00,0x0000FF00,0x0000FF00,0x0000FF00};
__declspec(align(16))	static	const	unsigned	int	mask2[4] = {0x00FF0000,0x00FF0000,0x00FF0000,0x00FF0000};
__declspec(align(16))	static	const	unsigned	int	mask3[4] = {0xFF000000,0xFF000000,0xFF000000,0xFF000000};

	const	__m128i	_mm_mask0 = _mm_load_si128((__m128i*)&mask0);
	const	__m128i	_mm_mask1 = _mm_load_si128((__m128i*)&mask1);
	const	__m128i	_mm_mask2 = _mm_load_si128((__m128i*)&mask2);
	const	__m128i	_mm_mask3 = _mm_load_si128((__m128i*)&mask3);

	__m128i		a0	=	_mm_and_si128(_mm_mask0, data);					//縦方向の回転
	__m128i		a1	=	_mm_and_si128(_mm_mask3, _mm_shuffle_epi32(data, 0x39));	//0011 1001 b
	__m128i		a2	=	_mm_and_si128(_mm_mask2, _mm_shuffle_epi32(data, 0x4E));	//0100 1110 b
	__m128i		a3	=	_mm_and_si128(_mm_mask1, _mm_shuffle_epi32(data, 0x93));	//1001 0011 b

	return(_mm_or_si128(_mm_or_si128(a0,a1),_mm_or_si128(a2,a3)));
}

InvSubBytes()

SubBytes()関数の逆変換を行う。


//==============================================================
//		fips-197	5.3.2	InvSubBytes
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Input
//	●返値
//			__m128i		Output
//==============================================================
__m128i	AES::InvSubBytes(__m128i data)
{
	//テーブル変換は、SIMD化できない？
	data.m128i_u32[0] = InvSubWord(data.m128i_u32[0]);
	data.m128i_u32[1] = InvSubWord(data.m128i_u32[1]);
	data.m128i_u32[2] = InvSubWord(data.m128i_u32[2]);
	data.m128i_u32[3] = InvSubWord(data.m128i_u32[3]);

	return(data);
}

InvMixColumns()

MixColumns()で行った行列演算にて使用した行列の逆行列を用いて演算する。
入力された配列をI[0]～I[3]、出力すべき配列をO[0]～O[3]と仮定すると、

　| O[0] |　　　| 14　09　13　11 || I[0] |
　| O[1] |　＝　| 11　14　09　13 || I[1] |
　| O[2] |　　　| 13　11　14　09 || I[2] |
　| O[3] |　　　| 09　13　11　14 || I[3] |

つまり、

　O[0] ＝14I[0] ＋ 9I[1] ＋13I[2] ＋11I[3]
　O[1] ＝11I[0] ＋14I[1] ＋ 9I[2] ＋13I[3]
　O[2] ＝13I[0] ＋11I[1] ＋14I[2] ＋ 9I[3]
　O[3] ＝ 9I[0] ＋13I[1] ＋11I[2] ＋14I[3]

この計算を、行う。
入力に対して、14倍された配列（a0）、9倍された配列（a1）、13倍された配列（a2）と、11倍された配列（a3）を用意し、 MixColumns()関数同様に計算できる。


//==============================================================
//		fips-197	5.3.3	InvMixColumns
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Input
//	●返値
//			__m128i		Output
//==============================================================
__m128i	AES::InvMixColumns(__m128i data)
{
	__m128i		a0 = mul(data, 0x0E);
	__m128i		a1 = mul(data, 0x09);
	__m128i		a2 = mul(data, 0x0D);
	__m128i		a3 = mul(data, 0x0B);
										//	もしSSE命令にrorがあったら
										//	こういうこと（32bit右回転）
	a1	= _mm_or_si128(_mm_srli_epi32(a1,24),_mm_slli_epi32(a1, 8));	//	prord	a1, 24
	a2	= _mm_or_si128(_mm_srli_epi32(a2,16),_mm_slli_epi32(a2,16));	//	prord	a2, 16
	a3	= _mm_or_si128(_mm_srli_epi32(a3, 8),_mm_slli_epi32(a3,24));	//	prord	a3, 8

	return(_mm_xor_si128(_mm_xor_si128(a0,a1),_mm_xor_si128(a2,a3)));
}

InvAddRoundKey()

ラウンド数に応じた鍵スケジュールと、排他的論理和(XOR)するだけ。


//==============================================================
//		fips-197	5.3.4	InvAddRoundKey
//--------------------------------------------------------------
//	●引数
//			__m128i	data	Input
//			int	i	Round
//	●返値
//			__m128i		Output
//==============================================================
__m128i	AES::InvAddRoundKey(__m128i data, int i)
{
	return(_mm_xor_si128(data, _mm_load_si128((__m128i*)&w[i*4])));
}

th guest.

ソフトウェア（Software）

曲データ (Music Data)

資料（Document）

日記等

@sha_w_さんのツイート

メールアドレス
上のアドレスの『@』と『nifty』の間に『spa.』を追加して下さい。
画像で記載されているアドレスでも届きますが、スパム防止のフィルターを多数導入しています。

本ホームページはリンクフリーです。
リンクは、トップページ
"http://shaw.la.coocan.jp/"
にお願いいたします。

リンクページ (link page)

intel SSE2命令(SIMD)によるAES暗号処理 高速化実験資料

ソフトウェア（Software）

曲データ (Music Data)

資料（Document）

日記等

intel SSE2命令(SIMD)によるAES暗号処理　高速化実験資料