暗号化その3 - 日々量産

暗号化その2
http://d.hatena.ne.jp/ryousanngata/20100603/1275586104

の、続き。

OFB方式

暗号化するのは初期値に対してのみで、その暗号化した値と平文のxorを取ることで平文を暗号化します。

暗号文[0] = 平文[0] xor 暗号化関数(初期値)
暗号文[1] = 平文[1] xor 暗号化関数(暗号化[0]で生成した値)
.....
暗号文[n-1] = 平文[n-1] xor 暗号化関数(暗号化[n-2]で生成した値)
暗号文[n] = 平文[n] xor 暗号化関数(暗号化[n-1]で生成した値)

暗号化した値は次回の平文に再度しようすることで、同じ平文から同じ暗号文が生成されるのを防ぎます。
復号化については、S-DESは2回キーを使いますが復号化のときは2つのキーを入れ替えるだけでできるのですが、
この方式はその必要がなく、暗号化の処理さえ決まれば自動的に復号化もできるので、
暗号化関数と復号化関数と2つ管理する必要がなくなることと、
分岐が全くないので処理が単純化できるので、CBCより早く処理できることが利点です。
平文を暗号化すると暗号文ができ、暗号文を暗号化すると平文がとりだせることがこの方式の特徴です。

以下はS-DESにOFB方式を採用した例です。

// S-DES
// sw : 暗号化/復号化 切り替え(0:暗号化, 1:復号化)
// in : 暗号化/復号化するデータ列
// out: 暗号化/復号化したデータを記録する配列
// key: 10bitキー(2byte)
// len: 暗号化/復号化するデータ列の長さ
void _des_crypt(char sw, const char *in, char *out, short key, int len){
	register unsigned char key1, key2; // 鍵
	register unsigned char tmp, tmp2; // 作業領域
	
	register char iniv = 0xAA; // 10101010
	
	// 転置P10
	key = P10(key); 
	// 10bit列を左と右5bitに分け、5bit算術左シフト(1)をし、10bit列を生成
	key = LS1(key>>5)<<5|LS1(key&0x1F); // 統合
	key1 = P8(key); // key1取得
	// 10bit列を左と右5bitに分け、5bit算術左シフト(2)をし、10bit列を生成
	key = LS2(key>>5)<<5|LS2(key&0x1F); // 統合
	key2 = P8(key); // key2取得
	
	// 復号化切り替えは不要
//	if(sw){ tmp=key1; key1=key2; key2=tmp; }
	
	while(len--){
		// in
		tmp2 = IP(iniv);
		
		// round 1
		tmp = EP(tmp2&0xF) ^ key1;
		tmp = S0[(tmp>>6&2)|(tmp>>4&1)][(tmp>>5&3)]<<2 | S1[(tmp>>2&2)|(tmp&1)][(tmp>>1&3)]; // S0[14][23]<<2 | S1[14][23]
		tmp = P4(tmp) << 4 ^ tmp2;
		
		// SWAP (右4|左4) => (左4|右4)
		tmp2= SW(tmp);
		
		// round 2
		tmp = EP(tmp2&0xF) ^ key2;
		tmp = S0[(tmp>>6&2)|(tmp>>4&1)][(tmp>>5&3)]<<2 | S1[(tmp>>2&2)|(tmp&1)][(tmp>>1&3)];
		tmp = P4(tmp) << 4 ^ tmp2;
		
		iniv = IP_1(tmp);
		
		// out
		*out++ = *in++ ^ iniv;
	}
	*out = 0;
}

文字列を入力: aaaa
key(16bit): 1234
キー : 1234
入力 : 61 61 61 61 0A
暗号化: AD CE 2F B2 DE
復号化: 61 61 61 61 0A

前回と同じく、初期値inivとして0xAA(10101010)を採用していますが、
初期値は最悪ばれても、keyがわからないと復号化できません。
実際に平文から暗号文を生成している処理は、

		*out++ = *in++ ^ iniv;

この１行のみです。その前はinivをS-DESで暗号化しているだけです。

CTR方式

CTRはCounterの略字です。
考え方は、OFBと同じですが、暗号化をするときの値を算出する方法が少し異なり、
初期値を1づつカウントアップしながら暗号化をします。
暗号文を生成する例を示すと、

