Written on August 5, 2021

AESを実装しよう(1)

共通鍵暗号アルゴリズムの1つであるAESは，無線LAN通信(Wi-Fi)の暗号化をはじめとして身の回りの様々な場所で使われています．それがどのように動作しているのかの学習として，実装しながら理解を深めていこうと思います．

AESについて

AESはその公募を勝ち抜いたRijndaelと呼ばれるアルゴリズムが元になっています．Rijndaelではブロック長，鍵長がいくつかから選べるようになっていましたが，AESとして採用されるにあたりデータ長が128bit，鍵長が128, 192, 256bitの中から選択するようになりました．

AESの構成部品は大きく分けて暗号化部で用いられる4つの関数(SubBytes, ShiftRows, MixColumns, AddRoundKey)と，鍵拡張関数(KeyExpansion)があり，これらを複数ラウンド適用することにより暗号文を得ます．

またラウンド数は鍵長によって決められています．

128bit鍵 -> 10ラウンド
192bit鍵 -> 12ラウンド
256bit鍵 -> 14ラウンド

今回は鍵長128bitのAES(AES-128)をD言語を用いて実装していきます．

暗号化概要

今回は128bit鍵としましたので，ラウンド数は10ラウンドとなります．全体としての構造は下図のようになっています．最終ラウンドだけMixColumnsが省かれていることに注意してください．

AES概要

コードに起こしてみます．

ubyte[16] text = { ... };
ubyte[16] key = { ... };

void encryption(){
  addRoundKey();
  
  foreach(i; 0 .. 9){
    subBytes();
    shiftRows();
    mixColumns();
    keyExpansion(i);
   addRoundKey();
  }
  
    subBytes();
    shiftRows();
    keyExpansion(9);
   addRoundKey();
}

まだむずかしいところはなさそうです．

SubBytes

各バイトに対してS-boxと呼ばれる非線形な置換を施します．そのS-boxは以下のように2段階の操作を行って求められます．

まず1つ目の操作として，入力に対して，有限体\(GF(2^8)\)上での逆元(ただし既約多項式は\(x^8+x^4+x^3+x+1\))を求めます．

ここで\(GF(2^n)\)の要素というのは，2進数表現を多項式の係数に対応させた，係数が0 or 1のn次多項式の要素として考えることができます．ただし演算をするにあたって，\(n\)次の既約多項式\(f(x)\)を選び，\(\mod f(x)\)として進めていきます．係数は\(\mod 2\)で演算します．

例として\(GF(2^3)\)上で\(3 \times 6\)を計算してみましょう．既約多項式\(f(x)=x^3+x+1\)とします．まず3と6を多項式として表現すると，\(3 \rightarrow x+1,\ 6 \rightarrow x^2+x\)となります．これらをかけ合わせます． \begin{align} (x+1) \times (x^2+x) &= x^3 + x \mbox{ (係数はmod 2で演算します．)} \\
&= 1 \mbox{ (mod \(f(x)\)で演算します．係数にも注意です．)} \end{align} よって\(3 \times 6 = 1\)となりました．加えて\(GF(2^3)\)上での3の逆元が6，6の逆元が3であることも分かりました．

これを見るに掛け算表を作ってしまえば逆元を求められそうです．AESでは\(GF(2^8)\)を用いるので，掛け算表の要素はおよそ6万5千個と現実的な範囲ですね．

そして2つ目の操作として，各ビットに対して以下の行列変換を施します．

\begin{align} \begin{bmatrix} y_0\\ y_1\\ y_2\\ y_3\\ y_4\\ y_5\\ y_6\\ y_7 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
\end{bmatrix} \begin{bmatrix} x_0\\ x_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6\\ x_7 \end{bmatrix} \oplus \begin{bmatrix} 1\\ 1\\ 0\\ 0\\ 0\\ 1\\ 1\\ 0 \end{bmatrix} \end{align}

これらを毎ラウンド実行しても良いのですがなかなか大変そうな処理です．そこで前もってS-boxの変換表を作成しておき，SubBytesを実行する際にはそれを用いることにしてしまいます．

その2に続きます．

← Top