暗号 AES の SubByte 変換の評価
加藤知美 (指導教員：萩田真理子)
研究背景

1

2.3

AES は以下で示す 4 つの変換で成り立っている.

DES は 1976 年に標準暗号として採用され, ブロック暗号の代表的な規格として広く使われてきた. しかし 1997 年アメリカ合衆国において, 急速な計算機の処理速度の上昇によって安全ではなくなったことを理由に, 新しい規格として AES(Advanced EncryptionStandard) が世界規模で公募された. そして 2001 年 3月,J.Daemen と V.Rijmen が提案した Rijndael が AESとして採択され公表された. 以降,AES はアメリカ合衆国のみだけでなく, 欧州の暗号規格 NESSIE や日本の暗号規格 CRYPTREC にも採用され, 今日の共有鍵暗号方式の代表的な規格の一つとして利用されており,新たな共有鍵暗号方式の規格を提案する際の速度や安全性の評価基準としても利用されている.
本研究では,AES の変換のひとつである SubByte 変換における乱数性と AES の変換を一部を抜いたときの乱数性を評価した.

2AES(Advanced Encryption Standard)

2.1

仕様

それぞれの変換について

2.3.1

SubByte 変換 (SB)8bit b0 ,b1 ,· · · ,b7 をひとまとまりとして,0,1 係数の多項式 b0 + b1 x + · · · + b7 x7 とみなし, 次式により体にする.
GF (28 ) ' F2 [x]/(x8 + x4 + x3 + x + 1)
加法はビットごとに XOR をとり、乗法は多項式としてかけて同値関係で割る.(単位元は 1, 零元は 0)
SubByte 変換ではまず, GF (28 ) での乗法の逆元をとる. ただし,0 は 0 に写す. この逆元処理を A とおく.
次に行列処理 B を行う.

ブロック長 128bit,192bit,256bit の中から選択可能
鍵長 128bit,192bit,256bit の中から選択可能
ラ ウ ン ド 数 鍵 長 に 依 存. 鍵 長 128bit:10回,192bit:12 回,256bit:14 回

最後にベクトル (11000110)T を F2 上で足し算する.
このベクトル処理を C とおく.

2.3.2

ShiftRow 変換 (SR)

本研究ではブロック長 128bit, 鍵長 128bit を使用する.

2.2

暗号化アルゴリズム

行ごとにかき混ぜ,i 行目 (i=0,1,2,3) を i バイト左にシフトする.

AES(ブロック長 128bit) の暗号化アルゴリズムは以下の通り.

2.3.3

1. 入力された平文を 8bit 毎に区切り,4 × 4 マス(state) に振り分ける.

MixColumn 変換 (MC)

各 列 (a0 a1 a2 a3 )T を バ イ ト 係 数 多 項 式 a(x) =a0 + a1 x + a2 x2 + a3 x3 と み な し, そ れ ぞ れ に
GF (28 )[x]/(x4 + 1) 上で c(x) = 3x3 + x2 + x + 2 をかける.

2. 入力された鍵を KeyExpansion 関数を用いて【規定ラウンド数+1】(11) 個に拡張.
3. state に対して AddRoundKey 変換を施す.
4. state に対し,SubByte 変換,ShiftRow 変換,MixColumn 変換,AddRoundKey 変換を【規定ラウンド数-1】(9) 回繰り返し行う.
5. 最 終 ラ ウ ン ド の み,SubByte 変 換,ShiftRow 変換,AddRoundKey 変換だけを行う.

2.3.4

AddRoundKey 変換 (ARK)

鍵を知らないとできない唯一の変換
共有する鍵情報:128 ビットの鍵を簡単な変換で 128 ビッ
ト 11 個に拡張し、それぞれのデータに加える. そのとき k 回目の変換は k 番目の 128 ビットを加える.

1933.1

評価方法

除去した変換2χ 検定

