(57)【特許請求の範囲】
【請求項１】
ラウンドごとのRoundKeyが予め記憶されたRoundKey記憶部と、
入力された192bitの平文に、ByteSub、ShiftRow、MixColumn、AddRoundKeyの４つの演算を１ラウンドとするラウンド関数を、ラウンドごとにRoundKey記憶部から読み出したRoundKeyを用いて、複数ラウンド繰り返し適用するRijndael型192bitブロック暗号化アルゴリズムにより暗号文を生成する暗号文生成部と、 
を備えるRijndael型192bitブロック暗号化装置であって、
前記ShiftRow演算のShiftRowパラメータ（s0,s1,s2,s3）は、（0,1,3,4）である
ことを特徴とするRijndael型192bitブロック暗号化装置。
【請求項２】
請求項１に記載のRijndael型192bitブロック暗号化装置において、
ラウンド関数の適用ラウンド数は１２以上である
ことを特徴とするRijndael型192bitブロック暗号化装置。
【請求項３】
暗号文生成部が、入力された192bitの平文に、ByteSub、ShiftRow、MixColumn、 AddRoundKeyの４つの演算を１ラウンドとするラウンド関数を、ラウンドごとにRoundKey記憶部から読み出したRoundKeyを用いて、複数ラウンド繰り返し適用するRijndael型192bitブロック暗号化アルゴリズムにより暗号文を生成するRijndael型192bitブロック暗号化方法であって、
前記ShiftRow演算のShiftRowパラメータ（s0,s1,s2,s3）は、（0,1,3,4）である
ことを特徴とするRijndael型192bitブロック暗号化方法。
【請求項４】
請求項３に記載のRijndael型192bitブロック暗号化方法において、
ラウンド関数の適用ラウンド数は１２以上である
ことを特徴とするRijndael型192bitブロック暗号化方法。
【請求項５】
請求項１又は２に記載のRijndael型192bitブロック暗号化装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、より安全性の高いブロック暗号の設計手法に関するものであり、特に、Rijndael型192bitブロック暗号の丸め差分攻撃に対する安全性がより高いRijndael型192bitブロック暗号化装置、方法、及びそのプログラムに関する。
【背景技術】
【０００２】
ブロックサイズＮ-bitのブロック暗号Ｅkは、送信者と受信者で予め共有しておいた秘密鍵Ｋを用いて、Ｎ-bitの平文ＰからＮ-bitの暗号文Ｅk(Ｐ)を生成する、Ｋに依存する置換処理である。
【０００３】
Rijndael型192bitブロック暗号（非特許文献１参照）のアルゴリズムにおいては、Ｅkは192bitの入力ブロックに対してラウンド関数Ｒkという処理を複数ラウンド（12ラウンド以上であることが望ましい）繰り返し適用するものである。すなわち、192bit単位にブロック化された平文Ｐに対する暗号化処理は、192bitの変数Ｘi（ｉ＝０、１、…、ｔ−１）を用いて以下のように記述することができる。
【０００４】
Ｘ0 ←Ｐ
Ｘi+1 ←Ｒk(Ｘi)
Ｅk(Ｐ) ←Ｘt
Rijndael型192bitブロック暗号のアルゴリズムにおいては、１byte（８bit）が１要素として扱われ、図４に示すように192bitブロックは、24個の要素（byte）からなる４×６の行列として表現される。ここで、行列の横方向の各行をithrow（i=0,1,2,3）、縦方向の各列をjthcolumn（j=0,1,2,3,4,5）と呼び、192bit（24byte）全体をステートと呼ぶ。
【０００５】
ラウンド関数Ｒkは、ByteSub、ShiftRow、MixColumn、AddRoundKeyの４つの演算をこの順番で適用する関数である。
【０００６】
ByteSubは、非線形のbit転置であり、各byteの内部でbit転置を行う。
【０００７】
ShiftRowは、非線形の転置処理であり、図５(a)に示すように、ｉ番目のrowにある各バイトを左にｓiバイト巡回シフトする。s0、s1、s2、s3の４つの変数をShiftRowパラメータと呼び、非特許文献１においては192bitブロックに対し（s0,s1,s2,s3）＝（0,1,2,3）としている。
【０００８】
MixColumnは、図５(b)に示すように各Columnに対し４×４の行列を掛ける処理を行う。ここでいう４×４の行列は非特許文献１所定のものである。
【０００９】
AddRoundKeyは、MixColumn演算後の４×６行列と、非特許文献１所定の方法により秘密鍵Ｋから各ラウンドごとに生成された４×６の行列であるRoundKeyとが入力され、両行列の各要素について排他的論理和をとったものを出力する。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Joan Daemen, Vincent Rijmen, "AES Proposal: Rijndael", NIST AES Proposal, 1998, last updated at 1999
【発明の概要】
【発明が解決しようとする課題】
【００１１】
異なる２つの平文Ｐ、Ｐ´を暗号化するとき、Ｐに対して演算した時の値とＰ´に対して演算したときの値とのbit毎の排他的論理和(xor)を差分と呼ぶ。例えば平文の差分はＰ xor Ｐ´で表され、暗号文の差分はＥk(Ｐ) xor Ｅk(Ｐ´)で表される。演算の途中状態の差分も同様に定義できる。
【００１２】
異なる２つの平文Ｐ、Ｐ´を暗号化したとき、２つの暗号化の演算過程の値、及び演算結果は、独立にランダムに振る舞うことが望ましい。すなわち差分が偏った値であること、すなわち演算過程全体として差分が小さいことは望ましくない。
【００１３】
差分はブロック暗号の安全性を評価する上で、ひとつの重要な指標として用いられる。差分に偏りがある平文ペアを簡単に見つけることができるブロック暗号は安全ではないと評価され、見つけることが困難であるブロック暗号は安全であると評価される。
【００１４】
差分の考えの拡張として、byte単位など複数bitを同時に考慮し、複数bitうちどれか１bitでも差分があるか、又は全てのbitに差分が無いかを表したものを丸め差分と呼ぶ。Rijndael型192bitブロック暗号のようにbyte単位で処理を行う暗号方式に対しては、この丸め差分に基づく攻撃方法の存在が知られている（丸め差分攻撃）。
【００１５】
演算の過程において、丸め差分を持つbyteの累積個数が多ければ多いほど、差分が偏りを持たなくなり安全であると言える。そのため、ブロック暗号の設計者は、できるだけ差分が偏りを持たないように、つまり、できるだけ丸め差分を持つバイトの累積個数が多くなるように設計を行う必要がある。
【００１６】
しかし、非特許文献１に開示されたRijndael型192bitブロック暗号においては、ラウンド関数Ｒkによる５ラウンドの変換処理で42byte（簡単のため、各Ｒk処理の先頭のバイト数のみをカウント）しか丸め差分を持たないような、丸め差分の伝搬経路が存在するという問題があった。
【００１７】
図６は、５ラウンドの変換処理（＃１〜５）で累積の丸め差分が42byteとなる過程を図示したものである。灰色部分が丸め差分を持つbyteであり、図６のように処理前に右上隅のbyteにのみ丸め差分がある時に５ラウンドの変換処理後の丸め差分の累積個数が最小となる。処理前に１byteであった丸め差分は、１ラウンド目で４byteとなり、２ラウンド目で４byteから16byteとなり、３ラウンド目では16byteが維持され、４ラウンド目で16byteから４byteとなり、５ラウンド目で４byteから１byteとなっている。従って、累積で42（=1+4+16+16+4+1）byteとなる。なお、ラウンド関数Ｒkの４つの演算のうち、ByteSubとAddRoundKeyについては、各byte内の処理であり、他のbyteへの丸め差分の伝搬に関わらないため、演算の前後で丸め差分を持つbyteに変化は生じない。また、MixColumnの演算は「入力の４byte全てに丸め差分がなければ、出力４byte全てに丸め差分がなく、それ以外の場合、入出力の合計８byte中、少なくとも５byte以上に丸め差分が存在する」というＭＤＳと呼ばれる性質を持つが、図６の各ラウンドのMixColumn演算はＭＤＳの丸め差分バイト数の性質を満たしている。
【００１８】
本発明の目的は、Rijndael型192bitブロック暗号の演算の過程でより多くのbyteに丸め差分を持たせることができ、かつ、従来と同じ暗号化処理能力を持つRijndael型192bitブロック暗号化装置、方法、及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００１９】
本発明のRijndael型192bitブロック暗号化装置は、ラウンドごとのRoundKeyが予め記憶されたRoundKey記憶部と、入力された１９２ｂｉｔの平文に、ByteSub、ShiftRow、MixColumn、AddRoundKeyの４つの演算を１ラウンドとするラウンド関数を、ラウンドごとにRoundKey記憶部から読み出したRoundKeyを用いて、複数ラウンド繰り返し適用するRijndael型192bitブロック暗号化アルゴリズムにより暗号文を生成する暗号文生成部と、を備え、
前記ShiftRow演算のShiftRowパラメータ（s0,s1,s2,s3）は、（0,1,3,4）であることを特徴とする。
【発明の効果】
【００２０】
本発明は、ShiftRowパラメータを適切に選択することによって、演算の過程でより多くのbyteに丸め差分を持たせるものである。ShiftRowパラメータの変更は暗号化処理能力に影響を及ぼさないため、従来と同じ暗号化処理能力を確保しつつ、従来より安全性が高いRijndael型192bitブロック暗号化装置、方法、及びそのプログラムを提供することができる。
【図面の簡単な説明】
【００２１】
【図１】ShiftRowパラメータを最適化した本発明のラウンド関数を、入力文に５ラウンド適用した場合の、丸め差分を持つbyteの遷移の様子を示す図。
【図２】Rijndael型192bitブロック暗号化装置１００の構成例を示すブロック図。
【図３】Rijndael型192bitブロック暗号化装置１００の処理フロー例を示す図。
【図４】192bitの変数を４×６の行列化するイメージを示す図。
【図５】ShiftRow演算及びMixColumn演算のイメージを示す図。
【図６】従来技術のラウンド関数を、入力文に５ラウンド適用した場合の、丸め差分を持つbyteの遷移の様子を示す図。
【発明を実施するための形態】
【００２２】
本発明は、Rijndael型192bitブロック暗号の演算の過程でより多くのbyteに丸め差分を持たせるため、ラウンド関数ＲkにおけるShiftRow演算に用いるShiftRowパラメータを最適化する。具体的には、ShiftRowパラメータ（s0,s1,s2,s3）として（0,1,3,4）を用いる。
【００２３】
図１は、ShiftRowパラメータ（s0,s1,s2,s3）として（0,1,3,4）を用いた場合に、５ラウンドの変換処理（＃１〜５）において、丸め差分を持つbyteが遷移していく様子を示したものである。灰色部分が丸め差分を持つbyteであり、図１のように処理前に右上隅のbyteにのみ丸め差分がある時に５ラウンドの変換処理後の丸め差分の累積個数が最小となる。処理前は１byteであった丸め差分は、１ラウンド目で４byteとなり、２ラウンド目で４byteから16byteとなり、３ラウンド目で16byteから24byteとなり、４ラウンド目で24byteから８byteとなり、５ラウンド目で８byteから２byteとなっている。従って、累積で55（=1+4+16+24+8+2）byteとなる。
【００２４】
このように、ShiftRowパラメータ（s0,s1,s2,s3）として（0,1,3,4）を用いることで、図６に示す42byteの丸め差分を発生させるパターンが形成不可能になり、代わりに図１に示すパターンが最小の丸め差分55byteを発生させる。
【００２５】
図２は、上記のShiftRowパラメータを用いて暗号化を行うRijndael型192bitブロック暗号化装置１００の構成例を示すブロック図である。また、図３はその処理フロー例である（Ｓ１〜Ｓ７）。適用するShiftRowパラメータが異なる以外は、構成、処理フローとも従来技術による場合と相違は無い。
【００２６】
Rijndael型192bitブロック暗号化装置１００は、ByteSub演算を行うByteSub演算部１１０とShiftRow演算を行うShiftRow演算部１２０とMixColumn演算を行うMixColumn演算部１３０とAddRoundKey演算を行うAddRoundKey演算部１４０とラウンドごとのRoundKeyが予め記憶されたRoundKey記憶部１５０とを備える。RoundKeyは、非特許文献１所定の方法により秘密鍵Ｋから各ラウンドごとに生成された４×６の行列である。
【００２７】
平文は192bit単位にブロック化されて入力され（Ｓ１）、ブロック毎に暗号化処理が行われる。処理に際しては、各ブロックは図４に示すようなbyte単位の４×６の行列として扱われる。４×６のbyte行列化された192bitブロックは、まずAddRoundKey演算部１４０でRoundKey記憶部１５０から読み出された第１ラウンドのRoundKeyと排他的論理和がとられ初期化される（Ｓ２）。この初期化した行列がByteSub１１０に入力され、まずByteSub演算が施され（Ｓ３）、続いてShiftRow演算部１２０にてShiftRowパラメータ（s0,s1,s2,s3）として（0,1,3,4）を用いたShiftRow演算が施され（Ｓ４）、続いてMixColumn演算部１３０にてMixColumn演算が施され（Ｓ５）、続いてAddRoundKey演算部１４０にてRoundKey記憶部１５０から読み出された第２ラウンドのRoundKeyとの排他的論理和がとられる（Ｓ６）。そしてＳ３〜Ｓ６の処理を各ラウンドのRoundKeyを用いつつ複数ラウンド（12ラウンド以上であることが望ましい）繰り返した後、得られた結果を暗号文として出力する（Ｓ７）。
【００２８】
以上のように本発明は、ShiftRowパラメータを適切に選択することによって、演算の過程でより多くのbyteに丸め差分を持たせるものである。ShiftRowパラメータの変更は暗号化処理能力に影響を及ぼさないため、従来と同じ暗号化処理能力を確保しつつ、従来より安全性が高いRijndael型192bitブロック暗号化装置、方法、及びそのプログラムを提供することができる。
【００２９】
上記の各処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【００３０】
また、本発明のRijndael型192bitブロック暗号化装置をコンピュータによって実現する場合、装置の各部が有す機能の処理内容はプログラムによって記述される。そのプログラムは、例えば、ハードディスク装置に格納されており、実行時には必要なプログラムやデータがＲＡＭ(Random Access Memory)に読み込まれる。その読み込まれたプログラムがＣＰＵにより実行されることにより、コンピュータ上で各処理内容が実現される。なお、処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図２】
0005449063.tif 000002
【図３】
0005449063.tif 000003
【図４】
0005449063.tif 000004
【図５】
0005449063.tif 000005
【図１】
0005449063.tif 000006
【図６】
0005449063.tif 000007