(57)【特許請求の範囲】
【請求項１】
データ処理対象となるデータブロックの構成ビットを複数のラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインの第１ラインのデータに対する変換データを生成し、生成した変換データに対して前記第１ラインと異なる第２ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行する演算部と、
前記演算部の演算結果を保持するレジスタを有し、
前記演算部は、前記レジスタから順次、データを取得して取得データ順の演算を実行して演算結果を前記レジスタに格納する構成であり、
前記演算部は、
前記第１ラインのデータに対する行列を適用した線形変換を実行する行列演算実行部を有し、
前記行列演算実行部は、
前記第１ラインのデータに対する行列演算の実行サイクル中、最初のサイクルの行列演算の実行に際して前記第２ラインのデータとの演算を実行する暗号処理装置。
【請求項２】
前記行列演算実行部は、
前段の非線形変換部から順次出力される複数の単位データに対する行列演算を複数サイクルで実行する構成であり、前記複数サイクルの最初のサイクルで、前記非線形変換部から入力する単位データの行列演算に併せて前記第２ラインのデータとの演算を実行する請求項１に記載の暗号処理装置。
【請求項３】
前記暗号処理装置は、
前記第１ラインのデータに対する行列演算に必要な演算サイクルの完了後に前記第２ラインのデータとの演算を実行する場合に必要となる前記第２ラインのデータ保持用の独立したレジスタを削減し、
前記第１ラインのデータに対する行列演算の途中結果の保持用レジスタを前記第２ラインのデータ保持用のレジスタとして利用した構成を有する請求項１に記載の暗号処理装置。
【請求項４】
前記行列演算実行部は、
前記第１ラインのデータに対する行列演算を実行する初期サイクルにおいて、前記第１ラインに対する行列演算過程データと前記第２ラインのデータとの排他的論理和演算を実行する請求項１に記載の暗号処理装置。
【請求項５】
前記行列演算実行部は、
巡回行列またはアダマール行列を適用した行列演算を実行する構成である請求項１に記載の暗号処理装置。
【請求項６】
前記暗号処理部は、前記ラウンド関数の実行部として、
非線形変換処理を実行する非線形変換部と、行列を適用した線形変換処理を実行する線形変換部としての行列演算実行部を有する請求項１に記載の暗号処理装置。
【請求項７】
前記行列演算実行部は、
前記非線形変換部としてのＳ−ｂｏｘの出力を、順次入力して入力データに対する行列演算を１サイクル処理として実行する請求項１に記載の暗号処理装置。
【請求項８】
前記暗号処理部の実行する暗号処理は、Ｆｅｉｓｔｅｌ構造または一般化Ｆｅｉｓｔｅｌ構造を適用した暗号処理である請求項１に記載の暗号処理装置。
【請求項９】
前記暗号処理部の実行する暗号処理は、ＣＬＥＦＩＡ暗号アルゴリズムに従った暗号処理である請求項１に記載の暗号処理装置。
【請求項１０】
暗号処理装置において暗号処理を実行する暗号処理方法であり、
暗号処理部が、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第１ラインのデータの変換処理を実行し、生成した変換データに対して前記第１ラインと異なる第２ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行し、
前記第１ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第２ラインのデータとの演算を実行する暗号処理方法。
【請求項１１】
暗号処理装置において暗号処理を実行させるプログラムであり、
暗号処理部に、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行させる暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第１ラインのデータの変換処理を実行し、生成した変換データに対して前記第１ラインと異なる第２ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行させ、
前記第１ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第２ラインのデータとの演算を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理装置、および暗号処理方法、並びにプログラムに関する。さらに詳細には、Ｆｅｉｓｔｅｌ構造や一般化Ｆｅｉｓｔｅｌ構造を持つ共通鍵ブロック暗号を実行する暗号処理装置、および暗号処理方法、並びにプログラムに関する。
【背景技術】
【０００２】
情報化社会が発展すると共に、扱う情報を安全に守るための情報セキュリティ技術の重要性が増してきている。情報セキュリティ技術の構成要素の一つとして暗号技術があり、現在では様々な製品やシステムで暗号技術が利用されている。
【０００３】
暗号処理アルゴリズムには様々なものがあるが、基本的な技術の一つとして、共通鍵ブロック暗号と呼ばれるものがある。共通鍵ブロック暗号では、暗号化用の鍵と復号用の鍵が共通のものとなっている。暗号化処理、復号処理共に、その共通鍵から複数の鍵を生成し、あるブロック単位、例えば６４ビット、１２８ビット、２５６ビット等のブロックデータ単位でデータ変換処理を繰り返し実行する。
【０００４】
代表的な共通鍵ブロック暗号のアルゴリズムとしては、過去の米国標準であるＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）や現在の米国標準であるＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）が知られている。他にも様々な共通鍵ブロック暗号が現在も提案され続けており、２００７年にソニー株式会社が提案したＣＬＥＦＩＡも共通鍵ブロック暗号の一つである。
【０００５】
このような、共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を繰り返し実行するラウンド関数実行部を有する暗号処理部と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部とによって構成される。鍵スケジュール部は、秘密鍵であるマスター鍵（主鍵）に基づいて、まずビット数を増加させた拡大鍵を生成し、生成した拡大鍵に基づいて、暗号処理部の各ラウンド関数部で適用するラウンド鍵（副鍵）を生成する。
【０００６】
このようなアルゴリズムを実行する具体的な構造として、線形変換部および非線形変換部を有するラウンド関数を繰り返し実行する構造が知られている。例えば代表的な構造にＦｅｉｓｔｅｌ構造や一般化Ｆｅｉｓｔｅｌ構造がある。Ｆｅｉｓｔｅｌ構造や一般化Ｆｅｉｓｔｅｌ構造は、データ変換関数としてのＦ関数を含むラウンド関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。Ｆ関数においては、線形変換処理および非線形変換処理が実行される。なお、Ｆｅｉｓｔｅｌ構造を適用した暗号処理について記載した文献としては、例えば非特許文献１、非特許文献２がある。
【０００７】
暗号アルゴリズムの実装形態には、ソフトウェア実装とハードウェア実装の二種類が存在する。ハードウェア実装では、回路規模が小さくなるように実装することで、ハードウェア化の際のコストダウンや低消費電力化が期待できる。そのため、新アルゴリズム、既存アルゴリズムを問わず、小型化するための実装法が様々、提案されている。
【０００８】
例えばＨａｍａｌａｉｎｅｎ，Ａｌｈｏ、Ｈａｎｎｉｋａｉｎｅｎ、Ｈａｍａｌａｉｎｅｎらは、Ｓｕｂｓｔｉｔｕｔｉｏｎ  Ｐｅｒｍｕｔａｔｉｏｎ  Ｎｅｔｗｏｒｋ（ＳＰＮ）構造を持つＡＥＳ暗号アルゴリズムに対する小型実装法を提案している。この小型実装法については、非特許文献３［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］に開示されている。
【００５０】
このＡＥＳ暗号アルゴリズムの小型実装手法について説明する。
まず、図４を参照してＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムのラウンド関数の構造について説明する。
なお、ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおいてもＦｅｉｓｔｅｌ構造と同様、ラウンド関数を複数回、繰り返し実行する構成を持つ。
図４は、ＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムにおいて利用されるラウンド関数実行部の構成例を示す図である。ＡＥＳでは、図４に示すラウンド関数を、複数回、繰り返して平文から暗号文、または暗号文から平文の生成を行う。
【００５１】
図４に示すラウンド関数実行部は以下の構成要素によって構成される。
非線形変換処理を実行する８ビット入出力の１６個のＳ−ｂｏｘからなる非線形変換部２０１、
非線形変換部２０１を構成するＳ−ｂｏｘからの８ビット出力の入れ替え処理としてのＳｈｉｆｔ  Ｌｏｗ実行部２０２、
Ｓｈｉｆｔ  Ｌｏｗ実行部２０２の出力を３２ビット単位で入力して行列を適用した線形変換処理を実行する４つの行列演算部からなる線形変換部２０３、
線形変換部２０３を構成する４つの行列演算部各々からの３２ビット出力に対して３２ビットのラウンド鍵との排他的論理和演算を実行する４つの演算部からなる排他的論理和演算部２０４を有する。
【００５２】
図４に示す例は、入出力１２８ビットのラウンド関数実行部であり、１６個のＳ−ｂｏｘ各々に８ビット、計８×１６＝１２８ビットを入力し、４つの排他的論理和部の各々〜３２ビット、計３２×４＝１２８ビット出力を行う構成である。非線形変換部２０１、Ｓｈｉｆｔ  Ｌｏｗ実行部２０２、線形変換部２０３、排他的論理和演算部２０４、これらを適用した一連の処理を１回のラウンド関数の実行処理として実行し、このラウンド関数を複数回、繰り返して１２８ビットの入力データ（例えば平文）から、１２８ビットの出力（例えば暗号文）を生成して出力する。
【００５３】
ＡＥＳの実装において、１つのラウンド関数の処理（１  ｒｏｕｎｄ）、すなわち、非線形変換部２０１、Ｓｈｉｆｔ  Ｌｏｗ実行部２０２、線形変換部２０３、排他的論理和演算部２０４、これらを適用した一連の処理を、１サイクル（１  ｃｙｃｌｅ）で実行しようとすると、少なくとも、図４に示すように、１６個のＳ−ｂｏｘの回路と、４個の行列演算回路がデータ暗号化部の構成として必要となる。
【００５４】
Ｈａｍａｌａｉｎｅｎらは、１つのラウンド関数の処理（１  ｒｏｕｎｄ）を、１サイクルではなく、１６サイクル（１６  ｃｙｃｌｅ）で順次シリアル処理として行う設定とすることで、データ暗号化部の小型化を実現した。
この小型化構成では、Ｓ−ｂｏｘの回路は１個しか用いず、さらに、４サイクル（４ｃｙｃｌｅ）かけて１つの行列演算を実行する。このような実装とすることで、行列演算回路の小型化を実現している。
【００５５】
図５にＨａｍａｌａｉｎｅｎらの提案したＡＥＳ暗号を実行するデータ暗号化部のデータパスを示す。図５に示す構成は、図４に示すＡＥＳ暗号のラウンド関数を実行するハードウェア構成に相当する。
【００５６】
図５に示す構成において、演算中のデータは８−ｂｉｔ単位に分割され、各８ビットデータをレジスタｒ０１〜ｒ１９に格納している。図５には１９個のレジスタ（ｒ０１〜ｒ１９）が示されている。１９個のレジスタ（ｒ０１〜ｒ１９）の各々は８ビットデータを保持する８ビットレジスタである。
【００５７】
図４を参照して説明した通り、図４に示す構成例は、入出力１２８ビットのラウンド関数実行部であり、図５は、入出力１２８ビットのラウンド関数を８ビット単位データのシリアル処理として実行するハードウェア構成に対応する。
【００５８】
図５の構成において、入出力データをすべて格納するために必要となる８ビットレジスタの数は、１２８／８＝１６であり、１６個のレジスタがあればよい。図５には１９個のレジスタがあり、３つのレジスタが余分であるが、これら２４ビット分の３つのレジスタは、行列を適用した線形変換処理を実行するための行列演算処理のために利用される。
【００５９】
また、図４を参照して説明したように、ＡＥＳでは、非線形変換を実行するＳ−ｂｏｘと線形変換を実行する行列演算の間にＳｈｉｆｔ  Ｌｏｗ実行部によるデータ置換が実行される。Ｈａｍａｌａｉｎｅｎらの実装手法では、図５中のいくつかのレジスタの前にマルチプレクサ（Ｍｕｌｔｉｐｌｅｘｅｒ）ｍ０１〜ｍ０８を導入することにより、Ｓｈｉｆｔ  Ｌｏｗ実行部で行なわれる置換を実現している。
【００６０】
図５に示すように、非線形変換部としてのＳ−ｂｏｘ２５２は１個しかない。このＳ−ｂｏｘ２５２に対して８ビットデータを順次入力し、１６サイクルで図４に示す１６個のＳ−ｂｏｘによる非線形変換処理を実行する。
【００６１】
Ｓ−ｂｏｘ２５２の出力は行列演算回路２５３に入力され、行列演算回路２５３において行列を適用した線形変換処理が実行される。なお、図４の構成ではＳ−ｂｏｘによる処理データをＳｈｉｆｔ−Ｌｏｗ実行部で置換した後、行列演算を行う構成となっているが、図５に示す例では、Ｓ−ｂｏｘ２５２の出力を行列演算回路２５３に直接入力する構成としている。図５の構成では、Ｓｈｉｆｔ−Ｌｏｗ実行部での置換処理に相当する処理は図５に示すレジスタ群ｒ０１〜ｒ１９内のマルチプレクサｍ０１〜ｍ０８の動作によって実行する。
【００６２】
図５に示す行列演算回路２５３では、図４に示す線形変換部２０３の４つの行列演算回路の処理が順次実行される。図４に示す線形変換部２０３の４つの行列演算回路の１つの行列演算回路で実行する行列を適用した線形変換処理を４サイクルで実行する。この処理については後段で詳細に説明する。
【００６３】
図４に示す排他的論理和演算部２０３の排他的論理和演算処理は、図５の排他的論理和演算部２５４ａ，２５４ｂにおいて実行される。これら排他的論理和演算部２５４ａ，２５４ｂにおいて、処理データと、鍵生成部２５１の出力するラウンド鍵との排他的論理和演算処理を実行する。
【００６４】
図４に示すＳｈｉｆｔ  Ｌｏｗ実行部２０２のデータ置換処理は、前述したように図５に示すレジスタ群ｒ０１〜ｒ１９内のマルチプレクサｍ０１〜ｍ０８の動作によって実行されることになる。
【００６５】
図５に示すＨａｍａｌａｉｎｅｎらの提案したＳＰＮ構造によるＡＥＳアルゴリズムの実行構成では、Ｓ−ｂｏｘを１つのみとしている。
レジスタ数は、図５に示すように１５２ビット分のレジスタ（８ビットレジスタ×１９）となっている。なお、鍵生成部２５１にも１２８ビット鍵データを保持する１２８ビットレジスタが必要となる。
【００６６】
図５に示すＨａｍａｌａｉｎｅｎらの提案したＳＰＮ構造を適用したＡＥＳアルゴリズムの実行構成は、Ｓ−ｂｏｘ数を１つのみとし、また必要なレジスタ数も最小限の設定とした小型実装を実現している。
【００６７】
［３．ＳＰＮの小型実装構成における行列演算回路の構成と処理の詳細について］
次に、図５を参照して説明したＳＰＮの小型実装構成における行列演算回路の構成と処理の詳細について説明する。
【００６８】
図５を参照して説明したＨａｍａｌａｉｎｅｎらの提案したＳＰＮ構造によるＡＥＳアルゴリズムの実行構成中、行列演算回路２５３の実行する行列を適用した線形変換処理について説明する。
説明の簡単化のため、図６のように、Ｓｈｉｆｔ  Ｌｏｗ実行部によるデータ置換を行なう回路や、鍵スケジュール部については省略したデータパスを用いて説明する。
【００６９】
図６中のレジスタ群２６１は、図５中の１２個のレジスタｒ０４〜ｒ１５とマルチプレクサｍ０５〜ｍ０８を含む回路に相当し、９６−ｂｉｔ分のデータを保持し、Ｓｈｉｆｔ  Ｌｏｗも考慮されたレジスタの集合を表す。
【００７０】
図７を用いて行列を適用した線形変換処理を実行する行列演算回路２５３の動作について説明する。今、下記の演算を図７に示す行列演算回路２５３を用いて実行するとする。なお、下記の演算は全て、ある有限体ＧＦ（２８）上で行われるものとする。
【００７１】
【数１】
0005605197.tif 000002
【００７２】
なお、式１に示す（ｘ０、ｘ１、ｘ２、ｘ３）は、行列演算回路２５３に対する入力（Ｓ−ｂｏｘからの出力）、
（ｙ０、ｙ１、ｙ２、ｙ３）は、行列演算回路２５３の出力（線形変換結果）、
４×４の行列は、行列演算回路２５３において適用する行列（線形変換行列）に対応する。
なお、４×４の線形変換行列の要素は１６進数値として示している。
本例では、（ｘ０、ｘ１、ｘ２、ｘ３）の各々は、Ｓ−ｂｏｘ２５２からの１サイクルあたりの出力であり８ビットデータである。出力（ｙ０、ｙ１、ｙ２、ｙ３）の各々も８ビットデータである。
【００７３】
なお、図７の行列演算回路２５３では、図４に示す４つの行列演算部からなる線形変換部２０３の処理を行う。図４に示す４つの行列演算部の各々は、４つのＳ−ｂｏｘにおいてそれぞれ非線形変換されたデータの出力（８ビット出力）を入力して線形変換を実行する。しかし、図５、図７に示す構成では、Ｓ−ｂｏｘが１つのＳ−ｂｏｘ２５２のみに削減され、１サイクルで図４に示す１６個のＳ−ｂｏｘ中の１つ分のＳ−ｂｏｘの出力のみが行われる。
【００７４】
従って、図７の行列演算回路２５３では、１つのＳ−ｂｏｘ２５２から４サイクルかけて必要となる図４に示す４つのＳ−ｂｏｘからの出力（ｘ０、ｘ１、ｘ２、ｘ３）を入力することになる。
例えば図７の行列演算回路２５３において、図４に示す行列演算回路２０３ａの行列演算処理を実行する場合、図４に示す行列演算回路２０３ａに対するＳ−ｂｏｘ出力（１）〜（４）が図７に示す行列演算回路２５３に順次Ｓ−ｂｏｘ２５２から４サイクルかけて入力されることになる。
【００７５】
図７に示す行列演算回路２５３に対するＳ−ｂｏｘ２５２からの入力は、
第１サイクルにおいてデータｘ０、
第２サイクルにおいてデータｘ１、
第３サイクルにおいてデータｘ２、
第４サイクルにおいてデータｘ３、
これらのデータであり、このデータを用いて行列を適用した線形変換結果としての（ｙ０，ｙ１，ｙ２，ｙ３）を出力する。
【００７６】
このデータ変換を、行列を用いて行うのが図７に示す行列演算回路２５３であり、この変換処理を式で表現したのが前記の（式１）である。
前述したように、Ｓ−ｂｏｘ２５２の各サイクルにおける出力ｘ０、ｘ１、ｘ２、ｘ３、の各々はそれぞれ８ビットデータであり、行列演算回路２５３における行列を適用した線形変換結果としてのｙ０，ｙ１，ｙ２，ｙ３の各々もそれぞれ８ビットデータである。
以下、各サイクルにおける処理について説明する。
【００７７】
図７に示す行列演算回路２５３は、１サイクル（１ｃｙｃｌｅ）目に入力データ（ｄｉｎ）としてｘ０を入力する。この時点で、論理積回路２７１〜２７４に入力されているイネーブル信号（ｅｎ）を０にしておく。なお、図５〜図７には示されていないが、制御部によって制御がなされる。
【００７８】
図７に示す最上段のラインＬ１では、入力データ（ｄｉｎ）＝ｘ０がそのまま排他論理和部２８１を通過してレジスタｒ１６に格納される。
２番目のラインＬ２でも、入力データ（ｄｉｎ）＝ｘ０がそのまま排他論理和部２８２を通過してレジスタｒ１７に格納される。
【００７９】
３番目のラインＬ３と、４番目のラインＬ４では、入力データ（ｄｉｎ）としてのｘ０と予め規定された値：２、３との有限体上での乗算処理が実行される。すなわち、乗算部２８５，２８６において以下の乗算が実行される。
ｘ０・２、
ｘ０・３、
これらを計算する。
これらの演算結果が、排他論理和部２８３，２８４を通過してレジスタｒ１８，ｒ１９に格納される。
【００８０】
なお、１番目のラインＬ１と、２番目のラインＬ２には乗算部が設定されていないが、入力データ（ｄｉｎ）としてのｘ０と予め規定された値：１との有限体上での乗算処理が実行されていると同等である。
【００８１】
２、３、４ｃｙｃｌｅ目には、入力データ（ｄｉｎ）としてｘ１、ｘ２、ｘ３をそれぞれ入力する。この２、３、４ｃｙｃｌｅ目は、１ｃｙｃｌｅ目とは異なり、論理積回路２７１〜２７４に入力されているイネーブル信号（ｅｎ）を１にする。
この設定により、排他論理和部２８１〜２８４では、入力データまたはその乗算値と論理積回路２７１〜２７４からの出力との排他的論理和演算が実行され、その結果がレジスタｒ１６〜ｒ１９に格納されることになる。
【００８２】
このような処理によって、４ｃｙｃｌｅ後のレジスタｒ１６〜ｒ１９には、前記式（式１）に従って算出される結果が格納される。すなわち、
（ｄｏｕｔ０，ｄｏｕｔ１，ｄｏｕｔ２，ｄｏｕｔ３）
＝（ｙ０，ｙ１，ｙ２，ｙ３）
となる。
このように、図７に示す行列演算回路２５３により、４サイクルの処理で上記（式１）に従った行列演算が実行されることになる。
【００８３】
なお、図７を参照して説明した処理は、ＡＥＳで採用されている巡回行列による行列演算による線形変換処理を実現する回路であるが、他の異なる行列を適用した線形変換処理も、回路の乗算部の設定と、接続構成等を変更することで実現できる。例えば、下記のようなアダマール行列を適用した行列演算を実現する回路は図８に示す行列演算回路２９０によって実現可能である。
【００８４】
【数２】
0005605197.tif 000003
【００８５】
なお、式２に示す（ｘ０、ｘ１、ｘ２、ｘ３）は、図８に示す行列演算回路２９０に対する入力（Ｓ−ｂｏｘからの出力）
（ｙ０、ｙ１、ｙ２、ｙ３）は、行列演算回路２９０の出力（線形変換結果）
４×４の行列は、行列演算回路２９０において適用する行列（線形変換行列）に対応する。
なお、４×４の線形変換行列の要素は１６進数値として示している。
【００８６】
図８に示すアダマール行列を適用した行列演算を実現する行列演算回路２９０と、図７に示す巡回行列を実現する行列演算回路２５３との異なる点は、例えば以下の構成である。
乗算部２９１〜２９４が式２に示す４×４のアダマール行列からなる線形変換行列の要素に対応した設定となっている。
論理積回路を、マルチプレクサ（Ｍｕｌｔｉｐｌｅｘｅｒ）２９５〜２９８に変更して、各レジスタｒ１６〜ｒ１９への入力を、２つの他レジスタからの出力か０、これら３つの内から１つ選択する設定としている。
これらの構成が変更点である。
【００８７】
図４〜図８を参照して説明したＨａｍａｌａｉｎｅｎらの提案したＳＰＮ構造を用いたＡＥＳ暗号構成の小型実装構成は、Ｓ−ｂｏｘを１つのみに削減し、レジスタ数を最小限の設定とした構成を実現している。
【００８８】
１ラウンドのラウンド演算に適用する必要なレジスタは、単純計算を行うと以下の通りとなる。ただしラウンド演算における処理データサイズとしてのブロックサイズｎは、ｎ＝１２８ビットとする。
（１）ラウンド鍵格納用の１２８ビットレジスタ
（２）処理データ格納用の１２８ビットレジスタ
（３）線形変換行列を適用した行列演算において演算途中結果を格納するための３２ビットレジスタ
データ演算部には、（２），（３）のレジスタが必要となり、１２８＋３２＝１６０ビットレジスタが必要となると計算される。
【００８９】
しかし、図５に示すＨａｍａｌａｉｎｅｎらの提案した構成では、１６０ビットより８ビット少ない１５２ビットレジスタ（＝８ビットレジスタ×１９）とすることに成功している。
Ｈａｍａｌａｉｎｅｎらの提案した構成は、Ｓ−ｂｏｘから行列演算回路へ入力が済んだ値（８ビット）が次のラウンドでは不要となる。このことに着目し、行列演算回路へＳ−ｂｏｘから入力する３２−ｂｉｔのうち、はじめに入力する８−ｂｉｔ分のレジスタを行列演算回路内のレジスタと共有する構成とすることで、８−ｂｉｔ分のレジスタを削減したものである。
【００９０】
［４．ＳＰＮ構造の小型実装構成の一般化Ｆｅｉｓｅｌ構造への適用と問題点について］
上述したように、ＨａｍａｌａｉｎｅｎらはＳＰＮ構造の小型化を実現している。しかし、この小型化構成はＳＰＮ構造に対応した特有の構成であり、この小型実装構成を一般化Ｆｅｉｓｅｌ構造へ適用しても十分な小型化の効果は得られない。以下、この問題点について説明する。なお、以下の説明では、一般化Ｆｅｉｓｅｌ構造はＦｅｉｓｅｌ構造を含む概念であるものとして説明する。
【００９１】
図５を参照して説明したＨａｍａｌａｉｎｅｎらの提案構成を一般化Ｆｅｉｓｔｅｌ構造を持つＣＬＥＦＩＡ等のアルゴリズムを実行する構成に単純に適用すると、行列演算のために、行列の出力ビット長分のデータを格納するレジスタが必要になる。これは、一般化Ｆｅｉｓｔｅｌ構造がＳＰＮ構造とは異なり、例えばラウンド関数内のＦ関数に入力した値を、次のラウンドでも利用する必要があるという処理シーケンスの根本的な違いに起因するものである。
【００９２】
また、ＳＰＮ構造では存在しなかったが、一般化Ｆｅｉｓｔｅｌ構造では、ラウンド関数内において、Ｆ関数演算後に他のラインと排他的論理和を行う必要がある。そのため、排他的論理和を行うための回路も、一般化Ｆｅｉｓｔｅｌ構造のラインのビット長分だけ必要となる。
【００９３】
図９は、Ｈａｍａｌａｉｎｅｎらの実装法を４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造に適用した場合のデータ演算部回路の概要図を示す図である。図９では、先に図６を参照して説明したＡＥＳのデータパスと同様、一般化Ｆｅｉｓｔｅｌ構造のラウンド関数終了時の置換動作や鍵スケジュール部は省略してある。
【００９４】
なお、ラウンド演算における処理データサイズとしてのブロックサイズはｎビットとする。先に図３を参照して説明したように、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造では、４つのライン各々にｎ／４ビットずつ入力され、順次転送される。
【００９５】
図９中のレジスタ群３０１は、図６に示すレジスタ群２６１に対応する。ただし、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造に対応する図９のレジスタ群３０１は、（３／４）ｎ−ｂｉｔ分のデータを保持するレジスタとラウンド関数終了時の置換動作と同様の処理を実現するマルチプレクサ等の組み合わせとして構成される。すなわち、レジスタ群３０１の下側のデータ演算部に１ライン分の（１／４）ｎビット分のデータが保持されるとすると、図９のレジスタ群３０１には、（３／４）ｎ−ｂｉｔ分のデータを保持するレジスタが必要となる。
【００９６】
なお、図９に示す４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムのデータパス（演算実行回路）を適用して実行する演算は、図３に示す４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造を適用した演算処理に対応する。
【００９７】
この図９に示すデータパスを利用して図３に示す４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造内のＦ関数を含むラウンド関数を実行することになる。
ラウンド関数内のＦ関数の具体例を図１０に示す。
【００９８】
図１０に示すＦ関数は、先に図２を参照して説明したＦｅｉｓｔｅｌ構造のＦ関数と同様、以下の構成要素を持つ。
（ａ）ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部３２１、
（ｂ）排他的論理和演算部３２１の出力に対して非線形変換処理を実行するＳ−ｂｏｘからなる非線形変換部［Ｓ］３２２、
（ｃ）非線形変換部［Ｓ］３２２の出力に対して、行列演算により線形変換の処理を行なう線形変換部［Ｍ］３２３、
これらの構成要素を持つ。
ただし、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造におけるＦ関数に対する入出力は、ｎ／４ビットとなる。
【００９９】
なお、線形変換部［Ｍ］３２３で実行する行列を適用した行列演算としての線形変換処理に適用する行列は、１行目の要素が（ａ，ｂ，ｃ，ｄ）となる巡回行列を想定している。すなわち、以下の（式３）に示す行列である。
【０１００】
【数３】
0005605197.tif 000004
【０１０１】
先に図４〜図８を参照して説明したＳＰＮ構造を適用したＡＥＳ暗号アルゴリズムの構成と比較するため、処理単位としてのブロック構成ビットｎは、
ｎ＝１２８−ｂｉｔ
とする。
【０１０２】
図９に示す回路も、図６に示す回路と同様、Ｓ−ｂｏｘは１つのみである。図９に示すＳ−ｂｏｘ３０３である。このＳ−ｂｏｘ３０３は図１０に示すＦ関数内に設定される１つのＳ−ｂｏｘの処理を１サイクルで実行する。サイクル毎に、順次、図１０に示す各Ｓ−ｂｏｘの処理を行うことになる。
【０１０３】
図１０に示すように、Ｆ関数の１つのＳ−ｂｏｘには、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造の１つのｌｉｎｅを伝送するｎ／４ビットの１／４、すなわちｎ／１６ビットが入力され非線形変換処理が実行される。
図９に示すＳ−ｂｏｘ３０３には、ｎ／１６ビットずつがサイクル毎に入力され非線形変換処理が実行される。
【０１０４】
なお、図９の構成では、レジスタ群３０１から１サイクル単位でＳ−ｂｏｘ３０３の処理単位であるｎ／１６ビットのデータを出力する設定であり、このｎ／１６ビットをまず、排他的論理和部３０２でラウンド鍵の構成データと排他的論理和を行うＳ−ｂｏｘで非線形変換を実行する構成としている。
【０１０５】
Ｓ−ｂｏｘ３０３において非線形変換のなされたデータは、ｎ／１６ビットごとに１サイクル単位で次の行列演算回路３０４に入力される。行列演算回路３０４では所定の行列を適用した線形変換処理が実行されることになる。
【０１０６】
図９に示す４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムのデータパス構成中、レジスタ群３０１を除く演算実行回路と、先に図６を参照して説明したＳＰＮ構造を利用したＡＥＳ暗号処理を実行する演算回路構成とを比較する。
【０１０７】
図６に示す演算回路では、８ビットレジスタがｒ０１〜ｒ０３、ｒ１６〜ｒ１９の７個であるのに対して、図９に示す演算回路では、８ビットレジスタがＲ０〜Ｒ７の８個である。すなわち、８−ｂｉｔレジスタの数が１つ増えている。
また、排他的論理和演算回路の数も増加している。
【０１０８】
このように、Ｈａｍａｌａｉｎｅｎらの提案構成を一般化Ｆｅｉｓｔｅｌ構造に適用した場合、図９に示す演算回路のように、ブロック長分のレジスタに加え、１−ｌｉｎｅ分のレジスタと排他的論理和演算回路が必要になってくる。
レジスタの増加は回路規模に大きく影響するため、ブロック長分のみのレジスタで構成できる実装法が実現できれば、そのほうが望ましい。
【０１０９】
なお、レジスタのゲートサイズは他のセルに比べて比較的大きなものとなり、レジスタ数の増加はゲートサイズに大きく影響する。そのため、小型化を実現するための一つの方向性として、レジスタの増加を抑えた実装法を考慮することが重要となる。
【０１１０】
［５．一般化Ｆｅｉｓｔｅｌ構造の小型化の実現構成について］
次に、本発明の構成、すなわち、一般化Ｆｅｉｓｔｅｌ構造の小型化の実現構成について説明する。
Ｈａｍａｌａｉｎｅｎらの実装法を、一般化Ｆｅｉｓｔｅｌ構造を持つ暗号アルゴリズムの実行構成に適用した場合には、前節で説明したようにレジスタと排他的論理和の回路が増加してしまい、小型化が実現されない。
【０１１１】
これは、ＳＰＮ構造を適用した暗号アルゴリズムと、一般化Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムが異なること、特に、一般化Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムでは、行列演算結果を求めてから、他のラインとの排他的論理和を行う設定となっていることなどが要因であると考えられる。
すなわち、一般化Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムでは、行列の途中結果を保持するレジスタと他のラインのデータを保持するレジスタの両方が必要となる。
【０１１２】
また、一般化Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムでは、１つのラインのデータに対する行列演算が終了すると、次のサイクル（ｃｙｃｌｅ）で新たなラインの行列の演算が始まる。このため、その１ｃｙｃｌｅの間に他のラインとの排他的論理和を行なう必要がある。そのため、１−ｌｉｎｅ分の排他的論理和の回路が必要となる。
【０１１３】
以下に説明する本発明の構成では、排他的論理和演算における結合法則、すなわち、以下の式が成立することを利用し、演算順序を変更することで必要なレジスタの削減を実現している。
【０１１４】
【数４】
0005605197.tif 000005
【０１１５】
上記式４は、排他的論理和演算の順番を変更しても同じ結果が得られることを意味している。本発明では、この法則を利用して、演算順序を変更することで必要なレジスタの削減を実現している。
【０１１６】
具体的には、他のラインのデータを保持しているレジスタに行列演算の途中結果を排他的論理和していくように演算順序を変更する。このように演算順序を変更することにより、行列演算の途中結果を保持する必要がなくなり、レジスタ数を削減することができる。
【０１１７】
図１１に本発明の一実施例としてのデータパス、すなわち演算回路構成を示す。図１１に示す演算回路は、先に図３を参照して説明した４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造を適用した暗号アルゴリズムの実行回路である。具体的には、巡回行列演算部をアダマール行列演算部に置き換えることで、例えばＣＬＥＦＩＡ暗号の実行回路として利用可能である。
【０１１８】
なお、図１１に示す回路は、図９と同様、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造のラウンド関数終了時の置換動作の実行回路や鍵スケジュール部の構成については省略している。
【０１１９】
図１１中のレジスタ群５０１は、図９に示すレジスタ群３０１に対応する。すなわち、レジスタ群５０１は、データ保持用のレジスタとラウンド関数終了時の置換動作の実行機能を持つ回路によって構成される。
しかし、図１１中のレジスタ群５０１は、図９に示すレジスタ群３０１よりも少ないレジスタ数に設定されている。
【０１２０】
図９に示すレジスタ群３０１は、先に説明したように、（３／４）ｎ−ｂｉｔ分のデータを保持するレジスタとラウンド関数終了時の置換動作の実行機能を持つ回路を含む構成として説明した。
これに対して、図１１に示すレジスタ群５０１に含まれるレジスタは、ｎ／２−ｂｉｔ分のデータを保持するレジスタのみである。
【０１２１】
処理データとしてのブロックのビット数をｎ、すなわち、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造を適用した暗号処理単位としてのブロックのビット数：ｎが、
ｎ＝１２８−ｂｉｔ
とする。
【０１２２】
この設定で、先に説明した図９の構成では、
レジスタ群３０１に、（３／４）ｎ−ｂｉｔ＝９６−ｂｉｔ
レジスタ群３０１以外の演算部に８ビットレジスタが８個の８×８＝６４−ｂｉｔ
総計で、
９６＋６４＝１６０−ｂｉｔ
のレジスタが必要となっている。
【０１２３】
一方、本発明の手法を適用した図１１の構成では、
レジスタ群５０１に、（１／２）ｎ−ｂｉｔ＝６４−ｂｉｔ
レジスタ群５０１以外の演算部に８ビットレジスタが８個の８×８＝６４−ｂｉｔ
総計で、
６４＋６４＝１２８−ｂｉｔ
のレジスタが必要となっている。
【０１２４】
すなわち、ＳＰＮ構造に対応するＨａｍａｌａｉｎｅｎらの実装法を４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造に単純に適用した場合の図９の構成においては１６０−ｂｉｔのレジスタが必要となるのに対して、本発明の構成である図１１に示す４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造を適用した演算回路では、１２８−ｂｉｔのレジスタのみでよく、大幅なレジスタ削減が実現される。
【０１２５】
本発明の構成である図１１に示す４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造を適用した演算回路では、図９の構成に比較して３２ビット分のレジスタを削減している。
以下、詳細に説明するが、図１１に示す本発明の構成では、行列演算回路において、他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）を利用した演算を先行して実行することで、これらの出力データ（Ｅ０、Ｅ１、Ｅ２、Ｅ３）を行列演算期間中、保持するためのレジスタ（８×４＝３２ビット）を削減したことによる。
【０１２６】
以下、このレジスタ削減を実現させる演算シーケンスについて詳細に説明する。
レジスタ削減を実現するため、本発明の処理では、演算シーケンス、特に、線形変換を行う行列演算回路における行列を適用した演算シーケンスの設定を特別な設定とした。以下、図１１に示す本発明に従ったデータパスである回路構成を適用した演算シーケンスの詳細について説明する。
【０１２７】
図１２および以下に示す表１に図９に示すデータパスに従った行列演算回路３０４における行列演算シーケンスを示す。
さらに、図１３および以下に示す表２に図１１に示すデータパスに従った行列演算回路５０４における行列演算シーケンスを示す。
【０１２８】
【表１】
0005605197.tif 000006
（表１）
【０１２９】
【表２】
0005605197.tif 000007
（表２）
【０１３０】
図９に示す構成における行列演算シーケンスを示す表１（図１２）と、
図１１に示す構成における行列演算シーケンスを示す表２（図１３）を用いて各処理の差異について説明する。
【０１３１】
まず、図９と図１２（表１）を参照して、ＳＰＮ構造に対応するＨａｍａｌａｉｎｅｎらの実装法を４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造に単純適用した場合の行列演算シーケンスについて説明する。
【０１３２】
図９に示すデータパスの行列演算回路３０４に対して、Ｓ−ｂｏｘ３０３からの出力として、順次、データ（ｘ０，ｘ１，ｘ２，ｘ３）が入力されて行列を適用した線形変換処理を行うものとする。
【０１３３】
行列演算回路３０４は、行列を適用した行列演算によって生成した出力（ｙ０，ｙ１，ｙ２，ｙ３）を排他的論理和演算部３０５に出力する。
排他的論理和演算部３０５では、行列演算回路３０４の出力（ｙ０，ｙ１，ｙ２，ｙ３）と、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造における他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）と排他的論理和される。他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）は、例えば前ラウンドにおけるラウンド演算の処理結果に相当する。
【０１３４】
なお、行列演算回路３０４に対する入力（ｘ０，ｘ１，ｘ２，ｘ３）の各々はｎ／１６ビットであり、出力（ｙ０，ｙ１，ｙ２，ｙ３）と、他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）の各々もすべてｎ／１６ビットのデータである。
【０１３５】
このとき、図９に記載のレジスタＲ０，Ｒ１，・・・，Ｒ７の格納値は、上記および図１２の表１のように変化する。
【０１３６】
１サイクル（１ｃｙｃｌｅ）目で、レジスタＲ０、Ｒ１、Ｒ２、Ｒ３に、行列演算回路３０４に対する入力要素ｘ０に基づく行列演算結果の各要素が格納される。この時点で、論理積回路３１３に入力されているイネーブル信号（ｅｎ）は０に設定され、入力要素ｘ０に基づく乗算部３１１の乗算結果がレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納される。すなわち、
レジスタＲ０の格納値：ｄ・ｘ０、
レジスタＲ１の格納値：ｃ・ｘ０、
レジスタＲ２の格納値：ｂ・ｘ０、
レジスタＲ３の格納値：ａ・ｘ０、
これらのデータが各レジスタに格納される。
【０１３７】
その後、２サイクル目に行列演算回路３０４に入力要素ｘ１が入力される。２〜４サイクル目では、論理積回路３１３に入力されるイネーブル信号（ｅｎ）は１に設定され、排他論理和演算部３１２において、入力要素ｘ１の乗算部３１１の乗算結果と、前サイクルでレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納された値との排他的論理和演算が実行され、その結果がレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納される。
また、この２サイクル目において、他ラインからの出力要素Ｅ０がレジスタＲ７に格納される。
【０１３８】
３サイクル目に行列演算回路３０４に入力要素ｘ２が入力される。２〜４サイクル目では、論理積回路３１３に入力されるイネーブル信号（ｅｎ）は１に設定され、排他論理和演算部３１２において、入力要素ｘ２の乗算部３１１の乗算結果と、前サイクルでレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納された値との排他的論理和演算が実行され、その結果がレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納される。
また、この３サイクル目において、他ラインからの出力要素Ｅ０がレジスタＲ６に格納され、Ｅ１がレジスタＲ７に格納される。
【０１３９】
４サイクル目では、行列演算回路３０４に入力要素ｘ３が入力される。入力データ（ｘ０，ｘ１，ｘ２，ｘ３）の入力が完了し、この４サイクル目において、行列演算結果（ｙ０，ｙ１，ｙ２，ｙ３）がレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納される。
【０１４０】
その次の５サイクル目では、他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）と、行列演算回路３０４における行列を適用した行列演算結果（＝線形変換結果）である（ｙ０，ｙ１，ｙ２，ｙ３）とが、排他的論理和演算部３０５において排他的論理和されて、その結果としての値が、レジスタＲ４、Ｒ５、Ｒ６、Ｒ７に格納される。
このレジスタ格納値、すなわち、下記式（式５）に示すデータが図９に示すライン３０６を介して次のラウンド演算の利用データとしてレジスタ群３０１に入力される。
【０１４１】
【数５】
0005605197.tif 000008
【０１４２】
なお、上記（式５）に示す値は、図３に示すラウンド間の接続部のラウンド出力データ（Ｄ）に相当する。
また、この５サイクル目では、次の行列演算回路３０４への入力値（ｘ'０，ｘ'１、ｘ'２，ｘ'３）の始めの要素ｘ'０に対する演算がレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納される。
【０１４３】
次に、図１１に示す本発明に従ったデータパスを利用した行列演算回路５０４における行列演算のサイクル単位の遷移処理について、図１１と図１３（表２）を参照して説明する。
【０１４４】
図１１に示すデータパスの行列演算回路５０４に対して、図９を参照して説明したと同様のＳ−ｂｏｘ５０３からの出力として、順次、（ｘ０，ｘ１，ｘ２，ｘ３）が入力され、行列を適用した線形変換処理を行うものとする。
【０１４５】
この図１１に示す構成を用いた行列演算を行うと、図１３（表２）に示すように、４サイクル目においてレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に、次のラウンド演算の利用データ、すなわち、
【０１４６】
【数６】
0005605197.tif 000009
【０１４７】
なお、上記（式６）に示す値が格納される。これらの値は、第５サイクルでレジスタＲ４、Ｒ５、Ｒ６、Ｒ７に格納され、図１１に示すライン５０６を介して次のラウンド演算の利用データとしてレジスタ５０１に入力される。
図１１に示す構成は、図９に示す構成よりレジスタ数が削減された構成であるが、結果としては図９に示すと同様の演算処理を実現している。ただし、演算シーケンスが異なっている。
各サイクルにおける処理について説明する。
【０１４８】
図１１に示すデータパスを利用した処理では、例えば前ラウンドにおけるラウンド演算の処理結果に相当する他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）を、レジスタ５０１からの出力ライン５２１を介してレジスタＲ７、Ｒ６、Ｒ５に、順次格納する。図１３（表２）に示す１サイクル目の１つ前のサイクル（０サイクル）において、
レジスタＲ５にはＥ０、
レジスタＲ６にはＥ１、
レジスタＲ７にはＥ２、
これらのデータが格納された状態に設定される。
【０１４９】
１サイクル目において、これらのレジスタ格納値Ｅ０、Ｅ１、Ｅ２と、レジスタ群５０１から出力ライン５２１を介した新たな出力値Ｅ３を加えた出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）がマルチプレクサ５１３を介して、排他的論理和演算部５１２に入力される。なお、これらの演算制御は、例えば図示しない制御部やクロック入力情報に基づく制御によって行われる。
【０１５０】
排他的論理和演算部５１２では、これらの出力値（Ｅ０、Ｅ１、Ｅ２、Ｅ３）と、入力要素ｘ０に基づく乗算部３１１の乗算結果、すなわち、
ｄ・ｘ０、
ｃ・ｘ０、
ｂ・ｘ０、
ａ・ｘ０、
これらの各値との排他的論理和演算が実行される。この排他的論理和演算結果が、レジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納される。
【０１５１】
すなわち、
レジスタＲ０には、レジスタＲ６に格納された値Ｅ１が、マルチプレクサｍ０を介して排他論理和演算部５１２に入力されて、ｄ・ｘ０との排他論理和結果が格納される。
レジスタＲ１には、レジスタＲ７に格納された値Ｅ２が、マルチプレクサｍ１を介して排他論理和演算部５１２に入力されて、ｃ・ｘ０との排他論理和結果が格納される。
レジスタＲ２には、レジスタ群からライン５２１を介して出力される出力値Ｅ３が、マルチプレクサｍ２を介して排他論理和演算部５１２に入力されて、ｂ・ｘ０との排他論理和結果が格納される。
レジスタＲ３には、レジスタＲ５に格納された値Ｅ０が、マルチプレクサｍ３を介して排他論理和演算部５１２に入力されて、ａ・ｘ０との排他論理和結果が格納される。
すなわち、以下の（式７）に示す各値がレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納される。
【０１５２】
【数７】
0005605197.tif 000010
【０１５３】
なお、マルチプレクサ５１３（ｍ０〜ｍ３）は、２入力から選択された１つの入力を出力するセレクタと同様の処理を行う。
第１サイクルでは、レジスタＲ７、Ｒ６、Ｒ５の格納値、ライン５２１の出力値を出力するように設定される。なお、これらの制御は図示しない制御部の制御によって行われる。
【０１５４】
このように、本発明の構成では、図１１に示す行列演算回路５０４に対するＳ−ｂｏｘ５０３からの第１サイクルにおける入力ｘ０の入力タイミングにおいて、例えば前ラウンドにおけるラウンド演算の処理結果に相当する他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）との排他的論理和演算を実行し、その結果をレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納する。
【０１５５】
このように本発明の構成では、他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）との排他論理和演算処理を先行して実行する。この結果、４サイクルを要する行列演算期間が完了するまで他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）を保持する必要がなくなる。この演算シーケンスの変更処理によって必要なレジスタ数の削減を実現している。
【０１５６】
その後、２サイクル目に行列演算回路５０４に入力要素ｘ１が入力される。２〜４サイクル目では、マルチプレクサ５１３（ｍ０〜ｍ３）は、レジスタＲ０、Ｒ１、Ｒ２、Ｒ３の格納値を選択出力するように制御される。
この結果、排他論理和演算部５１２において、入力要素ｘ１の乗算部５１１の乗算結果と、前サイクルでレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納された値との排他的論理和演算が実行され、その結果がレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納される。
また、この２サイクル目において、他ラインからの出力要素Ｅ'０がレジスタＲ７に格納される。
【０１５７】
３サイクル目に行列演算回路５０４に入力要素ｘ２が入力される。排他論理和演算部５１２において、入力要素ｘ２の乗算部５１１の乗算結果と、前サイクルでレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納された値との排他的論理和演算が実行され、その結果がレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納される。
また、この３サイクル目において、他ラインからの出力要素Ｅ'０がレジスタＲ６に格納され、Ｅ'１がレジスタＲ７に格納される。
【０１５８】
４サイクル目では、行列演算回路５０４に入力要素ｘ３が入力される。入力データ（ｘ０，ｘ１，ｘ２，ｘ３）の入力が完了し、この４サイクル目において、レジスタＲ０、Ｒ１、Ｒ２、Ｒ３には、行列演算結果（ｙ０，ｙ１，ｙ２，ｙ３）と他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）との排他論理和結果が格納されることになる。
【０１５９】
その次の５サイクル目では、次の他ラインからの出力（Ｅ'０、Ｅ'１、Ｅ'２、Ｅ'３）がレジスタＲ７、Ｒ６、Ｒ５の格納値、ライン５２１の出力として、排他論理和演算部５１２に入力される。
排他論理和演算部５１２は、これらの入力値と、行列演算回路５０４に対する新たな入力ｘ'０と乗算部５１１での乗算結果との排他論理和結果を算出して、レジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納する。
この時点で、レジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納された値は、レジスタＲ４、Ｒ５、Ｒ６、Ｒ７に格納される。
このレジスタ格納値、すなわち、下記式（式８）に示すデータが図１０に示すライン５０６を介して次のラウンド演算の利用データとしてレジスタ群５０１に入力される。
【０１６０】
【数８】
0005605197.tif 000011
【０１６１】
このように、本発明に従った構成では、行列の演算処理に際して他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）との排他的論理和演算を先行して実行することにより、他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）を格納するレジスタと、行列演算の途中結果を格納するレジスタを、個別に設定した独立のレジスタとする必要性をなくして、これらのレジスタの共有化を行うことで、必要な総レジスタ数を削減している。
【０１６２】
［６．本発明の構成による効果および変形例について］
図１１に示す本発明に従った一般化Ｆｅｉｓｔｅｌ構造を適用した暗号処理を実行するデータパスでは、上述したように、先行した処理結果をラウンド演算における行列演算の最初のサイクル（１サイクル目）で排他論理和演算処理を実行してしまう構成としている。
【０１６３】
すなわち、例えば前ラウンドにおけるラウンド演算の処理結果に相当する他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）との排他的論理和演算を先行して実行する。
図１１を参照して説明したように、行列演算回路５０４における行列演算の最初の処理として実行する第１サイクルにおいて、他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）をレジスタ等からマルチプレクサ５１３を介して排他論理和演算部５１２に先行して入力させて、行列演算回路５０４に対する最初の入力値（ｘ０）の乗算部５１１での乗算結果（ｄ・ｘ０等）と排他論理和処理を実行する。
【０１６４】
このように、本発明の構成では、１−ｌｉｎｅ分（実施例では（ｎ／１６）×４）のマルチプレクサ（Ｍｕｌｔｉｐｌｅｘｅｒ）を導入することで、図９に示す構成において必要であった１−ｌｉｎｅ分のレジスタと１−ｌｉｎｅ分の排他的論理和と１−ｌｉｎｅ分の論理積の回路をなくすことができる。図１１に示す構成では、これらの差分だけ、小型化を行うことができる。
また、この小型化に伴い、低消費電力化も期待できる。
特に、レジスタのゲートサイズは、他のセルに比べて比較的大きなものとなるため、１−ｌｉｎｅ分のレジスタを削減できたことは小型化に特に寄与する。
【０１６５】
なお、上述した実施例では、本発明の適用構成の代表例として、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造への適用例について説明した。しかしながら、図１１、図１３（表１）を参照して説明した処理シーケンス、すなわち、他ラインからの出力値を先行して行列演算に適用することは、４−ｌｉｎｅ以外の一般化Ｆｅｉｓｔｅｌ構造やＦｅｉｓｔｅｌ構造においても適用可能であり、図１１を参照して説明したと同様のレジスタ他の回路構成の削減が実現される。すなわち、本発明は、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造のみでなく、ラウンド関数内部を変形、拡張された構造についても適用可能であり、２−ｌｉｎｅのＦｅｉｓｔｅｌ構造や、任意のｘ（ｘは２以上の自然数）の、ｘ−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造にも適用できる。
【０１６６】
また、上述した実施例では、行列演算回路において適用する行列を巡回行列とした例について説明したが、行列演算回路において適用する行列は巡回行列に限らず、例えばアダマール行列など、その他の形式の行列を適用することも可能である。
【０１６７】
さらに、行列演算回路において適用する行列は、４×４行列のみでなく、
任意のｘ×ｘ行列、ただし、ｘは２以上の自然数、
このような様々な行列の適用が可能である。
【０１６８】
また、先に図２を参照して説明したＦ関数を持つ構成に限らず、行列演算後に非線形変換を含まないラウンド関数を実行するアルゴリズムであれば、本発明の構成は適用可能であり、同様の小型化の効果が期待できる。
【０１６９】
なお、上述した実施例で説明した構成は、４−ｌｉｎｅ一般化Ｆｅｉｓｔｅｌ構造におけるｔｙｐｅ−２一般化Ｆｅｉｓｔｅｌ構造の例であるが、本発明は、この他のｔｙｐｅ−１や、ｔｙｐｅ−３の一般化Ｆｅｉｓｔｅｌ構造に対しても適用可能であり、同様の効果が期待できる。
【０１７０】
２ラインのＦｅｉｓｔｅｌ構造に対して本発明を適用したデータパスとしての回路構成例を図１４に示す。
図１４に示すデータパスにおいて、例えば前ラウンドの演算結果としての他ラインからの出力（Ｅ０、Ｅ１、Ｅ２、Ｅ３）をレジスタＲ４、Ｒ５、Ｒ６、Ｒ７に格納し、行列第１演算回路６０４における行列演算の最初の処理らサイクル（１サイクル目）においてＳ−ｂｏｘ６０３からの入力値ｘ０と乗算部６１１における乗算結果との排他論理和を実行してその結果をレジスタＲ０、Ｒ１、Ｒ２、Ｒ３に格納する。
このように、先に図１１を参照して説明したと同様の処理シーケンスで行列演算を実行することが可能であり、この処理により、レジスタ数の削減などによりハードウェア構成を小型化することが可能となる。
【０１７１】
具体的には、図１４の構成とすることで、例えば図９と同様の構成に従って２ラインのＦｅｉｓｔｅｌ構造のデータパスを設定した場合にｎ／２−ｂｉｔ分必要であった行列演算用のレジスタが不要となり、ｎ−ｂｉｔ分のレジスタのみで全体を構成できる。
【０１７２】
なお、図１４に示す２ラインのＦｅｉｓｔｅｌ構造とした場合でも、行列演算回路６０４において適用する行列は巡回行列、アダマール行列等が利用可能であり、またｘ×ｘ（ただしｘ≧２の整数）の任意の行列が利用できる。また、図２を参照して説明したＦ関数を持つ構成に限らず、行列演算後に非線形変換を実行しないラウンド関数であれば、本発明の適用が可能である。
【０１７３】
［７．暗号処理装置のＩＣカードとしての構成例について］
最後に、上述した実施例に従った暗号処理を実行する暗号処理装置としてのＩＣモジュール７００の構成例を図１５に示す。上述の処理は、例えばＰＣ、ＩＣカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図１５に示すＩＣモジュール７００は、これら様々な機器に構成することが可能である。
【０１７４】
図１５に示すＣＰＵ(Central processing Unit)７０１は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ７０２は、ＣＰＵ７０１が実行するプログラム、あるいは演算パラメータなどの固定データを格納するＲＯＭ（Read-Only-Memory）、ＣＰＵ７０１の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるＲＡＭ（Random Access Memory）等からなる。また、メモリ７０２は暗号処理に必要な鍵データや、暗号処理において適用する変換テーブル（置換表）や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【０１７５】
暗号処理部７０３は、例えば図１１や図１４を参照して説明した暗号処理構成、すなわち、例えば一般化Ｆｅｉｓｔｅｌ構造や、Ｆｅｉｓｔｅｌ構造を適用した共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理を実行する。
【０１７６】
なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをＲＯＭに格納し、ＣＰＵ７０１がＲＯＭ格納プログラムを読み出して実行するように構成してもよい。
【０１７７】
乱数発生器７０４は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【０１７８】
送受信部７０５は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ＩＣモジュールとのデータ通信を実行し、ＩＣモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【０１７９】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【０１８０】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【０１８１】
例えば、プログラムは記録媒体としてのハードディスクやＲＯＭ（Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納（記録）しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【０１８２】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【０１８３】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【０１８４】
上述したように、本発明の一実施例の構成によれば、一般化Ｆｅｉｓｔｅｌ構造を適用した暗号処理構成の小型化や省電力化が実現される。
具体的には、データを複数ラインに分割入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する一般化Ｆｅｉｓｔｅｌ構造を適用した暗号処理構成において、第１ラインのデータに対する行列を適用した線形変換処理を実行する行列演算実行部が行列演算の実行サイクル中、最初のサイクルにおいて行列演算過程データと第２ラインのデータとの演算を実行する。本構成により、第２ラインのデータ保持用のレジスタと第１ラインの行列演算途中結果保持用のレジスタの共有化が可能となり、総レジスタ数の削減、小型化が実現される。さらに回路構成の小型化、エレメント数の削減により電力消費量の削減も可能となる。
【符号の説明】
【０１８５】
１１１  鍵スケジュール部
１１２  データ暗号化部
１２０  Ｆ関数
１２１  排他的論理和演算部
１２２  非線形変換部
１２３  線形変換部
２０１  非線形変換部
２０２  Ｓｈｉｆｔ  Ｌｏｗ実行部
２０３  線形変換部
２０４  排他的論理和演算部
２５１  鍵生成部
２５２  Ｓ−ｂｏｘ
２５３  行列演算回路
２５４  排他的論理和演算部
２７１〜２７４  論理積回路
２８１〜２８４  排他的論理和演算部
２８５〜２８６  乗算部
２９０  行列演算回路
２９１〜２９４  乗算部
２９５〜２９８  マルチプレクサ
３０１  レジスタ群
３０２  排他的論理和演算部
３０３  Ｓ−ｂｏｘ
３０４  行列演算回路
３０５  排他的論理和部
３１１  乗算部
３１２  排他的論理和部
３１３  論理積回路
３２１  排他的論理和演算部
３２２  非線形変換部［Ｓ］
３２３  線形変換部［Ｍ］
５０１  レジスタ群
５０２  排他的論理和演算部
５０３  Ｓ−ｂｏｘ
５０４  行列演算回路
５１１  乗算部
５１２  排他的論理和部
５１３  マルチプレクサ
６０３  Ｓ−ｂｏｘ
６０４  行列演算回路
６１１  乗算部
６１３  マルチプレクサ
７００  ＩＣモジュール
７０１  ＣＰＵ(Central processing Unit)
７０２  メモリ
７０３  暗号処理部
７０４  乱数生成部
７０５  送受信部
【図１】
0005605197.tif 000012
【図２】
0005605197.tif 000013
【図３】
0005605197.tif 000014
【図４】
0005605197.tif 000015
【図５】
0005605197.tif 000016
【図６】
0005605197.tif 000017
【図７】
0005605197.tif 000018
【図８】
0005605197.tif 000019
【図９】
0005605197.tif 000020
【図１０】
0005605197.tif 000021
【図１１】
0005605197.tif 000022
【図１２】
0005605197.tif 000023
【図１３】
0005605197.tif 000024
【図１４】
0005605197.tif 000025
【図１５】
0005605197.tif 000026