期待度数と観測度数の差が大きいと χ2 値も大きくなる. 上記によって得られた χ2 値を表に示す.
有意水準は 0.05 とする.

rAES

SBSR

MC

ARK

13418

2436

3418

5186

1888

266.5

945

464

546

320

317.0625

279.5

170

171.5

208

4

14.6875116

185.25264.4375

528

535.9375

33.375117.375

255.8125

176

6

21.75

16.75

140.5625

166.625256

4SubByte 変換の乱数性の評価

7159432.0625

181.5

288

4.1

検定方法

810235.875

99104.0625

1608 ビット中の上位 3 ビットを 0 に固定した 25個のバイトの SubByte 変換後の 8 ビットに現れる 1 の個数について χ2 検定を行う.
ラウンド数 1〜規定回数-1 回まで観測

925.5625

210

185.25377.5625320

4.2

表 2: AES のそれぞれの変換後の χ2 値
たが, 本研究でも同じ結果が得られた. さらに本研究では,SubByte 変換の一部を除いたときの乱数性の評価を行った.

結果棄却される所を太字,r:ラウンド数とする.
逆元, 行列, ベクトルのそれぞれの処理を A,B,C とする.
このときの χ2 値は, 自由度 3,χ2 ≥ 7.81 で棄却
使用した変換使用した変換なし

A

BとC

BC

12436

4868

3418

3418

4868

2945

1457

27.5

116.5

1433

rA

BとC

AとBとC

3279.5154.0625

23.25

36896

1

4.5961

5.21384.96754116

27.9375

15

16.25

191.252

12.96131.44014.2702

533.37512.9375

19.375

9.25

66.75

3

4.59610.12504.5776

6

16.75

21.75

13.8751742

412.961312.96133.92047

94

15.8125

30.5

10.25

229.7554.5961

5.21384.20468

235.875

6.875

18.25

3.75

99.5

6

12.96131.44010.55369210

19.6875

9.562525.9375

165.1257

4.59610.12504.96678

12.961312.96135.881894.5961

5.21384.2416

表 3: SB 変換の中身に着目した χ2 値

62逆元変換のみ, 行列とベクトル変換だけでは乱数性は低いが, ２種類交互に繰り返し混ぜると乱数性が高くなることがわかった.

5AES の乱数性の評価

5.1

検定方法

まとめと今後の課題

先行研究と同様に 4 種類の変換のどのひとつを除いても乱数性が低いことがいえる. 今回着目した SubByte
変換の中の変換, 逆元, 行列, ベクトルについてみると,行列を行う時、乱数性が高いとわかる. 一方, ベクトルのみを行うと何もしないよりも乱数性が低いとわかった.
AES に対して有効だった今回の評価方法を用いて,他の暗号と AES の比較を行っていきたい.

表 1: 8 ビットにおける SB 変換の χ 値

128 ビットを 8 ビットごとに分けた 16ヶ所の中に 1ヶ所だけに 00000001 を入れ, それ以外は全て 0 とし,AES 変換後の写った先の 1 の入り方について χ2 検定を行う.
鍵 0(すべて 0 のビットのみ)
ラウンド数 1〜規定回数-1 回まで観測
5.2r

参考文献
[1] 福田恵子,”共有鍵暗号方式の評価と比較”, お茶の水女子大学修士論文,2010.
[2] J.Daemen,V.Rijmen,” AES Proposal:Rijndael ”,
AES submission,1998.

結果[3] Oliver Pretzel,”Error-Correcting Codes and Finite Fields”,1992.

SubByte 変換を SB, ShiftRow 変換を SR, MixColumn 変換を MC, AddRoundKey 変換を ARK とおく.
このときの χ2 値は, 自由度 15,χ2 ≥ 25.0 で棄却
別の検定方法による先行研究でも、4 種類の変換のどのひとつを除いても乱数性が低いことが知られてい[4] 篠崎信雄,”統計解析入門”, サイエンス社,1994

20