(57)【要約】【課題】攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な計算量をさらに低減することができる暗号強度評価装置、暗号強度評価方法及び暗号強度評価プログラムを提供する。【解決手段】暗号強度評価装置１００は、式生成部１０１によって生成された攻撃方程式を展開する式展開部１０３と、展開された攻撃方程式の中に存在する１次項から高次項までの暗号文項で纏めることによって展開式を整理する式整理部１０５とを備える。さらに、暗号強度評価装置１００は、整理された攻撃方程式において、暗号文の各次数項の係数である秘密鍵の各次数項を含む多項式を、１次の等価鍵に置き換える等価鍵置換部１０７と、等価鍵に関する未知項数を検出する未知項数検出部１０９と、未知項数に基づいて等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる暗号強度評価部１１１とを備える。【選択図】図２
2008109287.tif 000002
【特許請求の範囲】
【請求項１】
共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価装置であって、
前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成する式生成部と、
前記式生成部によって生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開する式展開部と、
前記式展開部によって展開された前記攻撃方程式の中に存在する１次項から高次項までの暗号文項で纏めることによって前記展開式を整理する式整理部と、
前記式整理部によって整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、１次の等価鍵に置き換える等価鍵置換部と、
前記等価鍵置換部によって前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出する未知項数検出部と、
前記未知項数検出部によって検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価する暗号強度評価部と
を備える暗号強度評価装置。
【請求項２】
共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価方法であって、
前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成するステップと、
生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開するステップと、
展開された前記攻撃方程式の中に存在する１次項から高次項までの暗号文項で纏めることによって前記展開式を整理するステップと、
整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、１次の等価鍵に置き換えるステップと、
前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出するステップと、
検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価するステップと
を備える暗号強度評価方法。
【請求項３】
共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価プログラムであって、
コンピュータに、
前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成する式生成処理と、
生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開する式展開処理と、
展開された前記攻撃方程式の中に存在する１次項から高次項までの暗号文項で纏めることによって前記展開式を整理する式整理処理と、
整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、１次の等価鍵に置き換える等価鍵置換処理と、
前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出する未知項数検出処理と、
検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価する暗号強度評価処理と
を実行させる暗号強度評価プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は攻撃方程式を解くことによって、共通鍵ブロック暗号の強度を評価する暗号強度評価装置、暗号強度評価方法及び暗号強度評価プログラムに関するものである。
【背景技術】
【０００２】
ＭＩＳＴＹ１をベースとして開発された共通鍵ブロック暗号として、ＫＡＳＵＭＩが知られている。ＫＡＳＵＭＩは第３世代移動通信システムの国際標準暗号として採用されている（非特許文献１参照）。
【０００３】
ＫＡＳＵＭＩなどの共通鍵ブロック暗号に対する暗号強度の評価に関して、当該共通鍵ブロック暗号にしたがって暗号化された暗号文を正しく平文に復号することができる正規の秘密鍵（以下、正規秘密鍵）の決定に用いられる攻撃方程式を、線形化手法を用いて解く方法が知られている。
【０００４】
線形化手法とは、攻撃方程式に含まれる鍵（秘密鍵や秘密鍵を元に生成された拡大鍵）に関する高次項を新たに独立な１次項と見なすことによって攻撃方程式を線形化し、得られた線形方程式を解くことによって正規秘密鍵を決定する手法である。
【０００５】
ＫＡＳＵＭＩに対して高階差分（例えば、１６階差分）を用いて攻撃する高階差分攻撃に関して、攻撃方程式の線形化手法を用いる方法が開示されている（非特許文献２参照）。さらに、当該線形化手法を高速化する方法も開示されている（非特許文献３参照）。
【０００６】
また、近年では、高階差分攻撃に類似したＩｎｔｅｇｒａｌ Ｃｒｙｐｔａｎａｌｙｓｉｓが提案された（非特許文献４参照）。非特許文献４には、Ｉｎｔｅｇｒａｌ特性を利用した攻撃方程式を解く際に、補間法（ｉｎｔｅｒｐｏｌａｔｉｏｎ）を用いる手法が示されている。
【非特許文献１】3GPP、“3GPP TS 35.202 V3.1.1 (KASUMI Specification)”、２００１年７月
【非特許文献２】南部俊一、金子敏信．「ＫＡＳＵＭＩの高階差分攻撃に関する一考察（III）」、基礎・境界ソサイエティ大会、Ａ−７−６、２００４年9月
【非特許文献３】Sugio, Nambu, Kaneko、“A Fast Calculus for the Linearizing Attack and Its Application to an Attack on KASUMI”、Applied Algebra, Algebraic Algorithms, and Error Correcting Codes (AAECC-16), pp163-172、２００６年２月
【非特許文献４】Knudsen, Wagner、“Integral Cryptanalysis (Extended abstract)”、Fast Software Encryption 2002 (FSE2002), pp112-127、２００２年
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述した攻撃方程式の線形化手法では、鍵に関する高次項を新たに独立な１次の未知項と見なして攻撃方程式を線形化する。攻撃方程式を線形化する際、攻撃方程式の中に存在する鍵が多いほど、求める未知項数が多くなる。この結果、暗号の強度を評価するために必要となる計算量が増大するという問題があった。
【０００８】
また、非特許文献４に示されている手法では、攻撃方程式の最大次数から見積もられ、存在し得るすべての未知項が数えられる。このため、実際に存在する未知項を数える場合と比較して未知項数が多くなる。この結果、暗号の強度を評価するために必要となる計算量が増大するという問題があった。
【０００９】
そこで、本発明は、このような状況に鑑みてなされたものであり、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な計算量を低減することができる暗号強度評価装置、暗号強度評価方法及び暗号強度評価プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した問題を解決するため、本発明は、次のような特徴を有している。まず、本発明の第１の特徴は、共通鍵ブロック暗号（例えば、ＫＡＳＵＭＩ）にしたがって暗号化された暗号文（暗号文Ｃ）、及び平文（平文Ｐ）を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式（式５）を解いて前記秘密鍵を求めるために必要となる選択平文組数（選択平文組数Ｍ）及び計算量（計算量Ｔ）を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価装置（暗号強度評価装置１００）であって、前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成する式生成部（式生成部１０１）と、前記式生成部によって生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開する式展開部（式展開部１０３）と、前記式展開部によって展開された前記攻撃方程式の中に存在する１次項から高次項までの暗号文項（例えば、c1，c2）で纏めることによって前記展開式を整理する式整理部（式整理部１０５）と、前記式整理部によって整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、１次の等価鍵に置き換える等価鍵置換部（等価鍵置換部１０７）と、前記等価鍵置換部によって前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数（未知項数Ｌ*）を検出する未知項数検出部（未知項数検出部１０９）と、前記未知項数検出部によって検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価する暗号強度評価部（暗号強度評価部１１１）とを備えることを要旨とする。
【００１１】
このような暗号強度評価装置によれば、暗号文項で整理された攻撃方程式において、暗号文の各次数項の係数である秘密鍵の各次数項を含む多項式が、新たな1次の等価鍵に置き換えられる。
【００１２】
このため、攻撃方程式中に存在する鍵に関する項数が減少する。つまり、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な選択平文の組数及び計算量を低減させることができる。
【００１３】
本発明の第２の特徴は、共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価方法であって、前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成するステップと、生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開するステップと、展開された前記攻撃方程式の中に存在する１次項から高次項までの暗号文項で纏めることによって前記展開式を整理するステップと、整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、１次の等価鍵に置き換えるステップと、前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出するステップと、検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価するステップとを備えることを要旨とする。
【００１４】
本発明の第３の特徴は、共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価プログラムであって、コンピュータに、前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成する式生成処理と、生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開する式展開処理と、展開された前記攻撃方程式の中に存在する１次項から高次項までの暗号文項で纏めることによって前記展開式を整理する式整理処理と、整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、１次の等価鍵に置き換える等価鍵置換処理と、前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出する未知項数検出処理と、検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価する暗号強度評価処理とを実行させることを要旨とする。
【発明の効果】
【００１５】
本発明の特徴によれば、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な計算量を低減することができる暗号強度評価装置、暗号強度評価方法及び暗号強度評価プログラムを提供することができる。
【発明を実施するための最良の形態】
【００１６】
次に、本発明の実施形態について説明する。具体的には、本実施形態において用いられる共通鍵ブロック暗号であるＫＡＳＵＭＩの内部構造、暗号強度評価装置の構成、暗号強度評価装置の動作、暗号強度評価装置の作用・効果、及びその他の実施形態について説明する。
【００１７】
なお、以下の図面の記載において、同一または類似の部分には、同一または類似の符号を付している。ただし、図面は模式的なものであり、各寸法の比率などは現実のものとは異なることに留意すべきである。
【００１８】
したがって、具体的な寸法などは以下の説明を参酌して判断すべきものである。また、図面相互間においても互いの寸法の関係や比率が異なる部分が含まれていることは勿論である。
【００１９】
（ＫＡＳＵＭＩの内部構造）
ＫＡＳＵＭＩは、ＭＩＳＴＹ１をベースに開発された共通鍵ブロック暗号である。ＫＡＳＵＭＩの入出力長は６４ビット、秘密鍵長は１２８ビットである。図１（ａ）〜（ｄ）は、ＫＡＳＵＭＩの内部構造を示す。
【００２０】
図１（ａ）は、ＫＡＳＵＭＩの全体構造を示す。図１（ａ）に示すように、ＫＡＳＵＭＩは、非線形関数のＦＯ関数と、鍵依存線形関数のＦＬ関数を交互に入れ替えた８段のＦｅｉｓｔｅｌ型構造を有する。
【００２１】
図１（ｂ）は、ＦＯ関数の内部構造を示す。ＦＯ関数は、各段にＦＩ関数が挿入された３段の変形Ｆｅｉｓｔｅｌ型構造である。
【００２２】
図１（ｃ）は、ＦＩ関数の内部構造を示す。ＦＩ関数では、各段において、置換テーブル（Ｓ−ｂｏｘ）Ｓ７、Ｓ９が交互に繰り返されている。Ｓ７の代数次数は３次、Ｓ９の代数次数は２次である。
【００２３】
図１（ｄ）は、ＦＬ関数の内部構造を示す。ＦＬ関数は、鍵のＡＮＤ／ＯＲ演算、１ビット左シフトローテーション、及び排他的論理和からなる。なお、図１（ａ）〜（ｄ）で示されているＫＡＳＵＭＩは、３ＧＰＰにおいて規格されている構造から鍵（ｋｉｊ１〜ｋｉｊ４）の挿入位置が一部変更されている。この理由は、攻撃方程式の生成を容易にするためである。
【００２４】
（暗号強度評価装置の構成）
次に、本実施形態に係る暗号強度評価装置１００の構成について説明する。具体的には、暗号強度評価装置１００の機能ブロック構成及び各機能の詳細について説明する。
【００２５】
（１）機能ブロック構成
図２は、本実施形態に係る暗号強度評価装置１００の機能ブロック構成を示す。図２に示すように、暗号強度評価装置１００は、式生成部１０１、式展開部１０３、式整理部１０５、等価鍵置換部１０７、未知項数検出部１０９及び暗号強度評価部１１１を備える。
【００２６】
暗号強度評価装置１００は、ＫＡＳＵＭＩにしたがって暗号化された暗号文Ｃ、及び平文Ｐを暗号化する際に用いた秘密鍵を入力とするＦＯ／ＦＬ関数を含む攻撃方程式（式５参照）を解いて、当該秘密鍵を求めるために必要となる選択平文組数Ｍ及び計算量Ｔを算出する。また、暗号強度評価装置１００は、攻撃方程式を解いて当該秘密鍵を求めることによってＫＡＳＵＭＩの暗号強度を評価する。
【００２７】
式生成部１０１は、暗号文Ｃを入力し、秘密鍵を求めるために用いられる攻撃方程式を生成する。
【００２８】
式展開部１０３は、式生成部１０１によって生成された攻撃方程式を入力とし、入力された攻撃方程式を展開する。
【００２９】
式整理部１０５は、式展開部１０３によって展開された攻撃方程式の中に存在する１次項から高次項までの暗号文項で纏めることによって当該展開式を整理する。
【００３０】
等価鍵置換部１０７は、式整理部１０５によって整理された攻撃方程式において、暗号文Ｃ（具体的には、暗号文ＣＬ，ＣＲ）の各次数項の係数である秘密鍵の各次数項を含む多項式を、１次の等価鍵に置き換える。
【００３１】
未知項数検出部１０９は、等価鍵置換部１０７によって等価鍵に置き換えられた攻撃方程式において、当該等価鍵に関する未知項数を検出する。
【００３２】
暗号強度評価部１１１は、未知項数検出部１０９によって検出された未知項数に基づいて、等価鍵を求めるために必要となる選択平文組数Ｍ及び計算量Ｔを見積もる、または当該等価鍵を求めることによってＫＡＳＵＭＩの暗号強度を評価する。
【００３３】
（２）機能詳細
次に、暗号強度評価装置１００の機能の詳細、具体的には、攻撃方程式の生成、展開、展開された攻撃方程式の整理、及び等価鍵への置換について説明する。
【００３４】
式生成部１０１は、（式１）に示すように、ＫＡＳＵＭＩのS-boxの入力サイズに合わせて平文Ｐを８つに分割する。
【数１】
2008109287.tif 000003
【００３５】
また、ＫＡＳＵＭＩの３段目出力のうち、右３２ビットをＨＲ３（図１（ａ）参照）と表記する。式生成部１０１は、Ｓ−ｂｏｘの出力サイズに合わせて、ＨＲ３を（式２）のように分割する。ここで、図３（ａ）〜（ｃ）は、ｈ３３に係る内部経路を示す。
【数２】
2008109287.tif 000004
【００３６】
このとき、（式３）に示す選択平文Ｐ*を用いた１６階差分を計算すると、常に（式４）が成立する。
【数３】
2008109287.tif 000005
【数４】
2008109287.tif 000006
【００３７】
式生成部１０１は、このような高階差分特性を用いて、（式５）に示すように、５段構成のＫＡＳＵＭＩの鍵に関する攻撃方程式を生成する。以降、本実施形態では、５段構成のＫＡＳＵＭＩを例として説明する。
【数５】
2008109287.tif 000007
【００３８】
（式５）において、ＣＬは、選択平文Ｐ*を暗号化した暗号文Ｃの左３２ビットである。同様に、ＣＲは、暗号文Ｃの右３２ビットである。ＦＯ５９、ＣＲ９は、それぞれ（式２）のｈ３３に関連する９ビットである。
【００３９】
攻撃方程式（式５）中に存在する鍵は、図３（ａ）〜（ｃ）より、ＫＬ５＝（ＫＬ５１，ＫＬ５２）：３２ビット、及びＫＯ５＝（ｋ５１１，ｋ５１２，ｋ５１３，ｋ５２１，ｋ５２２，ｋ５２３）：５０ビットの合計８２ビットである。
【００４０】
式展開部１０３は、暗号文ＣＬ，ＣＲを元に、式生成部１０１によって生成された攻撃方程式（式５）を展開する。具体的には、攻撃方程式（式５）中に存在する暗号文ＣＬ, ＣＲ及び鍵ＫＬ５，ＫＯ５をそれぞれビット単位で考え、非特許文献１に記載されている置換テーブルＳ７，Ｓ９のブール展開式を用いて攻撃方程式（式５）を展開する。
【００４１】
（式５）の展開式をすべて書き下すことは紙面の都合上できないため、ここでは簡単な例を用いて説明する。２ビット入力、１ビット出力の関数Fについて入力をX=(x1, x2)、出力をY=(y1)とし、Y=F(X)= x1x2+x1+x2とする。このとき、F(C;K)において暗号文２ビット：C=(c1, c2)、及び鍵２ビット：K=(k1, k2)とし、X=C+K=(c1 + k1, c2 + k2)とする。式展開部１０３にF(C;K)が入力された場合、出力は、F(C;K)の展開式：c1c2 + c1k2 + c2k1 + k1k2 + c1 + k1 + c2 + k2となる。
【００４２】
式整理部１０５は、式展開部１０３によって展開された攻撃方程式を暗号文項で纏めることによって、展開された攻撃方程式を整理する。ここでは、式展開部１０３で用いた例にしたがって、式整理部１０５の処理を説明する。式整理部１０５に展開式：c1c2 + c1k2 + c2k1 + k1k2 + c1 + k1 + c2 + k2が入力されると、式整理部１０５は当該展開式を暗号文項(c1, c2)で以下のように纏める。
【００４３】
c1c2 + c1(1+k2)+ c2(1+k1) + k1k2 + k1 + k2
等価鍵置換部１０７は、暗号文Ｃの各次数項の係数において、鍵（具体的には、秘密鍵）の各次数項からなる多項式を新たな１次の等価鍵に置き換える。ここでは、式展開部１０３及び式整理部１０５で用いた例にしたがって、式整理部１０５の処理を説明する。
【００４４】
等価鍵置換部１０７は、c1c2 + c1(1+k2)+ c2(1+k1) + k1k2 + k1 + k2が入力されると、暗号文(c1, c2)の各次数項において、秘密鍵の各次数項からなる多項式を以下のように新たな１次の等価鍵（ek1，ek2）に置き換える。
【００４５】
c1c2 + c1ek1+ c2ek2 + ek0 
（暗号強度評価装置の動作）
次に、暗号強度評価装置１００の動作について説明する。図４は、暗号強度評価装置１００の動作フローを示す。
【００４６】
図４に示すように、ステップＳ１０において、暗号強度評価装置１００は、ある秘密鍵の下で５段構成のＫＡＳＵＭＩを用いて平文Ｐを暗号化し、暗号文Ｃを得る。さらに、暗号強度評価装置１００は、得られた暗号文Ｃを段関数（ＦＯ／ＦＬ関数）に入力し、秘密鍵を求めるために用いられる攻撃方程式（式５）を生成する。
【００４７】
ステップＳ２０において、暗号強度評価装置１００は、生成した攻撃方程式を展開する。具体的には、上述したように、暗号強度評価装置１００は、攻撃方程式（式５）中に存在する暗号文ＣＬ, ＣＲ及び鍵ＫＬ５，ＫＯ５をそれぞれビット単位で考え、非特許文献１に記載されている置換テーブルＳ７，Ｓ９のブール展開式を用いて攻撃方程式（式５）を展開する。
【００４８】
ステップＳ３０において、暗号強度評価装置１００は、暗号文ＣＬの１次項から高次項、及び暗号文ＣRの１次項でそれぞれ纏めることによって、展開した攻撃方程式を整理する。
【００４９】
整理した攻撃方程式において、暗号文Ｃの各次数項の係数は、秘密鍵の各次数項からなる多項式で表現される。
【００５０】
ステップＳ４０において、暗号強度評価装置１００は、当該秘密鍵の各次数項を含む多項式をそれぞれ新たな１次の等価鍵に置き換える。具体的には、上述したように、暗号強度評価装置１００は、秘密鍵の各次数項を含む多項式をそれぞれ等価鍵eki (i=0,1,2, ~)に置換える。
【００５１】
ステップＳ５０において、暗号強度評価装置１００は、上述したステップＳ１０〜Ｓ４０の処理によって整理された攻撃方程式を入力とし、当該式の中に存在する等価鍵を含む項の数、すなわち、未知項数を検出する。
【００５２】
具体的には、暗号強度評価装置１００は、当該式の中に存在する等価鍵eki (i=0,1,2, ~)を含む項をすべて数え、数えた項の数を未知項数として検出する。
【００５３】
ステップＳ６０において、暗号強度評価装置１００は、検出した未知項数を元に、ＫＬ５及びＫＯ５に関する等価鍵を求めるために必要となる選択平文Ｐ*の選択平文組数Ｍ及び計算量Ｔを見積もる。若しくは、暗号強度評価装置１００は、実際に等価鍵を求めることによって、ＫＡＳＵＭＩの暗号強度を評価する。
【００５４】
上述した処理が実行されると、攻撃方程式９ビット中に存在する最小の未知項数Ｌ*は６１１２となる。この場合、非特許文献３に示されている線形化手法の高速化を用いて等価鍵を推定、若しくは実際に等価鍵の値を求めるために必要となる選択平文組数Ｍは２２８．６であり、計算量Ｔは、２３０．４である。
【００５５】
（作用・効果）
表１は、上述した方法によって整理した攻撃方程式について、鍵（等価鍵）に関する未知項数を解析した結果を示す。
【表１】
2008109287.tif 000008
【００５６】
表１によれば、攻撃方程式９ビット中に存在する最小の未知項数Ｌ*は、６１１２である。また、上述したように、この場合、攻撃コスト、具体的には、等価鍵の値を求めるために必要となる選択平文組数Ｍは２２８．６であり、計算量Ｔは、２３０．４である。なお、ＫＡＳＵＭＩの３段目出力右３２ビット（ＨＲ３）において、ｈ３３に該当するビット位置は、表１に示すように１６−ｔｈ〜２４−ｔｈである。
【００５７】
つまり、非特許文献３に示されている線形化手法の高速化を用いた場合、未知項数Ｌが２６６９３であったのに対し、暗号強度評価装置１００によれば、未知項数Ｌ*が６１１２まで低減する。このため、計算量Ｔは、非特許文献３に示されている方法にしたがった場合と比較して、約１，０００倍も高速化される。
【００５８】
また、非特許文献４に示されているＩｎｔｅｇｒａｌ Ｃｒｙｐｔａｎａｌｙｓｉｓにしたがった場合、攻撃方程式の最大次数が４次である。このため、暗号文Ｃの１次項から４次項までのすべての項が存在すると仮定した場合、未知項数Ｌは、３２Ｃ４＝３５９６０となる。暗号強度評価装置１００によれば、攻撃方程式が展開され、実際に存在している未知項が検出されるため、非特許文献４に示されているＩｎｔｅｇｒａｌ Ｃｒｙｐｔａｎａｌｙｓｉｓにしたがった場合と比較して、未知項数を大幅に少なくすることできる。
【００５９】
すなわち、暗号強度評価装置１００によれば、暗号文項で整理された攻撃方程式において、暗号文Ｃの各次数項の係数である秘密鍵の各次数項を含む多項式が、新たな1次の等価鍵に置き換えられる。
【００６０】
このため、攻撃方程式中に存在する鍵（等価鍵）に関する項数が減少する。つまり、攻撃方程式を解くことによってＫＡＳＵＭＩなどの共通鍵ブロック暗号の暗号強度を評価する場合において、必要となる選択平文組数Ｍ及び計算量Ｔを低減させることができる。
【００６１】
（その他の実施形態）
上述したように、本発明の一実施形態を通じて本発明の内容を開示したが、この開示の一部をなす論述及び図面は、本発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態が明らかとなろう。
【００６２】
例えば、上述した実施形態では、ＫＡＳＵＭＩを例として説明したが、本発明は、他の共通鍵ブロック暗号、例えば、ＭＩＳＴＹ１やＡＥＳ（Advanced Encryption Standard）などにも適用することができる。
【００６３】
また、上述した暗号強度評価装置１００は、コンピュータにおいて実行可能なプログラムとしても勿論提供することができる。
【００６４】
このように、本発明は、ここでは記載していない様々な実施の形態などを含むことは勿論である。したがって、本発明の技術的範囲は、上述の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【００６５】
【図１】本発明の実施形態に係る暗号強度の評価対象暗号であるＫＡＳＵＭＩの内部構造を示す図である。
【図２】本発明の実施形態に係る暗号強度評価装置の機能ブロック図である。
【図３】本発明の実施形態に係る暗号強度評価装置において用いられるＫＡＳＵＭＩのさらに具体的な構造（一部）を示す図である。
【図４】本発明の実施形態に係る暗号強度評価装置の動作フロー図である。
【符号の説明】
【００６６】
１００…暗号強度評価装置、１０１…式生成部、１０３…式展開部、１０５…式整理部、１０７…等価鍵置換部、１０９…未知項数検出部、１１１…暗号強度評価部
【図１】
2008109287.tif 000009
【図２】
2008109287.tif 000010
【図３】
2008109287.tif 000011
【図４】
2008109287.tif 000012