(57)【要約】【課題】ＭＤ５ダイジェスティングを実行するための装置および方法を提供する。【解決手段】本発明は、任意の長さの入力メッセージに対し１２８ビットダイジェストを作成するＭＤ５ダイジェスティングプロセスをパイプライン化する装置および方法を含む。【選択図】図６
2008500590.tif 000002
【特許請求の範囲】
【請求項１】
ＭＤ５ダイジェスティングを実行する装置であって、
ルート変数を格納する変数記憶装置と、
ルート変数の少なくとも一部の値に基づき、補助関数を計算する関数計算機構と、
前記関数計算機構により実行される補助関数計算と並行して、３つのパラメータの合計を計算する前加算機と、
前記関数計算機構からの出力データ、および、前記前加算機からの出力データの少なくとも一部に基づき、ＭＤ５ダイジェスティングプロセスのための繰返し結果を生成する後プロセッサと、
を含む装置。
【請求項２】
前記ＭＤ５ダイジェスティングプロセスは、４ラウンドの計算を含み、各ラウンドは、１６の計算の繰返しを含む、請求項１に記載の装置。
【請求項３】
前記関数計算機構は、４つの関数計算器を含み、各関数計算器は、各ラウンドの計算に用いられいる、請求項１に記載の装置。
【請求項４】
前記繰返し結果は、変数記憶装置内のルート変数の１つを更新すべく用いられる、請求項１に記載の装置。
【請求項５】
前記繰返し結果を生成し、かつ、入力メッセージのダイジェストを作成する前記ＭＤ５ダイジェスティングプロセスにより要求される計算の繰返しを実行するよう、前記変数記憶装置、前記関数計算機構、前記前加算機、および、前記後プロセッサを制御するコントローラをさらに含む、請求項１に記載の装置。
【請求項６】
前記変数記憶装置は、前記コントローラの制御下で、１つの計算の繰返しが終了し、かつ、次の計算の繰返しが開始する前に、ルート変数の値を循環させる、請求項１に記載の装置。
【請求項７】
前記後プロセッサは、
計算の１ラウンドに対応する、前記関数計算機構における４つの関数計算器により生成された結果の中から１つの結果を選択する関数結果セレクタと、
前記前加算機からの出力データと、前記関数計算機構からの選択結果とを加算する第１の加算器と、
前記第１の加算器からの出力データを予め決められたビット数だけシフトするシフタと、
前記シフタからの出力データと、前記ルート変数の１つとを加算することにより、繰返しの結果を生成する第２の加算器と、
を含む、請求項１に記載の装置。
【請求項８】
前記３つのパラメータは、前記ルート変数の１つ、１つの予め決められたパラメータ、および、入力メッセージから導かれたパラメータを含む、請求項１に記載の装置。
【請求項９】
メッセージダイジェスティングを実行する装置であって、
ルート変数を格納する変数記憶装置と、
前記ルート変数の少なくとも一部に基づき、第１の関数の組と、第２の関数の組とを計算する関数計算機構と、
前記関数計算機構により実行される補助関数計算と並行して、１組のパラメータの合計を計算する前加算機と、
前記関数計算機構からの出力データおよび前記前加算機からの出力データの少なくとも一部に基づき、メッセージダイジェスティングプロセスのための繰返し結果を生成する後プロセッサと、
を含む装置。
【請求項１０】
前記メッセージダイジェスティングプロセスは、Ｍラウンドの計算を含み、各ラウンドは、Ｎの計算の繰返しを含み、ＭおよびＮは、正の整数である、請求項９に記載の装置。
【請求項１１】
前記第１および第２の組の関数のそれぞれは、Ｋ関数計算器を含み、第１の組の関数計算器と、第２の組の対応する関数計算器とは、１ラウンドの計算に用いられ、、Ｋは、正の整数である、請求項９に記載の装置。
【請求項１２】
前記繰返しの結果は、前記変数記憶装置内のルート変数の１つを更新するべく用いられる、請求項９に記載の装置。
【請求項１３】
前記繰返し結果を生成し、かつ、入力メッセージのダイジェストを作成する前記メッセージダイジェスティングプロセスにより要求される計算の繰返しを実行するよう、前記変数記憶装置、前記関数計算機構、前記前加算機、および、前記後プロセッサを制御するコントローラをさらに含む、請求項９に記載の装置。
【請求項１４】
前記変数記憶装置は、前記コントローラの制御下で、１つの計算の繰返しが終了し、かつ、次の計算の繰返しが開始する前に、ルート変数の値を循環させる、請求項９に記載の装置。
【請求項１５】
前記コントローラは、連続する繰返しに含まれる演算をパイプライン化するよう、前記前加算機と、前記関数計算機構と、前記後プロセッサとを制御する、請求項１３に記載の装置。
【請求項１６】
前記後プロセッサは、
計算の１ラウンドに対応する、前記関数計算機構における前記第１の組の関数により生成された結果の中から第１の結果を選択する第１の関数結果セレクタと、
前記計算のラウンドに対応する、前記関数計算機構における前記第１の組の関数により生成された結果の中から第２の結果を選択する第２の関数結果セレクタと、
前の繰返しの結果に基づき、前記第１の結果と前記第２の結果との間で１組のビットを選択し、該１組のビットが最終的な関数結果となるビットセレクタと、
前記前加算機からの出力データと、前記最終的な関数結果とを加算する第１の加算器と、
前記第１の加算器からの出力データを予め決められたビット数だけシフトするシフタと、
前記シフタからの出力データと、前記ルート変数記憶装置からのルート変数の１つとを加算することにより、計算の現在の繰返しを生成する第２の加算器と、
を含む、請求項１に記載の装置。
【請求項１７】
前記１組のパラメータは、ルート変数の１つと、１つの予め決められたパラメータと、入力メッセージから導かれたパラメータとを含む、請求項９に記載の装置。
【請求項１８】
ＭＤ５ダイジェスティングを実行するための方法であって、
第１のメッセージを受信する段階と、
第２のメッセージと複数のパラメータとを生成する第１のメッセージを準備する段階であって、前記第２のメッセージは、１６ワードブロックの倍数の長さを有する段階と、
ルート変数を初期化する段階と、
前記複数のパラメータおよび前記初期化されたルート変数の少なくとも一部に基づき、前記第２のメッセージにおける１６ワードブロックそれぞれに対し４ラウンドの計算を実行する段階と、
を含む方法。
【請求項１９】
前記４ラウンドの計算のそれぞれは、１６の計算の繰返しを含み、１つの繰返しの結果は、前記ルート変数の１つを更新するべく用いられる、請求項１８に記載の方法。
【請求項２０】
前記４ラウンドの計算は、４つの関数の計算を含み、各関数は、１ラウンドに対応し、同じ関数は、同じラウンドの１６の繰返しに用いられる、請求項１８に記載の方法。
【請求項２１】
計算の繰返しが終了した後、次の繰返しが開始する前に、ルート変数を循環させる段階をさらに含む、請求項１８に記載の方法。
【請求項２２】
前記ダイジェストは、前記ルート変数の最終値を含む、請求項１７に記載の方法。
【請求項２３】
前記４ラウンドの計算の繰返しは、２段階のパイプラインを含み、各計算の繰返しは、第１の段階と第２の段階とを含む、請求項１９に記載の方法。
【請求項２４】
前記第１の段階と前記第２の段階とのそれぞれは、１クロックサイクル内で実行され、繰返しの第２の段階と、次の繰返しの第１の段階とは、１クロックサイクル内で実行される、請求項２３に記載の方法。
【請求項２５】
メッセージダイジェスティングをパイプライン化する方法であって、
第１のメッセージを受信する段階と、
第２のメッセージと複数のパラメータとを生成するべく前記第１のメッセージを準備する段階であって、前記第２のメッセージは、複数のＮワードブロックの長さを有し、Ｎは正の整数である段階と、
ルート変数を初期化する段階と、
前記複数のパラメータおよび前記初期化されたルート変数の少なくとも一部に基づき、前記第２のメッセージにおけるＮワードブロックのそれぞれに対しＭラウンドの計算を実行することにより、前記第１のメッセージのダイジェストを作成する段階であって、Ｍは、正の整数であり、１ラウンドの計算は、複数の計算の繰返しを含み、計算の繰返しは、２段階のパイプラインを用いて計算され、繰返しの結果は、前記ルート変数の１つを更新するべく用いられる段階と、
を含む方法。
【請求項２６】
１つの計算の繰返しが終了した後、次の繰返しが開始する前に、ルート変数を循環させることをさらに含む、請求項２５に記載の方法。
【請求項２７】
前記ダイジェストは、前記ルート変数の最終値を含む、請求項２５に記載の方法。
【請求項２８】
１つの計算の繰返しは、第１の段階と第２の段階とを含み、各段階は、１クロックサイクル内で実行される、請求項２５に記載の方法。
【請求項２９】
前記第１の段階は、
前記ルート変数の１つと、１つの予め決められたパラメータと、前記第２の段階から導かれたパラメータとにおいて前加算を実行する段階と、
第１の組のＫ関数と第２の組のＫ関数とを計算する段階であって、Ｋは、正の整数であり、各関数は、１ラウンドの計算に必要である段階と、
前記第１の組から得られた結果から第１の結果を選択し、かつ、前記第２の組から得られた結果から第２の結果を選択する段階と、
を含む、請求項２８に記載の方法。
【請求項３０】
前記第２の段階は、
前の繰返しからの最終結果に基づき、第１の関数結果と第２関数結果との間でビットごとに選択する段階であって、前記第１の関数結果と前記第２の関数結果とは、前記第１の段階において得られる段階と、
前記最終的な関数結果と、前記第１の段階で実行される前加算からの出力データとを加算することにより、現在の繰返しのための第１の中間結果を生成する段階と、
前記第１の中間結果を予め決められたビット数だけシフトすることにより、現在の繰返しのための第２の中間結果を得る段階と、
前記第２の中間結果と、前記ルート変数の１つとを加算することにより、前記現在の繰返しのための最終結果を生成する段階と、
を含む、請求項２８記載の方法。
【請求項３１】
ネットワークシステムであって、
交換機機構と、
前記交換機機構により相互接続される複数のラインカードと、
それぞれが１つのラインカードに動作可能に結合されることにより、ＭＤ５ダイジェスティングを実行する複数のＭＤ５モジュールであって、各ＭＤ５モジュールは、
ルート変数を格納する変数記憶装置と、
ルート変数の少なくとも一部の値に基づき、補助関数を計算する関数計算機構と、
前記関数計算機構により実行される補助関数計算と並行して、３つのパラメータの合計を計算する前加算機と、
前記関数計算機構からの出力データ、および、前記前加算機からの出力データの少なくとも一部に基づき、ＭＤ５ダイジェスティングプロセスのための繰返し結果を生成する後プロセッサと、
を含むネットワークシステム。
【請求項３２】
前記ＭＤ５ダイジェスティングプロセスは、４ラウンドの計算を含み、各ラウンドは、１６の計算の繰返しを含む、請求項３１に記載のネットワークシステム。
【請求項３３】
前記関数計算機構は、４つの関数計算器を含み、各関数計算器は、各ラウンドの計算に用いられいる、請求項３１に記載のネットワークシステム。
【請求項３４】
前記繰返しの結果は、変数記憶装置内のルート変数の１つを更新すべく用いられる、請求項３１に記載のネットワークシステム。
【請求項３５】
前記繰返し結果を生成し、かつ、入力メッセージのダイジェストを作成する前記ＭＤ５ダイジェスティングプロセスにより要求される計算の繰返しを実行するよう、前記変数記憶装置、前記関数計算機構、前記前加算機、および、前記後プロセッサを制御するコントローラをさらに含む、請求項３１に記載のネットワークシステム。
【請求項３６】
前記変数記憶装置は、前記コントローラの制御下で、１つの計算の繰返しが終了し、かつ、次の計算の繰返しが開始する前に、ルート変数の値を循環させる、請求項３１に記載のネットワークシステム。
【請求項３７】
前記後プロセッサは、
計算の１ラウンドに対応する、前記関数計算機構における４つの関数計算器により生成された結果の中から１つの結果を選択する関数結果セレクタと、
前記前加算機からの出力データと、前記関数計算機構からの選択結果とを加算する第１の加算器と、
前記第１の加算器からの出力データを予め決められたビット数だけシフトするシフタと、
前記シフタからの出力データと、前記ルート変数の１つとを加算することにより、繰返しの結果を生成する第２の加算器と、
を含む、請求項３１に記載のネットワークシステム。
【請求項３８】
前記３つのパラメータは、前記ルート変数の１つ、１つの予め決められたパラメータ、および、入力メッセージから導かれたパラメータを含む、請求項３１に記載のネットワークシステム。
【請求項３９】
ネットワークシステムであって、
交換機機構と、
前記交換機機構により相互接続される複数のラインカードと、
それぞれが１つのラインカードに動作可能に結合されることにより、メッセージダイジェスティングを実行する複数のメッセージダイジェスティングモジュールであって、各メッセージダイジェスティングモジュールは、
ルート変数を格納する変数記憶装置と、
前記ルート変数の少なくとも一部に基づき、第１の関数の組と、第２の関数の組とを計算する関数計算機構と、
前記関数計算機構により実行される補助関数計算と並行して、１組のパラメータの合計を計算する前加算機と、
前記関数計算機構からの出力データおよび前記前加算機からの出力データの少なくとも一部に基づき、メッセージダイジェスティングプロセスのための繰返し結果を生成する後プロセッサと、
を含む、ネットワークシステム。
【請求項４０】
前記メッセージダイジェスティングプロセスは、Ｍラウンドの計算を含み、各ラウンドは、Ｎの計算の繰返しを含み、ＭおよびＮは、正の整数である、請求項３９に記載のネットワークシステム。
【請求項４１】
前記第１および第２の組の関数のそれぞれは、Ｋ関数計算器を含み、第１の組の関数計算器と、第２の組の対応する関数計算器とは、１ラウンドの計算に用いられ、、Ｋは、正の整数である、請求項３９に記載のネットワークシステム。
【請求項４２】
前記繰返しの結果は、前記変数記憶装置内のルート変数の１つを更新するべく用いられる、請求項９に記載の装置。
【請求項４３】
前記繰返し結果を生成し、かつ、入力メッセージのダイジェストを作成する前記メッセージダイジェスティングプロセスにより要求される計算の繰返しを実行するよう、前記変数記憶装置、前記関数計算機構、前記前加算機、および、前記後プロセッサを制御するコントローラをさらに含む、請求項３９に記載のネットワークシステム。
【請求項４４】
前記変数記憶装置は、前記コントローラの制御下で、１つの計算の繰返しが終了し、かつ、次の計算の繰返しが開始する前に、ルート変数の値を循環させる、請求項３９に記載のネットワークシステム。
【請求項４５】
前記コントローラは、連続する繰返しに含まれる演算をパイプライン化するよう、前記前加算機と、前記関数計算機構と、前記後プロセッサとを制御する、請求項４３に記載のネットワークシステム。
【請求項４６】
前記後プロセッサは、
計算の１ラウンドに対応する、前記関数計算機構における前記第１の組の関数により生成された結果の中から第１の結果を選択する第１の関数結果セレクタと、
前記計算のラウンドに対応する、前記関数計算機構における前記第１の組の関数により生成された結果の中から第２の結果を選択する第２の関数結果セレクタと、
前の繰返しの結果に基づき、前記第１の結果と前記第２の結果との間で１組のビットを選択し、該１組のビットが最終的な関数結果となるビットセレクタと、
前記前加算機からの出力データと、前記最終的な関数結果とを加算する第１の加算器と、
前記第１の加算器からの出力データを予め決められたビット数だけシフトするシフタと、
前記シフタからの出力データと、前記ルート変数記憶装置からのルート変数の１つとを加算することにより、計算の現在の繰返しを生成する第２の加算器と、
を含む、請求項３９に記載のネットワークシステム。
【請求項４７】
前記１組のパラメータは、ルート変数の１つと、１つの予め決められたパラメータと、入力メッセージから導かれたパラメータとを含む、請求項３９に記載のネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概ねネットワークセキュリティ、より詳しくは、ＭＤ５ダイジェスティングプロセスをパイプライン化するための装置および方法に関する。
【背景技術】
【０００２】
ネットワークは、コンピュータと他のデバイスとの通信を可能にする。例えば、ネットワークは、ビデオ、オーディオ、電子メールなどを表わすデータを伝送することができる。しかしながら、ネットワークシステムは、プライバシーおよびデータの保全性を失う、同一人物になりすます、サービス拒絶攻撃といった多くの脅威にさらされている。これらの脅威に立ち向かうべく、多くの対策が採られ、ネットワーク通信のセキュリティは向上してきている。例えば任意の長さのバイナリデータストリームに対しコンパクトなデジタル署名を生成するメッセージダイジェストアルゴリズムを用いるのも１つの手である。理想的なメッセージダイジェストアルゴリズムは、２組の異なる入力に対し同じ署名を生成することは決してないが、この論理を実現するには、入力ファイル分だけメッセージだジェストを必要とする。メッセージダイジェスト５（ＭＤ５）アルゴリズムのような実際のメッセージダイジェストアルゴリズムは、適度なサイズ（例えば１２８ビット）のデジタル署名を用いる。ＭＤ５ダイジェスティングプロセスを用いると、同じメッセージダイジェストを有する２つのメッセージを作成すること、あるいは、予め定められたターゲットメッセージダイジェストを有するメッセージを作成することはコンピュータ的に不可能であることが予測される。したがって、受信者は、ＭＤ５プロセスを用いることにより、署名が発行された後にデータが変更されていないか確認することできる。
【０００３】
ＭＤ５は、５１２ビットブロックでデータを処理し、１２８ビットのダイジェストを生成する。メッセージが多ブロックにわたる場合、１つのブロックに対し生成されたダイジェストは、次のブロックに対し生成されるべきダイジェストの初期値として用いられる。ＭＤ５ダイジェスティングプロセスは、４ラウンドの計算を含み、各ラウンドでは計算を１６回繰り返す。ＭＤ５ダイジェスティングプロセスは、ソフトウェアシミュレーションでも実行できるが、ハードウェアでの実行がより好ましい。なぜなら、ハードウェアソリューションの処理速度のほうが速いからである。ダイジェスティングプロセスがネットワーク通信のデータ処理速度を著しく落とさなければ都合がよい。ハードウェアでの実行において、ＭＤ５の計算が遅ければ複数のＭＤ５モジュールを用いてＭＤ５の処理速度を向上させることが必要になるかも知れない。その結果、ネットワークステム全体のデータ処理速度が落ちるようなことはないだろうが、ＭＤ５モジュールを増やせば、チップ内で必要な物理的領域も大きくなるので、さらに高性能な計算を必要とし、費用も高くなる。したがって、ハードウェアで実行するＭＤ５の処理速度を向上させることが望ましい。
【図面の簡単な説明】
【０００４】
【図１】一般的なネットワークシステムを示す。
【０００５】
【図２】１メッセージに対し１２８ビットのダイジェストを生成するプロセスを示す擬似コードを表わす。
【０００６】
【図３】ＭＤ５ダイジェスティングプロセスに関係する演算を実行するプロセスの一例を示すブロック図である。
【０００７】
【図４】ＭＤ５ダイジェスティングプロセスに関係する演算を実行するプロセスの他の例を示すブロック図である。
【０００８】
【図５】ＭＤ５ダイジェスティングを実行するシステムの一例を示すブロック図である。
【０００９】
【図６】本発明の一実施例に従う、ＭＤ５ダイジェスティングプロセスを実行する機能ブロックを示す。
【００１０】
【図７】本発明の一実施例に従う、ダイジェスティングプロセスをパイプライン化することによりＭＤ５ダイジェスティングプロセスを実行する機能ブロックを示す。
【００１１】
【図８】本発明の一実施例に従う、ＭＤ５ダイジェスティングプロセスをパイプライン化するプロセスを示す表である。
【００１２】
【図９】ネットワークシステムを示す。
【発明を実施するための最良の形態】
【００１３】
本発明の特徴および利点を以下の詳細な説明により明らかにする。
本発明の一実施例は、ＭＤ５ダイジェスティングプロセスを実行するための装置および方法を含む。ＭＤ５ダイジェスティングプロセスは、任意のサイズのメッセージに対し１２８ビットのダイジェストを生成するものである。ダイジェスティングプロセスは、４ラウンドの計算を含み、各ラウンドは１６回計算を繰り返す。１ラウンドの各繰返しは、１つの関数計算、４つの加算演算、および、１つのシフト演算を含み、これを２クロックサイクルで完了することができる。各繰返しは、その前の繰返しの結果を用いるので、連続する繰返しの計算は、すぐにはパイプライン化されないおそれがある。したがって、ＭＤ５ダイジェスティングプロセスを単純に実行している状態では、５１２ビットブロックに対する１２８ビットダイジェストを生成するのに少なくとも１２８クロックサイクルかかる。
【００１４】
本発明の一実施例によれば、ＭＤ５ダイジェスティングプロセスの連続する繰返しの計算は、５１２ビットブロックに対し１２８ビットダイジェストを生成するのに必要な合計サイクル数を減少させるためにパイプライン化されることができる。各繰返しにおける関数は、その前の繰返しの結果を用いるため、連続する繰返しの計算がパイプライン化されることは避けられる。本発明の一実施例によれば、その前の繰返しの結果の２つの異なる仮定に対応し、２組の結果が関数に対し計算される。１つの仮定では、前の繰返しの結果におけるビットはすべて０であり、また、他の仮定では、結果におけるビットはすべて１である。この方法を用いれば、前の繰返しの結果を入手する前に、関数の計算を始めることができる。また、結果を入手した場合、その結果は、ビットごとに関数の正しい出力を選択するのに用いることもできる。この方法により、連続する繰返しの計算をパイプライン化し、かつ、５１２ビットブロックのメッセージに対し１２８ビットダイジェストを生成するのに必要な合計クロックサイクル数を減少させることができる。
【００１５】
本発明において、明細書中の「１つの実施例」または「一実施例」は、実施例に関連して記載された特定の機能、構造、または、特徴が、本発明の少なくとも１つの実施例に含まれることを意味する。したがって、明細書中を通じて随所に見られる「一実施例では」という言い回しは、必ずしも同じ実施例を指すものではない。
【００１６】
図１は、多数の端末を支持する一般的なネットワークシステム１１０を示す。ネットワークシステム１１０は、ルータ、スイッチ、および、ブリッジなど多数のデバイスを含み、端末から端末へのデータのやりとりを容易にすることができる。ネットワークシステムは、無線システム、イーサネットシステムなどのシステム、あるいは、異なるシステムの組合せであってよい。ネットワークシステムは、サテライト１２０を用いることにより、端末同士の接続を容易にすることもできる。ネットワークシステムの端末は、サーバ（１３０）、デスクトップコンピュータ（１４０）、パーソナル携帯情報機器（ＰＤＡ）（１５０）、携帯電話（１６０）、ラップトップコンピュータ（１７０）または他のデバイスを含んでよい。異なる端末間でやりとりされるデータは、ビデオ、オーディオ、メッセージ、その他を含んでよい。ネットワークシステムは、メッセージ確認・認証用ＭＤ５ダイジェスティングプロセスを用いることにより、ネットワーク通信のセキュリティを向上させることができる。
【００１７】
任意の長さのメッセージに対し１２８ビットダイジェストを生成すべく、マサチューセッツ工科大学コンピュータセキュリティ研究室のＲｏｎ・ＲｉｖｅｓｔおよびＲＳＡデータセキュリティによってＭＤ５ダイジェスティングプロセスが設計された。このプロセスは、Ｒｏｎ・Ｒｉｖｅｓｔによる「ＭＤ５アルゴリズム」ｈｔｔｐ：／／ｗｗｗ．ｋｌｅｉｎｓｃｈｍｉｄｔ．ｃｏｍ／ｅｄｉ／ｍｄ５．ｈｔｍ（直近の閲覧は２００４年４月５日）に記載されている。このＭＤ５の仕様によれば、パディングやアペンドによって任意の長さのメッセージを準備し、結果として生じたメッセージＭは、５１２ビットの正確な倍数である長さを有する。つまり、Ｍは、３２ビットワードＭ［０］、Ｍ［１］、...、Ｍ［Ｎ−１］で表わすことができる。Ｍ［］は、メッセージ内のワードを意味し、ＭおよびＮは、１６の倍数である。メッセージダイジェストの生成プロセスを通じて４つの変数Ａ、Ｂ、Ｃ、Ｄが用いられ、４つのワードバッファに格納されることができる。入力メッセージの最終的な１２８ビットダイジェストは、Ａ、Ｂ、Ｃ、Ｄ内のビットを連結することにより得られる。説明を簡単にするべく、以下、４つの変数をルート変数と呼ぶ。ルート変数Ａ、Ｂ、Ｃ、Ｄは、１６進法の以下の値に初期化される（下位バイトから）。
Ａ：０１  ２３  ４５  ６７、
Ｂ：８９  ａｂ  ｃｄ  ｅｆ、
Ｃ：ｆｅ  ｄｃ  ｂａ  ９８、
Ｄ：７６  ５４  ３２  １０
また、各ラウンドの４つの補助関数がメッセージダイジェストを計算するために定義されかつ用いられる。
Ｆ（Ｂ，Ｃ，Ｄ）＝（Ｂ  ＡＮＤ  Ｃ）ＯＲ（（ＮＯＴ  Ｂ）ＡＮＤ  Ｄ））  （ラウンド１）（１）
Ｇ（Ｂ，Ｃ，Ｄ）＝（Ｂ  ＡＮＤ  Ｄ）ＯＲ（Ｃ  ＡＮＤ（ＮＯＴ  Ｄ））（ラウンド２）（２）
Ｈ（Ｂ，Ｃ，Ｄ）＝Ｂ  ＸＯＲ  Ｃ  ＸＯＲ  Ｄ（ラウンド３）（３）
Ｉ（Ｂ，Ｃ，Ｄ）＝Ｃ  ＸＯＲ（Ｂ  ＯＲ（ＮＯＴ  Ｄ））（ラウンド４）（４）
これら４つの関数Ｆ、Ｇ、Ｈ、Ｉは、ビットずつ並列であり、Ｂ、Ｃ、Ｄのビットからそれらの出力を生成する。
【００１８】
図２は、１メッセージに対し１２８ビットダイジェストを生成するプロセスを示す擬似コードを表わす。この擬似コードは、ＭＤ５仕様に適合している。擬似コードにおける変数アレイＴ〔ｍ〕、ｍ＝１、・・・、６４、は、多数の定数値を表わす。Ｔ〔ｍ〕は、４２９４９６７２９６＊（ａｃｓ（ｓｉｎ（ｍ）））の整数部に等しく、ｍは、ラジアンで測定される。一般的なアプリケーションでは、これら一定の変数値は、予め計算され、テーブル（以降Ｔテーブルと呼ぶ）に格納されてよい。擬似コードのライン１から処理ループが開始する。ライン２からライン２２までのループ本体は、入力メッセージの１６ワード（５１２ビット）を処理する。入力メッセージ内の１６ワードブロックすべてが処理されるとループは終了する。ライン２からライン４において、１６ワードブロックのワードは、変数アレイＸ［ｋ］、ｋ＝０．・・・１５に読み出される。ライン５は、４つの一時的な変数ＡＡ、ＢＢ、ＣＣ、ＤＤを用い、現在の値Ａ、Ｂ、Ｃ、Ｄをバックアップする。ライン６−９は、１６の繰返しを含むラウンド１に含まれる演算を実行する。各繰返しは、以下の形式の演算を含む。
Ａ＝Ｂ＋（（Ａ＋Ｆ（Ｂ，Ｃ，Ｄ）＋Ｘ［ｋ］＋Ｔ［ｍ］）＜＜＜Ｓ）、（５）
"Ｙ＜＜＜Ｓ"は、Ｙの値をＳビット左に移動する演算を示す。ライン１０−１３は、ラウンド２に含まれる演算を実行する。ラウンド２は１６回の繰返しを含み、各繰返しはそれぞれ以下の形式の演算を含む。
Ａ＝Ｂ＋（（Ａ＋Ｇ（Ｂ，Ｃ，Ｄ）＋Ｘ［ｋ］＋Ｔ［ｍ］）＜＜＜Ｓ）、（６）
ライン１４−１７は、１６回の繰返しを含む、ラウンド３に含まれる演算を実行する。各繰返しは、以下の形式の演算を含む。
Ａ＝Ｂ＋（（Ａ＋Ｈ（Ｂ，Ｃ，Ｄ）＋Ｘ［ｋ］＋Ｔ［ｍ］）＜＜＜Ｓ）．（７）
最終ライン１８−２１は、１６回の繰返しを含む、ラウンド４に関係する演算を実行する。各繰返しは、以下の形式の演算を含む。
Ａ＝Ｂ＋（（Ａ＋Ｉ（Ｂ，Ｃ，Ｄ）＋Ｘ［ｋ］＋Ｔ［ｍ］）＜＜＜Ｓ）．（８）
４ラウンドの演算の後、ライン２２において１６ワードブロックの出力データが得られる。これは、現在の１６ワードブロックが入力メッセージの最初のブロックである場合、Ａ、Ｂ、Ｃ、Ｄの現在の値を、前の１６ワードブロック用に得られたそれらの前の値、または、それらの初期値と共に合計することにより得られる。ライン２から２２までに示されたようなプロセスは、入力メッセージ内の１６ワードブロックすべてが処理されるまで繰り返される。出力メッセージの最終出力は、１２８ビットダイジェスト、つまり、Ａ、Ｂ、Ｃ、Ｄ内のビットの連結である。
【００１９】
方程式５−８で示されるように、４つのラウンドにおける繰返しは、厳密に同じ演算というわけではないが、非常に近い。実際には、方程式５−８は、以下の式に要約されることができる。
Ａ＝Ｂ＋（（Ａ＋ＦＦ（Ｂ，Ｃ，Ｄ）＋Ｘ［ｋ］＋Ｔ［ｍ，ｎ］）＜＜＜Ｓ［ｍ，ｎ］）、（９）
ＦＦは、関数Ｆ、Ｇ、Ｈ、Ｉの総称表現であり、ｋは、１６ワードブロックにおけるワードの指数であり、ｍは、ラウンドの指数であり、ｎは、１ラウンドの繰返しの指数である。４つのルート変数Ａ、Ｂ、Ｃ、Ｄの値のは、各ラウンド内で繰返しごとに右に循環していくことがわかる。例えば、ＡＢＣＤ→ＤＡＢＣ→ＣＤＡＢ→ＢＣＤＡ→ＡＢＣＤ→ＤＡＢＣ→となっている。すべての繰返しにおける演算の共通性により、また、各繰返し間のルート変数のローテーションの規則性により、各繰返しに含まれる演算を実行するには共通のプロセスを用いることができる。
【００２０】
図３は、ＭＤ５ダイジェスティングプロセスの各ラウンドの各繰返しに関係する演算を実行するプロセスの一例を示す。ルート変数Ａ、Ｂ、Ｃ、Ｄの値は、ブロック３１０において受信されてよい。ラウンド１の最初の繰返しでは、Ａ、Ｂ、Ｃ、Ｄの受信された値は初期値である。同じくブロック３１０において、１つの繰返しが終了した後、次の繰返しが開始する前に、変数Ａ、Ｂ、Ｃ、Ｄの値は、Ｂ→Ｃ→Ｄ→Ａというように循環する。ブロック３２０では、補助関数（ラウンド１、２、３、４に対しそれぞれＦ、Ｇ、Ｈ、Ｉ）が選択され、実行されてよい。ブロック３３０では、補助関数の出力結果がルート変数Ａの値と共に追加されてよい。ブロック３４０では、ブロック３３０からの出力データは、現在処理されている１６ワードブロックにおける１６ワードから選択されるワードＸ〔ｋ〕と共に追加されてよい。ブロック３５０では、ブロック３４０からの出力データは、ｍラウンドのｎ回目の繰返しのためにＴテーブルから選択された定数値であるＴ〔ｍ、ｎ〕と共に追加されてよい。ブロック３６０では、ブロック３５０からの出力データ３５０は、Ｓ〔ｍ、ｎ〕ビット左に移動してよい。Ｓ〔ｍ、ｎ〕は、ｍラウンドのｎ回目の繰返しの予め決められた値の変数である。ブロック３７０では、ブロック３６０からの出力データは、ルート変数Ｂの値と共に追加されてよい。１ラウンドの１回の繰返しは、ブロック３７０における演算が終了した後に完了する。ブロック３７０からの出力データは、ルート変数Ａを更新するために用いられる。１回の繰返しの終了後、変数Ａ、Ｂ、Ｃ、Ｄの値は（"Ａ→Ｂ→Ｃ→Ｄ→Ａ"）と循環するので、Ｂの値は、ブロック３７０からの出力データとして直接設定され、その結果、各繰返しの後、Ｂ→Ｃ→Ｄ→Ａという循環が実際に実行される。
【００２１】
図４は、ＭＤ５ダイジェスティングプロセスの各ラウンドの各繰返しに含まれる演算を実行するプロセスの他の一例を示す。ルート変数Ａ、Ｂ、Ｃ、Ｄの値は、ブロック４１０において受信されてよい。ラウンド１の最初の繰返しでは、Ａ、Ｂ、Ｃ、Ｄの受信された値は初期値である。他のすべての繰返しでは、受信された値は、前の繰返しからの値である。同じくブロック４１０において、１つの繰返しが終了した後、次の繰返しが開始する前に、変数Ａ、Ｂ、Ｃ、Ｄの値は、Ｂ→Ｃ→Ｄ→Ａというように循環する。図３に示すような、Ｘ〔ｋ〕、Ｔ〔ｍ、ｎ〕および、ルート変数Ａの値は、１回の繰返しが開始する前に入手できることがわかる。そして、ブロック４３０において補助関数が選択されかつ実行される一方で、Ｘ〔ｋ〕、Ｔ〔ｍ、ｎ〕および、Ｓ〔ｍ、ｎ〕がブロック４２０で合算される。ブロック４４０では、ブロック４３０からの出力データは、ブロック４２０からの出力データと共に加算される。ブロック４５０では、ブロック４４０からの出力データは、Ｓ〔ｍ、ｎ〕ビット左に移動してよい。ブロック４６０では、ブロック４５０からの出力データは、ルート変数Ｂの値と共にさらに加算されてよい。ブロック４６０からの出力データは、Ａの値を更新するべく用いられてよい。ルート変数間の循環（"Ａ→Ｂ→Ｃ→Ｄ→Ａ"）により、Ｂの値は、ブロック４６０からの出力データの値に直接設定されることができる。補助関数が選択されかつ実行される間にＸ〔ｋ〕、Ｔ〔ｍ、ｎ〕および、Ａの値が合算されるので、１回の繰返しのクリティカルパスには、１つの補助関数、２つの加算、および、１つのシフトが存在する。と比較すると、図４に示すプロセスは、１回の繰返しのクリティカルパスに図３に示すプロセスより少ない２つの加算を有する。
【００２２】
図５は、ＭＤ５ダイジェスティングを実行するシステムの一例を示す。このシステムは、ルート変数記憶装置５１０、準備機構５２０、コントローラ５３０、および、ＭＤ５計算機構５４０を含む。ルート変数記憶装置５１０は、ルート変数Ａ、Ｂ、Ｃ、Ｄをそれぞれ格納する記憶領域Ａ（５１２）、記憶領域Ｂ（５１４）、記憶領域Ｃ（５１６）、および、記憶領域Ｄ（５１８）を有する。準備機構５２０は、パディングおよびアペンドなどの手段により入力メッセージを準備し、結果として生じたメッセージは、５１２ビットの倍数である長さを有する。準備機構はまた、６４の値をもつＴテーブルを作成し、各値は、ｍラウンドのｎ回目の繰返しのために式９に示すようなＴ〔ｍ、ｎ〕として用いられる。また、準備機構は、ＭＤ５計算機構に方程式９で示すような値Ｓ〔ｍ、ｎ〕を提供する。さらに、準備機構は、ＭＤ５仕様に従い、１ラウンドの各繰返しで要求される、準備された入力メッセージワードＸ〔ｋ〕（式９で示した）を供給する。一実施例では、準備機構は、図５に示す他の構成要素とは別個のものであってよい。他の実施例では、準備機構は、他の構成要素と全体的にまたは部分的に結合することにより、ＭＤ５ダイジェスティングプロセスのための所望の結果を生じることもできる。ＭＤ５計算機構５４０は、方程式９に含まれる演算を実行し、ルート変数記憶装置内のルート変数Ａを更新するためにさらに用いられる各繰返しの結果を生じる。ＭＤ５計算機構は、プロセッサ、特定用途向け集積回路（ＡＳＩＣ）、プログラマブル・ロジック、および、コンピュータ・プログラムのような回路構成を含んでよい。コントローラ５３０は、１回の繰返しが実行された後、次の繰返しが開始される前に、ルート変数記憶装置内でルート変数Ａ、Ｂ、Ｃ、Ｄを例えば、（"Ｂ→Ｃ→Ｄ→Ａ"）のように循環させる。コントローラは、また、どんなパラメータ（Ｘ〔ｋ〕、Ｔ〔ｍ、ｎ〕、Ｓ〔ｍ、ｎ〕など）がＭＤ５の計算機構に利用できるか、また、いつできるかを準備機構に指示する。また、コントローラは、ＭＤ５機構の計算機構内の構成要素を制御して、それらが協働してそれぞれの繰返しの結果を生じるようにする。さらに、コントローラは、要求された動作が実行されたか、または、要求されたデータが活用された場合、ルート変数記憶装置、準備機構、および、ＭＤ５計算機構から通知を受け取ることにより、要求される演算を実行するのに必要な次の指示を出してもよい。コントローラの制御下では、ＭＤ５の計算機構は、入力メッセージにおける各１６ワードブロックに対し、各ラウンドが１６回の動作の繰返しを含む４ラウンドの動作を実行する。入力メッセージにおける１６ワードブロックのすべてが処理されると、記憶領域Ａ、Ｂ、Ｃ、Ｄに格納されたデータは、結果として入力メッセージの１２８ビットダイジェストとなる。
【００２３】
図６は、本発明の一実施例に従う、ＭＤ５ダイジェスティングプロセスを実行するＭＤ計算機構５４０（図５参照）における構成要素を示す。ＭＤ５計算機構は、前加算機６１０、関数計算機構６２０、および、後プロセッサ６３０を含む。前加算機６１０は、３つのパラメータＸ〔ｋ〕、Ｔ〔ｍ、ｎ〕、ルート変数Ａから加算を実行する。Ｘ〔ｋ〕、およびＴ〔ｍ、ｎ〕は、ｍラウンドのｎ回目の繰返しに必要とされる、準備された入力メッセージにおける１ワード、および、Ｔテーブルから得られた定数である。Ｘ〔ｋ〕、および、Ｔ〔ｍ、ｎ〕は、コントローラ５３０の指示の下で準備機構５２０により提供される。前加算機は、関数計算機構６２０が補助関数Ｆ、Ｇ、Ｈ、Ｉを計算している間にそれと並行して加算を実行してよい。関数計算機構６２０は、Ｆ関数計算器６２２、Ｇ関数計算器６２４、Ｈ関数計算器６２６、および、Ｉ関数計算器６２８を含む。Ｆ、Ｇ、Ｈ、Ｉ関数計算器は、ルート変数Ｂ、Ｃ、Ｄに基づき、方程式１、２、３、４に含まれる演算をそれぞれ実行する。一実施例では、関数計算器のすべてが各ラウンドの各繰返しで稼動するよう設定されてよく、後プロセッサ６３０により後処理されるために１つだけ結果が選択される。他の実施例では、計算の１つのラウンドに基づき関数計算器を選択するべく、関数セレクタを用いることもでき、その結果、ＭＤ５仕様に必要とされる１つの関数だけが計算される。
【００２４】
後プロセッサ６３０は、関数結果セレクタ６４０、第１の加算器６５０、シフタ６６０、および、第２の加算器６７０を含む。関数結果セレクタ６４０は、計算のラウンドに従い、関数計算機構６２０におけるＦ、Ｇ、Ｈ，Ｉの関数計算器（ラウンド１に対しＦ関数、ラウンド２に対しＧ関数、ラウンド３に対しＨ関数、ラウンド４に対しＩ関数）による結果を選択する。ハードウェアでの実行では、関数セレクタがラウンドに必要な関数計算器を選択するのに使用される場合でも、関数結果セレクタがなお必要である。第１の加算器６５０は、関数結果セレクタ６４０から選択された関数結果を前加算機５１０からの出力データと共に加算する。第１の加算器６５０からの出力データは、シフタ６６０により、左にＳ〔ｍ、ｎ〕だけシフトされる。Ｓ〔ｍ、ｎ〕は、ｍラウンドのｎ回目の繰返しに対し、準備機構５２０により提供される。シフタ６６０からの出力データは、第２の加算器６７０によってルート変数Ｂの値と共にさらに加算され、現在の繰返しの結果を生じる。繰返しの結果は、ルート変数Ａの値を更新するべくさらに用いられる。ルート変数の循環（"Ａ→Ｂ→Ｃ→Ｄ→Ａ"）により、繰返しの結果は、ルート変数Ｂの値を更新するのにそのまま用いることができる。図６に示すＭＤ５計算機構における構成要素は、コントローラ５３０の制御下で協働して繰返しの結果を生じる。例えば、コントローラは、現在計算されているラウンドに基づいて４つの関数結果から１つの結果を選択するよう関数結果セレクタ６４０に指示してよい。
【００２５】
図６に示すように、繰返しｎから結果を生じるべく、補助関数の計算、２つの加算（第１および第２の加算器により実行される）、および、１つのシフトが実行される（３つのパラメータの前加算は、補助関数の計算と並行して実行できるので、別々にカウントする必要はない）。多くのネットワークプロセッサに対するこれらの演算が完了するには、少なくとも２クロックサイクルかかる。入力メッセージの１つの１６ワードブロックには、４つの計算のラウンドがあり、各ラウンドは、１６回の繰返しを含む。したがって、１つの１６ワードブロックの１２８ビットダイジェストを生成するには、少なくとも１２８サイクルかかる。ＭＤ５ダイジェスティングプロセスの速度を向上させる１つの方法として、連続する繰返しの計算をパイプライン化することがある。繰返しｎからの結果（繰返しｎ＋１に対するルート変数Ｂの値）は、繰返しｎ＋１における補助関数への入力なので、連続する繰返しの計算は、すぐにパイプライン化することはできない。したがって、図６に従うＭＤ５ダイジェスティングシステムは、２サイクルごとに１つの繰返しのスループットを有する。
【００２６】
４つのルート変数Ａ、Ｂ、ＣおよびＤの循環の方法は、例えばＡ→Ｂ→Ｃ→Ｄ→Ａというように、１つの繰返しから次の繰返しへと実行されるものなので、いずれの２つの連続する繰返しも２つの同じ入力を共有することがわかる。例えば、繰返しｎにおける補助関数への入力の順序がＢ−Ｃ−Ｄ（ルート変数Ｂ、Ｃ、Ｄの記憶領域からの値）であると仮定すると、繰返しｎ＋１における補助関数への入力順序は、Ａ−Ｂ−Ｃ（ルート変数Ａ、Ｂ、Ｃの記憶領域からの値）となるはずである。この例では、繰返しｎおよびｎ＋１は、ルート変数ＢおよびＣの記憶領域からの値である２つの同じ入力を共有する。それ故、その入力の値だけは、繰返しｎの最後がＡになるまで入手できないのは、その値が繰返しｎの最後に更新されるからである。４つの補助関数のすべてがビットごとの演算のみを含むので、３２ビットのそれぞれは、個別に処理される。各ビット位置に対し繰返しｎから入手できる値ＢおよびＣが与えられると、３２ビットそれぞれの補助関数の結果は、繰返しｎの最後に更新される、ルート変数Ａにおける対応ビットの値に従う２つの値の１つになるはずである。したがって、２つの値は、繰返しｎ＋１の補助関数に対し以下のように計算されてよい。Ａの１つの値、すなわちＡにおける各ビットに対応する１つを、１に設定し、Ａにおける各ビット値に対応するその他を、０に設定する。この方法では、繰返しｎ＋１は、繰返しｎがまだ実行中に開始されてよい。例えば、繰返しｎ＋１は、繰返しｎの第２のサイクルにおいて開始されてもよい。繰返しｎの結果が入手できるようになれば、それをビットごとに使用して、繰返しｎ＋１における補助関数の正しい出力を選択することができる。１つの繰返しを完了するのに２クロックサイクルかかると仮定する。第２のサイクルが、前の繰返しの結果を用いて補助関数の出力の選択から開始した場合は、したがって、連続する繰返しはパイプライン化されることができる。このようなスキームによるＭＤ５ダイジェスティングは、クロックサイクルごとに１つの繰返しのスループットを実現する。
【００２７】
図７は、ＭＤ５ダイジェスティングプロセスをパイプライン化できるＭＤ５計算機構の一実施例を示す。ＭＤ５計算機構は、前加算機７１０、関数計算機構７２０、および、後加算機７１０、関数計算機構７２０、および、後プロセッサ７４０を含む。前加算機７１０は、３つのパラメータＸ〔ｋ〕、Ｔ〔ｍ、ｎ〕、および、ルート変数Ａから加算を実行する。Ｘ〔ｋ〕、およびＴ〔ｍ、ｎ〕は、コントローラ５３０の指示の下で準備機構５２０により提供される。前加算機は、関数計算機構７２０が補助関数Ｆ、Ｇ、Ｈ、Ｉを計算している間にそれと並行して加算を実行してよい。関数計算機構７２０は、２組の関数計算器を含む。第１の組は、Ｆ関数計算器１（７２２）、Ｇ関数計算器１（７２４）、Ｈ関数計算器１（７２６）、Ｉ関数計算器１（７２８）であり、第２の組は、Ｆ関数計算器２（７３０）、Ｇ関数計算器２（７３２）、Ｈ関数計算器２（７３４）、Ｉ関数計算器２（７３６）である。Ｆ、Ｇ、Ｈ、Ｉ関数計算器は、ルート変数Ｂ、Ｃ、Ｄの値に基づき、方程式１、２、３、４に含まれる演算をそれぞれ実行する。第１の組の関数計算器は、ルート変数Ｂのすべてのビットが０に設定されるＧ、Ｈ、Ｉ関数を計算し、また、第２の組の関数計算器は、ルート変数Ｂのすべてのビットが１に設定されるＦ、Ｇ、Ｈ、Ｉ関数を計算する。値Ｂ、Ｃ、Ｄが受信されると、２組の関数計算器は並行して稼動することができる。一実施例では、各設定における４つの関数計算器のすべてが各ラウンドの各繰返しごとに設定されることもでき、後処理プロセッサ７４０による後処理のために各設定から１つの結果だけが選択される。他の実施例では、計算のラウンドに基づき各設定ごとに関数計算器を選択すべく、関数セレクタを用いることにより、ＭＤ５仕様に必要とされるラウンドの各設定ごとに１つの関数のみが計算される。
【００２８】
後プロセッサ７４０は、２つの関数結果セレクタ（関数結果セレクタ１（７５０）および関数結果セレクタ２（７５５））、ビットセレクタ７６０、第１の加算器７６５、シフタ７７０、および、第２の加算器７７５を含む。関数結果セレクタ１（７５０）は、計算のラウンドに従い、関数計算器の第１の組から第１の結果を選択する（ラウンド１はＦ関数、ラウンド２はＧ関数、ラウンド３はＨ関数、および、ラウンド４はＩ関数）。関数結果セレクタ２（７５５）は、関数計算器の第２の組から、第１の結果に対応する第２の結果を選択する。ハードウェアでの実行においては、１ラウンドに対する関数計算器の各組で必要な関数計算器を選択するべく関数セレクタを使用する場合でも、関数計算器の各組ごとに関数結果セレクタがなお必要である。関数結果セレクタ１により選択された第１の結果は、０であるＢの値に対応する（すなわち、Ｂのすべてのビットは、０に設定される）。また、関数結果セレクタ２により選択された第２の結果は、（２３２−１）のＢの値に対応する（すなわち、Ｂのすべてのビットは、１に設定される）。ビットセレクタ７６０は、コントローラ５３０の指示の下、前の繰返しの結果に基づき、第１の結果と第２の結果との間で正しい関数結果をビットごとに選択する。第１の加算器７６５は、ビットセレクタ７６０からの選択された関数結果を前加算機７１０からの出力データと共に加算する。第１の加算器７６５からの出力データは、シフタ７７０により左にＳ〔ｍ、ｎ〕だけシフトされる。Ｓ〔ｍ、ｎ〕は、ｍラウンドのｎ回目の繰返しに対し、準備機構５２０により提供される。シフタ７６５からの出力データは、第２の加算器７７５によってルート変数Ｂの値と共にさらに加算され、現在の繰返しの結果を生じる。繰返しの結果は、ルート変数Ａの値を更新するべくさらに用いられる。ルート変数の循環（"Ａ→Ｂ→Ｃ→Ｄ→Ａ"）により、繰返しの結果は、ルート変数Ｂの値を更新するのにそのまま用いることができる。
【００２９】
図７に示すＭＤ５計算機構における構成要素は、コントローラ５３０の制御下で協働して繰返しの結果を生じる。例えば、コントローラは、現在計算されているラウンドに基づいて４つの関数計算器の第１の組から１つの結果を選択するよう関数結果セレクタ１（７５０）に指示してよい。また、コントローラは、異なるクロックサイクルにどれだけの作業量を割り当てるかを決定することができる。１つの繰返しの結果を生じるのに必要なすべての演算が２サイクルで完了すると仮定する。ビットセレクタ７６０が正しい関数結果を選択し始めたときにコントローラが第２のサイクルを開始し、それが前の繰返しの結果を必要とする場合、第１のサイクルに含まれる演算は、前の繰返しの結果には依らない。したがって、連続する繰返しはパイプライン化されることができる。
【００３０】
図８は、本発明の一実施例に従う、ＭＤ５ダイジェスティングプロセスをパイプライン化するプロセスを示す表である。サイクル１においてＭＤ５ダイジェスティングが開始すると仮定する。サイクル１では、繰返し１のための補助関数計算に並行して前加算が実行されてよい。２組（第１の組は０のＢの値に対応し、第２の組は（２３２−１）のＢの値に対応する）は、並行に計算されることができる。また、サイクル１では、繰返し１に対する第１の結果は、第１の組の関数から選択され、第２の結果は、第２の組の関数から選択されてよい。サイクル２では、繰返し１に対するルート変数Ａの初期値に基づき、第１の結果と第２の結果との間で正しい関数結果がビットごとに計算されてよい。また、サイクル２では、繰返し１に対し２つの加算と１つのシフトとが（例えば図７に示す第１の加算器、第２の加算器、および、シフタにより）実行されてよい。また、サイクル２で繰返し２を開始してもよい。２つの組における補助関数計算、および、２つの組の補助関数計算それぞれからの関数結果の選択が実行されてよい。サイクル２の終わりまでに、繰返し１の結果が生じ、その結果は、Ａ、Ｂ、Ｃ、Ｄの循環により順番に繰返し２の値Ｂになるルート変数Ａの値を更新するよう用いられる。正しい関数の結果は、（現在入手可能な）繰返し１からの結果に基づき選択されてよく、２つの加算および１つのシフトが繰返し２の間に実行されてよい。サイクル３の終わりに繰返し２の結果が生成され、生成された結果は、最終的に繰返し３における値Ｂとなる。また、サイクル３で繰返し３が開始されてもよい。前加算、２組における補助関数計算、および、２組それぞれからの関数結果の選択がサイクル３において実行されてよい。準備された入力メッセージにおける１６ワードブロックすべてが処理されるまで、プロセスは続けられる。入力メッセージの最終的な１２８ビットダイジェストは、ルート変数Ａ、Ｂ、Ｃ、Ｄにおけるビットの連結となる。このようなパイプライン化スキームを用いることにより、ＭＤ５ダイジェスティングを実行するシステムは、サイクルごとに１つの繰返しのスループットを実現する。
【００３１】
図９は、ＭＤ５ダイジェスティングを実行できるネットワークシステムを示す。このシステムは、交換機機構９１０（クロスバーまたは共有メモリ交換機機構）により相互接続されるラインカード９２０（ブレード）の集合を含む。個別のラインカードは、同じ物理的位置または異なる物理的場所（異なる都市など）に配置されてよい。例えば、交換機機構は、共通スイッチインターフェース（ＣＳＩＸ）、または、ハイパートランスポート、ＰＣＩ、同期光通信ネットワーク、ＲａｐｉｄＩＯ、および／またはＵＴＯＰＩＡ（Ｕｎｉｖｅｒｓａｌ  Ｔｅｓｔ  ＆  Ｏｐｅｒａｔｉｏｎｓ  ＰＨＹ  Ｉｎｔｅｒｆａｃｅ  ｆｏｒ  ＡＴＭ）などのような他の構築技術でもよい。
【００３２】
個別のラインカード（例えば９２０Ａ）は、ネットワーク接続の通信を処理する１つまたはそれ以上の物理層デバイス（光、ワイヤ、および、ワイヤレス物理層）を含むこともできる。物理層は、異なるネットワーク媒体により伝達される物理的信号とデジタルシステムにより用いられるビット（例えば"０"および"１"）との間を変換する。ラインカード９２０は、エラー検出および／または補正などのフレームに対し演算を実行することができるフレーマデバイス（例えばイーサネット、同期光ネットワーク（ＳＯＮＥＴ）、ハイレベルデータリンク（ＨＤＬＣ）フレーマまたは他の「レイヤ２」デバイス）９２４を含んでもよい。図に示すラインカード９２０は、また、物理層９２２を介し受信されるパケットに対しパケット処理演算を実行し、かつ、そのパケットを転送すべく交換機機構９１０を介し出口インターフェースを提供するラインカードへと導く１つまたはそれ以上のプロセッサ９２６を含んでもよい。場合によっては、フレーマデバイス９２４の代わりにネットワークプロセッサ９２６が「レイヤ２」の役目を担ってもよい。
【００３３】
ネットワークプロセッサ９２６は、インテル（Ｒ）ＩＸＰネットワークプロセッサ、または、設計が異なる他のネットワークプロセッサであってもよい。ネットワークプロセッサは、単一の集積回路にパケット処理エンジンの集まりを含む。個々のエンジンは、多数の実行スレッドを提供する。また、ネットワークプロセッサは、コアプロセッサ（たいがいはネットワーク運用に含まれる「制御プレーン」タスクを実行するようプログラムされている）を含む。コアプロセッサは、「データプレーン」タスクも処理する。ネットワークプロセッサ９２６は、また、プロセッサと他のネットワーク要素との間でパケットをやりとりできる少なくとも１つのインターフェースを含む。例えば、プロセッサは、プロセッサ９２６が交換機機構に接続された他のプロセッサまたは回路構成にパケットを伝送できるようにする交換機機構インターフェース９１０を含む。プロセッサ９２６は、また、プロセッサが物理層（ＰＨＹ）および／またはリンク層デバイス（ＭＡＣまたはフレーマデバイスなど）と通信できるようにするインターフェースを含むことができる。プロセッサ９２６は、例えば、ホストまたは他のネットワークプロセッサと通信するためのインターフェース（ＰＣＩバスインターフェースなど）も含む。さらに、プロセッサ９２６は、メモリコントローラなどのエンジン、ハッシュエンジン、および、内部スクラッチパッドメモリにより共有される他の構成要素も含む。
【００３４】
図９に示すように、各ラインカード９２０は、ＭＤ５暗号化を実行する少なくとも１つのＭＤ５モジュール９３０（例えば９３０Ａ）に動作可能に結合されることができる。一実施例では、ＭＤ５モジュールは、ラインカードから独立していてよい。他の実施例では、ＭＤ５モジュールは、ラインカードと一体化していてもよい。また、一実施例では、ＭＤ５モジュールは、ネットワークプロセッサ９２６の一部、または、物理層９２２の一部であってもよい。さらに他の例では、ＭＤ５モジュールは、リンク層、ネットワーク層、および／または、アプリケーション層などの他のネットワーク層に配置されてもよい。
【００３５】
本開示の実施例を図１−９を参照して説明してきたが、他の多くの方法を用いても本発明を実施できることは当業者であれば容易に理解できるであろう。例えば、機能ブロックまたはプロセスの実行順序は変更してもよく、および／または、記載された機能ブロックまたはプロセスのいくつかを変更するか、削除するか、または、組み合わせてもよい。
【００３６】
本発明のさまざまな態様については先に述べたとおりである。本開示をわかりやすく説明すべく、特定の数、システム、および構成を記載している。しかしながら、本開示を特定の詳細な記述なしに実施しうることは、本開示によって利益を得る当業者にとっては明らかである。その他、本発明の開示を不明瞭にしないよう、よく知られた特徴、構成要素、またはモジュールなどは省略するか、簡易化するか、組み合わせるか、または、分割するなどした。
【００３７】
明細書中に記載された本発明の開示の実施例は、ハードワイヤード回路、デジタル回路、アナログ回路、プログラマブル回路といった回路において実行してよい。また、コンピュータプログラムで実行してもよい。そのようなコンピュータプログラムは、ハイレベルプロシージャまたはオブジェクト指向プログラミング言語にコード化されてよい。プログラムは、必要であれば、アセンブリまたはマシン言語で実行することもできる。言語は、コンパイルまたは翻訳されてよい。また、これらの技術は、様々なネットワーク環境で使用することができる。このようなコンピュータプログラムは、汎用または専用プログラマブル処理システムによって読み取られることができる記憶媒体または装置（例えばハードディスクドライブ、フロッピーディスクドライブ、リードオンリーメモリ（ＲＯＭ）、ＣＤ−ＲＯＭデバイス、フラッシュメモリデバイス、デジタル多用途ディスク（ＤＶＤ）、または、他の記憶装置）に格納されてよく、これらの記憶媒体または装置は、処理システムにより読み取られて本明細書中に記載された手順を実行するときに、処理システムを設定しかつ動作させる。本開示の実施例は、また、処理システムと共に使用するよう構成され、本明細書中に記載された機能を実行すべく処理システムを特定の予め定義された方法で動作させるためのマシン可読記憶媒体として実行するように考えられてもよい。
【００３８】
以上、本発明の一側面を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更又は改良を加えることができる。その様な変更又は改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図１】
2008500590.tif 000003
【図２】
2008500590.tif 000004
【図３】
2008500590.tif 000005
【図４】
2008500590.tif 000006
【図５】
2008500590.tif 000007
【図６】
2008500590.tif 000008
【図７】
2008500590.tif 000009
【図８】
2008500590.tif 000010
【図９】
2008500590.tif 000011
【国際調査報告】
2008500590.tif 000012
2008500590.tif 000013