説明

暗号強度評価装置、暗号強度評価方法及び暗号強度評価プログラム

【課題】攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な計算量をさらに低減することができる暗号強度評価装置、暗号強度評価方法及び暗号強度評価プログラムを提供する。
【解決手段】暗号強度評価装置100は、式生成部101によって生成された攻撃方程式を展開する式展開部103と、展開された攻撃方程式の中に存在する1次項から高次項までの暗号文項で纏めることによって展開式を整理する式整理部105とを備える。さらに、暗号強度評価装置100は、整理された攻撃方程式において、暗号文の各次数項の係数である秘密鍵の各次数項を含む多項式を、1次の等価鍵に置き換える等価鍵置換部107と、等価鍵に関する未知項数を検出する未知項数検出部109と、未知項数に基づいて等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる暗号強度評価部111とを備える。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は攻撃方程式を解くことによって、共通鍵ブロック暗号の強度を評価する暗号強度評価装置、暗号強度評価方法及び暗号強度評価プログラムに関するものである。
【背景技術】
【0002】
MISTY1をベースとして開発された共通鍵ブロック暗号として、KASUMIが知られている。KASUMIは第3世代移動通信システムの国際標準暗号として採用されている(非特許文献1参照)。
【0003】
KASUMIなどの共通鍵ブロック暗号に対する暗号強度の評価に関して、当該共通鍵ブロック暗号にしたがって暗号化された暗号文を正しく平文に復号することができる正規の秘密鍵(以下、正規秘密鍵)の決定に用いられる攻撃方程式を、線形化手法を用いて解く方法が知られている。
【0004】
線形化手法とは、攻撃方程式に含まれる鍵(秘密鍵や秘密鍵を元に生成された拡大鍵)に関する高次項を新たに独立な1次項と見なすことによって攻撃方程式を線形化し、得られた線形方程式を解くことによって正規秘密鍵を決定する手法である。
【0005】
KASUMIに対して高階差分(例えば、16階差分)を用いて攻撃する高階差分攻撃に関して、攻撃方程式の線形化手法を用いる方法が開示されている(非特許文献2参照)。さらに、当該線形化手法を高速化する方法も開示されている(非特許文献3参照)。
【0006】
また、近年では、高階差分攻撃に類似したIntegral Cryptanalysisが提案された(非特許文献4参照)。非特許文献4には、Integral特性を利用した攻撃方程式を解く際に、補間法(interpolation)を用いる手法が示されている。
【非特許文献1】3GPP、“3GPP TS 35.202 V3.1.1 (KASUMI Specification)”、2001年7月
【非特許文献2】南部俊一、金子敏信.「KASUMIの高階差分攻撃に関する一考察(III)」、基礎・境界ソサイエティ大会、A−7−6、2004年9月
【非特許文献3】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、2006年2月
【非特許文献4】Knudsen, Wagner、“Integral Cryptanalysis (Extended abstract)”、Fast Software Encryption 2002 (FSE2002), pp112-127、2002年
【発明の開示】
【発明が解決しようとする課題】
【0007】
上述した攻撃方程式の線形化手法では、鍵に関する高次項を新たに独立な1次の未知項と見なして攻撃方程式を線形化する。攻撃方程式を線形化する際、攻撃方程式の中に存在する鍵が多いほど、求める未知項数が多くなる。この結果、暗号の強度を評価するために必要となる計算量が増大するという問題があった。
【0008】
また、非特許文献4に示されている手法では、攻撃方程式の最大次数から見積もられ、存在し得るすべての未知項が数えられる。このため、実際に存在する未知項を数える場合と比較して未知項数が多くなる。この結果、暗号の強度を評価するために必要となる計算量が増大するという問題があった。
【0009】
そこで、本発明は、このような状況に鑑みてなされたものであり、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な計算量を低減することができる暗号強度評価装置、暗号強度評価方法及び暗号強度評価プログラムを提供することを目的とする。
【課題を解決するための手段】
【0010】
上述した問題を解決するため、本発明は、次のような特徴を有している。まず、本発明の第1の特徴は、共通鍵ブロック暗号(例えば、KASUMI)にしたがって暗号化された暗号文(暗号文C)、及び平文(平文P)を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式(式5)を解いて前記秘密鍵を求めるために必要となる選択平文組数(選択平文組数M)及び計算量(計算量T)を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価装置(暗号強度評価装置100)であって、前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成する式生成部(式生成部101)と、前記式生成部によって生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開する式展開部(式展開部103)と、前記式展開部によって展開された前記攻撃方程式の中に存在する1次項から高次項までの暗号文項(例えば、c1,c2)で纏めることによって前記展開式を整理する式整理部(式整理部105)と、前記式整理部によって整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、1次の等価鍵に置き換える等価鍵置換部(等価鍵置換部107)と、前記等価鍵置換部によって前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数(未知項数L*)を検出する未知項数検出部(未知項数検出部109)と、前記未知項数検出部によって検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価する暗号強度評価部(暗号強度評価部111)とを備えることを要旨とする。
【0011】
このような暗号強度評価装置によれば、暗号文項で整理された攻撃方程式において、暗号文の各次数項の係数である秘密鍵の各次数項を含む多項式が、新たな1次の等価鍵に置き換えられる。
【0012】
このため、攻撃方程式中に存在する鍵に関する項数が減少する。つまり、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な選択平文の組数及び計算量を低減させることができる。
【0013】
本発明の第2の特徴は、共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価方法であって、前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成するステップと、生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開するステップと、展開された前記攻撃方程式の中に存在する1次項から高次項までの暗号文項で纏めることによって前記展開式を整理するステップと、整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、1次の等価鍵に置き換えるステップと、前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出するステップと、検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価するステップとを備えることを要旨とする。
【0014】
本発明の第3の特徴は、共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価プログラムであって、コンピュータに、前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成する式生成処理と、生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開する式展開処理と、展開された前記攻撃方程式の中に存在する1次項から高次項までの暗号文項で纏めることによって前記展開式を整理する式整理処理と、整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、1次の等価鍵に置き換える等価鍵置換処理と、前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出する未知項数検出処理と、検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価する暗号強度評価処理とを実行させることを要旨とする。
【発明の効果】
【0015】
本発明の特徴によれば、攻撃方程式を解くことによって共通鍵ブロック暗号の暗号強度を評価する場合において、必要な計算量を低減することができる暗号強度評価装置、暗号強度評価方法及び暗号強度評価プログラムを提供することができる。
【発明を実施するための最良の形態】
【0016】
次に、本発明の実施形態について説明する。具体的には、本実施形態において用いられる共通鍵ブロック暗号であるKASUMIの内部構造、暗号強度評価装置の構成、暗号強度評価装置の動作、暗号強度評価装置の作用・効果、及びその他の実施形態について説明する。
【0017】
なお、以下の図面の記載において、同一または類似の部分には、同一または類似の符号を付している。ただし、図面は模式的なものであり、各寸法の比率などは現実のものとは異なることに留意すべきである。
【0018】
したがって、具体的な寸法などは以下の説明を参酌して判断すべきものである。また、図面相互間においても互いの寸法の関係や比率が異なる部分が含まれていることは勿論である。
【0019】
(KASUMIの内部構造)
KASUMIは、MISTY1をベースに開発された共通鍵ブロック暗号である。KASUMIの入出力長は64ビット、秘密鍵長は128ビットである。図1(a)〜(d)は、KASUMIの内部構造を示す。
【0020】
図1(a)は、KASUMIの全体構造を示す。図1(a)に示すように、KASUMIは、非線形関数のFO関数と、鍵依存線形関数のFL関数を交互に入れ替えた8段のFeistel型構造を有する。
【0021】
図1(b)は、FO関数の内部構造を示す。FO関数は、各段にFI関数が挿入された3段の変形Feistel型構造である。
【0022】
図1(c)は、FI関数の内部構造を示す。FI関数では、各段において、置換テーブル(S−box)S7、S9が交互に繰り返されている。S7の代数次数は3次、S9の代数次数は2次である。
【0023】
図1(d)は、FL関数の内部構造を示す。FL関数は、鍵のAND/OR演算、1ビット左シフトローテーション、及び排他的論理和からなる。なお、図1(a)〜(d)で示されているKASUMIは、3GPPにおいて規格されている構造から鍵(kij1〜kij4)の挿入位置が一部変更されている。この理由は、攻撃方程式の生成を容易にするためである。
【0024】
(暗号強度評価装置の構成)
次に、本実施形態に係る暗号強度評価装置100の構成について説明する。具体的には、暗号強度評価装置100の機能ブロック構成及び各機能の詳細について説明する。
【0025】
(1)機能ブロック構成
図2は、本実施形態に係る暗号強度評価装置100の機能ブロック構成を示す。図2に示すように、暗号強度評価装置100は、式生成部101、式展開部103、式整理部105、等価鍵置換部107、未知項数検出部109及び暗号強度評価部111を備える。
【0026】
暗号強度評価装置100は、KASUMIにしたがって暗号化された暗号文C、及び平文Pを暗号化する際に用いた秘密鍵を入力とするFO/FL関数を含む攻撃方程式(式5参照)を解いて、当該秘密鍵を求めるために必要となる選択平文組数M及び計算量Tを算出する。また、暗号強度評価装置100は、攻撃方程式を解いて当該秘密鍵を求めることによってKASUMIの暗号強度を評価する。
【0027】
式生成部101は、暗号文Cを入力し、秘密鍵を求めるために用いられる攻撃方程式を生成する。
【0028】
式展開部103は、式生成部101によって生成された攻撃方程式を入力とし、入力された攻撃方程式を展開する。
【0029】
式整理部105は、式展開部103によって展開された攻撃方程式の中に存在する1次項から高次項までの暗号文項で纏めることによって当該展開式を整理する。
【0030】
等価鍵置換部107は、式整理部105によって整理された攻撃方程式において、暗号文C(具体的には、暗号文C,C)の各次数項の係数である秘密鍵の各次数項を含む多項式を、1次の等価鍵に置き換える。
【0031】
未知項数検出部109は、等価鍵置換部107によって等価鍵に置き換えられた攻撃方程式において、当該等価鍵に関する未知項数を検出する。
【0032】
暗号強度評価部111は、未知項数検出部109によって検出された未知項数に基づいて、等価鍵を求めるために必要となる選択平文組数M及び計算量Tを見積もる、または当該等価鍵を求めることによってKASUMIの暗号強度を評価する。
【0033】
(2)機能詳細
次に、暗号強度評価装置100の機能の詳細、具体的には、攻撃方程式の生成、展開、展開された攻撃方程式の整理、及び等価鍵への置換について説明する。
【0034】
式生成部101は、(式1)に示すように、KASUMIのS-boxの入力サイズに合わせて平文Pを8つに分割する。
【数1】

