通信を必要としない鍵更新方法を用いた共有鍵暗号の強化
理学専攻

情報科学コース

加藤知美

はじめに1共有鍵暗号を用いて安全に通信するためには，定期的に鍵交換を行う必要がある．しかしよく使われるディフィー・ヘルマンの鍵交換方法などの公開鍵暗号を用いた鍵交換には通信を必要とするので回数を増やしにくいことが多い．ここでは通信を必要としない代わりに共有秘密鍵情報を鍵のサイズより大きくとることを特徴とする鍵更新方法を提案し，標準暗号 AES の具体的な鍵更新方法の例について安全性の比較を行なった結果を紹介する．

2AES(Advanced Encryption Standard) のしくみ

2.1

仕様

2.3.2

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

2.3.3

ブロック長 128bit,192bit,256bit の中から選択可能
鍵長 128bit,192bit,256bit の中から選択可能
ラウンド数鍵長に依存. 鍵長 128bit:10 回,192bit:12回,256bit:14 回
本研究ではブロック長 128bit, 鍵長 128bit を使用する.

2.2

MixColumn 変換

各 列 (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 をかける.

暗号化アルゴリズム

AES(ブロック長 128bit) の暗号化アルゴリズムは以下の通り.
1. 入力された平文を 8bit 毎に区切り,4 × 4 マス(state) に振り分ける.
2. 入力された鍵を KeyExpansion 関数を用いて【規定ラウンド数+1】(11) 個に拡張.
3.state に対して AddRoundKey 変換を施す.
4.state に対し,SubByte 変換,ShiftRow 変換,MixColumn 変換,AddRoundKey 変換を【規定ラウンド数-1】(9) 回繰り返し行う.
5. 最 終 ラ ウ ン ド の み,SubByte 変 換,ShiftRow 変換,AddRoundKey 変換だけを行う.

2.3

ShiftRow 変換

2.3.4

AddRoundKey 変換

鍵を知らないとできない唯一の変換
共有する鍵情報 128bit の鍵を簡単な方法で 128bit11個に拡張し，それぞれの 128bit のデータに加える. そのとき k 回目の変換は k 番目の 128bit に加える.4 回に 1 回上の式を使い、それ以外は下の式を使う。

それぞれの変換について

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

SubByte 変換 (Sbox とも呼ばれる)

3

8bit b7 ,b6 ,· · · ,b0 をひとまとまりとして,0,1 係数の多項式 · · · + b7 x7 + b1 x + b0 とみなし, 次式により体にする. GF (28 ) ' F2 [x]/(x8 + x4 + x3 + x + 1)
加法は係数ごとに GF(2) の元として計算し乗法は多項式としてかけて同値関係で割る.(単位元は 1, 零元は 0)
SubByte 変換ではまず,GF (28 ) での乗法の逆元をとる.
ただし,0 は 0 に移す. 次に以下のように処理を行う．

鍵更新方法

共有秘密情報を鍵のサイズより大きくとり，鍵更新
ではそれを一方向性関数で更新し，更新した共有秘密情報の一部を新しい暗号鍵として用いることで，通信せず暗号鍵更新を行う．共有秘密情報の一部しか暗号鍵として用いない構成とすることで，安全性を損なうことなく鍵更新ができる．この方法では暗号鍵更新のための情報を通信しないため，その情報を漏らさないための処理が不要となり，暗号鍵更新のための計算量も通信を利用して新たな鍵に交換するよりも少なくで1

きる．これにより頻繁に共有鍵を取り替えることが可能となり，同コストでこれまで以上に信頼性の高い暗号通信装置を実現できることが期待される．例として
AES の 128bit 鍵を以下のように更新する鍵更新方法について評価を行なう．

3.1

共有秘密情報の初期値はすべて 0 とする．
ラウンド数 1〜規定回数-1 回まで観測

5.2

χ2 検定

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

例

ここでは共有する秘密情報を 256bit とし，AES の鍵としてそのうちの 128bit を用いる．

5.3

最初に共有する 256bit の秘密情報 K0 の下位 128bitを取り出したものを L0 、L0 を Sbox したものを上位128bit にした計 256bit を e とする
i ≥ 0 について，Ki の上位 128bit を Mi ，下位 128bitを Li とする．Mi の最上位 8bit の mi を Sbox し，その次の 8bit に上書きしたものを Ci とし，次式で新しい Ki を作成する．Ki+1 =Cie modNi ≥ 1 のとき Ki の下位 128bit の Li を i 番目の鍵として使う．

4法 N の選び方

法 N は N=s × t で構成される 256bit の合成数で，s,t,(s-1)/2,(t-1)/2 は素数となるように選ぶ．この例では，以下を用いた．

6

t=111000010011100001111111110010111011
00110100101111111111011000111000000110
01001011011101000110001100101010011101
1110001000111111(128bit)

AES の乱数性の評価

AES は 4 種類の変換の一部をやめたりラウンド数を少なくしたりすると，十分に混ざらなくなることが知られている．以下で，平文・鍵ともに 128bit の AESを簡略化して意図的に安全でなくした暗号と，そこに鍵更新方法を適用した暗号の混ざり具合を比較することで乱数性を評価した結果を紹介する．
5.1

まとめと今後の課題

AES の 4 つの変換から 1 つ変換を抜くと乱数性が低下することが表よりわかるが，今回提案した鍵更新を用いれば，ずっと同じ鍵を使い続けるより乱数性が高くなることが示された．また，暗号に用いた 128bit 鍵 Liについての情報が第三者に伝わった場合にも，256bitの秘密情報 Ki を予想するには残りの 128bit を予想する必要があり，これは次の 128bit の AES 鍵 Li+1 を予想するのと同じ難しさがあることがわかる．このため，この共有秘密情報を鍵サイズより大きくとる鍵更新方法を用いれば，通信を用いることなく，新規の鍵を選びなおすことと同等の安全性を確保できると期待される．
今回有効だった検定方法だけでなく，違う検定方法を用いて評価をしたい．

s=101001010011101110011101011010100110
00100011001010111011011111000000000111
11110000010010000111000010100110110011
1100101111010111(128bit)

5

結果
変換を表では以下の番号で表すことにする
1.SubByte 変換 (Sbox でも表せる)
2.ShiftRow 変換
3.MixColumn 変換
4.AddRoundKey 変換 (通常の鍵)
4’.AddRoundKey 変換 (提案手法での鍵)
このときの χ2 値は, 自由度 15, 有意水準0.05,χ2 ≥ 25.0 で棄却

参考文献[1] 福田恵子,”共有鍵暗号方式の評価と比較”, お茶の水女子大学修士論文,2010.

検定方法

128bit の平文を 8bit × 16ヶ所とみなす．この 16ヶ所の中の 1ヶ所だけに 00000001 を入れ, それ以外は全て 0 とした 16 通りの平文を変換した後の各 4bit の数について χ2 検定を行う.
簡略化した暗号化の変換が十分によく混ざるものであれば，変換後の 16 × (128/4) 個の4bit の数の集合はランダムに選んだ 4bit の数の集合とみなせるはずである．

[2] J.Daemen,V.Rijmen,” AES Proposal:Rijndael ”,
AES submission,1998.
[3] Oliver Pretzel,”Error-Correcting Codes and Finite Fields”,1992.
[4] 篠崎信雄,”統計解析入門”, サイエンス社,1994[5] 学校法人慶應義塾，萩田真理子，暗号鍵更新方法，
特許第 3695526 号，特開 2003-110540，2003.

2