ブロック型共通鍵暗号の代表AES(Advanced Encryption Standard)の仕組みについてみていきます。AESはブロック長さ128ビット、鍵長128, 192, 256ビットのものが標準化され、現在でも広く使われています。
1. 仕組み
1.1 鍵の拡張
始めに与えられた鍵はAES鍵スケジュールに従ってラウンド鍵としてあらかじめ拡張しておきます。これを、次に説明するラウンドごとにシフトして適用することで暗号強度をさらに強化しています。下の図はこの鍵の拡張の仕組みを128ビット(16バイト)鍵の場合について説明したものです。図の一番上のK0,0〜K3,3は最初に与えられた鍵の各バイトです。これをベースに次の回転のための鍵を作り出します。４バイトを１ワードどして、一番右の１ワード中をバイトローテートさせ、バイトごとの値変換を行い一番左の１ワードと排他的論理和をとり２番目の鍵の一番左の１ワードとします。
1.2 ブロックの暗号化
AESのブロック単位の暗号化は下の図に示すように４つのステップを1回転として、鍵長によって決まった回数だけ処理を繰り返して1ブロックの暗号化を実現します。下の図のように、まず処理の入り口で与えられた1ブロック(16バイト)のプレーンテキストと鍵の排他的論理和を取ってから、このループに入ります。また、最後の回転では途中で抜けて暗号化ブロックと鍵の排他的論理和をさらにとって処理を完了します。
1回転の4ステップでは次のような処理をします。
ステップ1）バイト変換：あらかじめ決められたバイトdごとの変換表(Substitution Box)に基づいて、入力メッセージSを変換します。変換表は256個の配列で入力メッセージ1バイト(8bit)の値を引数として対応する変換値を求めます。
ステップ2）行シフト：1）で得られたメッセージを4x4の表に配置して行ごとにバイト単位でシフトします。
ステップ3）カラム混合：2）で得られたメッセージを4x4の表に配置してカラムごとに4バイトをビットローテートさせながら排他的論理和で混合します。
ステップ4）ラウンド鍵：3）で得られたメッセージとラウンド鍵の排他的論理和を求めます。
この様子を次のような図で表すと、1回転ごとに、バイト単位の入れ替え、行シフト、カラム混合、鍵による暗号化が組み合わされる様子が直感的に理解できます。
カラム混合は下に示すように一種のマトリックスの掛け算になっています。ただし、個々の要素は通常の掛け算ではなく、
因数分解できない多項式(既約多項式) x^8+x^4+x^3+x+1による剰余とします。また、各要素は排他的論理和を取ります。
2. Cプログラムによる実現
2.1 基本的な実現
AESによるブロック暗号の実際のC言語プログラムで見てみます。ソースコードはwolfSSLのGithubで参照できます。
鍵の拡張は下に示すように、前処理としてwc_AesSetKey(内部的にはwc_AesSetKeyLocal)の中で行なっておきます。
static int wc_AesSetKeyLocal(Aes* aes, const byte* userKey, word32 keylen,
const byte* iv, int dir, int checkKeyLen)
１ブロックの暗号化処理はwc_AesEncryptで行われます。同じ上記のアルゴリズムの実現でも、許されるROMサイズのような実装条件によって初期値テーブルのサイズやループを展開するかどうかなどをマクロスイッチで選べるようになっています。もっとも原理的なバージョンでは、原理通りの１バイト256エントリーの変換テーブルと鍵サイズにより10から14回のループによって処理を実現します。このソースコードは次のようになります。
まず、バイト変換用の256エントリーの初期値配列 Tsboxを定義します。
/* バイト変換テーブル */
static const byte Tsbox[256] = {
0x63U, 0x7cU, 0x77U, 0x7bU, 0xf2U, 0x6bU, 0x6fU, 0xc5U,
...
0x41U, 0x99U, 0x2dU, 0x0fU, 0xb0U, 0x54U, 0xbbU, 0x16U
};
１ブロックのAES暗号化関数 wc_AesEncrypt では、まず前処理としてラウンド鍵と排他的論理和を求めます。
回転処理に入り、まず１ワード(4バイト)のバイト変換結果をt0 - t3 に格納します。この時、行シフトも考慮して格納します。
次にカラムごとのカラム混合(col_mul)と結果の排他的論理和とさらにローテート鍵との排他的論理和を求めこれを一回転分の結果としてs0 -s3に戻します。
これを所定の回転数だけ繰り返し、最後にもう一度ラウンド鍵と排他的論理和をもとめ、これを結果とします。
static void wc_AesEncrypt(Aes* aes, const byte* inBlock, byte* outBlock)
{
XMEMCPY(&s0, inBlock, sizeof(s0));
XMEMCPY(&s1, inBlock + sizeof(s0), sizeof(s1));
XMEMCPY(&s2, inBlock + 2 * sizeof(s0), sizeof(s2));
XMEMCPY(&s3, inBlock + 3 * sizeof(s0), sizeof(s3));
/* はじめの鍵との排他的論理和 */
s0 ^= rk[0];
s1 ^= rk[1];
s2 ^= rk[2];
s3 ^= rk[3];
r *= 2;
/* Two rounds at a time */
for (rk += 4; r > 1; r--, rk += 4) {
/* バイト変換：変換テーブルによるバイト変換と行シフト */
t0 =
((word32)Tsbox[GETBYTE(s0, 3)] << 24) ^
((word32)Tsbox[GETBYTE(s1, 2)] << 16) ^
((word32)Tsbox[GETBYTE(s2, 1)] << 8) ^
((word32)Tsbox[GETBYTE(s3, 0)]);
t1 = ...
t2 = ...
t3 = ...
/* カラム混合と鍵との排他的論理和 */
s0 =
(col_mul(t0, 3, 2, 0, 1) << 24) ^
(col_mul(t0, 2, 1, 0, 3) << 16) ^
(col_mul(t0, 1, 0, 2, 3) << 8) ^
(col_mul(t0, 0, 3, 2, 1) ) ^
rk[0];
s1 = ...
s2 = ...
s3 = ...
}
/* 最後の変換テーブル */
t0 =
((word32)Tsbox[GETBYTE(s0, 3)] << 24) ^
((word32)Tsbox[GETBYTE(s1, 2)] << 16) ^
((word32)Tsbox[GETBYTE(s2, 1)] << 8) ^
((word32)Tsbox[GETBYTE(s3, 0)]);
t1 = ...
t2 = ...
t3 = ...
/* 鍵との排他的論理和 */
s0 = t0 ^ rk[0];
s1 = t1 ^ rk[1];
s2 = t2 ^ rk[2];
s3 = t3 ^ rk[3];
#endif
/* write out */
XMEMCPY(outBlock, &s0, sizeof(s0));
XMEMCPY(outBlock + sizeof(s0), &s1, sizeof(s1));
XMEMCPY(outBlock + 2 * sizeof(s0), &s2, sizeof(s2));
XMEMCPY(outBlock + 3 * sizeof(s0), &s3, sizeof(s3));
}
カラム混合cul_mul関数は次のように定義されています。カラム混合は対象の４バイトを多項式として要素の排他的論理和をとります。マトリックスの１行目は次のようになります。
2 x a0 ^ 3 x a1 ^ a2 ^ a3
AESのMixCulmnsでは、２倍演算は１ビット左ローテーと特定の値の剰余(0x1bとのand)なので、これをAES_XTIME(x)で定義します。
#define AES_XTIME(x) ((byte)((byte)((x) << 1) ^ ((0 - ((x) >> 7)) & 0x1b)))
col_mul内の処理は次のように変形できます。
2 x a0 ^ 2 x a1 ^ a1 ^ a2 ^ a3
= 2 x (a0 ^ a1) ^ a2 ^ a3
/* カラム混合 */
#define GETBYTE(x, y) (word32)((byte)((x) >> (8 * (y))))
static word32 col_mul(word32 t, int i2, int i3, int ia, int ib)
{
byte t3 = GETBYTE(t, i3);
byte tm = AES_XTIME(GETBYTE(t, i2) ^ t3);
return GETBYTE(t, ia) ^ GETBYTE(t, ib) ^ t3 ^ tm;
}
3.2 最適化
次にAESの最適化について見ていきます。最適化は主に次の二つで実現します。
１）あらかじめ計算できる部分を計算し拡張した変換テーブルを利用
２）ループも展開し、ブランチを排除する
下は最適化用のバイト変換テーブルの様子を示したものです。このように4面、1ワード(4バイト)による表(フルテーブル)を用意することによっていっぺんに4バイト単位のバイト変換、行シフトを行いカラム混合の処理につなぐことができます。
static const word32 Te[4][256] = {
{
0xc66363a5U, 0xf87c7c84U, 0xee777799U, 0xf67b7b8dU,
0xfff2f20dU, 0xd66b6bbdU, 0xde6f6fb1U, 0x91c5c554U,
0x60303050U, 0x02010103U, 0xce6767a9U, 0x562b2b7dU,
…
0x4141c382U, 0x9999b029U, 0x2d2d775aU, 0x0f0f111eU,
0xb0b0cb7bU, 0x5454fca8U, 0xbbbbd66dU, 0x16163a2cU,
}
};
3.3 ベンチマーク
次のグラフは、この変換表を使った最適化の効果を示したものです。AES-CBCの場合の１秒あたりの処理メッセージのバイト数の相対比較を、8ビット表と１ワードのフルテーブルを使ってループ処理した場合とループを展開した場合について示しています。グラフでわかるように、フルテーブルを使用する効果が大きいことがわかります。
一方、それらの３つの条件でのコードサイズについて下のグラフで比較します。このように、AESの最適化は処理速度とコードサイズのトレードオフで実現されていることがわかります。
まとめ
AESの原理と具体的な実現例についてみてきました。単純な１ブロックの暗号化アルゴリズムにも処理性能とコードサイズのトレードオフがあることがわかります。
この記事の内容を含めてTLプログラミングについて解説をまとめる機会をいただきました。興味のあるかたはご覧ください。徹底解剖 TLS 1.3 (翔泳社から 3/7刊行)。