Galois Finite Fields and the Advanced Encryption Standard (AES)

Galois有限体とAdvanced Encryption Standard (AES)

CS 463/480 講義、Dr. Lawlor 氏

与えられたサイズの全ての有限体は同等であるため、256個の要素を持つ体は常に同じ普遍的な性質を持ちます。Galois は、ナポレオン後のフランスの混乱の中で20歳で亡くなりましたが、この分野の多くの数学的道筋を開拓しました。そのため、256個の要素を持つ体はGF(2^8)、すなわち「2^8個の要素を持つGalois体」と呼ばれます。

奇妙なことに、サイズpnの体の要素は、係数を整数 modulo p（「標数pの体」）から選んだ、次数nまでの多項式と同等です。例えば、0や1のような数を多項式0や1で表すという、当たり前のことを行うことができます。ここまでは問題ありませんが、2は係数を modulo p からしか選べないため問題になります。そこで、多項式の次数を1つ上げ、例えば「2=10=1x+0」とします。これにより、数のバイナリ表現のビットと、対応する体の多項式の項との間に単純な対応関係が生まれます。

幸いなことに、この数学的構造は、置換テーブルの値を計算したり、単純なシフトやXOR演算を動機付けたりするために存在するだけです。実行時に「数を多項式に変換する」必要は全くなく、多項式をいかなるxの値でも評価することはありません。

有限体の加算

有限体の加算は、基となる多項式を加算することで理解できます。例えば：
1 + 2 = 1+10 = (1)+(1x+0) = 1x+1 = 11 = 3

しかし、係数は単一ビットであるため、
2 + 2 = 10+10 = (1x+0)+(1x+0) = 2x = 0x = 0
この単一ビットのバイナリラップアラウンドにより、GF(2^8)では加算、減算、XORはすべて同じ演算になります。これは通常の加算とは大きく異なるように思えますが、回路においては、各単一ビット加算の桁上げビットを捨てることに対応します。

以下は、4ビット（16進数1桁）の有限体であるGF(2^4)の加算テーブルです：

0 1 2 3 4 5 6 7 8 9 a b c d e f 
1 0 3 2 5 4 7 6 9 8 b a d c f e 
2 3 0 1 6 7 4 5 a b 8 9 e f c d 
3 2 1 0 7 6 5 4 b a 9 8 f e d c 
4 5 6 7 0 1 2 3 c d e f 8 9 a b 
5 4 7 6 1 0 3 2 d c f e 9 8 b a 
6 7 4 5 2 3 0 1 e f c d a b 8 9 
7 6 5 4 3 2 1 0 f e d c b a 9 8 
8 9 a b c d e f 0 1 2 3 4 5 6 7 
9 8 b a d c f e 1 0 3 2 5 4 7 6 
a b 8 9 e f c d 2 3 0 1 6 7 4 5 
b a 9 8 f e d c 3 2 1 0 7 6 5 4 
c d e f 8 9 a b 4 5 6 7 0 1 2 3 
d c f e 9 8 b a 5 4 7 6 1 0 3 2 
e f c d a b 8 9 6 7 4 5 2 3 0 1 
f e d c b a 9 8 7 6 5 4 3 2 1 0

(NetRunで試す！)
数独のように、逆元が存在するためには、各出力が各行と各列にちょうど1回現れる必要があります。

有限体の乗算

有限体の乗算は、多項式の乗算（代数IIを思い出してください！）とまったく同じように機能します。つまり：
22=1010= (1x+0)(1x+0)=xx=x^2=1x^2+0x+0=100=4

これは、nより高い次数を生成する問題を除けばうまくいきます。例えば、1616=x^4x^4=x^8となり、これはGF(2^8)を超えています。これを修正するために、私たちは「還元多項式」の倍数を減算することによって高次を「還元」します。AESの場合、還元多項式はx^8 + x^4 + x^3 + x + 1（16進数で0x11b）です。還元多項式には多くの選択肢があります（計算がうまくいくためには「既約」、つまり多項式の素数に相当するものである必要があります）。しかし、それらは単に数を置換するだけで、基盤となる数学的構造を変えるわけではありません。

この場合、還元多項式を1回減算します：
1616=x^4x^4=x^8=x^8 - (x^8 + x^4 + x^3 + x + 1)
全ての要素がそれ自身の加法逆元であるため、これは次のようになります：
...=x^4 + x^3 + x + 1 = 11011 = 27。
偶数×偶数がこの方法で奇数になる可能性があることに注意してください！

還元操作は、有限体の乗算に奇妙な風味を与えます。例えば、GF(2^8)における2（1x+0）を掛ける場合の256要素の16進数乗算テーブルは次のようになります（Wikipediaより）：

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

