(57)【要約】【課題】拡散行列切り替え機構（ＤＳＭ）を実現する拡張Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理構成を実現する。【解決手段】データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理構成において、Ｆ関数部の線形変換処理において複数の異なる複数の行列を選択的に適用する。行列としては、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列が選択される。本発明によりＤＳＭに基づく線形解析や差分解析に対する耐性の高い共通鍵ブロック暗号が実現される。【選択図】図５
2008051829.tif 000002
【特許請求の範囲】
【請求項１】
暗号処理装置であり、
非線形変換処理および線形変換処理を含むデータ変換処理を実行するＳＰ型Ｆ関数を複数ラウンド繰り返すＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理部を有し、
前記暗号処理部は、
データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する構成であり、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用する構成を有し、
前記２以上の複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列であり、
前記複数の異なる行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に繰り返し配置した構成を有することを特徴とする暗号処理装置。
【請求項２】
前記暗号処理部において利用される前記複数の異なる行列は、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続するｋ個（ただし、ｋは２以上の整数）のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［ＢｋＤ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［ＢｋＤ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする請求項１に記載の暗号処理装置。
【請求項３】
前記暗号処理部において利用される前記複数の異なる行列は、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続する２個のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［Ｂ２Ｄ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［Ｂ２Ｄ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする請求項１に記載の暗号処理装置。
【請求項４】
前記暗号処理部において利用される前記複数の異なる行列は、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続する２個のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［Ｂ２Ｌ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［Ｂ２Ｌ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする請求項１に記載の暗号処理装置。
【請求項５】
前記暗号処理部は、
前記複数の異なる行列を、ｎ個（ただし、ｎは２以上の整数）の異なる行列、
Ｍ０，Ｍ１，・・Ｍｎ−１としたとき、
これらの異なる行列Ｍ０，Ｍ１，・・Ｍｎ−１を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に順番に繰り返し配置した構成を有することを特徴とする請求項１に記載の暗号処理装置。
【請求項６】
前記暗号処理部は、
１つのラウンドに１つのＦ関数のみを実行する拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する構成であることを特徴とする請求項１〜５いずれかに記載の暗号処理装置。
【請求項７】
前記暗号処理部は、
１つのラウンドに複数のＦ関数を並列に実行する拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する構成であることを特徴とする請求項１〜５いずれかに記載の暗号処理装置。
【請求項８】
前記暗号処理部は、
ａ≧２の任意の整数、ｘ≧１の任意の整数としたとき、前記複数の異なる行列による異なる線形変換処理を実行するａ種類のＦ関数を利用したデータ系列数：ｄ＝２ａｘの拡張Ｆｅｓｉｔｅｌ構造を適用した暗号処理を実行する構成であり、
１つのラウンドにおいて、全種類（ａ種類）のＦ関数を均等にｘ個ずつ実行する構成であることを特徴とする請求項１〜５いずれかに記載の暗号処理装置。
【請求項９】
前記暗号処理部は、
１つのラウンドにおいて並列に実行するａｘ個のＦ関数を実行するＦ関数実行部と、
前記Ｆ関数実行部に対するデータ入出力制御を実行する制御部とを備えた構成であることを特徴とする請求項８に記載の暗号処理装置。
【請求項１０】
前記暗号処理部は、
前記複数の異なる行列による異なる線形変換処理を実行する複数のＦ関数実行部と、
前記複数のＦ関数実行部の利用シーケンスを設定に応じて変更する制御部とを備え、
前記制御部は、
（ａ）データ系列数ｄ＝２としたＦｅｉｓｔｅｌ構造による暗号処理、または、
（ｂ１）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて１つのＦ関数の実行のみを許容した暗号処理、または、
（ｂ２）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて複数のＦ関数の並列実行を許容した暗号処理、
上記（ａ），（ｂ１），（ｂ２）のいずれかの暗号処理を選択的に実行する構成であることを特徴とする請求項１〜５いずれかに記載の暗号処理装置。
【請求項１１】
前記制御部は、
暗号化または復号処理の対象となるデータのビット長に応じて、実行する処理形態を選択する構成であることを特徴とする請求項１０に記載の暗号処理装置。
【請求項１２】
暗号処理装置において、暗号処理を実行する暗号処理方法であり、
暗号処理部において、非線形変換処理および線形変換処理を含むデータ変換処理を実行するＳＰ型Ｆ関数を複数ラウンド繰り返すＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理ステップを有し、
前記暗号処理ステップは、
データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行するステップであり、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用した演算を実行する演算ステップを有し、
前記演算ステップにおいて適用する複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列であり、
前記演算ステップは、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数において、前記複数の異なる行列に基づく線形変換演算を実行するステップであることを特徴とする暗号処理方法。
【請求項１３】
前記複数の異なる行列は、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続するｋ個（ただし、ｋは２以上の整数）のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［ＢｋＤ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［ＢｋＤ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする請求項１２に記載の暗号処理方法。
【請求項１４】
前記複数の異なる行列は、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続する２個のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［Ｂ２Ｄ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［Ｂ２Ｄ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする請求項１２に記載の暗号処理方法。
【請求項１５】
前記複数の異なる行列は、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続する２個のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［Ｂ２Ｌ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［Ｂ２Ｌ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする請求項１２に記載の暗号処理方法。
【請求項１６】
前記複数の異なる行列を、ｎ個（ただし、ｎは２以上の整数）の異なる行列、
Ｍ０，Ｍ１，・・Ｍｎ−１としたとき、
前記演算ステップは、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数において、これらの異なる行列Ｍ０，Ｍ１，・・Ｍｎ−１を順番に繰り返し実行するステップであることを特徴とする請求項１２に記載の暗号処理方法。
【請求項１７】
前記暗号処理ステップは、
１つのラウンドに１つのＦ関数のみを実行する拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行するステップであることを特徴とする請求項１２〜１６いずれかに記載の暗号処理方法。
【請求項１８】
前記暗号処理ステップは、
１つのラウンドに複数のＦ関数を並列に実行する拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行するステップであることを特徴とする請求項１２〜１６いずれかに記載の暗号処理方法。
【請求項１９】
前記暗号処理ステップは、
ａ≧２の任意の整数、ｘ≧１の任意の整数としたとき、前記複数の異なる行列による異なる線形変換処理を実行するａ種類のＦ関数を利用したデータ系列数：ｄ＝２ａｘの拡張Ｆｅｓｉｔｅｌ構造を適用した暗号処理を実行するステップであり、
１つのラウンドにおいて、全種類（ａ種類）のＦ関数を均等にｘ個ずつ実行することを特徴とする請求項１２〜１６いずれかに記載の暗号処理方法。
【請求項２０】
前記暗号処理ステップは、
１つのラウンドにおいて並列に実行するａｘ個のＦ関数を実行するＦ関数実行部を適用して、前記Ｆ関数実行部に対するデータ入出力制御を実行する制御部の制御に従った暗号処理を実行するステップであることを特徴とする請求項１９に記載の暗号処理方法。
【請求項２１】
前記暗号処理ステップは、
前記複数の異なる行列による異なる線形変換処理を実行する複数のＦ関数実行部と、
前記複数のＦ関数実行部の利用シーケンスを設定に応じて変更する制御部とによってアン処理を実行し、前記制御部の制御によって、
（ａ）データ系列数ｄ＝２としたＦｅｉｓｔｅｌ構造による暗号処理、または、
（ｂ１）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて１つのＦ関数の実行のみを許容した暗号処理、または、
（ｂ２）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて複数のＦ関数の並列実行を許容した暗号処理、
上記（ａ），（ｂ１），（ｂ２）のいずれかの暗号処理を選択的に実行することを特徴とする請求項１２〜１６いずれかに記載の暗号処理方法。
【請求項２２】
前記制御部は、暗号化または復号処理の対象となるデータのビット長に応じて、実行する処理形態を選択することを特徴とする請求項２１に記載の暗号処理方法。
【請求項２３】
情報処理装置において暗号処理アルゴリズムを構築する暗号処理アルゴリズム構築方法であり、
情報処理装置における制御部が、データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理アルゴリズムの構成において、各ラウンドにおけるＦ関数において実行する線形変換処理に適用する少なくとも２以上の複数の異なる行列を決定する行列決定ステップと、
前記制御部が、前記行列決定ステップにおいて決定した複数の異なる行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に繰り返し配置する行列設定ステップを有し、
前記行列決定ステップは、
前記２以上の複数の異なる行列として、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列を適用行列として決定する処理を実行するステップであることを特徴とする暗号処理アルゴリズム構築方法。
【請求項２４】
暗号処理装置において、暗号処理を実行させるコンピュータ・プログラムであり、
暗号処理部において、非線形変換処理および線形変換処理を含むデータ変換処理を実行するＳＰ型Ｆ関数を複数ラウンド繰り返すＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行させる暗号処理ステップを有し、
前記暗号処理ステップは、
データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行させるステップであり、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用した演算を実行する演算ステップを含み、
前記演算ステップにおいて適用する複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列であり、
前記演算ステップは、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数において、前記複数の異なる行列に基づく線形変換演算を実行するステップであることを特徴とするコンピュータ・プログラム。
【請求項２５】
情報処理装置において暗号処理アルゴリズムを構築させるコンピュータ・プログラムであり、
情報処理装置における制御部に、データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理アルゴリズムの構成において、各ラウンドにおけるＦ関数において実行する線形変換処理に適用する少なくとも２以上の複数の異なる行列を決定させる行列決定ステップと、
前記制御部に、前記行列決定ステップにおいて決定した複数の異なる行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に繰り返し配置させる行列設定ステップを有し、
前記行列決定ステップは、
前記２以上の複数の異なる行列として、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列を適用行列として決定する処理を実行するステップであることを特徴とするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理装置、暗号処理アルゴリズム構築方法、および暗号処理方法、並びにコンピュータ・プログラムに関する。さらに詳細には、Ｆｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理装置、暗号処理アルゴリズム構築方法、および暗号処理方法、並びにコンピュータ・プログラムに関する。
【背景技術】
【０００２】
昨今、ネットワーク通信、電子商取引の発展に伴い、通信におけるセキュリティ確保が重要な問題となっている。セキュリティ確保の１つの方法が暗号技術であり、現在、様々な暗号化手法を用いた通信が実際に行なわれている。
【０００３】
例えばＩＣカード等の小型の装置中に暗号処理モジュールを埋め込み、ＩＣカードと、データ読み取り書き込み装置としてのリーダライタとの間でデータ送受信を行ない、認証処理、あるいは送受信データの暗号化、復号を行なうシステムが実用化されている。
【０００４】
暗号処理アルゴリズムには様々なものがあるが、大きく分類すると、暗号化鍵と復号鍵を異なる鍵、例えば公開鍵と秘密鍵として設定する公開鍵暗号方式と、暗号化鍵と復号鍵を共通の鍵として設定する共通鍵暗号方式とに分類される。
【０００５】
共通鍵暗号方式にも様々なアルゴリズムがあるが、その１つに共通鍵をベースとして複数の鍵を生成して、生成した複数の鍵を用いてブロック単位（６４ビット，１２８ビットなど）のデータ変換処理を繰り返し実行する方式がある。このような鍵生成方式とデータ変換処理を適用したアルゴリズムの代表的なものが共通鍵ブロック暗号方式である。
【０００６】
代表的な共通鍵ブロック暗号のアルゴリズムとしては、例えば米国標準暗号としてのＤＥＳ（Data Encryption Standard）アルゴリズムがあり、様々な分野において広く用いられている。
【０００７】
ＤＥＳに代表される共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を実行するラウンド関数部と、ラウンド関数（Ｆ関数）部の各ラウンドで適用する鍵を生成する鍵スケジュール部とに分けることができる。ラウンド関数部の各ラウンドで適用するラウンド鍵（副鍵）は、１つのマスター鍵（主鍵）に基づいて、鍵スケジュール部に入力されて生成され、各ラウンド関数部で適用される。
【０００８】
このようなラウンド関数を適用したアルゴリズムを実行する具体的な構造として、Ｆｅｉｓｔｅｌ構造が知られている。Ｆｅｉｓｔｅｌ構造はラウンド関数と呼ばれる変換関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。Ｆｅｉｓｔｅｌ構造を適用した暗号処理について記載した文献としては、例えば非特許文献１、非特許文献２がある。
【０００９】
しかし、例えばＦｅｉｓｔｅｌ構造を適用する共通鍵暗号処理においては、暗号解析による鍵の漏洩が問題となっている。暗号解析または攻撃手法の代表的な手法として、ある差分を持つ入力データ（平文）とその出力データ（暗号文）を多数解析することにより各ラウンド関数における適用鍵を解析する差分解析（差分解読法または差分攻撃とも呼ばれる）や、平文と対応暗号文に基づく解析を行う線形解析（線形解読法または線形攻撃とも呼ばれる）が知られている。
【００１０】
暗号解析による鍵の解析が容易であるということは、その暗号処理の安全性が低いということになる。従来の暗号アルゴリズムにおいては、ラウンド関数（Ｆ関数）部の線形変換部において適用する処理（変換行列）が、各段のラウンドにおいて等しいものであったため解析が行いやすく、結果として鍵の解析の容易性を招いていた。
【００１１】
このような問題に対処する構成として、Ｆｅｉｓｔｅｌ構造のラウンド関数（Ｆ関数）部の線形変換部に２つ以上の異なる行列を配置する構成が提案された。この技術は拡散行列切り替え機構（ＤＳＭ：Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ，以下ＤＳＭ）と呼ばれる。このＤＳＭにより、差分攻撃や線形攻撃に対する耐性を向上させることが可能となる。
【００１２】
この拡散行列切り替え機構（ＤＳＭ）は、通常の２つのデータ系列を持つＦｅｉｓｔｅｌ構造に対する適用構成として示されている。一方、このような、一般的な２つのデータ系列を持つＦｅｉｓｔｅｌ構造と異なり、３本以上のデータ系列を持つ拡張型のＦｅｉｓｔｅｌ構造がある。しかし、このような３本以上のデータ系列を持つ拡張型のＦｅｉｓｔｅｌ構造において、上述の拡散行列切り替え機構（ＤＳＭ）を適用して、差分攻撃や線形攻撃に対する耐性を向上させる構成についての開示はない。
【非特許文献１】K. Nyberg, "Generalized Feistel networks", ASIACRYPT'96, SpringerVerlag, 1996, pp.91--104.
【非特許文献２】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
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明は、上記問題点に鑑みてなされたものであり、線形解析や差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムを実現する暗号処理装置、暗号処理アルゴリズム構築方法、および暗号処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【００１４】
さらに具体的には、２つのデータ系列を持つＦｅｉｓｔｅｌ構造を拡張したＦｅｉｓｔｅｌ構造、すなわち、例えば３つ、４つなど、２以上の任意のデータ系列を持つ拡張型のＦｅｉｓｔｅｌ構造において、複数の異なる線形変換行列を適用したラウンド関数部を設定して、線形解析や差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムを実現する暗号処理装置、暗号処理アルゴリズム構築方法、および暗号処理方法、並びにコンピュータ・プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明の第１の側面は、
暗号処理装置であり、
非線形変換処理および線形変換処理を含むデータ変換処理を実行するＳＰ型Ｆ関数を複数ラウンド繰り返すＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理部を有し、
前記暗号処理部は、
データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する構成であり、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用する構成を有し、
前記２以上の複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列であり、
前記複数の異なる行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に繰り返し配置した構成を有することを特徴とする暗号処理装置にある。
【００１６】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部において利用される前記複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続するｋ個（ただし、ｋは２以上の整数）のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［ＢｋＤ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［ＢｋＤ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする。
【００１７】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部において利用される前記複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続する２個のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［Ｂ２Ｄ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［Ｂ２Ｄ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする。
【００１８】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部において利用される前記複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続する２個のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［Ｂ２Ｌ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［Ｂ２Ｌ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする。
【００１９】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部は、前記複数の異なる行列を、ｎ個（ただし、ｎは２以上の整数）の異なる行列、Ｍ０，Ｍ１，・・Ｍｎ−１としたとき、これらの異なる行列Ｍ０，Ｍ１，・・Ｍｎ−１を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に順番に繰り返し配置した構成を有することを特徴とする。
【００２０】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部は、１つのラウンドに１つのＦ関数のみを実行する拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する構成であることを特徴とする。
【００２１】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部は、１つのラウンドに複数のＦ関数を並列に実行する拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する構成であることを特徴とする。
【００２２】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部は、
ａ≧２の任意の整数、ｘ≧１の任意の整数としたとき、前記複数の異なる行列による異なる線形変換処理を実行するａ種類のＦ関数を利用したデータ系列数：ｄ＝２ａｘの拡張Ｆｅｓｉｔｅｌ構造を適用した暗号処理を実行する構成であり、
１つのラウンドにおいて、全種類（ａ種類）のＦ関数を均等にｘ個ずつ実行する構成であることを特徴とする。
【００２３】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部は、１つのラウンドにおいて並列に実行するａｘ個のＦ関数を実行するＦ関数実行部と、前記Ｆ関数実行部に対するデータ入出力制御を実行する制御部とを備えた構成であることを特徴とする。
【００２４】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部は、前記複数の異なる行列による異なる線形変換処理を実行する複数のＦ関数実行部と、前記複数のＦ関数実行部の利用シーケンスを設定に応じて変更する制御部とを備え、前記制御部は、
（ａ）データ系列数ｄ＝２としたＦｅｉｓｔｅｌ構造による暗号処理、または、
（ｂ１）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて１つのＦ関数の実行のみを許容した暗号処理、または、
（ｂ２）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて複数のＦ関数の並列実行を許容した暗号処理、
上記（ａ），（ｂ１），（ｂ２）のいずれかの暗号処理を選択的に実行する構成であることを特徴とする。
【００２５】
さらに、本発明の暗号処理装置の一実施態様において、前記制御部は、暗号化または復号処理の対象となるデータのビット長に応じて、実行する処理形態を選択する構成であることを特徴とする。
【００２６】
さらに、本発明の第２の側面は、
暗号処理装置において、暗号処理を実行する暗号処理方法であり、
暗号処理部において、非線形変換処理および線形変換処理を含むデータ変換処理を実行するＳＰ型Ｆ関数を複数ラウンド繰り返すＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理ステップを有し、
前記暗号処理ステップは、
データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行するステップであり、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用した演算を実行する演算ステップを有し、
前記演算ステップにおいて適用する複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列であり、
前記演算ステップは、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数において、前記複数の異なる行列に基づく線形変換演算を実行するステップであることを特徴とする暗号処理方法にある。
【００２７】
さらに、本発明の暗号処理方法の一実施態様において、前記複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続するｋ個（ただし、ｋは２以上の整数）のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［ＢｋＤ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［ＢｋＤ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする。
【００２８】
さらに、本発明の暗号処理方法の一実施態様において、前記複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続する２個のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［Ｂ２Ｄ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［Ｂ２Ｄ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする。
【００２９】
さらに、本発明の暗号処理方法の一実施態様において、前記複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続する２個のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［Ｂ２Ｌ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［Ｂ２Ｌ］が３以上となる条件を満足する複数の異なる行列であることを特徴とする。
【００３０】
さらに、本発明の暗号処理方法の一実施態様において、前記複数の異なる行列を、ｎ個（ただし、ｎは２以上の整数）の異なる行列、Ｍ０，Ｍ１，・・Ｍｎ−１としたとき、前記演算ステップは、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数において、これらの異なる行列Ｍ０，Ｍ１，・・Ｍｎ−１を順番に繰り返し実行するステップであることを特徴とする。
【００３１】
さらに、本発明の暗号処理方法の一実施態様において、前記暗号処理ステップは、１つのラウンドに１つのＦ関数のみを実行する拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行するステップであることを特徴とする。
【００３２】
さらに、本発明の暗号処理方法の一実施態様において、前記暗号処理ステップは、１つのラウンドに複数のＦ関数を並列に実行する拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行するステップであることを特徴とする。
【００３３】
さらに、本発明の暗号処理方法の一実施態様において、前記暗号処理ステップは、
ａ≧２の任意の整数、ｘ≧１の任意の整数としたとき、前記複数の異なる行列による異なる線形変換処理を実行するａ種類のＦ関数を利用したデータ系列数：ｄ＝２ａｘの拡張Ｆｅｓｉｔｅｌ構造を適用した暗号処理を実行するステップであり、
１つのラウンドにおいて、全種類（ａ種類）のＦ関数を均等にｘ個ずつ実行することを特徴とする。
【００３４】
さらに、本発明の暗号処理方法の一実施態様において、前記暗号処理ステップは、１つのラウンドにおいて並列に実行するａｘ個のＦ関数を実行するＦ関数実行部を適用して、前記Ｆ関数実行部に対するデータ入出力制御を実行する制御部の制御に従った暗号処理を実行するステップであることを特徴とする。
【００３５】
さらに、本発明の暗号処理方法の一実施態様において、前記暗号処理ステップは、前記複数の異なる行列による異なる線形変換処理を実行する複数のＦ関数実行部と、前記複数のＦ関数実行部の利用シーケンスを設定に応じて変更する制御部とによってアン処理を実行し、前記制御部の制御によって、
（ａ）データ系列数ｄ＝２としたＦｅｉｓｔｅｌ構造による暗号処理、または、
（ｂ１）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて１つのＦ関数の実行のみを許容した暗号処理、または、
（ｂ２）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて複数のＦ関数の並列実行を許容した暗号処理、
上記（ａ），（ｂ１），（ｂ２）のいずれかの暗号処理を選択的に実行することを特徴とする。
【００３６】
さらに、本発明の暗号処理方法の一実施態様において、前記制御部は、暗号化または復号処理の対象となるデータのビット長に応じて、実行する処理形態を選択することを特徴とする。
【００３７】
さらに、本発明の第３の側面は、
情報処理装置において暗号処理アルゴリズムを構築する暗号処理アルゴリズム構築方法であり、
情報処理装置における制御部が、データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理アルゴリズムの構成において、各ラウンドにおけるＦ関数において実行する線形変換処理に適用する少なくとも２以上の複数の異なる行列を決定する行列決定ステップと、
前記制御部が、前記行列決定ステップにおいて決定した複数の異なる行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に繰り返し配置する行列設定ステップを有し、
前記行列決定ステップは、
前記２以上の複数の異なる行列として、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列を適用行列として決定する処理を実行するステップであることを特徴とする暗号処理アルゴリズム構築方法にある。
【００３８】
さらに、本発明の第４の側面は、
暗号処理装置において、暗号処理を実行させるコンピュータ・プログラムであり、
暗号処理部において、非線形変換処理および線形変換処理を含むデータ変換処理を実行するＳＰ型Ｆ関数を複数ラウンド繰り返すＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行させる暗号処理ステップを有し、
前記暗号処理ステップは、
データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行させるステップであり、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用した演算を実行する演算ステップを含み、
前記演算ステップにおいて適用する複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列であり、
前記演算ステップは、
拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数において、前記複数の異なる行列に基づく線形変換演算を実行するステップであることを特徴とするコンピュータ・プログラムにある。
【００３９】
さらに、本発明の第５の側面は、
情報処理装置において暗号処理アルゴリズムを構築させるコンピュータ・プログラムであり、
情報処理装置における制御部に、データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理アルゴリズムの構成において、各ラウンドにおけるＦ関数において実行する線形変換処理に適用する少なくとも２以上の複数の異なる行列を決定させる行列決定ステップと、
前記制御部に、前記行列決定ステップにおいて決定した複数の異なる行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に繰り返し配置させる行列設定ステップを有し、
前記行列決定ステップは、
前記２以上の複数の異なる行列として、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列を適用行列として決定する処理を実行するステップであることを特徴とするコンピュータ・プログラムにある。
【００４０】
なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能なコンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、ＣＤやＦＤ、ＭＯなどの記録媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【００４１】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００４２】
本発明の一実施例の構成によれば、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行するＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理において、２つのデータ系列を持つＦｅｉｓｔｅｌ構造を拡張したＦｅｉｓｔｅｌ構造、すなわち、例えば３つ、４つなど、２以上の任意のデータ系列を持つ拡張型のＦｅｉｓｔｅｌ構造において、複数の異なる線形変換行列を適用したラウンド関数部を設定することで拡散行列切り替え機構（ＤＳＭ）を実現し、線形解析や差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムの構築および暗号処理の実行が可能となる。
【００４３】
本発明の一実施例の構成によれば、データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する構成において、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用する構成を有し、２以上の複数の異なる行列として、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列として設定することで、拡散行列切り替え機構（ＤＳＭ）を実現し、線形解析や差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムの構築および暗号処理の実行が可能となる。
【００４４】
さらに、本発明の一実施例の構成によれば、複数の異なる行列による異なる線形変換処理を実行するａ（ａ≧２）種類のＦ関数を利用したデータ系列数：ｄ＝２ａｘの拡張Ｆｅｓｉｔｅｌ構造（ｘ≧１）を適用した暗号処理を実行する構成において、１つのラウンドにおいて、全種類（ａ種類）のＦ関数を均等にｘ個ずつ実行する構成としたので、無駄な回路を設けることのない小型の暗号処理装置が実現される。
【００４５】
さらに、本発明の一実施例の構成によれば、複数の異なる行列による異なる線形変換処理を実行する複数のＦ関数実行部を構成して、複数のＦ関数実行部の利用シーケンスを設定に応じて変更する構成としたことで、
（ａ）データ系列数ｄ＝２としたＦｅｉｓｔｅｌ構造による暗号処理、または、
（ｂ１）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて１つのＦ関数の実行のみを許容した暗号処理、または、
（ｂ２）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて複数のＦ関数の並列実行を許容した暗号処理、
上記（ａ），（ｂ１），（ｂ２）のいずれかの暗号処理を選択的に実行することを可能とした暗号処理装置が実現される。
【発明を実施するための最良の形態】
【００４６】
以下、本発明の暗号処理装置、および暗号処理方法、並びにコンピュータ・プログラムの詳細について説明する。説明は、以下の項目に従って行なう。
１．ＳＰ型Ｆ関数を持つＦｅｉｓｔｅｌ構造
２．分岐数演算関数と耐性評価関数
２−１．分岐数演算関数：Ｂｒａｎｃｈ（）
２−２．差分攻撃に対する耐性評価指標
２−３．線形攻撃に対する耐性評価指標
３．２つのデータ系列を持つＦｅｉｓｔｅｌ構造に対するＤＳＭの設定法
４．拡張Ｆｅｉｓｔｅｌ構造におけるＤＳＭの設定
４−１．拡張Ｆｅｉｓｔｅｌ構造について
４−２．拡張Ｆｅｉｓｔｅｌ構造において差分攻撃に対する耐性を向上させるための構成
４−２−１．最小分岐数Ｂ２Ｄの値を３以上とするＦ関数中の行列選択構成
４−２−２．最小分岐数ＢｋＤの値を３以上とするＦ関数中の行列選択構成
４−３．拡張Ｆｅｉｓｔｅｌ構造において線形攻撃に対する耐性を向上させるための構成
４−３−１．最小分岐数Ｂ２Ｌの値を３以上とするＦ関数中の行列選択構成
５．特定の形を持つ拡張Ｆｅｉｓｔｅｌ構造に対するＤＳＭの利用構成
５−１．拡張Ｆｅｉｓｔｅｌ構造のタイプ１に対するＤＳＭの適用
５−２．拡張Ｆｅｉｓｔｅｌ構造のタイプ２に対するＤＳＭの適用
６．拡張Ｆｅｉｓｔｅｌ構造各タイプのアクティブＳ−ｂｏｘ数と、Ｆ関数中の線形変換行列に基づく最小分岐数との関係式の証明
６−１．拡張Ｆｅｉｓｔｅｌ構造のタイプ１のアクティブＳ−ｂｏｘ数と、Ｆ関数中の線形変換行列に基づく最小分岐数との関係式の証明
６−２．拡張Ｆｅｉｓｔｅｌ構造のタイプ２のアクティブＳ−ｂｏｘ数と、Ｆ関数中の線形変換行列に基づく最小分岐数との関係式の証明
７．Ｆ関数の設定および利用処理の工夫に基づく実装における改良構成
７−１．拡張Ｆｅｉｓｔｅｌのタイプ２の効率的なＦ関数配置方法
７−２．Ｆｅｉｓｔｅｌ構造と拡張Ｆｅｉｓｔｅｌ構造における部品の共通化
８．本発明の暗号処理および暗号アルゴリズム構築処理のまとめ
９．暗号処理装置の構成例
【００４７】
［１．ＳＰ型Ｆ関数を持つＦｅｉｓｔｅｌ構造］
まず、ＳＰ型Ｆ関数を持つＦｅｉｓｔｅｌ構造について説明する。共通鍵ブロック暗号のデザインとして、Ｆｅｉｓｔｅｌ構造が知られている。Ｆｅｉｓｔｅｌ構造はラウンド関数と呼ばれる基本処理単位の繰り返しにより、平文を暗号文に変換する構造を持つ。
【００４８】
図１を参照して、Ｆｅｉｓｔｅｌ構造の基本構成について説明する。図１には、ｒラウンドのラウンド数＝ｒを持つ２つのデータ系列を持つＦｅｉｓｔｅｌ構造の例を示している。なお、ラウンド数ｒは、設計の段階で決定されるパラメータであり、例えば入力される鍵の長さに応じて変更可能な値である。
【００４９】
図１に示すＦｅｉｓｔｅｌ構造において、暗号化対象として入力される平文の長さを２ｍｎビットとする。ただし、ｍ，ｎは共に整数である。初めに、２ｍｎビットの平文を、ｍｎビットの２つの入力データＰＬ（Plain-Left）１０１，ＰＲ(Plain-Right)１０２に分割し、これを入力値とする。
【００５０】
Ｆｅｉｓｔｅｌ構造はラウンド関数とよばれる基本処理単位の繰り返しで表現され、各ラウンドに含まれるデータ変換関数はＦ関数１２０と呼ばれる。図１の構成では、Ｆ関数（ラウンド関数）１２０がｒ段繰り返された構成例を示している。
【００５１】
例えば第１番目のラウンドでは、ｍｎビットの入力データＸと、鍵生成部（図示せず）から入力されるｍｎビットのラウンド鍵Ｋ１１０３がＦ関数１２０に入力され、Ｆ関数１２０におけるデータ変換処理の後にｍｎビットのデータＹを出力する。出力はもう片方の前段からの入力データ（第１段の場合は入力データＰＬ）と排他的論理和部１０４において、排他的論理和演算がなされ、ｍｎビットの演算結果が次のラウンド関数へと出力される。この処理、すなわちＦ関数を定められたラウンド数（ｒ）だけ繰り返し適用して暗号化処理が完了し、暗号文の分割データＣＬ（Cipher-Left）、ＣＲ（Cipher-Right）が出力される。以上の構成より、Ｆｅｉｓｔｅｌ構造の復号処理はラウンド鍵を挿入する順序を逆にするだけでよく、逆関数を構成する必要がないことが導かれる。
【００５２】
各ラウンドの関数として設定されるＦ関数１２０の構成について、図２を参照して説明する。図２（ａ）は、１つのラウンドにおけるＦ関数１２０に対する入力および出力を示す図であり、図２（ｂ）は、Ｆ関数１２０の構成の詳細を示す図である。Ｆ関数１２０は、図２（ｂ）に示すように、非線形変換層（Ｓ層）と線形変換層（Ｐ層）を接続したいわゆるＳＰ型の構成を有する。
【００５３】
図２に示すＦ関数１２０は、入出力ビット長がｍ×ｎ（ｍ，ｎ：整数）ビットの設定を持つ関数である。ＳＰ型Ｆ関数内部では初めに鍵データＫｉとデータＸｉとの排他的論理和が実行され、次に非線形変換層（Ｓ層）が適用され、続いて線形変換層（Ｐ層）が適用される。
【００５４】
具体的には非線形変換層（Ｓ層）は、Ｓボックス（Ｓ−ｂｏｘ）１２１と呼ばれるｎビット入力ｎビット出力の非線形変換テーブルがｍ個並んだものであり、ｍｎビットのデータはｎビットずつ分割されてそれぞれ対応するＳボックス（Ｓ−ｂｏｘ）１２１に入力されデータが変換される。各Ｓボックスでは、例えば変換テーブルを適用した非線形変換処理が実行される。
【００５５】
線形変換層（Ｐ層）は線形変換部１２２によって構成され、線形変換部１２２は、Ｓボックス１２１からの出力データであるｍｎビットの出力値Ｚを入力し、この入力に対して線形変換を施しｍｎビットの結果を出力する。線形変換部１２２は、入力ビット位置の入れ替え処理などの線形変換処理を実行して、ｍｎビットの出力値Ｙを出力する。この出力値Ｙが前段からの入力データと排他的論理和され、次のラウンドのＦ関数の入力値とされる。
【００５６】
なお、以下に説明する本実施例の構成では、線形変換層（Ｐ層）としての線形変換部１２２において実行する線形変換はＧＦ（２）上で定義されるｍｎ×ｍｎの行列を適用して行なわれる線形変換であると定義し、また、第ｉラウンド目に含まれる行列をＭｉと呼ぶものとする。なお、本発明において説明する構成における非線形変換部としてのＳボックスと、線形変換は、いずれも全単射であるものとする。
【００５７】
［２．分岐数演算関数と耐性評価関数］
次に、本発明を理解するために必要となる分岐数演算関数と耐性評価関数について説明する。
（２−１．分岐数演算関数：Ｂｒａｎｃｈ（））
上述したＦ関数内の線形変換層（Ｐ層）としての線形変換部１２２において実行される線形変換の例としての最適拡散変換（Ｏｐｔｉｍａｌ  Ｄｉｆｆｕｓｉｏｎ  Ｍａｐｐｉｎｇｓ）の分岐数演算関数：Ｂｒａｎｃｈ（）を以下のように定義する。
【００５８】
ｎ×ａビットデータからｎ×ｂビットデータへの線形変換を行う写像、
θ：｛０，１｝ｎａ→｛０，１｝ｎｂ
に対して分岐数：Ｂｒａｎｃｈｎ（θ）を次のように定義する。
Ｂｒａｎｃｈｎ（θ）＝ｍｉｎα≠０｛ｈｗｎ（α）＋ｈｗｎ（θ（α））｝
ただし、ｍｉｎα≠０｛Ｘα｝は、α≠０を満たすすべてのＸαのうちの最小値を表すものとし、ｈｗｎ（Ｙ）はビット列Ｙをｎビットごとに区切って表したときに、ｎビットのデータすべてが０ではない（非ゼロ）要素の数を返す関数とする。
なお、このとき、Ｂｒａｎｃｈｎ（θ）がｂ＋１であるような写像θを最適拡散変換と定義する。
【００５９】
（２−２．差分攻撃に対する耐性評価指標）
Ｆｅｉｓｔｅｌ構造を適用する共通鍵暗号処理においては、暗号解析による鍵の漏洩が問題となる。暗号解析または攻撃手法の代表的な手法として、ある差分（ΔＸ）を持つ入力データ（平文）とその出力データ（暗号文）を多数解析することにより各ラウンド関数における適用鍵を解析する差分解析（差分解読法または差分攻撃とも呼ばれる）や、平文と対応暗号文に基づく解析を行う線形解析（線形解読法または線形攻撃とも呼ばれる）が知られている。
【００６０】
差分攻撃に対する耐性を図る指標として、差分の接続関係を表現した差分パスに含まれる差分アクティブＳ−ｂｏｘの最小数が適用可能である。
差分パスとは、暗号化関数中の鍵データを除くすべてのデータ部分に対して特定の差分値を指定したものである。差分値は自由に決められるものではなく変換処理の前後の差分値は互いに関連しあっている。線形変換処理の前後では、入力差分と出力差分の関係は一対一に決定される。非線形変換の前後では、入力差分と出力差分の関係は一対一にはきまらないが、確率という概念が導入される。ある入力差分と出力差分に対する確率は事前に計算することができるものとする。すべての出力に対する確率をすべて足し合わせると１となっている。
【００６１】
ＳＰ型のＦ関数を持ったＦｅｉｓｔｅｌ構造においては、非線形変換はＳ−ｂｏｘによる処理の部分のみである。したがって、この場合、０以外の確率をもつ差分パスとは平文（入力）に対する差分値から始まって暗号文（出力）の差分値までに至る差分データの集合であり、すべてのＳ−ｂｏｘの前後で与えられる差分値は０以外の確率をもつものである。０以外の確率をもつある差分パスのＳ−ｂｏｘに入力される差分値が０でないものを差分アクティブＳ−ｂｏｘと呼ぶものとする。０以外の確率を持つすべての差分パスのアクティブＳ−ｂｏｘの数のうちで最も少ない数を最小差分アクティブＳ−ｂｏｘ数とよび、この数値が差分攻撃に対する安全性指標として知られている。なお、すべての差分値が０であるような差分パスは、確率が１となり攻撃として意味をなさないので、以降では考慮しない。
【００６２】
本発明の一実施例においては、この最小差分アクティブＳ−ｂｏｘ数を大きく保証することにより差分攻撃に対する安全性を高める構成を持つ。
【００６３】
（２−３．線形攻撃に対する耐性評価指標）
さらに、線形攻撃に対する耐性を図る指標として、線形マスクの接続関係を表現した線形パス（線形近似と呼ばれることが多いが、差分と対応させるためここではパスという言葉を用いる）に含まれる線形アクティブＳ−ｂｏｘの最小数が適用可能である。
【００６４】
線形パスとは、暗号化関数中の鍵データを除くすべてのデータ部分に対して特定の線形マスク値を指定したものである。線形マスク値は自由に決められるものではなく変換処理の前後の線形値は互いに関連しあっている。線形変換処理の前後では、入力線形マスク値と出力線形マスク値の関係は一対一に決定される。非線形変換の前後では、入力線形マスク値と出力線形マスク値の関係は一対一にはきまらないが、確率という概念が導入される。入力線形マスク値に対して、出力されうるひとつ以上の線形マスク値の集合が存在し、それぞれが出力される確率を事前に計算することができる。すべての出力に対する確率をすべて足し合わせると１となっている。
【００６５】
ＳＰ型のＦ関数を持ったＦｅｉｓｔｅｌ構造においては、非線形変換はＳ−ｂｏｘによる処理の部分のみである。したがって、この場合、０以外の確率をもつ線形パスとは平文（入力）に対する線形値から始まって暗号文（出力）の線形値までに至る線形マスク値データの集合であり、すべてのＳ−ｂｏｘの前後で与えられる線形値は０以外の確率をもつものである。０以外の確率をもつある線形パスのＳ−ｂｏｘに入力される線形値が０でないものを線形アクティブＳ−ｂｏｘと呼ぶものとする。０以外の確率を持つすべての線形パスのアクティブＳ−ｂｏｘの数のうちで最も少ない数を最小線形アクティブＳ−ｂｏｘ数とよび、この数値が線形攻撃に対する安全性指標として知られている。なお、すべての線形マスク値が０であるような線形パスは、確率が１となり攻撃として意味をなさないので、以降では考慮しない。
【００６６】
本発明の一実施例においては、この最小線形アクティブＳ−ｂｏｘ数を大きく保証することにより線形攻撃に対する安全性を高める。
【００６７】
［３．２つのデータ系列を持つＦｅｉｓｔｅｌ構造に対するＤＳＭの設定法］
先に説明したように、Ｆｅｉｓｔｅｌ構造を適用した暗号処理において、上述した差分攻撃や線形攻撃に対する耐性を高める構成として、拡散行列切り替え機構（ＤＳＭ：Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ，以下ＤＳＭ）を適用した構成が提案されている。ＤＳＭは、Ｆｅｉｓｔｅｌ構造のラウンド関数（Ｆ関数）部の線形変換部に２つ以上の異なる行列を配置する構成である。このＤＳＭにより、最小線形アクティブＳ−ｂｏｘ数を大きく保証することが可能となり、差分攻撃や線形攻撃に対する耐性を向上させることが可能となる。
【００６８】
このＤＳＭについて、その概要を説明する。Ｆｅｉｓｔｅｌ構造において、拡散行列切り替え機構（ＤＳＭ）を適用した場合、Ｆｅｉｓｔｅｌ構造を構成するラウンド関数（Ｆ関数）部の線形変換部（Ｐ層）において適用する行列は、複数の異なる行列となる。例えば、図１に示すようなｒラウンドのＦｅｉｓｔｅｌ構造の各ラウンドにおける適用行列は、全て同じ線形変換行列として設定されるのではなく、少なくとも２種類以上の行列が、特定の規則に従って配列されることになる。
【００６９】
例えば、２つの線形変換行列Ｍ０，Ｍ１によって、拡散行列切り替え機構（ＤＳＭ）を実現したＦｅｉｓｔｅｌ構造例を図３に、３つの線形変換行列Ｍ０，Ｍ１，Ｍ２によって、拡散行列切り替え機構（ＤＳＭ）を実現したＦｅｉｓｔｅｌ構造例を図４に示す。
【００７０】
図３に示すＦｅｉｓｔｅｌ構造例において、２つの線形変換行列Ｍ０，Ｍ１は、異なる行列によって構成される。また、図４に示すＦｅｉｓｔｅｌ構造例においては、３つの線形変換行列Ｍ０，Ｍ１，Ｍ２は、異なる行列によって構成される。
【００７１】
拡散行列切り替え機構（ＤＳＭ）を実現するためには、適用する行列が所定の条件を満たすことが必要となる。この条件の１つが、上述した分岐数（Ｂｒａｎｃｈ）に関する制約である。以下、この制約について説明する。
【００７２】
Ｆｅｉｓｔｅｌ構造におけるラウンド関数部の線形変換に適用する複数の異なる行列Ｍ０〜Ｍｎそれぞれの分岐数において、
適用行列中の分岐数の最小値：Ｂ１Ｄと、
適用する複数の行列の結合行列に対応する分岐数の最小値：Ｂ２Ｄ，Ｂ３Ｄ，Ｂ２Ｌ
を以下のように定義する。
【数１】
2008051829.tif 000003
【００７３】
上記式において、
Ｍｉは、Ｆｅｉｓｔｅｌ構造における第ｉラウンドの線形変換処理に適用する線形変換行列を示し、
［Ｍｉ｜Ｍｉ＋２｜・・］は、Ｍｉ｜Ｍｉ＋２｜・・各行列の連結により得られる結合行列を示し、
ｔＭは、行列Ｍの転値行列、Ｍ−１は、行列Ｍの逆行列を示す。
【００７４】
上記式において、：Ｂ２Ｄ，Ｂ３Ｄ，Ｂ２Ｌは、具体的には、Ｆｅｉｓｔｅｌ構造における１つ飛びで連続する２ラウンドもしくは３ラウンドのＦ関数に含まれる行列を結合した行列の分岐数の最小値を表している。
【００７５】
例えば、上記の各分岐数が以下の条件、すなわち、
Ｂ２Ｄ≧３，  Ｂ３Ｄ≧３，  Ｂ２Ｌ≧３、
上記条件を満足させるように各行列を設定することで、Ｆｅｉｓｔｅｌ構造において、差分攻撃や線形攻撃に対する耐性を向上させることが出来ることが知られている。
なお、Ｂ１Ｄ，Ｂ２Ｄ，Ｂ３Ｄ，Ｂ２Ｌにおける各添え字は以下の意味を持つものである。
ＢｎＤのｎは結合する行列数、ＢｎＤのＤは差分攻撃（Ｄｉｆｆｅｒｅｎｔｉａｌ  Ａｔｔａｃｋ）に対する耐性を持つための条件であることを示し、ＢｎＬのＬは線形攻撃（Ｌｉｎｅａｒ  Ａｔｔａｃｋ）に対する耐性を持つための条件であることを示している。
【００７６】
［４．拡張Ｆｅｉｓｔｅｌ構造におけるＤＳＭの設定］
本発明では、２つのデータ系列を持つＦｅｉｓｔｅｌ構造ではなく、例えば３系列や、４系列など２以上の任意のデータ系列を持つＦｅｉｓｔｅｌ構造に対して拡散行列切り替え機構（ＤＳＭ）を実現する構成を提案する。以下、この構成について、詳細に説明する。
【００７７】
本発明において取り扱うのはＳＰ型のＦ関数を使う点では上記の２つのデータ系列を持つＦｅｉｓｔｅｌ構造と同じであるが、データ系列数の分割数を一般化してｄとした拡張Ｆｅｉｓｔｅｌ構造を対象とする。ただしｄは２以上の整数である。
【００７８】
上述したように、データ系列数＝２に限定したＦｅｉｓｔｅｌ構造に対するＤＳＭの適用構成については提案されていたが、データ系列数ｄをｄ≧２とした任意数のｄを持つ拡張Ｆｅｉｓｔｅｌ構造に対して、ＤＳＭを適用して耐性を向上させる方法が知られていなかった。本発明は、ｄ≧２とした任意数のデータ系列数ｄを持つ拡張Ｆｅｉｓｔｅｌ構造に対して拡散行列切り替え機構（ＤＳＭ）を適用して差分攻撃や線形攻撃に対する耐性を向上させる構成を実現するものである。
以下、本発明の具体的構成および処理例について説明する。
【００７９】
（４−１．拡張Ｆｅｉｓｔｅｌ構造について）
以下、拡張Ｆｅｉｓｔｅｌ構造の定義について、図５を参照して説明する。本明細書では拡張Ｆｅｉｓｔｅｌ構造を以下のように定義する。
１．ｄ本（ｄは２以上）のデータ系列をもち、各データ系列のサイズはｍｎビット。
２．Ｆ関数の入出力サイズはｍｎビット。
３．ラウンドという処理単位をもち、ラウンド内では一つまたは複数のデータ系列に対してＦ関数による変換処理が施され、その結果は別のデータ系列に排他的論理和がなされる。ただし、２つ以上のＦ関数が１ラウンド内に含まれる場合はすべてのＦ関数の入出力となるデータ系列には重複する系列が存在しないものとする。
【００８０】
上記の定義によって構築される拡張Ｆｅｉｓｔｅｌ構造の例を図５を参照して説明する。
上記定義１．ｄ本（ｄは２以上）のデータ系列をもち、各データ系列のサイズはｍｎビット。
この定義について図５を参照して説明する。図５において、データ系列１〜ｄの各々の各データ系列の入出力サイズがｍｎビットであり、入出力の総ビット数はｄｍｎビットであることを意味している。
【００８１】
上記定義２．Ｆ関数の入出力サイズはｍｎビット。
この定義について図５を参照して説明する。例えばＦ関数２０２にはデータ系列２から上段の排他的論理和（ＸＯＲ）演算部２０１から演算結果としてのｍｎビットが入力され、さらに、ラウンド鍵Ｋが入力されて演算処理が実行される。この演算処理は、図２（ｂ）を参照して説明した処理であり、Ｓボックスにおける非線形変換と、線形変換部における線形変換行列Ｍｉを適用した線形変換処理が含まれる。Ｆ関数２０２の出力はｍｎビットであり、データ系列４の排他的論理和（ＸＯＲ）演算部２０３に入力される。
【００８２】
上記定義３．ラウンドという処理単位をもち、ラウンド内では一つまたは複数のデータ系列に対してＦ関数による変換処理が施され、その結果は別のデータ系列に排他的論理和がなされる。ただし、２つ以上のＦ関数が１ラウンド内に含まれる場合はすべてのＦ関数の入出力となるデータ系列には重複する系列が存在しないものとする。
この定義について図５を参照して説明する。図５にはｒラウンドの構成を持つ拡張Ｆｅｉｓｔｅｌ構造を示している。各ラウントには１つ以上のＦ関数が含まれ、その結果は別のデータ系列に排他的論理和がなされる。図５に示すラウンドｎは、複数のＦ関数が１ラウンド内に含まれる。図５に示すＦ関数２１１とＦ関数２１２である。
【００８３】
このように、１つのラウンドに複数のＦ関数が含まれる場合、各Ｆ関数の入出力系列は、それぞれ異なるデータ系列であり、重複したデータ系列が入出力系列として適用されない設定とする。
図５に示すＦ関数２１１の入力データ系列はデータ系列１、出力データ系列はデータ系列２であり、
Ｆ関数２１２の入力データ系列はデータ系列５以上のいずれか、出力データ系列はデータ系列３であり、
いずれの入出力データ系列も重複しない設定とされる。
【００８４】
なお、図５にも示すように、本明細書では、Ｆ関数は［Ｆ］、ラウンド鍵は［Ｋ］として示す。これらの各識別子Ｆ，Ｋに設定した添え字は以下の意味を持つ。
Ｆｉｎ、Ｋｉｎのｉはラウンドを示し、ｎは、同一ラウンドにおけるＦ関数またはラウンド鍵の識別番号を示す。
なお、図には示していないが、以下の説明において、各ラウンドにおけるＦ関数の線形変換部において適用される線形変換行列は［Ｍ］として示し、Ｍに設定する添え字も上記と同様、
Ｍｉｎのｉはラウンドを示し、ｎは、同一ラウンドに設定された複数のＦ関数各々に対応する線形変換行列の識別番号を示すものとする。
【００８５】
図６は、上述の定義を満足する７つのデータ系列（ｄ＝７）を持つ拡張Ｆｅｉｓｔｅｌ構造例を表したものである。なお、図６においては、各Ｆ関数の出力と、各データ系列との排他的論理和演算（ＸＯＲ）部の記号を省略しているが、各Ｆ関数の出力と、各データ系列と各交差ポイントでは、それぞれの入力による排他的論理和演算（ＸＯＲ）が実行され、その排他的論理和演算（ＸＯＲ）結果が同一データ系列の下方向に出力される構成である。図６に示す例では、ラウンドｉ＋４、ラウンドｉ＋５、ラウンドｉ＋９、ラウンドｉ＋１０が一つのラウンドに２つ以上のＦ関数が含まれるラウンドであり、これらのラウンドに示すＦ関数［Ｆ］と、ラウンド鍵［Ｋ］は、同一ラウンドにおけるＦ関数またはラウンド鍵の識別番号を示す番号が右上に示されている。
【００８６】
上記定義１〜３に従って、系列数ｄをｄ＝２としたＦｅｉｓｔｅｌ構造を構築すると、２本のデータ系列からなるＦｅｉｓｔｅｌ構造、すなわち、先に図１を参照して説明したＦｅｉｓｔｅｌ構造となる。すなわち、２本の各データ系列交互にＦ関数が行き来するような結線構造になるが、３本以上のデータ系列を持つ拡張Ｆｅｉｓｔｅｌ構造の場合はＦ関数の入力と出力として選ばれるデータ系列が複数存在するため結線構造が一意に定まることはない。つまり拡張Ｆｅｉｓｔｅｌ構造ではｄが大きくなればなるほど、Ｆ関数の設置場所の自由度が指数関数的に増大することとなる。
【００８７】
本発明では、このような拡張Ｆｅｉｓｔｅｌ構造において、差分攻撃や線形攻撃に対する耐性を向上させる拡散行列切り替え機構（ＤＳＭ：Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）を実現する構成を提案する。
【００８８】
系列数ｄをｄ＝２としたＦｅｉｓｔｅｌ構造では、例えば、図３や図４に示したように、Ｆｅｉｓｔｅｌ構造を構成するラウンド関数（Ｆ関数）部の線形変換部（Ｐ層）において適用する行列を、２つの異なる線形変換行列Ｍ０，Ｍ１、あるいは、３つの異なる線形変換行列Ｍ０，Ｍ１，Ｍ２とすることなどでＤＳＭが実現される。ただし、ＤＳＭを実現するためには、適用する行列が所定の条件を満たすことが必要となる。この条件の１つが、前述した分岐数（Ｂｒａｎｃｈ）に関する制約である。
【００８９】
データ系列数ｄを、
ｄ：ｄ≧２の任意の整数
とした拡張Ｆｅｉｓｔｅｌ構造において、ＤＳＭを実現する構成の説明の前に、以下の説明において使用する拡張Ｆｅｉｓｔｅｌ構造の各構成部および各構成部の入出力データの定義について、図７を参照して説明する。
図７は、例えば図６に示すような拡張Ｆｅｉｓｔｅｌ構造を構成する１つのデータ系列のみを抽出して示す図である。図７に示すように、ある１つのデータ系列への入力データは１回以上のＦ関数の出力が排他的論理和（ＸＯＲ）されて出力に至っていることがわかる。このことは拡張Ｆｅｉｓｔｅｌ構造に含まれる任意のデータ系列にあてはまる。
【００９０】
図７では、一本のデータ系列［ｓ（ｉ）］に対して複数のＦ関数［Ｆｓ（ｉ），１，Ｆｓ（ｉ），２，...］の出力が排他的論理和演算（ＸＯＲ）により足しあわされていく様子を表している。
なお、拡張Ｆｅｉｓｔｅｌ構造中のｄ本あるデータ系列を、それぞれｓ（ｉ）（１≦ｉ≦ｄ）とし、データ系列ｓ（ｉ）に入力するＦ関数を、データ系列ｓ（ｉ）の入力に近い方からＦｓ（ｉ），１，Ｆｓ（ｉ），２，...と名づけることとする。
またデータ系列ｓ（ｉ）の入力データをＷｓ（ｉ），０とし、
Ｆ関数Ｆｓ（ｉ），ｊの出力が排他的論理和された後のデータをＷｓ（ｉ），ｊとする。
また、Ｆ関数Ｆｓ（ｉ），ｊへの入力データをＸｓ（ｉ），ｊとする。
各Ｘｓ（ｉ），ｊは、データ系列ｓ（ｉ）以外の別の系列に属するデータであるが、ここではそれらがどこの系列に属しているかは問わないものとする。
このとき、拡張Ｆｅｉｓｔｅｌ構造は、このようなｄ本のデータ系列が相互に接続されて構成されるものと考えることができる。
【００９１】
拡張Ｆｅｉｓｔｅｌ構造において、ＤＳＭを実現するための構成
以下、ｄ：ｄ≧２の任意の整数
とした拡張Ｆｅｉｓｔｅｌ構造において、ＤＳＭを実現するための構成について説明する。説明は、
（４−２）拡張Ｆｅｉｓｔｅｌ構造において差分攻撃に対する耐性を向上させるための構成
（４−３）拡張Ｆｅｉｓｔｅｌ構造において線形攻撃に対する耐性を向上させるための構成
これらの各構成について、順次、説明する。
【００９２】
（４−２．拡張Ｆｅｉｓｔｅｌ構造において差分攻撃に対する耐性を向上させるための構成）
まず、拡張Ｆｅｉｓｔｅｌ構造において差分攻撃に対する耐性を向上させるための構成について説明する。
前述したように、差分攻撃は、ある差分（ΔＸ）を持つ入力データ（平文）とその出力データ（暗号文）を多数解析することにより各ラウンド関数における適用鍵を解析する攻撃であり、差分攻撃に対する耐性を図る指標として、差分の接続関係を表現した差分パスに含まれる差分アクティブＳ−ｂｏｘの最小数が適用される。差分パスは、暗号化関数中の鍵データを除くデータ部分における差分値である。線形変換処理の前後では、入力差分と出力差分の関係は一対一に決定され、非線形変換処理の前後では、一対一とはならないが、ある入力差分に対する出力差分の出現確率が算出される。すべての出力に対する確率をすべて足し合わせると１となる。
【００９３】
ＳＰ型のＦ関数を持ったＦｅｉｓｔｅｌ構造においては、非線形変換はＳ−ｂｏｘのみである。この場合、０以外の確率をもつ差分パスは平文（入力）に対する差分値から始まって暗号文（出力）の差分値までに至る差分データの集合であり、すべてのＳ−ｂｏｘの前後で与えられる差分値は０以外の確率をもつ。０以外の確率をもつある差分パスのＳ−ｂｏｘに入力される差分値が０でないものを差分アクティブＳ−ｂｏｘと呼ぶ。０以外の確率を持つすべての差分パスのアクティブＳ−ｂｏｘの数のうちで最も少ない数を最小差分アクティブＳ−ｂｏｘ数とよび、この数値が差分攻撃に対する安全性指標として用いられる。
【００９４】
最小差分アクティブＳ−ｂｏｘ数を大きくすることが、差分攻撃に対する耐性の向上をもたらす。以下では、データ系列数ｄをｄ≧２の任意整数とした拡張Ｆｅｉｓｔｅｌ構造において、最小差分アクティブＳ−ｂｏｘ数の数を大きくするＤＳＭ構造を構築する手法について説明する。
【００９５】
拡張Ｆｅｉｓｔｅｌ構造に含まれるＦ関数［Ｆｓ（ｉ），ｘ］で用いられる線形変換行列を［Ｍｓ（ｉ），ｘ］とする。このとき、分岐数演算関数：Ｂｒａｎｃｈ（）を適用した分岐数の算出式Ｂ２Ｄ（ｓ（ｉ））を次のように定義する、
【数２】
2008051829.tif 000004
【００９６】
上記式は、拡張Ｆｅｉｓｔｅｌ構造を構成する任意のデータ系列ｓ（ｉ）に入力する２つの隣り合うＦ関数［Ｆｓ（ｉ），ｊ，Ｆｓ（ｉ），ｊ＋１］中で用いられる２つの線形変換行列［Ｍｓ（ｉ），ｊ，Ｍｓ（ｉ），ｊ＋１］の結合行列［Ｍｓ（ｉ），ｊ｜Ｍｓ（ｉ），ｊ＋１］中の分岐数の最小値を求める式である。
【００９７】
拡張Ｆｅｉｓｔｅｌ構造を構成する任意のデータ系列ｓ（ｉ）において、データ系列ｓ（ｉ）に入力するＦ関数の上段からの個数に相当する［ｊ］を任意のｊとし、データ系列ｓ（ｉ）上のデータ［Ｗｓ（ｉ），ｊ］について考える。
データ系列ｓ（ｉ）に入力する２つのＦ関数［Ｆｓ（ｉ），ｊ＋１］，［Ｆｓ（ｉ），ｊ＋２］のデータ系列ｓ（ｉ）に対する入力部を挟むデータ系列ｓ（ｉ）上の入出力データ［Ｗｓ（ｉ），ｊ］と、［Ｗｓ（ｉ），ｊ＋２］について、
Ｗｓ（ｉ），ｊ＝０，
Ｗｓ（ｉ），ｊ＋２＝０である場合を考える。
【００９８】
このとき、
データ系列ｓ（ｉ）に入力するＦ関数中、隣り合うＦ関数［Ｆｓ（ｉ），ｊ＋１］と［Ｆｓ（ｉ），ｊ＋２］への各々の入力差分値［ΔＸｓ（ｉ），ｊ＋１］と、［ΔＸｓ（ｉ），ｊ＋２］との間に、
【数３】
2008051829.tif 000005
という関係式が成立している。
【００９９】
なお、上記式において、ｈｗはハミングウェイトであり、上記式の左辺はＦ関数の入力差分データにおける非ゼロの要素数つまりアクティブＳ−ｂｏｘ数の和を表している。この数が大きな値に保証されることが差分攻撃への耐性向上が期待できる条件である。従ってそれ以外の条件が同じであれば、Ｂ２Ｄ（ｓ（ｉ））をできるだけ大きくするように、拡張Ｆｅｉｓｔｅｌ構造を構成する各Ｆ関数内の行列を選択することが望ましいことが導かれる。
【０１００】
これまでの拡張Ｆｅｉｓｔｅｌ型暗号ではひとつの線形変換行列をすべてのＦ関数内の線形変換部で利用する構成が一般的である。
しかしながら、データ系列ｓ（ｉ）に入力する２つの隣り合うＦ関数［Ｆｓ（ｉ），ｊ，Ｆｓ（ｉ），ｊ＋１］中で用いられる２つの線形変換行列［Ｍｓ（ｉ），ｊ］、［Ｍｓ（ｉ），ｊ＋１］とが、同一の行列であると、前述の分岐数演算関数：Ｂｒａｎｃｈ（）を適用した分岐数の算出式、すなわち、
Ｂ２Ｄ（ｓ（ｉ））
は必ず最低の値である２となってしまう。このため耐性向上の効果は見込めない。
【０１０１】
また異なる行列を用いている場合でも不用意に２つの行列を選択してしまうとＢ２Ｄ（ｓ（ｉ））が２となってしまう場合がある。
前述の分岐数算出式によって定義されるＢ２Ｄ（ｓ（ｉ））をより大きな分岐数とすることが、局所的な最小差分アクティブＳ−ｂｏｘ数を大きく保証することになり、差分攻撃に対する耐性を向上させることが可能となる。従って、例えば、Ｂ２Ｄ（ｓ（ｉ））が３以上となるように行列を選択することで、差分攻撃に対する耐性を向上させることが可能となる。
【０１０２】
拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列に対してＢ２Ｄ（ｓ（ｉ））を計算し、それらの中で最小の値のものをＢ２Ｄとする。このＢ２Ｄを３以上とするように、Ｆ関数中の行列を選択する方法について以下説明する。
【０１０３】
（４−２−１．最小分岐数Ｂ２Ｄの値を３以上とするＦ関数中の行列選択構成）
まず、拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列における最小分岐数［Ｂ２Ｄ（ｓ（ｉ））］中、最小の分岐数［Ｂ２Ｄ］を３以上とするためには、最低２種類の行列があれば実現できることを以下に説明する。
【０１０４】
まず、２つの異なる行列［Ａ０］と［Ａ１］の結合行列［Ａ０｜Ａ１］の分岐数が３以上となる、すなわち、
Ｂｒａｎｃｈｎ（［Ａ０｜Ａ１］）≧３
を満たす２つの異なる行列［Ａ０］と［Ａ１］を用意する。
【０１０５】
次に、拡張Ｆｅｉｓｔｅｌ構造のデータ系列ｓ（ｉ）に入力する複数のＦ関数の線形変換部の線形変換行列を以下のように設定する。
最初のＦ関数Ｆｓ（ｉ），１の線形変換部に設定する線形変換行列をＡ０、
第２番目のＦ関数Ｆｓ（ｉ），２の線形変換部に設定する線形変換行列をＡ１、
第３番目のＦ関数Ｆｓ（ｉ），３の線形変換部に設定する線形変換行列をＡ０、
：
というように２つの異なる行列［Ａ０］と［Ａ１］をデータ系列ｓ（ｉ）に入力する複数のＦ関数に対して、上から順に交互に配置していく。
【０１０６】
このように線形変換行列を設定した場合、任意のデータ系列ｓ（ｉ）に入力する２つの隣り合うＦ関数［Ｆｓ（ｉ），ｊ，Ｆｓ（ｉ），ｊ＋１］中で用いられる２つの線形変換行列［Ｍｓ（ｉ），ｊ，Ｍｓ（ｉ），ｊ＋１］の結合行列［Ｍｓ（ｉ），ｊ｜Ｍｓ（ｉ），ｊ＋１］中の分岐数の最小値を求める上述した式は、
【数４】
2008051829.tif 000006
である。すなわち、最小分岐数が３以上であることが保証される。
【０１０７】
もちろん行列［Ａ０］と［Ａ１］を入れ替えても効果は同じである。また、拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列ｓ（ｉ）について同様に行列を設定すれば、２つの行列を用いただけでＢ２Ｄの値を３以上にすることが可能である。
【０１０８】
このように、Ｂｒａｎｃｈｎ（［Ａ０｜Ａ１］）≧３
を満たす２つの異なる行列［Ａ０］と［Ａ１］を用意して、これらの各行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力するＦ関数に交互に配置する設定とすることで、最小分岐数Ｂ２Ｄの値を３以上にすることが可能となり、拡散行列切り替え機構（ＤＳＭ）による差分攻撃に対する耐性の向上が実現される。
【０１０９】
上述した説明は、２つの異なる行列［Ａ０］と［Ａ１］を適用した例である。
次に、異なる行列を２以上の任意の数［ｋ］として一般化した例について、以下、説明する。
【０１１０】
拡張Ｆｅｉｓｔｅｌ構造に含まれるＦ関数［Ｆｓ（ｉ），ｊ］で用いられる線形変換行列を［Ｍｓ（ｉ），ｊ］とする。このとき、分岐数演算関数：Ｂｒａｎｃｈ（）を適用した分岐数の算出式Ｂ２Ｄ（ｓ（ｉ））を次のように定義する、
【数５】
2008051829.tif 000007
【０１１１】
上記式は、拡張Ｆｅｉｓｔｅｌ構造を構成する任意のデータ系列ｓ（ｉ）に入力するｋ個の隣り合うＦ関数［Ｆｓ（ｉ），ｊ，Ｆｓ（ｉ），ｊ＋１，・・・，Ｆｓ（ｉ），ｊ＋ｋ−１］中で用いられるｋ個の線形変換行列［Ｍｓ（ｉ），ｊ，Ｍｓ（ｉ），ｊ＋１，・・・，Ｍｓ（ｉ），ｊ＋ｋ−１］の結合行列［Ｍｓ（ｉ），ｊ｜Ｍｓ（ｉ），ｊ＋１｜・・・｜Ｍｓ（ｉ），ｊ＋ｋ−１］中の分岐数の最小値を求める式である。
【０１１２】
拡張Ｆｅｉｓｔｅｌ構造を構成する任意のデータ系列ｓ（ｉ）において、データ系列ｓ（ｉ）に入力するＦ関数の上段からの個数に相当する［ｊ］を任意のｊとし、データ系列ｓ（ｉ）上のデータ［Ｗｓ（ｉ），ｊ］について考える。
データ系列ｓ（ｉ）に入力するｋ個のＦ関数［Ｆｓ（ｉ），ｊ＋１］・・・［Ｆｓ（ｉ），ｊ＋ｋ］のデータ系列ｓ（ｉ）に対する入力部を挟むデータ系列ｓ（ｉ）上の入出力データ［Ｗｓ（ｉ），ｊ］と、［Ｗｓ（ｉ），ｊ＋ｋ］について、
Ｗｓ（ｉ），ｊ＝０，
Ｗｓ（ｉ），ｊ＋ｋ＝０である場合を考える。
【０１１３】
このとき、
データ系列ｓ（ｉ）に入力するＦ関数中、隣り合うｋ個のＦ関数［Ｆｓ（ｉ），ｊ＋１］・・・［Ｆｓ（ｉ），ｊ＋ｋ］への各々の入力差分値［ΔＸｓ（ｉ），ｊ＋１］・・・［ΔＸｓ（ｉ），ｊ＋ｋ］との間に、
【数６】
2008051829.tif 000008
という関係式が得られる。
【０１１４】
なお、上記式において、ｈｗはハミングウェイトであり、上記式の左辺はＦ関数の入力差分データにおける非ゼロの要素数つまりアクティブＳ−ｂｏｘ数の和を表している。この数が大きな値に保証されることが差分攻撃への耐性向上が期待できる条件である。従ってそれ以外の条件が同じであれば、ＢｋＤ（ｓ（ｉ））をできるだけ大きくするように、拡張Ｆｅｉｓｔｅｌ構造を構成する各Ｆ関数内の行列を選択することが望ましいことが導かれる。
【０１１５】
しかしながら、データ系列ｓ（ｉ）に入力するｋ個の隣り合うＦ関数［Ｆｓ（ｉ），ｊ］・・・［Ｆｓ（ｉ），ｊ＋ｋ−１］中で用いられるｋ個の線形変換行列［Ｍｓ（ｉ），ｊ］・・・［Ｍｓ（ｉ），ｊ＋ｋ−１］中に、同じ行列が１つでも存在すると、前述の分岐数演算関数：Ｂｒａｎｃｈ（）を適用した分岐数の算出式、すなわち、
ＢｋＤ（ｓ（ｉ））
は必ず最低の値である２となってしまう。このため耐性向上の効果は見込めない。
【０１１６】
またｋ個の線形変換行列［Ｍｓ（ｉ），ｊ］・・・［Ｍｓ（ｉ），ｊ＋ｋ−１］に異なる行列を用いている場合でも不用意に行列を選択してしまうとＢｋＤ（ｓ（ｉ））が２となってしまう場合がある。
【０１１７】
前述の分岐数算出式によって定義されるＢｋＤ（ｓ（ｉ））をより大きな分岐数とすることが、局所的な最小線形アクティブＳ−ｂｏｘ数を大きく保証することになり、差分攻撃に対する耐性を向上させることが可能となる。従って、例えば、ＢｋＤ（ｓ（ｉ））が３以上となるように行列を選択することで、差分攻撃に対する耐性を向上させることが可能となる。
【０１１８】
拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列に対してＢｋＤ（ｓ（ｉ））を計算し、それらの中で最小の値のものをＢｋＤとする。このＢｋＤを３以上とするように、Ｆ関数中の行列を選択する方法について以下説明する。
【０１１９】
（４−２−２．最小分岐数ＢｋＤの値を３以上とするＦ関数中の行列選択構成）
拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列における最小分岐数［ＢｋＤ（ｓ（ｉ））］中、最小の分岐数［ＢｋＤ］を３以上とするためには、最低ｋ種類の行列があれば実現できることを以下に説明する。
【０１２０】
まず、ｋ個の異なる行列［Ａ０］，［Ａ１］，［Ａ２］，・・・［Ａｋ−１］の結合行列［Ａ０｜Ａ１｜・・・｜Ａｋ−１］の分岐数が３以上となる、すなわち、
Ｂｒａｎｃｈｎ（［Ａ０｜Ａ１｜・・・｜Ａｋ−１］）≧３
を満たすｋ個の異なる行列［Ａ０］，［Ａ１］，［Ａ２］，・・・［Ａｋ−１］を用意する。
【０１２１】
次に、拡張Ｆｅｉｓｔｅｌ構造のデータ系列ｓ（ｉ）に入力する複数のＦ関数の線形変換部の線形変換行列を以下のように設定する。
最初のＦ関数Ｆｓ（ｉ），１の線形変換部に設定する線形変換行列をＡ０、
第２番目のＦ関数Ｆｓ（ｉ），２の線形変換部に設定する線形変換行列をＡ１、
第３番目のＦ関数Ｆｓ（ｉ），３の線形変換部に設定する線形変換行列をＡ２、
：
第ｋ番目のＦ関数Ｆｓ（ｉ），ｋの線形変換部に設定する線形変換行列をＡｋ−１、
第ｋ＋１番目のＦ関数Ｆｓ（ｉ），ｋ＋１の線形変換部に設定する線形変換行列をＡ０、
第ｋ＋２番目のＦ関数Ｆｓ（ｉ），ｋ＋２の線形変換部に設定する線形変換行列をＡ１、
：
というようにｋ個の異なる行列［Ａ０］，［Ａ１］，［Ａ２］，・・・［Ａｋ−１］をデータ系列ｓ（ｉ）に入力する複数のＦ関数に対して、上から順に、繰り返し配置していく。
【０１２２】
このように線形変換行列［Ａ０］，［Ａ１］，［Ａ２］，・・・［Ａｋ−１］を設定した場合、任意のデータ系列ｓ（ｉ）に入力するｋ個の隣り合うＦ関数［Ｆｓ（ｉ），ｊ，Ｆｓ（ｉ），ｊ＋１・・・Ｆｓ（ｉ），ｊ＋ｋ−１］中で用いられるｋ個の線形変換行列［Ｍｓ（ｉ），ｊ，Ｍｓ（ｉ），ｊ＋１・・・Ｍｓ（ｉ），ｊ＋ｋ−１］の結合行列［Ｍｓ（ｉ），ｊ｜Ｍｓ（ｉ），ｊ＋１｜・・・Ｍｓ（ｉ），ｊ＋ｋ−１］中の分岐数の最小値を求める式は、
【数７】
2008051829.tif 000009
である。すなわち、最小分岐数が３以上であることが保証される。
【０１２３】
もちろん行列［Ａ０］，［Ａ１］，［Ａ２］，・・・［Ａｋ−１］を入れ替えても効果は同じである。また、拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列ｓ（ｉ）について同様に行列を設定すれば、ｋ個の行列を用いただけでＢ２Ｄの値を３以上にすることが可能である。
【０１２４】
このように、
Ｂｒａｎｃｈｎ（［Ａ０｜Ａ１｜・・・｜Ａｋ−１］）≧３
を満たすｋ個の異なる行列［Ａ０］，［Ａ１］，［Ａ２］，・・・［Ａｋ−１］を用意して、これらの各行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力するＦ関数に順番に繰り返し配置する設定とすることで、最小分岐数ＢｋＤの値を３以上にすることが可能となり、拡散行列切り替え機構（ＤＳＭ）による差分攻撃に対する耐性の向上が実現される。
【０１２５】
なお、ｋの値の選択に関しては、最低でもｋが２以上であれば効果が見込まれる。ｋが大きくなればなるほど、保証される範囲が大きくなるため、耐性の向上がより期待できる。しかし、一方で、必要となる行列の種類の最小数が大きくなるため効率的な実装に不向きとなる可能性がある。よってｋの値は設計の段階で状況に応じて選択されるべき値である。
【０１２６】
（４−３．拡張Ｆｅｉｓｔｅｌ構造において線形攻撃に対する耐性を向上させるための構成）
次に、拡張Ｆｅｉｓｔｅｌ構造において線形攻撃に対する耐性を向上させる構成について説明する。
先に、説明したように、線形攻撃に対する耐性を図る指標としては、線形マスクの接続関係を表現した線形パス（線形近似と呼ばれることが多いが、差分と対応させるためここではパスという言葉を用いる）に含まれる線形アクティブＳ−ｂｏｘの最小数が適用可能である。線形パスは、暗号化関数中の鍵データを除くすべてのデータ部分に対して特定の線形マスク値を指定したものである。線形変換処理の前後では、入力線形マスク値と出力線形マスク値の関係は一対一に決定され、非線形変換処理の前後では、一対一とはならないが、ある入力線形マスクに対する出力線形マスクの出現確率が算出される。すべての出力に対する確率をすべて足し合わせると１となる。
【０１２７】
ＳＰ型のＦ関数を持ったＦｅｉｓｔｅｌ構造においては、非線形変換はＳ−ｂｏｘによる処理の部分のみである。したがって、この場合、０以外の確率をもつ線形パスとは平文（入力）に対する線形値から始まって暗号文（出力）の線形値までに至る線形マスク値データの集合であり、すべてのＳ−ｂｏｘの前後で与えられる線形値は０以外の確率をもつものである。０以外の確率をもつある線形パスのＳ−ｂｏｘに入力される線形値が０でないものを線形アクティブＳ−ｂｏｘと呼ぶ。０以外の確率を持つすべての線形パスのアクティブＳ−ｂｏｘの数のうちで最も少ない数を最小線形アクティブＳ−ｂｏｘ数とよび、この数値が線形攻撃に対する安全性指標として用いられる。
【０１２８】
最小線形アクティブＳ−ｂｏｘ数を大きくすることが、線形攻撃に対する耐性の向上をもたらす。以下では、データ系列数ｄをｄ≧２の任意整数とした拡張Ｆｅｉｓｔｅｌ構造において、最小線形アクティブＳ−ｂｏｘ数の数を大きくするＤＳＭ構造を構築する手法について説明する。
【０１２９】
拡張Ｆｅｉｓｔｅｌ構造に含まれるＦ関数［Ｆｓ（ｉ），ｘ］で用いられる線形変換行列を［Ｍｓ（ｉ），ｘ］とする。このとき、分岐数演算関数：Ｂｒａｎｃｈ（）を適用した分岐数の算出式Ｂ２Ｌ（ｓ（ｉ））を次のように定義する、
【数８】
2008051829.tif 000010
【０１３０】
上記式は、拡張Ｆｅｉｓｔｅｌ構造を構成する任意のデータ系列ｓ（ｉ）に入力する２つの隣り合うＦ関数［Ｆｓ（ｉ），ｊ，Ｆｓ（ｉ），ｊ＋１］中で用いられる２つの線形変換行列［Ｍｓ（ｉ），ｊ］、［Ｍｓ（ｉ），ｊ＋１］各々の逆行列の転置行列［ｔＭ−１ｓ（ｉ），ｊ］、［ｔＭ−１ｓ（ｉ），ｊ＋１］の結合行列［ｔＭ−１ｓ（ｉ），ｊ｜ｔＭ−１ｓ（ｉ），ｊ＋１］中の分岐数の最小値を求める式である。
【０１３１】
拡張Ｆｅｉｓｔｅｌ構造を構成する任意のデータ系列ｓ（ｉ）において、データ系列ｓ（ｉ）に入力するＦ関数の上段からの個数に相当する［ｊ］を任意のｊとし、あるｊに対して、
ｊ番目のＦ関数に対する入力：Ｘｓ（ｉ），ｊ、
ｊ番目のＦ関数の出力と、データ系列ｓ（ｉ）上のデータとの排他的論理和（ＸＯＲ）結果：Ｗｓ（ｉ），ｊ、
ｊ＋１番目のＦ関数に対する入力：Ｘｓ（ｉ），ｊ＋１、
これらの各データの線形マスクをそれぞれ、
ΓＸｓ（ｉ），ｊ、
ΓＷｓ（ｉ），ｊ、
ΓＸｓ（ｉ），ｊ＋１、
とすると、それらのうちどれかひとつでも０でないものがあれば、以下の式を満たす。すなわち、
【数９】
2008051829.tif 000011
【０１３２】
上記式を満足する。上記式の左辺の値が大きいほど局所的な線形アクティブＳ−ｂｏｘ数が多くなることを意味している。従って、Ｂ２Ｌ（ｓ（ｉ））を大きくするように行列を選択することが望ましいといえる。
【０１３３】
しかしながら、データ系列ｓ（ｉ）に入力する２つの隣り合うＦ関数［Ｆｓ（ｉ），ｊ，Ｆｓ（ｉ），ｊ＋１］中で用いられる２つの線形変換行列［Ｍｓ（ｉ），ｊ］、［Ｍｓ（ｉ），ｊ＋１］とが、同一の行列であると、上記の分岐数算出式、すなわち、
Ｂ２Ｌ（ｓ（ｉ））
は必ず最低の値である２となってしまう。このため耐性向上の効果は見込めない。Ｂ２Ｌ（ｓ（ｉ））をより大きな分岐数とすることが、最小線形アクティブＳ−ｂｏｘ数を大きく保証することになり、線形攻撃に対する耐性を向上させることが可能となる。従って、例えば、Ｂ２Ｌ（ｓ（ｉ））が３以上となるように行列を選択することで、線形攻撃に対する耐性を向上させることが可能となる。
【０１３４】
拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列に対してＢ２Ｌ（ｓ（ｉ））を計算し、それらの中で最小の値のものをＢ２Ｌとする。このＢ２Ｌを３以上とするように、Ｆ関数中の行列を選択する方法について以下説明する。
【０１３５】
（４−３−１．最小分岐数Ｂ２Ｌの値を３以上とするＦ関数中の行列選択構成）
拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列における最小分岐数［Ｂ２Ｌ（ｓ（ｉ））］中、最小の分岐数［Ｂ２Ｌ］を３以上とするためには、最低２種類の行列があれば実現できることを以下に説明する。
【０１３６】
まず、２つの異なる行列［Ａ０］と［Ａ１］の結合行列［ｔＡ０−１｜ｔＡ１−１］の分岐数が３以上となる、すなわち、
Ｂｒａｎｃｈｎ（［ｔＡ０−１｜ｔＡ１−１］）≧３
を満たす２つの異なる行列［Ａ０］と［Ａ１］を用意する。
【０１３７】
次に、拡張Ｆｅｉｓｔｅｌ構造のデータ系列ｓ（ｉ）に入力する複数のＦ関数の線形変換部の線形変換行列を以下のように設定する。
最初のＦ関数Ｆｓ（ｉ），１の線形変換部に設定する線形変換行列をＡ０、
第２番目のＦ関数Ｆｓ（ｉ），２の線形変換部に設定する線形変換行列をＡ１、
第３番目のＦ関数Ｆｓ（ｉ），３の線形変換部に設定する線形変換行列をＡ０、
：
というように２つの異なる行列［Ａ０］と［Ａ１］をデータ系列ｓ（ｉ）に入力する複数のＦ関数に対して、上から順に交互に配置していく。
【０１３８】
このように線形変換行列を設定した場合、任意のデータ系列ｓ（ｉ）に入力する２つの隣り合うＦ関数［Ｆｓ（ｉ），ｊ，Ｆｓ（ｉ），ｊ＋１］中で用いられる２つの線形変換行列［Ｍｓ（ｉ），ｊ］、［Ｍｓ（ｉ），ｊ＋１］各々の逆行列の転置行列［ｔＭ−１ｓ（ｉ），ｊ］、［ｔＭ−１ｓ（ｉ），ｊ＋１］の結合行列［ｔＭ−１ｓ（ｉ），ｊ｜ｔＭ−１ｓ（ｉ），ｊ＋１］中の分岐数の最小値を求める上述した式は、
【数１０】
2008051829.tif 000012
となる。すなわち、最小分岐数が３以上であることが保証される。
【０１３９】
もちろん行列［Ａ０］と［Ａ１］を入れ替えても効果は同じである。また、拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列ｓ（ｉ）について同様に行列を設定すれば、２つの行列を用いただけでＢ２Ｌの値を３以上にすることが可能である。
【０１４０】
このように、Ｂｒａｎｃｈｎ（［ｔＡ０−１｜ｔＡ１−１］）≧３
を満たす２つの異なる行列［Ａ０］と［Ａ１］を用意して、これらの各行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力するＦ関数に交互に配置する設定とすることで、最小分岐数Ｂ２Ｌの値を３以上にすることが可能となり、拡散行列切り替え機構（ＤＳＭ）による線形攻撃に対する耐性の向上が実現される。
【０１４１】
［５．特定の形を持つ拡張Ｆｅｉｓｔｅｌ構造に対するＤＳＭの利用構成］
上述したように、データ系列数ｄをｄ≧２の任意整数とした拡張Ｆｅｉｓｔｅｌ構造においてＤＳＭ技術を適用することで、差分攻撃や線形攻撃に対する耐性を向上させることが可能である。以下、差分攻撃や線形攻撃についての安全性指標を高いレベルで保証できる具体的な拡張Ｆｅｉｓｔｅｌ構造について説明する。
【０１４２】
先に図５、図６を参照して説明したように、データ系列数ｄをｄ≧２の任意整数とした拡張Ｆｅｉｓｔｅｌ構造は、１つのデータ系列に対する入力が、他の様々なデータ系列から入力可能であり、また、１つのラウンドにおいて、複数のＦ関数が並列に実行可能であるなど、様々な構成がある。以下では、拡張Ｆｅｉｓｔｅｌ構造を、大きく２つのタイプ（タイプ１、タイプ２）に分類して、各タイプ毎に、差分攻撃や線形攻撃についての安全性指標を高いレベルで保証できる具体的な拡張Ｆｅｉｓｔｅｌ構造を説明する。
【０１４３】
（５−１．拡張Ｆｅｉｓｔｅｌ構造のタイプ１に対するＤＳＭの適用）
まず、拡張Ｆｅｉｓｔｅｌ構造のタイプ１に対するＤＳＭの適用について、図８を参照して説明する。
拡張Ｆｅｉｓｔｅｌ構造のタイプ１は、以下のパラメータを持つものとする。
パラメータ
（ａ）データ分割数：ｄ（ｄは３以上）
（ｂ）入出力データ長：ｄｍｎビット
（ｃ）分割データ長：ｍｎビット
（ｄ）１ラウンドあたりのＦ関数の数：１
【０１４４】
図８に示すように、各ラウンド内では、図８に示す左端のデータ系列上のｍｎビットデータに対してＦ関数が適用され、Ｆ関数の処理結果は、すぐ隣のデータ系列に出力され、排他的論理和される。なお、図８においては排他的論理和の演算記号を省略してある。
【０１４５】
図８に示すように、各ラウンドにおいて、Ｆ関数に対するデータ入力を行なった左端のデータ系列は、次のラウンドでは、右端に移動し、それ以外のデータ系列は左にひとつずつずれる構成をとる。
【０１４６】
このように各ラウンド毎に１つのＦ関数が実行される拡張Ｆｅｉｓｔｅｌ構造にＤＳＭを適用して差分攻撃および線形攻撃に対する耐性を向上させる構成について説明する。
【０１４７】
先に説明した（４−２．拡張Ｆｅｉｓｔｅｌ構造において差分攻撃に対する耐性を向上させるための構成）において、拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列に対してＢ２Ｄ（ｓ（ｉ））を計算し、それらの中で最小の値のものをＢ２Ｄとし、このＢ２Ｄを３以上とするように、Ｆ関数中の行列を選択することで、差分攻撃に対する耐性が高められることを説明した。
さらに、先に説明した（４−３．拡張Ｆｅｉｓｔｅｌ構造において線形攻撃に対する耐性を向上させるための構成）において、拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列に対してＢ２Ｌ（ｓ（ｉ））を計算し、それらの中で最小の値のものをＢ２Ｌとし、このＢ２Ｌを３以上とするように、Ｆ関数中の行列を選択することで、線形攻撃に対する耐性が高められることを説明した。
【０１４８】
このＢ２ＤとＢ２Ｌに加えて、さらに、
Ｂ１Ｄを、図８に示すようなタイプ１の拡張Ｆｅｉｓｔｅｌ構造中に含まれるＦ関数中の線形変換行列の分岐数中の最小の分岐数とする。
【０１４９】
このとき、図８に示すようなタイプ１の拡張Ｆｅｉｓｔｅｌ構造における連続するｐラウンドに含まれる差分アクティブＳ−ｂｏｘ数をＡｃｔＤ（ｐ）と表記し、線形アクティブＳ−ｂｏｘ数をＡｃｔＬ（ｐ）と表記するものとすると、以下の関係式が存在する。
ＡｃｔＤ（３ｄ）≧Ｂ１Ｄ＋Ｂ２Ｄ
ＡｃｔＬ（３ｄ）≧２Ｂ２Ｌ
上記式において、
ＡｃｔＤ（３ｄ）は、連続する３ｄラウンドに含まれる差分アクティブＳ−ｂｏｘ数、
ＡｃｔＬ（３ｄ）は、連続する３ｄラウンドに含まれる線形アクティブＳ−ｂｏｘ数、
を示している。
これらの関係式が成立することの証明は後述する。
【０１５０】
このことから、Ｂ１Ｄ，Ｂ２Ｄ，Ｂ２Ｌが大きくなるような行列を利用することによって、アクティブＳ−ｂｏｘ数を多く確保することが出来ることになり、結果として、差分攻撃および線形攻撃に対する耐性を向上させることが可能となる。
なお、これらＢ１Ｄ，Ｂ２Ｄ，Ｂ２Ｌの理論上の最大値はｍ＋１になることが知られている。
【０１５１】
上述の式、すなわち、
ＡｃｔＤ（３ｄ）≧Ｂ１Ｄ＋Ｂ２Ｄ
ＡｃｔＬ（３ｄ）≧２Ｂ２Ｌ
これらの式の右辺には、先に説明した最小分岐数Ｂ２ＤまたはＢ２Ｌが含まれており、これらの最小分岐数の値を大きくすることが、アクティブＳ−ｂｏｘ数を多く確保することに貢献することになり、差分攻撃および線形攻撃に対する耐性を向上させるために有効となる。したがって、図８に示すような拡張Ｆｅｉｓｔｅｌ構造のタイプ１の構成においては、先に説明した最小分岐数Ｂ２ＤまたはＢ２Ｌを３以上とする構成が、有効であることになり、この構成とすることで、差分攻撃と線形攻撃に対する耐性をこれまでよりも高く保証することが可能となる。
【０１５２】
（５−２．拡張Ｆｅｉｓｔｅｌ構造のタイプ２に対するＤＳＭの適用）
次に、拡張Ｆｅｉｓｔｅｌ構造のタイプ２に対するＤＳＭの適用について、図９を参照して説明する。
拡張Ｆｅｉｓｔｅｌ構造のタイプ２は、以下のパラメータを持つものとする。
パラメータ
（ａ）データ分割数：ｄ（ただしｄは４以上の偶数）
（ｂ）入出力データ長：ｄｍｎビット
（ｃ）分割データ長：ｍｎビット
（ｄ）１ラウンドあたりのＦ関数の数：ｄ／２
【０１５３】
図９に示すように、各ラウンド内では左端から数えて奇数番目にあるｍｎビットのデータ系列に対してＦ関数が適用され、Ｆ関数の処理結果は、すぐ隣のデータに出力が排他的論理和される。なお、図９においては排他的論理和の演算記号を省略してある。
【０１５４】
図９に示すように、各ラウンドにおいて、Ｆ関数に対するデータ入力を行なった左端のデータ系列は、次のラウンドでは、右端に移動し、それ以外のデータ系列は左にひとつずつずれる構成をとる。
【０１５５】
このように各ラウンド毎にｄ／２個のＦ関数が実行される拡張Ｆｅｉｓｔｅｌ構造にＤＳＭを適用して差分攻撃および線形攻撃に対する耐性を向上させる構成について説明する。
【０１５６】
先に説明した（４−２．拡張Ｆｅｉｓｔｅｌ構造において差分攻撃に対する耐性を向上させるための構成）において、拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列に対してＢ２Ｄ（ｓ（ｉ））を計算し、それらの中で最小の値のものをＢ２Ｄとし、このＢ２Ｄを３以上とするように、Ｆ関数中の行列を選択することで、差分攻撃に対する耐性が高められることを説明した。
さらに、先に説明した（４−３．拡張Ｆｅｉｓｔｅｌ構造において線形攻撃に対する耐性を向上させるための構成）において、拡張Ｆｅｉｓｔｅｌ構造のすべてのデータ系列に対してＢ２Ｌ（ｓ（ｉ））を計算し、それらの中で最小の値のものをＢ２Ｌとし、このＢ２Ｌを３以上とするように、Ｆ関数中の行列を選択することで、線形攻撃に対する耐性が高められることを説明した。
【０１５７】
このＢ２ＤとＢ２Ｌに加えて、さらに、
Ｂ１Ｄを、図９に示すようなタイプ２の拡張Ｆｅｉｓｔｅｌ構造中に含まれるＦ関数中の線形変換行列の分岐数中の最小の分岐数とする。
【０１５８】
このとき、図９に示すようなタイプ２の拡張Ｆｅｉｓｔｅｌ構造における連続するｐラウンドに含まれる差分アクティブＳ−ｂｏｘ数をＡｃｔＤ（ｐ）と表記し、線形アクティブＳ−ｂｏｘ数をＡｃｔＬ（ｐ）と表記するものとすると、以下の関係式が存在する。
ＡｃｔＤ（６）≧Ｂ１Ｄ＋Ｂ２Ｄ
ＡｃｔＬ（６）≧２Ｂ２Ｌ
上記式において、
ＡｃｔＤ（６）は、連続する６ラウンドに含まれる差分アクティブＳ−ｂｏｘ数、
ＡｃｔＬ（６）は、連続する６ラウンドに含まれる線形アクティブＳ−ｂｏｘ数、
を示している。
これらの関係式が成立することの証明は後述する。
【０１５９】
このことから、Ｂ１Ｄ，Ｂ２Ｄ，Ｂ２Ｌが大きくなるような行列を利用することによって、アクティブＳ−ｂｏｘ数を多く確保することが出来ることになり、結果として、差分攻撃および線形攻撃に対する耐性を向上させることが可能となる。
なお、これらＢ１Ｄ，Ｂ２Ｄ，Ｂ２Ｌの理論上の最大値はｍ＋１になることが知られている。
【０１６０】
上述の式、すなわち、
ＡｃｔＤ（６）≧Ｂ１Ｄ＋Ｂ２Ｄ
ＡｃｔＬ（６）≧２Ｂ２Ｌ
これらの式の右辺には、先に説明した最小分岐数Ｂ２ＤまたはＢ２Ｌが含まれており、これらの最小分岐数の値を大きくすることが、アクティブＳ−ｂｏｘ数を多く確保することに貢献することになり、差分攻撃および線形攻撃に対する耐性を向上させるために有効となる。したがって、図９に示すような拡張Ｆｅｉｓｔｅｌ構造のタイプ２の構成においては、先に説明した最小分岐数Ｂ２ＤまたはＢ２Ｌを３以上とする構成が、有効であることになり、この構成とすることで、差分攻撃と線形攻撃に対する耐性をこれまでよりも高く保証することが可能となる。
【０１６１】
［６．拡張Ｆｅｉｓｔｅｌ構造各タイプのアクティブＳ−ｂｏｘ数と、Ｆ関数中の線形変換行列に基づく最小分岐数との関係式の証明］
次に、上述した
（５−１．拡張Ｆｅｉｓｔｅｌ構造のタイプ１に対するＤＳＭの適用）
（５−２．拡張Ｆｅｉｓｔｅｌ構造のタイプ２に対するＤＳＭの適用）
において説明したアクティブＳ−ｂｏｘ数と、Ｆ関数中の線形変換行列に基づく最小分岐数との関係式の証明について説明する。
【０１６２】
（６−１．拡張Ｆｅｉｓｔｅｌ構造のタイプ１のアクティブＳ−ｂｏｘ数と、Ｆ関数中の線形変換行列に基づく最小分岐数との関係式の証明）
まず、先に図８を参照して説明した拡張Ｆｅｉｓｔｅｌ構造のタイプ１のアクティブＳ−ｂｏｘ数と、Ｆ関数中の線形変換行列に基づく最小分岐数との関係式の証明について説明する。
【０１６３】
すなわち、タイプ１の拡張Ｆｅｉｓｔｅｌ構造における連続するｐラウンドに含まれる差分アクティブＳ−ｂｏｘ数をＡｃｔＤ（ｐ）と表記し、線形アクティブＳ−ｂｏｘ数をＡｃｔＬ（ｐ）と表記した場合の関係式、
ＡｃｔＤ（３ｄ）≧Ｂ１Ｄ＋Ｂ２Ｄ
ＡｃｔＬ（３ｄ）≧２Ｂ２Ｌ
この関係式が成立することを証明する。
【０１６４】
先に図８を参照して説明した拡張Ｆｅｉｓｔｅｌ構造のタイプ１の構成を、別の形で示すと、図１０のように示すことができる。図８では、Ｆ関数への入力を行なうデータ系列が左端になるように各データ系列の並びをラウンド毎に入れ替えて示していたが、図１０は、データ系列のラウンド毎の入れ替えを行なわず、１つの直線で示している。図１０では、ラウンド１〜６ｄまでを示している。ｄ個のラウンド（ラウンド１〜ｄ，ｄ＋１〜２ｄ，・・・，５ｄ＋１〜６ｄ）を１つの横ラインに並べて示してあるが、これらは並列に実行されるのではなく、各ラウンド、例えばラウンド１〜ｄは、順次実行される。
【０１６５】
また、図には、Ｆ関数の出力と各データ系列の交点における排他的論理和（ＸＯＲ）演算を省略しているが、Ｆ関数の出力と各データ系列の交点では排他的論理和（ＸＯＲ）演算が実行され、その結果が、次のラウンドのＦ関数の入力となる。
【０１６６】
この拡張Ｆｅｉｓｔｅｌ構造のタイプ１の構成において、先に、（５−１．拡張Ｆｅｉｓｔｅｌ構造のタイプ１に対するＤＳＭの適用）において説明した関係式、
ＡｃｔＤ（３ｄ）≧Ｂ１Ｄ＋Ｂ２Ｄ
ＡｃｔＬ（３ｄ）≧２Ｂ２Ｌ
が成立することを証明する。
上記式において、
ＡｃｔＤ（３ｄ）、ＡｃｔＬ（３ｄ）は、図８または図１０に示すタイプ１の拡張Ｆｅｉｓｔｅｌ構造における連続する３ｄラウンドに含まれる差分アクティブＳ−ｂｏｘ数と、線形アクティブＳ−ｂｏｘ数を意味する。
Ｂ１Ｄは、タイプ１の拡張Ｆｅｉｓｔｅｌ構造中に含まれるＦ関数中の線形変換行列の分岐数中の最小の分岐数、
Ｂ２Ｄ，Ｂ２Ｌは、先に（４−２），（４−３）において説明した拡張Ｆｅｉｓｔｅｌ構造中に含まれる１つのデータ系列に入力する連続するＦ関数中の線形変換行列の結合行列の最小分岐数、および逆行列の転置行列の結合行列の最小分岐数である。
【０１６７】
Ｂ１Ｄ，Ｂ２Ｄ，Ｂ２Ｌは、以下のように定義される。
【数１１】
2008051829.tif 000013
【０１６８】
なお、上記定義において、
Ｂ１Ｄ≧Ｂ２Ｄ
の関係が成立している。
また、図８または図１０に示すタイプ１の拡張Ｆｅｉｓｔｅｌ構造における第ｋ番目のＦ関数に含まれる差分アクティブＳ―ｂｏｘの数をＤｋで表し、線形アクティブＳ―ｂｏｘの数をＬｋで表すものとする。
【０１６９】
（証明１．ＡｃｔＤ（３ｄ）≧Ｂ１Ｄ＋Ｂ２Ｄの証明）
まず、ＡｃｔＤ（３ｄ）≧Ｂ１Ｄ＋Ｂ２Ｄの証明を行なう。
すなわち、図８、図１０に示すタイプ１の拡張Ｆｅｉｓｔｅｌ構造において、連続する３ｄラウンドに含まれる差分アクティブＳ−ｂｏｘの個数はＢ１Ｄ＋Ｂ２Ｄ以上であることを証明する。
【０１７０】
タイプ１の拡張Ｆｅｉｓｔｅｌ構造において、入力がゼロでない差分（Δｘ）を与えた場合について考察する。この場合、タイプ１の拡張Ｆｅｉｓｔｅｌ構造は、以下の４つの性質を持つ。
（性質１）連続するｄラウンドの中に最低ひとつのラウンドでは差分アクティブＳ−ｂｏｘが０ではないものが存在する
（性質２）Ｄｋ＝０ならば、Ｄｋ−ｄ＋１＝Ｄｋ＋１
（性質３）Ｄｋ≠０ならば、Ｄｋ−ｄ＋１＋Ｄｋ＋Ｄｋ＋１≧Ｂ１Ｄ
（性質４）Ｄｋ＋Ｄｋ＋ｄ≠０ならば、Ｄｋ−ｄ＋１＋Ｄｋ＋Ｄｋ＋ｄ＋Ｄｋ＋ｄ＋１≧Ｂ２Ｄ
【０１７１】
以上の４つの性質を利用して、
ＡｃｔＤ（３ｄ）≧Ｂ１Ｄ＋Ｂ２Ｄ
の証明、すなわち、
「連続する３ｄラウンドに含まれる差分アクティブＳ−ｂｏｘの個数はＢ１Ｄ＋Ｂ２Ｄ以上である」
ことを証明する。
【０１７２】
対象とするラウンドをｉ＋１番目からｉ＋３ｄ番目のラウンドとして考える。
場合１：もしも、ｉ＋ｄ＋２ラウンド目からｉ＋２ｄ−１ラウンド目までに０でないアクティブＳ−ｂｏｘが存在する場合。
０でないアクティブＳ−ｂｏｘが存在するラウンドをｋとするとＤｋ≠０と表せる。
【０１７３】
場合１−１：場合１に加えて、Ｄｋ＋ｄ−１≠０である場合、
性質３からＤｋ＋Ｄｋ＋１＋Ｄｋ−ｄ＋１≧Ｂ１Ｄ
性質４からＤｋ＋ｄ−１＋Ｄｋ−２ｄ＋Ｄｋ−１＋Ｄｋ＋ｄ≧Ｂ２Ｄ
であるから、
【数１２】
2008051829.tif 000014
となる。
【０１７４】
場合１−２：場合１に加えて、Ｄｋ＋１≠０である場合、
性質３からＤｋ＋１＋Ｄｋ＋２＋Ｄｋ−ｄ＋２≧Ｂ１Ｄ
性質４からＤｋ＋Ｄｋ−ｄ＋１＋Ｄｋ＋ｄ＋Ｄｋ＋ｄ＋１≧Ｂ２Ｄ
であるから、
【数１３】
2008051829.tif 000015
となる。
【０１７５】
場合１−３：場合１に加えて、Ｄｋ＋ｄ−１＝０かつＤｋ＋１＝０である場合、
性質２からＤｋ＝Ｄｋ＋ｄ≠０
性質３からＤｋ＋Ｄｋ＋１＋Ｄｋ−ｄ＋１≧Ｂ１Ｄ
性質３からＤｋ＋ｄ＋Ｄｋ＋ｄ＋１＋Ｄｋ＋１≧Ｂ２Ｄ
Ｄｋ＋１＝０であるため、
【数１４】
2008051829.tif 000016
となる。
【０１７６】
場合２：もしも、ｉ＋ｄ＋２ラウンド目からｉ＋２ｄ−１ラウンド目までに０でないアクティブＳ−ｂｏｘが存在しない場合。
性質１から、Ｄｉ＋ｄ＋１≠０、またはＤｉ＋２ｄ≠０である。
【０１７７】
場合２−１：Ｄｉ＋ｄ＋１≠０であるがＤｉ＋２ｄ＝０の場合、
性質２からＤｉ＋ｄ＋１＝Ｄｉ＋２ｄ＋１≠０
性質３からＤｉ＋ｄ＋１＋Ｄｉ＋ｄ＋２＋Ｄｉ＋２≧Ｂ１Ｄ
性質３からＤｉ＋２ｄ＋１＋Ｄｉ＋２ｄ＋２＋Ｄｉ＋ｄ＋２≧Ｂ１Ｄ
Ｄｉ＋ｄ＋２＝０であるため、
【数１５】
2008051829.tif 000017
である。
【０１７８】
場合２−２：Ｄｉ＋ｄ＋１＝０であるがＤｉ＋２ｄ≠０の場合、
性質２からＤｉ＋２ｄ＝Ｄｉ＋ｄ≠０
性質３からＤｉ＋ｄ＋Ｄｉ＋ｄ＋１＋Ｄｉ＋１≧Ｂ１Ｄ
性質３からＤｉ＋２ｄ＋Ｄｉ＋２ｄ＋１＋Ｄｉ＋ｄ＋１≧Ｂ１Ｄ
Ｄｉ＋ｄ＋１＝０であるため、
【数１６】
2008051829.tif 000018
である。
【０１７９】
場合２−３：Ｄｉ＋ｄ＋１≠０かつＤｉ＋２ｄ≠０の場合、
性質３からＤｉ＋ｄ＋１＋Ｄｉ＋ｄ＋２＋Ｄｉ＋２≧Ｂ１Ｄ
性質３からＤｉ＋２ｄ＋Ｄｉ＋２ｄ＋１＋Ｄｉ＋ｄ＋Ｄｉ＋１≧Ｂ２Ｄ
であるため、
【数１７】
2008051829.tif 000019
である。
【０１８０】
以上の場合１と場合２を総合すると、
【数１８】
2008051829.tif 000020
であることが証明される。すなわち、
ＡｃｔＤ（３ｄ）≧Ｂ１Ｄ＋Ｂ２Ｄ
が成立し、図８、図１０に示すタイプ１の拡張Ｆｅｉｓｔｅｌ構造において、連続する３ｄラウンドに含まれる差分アクティブＳ−ｂｏｘの個数はＢ１Ｄ＋Ｂ２Ｄ以上であることが証明される。
【０１８１】
（証明２．ＡｃｔＬ（３ｄ）≧２Ｂ２Ｌの証明）
次に、ＡｃｔＬ（３ｄ）≧２Ｂ２Ｌの証明を行なう。
すなわち、図８、図１０に示すタイプ１の拡張Ｆｅｉｓｔｅｌ構造において、連続する３ｄラウンドに含まれる線形アクティブＳ−ｂｏｘの個数は２Ｂ２Ｌ以上であることを証明する。
なお、Ｂ２Ｌは、前述したように、
【数１９】
2008051829.tif 000021
と定義する。
またｋ番目のＦ関数に含まれる線形アクティブＳ−ｂｏｘの数をＬｋで表すものとする。
【０１８２】
タイプ１の拡張Ｆｅｉｓｔｅｌ構造において、入力がゼロでない線形マスクを与えた場合には、以下の２つの性質を持つ。
（性質５）連続するｄラウンドの中の最低ひとつのラウンドでは線形アクティブＳ−ｂｏｘが０ではないものが存在する
（性質６）Ｌｋ＋Ｌｋ＋１＋Ｌｋ＋ｄ≧Ｂ２Ｌ、または、Ｌｋ＋Ｌｋ＋１＋Ｌｋ＋ｄ＝０である。なお、Ｌｋ＋Ｌｋ＋１＋Ｌｋ＋ｄ≧Ｂ２Ｌの場合は左辺に含まれる２つ以上の項が同時に０となることはない。
以上の２つの性質を利用して、
ＡｃｔＬ（３ｄ）≧２Ｂ２Ｌ
の証明、すなわち、
「連続する３ｄラウンドに含まれる線形アクティブＳ−ｂｏｘの個数は２Ｂ２Ｌ以上である」
ことを証明する。
【０１８３】
対象とするラウンドをｉ＋１番目からｉ＋３ｄ番目のラウンドとして考える。
場合１：もしも、ｉ＋ｄ＋２ラウンド目からｉ＋２ｄラウンド目までに０でないアクティブＳ−ｂｏｘが存在する場合。
０でないアクティブＳ−ｂｏｘが存在するラウンドをｋとするとＬｋ≠０である。
【０１８４】
場合１−１：場合１に加えて、Ｌｋ＋ｄ≠０またはＬｋ−１≠０である場合、
性質６からＬｋ＋Ｌｋ＋ｄ＋Ｌｋ＋１≧Ｂ２Ｌ
性質６からＬｋ−１＋Ｌｋ−１−ｄ＋Ｌｋ−ｄ≧Ｂ２Ｌ
であるから、
【数２０】
2008051829.tif 000022
となる。
【０１８５】
場合１−２：場合１に加えて、Ｌｋ＋ｄ＝０かつＬｋ−１＝０である場合、
性質６からＬｋ−ｄ＋１≠０
性質６からＬｋ＋Ｌｋ−１＋Ｌｋ＋ｄ−１≧Ｂ２Ｌ
性質６からＬｋ−ｄ＋１＋Ｌｋ＋１＋Ｌｋ−ｄ＋２≧Ｂ２Ｌ
【０１８６】
このときｄ≧４であれば、
【数２１】
2008051829.tif 000023
である。
【０１８７】
ｄ＝３であれば、Ｌｋ−１が重なるがすでにＬｋ−１＝０であることがわかっているため、
同様に、
【数２２】
2008051829.tif 000024
である。
【０１８８】
場合２：もしも、ｉ＋ｄ＋２ラウンド目からｉ＋２ｄ−１ラウンド目までに０でないアクティブＳ−ｂｏｘが存在しない場合。
性質１から、Ｌｉ＋ｄ＋１≠０となる。
性質６からＬｉ＋ｄ≠０
性質６からＬｉ＋ｄ＋１＋Ｌｉ＋ｄ＋２＋Ｌｉ＋２ｄ＋１≧Ｂ２Ｌ
性質６からＬｉ＋ｄ＋Ｌｉ＋ｄ−１＋Ｌｉ＋２ｄ−１≧Ｂ２Ｌ
【０１８９】
このときｄ≧４であれば、
【数２３】
2008051829.tif 000025
である。
【０１９０】
ｄ＝３であれば、Ｌｉ＋５が重なるがすでにＬｉ＋５＝０であることがわかっているため、
同様に、
【数２４】
2008051829.tif 000026
である。
【０１９１】
以上の場合１と場合２を総合すると、
【数２５】
2008051829.tif 000027
であることが証明される。すなわち、
ＡｃｔＬ（３ｄ）≧２Ｂ２Ｌ
が成立し、図８、図１０に示すタイプ１の拡張Ｆｅｉｓｔｅｌ構造において、連続する３ｄラウンドに含まれる線形アクティブＳ−ｂｏｘの個数は２Ｂ２Ｌ以上であることが証明される。
【０１９２】
（６−２．拡張Ｆｅｉｓｔｅｌ構造のタイプ２のアクティブＳ−ｂｏｘ数と、Ｆ関数中の線形変換行列に基づく最小分岐数との関係式の証明）
次に、図９を参照して説明した拡張Ｆｅｉｓｔｅｌ構造のタイプ２のアクティブＳ−ｂｏｘ数と、Ｆ関数中の線形変換行列に基づく最小分岐数との関係式の証明について説明する。
【０１９３】
すなわち、タイプ２の拡張Ｆｅｉｓｔｅｌ構造における連続するｐラウンドに含まれる差分アクティブＳ−ｂｏｘ数をＡｃｔＤ（ｐ）と表記し、線形アクティブＳ−ｂｏｘ数をＡｃｔＬ（ｐ）と表記した場合の関係式、
ＡｃｔＤ（６）≧Ｂ１Ｄ＋Ｂ２Ｄ
ＡｃｔＬ（６）≧２Ｂ２Ｌ
この関係式が成立することを証明する。
【０１９４】
先に図９を参照して説明した拡張Ｆｅｉｓｔｅｌ構造のタイプ２の構成を、別の形で示すと、図１１のように示すことができる。図９では、ラウンド毎に各データ系列の並びを入れ替えて示していたが、図１１は、データ系列の入れ替えを行なわず、１つの直線で示している。図１１では、ラウンド１〜１２までを示している。２つのラウンド（１〜２，３〜４，・・）のＦ関数を１つの横ラインに並べて示してある。例えば、図１１に示すラウンド１〜２の横ラインに示されたＦ関数Ｆ１，０〜Ｆ１，ｄ−１中、Ｆ１，０、Ｆ１，２、・・・、Ｆ１，ｄ−２の１つおきのＦ関数（出力の矢印が上向き）が第１ラウンドにおいて並列に実行される。次の第２ラウンドにおいて、残りのＦ１，１、Ｆ１，３、・・・、Ｆ１，ｄ−１の１つおきのＦ関数（出力の矢印が下向き）が並列に実行される。
【０１９５】
図１１において、Ｆ関数を識別するための番号は証明をわかりやすくするために新たに導入したものであり、２つの数字を使ってＦ関数の位置を決定している。
Ｆｉ，ｊのｉは、ラウンド数（１＝１，２ラウンド、２＝３，４ラウンド・・）を示し、ｙは、２つのラウンドにおけるＦ関数の一を示している。なお、ｊが０，２，４，の偶数であれば、先行ラウンドにおけるＦ関数であり、ｊが１，３，５，の奇数であれば、後続ラウンドにおけるＦ関数である。なお、Ｆ関数Ｆｉ，ｊに含まれる線形変換行列を［Ｍｉ，ｊ］と呼ぶものとする。
【０１９６】
この拡張Ｆｅｉｓｔｅｌ構造のタイプ２の構成において、先に、（５−２．拡張Ｆｅｉｓｔｅｌ構造のタイプ２に対するＤＳＭの適用）において説明した関係式、
ＡｃｔＤ（６）≧Ｂ１Ｄ＋Ｂ２Ｄ
ＡｃｔＬ（６）≧２Ｂ２Ｌ
が成立することを証明する。
上記式において、
ＡｃｔＤ（６）、ＡｃｔＬ（６）は、図９または図１１に示すタイプ２の拡張Ｆｅｉｓｔｅｌ構造における連続する６ラウンドに含まれる差分アクティブＳ−ｂｏｘ数と、線形アクティブＳ−ｂｏｘ数を意味する。
Ｂ１Ｄは、タイプ２の拡張Ｆｅｉｓｔｅｌ構造中に含まれるＦ関数中の線形変換行列の分岐数中の最小の分岐数、
Ｂ２Ｄ，Ｂ２Ｌは、先に（４−２），（４−３）において説明した拡張Ｆｅｉｓｔｅｌ構造中に含まれる１つのデータ系列に入力する連続するＦ関数中の線形変換行列の結合行列の最小分岐数、および逆行列の転置行列の結合行列の最小分岐数である。
【０１９７】
Ｂ１Ｄ，Ｂ２Ｄ，Ｂ２Ｌは、以下のように定義される。
【数２６】
2008051829.tif 000028
【０１９８】
なお、上記定義において、
Ｂ１Ｄ≧Ｂ２Ｄ
の関係が成立している。
また、Ｆｐ，ｑに含まれるアクティブＳ−ｂｏｘの数をＤｐ，ｑで表すものとする。なお以降で、添え字ｑの部分が負の値やｄ以上の値を持つ場合には、ｄによる剰余演算（ｑ  ｍｏｄ  ｄ）を行い常に０≦ｑ＜ｄとなるように補正するものとする。
【０１９９】
（証明３．ＡｃｔＤ（６）≧Ｂ１Ｄ＋Ｂ２Ｄの証明）
まず、ＡｃｔＤ（６）≧Ｂ１Ｄ＋Ｂ２Ｄの証明を行なう。
すなわち、図９、図１１に示すタイプ２の拡張Ｆｅｉｓｔｅｌ構造において、連続する６ラウンドに含まれる差分アクティブＳ−ｂｏｘの個数はＢ１Ｄ＋Ｂ２Ｄ以上であることを証明する。
【０２００】
タイプ２の拡張Ｆｅｉｓｔｅｌ構造において、入力がゼロでない差分（Δｘ）を与えた場合について考察する。この場合、タイプ２の拡張Ｆｅｉｓｔｅｌ構造は、以下の４つの性質を持つ。
（性質１）あるｉに対して、Ｆｐ，ｑ（ｐ＝ｉ，ｑ∈｛０，．．ｄ−１｝）の中には差分アクティブＳ−ｂｏｘが０ではないものが存在する
（性質２）Ｄｐ，ｑ＝０ならば、
Ｄｐ−１，ｑ＋１＝Ｄｐ，ｑ＋１  （ｑが偶数のとき）
Ｄｐ，ｑ＋１＝Ｄｐ＋１，ｑ＋１  （ｑが奇数のとき）
（性質３）Ｄｐ，ｑ≠０ならば、
Ｄｐ，ｑ＋Ｄｐ−１，ｑ＋１＋Ｄｐ，ｑ＋１≧Ｂ１Ｄ  （ｑが偶数のとき）
Ｄｐ，ｑ＋Ｄｐ，ｑ＋１＋Ｄｐ＋１，ｑ＋１≧Ｂ１Ｄ  （ｑが奇数のとき）
（性質４）Ｄｐ，ｑ＋Ｄｐ＋１，ｑ≠０ならば、
Ｄｐ，ｑ＋Ｄｐ＋１，ｑ＋Ｄｐ−１，ｑ＋１＋Ｄｐ＋１，ｑ＋１≧Ｂ２Ｄ  （ｑが偶数のとき）
Ｄｐ，ｑ＋Ｄｐ＋１，ｑ＋Ｄｐ，ｑ＋１＋Ｄｐ＋２，ｑ＋１≧Ｂ２Ｄ  （ｑが奇数のとき）
【０２０１】
以上の４つの性質を利用して、
ＡｃｔＤ（６）≧Ｂ１Ｄ＋Ｂ２Ｄ
の証明、すなわち、
「１以上の任意の整数ｉに対して、ｐ∈｛ｉ，ｉ＋１，ｉ＋２｝，ｑ∈｛０，１，．．ｄ−１｝を満たす３ｄ個のＦ関数Ｆｐ，ｑに含まれる差分アクティブＳ−ｂｏｘの総数はＢ１Ｄ＋Ｂ２Ｄ以上である」
ことを証明する。
【０２０２】
Ｄｐ，ｑ  （ｐ＝ｉ＋１，ｑ∈｛０，．．ｄ−１｝）の０でない要素を任意に取り出したとき、それがＤｊ，ｋ≠０であったとする。上述の（性質１）より必ず存在することが示される。
【０２０３】
場合１：Ｄｊ，ｋ−１≠０である場合、
性質３から
Ｄｊ，ｋ＋Ｄｊ−１，ｋ＋１＋Ｄｊ，ｋ＋１≧Ｂ１Ｄ  （ｋが偶数のとき）
Ｄｊ，ｋ＋Ｄｊ，ｋ＋１＋Ｄｊ＋１，ｋ＋１≧Ｂ１Ｄ  （ｋが奇数のとき）
性質４から
Ｄｊ−１，ｋ−１  ＋Ｄｊ，ｋ−１＋Ｄｊ−１，ｋ＋Ｄｊ＋１，ｋ≧Ｂ２Ｄ  （ｋが偶数のとき）
Ｄｊ，ｋ−１＋Ｄｊ＋１，ｋ−１＋Ｄｊ−１，ｋ＋Ｄｊ＋１，ｋ≧Ｂ２Ｄ  （ｋが奇数のとき）
であるから、
【数２７】
2008051829.tif 000029
が成立する。
【０２０４】
場合２：Ｄｊ，ｋ＋１≠０である場合、
性質３から
Ｄｊ，ｋ＋１＋Ｄｊ，ｋ＋２＋Ｄｊ＋１，ｋ＋２≧Ｂ１Ｄ  （ｋが偶数のとき）
Ｄｊ，ｋ＋１＋Ｄｊ−１，ｋ＋２＋Ｄｊ，ｋ＋２≧Ｂ１Ｄ  （ｋが奇数のとき）
性質４から
Ｄｊ，ｋ  ＋Ｄｊ＋１，ｋ＋Ｄｊ−１，ｋ＋１＋Ｄｊ＋１，ｋ＋１≧Ｂ２Ｄ  （ｋが偶数のとき）
Ｄｊ−１，ｋ＋Ｄｊ，ｋ＋Ｄｊ−１，ｋ＋１＋Ｄｊ＋１，ｋ＋１≧Ｂ２Ｄ  （ｋが奇数のとき）
であるから、
【数２８】
2008051829.tif 000030
が成立する。
【０２０５】
場合３：Ｄｊ，ｋ−１＝０かつＤｊ，ｋ＋１＝０である場合、
性質２から、Ｄｊ，ｋ−１＝０であるので
Ｄｊ＋１，ｋ＝Ｄｊ，ｋ≠０  （ｋが偶数のとき）
Ｄｊ−１，ｋ＝Ｄｊ，ｋ≠０  （ｋが奇数のとき）
性質３から、
Ｄｊ，ｋ＋Ｄｊ−１，ｋ＋１＋Ｄｊ，ｋ＋１≧Ｂ１Ｄ  （ｋが偶数のとき）
Ｄｊ，ｋ＋Ｄｊ，ｋ＋１＋Ｄｊ＋１，ｋ＋１≧Ｂ１Ｄ  （ｋが奇数のとき）
さらに性質３から
Ｄｊ＋１，ｋ＋Ｄｊ，ｋ＋１＋Ｄｊ＋１，ｋ＋１≧Ｂ１Ｄ  （ｋが偶数のとき）
Ｄｊ−１，ｋ＋Ｄｊ−１，ｋ＋１＋Ｄｊ，ｋ＋１≧Ｂ１Ｄ  （ｋが奇数のとき）
Ｄｊ，ｋ＋１＝０であるから、
【数２９】
2008051829.tif 000031
が成立する。
【０２０６】
以上を総合すると、
【数３０】
2008051829.tif 000032
であることが証明される。すなわち、
ＡｃｔＤ（６）≧Ｂ１Ｄ＋Ｂ２Ｄ
が成立し、図９、図１１に示すタイプ２の拡張Ｆｅｉｓｔｅｌ構造において、連続する６ラウンドに含まれる差分アクティブＳ−ｂｏｘの個数はＢ１Ｄ＋Ｂ２Ｄ以上であることが証明される。
【０２０７】
（証明４．ＡｃｔＬ（６）≧２Ｂ２Ｌの証明）
次に、ＡｃｔＬ（６）≧２Ｂ２Ｌの証明を行なう。
すなわち、図９、図１１に示すタイプ２の拡張Ｆｅｉｓｔｅｌ構造において、連続する６ラウンドに含まれる線形アクティブＳ−ｂｏｘの個数は２Ｂ２Ｌ以上であることを証明する。
なお、Ｂ２Ｌは、前述したように、
【数３１】
2008051829.tif 000033
と定義する。
またＦｐ，ｑ番目のＦ関数に含まれる線形アクティブＳ−ｂｏｘの数をＬｐ，ｑで表すものとする。
【０２０８】
タイプ２の拡張Ｆｅｉｓｔｅｌ構造において、入力がゼロでない線形マスクを与えた場合には、以下の２つの性質を持つ。
（性質５）あるｉに対して、Ｆｐ，ｑ  （ｐ＝ｉ，ｑ∈｛０，．．ｄ−１｝）の中には線形アクティブＳ−ｂｏｘが０ではないものが存在する
（性質６）
Ｌｊ，ｋ＋Ｌｊ＋１，ｋ＋Ｌｊ，ｋ＋１≧Ｂ２Ｌ  または、Ｌｊ，ｋ＋Ｌｊ＋１，ｋ＋Ｌｊ，ｋ＋１＝０  （ｋが偶数のとき）
Ｌｊ，ｋ＋Ｌｊ＋１，ｋ＋Ｌｊ＋１，ｋ＋１≧Ｂ２Ｌ  または、Ｌｊ，ｋ＋Ｌｊ＋１，ｋ＋Ｌｊ＋１，ｋ＋１＝０  （ｋが奇数のとき）
【０２０９】
なお、Ｌａ＋Ｌｂ＋Ｌｃ≧Ｂ２Ｌの形の場合は左辺に含まれる２つ以上の項が同時に０となることはない。
以上の２つの性質を利用して、
ＡｃｔＬ（６）≧２Ｂ２Ｌ
の証明、すなわち、
「１以上の任意の整数ｉに対して、ｐ∈｛ｉ，ｉ＋１，ｉ＋２｝，ｑ∈｛０，１，．．ｄ−１｝を満たす３ｄ個のＦ関数Ｆｐ，ｑに含まれる線形アクティブＳ−ｂｏｘの総数は２Ｂ２Ｌ以上である」
ことを証明する。
【０２１０】
Ｌｐ，ｑ  （ｐ＝ｉ＋１，ｑ∈｛０，．．ｄ−１｝）の０でない要素を任意に取り出したとき、それがＬｊ，ｋ≠０であったとする。そのようなＬｊ，ｋは性質５より必ず存在することが示される。
【０２１１】
性質６から、
Ｌｊ−１，ｋ＋Ｌｊ，ｋ＋Ｌｊ−１，ｋ＋１≧Ｂ２Ｌ    （ｋが偶数のとき）
Ｌｊ，ｋ＋Ｌｊ＋１，ｋ＋Ｌｊ＋１，ｋ＋１≧Ｂ２Ｌ    （ｋが奇数のとき）
【０２１２】
場合１：Ｌｊ，ｋ−１≠０である場合、
性質６から
Ｌｊ，ｋ−１＋Ｌｊ＋１，ｋ−１＋Ｌｊ＋１，ｋ≧Ｂ２Ｌ    （ｋが偶数のとき）
Ｌｊ−１，ｋ−１＋Ｌｊ，ｋ−１＋Ｌｊ−１，ｋ≧Ｂ２Ｌ    （ｋが奇数のとき）
従って、この場合、
【数３２】
2008051829.tif 000034
が成立する。
【０２１３】
場合２：Ｌｊ，ｋ−１＝０である場合、
性質６から
Ｌｊ−１，ｋ−１≠０    （ｋが偶数のとき）
Ｌｊ＋１，ｋ−１≠０    （ｋが奇数のとき）
であるので、
Ｌｊ−１，ｋ−２＋Ｌｊ，ｋ−２＋Ｌｊ−１，ｋ−１≧Ｂ２Ｌ    （ｋが偶数のとき）
Ｌｊ，ｋ−２＋Ｌｊ＋１，ｋ−２＋Ｌｊ＋１，ｋ−１≧Ｂ２Ｌ    （ｋが奇数のとき）
このときｄ≧４であるので、この場合、
【数３３】
2008051829.tif 000035
が成立する。
【０２１４】
以上の場合１と場合２を総合すると、
【数３４】
2008051829.tif 000036
であることが証明される。すなわち、
ＡｃｔＬ（６）≧２Ｂ２Ｌ
が成立し、図９、図１１に示すタイプ２の拡張Ｆｅｉｓｔｅｌ構造において、連続する６ラウンドに含まれる線形アクティブＳ−ｂｏｘの個数は２Ｂ２Ｌ以上であることが証明される。
【０２１５】
［７．Ｆ関数の設定および利用処理の工夫に基づく実装における改良構成］
上述したように、本発明では、データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造において、各ラウンドのＦ関数の線形変換処理として、少なくとも２以上の異なる行列を選択的に適用する、いわゆる拡散行列切り替え機構（ＤＳＭ）を適用することで、線形解析や差分解析に対する耐性を向上させた構成を実現している。
【０２１６】
このように、異なる複数の行列を選択適用させる演算処理を実行する構成をハードウェアで実現する場合、それぞれの行列に対応する演算を行なうハードウェア構成を持つ異なるＦ関数処理部が必要となる。特に、１つのラウンドにおいて、複数のＦ関数を並列に実行させようとした場合には、並列処理を行なうための複数のＦ関数用回路が必要となる。
【０２１７】
すなわち、先に図９や図１１を参照して説明したタイプ２の拡張Ｆｅｉｓｔｅｌ構造では、同一ラウンドに複数のＦ関数を適用したデータ変換処理を並列に実行する構成であり、このタイプ２の構成に従った処理をハードウェアで実行する場合、１つのラウンドで並列に実行する個数分のＦ関数のハードウェアを実装することが必要となる。このような並列実行の要求されるＦ関数は、同一構成である場合でも、その同一構成を持つＦ関数を複数、備えなければならない。
【０２１８】
前述したように、本発明の暗号処理構成は、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用する構成とすることで各種の攻撃に対する耐性を高めた構成を持つ。すなわち、拡散行列切り替え機構（ＤＳＭ：Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）を備えた構成としたものである。
【０２１９】
この拡散行列切り替え機構（ＤＳＭ）を満足させるためには、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続するｋ個（ただし、ｋは２以上の整数）のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［ＢｋＤ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［ＢｋＤ］が３以上となる条件を満足する複数の異なる行列に設定することなどの条件が満足されればよく、各ラウンドにおいて並列に実行されるＦ関数における制約は特にない。
【０２２０】
以下では、この特性に基づいて、拡張Ｆｅｉｓｔｅｌ構造において拡散行列切り替え機構（ＤＳＭ）に基づく耐性を維持しつつ、実装効率を高めた構成例について説明する。
【０２２１】
（７−１．拡張Ｆｅｉｓｔｅｌのタイプ２の効率的なＦ関数配置方法）
まず、先に、図９、図１１を参照して説明した拡張Ｆｅｉｓｔｅｌのタイプ２の効率的なＦ関数配置構成について説明する。タイプ２の拡張Ｆｅｉｓｔｅｌ構造は、先に説明した項目（５−２．拡張Ｆｅｉｓｔｅｌ構造のタイプ２に対するＤＳＭの適用）において述べたように、以下のパラメータを持つ。
パラメータ
（ａ）データ分割数：ｄ（ただしｄは４以上の偶数）
（ｂ）入出力データ長：ｄｍｎビット
（ｃ）分割データ長：ｍｎビット
（ｄ）１ラウンドあたりのＦ関数の数：ｄ／２
【０２２２】
すなわち、図９に示すように、各ラウンド内では左端から数えて奇数番目にあるｍｎビットのデータ系列に対してＦ関数が適用され、Ｆ関数の処理結果は、すぐ隣のデータに出力が排他的論理和される。なお、図９においては排他的論理和の演算記号を省略してある。
【０２２３】
以下では、このような構成を持つタイプ２の拡張Ｆｅｉｓｔｅｌ構造に対する実装効率を高めた構成について説明する。一例として、データ系列数（分割数）ｄ＝４の場合について、図１２を参照して説明する。図１２において、２つの異なる線形変換行列Ｍ１，Ｍ２によって線形変換を実行することなる２つのＦ関数をそれぞれＦ１，Ｆ２とする。
【０２２４】
図１２に示すＦｅｉｓｔｅｌ構造は、Ｆ関数Ｆ１，Ｆ２の２つのＦ関数を用いたｄ＝４の拡張Ｆｅｉｓｔｅｌ構造のタイプ２である。すなわち、
（ａ）データ分割数：４
（ｂ）入出力データ長：４ｍｎビット
（ｃ）分割データ長：ｍｎビット
（ｄ）１ラウンドあたりのＦ関数の数：４／２＝２
を持つ構成である。
【０２２５】
この図１２に示す構成の場合、２つのＦ関数を用いてＤＳＭ条件を満たすようにするにはいくつかの配置が考えられる。すなわち、ＤＳＭ条件を満足させるためには、前述したように、各データ系列ｓ（ｉ）に入力する連続するｋ個（ただし、ｋは２以上の整数）のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［ＢｋＤ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［ＢｋＤ］が３以上となる条件を満足する複数の異なる行列に設定することなどの条件が満足されればよく、各ラウンドにおいて並列に実行されるＦ関数における制約は特にない。
【０２２６】
従って、Ｆ関数の設定態様としては、
（ａ）１つのラウンドに設定する複数のＦ関数を同一のＦ関数とする設定、
（ｂ）１つのラウンドに設定する複数のＦ関数を異なるＦ関数とする設定、
上記２つの態様が可能となる。
【０２２７】
ここでは、図１２に示すように、１つのラウンドに存在する２つのＦ関数が互いにＦ１，Ｆ２となるように選択する構成をとる。この構成によるメリットは、１ラウンド分の処理を基本としてハードウェア（Ｈ／Ｗ）実装を行った場合に顕著に現れる。
【０２２８】
すなわち、ハードウェア（Ｈ／Ｗ）実装として、１つのラウンド分の処理だけを実行可能な構成、すなわち、図１３に示すように、Ｆ関数Ｆ１と、関数Ｆ２を並列に実行可能な構成を持つハードウェアを設定する。図１３は、図１２に示す拡張Ｆｅｉｓｔｅｌ構造に従った暗号処理を実行するハードウェア構成を持つ暗号処理装置２５０を示すブロック図である。
【０２２９】
暗号処理装置２５０は、Ｆ関数Ｆ１を実行する第１Ｆ関数（Ｆ１）専用処理回路２５１と、Ｆ関数Ｆ２を実行する第２Ｆ関数（Ｆ２）専用処理回路２５２と、制御回路２５３、および補助回路２５４から構成される。第１Ｆ関数（Ｆ１）専用処理回路２５１と、第２Ｆ関数（Ｆ２）専用処理回路２５２は並列に動作可能な構成であり、各ラウンドにおいて、これらの２つの回路を適用して２つの異なるＦ関数に基づくデータ変換が実行される。
【０２３０】
制御回路２５３は、各Ｆ関数専用処理回路２５１，２５２、および補助回路２５４に対する入出力データの制御を実行する。補助回路２５４はＦ関数以外の演算処理などを実行する。
【０２３１】
この構成を適用することで、必要なラウンド数分だけ、第１Ｆ関数（Ｆ１）専用処理回路２５１と、第２Ｆ関数（Ｆ２）専用処理回路２５２を適用してラウンド演算を行なうことが可能となる。すべてのラウンドにおいて２つのＦ関数専用回路が並列に実行され、無駄な回路を設けることのない実装が可能となる。
【０２３２】
図１２に示すように各ラウンドで並列に実行するＦ関数が２つの場合、これらを異なるＦ関数に設定することで、図１３に示すハードウェア実装により、すべてのラウンド演算を行なうことが可能となる。ちなみに、１つのラウンドにおいて実行するＦ関数を同じ設定、例えば第１ラウンドで、Ｆ１，Ｆ１を並列に実行し、第２ラウンドでＦ２，Ｆ２を実行するような構成とした場合、ハードウェアとしては、Ｆ１実行回路とＦ２実行回路を各々２つ設けることが必要となり、図１３に示す構成に比較して回路規模を大きなものとすることが必要となる。
【０２３３】
図１２に示すように各ラウンドで実行するＦ関数の組み合わせをすべてＦ１，Ｆ２の設定とすることで、図１３に示すハードウェアを適用して、各ラウンドにおいて、常にＦ１，Ｆ２が同時に実行でき、回路上の無駄を発生させることなく回路規模を小さくした小型の装置が実現される。
【０２３４】
図１２に示す構成は、データ系列ｄ＝４の場合であるが、その他のデータ系列数の場合も、同様な設定とすることで、効率的な実装が可能となる。例えばデータ系列数ｄ＝８の場合、１つのラウンドには、４つのＦ関数が設定されることになるが、この４つのＦ関数を、２つの異なるＦ関数Ｆ１，Ｆ２を２つずつ設定する構成とする。
【０２３５】
この場合の実装構成は、Ｆ関数Ｆ１，Ｆ２をそれぞれ２つずつ設けて、４つのＦ関数（Ｆ１，Ｆ１，Ｆ２，Ｆ２）を並列実行可能な構成とする。この構成により、すべてのラウンドにおいて４つのすべてのＦ関数が並列に実行され、無駄な回路を設けることのない実装が可能となる。
【０２３６】
また、データ系列数ｄ＝１６の場合、１つのラウンドに存在する８つのＦ関数をＦ１，Ｆ２を４つずつ設定する。さらに一般化して、データ系列数ｄ＝４ｘの場合には、各ラウンドにおいて、Ｆ関数Ｆ１，Ｆ２がｘ個づつ利用される構成にするようにして、ハードウェア実装として、Ｆ関数Ｆ１，Ｆ２を各々ｘ個設定した構成とすれば、毎ラウンドで必要とされるＦ１，Ｆ２の個数が同じであるため過不足無く実行でき実装効率を高めることができる。
【０２３７】
上述した処理例は、拡散行列切り替え機構（ＤＳＭ）を満足させるために、２つの線形変換行列を適用した２つの異なるＦ関数を設定した例であるが、３種類以上の線形変換行列を用いて３種類以上のＦ関数を設定した場合でも同様のことが言える。
【０２３８】
３種類のＦ関数を効率的な実装とするための配置例を図１４に示す。図１４は、データ系列数ｄ＝６の拡張Ｆｅｉｓｔｅｌのタイプ２の構造例である。この図１４に示す構成では、１つのラウンドに存在する３つのＦ関数がＦ１，Ｆ２，Ｆ３とかならずひとつずつ利用される構成になるように設定されている。
【０２３９】
この構成により、ハードウェア（Ｈ／Ｗ）実装時にＦ１，Ｆ２，Ｆ３をそれぞれひとつずつ実装するのみで、各ラウンドにおいて、Ｆ関数を並列に実行させる構成とすることができ、Ｈ／Ｗ的に見て無駄のない回路構成が実現される。
【０２４０】
さらに、データ系列数ｄ＝１２の場合は１つのラウンドに存在する６つのＦ関数をＦ１，Ｆ２，Ｆ３各々２つずつの設定とする。また、データ系列数ｄ＝１８の場合は、１つのラウンドに設定する９つのＦ関数について、Ｆ１，Ｆ２，Ｆ３を３つずつの設定とする。これらを一般化して、データ系列数ｄ＝６ｘの場合には、各ラウンドに設定するＦ関数をＦ１，Ｆ２，Ｆ３の各々がｘ個ずつとなるようにする。すなわち、各ラウンドにおいて、異なるＦは関数が均等に利用される構成とする。
【０２４１】
このようなＦ関数の設定構成とすることで、毎ラウンドで必要とされるＦ１，Ｆ２，Ｆ３の個数を同じ数に設定することができ、ハードウェア実装において過不足無く利用する回路の設定が可能となり、実装効率を高めることができる。ソフトウェアの場合にも、入出力値を取得するためのテーブルの利用態様が各ラウンドにおいて均一となるので、様々なパターンを想定したテーブルを構成することなく、１つの利用態様に応じたテーブルを設定してメモリに格納することが可能となる。
【０２４２】
上述した各処理例をさらに、一般化すると以下のように言える。
（１）ａ種類のＦ関数を利用したＴｙｐｅ２の拡張Ｆｅｓｉｔｅｌ構造を構成する場合、データ系列数（分割数）ｄ＝２ａｘ、ただしａは２以上の整数，ｘは１以上の整数、としたとき、１つのラウンド内に設定されるａｘ個のＦ関数として、全種類のＦ関数が均等にｘ個ずつ設定する構成とすることで実装効率を向上させることが可能となる。
【０２４３】
なお、上述したＦ関数の設定においては、各データ系列に入力されるＦ関数の設定を、前述したＤＳＭ条件を満足させる設定とすることで耐性の維持が可能である。
【０２４４】
（７−２．Ｆｅｉｓｔｅｌ構造と拡張Ｆｅｉｓｔｅｌ構造における部品の共通化）
前述したように、これまで説明してきたＦｅｉｓｔｅｌ構造、拡張Ｆｅｉｓｔｅｌのタイプ１、拡張Ｆｅｉｓｔｅｌのタイプ２のいずれに対してもＤＳＭメカニズムを利用することにより、攻撃に対する耐性を向上させるメリットがある。
【０２４５】
すなわち、Ｆｅｉｓｔｅｌ構造を大きく分類すると、
（ａ）データ系列数（分割数）ｄ＝２としたＦｅｉｓｔｅｌ構造
（ｂ）データ系列数（分割数）ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造
に分類され、さらに、拡張Ｆｅｉｓｔｅｌ構造は、
（ｂ１）各ラウンドにおいて１つのＦ関数の実行のみを許容したタイプ１、
（ｂ２）各ラウンドにおいて複数のＦ関数の並列実行を許容したタイプ２、
これら（ａ），（ｂ１），（ｂ２）の３種類に分類できる。
これらの３種類のＦｅｉｓｔｅｌ構造のいずれにおいても、ＤＳＭメカニズムの適用による耐性向上が実現される。
【０２４６】
ＤＳＭメカニズムの適用のためには、少なくとも２つ以上の異なる線形変換行列を実行する異なるＦ関数を実装することが必要となるが、この異なる複数のＦ関数を持つ実装構成によって、上述の複数の異なるＦｅｉｓｔｅｌ構造（ａ），（ｂ１），（ｂ２）を選択的に実行可能な装置を実現することができる。このような選択的な処理を実行する装置構成について以下、説明する。
【０２４７】
拡散行列切り替え機構（ＤＳＭ）を満足する線形変換行列を実行する複数の異なるＦ関数を決定し、これらの各Ｆ関数における入出力データのデータサイズをｍｎビットとする。このようなＦ関数を適用することで、例えば、図１５に示すような、データ系列ｄ＝２のＦｅｉｓｔｅｌ構造では２ｍｎビットのブロック暗号が実行される。
【０２４８】
図１５に示すデータ系列ｄ＝２のＦｅｉｓｔｅｌ構造の各Ｆ関数Ｆ１，Ｆ２は、入出力データサイズがｍｎビットである。このデータ系列ｄ＝２のＦｅｉｓｔｅｌ構造は、２ｍｎビットの平文を２ｍｎビットの暗号文にする処理、またはその逆の復号処理を行い、２ｍｎビットのブロック暗号を実行する。
【０２４９】
また、この図１５に示す入出力データサイズがｍｎビットのＦ関数Ｆ１，Ｆ２を利用することで、拡散行列切り替え機構（ＤＳＭ）を満足するデータ系列数ｄ＝４の拡張Ｆｅｉｓｔｅｌ構造を構成することができる。図１６にこの構成を示す。
【０２５０】
図１６に示すデータ系列ｄ＝４の拡張Ｆｅｉｓｔｅｌ構造の各Ｆ関数Ｆ１，Ｆ２は、入出力データサイズがｍｎビットであり、図１５に示すＦ関数Ｆ１，Ｆ２をそのまま適用したものである。このデータ系列ｄ＝４の拡張Ｆｅｉｓｔｅｌ構造は、４ｍｎビットの平文を４ｍｎビットの暗号文にする処理、またはその逆の復号処理を行い、４ｍｎビットのブロック暗号を実行する。
【０２５１】
さらに、一般化して、データ系列数ｄ＝ｘ、ただしｘは２以上の整数、とした場合、ｘｍｎビットの暗号化または復号処理を実行するブロック暗号構成を、同じＦ関数実行構成を用いて構築することができる。
【０２５２】
例えば、入出力ビットが６４ビットの異なるＦ関数Ｆ１，Ｆ２のみを用いて、ＤＳＭ機構を実現する入出力１２８ビットブロック暗号処理と、２５６ビットブロック暗号処理を選択的に実行可能な装置を構成することが可能となる。
【０２５３】
すなわちＦ関数としては、入出力ビットが６４ビットの異なる２つのＦ関数Ｆ１，Ｆ２を実装し、これらの利用態様を制御する。例えば、データ系列数ｄ＝２としたＦｅｉｓｔｅｌ構造（図１５）に基づく暗号処理を実行する場合は、各Ｆ関数Ｆ１，Ｆ２を各ラウンドにおいて１つ実行する構成とする。一方、データ系列数ｄ＝４とした拡張Ｆｅｉｓｔｅｌ構造（図１６）に基づく暗号処理を実行する場合は、各Ｆ関数Ｆ１，Ｆ２を各ラウンドにおいて並列に実行する構成とする。このように、２種類のＦ関数を装着することで、入出力１２８ビットブロック暗号と２５６ビットブロック暗号を選択的に実行可能な装置が実現される。すなわち、同じＦ関数を使って接続方法を変えることで異なるビット数のブロック暗号を実行することが可能であり、Ｓ／Ｗ，Ｈ／Ｗ両者において回路・コードの共有化などによる実装効率の向上が期待できる。
【０２５４】
このような構成を持つ暗号処理装置の構成例を図１７に示す。図１７に示す暗号処理装置２７０は、Ｆ関数Ｆ１を実行する第１Ｆ関数（Ｆ１）専用処理回路２７１と、Ｆ関数Ｆ２を実行する第２Ｆ関数（Ｆ２）専用処理回路２７２と、制御回路２７３、および補助回路２７４から構成される。第１Ｆ関数（Ｆ１）専用処理回路２７１と、第２Ｆ関数（Ｆ２）専用処理回路２７２は並列に動作可能な構成である。制御回路２７３は、各処理部に対するデータ入出力制御を行うとともに、Ｆｅｉｓｔｅｌ構造選択処理を実行する。補助回路２５４はＦ関数以外の演算処理などを実行する。
【０２５５】
制御回路２７３は、Ｆｅｉｓｔｅｌ構造選択処理として、
（ａ）データ系列数（分割数）ｄ＝２としたＦｅｉｓｔｅｌ構造
（ｂ１）データ系列数（分割数）ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて１つのＦ関数の実行のみを許容したタイプ１、
（ｂ２）データ系列数（分割数）ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて複数のＦ関数の並列実行を許容したタイプ２、
これらのいずれの構造に基づく暗号処理を実行するかを選択する。なお、設定情報は、例えば外部から入力する。あるいは暗号化または復号処理の対象となるデータのビット長に応じて実行する処理形態を選択する構成としてもよい。制御回路２７３は、選択に応じて、各Ｆ関数専用回路の適用シーケンスを変更し、各Ｆｅｉｓｔｅｌ構造に従ったラウンド関数を実行させる制御を行う。
【０２５６】
この構成を適用することで、第１Ｆ関数（Ｆ１）専用処理回路２５１と、第２Ｆ関数（Ｆ２）専用処理回路２５２を適用して様々なＦｅｉｓｔｅｌ構造を適用した暗号処理が可能となり、暗号化処理、または復号処理の処理ビットが異なる様々なビット対応の暗号処理を実行可能となる。
【０２５７】
また、図１７には２つのＦ関数を持つ例を示しているが、２つのＦ関数を用いた例にはとどまらず、任意の個数のＦ関数を用いた構成でも同様の結果が期待できる。例えば、先に図１４を参照して説明した拡張Ｆｅｉｓｔｅｌ構造では、３つの異なるＦ関数Ｆ１，Ｆ２．Ｆ３を適用して拡散行列切り替え機構（ＤＳＭ）を満足するデータ系列数ｄ＝６の拡張Ｆｅｉｓｔｅｌ構造を構成している。これと同じ３種類のＦ関数Ｆ１，Ｆ２，Ｆ３のＦ関数を適用して図１８に示すデータ系列ｄ＝２のＦｅｉｓｔｅｌ構造を持つ暗号処理構成が構築できる。このデータ系列ｄ＝２の構成においても、各行列Ｆ１，Ｆ２，Ｆ３は、ＤＳＭ機構を満足する設定で配置される。
【０２５８】
このような３種類のＦ関数Ｆ１，Ｆ２，Ｆ３を実行する暗号処理装置の構成例を図１９に示す。図１９に示す暗号処理装置２８０は、Ｆ関数Ｆ１を実行する第１Ｆ関数（Ｆ１）専用処理回路２８１と、Ｆ関数Ｆ２を実行する第２Ｆ関数（Ｆ２）専用処理回路２８２と、Ｆ関数Ｆ３を実行する第３Ｆ関数（Ｆ３）専用処理回路２８３と、制御回路２８４、および補助回路２７５から構成される。第１Ｆ関数（Ｆ１）専用処理回路２８１と、第２Ｆ関数（Ｆ２）専用処理回路２８２と、第３Ｆ関数（Ｆ３）専用処理回路２８３とは並列に動作可能な構成である。制御回路２８４は、各処理部に対するデータ入出力制御を行うとともに、Ｆｅｉｓｔｅｌ構造選択処理を実行する。補助回路２８５はＦ関数以外の演算処理などを実行する。
【０２５９】
制御回路２８４は、Ｆｅｉｓｔｅｌ構造選択処理として、
（ａ）データ系列数（分割数）ｄ＝２としたＦｅｉｓｔｅｌ構造
（ｂ１）データ系列数（分割数）ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて１つのＦ関数の実行のみを許容したタイプ１、
（ｂ２）データ系列数（分割数）ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて複数のＦ関数の並列実行を許容したタイプ２、
これらのいずれの構造に基づく暗号処理を実行するかを選択する。なお、設定情報は、例えば外部から入力する。制御回路２８４は、設定に応じて、各Ｆ関数専用回路の適用シーケンスを変更し、各Ｆｅｉｓｔｅｌ構造に従ったラウンド関数を実行させる制御を行う。
【０２６０】
この構成を適用することで、第１Ｆ関数（Ｆ１）専用処理回路２８１〜第３Ｆ関数（Ｆ３）専用処理回路２８３を適用して様々なＦｅｉｓｔｅｌ構造を適用した暗号処理が可能となり、暗号化処理、または復号処理の処理ビットが異なる様々なビット対応の暗号処理を実行可能となる。なお、４つ以上のＦ関数実行部を持つ構成も可能である。
【０２６１】
上述したように、拡散行列切り替え機構（ＤＳＭ）を満足する線形変換行列を実行する複数の異なるＦ関数を決定し、これらの各Ｆ関数を実装して、Ｆ関すを適用した処理シーケンスを変更することで、
（ａ）データ系列数（分割数）ｄ＝２としたＦｅｉｓｔｅｌ構造
（ｂ１）データ系列数（分割数）ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて１つのＦ関数の実行のみを許容したタイプ１、
（ｂ２）データ系列数（分割数）ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて複数のＦ関数の並列実行を許容したタイプ２、
これらのいずれかの構造に基づく暗号処理を洗濯的に実行する構成が実現され、暗号化処理または復号処理における処理ビット数を変更可能な装置が実現される。
【０２６２】
例えば、ａ種類（ａは２以上の整数）のＦ関数を構成して、上記３種類のＦｅｉｓｔｅｌ構造に基づく暗号処理を実行し、かつ拡散行列切り替え機構（ＤＳＭ）を満足させた処理構成により耐性の高い暗号処理を行なうことが可能となる。
【０２６３】
［８．本発明の暗号処理および暗号アルゴリズム構築処理のまとめ］
最後に、上述した本発明の暗号処理および暗号アルゴリズム構築処理についてまとめて説明する。
【０２６４】
本発明の暗号処理装置は、図１、図２を参照して説明したように、非線形変換処理および線形変換処理を含むデータ変換処理を実行するＳＰ型Ｆ関数を複数ラウンド繰り返すＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理を実行する暗号処理部を有する。さらに、図５以下を参照して説明したように、暗号処理部は、データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する構成であり、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用する構成を有する。
【０２６５】
これらの２以上の複数の異なる行列は、拡散行列切り替え機構（ＤＳＭ：Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）を実現するように設定され、ＤＳＭにより、差分攻撃や線形攻撃に対する耐性を向上させた暗号処理が実現される。このＤＳＭによる耐性向上の実現のため特定の条件に従った行列の選択、配置が行なわれる。
【０２６６】
すなわち、Ｆ関数において実行する線形変換処理に適用される複数の行列として、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列が選択され、これらの複数の異なる行列が、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に繰り返し配置される。
【０２６７】
さらに、具体的には、暗号処理部において利用される複数の異なる行列は、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続するｋ個（ただし、ｋは２以上の整数）のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［ＢｋＤ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［ＢｋＤ］が３以上となる条件を満足する複数の異なる行列である。
あるいは、拡張Ｆｅｉｓｔｅｌ構造の各データ系列ｓ（ｉ）に入力する連続する２個のＦ関数に含まれる線形変換行列に基づいて算出されるデータ系列対応の最小分岐数［Ｂ２Ｌ（ｓ（ｉ））］中から選択される全データ系列中の最小分岐数［Ｂ２Ｌ］が３以上となる条件を満足する複数の異なる行列である。
【０２６８】
本発明の暗号処理装置の暗号処理部は、これらの複数の異なる行列を、ｎ個（ただし、ｎは２以上の整数）の異なる行列を、Ｍ０，Ｍ１，・・Ｍｎ−１としたとき、これらを、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に順番に繰り返し配置した構成を有する。具体的な拡張Ｆｅｉｓｔｅｌ構造の例としては、例えば図８、図１０を参照して説明した１つのラウンドに１つのＦ関数のみを実行するタイプ１の拡張Ｆｅｉｓｔｅｌ構造や、図９、図１１を参照して説明した１つのラウンドに複数のＦ関数を並列に実行する拡張Ｆｅｉｓｔｅｌ構造がある。
【０２６９】
なお、本発明は、このような拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する暗号処理装置および方法並びに暗号処理を実行するコンピュータ・プログラムと、さらに、上述の拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行するための暗号処理アルゴリズムを構築する情報処理装置、方法並びにコンピュータ・プログラムをも含むものである。
【０２７０】
暗号処理アルゴリズムを構築する情報処理装置は、例えば一般的なＰＣ等の情報処理装置が適用可能であり、以下の処理ステップを実行可能な制御部を持つ。すなわち、
データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理アルゴリズムの構成において、各ラウンドにおけるＦ関数において実行する線形変換処理に適用する少なくとも２以上の複数の異なる行列を決定する行列決定ステップと、
行列決定ステップにおいて決定した複数の異なる行列を、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に繰り返し配置する行列設定ステップである。
【０２７１】
上述の行列決定ステップは、２以上の複数の異なる行列として、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列を適用行列として決定する処理を実行するステップとして実行される。
【０２７２】
このような処理アルゴリズムによって設定された拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理においては、拡散行列切り替え機構（ＤＳＭ：Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）が実現され、ＤＳＭにより、差分攻撃や線形攻撃に対する耐性を向上させた暗号処理が実現される。
【０２７３】
［９．暗号処理装置の構成例］
最後に、上述した実施例に従った暗号処理を実行する暗号処理装置としてのＩＣモジュール３００の構成例を図２０に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図２０に示すＩＣモジュール３００は、これら様々な機器に構成することが可能である。
【０２７４】
図２０に示すＣＰＵ(Central processing Unit)３０１は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ３０２は、ＣＰＵ３０１が実行するプログラム、あるいは演算パラメータなどの固定データを格納するＲＯＭ（Read-Only-Memory）、ＣＰＵ３０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるＲＡＭ（Random Access Memory）等からなる。また、メモリ３０２は暗号処理に必要な鍵データや、暗号処理において適用する変換テーブル（置換表）や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【０２７５】
暗号処理部３０３は、例えば上述した拡張Ｆｅｉｓｔｅｌ型の共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理を実行する。なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭに格納し、ＣＰＵ３０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。
【０２７６】
乱数発生器３０４は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【０２７７】
送受信部３０５は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ＩＣモジュールとのデータ通信を実行し、ＩＣモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【０２７８】
このＩＣモジュール３００は、例えば、上述した実施例に従って、データ系列数ｄがｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ型暗号処理を実行する。拡張Ｆｅｉｓｔｅｌ構造におけるＦ関数の線形変換行列として、上述した実施例に従った態様で、異なる線形変換行列を設定することで、拡散行列切り替え機構（ＤＳＭ：Ｄｉｆｆｕｓｉｏｎ  Ｓｗｉｔｃｈｉｎｇ  Ｍｅｃｈａｎｉｓｍ）が実現され、差分攻撃や線形攻撃に対する耐性を向上させることが可能となる。
【０２７９】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０２８０】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０２８１】
例えば、プログラムは記録媒体としてのハードディスクやＲＯＭ（Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０２８２】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０２８３】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０２８４】
上述したように、本発明の一実施例の構成によれば、非線形変換部および線形変換部を有するＳＰＮ型のＦ関数を、複数ラウンド繰り返し実行するＦｅｉｓｔｅｌ型共通鍵ブロック暗号処理において、２つのデータ系列を持つＦｅｉｓｔｅｌ構造を拡張したＦｅｉｓｔｅｌ構造、すなわち、例えば３つ、４つなど、２以上の任意のデータ系列を持つ拡張型のＦｅｉｓｔｅｌ構造において、複数の異なる線形変換行列を適用したラウンド関数部を設定することで拡散行列切り替え機構（ＤＳＭ）を実現し、線形解析や差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムの構築および暗号処理の実行が可能となる。
【０２８５】
本発明の一実施例の構成によれば、データ系列数：ｄをｄ≧２の整数とした拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行する構成において、各ラウンドにおけるＦ関数において実行する線形変換処理に、少なくとも２以上の複数の異なる行列を選択的に適用する構成を有し、２以上の複数の異なる行列として、拡張Ｆｅｉｓｔｅｌ構造の各データ系列に入力するＦ関数に含まれる線形変換行列に基づくデータ系列対応の最小分岐数中から選択される全データ系列中の最小分岐数が予め定めた値以上となる条件を満足する複数の異なる行列として設定することで、拡散行列切り替え機構（ＤＳＭ）を実現し、線形解析や差分解析に対する耐性の高い共通鍵ブロック暗号アルゴリズムの構築および暗号処理の実行が可能となる。
【０２８６】
さらに、本発明の一実施例の構成によれば、複数の異なる行列による異なる線形変換処理を実行するａ（ａ≧２）種類のＦ関数を利用したデータ系列数：ｄ＝２ａｘの拡張Ｆｅｓｉｔｅｌ構造（ｘ≧１）を適用した暗号処理を実行する構成において、１つのラウンドにおいて、全種類（ａ種類）のＦ関数を均等にｘ個ずつ実行する構成としたので、無駄な回路を設けることのない小型の暗号処理装置が実現される。
【０２８７】
さらに、本発明の一実施例の構成によれば、複数の異なる行列による異なる線形変換処理を実行する複数のＦ関数実行部を構成して、複数のＦ関数実行部の利用シーケンスを設定に応じて変更する構成としたことで、
（ａ）データ系列数ｄ＝２としたＦｅｉｓｔｅｌ構造による暗号処理、または、
（ｂ１）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて１つのＦ関数の実行のみを許容した暗号処理、または、
（ｂ２）データ系列数ｄ≧２の任意数とした拡張Ｆｅｉｓｔｅｌ構造であり、各ラウンドにおいて複数のＦ関数の並列実行を許容した暗号処理、
上記（ａ），（ｂ１），（ｂ２）のいずれかの暗号処理を選択的に実行することを可能とした暗号処理装置が実現される。
【図面の簡単な説明】
【０２８８】
【図１】Ｆｅｉｓｔｅｌ構造を持つ代表的な共通鍵ブロック暗号の構成を示す図である。
【図２】ラウンド関数部として設定されるＦ関数の構成について説明する図である。
【図３】２つの異なる線形変換行列を利用したＦｅｉｓｔｅｌ型暗号アルゴリズムについて説明する図である。
【図４】３つの異なる線形変換行列を利用したＦｅｉｓｔｅｌ型暗号アルゴリズムについて説明する図である。
【図５】拡張Ｆｅｉｓｔｅｌ構造の定義について説明する図である。
【図６】７つのデータ系列（ｄ＝７）を持つ拡張Ｆｅｉｓｔｅｌ構造例を示す図である。
【図７】拡張Ｆｅｉｓｔｅｌ構造の各構成部および各構成部の入出力データの定義について説明する図である。
【図８】拡張Ｆｅｉｓｔｅｌ構造のタイプ１に対するＤＳＭの適用について説明する図である。
【図９】拡張Ｆｅｉｓｔｅｌ構造のタイプ２に対するＤＳＭの適用について説明する図である。
【図１０】拡張Ｆｅｉｓｔｅｌ構造のタイプ１に対するＤＳＭの適用について説明する図である。
【図１１】拡張Ｆｅｉｓｔｅｌ構造のタイプ２に対するＤＳＭの適用について説明する図である。
【図１２】拡張Ｆｅｉｓｔｅｌ構造の実装効率を高めた構成について説明する図である。
【図１３】拡張Ｆｅｉｓｔｅｌ構造の実装効率を高めたハードウェア構成例について説明する図である。
【図１４】３種類のＦ関数を効率的な実装とするための配置例について説明する図である。
【図１５】データ系列ｄ＝２のＦｅｉｓｔｅｌ構造とした２ｍｎビットのブロック暗号構成を示す図である。
【図１６】拡散行列切り替え機構（ＤＳＭ）を満足するデータ系列数ｄ＝４の拡張Ｆｅｉｓｔｅｌ構造を示す図である。
【図１７】異なるビット数のブロック暗号を実行することを可能とした回路共有構成について説明する図である。
【図１８】３種類のＦ関数Ｆ１，Ｆ２，Ｆ３のＦ関数を適用したデータ系列ｄ＝２のＦｅｉｓｔｅｌ構造について説明する図である。
【図１９】３種類のＦ関数Ｆ１，Ｆ２，Ｆ３を実行する暗号処理装置の構成例について説明する図である。
【図２０】本発明に係る暗号処理を実行する暗号処理装置としてのＩＣモジュールの構成例を示す図である。
【符号の説明】
【０２８９】
１０１  入力データＰＬ（Plain-Left）
１０２  入力データＰＲ(Plain-Right)
１０３  ラウンド鍵
１０４  排他的論理和部
１２０  Ｆ関数
１２１  Ｓボックス（Ｓ−ｂｏｘ）
１２２  線形変換部
２５０  暗号処理装置
２５１  第１Ｆ関数専用処理回路
２５２  第２Ｆ関数専用処理回路
２５３  制御回路
２５４  補助回路
２７１  第１Ｆ関数専用処理回路
２７２  第２Ｆ関数専用処理回路
２７３  制御回路
２７４  補助回路
２８１  第１Ｆ関数専用処理回路
２８２  第２Ｆ関数専用処理回路
２８３  第３Ｆ関数専用処理回路
２８４  制御回路
２８５  補助回路
３００  ＩＣモジュール
３０１  ＣＰＵ(Central processing Unit)
３０２  メモリ
３０３  暗号処理部
３０４  乱数発生器
３０５  送受信部
【図１】
2008051829.tif 000037
【図２】
2008051829.tif 000038
【図３】
2008051829.tif 000039
【図４】
2008051829.tif 000040
【図５】
2008051829.tif 000041
【図６】
2008051829.tif 000042
【図７】
2008051829.tif 000043
【図８】
2008051829.tif 000044
【図９】
2008051829.tif 000045
【図１０】
2008051829.tif 000046
【図１１】
2008051829.tif 000047
【図１２】
2008051829.tif 000048
【図１３】
2008051829.tif 000049
【図１４】
2008051829.tif 000050
【図１５】
2008051829.tif 000051
【図１６】
2008051829.tif 000052
【図１７】
2008051829.tif 000053
【図１８】
2008051829.tif 000054
【図１９】
2008051829.tif 000055
【図２０】
2008051829.tif 000056