(57)【要約】暗号化アプリケーション用の列変換をＸＯＲ演算を用いて実行する。本発明の一実施例では、入力列のバイトをＡＥＳアルゴリズム用に変換する（１１０，１２０，１３０）。出力列の変換されたバイトは、入力列の各バイトからの少なくとも１ビットを論理的に組み合わせる（ＸＯＲ演算する）ことにより生成する（１２０）。変換されたバイトはＡＥＳアルゴリズムのためのMixColumn変換を満すため、MixColumn変換に使用される論理的組み合わせ及び乗算の代わりに上述の論理的組み合わせを使用することができる。このアプローチによれば、MixColumn変換に指定されている有限フィールド乗算を回避し、等価な変換を単一タイプの論理組合せのみを用いて実行することができる。
2006502437.tif 000002
【特許請求の範囲】
【請求項１】
ＡＥＳステートの一つの列内のデータの各Ｎビットの４つの入力バイトごとに、データを同じくＮビットの１つの出力バイトに変換する方法であって、該方法は、前記データの４つの入力バイトの各々からのＮデータビットの少なくとも１ビットを論理的に組み合わせることにより、複数の入力バイトにそれぞれの係数を乗算することなしに、前記出力バイトのＮビットの各々を生成するステップを具えることを特徴とするデータ変換方法。
【請求項２】
前記出力バイトのＮビットの各々の生成は係数の乗算なしに実行することを特徴とする請求項１記載の方法。
【請求項３】
前記出力バイトのＮビットの各々の生成は有限フィールド要素の乗算なしに実行することを特徴とする請求項１記載の方法。
【請求項４】
前記出力バイトのＮビットの各々の生成は入力バイトの乗算なしに実行することを特徴とする請求項１記載の方法。
【請求項５】
前記出力バイトのＮビットの各々の生成は何の乗算もなしに実行することを特徴とする請求項１記載の方法。
【請求項６】
前記論理的に組み合わせる処理は１つのタイプの論理演算のみを用いて実行することを特徴とする請求項１記載の方法。
【請求項７】
前記論理的に組み合わせる処理はＸＯＲ論理演算演算を用いて実行することを特徴とする請求項１記載の方法。
【請求項８】
ＸＯＲ論理演算は、否定ＸＯＲ論理演算と、非否定ＸＯＲ論理演算の少なくとも１つであることを特徴とする請求項１記載の方法。
【請求項９】
前記論理的に組み合わせる処理はＸＯＲ演算のみを用いて実行することを特徴とする請求項１記載の方法。
【請求項１０】
前記出力バイトのＮビットの各々の生成はＸＯＲ演算のみを用いて実行することを特徴とする請求項１記載の方法。
【請求項１１】
前記出力バイトの生成は表１に示された方程式に従って実行することを特徴とする請求項1記載の方法。
【請求項１２】
ＡＥＳステートの各列ごとに前記生成ステップを繰り返すことを特徴とする請求項１記載の方法。
【請求項１３】
ＡＥＳステートの列のそれぞれの出力バイトからのデータビットを用いて論理的組み合わせを実行することにより、それぞれの係数を乗算することなく、前記出力バイトの逆方向変換を実行するステップを更に具えることを特徴とする請求項１２記載の方法。
【請求項１４】
前記出力バイトのＮビットの各々の生成はＸＯＲ演算のみを用いて実行することを特徴とする請求項１３記載の方法。
【請求項１５】
前記出力バイトのＮビットの各々の生成はＸＯＲ演算のみを用いて実行し、ＡＥＳステートの各列ごとにこの生成ステップを繰り返すことを特徴とする請求項１記載の方法。
【請求項１６】
ＡＥＳ勧告に従うステップを実行するステップを更に具え、前記出力バイトのＮビットの各々の生成はＡＥＳ勧告と一致して実行することを特徴とする請求項１記載の方法。
【請求項１７】
ＡＥＳステートの一つの列内のデータの各Ｎビットの４つの入力バイトごとに、データを同じくＮビットの１つの出力バイトに変換する回路装置であって、該回路装置は、前記データの４つの入力バイトの各々からのＮデータビットの少なくとも１ビットを論理的に組み合わせることにより、複数の入力バイトにそれぞれの係数を乗算することなしに、前記出力バイトのＮビットの各々を生成する生成手段を具えることを特徴とするデータ変換回路装置。
【請求項１８】
ＡＥＳステートの一つの列内のデータの各Ｎビットの４つの入力バイトごとに、データを同じくＮビットの１つの出力バイトに変換する回路装置であって、該回路装置は、前記データの４つの入力バイトの各々からのＮデータビットの少なくとも１ビットを論理的に組み合わせることにより、複数の入力バイトにそれぞれの係数を乗算することなしに、前記出力バイトのＮビットの各々を生成するように構成された論理回路を具えることを特徴とするデータ変換回路装置。
【請求項１９】
前記論理回路はプログラマブルプロセッサを用いて実現されていることを特徴とする請求項１８記載の回路装置。
【請求項２０】
前記論理回路は個別の回路を用いて実現されていることを特徴とする請求項１８記載の回路装置。
【請求項２１】
前記論理回路はセミプログラマブル回路を用いて実現されていることを特徴とする請求項１８記載の回路装置。
【請求項２２】
係数の乗算がないことを特徴とする請求項１８記載の回路装置。
【請求項２３】
有限フィールド要素の乗算がないことを特徴とする請求項１８記載の回路装置。
【請求項２４】
入力バイトの乗算がないことを特徴とする請求項１８記載の回路装置。
【請求項２５】
何の乗算もないことを特徴とする請求項１８記載の回路装置。
【請求項２６】
前記論理回路は、更に、１つのタイプの論理演算のみを用いて論理的に組み合わせを実行することにより前記出力バイトのＮビットの各々を生成するように構成されていることを特徴とする請求項１８記載の回路装置。
【請求項２７】
前記論理回路は、更に、ＸＯＲ論理演算を用いて論理的組み合わせを実行することにより前記出力バイトのＮビットの各々を生成するように構成されていることを特徴とする請求項１８記載の回路装置。
【請求項２８】
前記論理回路は、更に、表1に示された方程式に従って論理的組み合わせを実行することにより前記出力バイトのＮビットの各々を生成するように構成されていることを特徴とする請求項１８記載の回路装置。
【請求項２９】
前記論理回路は、更に、ＡＥＳステートの各列に作用するように構成されていることを特徴とする請求項１８記載の岐路装置。
【請求項３０】
ＡＥＳステートの列のそれぞれの出力バイトからのデータビットを用いて論理的組み合わせを実行することにより、それぞれの係数を乗算することなしに、前記出力バイトに逆方向変換を実行する手段を更に具えることを特徴とする請求項１８記載の回路装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号化技術、特に高速暗号化を実現する回路装置に関するものである。
【背景技術】
【０００２】
種々の暗号化回路及びアルゴリズムが広範囲のアプリケーション、例えばデータ保護及びＩＤカードのために設計され、多くの種々のタイプのデータを保護するために使用されている。種々の理由のために、これらのアプリケーションの多くは、ＮＩＳＴ（National Institute of Standard and Technology）に由来するＡＥＳ（Advanced Encryption Standard）ベースの暗号化、或いはＤＥＳ（Data Encryption Standard）又はＩＤＥＡ（International Data Encryption Standard）のような他の暗号化標準の使用に向けられている。ＡＥＳ暗号化アルゴリズムは情報を暗号化し復号化することができる対称ブロックサイファーであって、１２８，１９２及び２５６ビットの暗号化鍵を用いて１２８ビットのブロックを暗号化及び復号化することができる。データの暗号化はデータを理解不能の形（暗号文という）に変換し、データの復号化はデータをもとの形（平文という）に変換する。
【０００３】
ＡＥＳベースの暗号化は、ByteSub（バイト置換）変換、ShiftRow（行シフト）変換及びMixColumn（列混合）変換を含む。MixColumn変換は、代表的には、ステート（バイトの二次元アレイ）の全ての列を取り、それらのデータを互いに独立に混合して新しい列を生成する。このデータの混合は、ルックアップテーブルを用いるアルゴリズム、及び／又は、乗算因子の対数を計算し２つの対数の和の逆対数値を求めて乗算結果（積）を決定する処理を使用する。ＡＥＳに関する一般的情報及び本発明の種々の実施例を適用し得る実現に関する具体的情報については、“Announcing the Advanced Encryption Standard (AES)”の題名が付けられた「federal Information Processing Standard (FIPS) publication 197 of November 26, 2001」を参照することができ、これは付録Ａとして添付され、参考のためにその内容の全てがここに含まれているものとする。
【０００４】
MixColumn変換を実現するために使用する回路及びアルゴリズムは、比較的大形で伝播遅延の結果低速である組合せ論理回路を含むのが典型的である。高速回路アプリケーションの要求が増え続けているので、比較的低速のMixColumn変換は暗号及び暗号化回路の実現のための課題を示している。
【０００５】
本発明の種々の態様は暗号化、もっと具体的なアプリケーションでは、比較的伝播遅延が小さい暗号化を提供する。
【０００６】
本発明の一実施例では、ＡＥＳステート（二次元アレイ）の一つの列内のデータの各Ｎビットの４つの入力バイトごとに、前記４つの入力バイトの各々からの少なくとも１ビットを論理的に組み合わせることによりＮビットの出力バイトに変換する。この変換は、複数の入力バイトにそれぞれの係数を乗算する必要なしに実行されるため、単一タイプの論理組合せ演算（例えばＸＯＲ又はＸＮＯＲ演算）を使用することができる。このアプローチによれば、暗号化と関連する難点（データミキシングと関連して上述した難点を含む）を解決することができる。
【０００７】
本発明の他の実施例では、回路装置を、ＡＥＳアルゴリズムにおけるデータの列を（例えばMixColumn変換の変わりに）列内の選択したビットに対してＸＯＲゲートを用いて、有限フィールド乗算を用いる必要なしに、出力列のビットを生成するようにプログラムする。このアプローチによれば、慣例のＡＥＳ MixColumn変換の実現に必要とされる代表的なゲート数より少数のゲートを用いてＸＯＲ演算出力を実現することができる。
【０００８】
本発明の上記の概要により本発明の各例示実施例又は全ての実現を説明するつもりはない。図面及び以下の詳細な説明は特にこれらの実施例を実証するものである。
【０００９】
本発明は、図面につき以下に説明する本発明の種々の実施例の詳細の説明から明らかになる。
【００１０】
本発明は種々の変更や代替形態が可能であり、その詳細は図面に例示されており、以下に詳細に説明する。しかし、本発明は開示した特定の実施例に限定されるものではなく、特許請求の範囲で規定される本発明の思想及び範囲に入るすべての変形例、等価例及び代替例をカバーするものである点に注意されたい。
【００１１】
本発明は、ＡＥＳ形式の回路及び方法を含むデータ暗号化のような暗号化のための方法及び装置に高度に適用可能である。本発明は、暗号化のためのデータの比較的高速変換、例えばＡＥＳ形式の暗号化におけるMixColumn変換に対して特に有利であることが確かめられた。本発明は必ずしもこのようなアプリケーションに限定されないが、本発明の種々の態様の正しい認識はこのような環境における実施例の検討により最良に得られる。
【００１２】
本発明の一実施例では、複数のＸＯＲ（排他的論理和）ゲートを含む組合せ論理回路をＡＥＳベース暗号化標準におけるMixColumnデータ変換を実行するようプログラムする。慣例の如く、MixColumn変換はＡＥＳステート内の列に有限ガロア体内の１以上のバイト（１６進数形態で表される）０１，０２，０２，０９，０ｂ，０ｄ及び０ｅを乗算することを意味する。この実施例は、上述した慣例のアプローチに関連して実施することができるものであって、MixColumn変換のための乗算処理をＸＯＲゲートを用いて実行してステート（例えばバイトの二次元アレイ）の入力列内の種々のビットから出力ビットを出力する。もっと具体的に言うと、ステートの入力列内の選択したビットをＸＯＲ演算を用いて組み合わせて、乗算を用いる必要なしにMixColumn変換を実行する。このＸＯＲ演算変換は慣例のアプローチより高速であり、例えばMixColumn変換のために慣用されている回路装置より小さいスペース及び電力を必要とする比較的小形の回路装置を用いて実現することができる。
【００１３】
上述のアプローチは慣例の暗号化アプローチに対する種々の課題を克服するために有用であり、上述したように、特に順方向MixColumn変換及び逆方向MixColumn変換に有用である。例えば、ＸＯＲ演算出力は、ＡＥＳベース暗号化に対する慣例のMixColumn変換に使用されるＸＯＲゲートの数より少数のＸＯＲゲートを用いて達成される。更に、この変換は慣例のMixColumn変換に使用される複雑な数学的処理、例えば乗算因子の対数を計算し２つの対数の和の逆対数値を求めて乗算の積を決定する数学的処理を必要としない。このアプローチによれば、この変換の実現に使用する組合せ論理回路は比較的少数のゲートを使用し、従って比較的低い伝播遅延を示す。ＡＥＳ及びMixColumn変換に関する情報については、前記の刊行物「Announcing the Advanced Encryption Standard (AES)」を参照されたい。
【００１４】
上述のアプローチは更に複数のデータタイプの暗号化に適用することができる。例えば、音声、ビデオ及び電子メールデータのような通信データを暗号化し、送信中保護することができる。電子ファイルや秘密書類のような他のデータを暗号化し、保護されたフォーマットで蓄積及び／又は送信することができる。更に、速度、回路コスト及び電力消費が関係するアプリケーションにおいて上述の暗号化アプローチを実現するためには比較的速い復号時間及び簡単な復号化回路が有用である。
【００１５】
一つの実装例では、ＡＥＳアルゴリズムに対する入力及び出力は各々１２８ビット（０又は１の値を有するディジット）のシーケンスからなる。これらのシーケンスはブロックと呼ぶことができ、それらが含むビット数はそれらの長さと呼ぶことができる。ＡＥＳアルゴリズムに関連して使用される暗号鍵は代表的には１２８，１９２又は２５６ビットのシーケンスである。このようなシーケンス内のビットは零で始まりシーケンス長（ブロック長又は鍵長）より１小さい値で終わる番号が付けられ、例えば１２８ビットシーケンスのビットは０−１２７の番号が付けられている。暗号化演算はステートに実行され、ステート内の各列は３２ビットワードを構成する４つのバイトを有する。これらの暗号化演算はMixColumn変換を含み、この変換はステートに対し一列ずつ実行され、各列を４項多項式として取り扱い、各列のデータを混合してデータの新しい列を生成する。
【００１６】
図１は本発明の特定の実施例に従うデータ暗号化方法のフロー図である。ブロック１１０において、ステート内の一列のバイトがメモリから読み出され、ブロック１２０において１以上のバイトからの選択されたビットにＸＯＲ演算が実行される。ＸＯＲ演算の出力は変換されたバイトの列内のビットを決定するために使用される。変換されたバイトはブロック１３０においてメモリに書き込まれ、次いでブロック１４０において異なる位置での使用のために送信される。代替例では、ブロック１４０における送信ステップは省略され、変換されたバイトがメモリに保持される。逆方向ＸＯＲ演算がブロック１５０において変換されたバイトの各々に実行される。逆方向ＸＯＲ演算は変換されたバイトをもとの形に復号し、逆方向変換されたバイトがブロック１６０において種々の実施のために処理される。
【００１７】
図２は本発明の他の実施例に従うデータ暗号化用の回路装置２００を示す。回路装置２００は複数の回路要素を通信可能に結合するように構成された通信バス２０５を含む。図示の回路要素は暗号化回路２１０、メモリ２２０、回路コントローラ２３０、ユーザインターフェースデバイス２４０及び通信ポート２５０を含む。これらの回路要素の１つ以上が回路装置２００の種々の実現に使用され、バス２０５は追加の要素（例えば代表的にはコンピュータに使用されている要素）に結合されるように構成されている。
【００１８】
回路装置２００は種々のプログラミング言語及び技術の１つ以上を用いてプログラムすることができる。例えば、Verilog又はＶＨＤＬハードウエア設計言語を使用することができる。一つの実装例では、回路コントローラ２３０はメモリ２２０からステートの一列のデータビットを読出し、これらのデータビットを暗号化回路２１０で処理させるようにプログラムされる。暗号化回路２１０はメモリ２３０から読み出されたデータビットの選択したビットについてＸＯＲ演算を実行することにより前記列から変換されたバイトの出力をバス２０５に付与する。暗号化回路２１０で変換されたビットは他のユーザ処理のためにメモリ２３０に蓄積される。
【００１９】
特定の実装例では、変換されたバイトは通信ポート２５０（例えばモデム、ＵＳＢポート又は他の市販の通信ポート）を経て転送される。他の特定の実装例では、メモリ２２０からの暗号化及び／又は送信データビットを指示するためにユーザインターフェース２４０のユーザ入力を用いる。例えばユーザ入力を用いてコントローラ２３０により実行される暗号化処理をプログラムすることができる。更に他の実装例では、コントローラはメモリ２２０をプログラミングデータの蓄積のためにも使用する。
【００２０】
本発明の他の実施例では、暗号化チップはＡＥＳ MixColumn変換のために一列のバイトにＸＯＲ演算を、例えば上述した方法と同様に実行するように構成される。このチップは、複数のＸＯＲゲートと、一列内の選択したビットをＸＯＲ演算して出力列のバイトを生成するように構成されたコントローラとを含む。例えば、本発明を適用し得る一つのタイプの暗号化チップ装置に、アメリカ、カリフォルニア州、サニーベール所在のフィリップスセミコンダクタ社から入手し得るＰＴＤ３０００チップがある。
【００２１】
本発明の更に他の実施例では、順方向及び／又は逆方向MixColumn変換を以下の表１及び２に詳細に示されているステートの一列内のバイトに対するＸＯＲ演算を用いて実行する。例えば、図２のコントローラ２３０は、これらのＸＯＲ演算を実行するようにプログラムすることができる。変換すべきステートの一列のバイトはａ，ｂ，ｃ，ｄで示され、順方向及び逆方向MixColumn変換後の列の１つのバイト（ｅ）が表１及び２にそれぞれ示されている。文字の後の添え字はビットの位置を示し（最上位ビットが７で、最下位ビットが０）、記号
2006502437.tif 000003
はＸＯＲ演算を示す。
【００２２】
表１は一列内のバイトの順方向変換を示す。
2006502437.tif 000004
【００２３】
表２は逆方向変換すべきバイトの逆方向変換を示す（例えば、バイトａ，ｂ，ｃ，ｄは変換されたバイトであり、その列は逆方向変換されている）。
2006502437.tif 000005
【００２４】
実験結果
データ暗号化に関する一般的情報及び上述した本発明の種々の実施例を適用することができる実験結果に関する具体的情報については、添付の付録Ａを参照されたい。
【００２５】
本発明は上述した特定の実施例に限定されない。例えば、ＸＯＲ演算の代わりに、対応する数学的変更を加えたＸＮＯＲ（排他的否定論理和）演算を用いて、同一の結果を達成することができる。本発明を適用し得る種々の変更、等価的処理並びに多数の構造も特許請求の範囲に記載された本発明の範囲に含まれるものである。
【図面の簡単な説明】
【００２６】
【図１】本発明の一実施例に基づくデータ暗号化方法のフロー図である。
【図２】本発明の他の実施例に基づくデータ暗号化回路装置を示す図である。
【図１】
2006502437.tif 000006
【図２】
2006502437.tif 000007
【国際調査報告】
2006502437.tif 000008
2006502437.tif 000009