AES暗号(Rijndael)について教えてください。


SubBytes,ShiftRows,MixColumns,AddRoundKeyの4つの処理を一つのラウンドとしていますが、このうちMixColumnsが理解出来ません。

↓こちらでソースをDLしたのですが、悲しいことに理解出来ませんでした。
http://mars.elcom.nitech.ac.jp/security/aes/c.html

ある決められた行列との積を求める、との事ですが
「ある決められた行列」とはいったい何の事でしょうか。

128bit 4×4バイトの2次元配列と考えて縦の列を処理する、という所まで分かりました。具体的にどういった処理になるのか教えてください。

回答の条件
  • 1人3回まで
  • 登録:2006/07/11 21:18:12
  • 終了:2006/07/14 17:29:54

回答(5件)

id:quintia No.1

quintia回答回数562ベストアンサー獲得回数712006/07/11 22:19:24

ポイント12pt

http://www.quadibloc.com/crypto/co040401.htm

Next comes the Mix Column step.

という行の下に4x4の行列が書いてあります。

で、その下に、

However, this multiplication is done over GF(2^8). This means that the bytes being multiplied are treated as polynomials rather than numbers. Thus, a byte "muliplied" by 3 is that byte XORed with that byte shifted one bit left.

If the result has more than 8 bits, the extra bits are not simply discarded: instead, they're cancelled out by XORing the binary 9-bit string 100011011 with the result (shifted right if necessary). This string stands for the generating polynomial of the particular version of GF(2^8) used; a similar technique is used in cyclic redundancy checks.

とあって、

結果が 8bit表現でのガロア体(GF)を超える。

したがって3をかける代わりに 1ビット左シフトして XOR する。

その結果が8bitを超えるなら、2進9桁 100011011 との XOR をする。

それにより体を成す様になる。

というようなことが書いてあります。


aes_function.c の

MixColumn_AddRoundKeyに

x ^= (x << 1); 
if (( x >> 8) == 1) ret[ ここは色々 ] ^= (x ^ 283);

というのがちらほら見えます。

283 が 2進数9桁で 100011011 となるので上の説明と一致すると思います。


ざっくりgoogleで検索した結果からの回答ですが……。

id:herbest_an

GF(2^8)って何の事かと思ってたらガロア体という

ものだったんですね。

ガロア体、多項式…うぅ頭が痛くなってきました。

AESのアルゴリズムを理解するは数学の知識が必要なようですね…。

>したがって3をかける代わりに 1ビット左シフトして XOR する。

>その結果が8bitを超えるなら、2進9桁 100011011 との XOR をする。

3をかけるっていうのと283という数値が何処から出てきたのかが

いまいち分かりません。

何かの式があるのでしょうか。

式といえば関係ありそうなのを見つけましたが

多項式のようですがなぜこんな式が出来上がるのか

さらに、使い方すら分かりません。

a(t) = {03}t^3 + {01}t^2 + {01}t + {02}

こいつは、理解するの無理かも。。

2006/07/12 13:26:06
id:kurukuru-neko No.2

kurukuru-neko回答回数1844ベストアンサー獲得回数1552006/07/12 11:41:15

id:herbest_an

実は英語読めないのでgoogleで日本語記事だけに

絞って検索してたんですよ。

教えてもらった物はエキサイト翻訳しながら少しずつ読ませてもらいます。

どうもここを見てるともう少しで理解出来そうな気がするんですが

http://mailsrv.nara-edu.ac.jp/~asait/crypto/crypto/crypt.htm...う~ん、ガロア体ってのを十分に理解してないせいか

いまいち分からない。

例えば、演算に利用する縦4バイトに具体的な数値が入っていたとして、

どのような計算過程を経てどんな答えが出てくるのでしょうか。

2006/07/12 13:54:16
id:smoking186 No.4

186回答回数74ベストアンサー獲得回数62006/07/12 23:30:18

ポイント50pt

どうもここを見てるともう少しで理解出来そうな気がするんですが

http://mailsrv.nara-edu.ac.jp/~asait/crypto/crypto/crypt.htm#sec...う~ん、ガロア体ってのを十分に理解してないせいか

いまいち分からない。

とりあえず有限体そのものを説明するのは置いておくとして, 有限体上での計算が出来るように説明していきます.

http://mailsrv.nara-edu.ac.jp/~asait/crypto/crypto/crypt.htm#sec...

を引きながら説明を加えていきます.

準備 1. 1 バイトデータを有限体 GF(2^8) の元とみなすことができる

Rijndael では有限体 GF(2) 上の既約多項式

m(t) = t^8 + t^4 + t^3 + t + 1

を固定して、 1 バイト データ (8 ビット データ) を次のようにして、有限体 GF(2^8) の元とみなしている。

\{c_7,c_6,c_5,c_4,c_3,c_2,c_1,c_0\} \leftrightarrow c_7t^7+c_6t^6+c_5t^5+c_4t^4+c_3t^3+c_2t^2+c_1t+c_0 \bmod{m(t)}

