Notice: Undefined variable: fterm_desc_sub in /mnt/www/biblio_conv.php on line 353
復号処理装置、情報処理装置、および復号処理方法、並びにコンピュータ・プログラム
説明

復号処理装置、情報処理装置、および復号処理方法、並びにコンピュータ・プログラム

【課題】飽和攻撃や代数的攻撃(XSL攻撃)などの攻撃に対する耐性を高めた共通鍵ブロック暗号を適用した復号処理構成を実現する。
【解決手段】共通鍵ブロック暗号を適用した復号処理において、ラウンド関数実行部に設定される非線形変換処理部としてのSボックスに、少なくとも2種類以上の複数の異なるSボックスを利用した構成とした。本構成により、飽和攻撃に対する耐性を高めることが可能となる。また、Sボックスのタイプとして、異なるタイプのものを混在させる本発明の一実施例の構成によれば、代数的攻撃(XSL攻撃)に対する耐性を高めることが可能となり、安全性の高い復号処理装置が実現される。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、復号処理装置、情報処理装置、および復号処理方法、並びにコンピュータ・プログラムに関する。さらに詳細には、例えば、共通鍵ブロック暗号を適用した復号処理を実行する復号処理装置、情報処理装置、および復号処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【0002】
昨今、ネットワーク通信、電子商取引の発展に伴い、通信におけるセキュリティ確保が重要な問題となっている。セキュリティ確保の1つの方法が暗号技術であり、現在、様々な暗号化手法を用いた通信が実際に行なわれている。
【0003】
例えばICカード等の小型の装置中に暗号処理モジュールを埋め込み、ICカードと、データ読み取り書き込み装置としてのリーダライタとの間でデータ送受信を行ない、認証処理、あるいは送受信データの暗号化、復号を行なうシステムが実用化されている。
【0004】
暗号処理アルゴリズムには様々なものがあるが、大きく分類すると、暗号化鍵と復号鍵を異なる鍵、例えば公開鍵と秘密鍵として設定する公開鍵暗号方式と、暗号化鍵と復号鍵を共通の鍵として設定する共通鍵暗号方式とに分類される。
【0005】
共通鍵暗号方式にも様々なアルゴリズムがあるが、その1つに共通鍵をベースとして複数の鍵を生成して、生成した複数の鍵を用いてブロック単位(64ビット,128ビットなど)のデータ変換処理を繰り返し実行する方式がある。このような鍵生成方式とデータ変換処理を適用したアルゴリズムの代表的なものが共通鍵ブロック暗号方式である。
【0006】
代表的な共通鍵ブロック暗号のアルゴリズムとしては,例えば過去に米国標準暗号であったDES(Data Encryption Standard)アルゴリズム,現在の米国標準暗号であるAES(Advanced Encryption Standard)アルゴリズムなどが知られている。
【0007】
このような、共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を繰り返し実行するラウンド関数実行部を有する暗号処理部と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジューリング部とによって構成される。鍵スケジューリング部は、秘密鍵であるマスター鍵(主鍵)に基づいて、まずビット数を増加させた拡大鍵を生成し、生成した拡大鍵に基づいて、暗号処理部の各ラウンド関数部で適用するラウンド鍵(副鍵)を生成する。
【0008】
このようなアルゴリズムを実行する具体的な構造として、線形変換部および非線形変換部を有するラウンド関数を繰り返し実行する構造が知られている。例えば代表的な構造にFeistel構造がある。Feistel構造は、データ変換関数としてのラウンド関数(F関数)の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。ラウンド関数(F関数)においては、線形変換処理および非線形変換処理が実行される。なお、Feistel構造を適用した暗号処理について記載した文献としては、例えば非特許文献1、非特許文献2がある。
【0009】
しかし、この共通鍵ブロック暗号処理の問題点として、暗号解析による鍵の漏洩がある。暗号解析による鍵の解析が容易であるということは、その暗号処理の安全性が低いということになり、実用上、大きな問題となる。
【先行技術文献】
【非特許文献】
【0010】
【非特許文献1】K. Nyberg, "Generalized Feistel networks", ASIACRYPT'96, SpringerVerlag, 1996, pp.91--104.
【非特許文献2】Yuliang Zheng, Tsutomu Matsumoto, Hideki Imai: On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses. CRYPTO 1989: 461-480
【発明の開示】
【発明が解決しようとする課題】
【0011】
本発明は、上記問題点に鑑みてなされたものであり、暗号解析の困難性を高め、安全性の高い共通鍵ブロック暗号アルゴリズムを適用した復号処理を実行する復号処理装置、情報処理装置、および復号処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【0012】
本発明の第1の側面は、
入力データを2以上の数で分割して得られる各データ系列に対し、Sボックスを含むF関数によるデータ変換処理をラウンド関数として各々実行する復号処理部を有し、
前記復号処理部は、入力データの系列と出力データの系列が同一であり、かつ隣り合う位置にあるF関数において対応するビット列に適用されるSボックスが異なる構成であり、
前記復号処理部は、
sビットの入出力をもつSボックスとして、
(1)タイプ1:拡大体GF(2)上の逆元写像:Y=X−1、または、べき乗関数Y=Xを利用したSボックス、
(2)タイプ2:t−bitの小さなS−boxを複数組み合わせて作り出されたSボックス、ただしt<sとする。
(3)タイプ3:ランダムに選択されたSボックス、
上記(1)〜(3)の3タイプのSボックス中、少なくとも2つ以上の異なるタイプのSボックスを利用した構成である復号処理装置にある。
【0013】
さらに、本開示の復号処理装置の一実施態様において、前記復号処理部は、前記Sボックスを、
(a)一部をタイプ1のSボックスとし、その他をタイプ2のSボックスとした構成、
(b)一部をタイプ1のSボックスとし、その他をタイプ3のSボックスとした構成、
(c)一部をタイプ2のSボックスとし、その他をタイプ3のSボックスとした構成、
(d)一部をタイプ1のSボックスとし、他の一部をタイプ2のSボックスとし、その他をタイプ3のSボックスとした構成、
上記(a)〜(d)のいずれかの構成を有することを特徴とする。
【0014】
さらに、本開示の復号処理装置の一実施態様において、前記復号処理部は、ラウンド関数実行部内に、処理対象データを分割した分割データ各々の非線形変換処理を実行する複数のSボックスを有し、1つのラウンドでは1種類のタイプのSボックスを利用し、ラウンド単位で異なるタイプのSボックスを利用した処理を実行する構成であることを特徴とする。
【0015】
さらに、本開示の復号処理装置の一実施態様において、前記復号処理部は、ラウンド関数実行部内に、処理対象データを分割した分割データ各々の非線形変換処理を実行する複数のSボックスを有し、1つのラウンドで、複数のタイプのSボックスを利用した構成であることを特徴とする。
【0016】
さらに、本開示の復号処理装置の一実施態様において、前記ラウンド関数実行部の各々に含まれるSボックスの種類および各Sボックスの数は、各F関数において同一の設定であることを特徴とする。
【0017】
さらに、本開示の復号処理装置の一実施態様において、前記復号処理部は、共通鍵暗号方式に従った復号処理を実行する構成であることを特徴とする。
【0018】
さらに、本開示の復号処理装置の一実施態様において、前記復号処理部は、共通鍵ブロック暗号方式に従った復号処理を実行する構成であることを特徴とする。
【0019】
さらに、本開示の第2の側面は、
入力データを2以上の数で分割して得られる各データ系列に対し、Sボックスを含むF関数によるデータ変換処理をラウンド関数として各々実行する復号処理部と、
前記復号処理部における復号処理の制御を行う制御部と、
前記制御部の実行する復号処理制御プログラムを格納したメモリを有し、
前記復号処理部は、入力データの系列と出力データの系列が同一であり、かつ隣り合う位置にあるF関数において対応するビット列に適用されるSボックスが異なる構成であり、
前記復号処理部は、
sビットの入出力をもつSボックスとして、
(1)タイプ1:拡大体GF(2)上の逆元写像:Y=X−1、または、べき乗関数Y=Xを利用したSボックス、
(2)タイプ2:t−bitの小さなS−boxを複数組み合わせて作り出されたSボックス、ただしt<sとする。
(3)タイプ3:ランダムに選択されたSボックス、
上記(1)〜(3)の3タイプのSボックス中、少なくとも2つ以上の異なるタイプのSボックスを利用した構成である情報処理装置にある。
【0020】
さらに、本開示の情報処理装置の一実施態様において、前記復号処理部は、前記Sボックスを、
(a)一部をタイプ1のSボックスとし、その他をタイプ2のSボックスとした構成、
(b)一部をタイプ1のSボックスとし、その他をタイプ3のSボックスとした構成、
(c)一部をタイプ2のSボックスとし、その他をタイプ3のSボックスとした構成、
(d)一部をタイプ1のSボックスとし、他の一部をタイプ2のSボックスとし、その他をタイプ3のSボックスとした構成、
上記(a)〜(d)のいずれかの構成を有することを特徴とする。
【0021】
さらに、本開示の情報処理装置の一実施態様において、前記復号処理部は、ラウンド関数実行部内に、処理対象データを分割した分割データ各々の非線形変換処理を実行する複数のSボックスを有し、1つのラウンドでは1種類のタイプのSボックスを利用し、ラウンド単位で異なるタイプのSボックスを利用した処理を実行する構成であることを特徴とする。
【0022】
さらに、本開示の情報処理装置の一実施態様において、前記復号処理部は、ラウンド関数実行部内に、処理対象データを分割した分割データ各々の非線形変換処理を実行する複数のSボックスを有し、1つのラウンドで、複数のタイプのSボックスを利用した構成であることを特徴とする。
【0023】
さらに、本開示の情報処理装置の一実施態様において、前記ラウンド関数実行部の各々に含まれるSボックスの種類および各Sボックスの数は、各F関数において同一の設定であることを特徴とする。
【0024】
さらに、本開示の情報処理装置の一実施態様において、前記復号処理部は、共通鍵暗号方式に従った復号処理を実行する構成であることを特徴とする。
【0025】
さらに、本開示の情報処理装置の一実施態様において、前記復号処理部は、共通鍵ブロック暗号方式に従った復号処理を実行する構成であることを特徴とする。
【0026】
さらに、本開示の第3の側面は、
復号処理装置において、復号処理を実行する復号処理方法であり、
復号処理部において、入力データを2以上の数で分割して得られる各データ系列に対し、Sボックスを含むF関数によるデータ変換処理をラウンド関数として各々実行する復号処理ステップを実行し、
前記復号処理ステップにおいて、入力データの系列と出力データの系列が同一であり、かつ隣り合う位置にあるF関数において対応するビット列に適用するSボックスを異なる設定のSボックスを適用したデータ変換処理を実行し、
前記復号処理ステップにおいて、
sビットの入出力をもつSボックスとして、
(1)タイプ1:拡大体GF(2)上の逆元写像:Y=X−1、または、べき乗関数Y=Xを利用したSボックス、
(2)タイプ2:t−bitの小さなS−boxを複数組み合わせて作り出されたSボックス、ただしt<sとする。
(3)タイプ3:ランダムに選択されたSボックス、
上記(1)〜(3)の3タイプのSボックス中、少なくとも2つ以上の異なるタイプのSボックスを利用したデータ変換処理を実行する復号処理方法にある。
【0027】
さらに、本開示の復号処理方法の一実施態様において、前記復号処理ステップは、共通鍵暗号方式または共通鍵ブロック暗号方式に従った復号処理を実行することを特徴とする。
【0028】
さらに、本開示の第4の側面は、
復号処理装置において、復号処理を実行させるコンピュータ・プログラムであり、
復号処理部において、入力データを2以上の数で分割して得られる各データ系列に対し、Sボックスを含むF関数によるデータ変換処理をラウンド関数として各々実行する復号処理ステップを実行させ、
前記復号処理ステップにおいて、入力データの系列と出力データの系列が同一であり、かつ隣り合う位置にあるF関数において対応するビット列に適用するSボックスを異なる設定のSボックスを適用したデータ変換処理を行なわせ、
前記復号処理ステップにおいて、
sビットの入出力をもつSボックスとして、
(1)タイプ1:拡大体GF(2)上の逆元写像:Y=X−1、または、べき乗関数Y=Xを利用したSボックス、
(2)タイプ2:t−bitの小さなS−boxを複数組み合わせて作り出されたSボックス、ただしt<sとする。
(3)タイプ3:ランダムに選択されたSボックス、
上記(1)〜(3)の3タイプのSボックス中、少なくとも2つ以上の異なるタイプのSボックスを利用したデータ変換処理を実行させるコンピュータ・プログラムにある。
【0029】
さらに、本開示のコンピュータ・プログラムの一実施態様において、前記復号処理ステップは、共通鍵暗号方式または共通鍵ブロック暗号方式に従った復号処理を実行させるステップであることを特徴とする。
【0030】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、CDやFD、MOなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【0031】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【0032】
本発明の一実施例の構成によれば、共通鍵ブロック暗号を適用した復号処理において、ラウンド関数実行部に設定される非線形変換処理部としてのSボックスに、少なくとも2種類以上の複数の異なるSボックスを利用した構成とした。本構成により、飽和攻撃に対する耐性を高めることが可能となる。また、Sボックスのタイプとして、異なるタイプのものを混在させる本発明の一実施例の構成によれば、代数的攻撃(XSL攻撃)に対する耐性を高めることが可能となり、安全性の高い復号処理装置が実現される。
【図面の簡単な説明】
【0033】
【図1】共通鍵ブロック暗号アルゴリズムの基本構成を示す図である。
【図2】図1に示す共通鍵ブロック暗号処理部E10の内部構成について説明する図である。
【図3】図2に示す暗号処理部12の詳細構成について説明する図である。
【図4】ラウンド関数実行部の一構成例としてのSPN構造ラウンド関数について説明する図である。
【図5】ラウンド関数実行部の一構成例としてのFeistel(フェイステル)構造について説明する図である。
【図6】ラウンド関数実行部の一構成例としての拡張Feistel構造について説明する図である。
【図7】非線形変換処理部の具体例について説明する図である。
【図8】線形変換処理部の具体例について説明する図である。
【図9】Feistel構造もしくは拡張Feistel構造の一般的構成例について説明する図である。
【図10】Feistel構造もしくは拡張Feistel構造において、異なるS−boxを配置した構成例について説明する図である。
【図11】異なるS−boxを配置することにより飽和攻撃に対する耐性の向上を実現した構成例について説明する図である。
【図12】異なるS−boxを配置することにより飽和攻撃に対する耐性の向上を実現した構成例について説明する図である。
【図13】異なるS−boxを配置することにより飽和攻撃に対する耐性の向上を実現した構成例について説明する図である。
【図14】異なるタイプのS−boxを配置することにより代数的攻撃(XSL攻撃)に対する耐性の向上を実現した構成例について説明する図である。
【図15】異なるタイプのS−boxを配置することにより代数的攻撃(XSL攻撃)に対する耐性の向上を実現した構成例について説明する図である。
【図16】異なるタイプのS−boxを配置することにより代数的攻撃(XSL攻撃)に対する耐性の向上を実現した構成例について説明する図である。
【図17】異なるタイプのS−boxを配置することにより代数的攻撃(XSL攻撃)に対する耐性の向上を実現した構成例について説明する図である。
【図18】異なるタイプのS−boxを配置することにより代数的攻撃(XSL攻撃)に対する耐性の向上を実現した構成例について説明する図である。
【図19】本発明に係る暗号処理を実行する暗号処理装置としてのICモジュールの構成例を示す図である。
【発明を実施するための形態】
【0034】
以下、本発明の復号処理装置、および復号処理方法、並びにコンピュータ・プログラムの詳細について説明する。説明は、以下の項目に従って行なう。
1.共通鍵ブロック暗号の概要
2.複数の異なるSボックスの配置により耐性を向上させた構成
(2A)S−boxを用いたFeistelもしくは拡張Feistel型暗号において2種類以上の異なるS−boxを配置することで飽和攻撃に対する耐性を向上させた構成
(2B)S−boxを用いたブロック暗号において、2種類以上の異なるS−boxを混在させることで代数的攻撃(XSL攻撃)に対する耐性を向上させた構成
(2C)S−boxを用いたFeistel暗号もしくは拡張Feistel型暗号において上記(2A),(2B)を同時に実現する構成
3.暗号処理装置の構成例
【0035】
[1.共通鍵ブロック暗号の概要]
まず、本発明の適用可能な共通鍵ブロック暗号の概要について説明する。本明細書において、共通鍵ブロック暗号(以下ではブロック暗号)は、以下に定義するものを指すものとする。
【0036】
ブロック暗号は平文Pと鍵Kを入力し、暗号文Cを出力する。平文と暗号文のビット長をブロックサイズと呼びここではnで示す。nは任意の整数値を取りうるが、通常、ブロック暗号アルゴリズムごとに、予め1つに決められている値である。ブロック長がnのブロック暗号のことをnビットブロック暗号と呼ぶこともある。
【0037】
鍵のビット長は、kで表す。鍵は任意の整数値を取りうる。共通鍵ブロック暗号アルゴリズムは1つまたは複数の鍵サイズに対応することになる。例えば、あるブロック暗号アルゴリズムAはブロックサイズn=128であり、ビット長k=128、またはk=192またはk=256の各種の鍵サイズに対応するという構成もありうる。
平文[P]、暗号文[C]、鍵[K]の各ビットサイズは、以下のように示される。
平文P:nビット
暗号文C:nビット
鍵K:kビット
【0038】
図1にkビットの鍵長に対応したnビット共通鍵ブロック暗号アルゴリズムEの図を示す。図1に示すように、共通鍵ブロック暗号処理部E10は、nビットの平文Pと、kビットの鍵Kを入力して、予め定められた暗号アルゴリズムを実行して、nビットの暗号文Cを出力する。なお、図1には平文から暗号文を生成する暗号化処理のみを示している.暗号文から平文を生成する復号処理は,一般的にはE10の逆関数が用いられる.ただし,暗号化処理部E10の構造によっては、復号処理においても、同様の共通鍵ブロック暗号処理部E10が適用でき,鍵の入力順などのシーケンスの変更によって復号処理が可能となる。
【0039】
図1に示す共通鍵ブロック暗号処理部E10の内部構成について、図2を参照して説明する。ブロック暗号は2つの部分に分けて考えることができる。ひとつは鍵Kを入力とし、ある定められたステップにより入力鍵Kのビット長を拡大して拡大鍵K'(ビット長k')を出力する鍵スケジューリング部11と、平文Pと鍵スケジューリング部11から入力する拡大鍵K'を受け取り、平文Pを入力して、拡大鍵K'を適用した暗号処理を実行して、暗号文Cを生成するためのデータの変換を実行する暗号処理部12である。なお,先に説明したように、暗号処理部12の構造によっては,暗号文を平文に戻すデータ復号処理にも暗号処理部12が適用可能な場合もある。
【0040】
次に、図2に示す暗号処理部12の詳細構成について図3を参照して説明する。暗号処理部12は、図3に示すように、ラウンド関数実行部20を適用したデータ変換を繰り返し実行する構成を持つ。すなわち、暗号処理部12は、ラウンド関数実行部20という処理単位に分割できる。ラウンド関数実行部20は入力として、前段のラウンド関数実行部の出力Xと、拡大鍵に基づいて生成されるラウンド鍵PKの2つのデータを受け取り、内部でデータ変換処理を実行して出力データXi+1を次のラウンド関数実行部に出力する。なお、第1ラウンドでは、入力は、平文または平文に対する初期化処理データである。また最終ラウンドの出力は暗号文となる。
【0041】
図3示す例では、暗号処理部12は、r個のラウンド関数実行部20を有し、r回のラウンド関数実行部におけるデータ変換を繰り返して暗号文を生成する構成となっている。ラウンド関数の繰り返し回数をラウンド数と呼ぶ。図に示す例では、ラウンド数はrとなる。
【0042】
各ラウンド関数実行部の入力データXは暗号化途中のnビットデータであり、あるラウンドにおけるラウンド関数の出力Xi+1が次のラウンドの入力として供給される。各ラウンド関数実行部のもう一つの入力データは鍵スケジュールから出力された拡大鍵のK'に基づくデータが用いられる。この各ラウンド関数実行部に入力され、ラウンド関数の実行に適用される鍵をラウンド鍵と呼ぶ。図で、iラウンドに適用するラウンド鍵をRKとして示している。拡大鍵K'は、例えば、rラウンド分のラウンド鍵RK〜RKの連結データとして構成される。
【0043】
図3に示す構成は、暗号処理部12の入力側から見て1ラウンド目の入力データをXとし、i番目のラウンド関数から出力されるデータをX、ラウンド鍵をRKとして示した暗号処理部12の構成である。なお,この暗号処理部12の構造によっては,例えば,適用するラウンド鍵の適用シーケンスを,暗号化処理と逆に設定し,暗号文を暗号処理部12に入力することで平文を出力する構成にできる。
【0044】
図3に示す暗号処理部12のラウンド関数実行部20は、さまざまな形態をとりうる。ラウンド関数はその暗号アルゴリズムが採用する構造(structure)によって分類できる。代表的な構造として、
(ア)SPN(Substitution Permutation Network)構造、
(イ)Feistel構造、
(ウ)拡張Feistel構造、
がある。以下、これらの具体的構成について、図4〜図6を参照して説明する。
【0045】
(ア)SPN構造ラウンド関数
まず、図4を参照して、ラウンド関数実行部20の一構成例としてのSPN構造ラウンド関数について説明する。SPN構造ラウンド関数実行部20aは、非線形変換層(S層)と線形変換層(P層)を接続したいわゆるSP型の構成を有する。図4に示すように、nビットの入力データすべてに対して、ラウンド鍵との排他的論理和(EXOR)演算を実行する排他的論理和演算部21、排他的論理和演算部21の演算結果を入力し、入力データの非線形変換を実行する非線形変換処理部22、非線形変換処理部22における非線形変換処理結果を入力し、入力データに対する線形変換処理を実行する線形変換処理部23などによって構成される。線形変換処理部23の線形変換処理結果が、次のラウンドに出力される。最終ラウンドでは暗号文となる。なお、図4に示す例では、排他的論理和演算部21、非線形変換処理部22、線形変換処理部23の処理順を示しているが、これらの処理部の順番は、限定されるものではなく、他のシーケンスで処理を行なう構成としてもよい。
【0046】
(イ)Feistel構造
次に、図5を参照してラウンド関数実行部20の一構成例としてのFeistel(フェイステル)構造について説明する。Feistel構造は、図5に示すように、前ラウンドからの入力(第1ラウンドでは入力文)であるnビットの入力データをn/2ビットの2つのデータに分割して、各ラウンドにおいて入れ替えながら処理を実行する。
【0047】
Feistel構造を持つラウンド関数実行部20bを適用した処理においては、図に示すように、一方のn/2ビットデータとラウンド鍵とがF関数部30に入力される。F関数部30は、上述したSPN構造と同様、非線形変換層(S層)と線形変換層(P層)を接続したいわゆるSP型の構成を有する。
【0048】
前ラウンドからのn/2ビットデータとラウンド鍵とがF関数部30の排他的論理和演算部31に入力され排他的論理和(EXOR)処理がなされる。さらに、この結果データを非線形変換処理部32に入力して非線形変換を実行し、さらに、この非線形変換結果が線形変換処理部33に入力され線形変換が実行される。この線形変換結果が、F関数処理結果データとして出力する。
【0049】
さらに、このF関数出力と、前ラウンドから入力するもう1つのn/2ビット入力とを、排他的論理和演算部34に入力し、排他的論理和演算(EXOR)を実行して、実行結果を、次のラウンドにおけるF関数の入力として設定される。なお、図に示す第iラウンドにおけるF関数入力に設定されたn/2ビットは次のラウンドのF関数出力との排他的論理和演算に適用される。このように、Feistel構造は、各ラウンドにおいて入力を交互に入れ替えながらF関数を適用したデータ変換処理を実行する。
【0050】
(ウ)拡張Feistel構造
次に、図6を参照してラウンド関数実行部20の一構成例としての拡張Feistel構造について説明する。先に、図5を参照して説明したFeistel構造は、nビットの平文を2つに分割してn/2ビットずつに区分して処理を実行していた。すなわち、分割数:d=2とした処理である。なお、この分割数は、データ系列数とも呼ばれる。
【0051】
拡張Feistel構造では、このデータ系列数(分割数)dを2以上の任意の整数とした設定である。データ系列数(分割数)dの値に応じたさまざまな拡張Feistel構造を定義することができる。図6に示す例では、データ系列数(分割数)d=4であり、各系列に対してn/4ビットのデータが入力される。各ラウンドでは、1つ以上のラウンド関数としてのF関数が実行される。図に示す例は、1ラウンドにおいて2つのF関数部によるラウンド演算を行なう構成例である。
【0052】
F関数部41,42の構成は、先に図5を参照して説明したF関数部30の構成と同様であり、ラウンド鍵と入力値との排他的論理和演算と、非線形変換処理、線形変換処理を実行する構成となっている。なお、各F関数部に入力するラウンド鍵は、入力ビットとビット数が一致するように調整される。図に示す例では、各F関数部41,42に入力するラウンド鍵は、n/4ビットとなる。これらの鍵は、拡大鍵を構成するラウント鍵をさらにビット分割して生成する。なお、データ系列数(分割数)をdとしたとき、各系列に入力されるデータはn/dビットであり、各F関数に入力する鍵のビット数もn/dビットに調整される。
【0053】
なお、図6に示す拡張Feistel構造では、データ系列数(分割数)をdとして、各ラウンドにおいてd/2のF関数を並列に実行する構成例であるが、拡張Feistel構造は、各ラウンドにおいて、1つ以上d/2以下のF関数を実行する構成が可能である。
【0054】
図4〜図6を参照して説明したように、共通鍵ブロック暗号における暗号処理部12のラウンド関数実行部20は、
(ア)SPN(Substitution Permutation Network)構造、
(イ)Feistel構造、
(ウ)拡張Feistel構造、
これらの構造をとり得る。これらのラウンド関数実行部は、いずれも非線形変換層(S層)と線形変換層(P層)を接続したいわゆるSP型の構成を有する。すなわち、非線形変換処理を実行する非線形変換処理部と、線形変換処理を実行する線形変換処理部とを有する。以下、これらの変換処理構成について説明する。
【0055】
(非線形変換処理部)
非線形変換処理部の具体例について、図7を参照して説明する。図7に示すように、非線形変換処理部50は、具体的には、Sボックス(S−box)51と呼ばれるsビット入力sビット出力の非線形変換テーブルがm個並んだものであり、msビットの入力データがsビットずつ分割されてそれぞれ対応するSボックス(S−box)51に入力されデータが変換される。各Sボックス51では、例えば変換テーブルを適用した非線形変換処理が実行される。
【0056】
入力されるデータのサイズが大きくなると実装上のコストが高くなる傾向がある。それを回避するために、図7に示すように、処理対象データXを複数の単位に分割し、それぞれに対して、非線形変換を施す構成がとられることが多い。例えば入力サイズをmsビットとしたとき、sビットずつのm個のデータに分割して、m個のSボックス(S−box)51それぞれに対してsビットを入力し、例えば変換テーブルを適用した非線形変換処理を実行して、これらの各Sビット出力m個を合成してmsビットの非線形変換結果を得る。
【0057】
(線形変換処理部)
線形変換処理部の具体例について、図8を参照して説明する。線形変換処理部は、入力値、例えば、Sボックスからの出力データであるmsビットの出力値を入力値Xとして入力し、この入力に対して線形変換を施しmsビットの結果を出力する。線形変換処理は、例えば、入力ビット位置の入れ替え処理などの線形変換処理を実行して、msビットの出力値Yを出力する。線形変換処理は、例えば、入力に対して、線形変換行列を適用して入力ビット位置の入れ替え処理を行なう。この行列の一例が図8に示す線形変換行列である。
【0058】
線形変換処理部において適用する線形変換行列の要素は拡大体:GF(2)の体の要素やGF(2)の要素など、一般的にはさまざまな表現を適用した行列として構成できる。図8は、msビット入出力をもち、GF(2)の上で定義されるm×mの行列により定義される線形変換処理部の1つの構成例を示すものである。
【0059】
[2.複数の異なるSボックスの配置により耐性を向上させた構成]
上述したように、共通鍵ブロック暗号は、ラウンド関数の繰り返しによる暗号処理を行なう構成である。この共通鍵ブロック暗号処理の問題点として、暗号解析による鍵の漏洩がある。暗号解析による鍵の解析が容易であるということは、その暗号処理の安全性が低いということになり、実用上、大きな問題となる。以下では、複数の異なるS−box(Sボックス)を配置することで耐性を向上させた暗号処理構成について説明する。
【0060】
図7を参照して説明したように、ラウンド関数実行部に含まれる非線形変換処理部は、非線形変換処理を実行する複数のS−box(Sボックス)によって構成される。従来、これらのS−boxはすべて共通の非線形変換処理用のテーブルを適用し、各Sボックスにおいて共通の非線形変換処理を行なう構成となっていた。
【0061】
本発明では、このS−boxの共通性に起因する脆弱性、すなわち、鍵解析などの暗号解析である攻撃に対する弱さに着目し、複数の異なるS−boxの配置により耐性を向上させた構成を提案する。
【0062】
以下、本発明の実施例として、以下の3つの実施例について、順次、説明する。
(2A)S−boxを用いたFeistelもしくは拡張Feistel型暗号において2種類以上の異なるS−boxを配置することで飽和攻撃に対する耐性を向上させた構成
(2B)S−boxを用いたブロック暗号において、2種類以上の異なるS−boxを混在させることで代数的攻撃(XSL攻撃)に対する耐性を向上させた構成
(2C)S−boxを用いたFeistel暗号もしくは拡張Feistel型暗号において上記(2A),(2B)を同時に実現する構成
【0063】
(2A)S−boxを用いたFeistelもしくは拡張Feistel型暗号において2種類以上の異なるS−boxを配置することで飽和攻撃に対する耐性を向上させた構成
【0064】
まず、S−boxを用いたFeistelもしくは拡張Feistel型暗号において2種類以上の異なるS−boxを配置することで飽和攻撃に対する耐性を向上させた構成について説明する。
【0065】
(2A−1.飽和攻撃の概要)
まず、最初にブロック暗号に対する攻撃として知られる飽和攻撃について説明する。飽和攻撃には複数のタイプがある。第1のタイプは、平文の特定のバイト位置について、256種類の値を変化させながら入力した場合、数ラウンド分のラウンド変換処理後に、出力値の特定のバイト位置に256種類の値がすべて現れるという性質を利用した攻撃法である。
また、飽和攻撃の別の形態の攻撃としては、数ラウンド分のラウンド変換後の特定のバイト位置に表れる値の総和を計算すると必ず0になるという性質を利用した攻撃手法である。
【0066】
例えば、ラウンド関数を実行する共通鍵ブロック暗号処理装置に対して入力する256種類の平文P〜P255として、
=(0,0,0,0,0,0,0,0)
=(0,0,0,0,0,0,0,1)
: :
255=(0,0,0,0,0,0,0,255)
これらの平文P〜P255を、順次入力する。なお、上記表記において、各[0]は1バイトデータの0を示す。
【0067】
これらの平文P〜P255を、順次入力した場合に、ある特定のラウンド分のデータ変換処理が終了した後の出力値を以下のようにC〜C255とする。
=(c,?,?,?,?,?,?,?)
=(c,?,?,?,?,?,?,?)
: :
255=(c255,?,?,?,?,?,?,?)
上記出力中[?]は、いかなるビット値でも構わない。
【0068】
これらの出力C〜C255には、上記のように、特定のバイト位置(上記例では最初のバイト位置)に256種類の値c〜c255がすべて現れるという性質がある。このように、0から255までの値が、順番は問わずに、それぞれ一回ずつ必ず現れることが予め分かっている場合、その性質を利用した攻撃をすることが可能である。入力値を、順次変更して出力値を解析することで、ラウンド鍵の推定を行なうことが可能であることが知られている。
【0069】
さらに出力C〜C255に含まれる特定のバイト位置の値:c〜c255を総和(EXOR)した場合に0となる場合、この性質を利用した攻撃(暗号解析)が可能となる。このように、256種類の平文P〜P255を順次、入力して、特定バイト位置の出力を解析することで、鍵の推定が可能となる。
【0070】
飽和攻撃は、このようにラウンド関数部の変換結果に、上記のような特定の規則をもたらす出力、すなわち、
256種類の値c〜c255がすべて出現する。あるいは、
特定のバイト位置の値:c〜c255を総和(EXOR)した場合に0となる。
このような規則性のある出力が発生する場合に、これらの規則性に基づいて実行する攻撃(解析)手法である。
【0071】
従って、暗号の設計の段階で、このような特異な出力をラウンド関数部の出力として発生させない構成とすることが、飽和攻撃に対して強い暗号とするために有効である。なお、この飽和攻撃は、バイト単位(8ビット)のみの解析に限らず、任意のビット長に対して同様の性質を利用した攻撃が可能となる。
【0072】
(2A−2)Feistel構造、または拡張Feistel構造を適用した暗号処理における問題点
次に、Feistel構造、または拡張Feistel構造を適用した暗号処理における問題点について検討する。
【0073】
Feistel構造、または拡張Feistel構造については、先に、図5、図6を参照して説明したように、いずれもSP型の非線形変換処理部と、線形変換処理部を有するF関数部を適用したラウンド演算を繰り返し実行する構成である。Feistel構造は、データ系列数(分割数)が2に限定されるが、拡張Feistel構造では、データ系列数(分割数)が2以上の任意の数に設定される点が異なる。
【0074】
以下では、Feistel構造、または拡張Feistel構造を適用した暗号処理におけるラウンド関数の実行部であるF関数内の非線形変換処理部にS−boxを利用した構成を想定する。S−boxは、先に図7を参照して説明したように、非線形変換処理部に入力されるmsビットデータをm分割したsビットデータそれぞれについて、例えば非線形変換用テーブルを適用した非線形変換処理を実行する。
【0075】
先に、説明したように、旧来のブロック暗号におけるラウンド関数の実行に適用するF関数は、各ラウンドにおいて繰り返し同じものが利用される。このような同じF関数を各ラウンドに設定したFeistel構造、または拡張Feistel構造では、前述した飽和攻撃にさらされ易くなる。この理由について、図9を参照して説明する。
【0076】
図9は、Feistel構造もしくは拡張Feistel構造の一部分を切り出した構成を示す図である。すなわち、図9には、Feistel構造もしくは拡張Feistel構造を持つ暗号構成に含まれる2つのラウンド関数実行部、すなわち、F関数101,102を示している。この2つのF関数101,102は入力データの系列(x)と出力データの系列(y)が同一であり、かつ上下に隣り合う位置にあるF関数である。
【0077】
2つのF関数101,102は、ラウンド鍵との排他的論理和演算部、非線形変換処理部、線形変換処理部によって構成されている。本処理例では、F関数101,102は、32ビット入出力処理を行う構成であり、非線形変換処理部は、4つのS−boxによって構成され、それぞれのS−boxは、8ビット入出力を行なう。
【0078】
図9に示すA〜Jは、様々なデータを示す。すなわち、
A:先行F関数101に対する入力
B:先行F関数101の出力
C:後続F関数102の入力
D:後続F関数102の出力
E:先行F関数101の出力Bに対する排他的論理和演算データ
F:データAに対する排他的論理和演算データ
G:データBとデータEとの排他的論理和演算結果
H:データDとデータGとの排他的論理和演算結果
I:先行F関数101に対して入力するラウンド鍵
J:後続F関数102に対して入力するラウンド鍵
これらの各データを示している。
【0079】
以降の説明で、各F関数101,102において処理される32ビットデータをバイト単位(8ビット)で分割して示す場合、例えばデータAが32ビットデータである場合、各1バイト(8ビット)データA[0],A[1],A[2],A[3]の連結データとして、
A=A[0]|A[1]|A[2]|A[3]
上記のように表現する。
【0080】
ここで、図9に示す暗号化処理構成に対して入力する平文として256種類のデータ、例えば、
=(0,0,0,0)
=(1,0,0,0)
: :
255=(255,0,0,0)
これらの平文P〜P255を、順次入力すると仮定する。なお、上記表記において、各[0],[1]〜[255]は1バイトデータを示す。
【0081】
この入力値を、図9に示す先行F関数101に対する入力データAとする。データAは上記のように、256種類のデータを観察したときに第1番目のバイトA[0]に0から255までの256種類の全ての値が現れ、それ以外のバイト位置はつねに同じ値で固定されていたものとする。(これは飽和攻撃を試みる攻撃者が平文入力を制御してこのような状況を作り出すことがあるために想定する。)
【0082】
さらにデータAに対する排他的論理和演算データFの値が、上記256種類のデータAの順次入力処理の間、常に固定であったと仮定すると、後続F関数102の入力データCの第一番目のバイトC[0]もまた0から255までの256種類の全ての値が現れ、それ以外のバイト位置はつねに同じ値で固定されることが保証される。
【0083】
このとき、
I:先行F関数101に対して入力するラウンド鍵
J:後続F関数102に対して入力するラウンド鍵
および、
F:データAに対する排他的論理和演算データ
これらの各データの値の組み合わせによっては、常に以下の式が成立することが発生し得る。すなわち、
A[0](EXOR)I[0]=C[0](EXOR)J[0]
上記式が成立することがありうる。
なお、(EXOR)は排他的論理和演算を示し、
A[0](EXOR)I[0]は、データA[0]とデータI[0]との排他的論理和演算、
C[0](EXOR)J[0]は、データC[0]とデータJ[0]との排他的論理和演算、
を示している。
【0084】
式:A[0](EXOR)I[0]=C[0](EXOR)J[0]
この式が意味することは2つのF関数101,102における2つのS−boxに入力される値がつねに同じ値となることに他ならない。これらS−boxはすべて同じ非線形変換処理を実行しており、同じ入力値に対しては同じ出力値を出力する。従って、2つのF関数101,102における2つのS−boxの出力が常に同じになる。各F関数101,102では、この同じS−box出力が、線形変換処理部の行列により線形変換されて右側のデータ系列(y)の排他的論理和演算部に出力される。図に示す排他的論理和演算部111,112である。
【0085】
この2つのF関数101,102から排他的論理和演算部111,112に出力される値B,Dは特定の差分値Δをもつ。すなわち、
B(EXOR)Δ=D
となる。
このとき、排他的論理和演算部111では、
G=B(EXOR)E
の演算によりデータGが算出され、
排他的論理和演算部112では、
H=G(EXOR)D
が実行される。
上記式、H=G(EXOR)Dは、G=B(EXOR)E、B(EXOR)Δ=Dであるので、
H=B(EXOR)E(EXOR)B(EXOR)Δ
=E(EXOR)Δとなる。
【0086】
すなわち、固定の差分値をもつ値同士の排他的論理和演算結果は、固定値Δとなるので、結果として、
H=B(EXOR)E(EXOR)B(EXOR)Δ
=Δ(EXOR)E
=E(EXOR)Δ
となる。
【0087】
すなわち、排他的論理和演算部112の出力HがデータEに固定された値Δが排他的論理和されただけとなり、ラウンド関数(F関数)を2段分実行したのにもかかわらず、データの攪拌がされないという結果となる。この性質を利用すると、後続のラウンドのラウンド鍵を推定することが容易となる。すなわち、後続のラウンドが存在しても、そのラウンドを仮に設定した鍵を用いて復号してHのデータまで復号したときに、この性質が現れているか否かをチェックすることにより、仮に用いた鍵が正しいものかそうでないものかを確率的に判断することが可能となる。つまりラウンド鍵の推定が可能となり、飽和攻撃による解析を可能にしてしまうことになる。
【0088】
この対策として、各F関数の位置によって線形変換処理に適用する行列部分を変更することは可能であるが、各F関数のS−boxが同一のものである場合には、上記と同様の条件が発生すれば、線形変換行列の要素の関係性によっては、後続のF関数102の出力DがデータGと排他的論理和された時点で、一部のバイトで打ち消しあいが起こってしまい、攻撃者に有利な状況が発生することがある。
【0089】
このように、少なくとも同一系列に対する出力を行なう複数のF関数において適用する非線形変換処理を同一構成とすることは、飽和攻撃による鍵推定を可能にする可能性がある。さらに、S−boxによっては、その演算(EXOR)結果、すなわち、
S(A[0](EXOR)I[0])(EXOR)S(C[0](EXOR)J[0])
これらの結果として、0から255までの256種類の全ての値が現れるという場合も望ましいとは言えない。本来ならばA[0]とC[0]の両者が256種類の異なる値をそれぞれ出力していてもそれらの演算(EXOR)結果が、かならずしも256種類の出力値をすべて取ることは保証されないが、S−boxによってはそのような状況が発生することはありえる。この予期しないことがらが発生すると攻撃に利用できる情報(値がすべて異なるという情報)が次の段まで保存されてしまうことになり、攻撃者にとって有利な状況を生み出してしまう。
【0090】
(2A−3)複数種類のS−boxを利用することによる耐性向上方法
以下、飽和攻撃による鍵推定を困難化するための構成例について説明する。すなわち、上記のような条件が万が一揃ってしまっても、データの打消しによるラウンド関数の実行前のデータと実行後のデータとが等しいデータとならないように、各F関数の非線形変換処理部、すなわちS−boxを構成する。
【0091】
この具体的例について、図10を参照して説明する。図10に示す構成も、図9と同様、Feistel構造もしくは拡張Feistel構造の一部分を切り出した構成を示し、入力データの系列(x)と出力データの系列(y)が同一であり、かつ上下に隣り合う位置にあるF関数201,202を示している。
【0092】
2つのF関数201,202は、ラウンド鍵との排他的論理和演算部、非線形変換処理部、線形変換処理部によって構成されている。F関数201,202は、32ビット入出力処理を行う構成であり、非線形変換処理部は、4つのS−boxによって構成され、それぞれのS−boxは、8ビット入出力を行なう。
【0093】
図10に示すA〜Jは、図9と同様、
A:先行F関数201に対する入力
B:先行F関数201の出力
C:後続F関数202の入力
D:後続F関数202の出力
E:先行F関数201の出力Bに対する排他的論理和演算データ
F:データAに対する排他的論理和演算データ
G:データBとデータEとの排他的論理和演算結果
H:データDとデータGとの排他的論理和演算結果
I:先行F関数201に対して入力するラウンド鍵
J:後続F関数202に対して入力するラウンド鍵
これらの各データを示している。
【0094】
図10に示す構成において、先行F関数201と後続F関数202の各々に設定されたる非線形変換処理部のS−boxは、異なるS−box[S1],[S2]を利用した構成としてある。
【0095】
すなわち、先行F関数201において非線形変換処理を実行するS−box[S1]と、後続F関数202において非線形変換処理を実行するS−box[S2]とは異なる非線形変換処理を実行する。具体的には、例えば異なる非線形変換テーブルを適用した非線形変換処理を実行し、同じ入力に対して同じ出力がなされるとは限らない。
【0096】
ここで,各S−box:S1,S2は以下の条件を満たす2つの異なるS−boxであるとする。
各S−box:S1,S2がnビット入出力の非線形変換処理を実行するS−boxであるとき、
(条件1)
任意のsビットデータcに対して、すべてのsビットデータである2個のxを、順次、入力した場合、
入力データ[x]に対応する第1のS−box[S1]の出力S1(x)と、
入力データ[x(EXOR)c]に対応するS−box[S2]の出力S2(x(EXOR)c)、
は、最低でもひとつは異なる値を持つ。すなわち、
S1(x)(EXOR)S2(x(EXOR)c)
上記式は固定値にならない。
さらに、
(条件2)
任意のsビットデータcに対して、すべてのsビットデータである2個のxを、順次、入力した場合、
入力データ[x]に対応する第1のS−box[S1]の出力S1(x)と、
入力データ[x(EXOR)c]に対応するS−box[S2]の出力S2(x(EXOR)c)、
は、最低でもひとつは重複値を持つ。すなわち、
S1(x)(EXOR)S2(x(EXOR)c)
上記式は、2のすべてが一度ずつ表れる形にならない。
【0097】
これは、図10において、
データAを[x]
データFを[c]
と仮定した場合、
先行F関数201のS−box[S1]の出力S1(x)と、
後続F関数202のS−box[S2]の出力S2(x(EXOR)c)と、
これらの2つの出力が全く同一であったり、排他的論理和した結果がすべてことなる値にはならないという条件を示すものである。
【0098】
この条件を満たす2つのS−box[S1],[S2]を、図10に示すように設定する。
すなわち、あるF関数ではS−box[S1]のみを用いた非線形変換処理部として、次のF関数ではS−box[S2]のみを用いた非線形変換処理部とする。それ以降のラウンドがある場合は、同様に、各F関数の非線形変換処理部にS−box[S1],[S2]の順に設定する。
【0099】
このように、入力データの系列と出力データの系列が同一であり、かつ上下に隣り合う位置にあるF関数における非線形変換処理を異なる非線形変換処理を実行する構成、すなわち、異なるS−boxの配置を行なうことで、出力系列に表れるデータが、ラウンド関数実行前の同一出力系列に出現するデータと強い相関をもつ可能性を著しく低下させることができる。
【0100】
すなわち、上述した(条件1)を満たすS−boxを利用することにより、たとえ2つのS−boxの入力の関係が、固定値の差を持つ場合でも、その出力の排他的論理和は最低でも一回は異なる値を持つため、完全に打ち消されることはないことが保証できる。
また、上述した(条件2)を満たすS−boxを利用することにより、たとえ2つのS−boxの入力の関係が、固定値の差を持つ場合でも、その出力の排他的論理和は最低でも一回は重複する値を持つため、攻撃に利用可能な性質を損なわれるといえる。従って、2つのS−boxを以上のように配置することで飽和攻撃の攻撃者に対する有利な条件が減少するため、攻撃に対する耐性が向上できることが期待できる。
【0101】
すなわち、図10において、各F関数201,202におけるS−boxの入力値が等しい場合、
A[0](EXOR)I[0]=C[0](EXOR)J[0]
となったとしても、
各F関数のS−boxの出力値、すなわち、
S1(A[0](EXOR)I[0])と、
S2(C[0](EXOR)J[0])と、
これらの出力値が、すべての場合において完全に一致することはなく、結果として、各F関数201,202のF関数出力B,Dは完全に一致することがなく、先に図9を参照して説明したような事象、すなわち、
E=H(EXOR)Δ
といった、1つのデータ系列において、ラウンド関数(F関数)の実行前後のデータが固定値のみの差分をもつという可能性をなくすことができる。
【0102】
このように、入力データの系列と出力データの系列が同一であり、かつ上下に隣り合う位置にあるF関数における非線形変換処理を異なる非線形変換処理を実行する異なるS−boxとすることで、飽和攻撃の難易度を大きく向上させ、攻撃に対する耐性が高めることが可能となる。
【0103】
(発展系−1)
図10を参照して説明した上記構成は、2つのF関数の関係にのみ着目し、この2つのF関数に設定するS−boxを異なるものとするという条件を導いたが、3つ以上のF関数においても同様のことがいえる。例えば、図11に示すようにF関数ごとに異なるS−boxを配置することにより飽和攻撃に対する耐性の向上が期待できる。
【0104】
図11は、Feistel構造もしくは拡張Feistel構造の一部分を切り出した構成を示し、入力データの系列(x)と出力データの系列(y)が同一であり、かつ上下に隣り合う位置にある3つのF関数211〜213を示している。
F関数211の非線形変換処理部にはS−box[S1]が設定され、
F関数212の非線形変換処理部にはS−box[S2]が設定され、
F関数213の非線形変換処理部にはS−box[S3]が設定されており、
S1≠S2≠S3
である。
【0105】
このように、複数のS−boxに求められる条件としては、
(条件1)
k個(k>2)のS−boxからなる集合S1,S2,..,Skに対して、互いに相異なる2つのS−boxの組SiとSj(i≠j)に対して、任意のcに対して、すべての可能な2個のxを入力として与えたとき、
Si(x)と、
Sj(x(EXOR)c)、
これらのSボックス出力は、完全同一にならず、最低でもひとつは異なる値を出力する。すなわち、
Si(x)と、Sj(x(EXOR)c)の排他的論理和の結果は固定値にならない。
さらに、
(条件2)
k個(k>2)のS−boxからなる集合S1,S2,..,Skに対して、互いに相異なる2つのS−boxの組SiとSj(i≠j)に対して、任意のcに対して、すべての可能な2個のxを入力として与えたとき、
Si(x)と、
Sj(x(EXOR)c)、
これらのSボックス出力は、2個のすべての値が一度ずつ現れる形にならない。すなわち、最低でも一つの重複値が現れる。
【0106】
この条件を満足するS−boxからなる集合S1,S2,..,Skを設定し、入力データの系列(x)と出力データの系列(y)が同一であり、かつ上下にシーケンシャルに並ぶ位置にある複数のF関数に、これらのF関数を配列することで、出力系列に表れるデータが、ラウンド関数実行前の同一出力系列に出現するデータと一致する可能性を著しく低下させることができ、結果として、飽和攻撃の難易度を大きく向上させ、攻撃に対する耐性が高めることが可能となる。
【0107】
(発展系−2)
現実的な実装を考慮すると、各F関数に含まれるS−boxの種類が複数になっても、各F関数に含まれるS−boxの組み合わせは、同じになっている方が望ましい場合がある。
【0108】
すなわち、例えばハードウェアやソフトウェアによってF関数に相当するデータ変換を行う場合、各F関数に含まれるS−boxの組み合わせが同じになっていれば、F関数としてのハードウェアやソフトウェアは同一のものとして、各ラウンドにおいて、適宜、入出力を変更するのみで、各ラウンドにおけるF関数のデータ変換が実現できる。
【0109】
具体的な例を図12を参照して説明する。図12も、図10と同様、Feistel構造もしくは拡張Feistel構造の一部分を切り出した構成を示し、入力データの系列(x)と出力データの系列(y)が同一であり、かつ上下に隣り合う位置にあるF関数221,222を示している。
【0110】
先行F関数221に含まれる4つのS−boxは、上からS1,S2,S1,S2の順に配置し、次のラウンドの後続F関数222では、上からS2,S1,S2,S1の順にする。
なお、S1≠S2
である。
【0111】
このような設定とすれば、S1を2つ、S2を2つ、並列実行可能な構成とした実装を行なえば、その構成を適用して、F関数221,222を実行することが可能となり、実装上のコストを低下させ、また、装置の小型化も可能となる。
【0112】
図12に示す構成でも、各F関数221,222において、対応するビット列に適用される非線形変換処理は、
S1→S2、または、
S2→S1、
となり、対応するビットデータ(例えば各バイト単位)の処理としては、図10を参照して説明したと同様の処理となり、結果として、同様の効果、すなわち、出力系列に表れるデータが、ラウンド関数実行前の同一出力系列に出現するデータと一致する可能性を著しく低下させることができ、結果として、飽和攻撃の難易度を大きく向上させ、攻撃に対する耐性が高めることが可能となる。
【0113】
もう1つの具体的な例を図13に示す。図13は、図11と同様、Feistel構造もしくは拡張Feistel構造の一部分を切り出した構成を示し、入力データの系列(x)と出力データの系列(y)が同一であり、かつ上下に隣り合う位置にある3つのF関数231〜233を示している。
【0114】
先行F関数231に含まれる4つのS−boxは、上からS1,S2,S3,S4の順に配置し、次のラウンドの中間F関数232では、上からS2,S3,S4,S1の順、さらに次のラウンドの中間F関数233では、上からS3,S4,S1,S2の順に設定する。
なお、S1≠S2≠S3≠S4
である。
【0115】
このような設定とすれば、S1〜S4を各々1つずつ並列実行可能な構成とした実装を行なえば、その構成を適用して、すべてのF関数231〜233を実行することが可能となり、実装上のコストを低下させ、また、装置の小型化も可能となる。
【0116】
図13に示す構成でも、各F関数231〜233において、対応するビット列に適用される非線形変換処理は、
S1→S2→S3→S4→S1→S2・・・、
の順番となり、対応するビットデータ(例えば各バイト単位)の処理としては、図10や図11を参照して説明したと同様の処理となり、結果として、同様の効果、すなわち、出力系列に表れるデータが、ラウンド関数実行前の同一出力系列に出現するデータと一致する可能性を著しく低下させることができ、結果として、飽和攻撃の難易度を大きく向上させ、攻撃に対する耐性を高めることが可能となる。
【0117】
(2B)S−boxを用いたブロック暗号において、2種類以上の異なるS−boxを混在させることで代数的攻撃(XSL攻撃)に対する耐性を向上させた構成
次に、S−boxを用いたブロック暗号において、種類の異なるS−boxを混ぜることで代数的攻撃(XSL攻撃)に対する耐性を向上させる構成について説明する。
【0118】
(2B−1)代数的攻撃(XSL攻撃)の概要
まず、ブロック暗号に対する攻撃として知られる代数的攻撃(XSL攻撃)について説明する。ブロック暗号に対する代数的攻撃(XSL攻撃)はS−boxの代数表現を利用した攻撃である。S−boxの入出力に関して代数式として表現すると複数の式を導き出すことができるが、その式の最大次数や含まれる項の数によって、攻撃に必要な計算量が変化する。
【0119】
代数的攻撃(XSL攻撃)のひとつの実施例としてブール式を用いた方式がある。たとえばある8−bit入出力を持つS−boxを複数組み込んだブロック暗号が存在するとする。このとき、8ビット入出力S−boxにおいて、入力側と出力側のビットをそれぞれ、
入力X:(x1,x2,x3,x4,x5,x6,x7,x8)、
出力Y:(y1,y2,y3,y4,y5,y6,y7,y8)、
とすると2次以下のブール式で書き表すことの式の数を評価する。
【0120】
より具体的に言うと、上記入出力X,Yをブール式で表した結果に含まれる項が、
(1,xi,yi,xixj,yiyj,xiyj)
このような2次以下のいずれかの形で表すことのできる多項式の数を評価する。
【0121】
このように表された全ブール式のうち、最大次数を2次などの低次数に限定して取り出した際に独立な式の数がより多く、項の数が少ないと攻撃に有利だとされている。すなわち、このように最大次数を2次などに限定した際に独立な式の数がより多く、項の数が少ないと攻撃に有利だとされ、攻撃に対する耐性が劣ることになる。
また、ブール式のみではならず、拡大体GF(2)などの定義体の上で低い次数での代数表現ができる場合も同様な手法を使って代数的攻撃(XSL攻撃)をすることが容易となり、攻撃耐性が弱いとされる。
【0122】
(2B−2)1種類のS−boxを用いたときの問題点
次に、S−boxを用いたブロック暗号において、1種類のみのS−boxを利用した構成での、問題点、すなわち、代数的攻撃(XSL攻撃)が行ないやすくなるという問題点について説明する。
【0123】
n−bitの入出力の非線形変換を実行するsビットS−boxには、以下の3つの代表的なタイプがある。
タイプ1:拡大体GF(2)上の逆元写像:Y=X−1や、べき乗関数Y=Xを利用したS−box
タイプ2:例えば4−bit入出力等のsビットより小さなS−boxを複数組み合わせて作り出されたS−box
タイプ3:ランダムに選択されたS−box
これらの3タイプが代表的である。
特にタイプ1とタイプ2に関しては、ハードウェア(H/W)実装時に低コストで実装できるためしばしば利用されるS−boxである。
以下、上記タイプ1〜3、各々について、1種類のみのS−boxを利用した構成での、問題点、すなわち、代数的攻撃(XSL攻撃)が行ないやすくなるという問題点について説明する。
【0124】
〈タイプ1の問題点〉
タイプ1、すなわち、GF(2)上の逆元写像:Y=X−1や、べき乗関数Y=Xを利用したS−boxの場合の問題点について説明する。
【0125】
たとえば、GF(2)上の逆元写像を用いたS−boxの場合、ブール式で表すと20数個の独立な2次式でかつ項数が80数個となる表現があることが知られている。べき乗関数に関しても同様な単純な関係がある。またGF(2)上だけではなくGF(2)上で定義されるS−boxでも同様の関係が見込まれる。
【0126】
これらの多項式表現を用いると、代数的攻撃(XSL攻撃)に対する計算量を見積もることができ、暗号の設計の段階では安全性を確保するのに十分な計算量が得られるように十分な数のS−boxを利用する必要がある。さらにGF(2)上の逆元写像を用いたS−boxの場合GF(2)でXY=1というような代数表現が可能であり次数の低い多項式を導出することも可能である。これらの性質を利用した攻撃方法も存在することが知られている。べき乗関数に関しても同様の結果が適用されうる。
【0127】
このように、GF(2)上の逆元写像やべき乗写像を用いたS−boxだけを用いた暗号では、2種類の代数的性質を利用されるためその両者に対して配慮した設計をしなくてはならない。
【0128】
なお、逆元写像やべき乗関数の前後にアフィン変換を追加した作成されたS−boxに関しても上記と同様のことが言える。
【0129】
〈タイプ2の問題点〉
次に、タイプ2、すなわち、より小さな(例えば4−bit)S−boxを複数組み合わせて作り出されたS−boxの場合の問題点について説明する。
【0130】
入出力が例えば4−bitの小さなS−boxを複数組み合わせて作り出した8ビットS−boxを用いた場合を考える。4ビットS−boxを3〜5個利用して8ビットS−boxを作り上げることができることが知られている。代数的攻撃(XSL攻撃)のためには4ビットS−boxの入出力のビットに対して2次以下のブール式多項式を導出することになるが、そもそも入出力ビットの合計が8つしかないため、そのような低い次数で表現される独立な式が少なくとも20数個程度存在することが知られている。よって、これを利用した攻撃を構成することができる。この傾向は大きな入出力サイズのS−boxを作るためにより小さなサイズのS−boxを用いて構成された場合に言えることである。
【0131】
しかしこの方式のメリットとしては、GF(2)上の逆元写像を用いたS−boxを使った場合のようなGF(2)の体の上で単純な代数的関係が存在する確率は極端に低くなることから、攻撃に必要な計算量が多くなることが分かっているため、上記ことがらより前出のS−boxにくらべて代数的攻撃(XSL攻撃)の観点からは良い点と悪い点が両者混在しているといえる。
【0132】
〈タイプ3の問題点〉
次に、タイプ3、すなわち、ランダムに選択されたS−boxの場合の問題点について説明する。ランダムに選択されたS−boxは上述のような代数的に見て弱い性質があることが望めず、代数的攻撃(XSL攻撃)に対しての高い安全性が期待できるが、H/W実装コストが極めて高いため、すべてのS−boxをランダムに選択されたS−boxにすることは望ましくはないという問題がある。
【0133】
(2B−3)代数的性質の異なる複数種類のS−boxを利用することにより、耐性を向上させた構成
上記の問題に鑑み、代数的性質の異なる2種類以上のS−boxを利用することでブール多項式を用いた代数的攻撃(XSL攻撃)、およびGF(2)の体を利用した代数的攻撃(XSL攻撃)の両者に対して耐性を向上さら、さらにすべてのS−boxをランダムに選択されたS−boxにする場合よりハードウェア(H/W)実装効率を高めた構成について、以下説明する。
【0134】
先に、説明したように、s−bitの入出力の非線形変換を実行するsビットS−boxには、以下の3つの代表的なタイプがある。
タイプ1:拡大体GF(2)上の逆元写像:Y=X−1や、べき乗関数Y=Xを利用したS−box
タイプ2:t−bitの小さなS−boxを複数組み合わせて作り出されたS−box(ただしt<sとする)
タイプ3:ランダムに選択されたS−box
これらの3タイプが代表的である。
【0135】
本実施例では、これらの異なるタイプのS−boxを組み合わせて利用することで、代数的攻撃(XSL攻撃)に対する耐性を向上させ、またハードウェア(H/W)実装効率を高めた構成を実現するものである。すなわち、S−boxを用いたブロック暗号において、2種類以上の異なるS−boxを混在させることで代数的攻撃(XSL攻撃)に対する耐性を向上させた構成である。なお、本実施例の適用可能な暗号処理構成は、非線形変換処理を実行するS−boxを有する暗号処理構成であればよく、例えば、先に説明した以下の各種の暗号処理構成、すなわち、
(ア)SPN(Substitution Permutation Network)構造、
(イ)Feistel構造、
(ウ)拡張Feistel構造、
これらのいずれにも適用可能である。
【0136】
本処理例においては、データ変換処理を実行するラウンド関数中に含まれる非線形変換処理部としてのS−boxを、以下の(a)〜(d)のいずれかの設定とする。
(a)一部をタイプ1のS−boxとし、その他をタイプ2のS−boxとする構成
(b)一部をタイプ1のS−boxとし、その他をタイプ3のS−boxとする構成
(c)一部をタイプ2のS−boxとし、その他をタイプ3のS−boxとする構成
(d)一部をタイプ1のS−boxとし、他の一部をタイプ2のS−boxとし、その他をタイプ3のS−boxと構成
【0137】
例えば、上記(a)の設定とする場合、
データ変換処理を実行するラウンド関数中に含まれる非線形変換処理部としてのS−box中、半分のS−boxをタイプ1、すなわち、GF(2)上の逆元写像を用いたS−boxとし、それ以外のS−boxを取り除いた架空の暗号を考え、そのもとでブール式を利用した代数的攻撃(XSL攻撃)の計算量の見積もりを行い、十分な計算量が見積もられていれば、残りの半分のS−boxを、タイプ2、すなわち、4−bitの小さなS−boxを複数組み合わせて作り出した8ビットS−boxとする構成にする。
【0138】
このように、上記(a)のタイプ1とタイプ2の混在設定とした暗号処理構成にすることでGF(2)上での計算量の見積もりをしたときに十分な耐性を持つことができれば、それぞれのS−boxを単独に利用したときに比べて、総合的な耐性が向上したブロック暗号を作ることが可能である。
【0139】
上記設定に限らず、上記(a)〜(d)いずれの場合でも同様に、一部のS−boxだけに限定しても代数的攻撃(XSL攻撃)に対する耐性が十分高くなるように設定し、残りのS−boxは実装効率などを配慮して決定すればよい。
【0140】
上記(a)〜(d)のように異なるタイプのS−boxを配置した具体的な暗号処理構成例について、図14〜図18を参照して説明する。図14〜図18に示す例は、いずれも6ラウンドのラウンド関数実行部を持つ暗号処理構成を示し、各ラウンド関数実行部には、複数のS−boxからなる非線形変換処理部と、線形変換処理部を有する。
【0141】
図14は、6ラウンドからなり1ラウンドあたり10個のS−boxが含まれるSPNブロック暗号の例を示している。SPNブロック暗号は、非線形変換層(S層)、線形変換層(P層)を有したデータ変換を各ラウンドにおいて実行する。各ラウンドの10個のS−boxは、例えば入力データを10分割した分割データを入力して、非線形変換処理を実行して、非線形変換結果データを線形変換層(P層)に出力し、線形変換処理結果が次のラウンド関数実行部に出力される。最終段のラウンド関数実行部の出力が暗号文となる。
【0142】
図に示す各ラウンド関数実行部301〜306の[S],[S]は、それぞれタイプ1のS−box、タイプ2のS−boxを示し、上述した異なるタイプの非線形変換処理部としてのS−boxである。
【0143】
図14に示す例は、先行する3ラウンドのラウンド関数実行部301〜303に、
タイプ1:拡大体GF(2)上の逆元写像:Y=X−1や、べき乗関数Y=Xを利用したS−box
このタイプ1のS−box[S]を配置し、
後続する3ラウンドのラウンド関数実行部301〜303に、
タイプ2:4−bitのような小さなS−boxを複数組み合わせて作り出されたS−box
このタイプ2のS−box[S]を配置した構成例である。
【0144】
図14の構成では、非線形変換処理は、前半のラウンドでは、タイプ1のS−boxを適用した処理として実行され、後半のラウンドでは、タイプ2のS−boxを適用した処理として実行される。一般的に代数的攻撃(XSL攻撃)は、すべてを同一タイプのS−boxとして仮定した上で実行されるものであり、このように異なるタイプのS−boxが混在した設定である場合には、攻撃、すなわち解析が困難となる。結果として、代数的攻撃(XSL攻撃)などの暗号解析に対する耐性の高い暗号処理構成が実現される。
【0145】
図15は、図14と同様、6ラウンドからなり1ラウンドあたり10個のS−boxが含まれるSPNブロック暗号の例を示している。
図15に示す例は、
第1,3,5の奇数ラウンドのラウンド関数実行部321,323,325には、
タイプ1:拡大体GF(2)上の逆元写像:Y=X−1や、べき乗関数Y=Xを利用したS−box
このタイプ1のS−box[S]を配置し、
第2,4,6の偶数ラウンドのラウンド関数実行部322,324,326には、
タイプ2:4−bitのような小さなS−boxを複数組み合わせて作り出されたS−box
このタイプ2のS−box[S]を配置した構成例である。
【0146】
図15の構成では、非線形変換処理は、奇数ラウンドでは、タイプ1のS−boxを適用した処理として実行され、偶数ラウンドでは、タイプ2のS−boxを適用した処理として実行される。本構成においても、図14の構成と同様、異なるタイプのS−boxが混在した設定であり、代数的攻撃(XSL攻撃)などの暗号解析に対する耐性の高い暗号処理構成が実現される。
【0147】
図16は、図14、図15と同様、6ラウンドからなり1ラウンドあたり10個のS−boxが含まれるSPNブロック暗号の例を示している。
図16に示す例は、
すべてのラウンドのラウンド関数実行部341〜346において、
タイプ1:拡大体GF(2)上の逆元写像:Y=X−1や、べき乗関数Y=Xを利用したS−box
このタイプ1のS−box[S]と、
タイプ2:4−bitのような小さなS−boxを複数組み合わせて作り出されたS−box
このタイプ2のS−box[S]を、
半数ずつ、すなわち5個ずつ配置した構成例である。
【0148】
各ラウンド関数実行部341〜346に入力するデータは10分割されて各Sボックスに入力される。10分割された分割データd〜d10の前半のデータd〜dは、タイプ1のS−boxに入力されてタイプ1のS−boxを適用した非線形変換処理が実行され、後半のデータd〜d10は、タイプ2のS−boxに入力されてタイプ2のS−boxを適用した非線形変換処理が実行されることになる。
【0149】
図16の構成においても、図14、図15の構成と同様、異なるタイプのS−boxが混在した設定であり、代数的攻撃(XSL攻撃)などの暗号解析に対する耐性の高い暗号処理構成が実現される。
【0150】
図17は、図14〜図16と同様、6ラウンドからなり1ラウンドあたり10個のS−boxが含まれるSPNブロック暗号の例を示している。
図17に示す例は、図16に示す例と同様、
すべてのラウンドのラウンド関数実行部361〜366において、
タイプ1:拡大体GF(2)上の逆元写像:Y=X−1や、べき乗関数Y=Xを利用したS−box
このタイプ1のS−box[S]と、
タイプ2:4−bitのような小さなS−boxを複数組み合わせて作り出されたS−box
このタイプ2のS−box[S]を、
半数ずつ、すなわち5個ずつ配置した構成例である。
【0151】
各ラウンド関数実行部361〜366に入力するデータは10分割されて各Sボックスに入力される。10分割された分割データd〜d10の奇数番目の分割データd,d,d,d,dは、タイプ1のS−boxに入力されてタイプ1のS−boxを適用した非線形変換処理が実行され、偶数番目の分割データd,d,d,d,d10は、タイプ2のS−boxに入力されてタイプ2のS−boxを適用した非線形変換処理が実行されることになる。
【0152】
図17の構成においても、図14〜図16の構成と同様、異なるタイプのS−boxが混在した設定であり、代数的攻撃(XSL攻撃)などの暗号解析に対する耐性の高い暗号処理構成が実現される。
【0153】
図16や図17に示す構成では、各ラウンドにおいて並列に実行するS−boxは、それぞれタイプ1のS−boxと、タイプ2のS−boxが5個ずつであり、これはすべてのラウンドにおいて共通している。従って、例えば、実装として、タイプ1とタイプ2のS−boxが5個ずつ並列実行可能な構成とすれば、その構成を繰り返し適用してすべてのラウンドのラウンド関数を実行することが可能となり、実装面においてもコストダウン、小型化が図れるというメリットがある。
【0154】
図18には、Feistel構造における各ラウンド関数実行部381〜386に複数の異なるタイプのS−boxを配置した例を示している。
図18に示す例は、
すべてのラウンドのラウンド関数実行部381〜386において、
タイプ1:拡大体GF(2)上の逆元写像:Y=X−1や、べき乗関数Y=Xを利用したS−box
このタイプ1のS−box[S]と、
タイプ2:4−bitのような小さなS−boxを複数組み合わせて作り出されたS−box
このタイプ2のS−box[S]を、
半数ずつ、すなわち2個ずつ配置した構成例である。
【0155】
各ラウンド関数実行部381〜386に入力するデータは4分割されて各Sボックスに入力される。4分割された分割データd〜dの奇数番目の分割データd,dは、タイプ1のS−boxに入力されてタイプ1のS−boxを適用した非線形変換処理が実行され、偶数番目の分割データd,dは、タイプ2のS−boxに入力されてタイプ2のS−boxを適用した非線形変換処理が実行されることになる。
【0156】
図18の構成においても、図14〜図17の構成と同様、異なるタイプのS−boxが混在した設定であり、代数的攻撃(XSL攻撃)などの暗号解析に対する耐性の高い暗号処理構成が実現される。
【0157】
なお、図14〜図18に示す例では、タイプ1とタイプ2の2種類のタイプのS−boxを混在させて利用した構成例を示したが、異なるタイプのS−boxの混在構成としては、先に説明したように、
(a)一部をタイプ1のS−boxとし、その他をタイプ2のS−boxとする構成
(b)一部をタイプ1のS−boxとし、その他をタイプ3のS−boxとする構成
(c)一部をタイプ2のS−boxとし、その他をタイプ3のS−boxとする構成
(d)一部をタイプ1のS−boxとし、他の一部をタイプ2のS−boxとし、その他をタイプ3のS−boxと構成
これらの各種の混在構成が可能であり、いずれの場合においても、代数的攻撃(XSL攻撃)に対する耐性の向上が実現される。
【0158】
(2C)S−boxを用いたFeistel暗号もしくは拡張Feistel型暗号において上記(2A),(2B)を同時に実現する構成
次に、S−boxを用いたFeistel暗号もしくは拡張Feistel型暗号において上記(2A),(2B)、すなわち、
(2A)S−boxを用いたFeistelもしくは拡張Feistel型暗号において2種類以上の異なるS−boxを配置することで飽和攻撃に対する耐性を向上させた構成
(2B)S−boxを用いたブロック暗号において、2種類以上の異なるS−boxを混在させることで代数的攻撃(XSL攻撃)に対する耐性を向上させた構成
これらの構成を同時に実現する構成例について説明する。
【0159】
上述した(2A)の構成は、2種類以上のS−boxをFeistel構造または拡張Feistel構造に適用することで飽和攻撃に対する耐性を向上させる構成であり、上述した(2B)の構成は、2種類以上のS−boxをS−boxを持つ任意のブロック暗号に対して用いることで代数的攻撃(XSL攻撃)に対する耐性を向上させる構成である。
【0160】
これら(2A),(2B)の構成は、併せて実現することが可能である。すなわち、(2A),(2B)に必要な性質を満足する2種類以上のS−boxを利用して同時に両方の攻撃に対する耐性を向上させたFeistelまたは拡張Feistel構造を持つブロック暗号を構成することが可能となる。
【0161】
具体的には、上述した
(2A)S−boxを用いたFeistelもしくは拡張Feistel型暗号において2種類以上の異なるS−boxを配置することで飽和攻撃に対する耐性を向上させた構成
において説明した図10〜図13の各構成において適用した異なる非線形変換処理を実行するS−box[S1],[S2],[S3],[S4]・・のそれぞれについて、
上述した
(2B)S−boxを用いたブロック暗号において、2種類以上の異なるS−boxを混在させることで代数的攻撃(XSL攻撃)に対する耐性を向上させた構成
において説明した異なるタイプのS−box、すなわち、
タイプ1:拡大体GF(2)上の逆元写像:Y=X−1や、べき乗関数Y=Xを利用したS−box
タイプ2:4−bitのような小さなS−boxを複数組み合わせて作り出されたS−box
タイプ3:ランダムに選択されたS−box
これらの3タイプを対応付けて設定する。
【0162】
例えば、図10に示す構成において、
S−box[S1]と、S−box[S2]とを、(2B)において説明した異なるタイプのS−boxとして設定することで、
飽和攻撃に対しても、代数的攻撃(XSL攻撃)に対しても耐性の高い構成が実現される。
【0163】
図11〜図13に示す構成においても、同様であり、
S−box[S1],[S2]・・を、(2B)において説明した異なるタイプのS−boxとして設定することで、
飽和攻撃に対しても、代数的攻撃(XSL攻撃)に対しても耐性の高い構成が実現される。
【0164】
[3.暗号処理装置の構成例]
最後に、上述した実施例に従った暗号処理を実行する暗号処理装置としてのICモジュール700の構成例を図19に示す。上述の処理は、例えばPC、ICカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図19に示すICモジュール700は、これら様々な機器に構成することが可能である。
【0165】
図19に示すCPU(Central processing Unit)701は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ702は、CPU701が実行するプログラム、あるいは演算パラメータなどの固定データを格納するROM(Read-Only-Memory)、CPU701の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるRAM(Random Access Memory)等からなる。また、メモリ702は暗号処理に必要な鍵データや、暗号処理において適用する変換テーブル(置換表)や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【0166】
暗号処理部703は、例えば上述した各種の暗号処理構成、すなわち、
(ア)SPN(Substitution Permutation Network)構造、
(イ)Feistel構造、
(ウ)拡張Feistel構造、
これらの各構成のいずれかの構造を適用した共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理を実行する。
【0167】
また、暗号処理部703は、上述した各実施例に対応した構成、すなわち、
(2A)S−boxを用いたFeistelもしくは拡張Feistel型暗号において2種類以上の異なるS−boxを配置した構成、
(2B)S−boxを用いたブロック暗号において、2種類以上の異なるタイプのS−boxを混在させた構成、
(2C)S−boxを用いたFeistel暗号もしくは拡張Feistel型暗号において上記(2A),(2B)を同時に実現する構成、
これらの構成のいずれかに対応する構成を持つ非線形変換処理部としてのS−boxを持つ。
【0168】
なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをROMに格納し、CPU701がROM格納プログラムを読み出して実行するように構成してもよい。
【0169】
乱数発生器704は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【0170】
送受信部705は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ICモジュールとのデータ通信を実行し、ICモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【0171】
このICモジュール700は、上述した実施例に従った非線形変換処理部としてのS−boxの配列を有しており、結果として、
(2A)S−boxを用いたFeistelもしくは拡張Feistel型暗号において2種類以上の異なるS−boxを配置することで飽和攻撃に対する耐性を向上させた構成、
(2B)S−boxを用いたブロック暗号において、2種類以上の異なるS−boxを混在させることで代数的攻撃(XSL攻撃)に対する耐性を向上させた構成、
(2C)S−boxを用いたFeistel暗号もしくは拡張Feistel型暗号において上記(2A),(2B)を同時に実現する構成、
これらのいずれかの構成を持ち、飽和攻撃や代数的攻撃(XSL攻撃)に対する耐性が向上した構成を持つ。
【0172】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【0173】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【0174】
例えば、プログラムは記録媒体としてのハードディスクやROM(Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、CD−ROM(Compact Disc Read Only Memory),MO(Magneto optical)ディスク,DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納(記録)しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【0175】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、LAN(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【0176】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【0177】
上述したように、本発明の一実施例の構成によれば、共通鍵ブロック暗号を適用した復号処理において、ラウンド関数実行部に設定される非線形変換処理部としてのSボックスに、少なくとも2種類以上の複数の異なるSボックスを利用した構成とした。本構成により、飽和攻撃に対する耐性を高めることが可能となる。また、Sボックスのタイプとして、異なるタイプのものを混在させる本発明の一実施例の構成によれば、代数的攻撃(XSL攻撃)に対する耐性を高めることが可能となり、安全性の高い復号処理装置が実現される。
【符号の説明】
【0178】
10 共通鍵ブロック暗号処理部E
11 鍵スケジューリング部
12 暗号処理部
20 ラウンド関数実行部
21 排他的論理和演算部
22 非線形変換処理部
23 線形変換処理部
30 F関数部
31 排他的論理和演算部
32 非線形変換処理部
33 線形変換処理部
34 排他的論理和演算部
41,42 F関数部
50 非線形変換処理部
51 Sボックス
101,102 F関数
201,202 F関数
211〜231 F関数
221,222 F関数
231〜233 F関数
301〜306 ラウンド関数実行部
321〜326 ラウンド関数実行部
341〜346 ラウンド関数実行部
361〜366 ラウンド関数実行部
381〜386 ラウンド関数実行部
700 ICモジュール
701 CPU(Central processing Unit)
702 メモリ
703 暗号処理部
704 乱数発生器
705 送受信部

【特許請求の範囲】
【請求項1】
入力データを2以上の数で分割して得られる各データ系列に対し、Sボックスを含むF関数によるデータ変換処理をラウンド関数として各々実行する復号処理部を有し、
前記復号処理部は、入力データの系列と出力データの系列が同一であり、かつ隣り合う位置にあるF関数において対応するビット列に適用されるSボックスが異なる構成であり、
前記復号処理部は、
sビットの入出力をもつSボックスとして、
(1)タイプ1:拡大体GF(2)上の逆元写像:Y=X−1、または、べき乗関数Y=Xを利用したSボックス、
(2)タイプ2:t−bitの小さなS−boxを複数組み合わせて作り出されたSボックス、ただしt<sとする。
(3)タイプ3:ランダムに選択されたSボックス、
上記(1)〜(3)の3タイプのSボックス中、少なくとも2つ以上の異なるタイプのSボックスを利用した構成である復号処理装置。
【請求項2】
前記復号処理部は、前記Sボックスを、
(a)一部をタイプ1のSボックスとし、その他をタイプ2のSボックスとした構成、
(b)一部をタイプ1のSボックスとし、その他をタイプ3のSボックスとした構成、
(c)一部をタイプ2のSボックスとし、その他をタイプ3のSボックスとした構成、
(d)一部をタイプ1のSボックスとし、他の一部をタイプ2のSボックスとし、その他をタイプ3のSボックスとした構成、
上記(a)〜(d)のいずれかの構成を有することを特徴とする請求項1に記載の復号処理装置。
【請求項3】
前記復号処理部は、
ラウンド関数実行部内に、処理対象データを分割した分割データ各々の非線形変換処理を実行する複数のSボックスを有し、
1つのラウンドでは1種類のタイプのSボックスを利用し、ラウンド単位で異なるタイプのSボックスを利用した処理を実行する構成であることを特徴とする請求項1に記載の復号処理装置。
【請求項4】
前記復号処理部は、
ラウンド関数実行部内に、処理対象データを分割した分割データ各々の非線形変換処理を実行する複数のSボックスを有し、
1つのラウンドで、複数のタイプのSボックスを利用した構成であることを特徴とする請求項1に記載の復号処理装置。
【請求項5】
前記ラウンド関数実行部の各々に含まれるSボックスの種類および各Sボックスの数は、各F関数において同一の設定であることを特徴とする請求項4に記載の復号処理装置。
【請求項6】
前記復号処理部は、
共通鍵暗号方式に従った復号処理を実行する構成であることを特徴とする請求項1〜5いずれかに記載の復号処理装置。
【請求項7】
前記復号処理部は、
共通鍵ブロック暗号方式に従った復号処理を実行する構成であることを特徴とする請求項1〜5いずれかに記載の復号処理装置。
【請求項8】
入力データを2以上の数で分割して得られる各データ系列に対し、Sボックスを含むF関数によるデータ変換処理をラウンド関数として各々実行する復号処理部と、
前記復号処理部における復号処理の制御を行う制御部と、
前記制御部の実行する復号処理制御プログラムを格納したメモリを有し、
前記復号処理部は、入力データの系列と出力データの系列が同一であり、かつ隣り合う位置にあるF関数において対応するビット列に適用されるSボックスが異なる構成であり、
前記復号処理部は、
sビットの入出力をもつSボックスとして、
(1)タイプ1:拡大体GF(2)上の逆元写像:Y=X−1、または、べき乗関数Y=Xを利用したSボックス、
(2)タイプ2:t−bitの小さなS−boxを複数組み合わせて作り出されたSボックス、ただしt<sとする。
(3)タイプ3:ランダムに選択されたSボックス、
上記(1)〜(3)の3タイプのSボックス中、少なくとも2つ以上の異なるタイプのSボックスを利用した構成である情報処理装置。
【請求項9】
前記復号処理部は、前記Sボックスを、
(a)一部をタイプ1のSボックスとし、その他をタイプ2のSボックスとした構成、
(b)一部をタイプ1のSボックスとし、その他をタイプ3のSボックスとした構成、
(c)一部をタイプ2のSボックスとし、その他をタイプ3のSボックスとした構成、
(d)一部をタイプ1のSボックスとし、他の一部をタイプ2のSボックスとし、その他をタイプ3のSボックスとした構成、
上記(a)〜(d)のいずれかの構成を有することを特徴とする請求項8に記載の情報処理装置。
【請求項10】
前記復号処理部は、
ラウンド関数実行部内に、処理対象データを分割した分割データ各々の非線形変換処理を実行する複数のSボックスを有し、
1つのラウンドでは1種類のタイプのSボックスを利用し、ラウンド単位で異なるタイプのSボックスを利用した処理を実行する構成であることを特徴とする請求項8に記載の情報処理装置。
【請求項11】
前記復号処理部は、
ラウンド関数実行部内に、処理対象データを分割した分割データ各々の非線形変換処理を実行する複数のSボックスを有し、
1つのラウンドで、複数のタイプのSボックスを利用した構成であることを特徴とする請求項8に記載の情報処理装置。
【請求項12】
前記ラウンド関数実行部の各々に含まれるSボックスの種類および各Sボックスの数は、各F関数において同一の設定であることを特徴とする請求項11に記載の情報処理装置。
【請求項13】
前記復号処理部は、
共通鍵暗号方式に従った復号処理を実行する構成であることを特徴とする請求項8〜12いずれかに記載の情報処理装置。
【請求項14】
前記復号処理部は、
共通鍵ブロック暗号方式に従った復号処理を実行する構成であることを特徴とする請求項8〜12いずれかに記載の情報処理装置。
【請求項15】
復号処理装置において、復号処理を実行する復号処理方法であり、
復号処理部において、入力データを2以上の数で分割して得られる各データ系列に対し、Sボックスを含むF関数によるデータ変換処理をラウンド関数として各々実行する復号処理ステップを実行し、
前記復号処理ステップにおいて、入力データの系列と出力データの系列が同一であり、かつ隣り合う位置にあるF関数において対応するビット列に適用するSボックスを異なる設定のSボックスを適用したデータ変換処理を実行し、
前記復号処理ステップにおいて、
sビットの入出力をもつSボックスとして、
(1)タイプ1:拡大体GF(2)上の逆元写像:Y=X−1、または、べき乗関数Y=Xを利用したSボックス、
(2)タイプ2:t−bitの小さなS−boxを複数組み合わせて作り出されたSボックス、ただしt<sとする。
(3)タイプ3:ランダムに選択されたSボックス、
上記(1)〜(3)の3タイプのSボックス中、少なくとも2つ以上の異なるタイプのSボックスを利用したデータ変換処理を実行する復号処理方法。
【請求項16】
前記復号処理ステップは、
共通鍵暗号方式または共通鍵ブロック暗号方式に従った復号処理を実行することを特徴とする請求項15に記載の復号処理方法。
【請求項17】
復号処理装置において、復号処理を実行させるコンピュータ・プログラムであり、
復号処理部において、入力データを2以上の数で分割して得られる各データ系列に対し、Sボックスを含むF関数によるデータ変換処理をラウンド関数として各々実行する復号処理ステップを実行させ、
前記復号処理ステップにおいて、入力データの系列と出力データの系列が同一であり、かつ隣り合う位置にあるF関数において対応するビット列に適用するSボックスを異なる設定のSボックスを適用したデータ変換処理を行なわせ、
前記復号処理ステップにおいて、
sビットの入出力をもつSボックスとして、
(1)タイプ1:拡大体GF(2)上の逆元写像:Y=X−1、または、べき乗関数Y=Xを利用したSボックス、
(2)タイプ2:t−bitの小さなS−boxを複数組み合わせて作り出されたSボックス、ただしt<sとする。
(3)タイプ3:ランダムに選択されたSボックス、
上記(1)〜(3)の3タイプのSボックス中、少なくとも2つ以上の異なるタイプのSボックスを利用したデータ変換処理を実行させるコンピュータ・プログラム。
【請求項18】
前記復号処理ステップは、
共通鍵暗号方式または共通鍵ブロック暗号方式に従った復号処理を実行させるステップであることを特徴とする請求項17に記載のコンピュータ・プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate


【公開番号】特開2012−155349(P2012−155349A)
【公開日】平成24年8月16日(2012.8.16)
【国際特許分類】
【出願番号】特願2012−116685(P2012−116685)
【出願日】平成24年5月22日(2012.5.22)
【分割の表示】特願2006−238225(P2006−238225)の分割
【原出願日】平成18年9月1日(2006.9.1)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】