AESの内部構造がどうなっているか、線形写像の組み合わせとして解き明かしていくつもりです。
行列でわかるAES？
今回はAES暗号の全体的な流れを考察する。
ビジュネル暗号とAESを比較する
AES暗号を既存の秘密鍵暗号のような線形写像を用いた暗号にS-Boxという非線形写像とラウンドという処理を追加したものと考えてみる。
まず、S-boxを取り除いて残りの３種類の変換に分解したとき、それがどのような線形写像として与えられるかについて考察したい。
SubBytes(state);
ShiftRows(state);
MixColumns(state);
AddRoundKey(state, i);
このようになるのがAES。各段階をそれぞれビジュネル暗号に対して読み替えてみる。
1.SubByte：これが問題のS-Boxである。単にビジュネル暗号に処理を追加するだけ。
2.ShiftRows：行列状に並べ替えたデータの各行を１ブロックずつ巡回シフトする。
3.MixColumns：データと定数の入った行列との積をとる。
4.AddRoundKey：ビジュネル暗号の発展形か。
こう見ると、ビジュネル暗号の全ての段階において何らかの処理の変更をする必要がある。
で、これがどういう効果を持つかは攻撃法を理解しないと分からない。
4のAddRoundKeyであるが、これも単純に固定鍵を足すのではなく、ラウンド処理をする中でビジュネル暗号の鍵に対応する部分を変えながらRound数だけ繰り返す処理になる。
これらの妄想に従ってAESの秘密に迫ることになる。
まず単純にビジュネル暗号をRound処理する。
Roundの謎
DESやAESではビジュネルはもちろんのこと、エニグマにもない工夫がされている。
ラウンドといって同じ平文ブロックを繰り返し暗号化している。
これが何を意味するのか知りたい。
Roundを追加するにあたって、Roundo鍵に対応するのが$\pi,\phi$を使った鍵の置換処理である。
この場合、AESのラウンド鍵を生成する方法をそのまま借りてくることと、単に置換することとの安全性はどのように違うのか。
果たしてRound処理というのはどのような効果があるのか？
そしてなぜRound鍵はあのように生成するのか？
S-boxの謎
S-Boxの使い方がよくわからない。（線形だけど安全な符号ベースの暗号がなぜ安全なのだろうか？組み合わせ論の問題だろうか？）
線形写像でしかない暗号計算から、線形性をなくすための処理であると考えられる。
AESの場合、このS-BoxはGF(2)上の既約多項式$f(x)=x^8+x^4+x^3+x+1$を法として、平文mを２進多項式とみなした$m(x)$の逆元をとることに相当する。
これはアリスが少しプログラミングができるので可能である。
彼女は最初手書きで暗号日記を書いていたが、そのうち計算機でやることになる。
20240310追記：
具体的に非線形変換という例が思いつかなかったのだが、論文に例えば$x^3$だよと書いてあったので納得する。とりあえず入力の３乗を返すテーブルを作って試してみた。テーブルなんだから効率と速度はS-boxと同じである。でも３乗の方が好き。
AESを４つに分ける
void sub_bytes(uint8_t *state) {
uint8_t i, j;
for (i = 0; i < 4; i++) {
for (j = 0; j < Nb; j++) {
// s_box row: yyyy ----
// s_box col: ---- xxxx
// s_box[16*(yyyy) + xxxx] == s_box[yyyyxxxx]
state[Nb*i+j] = s_box[state[Nb*i+j]];
}
}
}
この処理をずっと続けたらどうなるんでしょうね？周期が現れないかやってみます。
添字を見て行列！ってわかったのはうれしい。
void shift_rows(uint8_t *state) {
uint8_t i, k, s, tmp;
for (i = 1; i < 4; i++) {
// shift(1,4)=1; shift(2,4)=2; shift(3,4)=3
// shift(r, 4) = r;
s = 0;
while (s < i) {
tmp = state[Nb*i+0];
for (k = 1; k < Nb; k++) {
state[Nb*i+k-1] = state[Nb*i+k];
}
state[Nb*i+Nb-1] = tmp;
s++;
}
}
}
行列状に平文を並べ替えてシフトするだけ。暗号っぽくないけど何だろう？
void mix_columns(uint8_t *state) {
uint8_t a[] = {0x02, 0x01, 0x01, 0x03}; // a(x) = {02} + {01}x + {01}x2 + {03}x3
uint8_t i, j, col[4], res[4];
for (j = 0; j < Nb; j++) {
for (i = 0; i < 4; i++) {
col[i] = state[Nb*i+j];
}
coef_mult(a, col, res);
for (i = 0; i < 4; i++) {
state[Nb*i+j] = res[i];
}
}
}
固定の行列をかけるだけ。この行列にも意味がある。
void add_round_key(uint8_t *state, uint8_t *w, uint8_t r) {
uint8_t c;
for (c = 0; c < Nb; c++) {
state[Nb*0+c] = state[Nb*0+c]^w[4*Nb*r+4*c+0]; //debug, so it works for Nb !=4
state[Nb*1+c] = state[Nb*1+c]^w[4*Nb*r+4*c+1];
state[Nb*2+c] = state[Nb*2+c]^w[4*Nb*r+4*c+2];
state[Nb*3+c] = state[Nb*3+c]^w[4*Nb*r+4*c+3];
}
}
ビジュネル暗号における鍵の足し算に相当する。鍵がない場合どうなるのだろう？例えば鍵が全部０だったり、ラウンドを回すときに変化しない鍵だったりすると暗号文はどうなるか？
ソースを見ると、このラウンドキーを生成する方法が一番凝っている。
1.sub_bytes
平文$b=(0,0,0,0,0,0,1,1)$とする。
これを有限体$GF(2^8)$の元に対応させると、$\alpha +1$となる。
AESのs-boxは既約多項式を法とする有限体上の計算なので、$b^{-1}=(1,1,1,1,0,1,1,0)$となる。
これを踏まえて、S-boxは以下の式に要約できる。
$$b=Ab^{-1} \oplus c$$
$A,c=(1,1,0,0,0,1,1,0)$は定数である。
Aはちょっと面倒なので、FIPSをご覧ください。
これってアフィン変換のように見えるのですが、本当に非線形なんでしょうか？
固定行列かけてるだけだし、非線形だとすると逆元計算の部分だろうか。
ここで逆元計算（必要なら）は、次のような正引きまたは逆引き配列を参照することで簡単にできる。
つまり、fg[b]=$b^{-1}$とする。gf[$b^{-1}$]=bである。
/*
* Multiplication in GF(2^8)
* http://en.wikipedia.org/wiki/Finite_field_arithmetic
* Irreducible polynomial m(x) = x8 + x4 + x3 + x + 1
*
* NOTE: This function can be easily replaced with a look up table for a speed
* boost, at the expense of an increase in memory size (around 65 KB). See
* the aes.h header file to find the macro definition.
*
*/
uint8_t gmult(uint8_t a, uint8_t b)
{
uint8_t p = 0, i = 0, hbs = 0;
for (i = 0; i < 8; i++)
{
if (b & 1)
{
p ^= a;
}
hbs = a & 0x80; // (1<<(8-1))
a <<= 1;
if (hbs)
a ^= 0x1b; // 0000 0001 0001 1011 ^ (1<<(8))
b >>= 1;
}
return p&0xff;
}
この掛け算関数から１対１対応が計算できる。
static const unsigned short fg[256]={0,1,141,246,203,82,123,209,232,79,41,192,176,225,229,199,116,180,170,75,153,43,96,95,88,63,253,204,255,64,238,178,58,110,90,241,85,77,168,201,193,10,152,21,48,68,162,194,44,69,146,108,243,57,102,66,242,53,32,111,119,187,89,25,29,254,55,103,45,49,245,105,167,100,171,19,84,37,233,9,237,92,5,202,76,36,135,191,24,62,34,240,81,236,97,23,22,94,175,211,73,166,54,67,244,71,145,223,51,147,33,59,121,183,151,133,16,181,186,60,182,112,208,6,161,250,129,130,131,126,127,128,150,115,190,86,155,158,149,217,247,2,185,164,222,106,50,109,216,138,132,114,42,20,159,136,249,220,137,154,251,124,46,195,143,184,101,72,38,200,18,74,206,231,210,98,12,224,31,239,17,117,120,113,165,142,118,61,189,188,134,87,11,40,47,163,218,212,228,15,169,39,83,4,27,252,172,230,122,7,174,99,197,219,226,234,148,139,196,213,157,248,144,107,177,13,214,235,198,14,207,173,8,78,215,227,93,80,30,179,91,35,56,52,104,70,3,140,221,156,125,160,205,26,65,28};
S-Boxがこれから計算できる？
自分の計算法では体になるはずの配列が全部埋まらない。なので、既約多項式の中に体を作れないものが存在する？と思っていたのですがどこにもそんなことは書いていない。何かがおかしい。
既約多項式を法とする代数系では素数を法に持つ有限体と同じように、必ず逆元を持つ。
で、結合法則と単位元の存在、逆元の存在、分配則が成り立つので、これは体である。
一方自分のやっている有限体の計算法では、１つの元を２倍して全部得られるような特別な場合に限られると気が付いた。
今まで自分は有限体というものが正規基底しかないものだと思ってました。
つまり一般の既約多項式はそういう計算にならない。
公開鍵で使うようなでかい体、$GF(2^{256})$も多項式の積で計算できるけど早くない。
昔のパソコンだと一般の多項式基底を計算するのも$GF(2^{32})$までだし、なんかいい方法ないかしら。
跡からわかったけど、2以外を既約多項式に代入して式の値が0になればいいので、
それを使ってゼフ対数が作れるだろうと予想している。
多項式の計算ツール作っておいてよかった。
2.shift_row
左巡回シフト。例えば、
L=
\begin{pmatrix}
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
\end{pmatrix}
平文を行列状に配置して、この行列を書けることで行に対する左巡回シフトを行っている。
ただしシフト行列は行の位置$i$でべき乗$L^i$されている。
これは置換の一種なので線形。
ビジュネル暗号のように展開すると、４つの置換行列になっている。
ここをGF(256)の正則行列にするとどうなるんだろう？
遅くなるだけかもしれないですが、これはランダムに置換した鍵を平文に足すという計算を
m[i] = (m[i] + k[r[i]]) % 256;
と書くだけでいい。これは、鍵ベクトル$k$を置換$r$を使って平文との加法をとったものである。
void round(){
for(int i=0;i<16;i++)
q[i]=p[r[inv_p[i]]];
for(int i=0;i<16;i++)
r[i]=q[i];
}
for(i=0;i<4;i++){
round();
for(j=0;j<4;i++)
m[i][j] = (m[i][j] + k[r[(i*4+j)%16]]) % 256;
}
みたいな。
置換のサイクルの組を$P=(2,3,11)$とすると、例えば$P=(2,3)(1,4,6)(8,10,5,7,9,13,12,15,14,11,0)$のように取れば、この置換の巡回位数は66なので、$P^{66}$という巡回シフトより長い周期が得られる。
3.MixColmns
$0 \leq j \leq Nb$ とし、$j$は列番号とする。
$a(x)=3x^3+x^2+x+2$
$s_j=(s_j*a(x)) \pmod {x^4+1} $
これは以下のような行列変換として書ける。
X=
\begin{pmatrix}
2 & 3 & 1 & 1 \\
1 & 2 & 3 & 1 \\
1 & 1 & 2 & 3 \\
3 & 1 & 1 & 2
\end{pmatrix}
=
\begin{pmatrix}
2 & 3x^3 & x^2 & x \\
x & 2 & 3x^3 & x^2 \\
x^2 & x & 2 & 3x^3 \\
3x^3 & x^2 & x & 2
\end{pmatrix}
つまり線形写像。
どういう多項式になっているかというのも検証してみたい。
この行列をかけることでどのようにデータが混ざっているかわかるといいなあ。
4.Addroundkey
鍵拡大で生成されたベクトルを排他的論理和でストリーム暗号のように足す。
０とか固定値とか、或いは線形合同法にしたら弱点となるか実験したい。
KeyExpansion
ややこしいのでやる気が起きない。
この処理が一番ややこしいのだが何だろう？
実験
本に載っているように、（或いはFIPSにも書いてあるかもしれないが長いので読んでない）S-Boxと鍵拡大以外は全部線形だという事が知られている。（つまり半分くらいはヒル暗号）
しかも鍵拡大以外どこにも秘密鍵が出てこない。
これは一体・・・。
パッと見て気が付くのはshift_rowの単純さである。
ビジュネル暗号の場合、多表式暗号なので文字列ごとに置換群が変わっている。例えば長さ３のキーワードであれば３つの置換を文字ごとに使い分けて、文字の周期ごとに使いまわしている。
AESではもっとシンプルなので、この辺はあまり強度と関係ないのだろうか？
行ごとに異なる多表式の置換を使ってAESを作り変えることもできるだろう。つまりキーワードの長さであるn種類の置換を使って、文字の位置ごとに異なる置換を行う。このように変えたとしても逆変換は可能だ。更に置換は固定している必要はなく、秘密鍵に依存させてもいい。この場合弱い恒等写像のような弱い置換にはならないようにする。
経験的に$\pi_{i+1}=\phi^i\pi^i\phi^{-i}$がいいようだ。縦横４バイトのサイズなので、$4 \times 4$の正方行列だが次元が４だとあまり長い周期にならない。いっそのこと、ここもヒル暗号にしたらどうなるか？
もしかするとAESの関数には微妙なバランスがあって、少しでも変えてしまうと全体のセキュリティが下がってしまうのかもしれない。
それも確かめてみたい。
ざっと見た限りでは、鍵以外は全部固定で公開された変換による１対１対応
ECBモードが危険だといわれるのは、このような固定した写像の下で頻度解析すれば暗号文攻撃ですら危ないからだと分かります。
カギに依存する、つまり鍵がなければ定義できないような写像は拡大鍵だけという事になります。
拡大鍵が仮に０だったとすれば、写像が鍵に依存する部分はないに等しいのであった。
クソいコード
ここで、rは置換、kは鍵である。
暗号化関数
void enc(uint8_t *m, __uint8_t *k)
{
unsigned char n;
for (int i = 0; i < 32; i++){
n = (m[i] + k[r[i]]) % 256;
m[i]=s_box[((n % 16) + (n >> 4) * 16)];
}
}
復号関数
void dec(uint8_t *c, uint8_t *k)
{
unsigned char n;
for (int i = 0; i < 32; i++){
n=inv_s_box[((n % 16) + (n >> 4) * 16)];
c[i] = (256 + n - k[r[i]]) % 256;
}
}
これがビジュネル暗号（S-Box付き）のコードである。
おまけ
クソコード（追加処理付きビジュネル暗号）
一応これでも動いているように見える。
ボヤキ
巷では符号暗号という言い方がされるようになってきたが、英語ではそんな言い方はされていない。
符号に基づく暗号とかいう言い方の方がすっきりすると思うんだけどどうなんだろう。
格子に基づく暗号とか言い回しもきく。
暗号初めてな人がはまりやすいのかなと思う所に有限体がある。
符号やってた関係で最初に素体と拡大体の２つのタイを知っていたのは幸運だと思った。
まさか暗号をやるなんて思いもしなかったから。
2の拡大体の代わりに257とか素体を使ったらどうなるかやってみたくなった。
何だかラウンド鍵を生成する計算が一番複雑なようで、それだけ１つのマスター鍵から安全な暗号化鍵を導出するのは難しいという事だろうか？
この論文イイね。
秘密鍵暗号ってどう設計すればいいの？っていうとき参考になる。
今まで暗号について書籍を通じて大抵は知っていたと思っていたら、まったく知らないことを見つけた。
もう１０年前と今では全く違うのだ。
ヒル暗号をどうやって改良するか。
その指針がこの論文で得られれば幸いである。
で、MISTY実装してみたのですが、IETFドラフトにコードが載ってるので、ほとんど何も考えずにできてしまった。
公開鍵暗号のコード量より、秘密鍵暗号の方が遥かに少ない。
いわば線形代数としての秘密鍵暗号とか。
今考えているのは、DESでいう所のF関数で処理する部分を、左右に分けるのではなくバイトごとに置換しながら複数のF関数を使って並列処理をするという暗号だ。
今やコアが複数載っているのは当たり前なのでちょっとやってみたい。
その場合の代数構造も解き明かしたい。