これが1のコメント中の283という数値が何処から出てきたのかの回答です.

283というのは2進表記して, 100011011になり, 多項式としてみれば, x^8+x^4+x^3+x+1になるので, 有限体のタネとして用意した多項式m(t)と一緒になります.

http://mailsrv.nara-edu.ac.jp/~asait/crypto/crypto/crypt.htm#sec...

のMixColumns()変換のところに入ります.

MixColumns () 変換は state の列の変換である。

準備 1 最初に state の各列を GF(2^8)上の 4 次の多項式とみなす。

\begin{pmatrix}s_0 \\ s_1 \\ s_2 \\ s_3 \end{pmatrix} \leftrightarrow s_0 x^3+ s_1 x^2+ s_2 x + s_3

準備 2 GF(2^8) 上の多項式 a(x) を次で定める。

a(x)=\{03\}_{16}x^3+\{01\}_{16}x^2+\{01\}_{16}x+\{02\}_{16}

但し、GF(2^8)と 1 バイトデータを同一視し、多項式 a(x) の係数は 2 桁の 16 進数である。

MixColumns() 変換は state の列を 4 次未満の多項式 s(x) と同一視したとき次で与えられる。

s(x) := s(x) a(x) mod (x^4 - 1)

誤解を招かないよう変数をtからxにしました.

1や質問では行列で説明されていたのが, こちらでは多項式の掛け算になっています. これを同一視する方法は以下です. というか普通に行列の掛け算です.

a(x) * s(x) \bmod{x^4 - 1}の演算を4次元正方行列と4次元ベクトルの積に直します. a(x)= {}^t(a_0, a_1, a_2, a_3)となっているとき, 回転関数を\mathrm{rot}(a)={}^t(a_3, a_0, a_1, a_2)で定義します. すると, a(x)*s(x) \bmod{x^4-1}は以下の形になります. (a,\mathrm{rot}(a), \mathrm{rot}^2(a), \mathrm{rot}^3(a)) s. a(x)=\{03\}_{16}x^3+\{01\}_{16}x^2+\{01\}_{16}x+\{02\}_{16}として, 1の回答中にある行列を見ると,\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}となって確かに一致しています.

これで, 3をかけるっていうのの回答がようやくできます. \{03\}_{16}はa(x)の3次の項の係数だから, 3を"掛ける"わけです.

最後に有限体上での掛け算を多項式と思ってやってみます.

具体的に, 1の回答中にある,

For example, multiplying the binary string 11001010 by 3 within this Galois Field works like this:

1        11001010
2      *       11
3       ---------
4       110010100
5        11001010
6       ---------
7       101011110  (XOR instead of addition)
8       100011011  (this is XORed, instead of subtracting 256)
9       ---------
10        1000101

を見ます.

1行目は11001010をZ_2[x]中の多項式としてみれば, x^7+x^6+x^3+x^1です. 2行目は3をZ_2[x]中の多項式としてみて, x+1です. 4行目はxを掛けるので1ビット左にシフトして110010100です. 5行目は1を掛けるのでそのまま11001010です. 7行目は, 各係数がGF(2)上の要素なので, XORを取ります. すると8次の多項式 (2進9ビット)になってしまったので, 有限体のタネの多項式100011011XORを取って, 10行目が得られるというわけです.

id:herbest_an

詳しい解説ありがとうございます。

かなり、自分には難しいですね。

この説明で一瞬分かりかけた気がしましたけどやっぱりダメでした。

完全に理解するのは追々として、とにかくプログラムが組めれば

いいので(丸写しとかでなく)自分なりに概念と手順だけでも

考えてみる事にします。

まずビット計算で縦4byteを加算処理する。

(Cのソースを見てると何故かXOR)

この時に各バイトに一定の係数をつける。

さらに8bitで収まるように、計算後8bitを超えたら283でXOR。

この係数と283は復元の為に計算されつくした数値(なのかな)

これを1byte毎にずらしながら暗号化していく。

そしてこれを間逆の順序でやったら複合化される…(ホント?)

{3,1,1,2}の係数はRijndaelの計算上でのキマリと考える事にします。

とすると下のような計算になるのですが

int a,b,c,d;

a = s[0] * 3 ^ s[1] * 1; //s0に係数の3,s1に1をかけて二つをXOR

if(a >> 8 == 1){ //9bitになった場合283でXOR

a = a ^ 283;

}

a = a ^ s[2] * 1;

if(a >> 8 == 1){

a = a ^ 283;

}

a = a ^ s[3] * 2;

if(a >> 8 == 1){

a = a ^ 283;

}

これで変換後の1byteデータが変数aに入る。

ただこれだとDLしたCのソースと全然違って来るんですよね。

何処か勘違いしてます?

まったくかすりもしてなかったら泣けてくる…

2006/07/13 13:57:23
id:smoking186 No.5

186回答回数74ベストアンサー獲得回数62006/07/14 00:01:48

ポイント73pt