暗号文[0] = 平文[0] xor 暗号化関数(初期値 + 0)
暗号文[1] = 平文[1] xor 暗号化関数(初期値 + 1)
.....
暗号文[n-1] = 平文[n-1] xor 暗号化関数(初期値 + n-1)
暗号文[n] = 平文[n] xor 暗号化関数(初期値 + n)

という感じに求めることができます。
ここで注目したいのは、暗号化関数に使われる値は、
前回の暗号化に使った値とは関連がないということです。
初期値さえ決まれば、あとはその順番さえわかれば任意の場所から暗号化が可能です。
また、これは並列処理もできることを意味します。
今回は都合上、2つのメリットを生かした実装は行いません。
"何番目"から"何番目"まで暗号/復号する、という引数を与えるだけでいいんですけどね。

// S-DES
// sw : 暗号化/復号化 切り替え(0:暗号化, 1:復号化)
// in : 暗号化/復号化するデータ列
// out: 暗号化/復号化したデータを記録する配列
// key: 10bitキー(2byte)
// len: 暗号化/復号化するデータ列の長さ

void _des_crypt(char sw, const char *in, char *out, short key, int len){
	register unsigned char key1, key2; // 鍵
	register unsigned char tmp, tmp2; // 作業領域
	register char iniv;
	
	srand(key<<16|key);
	iniv = rand()>>8 & 0xFF;

	// 転置P10
	key = P10(key); 
	// 10bit列を左と右5bitに分け、5bit算術左シフト(1)をし、10bit列を生成
	key = LS1(key>>5)<<5|LS1(key&0x1F); // 統合
	key1 = P8(key); // key1取得
	// 10bit列を左と右5bitに分け、5bit算術左シフト(2)をし、10bit列を生成
	key = LS2(key>>5)<<5|LS2(key&0x1F); // 統合
	key2 = P8(key); // key2取得
	
	// 復号化切り替えは不要(S-DESの特徴がなくなるけど)
//	if(sw){ tmp=key1; key1=key2; key2=tmp; }
	
	while(len--){
		// in
		tmp2 = IP(iniv++);
		
		// round 1
		tmp = EP(tmp2&0xF) ^ key1;
		tmp = S0[(tmp>>6&2)|(tmp>>4&1)][(tmp>>5&3)]<<2 | S1[(tmp>>2&2)|(tmp&1)][(tmp>>1&3)]; // S0[14][23]<<2 | S1[14][23]
		tmp = P4(tmp) << 4 ^ tmp2;
		
		// SWAP (右4|左4) => (左4|右4)
		tmp2= SW(tmp);
		
		// round 2
		tmp = EP(tmp2&0xF) ^ key2;
		tmp = S0[(tmp>>6&2)|(tmp>>4&1)][(tmp>>5&3)]<<2 | S1[(tmp>>2&2)|(tmp&1)][(tmp>>1&3)];
		tmp = P4(tmp) << 4 ^ tmp2;
		
		// out
		*out++ = *in++ ^ IP_1(tmp);
	}
	*out = 0;
}

最初の段階で、srandとrandで乱数を作っています。
srandとrandの特徴として、srandに同じ値で乱数を初期化した場合、
randで得られる乱数は同じものとなるという事を利用します。
ただ、randの実装に依存してしまうので、機器の間での互換性を持たせるには不向きです。
独自の乱数生成関数を定義する必要があるでしょう。

今までと違うのは初期値に定数を使わず、キーに依存した乱数を生成していることです。
初期値が違うことで初期値に依存した一定のパターンがなくなるので、より特定しにくくなります。
本来ならばこんな感じに、初期値は定数ではなく何らかの方法でkeyと一意な値を算出できるようにするべきかもしれません。

srand(key<<16|key);とした理由は特にないんですが、
なんとなくできるだけ大きい値を使って初期化しようとしました。
rand()で乱数を取り出すときは8bit目〜15bit目を使います。
これも特に理由はありませんが、線形合同法では下位bitが偏りやすいらしいので上位bitを使うようにしたというだけです。

基本的な暗号化手順はOFBとやっていることが同じですが、
iniv++の部分を、n番目の平文を暗号化するのであれば、iniv+nとする感じに、
並列処理を実現することが可能になります。
OFBも1回目の暗号化、2回目の暗号化の結果を先に計算できていれば、同様に並列処理が可能です。