(57)【要約】本発明によるAES Rijndael MixColumns変換を遂行するための簡素化された論理回路は、変換行列の一連の各行とそれに先行する行との間の共通の関係を利用する。本発明によると、（ｍ×ｎ）行列と（１×ｎ）或いは（ｍ×１）行列との乗法を遂行するための論理回路が提供される。ここで、ｍは行の数を表し、ｎは列の数を表し、ｎ個の要素の一連の各行ｍはそれに先行する行の所定の行置換から成る。本発明によると、この論理回路は、ｎ個の乗法回路と、ｎ個の論理回路と、これら論理回路から論理出力を受け取るためのｎ個のレジスタと、各レジスタの内容をこれら論理回路の入力のある選択された一つに上述の行列の一連の行間の共通の関係に対応する帰還プランに従ってルーティングするための帰還論理と、これらｎ個の乗法回路の各々に前記（１×ｎ）或いは（ｍ×１）行列内の各要素を入力として次々と供給するための制御手段と、を備える。
2005529365.tif 000002
【特許請求の範囲】
【請求項１】
（ｍ×ｎ）行列と（１×ｎ）或いは（ｍ×１）行列とを乗算するための論理回路であって、ｍは行の数を表し、ｎは列の数を表し、ｎ個の要素を有する一連の各行ｍは先行する行の所定の行置換から成り、
各々が一つの入力と出力を有し、前記入力の値に所定の被乗数を乗じた値を返すためのｎ個の乗法回路と、
各々が論理出力を提供するために第一の入力と第二の入力の所定の論理結合を実行し、前記第一の入力は前記ｎ個の乗法回路の対応する一つの前記出力に結合されるｎ個の論理回路と、
前記論理出力を受け取るためのｎ個のレジスタと、
前記各レジスタの内容を前記所定の行置換に対応する帰還プランに従って前記第二の入力のある選択された一つにルーティングするための帰還論理と、
前記ｎ個の乗法回路の各々に前記（１×ｎ）或いは（ｍ×１）行列内の各要素を入力として次々と供給するための制御手段と
を備えることを特徴とする論理回路。
【請求項２】
前記帰還論理は、前記所定の行置換に対応する帰還プランとして、行シフトを提供することを特徴とする請求項１記載の論理回路。
【請求項３】
前記行シフトは、要素の１位置だけ右へのシフトから成ることを特徴とする請求項２記載の論理回路。
【請求項４】
前記ｎ個の論理回路は、各々、前記第一の入力と前記第二の入力との排他的論理和結合を実行するように構成されることを特徴とする請求項１記載の論理回路。
【請求項５】
前記所定の被乗数の各々は、AES Rijndael ミックスカラム変換関数内の要素の一つに対応することを特徴とする請求項１記載の論理回路。
【請求項６】
前記ｍの数は４とされ、前記ｎの数は４とされ、前記第一の乗法回路に対する被乗数は０２とされ、前記第二の乗法回路に対する被乗数は０３とされ、前記第三の乗法回路に対する被乗数は０１とされ、前記第四の乗法回路に対する被乗数は０１とされることを特徴とする請求項５記載の論理回路。
【請求項７】
前記ｍの数は４とされ、前記ｎの数は４とされ、前記第一の乗法回路に対する被乗数は０Eとされ、前記第二の乗法回路に対する被乗数は０Bとされ、前記第三の乗法回路に対する被乗数は０Dとされ、前記第四の乗法回路に対する被乗数は０９とされることを特徴とする請求項５記載の論理回路。
【請求項８】
前記４個の被乗数は請求項６における数と請求項７における数との間で切換え可能であることを特徴とする請求項６或いは７記載の論理回路。
【請求項９】
前記制御手段は、ｎ或いはｍ回の各動作サイクルにおいて、前記ｎ個の乗法回路の各々に、前記（１×ｎ）或いは（ｍ×１）行列内の各要素を入力として次々と供給するように構成されることを特徴とする請求項1記載の論理回路。
【請求項１０】
前記ｎ個の乗法回路の各々、前記ｎ個の論理回路の各々、及び前記ｎ個のレジスタの各々は、少なくとも８ビット幅とされることを特徴とする請求項1記載の論理回路。
【請求項１１】
前記制御回路は、更に、各ｎ番目のサイクルの後に、前記ｎ個のレジスタの内容を前記論理回路からの出力として供給するための手段を含むことを特徴とする請求項1記載の論理回路。
【請求項１２】
前記制御回路は、更に、前記第一の計算サイクルの前に、前記レジスタの各々をリセットするための手段を含むことを特徴とする請求項1記載の論理回路。
【請求項１３】
ｎ個の要素の一連の各行ｍは、直前の行の所定の行置換から成ることを特徴とする請求項1記載の論理回路。
【請求項１４】
請求項1乃至１３のいずれかに記載の論理回路を組み込むことを特徴とするAES ミックスカラム変換回路。
【請求項１５】
前記ミックスカラム変換を遂行するために請求項1乃至１３のいずれかに記載の論理回路を組み込むことを特徴とするAES暗号化及び復号化の少なくとも一方を行うエンジン。
【請求項１６】
実質的に添付の図面を参照しながら説明されたような装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、AES(Advanced Encryption Standard）アルゴリズムを実現するための方法及び装置、より具体的には、このアルゴリズムの暗号化及び復号化ラウンドのおのおのにおけるAES MixColumns（ミックスカラム）変換を構成する行列乗法演算を遂行するための方法及び装置に係る。
【背景技術】
【０００２】
本発明は、これに限定されるものではないが、とりわけ、暗号デバイス、例えば、プロセッサ及びメモリ資源に制約があり、暗号アルゴリズムの多くの演算が専用のASIC或いはFPGAハードウェアにて遂行されるようなスマートカード或いは他のデバイス内に実装される暗号デバイスに用いるのに適する。
【０００３】
AESアルゴリズムは、安全なやり方にて伝送されることが必要とされるデータの暗号化に対して広範な用途を有する。このアルゴリズムは、一例として、パーソナル及びファイナンシャル情報の少なくとも一方をスマートカードからカード読出しデバイスに伝送する際に用いられる。カード上に格納されている機密データをカードから取り出す際には、カードから取り出されたデータが不正な第三者によって傍受され、読み出されることがないように、データを暗号化された形式にて取り出すことが要求される。そして、カードから取り出されたデータの復号化は、許可された者によって可能でないことが要求される。
【０００４】
同様にして、カードリーダからカード内に格納するために供給されるデータは、カードに暗号形式にてパスされ、カードによって、格納及びその後の取り出しのために、復号化されることを要求される。
【０００５】
AESアルゴリズムは、従来技術によるプロセッサ及びメモリ回路を採用する従来のコンピュータシステム内に実現することは比較的簡単ではあるが、スマートカードに応用しようとすると、プロセッサ及びメモリ資源が極端に限られているために、多くの機能を専用のハードウェア、例えば、ASIC或いはFPGA内に実行することを要求される。
【発明の開示】
【０００６】
従って、AESアルゴリズムにおいて要求される手続をハードウェア資源の使用を最小限に抑えることができるようなやり方にてハードウェアにて実現することに対する要請が存在する。
【０００７】
本発明の一つの目的は、標準のAES（Rijndael）暗号アルゴリズムにおいて暗号化及び復号化の両方に対して展開されるミックスカラム変換を実行するための適当な回路を提供することにある。
【０００８】
一つの態様によると、本発明は、（ｍ×ｎ）行列と（１×ｎ）或いは（ｍ×１）行列との乗算のための論理回路を提供する。ここで、ｍは、行の数を表し、ｎは、列の数を表し、ｎ個の要素の一連の各行ｍは、先行する行の所定の行置換から成る。本発明によると、この回路は、
各々が一つの入力と出力を有し、前記入力の値に所定の被乗数を乗じた値を返すためのｎ個の乗法回路と、
各々が論理出力を提供するために第一の入力と第二の入力の所定の論理結合を実行するための、第一の入力はこれらｎ個の乗法回路の対応する一つの出力に結合される、ｎ個の論理回路と、
この論理出力を受け取るためのｎ個のレジスタ（８０...８３）と、
これら各レジスタの内容を前記所定の行置換に対応する帰還プランに従って前記第二の入力のある選択された一つにルーティングするための帰還論理と、
前記ｎ個の乗法回路の各々に前記（１×ｎ）或いは（ｍ×１）行列内の各要素を入力として次々と供給するための制御手段と、を備える。
【０００９】
以下では、本発明の幾つかの実施例について、単に例示として、添付の図面を参照しながら説明する。
【発明を実施するための最良の形態】
【００１０】
図１には平文から暗号文に暗号化するためのAESアルゴリズムが示されている。このAESアルゴリズムは、入力データの一連の１２８ビットブロックに関して動作する１２８ビットキーを用いて実現されることも、１９２ビットキーを用いて実現されることも、或いは２５６ビットキーを用いて実現されることもあるが、本発明はこれら全ての実現に適用できるものである。以下では、図１について、１２８ビットキーを用いる基本的実現の背景内で説明する。
【００１１】
最初に、初期ラウンド１５において、入力平文１０の最初の１２８ビットブロックが元の１２８ビットキー１２と排他的論理和結合（XOR-combined）１１される。次にこの初期ラウンド１５からの出力１３が、暗号化ラウンド２８において、複数の変換段を幾度もパスされるが、この暗号化ラウンド２８は、サブバイト(SubBytes)変換２０、シフト行(ShiftRows)変換２１、及びミックスカラム(MixColumns)変換２２から構成されるが、これは定義されたAESアルゴリズムに依存する。
【００１２】
ミックスカラム変換２２からの出力は、次に、新たな１２８ビットキー２６と排他的論理和結合２３されるが、この新たな１２８ビットキー２６は、元のキー１２から生成される。この排他的論理和結合２３からの出力は、暗号化ラウンド２８に帰還され、更らにある所定の回数だけこの暗号化ラウンド２８内をパスされるが、この回数はこのアルゴリズムの特定の実現に依存する。
【００１３】
暗号化ラウンド２８を通じての各一連の反復に対して、新たなラウンドに対するキー２６’がAESラウンドキースケジュールに従って生成される。
【００１４】
この暗号化ラウンド２８の反復回数（ＮＲ−１）は、１２８ビット暗号キーが用いられる場合は９回、１９２ビット暗号キーが用いられる場合は１１回、２５６ビット暗号キーが用いられる場合は１３回となる。
【００１５】
暗号化ラウンド２８が要求された回数（ＮＲ−１）だけ遂行されると、その後、判定ブロック２４の制御下で、最終ラウンドＮＲへと入る。この最終ラウンド３０は、もう一つのサブバイト変換３１と、もう一つのシフト行変換３２と、これに続く、この結果と先のラウンドキーから生成された最終ラウンドキー３６との排他的論理和結合から構成される。これからの出力は、この暗号化アルゴリズムの暗号文出力３９を構成する。
【００１６】
本発明は、とりわけ、ミックスカラム変換２２の遂行に係る。ラウンド２８と３０を通じて、処理される１２８ビットブロックは、便宜的に、１６個の８ビットブロックとして、４×４行列にて、以下のパターンに従って、Srow,columnとして表現される；
【表１】
2005529365.tif 000003
【００１７】
ミックスカラム変換２２においては、この状態の列は、ＧＦ(２８)上の多項式と見なされ、これら多項式は、モジュロ（ｘ４＋１）にある所定の固定の多項式ａ（ｘ）を乗じられたものとして、以下によって与えられる：
ａ（ｘ）＝ａ３ｘ３＋ａ２ｘ２＋ａ１ｘ＋ａ０
【００１８】
ここで、これら多項式ａ３、ａ２、ａ１、ａ０は１６進値にて以下のように表される：
ａ３＝０３ｈ
ａ２＝０１ｈ
ａ１＝０１ｈ
ａ０＝０２ｈ
【００１９】
この多項式は、ｘ４＋１に対する共通の素数（co-prime）であり、従って、逆元を有する。
【００２０】
暗号化のためには、ミックスカラム変換は、状態ｓ内の列の各々について、ｓｒ，ｃ→ｓ’ｒ，ｃとして以下のように表される：
【数１】
2005529365.tif 000004
【００２１】
この行列の乗法の評価は以下のように行なわれる：
【数２】
2005529365.tif 000005
【００２２】
復号化の際には、この演算の逆演算が必要となるが、これは、以下のような行列の乗法によって達成される：
【数３】
2005529365.tif 000006
【００２３】
この行列の乗法の評価は、以下のように行なわれる：
【数４】
2005529365.tif 000007
【００２４】
このミックスカラム変換行列は、一連の各行が先行する行（preceding row）のシフト（shifted）或いは巡回された（rotated）バージョンから成るという特別な性質を有する。一般には、ある行内の各要素は、各行内に現れるが、ただし、その行内の異なる位置に現れ、とりわけ、このミックスカラム変換行列の場合は、各行に対する各要素のこの異なる位置は、１位置だけ右へのシフト或いは巡回から成る。
【００２５】
本発明は、この性質を利用することで、この状態ｓの各列の乗法を遂行するためのハードウェアを大幅に低減できることができるという認識に依拠する。
【００２６】
図２は、ｍ×ｎ行列と１×ｎ行列との乗算のために適合化されたハードウェア論理５０の一つの実施例を示すが、ここで、このｍ×ｎ行列のｎ個の要素の一連の各行間の関係は、ある所定の行シフトから成る。AES ミックスカラム変換に対しては、ｍは４とされ、ｎも４とされ、この所定の関係は、１位置だけ右へのシフト（single rigth shift）とされる。
【００２７】
この論理回路５０は、４つの８ビット乗法回路６０...６３、４つの８ビット排他的論理和ゲート７０...７３、及びMixCol0...MixCol3として示される４つの帰還/出力レジスタ８０...８３から構成される。各乗法回路７０...７３は、入力に行列係数ｃ０、ｃ１、ｃ２、ｃ３の一つを乗じるように適合化される。排他的論理和ゲート７０...７３のおのおのは、後に説明するように、２つの入力の適当な論理結合を実行するために必要とされる論理要素の任意の適当な組み合わせを用いて実現される。
【００２８】
暗号化ラウンドに対しては、これら行列係数c0...c3の値としては、それぞれ、上で定義されたａ０．．．ａ３が用いられる。復号化ラウンドに対しては、これら行列係数ｃ０．．．ｃ３の値としては、それぞれ、上で定義されたｂ０．．．ｂ３が用いられる。各乗法回路６０...６３の出力は、対応する排他的論理和ゲート７０...７３の第一の入力に結合される。各排他的論理和ゲート７０...７３の出力は、対応するMixColレジスタ８０...８３に結合される。各MixColレジスタ８０...８３の出力は、排他的論理和ゲート７０...７３の一つの第二の入力に、この行列の一連の行間の関係を定義する行シフト関数に対応する帰還プラン（feedback plan）９０...９３に従って結合される。説明のケースにおいては、この帰還プラン９０...９３は、行列ａｒ，ｃ（暗号化用）及び行列ｂｃ，ｒ（復号化用）の、より一般的には、行列ｃｒ，ｃの、一連の行間の右への行シフトファンクションを実現する。
【００２９】
回路５０の動作の際には、一連のサイクルにおいてｓ０ｃ、ｓ１ｃ、ｓ２ｃ、ｓ３ｃ  が乗法論理６０...６３に次々と供給される。各列乗法の開始時にレジスタMixCol0...MixCol3 は予め零にセットされる。
【００３０】
第一回目のサイクルの後は、
【数５】
2005529365.tif 000008
となり、第二回目のサイクルの後は、
【数６】
2005529365.tif 000009
となり、第三回目のサイクルの後は、
【数７】
2005529365.tif 000010
となり、第四回目のサイクルの後は、
【数８】
2005529365.tif 000011
となる。
【００３１】
これら出力に関しては、帰還プラン９０...９３に従って以下のような出力が与えられる：
【数９】
2005529365.tif 000012
【００３２】
これは、要求される結果に他ならない。
【００３３】
一般的には、この行列内の行の数ｍによって要求されるサイクルの数が決まり、列の数ｎによって要求される論理グループ（乗法回路６０...６３、排他的論理和ゲート７０...７３、及びレジスタ８０...８３）の数が決まることに注意する。
【００３４】
乗法論理６０...６３は、任意の適当な論理を用いて実現することができる。一つの好ましい実施例においては、この乗法論理は、暗号化及び復号化の両方に対して、幾つかの論理を以下のスケジュールに従って結合することで提供される。
【００３５】
このスケジュールによると、c0×ｓ0cを遂行するためには、各々の乗法論理６０...６３からの出力は、ecycle,bitとして以下のように定義され、ｄは、暗号化に対しては０、復号化に対しては１とされる：
【数１０】
2005529365.tif 000013
【００３６】
同様にして、c1×ｓ1c'に対しては、
【数１１】
2005529365.tif 000014
として定義され、c2×ｓ2c'に対しては、
【数１２】
2005529365.tif 000015
として定義され、c3×ｓ3c'に対しては、
【数１３】
2005529365.tif 000016
として定義され、ここで、
【数１４】
2005529365.tif 000017
とされる。
【００３７】
これを達成するためには、２３個の排他的論理和ゲートと、３２個の排他的ＮＯＲゲートと、３２個のＮＡＮＤゲートが必要とされる。
【００３８】
当業者においては明らかなように、添付のクレームの範囲から逸脱することなく、他の形態も可能である。
【図面の簡単な説明】
【００３９】
【図１】AESブロック暗号化アルゴリズムを用いる暗号化動作の実現を解説する流れ図である。
【図２】ミックスカラム変換を遂行するための機能論理ブロックの略図である。
【図１】
2005529365.tif 000018
【図２】
2005529365.tif 000019
【国際調査報告】
2005529365.tif 000020
2005529365.tif 000021