暗号 AES の実装と評価
福田恵子(指導教員：萩田真理子)

研究背景の集合へと変換されることが挙げられる．これは，類似した平文から類似した暗号文が生1997 年アメリカ合衆国において，それまで共 成されてしまうと，解読したい暗号文に類似有鍵暗号方式の代表的な規格であった DES が， した暗号文を用いて平文を推測されてしまう
急速な計算機の処理速度の上昇によって安全 恐れがあるからである．従って，暗号文と真性ではなくなってきたことを理由に，新しい規格 乱数が識別不可能であることが必要とされる．
として AES(Advanced Encryption Standard)が世界規模で公募された．そして 2001 年 3 月， 3.2 評価方法
J.Daemen と V.Rijmen が提案した Rijndael が本研究は，4.1 の条件を AES が満たしていAES として採択され公表された．以降，AES るかについていくつかの評価を行った．評価
はアメリカ合衆国のみだけでなく，欧州の暗号 方法と条件については以下の通りである．
規格 NESSIE や日本の暗号規格 CRYPTRECにも採用され，今日の共有鍵暗号方式の代表評価方法１ 各暗号文の 1 のビットの数を数え，的な規格の一つとして利用されており，新たその分布と同数の乱数の 1 のビットの数な共有鍵暗号方式の規格を提案する際の速度の分布を比較．評価条件は以下の通り．
や安全性の評価基準としても利用されている．
本研究では，評価基準に用いられる AES 自身
平文空間 128bit 中 1 のビットが 1 つまたの安全性を考察していく．
は 2 つだけの類似した平文の集合
鍵 0(全て 0 のビットのみ，鍵長 128bit)
ラウンド数 1 〜 10 ラウンドまで 1 ラウン
2 AES(AdvancedEncryption
ドずつ観測

1Standard)

2.1 仕様ブロック長 128bit, 192bit，256bit の中から選択可能
鍵長 128bit，192bit，256bit の中から選択可能
ラウンド数 鍵長に依存．鍵長 128bit：10 回，192bit：12 回，256bit：14 回
本研究ではブロック長 128bit，鍵長 128bit を使用する．
2.2 暗号化アルゴリズム
AES(ブロック長 128bit) の暗号化アルゴリ
ズムは以下の通り．

評価方法２ 各暗号文を 4byte 毎に区切って格納し，格納時に以前に等しい値を格納していた場合を衝突 1 としてその回数を計測．
平文空間 128bit 中 1 のビットが 1 つまた
は 2 つだけの類似した平文の集合
鍵 0(全て 0 のビットのみ，鍵長 128bit)
ラウンド数 1 〜 10 ラウンドまで 1 ラウン
ドずつ観測
本研究において 4byte 毎に区切ったのは，AESアルゴリズムが 1byte 毎の演算を行うことが多く，かつ 4byte で 1 つの変換を行うからである．

1. 入力された平文を 8bit 毎に区切り，4 × 4
3.3 結果マス (state) に振り分ける．
2. 入力された鍵を KeyExpansion 関数を用 3.3.1 評価方法 1 の結果
いて【規定ラウンド数 +1】(11) 個に拡張．
3. state に対して AddRoundKey 変換を施す． 図 1 は評価方法 1 に基づいて，1 ラウンドの4. state に対し，SubByte 変換，ShiftRow 変 み操作した各暗号文の 1 のビットの数を数え，換，MixColumn 変換，AddRoundKey 変 同数のものがいくつあるかを示している．図 2
換を【規定ラウンド数 −1】(9) 回繰り返 は同数の乱数を同様に 1 のビットの数を数え，各々の個数を示したものである．図 1 と図 2 をし行う．
5. 最 終 ラ ウ ン ド の み ，SubByte 変 換 ， 比較すると，1 ラウンドのみ変換を施したもの
ShiftRow 変換，AddRoundKey 変換だけ には偏りが存在し，本来多いはずの中心部分にはあまり存在していないことがわかる．しを行う．
かし，図 1 のように，3 ラウンド操作すると分布が乱数と比較しても差がなくなってしまっ
3 評価方法と結果ている．
よって，評価方法 1 においては，AES は乱3.1 安全性の高い暗号の条件数性が高いことがわかった．
安全性の高い暗号の条件の一つとして，類似性の高い平文の集合が類似性の低い暗号文
43変換 (MC)，AddRoundKey 変換 (ARK)の 4 つの変換のうち，どれか一つの変換を除いて暗号化を行う．
評価方法 各暗号文を 4byte 毎に区切り，3 節の評価方法 2 と同様の衝突を計測．
平文空間 128bit 中 1 のビットが 1 つまたは 2つだけの類似した平文の集合
鍵 0(全て 0 のビットのみ，鍵長 128bit)
ラウンド数 1 〜 10 ラウンドまで 1 ラウンドずつ観測