テーブルの前半は整数乗算とほぼ同じですが、テーブルの途中から還元が必要になり、結果が特に下位ビットでばらつき始めます。

還元多項式0x13 == 10011 == x^4+x+1 を使用したGF(2^4)の乗算テーブルを以下に示します。（より詳細なGF(16)の例 を参照してください。）

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 2 3 4 5 6 7 8 9 a b c d e f 
0 2 4 6 8 a c e 3 1 7 5 b 9 f d 
0 3 6 5 c f a 9 b 8 d e 7 4 1 2 
0 4 8 c 3 7 b f 6 2 e a 5 1 d 9 
0 5 a f 7 2 d 8 e b 4 1 9 c 3 6 
0 6 c a b d 7 1 5 3 9 f e 8 2 4 
0 7 e 9 f 8 1 6 d a 3 4 2 5 c b 
0 8 3 b 6 e 5 d c 4 f 7 a 2 9 1 
0 9 1 8 2 b 3 a 4 d 5 c 6 f 7 e 
0 a 7 d e 4 9 3 f 5 8 2 1 b 6 c 
0 b 5 e a 1 f 4 7 c 2 9 d 6 8 3 
0 c b 7 5 9 e 2 a 6 1 d f 3 4 8 
0 d 9 4 1 c 8 5 2 f b 6 3 e a 7 
0 e f 1 d 3 2 c 9 7 6 8 4 a b 5 
0 f d 2 9 6 4 b 1 e c 3 8 7 5 a

これは以下のコードによって生成されます：

// Bitwise ("peasant") multiplication, using galois addition
for (int bit=3;bit>=0;bit--) {
	if (b&(1<<bit))
		c=c^(a<<bit);
}
// Reduce back into galois field (can also be folded into above loop)
int irr=0x13; // represents reduction polynomial
int high=0x10; // high bit of above
for (int bit=3;bit>=0;bit--) {
	if (c&(high<<bit))  // if that bit is set
		c=c^(irr<<bit); // galois "subtract" it off
}

(NetRunで試す！)

GF(2^8)であるAESの体では、これは乗算テーブルになります：
［画像: GF(256) or GF(2^8) multiplication table］

テーブルの前半は単純な乗算と同じですが、テーブルの途中から還元が必要になり、結果がばらつき始めます。

前方乗算は短いアルゴリズムですが、非線形性が高いため、有限体での除算は困難です。通常は乗算逆元のテーブルを作成し、その逆元を掛けることで行われます。対数と逆対数のテーブルを作成することでも、乗算と除算を効率的に実行できます。これらの体には要素が256個しかないため、テーブルは有効です。

AESの操作

AES の各ラウンドは、4x4バイトのグリッドに対して以下の操作で構成されます。

1. グリッド内の各バイトはS-box を通ります。これは、乗算逆元と、それに続くアフィン変換（0または1との乗算および加算のシリーズ）で構成されます。アフィン変換は、0の問題（乗算逆元が存在しないため、慣例により1/0=0）を解決し、数学的な性質を操作して、乗算逆元を連鎖させられないようにします。
2. ShiftRows は、4x4グリッド内で各バイトを水平方向にシフトします。行iはiバイトだけ循環シフトされます。
3. MixColumns は、各列に対して線形変換を計算します。線形変換は、有限体の乗算と加算のシリーズです。使用される行列は可逆であるため、逆操作が存在します。また、入力バイトが1つでも変更されると、全ての出力バイトが変更されるように選択されています。
4. 最後に、ラウンドキー が各バイトに加えられます（有限体でのXORと同じ操作）。

なぜ気にするのか？

有限体で作業する主な利点は次のとおりです。

• 数値が小さく保たれます。GF(2^8)では、乗算や除算の後でも、常に1バイトに収まります。

• 各操作に逆元が存在するため、復号化が可能です。これは、2を掛けると最上位ビットが失われるような、より単純な2のべき乗法におけるモジュラ算術よりも優れています。

• 数学がよく理解されており、1830年代にまで遡ります。これにより、優れた混合関数を選択しやすくなり、新しい解析手法に驚かされる可能性が低くなります。

• 操作が豊富に組み合わさるため、豊かな方法で組み合わせることができます。AESは、Sボックスの前半での除算、行シフトでの転置、MixColumnsおよびSボックスの後半での行列演算を組み合わせています。行列演算は互いに可換ではなく、転置と除算により行列を掛け合わせることができなくなります。対照的に、例えば加算のみの場合、いくら操作を繰り返してもシフト暗号になります。加算と乗算のみの場合、いくら操作を繰り返しても線形暗号になります。

興味がある場合は、FIPS 197 に詳細な例があり、Rijndael AES論文 は非常に読みやすく、設計の動機に関する詳細が含まれています。