(57)【要約】      （修正有）【課題】4段AES型暗号の最小Active S-boxes数が所定の目標値th以上になるようなMixColumns関数のn次元2進行列Mを生成することができる技術を提供する。【解決手段】n次元２進行列Mのブランチナンバーbを決定するブランチナンバー計算部１と、j=1,2として、n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して定義される値を計算して、その最小値をASjとする第一計算部２と、j=2,3として、n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して非ゼロではないWi及びZiの数の和を計算して、その最小値をASSjとする第二計算部３と、b,ASj及びASSjに基づいて判定を行いVの値を決定する第一判定部４及び第二判定部５と、Vが所定の閾値th以上であると判定された場合には、Mを出力する第三判定部６と、を備える。【選択図】図１
2017207604.tif 000002
【特許請求の範囲】
【請求項１】
n次元２進行列Mを選択し、選択されたMのブランチナンバーbを決定するブランチナンバー計算部と、
L,nを所定の１以上の整数とし、i=0,1,…,n-1とし、Xi∈(F2^L)nとし、Yi=MXiとし、(X0,X1,…,Xn-1)に4段AES型暗号における所定のShiftRows関数の逆変換を行った結果を(W0,W1,…,Wn-1)とし、(Y0,Y1,…,Yn-1)に上記ShiftRows関数の変換を行った結果を(Z0,Z1,…,Zn-1)とし、Aを任意のベクトルとし、hw(A)をAの要素の中の非ゼロの要素の数とし、j=1,2として、n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して以下の式により定義される値を計算して、その最小値をASjとする第一計算部と、
【数４】
2017207604.tif 000006
j=2,3として、n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して非ゼロではないWi及びZiの数の和を計算して、その最小値をASSjとする第二計算部と、
AS1≦min{b×ASS2,b(b+2)}であるか判定し、AS1≦min{b×ASS2,b(b+2)}であると判定された場合には、V=AS1とする第一判定部と、
上記第一判定部においてAS1≦min{b×ASS2,b(b+2)}でないと判定された場合には、min{AS1,AS2}≦min{b×ASS3,b(b+2)}であるか判定し、min{AS1,AS2}≦min{b×ASS3,b(b+2)}であると判定された場合にはV=min{AS1,AS2}とし、min{AS1,AS2}≦min{b×ASS3,b(b+2)}でないと判定された場合にはV=min{b×ASS3,b(b+2)}とする第二判定部と、
上記Vが所定の閾値th以上であるか判定し、上記Vが所定の閾値th以上であると判定された場合には、上記Mを出力する第三判定部と、
上記第三判定部によりMが出力されるまで、上記ブランチナンバー計算部に上記選択されたMとは異なるMを選択させ、上記ブランチナンバー計算部、上記第一計算部、上記第二計算部、上記第一判定部、上記第二判定部及び上記第三判定部の処理を繰り返し行わせる制御部と、
を含む行列生成装置。
【請求項２】
請求項１の行列生成装置で出力されたMをMixColumnsとして4段AES型暗号を行う暗号装置。
【請求項３】
ブランチナンバー計算部が、n次元２進行列Mを選択し、選択されたMのブランチナンバーbを決定するブランチナンバー計算ステップと、
第一計算部が、L,nを所定の１以上の整数とし、i=0,1,…,n-1とし、Xi∈(F2^L)nとし、Yi=MXiとし、(X0,X1,…,Xn-1)に4段AES型暗号における所定のShiftRows関数の逆変換を行った結果を(W0,W1,…,Wn-1)とし、(Y0,Y1,…,Yn-1)に上記ShiftRows関数の変換を行った結果を(Z0,Z1,…,Zn-1)とし、Aを任意のベクトルとし、hw(A)をAの要素の中の非ゼロの要素の数とし、j=1,2として、n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して以下の式により定義される値を計算して、その最小値をASjとする第一計算ステップと、
【数５】
2017207604.tif 000007
第二計算部が、j=2,3として、n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して非ゼロではないWi及びZiの数の和を計算して、その最小値をASSjとする第二計算ステップと、
第一判定部が、AS1≦min{b×ASS2,b(b+2)}であるか判定し、AS1≦min{b×ASS2,b(b+2)}であると判定された場合には、V=AS1とする第一判定ステップと、
第二判定部が、上記第一判定ステップにおいてAS1≦min{b×ASS2,b(b+2)}でないと判定された場合には、min{AS1,AS2}≦min{b×ASS3,b(b+2)}であるか判定し、min{AS1,AS2}≦min{b×ASS3,b(b+2)}であると判定された場合にはV=min{AS1,AS2}とし、min{AS1,AS2}≦min{b×ASS3,b(b+2)}でないと判定された場合にはV=min{b×ASS3,b(b+2)}とする第二判定ステップと、
第三判定部が、上記Vが所定の閾値th以上であるか判定し、上記Vが所定の閾値th以上であると判定された場合には、上記Mを出力する第三判定ステップと、
制御部が、上記第三判定ステップによりMが出力されるまで、上記ブランチナンバー計算ステップに上記選択されたMとは異なるMを選択させ、上記ブランチナンバー計算ステップ、上記第一計算ステップ、上記第二計算ステップ、上記第一判定ステップ、上記第二判定ステップ及び上記第三判定ステップの処理を繰り返し行わせる制御ステップと、
を含む行列生成方法。
【請求項４】
請求項３の行列生成方法で出力されたMをMixColumnsとして4段AES型暗号を行う暗号方法。
【請求項５】
請求項１の行列生成装置又は請求項２の暗号装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、主に情報セキュリティ分野で用いられる暗号に関する。特に、4段AES暗号で用いられるMixColumns行列を生成する技術に関する。
【背景技術】
【０００２】
データを秘匿するためには暗号化技術が有効である。暗号化の方法は共通鍵暗号と公開鍵暗号がある。共通鍵暗号では、暗号作成側と暗号復号側で同一の鍵を用い、この鍵は秘密に管理されている。一方、公開鍵暗号では暗号文作成の鍵と暗号文復号の鍵は異なっており、一方の鍵は公開しても、他の鍵は現実的な時間内に求まらないと広く信じられている。一般的に、暗号化の処理速度の観点からは、共通鍵暗号方式が有利であり、インターネット上の多くの環境で共通鍵暗号が利用されている。
【０００３】
高速かつ安全な共通鍵暗号を構成するために、暗号化対象のデータを適当な長さのブロックに分割し、そのブロック毎に暗号化する方法をブロック暗号と呼ぶ。ブロック暗号では、始め、ラウンド関数と呼ばれる暗号装置としては不十分だが、非常に高速に処理できる暗号装置を用意する。次に、ラウンド関数を複数回繰り返し実行することで、ブロック暗号の暗号装置とする。このような暗号の代表例として、AES暗号がある（例えば、非特許文献１参照。）。AESは、8ビットを1セルとした4×4行列を1ブロックとした暗号装置である。そのラウンド関数は下記の4つの関数で構成される。
【０００４】
SubBytes:各セルの値をS-boxと呼ばれる置換表を用いて別の値に置換する。
【０００５】
ShiftRows:4×4行列の各行を行番号分ローテーションする。
【０００６】
MixColumns:4×4行列の各列を撹拌装置により撹拌する。
【０００７】
AddRoundKey:4×4行列で表現された副鍵を排他的論理和する。
【０００８】
AESは高い安全性を保有する暗号としてアメリカ国立標準技術研究所(NIST)により米国標準として定められている。
【０００９】
多くの利用実績や解析評価が存在するAES構造は広く議論されており、AESのビット長や行列サイズを一般化した暗号を一般に、AES型暗号と呼ぶ（例えば、非特許文献２参照。）。
【００１０】
軽量実装に優れたAES 型暗号を構成する場合、MixColumns処理にて2進行列を利用することが優位であることは広く知られている。しかしながら、2進行列がもたらす撹拌性能は、AESがMixColumnsで用いたMDS行列がもたらす撹拌性能と比較して、著しく小さい。したがって、軽量実装に優れたAES型暗号は、安全性を確保するためにラウンド関数の繰り返す回数を多くする必要があり、結果的に、処理速度が低下する可能性があった。
【００１１】
AES型暗号の撹拌性能を評価する手段の１つに、4段AES型暗号におけるActive S-boxes数の保証がある。MixColumnsで利用される撹拌行列の撹拌性能を評価する指数としてBranch Number（以下、ブランチナンバーとも言う。）があるが、4段AES型暗号はBranch Numberがbのとき、最小Active S-boxes 数がb2になることが保証されている。2進行列はMDS行列と比較して、Branch Numberが小さくなるため、結果、2進行列を用いたAES 型暗号の撹拌性能は劣化する。例えばn次元MDS行列のBranch Numberはn=4,5,6,7,8に対して、それぞれ5,6,7,8,9となることが知られており、それらを4段AES 型暗号のMixColumnsに利用した場合、最小Active S-boxes数は25、36、49、64、81 となる。一方で、n次元2進行列のBranch Numberはn=4,5,6,7,8に対して、それぞれ最大4,4,4,4,5となることが知られており、それらを4段AES型暗号のMixColumnsに利用した場合、最小Active S-boxes数は16、16、16、16、25となる。以上より、2進行列の利用は、軽量実装の面で有益ではあるが、撹拌性能を著しく劣化させる可能性がある。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Specification for the ADVANCED ENCRYPTION STANDARD (AES). U.S. DEPARTMENT OF COMMERCE/National Institute of Standards and Technology (2001), Federal Information Processing Standards Publication 197
【非特許文献２】Jean, J., Naya-Plasencia, M., Peyrin, T.: Improved cryptanalysis of AES-like permutations. J. Cryptology 27(4), pp.772-798, (2014)
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、これまで4段AES型暗号の最小Active S-boxes数が所定の目標値th以上になるようなMixColumns関数のn次元2進行列Mを生成する技術は知られていなかった。
【００１４】
以上を鑑みて、この発明は、4段AES型暗号の最小Active S-boxes数が所定の目標値th以上になるようなMixColumns関数のn次元2進行列Mを生成する行列生成装置、生成された行列Mを用いた暗号装置、これらの方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
この発明の一態様による行列生成装置は、n次元２進行列Mを選択し、選択されたMのブランチナンバーbを決定するブランチナンバー計算部と、L,nを所定の１以上の整数とし、i=0,1,…,n-1とし、Xi∈(F2^L)nとし、Yi=MXiとし、(X0,X1,…,Xn-1)に4段AES型暗号における所定のShiftRows関数の逆変換を行った結果を(W0,W1,…,Wn-1)とし、(Y0,Y1,…,Yn-1)にShiftRows関数の変換を行った結果を(Z0,Z1,…,Zn-1)とし、Aを任意のベクトルとし、hw(A)をAの要素の中の非ゼロの要素の数とし、j=1,2として、n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して以下の式により定義される値を計算して、その最小値をASjとする第一計算部と、
【００１６】
【数１】
2017207604.tif 000003
【００１７】
j=2,3として、n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して非ゼロではないWi及びZiの数の和を計算して、その最小値をASSjとする第二計算部と、AS1≦min{b×ASS2,b(b+2)}であるか判定し、AS1≦min{b×ASS2,b(b+2)}であると判定された場合には、V=AS1とする第一判定部と、第一判定部においてAS1≦min{b×ASS2,b(b+2)}でないと判定された場合には、min{AS1,AS2}≦min{b×ASS3,b(b+2)}であるか判定し、min{AS1,AS2}≦min{b×ASS3,b(b+2)}であると判定された場合にはV=min{AS1,AS2}とし、min{AS1,AS2}≦min{b×ASS3,b(b+2)}でないと判定された場合にはV=min{b×ASS3,b(b+2)}とする第二判定部と、Vが所定の閾値th以上であるか判定し、Vが所定の閾値th以上であると判定された場合には、Mを出力する第三判定部と、第三判定部によりMが出力されるまで、ブランチナンバー計算部に選択されたMとは異なるMを選択させ、ブランチナンバー計算部、第一計算部、第二計算部、第一判定部、第二判定部及び第三判定部の処理を繰り返し行わせる制御部と、を備えている。
【発明の効果】
【００１８】
4段AES型暗号の最小Active S-boxes数が所定の目標値th以上になるようなMixColumns関数のn次元2進行列Mを生成することができる。
【図面の簡単な説明】
【００１９】
【図１】行列生成装置の例を説明するためのブロック図。
【図２】行列生成方法の例を説明するための流れ図。
【図３】4段AES型暗号の概要の例を示す図。
【図４】ラウンド関数計算装置の例を説明するためのブロック図。
【図５】ラウンド関数計算方法の例を説明するための流れ図。
【図６】暗号装置の例を説明するためのブロック図。
【発明を実施するための形態】
【００２０】
以下、図面を参照して、この発明の一実施形態について説明する。
【００２１】
［行列生成装置及び方法］
行列生成装置は、ブランチナンバー計算部１、第一計算部２、第二計算部３、第一判定部４、第二判定部５、第三判定部６及び制御部７を例えば備えている。この行列生成装置の各部が、図２に例示するステップＳ１からステップＳ７の処理を行うことにより行列生成方法が実現される。
【００２２】
行列生成装置及び方法では、与えられたMに対してASj(j=1,2)及びASSj(j=2,3)を計算する。ASj及びASSjは例えば以下のように定義される。
【００２３】
定義1：(ASj)
4段AES型暗号の2段目にあるn個のMixColumnsのうちi番目のMixColumnsの入力をXiとする。4段AES型暗号の概要の例を図３に示す。図３では、nのことをmと表記している。i=0,1,…,n-1とし、Xi∈(F2^L)nとする。XiにMixColumnsを作用した結果をYi=MXiとする。また、(X0,X1,…,Xn-1)に4段AES型暗号における所定のShiftRows関数の逆変換を行った結果を(W0,W1,…,Wn-1)とする。(Y0,Y1,…,Yn-1)に上記ShiftRows関数の変換を行った結果を(Z0,Z1,…,Zn-1)とする。また、Aを任意のベクトルとし、hw(A)をAの要素の中の非ゼロの要素の数とする。
【００２４】
n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して以下の式により定義される値を計算して、その最小値をASjとする。
【００２５】
【数２】
2017207604.tif 000004
【００２６】
定義2(ASSj)
Wi,Xi,Yi,ZiをASjのときと同様に定義する。n個のXiのうちj個が非ゼロな全ての取り得る(X0,X1,…,Xn-1)に対して非ゼロではないWi及びZiの数の和を計算して、その最小値をASSjとする。
【００２７】
＜ブランチナンバー計算部１＞
ブランチナンバー計算部１は、n次元２進行列Mを選択し、選択されたMのブランチナンバーbを決定する（ステップＳ１）。決定されたブランチナンバーbは、第一判定部４及び第二判定部５に出力される。
【００２８】
n次元２進行列Mの選択は、任意に行えばよい。例えば、ブランチナンバー計算部１は、n次元２進行列Mをランダムに選択する。
【００２９】
ブランチナンバーbは、例えば以下の式により計算することができる。このブランチナンバーbは、例えば、xの総当たりで計算することができる。
【００３０】
b=minx≠0(hw(x)+hw(Mx))
ブランチナンバーbについては、参考文献１を参照のこと。
【００３１】
〔参考文献１〕Joan Daemen, "Cipher and Hash Function Design Strategies based on linear and differential cryptanalysis", Katholieke Universiteit Leuven, March 1995
【００３２】
＜第一計算部２＞
第一計算部２は、AS1,AS2を計算する（ステップＳ２）。計算されたAS1は、第一判定部４に出力される。計算されたAS2は、第二判定部５に出力される。
【００３３】
なお、AS2の計算は、第一判定部４においてAS1≦min{b×ASS2,b(b+2)}でないと判定された後に行ってもよい。
【００３４】
＜第二計算部３＞
第二計算部は、ASS2,ASS3を計算する（ステップＳ３）。計算されたASS2は、第一判定部４に出力される。計算されたASS3は、第二判定部５に出力される。
【００３５】
なお、ASS3の計算は、第一判定部４においてAS1≦min{b×ASS2,b(b+2)}でないと判定された後に行ってもよい。
【００３６】
＜第一判定部４＞
第一判定部４は、AS1≦min{b×ASS2,b(b+2)}であるか判定し、AS1≦min{b×ASS2,b(b+2)}であると判定された場合には、V=AS1とする（ステップＳ４）。Vは、第三判定部６に出力される。また、判定結果は、第二判定部５に出力される。
【００３７】
＜第二判定部５＞
第二判定部５は、第一判定部４においてAS1≦min{b×ASS2,b(b+2)}でないと判定された場合には、min{AS1,AS2}≦min{b×ASS3,b(b+2)}であるか判定し、min{AS1,AS2}≦min{b×ASS3,b(b+2)}であると判定された場合にはV=min{AS1,AS2}とし、min{AS1,AS2}≦min{b×ASS3,b(b+2)}でないと判定された場合にはV=min{b×ASS3,b(b+2)}とする（ステップＳ５）。V及び判定結果は、第三判定部６に出力される。
【００３８】
＜第三判定部６＞
第三判定部６は、Vが所定の閾値th以上であるか判定し、Vが所定の閾値th以上であると判定された場合には、上記Mを出力する（ステップＳ６）。
【００３９】
所定の閾値thは、所定の正の整数である。
【００４０】
＜制御部７＞
制御部７は、第三判定部６によりMが出力されるまで、ブランチナンバー計算部１に上記選択されたMとは異なるMを選択させ、ブランチナンバー計算部１、第一計算部２、第二計算部３、第一判定部４、第二判定部５及び第三判定部６の処理を繰り返し行わせる（ステップＳ７）。
【００４１】
第一判定部４及び第二判定部５により得られるVは、Mに対応する最小Active S-boxesとなる。ここでは、説明の簡略化のため、その証明を省略する。このため、第三判定部６によりVが所定の閾値th以上であると判定された場合には、その場合のMを用いた4段AES型暗号でV以上のActive S-boxes数が保証される。
【００４２】
上記の行列生成装置及び方法を用いることで、軽量性と撹拌性能の両方に優れた、2進行列M、言い換えればMixColumnsを構成できるようになる。
【００４３】
［ラウンド関数計算装置及び方法］
上記の行列生成装置及び方法で生成された行列Mにより定まるMixColumnsを用いてラウンド関数計算装置及び方法を構成することができる。
【００４４】
ラウンド関数計算装置は、図４に示すように、第一計算部１０、第二計算部２０、第三計算部３０及び第四計算部４０を例えば備えている。このラウンド関数計算装置の各部が、図５に例示するステップＳ１０からステップＳ４０の処理を行うことによりラウンド関数計算方法が実現される。
【００４５】
＜第一計算部１０＞
第一計算部１０は、入力された４行４列の行列に対して、所定の置換表を用いて置換するSubBytes関数の計算を行う（ステップＳ１）。計算結果は、第二計算部２０に出力される。
【００４６】
入力される４行４列の行列は、ラウンド関数計算装置が用いられるブロック暗号方式及び暗号方式に依存する。
【００４７】
＜第二計算部２０＞
第二計算部２０は、第一計算部１の計算結果に対して、例えば次式で定義されるShiftRowsの変換をするShiftRows関数の計算を行う（ステップＳ２）。計算結果は、第三計算部３０に出力される。
【００４８】
【数３】
2017207604.tif 000005
【００４９】
＜第三計算部３０＞
第三計算部３０は、第二計算部２の計算結果に対して、行列生成装置及び方法により生成されたMにより定まるMixColumns関数の計算を行う（ステップＳ３）。計算結果は、第四計算部４に出力される。
【００５０】
＜第四計算部４０＞
第四計算部４０は、第三計算部３０の計算結果に対して、４行４列の所定の副鍵行列との排他的論理を計算するAddRoundKey関数の計算を行う（ステップＳ４）。
【００５１】
４行４列の所定の副鍵行列は、ラウンド関数計算装置が用いられるブロック暗号方式及び暗号方式に依存する。
【００５２】
［暗号装置及び方法］
ラウンド関数計算装置及び方法を用いて、暗号装置及び方法を構成することができる。
【００５３】
暗号装置及び方法は、例えば図６に示すように、それぞれラウンド関数計算装置及び方法を含む。暗号装置及び方法は、ラウンド関数計算装置及び方法によるラウンド関数の計算を複数回繰り返し実行することでデータの暗号化又は復号を実行する。
【００５４】
暗号装置及び方法の詳細は、実装しようとする暗号方式に依存する。例えば、4段AES型暗号方式を用いることができる。
【００５５】
行列生成装置及び方法により、最小Active S-boxes数が所定の閾値th以上になることが保証される。最小Active S-boxes数が大きくなることで、効率よく安全性保証が可能になり、処理性能の向上が可能となる。
【００５６】
[3] Todo, Y., Aoki, K.: Wide trail design strategy for binary mixcolumns.
In: ACNS (2016)
【００５７】
［プログラム及び記録媒体］
行列生成装置、ラウンド関数計算装置、暗号装置及び復号装置における各処理をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、その各処理がコンピュータ上で実現される。
【００５８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５９】
また、各処理手段は、コンピュータ上で所定のプログラムを実行させることにより構成することにしてもよいし、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００６０】
［変形例］
また、上記の処理は、記載の順にしたがって時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６１】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
2017207604.tif 000008
【図２】
2017207604.tif 000009
【図３】
2017207604.tif 000010
【図４】
2017207604.tif 000011
【図５】
2017207604.tif 000012
【図６】
2017207604.tif 000013