まずビット計算で縦4byteを加算処理する。(Cのソースを見てると何故かXOR) この時に各バイトに一定の係数をつける。さらに8bitで収まるように、計算後8bitを超えたら283でXOR。この係数と283は復元の為に計算されつくした数値(なのかな)。これを1byte毎にずらしながら暗号化していく。そしてこれを間逆の順序でやったら複合化される…(ホント?)

{3,1,1,2}の係数はRijndaelの計算上でのキマリと考える事にします。とすると下のような計算になるのですが

int a,b,c,d;
a = s[0] * 3 ^ s[1] * 1; //s0に係数の3,s1に1をかけて二つをXOR
if(a >> 8 == 1){ //9bitになった場合283でXOR
 a = a ^ 283;
}

a = a ^ s[2] * 1;
if(a >> 8 == 1){
 a = a ^ 283;
}

a = a ^ s[3] * 2;
if(a >> 8 == 1){
 a = a ^ 283;
}

これで変換後の1byteデータが変数aに入る。ただこれだとDLしたCのソースと全然違って来るんですよね。何処か勘違いしてます? まったくかすりもしてなかったら泣けてくる…

惜しい.

分かり易くするためにMixColumn()の入力をs={}^t(s_0, s_1, s_2, s_3), 出力をf={}^t(f_0, f_1, f_2, f_3)とします.

具体的に計算を書くと,

\begin{pmatrix}f_0\\f_1\\f_2\\f_3\end{pmatrix}=\begin{pmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{pmatrix}\begin{pmatrix}s_0\\s_1\\s_2\\s_3\end{pmatrix}

で, 真面目に行列の掛け算を行うと,

\begin{pmatrix}f_0\\f_1\\f_2\\f_3\end{pmatrix}=\begin{pmatrix}2 s_0 + 3 s_1 + s_2 + s_3\\s_0 + 2 s_1 + 3 s_2 + s_1\\s_0 + s_1 + 2 s_2 + 3 s_1\\3 s_0 + s_1 + s_2 + 2 s_3\end{pmatrix}

です. (演算はGF(2^8)上で行っていることに注意してください.)

書かれているプログラムの断片は, こちらの表記では a = f_3ということになると思います.

さて, 演算はGF(2^8)上でやっているので, a = s[0] * 3 ^ s[1] * 1; //s0に係数の3,s1に1をかけて二つをXORだと間違っています. (使われている言語がC++等で, 二項演算子"*"がちゃんと定義し直されていれば大丈夫ですが.) 1の回答に書かれている通り,

したがって3をかける代わりに 1ビット左シフトして XOR する。

その結果が8bitを超えるなら、2進9桁 100011011 との XOR をする。

が正しいGF(2^8)上での00000011との掛け算です. 前回の回答中のFor example, ...のところの演算は具体的にGF(2^8)上で11001010に00000011を掛けています.

ということなので, プログラムの断片を正しく書き直すと以下かと.

int f_3;
//s0に0000 0011を掛ける.
f_3 = (s[0] << 1) ^ s[0];
if ((f_3 >> 8) == 1) {f_3 = f_3 ^ 283;} 
//s1を足す.
f_3 = f_3 ^ s[1];
//s2を足す.
f_3 = f_3 ^ s[2];
//s3に0000 0010を掛けて足す.
f_3 = f_3 ^ (s[3] << 1);
if ((f_3 >> 8) == 1) {f_3 = f_3 ^ 283;}

そしてこれを間逆の順序でやったら複合化される…(ホント?)と書かれていますが, 真逆が良く分かりません.

結果として出てきたfからsを得るためには, a(x)で生成される行列Aの逆行列をA^{-1}と書くと, s=A^{-1} fとする必要があります. 更に, A ≠ A^{-1}です.

id:herbest_an

あーーわかったー!

いや、わかってないかもしれません。

でも勘違いしてた事はわかりました。

係数の3は(x^1)+(1)=(10)+(1)だから(左シフト)+(1かけたもの)なんですね。

それで足し算はGF(2)上の出来事だからxorになると。

(この辺がいまいちピンときませんが…)

それで283xorは係数をかけた時に(というか桁上がりが発生する段階で)行うんですね。

気になっていた復元の為の逆行列ですが2の回答で頂いたpdfに載っていました。

a(x)={02,03,01,01} の時、A^{-1}={0E,0B,0D,09} だそうです。

そのまま試してみるとfからsを求めることが出来ました。

わーい。

逆数がどのようにして求められるのかとか、まだよく分からない所が

ありますが、とりあえず何とかプログラムは組めそうなのでここで終了

したいと思います。

ありがとうございました。

2006/07/14 17:26:02

コメントはまだありません

この質問への反応(ブックマークコメント)

トラックバック

  • euc prima materia diary 2006-07-12 17:11:32
    GF(2^8)って何の事かと思ってたらガロア体という ものだったんですね。 ガロア体、多項式…うぅ頭が痛くなってきました。 http://q.hatena.ne.jp/1152620289 とりあえずガロア体についてはお
  • 186::Diary 2006-07-13 14:45:39
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません