(57)【特許請求の範囲】
【請求項１】
データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対するデータ変換処理を繰り返し実行するデータ変換処理部を有し、
前記データ変換処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部を有し、
前記Ｆ関数実行部は、
非線形変換処理を実行する非線形変換処理部を有し、
前記非線形変換処理部は、
非線形演算部と、ビット置換部を交互に繰り返す繰り返し構造を有し、
前記繰り返し構造に含まれる複数の非線形演算部は、異なる演算構成を持つ少なくとも２以上の異なる非線形演算部を含み、
前記２以上の異なる非線形演算部は、
（ａ）２ラインのデータの論理演算結果と別ラインのデータとのＸＯＲ演算を実行する構成、
（ｂ）２ラインのデータの論理演算結果と別ラインのデータとのＸＮＯＲ演算を実行する構成、
上記（ａ），（ｂ）の２つの構成を含むデータ処理装置。
【請求項２】
前記ビット置換部は、前記非線形演算部に対する入出力ビットを入れ替える配線構成を有する請求項１に記載のデータ処理装置。
【請求項３】
前記繰り返し構造に含まれる非線形演算部は、
１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる構成される演算部であり、
前記非線形変換処理部は、
２ビット入力１ビット出力のＮＡＮＤまたはＮＯＲ演算部における演算結果としての１ビットを、前記ＸＯＲまたはＸＮＯＲ演算部に出力して、他の入力１ビットデータとのＸＯＲまたはＸＮＯＲ演算を実行し、ＸＯＲまたはＸＮＯＲ演算結果として生成した１ビットデータを非線形変換処理結果の構成ビットとして出力する請求項１に記載のデータ処理装置。
【請求項４】
前記非線形変換処理部は、
ｎビットデータの非線型変換結果を出力する構成において、
前記非線形演算部を、ｎ回以上繰り返す繰り返し構造を有する請求項１に記載のデータ処理装置。
【請求項５】
前記非線形変換処理部は、
ｎビットデータの非線型変換結果を出力する構成において、
前記非線形演算部をｎ回、前記ビット置換部をｎ回の前記非線形演算部の間にｎ−１回設定した構成である請求項１に記載のデータ処理装置。
【請求項６】
前記繰り返し構造に含まれる非線形演算部は、
１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる構成される演算部であり、
前記非線形変換処理部は、
非線形変換対象となるデータの構成ビットの全てに対して、１つのＮＡＮＤまたはＮＯＲ演算部の演算結果とのＸＯＲまたはＸＮＯＲ演算結果を生成し、該ＸＯＲまたはＸＮＯＲ演算結果を非線型変換結果の構成ビットとして出力する請求項１に記載のデータ処理装置。
【請求項７】
前記繰り返し構造に含まれる非線形演算部は、
１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる構成される演算部であり、
前記非線形変換処理部は、
前記繰り返し構造中に、ＸＯＲ演算部とＸＮＯＲ演算部の双方を有する構成である請求項１に記載のデータ処理装置。
【請求項８】
前記データ処理装置は、
入力データとしての平文を暗号文に変換する暗号化処理、または、
入力データとしての暗号文を平文に変換する復号処理を実行する請求項１に記載のデータ処理装置。
【請求項９】
前記非線形変換処理部は、
４ビット入力、４ビット出力の非線形演算部と、ビット置換部との繰り返し構造を有する請求項１に記載のデータ処理装置。
【請求項１０】
非線形演算部と、一種類のビット置換部との繰り返し構造を有する非線形変換処理部を有し、
前記非線形演算部は、１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる非線形演算部であり、
前記繰り返し構造に含まれる複数の非線形演算部は、異なる演算構成を持つ少なくとも２以上の異なる非線形演算部を含み、
前記２以上の異なる非線形演算部は、
（ａ）２ラインのデータの論理演算結果と別ラインのデータとのＸＯＲ演算を実行する構成、
（ｂ）２ラインのデータの論理演算結果と別ラインのデータとのＸＮＯＲ演算を実行する構成、
上記（ａ），（ｂ）の２つの構成を含み、
前記非線形変換処理部は、
非線形変換対象となるデータの構成ビットの全てに対して、１つのＮＡＮＤまたはＮＯＲ演算部の演算結果とのＸＯＲまたはＸＮＯＲ演算結果を生成し、該ＸＯＲまたはＸＮＯＲ演算結果を非線型変換結果の構成ビットとして出力するデータ処理装置。
【請求項１１】
プログラムを保持するメモリと、
前記プログラムを実行するプロセッサと、
データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対するデータ変換処理を繰り返し実行するデータ変換処理部を有し、
前記データ変換処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部を有し、
前記Ｆ関数実行部は、
非線形変換処理を実行する非線形変換処理部を有し、
前記非線形変換処理部は、
非線形演算部と、ビット置換部を交互に繰り返す繰り返し構造を有し、
前記繰り返し構造に含まれる複数の非線形演算部は、異なる演算構成を持つ少なくとも２以上の異なる非線形演算部を含み、
前記２以上の異なる非線形演算部は、
（ａ）２ラインのデータの論理演算結果と別ラインのデータとのＸＯＲ演算を実行する構成、
（ｂ）２ラインのデータの論理演算結果と別ラインのデータとのＸＮＯＲ演算を実行する構成、
上記（ａ），（ｂ）の２つの構成を含む情報処理装置。
【請求項１２】
データ処理装置において実行するデータ処理方法であり、
データ処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対するデータ変換処理を繰り返し実行し、
前記データ変換処理において、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数を実行し、
前記Ｆ関数の実行処理において、非線形変換処理を実行し、
前記非線形変換処理は、
非線形演算部と、ビット置換部を交互に繰り返す繰り返し構造を適用した処理であり、
前記繰り返し構造に含まれる複数の非線形演算部は、異なる演算構成を持つ少なくとも２以上の異なる非線形演算部を含み、
前記２以上の異なる非線形演算部は、
（ａ）２ラインのデータの論理演算結果と別ラインのデータとのＸＯＲ演算を実行する構成、
（ｂ）２ラインのデータの論理演算結果と別ラインのデータとのＸＮＯＲ演算を実行する構成、
上記（ａ），（ｂ）の２つの構成を含み、
前記非線形変換処理は、
前記２以上の異なる非線形演算部を適用した処理として実行するデータ処理方法。
【請求項１３】
データ処理装置においてデータ変換処理を実行させるプログラムであり、
データ処理部に、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対するデータ変換処理を繰り返し実行させ、
前記データ変換処理において、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数を実行させ、
前記Ｆ関数の実行処理において、非線形変換処理を実行させ、
前記非線形変換処理は、
非線形演算部と、ビット置換部を交互に繰り返す繰り返し構造を適用した処理であり、
前記繰り返し構造に含まれる複数の非線形演算部は、異なる演算構成を持つ少なくとも２以上の異なる非線形演算部を含み、
前記２以上の異なる非線形演算部は、
（ａ）２ラインのデータの論理演算結果と別ラインのデータとのＸＯＲ演算を実行する構成、
（ｂ）２ラインのデータの論理演算結果と別ラインのデータとのＸＮＯＲ演算を実行する構成、
上記（ａ），（ｂ）の２つの構成を含み、
前記非線形変換処理は、
前記２以上の異なる非線形演算部を適用した処理として実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、データ処理装置、およびデータ処理方法、並びにプログラムに関する。さらに詳細には、例えば共通鍵系暗号を実行するデータ処理装置、およびデータ処理方法、並びにプログラムに関する。
【背景技術】
【０００２】
情報化社会が発展すると共に、扱う情報を安全に守るための情報セキュリティ技術の重要性が増してきている。情報セキュリティ技術の構成要素の一つとして暗号技術があり、現在では様々な製品やシステムで暗号技術が利用されている。
【０００３】
暗号処理アルゴリズムには様々なものがあるが、基本的な技術の一つとして、共通鍵ブロック暗号と呼ばれるものがある。共通鍵ブロック暗号では、暗号化用の鍵と復号用の鍵が共通のものとなっている。暗号化処理、復号処理共に、その共通鍵から複数の鍵を生成し、あるブロック単位、例えば６４ビット、１２８ビット、２５６ビット等のブロックデータ単位でデータ変換処理を繰り返し実行する。
【０００４】
代表的な共通鍵ブロック暗号のアルゴリズムとしては、過去の米国標準であるＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）や現在の米国標準であるＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）が知られている。他にも様々な共通鍵ブロック暗号が現在も提案され続けており、２００７年にソニー株式会社が提案したＣＬＥＦＩＡも共通鍵ブロック暗号の一つである。
【０００５】
このような、共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を繰り返し実行するラウンド関数実行部を有する暗号処理部と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部とによって構成される。鍵スケジュール部は、秘密鍵であるマスター鍵（主鍵）に基づいて、まずビット数を増加させた拡大鍵を生成し、生成した拡大鍵に基づいて、暗号処理部の各ラウンド関数部で適用するラウンド鍵（副鍵）を生成する。
【０００６】
このようなアルゴリズムを実行する具体的な構造として、線形変換部および非線形変換部を有するラウンド関数を繰り返し実行する構造が知られている。例えば代表的な構造にＦｅｉｓｔｅｌ構造や一般化Ｆｅｉｓｔｅｌ構造がある。Ｆｅｉｓｔｅｌ構造や一般化Ｆｅｉｓｔｅｌ構造は、データ変換関数としてのＦ関数を含むラウンド関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。Ｆ関数においては、線形変換処理および非線形変換処理が実行される。なお、Ｆｅｉｓｔｅｌ構造を適用した暗号処理について記載した文献としては、例えば非特許文献１、非特許文献２がある。
【０００７】
Ｆ関数において実行される非線形変換処理は、例えばＳ−ｂｏｘと呼ばれる非線形変換関数を適用して行われる。このＳ−ｂｏｘは、ブロック暗号やハッシュ関数の構成要素であり、その安全性や実装性能を決定付ける非常に重要な関数である。
このＳ−ｂｏｘは、高い安全性が要求される。しかし、高い安全性を保持するために回路規模が大きくなってしまうという問題がある。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】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
【非特許文献３】ＵＳ  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ，  Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｔａｎｄａｒｄｓ  Ｐｕｂｌｉｃａｔｉｏｎｓ  Ｎｏ．  １９７，  ２００１．
【非特許文献４】青木，市川，神田，松井，盛合，中嶋，時田，"１２８ビットブロック暗号  Ｃａｍｅｌｌｉａ  アルゴリズム仕様書"，第  ２．０版，  ２００１．
【非特許文献５】Ｃｈａｅ  Ｈｏｏｎ  Ｌｉｍ，，  "ＣＲＹＰＴＯＮ：Ａ  Ｎｅｗ  １２８−ｂｉｔ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  -Ｓｐｅｃｉｆｉｃａｔｉｏｎ  ａｎｄ  Ａｎａｌｙｓｉｓ  （Ｖｅｒｓｉｏｎ  ０．５）"
【非特許文献６】Ｃｈａｅ  Ｈｏｏｎ  Ｌｉｍ，  "ＣＲＹＰＴＯＮ：Ａ  Ｎｅｗ  １２８−ｂｉｔ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  -Ｓｐｅｃｉｆｉｃａｔｉｏｎ  ａｎｄ  Ａｎａｌｙｓｉｓ  （Ｖｅｒｓｉｏｎ  １．０）"
【非特許文献７】Ｐａｕｌｏ  Ｓ．  Ｌ．  Ｍ  Ｂａｒｒｅｔｏ，  Ｖｉｎｃｅｎｔ  Ｒｉｊｍｅｎ  "Ｔｈｅ  ＷＨＩＲＬＰＯＯＬ  Ｈａｓｈｉｎｇ  Ｆｕｎｃｔｉｏｎ"，  ２００３．
【非特許文献８】Ｐａｓｃａｌ  Ｊｕｎｏｄ  ａｎｄ  Ｓｅｒｇｅ  Ｖａｕｄｅｎａｙ，    "ＦＯＸ  ：  ａ  Ｎｅｗ  Ｆａｍｉｌｙ  ｏｆ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒｓ"  ，２００４
【非特許文献９】Ｓｏｎｙ  Ｃｏｒｐｏｒａｔｉｏｎ，  "Ｔｈｅ  １２８−ｂｉｔ  Ｂｌｏｃｋｃｉｐｈｅｒ  ＣＬＥＦＩＡ    Ａｌｇｏｒｉｔｈｍ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ"，  Ｒｅｖｉｓｉｏｎ  １．０，  ２００７．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本開示は、例えば上述の状況に鑑みてなされたものであり、小型化可能な安全性を持つＳ−ｂｏｘを備えたデータ処理装置、およびデータ処理方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本開示の第１の側面は、
データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対するデータ変換処理を繰り返し実行するデータ変換処理部を有し、
前記データ変換処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部を有し、
前記Ｆ関数実行部は、
非線形変換処理を実行する非線形変換処理部を有し、
前記非線形変換処理部は、
１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる非線形演算部と、
ビット置換部と、
の繰り返し構造を有するデータ処理装置にある。
【００１１】
さらに、本開示のデータ処理装置の一実施態様において、前記ビット置換部は、前記非線形演算部に対する入出力ビットを入れ替える配線構成を有する。
【００１２】
さらに、本開示のデータ処理装置の一実施態様において、前記非線形変換処理部は、２ビット入力１ビット出力のＮＡＮＤまたはＮＯＲ演算部における演算結果としての１ビットを、前記ＸＯＲまたはＸＮＯＲ演算部に出力して、他の入力１ビットデータとのＸＯＲまたはＸＮＯＲ演算を実行し、ＸＯＲまたはＸＮＯＲ演算結果として生成した１ビットデータを非線形変換処理結果の構成ビットとして出力する。
【００１３】
さらに、本開示のデータ処理装置の一実施態様において、前記非線形変換処理部は、ｎビットデータの非線型変換結果を出力する構成において、前記非線形演算部を、ｎ回以上繰り返す繰り返し構造を有する。
【００１４】
さらに、本開示のデータ処理装置の一実施態様において、前記非線形変換処理部は、ｎビットデータの非線型変換結果を出力する構成において、前記非線形演算部をｎ回、前記ビット置換部をｎ回の前記非線形演算部の間にｎ−１回設定した構成である。
【００１５】
さらに、本開示のデータ処理装置の一実施態様において、前記非線形変換処理部は、非線形変換対象となるデータの構成ビットの全てに対して、１つのＮＡＮＤまたはＮＯＲ演算部の演算結果とのＸＯＲまたはＸＮＯＲ演算結果を生成し、該ＸＯＲまたはＸＮＯＲ演算結果を非線型変換結果の構成ビットとして出力する。
【００１６】
さらに、本開示のデータ処理装置の一実施態様において、前記非線形変換処理部は、前記繰り返し構造中に、ＸＯＲ演算部とＸＮＯＲ演算部の双方を有する構成である。
【００１７】
さらに、本開示のデータ処理装置の一実施態様において、前記データ処理装置は、入力データとしての平文を暗号文に変換する暗号化処理、または、入力データとしての暗号文を平文に変換する復号処理を実行する。
【００１８】
さらに、本開示の第２の側面は、
１つのＮＡＮＤまたはＮＯＲ演算部と、
１つのＸＯＲまたはＸＮＯＲ演算部からなる非線形演算部と、
ビット置換部と、
の繰り返し構造を有する非線形変換処理部を有するデータ処理装置にある。
【００１９】
さらに、本開示のデータ処理装置の一実施態様において、前記非線形変換処理部は、非線形変換対象となるデータの構成ビットの全てに対して、１つのＮＡＮＤまたはＮＯＲ演算部の演算結果とのＸＯＲまたはＸＮＯＲ演算結果を生成し、該ＸＯＲまたはＸＮＯＲ演算結果を非線型変換結果の構成ビットとして出力する。
【００２０】
さらに、本開示の第３の側面は、
データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、
複数ラインを構成する１ラインのデータを入力して変換データを生成する非線形関数実行部を有するラウンド関数の繰り返し構造を有するデータ処理装置にある。
【００２１】
さらに、本開示のデータ処理装置の一実施態様において、前記非線形関数実行部は、非線形変換対象となるデータの構成ビットの全てに対して、１つのＮＡＮＤまたはＮＯＲ演算部の演算結果とのＸＯＲまたはＸＮＯＲ演算結果を生成し、該ＸＯＲまたはＸＮＯＲ演算結果を非線型変換結果の構成ビットとして出力する。
【００２２】
さらに、本開示の第４の側面は、
データ処理装置において実行するデータ処理方法であり、
データ処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対するデータ変換処理を繰り返し実行し、
前記データ変換処理において、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数を実行し、
前記Ｆ関数の実行処理において、非線形変換処理を実行し、
前記非線形変換処理において、
１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる非線形演算部と、
ビット置換部と、
を適用した繰り返し演算を実行するデータ処理方法にある。
【００２３】
さらに、本開示の第５の側面は、
データ処理装置においてデータ変換処理を実行させるプログラムであり、
データ処理部に、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対するデータ変換処理を繰り返し実行させ、
前記データ変換処理において、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数を実行させ、
前記Ｆ関数の実行処理において、非線形変換処理を実行させ、
前記非線形変換処理において、
１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる非線形演算部と、
ビット置換部と、
を適用した繰り返し演算を実行させるプログラムにある。
【００２４】
なお、本開示のプログラムは、例えば、様々なプログラム・コードを実行可能な情報処理装置やコンピュータ・システムに対して例えば記憶媒体によって提供されるプログラムである。このようなプログラムを情報処理装置やコンピュータ・システム上のプログラム実行部で実行することでプログラムに応じた処理が実現される。
【００２５】
本開示のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００２６】
本開示の一実施例によれば、小型化した非線形変換部が実現される。
具体的には、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理部を有し、暗号処理部は、複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部を有し、Ｆ関数実行部は非線形変換処理を実行する非線形変換処理部を有し、非線形変換処理部は１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる非線形演算部と、ビット置換部との繰り返し構造を有する。この繰り返し構成により小型化された非線形変換部が実現される。
【図面の簡単な説明】
【００２７】
【図１】ｋビットの鍵長に対応したｎビット共通鍵ブロック暗号アルゴリズムを説明する図である。
【図２】図１に示すｋビットの鍵長に対応したｎビット共通鍵ブロック暗号アルゴリズムに対応する復号アルゴリズムを説明する図である。
【図３】鍵スケジュール部とデータ暗号化部の関係について説明する図である。
【図４】データ暗号化部の構成例について説明する図である。
【図５】ＳＰＮ構造のラウンド関数の例について説明する図である。
【図６】Ｆｅｉｓｔｅｌ構造のラウンド関数の一例について説明する図である。
【図７】拡張Ｆｅｉｓｔｅｌ構造の一例について説明する図である。
【図８】拡張Ｆｅｉｓｔｅｌ構造の一例について説明する図である。
【図９】非線形変換部の構成例について説明する図である。
【図１０】線形変換処理部の構成例について説明する図である。
【図１１】小さなサイズの入出力を持つＳ−ｂｏｘを複数個組み合わせて大きなＳ−ｂｏｘを生成する構成例について説明する図である。
【図１２】小さなサイズの入出力を持つＳ−ｂｏｘを複数個組み合わせて大きなＳ−ｂｏｘを生成する構成例について説明する図である。
【図１３】小さなサイズの入出力を持つＳ−ｂｏｘを複数個組み合わせて大きなＳ−ｂｏｘを生成する構成例について説明する図である。
【図１４】小さなサイズの入出力を持つＳ−ｂｏｘを複数個組み合わせて大きなＳ−ｂｏｘを生成する構成例について説明する図である。
【図１５】小さなサイズの入出力を持つＳ−ｂｏｘを複数個組み合わせて大きなＳ−ｂｏｘを生成する構成例について説明する図である。
【図１６】論理演算とビット置換の繰り返し構造による４ビットＳ−ｂｏｘの構成例について説明する図である。
【図１７】論理演算とビット置換の繰り返し構造による４ビットＳ−ｂｏｘの構成例について説明する図である。
【図１８】論理演算とビット置換の繰り返し構造による４ビットＳ−ｂｏｘの構成例について説明する図である。
【図１９】論理演算とビット置換の繰り返し構造による４ビットＳ−ｂｏｘの構成例について説明する図である。
【図２０】論理演算とビット置換の繰り返し構造による４ビットＳ−ｂｏｘの構成例について説明する図である。
【図２１】論理演算とビット置換の繰り返し構造による５ビットＳ−ｂｏｘの構成例について説明する図である。
【図２２】ｔｙｐｅ−ＩＧＦＮ（Ｇｅｎｅｒａｌｉｚｅｄ  Ｆｅｉｓｔｅｌ  Ｎｅｔｗｏｒｋ）を基にした小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの構成例について説明する図である。
【図２３】ｔｙｐｅ−ＩＩＧＦＮを基にした，小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの構成例について説明する図である。
【図２４】小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの構成法の適用例について説明する図である。
【図２５】小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの構成法の適用例について説明する図である。
【図２６】小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの構成法の適用例について説明する図である。
【図２７】小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの構成法の適用例について説明する図である。
【図２８】小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの構成法の適用例について説明する図である。
【図２９】暗号処理装置としてのＩＣモジュール７００の構成例を示す図である。
【発明を実施するための形態】
【００２８】
以下、図面を参照しながら本開示に係るデータ処理装置、およびデータ処理方法、並びにプログラムの詳細について説明する。説明は、以下の項目に従って行う。
１．共通鍵ブロック暗号の概要
２．Ｓ−ｂｏｘについて
３．本開示に係るＳ−ｂｏｘの概要について
４．暗号処理装置の構成例について
５．本開示の構成のまとめ
【００２９】
［１．共通鍵ブロック暗号の概要］
まず、共通鍵ブロック暗号の概要について説明する。
（１−１．共通鍵ブロック暗号）
ここでは共通鍵ブロック暗号（以下ではブロック暗号）としては以下に定義するものを指すものとする。
ブロック暗号は入力として平文Ｐと鍵Ｋを取り、暗号文Ｃを出力する。平文と暗号文のビット長をブロックサイズと呼びここではｎで著す。ｎは任意の整数値を取りうるが、通常、ブロック暗号アルゴリズムごとに、あらかじめひとつに決められている値である。ブロック長がｎのブロック暗号のことをｎビットブロック暗号と呼ぶこともある。
【００３０】
鍵のビット長をｋで表す。鍵は任意の整数値を取りうる。共通鍵ブロック暗号アルゴリズムは１つまたは複数の鍵サイズに対応することになる。例えば、あるブロック暗号アルゴリズムＡはブロックサイズｎ＝１２８であり、ｋ＝１２８またはｋ＝１９２またはｋ＝２５６の鍵サイズに対応するという構成もありうるものとする。
平文Ｐ：ｎビット
暗号文Ｃ：ｎビット
鍵Ｋ：ｋビット
【００３１】
図１にｋビットの鍵長に対応したｎビット共通鍵ブロック暗号アルゴリズムＥの図を示す。
暗号化アルゴリズムＥに対応する復号アルゴリズムＤは暗号化アルゴリズムＥの逆関数Ｅ−１と定義でき、入力として暗号文Ｃと鍵Ｋを受け取り，平文Ｐを出力する。図２に図１に示した暗号アルゴリズムＥに対応する復号アルゴリズムＤの図を示す。
【００３２】
（１−２．内部構成）
ブロック暗号は２つの部分に分けて考えることができる。ひとつは鍵Ｋを入力とし、
ある定められたステップによりビット長を拡大してできた拡大鍵Ｋ'（ビット長ｋ'）を出力する「鍵スケジュール部」と、もうひとつは平文Ｐと鍵スケジュール部から拡大された鍵Ｋ'を受け取ってデータの変換を行い暗号文Ｃを出力する「データ暗号化部」である。
２つの部分の関係は図３に示される。
【００３３】
（１−３．データ暗号化部）
以下の実施例において用いるデータ暗号化部はラウンド関数という処理単位に分割できるものとする。ラウンド関数は入力としての２つのデータを受け取り、内部で処理を施したのち、１つのデータを出力する。入力データの一方は暗号化途中のｎビットデータであり、あるラウンドにおけるラウンド関数の出力が次のラウンドの入力として供給される構成となる。もう１つの入力データは鍵スケジュールから出力された拡大鍵の一部のデータが用いられ、この鍵データのことをラウンド鍵と呼ぶものとする。またラウンド関数の総数は総ラウンド数と呼ばれ、暗号アルゴリズムごとにあらかじめ定められている値である。ここでは総ラウンド数をＲで表す。
【００３４】
データ暗号化部の入力側から見て１ラウンド目の入力データをＸ１とし、ｉ番目のラウンド関数に入力されるデータをＸｉ、ラウンド鍵をＲＫｉとすると、データ暗号化部全体は図４のように示される。
【００３５】
（１−４．ラウンド関数）
ブロック暗号アルゴリズムによってラウンド関数はさまざまな形態をとりうる。ラウンド関数はその暗号アルゴリズムが採用する構造（ｓｔｒｕｃｔｕｒｅ）によって分類できる。代表的な構造としてここではＳＰＮ構造、Ｆｅｉｓｔｅｌ構造、拡張Ｆｅｉｓｔｅｌ構造を例示する。
【００３６】
（ア）ＳＰＮ構造ラウンド関数
ｎビットの入力データすべてに対して、ラウンド鍵との排他的論理和演算、非線形変換、線形変換処理などが適用される構成。各演算の順番は特に決まっていない。図５にＳＰＮ構造のラウンド関数の例を示す。
【００３７】
（イ）Ｆｅｉｓｔｅｌ構造
ｎビットの入力データはｎ／２ビットの２つのデータに分割される。うち片方のデータとラウンド鍵を入力として持つ関数（Ｆ関数）が適用され、出力がもう片方のデータに排他的論理和される。そののちデータの左右を入れ替えたものを出力データとする。Ｆ関数の内部構成にもさまざまなタイプのものがあるが、基本的にはＳＰＮ構造同様にラウンド鍵データとの排他的論理和演算、非線形演算、線形変換の組み合わせで実現される。図６にＦｅｉｓｔｅｌ構造のラウンド関数の一例を示す。
【００３８】
（ウ）拡張Ｆｅｉｓｔｅｌ構造
拡張Ｆｅｉｓｔｅｌ構造はＦｅｉｓｔｅｌ構造ではデータ分割数が２であったものを，３以上に分割する形に拡張したものである。分割数をｄとすると、ｄによってさまざまな拡張Ｆｅｉｓｔｅｌ構造を定義することができる。Ｆ関数の入出力のサイズが相対的に小さくなるため、小型実装に向いているとされる。図７にｄ＝４でかつ、ひとつのラウンド内に２つのＦ関数が並列に適用される場合の拡張Ｆｅｉｓｔｅｌ構造の一例を示す。また，図８にｄ＝８でかつ，ひとつのラウンド内に１つのＦ関数が適用される場合の拡張Ｆｅｉｓｔｅｌ構造の一例を示す。
【００３９】
（１−５．非線形変換処理部）
非線形変換処理部は、入力されるデータのサイズが大きくなると実装上のコストが高くなる傾向がある。それを回避するために対象データを複数の単位に分割し、それぞれに対して非線形変換を施す構成がとられることが多い。例えば入力サイズをｍｓビットとして、それらをｓビットずつのｍ個のデータに分割して、それぞれに対してｓビット入出力を持つ非線形変換を行う構成である。それらのｓビット単位の非線形変換をＳ−ｂｏｘと呼ぶものとする。図９に例を示す。
【００４０】
（１−６．線形変換処理部）
線形変換処理部はその性質上、行列として定義することが可能である。行列の要素はＧＦ（２８）の体の要素やＧＦ（２）の要素など、一般的にはさまざまな表現ができる。図１０にｍｓビット入出力をもち、ＧＦ（２ｓ）の上で定義されるｍ×ｍの行列により定義される線形変換処理部の例を示す。
【００４１】
［２．Ｓ−ｂｏｘについて］
まず、本発明の構成についての説明の前に、非線形変換部としてのＳ−ｂｏｘの概要について説明する。
【００４２】
Ｆ関数において実行される非線形変換処理は、例えばＳ−ｂｏｘと呼ばれる非線形変換関数を適用して行われる。このＳ−ｂｏｘは、ブロック暗号やハッシュ関数の構成要素であり、その安全性や実装性能を決定付ける非常に重要な関数である。
【００４３】
このＳ−ｂｏｘは一般的にはｎ−ｂｉｔ入力、ｍ−ｂｉｔ出力の非線形変換関数であるが、以降ではｎ−ｂｉｔ入出力の全単射なＳ−ｂｏｘについて話を進める。ここで全単射とは出力の全ての値がただ一つの入力の値からの写像であることを意味する。
【００４４】
（安全面）
Ｓ−ｂｏｘの性質は、暗号全体の安全性に大きな影響を与える。暗号全体やラウンド関数自体の厳密な安全性評価はその入出力サイズが大きいことから一般的に困難であるが、Ｓ−ｂｏｘの入出力サイズは一般的には小さい（８−ｂｉｔ入出力程度）ので厳密な評価が可能である。暗号全体の安全性を高くするために、Ｓ−ｂｏｘには、少なくとも以下のような特性（１）〜（４）が求められる。
【００４５】
（特性１）最大差分確率が十分小さい
Ｓ−ｂｏｘの差分確率は、任意の入力差分Δｘと出力差分Δｙに対し、入力変数ｘが一様に選ばれたとき、
Ｓ（ｘ）＋Ｓ（ｘ＋Δｘ）＝Δｙを満たす確率である。
ただし、Ｓ（ｘ）はあるＳ−ｂｏｘ  Ｓの入力ｘに対する出力を表す。
【００４６】
最大差分確率は，すべての入出力差分の組み合わせのうち，最も高い確率で定義される。以下にそれぞれを式で定義する。
入力差分Δｘ，および出力差分Δｙが与えられたときの関数Ｓの差分確率をＤＰｓ（Δｘ，  Δｙ）と定義すると、ＤＰｓ（Δｘ，  Δｙ）は以下のように定義される。
【００４７】
【数１】
0005682526.tif 000002
【００４８】
このとき、関数の最大差分確率ＭＤＰｓは以下のように定義される。
【００４９】
【数２】
0005682526.tif 000003
【００５０】
この差分確率が十分小さいＳ−ｂｏｘを設計することで，差分攻撃に耐性を持たせることができる。
【００５１】
（特性２）最大線形確率が十分小さい
Ｓ−ｂｏｘの線形確率は、任意の入力マスクΓｘと出力マスクΓｙに対し、入力変数ｘが一様に選ばれたとき、
Γｘ・ｘ＝Γｙ・Ｓ（ｘ）
を満たす確率から求められる値である。
ここで，・はｎビットベクトル同士の内積演算を意味する。
【００５２】
最大線形確率は、すべての入出力マスクの組み合わせのうちで最も高い確率で定義される。
以下にそれぞれを式で定義する。
入力マスクΓｘ，および、
出力マスクΓｙ、
が与えられたときの関数Ｓの線形確率を、
ＬＰｓ（Γｘ，  Γｙ）と定義すると，
ＬＰｓ（Γｘ，  Γｙ）は以下のように表現できる．
【００５３】
【数３】
0005682526.tif 000004
【００５４】
このとき、関数Ｓの最大差分確率ＭＬＰｓは以下のように定義される。
【００５５】
【数４】
0005682526.tif 000005
【００５６】
この最大線形確率が十分小さいＳ−ｂｏｘを設計することで線形攻撃に耐性を持たせることができる．
【００５７】
（特性３）ブール多項式表現を行った際のブール代数次数が十分大きい
ブール代数次数は、Ｓ−ｂｏｘの出力のビットを入力ビットのブール式で表現した場合の次数を意味する。すべてのビットに対して十分ブール代数次数の高いＳ−ｂｏｘを設計することで、高階差分攻撃等の代数的性質を利用した攻撃に耐性を持たせることができる。
【００５８】
（特性４）入出力を多項式表現した際の項数が十分多い
Ｓ−ｂｏｘの出力ビットを入力ビットで多項式表現した場合の項数を十分多くすることで、補間攻撃に耐性を持たせることができる。
【００５９】
（実装面について）
Ｓ−ｂｏｘは安全性の要求とは別に高い実装性能も要求される。ソフトウェア実装においては通常、表引き（テーブル実装）と呼ばれる手法により実装されるため、その実装性能はＳ−ｂｏｘの内部構造にはあまり依存しない。しかしながら、ハードウェア実装においては、Ｓ−ｂｏｘの内部構造により、実装性能が大きく左右される。よってＳ−ｂｏｘの内部構造は特にハードウェアの実装性能において重要だということができる。
【００６０】
（従来技術の問題点）
このような要求を満たすＳ−ｂｏｘを効率よく生成する手法として、拡大体上のべき乗関数を用いる方法がよく知られている。この手法で拡大体の次数とべき乗の乗数を適切に選べば、非常に特性の良いＳ−ｂｏｘが生成できる。
【００６１】
実際にｎ−ｂｉｔ入出力Ｓ−ｂｏｘの入力をｘ，出力をｙとして，それぞれがＧＦ（２ｎ）の元だとした場合、
【００６２】
【数５】
0005682526.tif 000006
【００６３】
で与えられる場合、
最大差分確率，最大線形確率の点で最適なＳ−ｂｏｘが構成できることがよく知られている（しかしながら、この手法を用いると入出力を多項式表現した際の項数が少なくなってしまうため、適当なａｆｆｉｎｅ変換を加える必要がある）。
このような手法で構成されたＳ−ｂｏｘの例としては、ＡＥＳ（非特許文献３：ＵＳ  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ，  Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｔａｎｄａｒｄｓ  Ｐｕｂｌｉｃａｔｉｏｎｓ  Ｎｏ．  １９７，  ２００１．），Ｃａｍｅｌｌｉａ（非特許文献４：青木，市川，神田，松井，盛合，中嶋，時田，"１２８ビットブロック暗号  Ｃａｍｅｌｌｉａ  アルゴリズム仕様書"，第  ２．０版，  ２００１．）のＳ−ｂｏｘなどが挙げられる。
【００６４】
ＡＥＳやＣａｍｅｌｌｉａのＳ−ｂｏｘはＧＦ（（２４）２）上の逆元関数としてＳ−ｂｏｘを構成することもできるため、安全性の観点からも特性が非常に良く、さらに非常に高いハードウェア実装性能も持つ。
【００６５】
しかしながら、近年このようなＳ−ｂｏｘに関して、その特徴的な代数的性質を利用した攻撃法や、そのあまりに均一的な拡散性に関する問題点などが指摘されるようになった。
【００６６】
このような点から、特徴的な代数的性質を持たないＳ−ｂｏｘの構成法が考えられ、強い代数的構造を持たないように、ランダム、もしくはそれに準ずるような手法で要素を選択するような手法によりＳ−ｂｏｘを生成する方法が考えられた。このような手法でＳ−ｂｏｘを生成すると、多くの場合、特徴的な代数的構造は持たず、さらに拡大体上のべき乗関数のような均一的な拡散はしないため、上記のような問題に関しては対策がされていると言うことができる。
【００６７】
しかしながら、ｎ−ｂｉｔ入出力のＳ−ｂｏｘの数は，２ｎの階乗個存在するため、実際にｎ−ｂｉｔ入出力のＳ−ｂｏｘをランダムに生成し、その特性をひとつひとつチェックするような手法ではｎがある程度大きくなると効率的に特性の良いＳ−ｂｏｘを生成することは難しくなる。
【００６８】
また、要素が完全にランダムである場合、ハードウェアで実装する際も主にテーブル実装と呼ばれる手法しか用いることができなくなってしまうため、実装効率が大きく低下する。
【００６９】
このような問題から、小さなサイズの入出力を持つＳ−ｂｏｘをランダムに生成、それらを複数個組み合わせて、より大きなＳ−ｂｏｘを生成するという試みがなされている。
例えば、ＣＲＹＰＴＯＮｖｅｒ．０．５（非特許文献５：Ｃｈａｅ  Ｈｏｏｎ  Ｌｉｍ，  "ＣＲＹＰＴＯＮ：Ａ  Ｎｅｗ  １２８−ｂｉｔ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  -Ｓｐｅｃｉｆｉｃａｔｉｏｎ  ａｎｄ  Ａｎａｌｙｓｉｓ  （Ｖｅｒｓｉｏｎ  ０．５）"），ＣＲＹＰＴＯＮ  ｖｅｒ．１．０（非特許文献６：Ｃｈａｅ  Ｈｏｏｎ  Ｌｉｍ，  "ＣＲＹＰＴＯＮ：Ａ  Ｎｅｗ  １２８−ｂｉｔ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  -Ｓｐｅｃｉｆｉｃａｔｉｏｎ  ａｎｄ  Ａｎａｌｙｓｉｓ  （Ｖｅｒｓｉｏｎ  １．０）"），Ｗｈｉｒｌｐｏｏｌ（非特許文献７：Ｐａｕｌｏ  Ｓ．  Ｌ．  Ｍ  Ｂａｒｒｅｔｏ，  Ｖｉｎｃｅｎｔ  Ｒｉｊｍｅｎ  "Ｔｈｅ  ＷＨＩＲＬＰＯＯＬ  Ｈａｓｈｉｎｇ  Ｆｕｎｃｔｉｏｎ"，  ２００３．），ＦＯＸ（非特許文献８：Ｐａｓｃａｌ  Ｊｕｎｏｄ  ａｎｄ  Ｓｅｒｇｅ  Ｖａｕｄｅｎａｙ，    "ＦＯＸ  ：  ａ  Ｎｅｗ  Ｆａｍｉｌｙ  ｏｆ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒｓ"  ，２００４），ＣＬＥＦＩＡ（非特許文献９：Ｓｏｎｙ  Ｃｏｒｐｏｒａｔｉｏｎ，  "Ｔｈｅ  １２８−ｂｉｔ  Ｂｌｏｃｋｃｉｐｈｅｒ  ＣＬＥＦＩＡ    Ａｌｇｏｒｉｔｈｍ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ"，  Ｒｅｖｉｓｉｏｎ  １．０，  ２００７．）に示されたＳ−ｂｏｘなどがこのような手法に基づいて生成されたＳ−ｂｏｘだと考えることができる。
【００７０】
それぞれの構造を図１１〜図１５に示す。これらの構造は、前述のようにランダムに大きなＳ−ｂｏｘを生成した場合と比較して、テーブルサイズが小さくなり、ハードウェアの実装コストは小さくなる。
【００７１】
図１１は、８ビットの入力データの非線形変換処理を実行する構成である。
４ビットデータの非線形変換処理を実行する３つのＳ−ｂｏｘ：Ｓ４０，Ｓ４１，Ｓ４２、
各Ｓ−ｂｏｘの出力４ビットと他の４ビットとの排他的論理和演算を実行する３つの配置的論理演算部を有する。
８ビットの入力データは、左ライン入力と、右ライン入力にそれぞれ４ビットずつ入力される。
３つのＳ−ｂｏｘ：Ｓ４０，Ｓ４１，Ｓ４２を利用した非線形変換結果としての８ビットデータは、左ライン出力と右ライン出力からそれぞれ４ビットずつ出力される。
【００７２】
処理は以下の処理シーケンスに従って実行される。
（１）入力８ビット中の４ビット（右ライン入力）を、第１段のＳ−ｂｏｘ：Ｓ４０に入力し、非線形変換を実行する。
この非線形変換結果と、入力８ビット中の他の４ビット（左ライン入力）とを排他的論理和演算する。
【００７３】
（２）この排他的論理和演算結果を、第２段のＳ−ｂｏｘ：Ｓ４１に入力し、非線形変換を実行する。
この非線形変換結果と、入力８ビット中の４ビット（右ライン入力）とを排他的論理和演算する。
排他的論理和演算結果を、出力８ビットの４ビット（右ライン出力）として出力する。
【００７４】
（３）さらに、この排他的論理和演算結果を、第３段のＳ−ｂｏｘ：Ｓ４２に入力し、非線形変換を実行する。
この非線形変換結果と、上記処理（１）における排他的論理和演算結果とを排他的論理和演算し、この結果を出力８ビットの４ビット（Ｏｕｔ−ａ）として出力する。
図１１は、上記の処理によって、８ビットの入力データの非線形変換処理を実行する構成である。
【００７５】
図１２に示す構成は、
４ビットデータの非線型変換を実行するＳ−ｂｏｘ：Ｓ４０，Ｓ４１、
各Ｓ−ｂｏｘの出力４ビットに対して、２〜３ビット単位の排他的論理和演算を実行する演算実行部、
演算実行部の出力に対して、先のＳ−ｂｏｘ：Ｓ４０，Ｓ４１の逆演算を実行する非線形変換部：Ｓ４１−１，Ｓ４０−１、
これらによって構成される。
【００７６】
図１３に示す構成は、
４ビットデータの非線型変換を実行するＳ−ｂｏｘ：Ｓ４０，Ｓ４２、
Ｓ−ｂｏｘ：Ｓ４１の逆演算を実行する非線形変換部：Ｓ４１−１、
複数の排他的論理和演算部、
これらの組み合わせによって構成された非線形変換処理構成である。
【００７７】
図１４は、
４ビットデータの非線型変換を実行するＳ−ｂｏｘ：Ｓ４０，Ｓ４１，Ｓ４２、
複数の排他的論理和演算部、
複数のＯＲ演算部、
これらの組み合わせによって構成された非線形変換処理構成である。
【００７８】
図１５は、
４ビットデータの非線型変換を実行するＳ−ｂｏｘ：ＳＳ０，ＳＳ１，ＳＳ２，ＳＳ３、
２×２の行列（ＭＤＳ行列）を適用したデータ変換を実行する行列変換実行部、
これらの組み合わせによって構成された非線形変換処理構成である。
【００７９】
このように、図１１〜図１５に示す小さなＳ−ｂｏｘをベースにした大きなＳ−ｂｏｘの構成法は従来からいくつか提案されている。このような構成は、ランダムに大きなＳ−ｂｏｘを生成した場合と比較して、テーブルサイズが小さくなり、ハードウェアの実装コストは小さくなる。
しかし、このように従来の小さなＳ−ｂｏｘをベースにした構成法では、小さなＳ−ｂｏｘの設計法、および小さなＳ−ｂｏｘの組み合わせ法、それぞれについて以下のような問題がある。
【００８０】
（問題点１）  それぞれの小さなＳ−ｂｏｘの設計に関して
従来法では，それぞれの小さなＳ−ｂｏｘはランダムに作成している。よって、それら小さなＳ−ｂｏｘはテーブル実装する必要があり、ハードウェア実装に必要な回路規模は依然大きくなってしまう。
【００８１】
（問題点２）  小さなＳ−ｂｏｘの組み合わせ方法に関して
従来法は単純な繰り返し構造を持っていないため、複数サイクルをかけてＳ−ｂｏｘを実行する場合でも、回路の共有化が難しい。単純な繰り返し構造を持つ場合は、回路の共有化が可能であり、実行に複数サイクルが必要になるものの必要な回路規模を小さくできる可能性がある。しかしながら、従来法ではこのような実装手法を行うメリットは少なく、複数サイクルを使えたとしても回路規模を削減することが難しい。
【００８２】
［３．本開示に係るＳ−ｂｏｘについて］
以上のような問題点を鑑み、以下では、高い安全性を持ち、かつハードウェア実装を行う際に回路規模を従来法と比較して小さくできるＳ−ｂｏｘの構成法を提案する。
以下において説明する構成は、ハードウェア実装において、実行スループットよりも実装に必要な回路規模を小さくすることが求められるような場合に特に高い効果を発揮する。なお、以降の説明では簡単のためにｎ−ｂｉｔ入出力の全単射Ｓ−ｂｏｘのみについて説明する。
【００８３】
以下の２つのＳ−ｂｏｘ構成例について、順次説明する。
（１）論理演算とビット置換の繰り返し構造による安全でかつ少ない回路で実装することが可能なＳ−ｂｏｘの構成法
（２）小さいサイズのＳ−ｂｏｘをベースとした，安全で，かつ少ない回路で実装することが可能な繰り返し構造を持つより大きなサイズのＳ−ｂｏｘの構成法
【００８４】
なお、上記の（１）は、前述の（問題点１）を解決し、（２）は（問題点２）を解決することが可能な構成である。
（１）と、（２）を組み合わせた構成も可能であり、この組み合わせ構成によって、（問題点１，２）の両方を解決することが可能である。
【００８５】
（３−１．論理演算とビット置換の繰り返し構造によるＳ−ｂｏｘの構成法）
まず、
（１）論理演算とビット置換の繰り返し構造による安全でかつ少ない回路で実装することが可能なＳ−ｂｏｘの構成法
について説明する。
【００８６】
（３−１−１．Ｓ−ｂｏｘの構成の概要）
Ｓ−ｂｏｘは、様々な論理回路の組み合わせによって実現できる。
ここで、提案するＳ−ｂｏｘは、ＡＮＤ（論理積）、ＯＲ（論理和）、ＮＯＴ（論理否定）等の基本論理演算を基にした"非線形演算部"と、ビット位置の入れ替えを行う"ビット置換部"の２つの部分を基本的な要素として、これらの繰り返しによりＳ−ｂｏｘを構成するものである。
【００８７】
非線形演算部は、全単射かつ非線形変換になるように、１つの２ビット入力１ビット出力のＮＡＮＤ（否定論理積）、もしくはＮＯＲ（否定論理和）演算と、１つの２ビット入力１ビット出力のＸＯＲ（排他的論理和）、もしくはＸＮＯＲ（否定排他的論理和）演算をそれぞれ用い、任意の２ビットに対しＮＡＮＤ、もしくはＮＯＲ演算を行った結果を、その２ビット以外の１ビットとＸＯＲ、もしくはＸＮＯＲ演算する構造を有する。
【００８８】
ビット置換部は単純にビット位置の入れ変えを行う。
これら非線形演算部、ビット置換部を複数回繰り返すことにより、Ｓ−ｂｏｘを生成する。
非線形演算部、ビット置換部は繰り返すごとに変更しても同じものを使用しても構わない。
【００８９】
一般的に、安全なｎ−ｂｉｔ  Ｓ−ｂｏｘを構成するためには，ｎ回以上の非線形演算部分の繰り返しが必要なため，ｎ回の繰り返し構造がこの構成法において安全性を大きく損なわない範囲での最小の構成だと考えられる．また，最終回のビット置換部は安全性，回路規模ともに影響を与えないため，実行せずに省略することも可能である。
【００９０】
なお、非線形演算部は、前述したように、ＮＡＮＤまたはＮＯＲ演算部と、ＸＯＲまたはＸＮＯＲ演算部から構成されるが、ｎ回繰り返し構造中において、ＸＯＲ演算部と、ＸＮＯＲ演算部とを混在させることで、非線形変換処理における不動点をなくすことが可能となる。従って、不動点を発生させない非線形変換処理を実現するためには、非線形演算部のｎ回繰り返し構造中において、ＸＯＲ演算部と、ＸＮＯＲ演算部とを混在させる構成とすることが好ましい。
【００９１】
（３−１−２．本手法の効果について）
本手法の効果には以下の３つ効果（効果１〜３）がある。１つめは既存の技術の（問題点１）を解決し、残りの２つは更なる本発明のアドバンテージである。
【００９２】
（効果１）従来法より小さな回路で実装することができる。
非線形演算部１つは、１つのＮＡＮＤ、もしくはＮＯＲ演算、および１つのＸＯＲ、もしくはＸＮＯＲ演算のみで構成されている。
ＮＡＮＤ／ＮＯＲ演算は入力に対して非線形な処理を行う非線形な基本論理演算のなかでも小さな回路で実装できることが知られている。
このＮＡＮＤ／ＮＯＲ演算以外は全単射性を担保するためのＸＯＲ／ＸＮＯＲ演算しか用いていない．よって，この非線形演算部分は全単射な非線形関数の中で，ハードウェアの実装コスト（必要回路規模）が最小クラスであると言える。
さらに、ビット置換部はハードウェア実装では配線の変更のみで実装可能であり、必要回路規模に影響を与えない。つまり、ハードウェア実装コスト（必要回路規模）はゼロであると言える。
【００９３】
本構成は、これら非線形演算部、ビット置換部の繰り返しで構成されているため、実装に必要な回路は従来法に比べて大きく削減できる。
【００９４】
（効果２）ハードウェア実装コストを正確に見積もることができる。
従来法では、ランダムにＳ−ｂｏｘを生成していたため、必要回路規模を見積もる際は，論理合成ツールなどを用いて毎回評価を行う必要があった。
【００９５】
本構成法の場合、論理演算子の数、つまり繰り返し回数を評価することにより、ハードウェア実装コスト（必要回路規模）を論理合成ツールなどを用いることなく容易に見積もることができる。従来では必要回路規模見積もりに時間がかかるため多くのＳ−ｂｏｘの中から最適なものを見つけ出すことは難しかったが、本構成では容易に回路規模を見積もれるため最適なＳ−ｂｏｘを容易に選択できることになる。
【００９６】
（効果３）同じハードウェア実装コスト（必要回路規模）のＳ−ｂｏｘを複数種類構成可能である。
非線形演算部で用いる論理演算子と、ビット置換部で使用するビット置換の種類は選択の自由度があり、かつ繰り返し毎に種類が異なってもよいため、必要な回路規模が同じとなる複数個のＳ−ｂｏｘを構成することができる。
これは、上位関数やほかの関数との組み合わせで最適なものを、同じハードウェア実装コスト（必要回路規模）のＳ−ｂｏｘから選択できることに寄与する。
【００９７】
（３−１−３．具体的な構成例について）
次に、論理演算とビット置換の繰り返し構造によるＳ−ｂｏｘの具体的な構成例について説明する。
４ビットの場合のＳ−ｂｏｘの具体的な構成例を図１６に示す。
【００９８】
この図１６に示す４ビットＳ−ｂｏｘは、非線形演算部とビット置換部の組み合わせ構成の４段繰り返し構造を有しており、非線形演算部は、４つのＮＡＮＤと３つのＸＯＲ、１つのＸＮＯＲから構成されている。なお、図においては最終段のビット置換は省略しているが、最終段のビット置換については設定する構成としても、省略した構成としても、いずれの構成も可能である。
【００９９】
１段目の非線形演算部は、ＮＡＮＤとＸＮＯＲによって構成されている。
入力４ビット中の２ビットを１段目のＮＡＮＤに入力し、その出力ビットを１段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
１段目のＸＮＯＲ演算の実行結果は、出力ビットに設定され、さらに３〜４段目の非線型部分のＮＡＮＤに入力される。
【０１００】
２段目の非線形演算部は、ＮＡＮＤとＸＯＲによって構成されている。
入力４ビット中の２ビットを２段目のＮＡＮＤに入力し、その出力ビットを２段目のＸＯＲに入力して、入力４ビット中の１ビットとＸＯＲ演算を実行する。
２段目のＸＯＲ演算の実行結果は、出力ビットに設定され、さらに４段目の非線型部分のＮＡＮＤに入力される。
【０１０１】
３段目の非線形演算部は、ＮＡＮＤとＸＯＲによって構成されている。
入力４ビット中の１ビットと、１段目のＸＮＯＲ演算の実行結果を３段目のＮＡＮＤに入力し、その出力ビットを３段目のＸＯＲに入力して、入力４ビット中の１ビットとＸＯＲ演算を実行する。
３段目のＸＯＲ演算の実行結果は、出力ビットに設定される。
【０１０２】
４段目の非線形演算部は、ＮＡＮＤとＸＯＲによって構成されている。
１段目のＸＮＯＲ演算の実行結果と、２段目のＸＯＲ演算の実行結果を４段目のＮＡＮＤに入力し、その出力ビットを４段目のＸＯＲに入力して、入力４ビット中の１ビットとＸＯＲ演算を実行する。
４段目のＸＯＲ演算の実行結果は、出力ビットに設定される。
【０１０３】
この４ビットＳ−ｂｏｘは、前述の項目［２．Ｓ−ｂｏｘについて］において説明した安全性の高いＳ−ｂｏｘの条件である最大差分確率，最大線形確率がともに２−２である。これは４ビットＳ−ｂｏｘにおいて最適な値であり、ランダムに生成した４ビットＳ−ｂｏｘと比較してハードウェア実装コストは小さくなる。
【０１０４】
よって、この４ビットＳ−ｂｏｘは、安全でかつハードウェア実装性能にも優れていると言える。
同じ最適な差分確率、線形確率をもち、かつ同じ回路規模（同じ繰り返し回数）で構成される他のＳ−ｂｏｘの具体例を図１７〜図２０に示す。図１６〜図２０に示す例では最終段のビット置換は省略しているが、最終段のビット置換については設定する構成としても、省略した構成としても、いずれの構成も可能である。
【０１０５】
図１７に示す４ビットＳ−ｂｏｘは、４つのＮＯＲと、３つのＸＮＯＲ、１つのＸＯＲから構成されている。
図１８に示す４ビットＳ−ｂｏｘは、３つのＮＡＮＤと、１つのＮＯＲと、３つのＸＮＯＲ、１つのＸＯＲから構成されている。
図１９に示す４ビットＳ−ｂｏｘは、３つのＮＡＮＤと、１つのＮＯＲと、３つのＸＮＯＲ、１つのＸＯＲから構成されている。
図２０に示す４ビットＳ−ｂｏｘは、４つのＮＯＲと、１つのＸＮＯＲ、３つのＸＯＲから構成されている。
【０１０６】
各図に示す４ビットＳ−ｂｏｘの構成と処理について説明する。
図１７に示す４ビットＳ−ｂｏｘは、非線形演算部とビット置換部の組み合わせ構成の４段繰り返し構造を有しており、非線形処理部分は、４つのＮＯＲと、３つのＸＮＯＲ、１つのＸＯＲから構成されている。なお、図においては最終段のビット置換は省略しているが、最終段のビット置換については設定する構成としても、省略した構成としても、いずれの構成も可能である。
【０１０７】
１段目の非線形演算部は、ＮＯＲとＸＮＯＲによって構成されている。
入力４ビット中の２ビットを１段目のＮＯＲに入力し、その出力ビットを１段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
１段目のＸＮＯＲ演算の実行結果は、出力ビットに設定され、さらに３〜４段目の非線型部分のＮＯＲに入力される。
【０１０８】
２段目の非線形演算部は、ＮＯＲとＸＮＯＲによって構成されている。
入力４ビット中の２ビットを２段目のＮＯＲに入力し、その出力ビットを２段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
２段目のＸＮＯＲ演算の実行結果は、出力ビットに設定され、さらに４段目の非線型部分のＮＯＲに入力される。
【０１０９】
３段目の非線形演算部は、ＮＯＲとＸＮＯＲによって構成されている。
入力４ビット中の１ビットと、１段目のＸＮＯＲ演算の実行結果を３段目のＮＯＲに入力し、その出力ビットを３段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
３段目のＸＮＯＲ演算の実行結果は、出力ビットに設定される。
【０１１０】
４段目の非線形演算部は、ＮＯＲとＸＯＲによって構成されている。
１段目のＸＮＯＲ演算の実行結果と、２段目のＸＮＯＲ演算の実行結果を４段目のＮＯＲに入力し、その出力ビットを４段目のＸＯＲに入力して、入力４ビット中の１ビットとＸＯＲ演算を実行する。
４段目のＸＯＲ演算の実行結果は、出力ビットに設定される。
【０１１１】
図１８に示す４ビットＳ−ｂｏｘは、非線形演算部とビット置換部の組み合わせ構成の４段繰り返し構造を有しており、非線形処理部分は、３つのＮＡＮＤと、１つのＮＯＲと、３つのＸＮＯＲ、１つのＸＯＲから構成されている。なお、図においては最終段のビット置換は省略しているが、最終段のビット置換については設定する構成としても、省略した構成としても、いずれの構成も可能である。
【０１１２】
１段目の非線形演算部は、ＮＡＮＤとＸＮＯＲによって構成されている。
入力４ビット中の２ビットを１段目のＮＡＮＤに入力し、その出力ビットを１段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
１段目のＸＮＯＲ演算の実行結果は、出力ビットに設定され、さらに３〜４段目の非線型部分のＮＯＲとＮＡＮＤに入力される。
【０１１３】
２段目の非線形演算部は、ＮＡＮＤとＸＯＲによって構成されている。
入力４ビット中の２ビットを２段目のＮＡＮＤに入力し、その出力ビットを２段目のＸＯＲに入力して、入力４ビット中の１ビットとＸＯＲ演算を実行する。
２段目のＸＯＲ演算の実行結果は、出力ビットに設定され、さらに４段目の非線型部分のＮＡＮＤに入力される。
【０１１４】
３段目の非線形演算部は、ＮＯＲとＸＮＯＲによって構成されている。
入力４ビット中の１ビットと、１段目のＸＮＯＲ演算の実行結果を３段目のＮＯＲに入力し、その出力ビットを３段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
３段目のＸＮＯＲ演算の実行結果は、出力ビットに設定される。
【０１１５】
４段目の非線形演算部は、ＮＡＮＤとＸＮＯＲによって構成されている。
１段目のＸＮＯＲ演算の実行結果と、２段目のＸＯＲ演算の実行結果を４段目のＮＡＮＤに入力し、その出力ビットを４段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
４段目のＸＮＯＲ演算の実行結果は、出力ビットに設定される。
【０１１６】
図１９に示す４ビットＳ−ｂｏｘは、非線形演算部とビット置換部の組み合わせ構成の４段繰り返し構造を有しており、非線形処理部分は、３つのＮＡＮＤと、１つのＮＯＲと、３つのＸＮＯＲ、１つのＸＯＲから構成されている。なお、図においては最終段のビット置換は省略しているが、最終段のビット置換については設定する構成としても、省略した構成としても、いずれの構成も可能である。
【０１１７】
１段目の非線形演算部は、ＮＡＮＤとＸＯＲによって構成されている。
入力４ビット中の２ビットを１段目のＮＡＮＤに入力し、その出力ビットを１段目のＸＯＲに入力して、入力４ビット中の１ビットとＸＯＲ演算を実行する。
１段目のＸＯＲ演算の実行結果は、出力ビットに設定され、さらに２〜３段目の非線型部分のＮＯＲとＮＡＮＤに入力される。
【０１１８】
２段目の非線形演算部は、ＮＯＲとＸＮＯＲによって構成されている。
入力４ビット中の１ビットと、１段目のＸＯＲ演算の実行結果を２段目のＮＯＲに入力し、その出力ビットを２段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
２段目のＸＮＯＲ演算の実行結果は、出力ビットに設定され、さらに４段目の非線型部分のＮＡＮＤに入力される。
【０１１９】
３段目の非線形演算部は、ＮＡＮＤとＸＮＯＲによって構成されている。
入力４ビット中の１ビットと、１段目のＸＮＯＲ演算の実行結果を３段目のＮＡＮＤに入力し、その出力ビットを３段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
３段目のＸＮＯＲ演算の実行結果は、出力ビットに設定される。
【０１２０】
４段目の非線形演算部は、ＮＡＮＤとＸＮＯＲによって構成されている。
２段目のＸＮＯＲ演算の実行結果と、３段目のＸＮＯＲ演算の実行結果を４段目のＮＡＮＤに入力し、その出力ビットを４段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
４段目のＸＮＯＲ演算の実行結果は、出力ビットに設定される。
【０１２１】
図２０に示す４ビットＳ−ｂｏｘは、非線形演算部とビット置換部の組み合わせ構成の４段繰り返し構造を有しており、非線形処理部分は、４つのＮＯＲと、１つのＸＮＯＲ、３つのＸＯＲから構成されている。なお、図においては最終段のビット置換は省略しているが、最終段のビット置換については設定する構成としても、省略した構成としても、いずれの構成も可能である。
【０１２２】
１段目の非線形演算部は、ＮＯＲとＸＯＲによって構成されている。
入力４ビット中の２ビットを１段目のＮＯＲに入力し、その出力ビットを１段目のＸＯＲに入力して、入力４ビット中の１ビットとＸＯＲ演算を実行する。
１段目のＸＯＲ演算の実行結果は、出力ビットに設定され、さらに３〜４段目の非線型部分のＮＯＲに入力される。
【０１２３】
２段目の非線形演算部は、ＮＯＲとＸＯＲによって構成されている。
入力４ビット中の２ビットを２段目のＮＯＲに入力し、その出力ビットを２段目のＸＯＲに入力して、入力４ビット中の１ビットとＸＯＲ演算を実行する。
２段目のＸＯＲ演算の実行結果は、出力ビットに設定され、さらに４段目の非線型部分のＮＯＲに入力される。
【０１２４】
３段目の非線形演算部は、ＮＯＲとＸＮＯＲによって構成されている。
入力４ビット中の１ビットと、１段目のＸＯＲ演算の実行結果を３段目のＮＯＲに入力し、その出力ビットを３段目のＸＮＯＲに入力して、入力４ビット中の１ビットとＸＮＯＲ演算を実行する。
３段目のＸＮＯＲ演算の実行結果は、出力ビットに設定される。
【０１２５】
４段目の非線形演算部は、ＮＯＲとＸＯＲによって構成されている。
１段目のＸＯＲ演算の実行結果と、２段目のＸＯＲ演算の実行結果を４段目のＮＯＲに入力し、その出力ビットを４段目のＸＯＲに入力して、入力４ビット中の１ビットとＸＯＲ演算を実行する。
４段目のＸＯＲ演算の実行結果は、出力ビットに設定される。
【０１２６】
また、上記の例で示した４ビットＳ−ｂｏｘと同じ回路規模で実装することができる４ビットＳ−ｂｏｘは、非線形演算部の演算が４（＝２ｘ２）種類，ビット置換部のビット置換が２４（＝４！）種類あり、さらに繰り返し毎に種類が異なってもよいため、９６の４乗通り存在することが分かる。
【０１２７】
つまり、同じ回路規模の４ビットＳ−ｂｏｘを数多く構成できるため、設計の際に目的に応じた最適なＳ−ｂｏｘを選択することができる。
【０１２８】
もう一つのＳ−ｂｏｘの構成例として、５ビットＳ−ｂｏｘの構成例を図２１に示す。
図２１に示す５ビットＳ−ｂｏｘは、非線形演算部とビット置換部の組み合わせ構成の５段繰り返し構造を有しており、非線形演算部は、５つのＮＡＮＤと４つのＸＯＲ、１つのＸＮＯＲから構成されている。なお、図においては最終段のビット置換は省略しているが、最終段のビット置換については設定する構成としても、省略した構成としても、いずれの構成も可能である。
【０１２９】
１段目の非線形演算部は、ＮＡＮＤとＸＯＲによって構成されている。
入力５ビット中の２ビットを１段目のＮＡＮＤに入力し、その出力ビットを１段目のＸＯＲに入力して、入力５ビット中の１ビットとＸＯＲ演算を実行する。
１段目のＸＯＲ演算の実行結果は、出力ビットに設定され、さらに４〜５段目の非線型部分のＮＡＮＤに入力される。
【０１３０】
２段目の非線形演算部は、ＮＡＮＤとＸＮＯＲによって構成されている。
入力５ビット中の２ビットを２段目のＮＡＮＤに入力し、その出力ビットを２段目のＸＮＯＲに入力して、入力５ビット中の１ビットとＸＮＯＲ演算を実行する。
２段目のＸＮＯＲ演算の実行結果は、出力ビットに設定され、さらに５段目の非線型部分のＮＡＮＤに入力される。
【０１３１】
３段目の非線形演算部は、ＮＡＮＤとＸＯＲによって構成されている。
入力５ビット中の２ビットを３段目のＮＡＮＤに入力し、その出力ビットを３段目のＸＯＲに入力して、入力５ビット中の１ビットとＸＯＲ演算を実行する。
３段目のＸＯＲ演算の実行結果は、出力ビットに設定される。
【０１３２】
４段目の非線形演算部は、ＮＡＮＤとＸＯＲによって構成されている。
入力５ビット中の１ビットと、１段目のＸＯＲ演算の実行結果を４段目のＮＡＮＤに入力し、その出力ビットを４段目のＸＯＲに入力して、入力５ビット中の１ビットとＸＯＲ演算を実行する。
４段目のＸＯＲ演算の実行結果は、出力ビットに設定される。
【０１３３】
５段目の非線形演算部は、ＮＡＮＤとＸＯＲによって構成されている。
１段目のＸＯＲ演算の実行結果と、２段目のＸＮＯＲ演算の実行結果を５段目のＮＡＮＤに入力し、その出力ビットを５段目のＸＯＲに入力して、入力５ビット中の１ビットとＸＯＲ演算を実行する。
５段目のＸＯＲ演算の実行結果は、出力ビットに設定される。
【０１３４】
この５ビットＳ−ｂｏｘの差分確率と線形確率は共に２−２である。５ビットＳ−ｂｏｘの各々の最適な値は２−４であるため、最も安全性の高いものではないが、回路規模はランダムに作成したものと比較して非常に小さくなる。そのため、実装性能を優先したい場合には、適している。
【０１３５】
（３−２．小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの構成法）
次に、小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの構成法について説明する。
【０１３６】
小さいサイズのＳ−ｂｏｘから大きなサイズのＳ−ｂｏｘを構成する際に，特定の関数の繰り返し構造になるように構成する。具体的には、まず小さいサイズのＳ−ｂｏｘからハードウェア実装コスト（必要回路規模）の比較的小さい、大きなＳ−ｂｏｘを生成し、その大きなＳ−ｂｏｘを繰り返す構造を有する。これにより、小さいＳ−ｂｏｘから、繰り返し構造を持った大きなＳ−ｂｏｘを構成することができる。
【０１３７】
（３−２−２．本手法の効果について）
本手法は，Ｈ／Ｗ実装，特に必要回路規模を削減することを目的とした実装、例えばシリアル実装をした際に利点が大きい。
繰り返し構造を持っている演算に関しては、シリアル実装でＳ−ｂｏｘを実装する際にすべての要素を実装する必要がなく、繰り返し単位を実装し、それを任意回反復実行すればよい。
よって、この構造は、繰り返し構造を持たない従来のＳ−ｂｏｘに対して、より少ない回路規模で実装できると言える。
【０１３８】
（３−２−３．具体的な構成例について）
次に、小さいＳ−ｂｏｘを用いた繰り返し処理による大きなＳ−ｂｏｘの具体的な構成例について、説明する。
以下、具体的な構成法について詳細に述べる。
なお、以下に説明する図２２〜図２８において、各図にＳとして示す矩形領域が、例えば図１６〜図２１を参照して説明した小さなＳ−ｂｏｘ、すなわち例えば４ビット単位の非線形変換処理を実行するＳ−ｂｏｘである。
【０１３９】
図２２〜図２８は、いずれも、入力ｎビットを４つのｎ／４ビットに分割して４つのラインに入力し、各ラインデータに対して小さなＳ−ｂｏｘとＸＯＲ回路からなる演算実行部による演算処理と、各ラインデータ単位のローテーション（Ｒｏｔａｔｉｏｎ）実行部によるローテーションを複数段、繰り返し実行する構成を持つ。
【０１４０】
図２２に示す構成は、各段において１つのＳ−ｂｏｘと１つのＸＯＲ回路の適用構成を持ち、先行する処理段において、ｎ／４ビットのＳ−ｂｏｘとＸＯＲ回路の適用結果を生成し、このｎ／４ビットの演算結果と、その他の未処理データに対して、ｎ／４ビットのライン単位データのローテーションを行い、ローテーション結果を次の処理段に出力する構成を持つ。
【０１４１】
図２３に示す構成は、各段において２つのＳ−ｂｏｘと２つのＸＯＲ回路の適用構成を持ち、先行する処理段において、ｎ／４ビットのＳ−ｂｏｘとＸＯＲ回路の適用結果を２ライン分（２×（ｎ／４）ビット）生成し、この２ラインの演算結果と、その他の２ラインの未処理データに対して、ｎ／４ビットのライン単位データのローテーションを行い、ローテーション結果を次の処理段に出力する構成を持つ。
【０１４２】
図２４に示す構成は、各段において１つのＳ−ｂｏｘと２つのＸＯＲ回路の適用構成を持ち、先行する処理段において、
ｎ／４ビットのＳ−ｂｏｘの適用結果と、
ｎ／４ビットのＳ−ｂｏｘとＸＯＲ回路の適用結果と、
ｎ／４ビットのＸＯＲ回路の適用結果、
を生成し、これらの３つのｎ／４ビットの演算結果と、その他の未処理データに対して、ｎ／４ビットのライン単位データのローテーションを行い、ローテーション結果を次の処理段に出力する構成を持つ。
【０１４３】
図２５に示す構成は、各段において２つのＳ−ｂｏｘと２つのＸＯＲ回路の適用構成を持ち、先行する処理段において、
２つのｎ／４ビットのＳ−ｂｏｘの適用結果と、
２つのｎ／４ビットのＳ−ｂｏｘとＸＯＲ回路の適用結果と、
を生成し、これらの４つのｎ／４ビットの演算結果に対して、ｎ／４ビットのライン単位データのローテーションを行い、ローテーション結果を次の処理段に出力する構成を持つ。
【０１４４】
図２６に示す構成は、各段において１つのＳ−ｂｏｘと２つのＸＯＲ回路の適用構成を持ち、先行する処理段において、
ｎ／４ビットのＳ−ｂｏｘとＸＯＲ回路の適用結果と、
ｎ／４ビットのＸＯＲ回路の適用結果、
を生成し、これらの２つのｎ／４ビットの演算結果と、その他の未処理データに対して、ｎ／４ビットのライン単位データのローテーションを行い、ローテーション結果を次の処理段に出力する構成を持つ。
【０１４５】
図２７に示す構成は、各段において２つのＳ−ｂｏｘと２つのＸＯＲ回路の適用構成を持ち、先行する処理段において、
２つのｎ／４ビットのＳ−ｂｏｘとＸＯＲ回路の適用結果、
を生成し、これらの２つのｎ／４ビットの演算結果と、その他の未処理データに対して、ｎ／４ビットのライン単位データのローテーションを行い、ローテーション結果を次の処理段に出力する構成を持つ。
【０１４６】
図２８に示す構成は、各段において２つのＳ−ｂｏｘと２つのＸＯＲ回路の適用構成を持ち、先行する処理段において、
ｎ／４ビットのＳ−ｂｏｘの適用結果と、
ｎ／４ビットのＳ−ｂｏｘとＸＯＲ回路の適用結果と、
ｎ／４ビットのＸＯＲ回路の適用結果、
を生成し、これらの３つのｎ／４ビットの演算結果と、その他の未処理データに対して、ｎ／４ビットのライン単位データのローテーションを行い、ローテーション結果を次の処理段に出力する構成を持つ。
【０１４７】
図２２、図２３はそれぞれ、
ｔｙｐｅ−ＩＧＦＮ（Ｇｅｎｅｒａｌｉｚｅｄ  Ｆｅｉｓｔｅｌ  Ｎｅｔｗｏｒｋ）、
ｔｙｐｅ−ＩＩＧＦＮ、
と呼ばれる繰り返し構造である。
【０１４８】
これらは通常小さな非線形部分に作用する秘密鍵とともに用いられるが、本実施例においては実装効率を考慮して秘密鍵を挿入しない。
このように秘密鍵を用いずに構成することで全体をひとつの固定テーブルとして実装することも可能になる。
【０１４９】
図２２、図２３の構成の違いは各段の小さなＳ−ｂｏｘの数である。
図２２のｔｙｐｅ−ＩＧＦＮは、各段が１つのｎビットＳ−ｂｏｘとｎビットのＸＯＲ、ｎビット単位のＲｏｔａｔｉｏｎから構成される。
【０１５０】
図２２に示す例では入力データはｎビットであり４分割されｎ／４ビット単位で各ラインに入力されている。
なお、入力データの分割数は任意である。すなわち、任意のｒ分割（ｒ＞２）への拡張が可能であり、必要な大きなＳ−ｂｏｘの入出力サイズに応じて適時決定することができる。
【０１５１】
図２３に示すｔｙｐｅ−ＩＩＧＦＮは、各段単位で、２つの小さなｎビットＳ−ｂｏｘとｎビットのＸＯＲ、ｎビット単位のＲｏｔａｔｉｏｎで構成される。
これらの２つの構成方法の特徴は、順方向からの演算と逆方向からの演算がほとんど同じであり、違いはＲｏｔａｔｉｏｎ部分のみとなっている。
【０１５２】
これにより、順関数と逆関数を両方実装する必要がある場合、回路の共有化が行える。図２３の構成法において、図１６の４ビットＳ−ｂｏｘを用い、１６ビットＳ−ｂｏｘを生成した場合は、
６回繰り返しで最大差分確率は２−８．３，
最大線形確率は２−７．８３であり，
７回繰り返しで最大差分確率は２−９．１，
最大線形確率は２−８になる。
これらの値は１６−ｂｉｔで最適な値ではないが、十分低い確率であり、回路規模はランダムに作成したものと比べて非常に小さくなる。
【０１５３】
図２４〜図２８は、図２２，図２３の構造とは異なる部分に小さなＳ−ｂｏｘを配置した構造である。各々の違いはその配置場所と繰り返し単位でのＳ−ｂｏｘの数のみである。
【０１５４】
これらの構造では、小さなＳ−ｂｏｘに入力されるデータが、その後の演算では不要となるため、余計な記憶領域は不要であり、繰り返し関数をさらに細かく分割して実装した場合にハードウェアで必要な回路規模をさらに小さくすることが可能である。
【０１５５】
図２５の構成法で、図１７を参照して説明した４ビットＳ−ｂｏｘを用い、１６ビットＳ−ｂｏｘを構成した場合は、
６回繰り返しで最大差分確率は２−８．３，
最大線形確率は２−８であり、
７回繰り返しで、最大差分確率は２−９．１，
最大線形確率は２−８．５であり、
１６−ｂｉｔで最適な値ではないが、十分低い確率であり、回路規模はランダムに作成したものと比べて非常に小さくなる。
【０１５６】
［４．暗号処理装置の構成例について］
最後に、上述した実施例に従った暗号処理を実行する暗号処理装置の実相例について説明する。
上述した実施例に従った暗号処理を実行する暗号処理装置は、暗号処理を実行する様々な情報処理装置に搭載可能である。具体的には、ＰＣ、ＴＶ、レコーダ、プレーヤ、通信機器、さらに、ＲＦＩＤ、スマートカード、センサネットワーク機器、デンチ／バッテリー認証モジュール、健康、医療機器、自立型ネットワーク機器等、例えばデータ処理や通信処理に伴う暗号処理を実行する様々な危機において利用可能である。
【０１５７】
本開示の暗号処理を実行する装置の一例としてのＩＣモジュール７００の構成例を図２９に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図２９に示すＩＣモジュール７００は、これら様々な機器に構成することが可能である。
【０１５８】
図２９に示すＣＰＵ(Central processing Unit)７０１は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ７０２は、ＣＰＵ７０１が実行するプログラム、あるいは演算パラメータなどの固定データを格納するＲＯＭ（Read-Only-Memory）、ＣＰＵ７０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるＲＡＭ（Random Access Memory）等からなる。また、メモリ７０２は暗号処理に必要な鍵データや、暗号処理において適用する変換テーブル（置換表）や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【０１５９】
暗号処理部７０３は、上記において説明した暗号処理構成、すなわち、例えば一般化Ｆｅｉｓｔｅｌ構造や、Ｆｅｉｓｔｅｌ構造を適用した共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理を実行する。
【０１６０】
なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭに格納し、ＣＰＵ７０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。
【０１６１】
乱数発生器７０４は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【０１６２】
送受信部７０５は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ＩＣモジュールとのデータ通信を実行し、ＩＣモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【０１６３】
なお、上述した実施例において説明したデータ処理装置は、入力データとしての平文を暗号化する暗号化処理に適用可能であるのみならず、入力データとしての暗号文を平文に復元する復号処理にも適用可能である。
暗号化処理、復号処理、双方の処理において、上述した実施例において説明した構成を持つ非線形変換部の構成を適用することが可能である。
【０１６４】
［５．本開示の構成のまとめ］
以上、特定の実施例を参照しながら、本開示の実施例について詳解してきた。しかしながら、本開示の要旨を逸脱しない範囲で当業者が実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本開示の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０１６５】
なお、本明細書において開示した技術は、以下のような構成をとることができる。
（１）  データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対するデータ変換処理を繰り返し実行するデータ変換処理部を有し、
前記データ変換処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部を有し、
前記Ｆ関数実行部は、
非線形変換処理を実行する非線形変換処理部を有し、
前記非線形変換処理部は、
１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる非線形演算部と、
ビット置換部と、
の繰り返し構造を有するデータ処理装置。
【０１６６】
（２）前記ビット置換部は、前記非線形演算部に対する入出力ビットを入れ替える配線構成を有する前記（１）に記載のデータ処理装置。
（３）前記非線形変換処理部は、２ビット入力１ビット出力のＮＡＮＤまたはＮＯＲ演算部における演算結果としての１ビットを、前記ＸＯＲまたはＸＮＯＲ演算部に出力して、他の入力１ビットデータとのＸＯＲまたはＸＮＯＲ演算を実行し、ＸＯＲまたはＸＮＯＲ演算結果として生成した１ビットデータを非線形変換処理結果の構成ビットとして出力する前記（１）または（２）に記載のデータ処理装置。
【０１６７】
（４）前記非線形変換処理部は、ｎビットデータの非線型変換結果を出力する構成において、前記非線形演算部を、ｎ回以上繰り返す繰り返し構造を有する前記（１）〜（３）いずれかに記載のデータ処理装置。
（５）前記非線形変換処理部は、ｎビットデータの非線型変換結果を出力する構成において、前記非線形演算部をｎ回、前記ビット置換部をｎ回の前記非線形演算部の間にｎ−１回設定した構成である前記（１）〜（４）いずれかに記載のデータ処理装置。
【０１６８】
（６）前記非線形変換処理部は、非線形変換対象となるデータの構成ビットの全てに対して、１つのＮＡＮＤまたはＮＯＲ演算部の演算結果とのＸＯＲまたはＸＮＯＲ演算結果を生成し、該ＸＯＲまたはＸＮＯＲ演算結果を非線型変換結果の構成ビットとして出力する前記（１）〜（５）いずれかに記載のデータ処理装置。
（７）前記非線形変換処理部は、前記繰り返し構造中に、ＸＯＲ演算部とＸＮＯＲ演算部の双方を有する構成である前記（１）〜（６）いずれかに記載のデータ処理装置。
（８）前記データ処理装置は、入力データとしての平文を暗号文に変換する暗号化処理、または、入力データとしての暗号文を平文に変換する復号処理を実行する前記（１）〜（７）いずれかに記載のデータ処理装置。
【０１６９】
（９）１つのＮＡＮＤまたはＮＯＲ演算部と、
１つのＸＯＲまたはＸＮＯＲ演算部からなる非線形演算部と、
ビット置換部と、
の繰り返し構造を有する非線形変換処理部を有するデータ処理装置。
【０１７０】
（１０）前記非線形変換処理部は、非線形変換対象となるデータの構成ビットの全てに対して、１つのＮＡＮＤまたはＮＯＲ演算部の演算結果とのＸＯＲまたはＸＮＯＲ演算結果を生成し、該ＸＯＲまたはＸＮＯＲ演算結果を非線型変換結果の構成ビットとして出力する前記（９）に記載のデータ処理装置。
【０１７１】
（１１）データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、
複数ラインを構成する１ラインのデータを入力して変換データを生成する非線形関数実行部を有するラウンド関数の繰り返し構造を有するデータ処理装置。
（１２）前記非線形関数実行部は、非線形変換対象となるデータの構成ビットの全てに対して、１つのＮＡＮＤまたはＮＯＲ演算部の演算結果とのＸＯＲまたはＸＮＯＲ演算結果を生成し、該ＸＯＲまたはＸＮＯＲ演算結果を非線型変換結果の構成ビットとして出力する前記（１１）に記載のデータ処理装置。
【０１７２】
さらに、上記した装置およびシステムにおいて実行する処理の方法や、処理を実行させるプログラムも本開示の構成に含まれる。
【０１７３】
また、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。例えば、プログラムは記録媒体に予め記録しておくことができる。記録媒体からコンピュータにインストールする他、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介してプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０１７４】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０１７５】
上述したように、本開示の一実施例の構成によれば、小型化した非線形変換部が実現される。
具体的には、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理部を有し、暗号処理部は、複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部を有し、Ｆ関数実行部は非線形変換処理を実行する非線形変換処理部を有し、非線形変換処理部は１つのＮＡＮＤまたはＮＯＲ演算部と、１つのＸＯＲまたはＸＮＯＲ演算部からなる非線形演算部と、ビット置換部との繰り返し構造を有する。この繰り返し構成により小型化された非線形変換部が実現される。
【符号の説明】
【０１７６】
７００  ＩＣモジュール
７０１  ＣＰＵ(Central processing Unit)
７０２  メモリ
７０３  暗号処理部
７０４  乱数生成部
７０５  送受信部
【図１】
0005682526.tif 000007
【図２】
0005682526.tif 000008
【図３】
0005682526.tif 000009
【図４】
0005682526.tif 000010
【図５】
0005682526.tif 000011
【図６】
0005682526.tif 000012
【図７】
0005682526.tif 000013
【図８】
0005682526.tif 000014
【図９】
0005682526.tif 000015
【図１０】
0005682526.tif 000016
【図１１】
0005682526.tif 000017
【図１２】
0005682526.tif 000018
【図１３】
0005682526.tif 000019
【図１４】
0005682526.tif 000020
【図１５】
0005682526.tif 000021
【図１６】
0005682526.tif 000022
【図１７】
0005682526.tif 000023
【図１８】
0005682526.tif 000024
【図１９】
0005682526.tif 000025
【図２０】
0005682526.tif 000026
【図２１】
0005682526.tif 000027
【図２２】
0005682526.tif 000028
【図２３】
0005682526.tif 000029
【図２４】
0005682526.tif 000030
【図２５】
0005682526.tif 000031
【図２６】
0005682526.tif 000032
【図２７】
0005682526.tif 000033
【図２８】
0005682526.tif 000034
【図２９】
0005682526.tif 000035