以下、本発明の暗号処理装置、および暗号� ��理方法、並びにコンピュータ・プログラム� ��詳細について説明する。説明は、以下の項� ��に従って行なう。
 1.SP型F関数を持つFeistel構造
 2.2つのデータ系列を持つFeistel構造に対する 拡散行列切り替え機構(DSM)の設定法
 3.拡張型Feistel構造(GFN:Generalized Feistel Network )について
 (3-1)拡散行列切り替え機構(DSM)を持たない拡 張型Feistel構造(GFN)について
 (3-2)拡散行列切り替え機構(DSM)を持つ拡張型 Feistel構造(GFN)について
 4.拡張型Feistel構造(GFN)におけるインボリュ� �ション性保持構造について
 (4-1)拡散行列切り替え機構(DSM)を持たない拡 張型Feistel構造(GFN)におけるインボリューショ ン性保持構造について
 (4-2)拡散行列切り替え機構(DSM)を持つ拡張型 Feistel構造(GFN)におけるインボリューション性 保持構造について
 5.暗号処理装置の構成例

  [1.SP型F関数を持つFeistel構造]
 まず、SP型F関数を持つFeistel構造について説 明する。共通鍵ブロック暗号のデザインとし て知られているFeistel構造はラウンド関数と� �ばれる基本処理単位の繰り返しにより、平� �を暗号文に変換する構造を持つ。

 図5を参照して、Feistel構造の基本構成に� �いて説明する。図5には、rラウンドのラウン ド数=rを持つ2つのデータ系列を持つFeistel構� �の例を示している。なお、ラウンド数rは、� ��計の段階で決定されるパラメータであり、� ��えば入力される鍵の長さに応じて変更可能� ��値である。

 図5に示すFeistel構造において、暗号化対� �として入力される平文の長さを2mnビットと� �る。ただし、m,nは共に整数である。初めに� �2mnビットの平文を、mnビットの2つの入力デ� �タP[0]101,P[1]102に分割し、これを入力値とす� �。図に示す例は、入力値を2分割する構成で� ��り、データ系列数(分割数)=2の構成例である 。

 Feistel構造はラウンド関数とよばれる基本 処理単位の繰り返しで表現され、各ラウンド に含まれるデータ変換関数はラウンド関数(F� ��数)120と呼ばれる。図5の構成では、ラウン� �関数120がr段繰り返された構成例を示してい� ��。

 例えば第1番目のラウンドでは、mnビットの� ��力データXと、図示しない鍵スケジュール部 (鍵生成部)から入力されるmnビットのラウン� �鍵RK ₁ 103がF関数120に入力され、ラウンド関数(F関数 )120におけるデータ変換処理の後にmnビットの データYを出力する。出力はもう片方の前段� �らの入力データ(第1段の場合は入力データP _L )と排他的論理和部104において、排他的論理� �演算がなされ、mnビットの演算結果が次のラ ウンド関数へと出力される。この処理、すな わちラウンド関数(F関数)を定められたラウン ド数(r)だけ繰り返し適用して暗号化処理が完 了し、暗号文の分割データC[0]、C[1]が出力さ� ��る。各ラウンドにおいて実行されるラウン� ��関数(F関数)が同一構成であるFeistel構造の復 号処理はラウンド鍵を挿入する順序を逆にす るだけでよく、逆関数を構成する必要がない 。

 各ラウンドの関数として設定されるラウ� ��ド関数(F関数)120の構成について、図6を参照 して説明する。図6(a)は、1つのラウンドにお� ��るラウンド関数(F関数)120に対する入力およ� ��出力を示す図であり、図6(b)は、ラウンド関 数(F関数)120の構成の詳細を示す図である。ラ ウンド関数(F関数)120は、図6(b)に示すように� �非線形変換層(S層)と線形変換層(P層)を接続� �たいわゆるSP型の構成を有する。

 図6に示すラウンド関数(F関数)120は、入出力 ビット長がm×n(m,n:整数)ビットの設定を持つ� �数である。SP型F関数内部では初めに鍵デー� �K _i とデータX _i との排他的論理和が実行され、次に非線形変 換層(S層)が適用され、続いて線形変換層(P層) が適用される。

 具体的には非線形変換層(S層)は、Sボック ス(S-box)121と呼ばれるnビット入力nビット出力 の非線形変換テーブルがm個並んだものであ� �、mnビットのデータはnビットずつ分割され� �それぞれ対応するSボックス(S-box)121に入力さ れデータが変換される。各Sボックスでは、� �えば変換テーブルを適用した非線形変換処� �が実行される。

 線形変換層(P層)は線形変換部122によって� ��成され、線形変換部122は、Sボックス121から の出力データであるmnビットの出力値Zを入力 し、この入力に対して線形変換を施しmnビッ� ��の結果を出力する。線形変換部122は、入力� ��ット位置の入れ替え処理などの線形変換処� ��を実行して、mnビットの出力値Yを出力する� ��この出力値Yが前段からの入力データと排他 的論理和され、次のラウンドのF関数の入力� �とされる。

 なお、以下に説明する本実施例の構成では� ��線形変換層(P層)としての線形変換部122にお� ��て実行する線形変換はGF(2)上で定義されるmn ×mnの行列を適用して行なわれる線形変換で� �ると定義し、また、第iラウンド目に含まれ� ��行列をM _i と呼ぶものとする。なお、本発明において説 明する構成における非線形変換部としてのS� �ックスと、線形変換は、いずれも全単射で� �るものとする。

  [2.2つのデータ系列を持つFeistel構造に対す る拡散行列切り替え機構(DSM)の設定法]
 先に説明したように、Feistel構造を適用した 暗号処理において、差分攻撃や線形攻撃に対 する耐性を高める構成として、拡散行列切り 替え機構(DSM:Diffusion Switching Mechanism,以下DSM)� ��適用した構成が提案されている。DSMは、Feis tel構造のラウンド関数(F関数)部の線形変換部 において適用する行列をすべてのラウンドで 同一とするのではなく、少なくとも2つ以上� �異なる行列を各ラウンドに配置する構成で� �る。このDSMにより、差分攻撃や線形攻撃に� �する耐性を向上させることが可能となる。

 このDSMについて、その概要を説明する。F eistel構造において、拡散行列切り替え機構(DS M)を適用した場合、Feistel構造を構成するラウ ンド関数(F関数)部の線形変換部(P層)において 適用する行列は、複数の異なる行列となる。 例えば、図5に示すようなrラウンドのFeistel構 造の各ラウンドにおける適用行列を全て同じ 線形変換行列として設定するのではなく、少 なくとも2種類以上の行列を特定の規則に従� �て配列する。

 例えば、各ラウンドのF関数の線形変換層に 2つの異なる線形変換行列M ₀ ,M ₁ を配置した拡散行列切り替え機構(DSM)を実現� ��たFeistel構造例を図7に示す。図7に示すFeistel 構造例において、
 F関数F ₀ は、線形変換行列M ₀ を適用した線形変換処理を実行するF関数、
 F関数F ₁ は、線形変換行列M ₁ を適用した線形変換処理を実行するF関数、
 を示している。
 2つの線形変換行列M ₀ ,M ₁ は、異なる行列によって構成される。

 なお、拡散行列切り替え機構(DSM)を実現� �るためには、適用する行列は、所定の条件� �満たすことが必要となる。この条件の1つが� ��分岐数(Branch)に関する制約である。以下、� �の制約について説明する。

 Feistel構造におけるラウンド関数部の線形変 換に適用する複数の異なる行列M ₀ ~M _n それぞれの分岐数において、
 適用行列中の分岐数の最小値:B ₁ ^D と、
 適用する複数の行列の結合行列に対応する� ��岐数の最小値:B ₂ ^D ,B ₃ ^D ,B ₂ ^L
 を以下のように定義する。

 上記式において、
 M _i は、Feistel構造における第iラウンドの線形変� ��処理に適用する線形変換行列を示し、
 [M _i |M _i+2 |・・]は、M _i |M _i+2 |・・各行列の連結により得られる結合行列� �示し、
  ^t Mは、行列Mの転置行列、M ^-1 は、行列Mの逆行列を示す。

 上記式において、:B ₂ ^D ,B ₃ ^D ,B ₂ ^L は、具体的には、Feistel構造における1つ飛び� ��連続する2ラウンドもしくは3ラウンドのF関� ��に含まれる行列を結合した行列の分岐数の� ��小値を表している。

 例えば、上記の各分岐数が以下の条件、す� ��わち、
 B ₂ ^D ≧3, B ₃ ^D ≧3, B ₂ ^L ≧3、
 上記条件を満足させるように各行列を設定� ��ることで、Feistel構造において、差分攻撃や 線形攻撃に対する耐性を向上させることが出 来ることが知られている。
 なお、B ₁ ^D ,B ₂ ^D ,B ₃ ^D ,B ₂ ^L における各添え字は以下の意味を持つもので ある。
 B _n ^D のnは結合する行列数、B _n ^D のDは差分攻撃(Differential Attack)に対する耐性� ��持つための条件であることを示し、B _n ^L のLは線形攻撃(Linear Attack)に対する耐性を持� ��ための条件であることを示している。

 図7に示すような、データ系列数(分割数)= 2の拡散行列切り替え機構(DSM)を持つFeistel構� �においては、先に、図3、図4を参照して説明 したように、インボリューション性、すなわ ち暗号化関数と復号関数を共有可能な構成と することは、F関数の適切な配置により可能� �なる。

 しかし、2つのみのデータ系列を持つFeiste l構造と異なり、データ系列数(分割数)dが、3, 4・・・等の3以上の任意数のデータ系列を許� ��した拡張型Feistel構造(GFN:Generalized Feistel Net work)、すなわち、入力としての平文Pを3つの� �ータ系列P[0],P[1],P[2]に分割してラウンド関数 部に入力する構成や、4つのデータ系列P[0],P[1 ],P[2],P[3]に分割してラウンド関数部に入力す� ��構成などにおいては、暗号化関数と復号関� ��を共有できるインボリューション性を保持� ��せることは困難となる。本発明では、この� ��うな拡張型Feistel構造において、暗号化関数 と復号関数を共有できるインボリューション 性を実現する構成を提案する。

  [3.拡張型Feistel構造(GFN:Generalized Feistel Netw ork)について]
 拡張型Feistel構造(GFN:Generalized Feistel Network)� ��ついて説明する。本発明において取り扱う� ��はSP型のF関数を使う点では上記の2つのデー タ系列を持つFeistel構造と同じであるが、デ� �タ系列数(分割数)を3以上の任意数:dとした拡 張型Feistel構造(GFN)を対象とする。dは3以上の� ��数である。

 (3-1)拡散行列切り替え機構(DSM)を持たない拡 張型Feistel構造(GFN)について
 まず、拡散行列切り替え機構(DSM)を持たな� �拡張型Feistel構造(GFN)を持つ暗号化処理構成� �構成例を図8に示す。なお、図8に示す暗号化 処理構成は、ハードウェアやソフトウェアを 適用して実行可能な暗号化関数に相当する。 前述したように暗号化関数と、復号関数を共 通の関数を適用可能としたインボリューショ ン性を保持する構成とすることで、実装コス トの削減、装置の小型化などのメリットを奏 することが可能となる。

 図8に示す例は、データ系列数(分割数)dを 、d=4とした拡張型Feistel構造(GFN)の暗号化関数 の構成例である。また、拡散行列切り替え機 構(DSM)を持たない構成であるので、各ラウン� ��において適用される線形変換行列は同一の� ��列であり、各F関数での処理は同じ処理とな る。

 前述したように、拡張型Feistel構造(GFN)の� ��ータ系列数(分割数)は3以上の任意の整数:d� �与えることが可能である。以下の実施例で� �、データ系列数(分割数)dをd=4とした構成例� �ついて説明する。なお、本発明は、d=4に限� �ず、3以上の任意のデータ系列数(分割数)を� �つ拡張型Feistel構造(GFN)において適用可能で� �る。

 図8に示す暗号化関数の構成において、入力 は、平文Pであり、平文PはP[0],P[1],P[2],P[3]の4� �のデータ系列(分割数=4)に分割され、順次、� ��ラウンドにおいてF関数を適用したデータ変 換が実行されて、rラウンドの変換結果とし� �暗号文Cを構成するC[0],C[1],C[2],C[3]を出力する 。各ラウンドのF関数では、図示しない鍵ス� �ジュール部から供給されるマスター鍵(主鍵) に基づいて生成された拡大鍵の構成要素とし てのラウンド鍵(副鍵)のRK _i [0],RK _i [1]が入力され、データ変換に適用される。な お、鍵RK _i [n]のiはラウンドを示し、nは、同一ラウンド� ��おけるラウンド鍵の識別子を示す。

 図8に示す構成では、n-bitの平文Pをラウンド 鍵RK ₁ ,RK ₂ ,・・・,RK _r が入力されたF関数でr回(r段)処理し、その結� ��として暗号文Cを得る.平文Pを1/4に分割した� ��のをそれぞれP[0],P[1],P[2],P[3],ラウンド鍵RK1� �1/2に分割したものをそれぞれRK ₁ [0],RK ₁ [1]と表現する。1段目の処理は、まず、デー� �P[0]とラウンド鍵RK ₁ [0]が入力されたF関数での処理結果と、デー� �P[1]との排他的論理和演算(EXOR)を行い、デー� ��P[2]と、ラウンド鍵RK ₁ [1]が入力されたF関数での処理結果と、デー� �P[3]との排他的論理和演算(EXOR)を行う。

 さらに、それぞれの結果をY ₁ [1],Y ₁ [3]として、P[0],P[2]をそれぞれY ₁ [0],Y ₁ [2]とする。1段目の処理結果、つまり2段目の� ��力値をX ₂ [0],X ₂ [1],X ₂ [2],X ₂ [3]とすると、
 X ₂ [0]にはY ₁ [1]、
 X ₂ [1]にはY ₁ [2]、
 X ₂ [2]にはY ₁ [3]、
 X ₂ [3]にはY ₁ [0]、
 がそれぞれ代入される。このようなデータ� ��入れ替え処理を「スワップ(入れ替え)関数� �と定義する。

 図8に示すように、各ラウンドの切り替え 部分では、各データ系列を入れ替えるスワッ プ処理が実行される。このスワップ処理に適 用する関数がスワップ関数である。スワップ 関数は、暗号化関数の1つの構成要素となる� �図8に示すようにスワップ関数201は、各ラウ� ��ドの切り替え時に、各データ系列の出力に� ��して適用され、各データ系列の出力に対応� ��る次のラウンドにおける入力系列を設定す� ��ための関数である。

 図8において、例えばデータ系列を、図8上� �に示すように左からデータ系列0,1,2,3とした� ��き、先行ラウンドの4つの系列の出力と、後 続ラウンドに対する入力系列の入れ替えがス ワップ関数201によって以下のように切り替え られる。
 先行ラウンドのデータ系列0の出力は後続ラ ウンドにおけるデータ系列3の入力として設� �される。
 先行ラウンドのデータ系列1の出力は後続ラ ウンドにおけるデータ系列0の入力として設� �される。
 先行ラウンドのデータ系列2の出力は後続ラ ウンドにおけるデータ系列1の入力として設� �される。
 先行ラウンドのデータ系列3の出力は後続ラ ウンドにおけるデータ系列2の入力として設� �される。
 このような系列入れ替え処理を実行する関� ��が暗号化処理において適用されるスワップ� ��数である。

 図8に示すd=4とした拡張型Feistel構造(GFN)の 暗号化処理構成を適用して暗号化処理を実行 した結果を復号する復号処理構成の構成例を 図9に示す。拡散行列切り替え機構(DSM)を持た ない構成であるので、各ラウンドにおいて適 用される線形変換行列は同一の行列であり、 各F関数での処理は同じ処理となる。

 なお、図9に示す復号処理構成は、ハード ウェアやソフトウェアを適用して実行可能な 復号関数に相当する。前述したように暗号化 関数と、復号関数を共通の関数を適用可能と したインボリューション性を保持する構成と することで、実装コストの削減、装置の小型 化などのメリットを奏することが可能となる 。

 図9に示す復号関数の構成において、入力は 、暗号文Cであり、暗号文CはC[0],C[1],C[2],C[3]の 4つのデータ系列(分割数=4)に分割され、順次� ��各ラウンドにおいてF関数を適用したデータ 変換が実行されて、rラウンドの変換結果と� �て平文Pを構成するP[0],P[1],P[2],P[3]を出力する 。各ラウンドのF関数では、図示しない鍵ス� �ジュール部から供給されるマスター鍵(主鍵) に基づいて生成された拡大鍵の構成要素とし てのラウンド鍵(副鍵)のRK _i [0],RK _i [1]が入力され、データ変換に適用される。

 図9に示すように、各ラウンドの適用鍵は 、図8に示す暗号化関数の各ラウンドの適用� �と逆の順番となる。さらに、図9における復� ��関数においても、ラウンド切り替え部分で� ��、各データ系列を入れ替えるスワップ処理� ��実行される。このスワップ処理は、図8に示 すスワップ処理とは異なる処理となる。図9� �示すようにスワップ関数202は、各ラウンド� �切り替え時に、各データ系列の出力に対し� �適用され、各データ系列の出力に対応する� �のラウンドにおける入力系列を設定するた� �の関数である。

 図9において、例えばデータ系列を、図9上� �に示すように左からデータ系列0,1,2,3とした� ��き、先行ラウンドの4つの系列の出力と、後 続ラウンドに対する入力系列の入れ替えがス ワップ関数202によって以下のように切り替え られる。
 先行ラウンドのデータ系列0の出力は後続ラ ウンドにおけるデータ系列1の入力として設� �される。
 先行ラウンドのデータ系列1の出力は後続ラ ウンドにおけるデータ系列2の入力として設� �される。
 先行ラウンドのデータ系列2の出力は後続ラ ウンドにおけるデータ系列3の入力として設� �される。
 先行ラウンドのデータ系列3の出力は後続ラ ウンドにおけるデータ系列0の入力として設� �される。
 このような系列入れ替え処理を実行する関� ��が復号処理において適用されるスワップ関� ��となる。

 このように、図8に示す暗号化処理構成に おいて適用されるスワップ関数201と、図9に� �す復号処理構成において適用するスワップ� �数202とは、スワップ処理の態様が異なり、� �号化処理と、復号処理によって同じ関数を� �通に利用することができない。図1~図4に示� �ようなデータ系列数(分割数)d=2のFeistel構造� �は、系列の入れ替えはデータ系列0,1の入れ� �えのみであり、暗号化、復号処理において� �様のスワップ関数を共通に利用した処理が� �能であるが、データ系列数(分割数)d=3,4,5・� �・等、3以上の任意数のデータ系列数(分割数 )dを持つことが許容される拡張型Feistel構造(GF N)では、各ラウンド間でのスワップ(入れ替え )関数が暗号化関数と復号関数とで異なるこ� �になり、データ系列数(分割数)d=2に限定され る通常のFeistel構造のように単純に暗号化関� �と復号関数は同じ関数を使用することがで� �ないという問題がある。

 (3-2)拡散行列切り替え機構(DSM)を持つ拡張型 Feistel構造(GFN)について
 次に、拡散行列切り替え機構(DSM)を持つ拡� �型Feistel構造(GFN)について説明する。拡散行� �切り替え機構(DSM)を持つ拡張型Feistel構造(GFN) を持つ暗号化関数の構成例を図10に示す。図1 0に示す例は、データ系列数(分割数)dを、d=4� �した拡散行列切り替え機構(DSM)を持つ拡張型 Feistel構造(GFN)の暗号化関数の構成例である。

 拡散行列切り替え機構(DSM)を持つ拡張型Feist el構造(GFN)は、前述したように、Feistel構造の� ��ウンド関数(F関数)部の線形変換部に2つ以上 の異なる行列を各ラウンド毎に切り替えるよ うに配置する構成としたものである。DSMによ り、差分攻撃や線形攻撃に対する耐性を向上 させることが可能となる。図10に示す例では� ��F関数F ₀ と、F関数F ₁ とでは、それぞれ異なる線形変換行列を適用 したデータ変換を実行する構成となっている 。なお、これらF関数において適用する線形� �換行列は、ある特定の条件を満足する行列� �設定することで、差分攻撃や線形攻撃に対� �る耐性を大きく向上させることが可能とな� �。この構成については、本出願人が先に出� �した特願2006-206376号において詳細に説明して いる。

 図10に示す暗号化関数の構成において、入� �は、平文Pであり、平文PはP[0],P[1],P[2],P[3]の4� ��のデータ系列(分割数=4)に分割され、順次、 各ラウンドにおいてF関数F ₀ 、またはF関数F ₁ を適用したデータ変換が実行されて、rラウ� �ドの変換結果として暗号文Cを構成するC[0],C[ 1],C[2],C[3]を出力する。各ラウンドのF関数F ₀ 、またはF関数F ₁ では、図示しない鍵スケジュール部から供給 されるマスター鍵(主鍵)に基づいて生成され� ��拡大鍵の構成要素としてのラウンド鍵(副鍵 )のRK _i [0],RK _i [1]が入力され、データ変換に適用される。な お、鍵RK _i [n]のiはラウンドを示し、nは、同一ラウンド� ��おけるラウンド鍵の識別子を示す。

 図10に示すように、拡散行列切り替え機� �(DSM)を持つ拡張型Feistel構造(GFN)においても、 各ラウンドの切り替え部分では、各データ系 列を入れ替えるスワップ処理が実行される。 図10に示すようにスワップ関数211は、各ラウ� ��ドの切り替え時に、各データ系列の出力に� ��して適用され、各データ系列の出力に対応� ��る次のラウンドにおける入力系列を設定す� ��。

 図10において、データ系列を、図10上段に示 すように左からデータ系列0,1,2,3としたとき� �先行ラウンドの4つの系列の出力と、後続ラ� ��ンドに対する入力系列の入れ替えがスワッ� ��関数211によって以下のように切り替えられ� ��。
 先行ラウンドのデータ系列0の出力は後続ラ ウンドにおけるデータ系列3の入力として設� �される。
 先行ラウンドのデータ系列1の出力は後続ラ ウンドにおけるデータ系列0の入力として設� �される。
 先行ラウンドのデータ系列2の出力は後続ラ ウンドにおけるデータ系列1の入力として設� �される。
 先行ラウンドのデータ系列3の出力は後続ラ ウンドにおけるデータ系列2の入力として設� �される。
 このような系列入れ替え処理を実行する関� ��が暗号化処理において適用されるスワップ� ��数である。

 図10に示すd=4とした拡散行列切り替え機構(D SM)を持つ拡張型Feistel構造(GFN)の暗号化関数に おいて暗号化処理を実行した結果を復号する 復号関数の構成例を図11に示す。図11に示す� �号化関数の構成において、入力は、暗号文C� ��あり、暗号文CはC[0],C[1],C[2],C[3]の4つのデー� ��系列(分割数=4)に分割され、順次、各ラウン ドにおいてF関数F ₀ 、またはF関数F ₁ を適用したデータ変換が実行されて、rラウ� �ドの変換結果として平文Pを構成するP[0],P[1], P[2],P[3]を出力する。各ラウンドのF関数F ₀ 、またはF関数F ₁ では、図示しない鍵スケジュール部から供給 されるマスター鍵(主鍵)に基づいて生成され� ��拡大鍵の構成要素としてのラウンド鍵(副鍵 )のRK _i [0],RK _i [1]が入力され、データ変換に適用される。

 図11に示すように、各ラウンドの適用鍵� �、図10に示す暗号化関数の各ラウンドの適用 鍵と逆の順番となる。さらに、図11における� ��号関数においても、ラウンド切り替え部分� ��は、各データ系列を入れ替えるスワップ処� ��が実行される。このスワップ処理は、図10� �示すスワップ処理とは異なる処理となる。� �11に示すようにスワップ関数212は、各ラウン ドの切り替え時に、各データ系列の出力に対 して適用され、各データ系列の出力に対応す る次のラウンドにおける入力系列を設定する 。

 図11において、例えばデータ系列を、図11上 段に示すように左からデータ系列0,1,2,3とし� �とき、先行ラウンドの4つの系列の出力と、� ��続ラウンドに対する入力系列の入れ替えが� ��ワップ関数212によって以下のように切り替� ��られる。
 先行ラウンドのデータ系列0の出力は後続ラ ウンドにおけるデータ系列1の入力として設� �される。
 先行ラウンドのデータ系列1の出力は後続ラ ウンドにおけるデータ系列2の入力として設� �される。
 先行ラウンドのデータ系列2の出力は後続ラ ウンドにおけるデータ系列3の入力として設� �される。
 先行ラウンドのデータ系列3の出力は後続ラ ウンドにおけるデータ系列0の入力として設� �される。
 このような系列入れ替え処理を実行する関� ��が復号処理において適用されるスワップ関� ��となる。

 このように、図10に示す暗号化処理構成� �おいて適用されるスワップ関数211と、図11に 示す復号処理構成において適用するスワップ 関数212とは、スワップ処理の態様が異なり、 同じ関数を共通に利用することができない。

 上述したように、データ系列数(分割数)d= 3,4,5・・・等、3以上の任意数のデータ系列数 (分割数)dを持つことが許容される拡張型Feiste l構造(GFN)では、拡散行列切り替え機構(DSM)を� ��たない拡張型Feistel構造(GFN)においても、ま� ��、拡散行列切り替え機構(DSM)を持つ拡張型Fe istel構造(GFN)においても、各ラウンド間での� �ワップ(入れ替え)関数が暗号化関数と復号関 数とで異なり、データ系列数(分割数)d=2に限� ��される通常のFeistel構造のように単純に暗号 化関数と復号関数は同じ関数を使用すること ができないという問題がある。

 暗号化処理と復号処理とで同じスワップ� ��数を適用可能な構成とすれば、暗号処理装� ��を構成する際、ハードウェア実装において� ��ソフトウェア実装においても、実装コスト� ��低減することが可能であり、特にハードウ� ��ア実装の場合には装置の小型化の実現につ� ��がる。さらに、検証コストが半減できると� ��うメリットもある。すなわち、関数部の検� ��として、暗号化関数、復号関数のどちらか� ��検証するのみでよくなり、ソフトウェアに� ��いてもコードサイズが半減できるなどメリ� ��トが大きい。従って、できる限り暗号化関� ��と復号関数で同じ関数を使う構成とするこ� ��が望ましい。

 しかし、一般的にブロック暗号は1回の実 行速度が非常に短く、高速に動作することが 要求される。従って、暗号化関数と復号関数 の共有させるために実行速度が低下してしま うといったことは避けたい。このような要求 に応じるため、暗号化関数と復号関数におい て共通に利用可能な関数をより多く設定する とともに、実行速度の低下しない構成が望ま れる。以下では、このような構成について説 明する。

  [4.拡張型Feistel構造(GFN)におけるインボリ� �ーション性保持構造について]
 以下、拡張型Feistel構造(GFN)において、イン� ��リューション性、すなわち、暗号化処理と� ��号処理に共通の関数を適用可能とした構成� ��について説明する。

 暗号化処理と復号処理において、共通の� ��数を利用するための簡易な手法としては、� ��ワップ関数部分だけを外部から入力する構� ��の採用が考えられる。すなわち、暗号化関� ��と復号関数において、スワップ関数部だけ� ��切り替える構成とし、その他の関数部分を� ��通に利用する構成である。

 この構成を用いれば通常のデータ系列数( 分割数)d=2としたFeistel構造と同様にラウンド( 段)ごとにラウンド鍵を入れ替え、さらに、� �ウンド切り替え時に適用するスワップ関数� �、暗号処理と復号処理において適宜入れ替� �て利用するのみで、その他の関数部分は、� �号化処理と復号処理とで同じ関数を使用す� �ことが可能となる。例えばスワップ関数を� �号化スワップ関数、復号スワップ関数の2種� ��作成しておき、この関数を外部から与える� ��うな構成である。

 しかしながら、この手法では暗号化スワ� ��プ関数、復号スワップ関数の呼び出しは、� ��号化処理、復号処理の実行期間において、� ��ラウンドの切り替え毎に行なわなければな� ��ないことになり、関数呼び出し処理を繰り� ��し実行しなければならないことになる。こ� ��ような関数呼び出し処理は、時間の消費を� ��生させ、結果として処理時間を大きくして� ��まうという問題がある。一般的に1回の実行 時間が非常に短いブロック暗号において、こ のような新たな関数呼び出処理を発生させる ことは、実行速度の大幅な低下を招くことに なり、パフォーマンスを低下させることにな る。従って現実的な使用を考慮した場合、こ のようなスワップ関数の呼び出し構成を適用 することは好ましくない。

 実装を考慮した場合、処理速度の低下を発� ��させない構成が必要であり、スワップ部分� ��変更せずに暗号化関数と復号関数を共有で� ��ることが望ましい構成である。以下、この� ��うな構成の具体的構成例について説明する� ��説明は、以下の項目に分けて行なう。
 (4-1)拡散行列切り替え機構(DSM)を持たない拡 張型Feistel構造(GFN)におけるインボリューショ ン性保持構造について
 (4-2)拡散行列切り替え機構(DSM)を持つ拡張型 Feistel構造(GFN)におけるインボリューション性 保持構造について

 なお、以下において説明する拡張型Feistel構 造(GFN)は、
 分割数d≧3で、かつ以下に説明する条件を� �たす拡張型Feistel構造であり、これを拡張型F eistel構造のタイプ2とする。本発明において� �用する拡張型Feistel構造のタイプ2について、 図12を参照して説明する。
 本発明の拡張型Feistel構造タイプ2は、以下� �パラメータを有する。
 (a)データ分割数:d(ただしdは4以上の偶数)、
 (b)入出力データ長:dmnビット、
 (c)分割データ長:mnビット、
 (d)1ラウンドあたりのF関数の数:d/2、

 図12に示すように、各ラウンド内では左� �から数えて奇数番目にあるmnビットのデータ 系列に対してF関数が適用され、F関数の処理� ��果は、すぐ隣のデータに出力が排他的論理� ��される。なお、図においては排他的論理和� ��演算記号を省略してある。図に示すように� ��各ラウンドにおいて、F関数に対するデータ 入力を行った左端のデータ系列は、次のラウ ンドでは右端に移動し、それ以外のデータ系 列は左にひとつずつずれる構成をとる。この ような構造を持つ拡張Feistel構造を拡張Feistel� ��造タイプ2と定義する。

 (4-1)拡散行列切り替え機構(DSM)を持たない拡 張型Feistel構造(GFN)におけるインボリューショ ン性保持構造について
 まず、拡散行列切り替え機構(DSM)を持たな� �拡張型Feistel構造(GFN)におけるインボリュー� �ョン性保持構造について説明する。

 拡散行列切り替え機構(DSM)を持たない拡� �型Feistel構造(GFN)において、インボリューシ� �ン性を保持させる構成とした復号処理構成� �を図13に示す。

 図13に示す復号処理構成は、先に図8を参� ��して説明したデータ系列数(分割数)dを、d=4� ��した拡散行列切り替え機構(DSM)を持たない� �張型Feistel構造(GFN)の暗号化関数の構成例に� �応する復号関数の構成例である。すなわち� �図8を参照して説明した暗号処理構成におい� ��生成した暗号文の復号に適用可能な復号処� ��を実行する構成を示している。なお、図13� �示す復号処理構成は、ハードウェアやソフ� �ウェアを適用して実行可能な復号関数に相� �する。前述したように暗号化関数と、復号� �数を共通の関数を適用可能としたインボリ� �ーション性を保持する構成とすることで、� �装コストの削減、装置の小型化などのメリ� �トを奏することが可能となる。

 図8に示す暗号処理構成に対応する復号処 理構成として、先に説明した図9に示した復� �処理構成では、適用するスワップ関数が異� �るため、暗号関数と復号関数との構成が異� �り、インボリューション性を保持できなか� �たが、図13に示す復号処理構成では、図8に� �す暗号処理構成において適用するスワップ� �数と同じ態様のスワップ処理を行なう構成� �している。すなわち暗号化処理と復号処理� �で適用するスワップ関数を共通の関数とし� �構成を持つ。すなわち、暗号化関数(図8)と� �号関数(図13)は、共通の関数を適用可能とし� ��インボリューション性を保持させた構成を� ��現している。

 ただし、図13に示す復号処理構成は、ラ� �ンド数rが奇数の場合の復号処理構成である� ��ラウンド数rが偶数の場合の暗号化関数(図8) に対応するインボリューション性を保持した 復号処理構成は図14に示す構成となる。

 まず、ラウンド数rが奇数の場合の復号処理 構成である図13に示す復号関数の構成につい� ��説明する。図13の復号処理構成において、� �力は、暗号文Cであり、暗号文CはC[0],C[1],C[2], C[3]の4つのデータ系列(分割数=4)に分割され、 順次、各ラウンドにおいてF関数を適用した� �ータ変換が実行されて、rラウンドの変換結� ��として平文Pを構成するP[0],P[1],P[2],P[3]を出� �する。各ラウンドのF関数では、図示しない� ��スケジュール部から供給されるマスター鍵( 主鍵)に基づいて生成された拡大鍵の構成要� �としてのラウンド鍵(副鍵)のRK _i [0],RK _i [1]が入力され、データ変換に適用される。

 図13に示す復号関数において、各ラウン� �の適用鍵は、図8に示す暗号化関数の各ラウ� ��ドの適用鍵と逆の順番となる。これは、図8 の暗号化関数と図9の復号関数の対応と同様� �関係である。

 しかし、図13における復号関数では、ラ� �ンド切り替え部分の各データ系列入れ替え� �理として実行するスワップ処理は、図8に示� ��スワップ処理と同一のスワップ処理となる� ��図13に示すようにスワップ関数251は、各ラ� �ンドの切り替え時に、各データ系列の出力� �対して適用され、各データ系列の出力に対� �する次のラウンドにおける入力系列を設定� �る。

 図13において、例えばデータ系列を、図13上 段に示すように左からデータ系列0,1,2,3とし� �とき、先行ラウンドの4つの系列の出力と、� ��続ラウンドに対する入力系列の入れ替えが� ��ワップ関数251によって以下のように切り替� ��られる。
 先行ラウンドのデータ系列0の出力は後続ラ ウンドにおけるデータ系列3の入力として設� �される。
 先行ラウンドのデータ系列1の出力は後続ラ ウンドにおけるデータ系列0の入力として設� �される。
 先行ラウンドのデータ系列2の出力は後続ラ ウンドにおけるデータ系列1の入力として設� �される。
 先行ラウンドのデータ系列3の出力は後続ラ ウンドにおけるデータ系列2の入力として設� �される。
 このような系列入れ替え処理を実行する関� ��がスワップ関数251である。

 このスワップ処理は、先に図8を参照して説 明した暗号化処理におけるスワップ関数と同 一の系列入れ替え処理である。
 従って、図8に示す暗号化処理と、図13に示� ��復号処理とでは、全く同一のスワップ関数� ��適用することが可能となる。

 図13に示す復号処理構成では、スワップ関� �を暗号化処理と同一の構成とするための工� �として、各ラウンドにおけるF関数に対する� ��力鍵(ラウンド鍵)の入力態様を変更してい� �。図13に示す復号処理構成中、図に示す◎の 偶数ラウンドにおいて、各F関数に入力する� �ウンド鍵の入れ替えを行なっている。図に� �すように、図13に示す復号処理構成の、上か ら2つのラウンドである第2ラウンドでは、図� ��示す左側のF関数に対してラウンド鍵RK _(r-1) [1]を入力し、右側のF関数に対してラウンド� �RK _(r-1) [0]を入力する構成としている。以下、第4ラ� �ンド、第6ラウンド・・・各偶数ラウンドに� ��いて、各F関数に入力するラウンド鍵の入れ 替えを行なっている。図9と対比するとその� �異が明確となる。図9では、全てのラウンド� ��おいて、左側のF関数にはラウンド鍵RK _i [0]を入力し、右側のF関数にはラウンド鍵RK _i [1]を入力している。

 このように、図13に示す復号処理構成で� �、各偶数ラウンドのF関数に対して入力する� ��ウンド鍵を入れ替えることで、図8に示す暗 号処理構成において適用するスワップ関数と 同一のスワップ関数を適用可能として、暗号 化関数と復号関数のインボリューション性を 実現している。

 図13に示す復号処理構成は、ラウンド数r� ��奇数の場合の復号処理構成である。ラウン� ��数rが偶数の場合の暗号化関数(図8)に対応す るインボリューション性を保持した復号処理 構成は図14に示す構成となる。

 図14に示す復号処理構成も、図8に示す暗� ��処理構成によって暗号化された暗号文を平� ��に戻す復号処理に適用される復号関数に相� ��する復号処理構成を示している。図14の構� �は、ラウンド数rが奇数である。

 図14に示す復号処理構成も、図13に示す復 号処理構成と同様、図に◎で示す各偶数ラウ ンドに設定されたF関数に対して入力するラ� �ンド鍵の入れ替えを実行する構成としてい� �。さらに、最終ラウンドの処理結果に対す� �出力調整処理を実行する構成を持つ。出力� �整部262は、最終ラウンドにおける各データ� �列の値を入れ替えて、P[0],P[1],P[2],P[3]の最終� ��力を得るための処理として実行される。こ� ��部分は、復号関数の実行後の処理として1回 のみ実行すればよく、大きな効率低下を発生 させるものとはならない。

 図14に示す構成におけるスワップ関数261は� �図13に示す構成と同様、図8を参照して説明� �た暗号化処理構成におけるスワップ関数201� �同一のスワップ処理を行なう構成を持つ。� �なわち、
 先行ラウンドのデータ系列0の出力は後続ラ ウンドにおけるデータ系列3の入力として設� �される。
 先行ラウンドのデータ系列1の出力は後続ラ ウンドにおけるデータ系列0の入力として設� �される。
 先行ラウンドのデータ系列2の出力は後続ラ ウンドにおけるデータ系列1の入力として設� �される。
 先行ラウンドのデータ系列3の出力は後続ラ ウンドにおけるデータ系列2の入力として設� �される。
 このような系列入れ替え処理を実行する関� ��がスワップ関数261である。

 このスワップ処理は、先に図8を参照して説 明した暗号化処理におけるスワップ関数201と 同一の系列入れ替え処理である。
 従って、図8に示す暗号化処理と、図13に示� ��復号処理とでは、全く同一のスワップ関数� ��適用することが可能となる。

 図14に示す復号処理構成では、スワップ� �数を暗号化処理と同一の構成とするための� �夫として、各ラウンドにおけるF関数に対す� ��入力鍵(ラウンド鍵)の入力態様を変更し、� �らに、出力調整部262により、最終ラウンド� �処理結果に対する出力調整処理を実行する� �成としている。この設定とすることで、図8� ��示す暗号処理構成において適用するスワッ� ��関数と同一のスワップ関数を適用可能とし� ��、暗号化関数と復号関数に共通の関数を適� ��可能なインボリューション性を実現してい� ��。

 拡散行列切り替え機構(DSM)を持たない拡張� �Feistel構造(GFN)においては、上述した構成に� �ってインボリューション性を保持した構造� �実現することができる。この処理おける暗� �化関数、復号関数は、以下のように示すこ� �ができる。
 (暗号化関数)
 C=E(P,RK ₁ ,RK ₂ ,RK ₃ ,RK ₄ ,RK ₅ ,・・・,RK _r-1 ,RK _r )
 (復号関数(r=奇数の場合))
 P=D(P,RK ₁ ,RK ₂ ,RK ₃ ,RK ₄ ,RK ₅ ,・・・,RK _r-1 ,RK _r )
  =E(P,RK _r ,RK' _r-1 ,RK _r-2 ,RK' _r-3 ,RK _r-4 ・・・,RK' ₂ ,RK ₁ )
 (復号関数(r=偶数の場合))
 P=D(P,RK ₁ ,RK ₂ ,RK ₃ ,RK ₄ ,RK ₅ ,・・・,RK _r-1 ,RK _r )
  =HalfSwap(E(P,RK _r ,RK' _r-1 ,RK _r-2 ,RK' _r-3 ,RK _r-4 ・・・,RK ₂ ,RK' ₁ ))
 として示すことができ、ラウンド鍵の適切� ��置換により、暗号化関数と復号関数が共有� ��きることが分かる。
 ただし、RK ₁ =(RK ₁ [0]||RK ₁ [1])とすると、RK' ₁ =(RK ₁ [1]||RK ₁ [0])であり、HalfSwapは入力値の前後を入れ替え る関数を表す。

 ラウンド数が奇数段の詳細な例として、3段 GFNの暗号化、復号関数を図15に示す。図15の� �号化関数(図15(a))は,以下のように処理される 、以降の説明で用いる(+)はビットごとの排他 的論理和を表す.
  [(0段目)]
 X ₁ [0]=P[0]
 X ₁ [1]=P[1]
 X ₁ [2]=P[2]
 X ₁ [3]=P[3]
  [1段目]
 X ₂ [0]=F(X ₁ [0],RK ₁ [0])(+)X ₁ [1]
 X ₂ [1]=X ₁ [2]
 X ₂ [2]=F(X ₁ [2], RK ₁ [1])(+)X ₁ [3]
 X ₂ [3]=X ₁ [0]

  [2段目]
 X ₃ [0]=F(X ₂ [0],RK ₂ [0])(+)X ₂ [1]
 X ₃ [1]=X ₂ [2]
 X ₃ [2]=F(X ₂ [2],RK ₂ [2])(+)X ₂ [3]
 X ₃ [3]=X ₂ [0]
  [3段目]
 C[0]=X ₃ [0]
 C[1]=F(X ₃ [0],RK ₃ [0])(+)X ₃ [1]
 C[2]=X ₃ [2]
 C[3]=F(X ₃ [2],RK ₃ [1])(+)X ₃ [3]

 また、図11の復号関数(図15(b))は以下のよう� ��処理される.
  [1段目]
 X ₃ [0]=C[0]
 X ₃ [1]=F(X ₃ [0],RK ₃ [0])(+)C[1]
 X ₃ [2]=C[2]
 X ₃ [3]=F(X ₃ [2],RK ₃ [1])(+)C[3]
  [2段目]
 X ₂ [0]=X ₃ [3]
 X ₂ [1]=F(X ₂ [0],RK ₂ [0])(+)X ₃ [0]
 X ₂ [2]=X ₃ [1]
 X ₂ [3]=F(X ₂ [2],RK ₂ [1])(+)X ₃ [2]

  [3段目]
 X ₁ [0]=X ₂ [3]
 X ₁ [1]=F(X ₁ [0],RK ₁ [0])(+)X ₂ [0]
 X ₁ [2]=X ₂ [1]
 X ₁ [3]=F(X ₁ [2],RK ₁ [1])(+)X ₂ [2]
  [最終段]
 P[0]=X ₁ [0]
 P[1]=X ₁ [1]
 P[2]=X ₁ [2]
 P[3]=X ₁ [3]

 上記式より明らかに暗号化関数で暗号化� ��れたデータは、偶数段のラウンド鍵を適切� ��入れ替えただけの暗号化関数によって復号� ��きることが分かる。なお、式を一般化した� ��合、暗号化関数、復号関数は、それぞれ以� ��のように表現可能である。

  [GFN暗号化関数(奇数段の場合(r=奇数))]
 X ₁ [0]=P[0]
 X ₁ [1]=P[1]
 X ₁ [2]=P[2]
 X ₁ [3]=P[3]
 fori=2tor
  X _i [0]=F(X _i-1 [0],RK _i-1 [0])(+)X _i-1 [1]
  X _i [1]=X _i-1 [2]
  X _i [2]=F(X _i-1 [2],RK _i-1 [2])(+)X _i-1 [3]
  X _i [3]=X _i-1 [0]
 C[0]=X _r [0]
 C[1]=F(X _r [0],RK _r [0])(+)X _r [1]
 C[2]=X _r [2]
 C[3]=F(X _r [2],RK _r [1])(+)X _r [3]

  [GFN復号関数(奇数段の場合(r=奇数))]
 Xr[0]=C[0]
 Xr[1]=F(X _r [0],RK _r [0])(+)C[1]
 Xr[2]=C[2]
 Xr[3]=F(X _r [2],RK _r [1])(+)C[3]
 fori=r-1downto1
  Xi[0]=X _i+1 [3]
  Xi[1]=F(X _i [0],RK _i [0])(+)X _i+1 [0]
  Xi[2]=X _i+1 [1]
  Xi[3]=F(X _i [2],RK _i [1])(+)X _i+1 [2]
 P[0]=X ₁ [0]
 P[1]=X ₁ [1]
 P[2]=X ₁ [2]
 P[3]=X ₁ [3]

 偶数段の例として、4段GFNの暗号化、復号関 数を図16に示す。図16の暗号化関数(図16(a))は, 以下のように処理される。
  [(0段目)]
 X ₁ [0]=P[0]
 X ₁ [1]=P[1]
 X ₁ [2]=P[2]
 X ₁ [3]=P[3]
  [1段目]
 X ₂ [0]=F(X ₁ [0],RK ₁ [0])(+)X ₁ [1]
 X ₂ [1]=X ₁ [2]
 X ₂ [2]=F(X ₁ [2],RK ₁ [1])(+)X ₁ [3]
 X ₂ [3]=X ₁ [0]

  [2段目]
 X ₃ [0]=F(X ₂ [0],RK ₂ [0])(+)X ₂ [1]
 X ₃ [1]=X ₂ [2]
 X ₃ [2]=F(X ₂ [2],RK ₂ [2])(+)X ₂ [3]
 X ₃ [3]=X ₂ [0]
  [3段目]
 X ₄ [0]=F(X ₃ [0],RK ₃ [0])(+)X ₃ [1]
 X ₄ [1]=X ₃ [2]
 X ₄ [2]=F(X ₃ [2],RK ₃ [1])(+)X ₃ [3]
 X ₄ [3]=X ₃ [0]
  [4段目]
 C[0]=X ₄ [0]
 C[1]=F(X ₄ [0],RK ₄ [0])(+)X ₄ [1]
 C[2]=X ₄ [2]
 C[3]=F(X ₄ [2],RK ₄ [1])(+)X ₄ [3]

 また,図16の復号関数(図16(b))は以下のように 処理される.
  [1段目]
 X ₄ [0]=C[0]
 X ₄ [1]=F(X ₄ [0],RK ₄ [0])(+)C[1]
 X ₄ [2]=C[2]
 X ₄ [3]=F(X ₄ [2],RK ₄ [1])(+)C[3]
  [2段目]
 X ₃ [0]=X ₄ [3]
 X ₃ [1]=F(X ₃ [0],RK ₃ [0])(+)X ₄ [0]
 X ₃ [2]=X ₄ [1]
 X ₃ [3]=F(X ₃ [2],RK ₃ [1])(+)X ₄ [2]

  [3段目]
 X ₂ [0]=X ₃ [3]
 X ₂ [1]=F(X ₂ [0],RK ₂ [0])(+)X ₃ [0]
 X ₂ [2]=X ₃ [1]
 X ₂ [3]=F(X ₂ [2],RK ₂ [1])(+)X ₃ [2]
  [4段目]
 X ₁ [0]=X ₂ [3]
 X ₁ [1]=F(X ₁ [0],RK ₁ [0])(+)X ₂ [0]
 X ₁ [2]=X ₂ [1]
 X ₁ [3]=F(X ₁ [2],RK ₁ [1])(+)X ₂ [2]
  [最終段]
 P[0]=X ₁ [2]
 P[1]=X ₁ [3]
 P[2]=X ₁ [0]
 P[3]=X ₁ [1]

 上記式より明らかに暗号化関数で暗号化� ��れたデータは、ラウンド鍵の順序を入れ替� ��、最終出力の左右の出力を入れ替えた暗号� ��関数によって復号できることが分かる。な� ��、式を一般化した場合、暗号化関数、復号� ��数はそれぞれ以下のように示すことができ� ��。

  [GFN暗号化関数(偶数段の場合(r=偶数))]
 X ₁ [0]=P[0]
 X ₁ [1]=P[1]
 X ₁ [2]=P[2]
 X ₁ [3]=P[3]
 fori=2tor
  X _i [0]=F(X _i-1 [0],RK _i-1 [0])(+)X _i-1 [1]
  X _i [1]=X _i-1 [2]
  X _i [2]=F(X _i-1 [2],RK _i-1 [2])(+)X _i-1 [3]
  X _i [3]=X _i-1 [0]
 C[0]=X _r [0]
 C[1]=F(X _r [0],RK _r [0])(+)X _r [1]
 C[2]=X _r [2]
 C[3]=F(X _r [2],RK _r [1])(+)X _r [3]

  [GFN復号関数(偶数段の場合(r=偶数))]
 Xr[0]=C[0]
 Xr[1]=F(X _r [0],RK _r [0])(+)C[1]
 Xr[2]=C[2]
 Xr[3]=F(X _r [2],RK _r [1])(+)C[3]
 fori=r-1downto1
  Xi[0]=X _i+1 [3]
  Xi[1]=F(X _i [0],RK _i [0])(+)X _i+1 [0]
  Xi[2]=X _i+1 [1]
  Xi[3]=F(X _i [2],RK _i [1])(+)X _i+1 [2]
 P[0]=X ₁ [2]
 P[1]=X ₁ [3]
 P[2]=X ₁ [0]
 P[3]=X ₁ [1]

 (4-2)拡散行列切り替え機構(DSM)を持つ拡張型 Feistel構造(GFN)におけるインボリューション性 保持構造について
 次に、拡散行列切り替え機構(DSM)を持つ拡� �型Feistel構造(GFN)におけるインボリューショ� �性保持構造について説明する。

 拡散行列切り替え機構(DSM)を持つ拡張型Fe istel構造(GFN)において、インボリューション� �を保持させる構成とした復号処理構成例を� �17に示す。

 図17に示す復号処理構成は、先に図10を参 照して説明したデータ系列数(分割数)dを、d=4 とした拡散行列切り替え機構(DSM)を持つ拡張� ��Feistel構造(GFN)の暗号化関数の構成例に対応� ��る復号関数の構成例である。すなわち、図1 0を参照して説明した拡散行列切り替え機構(D SM)を持つ暗号処理構成において生成した暗号 文の復号に適用可能な復号処理を実行する構 成を示している。なお、図17に示す復号処理� ��成は、ハードウェアやソフトウェアを適用� ��て実行可能な復号関数に相当する。前述し� ��ように暗号化関数と、復号関数を共通の関� ��を適用可能としたインボリューション性を� ��持する構成とすることで、実装コストの削� ��、装置の小型化などのメリットを奏するこ� ��が可能となる。

 図10に示す暗号処理構成に対応する復号� �理構成として、先に説明した図11に示した復 号処理構成では、適用するスワップ関数が異 なるため、暗号関数と復号関数との構成が異 なり、インボリューション性を保持できなか ったが、図17に示す復号処理構成では、図10� �示す暗号処理構成において適用するスワッ� �関数と同じ態様のスワップ処理を行なう構� �としている。すなわち暗号化処理と復号処� �とで適用するスワップ関数を共通の関数と� �た構成を持つ。すなわち、暗号化関数(図10)� ��復号関数(図17)は、共通の関数を適用可能と したインボリューション性を保持させた構成 を実現している。

 ただし、図17に示す復号処理構成は、ラ� �ンド数rが奇数の場合の復号処理構成である� ��ラウンド数rが偶数の場合の暗号化関数(図10 )に対応するインボリューション性を保持し� �復号処理構成は図18に示す構成となる。

 まず、ラウンド数rが奇数の場合の復号処理 構成である図17に示す復号関数の構成につい� ��説明する。図17の復号処理構成において、� �力は、暗号文Cであり、暗号文CはC[0],C[1],C[2], C[3]の4つのデータ系列(分割数=4)に分割され、 順次、各ラウンドにおいてF関数F ₀ 、またはF関数F ₁ を適用したデータ変換が実行されて、rラウ� �ドの変換結果として平文Pを構成するP[0],P[1], P[2],P[3]を出力する。各ラウンドのF関数F ₀ とF関数F ₁ では、図示しない鍵スケジュール部から供給 されるマスター鍵(主鍵)に基づいて生成され� ��拡大鍵の構成要素としてのラウンド鍵(副鍵 )のRK _i [0],RK _i [1]が入力され、データ変換に適用される。

 図17に示す復号関数において、各ラウン� �の適用鍵は、図10に示す暗号化関数の各ラウ ンドの適用鍵と逆の順番となる。これは、図 10の暗号化関数と図11の復号関数の対応と同� �の関係である。

 しかし、図17における復号関数では、ラ� �ンド切り替え部分の各データ系列入れ替え� �理として実行するスワップ処理は、図10に示 すスワップ処理と同一のスワップ処理となる 。図17に示すようにスワップ関数271は、各ラ� ��ンドの切り替え時に、各データ系列の出力� ��対して適用され、各データ系列の出力に対� ��する次のラウンドにおける入力系列を設定� ��る。

 図17において、例えばデータ系列を、図17上 段に示すように左からデータ系列0,1,2,3とし� �とき、先行ラウンドの4つの系列の出力と、� ��続ラウンドに対する入力系列の入れ替えが� ��ワップ関数271によって以下のように切り替� ��られる。
 先行ラウンドのデータ系列0の出力は後続ラ ウンドにおけるデータ系列3の入力として設� �される。
 先行ラウンドのデータ系列1の出力は後続ラ ウンドにおけるデータ系列0の入力として設� �される。
 先行ラウンドのデータ系列2の出力は後続ラ ウンドにおけるデータ系列1の入力として設� �される。
 先行ラウンドのデータ系列3の出力は後続ラ ウンドにおけるデータ系列2の入力として設� �される。
 このような系列入れ替え処理を実行する関� ��がスワップ関数271である。

 このスワップ処理は、先に図10を参照して� �明した暗号化処理におけるスワップ関数211� �同一の系列入れ替え処理である。
 従って、図10に示す暗号化処理と、図17に示 す復号処理とでは、全く同一のスワップ関数 を適用することが可能となる。

 図17に示す復号処理構成では、スワップ関� �を暗号化処理と同一の構成とするための工� �として、各偶数ラウンドにおけるF関数F ₀ とF関数F ₁ の入れ替えと、入力鍵(ラウンド鍵)の入れ替� ��を行なっている。

 図17に示す復号処理構成中、図に示す◎の� �数ラウンドにおいて、F関数F ₀ とF関数F ₁ の入れ替えと、入力鍵(ラウンド鍵)の入れ替� ��を行なっている。図に示すように、図17に� �す復号処理構成の、上から2つのラウンドで� ��る第2ラウンドでは、左側にF関数F ₁ を設定し、右側にF関数F ₀ を設定し、さらに、左側のF関数F ₁ に対してラウンド鍵RK _(r-1) [1]を入力し、右側のF関数F ₀ に対してラウンド鍵RK _(r-1) [0]を入力する構成としている。以下、第4ラ� �ンド、第6ラウンド・・・各偶数ラウンドに� ��いて、各F関数と、F関数に入力するラウン� �鍵の入れ替えを行なっている。図11と対比す るとその差異が明確となる。図11では、全て� ��ラウンドにおいて、左側のF関数はF ₀ であり、ラウンド鍵RK _i [0]を入力する設定であり、右側のF関数はF ₁ であり、ラウンド鍵RK _i [1]を入力している。

 しかし、上記構成とした場合、図10を参� �して説明した暗号化処理構成と、図17に示す 復号処理構成では、F関数の配列が異なるこ� �になるため、暗号化関数と復号関数の共有� �を実現する構成とは言い難い。すなわち、� �号処理のみにおいて偶数段のF関数の入れ替� ��が発生してしまい、暗号関数と同一の関数� ��実現しているとは言えないことになる。

 暗号化関数と、復号関数において、F関数 部分を別の関数として外部から与えるような 構成としてもよいが、この手法ではスワップ 関数を外部から与える手法と同様、実行速度 の低下を招くことになり好ましい手法とは言 えない。そこで、F関数の入出力結果を表引� �(テーブル)実装する構成とする。

 すなわち、図17に示す構成の場合、2つの異� ��るF関数、すなわち、F関数F ₀ とF関数F ₁ を適用した構成であり、これらの各F関数の� �力値に対応する出力値を予めテーブルとし� �用意して、暗号処理装置のメモリに格納す� �。各F関数のテーブルは、メモリのテーブル� ��納位置を示す各アドレスに基づいて取得可� ��な構成とする。

 このように各F関数F ₀ ,F ₁ の出力値をメモリに格納したテーブルから取 得可能な構成とし、図17に示す復号処理構成� ��おける偶数段のF関数の実行部分では、復号 関数に対して、各テーブルのアドレスを外部 から与えてテーブルを取得して各F関数の出� �を得る構成とする。すなわち、少なくとも� �数段のF関数の実行部分は、暗号関数、復号� ��数においてテーブルを取得するアドレスに� ��った処理を実行する構成とする。

 一般的に、ソフトウェアによって実行する� ��理構成とした場合、F関数の内部は表引き(� �ーブル)で実装されている。表引き(テーブル )実装というのは,実際の演算は行わずに予め� ��算しておいた演算結果のみをテーブル(置換 表)という形でメモリ空間上に保持しておき� �それを適時参照することによって求めたい� �力値を得る実装手法である。例えば,
 f(x)=x ³
 といった計算を行いたい場合に、以下のよ� ��な値を持つftabというテーブル(置換表)を持� ��ことにより、実際のx ³ の計算を行わずともftabの中身を参照するこ� �により、x ³ の結果を得ることが可能になる。
 ftab[0]=0(=0 ³ ),
 ftab[1]=1(=1 ³ ),
 ftab[2]=8(=2 ³ ),
 ftab[3]=27(=3 ³ ),
 ftab[4]=64(=4 ³ )
  ・・,
 上記は、入力値として0,1,2,3,4があるとき、� ��力として0,1,8,27,64を取得する構成を持つテ� �ブルftabの例である。

 このようにF関数が表引き(テーブル)実装� ��成を適用し、必要となる各F関数の入力値に 対応する出力値を予めテーブルとして用意し て、暗号処理装置のメモリに格納する。各F� �数のテーブルは、メモリのテーブル格納位� �を示す各アドレスに基づいて取得可能な構� �とする。この方法によれば、F関数の入れ替� ��は実行速度を落とさずに容易に行うことが� ��能となる。これを応用して、偶数段のF関数 のテーブルのアドレスだけを外部から与える ようにすることで、関数を用いずに暗号化関 数と復号関数の変更が可能になる。

 つまり、DSMを用いたGFNにおいて、暗号化関� ��と復号関数を共有するためには、
 (1)通常のFeistel型暗号同様,段ごとに拡大鍵� �順序を入れ替える
 (2)通常のGFN構造同様,偶数段のF関数ごとに� �大鍵の位置を入れ替える
 (3)偶数段のF関数のテーブルのアドレスを暗 号化関数と復号関数で入れ替える
 これらの構成を採用する。
 以上のような方法により実行速度の低下を� ��小限に抑えつつ暗号化関数と復号関数を共� ��することが可能になる.

 上述したように、図17に示す復号処理構� �では、各偶数ラウンドの入力ラウンド鍵を� �れ替え、偶数ラウンドの各F関数の処理結果� ��テーブルから取得する構成として、それぞ� ��のF関数に対応するテーブルのアドレスを適 用した処理を実行させることで、図10に示す� ��号処理構成において適用するスワップ関数� ��同一のスワップ関数を適用可能として、暗� ��化関数と復号関数で共通の関数を用いるこ� ��ができるインボリューション性を実現する� ��とが可能となる。

 図17に示す復号処理構成は、ラウンド数r� ��奇数の場合の復号処理構成である。ラウン� ��数rが偶数の場合の暗号化関数(図10)に対応� �るインボリューション性を保持した復号処� �構成は図18に示す構成となる。

 図18に示す復号処理構成も、図10に示す暗 号処理構成によって暗号化された暗号文を平 文に戻す復号処理に適用される復号関数に相 当する復号処理構成を示している。図18の構� ��は、ラウンド数rが奇数である。

 図18に示す復号処理構成も、図17に示す復号 処理構成と同様、図に◎で示す各偶数ラウン ドに設定されたF関数F ₀ ,F ₁ と、各F関数に対して入力するラウンド鍵の� �れ替えを実行する構成としている。さらに� �最終ラウンドの処理結果に対する出力調整� �理を実行する構成を持つ。出力調整部282は� �最終ラウンドにおける各データ系列の値を� �れ替えて、P[0],P[1],P[2],P[3]の最終出力を得る� ��めの処理として実行される。この部分は、� ��号関数の実行後の処理として1回のみ実行す ればよく、大きな効率低下を発生させるもの とはならない。

 図18に示す構成におけるスワップ関数281は� �図17に示す構成と同様、図10を参照して説明� ��た暗号化処理構成におけるスワップ関数211� ��同一のスワップ処理を行なう構成を持つ。� ��なわち、
 先行ラウンドのデータ系列0の出力は後続ラ ウンドにおけるデータ系列3の入力として設� �される。
 先行ラウンドのデータ系列1の出力は後続ラ ウンドにおけるデータ系列0の入力として設� �される。
 先行ラウンドのデータ系列2の出力は後続ラ ウンドにおけるデータ系列1の入力として設� �される。
 先行ラウンドのデータ系列3の出力は後続ラ ウンドにおけるデータ系列2の入力として設� �される。
 このような系列入れ替え処理を実行する関� ��がスワップ関数281である。

 このスワップ処理は、先に図10を参照して� �明した暗号化処理におけるスワップ関数211� �同一の系列入れ替え処理である。
 従って、図10に示す暗号化処理と、図18に示 す復号処理とでは、全く同一のスワップ関数 を適用することが可能となる。

 図18に示す復号処理構成では、スワップ� �数を暗号化処理と同一の構成とするための� �夫として、各ラウンドにおけるF関数と入力� ��(ラウンド鍵)の入力態様を変更し、さらに� �出力調整部282により、最終ラウンドの処理� �果に対する出力調整処理を実行する構成と� �ている。

 なお、各偶数段におけるF関数の入れ替え は、先に図17を参照して説明した構成例と同� ��、各F関数の入出力データの対応テーブルを 予めメモリに格納し、各F関数対応のテーブ� �を取得するためのアドレスによって各F関数� ��応のテーブルを取得してF関数の処理結果を 取得する構成とすることで、暗号化関数と復 号関数の共通化を実現することが可能である 。

 上記の設定とすることで、図10に示す暗� �処理構成において適用するスワップ関数と� �一のスワップ関数を適用可能として、暗号� �関数と復号関数に共通な関数を適用可能な� �ンボリューション性が実現される。

  [5.暗号処理装置の構成例]
 最後に、上述した実施例に従った暗号処理� ��実行する暗号処理装置としてのICモジュー� �300の構成例を図19に示す。上述の処理は、例 えばPC、ICカード、リーダライタ、その他、� �々な情報処理装置において実行可能であり� �図19に示すICモジュール300は、これら様々な� ��器に構成することが可能である。

 図19に示すCPU(Central processing Unit)301は、� �号処理の開始や、終了、データの送受信の� �御、各構成部間のデータ転送制御、その他� �各種プログラムを実行するプロセッサであ� �。メモリ302は、CPU301が実行するプログラム� �あるいは演算パラメータなどの固定データ� �格納するROM(Read-Only-Memory)、CPU301の処理にお� �て実行されるプログラム、およびプログラ� �処理において適宜変化するパラメータの格� �エリア、ワーク領域として使用されるRAM(Rand om Access Memory)等からなる。また、メモリ302� �暗号処理に必要な鍵データや、暗号処理に� �いて適用する変換テーブル(置換表)や変換行 列に適用するデータ等の格納領域として使用 可能である。なおデータ格納領域は、耐タン パ構造を持つメモリとして構成されることが 好ましい。

 暗号処理部303は、例えば上述した拡張型F eistel型の共通鍵ブロック暗号処理アルゴリズ ムに従った暗号処理、復号処理を実行する。 なお、ここでは、暗号処理手段を個別モジュ ールとした例を示したが、このような独立し た暗号処理モジュールを設けず、例えば暗号 処理プログラムをROMに格納し、CPU301がROM格納 プログラムを読み出して実行するように構成 してもよい。

 乱数発生器304は、暗号処理に必要となる� ��の生成などにおいて必要となる乱数の発生� ��理を実行する。

 送受信部305は、外部とのデータ通信を実� ��するデータ通信処理部であり、例えばリー� ��ライタ等、ICモジュールとのデータ通信を� �行し、ICモジュール内で生成した暗号文の出 力、あるいは外部のリーダライタ等の機器か らのデータ入力などを実行する。

 このICモジュール300の暗号処理部303は、� �えば、上述した実施例に従って、データ系� �数dがd≧3の整数とした拡張型Feistel型暗号処� ��を実行するデータ処理部として機能する。� ��の暗号処理部303は、暗号化処理および復号� ��理に共通のスワップ処理を含むデータ処理� ��実行し、例えば、暗号化処理と、復号処理� ��おいて、適用ラウンド鍵の変更を行なうこ� ��で、暗号化処理と復号処理のいずれの処理� ��おいても前記共通のスワップ処理を含むデ� ��タ処理を実行する。すなわち、暗号化処理� ��よび復号処理に共通のスワップ関数を含む� ��通の関数を実行する。

 暗号処理部303は、拡張型Feistel構造を構成 する各ラウンドのF関数において実行する線� �変換処理の変換行列を共通の行列に設定し� �暗号処理を実行する場合には、先に図13、図 14を参照して説明したように、復号処理の各� ��ウンドにおいて適用するラウンド鍵の適用� ��ーケンスを、暗号処理と逆のシーケンスに� ��定するとともに、偶数ラウンド各々の複数� ��F関数に入力するラウンド鍵を、暗号化処理 における入力態様と異なる設定としたラウン ド鍵入れ替え処理を行なう。

 また、暗号処理部303は、拡張型Feistel構造 を構成する各ラウンドのF関数中の線形変換� �理に適用する変換行列を少なくとも2以上の� ��なる行列の選択適用構成とした拡散行列切� ��替え機構(DSM:Diffusion Switching Mechanism)を持つ Feistel構造に従った暗号処理を実行する場合� �は、先に図17、図18を参照して説明したよう� ��、復号処理の各ラウンドにおいて適用する� ��ウンド鍵の適用シーケンスを、暗号処理と� ��のシーケンスに設定するとともに、偶数ラ� ��ンド各々の複数のF関数、および該複数のF� �数に入力するラウンド鍵を、暗号化処理に� �ける入力態様と異なる設定とするF関数およ� ��ラウンド鍵入れ替え処理を行なう。この処� ��の場合には、複数の異なるF関数各々に対応 する入出力対応データを格納したテーブルを 、各ラウンドに対応して指定されるアドレス に従ってメモリから呼び出して各F関数処理� �果を算出する処理を実行する。

 さらに、暗号処理部303は、拡張型Feistel構 造を構成するラウンドのラウンド数が偶数で ある場合、先に図14、図18を参照して説明し� �ように、復号処理の最終ラウンドの出力結� �のシーケンス入れ替え処理を行なう出力調� �を実行する。

 以上、特定の実施例を参照しながら、本� ��明について詳解してきた。しかしながら、� ��発明の要旨を逸脱しない範囲で当業者が該� ��施例の修正や代用を成し得ることは自明で� ��る。すなわち、例示という形態で本発明を� ��示してきたのであり、限定的に解釈される� ��きではない。本発明の要旨を判断するため� ��は、特許請求の範囲の欄を参酌すべきであ� ��。

 なお、明細書中において説明した一連の� ��理はハードウェア、またはソフトウェア、� ��るいは両者の複合構成によって実行するこ� ��が可能である。ソフトウェアによる処理を� ��行する場合は、処理シーケンスを記録した� ��ログラムを、専用のハードウェアに組み込� ��れたコンピュータ内のメモリにインストー� ��して実行させるか、あるいは、各種処理が� ��行可能な汎用コンピュータにプログラムを� ��ンストールして実行させることが可能であ� ��。

 例えば、プログラムは記録媒体としての� ��ードディスクやROM(Read Only Memory)に予め記� �しておくことができる。あるいは、プログ� �ムはフレキシブルディスク、CD-ROM(Compact Disc  Read Only Memory),MO(Magneto optical)ディスク,DVD(D igital Versatile Disc)、磁気ディスク、半導体メ モリなどのリムーバブル記録媒体に、一時的 あるいは永続的に格納(記録)しておくことが� ��きる。このようなリムーバブル記録媒体は� ��いわゆるパッケージソフトウエアとして提� ��することができる。

 なお、プログラムは、上述したようなリ� ��ーバブル記録媒体からコンピュータにイン� ��トールする他、ダウンロードサイトから、� ��ンピュータに無線転送したり、LAN(Local Area� �Network)、インターネットといったネットワー クを介して、コンピュータに有線で転送し、 コンピュータでは、そのようにして転送され てくるプログラムを受信し、内蔵するハード ディスク等の記録媒体にインストールするこ とができる。

 なお、明細書に記載された各種の処理は� ��記載に従って時系列に実行されるのみなら� ��、処理を実行する装置の処理能力あるいは� ��要に応じて並列的にあるいは個別に実行さ� ��てもよい。また、本明細書においてシステ� ��とは、複数の装置の論理的集合構成であり� ��各構成の装置が同一筐体内にあるものには� ��らない。