仕事の関係で暗号化周りについていろいろ勉強していたので、個人的な備忘録としていろいろ資料を書き残そうと思います。
(といってもほとんど外部サイトの引用ばかりなのですが...)
まずAESとは？
Advanced Encryption Standardを略してAESと呼ぶ。
DES暗号の後継としてアメリカ国立標準技術研究所（NIST：National Institute of Standards and Technology）によって制定された新しい暗号化規格らしい。
※AESの前はDES暗号が使われていたようです。こちらはセキュリティリスクがあるとされており現在では使用を推奨されていません。
AES と Rijndael の違いは？
よく AES 暗号で Rijndael という単語が出てくるのですが、この AES と Rijndael は何が違うのか？
AES とは暗号アルゴリズムのことではなく、あくまでアメリカ国立標準技術研究所によって定義された仕様であるようです。
Rijndael(ラインダール) というのはそのAESの暗号化規格で採用された暗号化に使われるアルゴリズムを指します。
Rijndael はブロック暗号であり、固定長のデータを一つの「ブロック」という単位として扱います。
Rijndael では128bit(16byte)、192bit(24byte), 256bit(32byte)の3種類のブロック長を扱いますが、AES ではブロックサイズは128bitで固定されています。
(Rijndaelの192bit, 256bitは互換性がなく、全く別のアルゴリズムとして扱う必要があるようです)
この記事では混同を避けるため以降は AES暗号 で統一します。
ブロック暗号 はRijndael以外にもいろいろあるようですが指定ビットサイズのブロックと指定サイズの暗号鍵で暗号文を生成するという点で共通しています。
AES ではブロックサイズは128bitに固定されますが鍵サイズに関しては
128bit、192bit、256bitの3種類が選べます。
鍵はサイズが大きいほど暗号強度が高くなる傾向にあるようですが、その代わり１回あたりの暗号処理が増えるため大きいデータなどを高速に処理したい場合などには向かないかもしれません。
尚、この記事では暗号鍵は128bitを使用するという前提で進めます。
AES暗号のアルゴリズムで使用されるパラメータ、 関数名、 シンボルなどの定義
実装例などは FIPS 197 に記述されておりこれを参考にすると良さそうですが、ドキュメントの説明での便宜上の各種パラメータ・関数の名称が定義されており、まずこの定義の内容を理解する必要があります。
(他のAES暗号を扱った記事などでも基本的にこれらの名称を使用している事が多いようです)
State
暗号化処理を行なっているブロック部分のことを State と命名します。
例えばある16バイトのデータを入力(input)として暗号化した結果を出力(output)する Encrypt(byte[] input, byte[] output) という関数があったとすると、以下のような流れになります。
input
↓
↓ State にinputをコピー
↓
State ← Stateに対して暗号処理を行う
↓
↓ 暗号結果をoutputにコピー
↓
output
Round
AES 暗号に限らず多くのブロック暗号では同じ暗号処理を何回か繰り返すように実装されており、この１回の暗号処理の単位を ラウンド と呼びます。
AESでは鍵の長さによってラウンド回数が異なり、128bit長の場合は10ラウンド、 192bit の場合は12ラウンド、 256bit の場合は14ラウンドの暗号処理を行います。
Round Key
実は指定された鍵をベースに Round Key (日本語サイトだとラウンド鍵と表記されることもある)
と呼ばれるラウンド回数分だけの鍵が生成されており、各ラウンドでは全てに対して異なる鍵を使用します。
128bitの場合は10ラウンド暗号処理を行うので10回分のラウンド鍵が生成されます。
最初の1ラウンド目は指定された鍵がそのまま使われます。
(ラウンド鍵生成の実装に関してはまた別の記事で書く予定です)
Word
16バイトのデータブロックを4byteデータ型(int, uintなど)に変換して扱っており、
この単位は Word と呼ばれています。
このWordという表現は主にStateを表すときや、ラウンド鍵の生成(後述する Key Expansion)で使用されます。
RotWord()
この関数は主にラウンド鍵の生成処理で使用されます
一つ上で説明したwordの内容を左方向に循環シフトします。
コードにすると下記のような感じ
private static uint RotWord(uint r)
{
return (r << 8) | ((r >> 24) & 0xFF);
}
Nb
Stateの列数(Word単位)
前述した通り、AES暗号は1ブロック16バイト固定なのでWord4つ分として定数:4が定義されます。
(Nbは Number of blockの略？)
Nk
暗号鍵のWord数
鍵の長さが128bit なら 4
192bit なら 6
256bit なら 8
Nr
ラウンド回数
鍵の長さが128bit なら 10
192bit なら 12
256bit なら 14
S-box
State の各データを変換する際に使用する置換テーブル
S-Boxの要素は ガロア体 $GF(2^8)$ 上の多項式として解釈された入力値から
既約多項式 $x8 + x4 + x3 + x + 1$を法とした乗法で逆数を求め、その逆数を以下の式でアフィン変換します。
\begin{bmatrix}
s_0 \\
s_1 \\
s_2 \\
s_3 \\
s_4 \\
s_5 \\
s_6 \\
s_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}
b_0 \\
b_1 \\
b_2 \\
b_3 \\
b_4 \\
b_5 \\
b_6 \\
b_7 \\
\end{bmatrix}
+
\begin{bmatrix}
1 \\
1 \\
0 \\
0 \\
0 \\
1 \\
1 \\
0 \\
\end{bmatrix}
このアフィン変換は、バイトをベクトルとして複数回回転させたものの和であり、加算はXOR演算となります。
行列の0部分に該当する要素は演算結果が0になるので、
コードとして表現すると
// bのi番目の計算式
s[i] = b[i] ^ b[(i + 4) % 8] ^ b[(i + 5) % 8] ^ b[(i + 6) % 8] ^ b[(i + 7) % 8] + c[i]
これをfor(i=0; i<8; ++i) として8回回転させると以下のようになります。
s[0] = b[0] ^ b[(0+4)%8] ^ b[(0+5)%8] ^ b[(0+6)%8] ^ b[(0+7)%8] ^ c[0]
s[1] = b[1] ^ b[(1+4)%8] ^ b[(1+5)%8] ^ b[(1+6)%8] ^ b[(1+7)%8] ^ c[1]
s[2] = b[2] ^ b[(2+4)%8] ^ b[(2+5)%8] ^ b[(2+6)%8] ^ b[(2+7)%8] ^ c[2]
s[3] = b[3] ^ b[(3+4)%8] ^ b[(3+5)%8] ^ b[(3+6)%8] ^ b[(3+7)%8] ^ c[3]
s[4] = b[4] ^ b[(4+4)%8] ^ b[(4+5)%8] ^ b[(4+6)%8] ^ b[(4+7)%8] ^ c[4]
s[5] = b[5] ^ b[(5+4)%8] ^ b[(5+5)%8] ^ b[(5+6)%8] ^ b[(5+7)%8] ^ c[5]
s[6] = b[6] ^ b[(6+4)%8] ^ b[(6+5)%8] ^ b[(6+6)%8] ^ b[(6+7)%8] ^ c[6]
s[7] = b[7] ^ b[(7+4)%8] ^ b[(7+5)%8] ^ b[(7+6)%8] ^ b[(7+7)%8] ^ c[7]
//
//↓
//
s[0] = b[0] ^ b[4] ^ b[5] ^ b[6] ^ b[7] ^ c[0]
s[1] = b[1] ^ b[5] ^ b[6] ^ b[7] ^ b[0] ^ c[1]
s[2] = b[2] ^ b[6] ^ b[7] ^ b[0] ^ b[1] ^ c[2]
s[3] = b[3] ^ b[7] ^ b[0] ^ b[1] ^ b[2] ^ c[3]
s[4] = b[4] ^ b[0] ^ b[1] ^ b[2] ^ b[3] ^ c[4]
s[5] = b[5] ^ b[1] ^ b[2] ^ b[3] ^ b[4] ^ c[5]
s[6] = b[6] ^ b[2] ^ b[3] ^ b[4] ^ b[5] ^ c[6]
s[7] = b[7] ^ b[3] ^ b[4] ^ b[5] ^ b[6] ^ c[7]
//
// 並べ替える
s[0] = b[0] ^ b[4] ^ b[5] ^ b[6] ^ b[7] ^ c[0]
s[1] = b[0] ^ b[1] ^ b[5] ^ b[6] ^ b[7] ^ c[1]
s[2] = b[0] ^ b[1] ^ b[2] ^ b[6] ^ b[7] ^ c[2]
s[3] = b[0] ^ b[1] ^ b[2] ^ b[3] ^ b[7] ^ c[3]
s[4] = b[0] ^ b[1] ^ b[2] ^ b[3] ^ b[4] ^ c[4]
s[5] = b[1] ^ b[2] ^ b[3] ^ b[4] ^ b[5] ^ c[5]
s[6] = b[2] ^ b[3] ^ b[4] ^ b[5] ^ b[6] ^ c[6]
s[7] = b[3] ^ b[4] ^ b[5] ^ b[6] ^ b[7] ^ c[7]
SubBytes()
各 State の持つ1バイト値に対応したS-Boxのテーブルに置換します。
SubWord()
各Wordの持つ4バイト値をまとめてS-Boxのテーブルに置換します。