前回の続き
平日は仕事で忙しくなかなかこういった情報をまとめる時間がないのでお盆休みを活用してまとめていきたいと思います。
今回は前回軽く触れた S-Box についてもう少し深掘りしたいと思います。
S-BoxはStateの各バイトデータを置き換える置換テーブルとなります。
Rijndael S-box のWikiを見ると
① 8ビットの入力cを8ビットのsを出力する写像 S(c)
② 入力と出力はともにGF(2)上の多項式として解釈される
③ GF(28) = GF(2)[x]/(x8+x4+x3+x+1)における乗法逆数に写像される
まず、このGF(2)とはなんぞや？ というところから書いていこうと思います。
(といってもこれは調べれば沢山情報が出てきますので引用元リンクなども添付しようと思います)
まずこのGFというのは数学の世界では 有限体 と呼ばれます。
暗号理論ではガロア体と呼ぶこともあります
有限体(ガロア体)とは
暗号化の世界ではガロア体、ガロア域などと呼ばれることが多く、 Galois Field からGFと呼ばれます。
ある素数 p で除算した余りの値で構成される体 を有限体と呼びます。
体 というのは代数学で使われる群・環・体の体の事を指し、ざっくり言えば四則演算ができる有限個の元を持つ集合といった感じになります。
群の定義
① ある演算○に対して ○○○○(a○b)○c=a○(b○c)が成立する(結合法則の存在)
② 集合 G のどの元 g を取っても
○○g○e=e○g=gとなるような元 e が存在する。(単位元の存在)
③ 任意の a∈G に対して ○a○b=e を満たす b が存在する。(逆元の存在)
実数の集合Rの加法においては0、乗法は1が単位元となります
逆元は掛け算であれば 3×13=1や 2×12=1 などの分数が逆元になります。
足し算であれば 3+(−3)=0 などのマイナスの値が逆元になります。
また、これに加えて
・ $a ○ b = b ○ a$ が成立する(交換法則の存在)
を満たす場合、 可換群(アーベル群) と呼ばれます。
環の定義
環 は加法に関して可換群であり
・乗法に関して結合法則が成立する
・加法の単位元と異なる値で乗法の単位元が存在する
・$a(b + c) = ab + ac$が成立する(分配法則の存在)
また、これに加えて交換法則が成り立つ場合($ab = ba$が成り立つ場合)
可換環 と呼ばれます。
整数全体の集合 $\mathbb{Z} $ は可換環で、整数環と呼びます。
また、環の乗法において0以外の元と掛け算を行い結果が0になるような元のことを零因子と呼び、この零因子が0しか存在しない可換環を 整域 と呼びます。
この整域を $R$ としたとき、 $R$ の元を係数とした $x$ を変数とする(※1) 多項式の集合を多項式環と呼び、$R[x]$として表します。
$R[x] = \{a_0 + a_1x + a_2x^2 + a_3x^3 + ... a_nx^n | a_0,a_1,...a_n \in R \}$
$a_i$ : 係数
この多項式環も可換環です。
*1) $x$ は不定元とも呼ばれます。
参考: 環の定義とその具体例
体の定義
体は可換環であり、なおかつ乗法に関して逆元が存在する場合(ただし0は除外する)
その集合は体と呼ばれます。
「乗法に関して逆元が存在する」とはすなわち「割り算ができる」という意味でもあります。
実際、$1 ÷ 3$ のような割り算は $1 × 3^{-1}$ つまり $1 × \frac{1}{3}$ と等価です。
以上のことから体は四則演算ができる集合であると言えます。
有限体はこれらの条件を全て満たした要素数が有限個の集合です。
要素数を 位数 と呼び位数を $q$ で表して $F_q$ 、 $GF(q)$ と表現します。
有限体は位数が $q = p^m$ のときのみ存在します。
$p$ : 素数
$m$ : 正の整数
$m$ が2以上である場合、拡大体などと呼ばれます。
AES暗号をはじめとしたコンピュータ関係では $GF(2)$ がよく使われます。
$GF(2)$ では2で割った余りの値と０から成る体であるため、元は $\{0, 1\}$ の二つとなります。
加法
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
乗法
| $\times$ | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
0+1=1, 1+0=1, 0+0=0, 1+1=0 なので $GF(2)$ の世界における加法はプログラミングにおけるXORと同じ意味になります。
AES暗号ではこの $GF(2)$ の位数を $2^8$ まで拡大した $GF(2^8)$ を使います。
$GF(2^8)$ は {0, 1} を係数として持った $x^i$ を元とする 最大次数を7とした多項式の剰余環です。
この体の乗法では 既約多項式 (※1)を法とした剰余計算をします。
この既約多項式は選び方次第で $2^8 - 1 $ 通りの重複しない元を生成することが出来ます。(元の周期が$2^{8}-1となる$)
そのような既約多項式を 原始多項式 と呼びます。
原始多項式は既約多項式ですが、既約多項式は原始多項式ではないため注意。
また、原始多項式の解 a は常に原始元(全ての元をべき表現で生成できる)ですが、
原始多項式 でなくとも 既約多項式 は常に原始元を含みます。
例えば既約多項式 $x^2+x+1$ を法とした $GF(2^2)$ を考えた場合、
この有限体の元は以下のようになります。
| $GF(2^2)$ |
|---|
| 0 |
| 1 ($x^0$) |
| $x$ ($x^1$) |
| $x + 1$ ($x^2 = x + 1$) |
$x^2+x^1+1$ の根、つまり方程式の解が0となるような値 $a$ が存在することを仮定します。
(この値 $a$ は実数ではない、虚数のような台数的構造を持つ抽象的なオブジェクトです)
$a$ を代入し、以下のような方程式を作ります
$a^2+a^1+1 = 0$
この根 $a$ を $GF(2)$ に追加します。
つまり $\{0, 1, a\}$
拡大体 $GF(2^m)$ は m次既約多項式とその根 $a$ のべき表現 $ \{a^0, a^1, a^2, ... a^{2^{m}-2} \}$ と0から構成されます。
なので $GF(2^2) = \{0, a^0(=1), a^1, a^2\}$
$a^2+a^1+1 = 0$ なので $a^2 = -a^1 - 1$ とも出来ますが、
GF(2) は1+1=0であり 1=-1でもあり、つまり-1=1であるため負の数は存在しません。
なので $a^2 = a+1$ になります。
$a^0, a^1$ と続き $a^2$ になると上記の式で除算されるので $a^2$ の値は $a+1$ となります。
乗法
| $\times$ | 0 | 1 | $a$ | $a+1$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | $a$ | $a+1$ |
| $a$ | 0 | $a$ | $a + 1$ | 1 |
| $a + 1$ | 0 | $a + 1$ | 1 | $a$ |
加法
| $+$ | 0 | 1 | $a$ | $a+1$ |
|---|---|---|---|---|
| 0 | 0 | 1 | $a$ | $a+1$ |
| 1 | 1 | 0 | $a+1$ | $a$ |
| $a$ | $a$ | $a+1$ | 0 | 1 |
| $a + 1$ | $a+1$ | $a$ | 1 | 0 |
S-Box は8ビットの入力を $GF(2^8)$ の多項式に解釈します。
また、多項式はベクトル空間としての性質を持つので、{0,1}を係数とした 8 次元のベクトルとして表現することができます。
2次元のベクトルが(x,y)
3次元のベクトルが(x,y,z)
と表現するので
8次元の場合は(b0,b1,b2,b3,b4,b5,b6,b7)
例えば以下のような感じです
| ベクトル表現 | 多項式表現 | |
|---|---|---|
| 0x01 | (00000001) | $x^0$(=1) |
| 0x02 | (00000010) | $x$ |
| 0x03 | (00000011) | $x + 1$ |
| 0x04 | (00000100) | $x^2$ |
| 0x05 | (00000101) | $x^2 + 1$ |
| 0x06 | (00000110) | $x^2 + x$ |
| 0x07 | (00000111) | $x^2 + x + 1$ |
| 0x08 | (00001000) | $x^3$ |
| 0x09 | (00001001) | $x^3 + 1$ |
| 0x0A | (00001010) | $x^3 + x$ |
| 0x0B | (00001011) | $x^3 + x + 1$ |
| 0x0C | (00001100) | $x^3 + x^2$ |
| 0x0D | (00001101) | $x^3 + x^2 + 1$ |
| 0x0E | (00001110) | $x^3 + x^2 + x$ |
| 0x0F | (00001111) | $x^3 + x^2 + x + 1$ |
| 0x10 | (00010000) | $x^4$ |
その後、既約多項式 $x^8 + x^4 + x^3 + x + 1$(0x1B) を使った乗法逆元に写像します。
$GF(2^8)$ の乗算はそのまま多項式同士を掛け算して求めます。
例えば $0x2 \times 0x2$ とした場合、多項式表現に直すと $x \times x = x^2$
なので0x4になります。
0x1は多項式上だと要するに $x^0$ なので、 $x^2 \times 1$ は $x^2$ です。
例) 0xc6 × 0xd4 $(x^7 + x^6 + x^2 + x) \times (x^7 + x^6 + x^4 + x^2)$ の場合
$x^7 + x^6 + x^2 + x$
×)$x^7 + x^6 + x^4 + x^2$
= $x^7(x^7 + x^6 + x^2 + x)$
$+ x^6(x^7 + x^6 + x^2 + x)$
$+ x^4(x^7 + x^6 + x^2 + x)$
$+ x^2(x^7 + x^6 + x^2 + x)$
これはつまり
① ($x \times x \times x \times x \times x \times x \times x \times x$) $\times (x^7 + x^6 + x^2 + x)$ +
② ($x \times x \times x \times x \times x \times x \times x$) $\times (x^7 + x^6 + x^2 + x)$ +
③ ($x \times x \times x \times x \times x$) $\times (x^7 + x^6 + x^2 + x)$ +
④ ($x \times x$) $\times (x^7 + x^6 + x^2 + x)$
とも表せます。
一回xを掛け算する度に右辺の次数は１繰り上がります。
次数が8になったら既約多項式を使って除算します。
このことから、プログラミング的には掛け算は左辺の値を右辺の各ビット位置だけ左シフトし、それらの値をXOR演算して合算すれば積を求めることができます。
上記の場合は①、②、③、④のそれぞれ左辺のxの個数だけ右辺を左にビットシフトします。
$x^8$になったら(0x100になったら)既約多項式(0x1B)でXORします。
最後に①、②、③、④全てXORすればそれが積になります。
一度の呼び出しにつき１回だけ左に１ビットシフトさせる演算を xtime という関数として定義します
byte xtime(byte b)
{
// 7ビット目が1なら既約多項式(0x1b)で除算する
return (byte)((b << 1) ^ ((b & 0x80) != 0 ? 0x1b : 0x00));
}
byte product = 0;
byte a = 0xc6; // [11000110]; x^7 + x^6 + x^2 + x
byte b = 0xd4; // [11010100]; ×) x^7 + x^6 + x^4 + x^2
byte temp = a;
for (int i = 0; i < 2; ++i)
{
temp = xtime(temp);
}
product ^= temp;
temp = a;
for (int i = 0; i < 4; ++i)
{
temp = xtime(temp);
}
product ^= temp;
temp = a;
for (int i = 0; i < 6; ++i)
{
temp = xtime(temp);
}
product ^= temp;
temp = a;
for (int i = 0; i < 7; ++i)
{
temp = xtime(temp);
}
product ^= temp;
Debug.Log($"product:{product:x2}"); // 0x66 [01100110]
これを一つの関数にまとめると以下のような感じになります。
static byte Dot(int a, int b)
{
int Shift(int e)
{
int shifted = (e << 1) ^ (((e & 0x80) != 0) ? 0x1B : 0x00);
return shifted;
}
int mask = 0x1;
int product = 0;
while (mask != 0)
{
if ((b & mask) != 0)
{
product ^= a;
}
a = Shift(a);
mask <<= 1;
}
return (byte)product;
}
参考:
共通鍵暗号AES用SubBytes変換回路 設計仕様書
※1) 多項式の世界における素数のようなもので1次以上の多項式で因数分解できない多項式を既約多項式と呼びます。
参考:
復号化の検証 ハミング符号の符号化
通信路符号化法 ガロア体とBCH符号
GF(2^8) の乗法逆数を求める
S-Boxの値を計算するには8ビット入力値を $GF(2^8)$ の多項式として解釈した上で、その多項式の乗法逆元を求める必要があります。
フェルマーの小定理
$p$ が素数で $a$ が $p$ の倍数でない整数であるとき
$a^{p-1} ≡ 1$
有限体は素数pで割った余りの集合であるため、全ての元はq-1乗してからqで割ると必ず余りは1となります。
例えば素数pを5と定義して $GF(5)$ とすると、元は {0, 1, 2, 3, 4} となります。
| $a^2$ | $a^3$ | $a^4$ | |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 4 | 3 | 1 |
| 3 | 4 | 2 | 1 |
| 4 | 1 | 4 | 1 |
$p=7$と定義して $GF(7)$ とした場合は {0, 1, 2, 3, 4, 5, 6} が元です。
| $a^2$ | $a^3$ | $a^4$ | $a^5$ | $a^6$ | |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 4 | 1 | 2 | 4 | 1 |
| 3 | 2 | 6 | 4 | 5 | 1 |
| 4 | 2 | 1 | 4 | 2 | 1 |
環の定義から、乗法逆元は$a \times a^{-1} = 1$ となる値なので
$GF(p)$ の場合は元 $a$ に対して $a^{p-2}$ が逆元となります。
$GF(7)$ なら $a^5$ が逆元です。
これはフェルマーの小定理からもわかりますが、群・環・体の構造から見ても有限体 $GF(p)$ は0を除外すれば乗法において群の構造になります。
この位数p-1の乗法群は常に原始根が含まれることから、位数p-1の巡回群の構造を持ちます。
(有限体の乗法群は常に巡回群である)
参考: 有限体の基本定理
有限体 ― 塩田研一覚書帳 ―
$GF(2^8)$ の場合でも有限体であることから同様に成立し、位数 256 - 1 の巡回群になります。
そのため、$a^{254}$ が逆元になります。
そこである値vをm乗した値を返すという関数を用意してみます。
// 引数vをm乗した値を返す
public int Pow(int v, int m)
{
int times = v;
for (int i = 0; i < m - 1; ++i)
{
v = Dot(v, times);
}
return v;
}
以下のようなコードを書くと逆数を出力できます。
StringBuilder sb = new();
for (int y = 0; y <= 0xF; ++y)
{
for (int x = 0; x <= 0xF; ++x)
{
int inverse = Pow((y << 4) | x, 254);
sb.Append($"{inverse:x2},");
}
sb.AppendLine();
}
Debug.Log(sb.ToString());
/* 出力結果
00,01,8d,f6,cb,52,7b,d1,e8,4f,29,c0,b0,e1,e5,c7,
74,b4,aa,4b,99,2b,60,5f,58,3f,fd,cc,ff,40,ee,b2,
3a,6e,5a,f1,55,4d,a8,c9,c1,0a,98,15,30,44,a2,c2,
2c,45,92,6c,f3,39,66,42,f2,35,20,6f,77,bb,59,19,
1d,fe,37,67,2d,31,f5,69,a7,64,ab,13,54,25,e9,09,
ed,5c,05,ca,4c,24,87,bf,18,3e,22,f0,51,ec,61,17,
16,5e,af,d3,49,a6,36,43,f4,47,91,df,33,93,21,3b,
79,b7,97,85,10,b5,ba,3c,b6,70,d0,06,a1,fa,81,82,
83,7e,7f,80,96,73,be,56,9b,9e,95,d9,f7,02,b9,a4,
de,6a,32,6d,d8,8a,84,72,2a,14,9f,88,f9,dc,89,9a,
fb,7c,2e,c3,8f,b8,65,48,26,c8,12,4a,ce,e7,d2,62,
0c,e0,1f,ef,11,75,78,71,a5,8e,76,3d,bd,bc,86,57,
0b,28,2f,a3,da,d4,e4,0f,a9,27,53,04,1b,fc,ac,e6,
7a,07,ae,63,c5,db,e2,ea,94,8b,c4,d5,9d,f8,90,6b,
b1,0d,d6,eb,c6,0e,cf,ad,08,4e,d7,e3,5d,50,1e,b3,
5b,23,38,34,68,46,03,8c,dd,9c,7d,a0,cd,1a,41,1c,
*/
この出力結果に前回の記事で書いた書いたアフィン変換を行ったら、出力結果がWikiに書かれているS-Boxと同じになりました。
byte AffineTransform(int b)
{
Func<int, int, int> _ = (int v, int i) => { return (v >> i) & 1; };
const int c = 0x63; // 01100011
int s0 = _(b, 0) ^ _(b, 4) ^ _(b, 5) ^ _(b, 6) ^ _(b, 7) ^ _(c, 0);
int s1 = _(b, 0) ^ _(b, 1) ^ _(b, 5) ^ _(b, 6) ^ _(b, 7) ^ _(c, 1);
int s2 = _(b, 0) ^ _(b, 1) ^ _(b, 2) ^ _(b, 6) ^ _(b, 7) ^ _(c, 2);
int s3 = _(b, 0) ^ _(b, 1) ^ _(b, 2) ^ _(b, 3) ^ _(b, 7) ^ _(c, 3);
int s4 = _(b, 0) ^ _(b, 1) ^ _(b, 2) ^ _(b, 3) ^ _(b, 4) ^ _(c, 4);
int s5 = _(b, 1) ^ _(b, 2) ^ _(b, 3) ^ _(b, 4) ^ _(b, 5) ^ _(c, 5);
int s6 = _(b, 2) ^ _(b, 3) ^ _(b, 4) ^ _(b, 5) ^ _(b, 6) ^ _(c, 6);
int s7 = _(b, 3) ^ _(b, 4) ^ _(b, 5) ^ _(b, 6) ^ _(b, 7) ^ _(c, 7);
return (byte)(s0 | s1 << 1 | s2 << 2 | s3 << 3 | s4 << 4 | s5 << 5 | s6 << 6 | s7 << 7);
}
for (int y = 0; y <= 0xF; ++y)
{
for (int x = 0; x <= 0xF; ++x)
{
int inverse = Pow((y << 4) | x, 254);
byte t = AffineTransform(inverse);
sb.Append($"{t:x2},");
}
sb.AppendLine();
}
/*
63,7c,77,7b,f2,6b,6f,c5,30,01,67,2b,fe,d7,ab,76,
ca,82,c9,7d,fa,59,47,f0,ad,d4,a2,af,9c,a4,72,c0,
b7,fd,93,26,36,3f,f7,cc,34,a5,e5,f1,71,d8,31,15,
04,c7,23,c3,18,96,05,9a,07,12,80,e2,eb,27,b2,75,
09,83,2c,1a,1b,6e,5a,a0,52,3b,d6,b3,29,e3,2f,84,
53,d1,00,ed,20,fc,b1,5b,6a,cb,be,39,4a,4c,58,cf,
d0,ef,aa,fb,43,4d,33,85,45,f9,02,7f,50,3c,9f,a8,
51,a3,40,8f,92,9d,38,f5,bc,b6,da,21,10,ff,f3,d2,
cd,0c,13,ec,5f,97,44,17,c4,a7,7e,3d,64,5d,19,73,
60,81,4f,dc,22,2a,90,88,46,ee,b8,14,de,5e,0b,db,
e0,32,3a,0a,49,06,24,5c,c2,d3,ac,62,91,95,e4,79,
e7,c8,37,6d,8d,d5,4e,a9,6c,56,f4,ea,65,7a,ae,08,
ba,78,25,2e,1c,a6,b4,c6,e8,dd,74,1f,4b,bd,8b,8a,
70,3e,b5,66,48,03,f6,0e,61,35,57,b9,86,c1,1d,9e,
e1,f8,98,11,69,d9,8e,94,9b,1e,87,e9,ce,55,28,df,
8c,a1,89,0d,bf,e6,42,68,41,99,2d,0f,b0,54,bb,16,
*/
参考:
原始根
原始根の定義と具体例
有限体の構造
補足
-
「閉じている」というのは代数学ではよく出てくる単語なのですが、
これは「ある集合$S$の任意の 元(※2) $a$ と $b$ で２項演算を行う、その演算結果 $c$ が必ず集合 $S$ の元である場合、集合 S はその任意の演算●に対して閉じている」 などと表現されます。 -
ある集合 $S$ に含まれる要素 $s$ の事を 元 と呼び、 $s \in S$ と表現します。
含まない場合は $s \notin S$ と表現します。
参考:
ガロア体の簡単な説明
いまさら聞けない？群と環と体の関係とは
群の定義といろいろな具体例
代数学の基本 群・環・体の定義と具体例をゼロから解説