(57)【要約】【課題】攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、演算量を低減することができる暗号強度評価装置及び暗号強度評価方法を提供する。【解決手段】本発明に係る暗号強度評価装置１００は、共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密の鍵を入力とする関数を含む攻撃方程式を解いて秘密の鍵の値を求めるために必要となる演算量を算出する、または攻撃方程式を解いて秘密の鍵の値を求めることによって共通鍵ブロック暗号の暗号強度を評価する。暗号強度評価装置１００は、入力において秘密の鍵の単項を検出する単項検出部１０１と、検出された複数の単項を纏めた単項群を等価な等価鍵に置き換える等価鍵置換部１０３と、等価鍵と暗号文とを当該関数に入力し、攻撃方程式を展開する式展開部１０５と、攻撃方程式を用いて暗号強度を評価する暗号強度評価部１０７とを備える。【選択図】図１
2008011084.tif 000002
【特許請求の範囲】
【請求項１】
共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密の鍵を入力とする関数を含む攻撃方程式を解いて前記秘密の鍵の値を求めるために少なくとも必要となる演算量を算出する、または前記攻撃方程式を解いて前記秘密の鍵の値を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価装置であって、
前記入力において前記秘密の鍵の単項を検出する単項検出部と、
前記単項検出部によって検出された複数の前記単項を纏めた単項群を、前記単項群と等価な等価鍵に置き換える等価鍵置換部と、
前記等価鍵置換部によって置き換えられた前記等価鍵と、前記暗号文とを前記関数に入力し、前記攻撃方程式を展開する式展開部と、
前記式展開部によって展開された前記攻撃方程式を用いて、前記暗号文を平文に復号することができる正規復号鍵の値を求めるために少なくとも必要となる演算量を算出する、または前記正規復号鍵の値を求めることによって、前記暗号強度を評価する暗号強度評価部と
を備える暗号強度評価装置。
【請求項２】
共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密の鍵を入力とする関数を含む攻撃方程式を解いて前記秘密の鍵の値を求めるために少なくとも必要となる演算量を算出する、または前記攻撃方程式を解いて前記秘密の鍵の値を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価方法であって、
前記入力において前記秘密の鍵の単項を検出するステップと、
検出された複数の前記単項を纏めた単項群を、前記単項群と等価な等価鍵に置き換えるステップと、
前記等価鍵に置き換えるステップにおいて置き換えられた前記等価鍵と、前記暗号文とを前記関数に入力し、前記攻撃方程式を展開するステップと、
展開された前記攻撃方程式を用いて、前記暗号文を平文に復号することができる正規復号鍵の値を求めるために少なくとも必要となる演算量を算出する、または前記正規復号鍵の値を求めることによって前記暗号強度を評価するステップと
を備える暗号強度評価方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する暗号強度評価装置及び暗号強度評価方法に関する。
【背景技術】
【０００２】
ＭＩＳＴＹ１をベースとして開発された共通鍵ブロック暗号として、ＫＡＳＵＭＩが知られている。ＫＡＳＵＭＩは、第３世代移動通信システムの国際標準暗号として採用されている（例えば、非特許文献１）。
【０００３】
また、ＫＡＳＵＭＩなどの共通鍵ブロック暗号に対する暗号強度の評価に関して、当該共通鍵ブロック暗号にしたがって暗号化された暗号文を正しく平文に復号することができる正規な復号鍵（以下、正規復号鍵）の決定に用いられる攻撃方程式を、線形化手法を用いて解く方法が知られている。
【０００４】
線形化手法とは、攻撃方程式に含まれる鍵（秘密鍵や拡大鍵）に関する高次項を新たに独立な一次項と見なすことによって攻撃方程式を線形化し、線形化した攻撃方程式を解くことによって正規復号鍵を決定する手法である。
【０００５】
さらに、近年では、ＫＡＳＵＭＩに対して高階差分（例えば、１６階差分）を用いて攻撃する高階差分攻撃に関して、攻撃方程式の線形化手法による処理を高速化する方法が開示されている（例えば、非特許文献２）。
【非特許文献１】3GPP、“3GPP TS 35.202 V3.1.1 (KASUMI Specification)”、２００１年７月
【非特許文献２】南部俊一、杉尾信行、金子敏信、「ＫＡＳＵＭＩに対する攻撃方程式の効率的な解法」、２００５年暗号とその応用シンポジウム（SCIS2005）、pp1951-1956、２００５年１月
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した攻撃方程式の線形化手法による処理を高速化する方法には、次のような問題があった。すなわち、当該攻撃方程式は、処理負荷が過大となり、数式処理ソフトウェア（例えば、ＲＥＤＵＣＥ）で展開することが困難であった。
【０００７】
このため、当該攻撃方程式の展開の過程では、鍵に関する未知項数などに見積り値（上限値）を適用していた。このような見積り値は最適なパラメータとはなっておらず、暗号強度を評価するために必要な演算量が増大するといった問題があった。
【０００８】
そこで、本発明は、このような状況に鑑みてなされたものであり、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な演算量を低減することができる暗号強度評価装置及び暗号強度評価方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した問題を解決するため、本発明は、次のような特徴を有している。まず、本発明の第１の特徴は、共通鍵ブロック暗号（例えば、ＫＡＳＵＭＩ）にしたがって暗号化された暗号文（例えば、暗号文ｘ）、及び平文を暗号化する際に用いた秘密の鍵（例えば、鍵ｋ１，ｋ２）を入力とする関数（例えば、ＦＯ関数）を含む攻撃方程式を解いて前記秘密の鍵の値を求めるために少なくとも必要となる演算量を少なくとも算出する、または前記攻撃方程式を解いて前記秘密の鍵の値を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価装置（暗号強度評価装置１００）であって、前記入力において前記秘密の鍵の単項（例えば、鍵ｋ１，ｋ２）を検出する単項検出部（単項検出部１０１）と、前記単項検出部によって検出された複数の前記単項を纏めた単項群（ｋ１+ｋ２）群を、前記単項群と等価な等価鍵（等価鍵ＥＫ）に置き換える等価鍵置換部（等価鍵置換部１０３）と、前記等価鍵置換部によって置き換えられた前記等価鍵と、前記暗号文とを前記関数に入力し、前記攻撃方程式を展開する式展開部（式展開部１０５）と、前記式展開部によって展開された前記攻撃方程式を用いて、前記暗号文を平文に復号することができる正規復号鍵の値を求めるために少なくとも必要となる演算量を算出する、または前記正規復号鍵の値を求めることによって、前記暗号強度を評価する暗号強度評価部（暗号強度評価部１０７）とを備えることを要旨とする。
【００１０】
このような暗号強度評価装置によれば、攻撃方程式に入力において検出された単項を纏めた単項群が、当該単項群と等価な等価鍵に置き換えられる。また、攻撃方程式には、当該等価鍵と暗号文とが入力される。
【００１１】
つまり、攻撃方程式に入力される鍵に関する項数が低減するため、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な演算量を低減することができる。
【００１２】
本発明の第２の特徴は、共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密の鍵を入力とする関数を含む攻撃方程式を解いて前記秘密の鍵の値を求めるために少なくとも必要となる演算量を算出する、または前記攻撃方程式を解いて前記秘密の鍵の値を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価方法であって、前記入力において前記秘密の鍵の単項を検出するステップと、検出された複数の前記単項を纏めた単項群群を、前記単項群と等価な等価鍵に置き換えるステップと、前記等価鍵に置き換えるステップにおいて置き換えられた前記等価鍵と、前記暗号文とを前記関数に入力し、前記攻撃方程式を展開するステップと、展開された前記攻撃方程式を用いて、前記暗号文を平文に復号することができる正規復号鍵の値を求めるために少なくとも必要となる演算量を算出する、または前記正規復号鍵の値を求めることによって前記暗号強度を評価するステップとを備えることを要旨とする。
【発明の効果】
【００１３】
本発明の特徴によれば、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な演算量を低減することができる暗号強度評価装置及び暗号強度評価方法を提供することができる。
【発明を実施するための最良の形態】
【００１４】
次に、本発明の実施形態について説明する。なお、以下の図面の記載において、同一または類似の部分には、同一または類似の符号を付している。ただし、図面は模式的なものであり、各寸法の比率などは現実のものとは異なることに留意すべきである。
【００１５】
したがって、具体的な寸法などは以下の説明を参酌して判断すべきものである。また、図面相互間においても互いの寸法の関係や比率が異なる部分が含まれていることは勿論である。
【００１６】
（暗号強度評価装置の構成）
まず、図１〜図３を参照して、本実施形態に係る暗号強度評価装置１００の構成について説明する。なお、以下、本発明との関連がある部分について主に説明する。したがって、暗号強度評価装置１００は、暗号強度評価装置１００としての機能を実現する上で必須な、図示しない或いは説明を省略した機能ブロック（電源部など）を備える場合があることに留意されたい。
【００１７】
図１は、暗号強度評価装置１００の機能ブロック構成図である。暗号強度評価装置１００は、“ＫＡＳＵＭＩ”（共通鍵ブロック暗号）にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密の鍵を入力とする関数（具体的には、ＦＯ関数）を含む攻撃方程式を解いて当該秘密の鍵の値を求めるために、少なくとも必要となる演算量を算出することによって、ＫＡＳＵＭＩの暗号強度を評価することができる。
【００１８】
また、暗号強度評価装置１００は、攻撃方程式を解いて当該秘密の鍵の値を求めることによって、ＫＡＳＵＭＩの暗号強度を評価することもできる。
【００１９】
図２（ａ）〜（ｄ）は、本実施形態において用いられるＫＡＳＵＭＩの構造を示す。図２（ａ）は、ＫＡＳＵＭＩの全体構造を示す。図２（ｂ）〜（ｄ）は、ＦＯ関数、ＦＩ関数及びＦＬ関数の構造をそれぞれ示す。
【００２０】
ＫＡＳＵＭＩは、ＭＩＳＴＹ１をベースとして開発された共通鍵ブロック暗号である。ＫＡＳＵＭＩの入出力長は６４ビット、秘密鍵長は１２８ビットである。図２（ａ）〜（ｄ）に示すように、ＫＡＳＵＭＩは、非線形関数（ＦＯ関数）と、鍵依存線形関数（ＦＬ関数）を段関数とする８段のＦｅｉｓｔｅｌ構造となっている。
【００２１】
図２（ｂ）に示すように、ＦＯ関数は、３段の変形Ｆｅｉｓｔｅｌ構造であり、各段にはＦＩ関数が挿入される。
【００２２】
図２（ｃ）に示すように、ＦＩ関数は、４段の変形Ｆｅｉｓｔｅｌ構造であり、各段にはＳ−ｂｏｘ（Ｓ９，Ｓ７）が挿入される。Ｓ７の代数次数は３次、Ｓ９の代数次数は２次である。
【００２３】
なお、図２（ａ）〜（ｄ）に示すＫＡＳＵＭＩは、３ＧＰＰの規格（TS 35.202 V3.1.1 (KASUMI Specification)）において規定される構造から一部変更されている。また、添え字に関して、ｉ段目のＦＩ関数をＦＩｉ１〜ＦＩｉ３とし、各ＦＩ関数内において用いられる鍵を、ｋｉｊ１〜ｋｉｊ４とする。さらに、ＦＯ関数出力３２ビットをＳ−ｂｏｘの出力サイズに合わせて分割して、それぞれＬ７‖Ｌ９‖Ｒ７‖Ｒ９とし、以下のように表記する。
【数１】
2008011084.tif 000003
【００２４】
図１に示すように、暗号強度評価装置１００は、単項検出部１０１、等価鍵置換部１０３、式展開部１０５及び暗号強度評価部１０７を備える。
【００２５】
単項検出部１０１は、上述した関数（例えば、ＦＯ関数やＦＬ関数）などへの暗号文及び秘密の鍵の入力において、鍵の単項を検出する。また、単項検出部１０１は、検出した単項を等価鍵置換部１０３に出力する。
【００２６】
等価鍵置換部１０３は、単項検出部１０１によって検出された複数の単項を単項群として纏める。さらに、等価鍵置換部１０３は、当該単項群と等価な等価鍵に置き換える。
【００２７】
式展開部１０５は、等価鍵置換部１０３によって置き換えられた等価鍵と、暗号文とをＦＯ関数に入力し、攻撃方程式を展開する。
【００２８】
ここで、まず、等価鍵置換部１０３の機能について、簡略化したモデルを用いて説明する。例として、入力１次項に対し、１次項から３次項を出力する非線形関数Ｆがあるとする。当該非線形関数Ｆに、暗号文ｘ、及び鍵ｋ１，ｋ２が入力されると、出力は、（１式）に示すようになる。
【数２】
2008011084.tif 000004
【００２９】
（１式）に示すように、鍵ｋ１，ｋ２に関する項数は９である。ここで、暗号文ｘ及び鍵ｋ１，ｋ２に関する複数の単項を単項群として纏め、等価鍵ＥＫを（２式）のように定義すると、出力は、（３式）に示すようになる。
【数３】
2008011084.tif 000005
【数４】
2008011084.tif 000006
【００３０】
（３式）に示すように、ｋ１+ｋ２（単項群）を等価鍵ＥＫに置き換えることによって、鍵ｋ１，ｋ２に関する項数は３となる。このように、等価鍵に置き換えるによって、非線形関数（ＦＯ関数）に入力される鍵に関する項数を減少することができる。
【００３１】
本実施形態では、複数の単項を単項群として纏め、当該単項群と等価な等価鍵に置き換え、線形化手法を用いて攻撃方程式を解くことによってＫＡＳＵＭＩの暗号強度を評価する場合に必要となる演算量を低減する。
【００３２】
以下、より具体的に等価鍵置換部１０３及び式展開部１０５の機能について説明する。ＫＡＳＵＭＩ（にしたがって生成された暗号文）に対する攻撃コスト（平文組数及び演算量）を低減する効果的な選択平文を探索し、（４式）によって示される選択を用いて、５段構成のＫＡＳＵＭＩが攻撃可能なことが知られている（“A study on Higher Order Differential Attack of KASUMI”、proceedings of International Symposium on Information Theory and its Applications、pp.755-758, 2002参照）。
【数５】
2008011084.tif 000007
【００３３】
ｉ段目の出力をＨｉとする。また、Ｓ−ｂｏｘの出力サイズに合わせて、Ｈｉを（５式）のように定義し、（４式）に示した選択平文を用いた場合、（６式）が成立する。
【数６】
2008011084.tif 000008
【数７】
2008011084.tif 000009
【００３４】
このような高階差分特性を用いて、攻撃方程式（７式）を導出する。
【数８】
2008011084.tif 000010
【００３５】
（７式）には、ＫＯ５＝（ｋ５１１，ｋ５１２，ｋ５１３，ｋ５２１，ｋ５２２，ｋ５２３）：５０ビット、ＫＬ５＝（ＫＬ５１，ＫＬ５２）：３２ビットの合計８２ビットが存在する。このようなＫＡＳＵＭＩは、全数探索法と線形化手法とを併用することによって、２６３の（ＦＯ＋ＦＬ）関数演算量で攻撃可能である。
【００３６】
さらに、線形化手法の適用範囲を拡張し、攻撃方程式中に存在する８２ビットの鍵すべてを線形化手法で推定すると、未知項数Ｌは２６，６９３個となり、２４２．２の（ＦＯ＋ＦＬ）関数演算量が必要となる。
【００３７】
線形化手法を用いて攻撃方程式を解くことによって暗号強度を評価する処理を高速化するためには、上述した非特許文献２（「ＫＡＳＵＭＩに対する攻撃方程式の効率的な解法」、２００５年暗号とその応用シンポジウム（SCIS2005）、pp1951-1956）において記載されている要素数Ｄ（係数暗号文項数）、要素数Ｄ’及び未知項数Ｌ”を求める必要がある。
【００３８】
すなわち、当該処理を高速化するためには、要素数Ｄ、要素数Ｄ’及び未知項数Ｌ”（未知項数Ｌ−未知項数Ｌ’）を決定する必要がある。消去する未知項数Ｌ’によって要素数Ｄ’及び未知項数Ｌ”の値が変化するため、攻撃に必要となる演算量が変化する。
【００３９】
本実施形態では、式展開部１０５は、攻撃方程式（７式）を展開することによって、未知項数と、その係数暗号文項数とを解析し、当該演算量を低減することができる要素数Ｄ、要素数Ｄ’及び未知項数Ｌ”を決定する。
【００４０】
ここで、図３は、上述したｈ３３（６式参照）に係る内部経路を示す。式展開部１０５は、攻撃方程式（７式）において、暗号文ＣＬを、ＦＬ５の入力サイズに合わせて、以下のように変更する。
【数９】
2008011084.tif 000011
【００４１】
また、ＦＯ５の入力をＸＬ，ＸＲとする。ここで、ＸＬ，ＸＲは、ＦＬ関数内の鍵とのＡＮＤ演算、ＯＲ演算、及び１ビットのシフトローテーションを考慮すると、（８式）のように表すことができる。
【数１０】
2008011084.tif 000012
【００４２】
ここで、（ｉ）は、ビット位置を表す。ＦＯ５には、ＦＬ５内に存在する鍵の２次項が入力されるため、攻撃方程式には、最大８次項の鍵の未知項が存在する。そこで、本実施形態では、（９式）に示すように、鍵の２次項を含む部分を新たな変数（等価鍵ＥＫＬ（ｉ））に置き換える。
【数１１】
2008011084.tif 000013
【００４３】
等価鍵ＥＫＬ（ｉ）を用いることによって、ＦＯ５入力時の鍵の次数が１次となり、ＦＯ５出力後における鍵の未知項の次数は、最大４次となる。このように、ＦＯ関数（非線形関数）出力後の次数増加を抑制することによって、実際の未知項数に近い暗号強度の評価を行うことができる。
【００４４】
さらに、本実施形態では、ＸＬ（ｉ）に存在する鍵の単項ＫＬ５２（ｉ−１）を、次段の鍵ｋ５１１，ｋ５１２，ｋ５１３と合わせることによって、非線形関数出力後における鍵の未知項数の増加を抑制する。
【００４５】
暗号強度評価部１０７は、式展開部１０５によって展開された攻撃方程式を用いて、暗号文を平文に復号することができる鍵（正規復号鍵）を決定することによって、本実施形態に係るＫＡＳＵＭＩの暗号強度を評価する。
【００４６】
具体的には、暗号強度評価部１０７は、展開された攻撃方程式に基づいて、未知項数Ｌ及び要素数Ｄの値を演算する。表１は、暗号強度評価部１０７による演算結果を示す。
【表１】
2008011084.tif 000014
【００４７】
表２は、未知項数Ｌのうち、鍵のｎ次（ｎ＝１，２，３，４）以上からなる未知項を消去する未知項数Ｌ’とした際の要素数Ｄ’及び未知項数Ｌ”の詳細を示す。
【表２】
2008011084.tif 000015
【００４８】
暗号強度評価部１０７は、要素数Ｄ、要素数Ｄ’及び未知項数Ｌ”を用いて、攻撃方程式を解く際に必要となる選択平文組数Ｍ及び演算量Ｔ（（ＦＯ＋ＦＬ）関数演算量）を見積もる。ただし、すべての未知項数を消去してしまうと鍵が決定できないため、暗号強度評価部１０７は、表２において、未知項の次数が２次〜４次項までを対象として見積りを行う。
【００４９】
表３は、当該見積りの結果を示す。なお、選択平文組数Ｍ及び演算量Ｔの具体的な見積りは、非特許文献２に記載されている方法にしたがって行われる。
【表３】
2008011084.tif 000016
【００５０】
表３に示すように、攻撃方程式中に存在する未知項数Ｌ（２６，６９３個）のうち、３次項と４次項とからなる未知項２４，７７７個を消去すると演算量Ｔを最も低減することができる。
【００５１】
すなわち、表３に示すように、本実施形態に係るＫＡＳＵＭＩを、２２８．８６の選択平文組数Ｍと、２３３．５１の演算量Ｔによって攻撃可能となる。
【００５２】
さらに、暗号強度評価部１０７は、攻撃方程式を解いて、平文の暗号化に用いられる秘密の鍵（正規復号鍵）の値を求め、本実施形態に係るＫＡＳＵＭＩの暗号強度を評価することもできる。
【００５３】
（暗号強度評価装置の動作）
次に、暗号強度評価装置１００の動作について説明する。具体的には、暗号強度評価装置１００が、攻撃方程式を解いて、平文の暗号化に用いられる秘密の鍵の値を求め、本実施形態に係るＫＡＳＵＭＩの暗号強度を評価する動作フローについて説明する。
【００５４】
図４に示すように、ステップＳ１０において、暗号強度評価装置１００は、暗号文（例えば、ＣＬ）及び鍵（例えば、ＫＬ５１，ＫＬ５２）の攻撃方程式への入力において、鍵の単項を検出する（（８式）及び（９式）参照）。
【００５５】
ステップＳ２０において、暗号強度評価装置１００は、検出した単項を纏めた単項群と等価な等価鍵（等価鍵ＥＫＬ（ｉ））に置き換える。
【００５６】
ステップＳ３０において、暗号強度評価装置１００は、等価鍵及び暗号文をＦＯ／ＦＬ関数に入力する。
【００５７】
ステップＳ４０において、暗号強度評価装置１００は、等価鍵及び暗号文をＦＯ／ＦＬ関数に入力することによって、攻撃方程式（（７式）参照）を展開する。
【００５８】
ステップＳ５０において、暗号強度評価装置１００は、展開した攻撃方程式を用いて、暗号文を平文に復号することができる鍵（正規復号鍵）を決定することによって、本実施形態に係るＫＡＳＵＭＩの暗号強度を評価する。
【００５９】
具体的には、暗号強度評価装置１００は、展開した攻撃方程式を解いて平文の暗号化に用いられる秘密の鍵（正規復号鍵）を求めるために必要となる選択平文組数Ｍ及び演算量Ｔを算出することによりＫＡＳＵＭＩの暗号強度を評価したり、平文の暗号化に用いられる秘密の鍵（正規復号鍵）を求めることによりＫＡＳＵＭＩの暗号強度を評価したりする。
【００６０】
（変更例）
図４に示した動作フローでは、等価鍵及び暗号文をＦＯ／ＦＬ関数に１度だけ入力されるが、図２や図３に示したように、ＦＯ／ＦＬ関数の出力を繰り返しＦＯ／ＦＬ関数に入力するようにしてもよい。
【００６１】
この場合、図５に示すように、当該動作フローには、ステップＳ１４５の処理が追加される。ステップＳ１４５において、暗号強度評価装置１００は、ＦＯ／ＦＬ関数の出力を繰り返しＦＯ／ＦＬ関数に入力するか否かを判定する。なお、図５の動作フローにおいて、ステップＳ１１０〜Ｓ１５０の処理は、図４の動作フローにおけるステップＳ１０〜Ｓ５０の処理とそれぞれ同様である。
【００６２】
具体的には、図２や図３に示したＫＡＳＵＭＩの構造に基づいて、所定回数までＦＯ／ＦＬ関数の出力を繰り返しＦＯ／ＦＬ関数に入力するか否かを判定する。
【００６３】
ＦＯ／ＦＬ関数の出力を繰り返しＦＯ／ＦＬ関数に入力する場合（ステップＳ１４５のＹＥＳ）、暗号強度評価装置１００は、ステップＳ１１０からの処理を繰り返す。
【００６４】
一方、所定回数まで繰り返しを完了し、ＦＯ／ＦＬ関数の出力を繰り返しＦＯ／ＦＬ関数に入力しない場合（ステップＳ１４５のＮＯ）、暗号強度評価装置１００は、ステップＳ１５０の処理（図４のステップＳ５０と同様）を実行する。
【００６５】
（作用・効果）
上述した暗号強度評価装置１００によれば、攻撃方程式において検出された単項を纏めた単項群が、当該単項群と等価な等価鍵ＥＫＬ（ｉ）に置き換えられる。また、攻撃方程式には、等価鍵ＥＫＬ（ｉ）と暗号文（例えば、ＣＬ）とが入力される。
【００６６】
つまり、攻撃方程式に入力される鍵に関する項数が低減するため、攻撃方程式を解くことによってＫＡＳＵＭＩの暗号強度を評価する場合において、必要な演算量Ｔ（（ＦＯ＋ＦＬ）関数演算量）を低減することができる。
【００６７】
具体的には、上述したように、線形化手法のみを用いた場合、２４２．２の（ＦＯ＋ＦＬ）関数演算量が必要であった。本実施形態によれば、表３に示すように、２３３．５１の（ＦＯ＋ＦＬ）関数演算量に低減される。
【００６８】
（その他の実施形態）
上述したように、本発明の一実施形態を通じて本発明の内容を開示したが、この開示の一部をなす論述及び図面は、本発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態が明らかとなろう。
【００６９】
例えば、上述した実施形態では、ＫＡＳＵＭＩを例として説明したが、本発明は、他の共通鍵ブロック暗号、例えば、ＡＥＳ（Advanced Encryption Standard）やＣａｍｅｌｌｉａにも適用することができる。
【００７０】
上述した実施形態では、秘密の鍵を対象として処理を実行する形態としたが、当該秘密の鍵を鍵スケジューラに入力することによって得られる共通鍵ブロック暗号の拡大鍵を対象として、同様の処理を実行してもよい。
【００７１】
上述した実施形態では、ステップＳ２０において、暗号強度評価装置１００が、単項群を等価鍵ＥＫＬ（ｉ）に置き換える形態としたが、暗号強度評価装置１００が、表示装置（不図示）などを用いて、当該単項群をユーザに対して表示し、当該ユーザが等価鍵ＥＫＬ（ｉ）に置き換える形態としてもよい。さらに、上述した実施形態では、非線形関数であるＦＯ関数などに暗号文及び秘密の鍵を入力する形態としたが、用いる関数は、非線形関数に限らず、線形関数或いは両関数としてもよい。
【００７２】
また、上述した暗号強度評価装置１００は、コンピュータにおいて実行可能なプログラムとしても勿論提供することができる。
【００７３】
このように、本発明は、ここでは記載していない様々な実施の形態などを含むことは勿論である。したがって、本発明の技術的範囲は、上述の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【００７４】
【図１】本発明の実施形態に係る暗号強度評価装置の機能ブロック図である。
【図２】本発明の実施形態に係る暗号強度評価装置において用いられるＫＡＳＵＭＩの構造を示す図である。
【図３】本発明の実施形態に係る暗号強度評価装置において用いられるＫＡＳＵＭＩのさらに具体的な構造（一部）を示す図である。
【図４】本発明の実施形態に係る暗号強度評価装置の動作フロー図である。
【図５】本発明の実施形態に係る暗号強度評価装置の動作フロー図である。
【符号の説明】
【００７５】
１００…暗号強度評価装置、１０１…単項検出部、１０３…等価鍵置換部、１０５…式展開部、１０７…暗号強度評価部
【図１】
2008011084.tif 000017
【図２】
2008011084.tif 000018
【図３】
2008011084.tif 000019
【図４】
2008011084.tif 000020
【図５】
2008011084.tif 000021