AES (Rijndael) には攪拌するための処理の一つに MixColumns という処理があります。 AES を説明する記事は大量にあるにも関わらず、この MixColumns の処理は数学(数論)の知識が必要というだけで敬遠されているようなので、MixColumns について説明していきます。
AES 1 の暗号処理は、内部に 4×4 の状態を持ち、ラウンド関数を繰り返す SPN 構造 2 となっていて、ラウンド関数は、暗号処理の基本となる置換 (Substitution) と転置 (Permutation) を組み合わせたものです 3 4。 MixColumns の処理は「転置」にあたる部分の処理です。
+---+---+---+---+ +---+---+---+---+
| 0 | 4 | 8 | c | | 0'| 4'| 8'| c'|
+---+---+---+---+ +---+---+---+---+
| 1 | 5 | 9 | d | | 1'| 5'| 9'| d'|
+---+---+---+---+ +---+---+---+---+
| 2 | 6 | a | e | | 2'| 6'| a'| e'|
+---+---+---+---+ +---+---+---+---+
| 3 | 7 | b | f | | 3'| 7'| b'| f'|
+---+---+---+---+ +---+---+---+---+
| | | | ^ ^ ^ ^
+---|---|---|---------------+ | | |
+---|---|-------------------+ | |
+---|-----------------------+ |
+---------------------------+
列ごとにMixColumnsの処理を行う
数式
MixColumns の処理を数式で表すと次のようになります。つまり行列の掛け算です。 変換前が で、変換後が です。
ただし注意ですが、各要素は16進数による表現で、拡大体 (法既約多項式 : ) の要素です。なので、足し算と掛け算は次のように定義されます。
足し算
足し算は2つの要素のXOR () をとります。 例えばバイナリ表現で2つの要素が と のとき、足し算の結果は (ただし ) となります。
以下の数式は全て正しく、表現形式は異なりますが全て同じ意味です。
掛け算
掛け算は要素を多項式と見なして、多項式同士の掛け算を行います。 ただし、既約多項式 を法とする多項式環上で演算を行います。 要素の掛け算を表す記号は「」です。
例えば、 となります。 式変形して考えてみると:
これを、法既約多項式で剰余をとると、右辺と一致します。
行列の掛け算
上述した足し算「」と掛け算「」を使って行列の掛け算を行うと次のようになります。
次の章では、これを計算するためのプログラムを作る方法について説明していきます。
アルゴリズム
足し算にあたる「」は ^
で計算できます。
なので、実装する必要があるのは、要素同士の掛け算にあたる「」です。
掛け算のアルゴリズム
要素の掛け算を行うためには多項式同士の掛け算を行うためのプログラムを書く必要があります。 とりあえず SageMath を使えば簡単に計算できます (以下は を計算する SageMath のコードです)。
F.<X> = PolynomialRing(GF(2^8))
R.<x> = F.quotient(X^8 + X^4 + X^3 + X + 1)
R(x^6 + x^4 + x^2 + x + 1) * R(x^7 + x + 1)
# => x^7 + x^6 + 1
しかし、SageMath は数学屋さんか暗号屋さんくらいしかインストールしていないと思いますので、素直に実装していきましょう。
まず、ある要素 は次のように書けます。
このとき、ある要素 に を掛けた多項式は次のように書けます。
このとき、 を法既約多項式で剰余する必要があります。 なぜなら、要素の最大次数は だからです。
剰余する方法としては の計算結果で であれば、結果から法既約多項式 を引き算します。
足し算が XOR なら引き算も XOR でできます (GF(2) なので)。
この法既約多項式をバイナリ表現にすると となりますが、計算上は unsigned char
(1byte)で計算するため、桁あふれ分は考慮しません。
なので、引き算 (XOR) する値は です。
最終的に、 を掛け算する処理というのは「多項式 に を掛けて のときは する」という流れになります。
この処理を xtime(b)
という関数にしておきます。C言語で書くと次のようになります。
ここで、b
は多項式、<< 1
は の掛け算、^
は引き算、b & 0x80
は のとき真、0x1b
は法既約多項式の値を表します。
unsigned char xtime(unsigned char b)
{
return (b << 1) ^ ((b & 0x80) ? 0x1b : 0x00);
}
より高い次元の を掛け算するときは xtime
を繰り返します。
多項式に を掛け算することは、バイナリ表現における左1ビットシフトであり、16進数表現では値を2倍することと同じ意味です。
これによって、任意の値の掛け算を実装することができます。
例えば、先ほど示した例の をプログラム的に計算してみます。 まずは、forループで と を掛け算したときの結果を用意します。
よって、バイナリ法の考え方で
となり、これを応用すれば任意の要素同士の掛け算を行うことができます。
この処理を dot(x, y)
という関数にして、C言語で書くと次のようになります。
unsigned char dot(unsigned char x, unsigned char y)
{
unsigned char mask;
unsigned char product = 0;
for (mask = 0x01; mask; mask <<= 1) {
if (y & mask) {
product ^= x;
}
x = xtime(x);
}
return product;
}
行列の掛け算のアルゴリズム
足し算「」と掛け算「」がプログラムで計算できるようになったので、MixColumns の処理である行列の掛け算が実装できるようになります。 繰り返しになりますが、変換前が 、変換後が とすると、変換は次の数式で書けます。
この処理を mix_columns(s)
という関数にして、C言語で実装すると次のようになります。
なお なので、係数が1の要素はそのまま使います。
static void mix_columns(unsigned char s[][4])
{
int c;
unsigned char t[4];
for (c = 0; c < 4; c++) {
t[0] = dot(2, s[0][c]) ^ dot(3, s[1][c]) ^ s[2][c] ^ s[3][c];
t[1] = s[0][c] ^ dot(2, s[1][c]) ^ dot(3, s[2][c]) ^ s[3][c];
t[2] = s[0][c] ^ s[1][c] ^ dot(2, s[2][c]) ^ dot(3, s[3][c]);
t[3] = dot(3, s[0][c]) ^ s[1][c] ^ s[2][c] ^ dot(2, s[3][c]);
s[0][c] = t[0];
s[1][c] = t[1];
s[2][c] = t[2];
s[3][c] = t[3];
}
}
暗号化行列 (MDS行列)
MixColumns で使う暗号化行列は、MDS行列と呼ばれる行列で、各行が線形変換 によって生成されています。 符号理論におけるMDS(最大距離分離)の各符号の距離はシングルトン限界 (Singleton bound) の最大値の であるため、入力を効率よく攪拌することができることから、MDS行列は暗号プリミティブとしてよく使用されます 5。 AESではまず、以下の逆元が存在する多項式を最初の行としています。
行目から 行目は線形変換 によって生成され、 行目まで繰り返したものを 行列にまとめたものが暗号化行列になります。 以下のプログラムでは4行目、3行目、…の順に各行を生成してAESで使われる暗号化行列を生成している様子です。
G.<x> = GF(2^8)
F.<K> = PolynomialRing(G)
R.<k> = F.quotient(K^4 + 1)
row4 = R(G.fetch_int(0x03)*k^3 + G.fetch_int(0x01)*k^2 + G.fetch_int(0x01)*k + G.fetch_int(0x02))
row3 = row4 * k
row2 = row3 * k
row1 = row2 * k
matrix([[row1], [row2], [row3], [row4]])
# => [x*k^3 + (x + 1)*k^2 + k + 1] ... [02 03 01 01] 多項式の係数を行列で表したもの
# => [k^3 + x*k^2 + (x + 1)*k + 1] ... [01 02 03 01]
# => [ k^3 + k^2 + x*k + (x + 1)] ... [01 01 02 03]
# => [ (x + 1)*k^3 + k^2 + k + x] ... [03 01 01 02]
暗号化行列の各行は、多項式環上の多項式なので、その逆元を求めれば復号用の多項式が求まり、最終的に復号行列が求まります。 続いては復号の話です。
InvMixColumns (逆演算)
MixColumns が暗号化プロセスならば、InvMixColumns は復号プロセスです。 InvMixColumns では次の行列を使って逆変換を行います。
なぜこの数字になるかというと、まず MixColumns の暗号化とは、法を とする多項式環上の多項式の掛け算で表されており、4つの暗号化多項式を1つの行列として扱っています(※説明のために要素同士の掛け算には変数 、多項式同士の掛け算には変数 を使っています)。 MixColumns (暗号化処理) の各行は多項式を表しているため、その逆演算である InvMixColumns (復号処理) の各行は逆元となる多項式にしないといけません。 多項式の最大次数は3なので、法を とする多項式環について、まず、暗号化の多項式 が次のように書けます。
そして、その逆元 は次のように書けるからです。
実際に、この2つの暗号化多項式と復号多項式を SageMath を使って、法を とする多項式環上で掛け算したプログラムを以下に示します。
G = GF(2^8)
F.<X> = PolynomialRing(G)
R.<x> = F.quotient(X^8 + X^4 + X^3 + X + 1)
S.<K> = PolynomialRing(R)
T.<k> = S.quotient(K^4 + 1)
# 暗号化多項式 [03 01 01 02]
enc = (X+1)*k^3 + (1)*k^2 + (1)*k + (X)
# => (x + 1)*k^3 + k^2 + k + x
# 復号多項式 [0b 0d 09 0e]
dec = (X^3+X+1)*k^3 + (X^3+X^2+1)*k^2 + (X^3+1)*k + (X^3+X^2+X)
# => (x^3 + x + 1)*k^3 + (x^3 + x^2 + 1)*k^2 + (x^3 + 1)*k + x^3 + x^2 + x
enc * dec
# => 1
補足で、GF(2^8).fetch_int を使った別の解き方のプログラムも記載しておきます(こちらの方が読みやすい&書きやすいです)。
G.<x> = GF(2^8)
F.<K> = PolynomialRing(G)
R.<k> = F.quotient(K^4 + 1)
# 暗号化多項式 [02 03 01 01] と復号多項式 [0d 09 0e 0b]
enc = R(G.fetch_int(0x02)*k^3 + G.fetch_int(0x03)*k^2 + G.fetch_int(0x01)*k + G.fetch_int(0x01))
dec = R(G.fetch_int(0x0d)*k^3 + G.fetch_int(0x09)*k^2 + G.fetch_int(0x0e)*k + G.fetch_int(0x0b))
enc * dec
# => 1
# 暗号化多項式 [01 02 03 01] と復号多項式 [09 0e 0b 0d]
enc = R(G.fetch_int(0x01)*k^3 + G.fetch_int(0x02)*k^2 + G.fetch_int(0x03)*k + G.fetch_int(0x01))
dec = R(G.fetch_int(0x09)*k^3 + G.fetch_int(0x0e)*k^2 + G.fetch_int(0x0b)*k + G.fetch_int(0x0d))
enc * dec
# => 1
# 暗号化多項式 [01 01 02 03] と復号多項式 [0e 0b 0d 09]
enc = R(G.fetch_int(0x01)*k^3 + G.fetch_int(0x01)*k^2 + G.fetch_int(0x02)*k + G.fetch_int(0x03))
dec = R(G.fetch_int(0x0e)*k^3 + G.fetch_int(0x0b)*k^2 + G.fetch_int(0x0d)*k + G.fetch_int(0x09))
enc * dec
# => 1
# 暗号化多項式 [03 01 01 02] と復号多項式 [0b 0d 09 0e]
enc = R(G.fetch_int(0x03)*k^3 + G.fetch_int(0x01)*k^2 + G.fetch_int(0x01)*k + G.fetch_int(0x02))
dec = R(G.fetch_int(0x0b)*k^3 + G.fetch_int(0x0d)*k^2 + G.fetch_int(0x09)*k + G.fetch_int(0x0e))
enc * dec
# => 1
2つを掛け算すると単位元 になることから、確かに、暗号化多項式の逆元が復号多項式になっていることが確認できます。 つまり、暗号化多項式を掛けた後に、復号多項式を掛けると、元に戻ることがわかります。
最終的に、復号における行列の掛け算を表す変換式は次のように書けます。
この処理を inv_mix_columns(s)
という関数にして、C言語で実装すると次のようになります。
static void inv_mix_columns(unsigned char s[][4])
{
int c;
unsigned char t[4];
for (c = 0; c < 4; c++) {
t[0] = dot(0x0e, s[0][c]) ^ dot(0x0b, s[1][c]) ^ dot(0x0d, s[2][c]) ^ dot(0x09, s[3][c]);
t[1] = dot(0x09, s[0][c]) ^ dot(0x0e, s[1][c]) ^ dot(0x0b, s[2][c]) ^ dot(0x0d, s[3][c]);
t[2] = dot(0x0d, s[0][c]) ^ dot(0x09, s[1][c]) ^ dot(0x0e, s[2][c]) ^ dot(0x0b, s[3][c]);
t[3] = dot(0x0b, s[0][c]) ^ dot(0x0d, s[1][c]) ^ dot(0x09, s[2][c]) ^ dot(0x0e, s[3][c]);
s[0][c] = t[0];
s[1][c] = t[1];
s[2][c] = t[2];
s[3][c] = t[3];
}
}
これで、MixColumns における復号の処理ができるようになりました。
補足ですが、説明の都合上、暗号化・復号の行列が先で、暗号化・復号の多項式が後になりましたが、NIST FIPS 197での本来の説明では、多項式から行列を導出していますのでご了承ください。
おわりに
以上が AES (Rijndael) の MixColumns の処理でやっている行列の掛け算の説明になります。 もっと詳しく知りたい人は Rijndael MixColumns – Wikipedia や FIPS 197, Advanced Encryption Standard (AES) あたりを読むと、より理解を深めることができると思います。
最近は中学生がAES暗号化アルゴリズムを実装する時代ですから… 6
🎄 この記事は「セキュリティキャンプ 修了生進捗 Advent Calendar 2019」の12日目です 🎄
参考文献
- FIPS 197, Advanced Encryption Standard (AES)
- Rijndael MixColumns - Wikipedia
- MDS matrix - Wikipedia
- 株式会社 東芝『暗号技術仕様書:Hierocrypt—L1』, May 2002
- 平澤 茂一『符号理論』, 平成20年4月9日
- 金子敏信『解説論文 共通鍵暗号の安全性評価』
-
AES は米国連邦標準の暗号規格として公開されています ↩
-
SPN (Substitution Permutation Network Structure) 構造とは、シャノンが対象鍵ブロック暗号について提案した「多くの階層を使うか、拡散 (Diffusion) と攪拌 (Confusion) の繰り返しを使う混合変換 (Mixing Transformation) で安全で実用的な合成暗号は作成できる」というアイデアに基づいています ↩
-
岡本 龍明「現代暗号の誕生と発展:ポスト量子暗号・仮想通貨・新しい暗号」近代科学社 2019 ↩
-
AES の鍵長が 128, 192, 256 のとき、ラウンド関数を繰り返す回数は 10, 12, 14 回となります ↩
-
C#でAES暗号化アルゴリズムを外部ライブラリに一切頼らず完全実装してみた - Qiita の著者は自己紹介で(2019/12時点では)「もうすぐ高校1年生です」と書いているので中学生と判断しました ↩