暗号処理装置、および暗号処理方法、並びにプログラム
【課題】暗号処理構成の小型化を実現する。
【解決手段】データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、暗号処理部は、複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、中間データ格納レジスタの格納データに基づいて、Ｆ関数実行部に対する入力データを算出する逆演算実行部を有する。逆演算実行部における逆演算により、Ｆ関数実行部に対する入力値を算出可能となり、このデータを保持するレジスタを削減することが可能となる。
【解決手段】データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、暗号処理部は、複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、中間データ格納レジスタの格納データに基づいて、Ｆ関数実行部に対する入力データを算出する逆演算実行部を有する。逆演算実行部における逆演算により、Ｆ関数実行部に対する入力値を算出可能となり、このデータを保持するレジスタを削減することが可能となる。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、暗号処理装置、および暗号処理方法、並びにプログラムに関する。さらに詳細には、共通鍵系暗号を実行する暗号処理装置、および暗号処理方法、並びにプログラムに関する。
【背景技術】
【０００２】
情報化社会が発展すると共に、扱う情報を安全に守るための情報セキュリティ技術の重要性が増してきている。情報セキュリティ技術の構成要素の一つとして暗号技術があり、現在では様々な製品やシステムで暗号技術が利用されている。
【０００３】
暗号処理アルゴリズムには様々なものがあるが、基本的な技術の一つとして、共通鍵ブロック暗号と呼ばれるものがある。共通鍵ブロック暗号では、暗号化用の鍵と復号用の鍵が共通のものとなっている。暗号化処理、復号処理共に、その共通鍵から複数の鍵を生成し、あるブロック単位、例えば６４ビット、１２８ビット、２５６ビット等のブロックデータ単位でデータ変換処理を繰り返し実行する。
【０００４】
代表的な共通鍵ブロック暗号のアルゴリズムとしては、過去の米国標準であるＤＥＳ（Ｄａｔａ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）や現在の米国標準であるＡＥＳ（Ａｄｖａｎｃｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）が知られている。他にも様々な共通鍵ブロック暗号が現在も提案され続けており、２００７年にソニー株式会社が提案したＣＬＥＦＩＡも共通鍵ブロック暗号の一つである。
【０００５】
このような、共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を繰り返し実行するラウンド関数実行部を有する暗号処理部と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部とによって構成される。鍵スケジュール部は、秘密鍵であるマスター鍵（主鍵）に基づいて、まずビット数を増加させた拡大鍵を生成し、生成した拡大鍵に基づいて、暗号処理部の各ラウンド関数部で適用するラウンド鍵（副鍵）を生成する。
【０００６】
このようなアルゴリズムを実行する具体的な構造として、線形変換部および非線形変換部を有するラウンド関数を繰り返し実行する構造が知られている。例えば代表的な構造にＦｅｉｓｔｅｌ構造や拡張Ｆｅｉｓｔｅｌ構造がある。Ｆｅｉｓｔｅｌ構造や拡張Ｆｅｉｓｔｅｌ構造は、データ変換関数としてのＦ関数を含むラウンド関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。Ｆ関数においては、線形変換処理および非線形変換処理が実行される。なお、Ｆｅｉｓｔｅｌ構造および拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理について記載した文献としては、例えば非特許文献１、非特許文献２がある。
【０００７】
暗号アルゴリズムの実装形態には、ソフトウェア実装とハードウェア実装の二種類が存在する。ハードウェア実装では、回路規模が小さくなるように実装することで、ハードウェア化の際のコストダウンや低消費電力化が期待できる。そのため、新アルゴリズム、既存アルゴリズムを問わず、小型化するための実装法が様々、提案されている。
【０００８】
例えばＨａｍａｌａｉｎｅｎ，Ａｌｈｏ、Ｈａｎｎｉｋａｉｎｅｎ、Ｈａｍａｌａｉｎｅｎらは、Ｓｕｂｓｔｉｔｕｔｉｏｎ Ｐｅｒｍｕｔａｔｉｏｎ Ｎｅｔｗｏｒｋ（ＳＰＮ）構造を持つＡＥＳ暗号アルゴリズムに対する小型実装法を提案している。この小型実装法については、非特許文献３［Panu Hamalainen,Timo Alho,Marko Hannikainen,and Timo D.Hamalainen. Design and implementation of low-area and low-power AES encryption hardware core. In DSD,pages 577-583.IEEE Computer Society,2006.9］に開示されている。
【０００９】
この開示された実装法では、１２８−ｂｉｔブロック暗号のＡＥＳを８−ｂｉｔごとの演算単位で処理することで、回路規模の小型化を達成している。Ｈａｍａｌａｉｎｅｎらの実装法はＳＰＮ構造とは異なる拡張Ｆｅｉｓｔｅｌ構造を持つＣＬＥＦＩＡ等のアルゴリズムにも応用できる。
【００１０】
ただし、既存の手法を単純に適用するとブロック長分のレジスタに加え、非線形処理部Ｆ関数の演算時の中間値を保持するために必要なレジスタが増加してしまう。例えば、ＣＬＥＦＩＡへの適用を考えたときには、ｂｌｏｃｋ長の１２８−ｂｉｔ分のレジスタに加え、３２−ｂｉｔ分のレジスタが増加する。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】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
【非特許文献３】Panu Hamalainen,Timo Alho,Marko Hannikainen,and Timo D.Hamalainen. Design and implementation of low-area and low-power aes encryption hardware core. In DSD,pages 577-583.IEEE Computer Society,2006.9
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本開示は、例えば上述の状況に鑑みてなされたものであり、例えばＣＬＥＦＩＡ等の拡張Ｆｅｉｓｔｅｌ構造を持つ暗号アルゴリズムに対して、既存の手法よりも小型化が期待できるハードウェア構成を実現する暗号処理装置、および暗号処理方法、並びにプログラムを提供することを目的とする。
【００１３】
具体的には、例えばＦ関数演算時の中間値からＦ関数への入力を復元する回路を導入することにより、ｂｌｏｃｋ長以上のレジスタを必要としない実装法を実現する。その結果、構造によってはレジスタ削減効果により回路規模の小型化が期待できる。
【課題を解決するための手段】
【００１４】
本開示の第１の側面は、
データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、
前記Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行部と、
を有する暗号処理装置にある。
【００１５】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、Ｆ関数実行部への入力データに対する非線形変換処理を実行するＳ−ｂｏｘを有し、前記中間データ格納レジスタは、前記Ｓ−ｂｏｘの出力値を中間データとして保持し、前記逆演算実行部は、前記Ｓ−ｂｏｘによる非線形変換処理の逆演算を含む演算処理により、前記Ｆ関数実行部に対する入力データを算出する。
【００１６】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、非線形変換部、および線形変換部を有し、前記非線形変換部の出力を前記中間データとして格納するレジスタを有し、前記線形変換部は、前記レジスタの格納値に対する線型変換処理を実行し、前記逆演算実行部は、前記レジスタの格納値に対する演算処理により、前記Ｆ関数実行部に対する入力データを算出する。
【００１７】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行するＳＰ型Ｆ関数である。
【００１８】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行し、さらに非線形変換部において再度、非線形変換処理をするＳＰＳ型Ｆ関数である。
【００１９】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、外部から入力するラウンド鍵との排他的論理和演算部を有する。
【００２０】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、複数の非線形演算部の繰り返し構造を有する。
【００２１】
さらに、本開示の暗号処理装置の一実施態様において、前記暗号処理部は、入力データとしての平文を暗号文に変換する暗号化処理、または、入力データとしての暗号文を平文に変換する復号処理を実行する。
【００２２】
さらに、本開示の第２の側面は、
暗号処理装置において実行する暗号処理方法であり、
暗号処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理ステップを実行し、
前記暗号処理ステップは、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行ステップと、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行ステップと、
前記Ｆ関数実行ステップにおける変換データの生成過程の中間データを中間データ格納レジスタに格納するステップと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行ステップと、
を実行する暗号処理方法にある。
【００２３】
さらに、本開示の第３の側面は、
暗号処理装置において暗号処理を実行させるプログラムであり、
暗号処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理ステップを実行させ、
前記暗号処理ステップにおいて、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行ステップと、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行ステップと、
前記Ｆ関数実行ステップにおける変換データの生成過程の中間データを中間データ格納レジスタに格納するステップと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行ステップと、
を実行させるプログラムにある。
【００２４】
なお、本開示のプログラムは、例えば、様々なプログラム・コードを実行可能な情報処理装置やコンピュータ・システムに対して例えば記憶媒体によって提供されるプログラムである。このようなプログラムを情報処理装置やコンピュータ・システム上のプログラム実行部で実行することでプログラムに応じた処理が実現される。
【００２５】
本開示のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００２６】
本開示の一実施例によれば、暗号処理構成の小型化が実現される。
具体的には、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、暗号処理部は、複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、中間データ格納レジスタの格納データに基づいて、Ｆ関数実行部に対する入力データを算出する逆演算実行部を有する。逆演算実行部における逆演算により、Ｆ関数実行部に対する入力値を算出可能となり、このデータを保持するレジスタを削減することが可能となり、暗号処理構成の小型化が実現される。
【図面の簡単な説明】
【００２７】
【図１】ｋビットの鍵長に対応したｎビット共通鍵ブロック暗号アルゴリズムを説明する図である。
【図２】図１に示すｋビットの鍵長に対応したｎビット共通鍵ブロック暗号アルゴリズムに対応する復号アルゴリズムを説明する図である。
【図３】鍵スケジュール部とデータ暗号化部の関係について説明する図である。
【図４】データ暗号化部の構成例について説明する図である。
【図５】ＳＰＮ構造のラウンド関数の例について説明する図である。
【図６】Ｆｅｉｓｔｅｌ構造のラウンド関数の一例について説明する図である。
【図７】拡張Ｆｅｉｓｔｅｌ構造の一例について説明する図である。
【図８】拡張Ｆｅｉｓｔｅｌ構造の一例について説明する図である。
【図９】非線形変換部の構成例について説明する図である。
【図１０】線形変換処理部の構成例について説明する図である。
【図１１】共通鍵ブロック暗号について説明する図である。
【図１２】Ｆｅｉｓｔｅｌ構造について説明する図である。
【図１３】拡張Ｆｅｉｓｔｅｌ構造について説明する図である。
【図１４】ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムのラウンド関数の構造について説明する図である。
【図１５】Ｈａｍａｌａｉｎｅｎらの提案したＡＥＳ暗号を実行するデータ暗号化部のデータパスを示す図である。
【図１６】データ暗号化部の構成例を説明する図である。
【図１７】Ｈａｍａｌａｉｎｅｎらの実装法を４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に適用した場合のデータ演算部回路の概要図を示す図である。
【図１８】ラウンド関数内のＦ関数の具体例を説明する図である。
【図１９】本開示の一実施例に係る暗号処理構成を、図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｓｉｔｅｌ構造に適用した場合のデータ演算部回路の概要図である。
【図２０】ラウンド関数を説明する図である。
【図２１】ＳＰＳ型Ｆ関数について説明する図である。
【図２２】図２１に記載のＳＰＳ型Ｆ関数に、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図２３】鍵挿入が複数入ったＳＰＳ型Ｆ関数について説明する図である。
【図２４】図２３に記載のＳＰＳ型Ｆ関数に、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図２５】鍵挿入がＦ関数入力直後にあるＳＰ型Ｆ関数について説明する図である。
【図２６】図２５に記載のＳＰ型Ｆ関数に、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図２７】Ｆ関数の構成例について説明する図である。
【図２８】図２７に記載のＦ関数に、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図２９】Ｆ関数の構成例について説明する図である。
【図３０】ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の１つの構成例について説明する図である。
【図３１】図３０に記載のラウンド置換を持つ構成に対して、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図３２】暗号処理装置としてのＩＣモジュール７００の構成例を示す図である。
【発明を実施するための形態】
【００２８】
以下、図面を参照しながら本開示に係る暗号処理装置、および暗号処理方法、並びにプログラムの詳細について説明する。説明は、以下の項目に従って行う。
１．共通鍵ブロック暗号の概要
２．共通鍵ブロック暗号の構造と従来型の小型化実装手法の概要について
３．レジスタ削減を実現する暗号処理構成例について
４．本開示の手法の効果のまとめ
５．その他の実施例について
６．暗号処理装置の構成例について
７．本開示の構成のまとめ
【００２９】
［１．共通鍵ブロック暗号の概要］
まず、共通鍵ブロック暗号の概要について説明する。
（１−１．共通鍵ブロック暗号）
ここでは共通鍵ブロック暗号（以下ではブロック暗号）としては以下に定義するものを指すものとする。
ブロック暗号は入力として平文Ｐと鍵Ｋを取り、暗号文Ｃを出力する。平文と暗号文のビット長をブロックサイズと呼びここではｎで著す。ｎは任意の整数値を取りうるが、通常、ブロック暗号アルゴリズムごとに、あらかじめひとつに決められている値である。ブロック長がｎのブロック暗号のことをｎビットブロック暗号と呼ぶこともある。
【００３０】
鍵のビット長をｋで表す。鍵は任意の整数値を取りうる。共通鍵ブロック暗号アルゴリズムは１つまたは複数の鍵サイズに対応することになる。例えば、あるブロック暗号アルゴリズムＡはブロックサイズｎ＝１２８であり、ｋ＝１２８またはｋ＝１９２またはｋ＝２５６の鍵サイズに対応するという構成もありうるものとする。
平文Ｐ：ｎビット
暗号文Ｃ：ｎビット
鍵Ｋ：ｋビット
【００３１】
図１にｋビットの鍵長に対応したｎビット共通鍵ブロック暗号アルゴリズムＥの図を示す。
暗号化アルゴリズムＥに対応する復号アルゴリズムＤは暗号化アルゴリズムＥの逆関数Ｅ−１と定義でき、入力として暗号文Ｃと鍵Ｋを受け取り，平文Ｐを出力する。図２に図１に示した暗号アルゴリズムＥに対応する復号アルゴリズムＤの図を示す。
【００３２】
（１−２．内部構成）
ブロック暗号は２つの部分に分けて考えることができる。ひとつは鍵Ｋを入力とし、
ある定められたステップによりビット長を拡大してできた拡大鍵Ｋ'（ビット長ｋ'）を出力する「鍵スケジュール部」と、もうひとつは平文Ｐと鍵スケジュール部から拡大された鍵Ｋ'を受け取ってデータの変換を行い暗号文Ｃを出力する「データ暗号化部」である。
２つの部分の関係は図３に示される。
【００３３】
（１−３．データ暗号化部）
以下の実施例において用いるデータ暗号化部はラウンド関数という処理単位に分割できるものとする。ラウンド関数は入力としての２つのデータを受け取り、内部で処理を施したのち、１つのデータを出力する。入力データの一方は暗号化途中のｎビットデータであり、あるラウンドにおけるラウンド関数の出力が次のラウンドの入力として供給される構成となる。もう１つの入力データは鍵スケジュールから出力された拡大鍵の一部のデータが用いられ、この鍵データのことをラウンド鍵と呼ぶものとする。またラウンド関数の総数は総ラウンド数と呼ばれ、暗号アルゴリズムごとにあらかじめ定められている値である。ここでは総ラウンド数をＲで表す。
【００３４】
データ暗号化部の入力側から見て１ラウンド目の入力データをＸ１とし、ｉ番目のラウンド関数に入力されるデータをＸｉ、ラウンド鍵をＲＫｉとすると、データ暗号化部全体は図４のように示される。
【００３５】
（１−４．ラウンド関数）
ブロック暗号アルゴリズムによってラウンド関数はさまざまな形態をとりうる。ラウンド関数はその暗号アルゴリズムが採用する構造（ｓｔｒｕｃｔｕｒｅ）によって分類できる。代表的な構造としてここではＳＰＮ構造、Ｆｅｉｓｔｅｌ構造、拡張Ｆｅｉｓｔｅｌ構造を例示する。
【００３６】
（ア）ＳＰＮ構造ラウンド関数
ｎビットの入力データすべてに対して、ラウンド鍵との排他的論理和演算、非線形変換、線形変換処理などが適用される構成。各演算の順番は特に決まっていない。図５にＳＰＮ構造のラウンド関数の例を示す。
【００３７】
（イ）Ｆｅｉｓｔｅｌ構造
ｎビットの入力データはｎ／２ビットの２つのデータに分割される。うち片方のデータとラウンド鍵を入力として持つ関数（Ｆ関数）が適用され、出力がもう片方のデータに排他的論理和される。そののちデータの左右を入れ替えたものを出力データとする。Ｆ関数の内部構成にもさまざまなタイプのものがあるが、基本的にはＳＰＮ構造同様にラウンド鍵データとの排他的論理和演算、非線形演算、線形変換の組み合わせで実現される。図６にＦｅｉｓｔｅｌ構造のラウンド関数の一例を示す。
【００３８】
（ウ）拡張Ｆｅｉｓｔｅｌ構造
拡張Ｆｅｉｓｔｅｌ構造はＦｅｉｓｔｅｌ構造ではデータ分割数が２であったものを，３以上に分割する形に拡張したものである。分割数をｄとすると、ｄによってさまざまな拡張Ｆｅｉｓｔｅｌ構造を定義することができる。Ｆ関数の入出力のサイズが相対的に小さくなるため、小型実装に向いているとされる。図７にｄ＝４でかつ、ひとつのラウンド内に２つのＦ関数が並列に適用される場合の拡張Ｆｅｉｓｔｅｌ構造の一例を示す。また，図８にｄ＝８でかつ，ひとつのラウンド内に１つのＦ関数が適用される場合の拡張Ｆｅｉｓｔｅｌ構造の一例を示す。
【００３９】
（１−５．非線形変換処理部）
非線形変換処理部は、入力されるデータのサイズが大きくなると実装上のコストが高くなる傾向がある。それを回避するために対象データを複数の単位に分割し、それぞれに対して非線形変換を施す構成がとられることが多い。例えば入力サイズをｍｓビットとして、それらをｓビットずつのｍ個のデータに分割して、それぞれに対してｓビット入出力を持つ非線形変換を行う構成である。それらのｓビット単位の非線形変換をＳ−ｂｏｘと呼ぶものとする。図９に例を示す。
【００４０】
（１−６．線形変換処理部）
線形変換処理部はその性質上、行列として定義することが可能である。行列の要素はＧＦ（２８）の体の要素やＧＦ（２）の要素など、一般的にはさまざまな表現ができる。図１０にｍｓビット入出力をもち、ＧＦ（２ｓ）の上で定義されるｍ×ｍの行列により定義される線形変換処理部の例を示す。
【００４１】
［２．共通鍵ブロック暗号の構造と従来型の小型化実装手法の概要について］
次に、共通鍵ブロック暗号の構造と従来型の小型化実装手法の概要について説明する。
本開示に係る暗号処理構成の説明上、必要な用語について説明する。
【００４２】
（２−１．共通鍵ブロック暗号について）
図１１を参照して、再度、共通鍵ブロック暗号について説明する。共通鍵ブロック暗号のアルゴリズムは、入力データの変換を繰り返し実行するラウンド関数を有するデータ暗号化部と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部とによって構成される。鍵スケジュール部は秘密鍵を入力し、各ラウンド関数に入力するラウンド鍵を生成する。
例えば、ｒ段のラウンド関数を行なう構成としたブロック暗号においては、１からｒ段までのラウンド関数にそれぞれＲＫ１，ＲＫ２，...，Ｒｒのラウンド鍵が入力される。また、初期鍵としてＩＫが，最終鍵としてＦＫが排他的論理和される。
【００４３】
（２−２．Ｆｅｉｓｔｅｌ構造）
図１２を参照してＦｅｉｓｔｅｌ構造について説明する。共通鍵ブロック暗号におけるデータ暗号化部の代表的な構造としてＦｅｉｓｔｅｌ構造がある。ブロック長をｎ−ｂｉｔとした際の具体的なＦｅｉｓｔｅｌ構造の構成例を図１２に示す。
【００４４】
図１２を見ると，ｎ−ｂｉｔのデータをｎ／２−ｂｉｔずつの２−ｌｉｎｅに分割し、そのｎ／２−ｂｉｔの片方をラウンド内のＦ関数に入力し、その出力をもう片方のｎ／２−ｂｉｔと排他的論理和していく構成となっている。Ｆ関数の構成には様々なタイプのものが考えられる。一例を挙げると、図１２に示すＦ関数のように、ラウンド鍵との排他的論理和演算、Ｓ−ｂｏｘと呼ばれる非線形演算、その後、行列演算により線形変換の処理を行なう構成が知られている。
また、図１２に示した構造は，Ｆｅｉｓｔｅｌ構造の構成例の１つであり，ＩＫ，ＦＫを排他的論理和する位置を変更することで、別の構成例が可能である。
【００４５】
（２−３．拡張Ｆｅｉｓｔｅｌ構造）
図１３を参照して拡張Ｆｅｉｓｔｅｌ構造について説明する。前節のＦｅｉｓｔｅｌ構造の説明では，ｎ／２−ｂｉｔずつの２−ｌｉｎｅに分割し、処理を行なう構成であったが、３−ｌｉｎｅ以上に分割する形にも拡張が可能である。例えば、ｎ／４−ｂｉｔずつの４−ｌｉｎｅに分割し、処理を行なう４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造と呼ばれるものもある。
【００４６】
具体的な４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造の構成例を図１３に示す。図１３を見ると，ｎ−ｂｉｔのデータをｎ／４−ｂｉｔずつの４−ｌｉｎｅに分割し、そのうちの２−ｌｉｎｅをそれぞれＦ関数に入力し、その出力をその他の２−ｌｉｎｅと排他的論理和していく構成となっている。２−ｌｉｎｅから４−ｌｉｎｅと変更することにより、ラウンド鍵ＲＫｉ，初期鍵ＩＫ，最終鍵ＦＫも、ｎ／２−ｂｉｔから、ｎ／４−ｂｉｔのＲＫｉ［０］，ＲＫｉ［１］，ＩＫ［０］，ＩＫ［１］，ＦＫ［０］，ＦＫ［１］に分割される。上記は、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造についての説明だが、２−ｌｉｎｅ以上のＦｅｉｓｔｅｌ構造については全て拡張Ｆｅｉｓｔｅｌ構造と呼ぶ。本開示の実施例の説明においては簡単のため、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造についてのみ言及する．
【００４７】
（２−４．従来型の小型化実装手法の概要と課題）
（２−４−１．ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおける小型実装手法について）
先に説明したように、ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおける小型実装手法についてＨａｍａｌａｉｎｅｎ，Ａｌｈｏ，Ｈａｎｎｉｋａｉｎｅｎ，ＨａｍａｌａｉｎｅｎらはＡＥＳの小型実装法を提案している。非特許文献３［Panu Hamalainen,Timo Alho,Marko Hannikainen,and Timo D.Hamalainen. Design and implementation of low-area and low-power AES encryption hardware core. In DSD,pages 577-583.IEEE Computer Society,2006.9］
【００４８】
まず、図１４を参照してＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムのラウンド関数の構造について説明する。なお、ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおいてもＦｅｉｓｔｅｌ構造と同様、ラウンド関数を複数回繰り返し実行する構成を持つ。図１４は，ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおいて利用されるラウンド関数実行部の構成例を示す図である。ＡＥＳでは，図１４に示すラウンド関数を、複数回繰り返して平文から暗号文、または、暗号文から平文の生成を行なう。
【００４９】
図１４に示すラウンド関数実行部は以下の構成要素によって構成される。非線形変換処理を実行する８−ｂｉｔ入出力の１６個のＳ−ｂｏｘからなる非線形変換部４０１，非線形変換部を構成するＳ−ｂｏｘからの８−ｂｉｔ出力の入れ替え処理としてのＳｈｉｆｔＲｏｗ実行部４０２、ＳｈｉｆｔＲｏｗ実行部の出力を３２−ｂｉｔ単位で入力して行列を適用した線形変換処理を実行する４つの行列演算部からなる線形変換部４０３、線形変換部４０３を構成する４つの行列演算部各々からの３２−ｂｉｔ出力に対して３２−ｂｉｔのラウンド鍵との排他的論理和演算を実行する４つの演算部からなる排他的論理和演算部４０４を有する。
【００５０】
図１４に示す例は、入出力１２８−ｂｉｔのラウンド関数実行部であり、１６個のＳ−ｂｏｘ各々に８−ｂｉｔ、計８×１６＝１２８−ｂｉｔを入力し、４つの排他的論理和部の各々３２−ｂｉｔ、計３２×４＝１２８−ｂｉｔ出力を行なう構成である。
【００５１】
前述の非線形変換部４０１、ＳｈｉｆｔＲｏｗ実行部４０２、線形変換部４０３、排他的論理和演算部４０４、これらを適用した一連の処理を１回のラウンド関数の実行処理として実行し、このラウンド関数を複数回、繰り返して１２８−ｂｉｔの入力データ（例えば平文）から、１２８−ｂｉｔの出力（例えば暗号文）を生成して出力する。
【００５２】
ＡＥＳの実装において、１つのラウンド関数の処理（１ｒｏｕｎｄ）、すなわち、非線形変換部４０１、ＳｈｉｆｔＲｏｗ実行部４０２、線形変換部４０３、排他的論理和演算部４０４、これらを適用した一連の処理を、１ｃｙｃｌｅで実行しようとすると、少なくとも、図１４に示すように、１６個のＳ−ｂｏｘの回路と、４個の行列演算回路がデータ暗号化部の構成として必要となる。
【００５３】
Ｈａｍａｌａｉｎｅｎらは，１ｒｏｕｎｄに１６ｃｙｃｌｅかけることで、データ暗号化部の小型化を実現した。この小型化構成では、Ｓ−ｂｏｘの回路は１個しか用いず、さらに、４ｃｙｃｌｅかけて１つの行列演算を実行するように実装することで、行列演算回路の小型化も実現している。
【００５４】
図１５にＨａｍａｌａｉｎｅｎらの提案したＡＥＳ暗号を実行するデータ暗号化部のデータパスを示す。図１５に示す構成は、図１４に示すＡＥＳ暗号のラウンド関数を実行するハードウェア構成に相当する。
【００５５】
図１５に示す構成において、演算中のデータは８−ｂｉｔ単位に分割され、各８−ｂｉｔデータをレジスタＲ０〜Ｒ１８に格納している。図１５には、１９個のレジスタが示されている。１９個のレジスタ（Ｒ０〜Ｒ１８）の各々は８−ｂｉｔデータを保持する８−ｂｉｔレジスタである。図１４を参照して説明した通り、図１４に示す構成は、入出力１２８−ｂｉｔのラウンド関数実行部であり、図１５は，入出力１２８−ｂｉｔのラウンド関数を８−ｂｉｔ単位データのシリアル処理として実行するハードウェア構成に対応する。
【００５６】
図１５の構成において、入出力データを全て格納するために必要となる８−ｂｉｔレジスタの数は、１２８／８＝１６であり、１６個のレジスタがあればよい。図１５には、１９個のレジスタがあり、３つのレジスタが余分であるが、これら２４−ｂｉｔ分の３つのレジスタは、行列を適用した線形変換処理を実行するための行列演算処理のために利用される。
【００５７】
また、図１４を参照して説明したように、ＡＥＳでは、非線形変換を実行するＳ−ｂｏｘと線形変換を実行する行列演算の間にＳｈｉｆｔＲｏｗ実行部によるデータ置換が実行される。Ｈａｍａｌａｉｎｅｎらの実装手法では、図１５中のいくつかのレジスタの前にマルチプレクサ（Ｍｕｌｔｉｐｌｅｘｅｒ）ｍ０１〜ｍ０８を導入することにより、ＳｈｉｆｔＲｏｗ実行部で行なわれる置換を実現している。
【００５８】
図１５に示すように、非線形変換部としてのＳ−ｂｏｘ，Ｓ５０１は１個しかない。このＳ−ｂｏｘ，Ｓ５０１に対して８−ｂｉｔデータを順次入力し、１６ｃｙｃｌｅで図１４に示す１６個のＳ−ｂｏｘによる非線形変換処理を実行する。Ｓ−ｂｏｘ，Ｓ５０１の出力は、行列演算回路Ｍ５０２に入力され、行列演算回路Ｍ５０２において、行列を適用した線形変換処理が実行される。
【００５９】
なお，図１４の構成では、Ｓ−ｂｏｘによる処理データをＳｈｉｆｔＲｏｗ実行部で置換した後、行列演算を行なう構成となっているが、図１５に示す例では、Ｓ−ｂｏｘ，Ｓ５０１の出力を行列演算回路Ｍ５０２に直接入力する構成としている。図１５の構成では、ＳｈｉｆｔＲｏｗ実行部での置換処理に相当する処理は図１５に示すレジスタＲ０〜Ｒ１８とマルチプレクサｍ０１〜ｍ０８の動作によって実行する。
【００６０】
図１５に示す行列演算回路Ｍ５０２では，図１４に示す線形変換部４０３の４つの行列演算回路の処理が順次実行される。図１４に示す線形変換部４０３の４つの行列演算回路の１つの行列演算回路で実行する行列を適用した線形変換処理を４ｃｙｃｌｅで実行する。図１４に示す排他的論理和演算部４０４の排他的論理和演算処理は，図１５の排他的論理和演算部Ｘ５０３，Ｘ５０４において実行される。これら排他的論理和演算部Ｘ５０３，Ｘ５０４において，処理データと鍵生成部Ｋ５０５の出力するラウンド鍵との排他的論理和処理を実行する。
【００６１】
なお，本開示の構成に本質的に関連のある箇所のみを説明するため，ＳｈｉｆｔＲｏｗ等の置換を行なう回路や、鍵スケジュール部については図１６のように省略したデータパスで説明する。図１６中のレジスタ群と記述されている部分は、９６−ｂｉｔ分のデータを保持し、ＳｈｉｆｔＲｏｗも考慮されたレジスタの集合を表す。ＡＥＳの実装において，１ｒｏｕｎｄを１ｃｙｃｌｅで演算する場合、利用するデータ暗号化部用のレジスタはｂｌｏｃｋ長である１２８−ｂｉｔ分のみで済む。
【００６２】
それに対し、Ｈａｍａｌａｉｎｅｎらの実装法では、１５２−ｂｉｔと２４−ｂｉｔ分増えている。これは、行列への入力を８−ｂｉｔずつに分割した場合、行列を計算し終わるまでの途中演算結果の３２−ｂｉｔ分を保持する必要性が出てくるためである。そのため、単純に考えると３２−ｂｉｔ分のレジスタが追加されることになる。一方、行列へ入力する値は次のラウンドでは不要となる。このことを考慮すると、行列へ入力する３２−ｂｉｔのうち、はじめに入力する８−ｂｉｔ分のレジスタは行列演算部のレジスタと共有できるので、レジスタの増加分は、
３２−８＝２４−ｂｉｔ
分に抑えられる。
【００６３】
（２−４−２．ＳＰＮ構造の小型実装構成の拡張Ｆｅｉｓｔｅｌ 構造への適用と問題点について）
上述したように，Ｈａｍａｌａｉｎｅｎらは，ＳＰＮ構造の小型化を実現している。しかし、この小型化構成はＳＰＮ構造に対応した特有の構成であり、この小型実装構成を拡張Ｆｅｉｓｔｅｌ構造へ適用しても十分な小型化の効果は得られない。
【００６４】
以下、この問題点について説明する。なお、以下の説明では、拡張Ｆｅｉｓｔｅｌ構造は、Ｆｅｉｓｔｅｌ構造を含む概念であるものとして説明する。Ｈａｍａｌａｉｎｅｎらの実装法を拡張Ｆｅｉｓｔｅｌ構造を持つＣＬＥＦＩＡ等のアルゴリズムを実行する構成に適用すると、行列演算のために、行列の出力ビット長分のデータを格納するレジスタが必要になる。
【００６５】
これは、拡張Ｆｅｉｓｔｅｌ構造がＳＰＮ構造とは異なり、例えばラウンド関数内のＦ関数に入力した値を、次のラウンドでも利用する必要があるという処理シーケンスの根本的な違いに起因するものである。
【００６６】
図１７は、Ｈａｍａｌａｉｎｅｎらの実装法を４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に適用した場合のデータ演算部回路の概要図を示す図である。図１７では、先に図１６を参照して説明したＡＥＳのデータパスと同様、拡張Ｆｅｉｓｔｅｌ構造のラウンド関数終了時の置換動作や鍵スケジュール部は省略してある。なお、ラウンド演算における処理データサイズとしてのブロックサイズはｎ−ｂｉｔとする。
【００６７】
先に図１３を参照して説明したように，４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造では、４つのライン各々にｎ／４−ｂｉｔずつ入力され、順次転送される。図１７中のレジスタ群Ｒ７０３は、図１６に示すレジスタ群Ｒ６０１に対応する。ただし、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に対応する図１７中のレジスタ群Ｒ７０３は，（３／４）ｎ−ｂｉｔ分のデータを保持するレジスタとラウンド終了時の置換動作と同様の処理を実現するマルチプレクサ等の組み合わせとして構成される。
【００６８】
なお、図１７に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムのデータパス（演算実行回路）を適用して実行する演算は、図１３に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造を適用した演算処理に対応する。この図１７に示すデータパスを利用して図１３に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造内のＦ関数を含むラウンド関数を実行することになる。
【００６９】
ラウンド関数内のＦ関数の具体例を図１８に示す。図１８に示すＦ関数は、以下の構成要素を持つ。
＊非線形処理を実行するＳ−ｂｏｘからなる非線形変換部Ｓ８０１、
＊非線形変換部Ｓ８０１からの出力に対して、行列演算により線形変換の処理を行なうＭ８０２、
＊線形変換部Ｍ８０２からの出力に対して、ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部Ｘ８０３、
上記の構成要素を持つ。図１８に示すＦ関数はＳＰ型Ｆ関数と呼ばれる。
【００７０】
ただし，４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造におけるＦ関数に対する入出力は，ｎ／４−ｂｉｔになる。なお、図１８に示されている線形変換部Ｍ８０１は、ＡＥＳ暗号アルゴリズムで採用されている行列と同様に下記の（式１）に示される巡回行列を想定している。
【００７１】
【数１】
【００７２】
なお、式１に示す（ｘ０、ｘ１、ｘ２、ｘ３）は、行列演算回路である線形変換部Ｍ８０１に対する入力（Ｓ−ｂｏｘからの出力）、
（ｙ０、ｙ１、ｙ２、ｙ３）は、行列演算回路である線形変換部Ｍ８０１の出力（線形変換結果）、
４×４の行列は、行列演算回路である線形変換部Ｍ８０１において適用する行列（線形変換行列）に対応する。
なお、４×４の線形変換行列の要素は１６進数値として示している。
本例では、（ｘ０、ｘ１、ｘ２、ｘ３）の各々は、Ｓ−ｂｏｘからの１サイクルあたりの出力であり８ビットデータである。出力（ｙ０、ｙ１、ｙ２、ｙ３）の各々も８ビットデータである。
【００７３】
先に図１４〜図１６を参照して説明したＡＥＳ暗号アルゴリズムの構成と比較するため、処理単位としてのブロック構成ビットｎは、ｎ＝１２８−ｂｉｔとする。
図１７に示す回路も、図１６に示す回路と同様、Ｓ−ｂｏｘは１つのみである。図１７に示すＳ−ｂｏｘ，Ｓ７０１である。このＳ−ｂｏｘ，Ｓ７０１は、図１８に示すＦ関数内に設定される１つのＳ−ｂｏｘの処理を１ｃｙｃｌｅで実行する。
ｃｙｃｌｅごとに、順次、図１８に示す各Ｓ−ｂｏｘの処理を行なうことになる。
【００７４】
図１８に示すように、Ｆ関数の１つのＳ−ｂｏｘには、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造の１つのラインを伝送するｎ／４−ｂｉｔの１／４、すなわち、ｎ／１６−ｂｉｔが入力され非線形変換処理が実行される。
【００７５】
図１７に示すＳ−ｂｏｘＳ７０１には、ｎ／１６−ｂｉｔずつがｃｙｃｌｅごとに入力され、非線形変換処理が実行される。Ｓ−ｂｏｘ，Ｓ７０１において非線形変換のなされたデータは、ｎ／１６−ｂｉｔごとに１ｃｙｃｌｅ単位で次の線形変換回路Ｍ７０２に入力される。線形変換回路Ｍ７０２では、所定の行列を適用した線形変換処理が実行されることになる。
【００７６】
図１７に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムのデータパス構成中、レジスタ群Ｒ７０３を除く演算実行回路と、先に図１６を参照して説明したレジスタ群Ｒ６０１を除く、ＳＰＮ構造を利用したＡＥＳ暗号処理を実行する演算回路構成とを比較する。
【００７７】
図１６に示す演算回路では、８−ｂｉｔレジスタがＲ０〜Ｒ３，Ｒ１６〜Ｒ１８の７個であるのに対して、図１７に示す演算回路では、８−ｂｉｔレジスタがＲ０〜Ｒ３，Ｒ１６〜Ｒ１９の８個である。すなわち、８−ｂｉｔレジスタの数が１つ増加している。
【００７８】
このように、Ｈａｍａｌａｉｎｅｎらの提案構成を拡張Ｆｅｉｓｔｅｌ構造に適用した場合、図１７に示す演算回路のように、ブロック長分のレジスタに加え、１−ｌｉｎｅ分のレジスタが必要となってくる。レジスタの増加は回路規模に大きく影響するため、ブロック長分のみのレジスタで構成できるならば、そのほうが望ましい。
【００７９】
従来手法の課題点として以下の課題があげられる。
レジスタの回路規模は他のセルに比べて比較的大きなものとなり、レジスタ数の増加は回路規模に大きく影響する。そのため、小型化を実現するための一つの方向性として、レジスタの増加を抑えた実装法が考えられる。従来手法の実装法では、ｂｌｏｃｋ長分よりも大きなレジスタが必要になってしまうことが課題と考えられる。
【００８０】
［３．レジスタ削減を実現する暗号処理構成例について］
Ｈａｍａｌａｉｎｅｎらの実装法を、拡張Ｆｅｉｓｔｅｌ構造を持つアルゴリズムに適用した場合には、前節で述べたように必要なレジスタが増加してしまう。これは、Ｆ関数への入力は次のラウンドでも利用するため、Ｆ関数への入力を保持したまま、Ｆ関数の出力を演算しているためである。この考えのもとで実装すると、Ｆ関数への入力を保持するレジスタと、Ｆ関数演算時の中間値を保持するためのレジスタの両方が必要となる。
【００８１】
先の図１７、図１８を用いて説明した４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムでは、Ｆ関数内の線形変換部Ｍ８０２で表される行列演算時の中間値を保持する必要があったため、ブロック長分のレジスタに加え、１−ｌｉｎｅ分の３２−ｂｉｔ分のレジスタが必要となった。
【００８２】
以下に説明する実施例では、Ｆ関数への入力は一度破棄し、その入力が格納されていたレジスタをＦ関数演算時の中間値を保持するためのレジスタとして利用する。
Ｆ関数の出力値と、Ｆ関数へ入力したラインとは別のラインとの排他的論理和を実行後、Ｆ関数演算時の中間値からＦ関数への入力を復元するように考える。
【００８３】
このようにすることで、Ｆ関数への入力値とＦ関数演算時の中間値を同時に保持する必要がなくなり、レジスタ数を削減することができる。
【００８４】
以下、具体例について説明する。前述した構成との対比を容易とするため、図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｓｉｔｅｌ構造を例に説明する。なお，図１８に示されている線形変換部Ｍ８０１は，ＡＥＳ暗号アルゴリズムで採用されている行列と同様に下記の（式２）で記される巡回行列を想定している。
【００８５】
【数２】
【００８６】
図１９は、本開示の一実施例に係る暗号処理構成を、図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｓｉｔｅｌ構造に適用した場合のデータ演算部回路の概要図である。
【００８７】
先に説明した項目（２−４−２．ＳＰＮ構造の小型実装構成の拡張Ｆｅｉｓｔｅｌ 構造への適用と問題点について）で紹介したように、Ｈａｍａｌａｉｎｅｎらの実装法を図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に適用した場合、図１８のＦ関数内の線形変換部Ｍ８０２で表される行列演算時の中間値を保持するレジスタが必要となった。
【００８８】
それに対して、本開示の一実施例に係る暗号処理構成を用いて実現された図１９では、中間値として、非線形演算部Ｓ８０１後の線形演算部Ｍ８０２に入力される値を保持するようにしている。この手法で保持すべき中間値を図１８に保持する中間値Ｉ８０４として表す。図１９では、上記の中間値を図１９に示すＲ０〜Ｒ３で表されるレジスタ内に保持している。
【００８９】
また、Ｈａｍａｌａｉｎｅｎらの実装法を図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に適用した場合、図１８のＦ関数内の線形変換部Ｍ８０２で表される行列演算時の中間値を保持するレジスタとは別に、次のラウンドを演算するために必要となるＦ関数への入力値を保持するレジスタを必要としていた。それに対して、図１９では、次のラウンドを演算するために必要となるＦ関数への入力値は保持せずに、代わりに上記で述べた図１８のＦ関数内の非線形演算部Ｓ８０１後の線形演算部Ｍ８０２に入力される値である保持する中間値Ｉ８０４を保持している。
【００９０】
先に説明した項目（２−４−２．ＳＰＮ構造の小型実装構成の拡張Ｆｅｉｓｔｅｌ 構造への適用と問題点について）で紹介したＨａｍａｌａｉｎｅｎらの実装法では，１６０−ｂｉｔ分のレジスタを利用していたのに対し，図１９に示す構成においては、８−ｂｉｔレジスタを、Ｒ０〜Ｒ１５の１６個、利用しており、合計で１２８−ｂｉｔ分のレジスタのみで回路を実現できる。
【００９１】
この図１９に示すデータパスを利用して図１３，図１８で表されるラウンド関数を実行することになる。
図１３を参照すると、１ラウンドに演算する必要のあるＦ関数は２つあることが分かる。図１９では，１つのＦ関数の出力を４ｃｙｃｌｅかけて実行し、その後の４ｃｙｃｌｅをかけて図１８の保持する中間値Ｉ，８０４からＦ関数の入力を復元する。
【００９２】
前述したように、１ｒｏｕｎｄにＦ関数は２つ実行する必要があるため、合計１６ｃｙｃｌｅを要することで１ｒｏｕｎｄ分の演算を実行する。また、平文入力時には、１６ｃｙｃｌｅかけて上位８−ｂｉｔから８−ｂｉｔずつ入力し、暗号文出力時にも１６ｃｙｃｌｅかけて出力ポートから上位８−ｂｉｔから８−ｂｉｔずつ順次出力するように考える。
【００９３】
以下、以下に示す表１を参照しながら平文入力時の１６ｃｙｃｌｅ分と，１ｒｏｕｎｄの演算に必要な１６ｃｙｃｌｅ分と，暗号文出力時の１６ｃｙｃｌｅ分のデータの流れを説明する。
【００９４】
【表１】
【００９５】
まず、平文入力時の１６ｃｙｃｌｅ分の動きを説明する。
ｉ∈｛０，１，...，１５｝
に対して、
ｐｉを８−ｂｉｔの要素とする。
このとき，（ｐ０，ｐ１，...，ｐ１５）で表される１２８−ｂｉｔを平文として考える。
【００９６】
平文入力時の１ｃｙｃｌｅ目では，ｐ０を図１９に示す平文入力ポートからマルチプレクサｍ０１を利用しＲ１５に格納する．その後１１ｃｙｃｌｅかけて，ｐ０をマルチプレクサｍ０２を利用し，Ｒ１４，Ｒ１３，...，Ｒ４の順に格納していく。
【００９７】
上述したように、平文入力時の１２ｃｙｃｌｅ後にはｐ０はＲ４に格納されているとする。１３ｃｙｃｌｅ目には、Ｒ４に格納されていたｐ０を非線形演算部Ｓ９０１に入力し、その出力をマルチプレクサｍ０３を利用しＲ３に格納する。
【００９８】
ｐ０を非線形演算部Ｓ９０１に入力したときの出力をＳ（ｐ０）とする。その後、３ｃｙｃｌｅかけて，Ｓ（ｐ０）をＲ２，Ｒ１，Ｒ０の順に格納していく。
【００９９】
ｐ０以外の値であるｐｉ，ｉ∈｛１，２，...，１５｝に関しては、ｐ０が格納されていたレジスタにｉｃｙｃｌｅだけ遅れて格納されるようにする。ただし、Ｒ４に格納されていた値は次のサイクルで非線形演算部Ｓ９０１に入力され、その出力であるＳ（ｐｉ）がＲ３に入力されるとする。
【０１００】
最終的に、平文入力時の１６ｃｙｃｌｅ後には，Ｒ０〜Ｒ３には，（Ｓ（ｐ０），Ｓ（ｐ１），Ｓ（ｐ２），Ｓ（ｐ３））が格納され、Ｒ４〜Ｒ１５には、（ｐ４，ｐ５，...，ｐ１５）が格納されるようにマルチプレクサｍ０１，ｍ０２，ｍ０３を利用する。
【０１０１】
なお、Ｒ０〜Ｒ３に入力された（Ｓ（ｐ０），Ｓ（ｐ１），Ｓ（ｐ２），Ｓ（ｐ３））は、１ｒｏｕｎｄ目の図１８に記載のＦ関数の保持する中間値Ｉ８０４の値と一致する。
【０１０２】
次に，１ｒｏｕｎｄの演算に必要な１６ｃｙｃｌｅ分のデータの流れを説明する。
図２０は，図１３における、
ｉ∈｛１，...，ｒ｝ラウンド目のラウンド関数を表したものである。
【０１０３】
今、図２０においてｉ∈｛１，...，ｒ｝ラウンド目のラウンド関数への入力値を（ｘ０，ｘ１，...，ｘ１５）とし，ｉラウンド目のラウンド関数の出力値を（ｙ０，ｙ１，...，ｙ１５）とする。ただし、ｉ＝１のときは，（ｘ０，ｘ１，...，ｘ１５）は平文を表し、ｉ＝ｒのときは、（ｙ０，ｙ１，...，ｙ１５）は暗号文を表すこととする。
【０１０４】
図１９では、ラウンド開始時の初期状態として、Ｒ０〜Ｒ３には、（Ｓ（ｘ０），Ｓ（ｘ１），Ｓ（ｘ２），Ｓ（ｘ３））が格納され、Ｒ４〜Ｒ１５には、（ｘ４，ｘ５，...，ｘ１５）がそれぞれ格納されていると考える。
【０１０５】
なお、ｉ＝１の場合は、ラウンド開始時の初期状態として、前述の通り、
Ｒ０〜Ｒ３には、（Ｓ（ｐ０），Ｓ（ｐ１），Ｓ（ｐ２），Ｓ（ｐ３））が格納され、
Ｒ４〜Ｒ１５には，（ｐ４，ｐ５，...，ｐ１５）がそれぞれ格納されている状態を表す。
【０１０６】
表１では、図１９に記した発明手法におけるラウンド関数実行時のレジスタの保持内容を表している。１ｒｏｕｎｄを１６ｃｙｃｌｅで実行するため、各ｃｙｃｌｅ後のＲ０，Ｒ１，...，Ｒ１５のそれぞれのレジスタの保持内容を表している。また、図１９記載のように（ｘ０，ｘ１，ｘ２，ｘ３），（ｘ８，ｘ９，ｘ１０，ｘ１１）をＦ関数の入力とした場合の出力を（ｆ０，ｆ１，ｆ２，ｆ３），（ｆ８，ｆ９，ｆ１０，ｆ１１）と表すことにする。
【０１０７】
ラウンド関数実行時の１〜４ｃｙｃｌｅ目では、図１８記載の線形演算部Ｍ８０１を図１９記載の行列演算部Ｍ９０２を用いて実行する。行列演算部Ｍ９０２では，Ｒ０，Ｒ１に格納されている値に対して、有限体ＧＦ（２８）上での０ｘ０２，０ｘ０３との乗算を図１９記載のｍｕｌ０２，ｍｕｌ０３で実行する。その乗算後の値を排他的論理和し、さらに、Ｒ２，Ｒ３に格納されている値とも排他的論理和したものを出力している。
【０１０８】
このようにすることで、１ｃｙｃｌｅ目には，図１８記載の線形演算部Ｍ８０１の出力値の上位８−ｂｉｔが計算できる。
また、マルチプレクサｍ０３を利用することにより、Ｒ０に格納されている値を次のｃｙｃｌｅでＲ３に格納することで、２，３，４ｃｙｃｌｅ目には同様に図１８記載の線形演算部Ｍ８０１の出力値の９〜１６，１７〜２４，２５〜３２−ｂｉｔ目がそれぞれ計算できる。
【０１０９】
これは、想定している行列が、行ごとの要素を１行ごとに右ローテーションしている巡回行列であることを利用している。（Ｒ０，Ｒ１，Ｒ２，Ｒ３）の保持内容をｃｙｃｌｅごとに８−ｂｉｔ左ローテーションを施すことで、行列１行分の演算を実施する図１９記載の行列演算部Ｍ９０２を用いて、ｃｙｃｌｅごとに各行の演算を実施するようにしている。
【０１１０】
さらに、ラウンド関数実行時の１〜４ｃｙｃｌｅ目では、上述した線形演算部からの出力に対し、ラウンド鍵との排他的論理和演算が排他的論理和演算部Ｘ９０３で上位８−ｂｉｔから８−ｂｉｔずつ順次実行される。
【０１１１】
また、図２０記載のＦ関数Ｆ１９２の出力との排他的論理和演算Ｘ１９１は、図１９においてラウンド鍵との排他的論理和演算実行部Ｘ９０３の出力値とレジスタＲ４に格納されている値との排他的論理和演算部Ｘ９０４を利用することで実現される。
【０１１２】
Ｒ４には、１〜４ｃｙｃｌｅ目において、ｘ４，ｘ５，ｘ６，ｘ７が順次格納されるため、排他的論理和演算部Ｘ９０４の出力をマルチプレクサｍ０１を利用しレジスタＲ１５に格納することで、４ｃｙｃｌｅ後に（ｘ０，ｘ１，ｘ２，ｘ３）をＦ関数に入力したときの出力３２−ｂｉｔと３２−ｂｉｔの（ｘ４，ｘ５，ｘ６，ｘ７）を排他的論理和した値がＲ１２，Ｒ１３，Ｒ１４，Ｒ１５に８−ｂｉｔずつ格納された状態となる。
【０１１３】
表１に記載の通り、ラウンド関数開始後の４ｃｙｃｌｅ後には，Ｒ１２，Ｒ１３，Ｒ１４，Ｒ１５に（ｘ０，ｘ１，ｘ２，ｘ３）をＦ関数に入力したときの出力３２−ｂｉｔと３２−ｂｉｔの（ｘ４，ｘ５，ｘ６，ｘ７）を排他的論理和した値が格納されている。
【０１１４】
これらの値は、ラウンド関数の出力値の上位３２−ｂｉｔであるｙ０，ｙ１，ｙ２，ｙ３となる。
また、図１９記載のマルチプレクサｍ０３を利用し、Ｒ０が保持している値を次のｃｙｃｌｅではＲ３に格納するようにしていたので、表１を参照すると、ラウンド開始後の４ｃｙｃｌｅ後には、Ｒ０，Ｒ１，Ｒ２，Ｒ３の保持内容は、ラウンド開始時の値と変化していないことが分かる。
【０１１５】
また、その他のｘ８，ｘ９，...，ｘ１５は、図１９記載のマルチプレクサｍ０２を利用し、ラウンド開始後の４ｃｙｃｌｅ後には、それぞれＲ４，Ｒ５，...，Ｒ１１に格納される。
【０１１６】
次にラウンド関数実行時の５〜８ｃｙｃｌｅ目についてデータの流れを説明する。上述したように、（ｘ０，ｘ１，ｘ２，ｘ３）をＦ関数に入力したときの出力を用いた演算は実行可能ということが分かった。
しかし、ラウンド関数開始後の４ｃｙｃｌｅ後には、ラウンド関数出力の値として必要な（ｘ０，ｘ１，ｘ２，ｘ３）の値は保持しておらず、代わりにＦ関数演算時の中間値である（Ｓ（ｘ０），Ｓ（ｘ１），Ｓ（ｘ２），Ｓ（ｘ３））のみをＲ０，Ｒ１，Ｒ２，Ｒ３に保持している。
【０１１７】
５〜８ｃｙｃｌｅ目では，本発明の１つのポイントとなるＦ関数演算時の中間値からＦ関数への入力を復元する回路を用いて（ｘ０，ｘ１，ｘ２，ｘ３）を復元する。ラウンド関数開始後の４ｃｙｃｌｅ後には、Ｆ関数演算時の中間値として、Ｒ０，Ｒ１，Ｒ２，Ｒ３に（Ｓ（ｘ０），Ｓ（ｘ１），Ｓ（ｘ２），Ｓ（ｘ３））の値を保持している。
【０１１８】
図１９記載の非線形演算部Ｓ−１関数Ｓ９０５は、非線形演算部Ｓ−ｂｏｘＳ９０１の逆関数を表している。ラウンド関数開始後の５〜８ｃｙｃｌｅ目には、Ｒ０の保持値を非線形演算部Ｓ−１関数に入力し、その出力をマルチプレクサｍ０１を利用し、Ｒ１５に格納する。
【０１１９】
このようにすることで、ラウンド関数開始後の８ｃｙｃｌｅ後には、Ｒ１２，Ｒ１３，Ｒ１４，Ｒ１５にｘ０，ｘ１，ｘ２，ｘ３がそれぞれ格納された状態になる。非線形演算Ｓ−ｂｏｘの逆関数Ｓ−１関数は、拡張Ｆｅｉｓｔｅｌ構造とは異なるＳＰＮ構造を利用した暗号アルゴリズムでは、復号関数を構成する際に導入されているが、通常、拡張Ｆｅｉｓｔｅｌ構造では暗号化においても復号においても用いる必要がなく、Ｆ関数演算時の中間値からＦ関数への入力を復元するという目的のために導入された回路となる。
【０１２０】
さらに、ラウンド関数実行時の５〜８ｃｙｃｌｅ目では，図２０記載のＦ関数演算部Ｆ１９３の出力を計算するために、Ｒ４，Ｒ５，Ｒ６，Ｒ７に格納されている（ｘ８，ｘ９，ｘ１０，ｘ１１）をそれぞれ図１９記載の非線形演算部Ｓ９０１に入力し、その出力をマルチプレクサｍ０３を利用し，Ｒ０，Ｒ１，Ｒ２，Ｒ３に格納する。
【０１２１】
表１に記載の通り、ラウンド関数開始後の８ｃｙｃｌｅ後には、Ｒ１２，Ｒ１３，Ｒ１４，Ｒ１５に（ｘ０，ｘ１，ｘ２，ｘ３）の値が格納されている。これらの値は、ラウンド関数の出力値の下位３２−ｂｉｔであるｙ１２，ｙ１３，ｙ１４，ｙ１５となる。
【０１２２】
また、ラウンド関数開始後の４ｃｙｃｌｅ後にＲ４，Ｒ５，Ｒ６，Ｒ７に格納されていたｘ８，ｘ９，ｘ１０，ｘ１１は、ラウンド関数開始後の８ｃｙｃｌｅ後には、非線形演算部Ｓ９０１への入力後、マルチプレクサｍ０３を利用し、Ｒ０，Ｒ１，Ｒ２，Ｒ３に格納される。
【０１２３】
また、その他のｘ１２，ｘ１３，ｘ１４，ｘ１５，ｙ０，ｙ１，ｙ２，ｙ３は、図１９記載のマルチプレクサｍ０２を利用し、ラウンド開始後の８ｃｙｃｌｅ後には、それぞれＲ４，Ｒ５，...，Ｒ１１に格納される。
【０１２４】
次にラウンド関数実行時の９〜１２ｃｙｃｌｅ目のデータの流れを説明する。まず、図２０記載のＦ関数演算部Ｆ１９３中の図１８記載の線形演算部Ｍ８０１を図１９記載の行列演算部Ｍ９０２を用いて実行する。
【０１２５】
行列演算部Ｍ９０２では、Ｒ０，Ｒ１に格納されている値に対して，有限体ＧＦ（２８）上での０ｘ０２，０ｘ０３との乗算を図１９記載のｍｕｌ０２，ｍｕｌ０３で実行する。その乗算後の値を排他的論理和し、さらに，Ｒ２，Ｒ３に格納されている値とも排他的論理和したものを出力している。
【０１２６】
このようにすることで、ラウンド関数開始後の９ｃｙｃｌｅ目には、図１８記載の線形演算部Ｍ８０１の出力値の上位８−ｂｉｔが計算できる。また、マルチプレクサｍ０３を利用することにより、Ｒ０に格納されている値を次のｃｙｃｌｅでＲ３に格納することで、２，３，４ｃｙｃｌｅ目には同様に図１８記載の線形演算部Ｍ８０１の出力値の９〜１６，１７〜２４，２５〜３２−ｂｉｔ目が計算できる。
【０１２７】
さらに、ラウンド関数実行時の９〜１２ｃｙｃｌｅ目では、上述した線形演算部からの出力に対し、ラウンド鍵との排他的論理和演算が排他的論理和演算部Ｘ９０３で上位８−ｂｉｔから８−ｂｉｔずつ順次実行される。また、図２０記載のＦ関数Ｆ１９３の出力との排他的論理和演算Ｘ１９１は、図１９においてラウンド鍵との排他的論理和演算実行部Ｘ９０３の出力値とレジスタＲ４に格納されている値との排他的論理和演算部Ｘ９０４を利用することで実現される。
【０１２８】
Ｒ４には、９〜１２ｃｙｃｌｅ目において、ｘ１２，ｘ１３，ｘ１４，ｘ１５が順次格納されるため、排他的論理和演算部Ｘ９０４の出力をマルチプレクサｍ０１を利用しレジスタＲ１５に格納することで、４ｃｙｃｌｅ後に（ｘ８，ｘ９，ｘ１０，ｘ１１）をＦ関数に入力したときの出力３２−ｂｉｔと３２−ｂｉｔの（ｘ１２，ｘ１３，ｘ１４，ｘ１５）を排他的論理和した値がＲ１２，Ｒ１３，Ｒ１４，Ｒ１５に８−ｂｉｔずつ格納された状態となる。
【０１２９】
表１に記載の通り、ラウンド関数開始後の４ｃｙｃｌｅ後には，Ｒ１２，Ｒ１３，Ｒ１４，Ｒ１５に（ｘ８，ｘ９，ｘ１０，ｘ１１）をＦ関数に入力したときの出力３２−ｂｉｔと３２−ｂｉｔの（ｘ１２，ｘ１３，ｘ１４，ｘ１５）を排他的論理和した値が格納されている。
【０１３０】
これらの値は、ラウンド関数の出力値の６５−ｂｉｔ目から９６−ｂｉｔ目であるｙ８，ｙ９，ｙ１０，ｙ１１となる。また、図１９記載のマルチプレクサｍ０３を利用し、Ｒ０が保持している値を次のｃｙｃｌｅではＲ３に格納するようにしていたので、表１を参照すると、ラウンド開始後の８ｃｙｃｌｅ後と１２ｃｙｃｌｅ後のＲ０，Ｒ１，Ｒ２，Ｒ３の保持内容は、変化しないことが分かる。
【０１３１】
また、その他のｙ０，ｙ１，ｙ２，ｙ３，ｙ１２，ｙ１３，ｙ１４，ｙ１５は、図１９記載のマルチプレクサｍ０２を利用し、ラウンド開始後の１２ｃｙｃｌｅ後には、それぞれＲ４，Ｒ５，...，Ｒ１１に格納される。
【０１３２】
次にラウンド関数実行時の１３〜１６ｃｙｃｌｅ目についてデータの流れを説明する。上述したように，（ｘ８，ｘ９，ｘ１０，ｘ１１）をＦ関数に入力したときの出力を用いた演算は実行可能ということが分かった。
しかし、ラウンド関数開始後の４ｃｙｃｌｅ後には、ラウンド関数出力の値として必要な（ｘ８，ｘ９，ｘ１０，ｘ１１）の値は保持しておらず、代わりにＦ関数演算時の中間値である（Ｓ（ｘ８），Ｓ（ｘ９），Ｓ（ｘ１０），Ｓ（ｘ１１））のみをＲ０，Ｒ１，Ｒ２，Ｒ３に保持している。
【０１３３】
１３〜１６ｃｙｃｌｅ目では、本発明のポイントとなるＦ関数演算時の中間値からＦ関数への入力を復元する回路を用いて（ｘ８，ｘ９，ｘ１０，ｘ１１）を復元する。ラウンド関数開始後の１２ｃｙｃｌｅ後には、Ｆ関数演算時の中間値として，Ｒ０，Ｒ１，Ｒ２，Ｒ３に（Ｓ（ｘ８），Ｓ（ｘ９），Ｓ（ｘ１０），Ｓ（ｘ１１））の値を保持している。
【０１３４】
図１９記載の非線形演算部Ｓ−１関数Ｓ９０５は，非線形演算部Ｓ−ｂｏｘＳ９０１の逆関数を表している。ラウンド関数開始後の１３〜１６ｃｙｃｌｅ目には、Ｒ０の保持値を非線形演算部Ｓ−１関数に入力し、その出力をマルチプレクサｍ０２を利用し、Ｒ７に格納する。
【０１３５】
このようにすることで、ラウンド関数開始後の１６ｃｙｃｌｅ後には、Ｒ４，Ｒ５，Ｒ６，Ｒ７にｘ８，ｘ９，ｘ１０，ｘ１１がそれぞれ格納された状態になる。さらに、ラウンド関数実行時の１３〜１６ｃｙｃｌｅ目では、次のラウンド関数演算のため、Ｒ４，Ｒ５，Ｒ６，Ｒ７に格納されている（ｙ０，ｙ１，ｙ２，ｙ３）をそれぞれ図１９記載の非線形演算部Ｓ９０１に入力し、その出力をマルチプレクサｍ０３を利用し、Ｒ０，Ｒ１，Ｒ２，Ｒ３に格納する。
【０１３６】
表１に記載の通り、ラウンド関数開始後の１６ｃｙｃｌｅ後には、Ｒ４，Ｒ５，Ｒ６，Ｒ７に（ｘ８，ｘ９，ｘ１０，ｘ１１）の値が格納されている。これらの値は、ラウンド関数の出力値の３３−ｂｉｔ目から６４−ｂｉｔ目であるｙ４，ｙ５，ｙ６，ｙ７となる。
【０１３７】
また、ラウンド関数開始後の１２ｃｙｃｌｅ後にＲ４，Ｒ５，Ｒ６，Ｒ７に格納されていたｙ０，ｙ１，ｙ２，ｙ３は、ラウンド関数開始後の１６ｃｙｃｌｅ後には、非線形演算部Ｓ９０１への入力後、マルチプレクサｍ０３を利用し、Ｒ０，Ｒ１，Ｒ２，Ｒ３に格納される。
【０１３８】
また、ｙ８，ｙ９，ｙ１０，ｙ１１は、ラウンド関数開始後の１６ｃｙｃｌｅ後には、Ｒ８，Ｒ９，Ｒ１０，Ｒ１１にそれぞれ格納される。
また、ｙ１２，ｙ１３，ｙ１４，ｙ１５は、図１９記載のマルチプレクサｍ０１を利用し、ラウンド関数開始後の１６ｃｙｃｌｅ後には、それぞれＲ１２，Ｒ１３，Ｒ１４，Ｒ１５に格納される。
【０１３９】
最後に、暗号文出力時の１６ｃｙｃｌｅ分のデータの流れを説明する。
ｉ∈｛０，１，...，１５｝
に対して、ｃｉを８−ｂｉｔの要素とする。
このとき、（ｃ０，ｃ１，...，ｃ１５）で表される１２８−ｂｉｔを暗号文として考える。
【０１４０】
図１３記載のｒラウンド分のラウンド関数終了時には，図１９記載のＲ０，Ｒ１，...，Ｒ１５には、それぞれ、
Ｓ（ｃ４），Ｓ（ｃ５），Ｓ（ｃ６），Ｓ（ｃ７），ｃ８，ｃ９，ｃ１０，ｃ１１，ｃ１２，ｃ１３，ｃ１４，ｃ１５，ｃ０，ｃ１，ｃ２，ｃ３、
が格納されている。
【０１４１】
暗号文出力時の１６ｃｙｃｌｅでは、Ｒ０に格納されている値は、毎サイクルごとに非線形演算部Ｓ−１関数Ｓ９０５に入力し、その出力をマルチプレクサｍ０１を利用し、Ｒ１５に格納するようにする。
【０１４２】
また、Ｒ８に格納されている値は、毎サイクルごとにマルチプレクサｍ０２を利用し、Ｒ７に格納するようにする。また、Ｒ４に格納されている値は、毎サイクルごとに非線形演算部Ｓ−ｂｏｘＳ９０１に入力し、その出力をマルチプレクサｍ０３を利用し、Ｒ３に格納するようにする。また、暗号文出力時のは毎サイクルごとに、Ｒ１２の値を図１９での暗号文出力ポートから出力する。
上記のようにすることで，暗号文出力ポートから，毎サイクルごとにｃ０，ｃ１，...，ｃ１５の順で順次出力される。
【０１４３】
上述したように、図１９に示す構成において、非線形演算部Ｓ−１関数Ｓ９０５は、非線形演算部Ｓ−ｂｏｘＳ９０１の逆関数を表している。非線形演算部Ｓ−１関数Ｓ９０５は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図１８に示す中間値Ｉ８０４）からＦ関数への入力を復元する演算を実行する。この逆演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１４４】
［４．本開示の手法の効果のまとめ］
従来手法では、Ｆ関数への入力を保持したまま、Ｆ関数の出力を演算していた。この考えのもとでは、ｂｌｏｃｋ長分のレジスタに加え，Ｆ関数演算時の中間値を保持するレジスタが必要となる。
【０１４５】
一方、上述した発開示に係る手法では、Ｆ関数への入力は一度破棄し、Ｆ関数の出力を計算後にＦ関数演算時の中間値から元の入力を復元するための回路を導入する構成としている。
【０１４６】
このようにすることで、必要なレジスタはｂｌｏｃｋ長分のみとなり、従来手法において必要であったＦ関数演算時の中間値を保持するレジスタ分の回路を削減することが可能となる。前章の発明手法の適用例では、Ｆ関数演算時に必要な中間値として図１８に記載の非線形演算部Ｓ８０１後の線形演算部Ｍ８０２に入力される値である保持する中間値Ｉ８０４とし、Ｆ関数の出力を計算可能としている。
【０１４７】
また，従来手法では用いないＳ−ｂｏｘの逆演算処理回路を導入することにより、上記のＦ関数演算時の中間値からＦ関数への入力を復元するようにしている。このようにすることで，結果的にレジスタの削減を達成している。レジスタの回路規模は、他のセルに比べて比較的大きなものとなるため、レジスタの削減が小型化に寄与することは多い。
【０１４８】
［５．その他の実施例について］
前節では，４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造においてラウンド関数内部の構成要素もある程度仮定し、適用法と効果について説明した。本開示の手法は、前節までに説明した具体的なラウンド関数の構造のみではなく、変形、拡張された構造についても適用可能である。
【０１４９】
また、本開示の手法は、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造のみでなく、２−ｌｉｎｅのＦｅｉｓｔｅｌ構造や，任意のｘ（ｘは２以上の自然数）に対して、ｘ−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に対しても同様な考え方が適用できる。
【０１５０】
（５−１．拡張例１）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２１に記載のＳＰＳ型Ｆ関数にも適用可能である。この場合に考えられるデータパスの例を図２２に示す。
【０１５１】
図２２では、行列の一例として，１行目の要素が（２，３，１，１）となる巡回行列を想定している。また、図２１に記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対して本開示の手法を適用する場合のポイントである保持すべき中間値の例としては、第一非線形演算部Ｓ１０１の出力であり、線形演算部Ｍ１０２への入力となる。
図２１に示す保持する中間値Ｉ１０４となる。
【０１５２】
この場合も、図１８に記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対するＨＷ実装構成例である図１９でのデータの流れと同様に考えられるため、詳細な説明は省略する。
【０１５３】
図１９に記載のデータパスと異なる点を簡単に説明すると、図２２記載のデータパスでは、非線形演算部Ｓ−ｂｏｘＳ１１１の入力前にマルチプレクサｍ０１が導入され、行列演算部Ｍ１１２の出力がマルチプレクサｍ０１を利用し、非線形演算部Ｓ−ｂｏｘＳ１１１に入力され、Ｓ−ｂｏｘＳ１１１の出力がラウンド鍵との排他的論理和部Ｘ１１４に直接入力されている点である。
【０１５４】
これは、図１８記載のＳＰ型Ｆ関数ではなく、図２１記載のＳＰＳ型Ｆ関数を想定している点に起因する。図２１記載のＳＰＳ型Ｆ関数では、線形変換部Ｍ１０２の出力を第二非線形変換部Ｓ１０３に入力し、その第二非線形変換部Ｓ１０３の出力をラウンド鍵との排他的論理和部Ｘ１０５に入力するからである。
【０１５５】
図２２に示す構成において、非線形演算部Ｓ−１関数Ｓ１１３は、非線形演算部Ｓ−ｂｏｘＳ１１１の逆関数を表している。非線形演算部Ｓ−１関数Ｓ１１３は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図２１に示す中間値Ｉ１０４）からＦ関数への入力を復元する演算を実行する。この逆演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１５６】
（５−２．拡張例２）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２３に記載の鍵挿入が複数入ったＳＰＳ型Ｆ関数にも適用可能である。この場合に考えられるデータパスの例を図２４に示す。
【０１５７】
図２４では、行列の一例として、１行目の要素が（２，３，１，１）となる巡回行列を想定している。また、図２３記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対して本開示の手法を適用する場合のポイントである保持すべき中間値の例としては、第一非線形演算部Ｓ１２１の出力であり、線形演算部Ｍ１２２への入力となる。
保持する中間値は、図２３に示す保持する中間値Ｉ１２４となる。
【０１５８】
この場合も、図１８に記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対するＨＷ実装構成例である図１９でのデータの流れを考察することで推測可能と考えられるため、詳細な説明は省略する。
【０１５９】
図１９に記載のデータパスと異なる点を簡単に説明すると、図２４記載のデータパスでは、非線形演算部Ｓ−ｂｏｘＳ１３１の入力前にマルチプレクサｍ０１が導入され、行列演算部Ｍ１３２の出力がラウンド鍵との排他的論理和演算部Ｘ１３４へ入力され、その出力がマルチプレクサｍ０１を利用し、非線形演算部Ｓ−ｂｏｘＳ１３１に入力され、Ｓ−ｂｏｘＳ１３１の出力がラウンド鍵との排他的論理和部Ｘ１３５に直接入力されている点である。
【０１６０】
これは、図１８記載のＳＰ型Ｆ関数ではなく、図２３記載の鍵挿入を複数行なうＳＰＳ型Ｆ関数を想定している点に起因する。図２３記載の鍵挿入を複数行なうＳＰＳ型Ｆ関数では、線形変換部Ｍ１２２の出力を第一のラウンド鍵との排他的論理和演算部Ｘ１２５に入力し、その第一のラウンド鍵との排他的論理和演算部Ｘ１２５の出力を、第二非線形変換部Ｓ１２３に入力し、その第二非線形変換部Ｓ１２３の出力を第二のラウンド鍵との排他的論理和部Ｘ１２６に入力するからである。
【０１６１】
図２４に示す構成において、非線形演算部Ｓ−１関数Ｓ１３３は、非線形演算部Ｓ−ｂｏｘＳ１３１の逆関数を表している。非線形演算部Ｓ−１関数Ｓ１３３は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図２３に示す中間値Ｉ１２４）からＦ関数への入力を復元する演算を実行する。この逆演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１６２】
（５−３．拡張例３）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２５に記載の鍵挿入がＦ関数入力直後にあるＳＰ型Ｆ関数にも適用可能である。この場合に考えられるデータパスの例を図２６に示す。
【０１６３】
図２５に記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対して発明手法を適用する場合のポイントである保持すべき中間値の例としては、非線形演算部Ｓ１４１の出力であり、線形演算部Ｍ１４２への入力となる。
保持する中間値は、図２５に示す保持する中間値Ｉ１４４となる。
【０１６４】
図１８に表されるＦ関数と異なり、Ｆ関数演算時の中間値である図２５記載の保持する中間値Ｉ１４４からＦ関数への入力を復元するためには、Ｓ−１だけでなく、Ｆ関数への入力直後に排他的論理和したときと同じラウンド鍵を排他的論理和する回路が必要となる。これは、図１８に表されるＦ関数と異なり、図２５に記載の保持する中間値からＦ関数の入力を復元するためには、非線形演算部Ｓ１４１の逆演算のみでなく、その逆演算した値に対して、ラウンド鍵との排他的論理和演算部Ｘ１４３の逆演算も必要となるためである。
【０１６５】
この場合も、図１８記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対するＨＷ実装構成例である図１９でのデータの流れを考察することで推測可能と考えられるため、詳細な説明は省略する。図２６記載のデータパスでは、非線形演算部Ｓ−ｂｏｘＳ１５１の入力前にラウンド鍵との排他的論理和演算部Ｘ１５４が導入される。
【０１６６】
一方、行列演算部Ｍ１５２からの出力は、ラウンド鍵との排他的論理和演算を実行せずに、Ｒ４に格納されている値との排他的論理和演算部Ｘ１５６に直接入力される。また、Ｒ０に格納されている値は、非線形演算Ｓ−１関数に入力後、ラウンド鍵との排他的論理和演算部Ｘ１５５に入力されている点も図１９と異なる点である。これは、前述の通り、図２５記載の保持する中間値Ｉ１４４からＦ関数の入力を復元するためには、非線形演算部Ｓ１４１の逆演算のみでなく、その逆演算した値に対して、ラウンド鍵との排他的論理和演算部Ｘ１４３の逆演算も必要となるためである。
【０１６７】
図２６に示す構成において、非線形演算部Ｓ−１関数Ｓ１５３は、非線形演算部Ｓ−ｂｏｘＳ１５１の逆関数を表している。非線形演算部Ｓ−１関数Ｓ１５３は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図２５に示す中間値Ｉ１４４）からＦ関数への入力を復元する演算を実行する。この逆演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１６８】
（５−４．拡張例４）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２７に記載のＦ関数にも適用可能である。図２７に記載のＦ関数は、これまでに説明したＦ関数と大きく構造が異なるため、詳細に説明する。
【０１６９】
図２７に記載のＦ関数は、Ｆ関数への入力を第一の非線形演算部Ｓ１６１で演算し、その第一の非線形演算部Ｓ１６１の出力を第二の非線形演算部Ｓ１６２へ入力する。その後、繰り返し構造となり、第一，第二の非線形演算部と同じ演算をｓ−１回施し、最終的に第一，第二の非線形演算部と同じ演算である、第ｓの非線形演算部Ｓ１６ｓの出力をラウンド鍵との排他的論理和演算部Ｘ１０５に入力し、その出力をＦ関数の出力とするような構造である。
【０１７０】
このようなＦ関数においても、シリアル処理を実行するハードウェア回路を考えたときには、各サイクルごとにＦ関数演算時の中間値である図２７に記載の保持する中間値Ｉ１６４の値を保持するレジスタが必要となる。
【０１７１】
図２７に記載のＦ関数を保持する拡張Ｆｅｉｓｔｅｌ構造を持つ暗号アルゴリズムに対しても発明手法の効果は得られる。図１８，図１９で紹介したことと同様に，図２７に記載の保持する中間値Ｉ１６４からＦ関数の入力を復元することが可能であるため、そのための回路を導入することで、ブロック長分のみのレジスタで回路を実現できる。
【０１７２】
Ｆ関数内部が繰り返し構造となっているが、ｓ＝４としたときに考えられるデータパスの例を図２８に示す。図２７に記載のＦ関数は内部の繰り返し構造が４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造と似ており、Ｆｅｉｓｔｅｌ構造の性質から非線形回路Ｓ−１関数を用いずとも、Ｓ−ｂｏｘ回路である非線形演算部Ｓ１７２，Ｓ１７３のみを用いることにより、図２７に記載の保持する中間値Ｉ１６４からＦ関数の入力を復元することが可能である。
【０１７３】
図２８に示す構成において、非線形演算部Ｓ１７２，Ｓ１７３は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図２７に示す中間値Ｉ１６４）からＦ関数への入力を復元する演算を実行する。この演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１７４】
また、図２８に記載のデータパスでは、Ｓ−ｂｏｘ回路を二つ利用しているが、一つだけを利用することでもデータパスを記述することが可能であることは容易に推測できる。また、データパスは多少変更する必要があるが任意の繰り返し段数ｓに対してデータパスは構成可能である。また、図２８に現れる"ｅｎ"という記号で表される制御信号Ｅ１７４は、必要なタイミングでｈｉｇｈとなるように制御されるイネーブル信号を表し、図２８には示されていないが制御部によって制御がされる。
【０１７５】
（５−５．拡張例５）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２９に記載のＦ関数にも適用可能である。図２９は、図２７に記載の繰り返し型のＦ関数の非線形演算部Ｓ１６１，Ｓ１６２，Ｓ１６ｓが，図２９記載の非線形演算部Ｓ１８１，Ｓ１８２，Ｓ１８ｓに変更されたものと考えることができる。
【０１７６】
このようなＦ関数においても、シリアル処理を実行するハードウェア回路考えたときには、各サイクルごとにＦ関数演算時の中間値である図２９記載の保持する中間値Ｉ１８４の値を保持するレジスタが必要となる。
【０１７７】
図２９に記載のＦ関数を保持する拡張Ｆｅｉｓｔｅｌ構造を持つ暗号アルゴリズムに対しても発明手法の効果は得られる。図１８，図１９を参照して説明したことと同様に、図２９に記載の保持する中間値Ｉ１８４からＦ関数の入力を復元することが可能であるため、そのための回路を導入することで、ブロック長分のみのレジスタで回路を実現できる。
【０１７８】
Ｆ関数の構造上、Ｓ−ｂｏｘの逆演算処理回路であるＳ−１を導入することで、図２９に記載の保持する中間値Ｉ１８４からＦ関数の入力を復元することが可能である。また、Ｆ関数内部が繰り返し構造となっているが、任意の繰り返し段数に対して発明手法は適用可能である。
【０１７９】
（５−６．拡張例６）
ここで記載した具体的なＦ関数の構成は限られたものであるが、本開示の手法は、適した回路を導入することで中間値からＦ関数の入力を復元することが可能となる任意のＦ関数に適用可能である。
【０１８０】
（５−７．拡張例７）
Ｆ関数に行列演算を含む場合、本開示の手法は、巡回行列のみでなくアダマール行列に対しても適用可能であり、同様の効果が期待できる。また、上記以外の行列に対しても発明手法のアイデアは適用できる。
【０１８１】
（５−８．拡張例８）
Ｆ関数に行列演算を含む場合、本開示の方式は、４×４行列のみでなく任意のｘ（ｘは２以上の自然数）に対して，ｘ×ｘ行列でも同様の考えが適用可能であり、同様の効果が期待できる。
【０１８２】
（５−９．拡張例９）
４−ｌｉｎｅｔｙｐｅ−２拡張Ｆｅｉｓｔｅｌ構造を例に本開示の手法の適用例について説明したが、ｔｙｐｅ−１，ｔｙｐｅ−３の拡張Ｆｅｉｓｔｅｌ構造に対しても適用可能であり、同様の効果が期待できる。
【０１８３】
（５−１０．拡張例１０）
４−ｌｉｎｅｔｙｐｅ−２拡張Ｆｅｉｓｔｅｌ構造を例に本開示の手法の適用例について説明したが、２−ｌｉｎｅのＦｅｉｓｔｅｌ構造に対しても適用可能であり、同様の効果が期待できる。
【０１８４】
（５−１１．拡張例１１）
４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造への適用と同様の考えで、任意のｘ（ｘは３以上の自然数）に対して、ｘ−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に対しても適用可能であり、同様の効果が期待できる。
【０１８５】
（５−１２．拡張例１２）
図２０に点線枠で示すように、１つのラウンド関数の出力は、次の段のラウンド関数へ出力する際に、各ラインのデータ単位でシフト処理等の入れ替え処理が行われる。
このラウンド関数間のデータ入れ替え、すなわち、前段のラウンドの出力を後段のラウンドへ出力する際に、各ライン単位でデータを入れ替える処理をラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）と呼ぶ。
【０１８６】
例えば、図２０に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造における、ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）は以下の設定となっている。
左から１番目のラインの出力を、次のラウンド関数の左から４番目のラインへの入力に設定、
左から２番目のラインの出力を、次のラウンド関数の左から１番目のラインへの入力に設定、
左から３番目のラインの出力を、次のラウンド関数の左から２番目のラインへの入力に設定、
左から４番目のラインの出力を、次のラウンド関数の左から３番目のラインへの入力に設定、
上記のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の設定例である。
【０１８７】
例えば図１９を参照して説明したデータパスは、上記のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）設定に対応したデータパス構成例である。
【０１８８】
本開示の方式は、図２０に示すウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の設定に限らず、任意のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）に対して適用可能である。
【０１８９】
すなわち、任意のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）を持つ構成においても、Ｆ関数実行部における中間データからの逆演算構成を設定することで、上述したと同様のレジスタ削減効果が期待できる。
ただし、データパスの設定は、各ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の設定に応じた構成とすることが必要である。
【０１９０】
図２０に示すラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）構成と異なるラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の１つの構成例を図３０に示す。
図３０に示すラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）は、前段のラウンド関数の各ライン出力である（ｎ／４）ｂｉｔのそれぞれを２分割し、（ｎ／８）ｂｉｔの２つのライン出力に分割する。
各々が（ｎ／８）ｂｉｔのデータを持つ計８ラインのデータを次のラウンド関数に入力する際に、各ライン単位でデータ入れ替え（置換）を行う構成としている。
【０１９１】
図３０に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造における、ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）は以下の設定となっている。
左から１番目のラインの出力を２分割した前半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から４番目のラインの前半データ（ｎ／８）ｂｉｔの入力に設定、
左から１番目のラインの出力を２分割した後半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から２番目のラインの後半データ（ｎ／８）ｂｉｔの入力に設定、
左から２番目のラインの出力を２分割した前半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から１番目のラインの前半データ（ｎ／８）ｂｉｔの入力に設定、
左から２番目のラインの出力を２分割した後半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から３番目のラインの後半データ（ｎ／８）ｂｉｔの入力に設定、
【０１９２】
左から３番目のラインの出力を２分割した前半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から２番目のラインの前半データ（ｎ／８）ｂｉｔの入力に設定、
左から３番目のラインの出力を２分割した後半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から４番目のラインの後半データ（ｎ／８）ｂｉｔの入力に設定、
左から４番目のラインの出力を２分割した前半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から３番目のラインの前半データ（ｎ／８）ｂｉｔの入力に設定、
左から４番目のラインの出力を２分割した後半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から１番目のラインの後半データ（ｎ／８）ｂｉｔの入力に設定、
上記のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の設定例である。
なお、図３０に示すラウンド関数におけるＦ関数は、図２１に記載したＳＰＳ型Ｆ関数であると想定している。
【０１９３】
図３０に示す、ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）を実行する構成におけるラウンド関数部のデータパスの例を図３１に示す。
図３１に示すデータパスは、Ｆ関数として、図２１に記載のＳＰＳ型Ｆ関数を適用した場合の構成例である。また、Ｆ関数における線形変換実行部である行列演算部Ｍ２０４で適用する行列の一例として，１行目の要素が（２，３，１，１）となる巡回行列を想定している。
【０１９４】
本構成例においてレジスタに保持する中間値は，図２１に示す第一非線形演算部Ｓ１０１の出力であり、線形演算部Ｍ１０２への入力であり、図２１に示す中間値Ｉ１０４となる。
図３１において、これらの中間値は、レジスタＲ０〜Ｒ３に保持される。
基本的なデータの流れは、先に拡張例１として説明した図２２に示すデータパスと同様のものであり、非線形演算部Ｓ−ｂｏｘＳ２０３の入力前にマルチプレクサｍ２０２が設定されている。行列演算部Ｍ２０４の出力がマルチプレクサｍ２０２を利用し、非線形演算部Ｓ−ｂｏｘＳ２０３に入力され、Ｓ−ｂｏｘＳ２０３の出力が排他的論理和部Ｘ２０６に入力される。
【０１９５】
図３１に記載のデータパスでは、図２２に示す構成と異なり、Ｓ−ｂｏｘＳ２０３の出力に対してラウンド鍵との排他的論理和演算を実行する前に、排他的論理和演算部Ｘ２０６に入力され、レジスタＲ４に格納されている値との排他的論理和演算を実行する構成としている。この排他的論理和結果とラウンド鍵が、排他的論理和演算部Ｘ２０１において排他的論理和演算される。
【０１９６】
また、レジスタＲ８とレジスタＲ１５を結ぶパスｐ２１１と、ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部Ｘ２０１の出力とレジスタＲ７を結ぶパスｐ２１２を加えている。これは、図２２とは異なるラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｔｉｏｎ）、すなわち図３０に示す設定のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｔｉｏｎ）を実現するためのパス設定である。
【０１９７】
この図３１に示すデータパスにおいても、前述した図１９、図２２他の実施例と同様、Ｆ関数実行部における中間データからの逆演算構成、すなわち非線形演算部Ｓ−１関数Ｓ２０５を設定することで、次段のラウンド関数に対する入力値を算出可能とすることで、上述したと同様のレジスタ削減効果が期待できる。
【０１９８】
［６．暗号処理装置の構成例について］
最後に、上述した実施例に従った暗号処理を実行する暗号処理装置の実装例について説明する。
上述した実施例に従った暗号処理を実行する暗号処理装置は、暗号処理を実行する様々な情報処理装置に搭載可能である。具体的には、ＰＣ、ＴＶ、レコーダ、プレーヤ、通信機器、さらに、ＲＦＩＤ、スマートカード、センサネットワーク機器、デンチ／バッテリー認証モジュール、健康、医療機器、自立型ネットワーク機器等、例えばデータ処理や通信処理に伴う暗号処理を実行する様々な危機において利用可能である。
【０１９９】
本開示の暗号処理を実行する装置の一例としてのＩＣモジュール７００の構成例を図３２に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図３２に示すＩＣモジュール７００は、これら様々な機器に構成することが可能である。
【０２００】
図３２に示すＣＰＵ(Central processing Unit)７０１は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ７０２は、ＣＰＵ７０１が実行するプログラム、あるいは演算パラメータなどの固定データを格納するＲＯＭ（Read-Only-Memory）、ＣＰＵ７０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるＲＡＭ（Random Access Memory）等からなる。また、メモリ７０２は暗号処理に必要な鍵データや、暗号処理において適用する変換テーブル（置換表）や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【０２０１】
暗号処理部７０３は、上記において説明した暗号処理構成、すなわち、例えば拡張Ｆｅｉｓｔｅｌ構造や、Ｆｅｉｓｔｅｌ構造を適用した共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理を実行する。
【０２０２】
なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭに格納し、ＣＰＵ７０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。
【０２０３】
乱数発生器７０４は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【０２０４】
送受信部７０５は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ＩＣモジュールとのデータ通信を実行し、ＩＣモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【０２０５】
なお、上述した実施例において説明した暗号処理装置は、入力データとしての平文を暗号化する暗号化処理に適用可能であるのみならず、入力データとしての暗号文を平文に復元する復号処理にも適用可能である。
暗号化処理、復号処理、双方の処理において、上述した実施例において説明したレジスタ削減構成を持つＦ関数実行部の構成をそのまま適用することが可能である。
【０２０６】
［７．本開示の構成のまとめ］
以上、特定の実施例を参照しながら、本開示の実施例について詳解してきた。しかしながら、本開示の要旨を逸脱しない範囲で当業者が実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本開示の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０２０７】
なお、本明細書において開示した技術は、以下のような構成をとることができる。
（１）データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、
前記Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行部と、
を有する暗号処理装置。
【０２０８】
（２）前記Ｆ関数実行部は、Ｆ関数実行部への入力データに対する非線形変換処理を実行するＳ−ｂｏｘを有し、前記中間データ格納レジスタは、前記Ｓ−ｂｏｘの出力値を中間データとして保持し、前記逆演算実行部は、前記Ｓ−ｂｏｘによる非線形変換処理の逆演算を含む演算処理により、前記Ｆ関数実行部に対する入力データを算出する前記（１）に記載の暗号処理装置。
【０２０９】
（３）前記Ｆ関数実行部は、非線形変換部、および線形変換部を有し、前記非線形変換部の出力を前記中間データとして格納するレジスタを有し、前記線形変換部は、前記レジスタの格納値に対する線型変換処理を実行し、前記逆演算実行部は、前記レジスタの格納値に対する演算処理により、前記Ｆ関数実行部に対する入力データを算出する前記（１）または（２）に記載の暗号処理装置。
【０２１０】
（４）前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行するＳＰ型Ｆ関数である前記（１）〜（３）いずれかに記載の暗号処理装置。
【０２１１】
（５）前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行し、さらに非線形変換部において再度、非線形変換処理をするＳＰＳ型Ｆ関数である前記（１）〜（４）いずれかに記載の暗号処理装置。
【０２１２】
（６）前記Ｆ関数実行部は、外部から入力するラウンド鍵との排他的論理和演算部を有する前記（１）〜（５）いずれかに記載の暗号処理装置。
（７）前記Ｆ関数実行部は、複数の非線形演算部の繰り返し構造を有する前記（１）〜（６）いずれか１に記載の暗号処理装置。
（８）前記暗号処理部は、入力データとしての平文を暗号文に変換する暗号化処理、または、入力データとしての暗号文を平文に変換する復号処理を実行する前記（１）〜（７）いずれか１に記載の暗号処理装置。
【０２１３】
さらに、上記した装置およびシステムにおいて実行する処理の方法や、処理を実行させるプログラムも本開示の構成に含まれる。
【０２１４】
また、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。例えば、プログラムは記録媒体に予め記録しておくことができる。記録媒体からコンピュータにインストールする他、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介してプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０２１５】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０２１６】
上述したように、本開示の一実施例の構成によれば、暗号処理構成の小型化が実現される。
具体的には、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、暗号処理部は、複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、中間データ格納レジスタの格納データに基づいて、Ｆ関数実行部に対する入力データを算出する逆演算実行部を有する。逆演算実行部における逆演算により、Ｆ関数実行部に対する入力値を算出可能となり、このデータを保持するレジスタを削減することが可能となり、暗号処理構成の小型化が実現される。
【符号の説明】
【０２１７】
７００ ＩＣモジュール
７０１ ＣＰＵ(Central processing Unit)
７０２ メモリ
７０３ 暗号処理部
７０４ 乱数生成部
７０５ 送受信部
【技術分野】
【０００１】
本開示は、暗号処理装置、および暗号処理方法、並びにプログラムに関する。さらに詳細には、共通鍵系暗号を実行する暗号処理装置、および暗号処理方法、並びにプログラムに関する。
【背景技術】
【０００２】
情報化社会が発展すると共に、扱う情報を安全に守るための情報セキュリティ技術の重要性が増してきている。情報セキュリティ技術の構成要素の一つとして暗号技術があり、現在では様々な製品やシステムで暗号技術が利用されている。
【０００３】
暗号処理アルゴリズムには様々なものがあるが、基本的な技術の一つとして、共通鍵ブロック暗号と呼ばれるものがある。共通鍵ブロック暗号では、暗号化用の鍵と復号用の鍵が共通のものとなっている。暗号化処理、復号処理共に、その共通鍵から複数の鍵を生成し、あるブロック単位、例えば６４ビット、１２８ビット、２５６ビット等のブロックデータ単位でデータ変換処理を繰り返し実行する。
【０００４】
代表的な共通鍵ブロック暗号のアルゴリズムとしては、過去の米国標準であるＤＥＳ（Ｄａｔａ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）や現在の米国標準であるＡＥＳ（Ａｄｖａｎｃｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）が知られている。他にも様々な共通鍵ブロック暗号が現在も提案され続けており、２００７年にソニー株式会社が提案したＣＬＥＦＩＡも共通鍵ブロック暗号の一つである。
【０００５】
このような、共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を繰り返し実行するラウンド関数実行部を有する暗号処理部と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部とによって構成される。鍵スケジュール部は、秘密鍵であるマスター鍵（主鍵）に基づいて、まずビット数を増加させた拡大鍵を生成し、生成した拡大鍵に基づいて、暗号処理部の各ラウンド関数部で適用するラウンド鍵（副鍵）を生成する。
【０００６】
このようなアルゴリズムを実行する具体的な構造として、線形変換部および非線形変換部を有するラウンド関数を繰り返し実行する構造が知られている。例えば代表的な構造にＦｅｉｓｔｅｌ構造や拡張Ｆｅｉｓｔｅｌ構造がある。Ｆｅｉｓｔｅｌ構造や拡張Ｆｅｉｓｔｅｌ構造は、データ変換関数としてのＦ関数を含むラウンド関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。Ｆ関数においては、線形変換処理および非線形変換処理が実行される。なお、Ｆｅｉｓｔｅｌ構造および拡張Ｆｅｉｓｔｅｌ構造を適用した暗号処理について記載した文献としては、例えば非特許文献１、非特許文献２がある。
【０００７】
暗号アルゴリズムの実装形態には、ソフトウェア実装とハードウェア実装の二種類が存在する。ハードウェア実装では、回路規模が小さくなるように実装することで、ハードウェア化の際のコストダウンや低消費電力化が期待できる。そのため、新アルゴリズム、既存アルゴリズムを問わず、小型化するための実装法が様々、提案されている。
【０００８】
例えばＨａｍａｌａｉｎｅｎ，Ａｌｈｏ、Ｈａｎｎｉｋａｉｎｅｎ、Ｈａｍａｌａｉｎｅｎらは、Ｓｕｂｓｔｉｔｕｔｉｏｎ Ｐｅｒｍｕｔａｔｉｏｎ Ｎｅｔｗｏｒｋ（ＳＰＮ）構造を持つＡＥＳ暗号アルゴリズムに対する小型実装法を提案している。この小型実装法については、非特許文献３［Panu Hamalainen,Timo Alho,Marko Hannikainen,and Timo D.Hamalainen. Design and implementation of low-area and low-power AES encryption hardware core. In DSD,pages 577-583.IEEE Computer Society,2006.9］に開示されている。
【０００９】
この開示された実装法では、１２８−ｂｉｔブロック暗号のＡＥＳを８−ｂｉｔごとの演算単位で処理することで、回路規模の小型化を達成している。Ｈａｍａｌａｉｎｅｎらの実装法はＳＰＮ構造とは異なる拡張Ｆｅｉｓｔｅｌ構造を持つＣＬＥＦＩＡ等のアルゴリズムにも応用できる。
【００１０】
ただし、既存の手法を単純に適用するとブロック長分のレジスタに加え、非線形処理部Ｆ関数の演算時の中間値を保持するために必要なレジスタが増加してしまう。例えば、ＣＬＥＦＩＡへの適用を考えたときには、ｂｌｏｃｋ長の１２８−ｂｉｔ分のレジスタに加え、３２−ｂｉｔ分のレジスタが増加する。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】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
【非特許文献３】Panu Hamalainen,Timo Alho,Marko Hannikainen,and Timo D.Hamalainen. Design and implementation of low-area and low-power aes encryption hardware core. In DSD,pages 577-583.IEEE Computer Society,2006.9
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本開示は、例えば上述の状況に鑑みてなされたものであり、例えばＣＬＥＦＩＡ等の拡張Ｆｅｉｓｔｅｌ構造を持つ暗号アルゴリズムに対して、既存の手法よりも小型化が期待できるハードウェア構成を実現する暗号処理装置、および暗号処理方法、並びにプログラムを提供することを目的とする。
【００１３】
具体的には、例えばＦ関数演算時の中間値からＦ関数への入力を復元する回路を導入することにより、ｂｌｏｃｋ長以上のレジスタを必要としない実装法を実現する。その結果、構造によってはレジスタ削減効果により回路規模の小型化が期待できる。
【課題を解決するための手段】
【００１４】
本開示の第１の側面は、
データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、
前記Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行部と、
を有する暗号処理装置にある。
【００１５】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、Ｆ関数実行部への入力データに対する非線形変換処理を実行するＳ−ｂｏｘを有し、前記中間データ格納レジスタは、前記Ｓ−ｂｏｘの出力値を中間データとして保持し、前記逆演算実行部は、前記Ｓ−ｂｏｘによる非線形変換処理の逆演算を含む演算処理により、前記Ｆ関数実行部に対する入力データを算出する。
【００１６】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、非線形変換部、および線形変換部を有し、前記非線形変換部の出力を前記中間データとして格納するレジスタを有し、前記線形変換部は、前記レジスタの格納値に対する線型変換処理を実行し、前記逆演算実行部は、前記レジスタの格納値に対する演算処理により、前記Ｆ関数実行部に対する入力データを算出する。
【００１７】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行するＳＰ型Ｆ関数である。
【００１８】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行し、さらに非線形変換部において再度、非線形変換処理をするＳＰＳ型Ｆ関数である。
【００１９】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、外部から入力するラウンド鍵との排他的論理和演算部を有する。
【００２０】
さらに、本開示の暗号処理装置の一実施態様において、前記Ｆ関数実行部は、複数の非線形演算部の繰り返し構造を有する。
【００２１】
さらに、本開示の暗号処理装置の一実施態様において、前記暗号処理部は、入力データとしての平文を暗号文に変換する暗号化処理、または、入力データとしての暗号文を平文に変換する復号処理を実行する。
【００２２】
さらに、本開示の第２の側面は、
暗号処理装置において実行する暗号処理方法であり、
暗号処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理ステップを実行し、
前記暗号処理ステップは、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行ステップと、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行ステップと、
前記Ｆ関数実行ステップにおける変換データの生成過程の中間データを中間データ格納レジスタに格納するステップと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行ステップと、
を実行する暗号処理方法にある。
【００２３】
さらに、本開示の第３の側面は、
暗号処理装置において暗号処理を実行させるプログラムであり、
暗号処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理ステップを実行させ、
前記暗号処理ステップにおいて、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行ステップと、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行ステップと、
前記Ｆ関数実行ステップにおける変換データの生成過程の中間データを中間データ格納レジスタに格納するステップと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行ステップと、
を実行させるプログラムにある。
【００２４】
なお、本開示のプログラムは、例えば、様々なプログラム・コードを実行可能な情報処理装置やコンピュータ・システムに対して例えば記憶媒体によって提供されるプログラムである。このようなプログラムを情報処理装置やコンピュータ・システム上のプログラム実行部で実行することでプログラムに応じた処理が実現される。
【００２５】
本開示のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【００２６】
本開示の一実施例によれば、暗号処理構成の小型化が実現される。
具体的には、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、暗号処理部は、複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、中間データ格納レジスタの格納データに基づいて、Ｆ関数実行部に対する入力データを算出する逆演算実行部を有する。逆演算実行部における逆演算により、Ｆ関数実行部に対する入力値を算出可能となり、このデータを保持するレジスタを削減することが可能となり、暗号処理構成の小型化が実現される。
【図面の簡単な説明】
【００２７】
【図１】ｋビットの鍵長に対応したｎビット共通鍵ブロック暗号アルゴリズムを説明する図である。
【図２】図１に示すｋビットの鍵長に対応したｎビット共通鍵ブロック暗号アルゴリズムに対応する復号アルゴリズムを説明する図である。
【図３】鍵スケジュール部とデータ暗号化部の関係について説明する図である。
【図４】データ暗号化部の構成例について説明する図である。
【図５】ＳＰＮ構造のラウンド関数の例について説明する図である。
【図６】Ｆｅｉｓｔｅｌ構造のラウンド関数の一例について説明する図である。
【図７】拡張Ｆｅｉｓｔｅｌ構造の一例について説明する図である。
【図８】拡張Ｆｅｉｓｔｅｌ構造の一例について説明する図である。
【図９】非線形変換部の構成例について説明する図である。
【図１０】線形変換処理部の構成例について説明する図である。
【図１１】共通鍵ブロック暗号について説明する図である。
【図１２】Ｆｅｉｓｔｅｌ構造について説明する図である。
【図１３】拡張Ｆｅｉｓｔｅｌ構造について説明する図である。
【図１４】ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムのラウンド関数の構造について説明する図である。
【図１５】Ｈａｍａｌａｉｎｅｎらの提案したＡＥＳ暗号を実行するデータ暗号化部のデータパスを示す図である。
【図１６】データ暗号化部の構成例を説明する図である。
【図１７】Ｈａｍａｌａｉｎｅｎらの実装法を４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に適用した場合のデータ演算部回路の概要図を示す図である。
【図１８】ラウンド関数内のＦ関数の具体例を説明する図である。
【図１９】本開示の一実施例に係る暗号処理構成を、図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｓｉｔｅｌ構造に適用した場合のデータ演算部回路の概要図である。
【図２０】ラウンド関数を説明する図である。
【図２１】ＳＰＳ型Ｆ関数について説明する図である。
【図２２】図２１に記載のＳＰＳ型Ｆ関数に、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図２３】鍵挿入が複数入ったＳＰＳ型Ｆ関数について説明する図である。
【図２４】図２３に記載のＳＰＳ型Ｆ関数に、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図２５】鍵挿入がＦ関数入力直後にあるＳＰ型Ｆ関数について説明する図である。
【図２６】図２５に記載のＳＰ型Ｆ関数に、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図２７】Ｆ関数の構成例について説明する図である。
【図２８】図２７に記載のＦ関数に、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図２９】Ｆ関数の構成例について説明する図である。
【図３０】ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の１つの構成例について説明する図である。
【図３１】図３０に記載のラウンド置換を持つ構成に対して、本開示の方式を適用した場合に考えられるデータパスの例について説明する図である。
【図３２】暗号処理装置としてのＩＣモジュール７００の構成例を示す図である。
【発明を実施するための形態】
【００２８】
以下、図面を参照しながら本開示に係る暗号処理装置、および暗号処理方法、並びにプログラムの詳細について説明する。説明は、以下の項目に従って行う。
１．共通鍵ブロック暗号の概要
２．共通鍵ブロック暗号の構造と従来型の小型化実装手法の概要について
３．レジスタ削減を実現する暗号処理構成例について
４．本開示の手法の効果のまとめ
５．その他の実施例について
６．暗号処理装置の構成例について
７．本開示の構成のまとめ
【００２９】
［１．共通鍵ブロック暗号の概要］
まず、共通鍵ブロック暗号の概要について説明する。
（１−１．共通鍵ブロック暗号）
ここでは共通鍵ブロック暗号（以下ではブロック暗号）としては以下に定義するものを指すものとする。
ブロック暗号は入力として平文Ｐと鍵Ｋを取り、暗号文Ｃを出力する。平文と暗号文のビット長をブロックサイズと呼びここではｎで著す。ｎは任意の整数値を取りうるが、通常、ブロック暗号アルゴリズムごとに、あらかじめひとつに決められている値である。ブロック長がｎのブロック暗号のことをｎビットブロック暗号と呼ぶこともある。
【００３０】
鍵のビット長をｋで表す。鍵は任意の整数値を取りうる。共通鍵ブロック暗号アルゴリズムは１つまたは複数の鍵サイズに対応することになる。例えば、あるブロック暗号アルゴリズムＡはブロックサイズｎ＝１２８であり、ｋ＝１２８またはｋ＝１９２またはｋ＝２５６の鍵サイズに対応するという構成もありうるものとする。
平文Ｐ：ｎビット
暗号文Ｃ：ｎビット
鍵Ｋ：ｋビット
【００３１】
図１にｋビットの鍵長に対応したｎビット共通鍵ブロック暗号アルゴリズムＥの図を示す。
暗号化アルゴリズムＥに対応する復号アルゴリズムＤは暗号化アルゴリズムＥの逆関数Ｅ−１と定義でき、入力として暗号文Ｃと鍵Ｋを受け取り，平文Ｐを出力する。図２に図１に示した暗号アルゴリズムＥに対応する復号アルゴリズムＤの図を示す。
【００３２】
（１−２．内部構成）
ブロック暗号は２つの部分に分けて考えることができる。ひとつは鍵Ｋを入力とし、
ある定められたステップによりビット長を拡大してできた拡大鍵Ｋ'（ビット長ｋ'）を出力する「鍵スケジュール部」と、もうひとつは平文Ｐと鍵スケジュール部から拡大された鍵Ｋ'を受け取ってデータの変換を行い暗号文Ｃを出力する「データ暗号化部」である。
２つの部分の関係は図３に示される。
【００３３】
（１−３．データ暗号化部）
以下の実施例において用いるデータ暗号化部はラウンド関数という処理単位に分割できるものとする。ラウンド関数は入力としての２つのデータを受け取り、内部で処理を施したのち、１つのデータを出力する。入力データの一方は暗号化途中のｎビットデータであり、あるラウンドにおけるラウンド関数の出力が次のラウンドの入力として供給される構成となる。もう１つの入力データは鍵スケジュールから出力された拡大鍵の一部のデータが用いられ、この鍵データのことをラウンド鍵と呼ぶものとする。またラウンド関数の総数は総ラウンド数と呼ばれ、暗号アルゴリズムごとにあらかじめ定められている値である。ここでは総ラウンド数をＲで表す。
【００３４】
データ暗号化部の入力側から見て１ラウンド目の入力データをＸ１とし、ｉ番目のラウンド関数に入力されるデータをＸｉ、ラウンド鍵をＲＫｉとすると、データ暗号化部全体は図４のように示される。
【００３５】
（１−４．ラウンド関数）
ブロック暗号アルゴリズムによってラウンド関数はさまざまな形態をとりうる。ラウンド関数はその暗号アルゴリズムが採用する構造（ｓｔｒｕｃｔｕｒｅ）によって分類できる。代表的な構造としてここではＳＰＮ構造、Ｆｅｉｓｔｅｌ構造、拡張Ｆｅｉｓｔｅｌ構造を例示する。
【００３６】
（ア）ＳＰＮ構造ラウンド関数
ｎビットの入力データすべてに対して、ラウンド鍵との排他的論理和演算、非線形変換、線形変換処理などが適用される構成。各演算の順番は特に決まっていない。図５にＳＰＮ構造のラウンド関数の例を示す。
【００３７】
（イ）Ｆｅｉｓｔｅｌ構造
ｎビットの入力データはｎ／２ビットの２つのデータに分割される。うち片方のデータとラウンド鍵を入力として持つ関数（Ｆ関数）が適用され、出力がもう片方のデータに排他的論理和される。そののちデータの左右を入れ替えたものを出力データとする。Ｆ関数の内部構成にもさまざまなタイプのものがあるが、基本的にはＳＰＮ構造同様にラウンド鍵データとの排他的論理和演算、非線形演算、線形変換の組み合わせで実現される。図６にＦｅｉｓｔｅｌ構造のラウンド関数の一例を示す。
【００３８】
（ウ）拡張Ｆｅｉｓｔｅｌ構造
拡張Ｆｅｉｓｔｅｌ構造はＦｅｉｓｔｅｌ構造ではデータ分割数が２であったものを，３以上に分割する形に拡張したものである。分割数をｄとすると、ｄによってさまざまな拡張Ｆｅｉｓｔｅｌ構造を定義することができる。Ｆ関数の入出力のサイズが相対的に小さくなるため、小型実装に向いているとされる。図７にｄ＝４でかつ、ひとつのラウンド内に２つのＦ関数が並列に適用される場合の拡張Ｆｅｉｓｔｅｌ構造の一例を示す。また，図８にｄ＝８でかつ，ひとつのラウンド内に１つのＦ関数が適用される場合の拡張Ｆｅｉｓｔｅｌ構造の一例を示す。
【００３９】
（１−５．非線形変換処理部）
非線形変換処理部は、入力されるデータのサイズが大きくなると実装上のコストが高くなる傾向がある。それを回避するために対象データを複数の単位に分割し、それぞれに対して非線形変換を施す構成がとられることが多い。例えば入力サイズをｍｓビットとして、それらをｓビットずつのｍ個のデータに分割して、それぞれに対してｓビット入出力を持つ非線形変換を行う構成である。それらのｓビット単位の非線形変換をＳ−ｂｏｘと呼ぶものとする。図９に例を示す。
【００４０】
（１−６．線形変換処理部）
線形変換処理部はその性質上、行列として定義することが可能である。行列の要素はＧＦ（２８）の体の要素やＧＦ（２）の要素など、一般的にはさまざまな表現ができる。図１０にｍｓビット入出力をもち、ＧＦ（２ｓ）の上で定義されるｍ×ｍの行列により定義される線形変換処理部の例を示す。
【００４１】
［２．共通鍵ブロック暗号の構造と従来型の小型化実装手法の概要について］
次に、共通鍵ブロック暗号の構造と従来型の小型化実装手法の概要について説明する。
本開示に係る暗号処理構成の説明上、必要な用語について説明する。
【００４２】
（２−１．共通鍵ブロック暗号について）
図１１を参照して、再度、共通鍵ブロック暗号について説明する。共通鍵ブロック暗号のアルゴリズムは、入力データの変換を繰り返し実行するラウンド関数を有するデータ暗号化部と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部とによって構成される。鍵スケジュール部は秘密鍵を入力し、各ラウンド関数に入力するラウンド鍵を生成する。
例えば、ｒ段のラウンド関数を行なう構成としたブロック暗号においては、１からｒ段までのラウンド関数にそれぞれＲＫ１，ＲＫ２，...，Ｒｒのラウンド鍵が入力される。また、初期鍵としてＩＫが，最終鍵としてＦＫが排他的論理和される。
【００４３】
（２−２．Ｆｅｉｓｔｅｌ構造）
図１２を参照してＦｅｉｓｔｅｌ構造について説明する。共通鍵ブロック暗号におけるデータ暗号化部の代表的な構造としてＦｅｉｓｔｅｌ構造がある。ブロック長をｎ−ｂｉｔとした際の具体的なＦｅｉｓｔｅｌ構造の構成例を図１２に示す。
【００４４】
図１２を見ると，ｎ−ｂｉｔのデータをｎ／２−ｂｉｔずつの２−ｌｉｎｅに分割し、そのｎ／２−ｂｉｔの片方をラウンド内のＦ関数に入力し、その出力をもう片方のｎ／２−ｂｉｔと排他的論理和していく構成となっている。Ｆ関数の構成には様々なタイプのものが考えられる。一例を挙げると、図１２に示すＦ関数のように、ラウンド鍵との排他的論理和演算、Ｓ−ｂｏｘと呼ばれる非線形演算、その後、行列演算により線形変換の処理を行なう構成が知られている。
また、図１２に示した構造は，Ｆｅｉｓｔｅｌ構造の構成例の１つであり，ＩＫ，ＦＫを排他的論理和する位置を変更することで、別の構成例が可能である。
【００４５】
（２−３．拡張Ｆｅｉｓｔｅｌ構造）
図１３を参照して拡張Ｆｅｉｓｔｅｌ構造について説明する。前節のＦｅｉｓｔｅｌ構造の説明では，ｎ／２−ｂｉｔずつの２−ｌｉｎｅに分割し、処理を行なう構成であったが、３−ｌｉｎｅ以上に分割する形にも拡張が可能である。例えば、ｎ／４−ｂｉｔずつの４−ｌｉｎｅに分割し、処理を行なう４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造と呼ばれるものもある。
【００４６】
具体的な４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造の構成例を図１３に示す。図１３を見ると，ｎ−ｂｉｔのデータをｎ／４−ｂｉｔずつの４−ｌｉｎｅに分割し、そのうちの２−ｌｉｎｅをそれぞれＦ関数に入力し、その出力をその他の２−ｌｉｎｅと排他的論理和していく構成となっている。２−ｌｉｎｅから４−ｌｉｎｅと変更することにより、ラウンド鍵ＲＫｉ，初期鍵ＩＫ，最終鍵ＦＫも、ｎ／２−ｂｉｔから、ｎ／４−ｂｉｔのＲＫｉ［０］，ＲＫｉ［１］，ＩＫ［０］，ＩＫ［１］，ＦＫ［０］，ＦＫ［１］に分割される。上記は、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造についての説明だが、２−ｌｉｎｅ以上のＦｅｉｓｔｅｌ構造については全て拡張Ｆｅｉｓｔｅｌ構造と呼ぶ。本開示の実施例の説明においては簡単のため、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造についてのみ言及する．
【００４７】
（２−４．従来型の小型化実装手法の概要と課題）
（２−４−１．ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおける小型実装手法について）
先に説明したように、ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおける小型実装手法についてＨａｍａｌａｉｎｅｎ，Ａｌｈｏ，Ｈａｎｎｉｋａｉｎｅｎ，ＨａｍａｌａｉｎｅｎらはＡＥＳの小型実装法を提案している。非特許文献３［Panu Hamalainen,Timo Alho,Marko Hannikainen,and Timo D.Hamalainen. Design and implementation of low-area and low-power AES encryption hardware core. In DSD,pages 577-583.IEEE Computer Society,2006.9］
【００４８】
まず、図１４を参照してＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムのラウンド関数の構造について説明する。なお、ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおいてもＦｅｉｓｔｅｌ構造と同様、ラウンド関数を複数回繰り返し実行する構成を持つ。図１４は，ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおいて利用されるラウンド関数実行部の構成例を示す図である。ＡＥＳでは，図１４に示すラウンド関数を、複数回繰り返して平文から暗号文、または、暗号文から平文の生成を行なう。
【００４９】
図１４に示すラウンド関数実行部は以下の構成要素によって構成される。非線形変換処理を実行する８−ｂｉｔ入出力の１６個のＳ−ｂｏｘからなる非線形変換部４０１，非線形変換部を構成するＳ−ｂｏｘからの８−ｂｉｔ出力の入れ替え処理としてのＳｈｉｆｔＲｏｗ実行部４０２、ＳｈｉｆｔＲｏｗ実行部の出力を３２−ｂｉｔ単位で入力して行列を適用した線形変換処理を実行する４つの行列演算部からなる線形変換部４０３、線形変換部４０３を構成する４つの行列演算部各々からの３２−ｂｉｔ出力に対して３２−ｂｉｔのラウンド鍵との排他的論理和演算を実行する４つの演算部からなる排他的論理和演算部４０４を有する。
【００５０】
図１４に示す例は、入出力１２８−ｂｉｔのラウンド関数実行部であり、１６個のＳ−ｂｏｘ各々に８−ｂｉｔ、計８×１６＝１２８−ｂｉｔを入力し、４つの排他的論理和部の各々３２−ｂｉｔ、計３２×４＝１２８−ｂｉｔ出力を行なう構成である。
【００５１】
前述の非線形変換部４０１、ＳｈｉｆｔＲｏｗ実行部４０２、線形変換部４０３、排他的論理和演算部４０４、これらを適用した一連の処理を１回のラウンド関数の実行処理として実行し、このラウンド関数を複数回、繰り返して１２８−ｂｉｔの入力データ（例えば平文）から、１２８−ｂｉｔの出力（例えば暗号文）を生成して出力する。
【００５２】
ＡＥＳの実装において、１つのラウンド関数の処理（１ｒｏｕｎｄ）、すなわち、非線形変換部４０１、ＳｈｉｆｔＲｏｗ実行部４０２、線形変換部４０３、排他的論理和演算部４０４、これらを適用した一連の処理を、１ｃｙｃｌｅで実行しようとすると、少なくとも、図１４に示すように、１６個のＳ−ｂｏｘの回路と、４個の行列演算回路がデータ暗号化部の構成として必要となる。
【００５３】
Ｈａｍａｌａｉｎｅｎらは，１ｒｏｕｎｄに１６ｃｙｃｌｅかけることで、データ暗号化部の小型化を実現した。この小型化構成では、Ｓ−ｂｏｘの回路は１個しか用いず、さらに、４ｃｙｃｌｅかけて１つの行列演算を実行するように実装することで、行列演算回路の小型化も実現している。
【００５４】
図１５にＨａｍａｌａｉｎｅｎらの提案したＡＥＳ暗号を実行するデータ暗号化部のデータパスを示す。図１５に示す構成は、図１４に示すＡＥＳ暗号のラウンド関数を実行するハードウェア構成に相当する。
【００５５】
図１５に示す構成において、演算中のデータは８−ｂｉｔ単位に分割され、各８−ｂｉｔデータをレジスタＲ０〜Ｒ１８に格納している。図１５には、１９個のレジスタが示されている。１９個のレジスタ（Ｒ０〜Ｒ１８）の各々は８−ｂｉｔデータを保持する８−ｂｉｔレジスタである。図１４を参照して説明した通り、図１４に示す構成は、入出力１２８−ｂｉｔのラウンド関数実行部であり、図１５は，入出力１２８−ｂｉｔのラウンド関数を８−ｂｉｔ単位データのシリアル処理として実行するハードウェア構成に対応する。
【００５６】
図１５の構成において、入出力データを全て格納するために必要となる８−ｂｉｔレジスタの数は、１２８／８＝１６であり、１６個のレジスタがあればよい。図１５には、１９個のレジスタがあり、３つのレジスタが余分であるが、これら２４−ｂｉｔ分の３つのレジスタは、行列を適用した線形変換処理を実行するための行列演算処理のために利用される。
【００５７】
また、図１４を参照して説明したように、ＡＥＳでは、非線形変換を実行するＳ−ｂｏｘと線形変換を実行する行列演算の間にＳｈｉｆｔＲｏｗ実行部によるデータ置換が実行される。Ｈａｍａｌａｉｎｅｎらの実装手法では、図１５中のいくつかのレジスタの前にマルチプレクサ（Ｍｕｌｔｉｐｌｅｘｅｒ）ｍ０１〜ｍ０８を導入することにより、ＳｈｉｆｔＲｏｗ実行部で行なわれる置換を実現している。
【００５８】
図１５に示すように、非線形変換部としてのＳ−ｂｏｘ，Ｓ５０１は１個しかない。このＳ−ｂｏｘ，Ｓ５０１に対して８−ｂｉｔデータを順次入力し、１６ｃｙｃｌｅで図１４に示す１６個のＳ−ｂｏｘによる非線形変換処理を実行する。Ｓ−ｂｏｘ，Ｓ５０１の出力は、行列演算回路Ｍ５０２に入力され、行列演算回路Ｍ５０２において、行列を適用した線形変換処理が実行される。
【００５９】
なお，図１４の構成では、Ｓ−ｂｏｘによる処理データをＳｈｉｆｔＲｏｗ実行部で置換した後、行列演算を行なう構成となっているが、図１５に示す例では、Ｓ−ｂｏｘ，Ｓ５０１の出力を行列演算回路Ｍ５０２に直接入力する構成としている。図１５の構成では、ＳｈｉｆｔＲｏｗ実行部での置換処理に相当する処理は図１５に示すレジスタＲ０〜Ｒ１８とマルチプレクサｍ０１〜ｍ０８の動作によって実行する。
【００６０】
図１５に示す行列演算回路Ｍ５０２では，図１４に示す線形変換部４０３の４つの行列演算回路の処理が順次実行される。図１４に示す線形変換部４０３の４つの行列演算回路の１つの行列演算回路で実行する行列を適用した線形変換処理を４ｃｙｃｌｅで実行する。図１４に示す排他的論理和演算部４０４の排他的論理和演算処理は，図１５の排他的論理和演算部Ｘ５０３，Ｘ５０４において実行される。これら排他的論理和演算部Ｘ５０３，Ｘ５０４において，処理データと鍵生成部Ｋ５０５の出力するラウンド鍵との排他的論理和処理を実行する。
【００６１】
なお，本開示の構成に本質的に関連のある箇所のみを説明するため，ＳｈｉｆｔＲｏｗ等の置換を行なう回路や、鍵スケジュール部については図１６のように省略したデータパスで説明する。図１６中のレジスタ群と記述されている部分は、９６−ｂｉｔ分のデータを保持し、ＳｈｉｆｔＲｏｗも考慮されたレジスタの集合を表す。ＡＥＳの実装において，１ｒｏｕｎｄを１ｃｙｃｌｅで演算する場合、利用するデータ暗号化部用のレジスタはｂｌｏｃｋ長である１２８−ｂｉｔ分のみで済む。
【００６２】
それに対し、Ｈａｍａｌａｉｎｅｎらの実装法では、１５２−ｂｉｔと２４−ｂｉｔ分増えている。これは、行列への入力を８−ｂｉｔずつに分割した場合、行列を計算し終わるまでの途中演算結果の３２−ｂｉｔ分を保持する必要性が出てくるためである。そのため、単純に考えると３２−ｂｉｔ分のレジスタが追加されることになる。一方、行列へ入力する値は次のラウンドでは不要となる。このことを考慮すると、行列へ入力する３２−ｂｉｔのうち、はじめに入力する８−ｂｉｔ分のレジスタは行列演算部のレジスタと共有できるので、レジスタの増加分は、
３２−８＝２４−ｂｉｔ
分に抑えられる。
【００６３】
（２−４−２．ＳＰＮ構造の小型実装構成の拡張Ｆｅｉｓｔｅｌ 構造への適用と問題点について）
上述したように，Ｈａｍａｌａｉｎｅｎらは，ＳＰＮ構造の小型化を実現している。しかし、この小型化構成はＳＰＮ構造に対応した特有の構成であり、この小型実装構成を拡張Ｆｅｉｓｔｅｌ構造へ適用しても十分な小型化の効果は得られない。
【００６４】
以下、この問題点について説明する。なお、以下の説明では、拡張Ｆｅｉｓｔｅｌ構造は、Ｆｅｉｓｔｅｌ構造を含む概念であるものとして説明する。Ｈａｍａｌａｉｎｅｎらの実装法を拡張Ｆｅｉｓｔｅｌ構造を持つＣＬＥＦＩＡ等のアルゴリズムを実行する構成に適用すると、行列演算のために、行列の出力ビット長分のデータを格納するレジスタが必要になる。
【００６５】
これは、拡張Ｆｅｉｓｔｅｌ構造がＳＰＮ構造とは異なり、例えばラウンド関数内のＦ関数に入力した値を、次のラウンドでも利用する必要があるという処理シーケンスの根本的な違いに起因するものである。
【００６６】
図１７は、Ｈａｍａｌａｉｎｅｎらの実装法を４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に適用した場合のデータ演算部回路の概要図を示す図である。図１７では、先に図１６を参照して説明したＡＥＳのデータパスと同様、拡張Ｆｅｉｓｔｅｌ構造のラウンド関数終了時の置換動作や鍵スケジュール部は省略してある。なお、ラウンド演算における処理データサイズとしてのブロックサイズはｎ−ｂｉｔとする。
【００６７】
先に図１３を参照して説明したように，４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造では、４つのライン各々にｎ／４−ｂｉｔずつ入力され、順次転送される。図１７中のレジスタ群Ｒ７０３は、図１６に示すレジスタ群Ｒ６０１に対応する。ただし、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に対応する図１７中のレジスタ群Ｒ７０３は，（３／４）ｎ−ｂｉｔ分のデータを保持するレジスタとラウンド終了時の置換動作と同様の処理を実現するマルチプレクサ等の組み合わせとして構成される。
【００６８】
なお、図１７に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムのデータパス（演算実行回路）を適用して実行する演算は、図１３に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造を適用した演算処理に対応する。この図１７に示すデータパスを利用して図１３に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造内のＦ関数を含むラウンド関数を実行することになる。
【００６９】
ラウンド関数内のＦ関数の具体例を図１８に示す。図１８に示すＦ関数は、以下の構成要素を持つ。
＊非線形処理を実行するＳ−ｂｏｘからなる非線形変換部Ｓ８０１、
＊非線形変換部Ｓ８０１からの出力に対して、行列演算により線形変換の処理を行なうＭ８０２、
＊線形変換部Ｍ８０２からの出力に対して、ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部Ｘ８０３、
上記の構成要素を持つ。図１８に示すＦ関数はＳＰ型Ｆ関数と呼ばれる。
【００７０】
ただし，４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造におけるＦ関数に対する入出力は，ｎ／４−ｂｉｔになる。なお、図１８に示されている線形変換部Ｍ８０１は、ＡＥＳ暗号アルゴリズムで採用されている行列と同様に下記の（式１）に示される巡回行列を想定している。
【００７１】
【数１】
【００７２】
なお、式１に示す（ｘ０、ｘ１、ｘ２、ｘ３）は、行列演算回路である線形変換部Ｍ８０１に対する入力（Ｓ−ｂｏｘからの出力）、
（ｙ０、ｙ１、ｙ２、ｙ３）は、行列演算回路である線形変換部Ｍ８０１の出力（線形変換結果）、
４×４の行列は、行列演算回路である線形変換部Ｍ８０１において適用する行列（線形変換行列）に対応する。
なお、４×４の線形変換行列の要素は１６進数値として示している。
本例では、（ｘ０、ｘ１、ｘ２、ｘ３）の各々は、Ｓ−ｂｏｘからの１サイクルあたりの出力であり８ビットデータである。出力（ｙ０、ｙ１、ｙ２、ｙ３）の各々も８ビットデータである。
【００７３】
先に図１４〜図１６を参照して説明したＡＥＳ暗号アルゴリズムの構成と比較するため、処理単位としてのブロック構成ビットｎは、ｎ＝１２８−ｂｉｔとする。
図１７に示す回路も、図１６に示す回路と同様、Ｓ−ｂｏｘは１つのみである。図１７に示すＳ−ｂｏｘ，Ｓ７０１である。このＳ−ｂｏｘ，Ｓ７０１は、図１８に示すＦ関数内に設定される１つのＳ−ｂｏｘの処理を１ｃｙｃｌｅで実行する。
ｃｙｃｌｅごとに、順次、図１８に示す各Ｓ−ｂｏｘの処理を行なうことになる。
【００７４】
図１８に示すように、Ｆ関数の１つのＳ−ｂｏｘには、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造の１つのラインを伝送するｎ／４−ｂｉｔの１／４、すなわち、ｎ／１６−ｂｉｔが入力され非線形変換処理が実行される。
【００７５】
図１７に示すＳ−ｂｏｘＳ７０１には、ｎ／１６−ｂｉｔずつがｃｙｃｌｅごとに入力され、非線形変換処理が実行される。Ｓ−ｂｏｘ，Ｓ７０１において非線形変換のなされたデータは、ｎ／１６−ｂｉｔごとに１ｃｙｃｌｅ単位で次の線形変換回路Ｍ７０２に入力される。線形変換回路Ｍ７０２では、所定の行列を適用した線形変換処理が実行されることになる。
【００７６】
図１７に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムのデータパス構成中、レジスタ群Ｒ７０３を除く演算実行回路と、先に図１６を参照して説明したレジスタ群Ｒ６０１を除く、ＳＰＮ構造を利用したＡＥＳ暗号処理を実行する演算回路構成とを比較する。
【００７７】
図１６に示す演算回路では、８−ｂｉｔレジスタがＲ０〜Ｒ３，Ｒ１６〜Ｒ１８の７個であるのに対して、図１７に示す演算回路では、８−ｂｉｔレジスタがＲ０〜Ｒ３，Ｒ１６〜Ｒ１９の８個である。すなわち、８−ｂｉｔレジスタの数が１つ増加している。
【００７８】
このように、Ｈａｍａｌａｉｎｅｎらの提案構成を拡張Ｆｅｉｓｔｅｌ構造に適用した場合、図１７に示す演算回路のように、ブロック長分のレジスタに加え、１−ｌｉｎｅ分のレジスタが必要となってくる。レジスタの増加は回路規模に大きく影響するため、ブロック長分のみのレジスタで構成できるならば、そのほうが望ましい。
【００７９】
従来手法の課題点として以下の課題があげられる。
レジスタの回路規模は他のセルに比べて比較的大きなものとなり、レジスタ数の増加は回路規模に大きく影響する。そのため、小型化を実現するための一つの方向性として、レジスタの増加を抑えた実装法が考えられる。従来手法の実装法では、ｂｌｏｃｋ長分よりも大きなレジスタが必要になってしまうことが課題と考えられる。
【００８０】
［３．レジスタ削減を実現する暗号処理構成例について］
Ｈａｍａｌａｉｎｅｎらの実装法を、拡張Ｆｅｉｓｔｅｌ構造を持つアルゴリズムに適用した場合には、前節で述べたように必要なレジスタが増加してしまう。これは、Ｆ関数への入力は次のラウンドでも利用するため、Ｆ関数への入力を保持したまま、Ｆ関数の出力を演算しているためである。この考えのもとで実装すると、Ｆ関数への入力を保持するレジスタと、Ｆ関数演算時の中間値を保持するためのレジスタの両方が必要となる。
【００８１】
先の図１７、図１８を用いて説明した４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムでは、Ｆ関数内の線形変換部Ｍ８０２で表される行列演算時の中間値を保持する必要があったため、ブロック長分のレジスタに加え、１−ｌｉｎｅ分の３２−ｂｉｔ分のレジスタが必要となった。
【００８２】
以下に説明する実施例では、Ｆ関数への入力は一度破棄し、その入力が格納されていたレジスタをＦ関数演算時の中間値を保持するためのレジスタとして利用する。
Ｆ関数の出力値と、Ｆ関数へ入力したラインとは別のラインとの排他的論理和を実行後、Ｆ関数演算時の中間値からＦ関数への入力を復元するように考える。
【００８３】
このようにすることで、Ｆ関数への入力値とＦ関数演算時の中間値を同時に保持する必要がなくなり、レジスタ数を削減することができる。
【００８４】
以下、具体例について説明する。前述した構成との対比を容易とするため、図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｓｉｔｅｌ構造を例に説明する。なお，図１８に示されている線形変換部Ｍ８０１は，ＡＥＳ暗号アルゴリズムで採用されている行列と同様に下記の（式２）で記される巡回行列を想定している。
【００８５】
【数２】
【００８６】
図１９は、本開示の一実施例に係る暗号処理構成を、図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｓｉｔｅｌ構造に適用した場合のデータ演算部回路の概要図である。
【００８７】
先に説明した項目（２−４−２．ＳＰＮ構造の小型実装構成の拡張Ｆｅｉｓｔｅｌ 構造への適用と問題点について）で紹介したように、Ｈａｍａｌａｉｎｅｎらの実装法を図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に適用した場合、図１８のＦ関数内の線形変換部Ｍ８０２で表される行列演算時の中間値を保持するレジスタが必要となった。
【００８８】
それに対して、本開示の一実施例に係る暗号処理構成を用いて実現された図１９では、中間値として、非線形演算部Ｓ８０１後の線形演算部Ｍ８０２に入力される値を保持するようにしている。この手法で保持すべき中間値を図１８に保持する中間値Ｉ８０４として表す。図１９では、上記の中間値を図１９に示すＲ０〜Ｒ３で表されるレジスタ内に保持している。
【００８９】
また、Ｈａｍａｌａｉｎｅｎらの実装法を図１８で表されるＦ関数を持つ４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に適用した場合、図１８のＦ関数内の線形変換部Ｍ８０２で表される行列演算時の中間値を保持するレジスタとは別に、次のラウンドを演算するために必要となるＦ関数への入力値を保持するレジスタを必要としていた。それに対して、図１９では、次のラウンドを演算するために必要となるＦ関数への入力値は保持せずに、代わりに上記で述べた図１８のＦ関数内の非線形演算部Ｓ８０１後の線形演算部Ｍ８０２に入力される値である保持する中間値Ｉ８０４を保持している。
【００９０】
先に説明した項目（２−４−２．ＳＰＮ構造の小型実装構成の拡張Ｆｅｉｓｔｅｌ 構造への適用と問題点について）で紹介したＨａｍａｌａｉｎｅｎらの実装法では，１６０−ｂｉｔ分のレジスタを利用していたのに対し，図１９に示す構成においては、８−ｂｉｔレジスタを、Ｒ０〜Ｒ１５の１６個、利用しており、合計で１２８−ｂｉｔ分のレジスタのみで回路を実現できる。
【００９１】
この図１９に示すデータパスを利用して図１３，図１８で表されるラウンド関数を実行することになる。
図１３を参照すると、１ラウンドに演算する必要のあるＦ関数は２つあることが分かる。図１９では，１つのＦ関数の出力を４ｃｙｃｌｅかけて実行し、その後の４ｃｙｃｌｅをかけて図１８の保持する中間値Ｉ，８０４からＦ関数の入力を復元する。
【００９２】
前述したように、１ｒｏｕｎｄにＦ関数は２つ実行する必要があるため、合計１６ｃｙｃｌｅを要することで１ｒｏｕｎｄ分の演算を実行する。また、平文入力時には、１６ｃｙｃｌｅかけて上位８−ｂｉｔから８−ｂｉｔずつ入力し、暗号文出力時にも１６ｃｙｃｌｅかけて出力ポートから上位８−ｂｉｔから８−ｂｉｔずつ順次出力するように考える。
【００９３】
以下、以下に示す表１を参照しながら平文入力時の１６ｃｙｃｌｅ分と，１ｒｏｕｎｄの演算に必要な１６ｃｙｃｌｅ分と，暗号文出力時の１６ｃｙｃｌｅ分のデータの流れを説明する。
【００９４】
【表１】
【００９５】
まず、平文入力時の１６ｃｙｃｌｅ分の動きを説明する。
ｉ∈｛０，１，...，１５｝
に対して、
ｐｉを８−ｂｉｔの要素とする。
このとき，（ｐ０，ｐ１，...，ｐ１５）で表される１２８−ｂｉｔを平文として考える。
【００９６】
平文入力時の１ｃｙｃｌｅ目では，ｐ０を図１９に示す平文入力ポートからマルチプレクサｍ０１を利用しＲ１５に格納する．その後１１ｃｙｃｌｅかけて，ｐ０をマルチプレクサｍ０２を利用し，Ｒ１４，Ｒ１３，...，Ｒ４の順に格納していく。
【００９７】
上述したように、平文入力時の１２ｃｙｃｌｅ後にはｐ０はＲ４に格納されているとする。１３ｃｙｃｌｅ目には、Ｒ４に格納されていたｐ０を非線形演算部Ｓ９０１に入力し、その出力をマルチプレクサｍ０３を利用しＲ３に格納する。
【００９８】
ｐ０を非線形演算部Ｓ９０１に入力したときの出力をＳ（ｐ０）とする。その後、３ｃｙｃｌｅかけて，Ｓ（ｐ０）をＲ２，Ｒ１，Ｒ０の順に格納していく。
【００９９】
ｐ０以外の値であるｐｉ，ｉ∈｛１，２，...，１５｝に関しては、ｐ０が格納されていたレジスタにｉｃｙｃｌｅだけ遅れて格納されるようにする。ただし、Ｒ４に格納されていた値は次のサイクルで非線形演算部Ｓ９０１に入力され、その出力であるＳ（ｐｉ）がＲ３に入力されるとする。
【０１００】
最終的に、平文入力時の１６ｃｙｃｌｅ後には，Ｒ０〜Ｒ３には，（Ｓ（ｐ０），Ｓ（ｐ１），Ｓ（ｐ２），Ｓ（ｐ３））が格納され、Ｒ４〜Ｒ１５には、（ｐ４，ｐ５，...，ｐ１５）が格納されるようにマルチプレクサｍ０１，ｍ０２，ｍ０３を利用する。
【０１０１】
なお、Ｒ０〜Ｒ３に入力された（Ｓ（ｐ０），Ｓ（ｐ１），Ｓ（ｐ２），Ｓ（ｐ３））は、１ｒｏｕｎｄ目の図１８に記載のＦ関数の保持する中間値Ｉ８０４の値と一致する。
【０１０２】
次に，１ｒｏｕｎｄの演算に必要な１６ｃｙｃｌｅ分のデータの流れを説明する。
図２０は，図１３における、
ｉ∈｛１，...，ｒ｝ラウンド目のラウンド関数を表したものである。
【０１０３】
今、図２０においてｉ∈｛１，...，ｒ｝ラウンド目のラウンド関数への入力値を（ｘ０，ｘ１，...，ｘ１５）とし，ｉラウンド目のラウンド関数の出力値を（ｙ０，ｙ１，...，ｙ１５）とする。ただし、ｉ＝１のときは，（ｘ０，ｘ１，...，ｘ１５）は平文を表し、ｉ＝ｒのときは、（ｙ０，ｙ１，...，ｙ１５）は暗号文を表すこととする。
【０１０４】
図１９では、ラウンド開始時の初期状態として、Ｒ０〜Ｒ３には、（Ｓ（ｘ０），Ｓ（ｘ１），Ｓ（ｘ２），Ｓ（ｘ３））が格納され、Ｒ４〜Ｒ１５には、（ｘ４，ｘ５，...，ｘ１５）がそれぞれ格納されていると考える。
【０１０５】
なお、ｉ＝１の場合は、ラウンド開始時の初期状態として、前述の通り、
Ｒ０〜Ｒ３には、（Ｓ（ｐ０），Ｓ（ｐ１），Ｓ（ｐ２），Ｓ（ｐ３））が格納され、
Ｒ４〜Ｒ１５には，（ｐ４，ｐ５，...，ｐ１５）がそれぞれ格納されている状態を表す。
【０１０６】
表１では、図１９に記した発明手法におけるラウンド関数実行時のレジスタの保持内容を表している。１ｒｏｕｎｄを１６ｃｙｃｌｅで実行するため、各ｃｙｃｌｅ後のＲ０，Ｒ１，...，Ｒ１５のそれぞれのレジスタの保持内容を表している。また、図１９記載のように（ｘ０，ｘ１，ｘ２，ｘ３），（ｘ８，ｘ９，ｘ１０，ｘ１１）をＦ関数の入力とした場合の出力を（ｆ０，ｆ１，ｆ２，ｆ３），（ｆ８，ｆ９，ｆ１０，ｆ１１）と表すことにする。
【０１０７】
ラウンド関数実行時の１〜４ｃｙｃｌｅ目では、図１８記載の線形演算部Ｍ８０１を図１９記載の行列演算部Ｍ９０２を用いて実行する。行列演算部Ｍ９０２では，Ｒ０，Ｒ１に格納されている値に対して、有限体ＧＦ（２８）上での０ｘ０２，０ｘ０３との乗算を図１９記載のｍｕｌ０２，ｍｕｌ０３で実行する。その乗算後の値を排他的論理和し、さらに、Ｒ２，Ｒ３に格納されている値とも排他的論理和したものを出力している。
【０１０８】
このようにすることで、１ｃｙｃｌｅ目には，図１８記載の線形演算部Ｍ８０１の出力値の上位８−ｂｉｔが計算できる。
また、マルチプレクサｍ０３を利用することにより、Ｒ０に格納されている値を次のｃｙｃｌｅでＲ３に格納することで、２，３，４ｃｙｃｌｅ目には同様に図１８記載の線形演算部Ｍ８０１の出力値の９〜１６，１７〜２４，２５〜３２−ｂｉｔ目がそれぞれ計算できる。
【０１０９】
これは、想定している行列が、行ごとの要素を１行ごとに右ローテーションしている巡回行列であることを利用している。（Ｒ０，Ｒ１，Ｒ２，Ｒ３）の保持内容をｃｙｃｌｅごとに８−ｂｉｔ左ローテーションを施すことで、行列１行分の演算を実施する図１９記載の行列演算部Ｍ９０２を用いて、ｃｙｃｌｅごとに各行の演算を実施するようにしている。
【０１１０】
さらに、ラウンド関数実行時の１〜４ｃｙｃｌｅ目では、上述した線形演算部からの出力に対し、ラウンド鍵との排他的論理和演算が排他的論理和演算部Ｘ９０３で上位８−ｂｉｔから８−ｂｉｔずつ順次実行される。
【０１１１】
また、図２０記載のＦ関数Ｆ１９２の出力との排他的論理和演算Ｘ１９１は、図１９においてラウンド鍵との排他的論理和演算実行部Ｘ９０３の出力値とレジスタＲ４に格納されている値との排他的論理和演算部Ｘ９０４を利用することで実現される。
【０１１２】
Ｒ４には、１〜４ｃｙｃｌｅ目において、ｘ４，ｘ５，ｘ６，ｘ７が順次格納されるため、排他的論理和演算部Ｘ９０４の出力をマルチプレクサｍ０１を利用しレジスタＲ１５に格納することで、４ｃｙｃｌｅ後に（ｘ０，ｘ１，ｘ２，ｘ３）をＦ関数に入力したときの出力３２−ｂｉｔと３２−ｂｉｔの（ｘ４，ｘ５，ｘ６，ｘ７）を排他的論理和した値がＲ１２，Ｒ１３，Ｒ１４，Ｒ１５に８−ｂｉｔずつ格納された状態となる。
【０１１３】
表１に記載の通り、ラウンド関数開始後の４ｃｙｃｌｅ後には，Ｒ１２，Ｒ１３，Ｒ１４，Ｒ１５に（ｘ０，ｘ１，ｘ２，ｘ３）をＦ関数に入力したときの出力３２−ｂｉｔと３２−ｂｉｔの（ｘ４，ｘ５，ｘ６，ｘ７）を排他的論理和した値が格納されている。
【０１１４】
これらの値は、ラウンド関数の出力値の上位３２−ｂｉｔであるｙ０，ｙ１，ｙ２，ｙ３となる。
また、図１９記載のマルチプレクサｍ０３を利用し、Ｒ０が保持している値を次のｃｙｃｌｅではＲ３に格納するようにしていたので、表１を参照すると、ラウンド開始後の４ｃｙｃｌｅ後には、Ｒ０，Ｒ１，Ｒ２，Ｒ３の保持内容は、ラウンド開始時の値と変化していないことが分かる。
【０１１５】
また、その他のｘ８，ｘ９，...，ｘ１５は、図１９記載のマルチプレクサｍ０２を利用し、ラウンド開始後の４ｃｙｃｌｅ後には、それぞれＲ４，Ｒ５，...，Ｒ１１に格納される。
【０１１６】
次にラウンド関数実行時の５〜８ｃｙｃｌｅ目についてデータの流れを説明する。上述したように、（ｘ０，ｘ１，ｘ２，ｘ３）をＦ関数に入力したときの出力を用いた演算は実行可能ということが分かった。
しかし、ラウンド関数開始後の４ｃｙｃｌｅ後には、ラウンド関数出力の値として必要な（ｘ０，ｘ１，ｘ２，ｘ３）の値は保持しておらず、代わりにＦ関数演算時の中間値である（Ｓ（ｘ０），Ｓ（ｘ１），Ｓ（ｘ２），Ｓ（ｘ３））のみをＲ０，Ｒ１，Ｒ２，Ｒ３に保持している。
【０１１７】
５〜８ｃｙｃｌｅ目では，本発明の１つのポイントとなるＦ関数演算時の中間値からＦ関数への入力を復元する回路を用いて（ｘ０，ｘ１，ｘ２，ｘ３）を復元する。ラウンド関数開始後の４ｃｙｃｌｅ後には、Ｆ関数演算時の中間値として、Ｒ０，Ｒ１，Ｒ２，Ｒ３に（Ｓ（ｘ０），Ｓ（ｘ１），Ｓ（ｘ２），Ｓ（ｘ３））の値を保持している。
【０１１８】
図１９記載の非線形演算部Ｓ−１関数Ｓ９０５は、非線形演算部Ｓ−ｂｏｘＳ９０１の逆関数を表している。ラウンド関数開始後の５〜８ｃｙｃｌｅ目には、Ｒ０の保持値を非線形演算部Ｓ−１関数に入力し、その出力をマルチプレクサｍ０１を利用し、Ｒ１５に格納する。
【０１１９】
このようにすることで、ラウンド関数開始後の８ｃｙｃｌｅ後には、Ｒ１２，Ｒ１３，Ｒ１４，Ｒ１５にｘ０，ｘ１，ｘ２，ｘ３がそれぞれ格納された状態になる。非線形演算Ｓ−ｂｏｘの逆関数Ｓ−１関数は、拡張Ｆｅｉｓｔｅｌ構造とは異なるＳＰＮ構造を利用した暗号アルゴリズムでは、復号関数を構成する際に導入されているが、通常、拡張Ｆｅｉｓｔｅｌ構造では暗号化においても復号においても用いる必要がなく、Ｆ関数演算時の中間値からＦ関数への入力を復元するという目的のために導入された回路となる。
【０１２０】
さらに、ラウンド関数実行時の５〜８ｃｙｃｌｅ目では，図２０記載のＦ関数演算部Ｆ１９３の出力を計算するために、Ｒ４，Ｒ５，Ｒ６，Ｒ７に格納されている（ｘ８，ｘ９，ｘ１０，ｘ１１）をそれぞれ図１９記載の非線形演算部Ｓ９０１に入力し、その出力をマルチプレクサｍ０３を利用し，Ｒ０，Ｒ１，Ｒ２，Ｒ３に格納する。
【０１２１】
表１に記載の通り、ラウンド関数開始後の８ｃｙｃｌｅ後には、Ｒ１２，Ｒ１３，Ｒ１４，Ｒ１５に（ｘ０，ｘ１，ｘ２，ｘ３）の値が格納されている。これらの値は、ラウンド関数の出力値の下位３２−ｂｉｔであるｙ１２，ｙ１３，ｙ１４，ｙ１５となる。
【０１２２】
また、ラウンド関数開始後の４ｃｙｃｌｅ後にＲ４，Ｒ５，Ｒ６，Ｒ７に格納されていたｘ８，ｘ９，ｘ１０，ｘ１１は、ラウンド関数開始後の８ｃｙｃｌｅ後には、非線形演算部Ｓ９０１への入力後、マルチプレクサｍ０３を利用し、Ｒ０，Ｒ１，Ｒ２，Ｒ３に格納される。
【０１２３】
また、その他のｘ１２，ｘ１３，ｘ１４，ｘ１５，ｙ０，ｙ１，ｙ２，ｙ３は、図１９記載のマルチプレクサｍ０２を利用し、ラウンド開始後の８ｃｙｃｌｅ後には、それぞれＲ４，Ｒ５，...，Ｒ１１に格納される。
【０１２４】
次にラウンド関数実行時の９〜１２ｃｙｃｌｅ目のデータの流れを説明する。まず、図２０記載のＦ関数演算部Ｆ１９３中の図１８記載の線形演算部Ｍ８０１を図１９記載の行列演算部Ｍ９０２を用いて実行する。
【０１２５】
行列演算部Ｍ９０２では、Ｒ０，Ｒ１に格納されている値に対して，有限体ＧＦ（２８）上での０ｘ０２，０ｘ０３との乗算を図１９記載のｍｕｌ０２，ｍｕｌ０３で実行する。その乗算後の値を排他的論理和し、さらに，Ｒ２，Ｒ３に格納されている値とも排他的論理和したものを出力している。
【０１２６】
このようにすることで、ラウンド関数開始後の９ｃｙｃｌｅ目には、図１８記載の線形演算部Ｍ８０１の出力値の上位８−ｂｉｔが計算できる。また、マルチプレクサｍ０３を利用することにより、Ｒ０に格納されている値を次のｃｙｃｌｅでＲ３に格納することで、２，３，４ｃｙｃｌｅ目には同様に図１８記載の線形演算部Ｍ８０１の出力値の９〜１６，１７〜２４，２５〜３２−ｂｉｔ目が計算できる。
【０１２７】
さらに、ラウンド関数実行時の９〜１２ｃｙｃｌｅ目では、上述した線形演算部からの出力に対し、ラウンド鍵との排他的論理和演算が排他的論理和演算部Ｘ９０３で上位８−ｂｉｔから８−ｂｉｔずつ順次実行される。また、図２０記載のＦ関数Ｆ１９３の出力との排他的論理和演算Ｘ１９１は、図１９においてラウンド鍵との排他的論理和演算実行部Ｘ９０３の出力値とレジスタＲ４に格納されている値との排他的論理和演算部Ｘ９０４を利用することで実現される。
【０１２８】
Ｒ４には、９〜１２ｃｙｃｌｅ目において、ｘ１２，ｘ１３，ｘ１４，ｘ１５が順次格納されるため、排他的論理和演算部Ｘ９０４の出力をマルチプレクサｍ０１を利用しレジスタＲ１５に格納することで、４ｃｙｃｌｅ後に（ｘ８，ｘ９，ｘ１０，ｘ１１）をＦ関数に入力したときの出力３２−ｂｉｔと３２−ｂｉｔの（ｘ１２，ｘ１３，ｘ１４，ｘ１５）を排他的論理和した値がＲ１２，Ｒ１３，Ｒ１４，Ｒ１５に８−ｂｉｔずつ格納された状態となる。
【０１２９】
表１に記載の通り、ラウンド関数開始後の４ｃｙｃｌｅ後には，Ｒ１２，Ｒ１３，Ｒ１４，Ｒ１５に（ｘ８，ｘ９，ｘ１０，ｘ１１）をＦ関数に入力したときの出力３２−ｂｉｔと３２−ｂｉｔの（ｘ１２，ｘ１３，ｘ１４，ｘ１５）を排他的論理和した値が格納されている。
【０１３０】
これらの値は、ラウンド関数の出力値の６５−ｂｉｔ目から９６−ｂｉｔ目であるｙ８，ｙ９，ｙ１０，ｙ１１となる。また、図１９記載のマルチプレクサｍ０３を利用し、Ｒ０が保持している値を次のｃｙｃｌｅではＲ３に格納するようにしていたので、表１を参照すると、ラウンド開始後の８ｃｙｃｌｅ後と１２ｃｙｃｌｅ後のＲ０，Ｒ１，Ｒ２，Ｒ３の保持内容は、変化しないことが分かる。
【０１３１】
また、その他のｙ０，ｙ１，ｙ２，ｙ３，ｙ１２，ｙ１３，ｙ１４，ｙ１５は、図１９記載のマルチプレクサｍ０２を利用し、ラウンド開始後の１２ｃｙｃｌｅ後には、それぞれＲ４，Ｒ５，...，Ｒ１１に格納される。
【０１３２】
次にラウンド関数実行時の１３〜１６ｃｙｃｌｅ目についてデータの流れを説明する。上述したように，（ｘ８，ｘ９，ｘ１０，ｘ１１）をＦ関数に入力したときの出力を用いた演算は実行可能ということが分かった。
しかし、ラウンド関数開始後の４ｃｙｃｌｅ後には、ラウンド関数出力の値として必要な（ｘ８，ｘ９，ｘ１０，ｘ１１）の値は保持しておらず、代わりにＦ関数演算時の中間値である（Ｓ（ｘ８），Ｓ（ｘ９），Ｓ（ｘ１０），Ｓ（ｘ１１））のみをＲ０，Ｒ１，Ｒ２，Ｒ３に保持している。
【０１３３】
１３〜１６ｃｙｃｌｅ目では、本発明のポイントとなるＦ関数演算時の中間値からＦ関数への入力を復元する回路を用いて（ｘ８，ｘ９，ｘ１０，ｘ１１）を復元する。ラウンド関数開始後の１２ｃｙｃｌｅ後には、Ｆ関数演算時の中間値として，Ｒ０，Ｒ１，Ｒ２，Ｒ３に（Ｓ（ｘ８），Ｓ（ｘ９），Ｓ（ｘ１０），Ｓ（ｘ１１））の値を保持している。
【０１３４】
図１９記載の非線形演算部Ｓ−１関数Ｓ９０５は，非線形演算部Ｓ−ｂｏｘＳ９０１の逆関数を表している。ラウンド関数開始後の１３〜１６ｃｙｃｌｅ目には、Ｒ０の保持値を非線形演算部Ｓ−１関数に入力し、その出力をマルチプレクサｍ０２を利用し、Ｒ７に格納する。
【０１３５】
このようにすることで、ラウンド関数開始後の１６ｃｙｃｌｅ後には、Ｒ４，Ｒ５，Ｒ６，Ｒ７にｘ８，ｘ９，ｘ１０，ｘ１１がそれぞれ格納された状態になる。さらに、ラウンド関数実行時の１３〜１６ｃｙｃｌｅ目では、次のラウンド関数演算のため、Ｒ４，Ｒ５，Ｒ６，Ｒ７に格納されている（ｙ０，ｙ１，ｙ２，ｙ３）をそれぞれ図１９記載の非線形演算部Ｓ９０１に入力し、その出力をマルチプレクサｍ０３を利用し、Ｒ０，Ｒ１，Ｒ２，Ｒ３に格納する。
【０１３６】
表１に記載の通り、ラウンド関数開始後の１６ｃｙｃｌｅ後には、Ｒ４，Ｒ５，Ｒ６，Ｒ７に（ｘ８，ｘ９，ｘ１０，ｘ１１）の値が格納されている。これらの値は、ラウンド関数の出力値の３３−ｂｉｔ目から６４−ｂｉｔ目であるｙ４，ｙ５，ｙ６，ｙ７となる。
【０１３７】
また、ラウンド関数開始後の１２ｃｙｃｌｅ後にＲ４，Ｒ５，Ｒ６，Ｒ７に格納されていたｙ０，ｙ１，ｙ２，ｙ３は、ラウンド関数開始後の１６ｃｙｃｌｅ後には、非線形演算部Ｓ９０１への入力後、マルチプレクサｍ０３を利用し、Ｒ０，Ｒ１，Ｒ２，Ｒ３に格納される。
【０１３８】
また、ｙ８，ｙ９，ｙ１０，ｙ１１は、ラウンド関数開始後の１６ｃｙｃｌｅ後には、Ｒ８，Ｒ９，Ｒ１０，Ｒ１１にそれぞれ格納される。
また、ｙ１２，ｙ１３，ｙ１４，ｙ１５は、図１９記載のマルチプレクサｍ０１を利用し、ラウンド関数開始後の１６ｃｙｃｌｅ後には、それぞれＲ１２，Ｒ１３，Ｒ１４，Ｒ１５に格納される。
【０１３９】
最後に、暗号文出力時の１６ｃｙｃｌｅ分のデータの流れを説明する。
ｉ∈｛０，１，...，１５｝
に対して、ｃｉを８−ｂｉｔの要素とする。
このとき、（ｃ０，ｃ１，...，ｃ１５）で表される１２８−ｂｉｔを暗号文として考える。
【０１４０】
図１３記載のｒラウンド分のラウンド関数終了時には，図１９記載のＲ０，Ｒ１，...，Ｒ１５には、それぞれ、
Ｓ（ｃ４），Ｓ（ｃ５），Ｓ（ｃ６），Ｓ（ｃ７），ｃ８，ｃ９，ｃ１０，ｃ１１，ｃ１２，ｃ１３，ｃ１４，ｃ１５，ｃ０，ｃ１，ｃ２，ｃ３、
が格納されている。
【０１４１】
暗号文出力時の１６ｃｙｃｌｅでは、Ｒ０に格納されている値は、毎サイクルごとに非線形演算部Ｓ−１関数Ｓ９０５に入力し、その出力をマルチプレクサｍ０１を利用し、Ｒ１５に格納するようにする。
【０１４２】
また、Ｒ８に格納されている値は、毎サイクルごとにマルチプレクサｍ０２を利用し、Ｒ７に格納するようにする。また、Ｒ４に格納されている値は、毎サイクルごとに非線形演算部Ｓ−ｂｏｘＳ９０１に入力し、その出力をマルチプレクサｍ０３を利用し、Ｒ３に格納するようにする。また、暗号文出力時のは毎サイクルごとに、Ｒ１２の値を図１９での暗号文出力ポートから出力する。
上記のようにすることで，暗号文出力ポートから，毎サイクルごとにｃ０，ｃ１，...，ｃ１５の順で順次出力される。
【０１４３】
上述したように、図１９に示す構成において、非線形演算部Ｓ−１関数Ｓ９０５は、非線形演算部Ｓ−ｂｏｘＳ９０１の逆関数を表している。非線形演算部Ｓ−１関数Ｓ９０５は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図１８に示す中間値Ｉ８０４）からＦ関数への入力を復元する演算を実行する。この逆演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１４４】
［４．本開示の手法の効果のまとめ］
従来手法では、Ｆ関数への入力を保持したまま、Ｆ関数の出力を演算していた。この考えのもとでは、ｂｌｏｃｋ長分のレジスタに加え，Ｆ関数演算時の中間値を保持するレジスタが必要となる。
【０１４５】
一方、上述した発開示に係る手法では、Ｆ関数への入力は一度破棄し、Ｆ関数の出力を計算後にＦ関数演算時の中間値から元の入力を復元するための回路を導入する構成としている。
【０１４６】
このようにすることで、必要なレジスタはｂｌｏｃｋ長分のみとなり、従来手法において必要であったＦ関数演算時の中間値を保持するレジスタ分の回路を削減することが可能となる。前章の発明手法の適用例では、Ｆ関数演算時に必要な中間値として図１８に記載の非線形演算部Ｓ８０１後の線形演算部Ｍ８０２に入力される値である保持する中間値Ｉ８０４とし、Ｆ関数の出力を計算可能としている。
【０１４７】
また，従来手法では用いないＳ−ｂｏｘの逆演算処理回路を導入することにより、上記のＦ関数演算時の中間値からＦ関数への入力を復元するようにしている。このようにすることで，結果的にレジスタの削減を達成している。レジスタの回路規模は、他のセルに比べて比較的大きなものとなるため、レジスタの削減が小型化に寄与することは多い。
【０１４８】
［５．その他の実施例について］
前節では，４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造においてラウンド関数内部の構成要素もある程度仮定し、適用法と効果について説明した。本開示の手法は、前節までに説明した具体的なラウンド関数の構造のみではなく、変形、拡張された構造についても適用可能である。
【０１４９】
また、本開示の手法は、４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造のみでなく、２−ｌｉｎｅのＦｅｉｓｔｅｌ構造や，任意のｘ（ｘは２以上の自然数）に対して、ｘ−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に対しても同様な考え方が適用できる。
【０１５０】
（５−１．拡張例１）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２１に記載のＳＰＳ型Ｆ関数にも適用可能である。この場合に考えられるデータパスの例を図２２に示す。
【０１５１】
図２２では、行列の一例として，１行目の要素が（２，３，１，１）となる巡回行列を想定している。また、図２１に記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対して本開示の手法を適用する場合のポイントである保持すべき中間値の例としては、第一非線形演算部Ｓ１０１の出力であり、線形演算部Ｍ１０２への入力となる。
図２１に示す保持する中間値Ｉ１０４となる。
【０１５２】
この場合も、図１８に記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対するＨＷ実装構成例である図１９でのデータの流れと同様に考えられるため、詳細な説明は省略する。
【０１５３】
図１９に記載のデータパスと異なる点を簡単に説明すると、図２２記載のデータパスでは、非線形演算部Ｓ−ｂｏｘＳ１１１の入力前にマルチプレクサｍ０１が導入され、行列演算部Ｍ１１２の出力がマルチプレクサｍ０１を利用し、非線形演算部Ｓ−ｂｏｘＳ１１１に入力され、Ｓ−ｂｏｘＳ１１１の出力がラウンド鍵との排他的論理和部Ｘ１１４に直接入力されている点である。
【０１５４】
これは、図１８記載のＳＰ型Ｆ関数ではなく、図２１記載のＳＰＳ型Ｆ関数を想定している点に起因する。図２１記載のＳＰＳ型Ｆ関数では、線形変換部Ｍ１０２の出力を第二非線形変換部Ｓ１０３に入力し、その第二非線形変換部Ｓ１０３の出力をラウンド鍵との排他的論理和部Ｘ１０５に入力するからである。
【０１５５】
図２２に示す構成において、非線形演算部Ｓ−１関数Ｓ１１３は、非線形演算部Ｓ−ｂｏｘＳ１１１の逆関数を表している。非線形演算部Ｓ−１関数Ｓ１１３は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図２１に示す中間値Ｉ１０４）からＦ関数への入力を復元する演算を実行する。この逆演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１５６】
（５−２．拡張例２）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２３に記載の鍵挿入が複数入ったＳＰＳ型Ｆ関数にも適用可能である。この場合に考えられるデータパスの例を図２４に示す。
【０１５７】
図２４では、行列の一例として、１行目の要素が（２，３，１，１）となる巡回行列を想定している。また、図２３記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対して本開示の手法を適用する場合のポイントである保持すべき中間値の例としては、第一非線形演算部Ｓ１２１の出力であり、線形演算部Ｍ１２２への入力となる。
保持する中間値は、図２３に示す保持する中間値Ｉ１２４となる。
【０１５８】
この場合も、図１８に記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対するＨＷ実装構成例である図１９でのデータの流れを考察することで推測可能と考えられるため、詳細な説明は省略する。
【０１５９】
図１９に記載のデータパスと異なる点を簡単に説明すると、図２４記載のデータパスでは、非線形演算部Ｓ−ｂｏｘＳ１３１の入力前にマルチプレクサｍ０１が導入され、行列演算部Ｍ１３２の出力がラウンド鍵との排他的論理和演算部Ｘ１３４へ入力され、その出力がマルチプレクサｍ０１を利用し、非線形演算部Ｓ−ｂｏｘＳ１３１に入力され、Ｓ−ｂｏｘＳ１３１の出力がラウンド鍵との排他的論理和部Ｘ１３５に直接入力されている点である。
【０１６０】
これは、図１８記載のＳＰ型Ｆ関数ではなく、図２３記載の鍵挿入を複数行なうＳＰＳ型Ｆ関数を想定している点に起因する。図２３記載の鍵挿入を複数行なうＳＰＳ型Ｆ関数では、線形変換部Ｍ１２２の出力を第一のラウンド鍵との排他的論理和演算部Ｘ１２５に入力し、その第一のラウンド鍵との排他的論理和演算部Ｘ１２５の出力を、第二非線形変換部Ｓ１２３に入力し、その第二非線形変換部Ｓ１２３の出力を第二のラウンド鍵との排他的論理和部Ｘ１２６に入力するからである。
【０１６１】
図２４に示す構成において、非線形演算部Ｓ−１関数Ｓ１３３は、非線形演算部Ｓ−ｂｏｘＳ１３１の逆関数を表している。非線形演算部Ｓ−１関数Ｓ１３３は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図２３に示す中間値Ｉ１２４）からＦ関数への入力を復元する演算を実行する。この逆演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１６２】
（５−３．拡張例３）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２５に記載の鍵挿入がＦ関数入力直後にあるＳＰ型Ｆ関数にも適用可能である。この場合に考えられるデータパスの例を図２６に示す。
【０１６３】
図２５に記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対して発明手法を適用する場合のポイントである保持すべき中間値の例としては、非線形演算部Ｓ１４１の出力であり、線形演算部Ｍ１４２への入力となる。
保持する中間値は、図２５に示す保持する中間値Ｉ１４４となる。
【０１６４】
図１８に表されるＦ関数と異なり、Ｆ関数演算時の中間値である図２５記載の保持する中間値Ｉ１４４からＦ関数への入力を復元するためには、Ｓ−１だけでなく、Ｆ関数への入力直後に排他的論理和したときと同じラウンド鍵を排他的論理和する回路が必要となる。これは、図１８に表されるＦ関数と異なり、図２５に記載の保持する中間値からＦ関数の入力を復元するためには、非線形演算部Ｓ１４１の逆演算のみでなく、その逆演算した値に対して、ラウンド鍵との排他的論理和演算部Ｘ１４３の逆演算も必要となるためである。
【０１６５】
この場合も、図１８記載のＦ関数を持つ拡張Ｆｅｉｓｔｅｌ構造に対するＨＷ実装構成例である図１９でのデータの流れを考察することで推測可能と考えられるため、詳細な説明は省略する。図２６記載のデータパスでは、非線形演算部Ｓ−ｂｏｘＳ１５１の入力前にラウンド鍵との排他的論理和演算部Ｘ１５４が導入される。
【０１６６】
一方、行列演算部Ｍ１５２からの出力は、ラウンド鍵との排他的論理和演算を実行せずに、Ｒ４に格納されている値との排他的論理和演算部Ｘ１５６に直接入力される。また、Ｒ０に格納されている値は、非線形演算Ｓ−１関数に入力後、ラウンド鍵との排他的論理和演算部Ｘ１５５に入力されている点も図１９と異なる点である。これは、前述の通り、図２５記載の保持する中間値Ｉ１４４からＦ関数の入力を復元するためには、非線形演算部Ｓ１４１の逆演算のみでなく、その逆演算した値に対して、ラウンド鍵との排他的論理和演算部Ｘ１４３の逆演算も必要となるためである。
【０１６７】
図２６に示す構成において、非線形演算部Ｓ−１関数Ｓ１５３は、非線形演算部Ｓ−ｂｏｘＳ１５１の逆関数を表している。非線形演算部Ｓ−１関数Ｓ１５３は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図２５に示す中間値Ｉ１４４）からＦ関数への入力を復元する演算を実行する。この逆演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１６８】
（５−４．拡張例４）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２７に記載のＦ関数にも適用可能である。図２７に記載のＦ関数は、これまでに説明したＦ関数と大きく構造が異なるため、詳細に説明する。
【０１６９】
図２７に記載のＦ関数は、Ｆ関数への入力を第一の非線形演算部Ｓ１６１で演算し、その第一の非線形演算部Ｓ１６１の出力を第二の非線形演算部Ｓ１６２へ入力する。その後、繰り返し構造となり、第一，第二の非線形演算部と同じ演算をｓ−１回施し、最終的に第一，第二の非線形演算部と同じ演算である、第ｓの非線形演算部Ｓ１６ｓの出力をラウンド鍵との排他的論理和演算部Ｘ１０５に入力し、その出力をＦ関数の出力とするような構造である。
【０１７０】
このようなＦ関数においても、シリアル処理を実行するハードウェア回路を考えたときには、各サイクルごとにＦ関数演算時の中間値である図２７に記載の保持する中間値Ｉ１６４の値を保持するレジスタが必要となる。
【０１７１】
図２７に記載のＦ関数を保持する拡張Ｆｅｉｓｔｅｌ構造を持つ暗号アルゴリズムに対しても発明手法の効果は得られる。図１８，図１９で紹介したことと同様に，図２７に記載の保持する中間値Ｉ１６４からＦ関数の入力を復元することが可能であるため、そのための回路を導入することで、ブロック長分のみのレジスタで回路を実現できる。
【０１７２】
Ｆ関数内部が繰り返し構造となっているが、ｓ＝４としたときに考えられるデータパスの例を図２８に示す。図２７に記載のＦ関数は内部の繰り返し構造が４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造と似ており、Ｆｅｉｓｔｅｌ構造の性質から非線形回路Ｓ−１関数を用いずとも、Ｓ−ｂｏｘ回路である非線形演算部Ｓ１７２，Ｓ１７３のみを用いることにより、図２７に記載の保持する中間値Ｉ１６４からＦ関数の入力を復元することが可能である。
【０１７３】
図２８に示す構成において、非線形演算部Ｓ１７２，Ｓ１７３は、レジスタＲ０〜Ｒ３に格納されるＦ関数演算時の中間値（図２７に示す中間値Ｉ１６４）からＦ関数への入力を復元する演算を実行する。この演算構成によって次段のラウンド関数に対する入力値が算出可能となり、上述したと同様のレジスタ削減効果が期待できる。
【０１７４】
また、図２８に記載のデータパスでは、Ｓ−ｂｏｘ回路を二つ利用しているが、一つだけを利用することでもデータパスを記述することが可能であることは容易に推測できる。また、データパスは多少変更する必要があるが任意の繰り返し段数ｓに対してデータパスは構成可能である。また、図２８に現れる"ｅｎ"という記号で表される制御信号Ｅ１７４は、必要なタイミングでｈｉｇｈとなるように制御されるイネーブル信号を表し、図２８には示されていないが制御部によって制御がされる。
【０１７５】
（５−５．拡張例５）
本開示の方式は、図１８に記載のＳＰ型Ｆ関数だけではなく、図２９に記載のＦ関数にも適用可能である。図２９は、図２７に記載の繰り返し型のＦ関数の非線形演算部Ｓ１６１，Ｓ１６２，Ｓ１６ｓが，図２９記載の非線形演算部Ｓ１８１，Ｓ１８２，Ｓ１８ｓに変更されたものと考えることができる。
【０１７６】
このようなＦ関数においても、シリアル処理を実行するハードウェア回路考えたときには、各サイクルごとにＦ関数演算時の中間値である図２９記載の保持する中間値Ｉ１８４の値を保持するレジスタが必要となる。
【０１７７】
図２９に記載のＦ関数を保持する拡張Ｆｅｉｓｔｅｌ構造を持つ暗号アルゴリズムに対しても発明手法の効果は得られる。図１８，図１９を参照して説明したことと同様に、図２９に記載の保持する中間値Ｉ１８４からＦ関数の入力を復元することが可能であるため、そのための回路を導入することで、ブロック長分のみのレジスタで回路を実現できる。
【０１７８】
Ｆ関数の構造上、Ｓ−ｂｏｘの逆演算処理回路であるＳ−１を導入することで、図２９に記載の保持する中間値Ｉ１８４からＦ関数の入力を復元することが可能である。また、Ｆ関数内部が繰り返し構造となっているが、任意の繰り返し段数に対して発明手法は適用可能である。
【０１７９】
（５−６．拡張例６）
ここで記載した具体的なＦ関数の構成は限られたものであるが、本開示の手法は、適した回路を導入することで中間値からＦ関数の入力を復元することが可能となる任意のＦ関数に適用可能である。
【０１８０】
（５−７．拡張例７）
Ｆ関数に行列演算を含む場合、本開示の手法は、巡回行列のみでなくアダマール行列に対しても適用可能であり、同様の効果が期待できる。また、上記以外の行列に対しても発明手法のアイデアは適用できる。
【０１８１】
（５−８．拡張例８）
Ｆ関数に行列演算を含む場合、本開示の方式は、４×４行列のみでなく任意のｘ（ｘは２以上の自然数）に対して，ｘ×ｘ行列でも同様の考えが適用可能であり、同様の効果が期待できる。
【０１８２】
（５−９．拡張例９）
４−ｌｉｎｅｔｙｐｅ−２拡張Ｆｅｉｓｔｅｌ構造を例に本開示の手法の適用例について説明したが、ｔｙｐｅ−１，ｔｙｐｅ−３の拡張Ｆｅｉｓｔｅｌ構造に対しても適用可能であり、同様の効果が期待できる。
【０１８３】
（５−１０．拡張例１０）
４−ｌｉｎｅｔｙｐｅ−２拡張Ｆｅｉｓｔｅｌ構造を例に本開示の手法の適用例について説明したが、２−ｌｉｎｅのＦｅｉｓｔｅｌ構造に対しても適用可能であり、同様の効果が期待できる。
【０１８４】
（５−１１．拡張例１１）
４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造への適用と同様の考えで、任意のｘ（ｘは３以上の自然数）に対して、ｘ−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造に対しても適用可能であり、同様の効果が期待できる。
【０１８５】
（５−１２．拡張例１２）
図２０に点線枠で示すように、１つのラウンド関数の出力は、次の段のラウンド関数へ出力する際に、各ラインのデータ単位でシフト処理等の入れ替え処理が行われる。
このラウンド関数間のデータ入れ替え、すなわち、前段のラウンドの出力を後段のラウンドへ出力する際に、各ライン単位でデータを入れ替える処理をラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）と呼ぶ。
【０１８６】
例えば、図２０に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造における、ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）は以下の設定となっている。
左から１番目のラインの出力を、次のラウンド関数の左から４番目のラインへの入力に設定、
左から２番目のラインの出力を、次のラウンド関数の左から１番目のラインへの入力に設定、
左から３番目のラインの出力を、次のラウンド関数の左から２番目のラインへの入力に設定、
左から４番目のラインの出力を、次のラウンド関数の左から３番目のラインへの入力に設定、
上記のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の設定例である。
【０１８７】
例えば図１９を参照して説明したデータパスは、上記のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）設定に対応したデータパス構成例である。
【０１８８】
本開示の方式は、図２０に示すウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の設定に限らず、任意のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）に対して適用可能である。
【０１８９】
すなわち、任意のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）を持つ構成においても、Ｆ関数実行部における中間データからの逆演算構成を設定することで、上述したと同様のレジスタ削減効果が期待できる。
ただし、データパスの設定は、各ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の設定に応じた構成とすることが必要である。
【０１９０】
図２０に示すラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）構成と異なるラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の１つの構成例を図３０に示す。
図３０に示すラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）は、前段のラウンド関数の各ライン出力である（ｎ／４）ｂｉｔのそれぞれを２分割し、（ｎ／８）ｂｉｔの２つのライン出力に分割する。
各々が（ｎ／８）ｂｉｔのデータを持つ計８ラインのデータを次のラウンド関数に入力する際に、各ライン単位でデータ入れ替え（置換）を行う構成としている。
【０１９１】
図３０に示す４−ｌｉｎｅ拡張Ｆｅｉｓｔｅｌ構造における、ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）は以下の設定となっている。
左から１番目のラインの出力を２分割した前半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から４番目のラインの前半データ（ｎ／８）ｂｉｔの入力に設定、
左から１番目のラインの出力を２分割した後半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から２番目のラインの後半データ（ｎ／８）ｂｉｔの入力に設定、
左から２番目のラインの出力を２分割した前半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から１番目のラインの前半データ（ｎ／８）ｂｉｔの入力に設定、
左から２番目のラインの出力を２分割した後半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から３番目のラインの後半データ（ｎ／８）ｂｉｔの入力に設定、
【０１９２】
左から３番目のラインの出力を２分割した前半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から２番目のラインの前半データ（ｎ／８）ｂｉｔの入力に設定、
左から３番目のラインの出力を２分割した後半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から４番目のラインの後半データ（ｎ／８）ｂｉｔの入力に設定、
左から４番目のラインの出力を２分割した前半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から３番目のラインの前半データ（ｎ／８）ｂｉｔの入力に設定、
左から４番目のラインの出力を２分割した後半データ（ｎ／８）ｂｉｔを、次のラウンド関数の左から１番目のラインの後半データ（ｎ／８）ｂｉｔの入力に設定、
上記のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）の設定例である。
なお、図３０に示すラウンド関数におけるＦ関数は、図２１に記載したＳＰＳ型Ｆ関数であると想定している。
【０１９３】
図３０に示す、ラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｉｏｎ）を実行する構成におけるラウンド関数部のデータパスの例を図３１に示す。
図３１に示すデータパスは、Ｆ関数として、図２１に記載のＳＰＳ型Ｆ関数を適用した場合の構成例である。また、Ｆ関数における線形変換実行部である行列演算部Ｍ２０４で適用する行列の一例として，１行目の要素が（２，３，１，１）となる巡回行列を想定している。
【０１９４】
本構成例においてレジスタに保持する中間値は，図２１に示す第一非線形演算部Ｓ１０１の出力であり、線形演算部Ｍ１０２への入力であり、図２１に示す中間値Ｉ１０４となる。
図３１において、これらの中間値は、レジスタＲ０〜Ｒ３に保持される。
基本的なデータの流れは、先に拡張例１として説明した図２２に示すデータパスと同様のものであり、非線形演算部Ｓ−ｂｏｘＳ２０３の入力前にマルチプレクサｍ２０２が設定されている。行列演算部Ｍ２０４の出力がマルチプレクサｍ２０２を利用し、非線形演算部Ｓ−ｂｏｘＳ２０３に入力され、Ｓ−ｂｏｘＳ２０３の出力が排他的論理和部Ｘ２０６に入力される。
【０１９５】
図３１に記載のデータパスでは、図２２に示す構成と異なり、Ｓ−ｂｏｘＳ２０３の出力に対してラウンド鍵との排他的論理和演算を実行する前に、排他的論理和演算部Ｘ２０６に入力され、レジスタＲ４に格納されている値との排他的論理和演算を実行する構成としている。この排他的論理和結果とラウンド鍵が、排他的論理和演算部Ｘ２０１において排他的論理和演算される。
【０１９６】
また、レジスタＲ８とレジスタＲ１５を結ぶパスｐ２１１と、ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部Ｘ２０１の出力とレジスタＲ７を結ぶパスｐ２１２を加えている。これは、図２２とは異なるラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｔｉｏｎ）、すなわち図３０に示す設定のラウンド置換（ｒｏｕｎｄ ｐｅｒｍｕｔａｔｉｏｎ）を実現するためのパス設定である。
【０１９７】
この図３１に示すデータパスにおいても、前述した図１９、図２２他の実施例と同様、Ｆ関数実行部における中間データからの逆演算構成、すなわち非線形演算部Ｓ−１関数Ｓ２０５を設定することで、次段のラウンド関数に対する入力値を算出可能とすることで、上述したと同様のレジスタ削減効果が期待できる。
【０１９８】
［６．暗号処理装置の構成例について］
最後に、上述した実施例に従った暗号処理を実行する暗号処理装置の実装例について説明する。
上述した実施例に従った暗号処理を実行する暗号処理装置は、暗号処理を実行する様々な情報処理装置に搭載可能である。具体的には、ＰＣ、ＴＶ、レコーダ、プレーヤ、通信機器、さらに、ＲＦＩＤ、スマートカード、センサネットワーク機器、デンチ／バッテリー認証モジュール、健康、医療機器、自立型ネットワーク機器等、例えばデータ処理や通信処理に伴う暗号処理を実行する様々な危機において利用可能である。
【０１９９】
本開示の暗号処理を実行する装置の一例としてのＩＣモジュール７００の構成例を図３２に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図３２に示すＩＣモジュール７００は、これら様々な機器に構成することが可能である。
【０２００】
図３２に示すＣＰＵ(Central processing Unit)７０１は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ７０２は、ＣＰＵ７０１が実行するプログラム、あるいは演算パラメータなどの固定データを格納するＲＯＭ（Read-Only-Memory）、ＣＰＵ７０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるＲＡＭ（Random Access Memory）等からなる。また、メモリ７０２は暗号処理に必要な鍵データや、暗号処理において適用する変換テーブル（置換表）や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【０２０１】
暗号処理部７０３は、上記において説明した暗号処理構成、すなわち、例えば拡張Ｆｅｉｓｔｅｌ構造や、Ｆｅｉｓｔｅｌ構造を適用した共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理を実行する。
【０２０２】
なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭに格納し、ＣＰＵ７０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。
【０２０３】
乱数発生器７０４は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【０２０４】
送受信部７０５は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ＩＣモジュールとのデータ通信を実行し、ＩＣモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【０２０５】
なお、上述した実施例において説明した暗号処理装置は、入力データとしての平文を暗号化する暗号化処理に適用可能であるのみならず、入力データとしての暗号文を平文に復元する復号処理にも適用可能である。
暗号化処理、復号処理、双方の処理において、上述した実施例において説明したレジスタ削減構成を持つＦ関数実行部の構成をそのまま適用することが可能である。
【０２０６】
［７．本開示の構成のまとめ］
以上、特定の実施例を参照しながら、本開示の実施例について詳解してきた。しかしながら、本開示の要旨を逸脱しない範囲で当業者が実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本開示の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０２０７】
なお、本明細書において開示した技術は、以下のような構成をとることができる。
（１）データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、
前記Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行部と、
を有する暗号処理装置。
【０２０８】
（２）前記Ｆ関数実行部は、Ｆ関数実行部への入力データに対する非線形変換処理を実行するＳ−ｂｏｘを有し、前記中間データ格納レジスタは、前記Ｓ−ｂｏｘの出力値を中間データとして保持し、前記逆演算実行部は、前記Ｓ−ｂｏｘによる非線形変換処理の逆演算を含む演算処理により、前記Ｆ関数実行部に対する入力データを算出する前記（１）に記載の暗号処理装置。
【０２０９】
（３）前記Ｆ関数実行部は、非線形変換部、および線形変換部を有し、前記非線形変換部の出力を前記中間データとして格納するレジスタを有し、前記線形変換部は、前記レジスタの格納値に対する線型変換処理を実行し、前記逆演算実行部は、前記レジスタの格納値に対する演算処理により、前記Ｆ関数実行部に対する入力データを算出する前記（１）または（２）に記載の暗号処理装置。
【０２１０】
（４）前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行するＳＰ型Ｆ関数である前記（１）〜（３）いずれかに記載の暗号処理装置。
【０２１１】
（５）前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行し、さらに非線形変換部において再度、非線形変換処理をするＳＰＳ型Ｆ関数である前記（１）〜（４）いずれかに記載の暗号処理装置。
【０２１２】
（６）前記Ｆ関数実行部は、外部から入力するラウンド鍵との排他的論理和演算部を有する前記（１）〜（５）いずれかに記載の暗号処理装置。
（７）前記Ｆ関数実行部は、複数の非線形演算部の繰り返し構造を有する前記（１）〜（６）いずれか１に記載の暗号処理装置。
（８）前記暗号処理部は、入力データとしての平文を暗号文に変換する暗号化処理、または、入力データとしての暗号文を平文に変換する復号処理を実行する前記（１）〜（７）いずれか１に記載の暗号処理装置。
【０２１３】
さらに、上記した装置およびシステムにおいて実行する処理の方法や、処理を実行させるプログラムも本開示の構成に含まれる。
【０２１４】
また、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。例えば、プログラムは記録媒体に予め記録しておくことができる。記録媒体からコンピュータにインストールする他、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネットといったネットワークを介してプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０２１５】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０２１６】
上述したように、本開示の一実施例の構成によれば、暗号処理構成の小型化が実現される。
具体的には、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、暗号処理部は、複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、中間データ格納レジスタの格納データに基づいて、Ｆ関数実行部に対する入力データを算出する逆演算実行部を有する。逆演算実行部における逆演算により、Ｆ関数実行部に対する入力値を算出可能となり、このデータを保持するレジスタを削減することが可能となり、暗号処理構成の小型化が実現される。
【符号の説明】
【０２１７】
７００ ＩＣモジュール
７０１ ＣＰＵ(Central processing Unit)
７０２ メモリ
７０３ 暗号処理部
７０４ 乱数生成部
７０５ 送受信部
【特許請求の範囲】
【請求項１】
データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、
前記Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行部と、
を有する暗号処理装置。
【請求項２】
前記Ｆ関数実行部は、
Ｆ関数実行部への入力データに対する非線形変換処理を実行するＳ−ｂｏｘを有し、
前記中間データ格納レジスタは、前記Ｓ−ｂｏｘの出力値を中間データとして保持し、
前記逆演算実行部は、
前記Ｓ−ｂｏｘによる非線形変換処理の逆演算を含む演算処理により、前記Ｆ関数実行部に対する入力データを算出する請求項１に記載の暗号処理装置。
【請求項３】
前記Ｆ関数実行部は、
非線形変換部、および線形変換部を有し、前記非線形変換部の出力を前記中間データとして格納するレジスタを有し、
前記線形変換部は、前記レジスタの格納値に対する線型変換処理を実行し、
前記逆演算実行部は、前記レジスタの格納値に対する演算処理により、前記Ｆ関数実行部に対する入力データを算出する請求項１に記載の暗号処理装置。
【請求項４】
前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行するＳＰ型Ｆ関数である請求項１に記載の暗号処理装置。
【請求項５】
前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行し、さらに非線形変換部において再度、非線形変換処理をするＳＰＳ型Ｆ関数である請求項１に記載の暗号処理装置。
【請求項６】
前記Ｆ関数実行部は、外部から入力するラウンド鍵との排他的論理和演算部を有する請求項１に記載の暗号処理装置。
【請求項７】
前記Ｆ関数実行部は、複数の非線形演算部の繰り返し構造を有する請求項１に記載の暗号処理装置。
【請求項８】
前記暗号処理部は、
入力データとしての平文を暗号文に変換する暗号化処理、または、
入力データとしての暗号文を平文に変換する復号処理を実行する請求項１に記載の暗号処理装置。
【請求項９】
暗号処理装置において実行する暗号処理方法であり、
暗号処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理ステップを実行し、
前記暗号処理ステップは、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行ステップと、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行ステップと、
前記Ｆ関数実行ステップにおける変換データの生成過程の中間データを中間データ格納レジスタに格納するステップと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行ステップと、
を実行する暗号処理方法。
【請求項１０】
暗号処理装置において暗号処理を実行させるプログラムであり、
暗号処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理ステップを実行させ、
前記暗号処理ステップにおいて、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行ステップと、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行ステップと、
前記Ｆ関数実行ステップにおける変換データの生成過程の中間データを中間データ格納レジスタに格納するステップと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行ステップと、
を実行させるプログラム。
【請求項１】
データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行部と、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行部と、
前記Ｆ関数実行部における変換データの生成過程の中間データを格納する中間データ格納レジスタと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行部と、
を有する暗号処理装置。
【請求項２】
前記Ｆ関数実行部は、
Ｆ関数実行部への入力データに対する非線形変換処理を実行するＳ−ｂｏｘを有し、
前記中間データ格納レジスタは、前記Ｓ−ｂｏｘの出力値を中間データとして保持し、
前記逆演算実行部は、
前記Ｓ−ｂｏｘによる非線形変換処理の逆演算を含む演算処理により、前記Ｆ関数実行部に対する入力データを算出する請求項１に記載の暗号処理装置。
【請求項３】
前記Ｆ関数実行部は、
非線形変換部、および線形変換部を有し、前記非線形変換部の出力を前記中間データとして格納するレジスタを有し、
前記線形変換部は、前記レジスタの格納値に対する線型変換処理を実行し、
前記逆演算実行部は、前記レジスタの格納値に対する演算処理により、前記Ｆ関数実行部に対する入力データを算出する請求項１に記載の暗号処理装置。
【請求項４】
前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行するＳＰ型Ｆ関数である請求項１に記載の暗号処理装置。
【請求項５】
前記Ｆ関数実行部は、Ｆ関数実行部に対する入力に対して非線形変換部において非線形変換処理を実行し、さらに線形変換部において線形変換処理を実行し、さらに非線形変換部において再度、非線形変換処理をするＳＰＳ型Ｆ関数である請求項１に記載の暗号処理装置。
【請求項６】
前記Ｆ関数実行部は、外部から入力するラウンド鍵との排他的論理和演算部を有する請求項１に記載の暗号処理装置。
【請求項７】
前記Ｆ関数実行部は、複数の非線形演算部の繰り返し構造を有する請求項１に記載の暗号処理装置。
【請求項８】
前記暗号処理部は、
入力データとしての平文を暗号文に変換する暗号化処理、または、
入力データとしての暗号文を平文に変換する復号処理を実行する請求項１に記載の暗号処理装置。
【請求項９】
暗号処理装置において実行する暗号処理方法であり、
暗号処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理ステップを実行し、
前記暗号処理ステップは、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行ステップと、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行ステップと、
前記Ｆ関数実行ステップにおける変換データの生成過程の中間データを中間データ格納レジスタに格納するステップと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行ステップと、
を実行する暗号処理方法。
【請求項１０】
暗号処理装置において暗号処理を実行させるプログラムであり、
暗号処理部が、データ処理対象となるデータの構成ビットを複数ラインに分割して入力し、各ラインのデータに対してデータ変換処理を繰り返して実行する暗号処理ステップを実行させ、
前記暗号処理ステップにおいて、
前記複数ラインを構成する１ラインのデータを入力して、変換データを生成するＦ関数実行ステップと、
前記Ｆ関数の出力に対する他ラインのデータとの排他的論理和演算を実行する排他的論理和演算実行ステップと、
前記Ｆ関数実行ステップにおける変換データの生成過程の中間データを中間データ格納レジスタに格納するステップと、
前記中間データ格納レジスタの格納データに基づいて、前記Ｆ関数実行部に対する入力データを算出する逆演算実行ステップと、
を実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【公開番号】特開２０１２−２１５８１４（Ｐ２０１２−２１５８１４Ａ）
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願番号】特願２０１１−２０７７０３（Ｐ２０１１−２０７７０３）
【出願日】平成２３年９月２２日（２０１１．９．２２）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願日】平成２３年９月２２日（２０１１．９．２２）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]