【0035】
また、KASUMIの3段目出力のうち、右32ビットをHR3(図1(a)参照)と表記する。式生成部101は、S−boxの出力サイズに合わせて、HR3を(式2)のように分割する。ここで、図3(a)〜(c)は、h33に係る内部経路を示す。
【数2】

【0036】
このとき、(式3)に示す選択平文P*を用いた16階差分を計算すると、常に(式4)が成立する。
【数3】

【数4】

【0037】
式生成部101は、このような高階差分特性を用いて、(式5)に示すように、5段構成のKASUMIの鍵に関する攻撃方程式を生成する。以降、本実施形態では、5段構成のKASUMIを例として説明する。
【数5】

【0038】
(式5)において、Cは、選択平文P*を暗号化した暗号文Cの左32ビットである。同様に、Cは、暗号文Cの右32ビットである。FO、Cは、それぞれ(式2)のh33に関連する9ビットである。
【0039】
攻撃方程式(式5)中に存在する鍵は、図3(a)〜(c)より、KL=(KL51,KL52):32ビット、及びKO=(k511,k512,k513,k521,k522,k523):50ビットの合計82ビットである。
【0040】
式展開部103は、暗号文C,Cを元に、式生成部101によって生成された攻撃方程式(式5)を展開する。具体的には、攻撃方程式(式5)中に存在する暗号文CL, C及び鍵KL,KOをそれぞれビット単位で考え、非特許文献1に記載されている置換テーブルS7,S9のブール展開式を用いて攻撃方程式(式5)を展開する。
【0041】
(式5)の展開式をすべて書き下すことは紙面の都合上できないため、ここでは簡単な例を用いて説明する。2ビット入力、1ビット出力の関数Fについて入力をX=(x1, x2)、出力をY=(y1)とし、Y=F(X)= x1x2+x1+x2とする。このとき、F(C;K)において暗号文2ビット:C=(c1, c2)、及び鍵2ビット:K=(k1, k2)とし、X=C+K=(c1 + k1, c2 + k2)とする。式展開部103にF(C;K)が入力された場合、出力は、F(C;K)の展開式:c1c2 + c1k2 + c2k1 + k1k2 + c1 + k1 + c2 + k2となる。
【0042】
式整理部105は、式展開部103によって展開された攻撃方程式を暗号文項で纏めることによって、展開された攻撃方程式を整理する。ここでは、式展開部103で用いた例にしたがって、式整理部105の処理を説明する。式整理部105に展開式:c1c2 + c1k2 + c2k1 + k1k2 + c1 + k1 + c2 + k2が入力されると、式整理部105は当該展開式を暗号文項(c1, c2)で以下のように纏める。
【0043】
c1c2 + c1(1+k2)+ c2(1+k1) + k1k2 + k1 + k2
等価鍵置換部107は、暗号文Cの各次数項の係数において、鍵(具体的には、秘密鍵)の各次数項からなる多項式を新たな1次の等価鍵に置き換える。ここでは、式展開部103及び式整理部105で用いた例にしたがって、式整理部105の処理を説明する。
【0044】
等価鍵置換部107は、c1c2 + c1(1+k2)+ c2(1+k1) + k1k2 + k1 + k2が入力されると、暗号文(c1, c2)の各次数項において、秘密鍵の各次数項からなる多項式を以下のように新たな1次の等価鍵(ek1,ek2)に置き換える。
【0045】
c1c2 + c1ek1+ c2ek2 + ek0
(暗号強度評価装置の動作)
次に、暗号強度評価装置100の動作について説明する。図4は、暗号強度評価装置100の動作フローを示す。
【0046】
図4に示すように、ステップS10において、暗号強度評価装置100は、ある秘密鍵の下で5段構成のKASUMIを用いて平文Pを暗号化し、暗号文Cを得る。さらに、暗号強度評価装置100は、得られた暗号文Cを段関数(FO/FL関数)に入力し、秘密鍵を求めるために用いられる攻撃方程式(式5)を生成する。
【0047】
ステップS20において、暗号強度評価装置100は、生成した攻撃方程式を展開する。具体的には、上述したように、暗号強度評価装置100は、攻撃方程式(式5)中に存在する暗号文CL, C及び鍵KL,KOをそれぞれビット単位で考え、非特許文献1に記載されている置換テーブルS7,S9のブール展開式を用いて攻撃方程式(式5)を展開する。
【0048】
ステップS30において、暗号強度評価装置100は、暗号文Cの1次項から高次項、及び暗号文CRの1次項でそれぞれ纏めることによって、展開した攻撃方程式を整理する。
【0049】
整理した攻撃方程式において、暗号文Cの各次数項の係数は、秘密鍵の各次数項からなる多項式で表現される。
【0050】
ステップS40において、暗号強度評価装置100は、当該秘密鍵の各次数項を含む多項式をそれぞれ新たな1次の等価鍵に置き換える。具体的には、上述したように、暗号強度評価装置100は、秘密鍵の各次数項を含む多項式をそれぞれ等価鍵eki (i=0,1,2, ~)に置換える。
【0051】
ステップS50において、暗号強度評価装置100は、上述したステップS10〜S40の処理によって整理された攻撃方程式を入力とし、当該式の中に存在する等価鍵を含む項の数、すなわち、未知項数を検出する。
【0052】
具体的には、暗号強度評価装置100は、当該式の中に存在する等価鍵eki (i=0,1,2, ~)を含む項をすべて数え、数えた項の数を未知項数として検出する。
【0053】
ステップS60において、暗号強度評価装置100は、検出した未知項数を元に、KL及びKOに関する等価鍵を求めるために必要となる選択平文P*の選択平文組数M及び計算量Tを見積もる。若しくは、暗号強度評価装置100は、実際に等価鍵を求めることによって、KASUMIの暗号強度を評価する。
【0054】
上述した処理が実行されると、攻撃方程式9ビット中に存在する最小の未知項数L*は6112となる。この場合、非特許文献3に示されている線形化手法の高速化を用いて等価鍵を推定、若しくは実際に等価鍵の値を求めるために必要となる選択平文組数Mは228.6であり、計算量Tは、230.4である。
【0055】
(作用・効果)
表1は、上述した方法によって整理した攻撃方程式について、鍵(等価鍵)に関する未知項数を解析した結果を示す。
【表1】

【0056】
表1によれば、攻撃方程式9ビット中に存在する最小の未知項数L*は、6112である。また、上述したように、この場合、攻撃コスト、具体的には、等価鍵の値を求めるために必要となる選択平文組数Mは228.6であり、計算量Tは、230.4である。なお、KASUMIの3段目出力右32ビット(HR3)において、h33に該当するビット位置は、表1に示すように16−th〜24−thである。
【0057】
つまり、非特許文献3に示されている線形化手法の高速化を用いた場合、未知項数Lが26693であったのに対し、暗号強度評価装置100によれば、未知項数L*が6112まで低減する。このため、計算量Tは、非特許文献3に示されている方法にしたがった場合と比較して、約1,000倍も高速化される。
【0058】
また、非特許文献4に示されているIntegral Cryptanalysisにしたがった場合、攻撃方程式の最大次数が4次である。このため、暗号文Cの1次項から4次項までのすべての項が存在すると仮定した場合、未知項数Lは、32=35960となる。暗号強度評価装置100によれば、攻撃方程式が展開され、実際に存在している未知項が検出されるため、非特許文献4に示されているIntegral Cryptanalysisにしたがった場合と比較して、未知項数を大幅に少なくすることできる。
【0059】
すなわち、暗号強度評価装置100によれば、暗号文項で整理された攻撃方程式において、暗号文Cの各次数項の係数である秘密鍵の各次数項を含む多項式が、新たな1次の等価鍵に置き換えられる。
【0060】
このため、攻撃方程式中に存在する鍵(等価鍵)に関する項数が減少する。つまり、攻撃方程式を解くことによってKASUMIなどの共通鍵ブロック暗号の暗号強度を評価する場合において、必要となる選択平文組数M及び計算量Tを低減させることができる。
【0061】
(その他の実施形態)
上述したように、本発明の一実施形態を通じて本発明の内容を開示したが、この開示の一部をなす論述及び図面は、本発明を限定するものであると理解すべきではない。この開示から当業者には様々な代替実施の形態が明らかとなろう。
【0062】
例えば、上述した実施形態では、KASUMIを例として説明したが、本発明は、他の共通鍵ブロック暗号、例えば、MISTY1やAES(Advanced Encryption Standard)などにも適用することができる。
【0063】
また、上述した暗号強度評価装置100は、コンピュータにおいて実行可能なプログラムとしても勿論提供することができる。
【0064】
このように、本発明は、ここでは記載していない様々な実施の形態などを含むことは勿論である。したがって、本発明の技術的範囲は、上述の説明から妥当な特許請求の範囲に係る発明特定事項によってのみ定められるものである。
【図面の簡単な説明】
【0065】
【図1】本発明の実施形態に係る暗号強度の評価対象暗号であるKASUMIの内部構造を示す図である。
【図2】本発明の実施形態に係る暗号強度評価装置の機能ブロック図である。
【図3】本発明の実施形態に係る暗号強度評価装置において用いられるKASUMIのさらに具体的な構造(一部)を示す図である。
【図4】本発明の実施形態に係る暗号強度評価装置の動作フロー図である。
【符号の説明】
【0066】
100…暗号強度評価装置、101…式生成部、103…式展開部、105…式整理部、107…等価鍵置換部、109…未知項数検出部、111…暗号強度評価部

【特許請求の範囲】
【請求項1】
共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価装置であって、
前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成する式生成部と、
前記式生成部によって生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開する式展開部と、
前記式展開部によって展開された前記攻撃方程式の中に存在する1次項から高次項までの暗号文項で纏めることによって前記展開式を整理する式整理部と、
前記式整理部によって整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、1次の等価鍵に置き換える等価鍵置換部と、
前記等価鍵置換部によって前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出する未知項数検出部と、
前記未知項数検出部によって検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価する暗号強度評価部と
を備える暗号強度評価装置。
【請求項2】
共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価方法であって、
前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成するステップと、
生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開するステップと、
展開された前記攻撃方程式の中に存在する1次項から高次項までの暗号文項で纏めることによって前記展開式を整理するステップと、
整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、1次の等価鍵に置き換えるステップと、
前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出するステップと、
検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価するステップと
を備える暗号強度評価方法。
【請求項3】
共通鍵ブロック暗号にしたがって暗号化された暗号文、及び平文を暗号化する際に用いた秘密鍵を入力とする関数を含む攻撃方程式を解いて前記秘密鍵を求めるために必要となる選択平文組数及び計算量を算出する、または前記攻撃方程式を解いて前記秘密鍵を求めることによって前記共通鍵ブロック暗号の暗号強度を評価する暗号強度評価プログラムであって、
コンピュータに、
前記暗号文を入力し、前記秘密鍵を求めるために用いられる攻撃方程式を生成する式生成処理と、
生成された前記攻撃方程式を入力とし、入力された前記攻撃方程式を展開する式展開処理と、
展開された前記攻撃方程式の中に存在する1次項から高次項までの暗号文項で纏めることによって前記展開式を整理する式整理処理と、
整理された前記攻撃方程式において、前記暗号文の各次数項の係数である前記秘密鍵の各次数項を含む多項式を、1次の等価鍵に置き換える等価鍵置換処理と、
前記等価鍵に置き換えられた前記攻撃方程式において、前記等価鍵に関する未知項数を検出する未知項数検出処理と、
検出された前記未知項数に基づいて、前記等価鍵を求めるために必要となる選択平文組数と計算量とを見積もる、または前記等価鍵を求めることによって前記暗号強度を評価する暗号強度評価処理と
を実行させる暗号強度評価プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate


【公開番号】特開2008−109287(P2008−109287A)
【公開日】平成20年5月8日(2008.5.8)
【国際特許分類】
【出願番号】特願2006−289019(P2006−289019)
【出願日】平成18年10月24日(2006.10.24)
【出願人】(392026693)株式会社エヌ・ティ・ティ・ドコモ (5,876)
【出願人】(803000115)学校法人東京理科大学 (545)
【Fターム(参考)】