(57)【特許請求の範囲】
【請求項１】
ブロック暗号方式による暗号化装置において、
第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する、縦続接続された複数の拡散処理手段を備え、
前記拡散処理手段は、それぞれ、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施して出力する複数の第１の処理手段と、これら複数の第１の処理手段からの第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理手段とを含み、
前記拡散処理手段に含まれる複数の第１の処理手段及び第２の処理手段においては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段は、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理手段は、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする暗号化装置。
【請求項２】
前記第１の処理手段は、それぞれ、前記第２のビット長のデータがさらに複数に分割された第３のデータ幅の各データに対してそれぞれ非線形変換処理を施す複数の非線形変換処理手段と、これら複数の非線形変換処理手段からの第３のデータ幅の各データからなる第２のデータ幅のデータに対して線形拡散処理を施す線形拡散処理手段と、この線形拡散処理手段からの第２のデータ幅のデータがさらに複数に分割された第３のデータ幅の各データに対してそれぞれ非線形変換処理を施す複数の非線形変換処理手段とからなるものであることを特徴とする請求項１に記載の暗号化装置。
【請求項３】
前記第２の処理手段は、各々の前記非線形変換処理手段から出力される各第３のビット長のデータから相対応する１ビットずつを取りだしたビット群に対して施す線形拡散処理を、該１ビットを取り出す位置を排他的に変えたものについてそれぞれ行うことによって、前記第１のビット長のデータにわたる線形拡散処理を行うものであることを特徴とする請求項２に記載の暗号化装置。
【請求項４】
前記第１のビット長は１２８ビットであり、前記第２のビット長は３２ビットであり、前記第３のビット長は８ビットであり、
前記第２の処理手段は、１６個の前記第３のビット長のデータの各々から同一位置の１ビットずつを取りだして得た１６ビットデータに対して施す線形拡散処理を、該１ビットを取り出す位置を排他的に変えた８つの１６ビットデータのそれぞれについて行うものであることを特徴とする請求項３に記載の暗号化装置。
【請求項５】
前記第２の処理手段は、実回路によって実装されたものであることを特徴とする請求項１ないし４のいずれか１項に記載の暗号化装置。
【請求項６】
前記第２の処理手段の入力側のビットと出力側のビットとの間の結合関係は、ガロア体の乗算に基づいて決定されたものであることを特徴とする請求項５に記載の暗号化装置。
【請求項７】
前記第２の処理手段は、ソフトウェアを実行することによって実現されるものであることを特徴とする請求項１ないし４のいずれか１項に記載の暗号化装置。
【請求項８】
共通鍵ブロック暗号方式による暗号化装置であって、
初段では入力された１２８ビットの平文ブロックデータを、２段目以降では前段での処理が施された１２８ビットのブロックデータを入力とし、該ブロックデータを４分割した４組の３２ビット・データに対してそれぞれ局所的な線形拡散処理および非線形変換処理を施し出力する４つの第１の非線形変換処理部と、これら４つの第１の非線形変換処理部からそれぞれ出力された４組の３２ビット・データを連結した１２８ビットのブロックデータに対して最大距離分離行列を用いて線形拡散処理を施し次段へ出力する第１の拡散処理部とを、１段分の段構成として、該段構成を所定段数分接続し、
最後の前記第１の拡散処理部の後段に、この第１の拡散処理部から出力される１２８ビットのブロックデータを入力とする前記４つの第１の非線形変換処理部を接続し、
この４つの第１の非線形変換処理部の後段に、これら４つの第１の非線形変換処理部からそれぞれ出力された４組の３２ビット・データを連結した１２８ビットのブロックデータに対して１２８ビットの鍵データを加算して１２８ビットの暗号化されたブロックデータとして出力する第１の鍵加算部を接続して構成されるとともに、
前記第１の非線形変換処理部の各々は、与えられた１組の前記３２ビット・データをさらに４分割した４組の８ビット・データに対してそれぞれ８ビットの鍵データを加算する４つの第２の鍵加算部と、各第２の鍵加算部の出力に対してそれぞれ８ビットの入出力変換表を用いて非線形変換を行う４つの第２の非線形変換処理部と、これら４つの第２の非線形変換処理部からそれぞれ出力された４組の８ビット・データを連結した３２ビット・データに対して最大距離分離行列を用いて線形拡散処理を施す第２の拡散処理部と、この第２の拡散処理部の後段にさらに接続された４組の前記第２の鍵加算部および第２の非線形変換処理部とを含むものであり、
前記第１の拡散処理部の各々は、前段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部からそれぞれ出力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における入力側の１つの要素とするとともに、後段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部へそれぞれ入力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における出力側の１つの要素として、２４のガロア体の乗算に基づいた４行４列の行列演算またはこれと等価な回路によって線形拡散処理を行う１６ビット拡散手段を、該前段及び後段の第２の非線形変換処理部についての該８ビットのうちの各ビットに対応して有し、
各々の段を構成する当該第１の拡散処理部及び当該４つの第１の非線形変換処理部においては、当該４つの第１の非線形変換処理部に１つずつ含まれる合計４つの第２の拡散処理部への入力たる１２８ビットのブロックデータから選択した１ビットと、当該第１の拡散処理部からの出力たる１２８ビットのブロックデータから選択した１ビットとからなる全ての組み合わせの各々において、当該組み合わせに係る入力たる１ビットを処理すべき第２の拡散処理部は、当該第２の拡散処理部から出力される３２ビット・データのうちの少なくとも２ビットであって当該第１の拡散処理部の有する８つの１６ビット拡散手段のうちのいずれか同一の１６ビット拡散手段により処理される２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、当該第１の拡散処理部の有する当該同一の１６ビット拡散手段は、少なくとも当該第２の拡散処理部から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする暗号化装置。
【請求項９】
共通鍵ブロック暗号方式による暗号化装置であって、
初段では入力された６４ビットの平文ブロックデータを、２段目以降では前段での処理が施された６４ビットのブロックデータを入力とし、該ブロックデータを２分割した２組の３２ビット・データに対してそれぞれ局所的な線形拡散処理および非線形変換処理を施し出力する２つの第１の非線形変換処理部と、これら２つの第１の非線形変換処理部からそれぞれ出力された２組の３２ビット・データを連結した６４ビットのブロックデータに対して最大距離分離行列を用いて線形拡散処理を施し次段へ出力する第１の拡散処理部とを、１段分の段構成として、該段構成を所定段数分接続し、
最後の前記第１の拡散処理部の後段に、この第１の拡散処理部から出力される６４ビットのブロックデータを入力とする前記２つの第１の非線形変換処理部を接続し、
この２つの第１の非線形変換処理部の後段に、これら２つの第１の非線形変換処理部からそれぞれ出力された２組の３２ビット・データを連結した６４ビットのブロックデータに対して６４ビットの鍵データを加算して６４ビットの暗号化されたブロックデータとして出力する第１の鍵加算部を接続して構成されるとともに、
前記第１の非線形変換処理部の各々は、与えられた１組の前記３２ビット・データをさらに４分割した４組の８ビット・データに対してそれぞれ８ビットの鍵データを加算する４つの第２の鍵加算部と、各第２の鍵加算部の出力に対してそれぞれ８ビットの入出力変換表を用いて非線形変換を行う４つの第２の非線形変換処理部と、これら４つの第２の非線形変換処理部からそれぞれ出力された４組の８ビット・データを連結した３２ビット・データに対して最大距離分離行列を用いて線形拡散処理を施す第２の拡散処理部と、この第２の拡散処理部の後段にさらに接続された４組の前記第２の鍵加算部および第２の非線形変換処理部とを含むものであり、
前記第１の拡散処理部の各々は、前段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部からそれぞれ出力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における入力側の１つの要素とするとともに、後段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部へそれぞれ入力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における出力側の１つの要素として、２４のガロア体の乗算に基づいた２行２列の行列演算またはこれと等価な回路によって線形拡散処理を行う８ビット拡散手段を、該前段及び後段の第２の非線形変換処理部についての該８ビットのうちの各ビットに対応して有し、
各々の段を構成する当該第１の拡散処理部及び当該２つの第１の非線形変換処理部においては、当該２つの第１の非線形変換処理部に１つずつ含まれる合計２つの第２の拡散処理部への入力たる６４ビットのブロックデータから選択した１ビットと、当該第１の拡散処理部からの出力たる６４ビットのブロックデータから選択した１ビットとからなる全ての組み合わせの各々において、当該組み合わせに係る入力たる１ビットを処理すべき第２の拡散処理部は、当該第２の拡散処理部から出力される３２ビット・データのうちの少なくとも２ビットであって当該第１の拡散処理部の有する８つの８ビット拡散手段のうちのいずれか同一の８ビット拡散手段により処理される２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、当該第１の拡散処理部の有する当該同一の８ビット拡散手段は、少なくとも当該第２の拡散処理部から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする暗号化装置。
【請求項１０】
縦続接続された複数の拡散処理手段を備え、各拡散処理手段は複数の第１の処理手段と第２の処理手段とを含むブロック暗号方式による暗号化装置における暗号化方法であって、
前記拡散処理手段により、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する拡散処理ステップを、前記複数の拡散処理手段につき順次行うものであり、
前記拡散処理ステップは、それぞれ、当該拡散処理手段の複数の第１の処理手段の各々により、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施す複数の第１の処理ステップと、当該拡散処理手段の第２の処理手段により、これら局所的拡散処理を施された複数の第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理ステップとを含み、
前記拡散処理ステップに含まれる複数の第１の処理ステップ及び第２の処理ステップにおいては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段に係る第１の処理ステップでは、当該第１の処理手段により、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理ステップでは、第２の処理手段により、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする暗号化方法。
【請求項１１】
縦続接続された複数の拡散処理手段を備え、各拡散処理手段は複数の第１の処理手段と第２の処理手段とを含むブロック暗号方式による暗号化装置としてコンピュータを機能させるためのプログラムにおいて、
前記プログラムは、
前記拡散処理手段により、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する拡散処理ステップを、前記複数の拡散処理手段につき順次、コンピュータに実行させるものであり、
前記拡散処理ステップは、それぞれ、当該拡散処理手段の複数の第１の処理手段の各々により、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施す複数の第１の処理ステップと、当該拡散処理手段の第２の処理手段により、これら局所的拡散処理を施された複数の第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理ステップとをコンピュータに実行させるものであるとともに、
前記拡散処理ステップに含まれる複数の第１の処理ステップ及び第２の処理ステップにおいては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段に係る第１の処理ステップでは、当該第１の処理手段により、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理ステップでは、第２の処理手段により、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めるものであることを特徴とするプログラム。
【請求項１２】
ブロック暗号方式による復号装置において、
第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する、縦続接続された複数の拡散処理手段を備え、
前記拡散処理手段は、それぞれ、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施して出力する複数の第１の処理手段と、これら複数の第１の処理手段からの第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理手段とを含み、
前記拡散処理手段に含まれる複数の第１の処理手段及び第２の処理手段においては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段は、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理手段は、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする復号装置。
【請求項１３】
縦続接続された複数の拡散処理手段を備え、各拡散処理手段は複数の第１の処理手段と第２の処理手段とを含むブロック暗号方式による復号装置における復号方法であって、
前記拡散処理手段により、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する拡散処理ステップを、前記複数の拡散処理手段につき順次行うものであり、
前記拡散処理ステップは、それぞれ、当該拡散処理手段の複数の第１の処理手段の各々により、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施す複数の第１の処理ステップと、当該拡散処理手段の第２の処理手段により、これら局所的拡散処理を施された複数の第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理ステップとを含み、
前記拡散処理ステップに含まれる複数の第１の処理ステップ及び第２の処理ステップにおいては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段に係る第１の処理ステップでは、当該第１の処理手段により、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理ステップでは、第２の処理手段により、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする復号方法。
【請求項１４】
縦続接続された複数の拡散処理手段を備え、各拡散処理手段は複数の第１の処理手段と第２の処理手段とを含むブロック暗号方式による復号装置としてコンピュータを機能させるためのプログラムにおいて、
前記プログラムは、
前記拡散処理手段により、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する拡散処理ステップを、前記複数の拡散処理手段につき順次、コンピュータに実行させるものであり、
前記拡散処理ステップは、それぞれ、当該拡散処理手段の複数の第１の処理手段の各々により、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施す複数の第１の処理ステップと、当該拡散処理手段の第２の処理手段により、これら局所的拡散処理を施された複数の第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理ステップとをコンピュータに実行させるものであるとともに、
前記拡散処理ステップに含まれる複数の第１の処理ステップ及び第２の処理ステップにおいては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段に係る第１の処理ステップでは、当該第１の処理手段により、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理ステップでは、第２の処理手段により、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めるものであることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ブロック暗号方式による暗号化装置及び暗号化方法並びに復号装置及び復号方法に関する。
【０００２】
【従来の技術】
共通鍵ブロック暗号の代表的な基本構造にＳＰＮ型とＦｅｉｓｔｅｌ型があり、各々について差分／線形解読法に対する強度評価と耐性を高める設計法が研究されている（文献［１］Ｖ．Ｒｉｊｍｅｎ，  Ｊ．Ｄａｅｍｅｎ，  Ｂ．Ｐｒｅｎｅｅｌ，  Ａ．Ｂｏｓｓｅｌａｅｒｓ，  Ｅ．ＤｃＷｉｎ，“Ｔｈｅ  Ｃｉｐｈｅｒ  ＳＨＡＲＫ，”  Ｆａｓｔ  Ｓｏｆｔｗａｒｅ  Ｅｎｃｒｙｐｔｉｏｎ，  ＬＮＣＳ  １０３９，１９９６．  、文献［２］青木和麻呂，太田和夫，“最大平均差分確率および最大平均線形確率のより厳密な評価，”ＳＣＩＳ  ９６−４Ａ，１９９６．  、文献［３］松井充，“ブロック暗号ＭＩＳＴＹ，”ＩＳＥＣ  ９６−１１，１９９６．）。ＳＰＮ構造では、活性Ｓ−ｂｏｘ数の保証が出来るので、設定した強度を達成するための段数決定がしやすい（文献［１］  ）。しかし、ブロック・サイズが大きくなりＳ−ｂｏｘの並列度が上がると、拡散層の処理が複雑になり、速度が低下する傾向がある。
【０００３】
この点を改善したのが、ＳＱＵＡＲＥ／Ｒｉｊｎｄａｅｌ型の暗号である（文献［４］Ｊ．Ｄａｅｍｅｎ，  Ｌ．Ｒ．Ｋｎｕｄｓｅｎ，  Ｖ．Ｒｉｊｍｅｎ，“Ｔｈｅ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  Ｓｑｕａｒｅ，”  Ｆａｓｔ  Ｓｏｆｔｗａｒｅ  Ｅｎｃｒｙｐｔｉｏｎ，  ＬＮＣＳ  １２６７，１９９７．  、文献［５］Ｊ．Ｄａｅｍｅｎ，  Ｖ．Ｒｉｊｍｅｎ，“ＡＥＳ  Ｐｒｏｐｏｓａｌ：  Ｒｉｊｎｄａｅｌ，”ｈｔｔｐ：／／ｗｗｗ．ｅａｓｔ．ｋｕｌｅｕｖｅｎ．ａｃ．ｂｅ／〜ｒｉｊｍｅｎ／ｒｉｊｄａｅｌ／ｒｉｊｎｄａｅｌｄｏｃＶ２．ｚｉｐ  ）。この型の暗号では、１６個の並列Ｓ−ｂｏｘを４×４の行列状に並べて線形拡散を同一列内に制限することで処理を軽減している。また、線形拡散にバイト位置の並べ替えを組み合わせることで、ある段の１バイトの影響は２段後に全バイトに広がり、４段で活性Ｓ−ｂｏｘ数は２５以上を達成している。
【０００４】
しかしながら、同一列内のバイトが次の段で混合しないという性質があるため、ＳＱＵＡＲＥ攻撃という専用の攻撃法が存在する（文献［１］、文献［５］）。これは、拡散層が１種類という制約下で、強度と効率の両立を目指した結果と考えることが出来る。
【０００５】
【発明が解決しようとする課題】
ＳＰＮ型構造は、活性Ｓ−ｂｏｘ数の下限の見積もりが容易で、差分／線形解読法に対する強度を保証した設計が可能である。しかしながら、平文／暗号文のブロック・サイズの増加に従い、Ｓ−ｂｏｘの並列度が高くなると、拡散層の結合部の計算コストも高くなるという欠点があった。また、拡散層の設計によってデータ攪拌が均一でなくなる可能性があった。
【０００６】
本発明は、上記事情を考慮してなされたもので、計算コストを抑えたまま高く均一な拡散を可能とする暗号化装置及び暗号化方法並びに復号装置及び復号方法を提供することを目的とする。
【０００７】
【課題を解決するための手段】
本発明は、ブロック暗号方式による暗号化装置において、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する、縦続接続された複数の拡散処理手段を備え、前記拡散処理手段は、それぞれ、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施して出力する複数の第１の処理手段と、これら複数の第１の処理手段からの第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理手段とを含み、前記拡散処理手段に含まれる複数の第１の処理手段及び第２の処理手段においては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段は、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理手段は、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする。
好ましくは、前記第１の処理手段は、それぞれ、前記第２のビット長のデータがさらに複数に分割された第３のデータ幅の各データに対してそれぞれ非線形変換処理を施す複数の非線形変換処理手段と、これら複数の非線形変換処理手段からの第３のデータ幅の各データからなる第２のデータ幅のデータに対して線形拡散処理を施す線形拡散処理手段と、この線形拡散処理手段からの第２のデータ幅のデータがさらに複数に分割された第３のデータ幅の各データに対してそれぞれ非線形変換処理を施す複数の非線形変換処理手段とからなるものであるようにしてもよい。
好ましくは、前記第２の処理手段は、各々の前記非線形変換処理手段から出力される各第３のビット長のデータから相対応する１ビットずつを取りだしたビット群に対して施す線形拡散処理を、該１ビットを取り出す位置を排他的に変えたものについてそれぞれ行うことによって、前記第１のビット長のデータにわたる線形拡散処理を行うものであるようにしてもよい。
好ましくは、前記第１のビット長は１２８ビットであり、前記第２のビット長は３２ビットであり、前記第３のビット長は８ビットであり、前記第２の処理手段は、１６個の前記第３のビット長のデータの各々から同一位置の１ビットずつを取りだして得た１６ビットデータに対して施す線形拡散処理を、該１ビットを取り出す位置を排他的に変えた８つの１６ビットデータのそれぞれについて行うものであるようにしてもよい。
好ましくは、前記第２の処理手段は、実回路によって実装されたものであるようにしてもよい。
好ましくは、前記第２の処理手段の入力側のビットと出力側のビットとの間の結合関係は、ガロア体の乗算に基づいて決定されたものであるようにしてもよい。
好ましくは、前記第２の処理手段は、ソフトウェアを実行することによって実現されるものであるようにしてもよい。
また、本発明は、共通鍵ブロック暗号方式による暗号化装置であって、初段では入力された１２８ビットの平文ブロックデータを、２段目以降では前段での処理が施された１２８ビットのブロックデータを入力とし、該ブロックデータを４分割した４組の３２ビット・データに対してそれぞれ局所的な線形拡散処理および非線形変換処理を施し出力する４つの第１の非線形変換処理部と、これら４つの第１の非線形変換処理部からそれぞれ出力された４組の３２ビット・データを連結した１２８ビットのブロックデータに対して最大距離分離行列を用いて線形拡散処理を施し次段へ出力する第１の拡散処理部とを、１段分の段構成として、該段構成を所定段数分接続し、最後の前記第１の拡散処理部の後段に、この第１の拡散処理部から出力される１２８ビットのブロックデータを入力とする前記４つの第１の非線形変換処理部を接続し、この４つの第１の非線形変換処理部の後段に、これら４つの第１の非線形変換処理部からそれぞれ出力された４組の３２ビット・データを連結した１２８ビットのブロックデータに対して１２８ビットの鍵データを加算して１２８ビットの暗号化されたブロックデータとして出力する第１の鍵加算部を接続して構成されるとともに、前記第１の非線形変換処理部の各々は、与えられた１組の前記３２ビット・データをさらに４分割した４組の８ビット・データに対してそれぞれ８ビットの鍵データを加算する４つの第２の鍵加算部と、各第２の鍵加算部の出力に対してそれぞれ８ビットの入出力変換表を用いて非線形変換を行う４つの第２の非線形変換処理部と、これら４つの第２の非線形変換処理部からそれぞれ出力された４組の８ビット・データを連結した３２ビット・データに対して最大距離分離行列を用いて線形拡散処理を施す第２の拡散処理部と、この第２の拡散処理部の後段にさらに接続された４組の前記第２の鍵加算部および第２の非線形変換処理部とを含むものであり、前記第１の拡散処理部の各々は、前段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部からそれぞれ出力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における入力側の１つの要素とするとともに、後段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部へそれぞれ入力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における出力側の１つの要素として、２４のガロア体の乗算に基づいた４行４列の行列演算またはこれと等価な回路によって線形拡散処理を行う１６ビット拡散手段を、該前段及び後段の第２の非線形変換処理部についての該８ビットのうちの各ビットに対応して有し、各々の段を構成する当該第１の拡散処理部及び当該４つの第１の非線形変換処理部においては、当該４つの第１の非線形変換処理部に１つずつ含まれる合計４つの第２の拡散処理部への入力たる１２８ビットのブロックデータから選択した１ビットと、当該第１の拡散処理部からの出力たる１２８ビットのブロックデータから選択した１ビットとからなる全ての組み合わせの各々において、当該組み合わせに係る入力たる１ビットを処理すべき第２の拡散処理部は、当該第２の拡散処理部から出力される３２ビット・データのうちの少なくとも２ビットであって当該第１の拡散処理部の有する８つの１６ビット拡散手段のうちのいずれか同一の１６ビット拡散手段により処理される２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、当該第１の拡散処理部の有する当該同一の１６ビット拡散手段は、少なくとも当該第２の拡散処理部から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする。
また、本発明は、共通鍵ブロック暗号方式による暗号化装置であって、初段では入力された６４ビットの平文ブロックデータを、２段目以降では前段での処理が施された６４ビットのブロックデータを入力とし、該ブロックデータを２分割した２組の３２ビット・データに対してそれぞれ局所的な線形拡散処理および非線形変換処理を施し出力する２つの第１の非線形変換処理部と、これら２つの第１の非線形変換処理部からそれぞれ出力された２組の３２ビット・データを連結した６４ビットのブロックデータに対して最大距離分離行列を用いて線形拡散処理を施し次段へ出力する第１の拡散処理部とを、１段分の段構成として、該段構成を所定段数分接続し、最後の前記第１の拡散処理部の後段に、この第１の拡散処理部から出力される６４ビットのブロックデータを入力とする前記２つの第１の非線形変換処理部を接続し、この２つの第１の非線形変換処理部の後段に、これら２つの第１の非線形変換処理部からそれぞれ出力された２組の３２ビット・データを連結した６４ビットのブロックデータに対して６４ビットの鍵データを加算して６４ビットの暗号化されたブロックデータとして出力する第１の鍵加算部を接続して構成されるとともに、
前記第１の非線形変換処理部の各々は、与えられた１組の前記３２ビット・データをさらに４分割した４組の８ビット・データに対してそれぞれ８ビットの鍵データを加算する４つの第２の鍵加算部と、各第２の鍵加算部の出力に対してそれぞれ８ビットの入出力変換表を用いて非線形変換を行う４つの第２の非線形変換処理部と、これら４つの第２の非線形変換処理部からそれぞれ出力された４組の８ビット・データを連結した３２ビット・データに対して最大距離分離行列を用いて線形拡散処理を施す第２の拡散処理部と、この第２の拡散処理部の後段にさらに接続された４組の前記第２の鍵加算部および第２の非線形変換処理部とを含むものであり、前記第１の拡散処理部の各々は、前段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部からそれぞれ出力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における入力側の１つの要素とするとともに、後段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部へそれぞれ入力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における出力側の１つの要素として、２４のガロア体の乗算に基づいた２行２列の行列演算またはこれと等価な回路によって線形拡散処理を行う８ビット拡散手段を、該前段及び後段の第２の非線形変換処理部についての該８ビットのうちの各ビットに対応して有し、各々の段を構成する当該第１の拡散処理部及び当該２つの第１の非線形変換処理部においては、当該２つの第１の非線形変換処理部に１つずつ含まれる合計２つの第２の拡散処理部への入力たる６４ビットのブロックデータから選択した１ビットと、当該第１の拡散処理部からの出力たる６４ビットのブロックデータから選択した１ビットとからなる全ての組み合わせの各々において、当該組み合わせに係る入力たる１ビットを処理すべき第２の拡散処理部は、当該第２の拡散処理部から出力される３２ビット・データのうちの少なくとも２ビットであって当該第１の拡散処理部の有する８つの８ビット拡散手段のうちのいずれか同一の８ビット拡散手段により処理される２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、当該第１の拡散処理部の有する当該同一の８ビット拡散手段は、少なくとも当該第２の拡散処理部から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする。
また、本発明は、縦続接続された複数の拡散処理手段を備え、各拡散処理手段は複数の第１の処理手段と第２の処理手段とを含むブロック暗号方式による暗号化装置における暗号化方法であって、前記拡散処理手段により、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する拡散処理ステップを、前記複数の拡散処理手段につき順次行うものであり、前記拡散処理ステップは、それぞれ、当該拡散処理手段の複数の第１の処理手段の各々により、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施す複数の第１の処理ステップと、当該拡散処理手段の第２の処理手段により、これら局所的拡散処理を施された複数の第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理ステップとを含み、前記拡散処理ステップに含まれる複数の第１の処理ステップ及び第２の処理ステップにおいては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段に係る第１の処理ステップでは、当該第１の処理手段により、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理ステップでは、第２の処理手段により、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする。
また、本発明は、縦続接続された複数の拡散処理手段を備え、各拡散処理手段は複数の第１の処理手段と第２の処理手段とを含むブロック暗号方式による暗号化装置としてコンピュータを機能させるためのプログラムにおいて、前記プログラムは、前記拡散処理手段により、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する拡散処理ステップを、前記複数の拡散処理手段につき順次、コンピュータに実行させるものであり、前記拡散処理ステップは、それぞれ、当該拡散処理手段の複数の第１の処理手段の各々により、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施す複数の第１の処理ステップと、当該拡散処理手段の第２の処理手段により、これら局所的拡散処理を施された複数の第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理ステップとをコンピュータに実行させるものであるとともに、前記拡散処理ステップに含まれる複数の第１の処理ステップ及び第２の処理ステップにおいては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段に係る第１の処理ステップでは、当該第１の処理手段により、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理ステップでは、第２の処理手段により、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めるものであることを特徴とする。
また、本発明は、ブロック暗号方式による復号装置において、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する、縦続接続された複数の拡散処理手段を備え、前記拡散処理手段は、それぞれ、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施して出力する複数の第１の処理手段と、これら複数の第１の処理手段からの第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理手段とを含み、前記拡散処理手段に含まれる複数の第１の処理手段及び第２の処理手段においては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段は、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理手段は、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする。
また、本発明は、縦続接続された複数の拡散処理手段を備え、各拡散処理手段は複数の第１の処理手段と第２の処理手段とを含むブロック暗号方式による復号装置における復号方法であって、前記拡散処理手段により、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する拡散処理ステップを、前記複数の拡散処理手段につき順次行うものであり、前記拡散処理ステップは、それぞれ、当該拡散処理手段の複数の第１の処理手段の各々により、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施す複数の第１の処理ステップと、当該拡散処理手段の第２の処理手段により、これら局所的拡散処理を施された複数の第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理ステップとを含み、前記拡散処理ステップに含まれる複数の第１の処理ステップ及び第２の処理ステップにおいては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段に係る第１の処理ステップでは、当該第１の処理手段により、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理ステップでは、第２の処理手段により、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めることを特徴とする。
また、本発明は、縦続接続された複数の拡散処理手段を備え、各拡散処理手段は複数の第１の処理手段と第２の処理手段とを含むブロック暗号方式による復号装置としてコンピュータを機能させるためのプログラムにおいて、前記プログラムは、前記拡散処理手段により、第１のビット長のデータを入力し、これに拡散処理を施して得た第１のビット長のデータを出力する拡散処理ステップを、前記複数の拡散処理手段につき順次、コンピュータに実行させるものであり、前記拡散処理ステップは、それぞれ、当該拡散処理手段の複数の第１の処理手段の各々により、当該拡散処理手段への入力たる第１のビット長のデータが複数に分割された第２のビット長の各データに対してそれぞれ局所的拡散処理を施す複数の第１の処理ステップと、当該拡散処理手段の第２の処理手段により、これら局所的拡散処理を施された複数の第２のビット長の各データからなる第１のビット長のデータに対して線形拡散処理を施して得た第１のビット長のデータを当該拡散処理手段からの出力とする第２の処理ステップとをコンピュータに実行させるものであるとともに、前記拡散処理ステップに含まれる複数の第１の処理ステップ及び第２の処理ステップにおいては、当該拡散処理手段への入力たる第１のビット長のデータから選択した１ビットと、当該拡散処理手段からの出力たる第１のビット長のデータから選択した１ビットとからなる全ての組み合わせの各々について、当該組み合わせに係る入力たる１ビットを処理すべき第１の処理手段に係る第１の処理ステップでは、当該第１の処理手段により、当該第１の処理手段から出力される第２のビット長のデータのうちの少なくとも２ビットの状態を、当該入力たる１ビットの状態に基づいて求め、第２の処理ステップでは、第２の処理手段により、少なくとも当該第１の処理手段から出力される当該２ビットの状態に基づいて、当該組み合わせに係る出力たる１ビットの状態を求めるものであることを特徴とする。
【０００９】
なお、暗号化装置に係る本発明は、暗号方法に係る発明、復号装置に係る発明、復号方法に係る発明としても成立する（もちろん、従属項についても同様である）。
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手順を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムを記録したコンピュータ読取り可能な記録媒体としても成立する。
【００１０】
本発明では、局所的なデータ拡散を行う小型の拡散層とブロック幅に及ぶ拡散を行う大型の拡散層を交互に重ねて運用する。本発明によれば、複数種類の異なる拡散（例えば、大小２段階の拡散）によって、計算コストを抑えたまま高く均一な拡散を実現した。また、階層的にブランチ数が保証でき（ブランチ数の階層性）、活性Ｓ−ｂｏｘ数の下限を容易に保証できる。また、強度評価がしやすいという特性がある。
【００１１】
ＳＱＵＡＲＥ暗号やＲｉｊｎｄａｅｌ暗号では、小型の拡散とバイト単位の並べ方によって同等の効果を実現している。しかし、それらの暗号では拡散層が１種類であるため、ＳＱＵＡＲＥ攻撃と呼ばれる解読法が存在する。本発明では、大小２種類の拡散層の組み合わせ方によって、ＳＱＵＡＲＥ攻撃に対する耐性の向上が可能である。
【００１２】
また、大型の拡散層の構造を工夫することによって、例えば、その前段のＳ−ｂｏｘと後段のＳ−ｂｏｘとの間の組み合わせの全部または一部について、差分経路を複線化することによって、高いなだれ効果が得られ、より効果的なＳＱＵＡＲＥ攻撃に対する耐性の向上が可能になる。
【００１３】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
【００１４】
本実施形態では、局所的な拡散（小拡散）と、ブロック幅に渡る拡散（大拡散）との組み合わせによる、入れ子型（再帰的）ＳＰＮ構造の暗号方式について説明する。
【００１５】
以下では、暗号化を中心に説明し、その後で復号について説明する。なお、復号アルゴリズムは、暗号アルゴリズムの逆変換であり、鍵は暗号化と復号で共通の、秘密の鍵である。
【００１６】
また、本暗号方式は、ハードウェアによってもソフトウェアによっても実現可能であり、以下に示す構成例は、暗号化装置（復号装置）の機能ブロック図としても成立し、また暗号アルゴリズム（復号アルゴリズム）の機能モジュール図としても成立する。
【００１７】
図１に、入れ子型（再帰的）ＳＰＮ構造の暗号方式（暗号化装置（もしくは復号装置）または暗号アルゴリズム（もしくは復号アルゴリズム）、暗号処理装置）の基本的な構成例を示す。
【００１８】
図１に示されるように、入れ子型ＳＰＮ構造では、各段において複数並列に並んだ非線形変換モジュール（後述の例では拡大Ｓ−ｂｏｘ）２の各々により局所的な小拡散を行い、次いで拡散モジュール（後述の例では大ＭＤＳ）３によりブロック幅に渡る大拡散を行い、また非線形変換モジュール２により局所的な小拡散を行い、ということを所定段数繰り返す。さらに、非線形変換モジュール２は、非線形変換モジュール（後述の例ではＳ−ｂｏｘ）４と拡散モジュール（後述の例では小ＭＤＳ）５とを交互に配列して構成される。
【００１９】
すなわち、本実施形態の入れ子型ＳＰＮ構造は、通常のＳＰＮ構造のＳ−ｂｏｘの部分に小型のＳＰＮ構造（後述の例では２段のＳＰＮ構造）を再帰的に埋め込んだものである。
【００２０】
このような入れ子型ＳＰＮ構造によれば、ブランチ数が階層的に保証でき（ブランチ数の階層性）、活性Ｓ−ｂｏｘ数の下限を容易に保証できる、という優れた特質が得られる。また、入れ子型ＳＰＮ構造には、この他に、単純明快な構造のため、強度評価がしやすいという特性がある。
【００２１】
なお、図１では、局所的な小拡散を４並列で表しているが、これに限定されるものではなく、それ以外の並列数も可能である。
また、図１では、全ブロック長を均等に分割した複数の小拡散を並列されているが、これに限定されるものではなく、異なるビット長の小拡散を複数組み合わせることも可能である。また、この場合に、全ての小拡散のビット長を異なるようにしてもよいし、一部の小拡散のビット長は同じであってもよい。
また、図１では、１種類の局所的な小拡散を用いているが、２種類以上の局所的な小拡散を用いることも可能である（例えば、図１において、ブロック幅に渡る拡散モジュール３を、１つおきに、２つの非線形変換モジュール２に渡る拡散モジュールに替えた構成）。
また、同一構成の繰り返し構造にする方法の他に、一部のみ構成を替えることも可能である。
また、例えば、全ての非線形変換モジュール２の構成を同一構成にすることも、非線形変換モジュール２について、異なる構成を混在させることも可能である。この点は、拡散モジュール３、非線形変換モジュール４、拡散モジュール５のそれぞれについても同様である。
また、例えば、最初の入力段と、最後の出力段だけ、他の中間段とは異なる内部構成にしてもよい。
また、図１では、２階層の入れ子構造であるが、３階層以上の入れ子構造も可能である（３階層の場合、例えば、非線形変換モジュール４をさらにＳＰＮ構造にする）。また、例えば、非線形変換モジュール２によって階層構造を異ならせることも可能である。
この他にも、種々のバリエーションが考えられる。
【００２２】
以下では、８ビットＳ−ｂｏｘを利用したＡＥＳ相当の１２８ビット・ブロック暗号の具体例を用いつつ本実施形態について説明する。
【００２３】
ここで、ブロック暗号の強度評価に関して説明する。
【００２４】
与えられた関数ｆの暗号強度を見積もる重要な指標として最大差分確率／最大線形確率がある。
【００２５】
［最大差分確率、最大線形確率の定義］
関数ｆ（ｘ）に対し、最大差分確率ｄｐｆと最大線形確率ｌｐｆはそれぞれ次式で表される。
【００２６】
【数１】
0003557178.tif 000002
ここで、Δｘはｘの入力差分、Γｘはｘのマスク値を表す。
【００２７】
一般には、最大差分確率ｄｐｆや最大線形確率ｌｐｆを求めることが困難な場合が多い。ここで、その近似値として最大差分特性確率ＤＰｆおよび最大線形特性確率ＬＰｆで安全性を評価する。
【００２８】
本実施形態では、入れ子型ＳＰＮ構造を暗号化関数として用いる。ここでは、その基本構造であるＳＰＳ構造の特性について述べる。ここで、ＳＰＳとは、Ｓ−ｂｏｘ層と拡散層ＰをＳ−Ｐ−Ｓのように３層重ねた構造を指す。
【００２９】
［ブランチ数］
ＳＰＳ構造において入力ｘに対する拡散層の出力がθ（ｘ）のとき、差分解読に対するブランチ数Ｂは次式で定義する（文献［１］、文献［６］清水秀夫，金子敏信，“共通鍵暗号のｄｉｆｆｕｓｉｏｎ層について，”ＳＣＩＳ  ９９−７２，１９９９．）。
【００３０】
【数２】
0003557178.tif 000003
【００３１】
ここで、ｗ（）はＳ−ｂｏｘのビット幅を符号長としたハミング距離である。非零の入出力差分に接続するＳ−ｂｏｘを活性Ｓ−ｂｏｘと呼ぶ。
【００３２】
この拡散層の入出力にＳ−ｂｏｘを接続した構造をＳＰＳ構造と呼ぶ。Ｓ−ｂｏｘが全単射のとき、ＳＰＳ構造への入力ビットに非零の差分を持つものが１個でもあれば、ブランチ数の定義により、活性Ｓ−ｂｏｘはブランチ数以上（すなわちＢ以上）になる。また、Ｓ−ｂｏｘの最大差分確率をｐｓ  とすると、ＳＰＳ構造の最大差分特性確率は、上界値ｐｓ  Ｂを越えない。
【００３３】
［ＭＤＳ（Ｍａｘｉｍｕｍ  Ｄｉｓｔａｎｃｅ  Ｓｅｐａｒａｂｌｅ）行列］
ＳＰＳ構造のＳ層としてＭ並列のＳ−ｂｏｘを用いた場合、それらを結合する拡散層のブランチ数は（Ｍ＋１）以下であり、ブランチ数が（Ｍ＋１）を満たす線形変換をＭＤＳ（Ｍａｘｉｍｕｍ  Ｄｉｓｔａｎｃｅ  Ｓｅｐａｒａｂｌｅ；最大距離分離）行列と呼ぶ。
【００３４】
拡散層がＭＤＳ行列であるとき、ＳＰＳ構造の最大差分特性確率は上界値ｐｓ  Ｍ＋１  を越えない［１］。同様に、Ｓ−ｂｏｘの最大線形確率をｑｓ  とすると、ＳＰＳ構造の最大線形特性確率はｑｓ Ｍ＋１  を越えない。
【００３５】
［入れ子型ＳＰＳ構造のブランチ数］
２段ＳＰＮ構造をそれより大きなＳＰＮ構造のＳ−ｂｏｘとして利用するとき、拡大Ｓ−ｂｏｘ（小構造）と呼ぶことにする。ここで、Ｓ−ｂｏｘはＭ１  並列であり、拡大Ｓ−ｂｏｘ内の拡散層のブランチ数をＢ１  とする。拡大Ｓ−ｂｏｘに対するＭ２  並列の２段ＳＰＮ構造（大構造）を考え、その拡散層のブランチ数をＢ２  とする。このとき、大構造中の活性Ｓ−ｂｏｘ数は下界値Ｂ１  ・Ｂ２  を下回らない。この性質がブランチ数の階層性である。
【００３６】
また、大小２種類の拡散層の両方がＭＤＳ行列であるとき、活性Ｓ−ｂｏｘ数は（Ｍ１  ＋１）（Ｍ２  ＋１）を下回らない。これにより、入れ子型ＳＰＮ構造のＤＰｆ、ＬＰｆの上限を抑えることが可能になる。
【００３７】
図２に、Ｍ１  ＝Ｍ２  ＝４の場合の例を示す。１５が後述する大ＭＤＳ行列による拡散部を示し、１１〜１４がその入力側の拡大Ｓ−ｂｏｘを示し、１６〜１９がその出力側の拡大Ｓ−ｂｏｘを示し、各々の拡大Ｓ−ｂｏｘ内において、２０が後述する小ＭＤＳによる拡散部を示し、図中で最も小さく示した矩形（２１，２２）が入力側および出力側のＳ−ｂｏｘを示す。
【００３８】
図２において、Ｓ−ｂｏｘのうちハッチングしたものは活性を表し（図中の２１参照）、白抜きで示したものは差分零を表す（図中の２２参照）。また、太線で示した拡大Ｓ−ｂｏｘ（１１，１３，１６，１７，１９）は活性を表し、その他の拡大Ｓ−ｂｏｘ（１２，１４，１８）は差分零を表す。４段で活性Ｓ−ｂｏｘが２５個以上であることが分かる。
【００３９】
このように、本例の暗号では、２段で５×５＝２５個以上の活性Ｓ−ｂｏｘ数を保証できる。Ｓ−ｂｏｘの最大差分確率は、
ｐｓ  ＝６／２５６、
２段での差分特性確率は、
ｐｓ  ２５＝２−１３５．４＜＜２−１２８、
となり、差分解読法が有効でないことが分かる。
【００４０】
同様に、線形特性確率についても、
ｑｓ  ＝２２／２５６、
ｑｓ  ２５＝２−８８．５  ＜＜２−６４  、
となり、線形解読法が有効でないことが分かる。
【００４１】
なお、従来のＳＱＵＡＲＥ／Ｒｉｊｎｄａｅｌ型暗号に適用されるＳＱＵＡＲＥ攻撃は、段内の１バイトに対して、他の入力を固定したまま、２８  通りのすべてのパターンを入力したとき、２段通過後の出力バイトの各々に対して２８  通りのすべてのパターンが出現する特性を利用するものであるが、本例の暗号では、例えば後述する大ＭＤＳの取り方によってＳ−ｂｏｘ間の攪拌性を向上させることで、その単純な適用を困難にしている。
【００４２】
以下では、入れ子型暗号方式の具体例を用いながら本実施形態についてより詳しく説明する。
【００４３】
本実施形態の具体例の構成について説明する。
【００４４】
図３に、本実施形態の入れ子型暗号方式のデータ攪拌部の階層構造の例を示す。
【００４５】
ブロック長は、１２８ビットを例にとる（もちろん、他のブロック長でも本発明は実施可能である）。
鍵長は、２５６ビットを例にとる（もちろん、他の鍵長でも本発明は実施可能である）。なお、本実施形態で、ブロック長を１２８ビットとしたときに、鍵長を１２８ビットや１９２ビットとした場合について後述する。
【００４６】
複数並列された拡大Ｓ−ｂｏｘと大ＭＤＳとの対（ただし、後述するように最終段は大ＭＤＳを含まない）を１段と数えるものとした場合に、段数をＲ段として表し、具体例を用いる場合にはＲ＝８を用いる。なお、基本的には段数は何段でも実施可能であるが、実際の段数は、例えば安全性や計算機資源等を想定して適宜設定することができ、好ましくは６段以上、より好ましくは８段以上とすると、より効果的である。
【００４７】
なお、本例の暗号では、段関数がＳ−ｂｏｘ層を２層含んでいるので、１段が通常の２段に相当する。段構造内の大ＭＤＳについては、異なるガロア体に基づくいくつかの実装を示す（強度優先や速度優先の例を挙げる）。
【００４８】
図４に、本実施形態に係る暗号化装置の構成例を示す。
【００４９】
１０１が各段であり、１０４は大ＭＤＳ拡散層、１０２は拡大Ｓ−ｂｏｘ層、１０３は各々の拡大Ｓ−ｂｏｘである。１０５は、排他的論理和部である。１２１〜１２４は、詳しくは後述する鍵スケジュール部の構成部分である。Ｐは入力となる１２８ビットの平文データ、Ｃは出力となる１２８ビットの暗号文データである。
【００５０】
段関数は、以下に述べるように、２段ＳＰＮ構造からなる３２ビット処理サブ・ブロック（拡大Ｓ−ｂｏｘ）１０３を４個並列に並べ、ＭＤＳ拡散層１０４で繋いだ構造である。全体の基本構造は、この段関数の繰り返しにする。
【００５１】
なお、図４の例では、暗号化と復号の処理を対称的にするため、最終段は拡大Ｓ−ｂｏｘ層１０２とその後の鍵加算１０５だけで構成することにしている。
【００５２】
段関数１段に２段ＳＰＮ構造が埋め込まれ、最後に鍵加算が行われるので、拡大鍵のビット長は、２×１２８×Ｒ＋１２８＝１２８（２Ｒ＋１）となる。Ｒ＝８の場合には、１２８×１７ビットとなる。
【００５３】
次に、Ｓ−ｂｏｘについて説明する。
【００５４】
本例の暗号では、入出力表で定義する８ビットＳ−ｂｏｘを利用する。
【００５５】
図５に、８ビットＳ−ｂｏｘの入出力表の一例を示す。図５において、配列要素は１６進数で表現してある。
【００５６】
図５の表は、最左上の値（７２）がｓ［０］に対応し、その１つ右の値（ＡＡ）がｓ［１］に対応し、その行の右端の値（９Ｆ）がｓ［１５］に対応し、次の行に移って、その左端の値（６９）がｓ［１６］に対応し、その１つ右の値（６Ａ）がｓ［１７］に対応し、以下同様の要領である。そして、最下右の値（５７）がｓ［２５５］に対応する。
【００５７】
図５に例示したＳ−ｂｏｘの特性は、次の通りである。
・最大差分確率：６／２５６（理論的最小値は４／２５６）
・最大線形確率：２２／２５６（理論的最小値は１６／２５６）
・代数次数：７次（全単射関数の最大値）
なお、Ｓ−ｂｏｘには、入出力表を用いる代わりに、演算処理を用いても良い。
【００５８】
次に、各々の拡大Ｓ−ｂｏｘ（または小構造とも呼ぶ）の部分について説明する。
【００５９】
図６に、拡大Ｓ−ｂｏｘ１０３の内部構成例を示す。この例では、４並列の８ビットＳ−ｂｏｘ１１２（図５参照）を２組用意し、拡散層１１３を挟んだ２段ＳＰＮ構造になっている。この構造は、ＳＰＳ構造と呼ぶべきものでもあるが、２段目の拡散層が省略された特殊な２段ＳＰＮ構造とみなす。Ｓ−ｂｏｘ１１２の入力直前では、必ず鍵加算１１１を行う。拡大Ｓ−ｂｏｘ内の拡散層１１３には、ＭＤＳ行列を使用し、これを小ＭＤＳと呼び、ＭＤＳＳと表記する。小ＭＤＳのブランチ数は５である。
【００６０】
図７に、本例の暗号で利用するＭＤＳＳ行列の一例を示す。図７において、行列要素は１６進数で表現してある。ここで、Ｓ−ｂｏｘ入出力と行列要素は、乗算の際、ガロア体ＧＦ（２８  ）の元とみなす。この例の場合の原始多項式は、ｘ８  ＋ｘ６  ＋ｘ５  ＋ｘ＋１である。
【００６１】
次に、本例の暗号の段関数である大構造について説明する。
【００６２】
図８に、１段の部分の構成例を示す。本例の暗号の段関数である大構造は、４並列の３２ビット拡大Ｓ−ｂｏｘ１０３（図６参照）をＭＤＳ行列の拡散層１０４で結合して構成する。この段関数である大構造における拡散層１０４にも、ＭＤＳ行列を使用し、これを大ＭＤＳと呼び、ＭＤＳＬと表記する。ただし、ここでのＭＤＳ行列とは、拡大Ｓ−ｂｏｘに着目したブランチ数が５であることを意味する。
【００６３】
大ＭＤＳの最も単純な構成は、拡大Ｓ−ｂｏｘの３２ビット幅の出力をＧＦ（２３２）の元として実現する方法である。この方法は高い強度が実現しやすいが、一般的な実行は困難もしくは高速化はしにくい。そこで、この場合には、大ＭＤＳ行列に制約を課すのが好ましい。
【００６４】
また、４並列のＭＤＳを構成するには、４ビット幅で十分であり、ＧＦ（２４  ）上の演算を利用して実現できる。さらに、ＭＤＳを巡回的なものにすることで、効率的な計算が可能になる。
【００６５】
また、実際には、これ以外のＧＦ（２８  ）やＧＦ（２１６）を利用する中間の型も可能である。
【００６６】
ＧＦ（２３２）を利用した大ＭＤＳについて説明する。
【００６７】
この場合、拡大Ｓ−ｂｏｘの入出力をＧＦ（２３２）の元とみなして、大構造ＭＤＳを設計する。これは、ＳＰＮ構造での自然な設計法である。しかし、３２ビット幅では乗算表による実装は現実的ではない。計算による場合も一般のＭＤＳ行列では計算量が掛かり高速化が困難である。計算量が増加する原因は、ガロア体上の乗算における桁上がり時の処理が重いためである。計算量を抑えるためには、大ＭＤＳ行列を、ビット表現で３２ビット中の下位５ビットにのみ１が現れる（下位５ビット以外は０のものに限定した）要素で構成する方法がある。このような条件を満たす行列を使用することで、桁上がり処理を上位４ビットを入力とする表引きで処理可能となる。
【００６８】
図９に、大ＭＤＳ行列の一例を示す。この例の場合の原始多項式は、ｘ３２＋ｘ２８＋ｘ２７＋ｘ＋１である。
【００６９】
ＧＦ（２４  ）を利用した大ＭＤＳについて説明する。
【００７０】
図１０に、この場合のＭＤＳ行列の一例を示す。この例の場合の原始多項式は、ｘ４  ＋ｘ＋１とする。
【００７１】
ここでは、１つの拡大Ｓ−ｂｏｘ１０３において４つのＳ−ｂｏｘの各々の出力すなわち８ビット・データの同じ位置（例えば図１０では最上位ビットを例にとって示している）の１ビットを集めて、これを１組４ビットのデータとし、４つの拡大Ｓ−ｂｏｘ１０３からの４組の４ビット・データを、ＧＦ（２４  ）の元とみなす。
【００７２】
そして、８ビット・データの同じ位置について、２段の４並列拡大Ｓ−ｂｏｘ層の間の拡散層１０４に４行４列のＭＤＳ行列（例えば図１０では最上位ビットの場合、１０４−１）を用いる。
【００７３】
出力となった４組の４ビット・データは、それぞれ対応するもとの８ビット・データの同じ位置に結線される。
【００７４】
Ｓ−ｂｏｘのビット幅に対応して、８個のＭＤＳ行列（１０４−１〜１０４−８）を用意して、大ＭＤＳとする。
【００７５】
これらの４行４列のＭＤＳ行列は、それぞれ、ブランチ数５を保証する。各ＭＤＳ行列は、Ｓ−ｂｏｘ中の異なるビット位置に接続するので、全体としてもブランチ数５を保証する。
【００７６】
各拡大Ｓ−ｂｏｘの同じ位置のＳ−ｂｏｘ出力を単位とした表引きによって（なお、演算によってもよい）、８個のＭＤＳ行列を同時に処理する効率的な実行が可能である。
【００７７】
さらに、ＭＤＳ行列が巡回的な場合、３２ビットごとの排他的論理和と８ビット単位のビット回転を組み合わせた効率的な処理が可能となる。
【００７８】
なお、上記と同様の考え方により、８ビット・データのうちの同じ位置の２ビットごとに処理を行うこととして、各要素が８ビットの４行４列のＭＤＳ行列（ＧＦ（２８  ））を、４個用意して、大ＭＤＳとすることも可能である。また、８ビット・データのうちの同じ位置の４ビットごとに処理を行うこととして、各要素が１６ビットの４行４列のＭＤＳ行列（ＧＦ（２１６））を、２個用意して、大ＭＤＳとすることも可能である。
【００７９】
なお、図４では、拡大Ｓ−ｂｏｘを４並列で表しているが、これに限定されるものではなく、それ以外の並列数も可能である。
また、拡大Ｓ−ｂｏｘの内部構成を、全て同一とせずに、異なるものを混在させることも可能である。
また、全ての大ＭＤＳ行列を同一にせずに、異なるものを混在させることも可能である。この点は、小ＭＤＳ行列、Ｓ−ｂｏｘの入出力表についても同様である。
また、例えば、最初の入力段と、最後の出力段だけ、他の中間段とは異なる内部構成にしてもよい。
この他にも、種々のバリエーションが考えられる。
【００８０】
次に、鍵スケジュール部（鍵生成部）について説明する。
【００８１】
図１１に、鍵スケジュール部の構成例を示す。１２１は、データ攪拌部の段関数の１段分に対応する部分であり、１３１は線形拡散層（本例では、大ＭＤＳによる拡散層とする）であり、１３２は非線形変換層（本例では、４並列のＳＰ層（Ｓ−ｂｏｘ層・拡散層）１３３とする）であり、１３４は排他的論理和部であり、１３５は剰余加算部である。図１１では省略しているが、１２１の部分の構成が必要に応じて繰り返されることになる。なお、１２８ビットの鍵を出力する構成単位を鍵スケジュール部の１つの段とすると、鍵スケジュール部の段数は（２Ｒ＋１）段となる（Ｒ＝８の場合、１７段である）。
【００８２】
図１１の例では、２５６ビットの変形Ｆｅｉｓｔｅｌ型繰り返し処理の各段の出力左半分１２８ビットを取り出し、段数依存定数Ｃｉ  を剰余加算して拡大鍵とする。
【００８３】
なお、鍵長を２５６ビットとする場合には、例えば、上位１２８ビットを初段の線形拡散層１３１に与え、下位１２８ビットを非線形変換層１３２に与えればよい。また、鍵長を１２８ビットとする場合には、例えば、その１２８ビットを初段の線形拡散層１３１に与えるとともに、非線形変換層１３２に与えればよい。また、鍵長を１９２ビットとする場合には、例えば、上位１２８ビットを初段の線形拡散層１３１に与え、下位側６４ビットと上位側６４ビットとを結合した１２８ビットを非線形変換層１３２に与えればよい。
【００８４】
なお、図１２のように、段数依存定数Ｃｉ  を剰余加算する箇所について、種々のバリエーションが考えられる。
【００８５】
図１３に、図１１や図１２における非線形変換層１３２の各々の非線形変換層１３３の構成例を示す。１４１はＳ−ｂｏｘであり、１４２は４並列のＳ−ｂｏｘを入力とする小ＭＤＳである。
【００８６】
なお、このＳ−ｂｏｘは、図４の暗号処理側のＳ−ｂｏｘと同じものでもよいし、異なるものでもよい。小ＭＤＳについても同様である。また、鍵スケジュール部の各段によってＳ−ｂｏｘや小ＭＤＳの構成を変えることも可能である。
【００８７】
図１４に、図１１や図１２における非線形変換層１３２の各々の非線形変換層１３３の他の構成例を示す。この例は、図１３の構成に対して、排他的論理和部１４３を付加したものである。
【００８８】
さらに、図１４において、Ｓ−ｂｏｘに対する入力と排他的論理和をとる定数を、段数依存定数とする構成も可能である。
【００８９】
次に、各段で異なる定数Ｃｉ  を作る方法の一例について説明する。
【００９０】
図１１や図１２の鍵スケジュール部の１２８ビットの加算定数Ｃｉ  は、４つのビット定数（Ｈ０  ，Ｈ１  ，Ｈ２  ，Ｈ３  ）の組み合わせで記述することができる。３２ビットの定数Ｈｉ  の一例を次に示す。
Ｈ０  ＝（５ａ８２７９９９）Ｈ＝２１／２  ／４
Ｈ１  ＝（６ｅｄ９ｅｂａ１）Ｈ＝３１／２  ／４
Ｈ２  ＝（８ｆ１ｂｂｃｄｃ）Ｈ＝５１／２  ／４
Ｈ３  ＝（ｃａ６２ｃ１ｄ６）Ｈ＝１０１／２  ／４
加算定数Ｃｉ  の組み合わせを、Ｃｉ  ＝（Ｃｉ０，Ｃｉ１，Ｃｉ２，Ｃｉ３）と記述する。各段で異なる１２８ビットの定数Ｃｉ  を容易に生成するため、Ｃｉ  を構成するＨｉ  の組み合わせの決定に８ビットＬＦＳＲを用いる。例えば、ＬＦＳＲの原始多項式には（１Ｄ）Ｈ  を、ＬＦＳＲの初期状態には（８Ｂ）Ｈ  を用いる。このＬＦＳＲを用いて生成されたビット列を２ビットづつ読み出し、定数として使用する３２ビット定数Ｈｉ  を決定する。
【００９１】
図１５に、上記のような方法によりＬＦＳＲを用いて決定した加算定数表の例を示す。
【００９２】
なお、ＬＦＳＲの初期状態は、可変としてもよいし、固定としてもよい。前者の場合には、ＬＦＳＲの初期状態も鍵の一部を構成することになる。後者の場合には、暗号側と同じＬＦＳＲの初期状態を持つ復号側のみ、暗号文を復号することができる。
【００９３】
以上説明したような鍵スケジュール部によれば、非線形変換層については、入力の１ビットが変化すると、Ｓ−ｂｏｘ（１４１）により、８ビットに変化を波及させ、さらに、小ＭＤＳ（１４２）により、３２ビットに変化を波及させることができる。さらにまた、線形拡散層については、大ＭＤＳ（１３１）が前段の非線形変換層の出力をより大きく攪拌するので、１ビットの違いも、１２８ビットの幅に広がる利点がある。
【００９４】
従って、このような鍵スケジュール部によれば、各段でバラバラな鍵が出やすい、攪拌しやすい、という効果を得ることができる。また、段ごとに異なる定数により、段にわたる鍵の一致が少ない（鍵がほぼ一致しない）、という効果を得ることができる。
【００９５】
さて、以下では、大きなブロック長を持つブロック暗号のデータの攪拌部に用いられる効率的な線形拡散装置について説明する。
【００９６】
図１６に、本実施形態の線形拡散装置の基本的な構成要素である有限体乗算装置の構成例を示す。前述したＧＦ（２３２）あるいはＧＦ（２１６）を利用した大ＭＤＳ（図９、図４の１０４、図１１や図１２の１３１参照）における、１つの入力と大ＭＤＳ行列の１つの要素との積の計算に、この線形拡散装置を用いることができる。
【００９７】
図１６に示されるように、この有限体乗算装置は、係数格納部２０２、乗算部２０３、桁溢れ帰還部２０１、排他的論理和部（排他和部）２０４を用いて構成される。
【００９８】
係数格納部２０２は、係数すなわち乗算の乗数（例えば、図９の大ＭＤＳ行列の１つの要素）を格納する部分である。
【００９９】
乗算部２０３は、入力ワードと係数を２進数とみなした場合の乗算を行う部分である。
【０１００】
桁溢れ帰還部２０１は、乗算の結果として生ずる桁溢れを有限体上の乗算に戻すため排他的論理和部２０４で足される数（帰還ワード）を検索する部分である。
【０１０１】
排他的論理和部２０４は、乗算部２０３の出力と桁溢れ帰還部２０１の出力ビット的な排他和を行う部分である。
【０１０２】
有限体乗算装置２００の機能は、有限体ＧＦ（２）の拡大体ＧＦ（２ｋ  ）の元である入力ワードａと同じ有限体の別の元である係数ｂの積ａ×ｂを出力ワードとして計算することである。
【０１０３】
まず、有限体における積について説明する。
【０１０４】
なお、以下の記述において、Σａｉ  ｘｉ  において総和を取るｉの範囲やΣｂｊ  ｘｊ  において総和を取るｊの範囲を０〜ｋ−１とし、それらの範囲についての記述を省略する。
【０１０５】
ＧＦ（２ｋ  ）の元は、多項式表現によって、ある変数ｘの（ｋ−１）次の多項式Σａｉ  ｘｉ  として表現できる。元ａを表現するのに、その係数を並べてｃｋ−１  ｃｋ−２  …ｃ０  として表現することもある。
【０１０６】
２つの元ａ＝Σａｉ  ｘｉ  とｂ＝Σｂｉ  ｘｉ  の積は、
ａ×ｂ＝（Σａｉ  ｘｉ  ）×（Σｂｉ  ｘｉ  ）  ｍｏｄ  ｐ（ｘ）
で定義される。
【０１０７】
ここで、ｐ（ｘ）はＧＦ（２ｋ  ）の原始多項式と呼ばれ、周期（２ｋ  −１）を持つｋ次の既約なモニック多項式である。また、ｍｏｄの意味は、例えば、ｋ＝３２の場合、原始多項式としてｐ（ｘ）＝ｘ３２＋ｘ２８＋ｘ２７＋ｘ＋１を選んだ場合、多項式の積によってｘ３２の項や因子が現れた場合には、それを（ｘ２８＋ｘ２７＋ｘ＋１）と見なすということを表す。従って、積もまたｋ次未満の多項式となる。
【０１０８】
一般に、このような操作を行う場合、高速な処理を行うため、乗数と被乗数をタグとして積を検索する乗算表を用いた乗算装置を用いることがある。しかし、乗数と被乗数はともに２ｋ  個の値を取り得るので、乗算表は、２２ｋ個のエントリを持ち、各エントリはｋビットのサイズを持つので、ｋがある程度大きくなると、乗算表のサイズは非常に大きなものとなる。
【０１０９】
本実施形態も、基本的には、乗算表を用いる方式に類似するが、係数がある制約条件を満足する場合には、はるかに小さな記憶容量によって実現することができる。
【０１１０】
その制約条件とは、係数ｂは、定数であって、非零の係数を持つのは、ある次数ｔ以下の下位の係数のみであるということである（ｔ次を越える次数の係数は０であり、ｔ次以下の係数は０または１である）。ある元ａが任意の元を取る場合には、桁溢れは、最大３２ビットであるが、この制約条件を満足する場合には、桁溢れは、高々、ｔビットである。このｔビットの桁溢れの値を決定するのは、被乗数ａの上位ｔビットまでのＭＳＢ（Ｍｏｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔｓ）である。
【０１１１】
有限体上の乗算と通常の多項式と見なした場合の乗算との違いは、２進数の積の結果、３２次以上の係数への桁溢れが起こった場合に、原始多項式によって、３２次未満の係数へその寄与を還元する必要があるが、本実施形態では、桁溢れ帰還部２０１が、還元すべきワードを表として持っている。
【０１１２】
この帰還ワードは、高々（ｔ＋１）ビットの係数ｂと乗数ａの上位ｔビットと原始多項式から決定できる。つまり、（ａ［（ｋ−ｔ）．．．（ｋ−１）］×ｂ）［（ｔ＋１）．．．２ｔ］  ｍｏｄ  ｐ（ｘ）によって与えられる。ここで、ａ［（ｋ−ｔ）．．．（ｋ−１）］とは、ａの中から、（ｋ−１）次から（ｋ−ｔ）次までの項を取り出したものである。
【０１１３】
すなわち、桁溢れ帰還部２０１が持つ帰還ワードの表の内容は、対応するＭＤＳ行列（図９参照）の要素に応じて決まる。
【０１１４】
桁溢れ帰還部２０１が持つ帰還ワードの表は、２ｔ  個のエントリからなり、各エントリはｋビットのサイズを持つ。
【０１１５】
次に、上述した有限体乗算装置を利用することで実現される、ブロック暗号のデータ・ブロックに線形変換を施す線形変換装置について説明する。
【０１１６】
線形変換の１種にＭＤＳ行列による線形変換がある。ＭＤＳ行列とは、データ・ブロックが、複数（ｎ）のワードから構成され、各ワードがｋビットの長さを持つ場合、各ワードを有限体ＧＦ（２ｋ  ）の元と見なし、ｎ個の元の組をｎ個の元の組に線形写像するｎ行ｎ列の行列であって、すべての小行列が非零のものである。ＭＤＳ行列による線形変換は、非零の入出力のワードの数の下限が保証されているという性質を持つ。
【０１１７】
しかし、一般に、有限体ＧＦ（２ｋ  ）上の行列演算は、ＧＦ（２ｋ  ）上の複数回の乗算と加算から構成され、計算コストが大きい。
【０１１８】
図１７に、本実施形態の線形変換装置の構成例を示す。前述したＧＦ（２３２）あるいはＧＦ（２１６）を利用した大ＭＤＳ（図９、図４の１０４、図１１や図１２の１３１）に、この線形変換装置を用いることができる。
【０１１９】
図１７の構成では、まず、図１６の有限体乗算装置をＭＤＳ行列に対応してマトリクス状に用意する。
【０１２０】
図１７においてｍ＝ｎとすると、ｎ２  個の有限体乗算装置２００の各々の係数は、ｎ行ｎ列のＭＤＳ行列の対応する要素と同じ値をとる。係数ａｉｊを持つ装置には、第ｉ入力ワードが入力される。
【０１２１】
各々の出力ワードに対する排他的論理和部（排他和部）２０５は、それぞれ、あるｊに対応する係数ａｉｊを持つすべての有限体乗算装置２００の出力ビット的な排他的論理和を計算し、第ｊ出力ワードとして出力する。
【０１２２】
本実施形態における線形変換装置は、線形変換を表現するＭＤＳ行列を（ａｉｊ）で表現するとき、各要素ａｉｊは高々ｔ次までの項しか非零の係数を持たないことを特徴とする。ここで、ｉ，ｊは、０からｎ−１までの整数値を取りうるとする。また、ｔは、有限体ＧＦ（２ｋ  ）の拡大次数ｋよりも小さな正数であるとする。
【０１２３】
これによって、図１８のような乗算が実現できる。
【０１２４】
なお、桁溢れ帰還部２０１が持つ帰還ワードの表の内容は、対応するＭＤＳ行列の要素に応じて決まるので、例えば、図９の大ＭＤＳ行列の例では、４種類の帰還ワード表だけ持てばよいことになる。
【０１２５】
次に、本暗号方式に用いるＭＤＳ行列（特に大ＭＤＳ）を生成するためのＭＤＳ行列生成装置（もしくはランダム生成アルゴリズム）について説明する。
【０１２６】
図１９に、ＭＤＳ行列生成装置の構成例を示す。図１９に示されるように、このＭＤＳ行列生成装置は、要素生成部２３１、小行列式計算部２３２、判定部２３３を用いて構成される。
【０１２７】
図２０に、この場合の手順の一例を示す。
【０１２８】
要素生成部２３１は、ランダムに、ｎ行ｎ列のＭＤＳ行列の各行列要素を生成する（ステップＳ１）。なお、先の有限体乗算装置を適用可能とする場合には、このときに、下位ｔビットのみ非零の要素（ｔ次以下の要素）からなるＭＤＳ行列を生成しておく（すなわち、この場合には、要素生成部２３１内で、下位ｔビットのみ非零かどうかのチェックを行うことになる）。
【０１２９】
なお、行列要素を生成するためには、乱数を発生して用いる方法や、多重ループの制御変数の値を用いる方法など種々の方法が考えられる。
【０１３０】
次に、小行列式計算部２３２は、要素生成部２３１の生成した行列の１次小行列を計算し（ステップＳ２）、判定部２３３は、小行列式計算部２３２が計算した小行列が非零か否かを判定する（ステップＳ３）。１つでも零の１次小行列式があれば、ステップＳ１からやり直す。
【０１３１】
すべての１次小行列式が非零ならば、同じ要領で、２次小行列について同様にチェックする（ステップＳ４，Ｓ５）。
【０１３２】
以上を、ｎ次小行列式まで、同じ要領で行い（ステップＳ６，Ｓ７）、１次からｎ次まですべての小行列式が非零であることが確認されたならば、そのＭＤＳ行列を出力する（ステップＳ８）。
【０１３３】
なお、ステップＳ８で得たＭＤＳ行列を暗号化に用いるＭＤＳ行列とした場合、復号に用いるＭＤＳ行列は、ステップＳ８で得たＭＤＳ行列の逆行列によって与えられる（逆に、ステップＳ８で得たＭＤＳ行列を復号に用いる場合には、その逆行列が、暗号化に用いるＭＤＳ行列となる）。
【０１３４】
ただし、ステップＳ８で得られたＭＤＳ行列の全ての要素が下位ｔビットのみ非零であっても、その逆行列の全ての要素が下位ｔビットのみ非零であるとは限らない。
【０１３５】
なお、図２０の手順おいて、小行列式の判定を１次からｎ次まで順番に行っているが、他の順番でもよく、また、それらの全部または一部を並列して行ってもよい。
【０１３６】
次に、暗号化に用いるＭＤＳ行列と、その逆行列である、復号に用いるＭＤＳ行列との両方とも、下位ｔビットのみ非零という条件を満たすように、ＭＤＳ行列を求める方法について説明する。
【０１３７】
図２１に、この場合のＭＤＳ行列生成装置の構成例を示す。図２１に示されるように、このＭＤＳ行列生成装置は、要素生成部２３１、小行列式計算部２３２、判定部２３３、逆行列生成部２３４、逆行列判定部２３５を用いて構成される。要素生成部２３１、小行列式計算部２３２、判定部２３３の部分は、図１９と同様である。
【０１３８】
図２２に、この場合の手順の一例を示す。
【０１３９】
まず、先の例と同様にして、要素生成部２３１、小行列式計算部２３２、判定部２３３により、下位ｔビットのみ非零の要素からなるＭＤＳ行列を生成する（ステップＳ１１）。
【０１４０】
次に、逆行列生成部２３４により、生成されたＭＤＳ行列の逆行列を求める（ステップＳ１２）。
【０１４１】
次に、逆行列判定部２３５は、求められた逆行列の各々の要素が、下位ｔビットのみ非零かどうか調べる。
【０１４２】
全ての要素が下位ｔビットのみ非零であれば（ステップＳ１３）、そのＭＤＳ行列および逆行列を出力する（ステップＳ１４）。
【０１４３】
１つでも下位ｔビットのみ非零ではない要素があれば（ステップＳ１３）、Ｓ１１からやり直す。
【０１４４】
なお、ステップＳ１１で生成されたＭＤＳ行列を暗号化に用いる場合、ステップＳ１２で生成された逆行列を復号に用いることになる（逆に、ステップＳ１１で生成されたＭＤＳ行列を復号に用いる場合、ステップＳ１２で生成された逆行列を暗号化に用いることになる）。
【０１４５】
なお、ＭＤＳ行列を生成するにあたっては、同一行内に同じ値の要素が存在しないようなＭＤＳ行列（ｎ行ｎ列のＭＤＳ行列において第ｉ１要素から第ｉｎ要素までの中に同一の値を持つ２個以上の要素がないもの）を生成するようにしてもよい。例えば、図２０や図２２の手順例の場合、ＭＤＳ行列の生成時に、同一行内に同じ値の要素が存在するかどうかチェックし、同一行内に１つでも同じ値の要素が存在すれば、ＭＤＳ行列を生成し直すようにすればよい。なお、同一列内に同じ値の要素が存在しても構わない。
【０１４６】
ブロック暗号のデータの線形変換装置として、同一行内に同じ値の要素が存在しないようなＭＤＳ行列を選択した線形変換装置を用いることによって、入力ワードの差分値が相殺する確率を小さくすることができる。
【０１４７】
また、同一行内の要素の和が１または０にならないようにＭＤＳ行列を生成するようにしてもよい。この場合も、同様の効果が得られる。
【０１４８】
次に、Ｓ−ｂｏｘと小ＭＤＳの組み合わせを選択する（あるいは最適化する）ことによって、より安全性を高める方法、より具体的には、最大差分特性確率が理論的最悪例よりも良くなることを保証するＳ−ｂｏｘとＭＤＳの組み合わせの設計方法について説明する。
【０１４９】
ＭＤＳはブランチ数Ｂしか保証しないので、Ｓ−ｂｏｘの最大差分確率がｐとすると、最大差分特性確率は、ｐＢ  になる。例えば、ｍ行ｍ列のＭＤＳはＢ＝ｍ＋１となる。しかし、Ｓ−ｂｏｘと小ＭＤＳの組み合わせを選択する（あるいは最適化する）ことにより、ブランチ数Ｂで、最大差分特性確率がｐＢ  未満を保証することができる。この結果、通常のＭＤＳよりも最大差分確率が小さいＭＤＳとＳ−ｂｏｘを組み合わせることにより、相乗効果が望め、安全性をより向上させることができる。
【０１５０】
さて、暗号アルゴリズムの安全性評価の一手法として、差分解読法あるいは線形解読法があり、両者は双対な関係にある。差分解読法に着目すると、Ｓ−ｂｏｘの安全性は入出力の差分相関を持つ確率で規定され、この確率が小さいほど安全性が高い。暗号アルゴリズムでは、差分確率の小さいＳ−ｂｏｘが多数組み合わせられるほど安全性が向上する。効率的なＳ−ｂｏｘの連結方法として、線形変換装置が従来から提案されている。線形変換装置は、あるブロック長のデータに対して線形変換を施す装置で、暗号化装置（や復号装置）の構成要素として利用されることがある。線形変換の一種にＭＤＳ行列による線形変換がある。
【０１５１】
ＭＤＳ行列とは、データブロックがｎ個の複数のワードから構成される場合、ｎ個のワードへの線形変換を定義する行列であり、非零の入出力ワードはｎ＋１個以上が保証されているという性質を持つ。しかし、Ｓ−ｂｏｘは、差分確率として、６／２５６、４／２５６、２／２５６など複数の値の候補を持つため、ＭＤＳであっても、ｎ＋１個の確率がそれぞれ６／２５６のＭＤＳと、それぞれ４／２５６であるＭＤＳとでは、後者の方が安全性が高い。
【０１５２】
従来、Ｓ−ｂｏｘとＭＤＳは単体の構成要素としてそれぞれ独立に安全性を評価されたが、ここでは、Ｓ−ｂｏｘとＭＤＳの相乗効果を検証する装置の例を示す。
【０１５３】
図２３に、この場合の処理手順の一例を示す。この例は、差分解読法に着目して、Ｓ−ｂｏｘとの相乗効果が望めるＭＤＳ決定処理を示している。差分解読法と線形解読法は双対な関係にあるため、この処理を線形確率に着目して行うことにより、線形解読法に対しても同じ効果が得られる。
【０１５４】
まず、複数のＳ−ｂｏｘの候補と複数の小ＭＤＳの候補を生成する（ステップＳ２１、ステップＳ２２）。なお、ステップＳ２１とステップＳ２２は逆の順番で行ってもよいし、並列して行ってもよい。
【０１５５】
次に、Ｓ−ｂｏｘ候補のなかからＳ−ｂｏｘを１つ選択するとともに（ステップＳ２３）、小ＭＤＳ候補のなかから小ＭＤＳを１つ選択する（ステップＳ２４）。なお、ステップＳ２３とステップＳ２４を逆の順番で行ってもよいし、並列して行ってもよい。
【０１５６】
次に、後述するように、有効な（活性にした）Ｓ−ｂｏｘの差分値の最大を計算し（ステップＳ２５）、上限（例えば、６／２５６）を下回る差分値（例えば、４／２５６）が含まれているかどうか調べる。
【０１５７】
そして、含まれていれば（ステップＳ２６）、そのときのＳ−ｂｏｘと小ＭＤＳの組み合わせを出力する（ステップＳ２７）。
【０１５８】
一方、含まれていなければ（ステップＳ２６）、Ｓ−ｂｏｘと小ＭＤＳの一方または両方を選択し直して、以下、同様に、処理を繰り返す。
【０１５９】
なお、図２３では、最初に複数のＳ−ｂｏｘの候補と複数の小ＭＤＳの候補を生成しておいたが、その代わりに、最初の１組以外は、ステップＳ２６で条件を満たさずに、他のＳ−ｂｏｘおよびまたはＭＤＳを選択することになったときに、生成するようにしてもよい。
【０１６０】
ステップＳ２５およびステップＳ２６の処理は、実際には、次のようになる。
【０１６１】
例えば、図６の例の場合、Ｓ−ｂｏｘと小ＭＤＳの組について、次の４種類、計２０通りの検証を行い、すべての条件を満たした場合に、ステップＳ２７でそのときのＳ−ｂｏｘと小ＭＤＳの組が出力される。
▲１▼小ＭＤＳ１１３の入力側の１つのＳ−ｂｏｘ１１２のみ活性にした場合に、小ＭＤＳ１１３の出力側の４つのＳ−ｂｏｘ１１２が全て活性になり、かつ、そのうちの１つでも上限を下回る差分値になれば、この検証を合格とする。この検証を、入力側の４つのＳ−ｂｏｘ１１２の各々について行う（４通りある）。
▲２▼小ＭＤＳ１１３の入力側の２つのＳ−ｂｏｘ１１２のみ活性にした場合に、小ＭＤＳ１１３の出力側の４つのＳ−ｂｏｘ１１２が全て活性になれば、この検証を合格とし、小ＭＤＳ１１３の出力側の３つのＳ−ｂｏｘ１１２が活性になり、かつ、そのうちの１つでも上限を下回る差分値になれば、この検証を合格とする。この検証を、入力側の２つのＳ−ｂｏｘ１１２の組み合わせの各々について行う（６通りある）。
▲３▼小ＭＤＳ１１３の出力側の２つのＳ−ｂｏｘ１１２のみ活性にした場合に、小ＭＤＳ１１３の入力側の４つのＳ−ｂｏｘ１１２が全て活性になれば、この検証を合格とし、小ＭＤＳ１１３の入力側の３つのＳ−ｂｏｘ１１２が活性になり、かつ、そのうちの１つでも上限を下回る差分値になれば、この検証を合格とする。この検証を、出力側の２つのＳ−ｂｏｘ１１２の組み合わせの各々について行う（６通りある）。
▲４▼小ＭＤＳ１１３の出力側の１つのＳ−ｂｏｘ１１２のみ活性にした場合に、小ＭＤＳ１１３の入力側の４つのＳ−ｂｏｘ１１２が全て活性になり、かつ、そのうちの１つでも上限を下回る差分値になれば、この検証を合格とする。この検証を、出力側の４つのＳ−ｂｏｘ１１２の各々について行う（４通りある）。
【０１６２】
上記の複数の検証処理は、逐次行ってもよいし、全部または一部を並列的に行ってもよい。上記の複数の検証処理のうち、１つでも合格しないものがあれば、そのＳ−ｂｏｘと小ＭＤＳの組み合わせについては、以降の全ての検証処理をうち切って、不合格として構わない。
【０１６３】
なお、図２３の手順の例では、最初に条件を満たしたＳ−ｂｏｘと小ＭＤＳの組み合わせが得られた時点で、処理をうち切るものであったが、条件を満たしたＳ−ｂｏｘと小ＭＤＳの組み合わせを複数求め、それらのうちで最も良いと評価されるものを選択するようにしてもよい。
【０１６４】
以下では、復号側について説明する。
【０１６５】
復号側は、基本的には、暗号側を逆にした構造である（鍵は同一である）。
【０１６６】
図２４に、図４の暗号化装置に対応する復号装置の構成例を示す。
【０１６７】
図２５に、図６の小構造に対応する構成例を示す。
【０１６８】
図２６に、図８の大構造に対応する構成例を示す。
【０１６９】
なお、図２４では、復号装置の鍵スケジュール部は、図４の暗号化装置の鍵スケジュール部と同一の構成としてある。
【０１７０】
復号装置における、Ｓ−ｂｏｘ１１１２の入出力表、小ＭＤＳ１１１３の小ＭＤＳ行列、大ＭＤＳ１１０４の大ＭＤＳ行列は、それぞれ、暗号化装置における、Ｓ−ｂｏｘ１１２の入出力表（例えば図５）、小ＭＤＳ１１３の小ＭＤＳ行列（例えば図７）、大ＭＤＳ１０４の大ＭＤＳ行列（例えば、図９、図１０）と逆関数（逆行列）の関係になっている。
【０１７１】
なお、図２４では、鍵については、図４と同様の順番で生成しているが、図４とは逆の順番で生成するように構成することも可能である。
【０１７２】
図２７に、この場合の鍵スケジュール部の構成例を示す。
【０１７３】
１１３２は、図１１の非線形変換層１３２の逆変換を示している（例えば各々のＳＰ層１３３の逆変換（例えば図１３あるいは図１４の入出力を逆方向にしたもの）を４並列にしたものである）。
【０１７４】
図２７の鍵スケジュール部で用いる、Ｓ−ｂｏｘの入出力表、小ＭＤＳ行列、大ＭＤＳ行列は、そ  れぞれ、図１１の鍵スケジュール部で用いる、Ｓ−ｂｏｘの入出力表、小ＭＤＳ行列、大ＭＤＳ行列と逆関数（逆行列）の関係になっている。
【０１７５】
また、図２７の復号の鍵入力Ｋ’は、図４において（暗号側で）最後の鍵加算に用いられた鍵とする。
【０１７６】
なお、この場合においても、段数依存定数Ｃｉ  を剰余加算する箇所について、図１２の場合と同様の方法をはじめとして、種々のバリエーションが考えられる。
【０１７７】
以下では、大ＭＤＳの好ましい一形態について説明する。
【０１７８】
入れ子型（再帰的）ＳＰＮ型暗号のＳＱＵＡＲＥ攻撃に対する安全性がＳＱＵＡＲＥ暗号／Ｒｉｊｎｄａｅｌ暗号より改善する一つの理由として、Ｓ−ｂｏｘ間（前段の拡大Ｓ−ｂｏｘの後半（あるいは最終段）のＳ−ｂｏｘと後段の拡大Ｓ−ｂｏｘの前半（あるいは初段）のＳ−ｂｏｘとの間）に設けた大ＭＤＳ拡散層による攪拌性があげられるが、ここでは、ＳＱＵＡＲＥ攻撃に対する耐性をより効果的なものにするための大ＭＤＳの構成についての選択基準の例を示す。
【０１７９】
ところで、通常、ＳＰＮ型暗号に対するＳＱＵＡＲＥ攻撃では、
▲１▼可変ｂｙｔｅは全２５６パターンを取る、
▲２▼他のｂｙｔｅは固定、
という条件を満たす２５６パターン（Λ集合）を入力し、そして、２５６パターンに対するビット和が０になる鍵を探索することによって、鍵を推定する、という手順が取られる。
【０１８０】
これを背景として、大ＭＤＳの結合（大ＭＤＳの入力側と出力側のビット間の結合関係あるいは演算経路の配線関係）に一定の条件を加えることによって、ＳＱＵＡＲＥ攻撃に対する安全性を向上させる。この一定の条件とは、概略的には、差分経路（前段の拡大Ｓ−ｂｏｘの前半のＳ−ｂｏｘと後段の拡大Ｓ−ｂｏｘの前半のＳ−ｂｏｘとの間の演算経路）の全部または一部を複線化させる（ファン・イン（ｆａｎ−ｉｎ）を２以上にする）というものである。これによって、高いなだれ効果が得られ、従来に比較してＳＱＵＡＲＥ攻撃可能な段数を１段減らせることにができる。
【０１８１】
まず、図２８〜図３５（各図においてデータは上側から下側へ流れるものとしている）を参照しながら、大ＭＤＳの一構成例を示す。この例は、全ての差分経路についてファン・インを２以上にするように、大ＭＤＳを構成した例である。
【０１８２】
なお、ここで説明する大ＭＤＳも、ハードウェア（例えば半導体基板上等に形成した実回路）によっても、機能的に等価な行列演算または入出力変換表による変換を実行するためのソフトウェアによっても実現可能であるが、図２８〜図３５ではハードウェアによって実現する場合を想定して説明する。
【０１８３】
図２８に、図４の暗号システムや図２４の復号システムにおける大ＭＤＳ層（暗号側の場合は１０４−１〜１０４−８で、復号側の場合は１１０４−１〜１１０４−８）と、その前段および後段の４並列の拡大Ｓ−ｂｏｘ（暗号側の場合は１０３で、復号側の場合は１１０３）、そして拡大Ｓ−ｂｏｘを構成する４並列のＳ−ｂｏｘおよび小ＭＤＳを示す。ただし、図６等に示したような鍵加算は図２８以降の各図ではその記述を省略している。
【０１８４】
さて、図２８の例は、図１０と同様に、各Ｓ−ｂｏｘの８ビットのうちの１ビットを抜き出したものについてそれぞれ独立に同一処理を行う構成を取っている。図２８は、各Ｓ−ｂｏｘの８ビットのうちの最も左側の１ビットを抜き出したもの（１６ビットデータあるいは４組の４ビットデータ）について処理を行うＭＤＳ部分１０４−１について説明している。なお、図２９では、各Ｓ−ｂｏｘの８ビットのうちの最も右側の１ビットを抜き出したものについて処理を行うＭＤＳ部分１０４−８について説明している。また、図示はしていないが他の６ビットの各々についても同様である。
【０１８５】
図２８以降の各図で示す配線やレイアウトは論理的な関係を示すものであり、実配線や実レイアウトにはもちろん設計の自由度がある。また、図２８の例では、大ＭＤＳ層の各部分１０４−１〜１０４−８の８つを実装するものとしているが、ＭＤＳ部分１０４−１〜１０４−８のうちの一部（例えば、１つ、２つ、あるいは４つ）のみを実装し、それを時分割的に共用するように構成することも可能である。
【０１８６】
なお、暗号側と復号側で構成の仕方は同様であるので（逆変換の関係になるだけである）、以下では、暗号側を例にとって説明する。また、大ＭＤＳ層の各部分１０４−１〜１０４−８は同一構成として、そのうちの１つの部分（１０４−１とする）について説明する。
【０１８７】
図３０に、大ＭＤＳ層の一つの部分（以下、単に大ＭＤＳと呼ぶ）１０４−１の前段の第１の拡大Ｓ−ｂｏｘ１０３−１−１の後半の４つのＳ−ｂｏｘと、大ＭＤＳの後段の４つの拡大Ｓ−ｂｏｘ１０３−２−１〜１０３−２−４の前半における合計１６のＳ−ｂｏｘとの間の結合関係の一例を示す。なお、図３０〜図３４において、ビットの配線が合流するところでは、排他的論理和によってそれら複数ビットが結合される（各図では、排他的論理和回路の記述を省略している）。
図３１に、大ＭＤＳの前段の第２の拡大Ｓ−ｂｏｘ１０３−１−２について、図３０と同様の関係を示す。
図３２に、大ＭＤＳの前段の第３の拡大Ｓ−ｂｏｘ１０３−１−３について、図３０と同様の関係を示す。
図３３に、大ＭＤＳの前段の第４の拡大Ｓ−ｂｏｘ１０３−１−４について、図３０と同様の関係を示す。
図３０〜図３３を参照すると、大ＭＤＳの後段の拡大Ｓ−ｂｏｘの同一のＳ−ｂｏｘには、いずれについても、それぞれ図３０〜図３３のようにして排他的論理和により結合された４つのビットが結合されるが、それら４つのビットについても排他的論理和によって接合される。この様子を、大ＭＤＳの後段の第１の拡大Ｓ−ｂｏｘ１０３−２−１について、図３４に示す。大ＭＤＳの後段の他の拡大Ｓ−ｂｏｘ１０３−２−２〜１０３−２−４については図示を省略するが、同様の結合関係である。なお、ここでは図３０〜図３３のような排他的論理和による結合の後に図３４のような排他的論理和による結合を行ったように示しているが、それらすべての排他的論理和による結合を一括して行ってもよいし、適宜複数に分けて行ってもよい。
【０１８８】
さて、以上に例示した構成は、次の基準に基づいている。
【０１８９】
図４のような暗号回路において連続する２段（すなわち図３０〜図３４）を考える。前段の拡大Ｓ−ｂｏｘ１０３における前半のＳ−ｂｏｘと、後段の拡大Ｓ−ｂｏｘ１０３の前半のＳ−ｂｏｘとは、前段の拡大Ｓ−ｂｏｘ１０３における後半のＳ−ｂｏｘを経由して接続されている。このときに、次の基準を大ＭＤＳ（１３０−１〜１０３−８）の選択基準とする。
（１）前段の拡大Ｓ−ｂｏｘ１０３の前半における全Ｓ−ｂｏｘ（ここでは合計１６個のＳ−ｂｏｘ）のうちから任意に選んだ１つのＳ−ｂｏｘと、後段の拡大Ｓ−ｂｏｘ１０３の前半における全Ｓ−ｂｏｘ（ここでは合計１６個のＳ−ｂｏｘ）のうちから任意に選んだ１つのＳ−ｂｏｘとが、いずれもの組み合わせについても、２本以上の経路によって相互に接続（結合）されている。
（２）当該大ＭＤＳによってなされる線形拡散の逆変換もしくは逆関数（すなわち復号回路側の大ＭＤＳ）が存在し、かつ、それについても（１）と同じ条件が満たされる。
（１）については、例えば、図３５に示すように、１００１のＳ−ｂｏｘと１００２のＳ−ｂｏｘとが、矢印で示すような２本の経路によって相互に接続されており、他のＳ−ｂｏｘ間についても同様に２〜４本の経路によって相互に接続されている。なお、これに対して、従来のＳＱＵＡＲＥ暗号／Ｒｉｊｎｄａｅｌ暗号では、図３６に示すように、１００３のＳ−ｂｏｘと１００４のＳ−ｂｏｘとの間は矢印で示すように１本のみの経路であり（ファン・イン＝１）、他のＳ−ｂｏｘ間についても同様である（したがって、なだれ効果は低い）。
（２）については、後述するように満たされている。
【０１９０】
ここで、上記基準を満たす構成におけるＳＱＵＡＲＥ攻撃に対する安全性について説明する。
【０１９１】
まず、ＳＱＵＡＲＥ攻撃で入力として用いるΛ（ラムダ）集合の定義を示す。
各データがｎ個のバイト（ｎは複数とする；なお１バイト＝８ビットである）を連結したものからなり、そのようなデータを２５６個含む集合があり、その２５６個の全データにおける各々のバイトの値について、次のいずれか一方が成立するとき、
（ａ）取り得る２５６（＝２＾８）種類の値が全部現れる
（ｂ）取り得る２５６（＝２＾８）種類の値のうちの１つのみが現れる（すなわち、常に値が固定）
この２５６個のｎバイトのデータの集合をΛ集合と呼ぶ。
Λ集合には、次の性質がある。
・Λ集合を入力とする並列Ｓ−ｂｏｘ（可逆）の出力の集合もまた、Λ集合である。
【０１９２】
値が固定でないバイトが１個だけあるΛ集合を、図３０〜図３３のような上記基準を満たす構成における前段の拡大Ｓ−ｂｏｘ１０３の後半のＳ−ｂｏｘ群に入力としたとき、次の性質が確率１で成立する（図３５参照）。
（ｉ）Λ集合となるのは、前段の拡大Ｓ−ｂｏｘの後半のＳ−ｂｏｘの出力までである。
（ｉｉ）任意ビットの２５６パターンについての和が０になるのは、後段の拡大Ｓ−ｂｏｘの前半のＳ−ｂｏｘの入力位置までである。
【０１９３】
これに対して、従来のＳＱＵＡＲＥ暗号／Ｒｉｊｎｄａｅｌ暗号では、次の性質が確率１で成立する（図３６参照）。
（ｉ’）後段の前半のＳ−ｂｏｘ通過後もΛ集合である。
（ｉｉ’）後段の後半のＳ−ｂｏｘの入力位置の任意のビットを２５６パターンについて足すと０になる。
【０１９４】
このように、上記基準を満たす大ＭＤＳでは、従来のＳＱＵＡＲＥ暗号／Ｒｉｊｎｄａｅｌ暗号に比較してＳ−ｂｏｘの層についてみると１層分早く解読に有効な性質が壊される。つまり、ある段数のＳＱＵＡＲＥ暗号／Ｒｉｊｎｄａｅｌ暗号に比べて、それより１層分少ない構成でもＳＱＵＡＲＥ攻撃に対する強度は同等と考えられる。よって、ＳＱＵＡＲＥ攻撃に対する安全性は、Ｓ−ｂｏｘ層で１層分は向上していることが分かる。
【０１９５】
次に、図３０〜図３４で説明した結合関係については、種々のバリエーションが可能である。以下、この結合関係のバリエーションについて説明する。
【０１９６】
図３０〜図３４において例示した大ＭＤＳの構成において、図３７（ａ）に示すように、前段の拡大Ｓ−ｂｏｘ１０３−１−１の後半の４つのＳ−ｂｏｘから取り出した１ビットをそれぞれＸ１１〜Ｘ１４で表し、これらをまとめたものを４ビットデータＸ で表し、同様に、拡大Ｓ−ｂｏｘ１０３−１−２、拡大Ｓ−ｂｏｘ１０３−１−３、拡大Ｓ−ｂｏｘ１０３−１−４、後段の拡大Ｓ−ｂｏｘ１０３−２−１、拡大Ｓ−ｂｏｘ１０３−２−２、拡大Ｓ−ｂｏｘ１０３−２−３、拡大Ｓ−ｂｏｘ１０３−２−４についても、それぞれ、Ｘ２１〜Ｘ２４およびＸ２  、Ｘ３１〜Ｘ３４およびＸ３  、Ｘ４１〜Ｘ４４およびＸ４  、Ｙ１１〜Ｙ１４およびＹ１  、Ｙ２１〜Ｙ２４およびＹ２  、Ｙ３１〜Ｙ３４およびＹ３  、Ｙ４１〜Ｙ４４およびＹ４  で表すものとする。
【０１９７】
この場合に、各拡大Ｓ−ｂｏｘ１０３に対応する４ビットデータＸ１  〜Ｘ４  、Ｙ１  〜Ｙ４の各々をＧＦ（２４  ）の元とみなした場合に、入力側のＸ１  〜Ｘ４から出力側のＹ１  〜Ｙ４  を求めるための大ＭＤＳ行列は、図３７（ｂ）に示すようになる。
【０１９８】
そして、図３０〜図３４において、前段の１つの拡大Ｓ−ｂｏｘの後半の４並列のＳ−ｂｏｘから１ビットずつ取り出した４ビットと、後段の１つの拡大Ｓ−ｂｏｘの前半の４並列のＳ−ｂｏｘから１ビットずつ取り出した４ビットとの間の結線（結線パターン）は、図３７（ｂ）に示す対応する行列要素についてのＧＦ（２４  ）上の乗算の結線表現（結線パターン）になっている（図３０〜図３４において、ｘ５、ｘＡ、ＸＥで示している）。すなわち、図３０〜図３４の線形拡散と、図３７（ｂ）の線形拡散は、等価な関係にある。
【０１９９】
ここで、図３８に、ＧＦ（２４  ）上の乗算の結線表現（結線パターン）を、ＧＦ（２４  ）の１〜Ｆの元の各々について示す。なお、前述したように、結合部分では、排他的論理和がなされる。
【０２００】
上記した基準を満たす構成の大ＭＤＳを作成する場合には、図３０〜図３４における１６個の結線部分を、図３８の３，６，Ｃ，Ｂ，５，Ａ，７，Ｅに対応する結線表現（結線パターン）のうちから適宜選択して組み合わせて構成することができる。ただし、その逆変換に対応する構成についても、同様の条件が満たされていることが必要である。
【０２０１】
また、この場合に、暗号側の大ＭＤＳ（の候補）を決めた場合の復号側の大ＭＤＳ（の候補）、または逆に復号側の大ＭＤＳ（の候補）を決めた場合の暗号側の大ＭＤＳの（の候補）は、図３７（ｂ）のような行列の逆行列を求めることによって、容易に得られる。
【０２０２】
つまり、ＧＦ（２４  ）による行列とその逆行列の全ての要素が３，６，Ｃ，Ｂ，５，Ａ，７，Ｅのいずれかであれば、上記した基準を満たすことになる。
【０２０３】
ここで、上記した基準を満たすＭＤＳ行列表現を、図３９（ａ）〜（ｄ）、図４０（ａ）〜（ｄ）に例示する。
【０２０４】
なお、これら行列の探索は、次の制約の下で行ったものである。
（一）行列は巡回型とする。
（二）要素を並べ替えて一致するものは１個だけ選ぶ。
ここで、並べ替えは、巡回（１，２，３，４）→（２，３，４，１）と、反転（１，２，３，４）→（４，３，２，１）を任意の回数組み合わせてできる操作とする。例えば、（３，３，７，Ｃ）→（３，７，Ｃ，３）→（３，Ｃ，７，３）は該当するが、（３，３，７，Ｃ）→（３，７，３，Ｃ）は該当しない。
また、逆関数の関係にある行列同士を比較すると分かるように、各々の行列は、他の行列の逆行列に並べ替えを行ったものになっている。例えば、（６，Ｂ，Ｅ，Ｅ）は、（５，５，Ａ，Ｅ）−１＝（Ｂ，Ｅ，Ｅ，６）を並べ替えたものになっている。
【０２０５】
これら線形拡散は、上記のように対応する乗算の結線表現を用いて図３０〜図３４のようにして実回路によって実現することも、行列演算または入出力変換表によっても実現することも可能である。
【０２０６】
図３９（ａ）と（ｂ）とは、逆関数の関係にあり、それらの一方を暗号側に用い、他方を復号側に用いればよく、この点は、図３９（ｃ）と（ｄ）、図４０（ａ）と（ｂ）、図４０（ｃ）と（ｄ）のそれぞれについても、同様である（なお、暗号側と復号側とで、どのような実現方法を採用するかについては、必ずしも揃える必要はない（もちろん、揃えてもよい））。
【０２０７】
ところで、各ｓ−ｂｏｘ間の結線パターンは、図３８の３，６，Ｃ，Ｂ，５，Ａ，７，Ｅに対応するものに限定されず、適宜設定することが可能である。例えば、図４２（ｃ）や（ｄ）に示すような結線パターンは図３８には含まれていないが、これらも使用することが可能である（なお、前述したように、該結線パターンの結合部分では、排他的論理和がなされる）。
【０２０８】
この場合には、図３７（ａ）のＸ１１〜Ｘ１４、Ｘ２１〜Ｘ２４、Ｘ３１〜Ｘ３４、Ｘ４１〜Ｘ４４を１６個の入力とし、Ｙ１１〜Ｙ１４、Ｙ２１〜Ｙ２４、Ｙ３１〜Ｙ３４、Ｙ４１〜Ｙ４４を１６個の出力として、１６行１６列のＭＤＳ行列を用いればよい。
【０２０９】
例えば、図３７（ｂ）の線形拡散は、図４１のように表現することができる。すなわち、図３７（ｂ）の５、ＡまたはＥの要素をそれぞれ対応する４行４列の行列で表現して対応する部分に入れると、図４１のようになる（図４１では、４行４列の部分ごとに区切って記述している）。
【０２１０】
そこで、例えば、あるｓ−ｂｏｘ間の結線パターンとして図４２（ｃ）あるいは（ｄ）に示すような結線パターンを用いる場合には、図３８のような１６行１６列の行列の対応する４行４列の部分を、図４２（ｃ）あるいは（ｄ）に示すような４行４列表現に設定すればよい。他の所望の結線パターンを用いる場合も同様である。なお、結線パターンの４行４列表現は、当該結線パターンの入力側を４つの１ビット入力と、出力側を４つの１ビット出力として考えた場合の変換行列となっているものである。
【０２１１】
このように図３０〜図３３のｓ−ｂｏｘ間の結線パターンとして任意の結線パターンを用いる場合にも、暗号側について図４２のように表現した場合の行列の逆行列が、復号側について図４２のように表現した場合の行列となる。また、この場合の線形拡散も、任意の結線パターンを用いて（図３０〜図３４と同様にして）実回路によって実現することも、行列演算または入出力変換表によっても実現することも可能である。
【０２１２】
ところで、上記では基準（１）として、
（１）前段の拡大Ｓ−ｂｏｘの前半における全Ｓ−ｂｏｘのうちから任意に選んだ１つのＳ−ｂｏｘと、後段の拡大Ｓ−ｂｏｘの前半における全Ｓ−ｂｏｘのうちから任意に選んだ１つのＳ−ｂｏｘとが、いずれもの組み合わせについても、２本以上の経路によって相互に接続（結合）されている。
としたが、
この条件を緩和して構成することも可能である。
【０２１３】
例えば、次の条件が考えられる。
（１’）前段の拡大Ｓ−ｂｏｘと後段の拡大Ｓ−ｂｏｘとの全ての組み合わせの各々において、少なくとも１組の、当該前段の拡大Ｓ−ｂｏｘの後半の４つのｓ−ｂｏｘのうちの１つと当該後段の拡大Ｓ−ｂｏｘの前半の４つのｓ−ｂｏｘのうちの１つとが、２本以上の経路によって相互に接続（結合）されている。
また、例えば、次の条件が考えられる。
（１’’）前段の拡大Ｓ−ｂｏｘの前半における少なくとも１つのＳ−ｂｏｘと、後段の拡大Ｓ−ｂｏｘの前半における少なくとも１つのＳ−ｂｏｘとが、２本以上の経路によって相互に接続（結合）されている。
【０２１４】
このような条件の場合には、Ｓ−ｂｏｘ間の結線パターンをＧＦ（２４  ）上の乗算の結線表現（結線パターン）に限定するときでも、図３８の１〜Ｆに対応する結線表現（結線パターン）のうちから適宜選択して組み合わせて構成することができる。
【０２１５】
また、Ｓ−ｂｏｘ間の結線パターンをＧＦ（２４  ）上の乗算の結線表現（結線パターン）に限定しないときは、例えば図４２（ａ）や（ｂ）に例示するものをはじめ様々な結線パターンあるいは対応する行列を用いることができる。
【０２１６】
なお、以上では、暗号側と復号側で同一の基準を適用するものとしたが、暗号側と復号側で異なる基準を採用することも可能である。例えば、暗号側と復号側の一方には上記基準（１）を適用し、他方には上記基準（１’）を適用するこよも可能である。また、その他の適用の仕方も可能である。
【０２１７】
なお、上記と同様の考え方により、８ビット・データのうちの同じ位置の２ビットごとに処理を行うこととして、各要素が８ビットの４行４列のＭＤＳ行列（ＧＦ（２８  ））を、４個用意して、大ＭＤＳを構成することも可能である。また、８ビット・データのうちの同じ位置の４ビットごとに処理を行うこととして、各要素が１６ビットの４行４列のＭＤＳ行列（ＧＦ（２１６））を、２個用意して、大ＭＤＳを構成することも可能である。また、各要素が３２ビットの４行４列のＭＤＳ行列（ＧＦ（２３２））を、１個用意して、大ＭＤＳを構成することも可能である。
【０２１８】
また、以上では、同じ位置のビットを取り出して処理を行うものとして説明したが、異なる位置のビットを（排他的に）取り出して処理を行うことも可能である。
【０２１９】
図４３に、大ＭＤＳの選択手順の一例を示す。
【０２２０】
ここでは、先に暗号側の構成を求めるものとして説明するが、その逆ももちろん可能である（暗号側と復号側が逆になるだけである）。
【０２２１】
まず、ステップＳ１０１で、所定の方法で（例えばランダムに）、暗号側のＭＤＳ行列を求め、ステップＳ１０２で、該行列が一定の基準（例えば、前述した基準（１））を満たしているか否か判定する。一定の基準を満たしていなければ、該行列を破棄し、ステップＳ１０１で他の行列を求める。
【０２２２】
一定の基準を満たした場合には、ステップＳ１０３で、上記ＭＤＳ行列の逆行列すなわち復号側のＭＤＳ行列を求め、ステップＳ１０４で、該行列が一定の基準（例えば、前述した基準（１））を満たしているか否か判定する。一定の基準を満たしていなければ、これら行列を破棄し、ステップＳ１０１で他の行列を求める。
【０２２３】
一定の基準を満たした場合には、暗号側のＭＤＳ行列および復号側のＭＤＳ行列の組みの候補となる。
【０２２４】
以上の手順を繰り返し行って得た複数の候補のうちから所定の方法で選択したものを採用しても良いし、最初に得られた候補を採用するようにしてもよい。
【０２２５】
なお、大ＭＤＳを実回路で実現する場合には、得られたＭＤＳ行列と等価な結線パターンを用いればよい。
【０２２６】
なお、以上のバリエーションとして、各々の大ＭＤＳの前段及び又は後段に、同一の拡大Ｓ−ｂｏｘに属する複数のＳ−ｂｏｘについてのビットの位置を入れ替える処理を行う（あるいはそのような回路を挿入する）構成も可能である。
【０２２７】
もちろん、ここで説明した大ＭＤＳの構成は、これまで説明してきた種々のバリエーションを持つ暗号化装置や復号装置に適用可能である。
【０２２８】
例えば、上記では、１つの拡張Ｓ−ｂｏｘを４並列２段分の８ビットＳ−ｂｏｘと小ＭＤＳ（と鍵加算）で構成し、このような拡張Ｓ−ｂｏｘを４並列にし、４並列の拡張Ｓ−ｂｏｘと大ＭＤＳとを交互に配置した（４並列の拡張Ｓ−ｂｏｘと４並列の拡張Ｓ−ｂｏｘとを大ＭＤＳで結合した）１２８ビット・ブロック暗号の暗号化装置／復号装置もしくは暗号アルゴリズム／復号アルゴリズムの場合を例にとって説明したが、もちろん、ここで説明した大ＭＤＳの構成は、上記と同様の拡張Ｓ−ｂｏｘを２並列にし、２並列の拡張Ｓ−ｂｏｘと大ＭＤＳとを交互に配置した（２並列の拡張Ｓ−ｂｏｘと２並列の拡張Ｓ−ｂｏｘとを大ＭＤＳで結合した）６４ビット・ブロック暗号の暗号化装置／復号装置もしくは暗号アルゴリズム／復号アルゴリズムの場合にも適用可能である。
【０２２９】
なお、このような６４ビット・ブロック暗号の場合、１２８ビット・ブロック暗号の構成における４並列の拡張Ｓ−ｂｏｘの部分を２並列の拡張Ｓ−ｂｏｘに置き換えるとともに、これに対応する部分を修正すればよい。
【０２３０】
例えば、鍵長は、１２８ビットとすればよいし、もちろん、６４ビットや９６ビットなど、他の鍵長も可能である。なお、この場合の段数Ｒは、好ましくは６段以上とする。
【０２３１】
６４ビット・ブロック暗号の場合、図３０〜図３４の構成では、４並列の拡張Ｓ−ｂｏｘが２並列の拡張Ｓ−ｂｏｘになる点が異なるが、前述した基準や結合の方法や結合パターンは同様である。また、図３７（ｂ）や図３９や図４０の大ＭＤＳ行列は、２行２列になる。また、これに対応して、図４１の大ＭＤＳ行列は、８行８列になる。なお、拡張Ｓ−ｂｏｘの内部構成は同じであるので、図３８や図４２などの結合パターンは同じものが使用可能である。また、図４３の手順も同様である。
【０２３２】
ブロックデータがその他のデータ長の場合ももちろん可能である。
【０２３３】
また、拡張Ｓ−ｂｏｘ内のＳ−ｂｏｘの並列数が異なる場合ももちろん可能である。
【０２３４】
上記のような大ＭＤＳを用いた１２８ビット暗号の場合の一構成例に係る共通鍵ブロック暗号方式による暗号化装置あるいは復号装置は、例えば、初段では入力された１２８ビットの平文ブロックデータを、２段目以降では前段での処理が施された１２８ビットのブロックデータを入力とし、該ブロックデータを４分割した４組の３２ビット・データに対してそれぞれ局所的な線形拡散処理および非線形変換処理を施し出力する４つの第１の非線形変換処理部と、これら４つの第１の非線形変換処理部からそれぞれ出力された４組の３２ビット・データを連結した１２８ビットのブロックデータに対して最大距離分離行列を用いて線形拡散処理を施し次段へ出力する第１の拡散処理部とを、１段分の段構成として、該段構成を所定段数分接続し、最後の前記第１の拡散処理部の後段に、この第１の拡散処理部から出力される１２８ビットのブロックデータを入力とする前記４つの第１の非線形変換処理部を接続し、この４つの第１の非線形変換処理部の後段に、これら４つの第１の非線形変換処理部からそれぞれ出力された４組の３２ビット・データを連結した１２８ビットのブロックデータに対して１２８ビットの鍵データを加算して１２８ビットの暗号化されたブロックデータとして出力する第１の鍵加算部を接続して構成されるとともに、前記第１の非線形変換処理部の各々は、与えられた１組の前記３２ビット・データをさらに４分割した４組の８ビット・データに対してそれぞれ８ビットの鍵データを加算する４つの第２の鍵加算部と、各第２の鍵加算部の出力に対してそれぞれ８ビットの入出力変換表を用いて非線形変換を行う４つの第２の非線形変換処理部と、これら４つの第２の非線形変換処理部からそれぞれ出力された４組の８ビット・データを連結した３２ビット・データに対して最大距離分離行列を用いて線形拡散処理を施す第２の拡散処理部と、この第２の拡散処理部の後段にさらに接続された４組の前記第２の鍵加算部および第２の非線形変換処理部とを含むものであり、前記第１の拡散処理部の各々は、前段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部からそれぞれ出力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における入力側の１つの要素とするとともに、後段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部へそれぞれ入力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における出力側の１つの要素として、２４のガロア体の乗算に基づいた４行４列の行列演算またはこれと等価な回路によって線形拡散処理を行う１６ビット拡散手段を、該前段及び後段の第２の非線形変換処理部についての該８ビットのうちの各ビットに対応して有し、１つの前記１６ビット拡散手段における前記２４のガロア体の乗算に基づいた４行４列の行列演算またはこれと等価な回路では、前段の４つの第１の非線形変換処理手段の最終段における合計１６の第２の非線形変換処理手段からの出力となる任意の１ビットと、後段の４つの第１の非線形変換処理手段の初段における合計１６の第２の非線形変換処理手段へ入力となる任意の１ビットとのすべての組み合わせにおいて、前段側における当該１ビットの状態を、後段側における当該１ビットへ、複数の演算経路を辿って波及させるための手段を含むものである。
【０２３５】
また、上記のような大ＭＤＳを用いた６４ビット暗号の場合の一構成例に係る共通鍵ブロック暗号方式による暗号化装置あるいは復号装置は、例えば、初段では入力された６４ビットの平文ブロックデータを、２段目以降では前段での処理が施された６４ビットのブロックデータを入力とし、該ブロックデータを２分割した２組の３２ビット・データに対してそれぞれ局所的な線形拡散処理および非線形変換処理を施し出力する２つの第１の非線形変換処理部と、これら２つの第１の非線形変換処理部からそれぞれ出力された２組の３２ビット・データを連結した６４ビットのブロックデータに対して最大距離分離行列を用いて線形拡散処理を施し次段へ出力する第１の拡散処理部とを、１段分の段構成として、該段構成を所定段数分接続し、最後の前記第１の拡散処理部の後段に、この第１の拡散処理部から出力される６４ビットのブロックデータを入力とする前記２つの第１の非線形変換処理部を接続し、この２つの第１の非線形変換処理部の後段に、これら２つの第１の非線形変換処理部からそれぞれ出力された２組の３２ビット・データを連結した６４ビットのブロックデータに対して６４ビットの鍵データを加算して６４ビットの暗号化されたブロックデータとして出力する第１の鍵加算部を接続して構成されるとともに、前記第１の非線形変換処理部の各々は、与えられた１組の前記３２ビット・データをさらに４分割した４組の８ビット・データに対してそれぞれ８ビットの鍵データを加算する４つの第２の鍵加算部と、各第２の鍵加算部の出力に対してそれぞれ８ビットの入出力変換表を用いて非線形変換を行う４つの第２の非線形変換処理部と、これら４つの第２の非線形変換処理部からそれぞれ出力された４組の８ビット・データを連結した３２ビット・データに対して最大距離分離行列を用いて線形拡散処理を施す第２の拡散処理部と、この第２の拡散処理部の後段にさらに接続された４組の前記第２の鍵加算部および第２の非線形変換処理部とを含むものであり、前記第１の拡散処理部の各々は、前段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部からそれぞれ出力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における入力側の１つの要素とするとともに、後段の１つの第１の非線形変換処理部の４つの第２の非線形変換処理部へそれぞれ入力される８ビットのうちの相対応する１ビットを一纏めにした４ビットを行列演算における出力側の１つの要素として、２４のガロア体の乗算に基づいた２行２列の行列演算またはこれと等価な回路によって線形拡散処理を行う８ビット拡散手段を、該前段及び後段の第２の非線形変換処理部についての該８ビットのうちの各ビットに対応して有し、１つの前記８ビット拡散手段における前記２４のガロア体の乗算に基づいた２行２列の行列演算またはこれと等価な回路では、前段の２つの第１の非線形変換処理手段の最終段における合計８の第２の非線形変換処理手段からの出力となる任意の１ビットと、後段の２つの第１の非線形変換処理手段の初段における合計８の第２の非線形変換処理手段へ入力となる任意の１ビットとのすべての組み合わせにおいて、前段側における当該１ビットの状態を、後段側における当該１ビットへ、複数の演算経路を辿って波及させるための手段を含むものである。
【０２３６】
以下では、本実施形態のハードウェア構成、ソフトウェア構成について説明する。
【０２３７】
本実施形態の暗号化装置や復号装置は、ハードウェアとしても、ソフトウェアとしても、実現可能である。
【０２３８】
本実施形態は、ソフトウェアで実現する場合に、暗号化装置や復号装置を実現するプログラムであって、コンピュータに所定の手段を実行させるための（あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるための）プログラムを記録したコンピュータ読取り可能な記録媒体としても実施することもできる。
【０２３９】
また、ハードウェアとして構成する場合、半導体装置として形成することができる。
【０２４０】
また、本発明を適用した暗号化装置や復号装置を構成する場合、あるいは暗号化プログラムや復号プログラムを作成する場合に、図４や図２４で例示したようなブロックもしくはモジュールをすべて個別に作成することも可能であるが、同一構成を有するブロックもしくはモジュールについては１または適当数のみ用意しておいて、それをアルゴリズムの各部分で共有する（使い回す）ことも可能である。
【０２４１】
また、ソフトウェアの場合には、マルチプロセッサを利用し、並列処理を行って、処理を高速化することも可能である。
【０２４２】
なお、暗号化機能を持ち、復号機能を持たない装置として構成することも、復号機能を持ち、暗号化機能を持たない装置として構成することも、暗号化機能と復号機能の両方を持つ装置として構成することも、可能である。同様に、暗号化機能を持ち、復号機能を持たないプログラムとして構成することも、復号機能を持ち、暗号化機能を持たないプログラムとして構成することも、暗号化機能と復号機能の両方を持つプログラムとして構成することも、可能である。
【０２４３】
次に、本実施形態のシステムへの応用について説明する。
【０２４４】
本実施形態の暗号方式は、基本的にはどのようなシステムにも適用可能である。
【０２４５】
例えば、図４４に示すように、送信側装置３０１と、受信側装置３０３との間で、所定の方法もしくは手続により、鍵を安全に共有しておき、送信側装置３０１は送信データをブロック長ごとに本実施形態の暗号方式で暗号化し、所定のプロトコルに従って、通信ネットワーク３０２を介して、暗号文を受信側装置３０３へ送信し、暗号文を受信した受信側装置３０３では、受信した暗号文をブロック長ごとに本実施形態の暗号方式で復号し、もとの平文を得ることができる。なお、各々の装置が、暗号化機能と復号機能を両方持っていれば、双方向に暗号通信を行うことができる。
【０２４６】
また、例えば、図４５に示すように、計算機３１１では、所定の方法で鍵を生成し、保存したいデータをブロック長ごとに本実施形態の暗号方式で暗号化し、所定のネットワーク（例えば、ＬＡＮ、インターネット等）３１４を介して、暗号化データとして、データ・サーバ３１３に保存しておく。計算機３１１では、このデータを読みたいときは、データ・サーバ３１３から所望の暗号化データを読み込み、これをブロック長ごとに本実施形態の暗号方式で復号し、もとの平文を得ることができる。また、他の計算機３１２が、この鍵を知っていれば、同様に復号してもとの平文を得ることができるが、鍵の分からない他の計算機は、該暗号データを復号することはできず、情報のセキュリティ・コントロールが可能になる。
【０２４７】
また、例えば、図４６に示すように、コンテンツ提供側では、暗号化装置３２１により、あるコンテンツを、ある鍵で、ブロック長ごとに本実施形態の暗号方式で暗号化し、これを暗号化コンテンツとして、記録媒体３２２に記録し、これを頒布等する。記録媒体３２２を取得したユーザ側では、所定の方法で該ある鍵を入手することにより、復号装置３２３により、該コンテンツを、ブロック長ごとに本実施形態の暗号方式で復号し、コンテンツの閲覧もしくは再生等を行うことができる。
【０２４８】
もちろん、上記以外にも種々のシステムに適用可能である。
【０２４９】
なお、本実施形態で示した各々の構成は、一例であって、それ以外の構成を排除する趣旨のものではなく、例示した構成の一部を他のもので置き換えたり、例示した構成の一部を省いたり、例示した構成に別の機能を付加したり、それらを組み合わせたりすることなどによって得られる別の構成も可能である。また、例示した構成と論理的に等価な別の構成、例示した構成と論理的に等価な部分を含む別の構成、例示した構成の要部と論理的に等価な別の構成なども可能である。また、例示した構成と同一もしくは類似の目的を達成する別の構成、例示した構成と同一もしくは類似の効果を奏する別の構成なども可能である。
また、各種構成部分についての各種バリエーションは、適宜組み合わせて実施することが可能である。
また、本実施形態は、暗号化装置としての発明、復号化装置としての発明、システム全体としての発明、個別装置内部の構成部分についての発明、またはそれらに対応する方法の発明等、種々の観点、段階、概念またはカテゴリに係る発明を包含・内在するものである。
従って、この発明の実施の形態に開示した内容からは、例示した構成に限定されることなく発明を抽出することができるものである。
【０２５０】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０２５１】
【発明の効果】
本発明によれば、局所的なデータ拡散を行う小型の拡散層とブロック幅に及ぶ拡散を行う大型の拡散層を交互に重ねて運用することにより、計算コストを抑えたまま高く均一な拡散を実現することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る暗号方式の基本的な構成について説明するための図
【図２】同実施形態の暗号強度に関して説明するための図
【図３】同実施形態の入れ子型暗号方式のデータ攪拌部の階層構造の例を示す図
【図４】同実施形態の暗号化装置の構成例を示す図
【図５】同実施形態のＳ−ｂｏｘの一例を示す図
【図６】同実施形態の拡大Ｓ−ｂｏｘの内部構成例を示す図
【図７】同実施形態の小ＭＤＳの一例を示す図
【図８】同実施形態の大ＭＤＳおよび拡大Ｓ−ｂｏｘの構造例を示す図
【図９】同実施形態の大ＭＤＳの一例を示す図
【図１０】同実施形態の大ＭＤＳの他の例を示す図
【図１１】同実施形態の鍵スケジュール部の構成例を示す図
【図１２】同実施形態の鍵スケジュール部の他の構成例を示す図
【図１３】同実施形態の非線形変換層の内部構成の一例を示す図
【図１４】同実施形態の非線形変換層の内部構成の他の例を示す図
【図１５】同実施形態の加算定数表の一例を示す図
【図１６】同実施形態の有限体乗算装置の構成例を示す図
【図１７】同実施形態の線形変換装置の構成例を示す図
【図１８】同実施形態の線形変換装置の構成例を示す図
【図１９】同実施形態のＭＤＳ行列生成装置の構成例を示す図
【図２０】同実施形態のＭＤＳ行列生成処理手順の一例を示すフローチャート
【図２１】同実施形態のＭＤＳ行列生成装置の他の構成例を示す図
【図２２】同実施形態のＭＤＳ行列生成処理手順の他の例を示すフローチャート
【図２３】同実施形態のＳ−ｂｏｘと小ＭＤＳの組み合わせを選択するための処理手順の一例を示すフローチャート
【図２４】同実施形態の復号装置の構成例を示す図
【図２５】同実施形態の拡大Ｓ−ｂｏｘの内部構成例を示す図
【図２６】同実施形態の大ＭＤＳおよび拡大Ｓ−ｂｏｘの構造例を示す図
【図２７】同実施形態の鍵スケジュール部の構成例を示す図
【図２８】同実施形態の大ＭＤＳのさらに他の例を示す図
【図２９】同実施形態の大ＭＤＳのさらに他の例を示す図
【図３０】同実施形態の大ＭＤＳのＳ−ｂｏｘ間の結線パターンの一例を示す図
【図３１】同実施形態の大ＭＤＳのＳ−ｂｏｘ間の結線パターンの一例を示す図
【図３２】同実施形態の大ＭＤＳのＳ−ｂｏｘ間の結線パターンの一例を示す図
【図３３】同実施形態の大ＭＤＳのＳ−ｂｏｘ間の結線パターンの一例を示す図
【図３４】同実施形態の大ＭＤＳのＳ−ｂｏｘ間の結線パターンの一例を示す図
【図３５】同実施形態の大ＭＤＳの前段と後段のＳ−ｂｏｘ間の経路について説明するための図
【図３６】従来の隣接する段のＳ−ｂｏｘ間の経路について説明するための図
【図３７】同実施形態の大ＭＤＳのＧＦ（２４  ）による行列表現について説明するための図
【図３８】ＧＦ（２４  ）上の乗算の結線表現を示す図
【図３９】ファン・インに関する基準（１）を満たすＭＤＳ行列の例を示す図
【図４０】ファン・インに関する基準（１）を満たすＭＤＳ行列の例を示す図
【図４１】同実施形態の大ＭＤＳの１６行１６列の行列表現について説明するための図
【図４２】ＧＦ（２４  ）上の乗算の結線表現以外の結線表現の例を示す図
【図４３】同実施形態の大ＭＤＳ行列選択処理手順の一例を示すフローチャート
【図４４】同実施形態の暗号方式を利用したシステムの一例を示す図
【図４５】同実施形態の暗号方式を利用したシステムの他の例を示す図
【図４６】同実施形態の暗号方式を利用したシステムのさらに他の例を示す図
【符号の説明】
１…暗号処理装置
２…最上位の階層の非線形変換モジュール
３…データ幅に渡る拡散モジュール
４…階層構造内部の非線形変換モジュール
５…局所的な拡散モジュール
１０２…拡大Ｓ−ｂｏｘ層
１０３，１１０３…拡大Ｓ−ｂｏｘ
１０４，１３１，１１０４…大ＭＤＳ
１０５，１１０５…（暗号文直前の）鍵加算部
１１１，１１１１…鍵加算部
１１２，１４１，１１１２…Ｓ−ｂｏｘ
１１３，１４２，１１１３…小ＭＤＳ
１２１〜１２４…鍵スケジュール部
１３４，１４３…排他的論理和部
１３５，１３６…剰余加算部
２００…有限体乗算装置
２０１…桁溢れ帰還部
２０２…係数格納部
２０３…乗算部
２０４，２０５…排他的論理和部
２３１…要素生成部
２３２…小行列式計算部
２３３…判定部
２３４…逆行列生成部
２３５…逆行列判定部
【図１】
0003557178.tif 000004
【図２】
0003557178.tif 000005
【図３】
0003557178.tif 000006
【図４】
0003557178.tif 000007
【図５】
0003557178.tif 000008
【図６】
0003557178.tif 000009
【図７】
0003557178.tif 000010
【図８】
0003557178.tif 000011
【図９】
0003557178.tif 000012
【図１０】
0003557178.tif 000013
【図１１】
0003557178.tif 000014
【図１２】
0003557178.tif 000015
【図１３】
0003557178.tif 000016
【図１４】
0003557178.tif 000017
【図１５】
0003557178.tif 000018
【図１６】
0003557178.tif 000019
【図１７】
0003557178.tif 000020
【図１８】
0003557178.tif 000021
【図１９】
0003557178.tif 000022
【図２０】
0003557178.tif 000023
【図２１】
0003557178.tif 000024
【図２２】
0003557178.tif 000025
【図２３】
0003557178.tif 000026
【図２４】
0003557178.tif 000027
【図２５】
0003557178.tif 000028
【図２６】
0003557178.tif 000029
【図２７】
0003557178.tif 000030
【図２８】
0003557178.tif 000031
【図２９】
0003557178.tif 000032
【図３０】
0003557178.tif 000033
【図３１】
0003557178.tif 000034
【図３２】
0003557178.tif 000035
【図３３】
0003557178.tif 000036
【図３４】
0003557178.tif 000037
【図３５】
0003557178.tif 000038
【図３６】
0003557178.tif 000039
【図３７】
0003557178.tif 000040
【図３８】
0003557178.tif 000041
【図３９】
0003557178.tif 000042
【図４０】
0003557178.tif 000043
【図４１】
0003557178.tif 000044
【図４２】
0003557178.tif 000045
【図４３】
0003557178.tif 000046
【図４４】
0003557178.tif 000047
【図４５】
0003557178.tif 000048
【図４６】
0003557178.tif 000049