700
1round3round600

500

400300200

1000020406080100120140

図 1: 1・3 ラウンド目の 1 の数の分布

4.2 結果
表 2 を見てわかるように，どの変換を抜いた場合においても衝突回数が格段に増加している．従って，AES の 4 つの変換は，どの変換を抜いた場合でも乱数性が非常に悪くなることがわかった．また，ShiftRow 変換と MixColumn
変換それぞれを除いた場合は等しい結果となり，これは各行 (列) に出現する種類の総数分を全体 (33024) から除いたものである．この原因は，同一のものは変換後も同一のものになるためである．

700random number

600

500

400300200

1000020406080100120140

図 2: 同数の乱数の 1 の数の分布

3.4 評価方法 2 の結果
先に，衝突の発生する期待値を計算する．
4byte 毎 に 取 り 出 す こ と よ り，空 間 全 体 は232 = 4294967296 個の元が存在する．平文空間は 128 C1 + 128 C2 = 128 + 8128 = 8256 個の元があり，これを 4byte 毎に区切るので，全体から 33024 個取り出したこととなる．232 の空間から 33024 個取り出した時の衝突回数の∑k−1
期待値は，多くとも 33024
k=1 232 = 0.126957 となる．従って，真性乱数を同数取ってきた場合，衝突回数は 1 程度である．
ここで表 1 を見ると，1 ラウンドと 2 ラウンドでは衝突が確認されるが，3 ラウンド以降は衝突が確認されない．従って衝突回数の期待値が極めて小さいことから，評価方法 2 において，1 ラウンドと 2 ラウンドは乱数性が低いが，3 ラウンド以降は乱数性が高いことがわかる．
表 1: 各ラウンドでの衝突数
Round
123 4
Number 32495 25266 0 0
Round678 9
Number000 04

表 2: 除去した変換毎の衝突数
Round
12345678910550100AES の各関数に対する評価

4.1 評価方法
3 節の結果より，本研究の評価方法においては，AES の乱数性は極めて高いことがわかった．ここでは，AES の 4 つの変換のうち，どの変換が重要な変換であるかを検証する．検証方法は以下の通りである.
暗号化アルゴリズム AES の SubByte 変 換(SB)，ShiftRow 変換 (SR)，MixColumn
44AES
32495
25266
00000000

SB32495
28706
014396
14396
04496
30908
30908
24388

除去した変換SRMC32495 32495
31966 31966
30908 30908
30908 30908
30908 30908
30908 30908
30908 30908
30908 30908
30908 30908
30908 30908

ARK32495
29145
2477024768
2476824768
24768
24768
24768
24768

まとめと今後の課題

本研究を通して，AES の乱数性は高く，10回のラウンド数は安全性を高めるために十分であることがわかった．そしてその安全性は 4つの変換を全て組み合わせることに起因しており，全ての変換が不可欠であるという結果が得られた．
今後，4 節の結果を詳しく分析するために，各変換の特徴をさらに解析していきたい．また，変換の順序を入れ換えた場合の解析をしたい．

参考文献[1] J. Daemen, V. Rijmen, ”AES Proposal:Rijndael”, AES submission, 1998.
[2] NIST, ”Advanced Encryption Standard(AES) ”, FIPS PUB 197, 2001.