暗号処理装置、および暗号処理方法、並びにプログラム
【課題】一般化Feistel構造を適用した暗号処理構成の小型化を実現する。
【解決手段】データを複数ラインに分割入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する一般化Feistel構造を適用した暗号処理構成において、第1ラインのデータに対する行列を適用した線形変換処理を実行する行列演算実行部が行列演算の実行サイクル中、最初のサイクルにおいて行列演算過程データと第2ラインのデータとの演算を実行する。本構成により、第2ラインのデータ保持用のレジスタと第1ラインの行列演算途中結果保持用のレジスタの共有化が可能となり、総レジスタ数の削減、小型化が実現された。
【解決手段】データを複数ラインに分割入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する一般化Feistel構造を適用した暗号処理構成において、第1ラインのデータに対する行列を適用した線形変換処理を実行する行列演算実行部が行列演算の実行サイクル中、最初のサイクルにおいて行列演算過程データと第2ラインのデータとの演算を実行する。本構成により、第2ラインのデータ保持用のレジスタと第1ラインの行列演算途中結果保持用のレジスタの共有化が可能となり、総レジスタ数の削減、小型化が実現された。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号処理装置、および暗号処理方法、並びにプログラムに関する。さらに詳細には、Feistel構造や一般化Feistel構造を持つ共通鍵ブロック暗号を実行する暗号処理装置、および暗号処理方法、並びにプログラムに関する。
【背景技術】
【0002】
情報化社会が発展すると共に、扱う情報を安全に守るための情報セキュリティ技術の重要性が増してきている。情報セキュリティ技術の構成要素の一つとして暗号技術があり、現在では様々な製品やシステムで暗号技術が利用されている。
【0003】
暗号処理アルゴリズムには様々なものがあるが、基本的な技術の一つとして、共通鍵ブロック暗号と呼ばれるものがある。共通鍵ブロック暗号では、暗号化用の鍵と復号用の鍵が共通のものとなっている。暗号化処理、復号処理共に、その共通鍵から複数の鍵を生成し、あるブロック単位、例えば64ビット、128ビット、256ビット等のブロックデータ単位でデータ変換処理を繰り返し実行する。
【0004】
代表的な共通鍵ブロック暗号のアルゴリズムとしては、過去の米国標準であるDES(Data Encryption Standard)や現在の米国標準であるAES(Advanced Encryption Standard)が知られている。他にも様々な共通鍵ブロック暗号が現在も提案され続けており、2007年にソニー株式会社が提案したCLEFIAも共通鍵ブロック暗号の一つである。
【0005】
このような、共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を繰り返し実行するラウンド関数実行部を有する暗号処理部と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部とによって構成される。鍵スケジュール部は、秘密鍵であるマスター鍵(主鍵)に基づいて、まずビット数を増加させた拡大鍵を生成し、生成した拡大鍵に基づいて、暗号処理部の各ラウンド関数部で適用するラウンド鍵(副鍵)を生成する。
【0006】
このようなアルゴリズムを実行する具体的な構造として、線形変換部および非線形変換部を有するラウンド関数を繰り返し実行する構造が知られている。例えば代表的な構造にFeistel構造や一般化Feistel構造がある。Feistel構造や一般化Feistel構造は、データ変換関数としてのF関数を含むラウンド関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。F関数においては、線形変換処理および非線形変換処理が実行される。なお、Feistel構造を適用した暗号処理について記載した文献としては、例えば非特許文献1、非特許文献2がある。
【0007】
暗号アルゴリズムの実装形態には、ソフトウェア実装とハードウェア実装の二種類が存在する。ハードウェア実装では、回路規模が小さくなるように実装することで、ハードウェア化の際のコストダウンや低消費電力化が期待できる。そのため、新アルゴリズム、既存アルゴリズムを問わず、小型化するための実装法が様々、提案されている。
【0008】
例えばHamalainen,Alho、Hannikainen、Hamalainenらは、Substitution Permutation Network(SPN)構造を持つAES暗号アルゴリズムに対する小型実装法を提案している。この小型実装法については、非特許文献3[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]に開示されている。
【0009】
しかし、この小型実装法は、SPN構造を利用したAESアルゴリズム固有の処理シーケンスに適応するものであり、SPN構造とは異なる上述のFeistel構造や一般化Feistel構造を持つ暗号アルゴリズムであるDESやCLEFIA暗号アルゴリズムへそのまま適用しても十分な小型化を実現できないという問題がある。
【0010】
なお、上述したAES暗号は、SPN構造を利用した暗号アルゴリズムであり、DES暗号や、CLEFIA暗号はSPN構造とは異なるFeistel構造や一般化Feistel構造を利用した暗号アルゴリズムである。これらの具体的な構造については後段で詳細に説明する。
【先行技術文献】
【非特許文献】
【0011】
【非特許文献1】K. Nyberg, "Generalized Feistel networks", ASIACRYPT'96, SpringerVerlag, 1996, pp.91--104.
【非特許文献2】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
【非特許文献3】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
【発明の概要】
【発明が解決しようとする課題】
【0012】
本発明は、例えば上述の状況に鑑みてなされたものであり、Feistel構造や一般化Feistel構造を利用した暗号処理構成における小型化を実現する暗号処理装置、および暗号処理方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【0013】
本発明の第1の側面は、
データ処理対象となるデータブロックの構成ビットを複数のラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインの第1ラインのデータに対する変換データを生成し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行する演算部と、
前記演算部の演算結果を保持するレジスタを有し、
前記演算部は、前記レジスタから順次、データを取得して取得データ順の演算を実行して演算結果を前記レジスタに格納する構成であり、
前記演算部は、
前記第1ラインのデータに対する行列を適用した線形変換を実行する行列演算実行部を有し、
前記行列演算実行部は、
前記第1ラインのデータに対する行列演算の実行サイクル中、最初のサイクルの行列演算の実行に際して前記第2ラインのデータとの演算を実行する暗号処理装置にある。
【0014】
さらに、本発明の暗号処理装置の一実施態様において、前記行列演算実行部は、前段の非線形変換部から順次出力される複数の単位データに対する行列演算を複数サイクルで実行する構成であり、前記複数サイクルの最初のサイクルで、前記非線形変換部から入力する単位データの行列演算に併せて前記第2ラインのデータとの演算を実行する。
【0015】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理装置は、前記第1ラインのデータに対する行列演算に必要な演算サイクルの完了後に前記第2ラインのデータとの演算を実行する場合に必要となる前記第2ラインのデータ保持用の独立したレジスタを削減し、前記第1ラインのデータに対する行列演算の途中結果の保持用レジスタを前記第2ラインのデータ保持用のレジスタとして利用した構成を有する。
【0016】
さらに、本発明の暗号処理装置の一実施態様において、前記行列演算実行部は、前記第1ラインのデータに対する行列演算を実行する初期サイクルにおいて、前記第1ラインに対する行列演算過程データと前記第2ラインのデータとの排他的論理和演算を実行する。
【0017】
さらに、本発明の暗号処理装置の一実施態様において、前記行列演算実行部は、巡回行列またはアダマール行列を適用した行列演算を実行する構成である。
【0018】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部は、前記ラウンド関数の実行部として、非線形変換処理を実行する非線形変換部と、行列を適用した線形変換処理を実行する線形変換部としての行列演算実行部を有する。
【0019】
さらに、本発明の暗号処理装置の一実施態様において、前記行列演算実行部は、前記非線形変換部としてのS−boxの出力を、順次入力して入力データに対する行列演算を1サイクル処理として実行する。
【0020】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部の実行する暗号処理は、Feistel構造または一般化Feistel構造を適用した暗号処理である。
【0021】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部の実行する暗号処理は、CLEFIA暗号アルゴリズムに従った暗号処理である。
【0022】
さらに、本発明の第2の側面は、
暗号処理装置において暗号処理を実行する暗号処理方法であり、
暗号処理部が、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第1ラインのデータの変換処理を実行し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行し、
前記第1ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第2ラインのデータとの演算を実行する暗号処理方法にある。
【0023】
さらに、本発明の第3の側面は、
暗号処理装置において暗号処理を実行させるプログラムであり、
暗号処理部に、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行させる暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第1ラインのデータの変換処理を実行し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行させ、
前記第1ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第2ラインのデータとの演算を実行させるプログラムにある。
【0024】
なお、本発明のプログラムは、例えば、様々なプログラム・コードを実行可能な情報処理装置やコンピュータ・システムに対して例えば記憶媒体によって提供されるプログラムである。このようなプログラムを情報処理装置やコンピュータ・システム上のプログラム実行部で実行することでプログラムに応じた処理が実現される。
【0025】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【0026】
本発明の一実施例によれば、一般化Feistel構造を適用した暗号処理構成の小型化や省電力化が実現される。
具体的には、データを複数ラインに分割入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する一般化Feistel構造を適用した暗号処理構成において、第1ラインのデータに対する行列を適用した線形変換処理を実行する行列演算実行部が行列演算の実行サイクル中、最初のサイクルにおいて行列演算過程データと第2ラインのデータとの演算を実行する。本構成により、第2ラインのデータ保持用のレジスタと第1ラインの行列演算途中結果保持用のレジスタの共有化が可能となり、総レジスタ数の削減、小型化が実現される。さらに回路構成の小型化、エレメント数の削減により電力消費量の削減も可能となる。
【図面の簡単な説明】
【0027】
【図1】kビットの鍵長に対応したnビット共通鍵ブロック暗号アルゴリズムを説明する図である。
【図2】Feistel構造の全体構造と、1つのF関数の詳細構成例について説明する図である。
【図3】一般化Feistel構造の一例について説明する図である。
【図4】SPN構造を適用したAES暗号アルゴリズムのラウンド関数の構造について説明する図である。
【図5】Hamalainenらの提案したAES暗号を実行するデータ暗号化部のデータパスを示す図である。
【図6】Hamalainenらの提案したAES暗号を実行するデータ暗号化部のデータパスを簡略化して示した図である。
【図7】行列を適用した線形変換処理を実行する行列演算回路253の動作について説明する図である。
【図8】アダマール行列を適用した行列演算を実現する行列演算回路について説明する図である。
【図9】Hamalainenらの実装法を4−line一般化Feistel構造に適用した場合のデータ演算部回路の概要図である。
【図10】F関数の構成例について説明する図である。
【図11】本発明の一実施例としてのデータパス、すなわち演算回路構成を示す図である。
【図12】図9に示すデータパスに従った行列演算回路304における行列演算シーケンスを示す図である。
【図13】図11に示すデータパスに従った行列演算回路504における行列演算シーケンスを示す図である。
【図14】2ラインのFeistel構造に対して本発明を適用したデータパスとしての回路構成例について説明する図である。
【図15】暗号処理装置としてのICモジュール700の構成例を示す図である。
【発明を実施するための形態】
【0028】
以下、図面を参照しながら本発明の暗号処理装置、および暗号処理方法、並びにプログラムの詳細について説明する。説明は、以下の項目に従って行う。
1.共通鍵ブロック暗号の概要
2.SPN構造を適用したAES暗号アルゴリズムにおける小型実装手法の概要について
3.SPNの小型実装構成における行列演算回路の構成と処理の詳細について
4.SPN構造の小型実装構成の一般化Feisel構造への適用と問題点について
5.一般化Feistel構造の小型化の実現構成について
6.本発明の構成による効果および変形例について
7.暗号処理装置のICカードとしての構成例について
【0029】
[1.共通鍵ブロック暗号の概要]
まず、本発明の適用可能な共通鍵ブロック暗号の概要について説明する。本明細書において、共通鍵ブロック暗号(以下ではブロック暗号)は、以下に定義するものを指すものとする。
【0030】
ブロック暗号は平文Pと鍵Kを入力し、暗号文Cを出力する。平文と暗号文のビット長をブロックサイズと呼び、ここではnで示す。nは任意の整数値を取りうるが、通常、ブロック暗号アルゴリズムごとに、予め1つに決められている値である。なお、複数のブロック長に対応するアルゴリズムもある。ブロック長がnのブロック暗号のことをnビットブロック暗号と呼ぶこともある。
【0031】
鍵のビット長はkで表す。鍵は任意の整数値を取りうる。共通鍵ブロック暗号アルゴリズムは1つまたは複数の鍵サイズに対応することになる。例えば、あるブロック暗号アルゴリズムAはブロックサイズn=128であり、ビット長k=128、またはk=192またはk=256の各種の鍵サイズに対応するという構成もありうる。
平文[P]、暗号文[C]、鍵[K]の各ビットサイズは、以下のように示される。
平文P:nビット
暗号文C:nビット
鍵K:kビット
【0032】
図1にkビットの鍵長に対応したnビット共通鍵ブロック暗号アルゴリズムを説明する図を示す。図1に示すように、共通鍵ブロック暗号処理は、nビットの平文Pと、kビットの秘密鍵Kを入力して、予め定められた暗号アルゴリズムを実行して、nビットの暗号文Cを出力する。なお、図1には平文から暗号文を生成する暗号化処理を示しているが、暗号文から平文を生成する復号処理では、鍵の入力順を逆にし、ラウンド関数の逆関数を構成することにより、復号処理がなされる。
【0033】
ブロック暗号は2つの部分に分けて考えることができる。ひとつは鍵Kを入力とし、ある定められたステップにより入力秘密鍵Kのビット長を拡大して拡大鍵K'(ビット長k')を出力する鍵スケジュール部111と、平文Pと鍵スケジュール部111から入力する拡大鍵K'から生成されるラウンド鍵RK等を受け取り、平文Pを入力して、ラウンド鍵RK等を適用した暗号処理を実行して、暗号文Cを生成するためのデータの変換を実行するデータ暗号化部112である。なお、先に説明したように、データ暗号化部112を変更することにより、復号処理を実現できる。
【0034】
このように、共通鍵ブロック暗号のアルゴリズムは、入力データの変換を繰り返し実行するラウンド関数を有するデータ暗号化部112と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部111とによって構成される。鍵スケジュール部111は秘密鍵Kを入力し、各ラウンド関数に入力するラウンド鍵を生成する。例えば、r段のラウンド関数を行なう構成としたブロック暗号においては、1からr段までのラウンド関数にそれぞれRK1、RK2・・・、Rrのラウンド鍵が入力される。また、鍵スケジュール部111は、初期鍵としてIK、最終鍵としてFKをデータ暗号化部112に出力し、これらの鍵と処理データとの排他的論理和がなされる。
【0035】
先に説明したように共通鍵ブロック暗号におけるデータ暗号化部112の代表的な構造としてFeistel構造がある。ブロック長をnビット(n−bit)とした場合の具体的なFeistel構造の構成例を図2に示す。
【0036】
Feistel構造は、データ変換関数としてのF関数を含むラウンド関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。F関数においては、線形変換処理および非線形変換処理が実行される。
図2には右側にFeistel構造の全体構造を示し、左側に1つのF関数120の詳細構成図を示している。
【0037】
図2右側のFeistel構造に示すように、n−bitのデータをn/2−bitずつの2−lineに分割し、そのn/2−bitの片方をラウンド内のF関数に入力し、その出力をもう片方のn/2−bitと排他的論理和していく構成となっている。
各ラウンドにおけるF関数には、鍵スケジュール部111から入力する拡大鍵K'から生成されるラウンド鍵RK1〜RKrが入力される。
【0038】
F関数の構成には様々なタイプのものがあるが、例えば、図2に示すF関数120のように、ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部121、排他的論理和演算部121の出力に対して非線形変換処理を実行するS−boxと呼ばれる非線形変換部[S]122、非線形変換部[S]122の出力に対して、行列演算により線形変換の処理を行なう線形変換部[M]123を有する構成が知られている。
【0039】
なお、図2に示した構造は、Feistel構造の構成例の1つである。この構造の他、例えば初期鍵IKや、最終鍵FKの排他的論理和演算を行う位置を変更した構成など、様々な構成がある。
【0040】
図2に示す構成は、処理対象となるn−bitの入力(例えば平文の構成データ)Pを2つに分割してn/2−bitずつの2−lineとして処理を行う構成であった。このように入力を2分割して処理を行う構成をFeistel構造と呼ぶ。
処理対象データの分割数は2分割に限らず、様々な設定が可能である。分割数を2に限定しないFeistel構造を一般化Feistel構造と呼ぶ。
【0041】
図3を参照して、一般化Feistel構造の一例について説明する。図3に示す構成は、処理対象データを4分割して処理を行う構成例である。
図2を参照して説明したFeistel構造は、処理対象データであるn−bitの平文データを、n/2−bitずつの2−lineに分割し、処理を行なう構成であった。これに対して、図3に示す構成は、処理対象データであるn−bitの平文データを、n/4−bitずつの4−lineに分割して処理を行なう構成を持つ。
【0042】
図3に示す構成は、4−line一般化Feistel構造と呼ばれる。図3に示す4−line一般化Feistel構造も、図2を参照して説明したFeistel構造と同様、F関数を持つラウンド関数を繰り返し実行する構成を持つ。
【0043】
ただし、図3に示すように入力nビットは4分割され、データの流れが複雑になっている。図3に示す構成では、n−bitのデータをn/4−bitずつの4−lineに分割し、そのうちの2−lineをそれぞれF関数に入力し、その出力をその他の2−lineと排他的論理和していく構成となっている。
【0044】
F関数は、例えば図2を参照して説明したF関数120と同様、ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部121、排他的論理和演算部121の出力に対して非線形変換処理を実行するS−boxと呼ばれる非線形変換部[S]122、非線形変換部[S]122の出力に対して、行列演算により線形変換の処理を行なう線形変換部[M]123を有する構成が利用される。
【0045】
図3に示す4−line一般化Feistel構造のように、データ暗号化部における処理ラインを2−lineから4−lineに変更することにより、ラウンド鍵RKi、初期鍵IK、最終鍵FKも、n/2−bitから、n/4−bitのRKi[0]、RKi[1]、IK[0]、IK[1]、FK[0]、FK[1]に分割される。
【0046】
なお、図3は4−line一般化Feistel構造を示しているが、処理データを2−line以上としたFeistel構造については全て一般化Feistel構造と呼ぶ。
【0047】
以下の本発明の説明においては、4−line一般化Feistel構造における本発明の適用例について説明する。ただし、本発明は、4−line一般化Feistel構造のみならず、2ライン(2−line)のFeistel構造、2ライン(2−line)以上の任意の処理ライン数を持つ一般化Feistel構造のいずれにも適用可能である。
【0048】
[2.SPN構造を適用したAES暗号アルゴリズムにおける小型実装手法の概要について]
次に、本発明の実施例の説明の前提として、既に提案されているSPN構造を適用したAES暗号アルゴリズムにおける小型実装手法の概要について説明する。
【0049】
先に説明したように、例えばHamalainen,Alho、Hannikainen、Hamalainenらは、Substitution Permutation Network(SPN)構造を持つAES暗号アルゴリズムに対する小型実装法として例えば必要なレジスタ数を削減した構成を提案している。この小型実装法については、非特許文献3[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]に開示されている。
【0050】
このAES暗号アルゴリズムの小型実装手法について説明する。
まず、図4を参照してSPN構造を適用したAES暗号アルゴリズムのラウンド関数の構造について説明する。
なお、SPN構造を適用したAES暗号アルゴリズムにおいてもFeistel構造と同様、ラウンド関数を複数回、繰り返し実行する構成を持つ。
図4は、SPN構造を適用したAES暗号アルゴリズムにおいて利用されるラウンド関数実行部の構成例を示す図である。AESでは、図4に示すラウンド関数を、複数回、繰り返して平文から暗号文、または暗号文から平文の生成を行う。
【0051】
図4に示すラウンド関数実行部は以下の構成要素によって構成される。
非線形変換処理を実行する8ビット入出力の16個のS−boxからなる非線形変換部201、
非線形変換部201を構成するS−boxからの8ビット出力の入れ替え処理としてのShift Low実行部202、
Shift Low実行部202の出力を32ビット単位で入力して行列を適用した線形変換処理を実行する4つの行列演算部からなる線形変換部203、
線形変換部203を構成する4つの行列演算部各々からの32ビット出力に対して32ビットのラウンド鍵との排他的論理和演算を実行する4つの演算部からなる排他的論理和演算部204を有する。
【0052】
図4に示す例は、入出力128ビットのラウンド関数実行部であり、16個のS−box各々に8ビット、計8×16=128ビットを入力し、4つの排他的論理和部の各々〜32ビット、計32×4=128ビット出力を行う構成である。非線形変換部201、Shift Low実行部202、線形変換部203、排他的論理和演算部204、これらを適用した一連の処理を1回のラウンド関数の実行処理として実行し、このラウンド関数を複数回、繰り返して128ビットの入力データ(例えば平文)から、128ビットの出力(例えば暗号文)を生成して出力する。
【0053】
AESの実装において、1つのラウンド関数の処理(1 round)、すなわち、非線形変換部201、Shift Low実行部202、線形変換部203、排他的論理和演算部204、これらを適用した一連の処理を、1サイクル(1 cycle)で実行しようとすると、少なくとも、図4に示すように、16個のS−boxの回路と、4個の行列演算回路がデータ暗号化部の構成として必要となる。
【0054】
Hamalainenらは、1つのラウンド関数の処理(1 round)を、1サイクルではなく、16サイクル(16 cycle)で順次シリアル処理として行う設定とすることで、データ暗号化部の小型化を実現した。
この小型化構成では、S−boxの回路は1個しか用いず、さらに、4サイクル(4cycle)かけて1つの行列演算を実行する。このような実装とすることで、行列演算回路の小型化を実現している。
【0055】
図5にHamalainenらの提案したAES暗号を実行するデータ暗号化部のデータパスを示す。図5に示す構成は、図4に示すAES暗号のラウンド関数を実行するハードウェア構成に相当する。
【0056】
図5に示す構成において、演算中のデータは8−bit単位に分割され、各8ビットデータをレジスタr01〜r19に格納している。図5には19個のレジスタ(r01〜r19)が示されている。19個のレジスタ(r01〜r19)の各々は8ビットデータを保持する8ビットレジスタである。
【0057】
図4を参照して説明した通り、図4に示す構成例は、入出力128ビットのラウンド関数実行部であり、図5は、入出力128ビットのラウンド関数を8ビット単位データのシリアル処理として実行するハードウェア構成に対応する。
【0058】
図5の構成において、入出力データをすべて格納するために必要となる8ビットレジスタの数は、128/8=16であり、16個のレジスタがあればよい。図5には19個のレジスタがあり、3つのレジスタが余分であるが、これら24ビット分の3つのレジスタは、行列を適用した線形変換処理を実行するための行列演算処理のために利用される。
【0059】
また、図4を参照して説明したように、AESでは、非線形変換を実行するS−boxと線形変換を実行する行列演算の間にShift Low実行部によるデータ置換が実行される。Hamalainenらの実装手法では、図5中のいくつかのレジスタの前にマルチプレクサ(Multiplexer)m01〜m08を導入することにより、Shift Low実行部で行なわれる置換を実現している。
【0060】
図5に示すように、非線形変換部としてのS−box252は1個しかない。このS−box252に対して8ビットデータを順次入力し、16サイクルで図4に示す16個のS−boxによる非線形変換処理を実行する。
【0061】
S−box252の出力は行列演算回路253に入力され、行列演算回路253において行列を適用した線形変換処理が実行される。なお、図4の構成ではS−boxによる処理データをShift−Low実行部で置換した後、行列演算を行う構成となっているが、図5に示す例では、S−box252の出力を行列演算回路253に直接入力する構成としている。図5の構成では、Shift−Low実行部での置換処理に相当する処理は図5に示すレジスタ群r01〜r19内のマルチプレクサm01〜m08の動作によって実行する。
【0062】
図5に示す行列演算回路253では、図4に示す線形変換部203の4つの行列演算回路の処理が順次実行される。図4に示す線形変換部203の4つの行列演算回路の1つの行列演算回路で実行する行列を適用した線形変換処理を4サイクルで実行する。この処理については後段で詳細に説明する。
【0063】
図4に示す排他的論理和演算部203の排他的論理和演算処理は、図5の排他的論理和演算部254a,254bにおいて実行される。これら排他的論理和演算部254a,254bにおいて、処理データと、鍵生成部251の出力するラウンド鍵との排他的論理和演算処理を実行する。
【0064】
図4に示すShift Low実行部202のデータ置換処理は、前述したように図5に示すレジスタ群r01〜r19内のマルチプレクサm01〜m08の動作によって実行されることになる。
【0065】
図5に示すHamalainenらの提案したSPN構造によるAESアルゴリズムの実行構成では、S−boxを1つのみとしている。
レジスタ数は、図5に示すように152ビット分のレジスタ(8ビットレジスタ×19)となっている。なお、鍵生成部251にも128ビット鍵データを保持する128ビットレジスタが必要となる。
【0066】
図5に示すHamalainenらの提案したSPN構造を適用したAESアルゴリズムの実行構成は、S−box数を1つのみとし、また必要なレジスタ数も最小限の設定とした小型実装を実現している。
【0067】
[3.SPNの小型実装構成における行列演算回路の構成と処理の詳細について]
次に、図5を参照して説明したSPNの小型実装構成における行列演算回路の構成と処理の詳細について説明する。
【0068】
図5を参照して説明したHamalainenらの提案したSPN構造によるAESアルゴリズムの実行構成中、行列演算回路253の実行する行列を適用した線形変換処理について説明する。
説明の簡単化のため、図6のように、Shift Low実行部によるデータ置換を行なう回路や、鍵スケジュール部については省略したデータパスを用いて説明する。
【0069】
図6中のレジスタ群261は、図5中の12個のレジスタr04〜r15とマルチプレクサm05〜m08を含む回路に相当し、96−bit分のデータを保持し、Shift Lowも考慮されたレジスタの集合を表す。
【0070】
図7を用いて行列を適用した線形変換処理を実行する行列演算回路253の動作について説明する。今、下記の演算を図7に示す行列演算回路253を用いて実行するとする。なお、下記の演算は全て、ある有限体GF(28)上で行われるものとする。
【0071】
【数1】
【0072】
なお、式1に示す(x0、x1、x2、x3)は、行列演算回路253に対する入力(S−boxからの出力)、
(y0、y1、y2、y3)は、行列演算回路253の出力(線形変換結果)、
4×4の行列は、行列演算回路253において適用する行列(線形変換行列)に対応する。
なお、4×4の線形変換行列の要素は16進数値として示している。
本例では、(x0、x1、x2、x3)の各々は、S−box252からの1サイクルあたりの出力であり8ビットデータである。出力(y0、y1、y2、y3)の各々も8ビットデータである。
【0073】
なお、図7の行列演算回路253では、図4に示す4つの行列演算部からなる線形変換部203の処理を行う。図4に示す4つの行列演算部の各々は、4つのS−boxにおいてそれぞれ非線形変換されたデータの出力(8ビット出力)を入力して線形変換を実行する。しかし、図5、図7に示す構成では、S−boxが1つのS−box252のみに削減され、1サイクルで図4に示す16個のS−box中の1つ分のS−boxの出力のみが行われる。
【0074】
従って、図7の行列演算回路253では、1つのS−box252から4サイクルかけて必要となる図4に示す4つのS−boxからの出力(x0、x1、x2、x3)を入力することになる。
例えば図7の行列演算回路253において、図4に示す行列演算回路203aの行列演算処理を実行する場合、図4に示す行列演算回路203aに対するS−box出力(1)〜(4)が図7に示す行列演算回路253に順次S−box252から4サイクルかけて入力されることになる。
【0075】
図7に示す行列演算回路253に対するS−box252からの入力は、
第1サイクルにおいてデータx0、
第2サイクルにおいてデータx1、
第3サイクルにおいてデータx2、
第4サイクルにおいてデータx3、
これらのデータであり、このデータを用いて行列を適用した線形変換結果としての(y0,y1,y2,y3)を出力する。
【0076】
このデータ変換を、行列を用いて行うのが図7に示す行列演算回路253であり、この変換処理を式で表現したのが前記の(式1)である。
前述したように、S−box252の各サイクルにおける出力x0、x1、x2、x3、の各々はそれぞれ8ビットデータであり、行列演算回路253における行列を適用した線形変換結果としてのy0,y1,y2,y3の各々もそれぞれ8ビットデータである。
以下、各サイクルにおける処理について説明する。
【0077】
図7に示す行列演算回路253は、1サイクル(1cycle)目に入力データ(din)としてx0を入力する。この時点で、論理積回路271〜274に入力されているイネーブル信号(en)を0にしておく。なお、図5〜図7には示されていないが、制御部によって制御がなされる。
【0078】
図7に示す最上段のラインL1では、入力データ(din)=x0がそのまま排他論理和部281を通過してレジスタr16に格納される。
2番目のラインL2でも、入力データ(din)=x0がそのまま排他論理和部282を通過してレジスタr17に格納される。
【0079】
3番目のラインL3と、4番目のラインL4では、入力データ(din)としてのx0と予め規定された値:2、3との有限体上での乗算処理が実行される。すなわち、乗算部285,286において以下の乗算が実行される。
x0・2、
x0・3、
これらを計算する。
これらの演算結果が、排他論理和部283,284を通過してレジスタr18,r19に格納される。
【0080】
なお、1番目のラインL1と、2番目のラインL2には乗算部が設定されていないが、入力データ(din)としてのx0と予め規定された値:1との有限体上での乗算処理が実行されていると同等である。
【0081】
2、3、4cycle目には、入力データ(din)としてx1、x2、x3をそれぞれ入力する。この2、3、4cycle目は、1cycle目とは異なり、論理積回路271〜274に入力されているイネーブル信号(en)を1にする。
この設定により、排他論理和部281〜284では、入力データまたはその乗算値と論理積回路271〜274からの出力との排他的論理和演算が実行され、その結果がレジスタr16〜r19に格納されることになる。
【0082】
このような処理によって、4cycle後のレジスタr16〜r19には、前記式(式1)に従って算出される結果が格納される。すなわち、
(dout0,dout1,dout2,dout3)
=(y0,y1,y2,y3)
となる。
このように、図7に示す行列演算回路253により、4サイクルの処理で上記(式1)に従った行列演算が実行されることになる。
【0083】
なお、図7を参照して説明した処理は、AESで採用されている巡回行列による行列演算による線形変換処理を実現する回路であるが、他の異なる行列を適用した線形変換処理も、回路の乗算部の設定と、接続構成等を変更することで実現できる。例えば、下記のようなアダマール行列を適用した行列演算を実現する回路は図8に示す行列演算回路290によって実現可能である。
【0084】
【数2】
【0085】
なお、式2に示す(x0、x1、x2、x3)は、図8に示す行列演算回路290に対する入力(S−boxからの出力)
(y0、y1、y2、y3)は、行列演算回路290の出力(線形変換結果)
4×4の行列は、行列演算回路290において適用する行列(線形変換行列)に対応する。
なお、4×4の線形変換行列の要素は16進数値として示している。
【0086】
図8に示すアダマール行列を適用した行列演算を実現する行列演算回路290と、図7に示す巡回行列を実現する行列演算回路253との異なる点は、例えば以下の構成である。
乗算部291〜294が式2に示す4×4のアダマール行列からなる線形変換行列の要素に対応した設定となっている。
論理積回路を、マルチプレクサ(Multiplexer)295〜298に変更して、各レジスタr16〜r19への入力を、2つの他レジスタからの出力か0、これら3つの内から1つ選択する設定としている。
これらの構成が変更点である。
【0087】
図4〜図8を参照して説明したHamalainenらの提案したSPN構造を用いたAES暗号構成の小型実装構成は、S−boxを1つのみに削減し、レジスタ数を最小限の設定とした構成を実現している。
【0088】
1ラウンドのラウンド演算に適用する必要なレジスタは、単純計算を行うと以下の通りとなる。ただしラウンド演算における処理データサイズとしてのブロックサイズnは、n=128ビットとする。
(1)ラウンド鍵格納用の128ビットレジスタ
(2)処理データ格納用の128ビットレジスタ
(3)線形変換行列を適用した行列演算において演算途中結果を格納するための32ビットレジスタ
データ演算部には、(2),(3)のレジスタが必要となり、128+32=160ビットレジスタが必要となると計算される。
【0089】
しかし、図5に示すHamalainenらの提案した構成では、160ビットより8ビット少ない152ビットレジスタ(=8ビットレジスタ×19)とすることに成功している。
Hamalainenらの提案した構成は、S−boxから行列演算回路へ入力が済んだ値(8ビット)が次のラウンドでは不要となる。このことに着目し、行列演算回路へS−boxから入力する32−bitのうち、はじめに入力する8−bit分のレジスタを行列演算回路内のレジスタと共有する構成とすることで、8−bit分のレジスタを削減したものである。
【0090】
[4.SPN構造の小型実装構成の一般化Feisel構造への適用と問題点について]
上述したように、HamalainenらはSPN構造の小型化を実現している。しかし、この小型化構成はSPN構造に対応した特有の構成であり、この小型実装構成を一般化Feisel構造へ適用しても十分な小型化の効果は得られない。以下、この問題点について説明する。なお、以下の説明では、一般化Feisel構造はFeisel構造を含む概念であるものとして説明する。
【0091】
図5を参照して説明したHamalainenらの提案構成を一般化Feistel構造を持つCLEFIA等のアルゴリズムを実行する構成に単純に適用すると、行列演算のために、行列の出力ビット長分のデータを格納するレジスタが必要になる。これは、一般化Feistel構造がSPN構造とは異なり、例えばラウンド関数内のF関数に入力した値を、次のラウンドでも利用する必要があるという処理シーケンスの根本的な違いに起因するものである。
【0092】
また、SPN構造では存在しなかったが、一般化Feistel構造では、ラウンド関数内において、F関数演算後に他のラインと排他的論理和を行う必要がある。そのため、排他的論理和を行うための回路も、一般化Feistel構造のラインのビット長分だけ必要となる。
【0093】
図9は、Hamalainenらの実装法を4−line一般化Feistel構造に適用した場合のデータ演算部回路の概要図を示す図である。図9では、先に図6を参照して説明したAESのデータパスと同様、一般化Feistel構造のラウンド関数終了時の置換動作や鍵スケジュール部は省略してある。
【0094】
なお、ラウンド演算における処理データサイズとしてのブロックサイズはnビットとする。先に図3を参照して説明したように、4−line一般化Feistel構造では、4つのライン各々にn/4ビットずつ入力され、順次転送される。
【0095】
図9中のレジスタ群301は、図6に示すレジスタ群261に対応する。ただし、4−line一般化Feistel構造に対応する図9のレジスタ群301は、(3/4)n−bit分のデータを保持するレジスタとラウンド関数終了時の置換動作と同様の処理を実現するマルチプレクサ等の組み合わせとして構成される。すなわち、レジスタ群301の下側のデータ演算部に1ライン分の(1/4)nビット分のデータが保持されるとすると、図9のレジスタ群301には、(3/4)n−bit分のデータを保持するレジスタが必要となる。
【0096】
なお、図9に示す4−line一般化Feistel構造を適用した暗号アルゴリズムのデータパス(演算実行回路)を適用して実行する演算は、図3に示す4−line一般化Feistel構造を適用した演算処理に対応する。
【0097】
この図9に示すデータパスを利用して図3に示す4−line一般化Feistel構造内のF関数を含むラウンド関数を実行することになる。
ラウンド関数内のF関数の具体例を図10に示す。
【0098】
図10に示すF関数は、先に図2を参照して説明したFeistel構造のF関数と同様、以下の構成要素を持つ。
(a)ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部321、
(b)排他的論理和演算部321の出力に対して非線形変換処理を実行するS−boxからなる非線形変換部[S]322、
(c)非線形変換部[S]322の出力に対して、行列演算により線形変換の処理を行なう線形変換部[M]323、
これらの構成要素を持つ。
ただし、4−line一般化Feistel構造におけるF関数に対する入出力は、n/4ビットとなる。
【0099】
なお、線形変換部[M]323で実行する行列を適用した行列演算としての線形変換処理に適用する行列は、1行目の要素が(a,b,c,d)となる巡回行列を想定している。すなわち、以下の(式3)に示す行列である。
【0100】
【数3】
【0101】
先に図4〜図8を参照して説明したSPN構造を適用したAES暗号アルゴリズムの構成と比較するため、処理単位としてのブロック構成ビットnは、
n=128−bit
とする。
【0102】
図9に示す回路も、図6に示す回路と同様、S−boxは1つのみである。図9に示すS−box303である。このS−box303は図10に示すF関数内に設定される1つのS−boxの処理を1サイクルで実行する。サイクル毎に、順次、図10に示す各S−boxの処理を行うことになる。
【0103】
図10に示すように、F関数の1つのS−boxには、4−line一般化Feistel構造の1つのlineを伝送するn/4ビットの1/4、すなわちn/16ビットが入力され非線形変換処理が実行される。
図9に示すS−box303には、n/16ビットずつがサイクル毎に入力され非線形変換処理が実行される。
【0104】
なお、図9の構成では、レジスタ群301から1サイクル単位でS−box303の処理単位であるn/16ビットのデータを出力する設定であり、このn/16ビットをまず、排他的論理和部302でラウンド鍵の構成データと排他的論理和を行うS−boxで非線形変換を実行する構成としている。
【0105】
S−box303において非線形変換のなされたデータは、n/16ビットごとに1サイクル単位で次の行列演算回路304に入力される。行列演算回路304では所定の行列を適用した線形変換処理が実行されることになる。
【0106】
図9に示す4−line一般化Feistel構造を適用した暗号アルゴリズムのデータパス構成中、レジスタ群301を除く演算実行回路と、先に図6を参照して説明したSPN構造を利用したAES暗号処理を実行する演算回路構成とを比較する。
【0107】
図6に示す演算回路では、8ビットレジスタがr01〜r03、r16〜r19の7個であるのに対して、図9に示す演算回路では、8ビットレジスタがR0〜R7の8個である。すなわち、8−bitレジスタの数が1つ増えている。
また、排他的論理和演算回路の数も増加している。
【0108】
このように、Hamalainenらの提案構成を一般化Feistel構造に適用した場合、図9に示す演算回路のように、ブロック長分のレジスタに加え、1−line分のレジスタと排他的論理和演算回路が必要になってくる。
レジスタの増加は回路規模に大きく影響するため、ブロック長分のみのレジスタで構成できる実現できれば、そのほうが望ましい。
【0109】
なお、レジスタのゲートサイズは他のセルに比べて比較的大きなものとなり、レジスタ数の増加はゲートサイズに大きく影響する。そのため、小型化を実現するための一つの方向性として、レジスタの増加を抑えた実装法を考慮することが重要となる。
【0110】
[5.一般化Feistel構造の小型化の実現構成について]
次に、本発明の構成、すなわち、一般化Feistel構造の小型化の実現構成について説明する。
Hamalainenらの実装法を、一般化Feistel構造を持つ暗号アルゴリズムの実行構成に適用した場合には、前節で説明したようにレジスタと排他的論理和の回路が増加してしまい、小型化が実現されない。
【0111】
これは、SPN構造を適用した暗号アルゴリズムと、一般化Feistel構造を適用した暗号アルゴリズムが異なること、特に、一般化Feistel構造を適用した暗号アルゴリズムでは、行列演算結果を求めてから、他のラインとの排他的論理和を行う設定となっていることなどが要因であると考えられる。
すなわち、一般化Feistel構造を適用した暗号アルゴリズムでは、行列の途中結果を保持するレジスタと他のラインのデータを保持するレジスタの両方が必要となる。
【0112】
また、一般化Feistel構造を適用した暗号アルゴリズムでは、1つのラインのデータに対する行列演算が終了すると、次のサイクル(cycle)で新たなラインの行列の演算が始まる。このため、その1cycleの間に他のラインとの排他的論理和を行なう必要がある。そのため、1−line分の排他的論理和の回路が必要となる。
【0113】
以下に説明する本発明の構成では、排他的論理和演算における結合法則、すなわち、以下の式が成立することを利用し、演算順序を変更することで必要なレジスタの削減を実現している。
【0114】
【数4】
【0115】
上記式4は、排他的論理和演算の順番を変更しても同じ結果が得られることを意味している。本発明では、この法則を利用して、演算順序を変更することで必要なレジスタの削減を実現している。
【0116】
具体的には、他のラインのデータを保持しているレジスタに行列演算の途中結果を排他的論理和していくように演算順序を変更する。このように演算順序を変更することにより、行列演算の途中結果を保持する必要がなくなり、レジスタ数を削減することができる。
【0117】
図11に本発明の一実施例としてのデータパス、すなわち演算回路構成を示す。図11に示す演算回路は、先に図3を参照して説明した4−line一般化Feistel構造を適用した暗号アルゴリズムの実行回路である。具体的には、巡回行列演算部をアダマール行列演算部に置き換えることで、例えばCLEFIA暗号の実行回路として利用可能である。
【0118】
なお、図11に示す回路は、図9と同様、4−line一般化Feistel構造のラウンド関数終了時の置換動作の実行回路や鍵スケジュール部の構成については省略している。
【0119】
図11中のレジスタ群501は、図9に示すレジスタ群301に対応する。すなわち、レジスタ群501は、データ保持用のレジスタとラウンド関数終了時の置換動作の実行機能を持つ回路によって構成される。
しかし、図11中のレジスタ群501は、図9に示すレジスタ群301よりも少ないレジスタ数に設定されている。
【0120】
図9に示すレジスタ群301は、先に説明したように、(3/4)n−bit分のデータを保持するレジスタとラウンド関数終了時の置換動作の実行機能を持つ回路を含む構成として説明した。
これに対して、図11に示すレジスタ群501に含まれるレジスタは、n/2−bit分のデータを保持するレジスタのみである。
【0121】
処理データとしてのブロックのビット数をn、すなわち、4−line一般化Feistel構造を適用した暗号処理単位としてのブロックのビット数:nが、
n=128−bit
とする。
【0122】
この設定で、先に説明した図9の構成では、
レジスタ群301に、(3/4)n−bit=96−bit
レジスタ群301以外の演算部に8ビットレジスタが8個の8×8=64−bit
総計で、
96+64=160−bit
のレジスタが必要となっている。
【0123】
一方、本発明の手法を適用した図11の構成では、
レジスタ群501に、(1/2)n−bit=64−bit
レジスタ群501以外の演算部に8ビットレジスタが8個の8×8=64−bit
総計で、
64+64=128−bit
のレジスタが必要となっている。
【0124】
すなわち、SPN構造に対応するHamalainenらの実装法を4−line一般化Feistel構造に単純に適用した場合の図9の構成においては160−bitのレジスタが必要となるのに対して、本発明の構成である図11に示す4−line一般化Feistel構造を適用した演算回路では、128−bitのレジスタのみでよく、大幅なレジスタ削減が実現される。
【0125】
本発明の構成である図11に示す4−line一般化Feistel構造を適用した演算回路では、図9の構成に比較して32ビット分のレジスタを削減している。
以下、詳細に説明するが、図11に示す本発明の構成では、行列演算回路において、他ラインからの出力(E0、E1、E2、E3)を利用した演算を先行して実行することで、これらの出力データ(E0、E1、E2、E3)を行列演算期間中、保持するためのレジスタ(8×4=32ビット)を削減したことによる。
【0126】
以下、このレジスタ削減を実現させる演算シーケンスについて詳細に説明する。
レジスタ削減を実現するため、本発明の処理では、演算シーケンス、特に、線形変換を行う行列演算回路における行列を適用した演算シーケンスの設定を特別な設定とした。以下、図11に示す本発明に従ったデータパスである回路構成を適用した演算シーケンスの詳細について説明する。
【0127】
図12および以下に示す表1に図9に示すデータパスに従った行列演算回路304における行列演算シーケンスを示す。
さらに、図13および以下に示す表2に図11に示すデータパスに従った行列演算回路504における行列演算シーケンスを示す。
【0128】
【表1】
(表1)
【0129】
【表2】
(表2)
【0130】
図9に示す構成における行列演算シーケンスを示す表1(図12)と、
図11に示す構成における行列演算シーケンスを示す表2(図13)を用いて各処理の差異について説明する。
【0131】
まず、図9と図12(表1)を参照して、SPN構造に対応するHamalainenらの実装法を4−line一般化Feistel構造に単純適用した場合の行列演算シーケンスについて説明する。
【0132】
図9に示すデータパスの行列演算回路304に対して、S−box303からの出力として、順次、データ(x0,x1,x2,x3)が入力されて行列を適用した線形変換処理を行うものとする。
【0133】
行列演算回路304は、行列を適用した行列演算によって生成した出力(y0,y1,y2,y3)を排他的論理和演算部305に出力する。
排他的論理和演算部305では、行列演算回路304の出力(y0,y1,y2,y3)と、4−line一般化Feistel構造における他ラインからの出力(E0、E1、E2、E3)と排他的論理和される。他ラインからの出力(E0、E1、E2、E3)は、例えば前ラウンドにおけるラウンド演算の処理結果に相当する。
【0134】
なお、行列演算回路304に対する入力(x0,x1,x2,x3)の各々はn/16ビットであり、出力(y0,y1,y2,y3)と、他ラインからの出力(E0、E1、E2、E3)の各々もすべてn/16ビットのデータである。
【0135】
このとき、図9に記載のレジスタR0,R1,・・・,R7の格納値は、上記および図12の表1のように変化する。
【0136】
1サイクル(1cycle)目で、レジスタR0、R1、R2、R3に、行列演算回路304に対する入力要素x0に基づく行列演算結果の各要素が格納される。この時点で、論理積回路313に入力されているイネーブル信号(en)は0に設定され、入力要素x0に基づく乗算部311の乗算結果がレジスタR0、R1、R2、R3に格納される。すなわち、
レジスタR0の格納値:d・x0、
レジスタR1の格納値:c・x0、
レジスタR2の格納値:b・x0、
レジスタR3の格納値:a・x0、
これらのデータが各レジスタに格納される。
【0137】
その後、2サイクル目に行列演算回路304に入力要素x1が入力される。2〜4サイクル目では、論理積回路313に入力されるイネーブル信号(en)は1に設定され、排他論理和演算部312において、入力要素x1の乗算部311の乗算結果と、前サイクルでレジスタR0、R1、R2、R3に格納された値との排他的論理和演算が実行され、その結果がレジスタR0、R1、R2、R3に格納される。
また、この2サイクル目において、他ラインからの出力要素E0がレジスタR7に格納される。
【0138】
3サイクル目に行列演算回路304に入力要素x2が入力される。2〜4サイクル目では、論理積回路313に入力されるイネーブル信号(en)は1に設定され、排他論理和演算部312において、入力要素x2の乗算部311の乗算結果と、前サイクルでレジスタR0、R1、R2、R3に格納された値との排他的論理和演算が実行され、その結果がレジスタR0、R1、R2、R3に格納される。
また、この3サイクル目において、他ラインからの出力要素E0がレジスタR6に格納され、E1がレジスタR7に格納される。
【0139】
4サイクル目では、行列演算回路304に入力要素x3が入力される。入力データ(x0,x1,x2,x3)の入力が完了し、この4サイクル目において、行列演算結果(y0,y1,y2,y3)がレジスタR0、R1、R2、R3に格納される。
【0140】
その次の5サイクル目では、他ラインからの出力(E0、E1、E2、E3)と、行列演算回路304における行列を適用した行列演算結果(=線形変換結果)である(y0,y1,y2,y3)とが、排他的論理和演算部305において排他的論理和されて、その結果としての値が、レジスタR4、R5、R6、R7に格納される。
このレジスタ格納値、すなわち、下記式(式5)に示すデータが図9に示すライン306を介して次のラウンド演算の利用データとしてレジスタ群301に入力される。
【0141】
【数5】
【0142】
なお、上記(式5)に示す値は、図3に示すラウンド間の接続部のラウンド出力データ(D)に相当する。
また、この5サイクル目では、次の行列演算回路304への入力値(x'0,x'1、x'2,x'3)の始めの要素x'0に対する演算がレジスタR0、R1、R2、R3に格納される。
【0143】
次に、図11に示す本発明に従ったデータパスを利用した行列演算回路504における行列演算のサイクル単位の遷移処理について、図11と図13(表2)を参照して説明する。
【0144】
図11に示すデータパスの行列演算回路504に対して、図9を参照して説明したと同様のS−box503からの出力として、順次、(x0,x1,x2,x3)が入力され、行列を適用した線形変換処理を行うものとする。
【0145】
この図11に示す構成を用いた行列演算を行うと、図13(表2)に示すように、4サイクル目においてレジスタR0、R1、R2、R3に、次のラウンド演算の利用データ、すなわち、
【0146】
【数6】
【0147】
なお、上記(式6)に示す値が格納される。これらの値は、第5サイクルでレジスタR4、R5、R6、R7に格納され、図11に示すライン506を介して次のラウンド演算の利用データとしてレジスタ501に入力される。
図11に示す構成は、図9に示す構成よりレジスタ数が削減された構成であるが、結果としては図9に示すと同様の演算処理を実現している。ただし、演算シーケンスが異なっている。
各サイクルにおける処理について説明する。
【0148】
図11に示すデータパスを利用した処理では、例えば前ラウンドにおけるラウンド演算の処理結果に相当する他ラインからの出力(E0、E1、E2、E3)を、レジスタ501からの出力ライン521を介してレジスタR7、R6、R5に、順次格納する。図13(表2)に示す1サイクル目の1つ前のサイクル(0サイクル)において、
レジスタR5にはE0、
レジスタR6にはE1、
レジスタR7にはE2、
これらのデータが格納された状態に設定される。
【0149】
1サイクル目において、これらのレジスタ格納値E0、E1、E2と、レジスタ群501から出力ライン521を介した新たな出力値E3を加えた出力(E0、E1、E2、E3)がマルチプレクサ513を介して、排他的論理和演算部512に入力される。なお、これらの演算制御は、例えば図示しない制御部やクロック入力情報に基づく制御によって行われる。
【0150】
排他的論理和演算部512では、これらの出力値(E0、E1、E2、E3)と、入力要素x0に基づく乗算部311の乗算結果、すなわち、
d・x0、
c・x0、
b・x0、
a・x0、
これらの各値との排他的論理和演算が実行される。この排他的論理和演算結果が、レジスタR0、R1、R2、R3に格納される。
【0151】
すなわち、
レジスタR0には、レジスタR6に格納された値E1が、マルチプレクサm0を介して排他論理和演算部512に入力されて、d・x0との排他論理和結果が格納される。
レジスタR1には、レジスタR7に格納された値E2が、マルチプレクサm1を介して排他論理和演算部512に入力されて、c・x0との排他論理和結果が格納される。
レジスタR2には、レジスタ群からライン521を介して出力される出力値E3が、マルチプレクサm2を介して排他論理和演算部512に入力されて、b・x0との排他論理和結果が格納される。
レジスタR3には、レジスタR5に格納された値E0が、マルチプレクサm3を介して排他論理和演算部512に入力されて、a・x0との排他論理和結果が格納される。
すなわち、以下の(式7)に示す各値がレジスタR0、R1、R2、R3に格納される。
【0152】
【数7】
【0153】
なお、マルチプレクサ513(m0〜m3)は、2入力から選択された1つの入力を出力するセレクタと同様の処理を行う。
第1サイクルでは、レジスタR7、R6、R5の格納値、ライン521の出力値を出力するように設定される。なお、これらの制御は図示しない制御部の制御によって行われる。
【0154】
このように、本発明の構成では、図11に示す行列演算回路504に対するS−box503からの第1サイクルにおける入力x0の入力タイミングにおいて、例えば前ラウンドにおけるラウンド演算の処理結果に相当する他ラインからの出力(E0、E1、E2、E3)との排他的論理和演算を実行し、その結果をレジスタR0、R1、R2、R3に格納する。
【0155】
このように本発明の構成では、他ラインからの出力(E0、E1、E2、E3)との排他論理和演算処理を先行して実行する。この結果、4サイクルを要する行列演算期間が完了するまで他ラインからの出力(E0、E1、E2、E3)を保持する必要がなくなる。この演算シーケンスの変更処理によって必要なレジスタ数の削減を実現している。
【0156】
その後、2サイクル目に行列演算回路504に入力要素x1が入力される。2〜4サイクル目では、マルチプレクサ513(m0〜m3)は、レジスタR0、R1、R2、R3の格納値を選択出力するように制御される。
この結果、排他論理和演算部512において、入力要素x1の乗算部511の乗算結果と、前サイクルでレジスタR0、R1、R2、R3に格納された値との排他的論理和演算が実行され、その結果がレジスタR0、R1、R2、R3に格納される。
また、この2サイクル目において、他ラインからの出力要素E'0がレジスタR7に格納される。
【0157】
3サイクル目に行列演算回路504に入力要素x2が入力される。排他論理和演算部512において、入力要素x2の乗算部511の乗算結果と、前サイクルでレジスタR0、R1、R2、R3に格納された値との排他的論理和演算が実行され、その結果がレジスタR0、R1、R2、R3に格納される。
また、この3サイクル目において、他ラインからの出力要素E'0がレジスタR6に格納され、E'1がレジスタR7に格納される。
【0158】
4サイクル目では、行列演算回路504に入力要素x3が入力される。入力データ(x0,x1,x2,x3)の入力が完了し、この4サイクル目において、レジスタR0、R1、R2、R3には、行列演算結果(y0,y1,y2,y3)と他ラインからの出力(E0、E1、E2、E3)との排他論理和結果が格納されることになる。
【0159】
その次の5サイクル目では、次の他ラインからの出力(E'0、E'1、E'2、E'3)がレジスタR7、R6、R5の格納値、ライン521の出力として、排他論理和演算部512に入力される。
排他論理和演算部512は、これらの入力値と、行列演算回路504に対する新たな入力x'0と乗算部511での乗算結果との排他論理和結果を算出して、レジスタR0、R1、R2、R3に格納する。
この時点で、レジスタR0、R1、R2、R3に格納された値は、レジスタR4、R5、R6、R7に格納される。
このレジスタ格納値、すなわち、下記式(式8)に示すデータが図10に示すライン506を介して次のラウンド演算の利用データとしてレジスタ群501に入力される。
【0160】
【数8】
【0161】
このように、本発明に従った構成では、行列の演算処理に際して他ラインからの出力(E0、E1、E2、E3)との排他的論理和演算を先行して実行することにより、他ラインからの出力(E0、E1、E2、E3)を格納するレジスタと、行列演算の途中結果を格納するレジスタを、個別に設定した独立のレジスタとする必要性をなくして、これらのレジスタの共有化を行うことで、必要な総レジスタ数を削減している。
【0162】
[6.本発明の構成による効果および変形例について]
図11に示す本発明に従った一般化Feistel構造を適用した暗号処理を実行するデータパスでは、上述したように、先行した処理結果をラウンド演算における行列演算の最初のサイクル(1サイクル目)で排他論理和演算処理を実行してしまう構成としている。
【0163】
すなわち、例えば前ラウンドにおけるラウンド演算の処理結果に相当する他ラインからの出力(E0、E1、E2、E3)との排他的論理和演算を先行して実行する。
図11を参照して説明したように、行列演算回路504における行列演算の最初の処理として実行する第1サイクルにおいて、他ラインからの出力(E0、E1、E2、E3)をレジスタ等からマルチプレクサ513を介して排他論理和演算部512に先行して入力させて、行列演算回路504に対する最初の入力値(x0)の乗算部511での乗算結果(d・x0等)と排他論理和処理を実行する。
【0164】
このように、本発明の構成では、1−line分(実施例では(n/16)×4)のマルチプレクサ(Multiplexer)を導入することで、図9に示す構成において必要であった1−line分のレジスタと1−line分の排他的論理和と1−line分の論理積の回路をなくすことができる。図11に示す構成では、これらの差分だけ、小型化を行うことができる。
また、この小型化に伴い、低消費電力化も期待できる。
特に、レジスタのゲートサイズは、他のセルに比べて比較的大きなものとなるため、1−line分のレジスタを削減できたことは小型化に特に寄与する。
【0165】
なお、上述した実施例では、本発明の適用構成の代表例として、4−line一般化Feistel構造への適用例について説明した。しかしながら、図11、図13(表1)を参照して説明した処理シーケンス、すなわち、他ラインからの出力値を先行して行列演算に適用することは、4−line以外の一般化Feistel構造やFeistel構造においても適用可能であり、図11を参照して説明したと同様のレジスタ他の回路構成の削減が実現される。すなわち、本発明は、4−line一般化Feistel構造のみでなく、ラウンド関数内部を変形、拡張された構造についても適用可能であり、2−lineのFeistel構造や、任意のx(xは2以上の自然数)の、x−line一般化Feistel構造にも適用できる。
【0166】
また、上述した実施例では、行列演算回路において適用する行列を巡回行列とした例について説明したが、行列演算回路において適用する行列は巡回行列に限らず、例えばアダマール行列など、その他の形式の行列を適用することも可能である。
【0167】
さらに、行列演算回路において適用する行列は、4×4行列のみでなく、
任意のx×x行列、ただし、xは2以上の自然数、
このような様々な行列の適用が可能である。
【0168】
また、先に図2を参照して説明したF関数を持つ構成に限らず、行列演算後に非線形変換を含まないラウンド関数を実行するアルゴリズムであれば、本発明の構成は適用可能であり、同様の小型化の効果が期待できる。
【0169】
なお、上述した実施例で説明した構成は、4−line一般化Feistel構造におけるtype−2一般化Feistel構造の例であるが、本発明は、この他のtype−1や、type−3の一般化Feistel構造に対しても適用可能であり、同様の効果が期待できる。
【0170】
2ラインのFeistel構造に対して本発明を適用したデータパスとしての回路構成例を図14に示す。
図14に示すデータパスにおいて、例えば前ラウンドの演算結果としての他ラインからの出力(E0、E1、E2、E3)をレジスタR4、R5、R6、R7に格納し、行列第1演算回路604における行列演算の最初の処理らサイクル(1サイクル目)においてS−box603からの入力値x0と乗算部611における乗算結果との排他論理和を実行してその結果をレジスタR0、R1、R2、R3に格納する。
このように、先に図11を参照して説明したと同様の処理シーケンスで行列演算を実行することが可能であり、この処理により、レジスタ数の削減などによりハードウェア構成を小型化することが可能となる。
【0171】
具体的には、図14の構成とすることで、例えば図9と同様の構成に従って2ラインのFeistel構造のデータパスを設定した場合にn/2−bit分必要であった行列演算用のレジスタが不要となり、n−bit分のレジスタのみで全体を構成できる。
【0172】
なお、図14に示す2ラインのFeistel構造とした場合でも、行列演算回路604において適用する行列は巡回行列、アダマール行列等が利用可能であり、またx×x(ただしx≧2の整数)の任意の行列が利用できる。また、図2を参照して説明したF関数を持つ構成に限らず、行列演算後に非線形変換を実行しないラウンド関数であれば、本発明の適用が可能である。
【0173】
[7.暗号処理装置のICカードとしての構成例について]
最後に、上述した実施例に従った暗号処理を実行する暗号処理装置としてのICモジュール700の構成例を図15に示す。上述の処理は、例えばPC、ICカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図15に示すICモジュール700は、これら様々な機器に構成することが可能である。
【0174】
図15に示すCPU(Central processing Unit)701は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ702は、CPU701が実行するプログラム、あるいは演算パラメータなどの固定データを格納するROM(Read-Only-Memory)、CPU701の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるRAM(Random Access Memory)等からなる。また、メモリ702は暗号処理に必要な鍵データや、暗号処理において適用する変換テーブル(置換表)や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【0175】
暗号処理部703は、例えば図11や図14を参照して説明した暗号処理構成、すなわち、例えば一般化Feistel構造や、Feistel構造を適用した共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理を実行する。
【0176】
なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをROMに格納し、CPU701がROM格納プログラムを読み出して実行するように構成してもよい。
【0177】
乱数発生器704は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【0178】
送受信部705は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ICモジュールとのデータ通信を実行し、ICモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【0179】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【0180】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【0181】
例えば、プログラムは記録媒体としてのハードディスクやROM(Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、CD−ROM(Compact Disc Read Only Memory),MO(Magneto optical)ディスク,DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納(記録)しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【0182】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、LAN(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【0183】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【0184】
上述したように、本発明の一実施例の構成によれば、一般化Feistel構造を適用した暗号処理構成の小型化や省電力化が実現される。
具体的には、データを複数ラインに分割入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する一般化Feistel構造を適用した暗号処理構成において、第1ラインのデータに対する行列を適用した線形変換処理を実行する行列演算実行部が行列演算の実行サイクル中、最初のサイクルにおいて行列演算過程データと第2ラインのデータとの演算を実行する。本構成により、第2ラインのデータ保持用のレジスタと第1ラインの行列演算途中結果保持用のレジスタの共有化が可能となり、総レジスタ数の削減、小型化が実現される。さらに回路構成の小型化、エレメント数の削減により電力消費量の削減も可能となる。
【符号の説明】
【0185】
111 鍵スケジュール部
112 データ暗号化部
120 F関数
121 排他的論理和演算部
122 非線形変換部
123 線形変換部
201 非線形変換部
202 Shift Low実行部
203 線形変換部
204 排他的論理和演算部
251 鍵生成部
252 S−box
253 行列演算回路
254 排他的論理和演算部
271〜274 論理積回路
281〜284 排他的論理和演算部
285〜286 乗算部
290 行列演算回路
291〜294 乗算部
295〜298 マルチプレクサ
301 レジスタ群
302 排他的論理和演算部
303 S−box
304 行列演算回路
305 排他的論理和部
311 乗算部
312 排他的論理和部
313 論理積回路
321 排他的論理和演算部
322 非線形変換部[S]
323 線形変換部[M]
501 レジスタ群
502 排他的論理和演算部
503 S−box
504 行列演算回路
511 乗算部
512 排他的論理和部
513 マルチプレクサ
603 S−box
604 行列演算回路
611 乗算部
613 マルチプレクサ
700 ICモジュール
701 CPU(Central processing Unit)
702 メモリ
703 暗号処理部
704 乱数生成部
705 送受信部
【技術分野】
【0001】
本発明は、暗号処理装置、および暗号処理方法、並びにプログラムに関する。さらに詳細には、Feistel構造や一般化Feistel構造を持つ共通鍵ブロック暗号を実行する暗号処理装置、および暗号処理方法、並びにプログラムに関する。
【背景技術】
【0002】
情報化社会が発展すると共に、扱う情報を安全に守るための情報セキュリティ技術の重要性が増してきている。情報セキュリティ技術の構成要素の一つとして暗号技術があり、現在では様々な製品やシステムで暗号技術が利用されている。
【0003】
暗号処理アルゴリズムには様々なものがあるが、基本的な技術の一つとして、共通鍵ブロック暗号と呼ばれるものがある。共通鍵ブロック暗号では、暗号化用の鍵と復号用の鍵が共通のものとなっている。暗号化処理、復号処理共に、その共通鍵から複数の鍵を生成し、あるブロック単位、例えば64ビット、128ビット、256ビット等のブロックデータ単位でデータ変換処理を繰り返し実行する。
【0004】
代表的な共通鍵ブロック暗号のアルゴリズムとしては、過去の米国標準であるDES(Data Encryption Standard)や現在の米国標準であるAES(Advanced Encryption Standard)が知られている。他にも様々な共通鍵ブロック暗号が現在も提案され続けており、2007年にソニー株式会社が提案したCLEFIAも共通鍵ブロック暗号の一つである。
【0005】
このような、共通鍵ブロック暗号のアルゴリズムは、主として、入力データの変換を繰り返し実行するラウンド関数実行部を有する暗号処理部と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部とによって構成される。鍵スケジュール部は、秘密鍵であるマスター鍵(主鍵)に基づいて、まずビット数を増加させた拡大鍵を生成し、生成した拡大鍵に基づいて、暗号処理部の各ラウンド関数部で適用するラウンド鍵(副鍵)を生成する。
【0006】
このようなアルゴリズムを実行する具体的な構造として、線形変換部および非線形変換部を有するラウンド関数を繰り返し実行する構造が知られている。例えば代表的な構造にFeistel構造や一般化Feistel構造がある。Feistel構造や一般化Feistel構造は、データ変換関数としてのF関数を含むラウンド関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。F関数においては、線形変換処理および非線形変換処理が実行される。なお、Feistel構造を適用した暗号処理について記載した文献としては、例えば非特許文献1、非特許文献2がある。
【0007】
暗号アルゴリズムの実装形態には、ソフトウェア実装とハードウェア実装の二種類が存在する。ハードウェア実装では、回路規模が小さくなるように実装することで、ハードウェア化の際のコストダウンや低消費電力化が期待できる。そのため、新アルゴリズム、既存アルゴリズムを問わず、小型化するための実装法が様々、提案されている。
【0008】
例えばHamalainen,Alho、Hannikainen、Hamalainenらは、Substitution Permutation Network(SPN)構造を持つAES暗号アルゴリズムに対する小型実装法を提案している。この小型実装法については、非特許文献3[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]に開示されている。
【0009】
しかし、この小型実装法は、SPN構造を利用したAESアルゴリズム固有の処理シーケンスに適応するものであり、SPN構造とは異なる上述のFeistel構造や一般化Feistel構造を持つ暗号アルゴリズムであるDESやCLEFIA暗号アルゴリズムへそのまま適用しても十分な小型化を実現できないという問題がある。
【0010】
なお、上述したAES暗号は、SPN構造を利用した暗号アルゴリズムであり、DES暗号や、CLEFIA暗号はSPN構造とは異なるFeistel構造や一般化Feistel構造を利用した暗号アルゴリズムである。これらの具体的な構造については後段で詳細に説明する。
【先行技術文献】
【非特許文献】
【0011】
【非特許文献1】K. Nyberg, "Generalized Feistel networks", ASIACRYPT'96, SpringerVerlag, 1996, pp.91--104.
【非特許文献2】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
【非特許文献3】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
【発明の概要】
【発明が解決しようとする課題】
【0012】
本発明は、例えば上述の状況に鑑みてなされたものであり、Feistel構造や一般化Feistel構造を利用した暗号処理構成における小型化を実現する暗号処理装置、および暗号処理方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【0013】
本発明の第1の側面は、
データ処理対象となるデータブロックの構成ビットを複数のラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインの第1ラインのデータに対する変換データを生成し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行する演算部と、
前記演算部の演算結果を保持するレジスタを有し、
前記演算部は、前記レジスタから順次、データを取得して取得データ順の演算を実行して演算結果を前記レジスタに格納する構成であり、
前記演算部は、
前記第1ラインのデータに対する行列を適用した線形変換を実行する行列演算実行部を有し、
前記行列演算実行部は、
前記第1ラインのデータに対する行列演算の実行サイクル中、最初のサイクルの行列演算の実行に際して前記第2ラインのデータとの演算を実行する暗号処理装置にある。
【0014】
さらに、本発明の暗号処理装置の一実施態様において、前記行列演算実行部は、前段の非線形変換部から順次出力される複数の単位データに対する行列演算を複数サイクルで実行する構成であり、前記複数サイクルの最初のサイクルで、前記非線形変換部から入力する単位データの行列演算に併せて前記第2ラインのデータとの演算を実行する。
【0015】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理装置は、前記第1ラインのデータに対する行列演算に必要な演算サイクルの完了後に前記第2ラインのデータとの演算を実行する場合に必要となる前記第2ラインのデータ保持用の独立したレジスタを削減し、前記第1ラインのデータに対する行列演算の途中結果の保持用レジスタを前記第2ラインのデータ保持用のレジスタとして利用した構成を有する。
【0016】
さらに、本発明の暗号処理装置の一実施態様において、前記行列演算実行部は、前記第1ラインのデータに対する行列演算を実行する初期サイクルにおいて、前記第1ラインに対する行列演算過程データと前記第2ラインのデータとの排他的論理和演算を実行する。
【0017】
さらに、本発明の暗号処理装置の一実施態様において、前記行列演算実行部は、巡回行列またはアダマール行列を適用した行列演算を実行する構成である。
【0018】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部は、前記ラウンド関数の実行部として、非線形変換処理を実行する非線形変換部と、行列を適用した線形変換処理を実行する線形変換部としての行列演算実行部を有する。
【0019】
さらに、本発明の暗号処理装置の一実施態様において、前記行列演算実行部は、前記非線形変換部としてのS−boxの出力を、順次入力して入力データに対する行列演算を1サイクル処理として実行する。
【0020】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部の実行する暗号処理は、Feistel構造または一般化Feistel構造を適用した暗号処理である。
【0021】
さらに、本発明の暗号処理装置の一実施態様において、前記暗号処理部の実行する暗号処理は、CLEFIA暗号アルゴリズムに従った暗号処理である。
【0022】
さらに、本発明の第2の側面は、
暗号処理装置において暗号処理を実行する暗号処理方法であり、
暗号処理部が、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第1ラインのデータの変換処理を実行し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行し、
前記第1ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第2ラインのデータとの演算を実行する暗号処理方法にある。
【0023】
さらに、本発明の第3の側面は、
暗号処理装置において暗号処理を実行させるプログラムであり、
暗号処理部に、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行させる暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第1ラインのデータの変換処理を実行し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行させ、
前記第1ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第2ラインのデータとの演算を実行させるプログラムにある。
【0024】
なお、本発明のプログラムは、例えば、様々なプログラム・コードを実行可能な情報処理装置やコンピュータ・システムに対して例えば記憶媒体によって提供されるプログラムである。このようなプログラムを情報処理装置やコンピュータ・システム上のプログラム実行部で実行することでプログラムに応じた処理が実現される。
【0025】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【0026】
本発明の一実施例によれば、一般化Feistel構造を適用した暗号処理構成の小型化や省電力化が実現される。
具体的には、データを複数ラインに分割入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する一般化Feistel構造を適用した暗号処理構成において、第1ラインのデータに対する行列を適用した線形変換処理を実行する行列演算実行部が行列演算の実行サイクル中、最初のサイクルにおいて行列演算過程データと第2ラインのデータとの演算を実行する。本構成により、第2ラインのデータ保持用のレジスタと第1ラインの行列演算途中結果保持用のレジスタの共有化が可能となり、総レジスタ数の削減、小型化が実現される。さらに回路構成の小型化、エレメント数の削減により電力消費量の削減も可能となる。
【図面の簡単な説明】
【0027】
【図1】kビットの鍵長に対応したnビット共通鍵ブロック暗号アルゴリズムを説明する図である。
【図2】Feistel構造の全体構造と、1つのF関数の詳細構成例について説明する図である。
【図3】一般化Feistel構造の一例について説明する図である。
【図4】SPN構造を適用したAES暗号アルゴリズムのラウンド関数の構造について説明する図である。
【図5】Hamalainenらの提案したAES暗号を実行するデータ暗号化部のデータパスを示す図である。
【図6】Hamalainenらの提案したAES暗号を実行するデータ暗号化部のデータパスを簡略化して示した図である。
【図7】行列を適用した線形変換処理を実行する行列演算回路253の動作について説明する図である。
【図8】アダマール行列を適用した行列演算を実現する行列演算回路について説明する図である。
【図9】Hamalainenらの実装法を4−line一般化Feistel構造に適用した場合のデータ演算部回路の概要図である。
【図10】F関数の構成例について説明する図である。
【図11】本発明の一実施例としてのデータパス、すなわち演算回路構成を示す図である。
【図12】図9に示すデータパスに従った行列演算回路304における行列演算シーケンスを示す図である。
【図13】図11に示すデータパスに従った行列演算回路504における行列演算シーケンスを示す図である。
【図14】2ラインのFeistel構造に対して本発明を適用したデータパスとしての回路構成例について説明する図である。
【図15】暗号処理装置としてのICモジュール700の構成例を示す図である。
【発明を実施するための形態】
【0028】
以下、図面を参照しながら本発明の暗号処理装置、および暗号処理方法、並びにプログラムの詳細について説明する。説明は、以下の項目に従って行う。
1.共通鍵ブロック暗号の概要
2.SPN構造を適用したAES暗号アルゴリズムにおける小型実装手法の概要について
3.SPNの小型実装構成における行列演算回路の構成と処理の詳細について
4.SPN構造の小型実装構成の一般化Feisel構造への適用と問題点について
5.一般化Feistel構造の小型化の実現構成について
6.本発明の構成による効果および変形例について
7.暗号処理装置のICカードとしての構成例について
【0029】
[1.共通鍵ブロック暗号の概要]
まず、本発明の適用可能な共通鍵ブロック暗号の概要について説明する。本明細書において、共通鍵ブロック暗号(以下ではブロック暗号)は、以下に定義するものを指すものとする。
【0030】
ブロック暗号は平文Pと鍵Kを入力し、暗号文Cを出力する。平文と暗号文のビット長をブロックサイズと呼び、ここではnで示す。nは任意の整数値を取りうるが、通常、ブロック暗号アルゴリズムごとに、予め1つに決められている値である。なお、複数のブロック長に対応するアルゴリズムもある。ブロック長がnのブロック暗号のことをnビットブロック暗号と呼ぶこともある。
【0031】
鍵のビット長はkで表す。鍵は任意の整数値を取りうる。共通鍵ブロック暗号アルゴリズムは1つまたは複数の鍵サイズに対応することになる。例えば、あるブロック暗号アルゴリズムAはブロックサイズn=128であり、ビット長k=128、またはk=192またはk=256の各種の鍵サイズに対応するという構成もありうる。
平文[P]、暗号文[C]、鍵[K]の各ビットサイズは、以下のように示される。
平文P:nビット
暗号文C:nビット
鍵K:kビット
【0032】
図1にkビットの鍵長に対応したnビット共通鍵ブロック暗号アルゴリズムを説明する図を示す。図1に示すように、共通鍵ブロック暗号処理は、nビットの平文Pと、kビットの秘密鍵Kを入力して、予め定められた暗号アルゴリズムを実行して、nビットの暗号文Cを出力する。なお、図1には平文から暗号文を生成する暗号化処理を示しているが、暗号文から平文を生成する復号処理では、鍵の入力順を逆にし、ラウンド関数の逆関数を構成することにより、復号処理がなされる。
【0033】
ブロック暗号は2つの部分に分けて考えることができる。ひとつは鍵Kを入力とし、ある定められたステップにより入力秘密鍵Kのビット長を拡大して拡大鍵K'(ビット長k')を出力する鍵スケジュール部111と、平文Pと鍵スケジュール部111から入力する拡大鍵K'から生成されるラウンド鍵RK等を受け取り、平文Pを入力して、ラウンド鍵RK等を適用した暗号処理を実行して、暗号文Cを生成するためのデータの変換を実行するデータ暗号化部112である。なお、先に説明したように、データ暗号化部112を変更することにより、復号処理を実現できる。
【0034】
このように、共通鍵ブロック暗号のアルゴリズムは、入力データの変換を繰り返し実行するラウンド関数を有するデータ暗号化部112と、ラウンド関数部の各ラウンドで適用するラウンド鍵を生成する鍵スケジュール部111とによって構成される。鍵スケジュール部111は秘密鍵Kを入力し、各ラウンド関数に入力するラウンド鍵を生成する。例えば、r段のラウンド関数を行なう構成としたブロック暗号においては、1からr段までのラウンド関数にそれぞれRK1、RK2・・・、Rrのラウンド鍵が入力される。また、鍵スケジュール部111は、初期鍵としてIK、最終鍵としてFKをデータ暗号化部112に出力し、これらの鍵と処理データとの排他的論理和がなされる。
【0035】
先に説明したように共通鍵ブロック暗号におけるデータ暗号化部112の代表的な構造としてFeistel構造がある。ブロック長をnビット(n−bit)とした場合の具体的なFeistel構造の構成例を図2に示す。
【0036】
Feistel構造は、データ変換関数としてのF関数を含むラウンド関数の単純な繰り返しにより、平文を暗号文に変換する構造を持つ。F関数においては、線形変換処理および非線形変換処理が実行される。
図2には右側にFeistel構造の全体構造を示し、左側に1つのF関数120の詳細構成図を示している。
【0037】
図2右側のFeistel構造に示すように、n−bitのデータをn/2−bitずつの2−lineに分割し、そのn/2−bitの片方をラウンド内のF関数に入力し、その出力をもう片方のn/2−bitと排他的論理和していく構成となっている。
各ラウンドにおけるF関数には、鍵スケジュール部111から入力する拡大鍵K'から生成されるラウンド鍵RK1〜RKrが入力される。
【0038】
F関数の構成には様々なタイプのものがあるが、例えば、図2に示すF関数120のように、ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部121、排他的論理和演算部121の出力に対して非線形変換処理を実行するS−boxと呼ばれる非線形変換部[S]122、非線形変換部[S]122の出力に対して、行列演算により線形変換の処理を行なう線形変換部[M]123を有する構成が知られている。
【0039】
なお、図2に示した構造は、Feistel構造の構成例の1つである。この構造の他、例えば初期鍵IKや、最終鍵FKの排他的論理和演算を行う位置を変更した構成など、様々な構成がある。
【0040】
図2に示す構成は、処理対象となるn−bitの入力(例えば平文の構成データ)Pを2つに分割してn/2−bitずつの2−lineとして処理を行う構成であった。このように入力を2分割して処理を行う構成をFeistel構造と呼ぶ。
処理対象データの分割数は2分割に限らず、様々な設定が可能である。分割数を2に限定しないFeistel構造を一般化Feistel構造と呼ぶ。
【0041】
図3を参照して、一般化Feistel構造の一例について説明する。図3に示す構成は、処理対象データを4分割して処理を行う構成例である。
図2を参照して説明したFeistel構造は、処理対象データであるn−bitの平文データを、n/2−bitずつの2−lineに分割し、処理を行なう構成であった。これに対して、図3に示す構成は、処理対象データであるn−bitの平文データを、n/4−bitずつの4−lineに分割して処理を行なう構成を持つ。
【0042】
図3に示す構成は、4−line一般化Feistel構造と呼ばれる。図3に示す4−line一般化Feistel構造も、図2を参照して説明したFeistel構造と同様、F関数を持つラウンド関数を繰り返し実行する構成を持つ。
【0043】
ただし、図3に示すように入力nビットは4分割され、データの流れが複雑になっている。図3に示す構成では、n−bitのデータをn/4−bitずつの4−lineに分割し、そのうちの2−lineをそれぞれF関数に入力し、その出力をその他の2−lineと排他的論理和していく構成となっている。
【0044】
F関数は、例えば図2を参照して説明したF関数120と同様、ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部121、排他的論理和演算部121の出力に対して非線形変換処理を実行するS−boxと呼ばれる非線形変換部[S]122、非線形変換部[S]122の出力に対して、行列演算により線形変換の処理を行なう線形変換部[M]123を有する構成が利用される。
【0045】
図3に示す4−line一般化Feistel構造のように、データ暗号化部における処理ラインを2−lineから4−lineに変更することにより、ラウンド鍵RKi、初期鍵IK、最終鍵FKも、n/2−bitから、n/4−bitのRKi[0]、RKi[1]、IK[0]、IK[1]、FK[0]、FK[1]に分割される。
【0046】
なお、図3は4−line一般化Feistel構造を示しているが、処理データを2−line以上としたFeistel構造については全て一般化Feistel構造と呼ぶ。
【0047】
以下の本発明の説明においては、4−line一般化Feistel構造における本発明の適用例について説明する。ただし、本発明は、4−line一般化Feistel構造のみならず、2ライン(2−line)のFeistel構造、2ライン(2−line)以上の任意の処理ライン数を持つ一般化Feistel構造のいずれにも適用可能である。
【0048】
[2.SPN構造を適用したAES暗号アルゴリズムにおける小型実装手法の概要について]
次に、本発明の実施例の説明の前提として、既に提案されているSPN構造を適用したAES暗号アルゴリズムにおける小型実装手法の概要について説明する。
【0049】
先に説明したように、例えばHamalainen,Alho、Hannikainen、Hamalainenらは、Substitution Permutation Network(SPN)構造を持つAES暗号アルゴリズムに対する小型実装法として例えば必要なレジスタ数を削減した構成を提案している。この小型実装法については、非特許文献3[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]に開示されている。
【0050】
このAES暗号アルゴリズムの小型実装手法について説明する。
まず、図4を参照してSPN構造を適用したAES暗号アルゴリズムのラウンド関数の構造について説明する。
なお、SPN構造を適用したAES暗号アルゴリズムにおいてもFeistel構造と同様、ラウンド関数を複数回、繰り返し実行する構成を持つ。
図4は、SPN構造を適用したAES暗号アルゴリズムにおいて利用されるラウンド関数実行部の構成例を示す図である。AESでは、図4に示すラウンド関数を、複数回、繰り返して平文から暗号文、または暗号文から平文の生成を行う。
【0051】
図4に示すラウンド関数実行部は以下の構成要素によって構成される。
非線形変換処理を実行する8ビット入出力の16個のS−boxからなる非線形変換部201、
非線形変換部201を構成するS−boxからの8ビット出力の入れ替え処理としてのShift Low実行部202、
Shift Low実行部202の出力を32ビット単位で入力して行列を適用した線形変換処理を実行する4つの行列演算部からなる線形変換部203、
線形変換部203を構成する4つの行列演算部各々からの32ビット出力に対して32ビットのラウンド鍵との排他的論理和演算を実行する4つの演算部からなる排他的論理和演算部204を有する。
【0052】
図4に示す例は、入出力128ビットのラウンド関数実行部であり、16個のS−box各々に8ビット、計8×16=128ビットを入力し、4つの排他的論理和部の各々〜32ビット、計32×4=128ビット出力を行う構成である。非線形変換部201、Shift Low実行部202、線形変換部203、排他的論理和演算部204、これらを適用した一連の処理を1回のラウンド関数の実行処理として実行し、このラウンド関数を複数回、繰り返して128ビットの入力データ(例えば平文)から、128ビットの出力(例えば暗号文)を生成して出力する。
【0053】
AESの実装において、1つのラウンド関数の処理(1 round)、すなわち、非線形変換部201、Shift Low実行部202、線形変換部203、排他的論理和演算部204、これらを適用した一連の処理を、1サイクル(1 cycle)で実行しようとすると、少なくとも、図4に示すように、16個のS−boxの回路と、4個の行列演算回路がデータ暗号化部の構成として必要となる。
【0054】
Hamalainenらは、1つのラウンド関数の処理(1 round)を、1サイクルではなく、16サイクル(16 cycle)で順次シリアル処理として行う設定とすることで、データ暗号化部の小型化を実現した。
この小型化構成では、S−boxの回路は1個しか用いず、さらに、4サイクル(4cycle)かけて1つの行列演算を実行する。このような実装とすることで、行列演算回路の小型化を実現している。
【0055】
図5にHamalainenらの提案したAES暗号を実行するデータ暗号化部のデータパスを示す。図5に示す構成は、図4に示すAES暗号のラウンド関数を実行するハードウェア構成に相当する。
【0056】
図5に示す構成において、演算中のデータは8−bit単位に分割され、各8ビットデータをレジスタr01〜r19に格納している。図5には19個のレジスタ(r01〜r19)が示されている。19個のレジスタ(r01〜r19)の各々は8ビットデータを保持する8ビットレジスタである。
【0057】
図4を参照して説明した通り、図4に示す構成例は、入出力128ビットのラウンド関数実行部であり、図5は、入出力128ビットのラウンド関数を8ビット単位データのシリアル処理として実行するハードウェア構成に対応する。
【0058】
図5の構成において、入出力データをすべて格納するために必要となる8ビットレジスタの数は、128/8=16であり、16個のレジスタがあればよい。図5には19個のレジスタがあり、3つのレジスタが余分であるが、これら24ビット分の3つのレジスタは、行列を適用した線形変換処理を実行するための行列演算処理のために利用される。
【0059】
また、図4を参照して説明したように、AESでは、非線形変換を実行するS−boxと線形変換を実行する行列演算の間にShift Low実行部によるデータ置換が実行される。Hamalainenらの実装手法では、図5中のいくつかのレジスタの前にマルチプレクサ(Multiplexer)m01〜m08を導入することにより、Shift Low実行部で行なわれる置換を実現している。
【0060】
図5に示すように、非線形変換部としてのS−box252は1個しかない。このS−box252に対して8ビットデータを順次入力し、16サイクルで図4に示す16個のS−boxによる非線形変換処理を実行する。
【0061】
S−box252の出力は行列演算回路253に入力され、行列演算回路253において行列を適用した線形変換処理が実行される。なお、図4の構成ではS−boxによる処理データをShift−Low実行部で置換した後、行列演算を行う構成となっているが、図5に示す例では、S−box252の出力を行列演算回路253に直接入力する構成としている。図5の構成では、Shift−Low実行部での置換処理に相当する処理は図5に示すレジスタ群r01〜r19内のマルチプレクサm01〜m08の動作によって実行する。
【0062】
図5に示す行列演算回路253では、図4に示す線形変換部203の4つの行列演算回路の処理が順次実行される。図4に示す線形変換部203の4つの行列演算回路の1つの行列演算回路で実行する行列を適用した線形変換処理を4サイクルで実行する。この処理については後段で詳細に説明する。
【0063】
図4に示す排他的論理和演算部203の排他的論理和演算処理は、図5の排他的論理和演算部254a,254bにおいて実行される。これら排他的論理和演算部254a,254bにおいて、処理データと、鍵生成部251の出力するラウンド鍵との排他的論理和演算処理を実行する。
【0064】
図4に示すShift Low実行部202のデータ置換処理は、前述したように図5に示すレジスタ群r01〜r19内のマルチプレクサm01〜m08の動作によって実行されることになる。
【0065】
図5に示すHamalainenらの提案したSPN構造によるAESアルゴリズムの実行構成では、S−boxを1つのみとしている。
レジスタ数は、図5に示すように152ビット分のレジスタ(8ビットレジスタ×19)となっている。なお、鍵生成部251にも128ビット鍵データを保持する128ビットレジスタが必要となる。
【0066】
図5に示すHamalainenらの提案したSPN構造を適用したAESアルゴリズムの実行構成は、S−box数を1つのみとし、また必要なレジスタ数も最小限の設定とした小型実装を実現している。
【0067】
[3.SPNの小型実装構成における行列演算回路の構成と処理の詳細について]
次に、図5を参照して説明したSPNの小型実装構成における行列演算回路の構成と処理の詳細について説明する。
【0068】
図5を参照して説明したHamalainenらの提案したSPN構造によるAESアルゴリズムの実行構成中、行列演算回路253の実行する行列を適用した線形変換処理について説明する。
説明の簡単化のため、図6のように、Shift Low実行部によるデータ置換を行なう回路や、鍵スケジュール部については省略したデータパスを用いて説明する。
【0069】
図6中のレジスタ群261は、図5中の12個のレジスタr04〜r15とマルチプレクサm05〜m08を含む回路に相当し、96−bit分のデータを保持し、Shift Lowも考慮されたレジスタの集合を表す。
【0070】
図7を用いて行列を適用した線形変換処理を実行する行列演算回路253の動作について説明する。今、下記の演算を図7に示す行列演算回路253を用いて実行するとする。なお、下記の演算は全て、ある有限体GF(28)上で行われるものとする。
【0071】
【数1】
【0072】
なお、式1に示す(x0、x1、x2、x3)は、行列演算回路253に対する入力(S−boxからの出力)、
(y0、y1、y2、y3)は、行列演算回路253の出力(線形変換結果)、
4×4の行列は、行列演算回路253において適用する行列(線形変換行列)に対応する。
なお、4×4の線形変換行列の要素は16進数値として示している。
本例では、(x0、x1、x2、x3)の各々は、S−box252からの1サイクルあたりの出力であり8ビットデータである。出力(y0、y1、y2、y3)の各々も8ビットデータである。
【0073】
なお、図7の行列演算回路253では、図4に示す4つの行列演算部からなる線形変換部203の処理を行う。図4に示す4つの行列演算部の各々は、4つのS−boxにおいてそれぞれ非線形変換されたデータの出力(8ビット出力)を入力して線形変換を実行する。しかし、図5、図7に示す構成では、S−boxが1つのS−box252のみに削減され、1サイクルで図4に示す16個のS−box中の1つ分のS−boxの出力のみが行われる。
【0074】
従って、図7の行列演算回路253では、1つのS−box252から4サイクルかけて必要となる図4に示す4つのS−boxからの出力(x0、x1、x2、x3)を入力することになる。
例えば図7の行列演算回路253において、図4に示す行列演算回路203aの行列演算処理を実行する場合、図4に示す行列演算回路203aに対するS−box出力(1)〜(4)が図7に示す行列演算回路253に順次S−box252から4サイクルかけて入力されることになる。
【0075】
図7に示す行列演算回路253に対するS−box252からの入力は、
第1サイクルにおいてデータx0、
第2サイクルにおいてデータx1、
第3サイクルにおいてデータx2、
第4サイクルにおいてデータx3、
これらのデータであり、このデータを用いて行列を適用した線形変換結果としての(y0,y1,y2,y3)を出力する。
【0076】
このデータ変換を、行列を用いて行うのが図7に示す行列演算回路253であり、この変換処理を式で表現したのが前記の(式1)である。
前述したように、S−box252の各サイクルにおける出力x0、x1、x2、x3、の各々はそれぞれ8ビットデータであり、行列演算回路253における行列を適用した線形変換結果としてのy0,y1,y2,y3の各々もそれぞれ8ビットデータである。
以下、各サイクルにおける処理について説明する。
【0077】
図7に示す行列演算回路253は、1サイクル(1cycle)目に入力データ(din)としてx0を入力する。この時点で、論理積回路271〜274に入力されているイネーブル信号(en)を0にしておく。なお、図5〜図7には示されていないが、制御部によって制御がなされる。
【0078】
図7に示す最上段のラインL1では、入力データ(din)=x0がそのまま排他論理和部281を通過してレジスタr16に格納される。
2番目のラインL2でも、入力データ(din)=x0がそのまま排他論理和部282を通過してレジスタr17に格納される。
【0079】
3番目のラインL3と、4番目のラインL4では、入力データ(din)としてのx0と予め規定された値:2、3との有限体上での乗算処理が実行される。すなわち、乗算部285,286において以下の乗算が実行される。
x0・2、
x0・3、
これらを計算する。
これらの演算結果が、排他論理和部283,284を通過してレジスタr18,r19に格納される。
【0080】
なお、1番目のラインL1と、2番目のラインL2には乗算部が設定されていないが、入力データ(din)としてのx0と予め規定された値:1との有限体上での乗算処理が実行されていると同等である。
【0081】
2、3、4cycle目には、入力データ(din)としてx1、x2、x3をそれぞれ入力する。この2、3、4cycle目は、1cycle目とは異なり、論理積回路271〜274に入力されているイネーブル信号(en)を1にする。
この設定により、排他論理和部281〜284では、入力データまたはその乗算値と論理積回路271〜274からの出力との排他的論理和演算が実行され、その結果がレジスタr16〜r19に格納されることになる。
【0082】
このような処理によって、4cycle後のレジスタr16〜r19には、前記式(式1)に従って算出される結果が格納される。すなわち、
(dout0,dout1,dout2,dout3)
=(y0,y1,y2,y3)
となる。
このように、図7に示す行列演算回路253により、4サイクルの処理で上記(式1)に従った行列演算が実行されることになる。
【0083】
なお、図7を参照して説明した処理は、AESで採用されている巡回行列による行列演算による線形変換処理を実現する回路であるが、他の異なる行列を適用した線形変換処理も、回路の乗算部の設定と、接続構成等を変更することで実現できる。例えば、下記のようなアダマール行列を適用した行列演算を実現する回路は図8に示す行列演算回路290によって実現可能である。
【0084】
【数2】
【0085】
なお、式2に示す(x0、x1、x2、x3)は、図8に示す行列演算回路290に対する入力(S−boxからの出力)
(y0、y1、y2、y3)は、行列演算回路290の出力(線形変換結果)
4×4の行列は、行列演算回路290において適用する行列(線形変換行列)に対応する。
なお、4×4の線形変換行列の要素は16進数値として示している。
【0086】
図8に示すアダマール行列を適用した行列演算を実現する行列演算回路290と、図7に示す巡回行列を実現する行列演算回路253との異なる点は、例えば以下の構成である。
乗算部291〜294が式2に示す4×4のアダマール行列からなる線形変換行列の要素に対応した設定となっている。
論理積回路を、マルチプレクサ(Multiplexer)295〜298に変更して、各レジスタr16〜r19への入力を、2つの他レジスタからの出力か0、これら3つの内から1つ選択する設定としている。
これらの構成が変更点である。
【0087】
図4〜図8を参照して説明したHamalainenらの提案したSPN構造を用いたAES暗号構成の小型実装構成は、S−boxを1つのみに削減し、レジスタ数を最小限の設定とした構成を実現している。
【0088】
1ラウンドのラウンド演算に適用する必要なレジスタは、単純計算を行うと以下の通りとなる。ただしラウンド演算における処理データサイズとしてのブロックサイズnは、n=128ビットとする。
(1)ラウンド鍵格納用の128ビットレジスタ
(2)処理データ格納用の128ビットレジスタ
(3)線形変換行列を適用した行列演算において演算途中結果を格納するための32ビットレジスタ
データ演算部には、(2),(3)のレジスタが必要となり、128+32=160ビットレジスタが必要となると計算される。
【0089】
しかし、図5に示すHamalainenらの提案した構成では、160ビットより8ビット少ない152ビットレジスタ(=8ビットレジスタ×19)とすることに成功している。
Hamalainenらの提案した構成は、S−boxから行列演算回路へ入力が済んだ値(8ビット)が次のラウンドでは不要となる。このことに着目し、行列演算回路へS−boxから入力する32−bitのうち、はじめに入力する8−bit分のレジスタを行列演算回路内のレジスタと共有する構成とすることで、8−bit分のレジスタを削減したものである。
【0090】
[4.SPN構造の小型実装構成の一般化Feisel構造への適用と問題点について]
上述したように、HamalainenらはSPN構造の小型化を実現している。しかし、この小型化構成はSPN構造に対応した特有の構成であり、この小型実装構成を一般化Feisel構造へ適用しても十分な小型化の効果は得られない。以下、この問題点について説明する。なお、以下の説明では、一般化Feisel構造はFeisel構造を含む概念であるものとして説明する。
【0091】
図5を参照して説明したHamalainenらの提案構成を一般化Feistel構造を持つCLEFIA等のアルゴリズムを実行する構成に単純に適用すると、行列演算のために、行列の出力ビット長分のデータを格納するレジスタが必要になる。これは、一般化Feistel構造がSPN構造とは異なり、例えばラウンド関数内のF関数に入力した値を、次のラウンドでも利用する必要があるという処理シーケンスの根本的な違いに起因するものである。
【0092】
また、SPN構造では存在しなかったが、一般化Feistel構造では、ラウンド関数内において、F関数演算後に他のラインと排他的論理和を行う必要がある。そのため、排他的論理和を行うための回路も、一般化Feistel構造のラインのビット長分だけ必要となる。
【0093】
図9は、Hamalainenらの実装法を4−line一般化Feistel構造に適用した場合のデータ演算部回路の概要図を示す図である。図9では、先に図6を参照して説明したAESのデータパスと同様、一般化Feistel構造のラウンド関数終了時の置換動作や鍵スケジュール部は省略してある。
【0094】
なお、ラウンド演算における処理データサイズとしてのブロックサイズはnビットとする。先に図3を参照して説明したように、4−line一般化Feistel構造では、4つのライン各々にn/4ビットずつ入力され、順次転送される。
【0095】
図9中のレジスタ群301は、図6に示すレジスタ群261に対応する。ただし、4−line一般化Feistel構造に対応する図9のレジスタ群301は、(3/4)n−bit分のデータを保持するレジスタとラウンド関数終了時の置換動作と同様の処理を実現するマルチプレクサ等の組み合わせとして構成される。すなわち、レジスタ群301の下側のデータ演算部に1ライン分の(1/4)nビット分のデータが保持されるとすると、図9のレジスタ群301には、(3/4)n−bit分のデータを保持するレジスタが必要となる。
【0096】
なお、図9に示す4−line一般化Feistel構造を適用した暗号アルゴリズムのデータパス(演算実行回路)を適用して実行する演算は、図3に示す4−line一般化Feistel構造を適用した演算処理に対応する。
【0097】
この図9に示すデータパスを利用して図3に示す4−line一般化Feistel構造内のF関数を含むラウンド関数を実行することになる。
ラウンド関数内のF関数の具体例を図10に示す。
【0098】
図10に示すF関数は、先に図2を参照して説明したFeistel構造のF関数と同様、以下の構成要素を持つ。
(a)ラウンド鍵との排他的論理和演算を実行する排他的論理和演算部321、
(b)排他的論理和演算部321の出力に対して非線形変換処理を実行するS−boxからなる非線形変換部[S]322、
(c)非線形変換部[S]322の出力に対して、行列演算により線形変換の処理を行なう線形変換部[M]323、
これらの構成要素を持つ。
ただし、4−line一般化Feistel構造におけるF関数に対する入出力は、n/4ビットとなる。
【0099】
なお、線形変換部[M]323で実行する行列を適用した行列演算としての線形変換処理に適用する行列は、1行目の要素が(a,b,c,d)となる巡回行列を想定している。すなわち、以下の(式3)に示す行列である。
【0100】
【数3】
【0101】
先に図4〜図8を参照して説明したSPN構造を適用したAES暗号アルゴリズムの構成と比較するため、処理単位としてのブロック構成ビットnは、
n=128−bit
とする。
【0102】
図9に示す回路も、図6に示す回路と同様、S−boxは1つのみである。図9に示すS−box303である。このS−box303は図10に示すF関数内に設定される1つのS−boxの処理を1サイクルで実行する。サイクル毎に、順次、図10に示す各S−boxの処理を行うことになる。
【0103】
図10に示すように、F関数の1つのS−boxには、4−line一般化Feistel構造の1つのlineを伝送するn/4ビットの1/4、すなわちn/16ビットが入力され非線形変換処理が実行される。
図9に示すS−box303には、n/16ビットずつがサイクル毎に入力され非線形変換処理が実行される。
【0104】
なお、図9の構成では、レジスタ群301から1サイクル単位でS−box303の処理単位であるn/16ビットのデータを出力する設定であり、このn/16ビットをまず、排他的論理和部302でラウンド鍵の構成データと排他的論理和を行うS−boxで非線形変換を実行する構成としている。
【0105】
S−box303において非線形変換のなされたデータは、n/16ビットごとに1サイクル単位で次の行列演算回路304に入力される。行列演算回路304では所定の行列を適用した線形変換処理が実行されることになる。
【0106】
図9に示す4−line一般化Feistel構造を適用した暗号アルゴリズムのデータパス構成中、レジスタ群301を除く演算実行回路と、先に図6を参照して説明したSPN構造を利用したAES暗号処理を実行する演算回路構成とを比較する。
【0107】
図6に示す演算回路では、8ビットレジスタがr01〜r03、r16〜r19の7個であるのに対して、図9に示す演算回路では、8ビットレジスタがR0〜R7の8個である。すなわち、8−bitレジスタの数が1つ増えている。
また、排他的論理和演算回路の数も増加している。
【0108】
このように、Hamalainenらの提案構成を一般化Feistel構造に適用した場合、図9に示す演算回路のように、ブロック長分のレジスタに加え、1−line分のレジスタと排他的論理和演算回路が必要になってくる。
レジスタの増加は回路規模に大きく影響するため、ブロック長分のみのレジスタで構成できる実現できれば、そのほうが望ましい。
【0109】
なお、レジスタのゲートサイズは他のセルに比べて比較的大きなものとなり、レジスタ数の増加はゲートサイズに大きく影響する。そのため、小型化を実現するための一つの方向性として、レジスタの増加を抑えた実装法を考慮することが重要となる。
【0110】
[5.一般化Feistel構造の小型化の実現構成について]
次に、本発明の構成、すなわち、一般化Feistel構造の小型化の実現構成について説明する。
Hamalainenらの実装法を、一般化Feistel構造を持つ暗号アルゴリズムの実行構成に適用した場合には、前節で説明したようにレジスタと排他的論理和の回路が増加してしまい、小型化が実現されない。
【0111】
これは、SPN構造を適用した暗号アルゴリズムと、一般化Feistel構造を適用した暗号アルゴリズムが異なること、特に、一般化Feistel構造を適用した暗号アルゴリズムでは、行列演算結果を求めてから、他のラインとの排他的論理和を行う設定となっていることなどが要因であると考えられる。
すなわち、一般化Feistel構造を適用した暗号アルゴリズムでは、行列の途中結果を保持するレジスタと他のラインのデータを保持するレジスタの両方が必要となる。
【0112】
また、一般化Feistel構造を適用した暗号アルゴリズムでは、1つのラインのデータに対する行列演算が終了すると、次のサイクル(cycle)で新たなラインの行列の演算が始まる。このため、その1cycleの間に他のラインとの排他的論理和を行なう必要がある。そのため、1−line分の排他的論理和の回路が必要となる。
【0113】
以下に説明する本発明の構成では、排他的論理和演算における結合法則、すなわち、以下の式が成立することを利用し、演算順序を変更することで必要なレジスタの削減を実現している。
【0114】
【数4】
【0115】
上記式4は、排他的論理和演算の順番を変更しても同じ結果が得られることを意味している。本発明では、この法則を利用して、演算順序を変更することで必要なレジスタの削減を実現している。
【0116】
具体的には、他のラインのデータを保持しているレジスタに行列演算の途中結果を排他的論理和していくように演算順序を変更する。このように演算順序を変更することにより、行列演算の途中結果を保持する必要がなくなり、レジスタ数を削減することができる。
【0117】
図11に本発明の一実施例としてのデータパス、すなわち演算回路構成を示す。図11に示す演算回路は、先に図3を参照して説明した4−line一般化Feistel構造を適用した暗号アルゴリズムの実行回路である。具体的には、巡回行列演算部をアダマール行列演算部に置き換えることで、例えばCLEFIA暗号の実行回路として利用可能である。
【0118】
なお、図11に示す回路は、図9と同様、4−line一般化Feistel構造のラウンド関数終了時の置換動作の実行回路や鍵スケジュール部の構成については省略している。
【0119】
図11中のレジスタ群501は、図9に示すレジスタ群301に対応する。すなわち、レジスタ群501は、データ保持用のレジスタとラウンド関数終了時の置換動作の実行機能を持つ回路によって構成される。
しかし、図11中のレジスタ群501は、図9に示すレジスタ群301よりも少ないレジスタ数に設定されている。
【0120】
図9に示すレジスタ群301は、先に説明したように、(3/4)n−bit分のデータを保持するレジスタとラウンド関数終了時の置換動作の実行機能を持つ回路を含む構成として説明した。
これに対して、図11に示すレジスタ群501に含まれるレジスタは、n/2−bit分のデータを保持するレジスタのみである。
【0121】
処理データとしてのブロックのビット数をn、すなわち、4−line一般化Feistel構造を適用した暗号処理単位としてのブロックのビット数:nが、
n=128−bit
とする。
【0122】
この設定で、先に説明した図9の構成では、
レジスタ群301に、(3/4)n−bit=96−bit
レジスタ群301以外の演算部に8ビットレジスタが8個の8×8=64−bit
総計で、
96+64=160−bit
のレジスタが必要となっている。
【0123】
一方、本発明の手法を適用した図11の構成では、
レジスタ群501に、(1/2)n−bit=64−bit
レジスタ群501以外の演算部に8ビットレジスタが8個の8×8=64−bit
総計で、
64+64=128−bit
のレジスタが必要となっている。
【0124】
すなわち、SPN構造に対応するHamalainenらの実装法を4−line一般化Feistel構造に単純に適用した場合の図9の構成においては160−bitのレジスタが必要となるのに対して、本発明の構成である図11に示す4−line一般化Feistel構造を適用した演算回路では、128−bitのレジスタのみでよく、大幅なレジスタ削減が実現される。
【0125】
本発明の構成である図11に示す4−line一般化Feistel構造を適用した演算回路では、図9の構成に比較して32ビット分のレジスタを削減している。
以下、詳細に説明するが、図11に示す本発明の構成では、行列演算回路において、他ラインからの出力(E0、E1、E2、E3)を利用した演算を先行して実行することで、これらの出力データ(E0、E1、E2、E3)を行列演算期間中、保持するためのレジスタ(8×4=32ビット)を削減したことによる。
【0126】
以下、このレジスタ削減を実現させる演算シーケンスについて詳細に説明する。
レジスタ削減を実現するため、本発明の処理では、演算シーケンス、特に、線形変換を行う行列演算回路における行列を適用した演算シーケンスの設定を特別な設定とした。以下、図11に示す本発明に従ったデータパスである回路構成を適用した演算シーケンスの詳細について説明する。
【0127】
図12および以下に示す表1に図9に示すデータパスに従った行列演算回路304における行列演算シーケンスを示す。
さらに、図13および以下に示す表2に図11に示すデータパスに従った行列演算回路504における行列演算シーケンスを示す。
【0128】
【表1】
(表1)
【0129】
【表2】
(表2)
【0130】
図9に示す構成における行列演算シーケンスを示す表1(図12)と、
図11に示す構成における行列演算シーケンスを示す表2(図13)を用いて各処理の差異について説明する。
【0131】
まず、図9と図12(表1)を参照して、SPN構造に対応するHamalainenらの実装法を4−line一般化Feistel構造に単純適用した場合の行列演算シーケンスについて説明する。
【0132】
図9に示すデータパスの行列演算回路304に対して、S−box303からの出力として、順次、データ(x0,x1,x2,x3)が入力されて行列を適用した線形変換処理を行うものとする。
【0133】
行列演算回路304は、行列を適用した行列演算によって生成した出力(y0,y1,y2,y3)を排他的論理和演算部305に出力する。
排他的論理和演算部305では、行列演算回路304の出力(y0,y1,y2,y3)と、4−line一般化Feistel構造における他ラインからの出力(E0、E1、E2、E3)と排他的論理和される。他ラインからの出力(E0、E1、E2、E3)は、例えば前ラウンドにおけるラウンド演算の処理結果に相当する。
【0134】
なお、行列演算回路304に対する入力(x0,x1,x2,x3)の各々はn/16ビットであり、出力(y0,y1,y2,y3)と、他ラインからの出力(E0、E1、E2、E3)の各々もすべてn/16ビットのデータである。
【0135】
このとき、図9に記載のレジスタR0,R1,・・・,R7の格納値は、上記および図12の表1のように変化する。
【0136】
1サイクル(1cycle)目で、レジスタR0、R1、R2、R3に、行列演算回路304に対する入力要素x0に基づく行列演算結果の各要素が格納される。この時点で、論理積回路313に入力されているイネーブル信号(en)は0に設定され、入力要素x0に基づく乗算部311の乗算結果がレジスタR0、R1、R2、R3に格納される。すなわち、
レジスタR0の格納値:d・x0、
レジスタR1の格納値:c・x0、
レジスタR2の格納値:b・x0、
レジスタR3の格納値:a・x0、
これらのデータが各レジスタに格納される。
【0137】
その後、2サイクル目に行列演算回路304に入力要素x1が入力される。2〜4サイクル目では、論理積回路313に入力されるイネーブル信号(en)は1に設定され、排他論理和演算部312において、入力要素x1の乗算部311の乗算結果と、前サイクルでレジスタR0、R1、R2、R3に格納された値との排他的論理和演算が実行され、その結果がレジスタR0、R1、R2、R3に格納される。
また、この2サイクル目において、他ラインからの出力要素E0がレジスタR7に格納される。
【0138】
3サイクル目に行列演算回路304に入力要素x2が入力される。2〜4サイクル目では、論理積回路313に入力されるイネーブル信号(en)は1に設定され、排他論理和演算部312において、入力要素x2の乗算部311の乗算結果と、前サイクルでレジスタR0、R1、R2、R3に格納された値との排他的論理和演算が実行され、その結果がレジスタR0、R1、R2、R3に格納される。
また、この3サイクル目において、他ラインからの出力要素E0がレジスタR6に格納され、E1がレジスタR7に格納される。
【0139】
4サイクル目では、行列演算回路304に入力要素x3が入力される。入力データ(x0,x1,x2,x3)の入力が完了し、この4サイクル目において、行列演算結果(y0,y1,y2,y3)がレジスタR0、R1、R2、R3に格納される。
【0140】
その次の5サイクル目では、他ラインからの出力(E0、E1、E2、E3)と、行列演算回路304における行列を適用した行列演算結果(=線形変換結果)である(y0,y1,y2,y3)とが、排他的論理和演算部305において排他的論理和されて、その結果としての値が、レジスタR4、R5、R6、R7に格納される。
このレジスタ格納値、すなわち、下記式(式5)に示すデータが図9に示すライン306を介して次のラウンド演算の利用データとしてレジスタ群301に入力される。
【0141】
【数5】
【0142】
なお、上記(式5)に示す値は、図3に示すラウンド間の接続部のラウンド出力データ(D)に相当する。
また、この5サイクル目では、次の行列演算回路304への入力値(x'0,x'1、x'2,x'3)の始めの要素x'0に対する演算がレジスタR0、R1、R2、R3に格納される。
【0143】
次に、図11に示す本発明に従ったデータパスを利用した行列演算回路504における行列演算のサイクル単位の遷移処理について、図11と図13(表2)を参照して説明する。
【0144】
図11に示すデータパスの行列演算回路504に対して、図9を参照して説明したと同様のS−box503からの出力として、順次、(x0,x1,x2,x3)が入力され、行列を適用した線形変換処理を行うものとする。
【0145】
この図11に示す構成を用いた行列演算を行うと、図13(表2)に示すように、4サイクル目においてレジスタR0、R1、R2、R3に、次のラウンド演算の利用データ、すなわち、
【0146】
【数6】
【0147】
なお、上記(式6)に示す値が格納される。これらの値は、第5サイクルでレジスタR4、R5、R6、R7に格納され、図11に示すライン506を介して次のラウンド演算の利用データとしてレジスタ501に入力される。
図11に示す構成は、図9に示す構成よりレジスタ数が削減された構成であるが、結果としては図9に示すと同様の演算処理を実現している。ただし、演算シーケンスが異なっている。
各サイクルにおける処理について説明する。
【0148】
図11に示すデータパスを利用した処理では、例えば前ラウンドにおけるラウンド演算の処理結果に相当する他ラインからの出力(E0、E1、E2、E3)を、レジスタ501からの出力ライン521を介してレジスタR7、R6、R5に、順次格納する。図13(表2)に示す1サイクル目の1つ前のサイクル(0サイクル)において、
レジスタR5にはE0、
レジスタR6にはE1、
レジスタR7にはE2、
これらのデータが格納された状態に設定される。
【0149】
1サイクル目において、これらのレジスタ格納値E0、E1、E2と、レジスタ群501から出力ライン521を介した新たな出力値E3を加えた出力(E0、E1、E2、E3)がマルチプレクサ513を介して、排他的論理和演算部512に入力される。なお、これらの演算制御は、例えば図示しない制御部やクロック入力情報に基づく制御によって行われる。
【0150】
排他的論理和演算部512では、これらの出力値(E0、E1、E2、E3)と、入力要素x0に基づく乗算部311の乗算結果、すなわち、
d・x0、
c・x0、
b・x0、
a・x0、
これらの各値との排他的論理和演算が実行される。この排他的論理和演算結果が、レジスタR0、R1、R2、R3に格納される。
【0151】
すなわち、
レジスタR0には、レジスタR6に格納された値E1が、マルチプレクサm0を介して排他論理和演算部512に入力されて、d・x0との排他論理和結果が格納される。
レジスタR1には、レジスタR7に格納された値E2が、マルチプレクサm1を介して排他論理和演算部512に入力されて、c・x0との排他論理和結果が格納される。
レジスタR2には、レジスタ群からライン521を介して出力される出力値E3が、マルチプレクサm2を介して排他論理和演算部512に入力されて、b・x0との排他論理和結果が格納される。
レジスタR3には、レジスタR5に格納された値E0が、マルチプレクサm3を介して排他論理和演算部512に入力されて、a・x0との排他論理和結果が格納される。
すなわち、以下の(式7)に示す各値がレジスタR0、R1、R2、R3に格納される。
【0152】
【数7】
【0153】
なお、マルチプレクサ513(m0〜m3)は、2入力から選択された1つの入力を出力するセレクタと同様の処理を行う。
第1サイクルでは、レジスタR7、R6、R5の格納値、ライン521の出力値を出力するように設定される。なお、これらの制御は図示しない制御部の制御によって行われる。
【0154】
このように、本発明の構成では、図11に示す行列演算回路504に対するS−box503からの第1サイクルにおける入力x0の入力タイミングにおいて、例えば前ラウンドにおけるラウンド演算の処理結果に相当する他ラインからの出力(E0、E1、E2、E3)との排他的論理和演算を実行し、その結果をレジスタR0、R1、R2、R3に格納する。
【0155】
このように本発明の構成では、他ラインからの出力(E0、E1、E2、E3)との排他論理和演算処理を先行して実行する。この結果、4サイクルを要する行列演算期間が完了するまで他ラインからの出力(E0、E1、E2、E3)を保持する必要がなくなる。この演算シーケンスの変更処理によって必要なレジスタ数の削減を実現している。
【0156】
その後、2サイクル目に行列演算回路504に入力要素x1が入力される。2〜4サイクル目では、マルチプレクサ513(m0〜m3)は、レジスタR0、R1、R2、R3の格納値を選択出力するように制御される。
この結果、排他論理和演算部512において、入力要素x1の乗算部511の乗算結果と、前サイクルでレジスタR0、R1、R2、R3に格納された値との排他的論理和演算が実行され、その結果がレジスタR0、R1、R2、R3に格納される。
また、この2サイクル目において、他ラインからの出力要素E'0がレジスタR7に格納される。
【0157】
3サイクル目に行列演算回路504に入力要素x2が入力される。排他論理和演算部512において、入力要素x2の乗算部511の乗算結果と、前サイクルでレジスタR0、R1、R2、R3に格納された値との排他的論理和演算が実行され、その結果がレジスタR0、R1、R2、R3に格納される。
また、この3サイクル目において、他ラインからの出力要素E'0がレジスタR6に格納され、E'1がレジスタR7に格納される。
【0158】
4サイクル目では、行列演算回路504に入力要素x3が入力される。入力データ(x0,x1,x2,x3)の入力が完了し、この4サイクル目において、レジスタR0、R1、R2、R3には、行列演算結果(y0,y1,y2,y3)と他ラインからの出力(E0、E1、E2、E3)との排他論理和結果が格納されることになる。
【0159】
その次の5サイクル目では、次の他ラインからの出力(E'0、E'1、E'2、E'3)がレジスタR7、R6、R5の格納値、ライン521の出力として、排他論理和演算部512に入力される。
排他論理和演算部512は、これらの入力値と、行列演算回路504に対する新たな入力x'0と乗算部511での乗算結果との排他論理和結果を算出して、レジスタR0、R1、R2、R3に格納する。
この時点で、レジスタR0、R1、R2、R3に格納された値は、レジスタR4、R5、R6、R7に格納される。
このレジスタ格納値、すなわち、下記式(式8)に示すデータが図10に示すライン506を介して次のラウンド演算の利用データとしてレジスタ群501に入力される。
【0160】
【数8】
【0161】
このように、本発明に従った構成では、行列の演算処理に際して他ラインからの出力(E0、E1、E2、E3)との排他的論理和演算を先行して実行することにより、他ラインからの出力(E0、E1、E2、E3)を格納するレジスタと、行列演算の途中結果を格納するレジスタを、個別に設定した独立のレジスタとする必要性をなくして、これらのレジスタの共有化を行うことで、必要な総レジスタ数を削減している。
【0162】
[6.本発明の構成による効果および変形例について]
図11に示す本発明に従った一般化Feistel構造を適用した暗号処理を実行するデータパスでは、上述したように、先行した処理結果をラウンド演算における行列演算の最初のサイクル(1サイクル目)で排他論理和演算処理を実行してしまう構成としている。
【0163】
すなわち、例えば前ラウンドにおけるラウンド演算の処理結果に相当する他ラインからの出力(E0、E1、E2、E3)との排他的論理和演算を先行して実行する。
図11を参照して説明したように、行列演算回路504における行列演算の最初の処理として実行する第1サイクルにおいて、他ラインからの出力(E0、E1、E2、E3)をレジスタ等からマルチプレクサ513を介して排他論理和演算部512に先行して入力させて、行列演算回路504に対する最初の入力値(x0)の乗算部511での乗算結果(d・x0等)と排他論理和処理を実行する。
【0164】
このように、本発明の構成では、1−line分(実施例では(n/16)×4)のマルチプレクサ(Multiplexer)を導入することで、図9に示す構成において必要であった1−line分のレジスタと1−line分の排他的論理和と1−line分の論理積の回路をなくすことができる。図11に示す構成では、これらの差分だけ、小型化を行うことができる。
また、この小型化に伴い、低消費電力化も期待できる。
特に、レジスタのゲートサイズは、他のセルに比べて比較的大きなものとなるため、1−line分のレジスタを削減できたことは小型化に特に寄与する。
【0165】
なお、上述した実施例では、本発明の適用構成の代表例として、4−line一般化Feistel構造への適用例について説明した。しかしながら、図11、図13(表1)を参照して説明した処理シーケンス、すなわち、他ラインからの出力値を先行して行列演算に適用することは、4−line以外の一般化Feistel構造やFeistel構造においても適用可能であり、図11を参照して説明したと同様のレジスタ他の回路構成の削減が実現される。すなわち、本発明は、4−line一般化Feistel構造のみでなく、ラウンド関数内部を変形、拡張された構造についても適用可能であり、2−lineのFeistel構造や、任意のx(xは2以上の自然数)の、x−line一般化Feistel構造にも適用できる。
【0166】
また、上述した実施例では、行列演算回路において適用する行列を巡回行列とした例について説明したが、行列演算回路において適用する行列は巡回行列に限らず、例えばアダマール行列など、その他の形式の行列を適用することも可能である。
【0167】
さらに、行列演算回路において適用する行列は、4×4行列のみでなく、
任意のx×x行列、ただし、xは2以上の自然数、
このような様々な行列の適用が可能である。
【0168】
また、先に図2を参照して説明したF関数を持つ構成に限らず、行列演算後に非線形変換を含まないラウンド関数を実行するアルゴリズムであれば、本発明の構成は適用可能であり、同様の小型化の効果が期待できる。
【0169】
なお、上述した実施例で説明した構成は、4−line一般化Feistel構造におけるtype−2一般化Feistel構造の例であるが、本発明は、この他のtype−1や、type−3の一般化Feistel構造に対しても適用可能であり、同様の効果が期待できる。
【0170】
2ラインのFeistel構造に対して本発明を適用したデータパスとしての回路構成例を図14に示す。
図14に示すデータパスにおいて、例えば前ラウンドの演算結果としての他ラインからの出力(E0、E1、E2、E3)をレジスタR4、R5、R6、R7に格納し、行列第1演算回路604における行列演算の最初の処理らサイクル(1サイクル目)においてS−box603からの入力値x0と乗算部611における乗算結果との排他論理和を実行してその結果をレジスタR0、R1、R2、R3に格納する。
このように、先に図11を参照して説明したと同様の処理シーケンスで行列演算を実行することが可能であり、この処理により、レジスタ数の削減などによりハードウェア構成を小型化することが可能となる。
【0171】
具体的には、図14の構成とすることで、例えば図9と同様の構成に従って2ラインのFeistel構造のデータパスを設定した場合にn/2−bit分必要であった行列演算用のレジスタが不要となり、n−bit分のレジスタのみで全体を構成できる。
【0172】
なお、図14に示す2ラインのFeistel構造とした場合でも、行列演算回路604において適用する行列は巡回行列、アダマール行列等が利用可能であり、またx×x(ただしx≧2の整数)の任意の行列が利用できる。また、図2を参照して説明したF関数を持つ構成に限らず、行列演算後に非線形変換を実行しないラウンド関数であれば、本発明の適用が可能である。
【0173】
[7.暗号処理装置のICカードとしての構成例について]
最後に、上述した実施例に従った暗号処理を実行する暗号処理装置としてのICモジュール700の構成例を図15に示す。上述の処理は、例えばPC、ICカード、リーダライタ、その他、様々な情報処理装置において実行可能であり、図15に示すICモジュール700は、これら様々な機器に構成することが可能である。
【0174】
図15に示すCPU(Central processing Unit)701は、暗号処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ702は、CPU701が実行するプログラム、あるいは演算パラメータなどの固定データを格納するROM(Read-Only-Memory)、CPU701の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるRAM(Random Access Memory)等からなる。また、メモリ702は暗号処理に必要な鍵データや、暗号処理において適用する変換テーブル(置換表)や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【0175】
暗号処理部703は、例えば図11や図14を参照して説明した暗号処理構成、すなわち、例えば一般化Feistel構造や、Feistel構造を適用した共通鍵ブロック暗号処理アルゴリズムに従った暗号処理、復号処理を実行する。
【0176】
なお、ここでは、暗号処理手段を個別モジュールとした例を示したが、このような独立した暗号処理モジュールを設けず、例えば暗号処理プログラムをROMに格納し、CPU701がROM格納プログラムを読み出して実行するように構成してもよい。
【0177】
乱数発生器704は、暗号処理に必要となる鍵の生成などにおいて必要となる乱数の発生処理を実行する。
【0178】
送受信部705は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ICモジュールとのデータ通信を実行し、ICモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【0179】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が該実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【0180】
なお、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。
【0181】
例えば、プログラムは記録媒体としてのハードディスクやROM(Read Only Memory)に予め記録しておくことができる。あるいは、プログラムはフレキシブルディスク、CD−ROM(Compact Disc Read Only Memory),MO(Magneto optical)ディスク,DVD(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的あるいは永続的に格納(記録)しておくことができる。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することができる。
【0182】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送したり、LAN(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送し、コンピュータでは、そのようにして転送されてくるプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【0183】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【0184】
上述したように、本発明の一実施例の構成によれば、一般化Feistel構造を適用した暗号処理構成の小型化や省電力化が実現される。
具体的には、データを複数ラインに分割入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する一般化Feistel構造を適用した暗号処理構成において、第1ラインのデータに対する行列を適用した線形変換処理を実行する行列演算実行部が行列演算の実行サイクル中、最初のサイクルにおいて行列演算過程データと第2ラインのデータとの演算を実行する。本構成により、第2ラインのデータ保持用のレジスタと第1ラインの行列演算途中結果保持用のレジスタの共有化が可能となり、総レジスタ数の削減、小型化が実現される。さらに回路構成の小型化、エレメント数の削減により電力消費量の削減も可能となる。
【符号の説明】
【0185】
111 鍵スケジュール部
112 データ暗号化部
120 F関数
121 排他的論理和演算部
122 非線形変換部
123 線形変換部
201 非線形変換部
202 Shift Low実行部
203 線形変換部
204 排他的論理和演算部
251 鍵生成部
252 S−box
253 行列演算回路
254 排他的論理和演算部
271〜274 論理積回路
281〜284 排他的論理和演算部
285〜286 乗算部
290 行列演算回路
291〜294 乗算部
295〜298 マルチプレクサ
301 レジスタ群
302 排他的論理和演算部
303 S−box
304 行列演算回路
305 排他的論理和部
311 乗算部
312 排他的論理和部
313 論理積回路
321 排他的論理和演算部
322 非線形変換部[S]
323 線形変換部[M]
501 レジスタ群
502 排他的論理和演算部
503 S−box
504 行列演算回路
511 乗算部
512 排他的論理和部
513 マルチプレクサ
603 S−box
604 行列演算回路
611 乗算部
613 マルチプレクサ
700 ICモジュール
701 CPU(Central processing Unit)
702 メモリ
703 暗号処理部
704 乱数生成部
705 送受信部
【特許請求の範囲】
【請求項1】
データ処理対象となるデータブロックの構成ビットを複数のラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインの第1ラインのデータに対する変換データを生成し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行する演算部と、
前記演算部の演算結果を保持するレジスタを有し、
前記演算部は、前記レジスタから順次、データを取得して取得データ順の演算を実行して演算結果を前記レジスタに格納する構成であり、
前記演算部は、
前記第1ラインのデータに対する行列を適用した線形変換を実行する行列演算実行部を有し、
前記行列演算実行部は、
前記第1ラインのデータに対する行列演算の実行サイクル中、最初のサイクルの行列演算の実行に際して前記第2ラインのデータとの演算を実行する暗号処理装置。
【請求項2】
前記行列演算実行部は、
前段の非線形変換部から順次出力される複数の単位データに対する行列演算を複数サイクルで実行する構成であり、前記複数サイクルの最初のサイクルで、前記非線形変換部から入力する単位データの行列演算に併せて前記第2ラインのデータとの演算を実行する請求項1に記載の暗号処理装置。
【請求項3】
前記暗号処理装置は、
前記第1ラインのデータに対する行列演算に必要な演算サイクルの完了後に前記第2ラインのデータとの演算を実行する場合に必要となる前記第2ラインのデータ保持用の独立したレジスタを削減し、
前記第1ラインのデータに対する行列演算の途中結果の保持用レジスタを前記第2ラインのデータ保持用のレジスタとして利用した構成を有する請求項1に記載の暗号処理装置。
【請求項4】
前記行列演算実行部は、
前記第1ラインのデータに対する行列演算を実行する初期サイクルにおいて、前記第1ラインに対する行列演算過程データと前記第2ラインのデータとの排他的論理和演算を実行する請求項1に記載の暗号処理装置。
【請求項5】
前記行列演算実行部は、
巡回行列またはアダマール行列を適用した行列演算を実行する構成である請求項1に記載の暗号処理装置。
【請求項6】
前記暗号処理部は、前記ラウンド関数の実行部として、
非線形変換処理を実行する非線形変換部と、行列を適用した線形変換処理を実行する線形変換部としての行列演算実行部を有する請求項1に記載の暗号処理装置。
【請求項7】
前記行列演算実行部は、
前記非線形変換部としてのS−boxの出力を、順次入力して入力データに対する行列演算を1サイクル処理として実行する請求項1に記載の暗号処理装置。
【請求項8】
前記暗号処理部の実行する暗号処理は、Feistel構造または一般化Feistel構造を適用した暗号処理である請求項1に記載の暗号処理装置。
【請求項9】
前記暗号処理部の実行する暗号処理は、CLEFIA暗号アルゴリズムに従った暗号処理である請求項1に記載の暗号処理装置。
【請求項10】
暗号処理装置において暗号処理を実行する暗号処理方法であり、
暗号処理部が、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第1ラインのデータの変換処理を実行し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行し、
前記第1ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第2ラインのデータとの演算を実行する暗号処理方法。
【請求項11】
暗号処理装置において暗号処理を実行させるプログラムであり、
暗号処理部に、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行させる暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第1ラインのデータの変換処理を実行し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行させ、
前記第1ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第2ラインのデータとの演算を実行させるプログラム。
【請求項1】
データ処理対象となるデータブロックの構成ビットを複数のラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理部を有し、
前記暗号処理部は、
前記複数ラインの第1ラインのデータに対する変換データを生成し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行する演算部と、
前記演算部の演算結果を保持するレジスタを有し、
前記演算部は、前記レジスタから順次、データを取得して取得データ順の演算を実行して演算結果を前記レジスタに格納する構成であり、
前記演算部は、
前記第1ラインのデータに対する行列を適用した線形変換を実行する行列演算実行部を有し、
前記行列演算実行部は、
前記第1ラインのデータに対する行列演算の実行サイクル中、最初のサイクルの行列演算の実行に際して前記第2ラインのデータとの演算を実行する暗号処理装置。
【請求項2】
前記行列演算実行部は、
前段の非線形変換部から順次出力される複数の単位データに対する行列演算を複数サイクルで実行する構成であり、前記複数サイクルの最初のサイクルで、前記非線形変換部から入力する単位データの行列演算に併せて前記第2ラインのデータとの演算を実行する請求項1に記載の暗号処理装置。
【請求項3】
前記暗号処理装置は、
前記第1ラインのデータに対する行列演算に必要な演算サイクルの完了後に前記第2ラインのデータとの演算を実行する場合に必要となる前記第2ラインのデータ保持用の独立したレジスタを削減し、
前記第1ラインのデータに対する行列演算の途中結果の保持用レジスタを前記第2ラインのデータ保持用のレジスタとして利用した構成を有する請求項1に記載の暗号処理装置。
【請求項4】
前記行列演算実行部は、
前記第1ラインのデータに対する行列演算を実行する初期サイクルにおいて、前記第1ラインに対する行列演算過程データと前記第2ラインのデータとの排他的論理和演算を実行する請求項1に記載の暗号処理装置。
【請求項5】
前記行列演算実行部は、
巡回行列またはアダマール行列を適用した行列演算を実行する構成である請求項1に記載の暗号処理装置。
【請求項6】
前記暗号処理部は、前記ラウンド関数の実行部として、
非線形変換処理を実行する非線形変換部と、行列を適用した線形変換処理を実行する線形変換部としての行列演算実行部を有する請求項1に記載の暗号処理装置。
【請求項7】
前記行列演算実行部は、
前記非線形変換部としてのS−boxの出力を、順次入力して入力データに対する行列演算を1サイクル処理として実行する請求項1に記載の暗号処理装置。
【請求項8】
前記暗号処理部の実行する暗号処理は、Feistel構造または一般化Feistel構造を適用した暗号処理である請求項1に記載の暗号処理装置。
【請求項9】
前記暗号処理部の実行する暗号処理は、CLEFIA暗号アルゴリズムに従った暗号処理である請求項1に記載の暗号処理装置。
【請求項10】
暗号処理装置において暗号処理を実行する暗号処理方法であり、
暗号処理部が、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行する暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第1ラインのデータの変換処理を実行し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行し、
前記第1ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第2ラインのデータとの演算を実行する暗号処理方法。
【請求項11】
暗号処理装置において暗号処理を実行させるプログラムであり、
暗号処理部に、データ処理対象となるデータブロックの構成ビットを複数ラインに分割して入力し、各ラインの伝送データに対してラウンド関数を適用したデータ変換処理を繰り返して実行させる暗号処理ステップを有し、
前記暗号処理ステップにおいて、前記複数ラインを構成する第1ラインのデータの変換処理を実行し、生成した変換データに対して前記第1ラインと異なる第2ラインのデータとの演算を行い、該演算結果を次ラウンドの入力データとする演算を繰り返し実行させ、
前記第1ラインのデータの変換データ生成処理において実行する行列演算処理の実行サイクル中、最初のサイクルの行列演算処理に際して前記第2ラインのデータとの演算を実行させるプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【公開番号】特開2012−123259(P2012−123259A)
【公開日】平成24年6月28日(2012.6.28)
【国際特許分類】
【出願番号】特願2010−274807(P2010−274807)
【出願日】平成22年12月9日(2010.12.9)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】
【公開日】平成24年6月28日(2012.6.28)
【国際特許分類】
【出願日】平成22年12月9日(2010.12.9)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】
[ Back to top ]