2017年05月15日

世界一強い暗号と言われるAES(Rijndael)を数学的に解説してみる

応援クリックを1日1回宜しくお願いいたします。



AES(Advanced Encryption Standard、Rijndael、ラインドール)の概説を試みます。
※)本記事が詳しくなって解説と称せるように点を減らしていきたいです。


暗号化アルゴリズム概要
AESの暗号化アルゴリズムは下記の通りです。
AddRoundKey
-----Nr+1回の繰り返し-----
SubBytes
ShiftRows
MixColumns
AddRoundKey
--------------------
SubBytes
ShiftRows
AddRoundKey
※)NrはAES-128の場合、10(回)です。
ここで、4種類の演算が登場しています。
1. SubBytes
2. ShiftRows
3. MixColumns
4. AddRoundKey
復号化はこの逆順で、それぞれの逆演算を行います。
これらの演算は本家のPDFにも勿論説明がありますが、できるだけ数学チックに説明したいと思います。
SubBytes
S-boxという変換表(行列)に基づいて、数字を変換します。
S-boxの使い方(過保護気味):
1. 変換前の数字を00〜ffの2桁16進数で表します。これを$X$とします。
2. $X$の左側の桁がS-boxの行に対応しています。例えば、a8の場合、S-boxの上から10(=a)行目を見つけます。
3. $X$の右側の桁がS-boxの列に対応しています。例えば、a8の場合、S-boxの左から8列目を見つけます。
4. 該当箇所の2桁16進数の数字が変換後の16進数の数となります。
※)上記の変換を行えば終了です。このS-box自体が群論から計算された"結果"なので、理論の元の所を解説できればと思っていたりします。
S-boxはこちら。(JavaScriptで書いています)
引数の1つ目が行、2つ目が列です。10〜15がa〜fです。
80はcdに変換されます。



4$\times$4の行列の各行を、横向きにずらしていく演算です。
1行目は変化なし。
2行目は1つ左にずらします。2行1列の要素は2行4列へ移動します。
3行目は2つ左にずらします。3行1列の要素は3行3列へ移動し、3行2列の要素は3行4列へ移動します。
4行目は3つ左にずらします。4行1列の要素は4行2列へ移動し、4行2列の要素は4行3列へ移動し、4行3列の要素は4行4列へ移動します。(=1つ右にずらします)
表の形で描くと、下記のようになります。
変換前
$a_{11}$$a_{12}$$a_{13}$$a_{14}$
$a_{21}$$a_{22}$$a_{23}$$a_{24}$
$a_{31}$$a_{32}$$a_{33}$$a_{34}$
$a_{41}$$a_{42}$$a_{43}$$a_{44}$


変換後
$a_{11}$$a_{12}$$a_{13}$$a_{14}$
$a_{22}$$a_{23}$$a_{24}$$a_{21}$
$a_{33}$$a_{34}$$a_{31}$$a_{32}$
$a_{44}$$a_{41}$$a_{42}$$a_{43}$
4行目は左に3つずらす、というのは128bitでのことであって、256bitでは異なります。
MixColumns
ある4$\times$4の行列との積をとったものです。
ただし、行列との積において通常の掛け算の代わりにRijndael finite field multiplicationを用い、通常の足し算の代わりに排他的論理和を用いた演算です。
ある$4\times4$の行列はこちらです。
\[
\left(\begin{array}{cccc}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{array}\right)
\]
通常の掛け算の代わりにRijndael finite field multiplicationを用いるというのは、数を2進数で表したときの各ビットを冪とした$x$の関数を考え、その積において排他的論理和を用いた後、$x^8+x^4+x^3+x+1$で割った余りの各冪をビットとした2進数を16進数に変換した数字をとる、という意味です。←
普通に説明すると、例えば16進数の数$0e$と$03$のRijndael finite field multiplicationは
\begin{eqnarray*}
\left\{0e\right\}\bullet\left\{03\right\}&=&\left\{00001110\right\}\bullet\left\{00000011\right\}\\
&=&\left(x^3+x^2+x\right)\left(x+1\right)\ \text{modulo}\ \left(x^8+x^4+x^3+x+1\right)\\
&=&\left(x^4+x^3+x^2+x^3+x^2+x\right)\ \text{modulo}\ \left(x^8+x^4+x^3+x+1\right)\\
&=&x^4+x\\
&=&\left\{00010010\right\}\\
&=&\left\{12\right\}
\end{eqnarray*}
となります。
その他の計算例はこちら。(このPDFでは逆行列との積をとって単位行列となるという結果を得ています。)
通常の足し算の代わりに排他的論理和を用いるというのは、その通りです。
上記のRijndael finite field multiplicationでも用いられています。
例えば、16進数の数$12$と$16$と$0d$と$09$の排他的論理和をとると、
\begin{eqnarray*}
&&\left\{12\right\}\oplus\left\{16\right\}\oplus\left\{0d\right\}\oplus\left\{09\right\}\\
&=&\left\{00010010\right\}\oplus\left\{00010110\right\}\oplus\left\{00001101\right\}\oplus\left\{00001001\right\}\\
&=&\left\{00000000\right\}\\
&=&\left\{00\right\}
\end{eqnarray*}
となります。
排他的論理和を用いることの証拠となる箇所は2.1.1 Additionです。
※)ソースコードでは、$03$との積が$x+1$との積であって左シフトと1倍の和で表せる、など工夫ができます。
AddRoundKey
さてラストです。
Key ScheduleというあらかじめCipher Keyから生成しておいた行列との排他的論理和を行う演算です。
Key Scheduleの作成方法が擬似コードの形で述べられています。
※)この擬似コードの分かりやすい説明も出来ればと思います。


タグ:暗号 IT 数学 web

posted by Line Segment at 18:00 | Comment(0) | TrackBack(0) | 日記 | このブログの読者になる | 更新情報をチェックする