(57)【要約】【課題】パイプライン処理システム上で実行可能なメッセージ認証コードを生成する暗号ブロック連鎖方式アルゴリズムを提供する。【解決手段】本発明の方法および装置は、大量のデータ値を複数のブロックに分割し、複数のブロックをそれぞれブロックのサブセットに分割し、各ブロックのサブセットのブロック上で第１の暗号ブロック連鎖方式アルゴリズムを実行することによって、各ブロックのサブセットについて中間メッセージ認証コードブロックを計算し、中間メッセージ認証コードブロック上で第２の暗号ブロック連鎖方式アルゴリズムを実行することによって、複数のブロックについてメッセージ認証コードブロックを計算する。【選択図】図３
2006221163.tif 000002
【特許請求の範囲】
【請求項１】
大量のデータ値を複数のブロックに分割し、
前記複数のブロックをそれぞれブロックのサブセットに分割し、
各ブロックのサブセットのブロック上で第１の暗号ブロック連鎖方式アルゴリズムを実行することによって、各ブロックのサブセットについて中間メッセージ認証コードブロックを計算し、
前記中間メッセージ認証コードブロック上で第２の暗号ブロック連鎖方式アルゴリズムを実行することによって、複数のブロックについてメッセージ認証コードブロックを計算することを含む方法。
【請求項２】
第１の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、前記データ値の所与のブロックを受け取り該所与のステージについて対応する暗号ブロックを生成し、
第１の暗号ブロック連鎖方式アルゴリズムの最後のステージが、各ブロックのサブセットについての中間メッセージ認証コードブロックを生成することを特徴とする請求項１に記載の方法。
【請求項３】
第１の暗号ブロック連鎖方式アルゴリズムの各ステージを別々のパイプラインで実行することをさらに含むことを特徴とする請求項２に記載の方法。
【請求項４】
第１の暗号ブロック連鎖方式アルゴリズムの第１のステージが、データ値の所与のブロック上で暗号化アルゴリズムを実行して対応する暗号ブロックを生成し、
第１の暗号ブロック連鎖方式アルゴリズムの後続ステージがそれぞれ、前のステージの暗号ブロックと、暗号化アルゴリズムの前にあるデータ値の所与のブロックと、を使用して排他的ＯＲ演算を実行して、前記所与のステージについての対応する暗号ブロックを生成することを特徴とする請求項２に記載の方法。
【請求項５】
第１の暗号ブロック連鎖方式アルゴリズムの各ステージを別々のパイプラインで実行することをさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
第２の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、前記中間メッセージ認証コードブロックのうち所与の一つを受け取り、該所与のステージについて対応する暗号ブロックを生成し、
第２の暗号ブロック連鎖方式アルゴリズムの最後のステージが、複数のブロックについてのメッセージ認証コードブロックを生成することを特徴とする請求項２に記載の方法。
【請求項７】
第２の暗号ブロック連鎖方式アルゴリズムの第１のステージが、データ値の所与のブロック上で暗号化アルゴリズムを実行して対応する暗号ブロックを生成し、
第２の暗号ブロック連鎖方式アルゴリズムの後続ステージがそれぞれ、前のステージの暗号ブロックと、暗号化アルゴリズムの前にある所与の中間メッセージ認証コードブロックと、を使用して排他的ＯＲ演算を実行して、前記所与のステージについての対応する暗号ブロックを生成することを特徴とする請求項６に記載の方法。
【請求項８】
第１および第２の暗号ブロック連鎖方式アルゴリズムが同一のものであることを特徴とする請求項１に記載の方法。
【請求項９】
大量のデータ値を複数のブロックに分割し、
前記複数のブロックをそれぞれブロックのセットに分割し、
ブロックの各セットをそれぞれブロックのサブセットに分割し、
各ブロックのサブセットのブロック上で第１の暗号ブロック連鎖方式アルゴリズムを実行することによって、各ブロックのサブセットについて中間メッセージ認証コードブロックを計算し、
前記中間メッセージ認証コードブロック上で第２の暗号ブロック連鎖方式アルゴリズムを実行することによって、複数のブロックについてメッセージ認証コードブロックを計算することを含む方法。
【請求項１０】
第１の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、前記データ値の所与のブロックを受け取り該所与のステージについて対応する暗号ブロックを生成し、
第１の暗号ブロック連鎖方式アルゴリズムの最後のステージが、各ブロックのサブセットについての中間メッセージ認証コードブロックを生成することを特徴とする請求項９に記載の方法。
【請求項１１】
第１の暗号ブロック連鎖方式アルゴリズムの各ステージを別々のパイプラインで実行することをさらに含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
複数のブロックに分割された大量のデータ値を格納するように動作可能な少なくとも一つのメモリ回路であって、前記複数のブロックはそれぞれブロックのサブセットに分割されており、
（ｉ）各ブロックのサブセットのブロック上で第１の暗号ブロック連鎖方式アルゴリズムを実行することによって、各ブロックのサブセットについて中間メッセージ認証コードブロックを計算し、（ｉｉ）前記中間メッセージ認証コードブロック上で第２の暗号ブロック連鎖方式アルゴリズムを実行することによって、複数のブロックについてメッセージ認証コードブロックを計算するよう動作可能な少なくとも一つのプロセッサと、
を備えることを特徴とする装置。
【請求項１３】
第１の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、前記データ値の所与のブロックを受け取り該所与のステージについて対応する暗号ブロックを生成し、
第１の暗号ブロック連鎖方式アルゴリズムの最後のステージが、各ブロックのサブセットについての中間メッセージ認証コードブロックを生成することを特徴とする請求項１２に記載の装置。
【請求項１４】
各プロセッサが第１の暗号ブロック連鎖方式アルゴリズムの少なくとも一つのステージをパイプラインとして実行するように動作可能である、複数のプロセッサをさらに備えることを特徴とする請求項１３に記載の装置。
【請求項１５】
前記複数のプロセッサが並列に動作することを特徴とする請求項１４に記載の装置。
【請求項１６】
前記少なくとも一つのプロセッサが、
データ値の所与のブロック上で暗号化アルゴリズムを実行することによって、第１の暗号ブロック連鎖方式アルゴリズムの第１のステージを実行して、対応する暗号ブロックを生成し、
前のステージの暗号ブロックと、暗号化アルゴリズムの前にあるデータ値の所与のブロックと、を使用して排他的ＯＲ演算を実行することによって、第１の暗号ブロック連鎖方式アルゴリズムの後続ステージを実行して、前記所与のステージについての対応する暗号ブロックを生成するように動作可能であることを特徴とする請求項１３に記載の装置。
【請求項１７】
各プロセッサが、第１の暗号ブロック連鎖方式アルゴリズムのステージのうちの一つをパイプラインとして実行するよう動作可能である、複数のプロセッサをさらに備えることを特徴とする請求項１６に記載の装置。
【請求項１８】
第２の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、前記中間メッセージ認証コードブロックのうち所与の一つを受け取り、該所与のステージについて対応する暗号ブロックを生成し、
第２の暗号ブロック連鎖方式アルゴリズムの最後のステージが、複数のブロックについてのメッセージ認証コードブロックを生成することを特徴とする請求項１３に記載の装置。
【請求項１９】
前記少なくとも一つのプロセッサが、
データ値の所与のブロック上で暗号化アルゴリズムを実行することによって、第２の暗号ブロック連鎖方式アルゴリズムの第１のステージを実行して、対応する暗号ブロックを生成し、
前のステージの暗号ブロックと、暗号化アルゴリズムの前にある所与の中間メッセージ認証コードブロックと、を使用して排他的ＯＲ演算を実行することによって、第２の暗号ブロック連鎖方式アルゴリズムの後続ステージを実行して、前記所与のステージについての対応する暗号ブロックを生成するように動作可能であることを特徴とする請求項１８に記載の装置。
【請求項２０】
第１および第２の暗号ブロック連鎖方式アルゴリズムが同一のものであることを特徴とする請求項１２に記載の装置。
【請求項２１】
プロセッサにアクションを実行させるよう動作可能なソフトウェアプログラムであって、前記アクションには、
大量のデータ値を複数のブロックに分割し、
前記複数のブロックをそれぞれブロックのサブセットに分割し、
各ブロックのサブセットのブロック上で第１の暗号ブロック連鎖方式アルゴリズムを実行することによって、各ブロックのサブセットについて中間メッセージ認証コードブロックを計算し、
前記中間メッセージ認証コードブロック上で第２の暗号ブロック連鎖方式アルゴリズムを実行することによって、複数のブロックについてメッセージ認証コードブロックを計算することが含まれることを特徴とするプログラム。
【請求項２２】
第１の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、前記データ値の所与のブロックを受け取り該所与のステージについて対応する暗号ブロックを生成し、
第１の暗号ブロック連鎖方式アルゴリズムの最後のステージが、各ブロックのサブセットについての中間メッセージ認証コードブロックを生成することを特徴とする請求項２１に記載のプログラム。
【請求項２３】
第１の暗号ブロック連鎖方式アルゴリズムの各ステージを別々のパイプラインで実行することをさらに含むことを特徴とする請求項２２に記載のプログラム。
【請求項２４】
第１の暗号ブロック連鎖方式アルゴリズムの第１のステージが、データ値の所与のブロック上で暗号化アルゴリズムを実行して対応する暗号ブロックを生成し、
第１の暗号ブロック連鎖方式アルゴリズムの後続ステージがそれぞれ、前のステージの暗号ブロックと、暗号化アルゴリズムの前にあるデータ値の所与のブロックと、を使用して排他的ＯＲ演算を実行して、前記所与のステージについての対応する暗号ブロックを生成することを特徴とする請求項２２に記載のプログラム。
【請求項２５】
第１の暗号ブロック連鎖方式アルゴリズムの各ステージを別々のパイプラインで実行することをさらに含むことを特徴とする請求項２４に記載のプログラム。
【請求項２６】
第２の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、前記中間メッセージ認証コードブロックのうち所与の一つを受け取り、該所与のステージについて対応する暗号ブロックを生成し、
第２の暗号ブロック連鎖方式アルゴリズムの最後のステージが、複数のブロックについてのメッセージ認証コードブロックを生成することを特徴とする請求項２２に記載のプログラム。
【請求項２７】
第２の暗号ブロック連鎖方式アルゴリズムの第１のステージが、データ値の所与のブロック上で暗号化アルゴリズムを実行して対応する暗号ブロックを生成し、
第２の暗号ブロック連鎖方式アルゴリズムの後続ステージがそれぞれ、前のステージの暗号ブロックと、暗号化アルゴリズムの前にある所与の中間メッセージ認証コードブロックと、を使用して排他的ＯＲ演算を実行して、前記所与のステージについての対応する暗号ブロックを生成することを特徴とする請求項２６に記載のプログラム。
【請求項２８】
第１および第２の暗号ブロック連鎖方式アルゴリズムが同一のものであることを特徴とする請求項２１に記載のプログラム。
【請求項２９】
プロセッサにアクションを実行させるよう動作可能なソフトウェアプログラムであって、前記アクションには、
大量のデータ値を複数のブロックに分割し、
前記複数のブロックをそれぞれブロックのセットに分割し、
ブロックの各セットをそれぞれブロックのサブセットに分割し、
各ブロックのサブセットのブロック上で第１の暗号ブロック連鎖方式アルゴリズムを実行することによって、各ブロックのサブセットについて中間メッセージ認証コードブロックを計算し、
前記中間メッセージ認証コードブロック上で第２の暗号ブロック連鎖方式アルゴリズムを実行することによって、複数のブロックについてメッセージ認証コードブロックを計算することが含まれることを特徴とするプログラム。
【請求項３０】
第１の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、前記データ値の所与のブロックを受け取り該所与のステージについて対応する暗号ブロックを生成し、
第１の暗号ブロック連鎖方式アルゴリズムの最後のステージが、各ブロックのサブセットについての中間メッセージ認証コードブロックを生成することを特徴とする請求項２９に記載のプログラム。
【請求項３１】
第１の暗号ブロック連鎖方式アルゴリズムの各ステージを別々のパイプラインで実行することをさらに含むことを特徴とする請求項３０に記載のプログラム。
【請求項３２】
請求項２１ないし３１のいずれかに記載されたプログラムを格納したことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばパイプライン処理システム上で実行可能なメッセージ認証コードを生成する暗号ブロック連鎖方式（cipher block chaining）アルゴリズムを提供するための方法および装置に関する。
【背景技術】
【０００２】
最先端のコンピュータアプリケーションがますます複雑化し、処理システムに対する要求が絶えず増加しているために、コンピュータの処理するデータのスループットをより高速にするという要請が常に存在する。グラフィックス・アプリケーションは、所望の視覚効果を得るために比較的短時間に膨大な数のデータアクセス、データ計算およびデータ操作を要求するので、処理システムに対して最も高い要求を出すアプリケーションの一つである。リアルタイムかつマルチメディアのアプリケーションも、処理システムに対して高い要求を出す。実際、これらのアプリケーションは、毎秒何千メガビットのデータ処理というような極めて速い処理速度を必要とする。
【０００３】
処理システムのなかには、単一のプロセッサを使用して高速の処理速度を出すものもあれば、マルチプロセッサアーキテクチャを利用して実装されるものもある。マルチプロセッサシステムにおいては、複数のサブプロセッサが並列に（または、少なくとも協調して）動作して、所望の処理結果を得ることができる。これらの並列処理システムは、繰り返し処理アルゴリズムを並列に実行するパイプラインプロセッサを形成するよう適応されてもよい。これは、アルゴリズムおよび命令レイテンシを隠すのに有用であることが多い。
【０００４】
パイプライン処理は望ましい構成であるが、パイプラインを通してデータを常に効率的に処理できるわけではない。例えば、メッセージ認証コードを生成する暗号ブロック連鎖方式アルゴリズムは、パイプラインシステムで効率的に実行することができない。これは、チェーン内の処理ステージが、前のステージによって生成されるデータに依存しており、したがって、ステージを別々のパイプラインで容易に実行することができないからである。
【０００５】
例えば、図１は、メッセージ認証コード（ＭＡＣ）を生成する暗号ブロック連鎖方式アルゴリズムを示す。このアルゴリズムは、複数のデータのブロックＢｉを暗号化してメッセージ認証コード（ＭＡＣ）生成することができる。暗号ブロック連鎖方式アルゴリズムの第１ステージでは、第１のデータブロックＢ１が暗号関数ｆ(Ｂｉ)に渡され、第１暗号ブロックＣ１を生成する。暗号ブロック連鎖方式アルゴリズムの次のステージでは、第２のデータブロックＢ２が別の暗号関数ｆ(Ｂｉ，Ｃｉ−１)に渡されて、第２の暗号ブロックＣ２を生成する。第２ステージの暗号関数が二つの入力、すなわち、第２のデータブロックＢ２と前のステージの暗号ブロックＣ１とを受け取ることに注意する。したがって、第２の暗号ブロックＣ２は、前のステージの暗号ブロックＣ１の関数である。暗号ブロック連鎖方式アルゴリズムの次のステージは、第２のステージと実質的に同じであり、暗号ブロック連鎖方式アルゴリズムの最後のステージがＭＡＣを生成する。
【０００６】
図２を参照すると、暗号ブロックＣｉのそれぞれは、対応するデータブロックＢｉと前の暗号ブロック（第１の暗号ブロックを除いて）とに依存している。したがって、データブロックＢｉに対するいかなる変更もＭＡＣを変更することになる。これは、データブロックＢｉを認証するメカニズムとなる。実際、ＭＡＣは、データに割り当てられ、そのデータが悪意をもって変更されていないことを後日確認するためのテストに用いられる暗号化チェックサム（または、ハッシュ結果）として機能する。ＭＡＣの作成に使用された暗号ブロック連鎖方式アルゴリズムを知らずに、無許可の人物がＭＡＣをうっかり変更することなくデータＢｉを変更することは、ほとんど起こり得ない。したがって、ＭＡＣは、データの送信および／またはデータの記憶において、悪意のある改ざんが必ず検出されることを保証するという価値を有する。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
残念なことに、上述の暗号ブロック連鎖方式アルゴリズムは、アルゴリズムの各ステージが前のステージで生成された暗号ブロックに依存するため、パイプライン処理には適していない。したがって、ステージを直ちにそれぞれのパイプラインに割り当てて並列に実行することができない。その結果、（暗号ブロック連鎖方式アルゴリズムを実行する所与のプロセッサに関連する）アルゴリズムレイテンシおよび命令レイテンシを隠すことができない。さらに、ＭＡＣを利用するデータＢｉの認証が、後に実行されるプロセスの重大なボトルネックとなり得る。
【０００８】
したがって、例えばパイプライン処理システム上で実行可能なメッセージ認証コードを生成する暗号ブロック連鎖方式アルゴリズムを提供するための新規な方法および装置が必要とされている。
【課題を解決するための手段】
【０００９】
本発明の態様は、チェーンが複数のセグメント、例えば４つのセグメントに分割される暗号ブロック連鎖方式アルゴリズムを提供するための方法および装置に振り向けられている。チェーンの端がＭＡＣであった上述の従来のプロセスと異なり、各セグメントが中間暗号ブロックＭｊを生成するが、この中間暗号ブロックはデータブロックＢｉのサブセットのみに依存する。依存関係が限定されるので、Ｍｊをパイプラインを通して取得することができる。ＭＡＣを取得するために、ＭｊがＸＯＲ演算および暗号化ステップを通され、全てのデータブロックＢｉに依存する単一の暗号ブロックを取得する。
【００１０】
本発明の一つまたは複数の態様によると、大量のデータ値を複数のブロックに分割し、複数のブロックをそれぞれブロックのサブセットに分割し、各ブロックのサブセットのブロック上で第１の暗号ブロック連鎖方式アルゴリズムを実行することによって、各ブロックのサブセットについて中間メッセージ認証コードブロックを計算し、中間メッセージ認証コードブロック上で第２の暗号ブロック連鎖方式アルゴリズムを実行することによって、複数のブロックについてメッセージ認証コードブロックを計算する方法および装置を提供する。
【００１１】
第１の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、データ値の所与のブロックを受け取り該所与のステージについて対応する暗号ブロックを生成してもよい。第１の暗号ブロック連鎖方式アルゴリズムの最後のステージが、各ブロックのサブセットについての中間メッセージ認証コードブロックを生成してもよい。
【００１２】
好適には、第１の暗号ブロック連鎖方式アルゴリズムのステージは、別々のパイプラインで実行される。
【００１３】
例えば、第１の暗号ブロック連鎖方式アルゴリズムの第１のステージが、データ値の所与のブロック上で暗号化アルゴリズムを実行して対応する暗号ブロックを生成してもよい。第１の暗号ブロック連鎖方式アルゴリズムの後続ステージがそれぞれ、前のステージの暗号ブロックと、暗号化アルゴリズムの前にあるデータ値の所与のブロックと、を使用して排他的ＯＲ演算を実行して、所与のステージについての対応する暗号ブロックを生成してもよい。
【００１４】
さらに、第２の暗号ブロック連鎖方式アルゴリズムは複数のデータ変換ステージを含み、各ステージは、中間メッセージ認証コードブロックのうち所与の一つを受け取り、該所与のステージについて対応する暗号ブロックを生成してもよい。第２の暗号ブロック連鎖方式アルゴリズムの最後のステージが、複数のブロックについてのメッセージ認証コードブロックを生成することが好ましい。
【００１５】
本発明の一つまたは複数のさらなる態様によると、大量のデータ値を複数のブロックに分割し、複数のブロックをそれぞれブロックのセットに分割し、ブロックの各セットをそれぞれブロックのサブセットに分割し、各ブロックのサブセットのブロック上で第１の暗号ブロック連鎖方式アルゴリズムを実行することによって、各ブロックのサブセットについて中間メッセージ認証コードブロックを計算し、中間メッセージ認証コードブロック上で第２の暗号ブロック連鎖方式アルゴリズムを実行することによって、複数のブロックについてメッセージ認証コードブロックを計算する方法および装置を提供する。
【００１６】
本発明の他の態様、特徴および効果は、添付の図面とともに本明細書においてなされる説明から当業者にとって明らかとなる。
【００１７】
本発明の様々な態様を説明するために、現在のところ好適である図面を示す。しかしながら、本発明は図示したものの正確な構成および手段に限定されないことが理解されるであろう。
【発明を実施するための最良の形態】
【００１８】
同一の数字が同一の要素を示す図面を参照すると、図３は、本発明の一つまたは複数の態様による暗号ブロック連鎖方式アルゴリズムを実行するよう動作可能なパイプラインプロセッサ構成１００を示すブロック図である。暗号ブロック連鎖方式アルゴリズムは、好適には、それぞれの中間メッセージ認証コードブロックＭｉを生成するために、暗号ブロックＣｉの限られたセットのみが互いに依存するように構成される。例えば、複数のデータが１６個のデータブロックＢｉ（ｉ＝１、２、・・・１６）に編成される場合、暗号ブロックＣ１、Ｃ５およびＣ９が互いに依存しあって第１の中間メッセージ認証コードブロックＭ１を生成するように、暗号ブロック連鎖方式アルゴリズムを構成することができる。さらに、暗号ブロックＣ２、Ｃ６およびＣ１０が互いに依存しあって第２のメッセージ認証コードブロックがＭ２を生成することができる。暗号ブロックＣｉの間に類似の関係を設定し、それぞれのサブセット内で互いに依存関係を有する暗号ブロックの４つのサブセットを生成し、対応する中間メッセージ認証コードブロックＭｉを生成してもよい。
【００１９】
全ての暗号ブロックＣｉの間に連続した依存関係があるわけではないので、本発明の態様による暗号ブロック連鎖方式アルゴリズムは、各パイプラインが暗号ブロック連鎖方式アルゴリズムの一つまたは複数のステージを実行するパイプラインプロセスによって実行可能である。図３に示すように、第１のパイプラインは、暗号ブロックＣ１、Ｃ２、Ｃ３およびＣ４を生成するよう動作可能である。第２のパイプラインは、暗号ブロックＣ５、Ｃ６、Ｃ７およびＣ８を生成するよう動作可能であり、これらの暗号ブロックは、前のパイプラインの暗号ブロック、すなわちＣ１、Ｃ２、Ｃ３およびＣ４には依存していないことに注意する。第３のパイプラインは、暗号ブロックＣ９、Ｃ１０、Ｃ１１およびＣ１２を生成するよう動作可能であり、これらの暗号ブロックは前の暗号ブロックに依存しているものはない。最後に、第４のパイプラインは、それぞれの中間メッセージ認証コードブロックＭ１、Ｍ２、Ｍ３およびＭ４を生成するよう動作可能である。パイプラインの数および大きさは、データブロックおよび生成される暗号ブロックの大きさ、および、これらのブロックがサブセットに分割される方法に依存することに注意する。データがサブセットに編成される方法に関する詳細については後述する。
【００２０】
図４を参照すると、中間メッセージ認証コードブロックＭｉ上で暗号ブロック連鎖方式アルゴリズムを実行することによって、メッセージ認証コードブロックＭＡＣ１１０を生成することができる。特に、それぞれの暗号ブロックＣｉおよびそれぞれの中間メッセージ認証コードブロックＭｉを生成したデータＢｉに対してのいかなる無許可の変更も、ＭＡＣ１１０内のデータを必ず変更することになる。これによって、この種の無許可の改変を検出可能にする。
【００２１】
次に図５を参照する。図５は、本発明の一つまたは複数の態様による暗号ブロック連鎖方式アルゴリズムを受けることのできる大量のデータの概念図を示す。上述したように、データを複数のブロックＢｉに分割し、ブロックＢｉをそれぞれのサブセットにさらに分割することによって、部分的に、パイプラインを利用する暗号ブロック連鎖方式アルゴリズム実行の利点を達成することができる。図５に示すように、データ１１２は任意のサイズであってよいし、任意の数のブロックＢｉに分割可能であってよい。図３ないし図４を参照して上述した実施例では、データが１６個のブロックＢｉに分割され、さらに４個のサブブロックに再分割された場合を仮定した。したがって、図３の実施例は、ブロックのセット１１４に対応するサイズのデータ量を表している。
【００２２】
説明のために、データ１１２が１６個のブロックＢｉ,ｊ（ｉ＝１、２、３、４；ｊ＝１、２、３、４）のみを含み、好適にはブロックＢｉ,ｊがそれぞれブロックのサブセットに分割されるものと仮定する。例えば、ブロックのサブセットは、添字ｉによって以下のサブセットにグループ化することができる。
（Ｂ１,１；Ｂ１,２；Ｂ１,３；Ｂ１,４）
（Ｂ２,１；Ｂ２,２；Ｂ２,３；Ｂ２,４）
（Ｂ３,１；Ｂ３,２；Ｂ３,３；Ｂ３,４）
（Ｂ４,１；Ｂ４,２；Ｂ４,３；Ｂ４,４）
【００２３】
次に図６を参照する。図６は、それぞれの暗号ブロックＣｉ,ｊと中間メッセージ認証コードＭｉとを生成するための、複数のパイプラインを通したデータ操作のシーケンスを示す概念的なブロック図である。各パイプラインは、好適には、暗号ブロック連鎖方式アルゴリズムの各ステージに関連付けられたデータ操作を実行するように動作可能である。したがって、第１の時間間隔ｔ１の間、第１のパイプラインはブロックの第１のサブセットの第１ブロックＢ１,１を受け取り、対応する暗号ブロックＣ１,１を生成することができる。
【００２４】
第２の時間間隔ｔ２において、第１のパイプラインは、ブロックの第２のサブセットから第１ブロックＢ２,１を受け取り、対応する暗号ブロックＣ２,１を生成することができる。同じ間隔の間に、第２のパイプラインは、前の時間間隔から、ブロックの第１のサブセットの第２データブロックＢ１,２と暗号ブロックＣ１,１とを受け取り、対応する暗号ブロックＣ１,２を生成することができる。
【００２５】
第３の時間間隔ｔ３において、第１のパイプラインは、ブロックの第３のサブセットからデータブロックＢ３,１を受け取り、対応する暗号ブロックＣ３,１を生成することができる。同じ時間間隔の間、第２のパイプラインは、データブロックの第２のサブセットからの第２のデータブロックＢ２,２と、前の時間間隔からの暗号ブロックＣ２,１とを受け取り、対応する暗号ブロックＣ２,２を生成することができる。さらに、第３のパイプラインは、ブロックの第１のサブセットからの第３のデータブロックＢ１,３と、前の時間間隔からの暗号ブロックＣ１,２とを受け取り、対応する暗号ブロックＣ１,３を生成することができる。
【００２６】
第４の時間間隔ｔ４において、第１のパイプラインは、ブロックの第４のサブセットから第１のデータブロックＢ４,１を受け取り、対応する暗号ブロックＣ４,１を生成することができる。同じ時間間隔において、第２のパイプラインは、ブロックの第３のサブセットからの第２のデータブロックＢ３,２と、前の時間間隔からの暗号ブロックＣ３,１とを受け取り、対応する暗号ブロックＣ３,２を生成することができる。さらに、第３のパイプラインは、ブロックの第２のサブセットからの第３のデータブロックＢ２,３と、前の時間間隔からの暗号ブロックＣ２,２とを受け取り、対応する暗号ブロックＣ２,３を生成することができる。さらに、第４のパイプラインは、ブロックの第１のサブセットからの第４のデータブロックＢ１,４と、前の時間間隔からの暗号ブロックＣ１,３とを受け取り、第１の中間メッセージ認証コードＭ１を生成することができる。全ての中間メッセージ認証コードブロックＭが取得されるまで、このプロセスが後の時間間隔でも繰り返される。
【００２７】
図６の例から注意すべきことは、それぞれの暗号ブロックＣ１,１、Ｃ１,２およびＣ１,３が互いに依存しあって中間メッセージ認証コードブロックＭ１を生成することである。ブロックの他のサブセットと、対応する中間メッセージ認証コードブロックＭ２、Ｍ３およびＭ４との関係として、同様の関連付けを理解してもよい。また、有利なことに、パイプラインが暗号ブロック連鎖方式アルゴリズムのそれぞれのステージを並列に実行することができるので、パイプラインを使用することでアルゴリズムレイテンシと命令レイテンシとが隠蔽される。
【００２８】
再び図５を参照すると、当業者は、データ１１２の大きさが、ブロックの全てのサブセット上で暗号ブロック連鎖方式アルゴリズムを並列に実行するにはパイプラインの数が不足するような大きさであってもよいことを理解するであろう。このような場合、データブロックＢｉ,ｊがそれぞれブロックのセット１１４に分割され、各セットがパイプラインの数および大きさに対応する数のデータブロックＢｉ,ｊを含むことが好ましい。上述したように、ブロックの各セット１１４は、それぞれブロックのサブセットに分割されることが好ましい。したがって、好適にはパイプラインを使用して、ブロックの各セット１１４について中間メッセージ認証コードブロックＭのセットをそれぞれ計算する。中間メッセージ認証コードブロックＭが利用できるようになるか、または全てが計算された後、好適には中間メッセージ認証ブロックＭ上で暗号ブロック連鎖方式アルゴリズムを実行することによって、全てのブロックＢｉ,ｊについてのメッセージ認証コードブロックが取得される。
【００２９】
図７は、本発明の一つまたは複数の態様による使用に適した暗号ブロック連鎖方式アルゴリズム１０２の一実施例を示す。暗号ブロック連鎖方式アルゴリズム１０２は、データブロックＢの各サブセットが４つのデータブロックを有し、したがって、暗号ブロック連鎖方式アルゴリズムが４つのステージを備える場合を仮定する。例えば、データブロックの第１のサブセットＢ１,１、Ｂ１,２、Ｂ１,３およびＢ１,４（図５）に暗号ブロック連鎖方式アルゴリズム１０２が適用されると仮定する。アルゴリズムの第１のステージでは、第１のデータブロックＢ１,１が暗号化アルゴリズム１０４に与えられ、対応する暗号ブロックＣ１,１を生成する。暗号ブロック連鎖方式アルゴリズムの第２のステージでは、第２のデータブロックＢ１,２と、前のステージからの暗号ブロックＣ１,１とに排他的ＯＲ演算（ＸＯＲ）が施され、データの中間ブロックを生成する。データの中間ブロックが暗号化アルゴリズム１０４に与えられ、対応する暗号ブロックＣ１,２を生成する。続くデータブロックＢ１,３およびＢ１,４に関してこのプロセスが繰り返され、中間メッセージ認証コードブロックＭ１を生成する。
【００３０】
本発明の様々な実施形態および態様をブロック図およびタイミング／シーケンス図とともに説明したが、本発明の一つまたは複数の特徴を数学的に記述することもできる。例えば、本発明による一実施例の暗号ブロック連鎖方式アルゴリズムの数学的説明をするために、以下のような変数を定義することができる。
M ：メッセージ
I(m) ：メッセージ長（ｎバイト）
P ：パイプラインの深さ
N ：臨時（１６−ｎバイト）
R ：ランダム値（１６＊Ｐバイト）
Mk ：暗号化マスターキー
【００３１】
上術の変数の定義を用いて、暗号化、ＸＯＲ演算および限定された依存関係を含む本発明による暗号ブロック連鎖方式アルゴリズムの実施例を以下のように記述することができる。
S[i] := E(K, N || i) for i = 0, ... ,l(m);
C[i] := M[i] XOR S[i] for i = 1, ... ,l(m); and
U := T XOR S[0],
ここで、E(K, B)は、キーKによる暗号化Bを使用する１２８ビットブロック暗号の暗号化である。
【００３２】
このような暗号ブロック連鎖方式アルゴリズムを大量のデータに適用してＭＡＣを生成すると、このデータは、以下のアルゴリズムにしたがって認証されることができる。
K := E(MK, R);
X[p] := E(K, N || l(m)+p) for p = 1, ... ,P;
X[i+P] := E(K, X[i] XOR M[i]) for i = 1, ... ,l(m);
X[i+P] := E(K, X[i] XOR X[i+P-1]) for i = l(m)+1,...,l(m)+P-1; and
T := X[l(m)+P*2+1].
【００３３】
上述したように、本発明の一つまたは複数の態様による暗号ブロック連鎖方式技術は、パイプライン処理技術を用いて実装されることが好ましい。パイプライン技術を実装可能な方法の一つは、並列プロセッサの使用である。この点に関して図８を参照すると、図８は、上述の本発明の態様を実行するのに適したコンピューティング装置２００を示す。好適には、装置２００は、複数のプロセッサ２０２Ａ〜２０２Ｄと、関連するローカルメモリ２０４Ａ〜２０４Ｄと、バス２０８を介して相互接続されるメインメモリ（または共有メモリ）２０６とを含む。一例として４台のプロセッサ２０２が示されているが、本発明の趣旨および範囲から逸脱することなく任意の数のプロセッサを使用することができる。
【００３４】
プロセッサ２０２は、システムメモリ２０６からデータを要求しデータを操作して所望の結果を達成することができる任意の既知の技術を利用して実装することができる。特に、ローカルメモリ２０４はそれぞれのプロセッサ２０２と同一チップ上に位置することが好ましい。しかしながら、ローカルメモリ２０４は、ハードウェアキャッシュメモリ機能を実現するためのオンチップもしくはオフチップのハードウェアキャッシュ回路、キャッシュレジスタ、キャッシュメモリコントローラ等を持たないという点で、ハードウェアキャッシュメモリでないことが好ましい。別の実施形態では、ローカルメモリ２０４はキャッシュメモリであってもよく、および／または、追加のキャッシュメモリを使用してもよい。チップ上のスペースが限られていることが多いので、ローカルメモリ２０４の寸法はシステムメモリ２０６より遙かに小さくてもよい。プロセッサ２０２は、プログラムの実行およびデータ処理のために、バス２０８を介してシステムメモリ２０６からそれぞれのローカルメモリ２０４にデータ（プログラムデータを含んでもよい）をコピーするデータアクセス要求をすることが好ましい。ダイレクトメモリアクセス（ＤＭＡ）技術等の既知の技術のいずれかを利用して、データアクセスを容易にするメカニズムが実装されてもよい。
【００３５】
本発明の少なくとも一つの態様によると、上述の方法および装置は、図示したような適切なハードウェアを利用して実現することができる。この種のハードウェアは、標準のディジタル回路、ソフトウェアプログラムおよび／またはファームウェアプログラムを実行するよう動作可能な任意の既知のプロセッサ、プログラマブルリードオンリメモリ（ＰＲＯＭ）、プログラマブルアレイロジック装置（ＰＡＬ）等の一つまたは複数のプログラム可能なディジタルデバイスまたはシステムなどの、既知の任意の技術を利用して実装することができる。さらに、図示した装置は特定の機能ブロックに分割された形で示されているが、このようなブロックが別々の回路によって実装されてもよいし、および／またはブロックが一つまたは複数の機能ユニットに統合されてもよい。さらに、可搬性および／または配布のために（フレキシブルディスク、メモリチップ等の）適切な記録メディア上に格納可能なソフトウェアプログラムおよび／またはファームウェアプログラムの形で、本発明の様々な態様が実装されてもよい。
【００３６】
以上、本発明を特定の実施形態を参照して説明したが、これらの実施形態は本発明の原理および適用法を例示するにすぎないことを理解すべきである。したがって、これら例示としての実施形態には多数の変形が可能であり、前掲の特許請求の範囲で規定される本発明の精神および範囲から逸脱することなく他の構成を考案することができる。
【図面の簡単な説明】
【００３７】
【図１】従来技術による暗号ブロック連鎖方式アルゴリズムの構造を示すブロック図である。
【図２】従来技術による図１の暗号ブロック連鎖方式アルゴリズムのデータ依存関係を示すブロック図である。
【図３】本発明の一つまたは複数の態様による暗号ブロック連鎖方式アルゴリズムを実行するよう動作可能なパイプラインプロセッサ構成を示すブロック図である。
【図４】図３の暗号ブロック連鎖方式アルゴリズムの結果を使用してメッセージ認証コードを生成可能なプロセスを示すブロック図である。
【図５】本発明の一つまたは複数の態様にしたがって、大量のデータが複数のブロックに分割され、これらブロックが複数のブロックのセットにグループ化され、各グループが複数のブロックのサブセットを含んでいる様子を示す概念図である。
【図６】本発明の一つまたは複数の態様による図３の暗号ブロック連鎖方式アルゴリズムを実行するよう動作可能なパイプラインプロセッサ構成を通した、データ操作のシーケンスを示す概念的なブロック図である。
【図７】本発明の一つまたは複数の態様による図３の暗号ブロック連鎖方式アルゴリズムに関するさらなる詳細を示すブロック図である。
【図８】本発明の一つまたは複数の態様による図７の暗号ブロック連鎖方式アルゴリズムを実行可能なマルチプロセッシングシステムの構造を示すブロック図である。
【符号の説明】
【００３８】
１００  パイプラインプロセッサ、  １０２  暗号ブロック連鎖方式アルゴリズム、  １０４  暗号化アルゴリズム、  １１０  ＭＡＣ、  １１２  データ、  ２００  コンピューティング装置、  ２０２  プロセッサ、  ２０４  ローカルメモリ、  ２０６  システムメモリ、  ２０８  バス。
【図１】
2006221163.tif 000003
【図２】
2006221163.tif 000004
【図３】
2006221163.tif 000005
【図４】
2006221163.tif 000006
【図５】
2006221163.tif 000007
【図６】
2006221163.tif 000008
【図７】
2006221163.tif 000009
【図８】
2006221163.tif 000010