(57)【特許請求の範囲】
【請求項１】
各々が最大ｎビットを有する２つの２進数Ａ及びＢの乗算のモジュロＮ、但しＮは奇数、を計算するために、ＡＢ２-mk mod Ｎを下記アルゴリズムに従い計算する回路であって、
Z0＝0
for i=0 to m-1
Xi=Zi+AiB
yi=sxi,0 mod R
Zi+1=(Xi+yiN)/R
end
[但し、Aiは数Ａを、各々がｋビットを有するｍブロックに区分化してΣjＡｉＲi（０≦ｊ≦ｍ−１）と表した場合の係数であり、ｍはｍｋ≧ｎ＋２を満たす最小の整数であり）、
xi,0はXiの最下位ｋビットであり、
ｓ＝（−１／Ｎ0）mod Ｒであり、
Ｎ0＝Ｎの最下位ｋビットであり及びＲ＝２kである]、
前記アルゴリズムは、Xi及びyiを計算する第１のフェーズ及びZi＋１を計算する第２のフェーズを有し、
前記回路は、直列に接続されたｄ＋１個の処理要素、但しｄ＝（ｎ＋ｋ）／２ｋである、を含み、
前記各処理要素は、数Ａの徐々に上位に向かうｋビットのブロック、及び、数Ｂ及びＮ 各々の徐々に上位に向かう２ｋビットのブロックを夫々処理し、
各々がｋビットの累算レジスタ部分290及び第２の累算レジスタ部分291であって、前記アルゴリズムにおける１〜ｍまでの各サイクルの間に、中間結果Xiを受信し及び保持し、但し、前記レジスタ部分290及び291は、当該処理要素とは別個のレジスタ中の一区分であってもよい、累算レジスタ部分290及び第２の累算レジスタ部分291と、
第１のマルチプレクサ293であって、各サイクルの前記第１のフェーズの間には、２ｋビットのデータZi＋１を出力として選択し、前記出力の最左端ｋビットは、前記直列に接続された処理要素内で当該処理要素より１ブロック上位のｋビットを処理する後続処理要素内の前記第1の累算レジスタ部分292から選択され、前記出力の最右端ｋビットは、当該処理要素内の第２の累算レジスタ部分291の最左端ｋビットから選択され、各サイクルの前記第２のフェーズの間には、２ｋビットのデータXiを出力として選択し、前記出力の最左端ｋビットは、当該処理要素の第２の累算レジスタ部分291から選択され、前記出力の最右端ｋビットは、当該処理要素の第１の累算レジスタ部分290から選択される、第１のマルチプレクサ293と、
前記数Ｂの２ｋビットのブロックを記憶する因数レジスタ部分220と、
前記数Ｎの２ｋビットのブロックを記憶するモジュロ・レジスタ部分240と、
各サイクルの前記第１のフェーズの間に、前記因数レジスタ部分220から、２ｋビットの数Ｂのデータを出力として選択し、各サイクルの前記第２のフェーズの間に、前記モジュロ・レジスタ部分240から２ｋビットの数Ｎのデータを選択する、第２のマルチプレクサ221と、
前記第２のマルチプレクサ210の出力を記憶する一時レジスタ298と、
各サイクルの前記第１のフェーズの間に、前記数Ａの２進表現から、データのブロックを表すｋビットのデータを出力として選択し、各サイクルの前記第２のフェーズの間に、数Ａの最も下位のｋビットを処理する処理要素からの出力yiを選択する、第３のマルチプレクサ231と、
各サイクルの前記第１フェーズではAiBを、第２フェーズではyiNを計算するためのｋビット×ｋビットの第１の乗算器273及び第２の乗算器272であって、第１の乗算器273は、前記第３のマルチプレクサ231からの出力ｋビットと、前記一時レジスタ298からの最左端ｋビットとを乗算し、その出力の最左端ｋビットが、前記後続処理要素における部分積として使用され、前記第２の乗算器272は、前記第３のマルチプレクサ231からの出力ｋビットと、前記一時レジスタ298からの最右端ｋビットとを乗算する、第１の乗算器273及び第２の乗算器272と、
前記第１の乗算器273と第２の乗算器272の出力とを加算し、且つ、前記先行処理要素から、第１のキャリー入力信号をその最下位桁に受け入れる、２ｋビットの中間加算器275であって、最左端部分が、前記第１の乗算器273からの最右端ｋビット出力であり、最右端部分が、前記第２の乗算器272からの最右端ｋビット出力である第１の入力と、最左端部分が、前記第２の乗算器272からの最左端ｋビット出力であり、最右端部分が、前記直列に接続された処理要素内で当該処理要素より１ブロック下位のｋビットを処理する先行処理要素からのｋビット部分積である第２の入力を加算し、前記後続処理要素への入力として、第１のキャリー出力信号を生成する、２ｋビットの中間加算器275と、
２ｋビットの出力加算器285であって、前記第１フェーズでは前記第１のマルチプレクサ293の出力Ziと、前記中間加算器275からの出力AiBとを加算し、及び、前記第２フェーズでは前記第１のマルチプレクサ293の出力Xiと、前記中間加算器275からの出力yiNとを加算し、前記先行処理要素から、第２のキャリー入力信号をその最下位桁に受け入れ、
前記出力加算器285からの出力の下位ｋビットは前記第１の累算レジスタ部分290へと及び上位ｋビットは第２の累算レジスタ部分291へと、夫々、供給され、前記出力加算器285は、前記後続のプロセッサ要素への入力として、第２のキャリー出力信号を生成する、出力加算器285と、
を含む回路。
【請求項２】
数Ａの最も下位のｋビットを処理する前記処理要素が、数ｓを記録するためのレジスタ160と、yi=sxi,0 mod Rを計算するための乗算器180と、前記乗算器180の出力yiを保持するためのレジスタ130とをさらに含む、請求項１記載の回路。
【請求項３】
各々が最大ｎ＋１ビットを有する２つの２進数Ａ及びＢの乗算のモジュロＮ、但しＮは奇数、を計算するために、ＡＢ２-mk mod Ｎを下記アルゴリズムに従い計算する回路であって、
Z0＝0
for i=0 to m-1
Xi=Zi+AiB
yi=sxi,0 mod R
Zi+1=(Xi+yiN)/R
end
[但し、Aiは数Ａを、各々がｋビットを有するｍブロックに区分化してΣjＡｉＲiと表した場合の係数であり（但しｍｋ≧ｎ＋２及び０≦ｊ≦ｍ−１）、
xi,0はXiの最下位ｋビットであり、
ｓ＝（−１／Ｎ0）mod Ｒであり、
Ｎ0＝Ｎの最下位ｋビットであり及びＲ＝２kである]、
前記アルゴリズムは、Xi及びyiを計算する第１のフェーズ及びZi＋１を計算する第２のフェーズを有し、
前記回路が、
Ａ、Ｂ、Ｎ、及びｓの各々を夫々記憶するＡレジスタ10、Ｂレジスタ20、Ｎレジスタ40、及びｓレジスタ60と、
前記アルゴリズムにおける各サイクル（１〜ｍ）において計算されるyi、Ziを夫々記憶するｙレジスタ30及びZレジスタ50と、
前記第１のフェーズで、Ａレジスタ10の下位から上位へ順次ｋビットごと取り出すマルチプレクサ11と、
前記第１フェーズでは数Ａの前記ｋビットを、及び、前記第２フェーズでは、ｙレジスタ30からyiを取り出して、乗算器70に出力するマルチプレクサ31と、ここで前記乗算器70は、前記第１フェーズではAiBを、前記第２フェーズではyiNを夫々計算し、
前記第１のフェーズでは数Ｂを、及び第２のフェーズでは数Ｎを取り出して、夫々前記乗算器70に出力するマルチプレクサ21と、
前記第１フェーズで得られる乗算値AiBの下位ｋビットと、当該サイクルの1つ前のサイクルで計算され前記Zレジスタに記憶されている（但しZ0＝0）Ziの最右端のｋビットとを加算してXiを出力する加算器65と、
前記Xiの最下位ｋビットxi,0とｓレジスタからのｓを乗算して下位ｋビットをyiとしてｙレジスタに出力する乗算器80と、
前記第１フェーズでは、前記乗算値AiBの上位ｎ＋１ビットと、前記Ziをｋビット右にシフトしたものとを加算してＸi＝Ｚi＋ＡiＢの上位ｎ＋１ビットを得てZレジスタへと出力し、前記第２フェーズではZレジスタに記憶された前記ＸiとyiNの上位ｎ＋１ビットを加算してZi+1を得て前記Zレジスタへと出力する加算器85と、
を含む回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は暗号化及び解読を実行する方法及び装置に関する。本願は、所望の暗号法の目標及び機能を迅速且つ正確に確実に達成する機構として、モジュロＮ羃法を使用する全体システムに関する。本開示の第１部は、モジュラ乗算を実行する方法及びその関連装置の構成に関する。本開示の第２部は、問題をより扱い易い断片に区分化して、モジュラ乗算を実行する改善された装置に関し、それにより、（必要に応じて）個々の同一の処理要素が構成される。本開示の第３部は、結果の一連の処理要素をパイプライン方式に使用することによる、スピード及びスループットの向上に関する。本開示の第４部は、モジュラ乗算演算への入力ステップまたはステージとして好ましい一意の逆演算を計算する装置及び方法に関する。本開示の第５部は、指数演算を実行する元来意図された機能において、ここで述べるモジュラ乗算システムを利用することに関する。本開示の第６部は、指数演算と併せて、中国剰余定理（Chinese Remainder Theorem）を利用することに関する。本開示の第７部は、システム全体の確率且つ正確な演算を保証するために使用されるチェックサム回路の構成及び利用に関する。本願は特に、本開示の第２部で述べる発明に重点を置くものである。
【０００２】
【従来の技術】
詳細には、本発明は各々がｎビットまでを有する２進数を乗算する回路、システム及び方法に関し、ここで乗算は奇数Ｎを法とする。特に、本発明は因数の１つをｍブロックに区分化し、各ブロック内にはｋビットが存在し、ｍｋ≧ｎ＋２なる自然拘束があてはまる。より詳細には、本発明は乗じられる因数が多ビットを有するときの、モジュロＮ乗算に関連する。本発明はまた、暗号化において使用されるモジュラ指数関数の計算における、ここで述べるモジュラ乗算機能ハードウェアの使用に関する。便利な逆数の計算や、装置全体のためのチェックサム機構などの補助的機能もここでは提供される。ここで使用される区分化はまた、カスケード接続されて、Ｎの大きな値のための重要な拡張能力を提供する処理要素の構成を生成する。これは次に、プロセッサ要素をパイプライン方式に使用するモダリティにつながる。プロセッサ要素のカスケード接続はまた、プロセッサ要素チェーンを、Ｎの異なる別々の因数に独立に作用する別々の断片に効果的に区分化するように有利に制御可能である。
【０００３】
本開示から最適な理解を求める当業者であれば、まず最初にここで示される方法及び方法の目的が、最新の暗号法で必要とされる特定の算術関数の性能であり、これらの演算が標準の乗算、反転及び累乗ではなく、モジュロＮ演算であることが理解できよう。本願が標準の演算とは対照的に、モジュロ算術回路及び方法に関する事実は、最も心に留めておく必要がある。なぜなら、モジュラ演算は除算を含意し、その実行及び計算は、特にモジュロＮ羃法が関わる場合に極めて困難であるからである。
【０００４】
本発明の特定の態様を利用する好適なシステムでは、加算器アレイ及び乗算器アレイが、一連のほぼ同一のプロセッサ要素に効果的に区分化され、各々のプロセッサ要素（ＰＥ）はデータのサブブロックに作用するように実行する回路及び方法に関する。乗算器アレイ及び加算器アレイはこのように区分化される。汎用構造を複数の直列接続されたプロセッサ要素に再構成する能力を理解した上で、本発明では、各プロセッサ要素がパイプラインの一部として、複数の動作サイクルに渡って動作する。パイプライン操作モードは更に、一連の数の乗算に拡張され、そこでは全てのプロセッサ要素が連続的に活発に結果を生成する。
【０００５】
２進数のモジュロＮ乗算は、最新の公開キー暗号法において重要な演算である。乗算及び続いて行われる大きな整数のファクタリングにもとづく暗号化システムのセキュリティは、使用される数のサイズ、すなわち、数のビット数または桁数に直接関連付けられる。例えば、乗算に関わる２つの因数の各々が、最大１０２４ビットを有する。しかしながら暗号化の目的上、このモジュロ（数Ｎ）乗算を実行することが必要である。従ってここで考慮される乗算は、２つのｎビットの数を乗算することにより、従来の乗算のように２ｎビットではなく、ｎビットまたはそれ以下を有する結果を生成することが理解されよう。
【０００６】
しかしながら、たとえ各因数に非常に多くのビットが含まれるように所望されても、桁数またはビット数が増えると、計算スピードは著しく低下する。しかしながらリアルタイム暗号化の目的上、暗号化及び解読のスピードが重要な問題となる。特に、リアルタイム暗号化処理が所望される結果である。
【０００７】
モジュラ乗算を実行する異なる方法が提案されている。特に、"The Mathematics of Computation"、Vol. 44、No. 170、April 1995、pp. 519-521に記載されるPeter L. Montgomeryによる論文は、"Modular Multiplication without Trial Division"のためのアルゴリズムについて述べている。しかしながらこの論文はＮの大きな値に対して、ハードウェアで実現するのが非現実的な演算について述べている。更にMontgomeryにより述べられる方法は、単一のフェーズでのみ動作する。それにひきかえここで述べるシステム及び方法は、動作サイクルを２つのフェーズに区分化する。ハードウェアの観点から、区分化はハードウェア共有化のための機構を提供し、これは多大な利点をもたらす。
【０００８】
【発明が解決しようとする課題】
従って、本発明の目的は、２つの大きな整数のモジュロＮを乗算する乗算器を生成することである。
【０００９】
本発明の別の目的は、暗号化回路及びシステムの性能及び能力を改善することである。
【００１０】
本発明の更に別の目的は、高速で動作する乗算器回路を構築することである。
【００１１】
本発明の更に別の目的は、除算演算を実行する必要無しに、モジュロＮ乗算を実行する乗算器回路を構築することである。
【００１２】
本発明の更に別の目的は、Ｎ及びｎの様々な値に対してスケーラブルな乗算器を提供することである。
【００１３】
本発明の別の目的は、２つのフェーズに渡って、ハードウェア回路の共有を可能にするマルチフェーズ・プロセスにおいて、２つの整数のモジュロＮの積を計算する方法を提供することである。
【００１４】
本発明の更に別の目的は、因数が各々がｋビットを有する複数ｍのサブブロックに区分化されるシステム及び方法を提供することであり、ここでｍ及びｋの値はハードウェア構造の追加の柔軟性を提供するために、選択可能である。
【００１５】
本発明の更に別の目的は、暗号化プロセスにおいて、乗算計算のスピードを向上させることである。
【００１６】
本発明の更に別の目的は、カスタム設計に関連するコストを回避するために、ビルディング・ブロックとしてマクロ・コンポーネントを使用する乗算器回路を提供することである。
【００１７】
本発明の更に別の目的は、柔軟性がありスケーラブルな設計を提供することである。
【００１８】
本発明の更に別の目的は、ビット指向ではなく、ワード指向の乗算システム及び回路を提供することである。
【００１９】
本発明の更に別の目的は、複数のほぼ同じプロセッサ要素を含む、モジュロＮ乗算のための回路を構築することである。
【００２０】
本発明の更に別の目的は、擬似独立計算のために、ｎビット数の乗算を複数の断片に区分化することである。
【００２１】
本発明の更に別の目的は、回路をパイプラン・モードで動作させることである。
【００２２】
本発明の更に別の目的は、別個のオペランド（因数）のシーケンスをパイプライン・モードで処理するように回路を動作させることである。
【００２３】
本発明の更に別の目的は、クリティカル・パスから加算機能を除去することにより、チェーン化処理要素のシーケンスの性能を改善することである。
【００２４】
本発明の更に別の目的は、例えばモジュロＮ指数関数の計算において、同一のまたは繰り返しオペランドのシーケンスをパイプラン・モードで処理するように回路を動作させることである。
【００２５】
本発明の更に別の目的は、暗号化プロセスにおいて、指数演算のスピードを向上させることである。
【００２６】
本発明の更に別の目的は、チェーンを、各々が因数Ｎにもとづく独立した並列処理を実行可能な複数のサブチェーンに区分化するために、その特性がチェーン内の始めのまたは中央の、或いは終わりのユニットとして制御可能な処理要素を提供することである。
【００２７】
本発明の更に別の目的は、ここで使用されるモジュラ乗算の方法への入力として有用である、逆演算を計算する機構を提供することである。
【００２８】
本発明の更に別の目的は、システムが適切に操作され、エラーを発生しなかったことを示すのに有用なチェックサムを生成する装置及び方法を提供することである。
【００２９】
本発明の更に別の目的は、モジュラ演算と調和するチェックサム回路及び方法を提供することである。
【００３０】
本発明の更に別の目的は、モジュロＮ羃法、大きな素数、または２つの大きな素数の積の使用により、データ暗号化が可能なエンジンを提供することである。
【００３１】
本発明の更に別の目的は、モジュロＮ羃法の使用により、データ解読が可能なエンジンを提供することである。
【００３２】
本発明の更に別の目的は、Ｎの因数が知られている場合に、中国剰余定理を用いて、モジュロＮ指数演算を容易にすることである。
【００３３】
本発明の更に別の目的は、公開キー暗号化システムのモードで動作可能な暗号化／解読エンジンを提供することである。
【００３４】
本発明の更に別の目的は、コード化デジタル署名を有する文書の生成及び受信可能なエンジンを提供することである。
【００３５】
本発明の更に別の目的は、データ暗号化及び解読のために、二人のユーザの間で交換されるキーの生成可能なエンジンを提供することである。
【００３６】
本発明の更に別の目的は、高速で高性能な暗号化エンジンを提供することである。
【００３７】
最後に本発明の更に別の目的は、大きな処理システムの一部として含まれる、暗号化及び解読のための暗号化エンジンを提供することであり、本エンジンはそれが接続される大規模データ処理システムの他の部分からの、データ及びコマンド情報の転送のための通信機能を有する。
【００３８】
本発明の様々な実施例により実現される前記の所望の目的は、これらの目的が本発明の最も汎用的な実施例において、またはより特定的な実施例において、個々にまたは集合的に、本質的なフィーチャとして存在することを意味するものではない。
【００３９】
【課題を解決するための手段】
本発明の好適な実施例によれば、初期値ゼロが結果レジスタＺ0に記憶される。本プロセスを用いて乗算される整数Ａ及びＢが、各々がｋビットを有するｍブロックに区分化される。乗算はモジュロＮで行われる。更に、値Ｒが２kにセットされる。このようにして、整数ＡがＡ＝Ａm-1Ｒm-1＋・・・＋Ａ2Ｒ2＋Ａ1Ｒ＋Ａ0として表される。これは整数Ａがｍブロックに区分化されることを示す。
【００４０】
本発明の１実施例では、関数Ｚ＝ｆ（Ａ，Ｂ）＝ＡＢ２-mk mod Ｎ（以下"mod"は"モジュロ"を意味する）を計算する方法及び回路が示される。その後で、この関数がＡＢ mod Ｎ（すなわちＡＢモジュロＮ）そのものを計算するために使用される様子について示す。
【００４１】
本発明のシステム、方法及び回路は、使用される基本的アルゴリズムの状況において最善に理解される。更に、このアルゴリズムを理解する目的上、モジュラ計算がモジュロＮで実行される。ここでＮは奇数であり、ｎはＮの２進表現でのビット数である。更に、Ｎ0はＮの最下位ｋビットを表す。また、定数ｓが使用され、これは（−１／Ｎ0）mod Ｒ＝１／（Ｒ−Ｎ0）mod Ｒである。この変形により、アルゴリズムは擬似コードを用いて、次のように表される。すなわち、
Z0＝0
for i=0 to m-1
Xi=Zi+AiB
yi=sxi,0 mod R（xi,0はXiの最下位ｋビット）
Zi+1=(Xi+yiN)/R
end
【００４２】
モジュロＮ乗算を実行するこの方法に関連して、特筆すべき２つの項目が存在する。第１の項目は、因数の１つを、各々がｋビットを有するサブブロックに区分化することにもとづき、乗算が行われることである。これは構築されなければならない乗算器アレイを著しく単純化する。更にこれは、乗算演算が著しく短い時間で実行されることを可能にする多大な並列性をもたらす。第２の項目は、区分化により、プロセスが複数のｍサイクルに分割されるだけでなく、方法が各サイクルにおいて発生する２つのフェーズに分割される。第１のフェーズ（Ｘフェーズ）では、値Ｘi及びｙiが計算される。第２フェーズ（Ｚフェーズ）では、中間結果値Ｚi+1が計算される。ここでＸiの計算及びＺi+1の計算において、加算演算及び乗算演算が存在する。この事実は、これらのステップの各々において、乗算及び加算を実行する同一のハードウェアが重複されるのではなく、共用されることを可能にする。Ｚi+1の生成におけるＲによる除算に関連して、これは単に下位ｋビットを廃棄することにより達成される。この構造の他の利点は、後に明らかとなろう。
【００４３】
前述のハードウェア及び方法の出力は、積ＡＢ２-mk mod Ｎを生成する。より望ましい結果ＡＢ mod Ｎを生成するために、前記の方法及び回路は２度目も使用される。特に、この回路からのオリジナル出力は入力レジスタの１つに供給され、他のレジスタは因数２2mk mod Ｎを含む。この因数は、第１の計算の間に加算された第１の因数２-mkを除去し、また回路が２度目に実行されるとき含まれる加算因数２-mkを取り消す。その結果、ＡＢ mod Ｎが生成される。
【００４４】
ソフトウェアにより本発明のプロセスを実行しようとする当業者にとって、前述の乗算のためのアルゴリズムは、標準のプロシージャ・ベースのプログラミング言語により容易に実現可能であり、結果のコードはソース形式またはオブジェクト形式により、磁気または光ディスクなどの重宝な記憶媒体上に容易に記憶可能である。このプロセスは後述の羃法プロセスと共に巧妙に利用可能であり、それらには中国剰余定理にもとづく羃法プロセスが含まれる。
【００４５】
前述のプロセスでは、プロセス入力の１つが変数"ｓ"である。この値は負の逆数のモジュロＲとして計算される。この入力信号の生成を容易にするために、その生成のための特殊な回路がここで述べられる。この回路はまた、処理要素の他の部分で使用される既存のハードウェアも利用する。特に、これはチェーン内の最右端プロセッサ要素の一部を形成する。
【００４６】
Ｘi及びＺiの前述の計算において、ｎビットよりも多い数が存在する。従って、乗算演算及び加算演算は比較的大きな回路で実行され、これらはここではそれぞれ乗算器アレイ及び加算器アレイと呼ばれる。本発明を実施する好適な方法によれば、加算器アレイ及び乗算器アレイはサブブロックに分割される。ハードウェアのこの区分化は、任意の好都合な数のブロックを用いて行われるが、１度にｋビットを処理できるブロックへの区分化が便利である。従って、好適な実施例では、ｎ＋１ビット及びｋビットを有する２つの数を処理するために、１つの大きな乗算器アレイを使用する代わりに、複数の別々のｋビット×ｋビットの乗算器が使用される。ここでｎはｋよりも遙かい大きい。更に、プロセッサ要素サブブロックへの区分化は、特に回路レイアウトの効率化のために有用であるが、究極的に、回路を幾つかのパイプライン・モードで動作させることを可能にする。
【００４７】
第１のパイプライン・モードでは、回路が複数サイクルｍを通じて動作され、そこでは隣接するプロセッサ要素が代替フェーズで動作される。すなわち、第１のパイプライン・モードでは、あるプロセッサ要素がＸフェーズの場合、その隣接プロセッサ要素はＺフェーズで動作しており、その逆のことも言える。第２のパイプライン・モードでは、パイプライン操作が継続されるが、入力レジスタ（Ａ及びＢ）内に新たなエントリを有し、これらも好適には、乗算器アレイ及び加算器アレイ同様、区分化される。
【００４８】
ｎは一般にｋよりも遙かに大きく（例えばｋ＝３２に対してｎ＝１０２４）、加算器ステージを通じるキャリー伝搬が処理遅延に大きく影響するので、区分化及びパイプライン化は一緒に、この回路遅延の原因及び有効パラメータｎへの回路動作時間の対応する依存性を取り除く。ここでｎのサイズは、暗号化の状況において、不当なコード解読の難度を決定する。
【００４９】
本発明のパイプライン方式回路はまた、特にモジュロＮ羃法を実行するとき有用であり、この演算は、暗号化アプリケーションにおいて非常に有用である。こうした演算は、繰り返し乗算演算を含む。従って、たとえパイプラン化が初期遅延を導入するとしても、指数演算の性能の多大な改善が達成される。
【００５０】
本開示において見いだされる１実施例では、前述のように、個々に動作する処理要素を一緒にチェーン化することにより、クリティカルなタイミング・パス、すなわち、その実行の遅延がプロセス全体を遅延させるパス内に、加算演算を導入する。本発明は、この加算演算を処理要素の動作の早期部分に配置することにより、個々の処理要素の設計の改善を提供する。しかしながら、そうすることにより、この早期ステージにおいて、一部の処理要素内において、一部の信号がまだ使用可能でないという事実を補うために、新たな制御信号が提供され、都合がつけば、それらが隣接処理要素内で発生している、または既に発生した動作から提供される。
【００５１】
ここで使用される処理要素はまた、異なる能力で機能するように特別に設計される。特に最右端の処理要素は、チェーン内の下位の処理要素としてのその位置に固有の演算を実行する。同様に、最左端要素は固有の役割を有し、より単純な形態を取ることができる。しかしながら、ここで使用される処理要素は、チェーン内の異なる役割に適応化できるように、特殊に設計及び構築される。特に中央の処理要素は、最右端の処理要素の機能的特性及び動作的特性を呈するように制御可能である。このように、チェーン全体が区分化され、（好適なモダリティでは、）大きな奇数の整数Ｎの因数に対して作用する２つの（または必要に応じて２つ以上の）別々で独立したチェーンを形成する。
【００５２】
本発明の中間目標は、モジュラ乗算エンジンの構築であるが、より最終的な目標は、モジュラ羃法のための装置を提供することである。本発明では、これが指数の２進表現にもとづき、開示されるモジュラ乗算器を繰り返し使用することにより実現される。このプロセスの更なる改善は、Ｎの因数が知られている指数演算の一部として、中国剰余定理の使用を含む。２つの部分に区分化される本発明の処理要素チェーンの能力は、特にこの場合に有用である。なぜなら、制御可能に区分化されるチェーンの各部分は、Ｎの因数の各々に独立且つ並列に作用できるからである。
【００５３】
計算回路はできるだけ高速に動作することが望まれ、これは時に誤動作につながるので、実行される演算が標準の演算にもとづかずに、モジュラ演算（加算、減算、反転、乗算及び累乗）にもとづく場合、エラーを如何に検出するかに関する取り組みが成される。しかしながら、本発明は、モジュラ算術演算の複雑な要求に調和するだけでなく、非常に少量のハードウェアの追加により、実行またはスループットの時間的な障害無しに、オンザフライ式に生成される回路及び方法を使用することによりこの問題を解決する。
【００５４】
【発明の実施の形態】
本発明の構造及び動作は、乗算因数の１つを複数のｋビット幅の断片に区分化することに依存する。従って、２進数ＡをΣiａi２i（但し０≦ｉ≦ｎ−１）として表す代わりに、本発明では乗算因数の１つが、Ａm-1Ｒm-1＋・・・＋Ａ2Ｒ2＋Ａ1Ｒ＋Ａ0＝ΣjＡjＲi（但し０≦ｊ≦ｍ−１）と表される。ここでＲ＝２kである。この表現では、数Ａがブロック形式で表され、ｍブロックの各々がｋビットを含む。すなわち、各Ａiはｋビットを有する整数を表す。
【００５５】
本システムでは、モジュロ奇数Ｎ乗算（すなわち奇数Ｎを法とする乗算）が重要な対象である。また本発明を理解するために、記号ｎがＮの２進表現でのビット数を示すために使用される。また同様に、数ＡはレジスタＡ（図１の参照番号１０）に記憶されて、ｍブロックに区分化される数と想定される。一般にブロック数ｍは、ｍｋ≧ｎ＋２の最も小さな整数に選択される。更に、Ｎ0は数Ｎの最下位ｋビットを表す。同様に定数ｓは、Ｎ0の負の逆数のモジュロＲ（すなわち（−１／Ｎ0）mod Ｒ）に等しい。
【００５６】
数学的見地から本出願人は、入力変数として乗算される２つの数、すなわちＡ及びＢ、モジュロ数Ｎ、Ｎに関連付けられる定数ｓ及びパラメータｍ、ｋ及びＲ＝２k有するアルゴリズムを使用した。本発明により提供される関数の出力Ｚは、Ｚ＝ｆ（Ａ，Ｂ）＝ＡＢ２-mk mod Ｎにより与えられる。本出願人の方法により指定されるプロシージャは、値Ｚ0を０に初期化し、０からｍ−１の範囲の整数ｉについて、Ｘi、ｙi及びＺi+1を生成する計算が実行される。Ｘi及びｙiの値が、ｍサイクルの各々の第１の演算フェーズの間に計算される。値Ｚiは各サイクルの第２の演算フェーズの間に計算される。Ｘiを計算するために使用される加算器及び乗算器は"時分割"され、Ｚiを生成するために必要とされる計算も実行する。特に、各ステージｉにおいて、ＸiはＺi＋ＡiＢにより与えられる。このステージでは、ｙiの値が、定数ｓにＸiの最下位ｋビットmod Ｒを乗じて求められる。Ｘiの最下位ｋビットをｘi,0と表す場合、ｙi＝ｓｘi,0となる。これで現プロセスの１サイクルの間の第１のフェーズ（すなわちＸフェーズ）の間に実行される演算が完了する。第２のフェーズ（すなわちＺフェーズ）では、Ｚレジスタ（図１の５０）の更新値が、（Ｘi＋ｙiＮ）／Ｒとして計算される。処理の最後のステージにおいて、Ｚの所望の値がＺレジスタ内に存在する。特にこのステージでは、Ｚm＝ＡＢ２-mk mod Ｎである。各ステージ（サイクル）において、Ｘi、ｙi及びＺiが続くステップでの計算のために記憶される。
【００５７】
入力変数Ａ及びＢの両方がｎ＋１ビットを有する場合、本発明により提供される関数の出力Ｚ＝ｆ（Ａ，Ｂ）＝ＡＢ２-mk mod Ｎ（ここでＮはｎビットの奇数）は、ｎ＋１有効ビットを有するに過ぎない。すなわち、出力は２n+1よりも小さい。ここで述べるハードウェア回路は入力として、それぞれがｎ＋１ビットのＡ及びＢを取り、ｎ＋１ビットの出力Ｚを生成する。
【００５８】
このプロセスを実行するハードウェア回路が図１に示される。特に、ｎ＋１ビット因数ＡがＡレジスタ１０に記憶される。ここで因数Ａは区分化形式で処理される因数である。マルチプレクサ１１はレジスタ１０からマルチプレクサ３１にｋビットの順次ブロックを供給する。ここで例えばｋ＝３２ビットである。マルチプレクサ３１、２１及び５２は、互いに協力して動作し、回路がＸフェーズで動作しているか、またはＺフェーズで動作しているかに応じて、２つの可能な入力の一方を選択する。従って、その動作の第１のフェーズの間には、マルチプレクサ１１はＡ0内のｋビットを提供する。第２のサイクルの第１フェーズで、Ａ内の次のｋビットＡ1がマルチプレクサ１１を介して供給される。Ａからのｋビットのサブブロックが、各サイクルの初期のすなわちＸフェーズの間に提供される。第３のサイクルでは、マルチプレクサ１１がＡ内の次のｋビット、すなわちＡ2を提供する。従って、マルチプレクサ１１はサイクル数（すなわちサイクル０乃至ｍ−１）の関数として、選択的に動作するものと見なされる。
【００５９】
各サイクルのＸフェーズの間に、値ＡiがＡレジスタ１０からマルチプレクサ１１を介して選択され、同様に、マルチプレクサ２１がＢレジスタ２０の内容を選択する。従って本発明によれば、乗算される数がレジスタ１０及び２０に記憶される。どちらの数がどちらのレジスタに記憶されるかは問題でない。また回路が各サイクルにおいて、初期Ｘフェーズまたは最終Ｚフェーズで動作しているかに拘わらず、マルチプレクサ３１及び２１は各フェーズにおいて、それぞれｋビット及びｎ＋１ビットを乗算器アレイ７０に供給する。従ってＸフェーズの間、マルチプレクサ３１及び２１はＢレジスタからの内容及びＡレジスタの一部を選択する。また、典型的な状況では、ｎの値は約５１２またはそれ以上であり、ｋの値は約３２である。従って、乗算器アレイ７０は１ビット×ｎビット乗算と、ｎビット×ｎビットのフル乗算との間のバランスを取ることが理解される。更に、ｎの値の増加は実際にはほとんどの場合、少なくとも２の累乗で増加する。
【００６０】
それぞれがｎ＋１ビット幅とｋビット幅の入力を有する任意の２進乗算器と同様、乗算器アレイ７０はｎ＋１＋ｋビット幅の出力を生成する。乗算器アレイ７０からの下位ｋビットは、２つのｋビット加数を１度に加算するように設計される加算器６５に供給される。この点に関して、加算器６５はｙiを計算する回路内に存在する。従ってｙiの値が、まだ完全に計算されていない合計にあたる値Ｘiの最後のｋビットに依存すると仮定すると、本来Ｘiの下位ｋビットの加算であるこの加算を実行することが必要である。第１の加数は、マルチプレクサ５２により選択されるＺレジスタ内の最右端のｋビットに由来する。これらのビットは、積ＡiＢの最右端部分内のｋビットと加算される。加算器６５の出力はｘi,0であり、これはＸi＝Ｚi＋ＡiＢの最下位ｋビットである。この出力がレジスタ５５に記憶され、同時に２つのｋビット数を乗算する乗算器８０にも供給される。しかしながら、これはモジュロＮ乗算（すなわちＮを法とする乗算）ではない。乗算器８０に供給される他の因数は、ｓレジスタ６０からの数ｓである。この結果が要求されるモジュロＲであるので、乗算器８０からの最右端ｋビットだけが、このＸフェーズにおいて、ｙレジスタ３０に戻される。このレジスタに記憶される値は、後述のように、Ｚフェーズで実行される計算の間に使用される。
【００６１】
Ｘフェーズ計算の残りは、合計Ｚi＋ＡiＢの上位ｎ＋１ビットの計算にあてがわれる。乗算器７０はＢレジスタ２０からのビットと、Ａレジスタからの選択されたｋビット・ブロックＡiに由来する、各々がｋビットのｍブロックのシーケンスとを乗算する回路として構成される。２つのｋビット数の乗算は、一般に２ｋビットを有する数を生成し、特にこれは本出願人の乗算器８０の状況にあてはまる。しかしながら、ｙiの計算はモジュロＲとして計算される。計算のモジュロ要求は、乗算器８０の出力から最右端ｋビットだけを、ｙレジスタ３０の入力に戻すことにより容易に達成される。
【００６２】
前述のように数の乗算は一般に、２つの入力された数のビット長のいずれよりも長いビット長を有する出力を生成する。特に乗算器７０については、出力がｎ＋１＋ｋビットの長さを有すると見なされる。下位（すなわち最右端）ｋビット出力が乗算器７０から加算器６５に供給される。しかしながら、乗算器アレイ７０内で実行される各ｋビット・ブロック乗算は、２ｋビットを生成し、これはｋビットの"結果"と、次の桁へのｋビットの"キャリー"として形成される。所望の中間出力Ａiを生成する合計が、加算器７５で実行され、ここでは２つの部分、すなわちｎ＋１ビット長の第１の部分と、ｎ＋１−ｋビット長の第２の部分とが加算される。ｎ＋１−ｋビットは、乗算の"キャリー"部分を表す。従って加算器アレイ７５の出力は、ＡiＢの上位ｎ＋１ビットの結果である。この結果が直接加算器アレイ８５に供給され、ここでＺレジスタ５０からのＺiのシフト値と加算される。また適宜、Ｘi＝Ｚi＋ＡiＢのこの上位ｎ＋１ビットが、Ｚフェーズ計算に備えて、Ｚレジスタ５０に記憶される。Ｘiの下位ｋビットは、前述のようにレジスタ５５に記憶される。
【００６３】
動作サイクルのＺフェーズでは、乗算器アレイ７０及び加算器７５及び８５が、再度使用される。但し、乗算器アレイ７０への入力は、マルチプレクサ３１により選択されるｙレジスタ３０の内容である。乗算器アレイ７０に供給される他の因数は、Ｎレジスタ４０の内容であり、これは動作サイクルのＺフェーズの間に、マルチプレクサ２１により選択される。以前同様、乗算器アレイ７０はｎ＋１ビット数と、ｋビット数との積を計算する。加算器アレイ７５は、乗算に関連付けられる自然加算演算を実行し、そこではあるｋビット・サブフィールドから次のｋビット・サブフィールドへの、有効キャリー式演算が存在する。従って、Ｚフェーズ動作の間の加算器アレイ７５の出力は、積ｙiＮの上位ｎ＋１ビットである。本方法において、ｙiＮと値Ｘiとの加算と共に、Ｒによるその除算が、加算器６５の出力から下位ｋビットを廃棄し、加算器８５からの上位ｎ＋１ビットだけをレジスタ５０に記憶することにより達成される。
【００６４】
Ｘフェーズ及びＺフェーズの動作における違いは、図２と図３との違いの検査からより明らかにされる。特に図２は、各動作サイクルの第１のすなわちＸフェーズの間に存在するアクティブ・データフロー・パスを示す。同様に図３は、各動作サイクルの第２のすなわちＺフェーズの間にアクティブであるデータフロー・パスを示す。Ｘフェーズ及びＺフェーズで実行される計算は、合計ｍ回繰り返され、最終結果Ｚmが、各々がＸフェーズ及びＺフェーズを含むｍ動作サイクルの終わりにおける所望の結果の１つである。この動作ステージにおいて、Ｚレジスタ５０内に存在する値はＡＢ２-mk mod Ｎである。
【００６５】
図１乃至図３に示される回路は、乗算結果ＡＢ mod Ｎを生成することができる。これは最初にＡＢ２-mk mod Ｎを計算するために示される回路を用い、次にこの回路を、第１の動作ステージからの出力を提供されるＡレジスタまたはＢレジスタのいずれかと共に使用して、この値に２2mk mod Ｎを乗じることにより達成される。回路の各動作は（ｍサイクルを通じて）因数２-mkを導入するので、２2mkによる乗算は、回路の第１の動作ステージの間に導入された第１の因数２-mkを取り消し、また第２の乗算ステージの間に導入される他の因数２-mkも取り消す。こうして、図１乃至図３の回路を通じて、各々がｍサイクルを有する２つのパス（２ステージ）を使用することにより、結果ＡＢ mod Ｎが計算される。
理解及び説明を明確且つ容易にするために、本発明のプロセスの動作ステージは、Ａレジスタ及びＢレジスタへの因数のロードに続く、ｍサイクルの回路動作を指し示す。
【００６６】
前記の回路の動作は恐らく次の例により、より容易に理解されよう。そこではｋ＝３、Ｒ＝２3、Ｎ＝１０７＝Ｒ2＋５Ｒ＋３＝（１，５，３）＝（Ｎ2，Ｎ1，Ｎ0）、Ｎ0＝３、ｍ＝３、ｓ＝（−１／Ｎ0）mod Ｒ＝５、Ａ＝８３＝Ｒ2＋２Ｒ＋３＝（１，２，３）、Ｂ＝７０＝Ｒ2＋０Ｒ＋６＝（１，０，６）である。ここでは例として、またプロセスの理解を容易にするため、１０進数字が使用される。より詳細には、１０進数はそれぞれが３ビットを含むブロックとして表される。前記の開示された回路により実行されるプロセスは、３つのステップにおいて次のように発生する（ｉ＝０、１、２）。
【００６７】
ステップ１：
Ｘ0＝Ｚ0＋Ａ0Ｂ＝（３，２，２）、ｙ0＝２ｓ mod Ｒ＝２
ｙ0Ｎ＝（２，１０，６）＝（３，２，６）
Ｘ0＋ｙ0Ｎ＝（６，５，０）
Ｚ1＝（Ｘ0＋ｙ0Ｎ）／Ｒ＝（０，６，５）
ステップ２：
Ａ1Ｂ＝（２，０，１２）＝（２，１，４）
Ｘ1＝Ｚ1＋Ａ1Ｂ＝（３，０，１）、ｙ1＝ｓ＝５
ｙ1Ｎ＝（５，２５，１５）＝（１，０，２，７）
Ｘ1＋ｙ1Ｎ＝（１，３，３，０）
Ｚ2＝（１，３，３）
ステップ３：
Ａ2Ｂ＝（１，０，６）
Ｘ2＝Ｚ2＋Ａ2Ｂ＝（２，４，１）、ｙ1＝ｓ＝５
ｙ2Ｎ＝（５，２５，１５）＝（１，０，２，７）
Ｘ2＋ｙ2Ｎ＝（１，２，７，０）
Ｚ3＝（１，２，７）＝８７
８７ｘＲ3＝ＡｘＢ mod Ｎ＝３２．
【００６８】
ＡＢ mod Ｎを計算することが目的であるが（ここでＡＢ及びＮは全てｎビット長）、便宜上ここではプロセスがＡレジスタ、Ｂレジスタ及びＺレジスタを使用する。これらはｎ＋１ビット長またはｍｋビット長である。これは最終結果及び中間結果が実際にＮよりも大きいか否かをチェックする必要性を回避する。例えば、この態様は前記の例のステップ２で現れる。
【００６９】
本発明者はまた、少なくとも部分的に、ｎ及びｋのサイズの一般に大きな違いにより、ｎ×ｋ乗算器の構築において、処理の不均衡が発生することを認識していた。従って、図１乃至図３に示される回路で実行される計算を区分化することが可能である。特に、図１に示される回路は実際に、複数（ｄ＋１）のプロセッサ要素（ＰＥ）がチェーン状にまたはカスケード状に接続される形態で構成可能である。処理要素の各々は、同一に構成される。しかしながら、データの最右端部分の処理要素（ここではＰＥ0と称す）は、図４に示されるように、幾分複雑な構造を有する。より単純な回路が、処理要素１乃至ｄとして使用される。しかしながら好適な実施例では、最右端すなわち最後のプロセッサ要素ＰＥdは、図８に示されるように、実際にはより単純に構成される。従って、図４はデータの最右端部分の処理要素回路の構造を示す。図６は、繰り返し使用可能な処理要素の回路を示し、ここでは必要なだけ多くの個々の処理要素が使用され、従って本発明のスケーラビリティの面を示している。最後に、図８は最後のすなわち最左端処理要素の好適な単純な実施例を示す。
【００７０】
本発明の理解のために、図４、図６及び図８に示されるレジスタＲ0乃至Ｒdは、それ自体処理要素の一部とは見なされず、別々の区分化されたレジスタ構造の一部と理解される。モジュロＮ乗算演算の所望の結果を含むのは、これらのレジスタである。これらのレジスタは、図１のＺレジスタと同一の機能を提供する。
【００７１】
図４を参照すると、マルチプレクサ１９３はＸフェーズの間、２ｋビットの被加算数を加算器１８５に供給するように動作する。第１のすなわちＸフェーズの動作の間、マルチプレクサ１９３は、レジスタＲ2（１９２）からの最左端ビットと、レジスタＲ1（１９１）からの最右端ビットを含む、２ｋビットの数を供給する。第２のすなわちＺフェーズの実行の間、マルチプレクサ１９３は異なる２ｋビットのデータを加算器１８５に供給する。特にＺフェーズの間、マルチプレクサ１９３はその最左端ｋビットとして、レジスタＲ1の内容を供給し、その最右端ｋビットとして、レジスタＲ0（１９０）の内容を供給する。
【００７２】
図１の完全な幅を有するレジスタ１０、２０、４０及び５０とは対照的に、区分化システムにおける対応するレジスタは、少ないビットを有する。特に、汎用処理要素ＰＥ内の対応するＢ変数レジスタ及びＮ変数レジスタは、好適には２ｋビットに等しい幅を使用する。しかしながら最右端処理要素では、より多くのビットが所望される。特に、ｎが５１２に等しい場合、図４のレジスタ１２０及び１４０は、好適には９６ビットの幅を有する。マルチプレクサ１２１はＸフェーズの計算の間、レジスタＢ（１２０）の内容を選択し、同様にＺフェーズの計算の間、レジスタＮ（１４０）の内容を選択する。一般に、全長ｎビット幅の計算は、任意の便利なサイズの区分に分割される。但し、全てのプロセッサ要素が同一のサイズであったり、同一のデータ幅を処理する必要はない。しかしながら回路設計及び回路レイアウトの便宜上、個々の処理要素の各々（最右端要素ＰＥ0を除く）が、データ幅の点で同一のデータ処理能力を有することが好ましい。従って、一般にここでの検討及び議論のために、合計ｄ＋１個の処理要素ＰＥ0乃至ＰＥdが存在するものとする。処理要素ＰＥ0は好適には、図４に示されるような構造を有し、ＰＥdは図８に示される好適な構造を有する。但し図６に示されるような、より汎用的な構造が最左端プロセッサＰＥdとして採用されてもよいし、またこの最左端処理要素が、図８に示されるものよりも複雑である必要はない。
【００７３】
また回路設計、レイアウト及び組立効率の都合上、一般に各処理要素のデータ幅Ｗがｋの整数倍であることが望ましい。ｎ＝５１２の値に対して提供される設計では、処理要素ＰＥ1乃至ＰＥd-1の各々は、２ｋビット幅のチャンク（chunk）でデータを処理する。従ってこの例では、Ｗ＝２ｋであり、ここでＷは、図６及び図７に示されるように、典型的なまたは汎用的な形態の処理要素におけるデータ幅である。図４に示されるプロセッサ要素ＰＥ0は、余分なｋビット処理能力を有する。これについては以下で詳述する。典型的な処理要素ＰＥiの各々がＷビット幅チャンクでデータを処理し、ｄ＋１個の処理要素が存在して、最右端処理要素が余分なｋビットを処理する場合、ｎ＝Ｗｄ＋ｋが好適なケースである。一般に、マルチプレクサ１２１の出力は好適にはＷ＋ｋビットを含む。これらのビットの左側の３分の１が乗算器１７３に供給され、レジスタＢＮ（１９８）の中央の３分の１のビットが乗算器１７２に供給され、右側の３分の１のビットが乗算器１７１に供給される。乗算器１７１、１７２及び１７３は、各々ｋビット×ｋビットの乗算器である。この点に関して、図１のかなり大きなオリジナル乗算器アレイ７０は、ｎ×ｋ乗算器を使用する。しかしながら、計算を複数のほぼ同一の処理要素を使用するシステムに区分化することにより、遙かに迅速に動作する乗算器を使用する回路構成が実現できる。なぜなら各乗算器は一般に、僅かにｋビット×ｋビットであるからである。明らかにｋはｎよりも遙かに小さいので、処理は多大に高速化される。
【００７４】
乗算器１７３から出力される２ｋビットの最左端部分は、部分積出力（ＰＰＯ：partial product out）として、チェーン内の次のユニットに供給される。特に、ここでの議論では、処理の自然順序はチェーン内の最右端の処理要素から、最左端の要素へと向かうものとする（図９参照）。従って、データはある処理要素から、そのすぐ左側の処理要素へ渡される。しかしながら左及び右は、本来本発明の説明及び理解のために有用な相対的な用語に過ぎない。乗算器１７３からの最右端ｋビットは、加算器１７５に供給される２ｋビット被加算数の最左端ｋビットとして供給される。２ｋビット被加算数の最右端ｋビットは、乗算器１７２の下位すなわち最右端ｋビットから供給される。このように図４に示されるように、乗算器１７３及び１７２の最右端ｋビットがそれぞれ結合されて、２ｋビット幅の被加算数を加算器１７５に供給する。加算器１７５は他の入力として、２ｋビット被加算数を有し、これは乗算器１７２及び１７１の最左端ｋビットからそれぞれ供給され、乗算器１７２が２ｋビット被加算数の最左端ｋビットを、また乗算器１７１が２ｋビット被加算数の最右端ｋビットを加算器１７５に供給する。従って、加算器１７５は２ｋビット幅の加算器である。等価ではあるが、別の代替接続構成が図５に示される。
【００７５】
マルチプレクサ１５２はＸフェーズの計算の間に、レジスタＲ０（１９０）からｋビットを選択するように動作する。Ｚフェーズの間、マルチプレクサ１５２はその入力として、変数ｘ0を含む一時レジスタ１５０の内容を選択する。マルチプレクサ１５２の出力は、ｋビット幅の加算器１６５に供給される。加算器１６５は２つの被加算数、すなわち、乗算器１７１からの最右端ｋビットと、マルチプレクサ１５２からのｋビットとを受信する。加算器１６５の出力は一時レジスタ１５０に記憶され、同時にｋビット×ｋビットの乗算器である乗算器１８０にも供給される。乗算器１８０に供給される他の因数は、変数ｓを含むレジスタ１６０の内容である（（−１／Ｎ0）mod Ｒとしてのｓの計算が、以下で詳述される図２０に示される回路で効率的に実行される）。乗算器１８０の出力が、前述のアルゴリズムにより定義される値ｙを含むレジスタ１３０に供給される。
【００７６】
レジスタ１３０の出力はマルチプレクサ１３１に供給され、同時に次の処理要素ＰＥ１（図６参照）にも供給される。マルチプレクサ１３１は、変数Ａの一部を選択するように動作し、これが乗算演算における因数の１つとなる（変数Ａの他のｋビット幅部分は、それぞれの処理要素により選択される）。特に、レジスタ１１０は変数Ａの最右端ｋビットを含む。従ってＸフェーズ動作の間、マルチプレクサ１３１は、図示のように乗算器１７３、１７２及び１７１に供給されるレジスタ１１０の内容を選択するように動作する。同様に、Ｚフェーズ計算の間マルチプレクサ１３１は、この乗算器の同一セットに供給される他の因数として、レジスタ１３０から変数ｙを選択するように動作する。
【００７７】
加算器１６５からのキャリー出力信号線は、図示のように、加算器１８５の最下位桁へのキャリー入力として供給される。更に、加算器１７５が第１のキャリー出力信号線を、チェーン内の次の処理要素に供給し、同様に、加算器１８５が第２のキャリー出力信号線を、チェーン内の次の処理要素に供給する。特に、図４は処理要素ＰＥ0を表すので、キャリー出力信号線１及びキャリー出力信号線２の両方は処理要素ＰＥ1に提供される。ＰＥ0とＰＥ1の間の接続は、図４を図６の右側に置くことにより容易に明らかとなろう。特に、処理要素ＰＥ0は変数ｙ、部分積出力及び２つのキャリー出力信号線を、図６のＰＥ1に示される入力に供給する。また、特に変数ｙ（すなわちレジスタ１３０の内容）は個々の処理要素の各々に供給される。最後に、図４に関連して加算器１８５の出力は、図４の最上部に示されるレジスタＲ0及びＲ1に供給される。前述のように、最終的に所望の計算結果を含むのは、レジスタ・セット（Ｒ1及びＲ0を含む）である。従って、図４において処理要素ＰＥ0を示す参照番号１００は、このレジスタ・セットを含まない。このレジスタ・セットは、本発明において使用される他の変形及び構造の幾つかに関連して、以下で別々に述べられる。
【００７８】
次に、図６に注目すると、これはより典型的なプロセッサ要素、特に、ｎビット幅の因数を処理するために要求される限り、回路／システム・チェーン内で繰り返されるプロセッサ要素の形態を示す。
【００７９】
図６を特に参照すると、これはｓ及びＮ0に関連するｋビット幅演算を扱う処理の一部が、最右端の処理要素すなわちＰＥ0を除くあらゆる処理要素内に存在する必要がない以外は、図４と類似である。特に図６は、参照番号２００で示される処理要素ＰＥpの汎用形態が、特にレジスタＢＮ（２９８）を含むが、図示の他のレジスタを含まないことを示す。図４と図６の大きな違いの１つは、レジスタ２２０が第２の因数Ｂの一部のビットだけを含むことである。特にレジスタ２２０は、Ｂ2p+2及びＢ2p+1として示される２ｋビット幅のチャンクを含む。ここでｐは１乃至ｄ−１の範囲を取る。再度前述のようにマルチプレクサ２２１は、レジスタ２２０からの２ｋビットか、またはレジスタ２４０からの２ｋビットの内、変数Ｎの対応する部分（２ｋビットのチャンク）を有する方を選択する。
従って、レジスタＢＮは２ｋビット幅である。図４のレジスタ１９８と異なり、図６のレジスタＢＮ（２９８）は、２ｋビット幅に過ぎない。本発明の好適な１実施例では、ｎ＝５１２のとき、レジスタＢＮは６４ビット幅である。
【００８０】
全体的な観点から、汎用処理要素ＰＥi（図６で参照番号２００で示される）は、右側からの入力として、ｙの値、部分積入力、キャリー入力１及びキャリー入力２を受諾する。プロセッサ要素ＰＥiは更に入力として、レジスタ２１０からの乗数Ａのｋビットの対応部分を有する。レジスタ２９２、２９１及び２９０の関与は、プロセッサ要素の汎用バージョンにおいて示される以外は、実質的に図４の場合と同様である。これらのレジスタは、フェーズ間の中間値を記憶し、最終的に完全な積すなわちＡＢ mod Ｎを記憶する。また全体的な観点から、プロセッサ要素２００は出力として、ｋビットの部分積出力を生成し、これがその左側のプロセッサ要素に、キャリー出力信号１及び２と一緒に供給される。そしてこれらのキャリー出力信号１及び２は、左側のプロセッサ要素内の対応する加算器２７５及び２８５にそれぞれ供給される。加算器２８５の出力はレジスタＲ2p+1及びＲ2pに戻されて供給される。従ってレジスタ・セットＲ、Ｂ、Ｎ及びＡへの接続以外は、処理要素は単に部分積入力及び部分積出力及びキャリー入力１、２及びキャリー出力１、２を突き合わせることにより、接続される。従って、複数の類似の処理ユニットを使用する本発明のこれらの態様に従い構成されるシステムでは、最右端の位置として図４または図５に示される回路から始まり、それに隣接して、図６または図７に示される処理要素を配置することにより、システム全体が構成される。従って、全体構成は図９に示されるようになる。
【００８１】
しかしながら、議論を進める前に、最左端プロセッサ要素ＰＥdが、図６または図７に示されるような、その右側の処理要素のように複雑である必要がない点を考慮することが有用であろう。特に、最左端の処理要素はｋビットだけを処理すればよい。Ｘフェーズの動作では、図８に示される回路は、増分キャリー回路３７５により、キャリー入力１を、最左端処理要素への部分積入力に加算するように作用する。同様に、加算器３８５はキャリー入力２を、加算器３８５への他の入力に加算して出力を生成し、これが直前のプロセッサ要素内のレジスタＲ2dに供給される。ＡＮＤゲート３９９により制御されるＺフェーズ動作では、レジスタＲ2i（３９０）の内容が、増分キャリー回路３７５の出力に加算され、この結果が図示のように、レジスタＲ2iにフィードバックされる。従って、本発明の区分化実施例では、最右端要素と最左端要素との間の汎用処理要素において一般に要求されるよりも、より単純な最左端処理要素を使用することが好ましい。しかしながら、この代用は好適ではあるが、強制的なものではない。
【００８２】
本発明の１実施例で提供されるように、計算問題を複数のほぼ同一の処理要素を有する解決策へと導く手法は、設計、効率、レイアウト及び構造の点で、大きな利点を提供する。同時に、これらの利点は回路スピード及びスループットの向上にもつながる。しかしながら複数の処理要素への区分化は、パイプライン操作が現在可能であるという事実の点でも、大きな利点を提供することを掲げることが重要である。特に、パイプライン操作は一般に小さな初期遅延を導入するが、単位時間当たりのモジュロＮ乗算に関して測定される場合、総スループットは非常に改善される。従って後述の説明の大部分は、前述の区分化処理要素構造を、図４、図６及び図８、並びにそれらの変形において示される回路を動作させるパイプライン方法と併せて使用する場合の議論にあてられる。
【００８３】
しかしながら、本発明のパイプライン方式に関わる議論を始める前に、図４乃至図９に示される回路が、非パイプライン方式でも完全に動作可能であることを言及することが有用であろう。こうした動作モードが図１０に示される。特に図１０は、情報を計算のＸフェーズとＺフェーズとの間で受け渡すために、レジスタ・セットＲ0乃至Ｒ33を最終及び一時記憶媒体として使用する様子を示す論理時間シーケンス図である。図１０はまた、レジスタ・セットと個々の処理要素との間の、前記指摘された違いを特に示す。この図はまた、最右端処理要素及び最左端処理要素の固有の位置を示し、最右端要素が３つのレジスタから情報を提供され、最左端処理要素は、レジスタセットの最左端部分すなわちＲ33からだけ、直接情報を受信する。なぜならこの特定のケースの場合、ｎは１０２４で、ｋは３２と仮定されるからである。図１０には、処理要素間の信号接続は示されていない。むしろ図１０は時間シーケンスと、レジスタ・セットの使用とを表している。特に図１０では、図の上半分のプロセッサ要素は、全てＸフェーズにおいて同時に動作し、同様に、図の下半分の全てのプロセッサ要素は、Ｚフェーズにおいて動作する。この動作モダリティの変形が、図１１、並びに回路への及び回路からの情報のパイプライン入出力に関する考察に関連して、以下で詳述される。図１０に示されるような非パイプライン方式の場合、全ての処理要素は同時にデータの処理を開始し、同時に処理を終了する。任意の所与のクロック・サイクルにおいて、全ての処理要素は全てがＸフェーズであるか、全てがＺフェーズである。このノードでは、各処理要素が、完全な部分結果レジスタ（２つのＲiレジスタ）の固定スライスを更新する。全ての部分積レジスタが同時に更新されるので、全てのことが前述のアルゴリズムに従い、円滑に作用する。
【００８４】
さて次に、処理要素がパイプライン方式に動作される本発明の態様について注目しよう。この結果を達成するために、図４及び図６に示される回路に特定のハードウェア変更が加えられる。これらの変更が、図１２及び図１３にそれぞれ詳細に示され、以下で詳述される。
【００８５】
しかしながら、パイプライン方式による処理要素の利用についてより理解するために、特に図１１に注目することにする。パイプライン・アプローチでは、所与のクロック・サイクルにおいて、任意の２つの隣接処理要素が常に異なるフェーズであり、重要度の低いデータ・スライスを処理している処理要素は、常に１クロック・サイクル先行する。一方、図１１の円矢印により示されるように、所与の処理要素がＸフェーズの間、それは入力として、３２ビット値をＺフェーズから要求し、この値は、まだ前のＺフェーズにあるチェーン内の次の処理要素により同時に計算されている。例えば図１０に示されるように、右上の最右端処理要素ＰＥ0はＸフェーズである。これは入力として、１クロック・サイクル遅れてＺフェーズにある処理要素ＰＥ1からの、Ｒ2の値を要求する。この問題は、チェーン内の次の処理要素からの、フィードバック・パスを追加することにより解決される。このパスは、ｋビット加算器（図１２の参照番号２３５及び図１３の参照番号１３５を参照）にリンクされる。この解決法は新たなｋビットの加算器の存在により、追加の遅延を生成する。しかしながら、最大動作周波数はそれ程影響を受けない。なぜなら、ｋビット加算器は比較的高速な回路であるからである。その上、この変化の前の以前の信号パスはクリティカル・パスではない。オリジナル・クリティカル・パスは、定数ｙの計算により、最右端処理要素ＰＥ0内で発生した。この特定の解決法の利点は、アルゴリズムの公式を変更する必要がないことである。しかしながら一方で、最大周波数はそれにも拘わらず僅かに影響を受ける。以下でより詳しく検討される追加の変形は、この些細な問題を考慮し、加算器２３５及び１３５により導入される遅延を排除する、更に別の解決法を提供する。いずれにしても、２つのパイプライン解決法のいずれも、図１０に示される純粋に並列なアプローチにより提供される解決法に比べて、より改善された解決法である。
【００８６】
前述のように、図１２は図６に類似であるが、円滑な演算をパイプライン方式に達成するための余分なハードウェア要素を含む。特に、ラッチ２３２、２３３及び２３４が、ｋビット幅の部分積出力（ＰＰＯ）及び（加算器２７５からの）単一ビット・キャリー出力線１及び（加算器２８５からの）単一ビット・キャリー出力線２を保持する、プロセッサ要素間の一時記憶機構として追加される。更にラッチ２３１は、乗数Ａiまたは定数ｙのいずれかの選択されたｋビット幅部分を記憶する。これはマルチプレクサ１３１（図１３）から交互に提供される。
更に、加算器２８５の出力からの下位ｋビットが、隣接する加算器２３５に供給される。これは実際には、先行する処理要素すなわち右側の処理要素内に存在する。同様にして、次の処理要素（すなわち左側の処理要素）からの下位ｋビットが、加算器２３５に供給される。更に、加算器２３５の出力から、レジスタ・"セット"の対応するセグメント、すなわち、Ｒ2p+1に接続されるフィードバック接続が存在する（但し図面の都合上、示されていない）。
【００８７】
図１３に示されるように、回路の類似の変更が最右端処理要素ＰＥ0にも実施される。特に、ラッチ１３１'、１３２、１３３及び１３４が追加され、図１２のラッチ２３１、２３２、２３３及び２３４により提供されるのと同じ機能を提供する。また図１２と同様に、パイプライン操作のための余分な加算ステップを組み込むために、加算器１３５が含まれる。図１３のラッチ１３１'は、マルチプレクサ１３１から供給される。このラッチからチェーン内の続く処理要素に、Ａi及びｙの値が供給される。この点に関して、値Ａiを含むレジスタ１１０が、図１３ではｋビット・レジスタとして示されるが、実際には、好適な実施例は図１に示され、そこではｎ＋１ビットを有するロングＡレジスタが、情報をマルチプレクサに提供し、これがＡレジスタの内容から、続くｋビット幅のチャンクを選択する。従って図１３のレジスタ１１０は、好適には、図１のレジスタ１０及びマルチプレクサ１１で示されるように構成される。図１３に示される単純化は、理解を明確化且つ容易にすることを目的とするに過ぎない。また図４の対応部分で明らかなように、マルチプレクサ１２１の出力は、好適にはＷ＋ｋビット幅である。ここでＷは汎用処理要素の各々により処理されるデータ・チャンクの幅である。
【００８８】
本発明の別の好適な実施例について述べる前に、全体的な考え方を提示するために、これまで述べてきた展開を考察することが役立つであろう。特に、本発明の第１の好適な実施例では、図１に示されるような、比較的大きな乗算器アレイ及び加算器アレイを使用する回路を提供する。第２の好適な実施例では、加算器アレイ及び乗算器アレイが区分化され、個々の処理要素がチェーン状に配置された。そこでは各々の処理要素が同一の構造を有し、情報がシステム内の最右端処理要素から最左端処理要素に転送され、図１に示される同一の操作を効率的に実行される。本発明の第３の好適な実施例では、処理要素が更に追加の加算器及びラッチを提供され、処理要素が図１１に示されるように、パイプライン方式で動作されることを可能にした。以下で詳述する本発明の次の好適な実施例では、追加の加算器１３５及び２３５が、クリティカル・データフロー・パスに悪影響を及ぼさないように、回路内で位置変更される。次に、この実施例について述べることにする。特にこの実施例では、処理要素及びレジスタ・セットが図１４に示されるように構成される。特に図１４では、個々の処理要素へのレジスタ接続が、実際に異なる。この違いは加算器の位置変更による。
【００８９】
特に図１５乃至図１６は、図１３からの加算器１３５の位置変更を示し、同様に図１７は、図１２からの加算器２３５の位置変更を示し、図１７では、加算器が加算器４３５'の位置へ位置変更される。従って、パイプライン操作に対応して図１２及び図１３で示される設計は、指摘された加算器を処理要素の入力ステージに移動することにより、更に改善され、これは図示のように、処理要素間の特定のフィードバック・パスを排除することにより容易になる。加算器は処理要素の出力から、部分積入力（Ｒレジスタ・パス）に移動され、よりゆっくりした乗算器機能ブロックと並列に動作する。これにより加算器がクリティカル・パスから排除される。図１１から、プロセッサ要素ＰＥpがＸフェーズのとき、それはレジスタ部分Ｒ2p+2及びＲ2p+1の両方から入力を要求することがわかる。Ｒ2p+1の値は実際には、ｐ番目のプロセッサ要素により、その前のクロック・サイクルの間に更新される。"問題"は、Ｚ2p+2の値を含むと予想されるＲ2p+2内の値が、プロセッサ要素ｐ＋１（ＰＥp+1）により、同一のクロック・サイクル内に更新されることである。Ｘフェーズの間、プロセッサ要素ＰＥpは、Ｒ2p+2に含まれる値Ｚ2p+2を、その出力の上位ｋビットに加算し、結果をＲ2p+1にロードする（これがＸ2p+1値である）。レジスタＲ2p+1の内容がＰＥpにより排他的に使用され、更新されると仮定すると、次のように続けることができる。すなわち、１）Ｘフェーズの間、プロセッサ要素ＰＥpはＲ2p+1をロードする前に、Ｒ2p+2の値をその出力に加算しない。また、２）Ｚフェーズの間、ＰＥpは余分な入力として、レジスタＲ2p+2の値を受信する（これはこの時点では、ＰＥp+1によりＺ2p+2と置換されており、以降の処理の前に、即時Ｒ2p+1入力に加算される）。図１３に示される回路の変更が、図１５乃至図１６に示され、これはこれらの目標を達成するように設計される。
【００９０】
前のパラグラフで述べたステップ１）の結果は、この時点では、Ｘフェーズの間に処理要素により生成される値が、前述のアルゴリズムで述べたものと、もはや同一ではない。この違いを補うために、Ｚフェーズの間に別の項が追加される。この変化の利点は、動作周波数の増加と、回路により必要とされるパワーの低減である。更に、必要とされるシリコン面積（すなわちチップ"面積"）が低減される利点と共に、より均一で繰り返し可能な回路設計を有する利点がある。従って、図１４はＲレジスタ・"セット"と処理要素との間の新たなデータフローを示す。同様に、図１５乃至図１６と図１７は、前述の目的を達成するための追加の回路の存在を示す。
【００９１】
本発明の改善されたパイプライン・バージョンのための最右端処理要素の特定の変更について次に述べることにする。前述の通り、乗算器１７３からの部分積出力がｋビット幅レジスタ４３２にラッチされる。更に、マルチプレクサ１３１からの変数Ｍがラッチ４３７にラッチされる。
【００９２】
位置変更される加算器４３５は、２ｋビットの幅を有する加算器である。これはキャリー入力信号（キャリー入力３）を受信し、２つの入力信号線を含む。２ｋビット幅信号は、レジスタＲ1（１９１）から供給される、ＡＮＤゲート４０２からの出力の組み合わせに由来する。レジスタ１９１はまた、マルチプレクサ１９３にも供給する（他の入力として、レジスタＲ0（１９０）からのｋビット出力信号を有する）。マルチプレクサ１９３の出力は、"Ｘ／Ｚ選択"信号線の制御に従い、レジスタＲ1またはレジスタＲ0の出力のいずれかを、加算器４３５への最右端ｋビット入力として供給する（加算器及び乗算器は、所望の操作が可換性であるので、左右の入力に関して対称である）。加算器４３５への第１の（最右端の）２ｋビット入力は、"Ｘ／Ｚ選択"信号が１か０かに応じて、それぞれ（Ｒ1，Ｒ0）または（０００．．．０，Ｒ1）である。"Ｘ／Ｚ選択"信号は、Ｘフェーズ動作またはＺフェーズ動作の回路を構成する。Ｘフェーズの間、加算器４３５は次の演算、すなわち（００．．．０，Ｒ1）＋０を実行し、その結果が加算器１３５に送られる。図１３と比較して、図１５乃至図１６の加算器回路１８５は（Ｒ1，Ｒ0）を受信するが、追加の信号入力（Ｒ2，００．．．０）も受信する。このオプションの理由は、パイプライン操作にもとづく。なぜならこうしたモードでは、左側の処理要素（ＰＥ）が常に１クロック・サイクル遅れているからである。例えば、図１３のＰＥ1はＲ2レジスタをＺ値により更新する責任を負い、このことはＸフェーズの間に、ＰＥ0がＰＥ1がまだ生成中であるそれ自身内のＲ2に記憶されるＺ値を必要とすることを意味する。従って図３では、加算器１３５がＲ2内のＸ値を続くＺ値に変換するために使用される。しかしながら、それにひきかえ図１５乃至図１６では、Ｒ2内の値が後に次のフェーズ（Ｚフェーズ）で、クリティカル・パス内に存在しない加算器４３５により加算される。
【００９３】
"Ｒ2選択"信号は、"Ｘ／Ｚ選択"信号がモジュラ乗算の間にＸフェーズ及びＺフェーズを制御する間、常に"０"である。この信号が"１"にセットされると、必要に応じて実行されるモジュラ乗算とは対照的に、通常の乗算を実行する機能を提供する。通常の乗算では、"Ｘ／Ｚ選択"信号線は常に"０"であり、"Ｒ2選択"信号線は常に"１"である。
【００９４】
加算器４３５への他の入力は、２ｋビット幅の信号であり、（ＡＮＤゲート４０１によりドライブされる）その最右端ｋビットは、モジュラ乗算の間はオールゼロであり、標準の乗算の間はレジスタＲ2の値に等しいように、"Ｒ2選択"信号により決定される。ＡＮＤゲート４０１の出力は、加算器４３５への最左端２ｋビット入力の下位ｋビットに接続される。この第２の入力の最左端ｋビットは、ＡＮＤゲート４０３を制御する"Ｘ／Ｚ選択"信号線の制御により、レジスタＲ2（１９２）から到来する。ＡＮＤゲート４０３は図示のように、マルチプレクサ１９３同様、"Ｘ／Ｚ選択"信号線により制御される。加算器の入力信号の再構成は、加算器１３５をタイム・クリティカル・パス内にない位置に位置変更することにより、必然的に生じる。
【００９５】
次に、信号線"ＰＥ0選択"の機能について説明する。この制御線の含有及び機能は、加算器４３５の位置変更に関係しない。信号線"ＰＥ0選択"が"１"のとき、処理要素内のハードウェアは汎用ハードウェア・プロセッサ要素Ｐｉ（１≦ｉ＜ｄ）に等価となる。信号線"ＰＥ0選択"が"１"にセットされると、マルチプレクサ４０６が"前のＰ"入力信号バスを選択し、それを加算器１７５（これはＰＥi内の加算器２７５に等価）に提供する。ＡＮＤゲート４０５の出力は、"０"（ＰＥ0が機能している場合）から、加算器１７５（またはＰＥiが機能している場合２７５）へのキャリー入力信号線によりドライブされる値に変化する。マルチプレクサ４０４は"キャリー入力２"信号線を選択し、それを加算器１８５（またはＰＥiが機能している場合２８５）へのキャリー入力として供給する。従って"ＰＥ0選択"信号線は、処理要素がＰＥ0としてではなく、汎用ＰＥiとして動作するように、次の装置、すなわち乗算器１７１、加算器１６５、マルチプレクサ１５２、乗算器１８０、レジスタ１５０及びレジスタ１６０を"ディセーブル"するために使用される。
【００９６】
"ＰＥ0選択"信号線が"１"状態にドライブされることが所望される２つのケースが存在する。これはＰＥが最右端ＰＥ0ではなしに、特に汎用ＰＥiのように振る舞うことを意味する。
【００９７】
第１のケースは、システムが処理要素の２つの別々のチェーンを含むように設計される場合である。例えば２つのチェーンの各々が、１つのＰＥ0と７つのＰＥiとの連結から構成される（すなわち、１チェーン当たり８つの処理要素から成る）。これらの２つのチェーン（各々が８つのＰＥを有する）は、モジュラ乗算演算を実行する上で特に有用であり、例えば、中国剰余定理（ＣＲＴ：Chinese Remainder Theorem）を使用するＲＳＡアルゴリズムなどの、公開キー暗号化アルゴリズムなどがこれにあてはまる。こうしたケースでは、２つのチェーンの各々が独立に動作して、２つのモジュラ乗算を実行する。前述のようなモジュラ乗算の場合、この演算を後述の指数関数と共に達成するコマンドが提供される。この場合、処理要素の２つのチェーンが連結されて、同一の時間内により多くのデータを処理することのできるより長いチェーンを形成する。この場合、左チェーンの最右端位置の"ＰＥ0"は、ＰＥiとして振る舞い、右チェーンのＰＥ7から入力を受信する（ここで"７"はチェーン・サイズが８の場合に調和して、１例として使用されるだけである）。これは"ＰＥ0選択"信号を"１"にセットすることにより達成される。これらの２つのチェーンは図式的に、次のように表される。
【数１】
ＰＥ7BＰＥ6B．．．ＰＥ1BＰＥ0B<......>ＰＥ7AＰＥ6A．．．ＰＥ1AＰＥ0A
【００９８】
ここで述べるハードウェアが中国剰余定理モード（後述）で動作していない場合、ＰＥ0BはＰＥiとして作用し、その"ＰＥ0選択"信号入力線が"１"にセットされる。ＰＥ0BをＰＥiとして動作させるために"１"にセットされる、他の１つの入力制御信号が存在する。特に、この信号線は図１５乃至図１６では、"補助選択"信号とラベル付けされて示される。
【００９９】
より詳細には、"ＰＥ0選択"制御線がマルチプレクサ４０４及び４０６及びＡＮＤゲート４０５の動作を制御する。ＰＥ0動作モードでは、キャリー入力１信号線が加算器１７５に、図１５乃至図１６に示される変更された最右端処理要素に入来する、前のＰＥ信号線からの信号と一緒に供給される。"ＰＥ0動作モード"でない場合には、キャリー入力は加算器１７５に供給されない。同様に、"ＰＥ0選択"信号線の状態にもとづき、マルチプレクサ４０４は、加算器１８５の最下位桁へのキャリー入力として、加算器１６５からの通常のキャリー出力信号か、非ＰＥ0動作モードでは、キャリー２信号を選択し、これらが加算器１８５のキャリー入力に供給される。これらの変形を除き、図１５乃至図１６に示される回路の残りの部分は、基本的に図１３に示される対応部分と同様に動作する。
【０１００】
図１５乃至図１６はまた、様々なハードウェア・モードでの適切な動作のために、幾つかの他の信号線を導入している。前述のように、"補助選択"信号線は２ビット信号であり、"００"、"０１"または"１０"の値を取る。"補助選択"信号線は、非ＣＲＴ動作では、ＰＥ0Bをその右側のＰＥ7Aと連結するために、前記ＰＥ0Bでは値"１０"を有する。"補助選択"信号バスがこの値にセットされるのは、このときだけである。他のケースでは、この信号線はＺフェーズの間（Ｘ／Ｚ選択信号＝１のとき）、"０１"にセットされる。"補助選択"信号の値"００"は、Ｘフェーズの間に使用されるＡi入力を選択し、値"０１"はＺフェーズの間に使用されるＹ入力を選択する。
【０１０１】
図１５乃至図１６に現れる他の信号線については、"ＲまたはＸ選択"信号線は、"Ｘ／Ｚ選択"信号と等価であり、"Ｒ2選択"信号線は、処理要素がモジュラ乗算ではなく、標準の乗算演算を実行するために使用されるときに、独立にドライブされる。"ＢまたはＮ選択"信号線は、次のクロック・サイクルの間に"Ｘ／Ｚ選択"信号により与えられる値を想定する（すなわち、"Ｘ／Ｚ選択"信号の予測バージョンである）。この理由は、マルチプレクサ１２１の出力が、ＢＮレジスタ１９８に記憶されるものを選択するために使用されるからである。すなわち、ＢＮレジスタ１９８はＸフェーズの間にはＢを含み、Ｚフェーズの間にはｎを含む。
【０１０２】
図１７は、図１２に示される回路の変形であり、図１２の位置変更された加算器２３５を、加算演算に関連して即時性が緩和される信号フロー・パス内の位置に収容する。図１２と図１７との特定の違いに関して、図１７では、もはや加算器２８５からの下位ｋビット出力を、右側の処理要素に供給する必要はない。更に、Ａi／ｙとラベル付けされる信号線の代わりに、入力信号線がＭとラベル付けされ、図１５乃至図１６のマルチプレクサ１３１が、単にＡiまたはｙからではなしに、３つの可能な入力から選択する事実を反映する。マルチプレクサ１３１の第３の入力（すなわち"前のＭ"信号線）は、（前記の例に従い、）非ＣＲＴ動作の間に、ＰＥ0BをＰＥ7Aと連結するために使用される。これは半分の数（すなわちこの例では８個）の処理要素を有する２つの独立したチェーンと対比して、処理要素の長いチェーン（この例では１６個）をオンザフライ式に構成することを可能にする。
【０１０３】
更に、２ｋビット幅を有する加算器４３５'が、その対応するレジスタ・セット・セグメントと加算器２８５との間に配置される。特に、加算器４３５'の出力は、加算器２８５への第２の入力として供給され、加算器４３５'のキャリー出力が、キャリー出力３信号線を出力するラッチＣ3（４３６）に供給される。ｋビット幅のレジスタＲ2p+2（２９２'）の内容が、"Ｒ2p+2選択"信号線により制御されるＡＮＤゲート・アレイ４０１の制御に従い、加算器４３５'の左側入力の下位ｋビット部分として供給される。レジスタＲ2p+2の内容はまた、"Ｘ／Ｚ選択"信号線により制御されるＡＮＤゲート・アレイ４０３の制御に従い、加算器４３５'の左側入力の上位ｋビット部分としても供給される。加算器４３５'の右側入力も２ｋビット幅であり、ＡＮＤゲート・アレイ４０２及びマルチプレクサ４９３から供給される。"Ｘ／Ｚ選択"信号線の制御に従い、マルチプレクサ４９３はレジスタＲ2p+1（２９１'）の内容か、右側の処理要素からのレジスタＲ2pの内容を供給する。加算器４３５'の左側入力に供給される２ｋビット・データ部分は、ＡＮＤゲート４０１及びＡＮＤゲート４０３により制御される。加算器４３５'の右側の２ｋビット入力は、２つの部分を含み、一方は上位ｋビット幅部分であり、これは"Ｒ2選択"信号線により制御されるＡＮＤゲート・アレイ４０１の制御に従い、０か、レジスタＲ2p+2（２９２'）から供給されるｋビット・データ部分のいずれかである。加算器４３５'への右側の入力の下位ｋビット幅部分はマルチプレクサ４９３により選択され、レジスタ２９１'（すなわちＲ2p+1）の内容か、右側の処理要素内のレジスタ２９２'（すなわちＲ2p）の内容のいずれかである。前述の回路の動作により、加算器２８５（図１７）が、乗算器２７２及び２７３により実行された乗算演算の結果を、加算器２７５の出力と一緒に累算する。加算器２８５の左入力は、加算器２８５を含む処理要素の動作フェーズに依存する。例えば、Ｘフェーズの間は結果が（００．．．０，Ｒ2i+1）であり、Ｚフェーズの間は結果が２進合計（Ｒ2i+1，Ｒ2i）＋（Ｒ2i+2，００．．．０）となる。但し、"００．．．０"はｋビット幅である。Ｒ2i+1を含む項は、Ｚフェーズの間だけ加算される。なぜならＸフェーズの間には、このレジスタ値はまだ左側の処理要素により更新されているからである。この様子は図１４に最も良く示される。
【０１０４】
更に図８に示されるような、単純化された最左端処理要素を使用したい場合、この回路に変更が加えられ、図１５乃至図１６及び図１７に関連付けられる改善されたパイプラン・バージョンが収容される。特に、これは前に使用されたＡＮＤゲート・アレイ３９９と、ｋビット幅加算器３８５との間に、増分キャリー回路４３９（図１８参照）を配置することにより達成される。増分キャリー回路４３９に供給される他の信号には、図１８に示される回路のすぐ右側の処理要素内のラッチ４３６から入来するキャリー入力Ｃinが含まれる。特に、この信号線は図１７にキャリー出力３として示される。前述の通り、単純化された最左端処理要素（ＰＥd）の使用は任意であるが、回路の単純化、スピード及びコストの点で、明らかに望ましいといえる。処理要素ＰＥENDすなわちＰＥdは、ＰＥからの前のＰＰＯ（部分積出力）を、その右側の加算器４３５'からの潜在的なキャリー出力信号（ラッチＣ3（４３６）に一時的に記憶される）に加算する機能を含む。この結果がレジスタＲ2pに記憶される。Ｚフェーズの間、この演算結果が図示のように、レジスタＲ2pに累算される。
【０１０５】
本発明のパイプライン・バージョンを用いて、処理要素チェーン幅内に存在するハードウェアよりも実際に広いオペランドを処理することも可能である（すなわち、ｎ＞＞Ｗｄまたはｎ＞＞ｍｋ）。この余分な幅の操作処理を実行する方法が、図１９に示される。特に、図１９の各水平線は１クロック・サイクルを表し、各垂直カラムは、処理されるデータのスライスを表す。各処理要素が６４ビットのデータ（一般に２ｋビット）を有すると仮定すると、第１のカラムは、データの下位２ｋビットのデータが常に処理要素ＰＥ0により処理されることを示す。第１のクロック・サイクルの間には、処理要素ＰＥ0だけがアクティブである。他の全ての処理要素はクロック・サイクル毎に、順次活動化される。このことは、前のプロセッサ要素が次の処理要素のためのパイプライン・データを生成するための、十分な時間を提供する。実際に、オペランドの幅が処理要素チェーン自体よりも長いことが可能である。例えばここでの議論では、ｎ＝５１２ビットの状況が考慮される。しかしながら本発明の態様によれば、５１２ビットとして設計されるパイプライン・ハードウェア構造を使用することにより、５１２ビットよりも長いオペランドを処理することが可能である。こうした状況では、第１の処理要素が活動化された後のクロック・サイクルにおいて、処理要素チェーン全体が左に２ｋビットシフトされ（図１９参照）、下位２ｋビットが未処理のままである。このシフトは、上位の処理要素（この場合ＰＥ8）がオペランドの上位２ｋビットを処理できるようになるまで継続される。その後処理要素チェーンは、ホーム位置にシフトして戻る代わりに、最右端処理要素ＰＥ0を除き、所定位置に留まる。下位の処理要素は、他の処理要素がホーム位置に戻った後、オペランドのスライスの下位２ｋビット・スライスの処理を継続する。全ての処理要素がそれらのホーム位置に戻ると、チェーン全体が前と同様に左シフトを開始する。この機構は全ての処理要素が常にビジーであるようにするので、最大性能レベルを達成する。更に、前の操作が終了する前に、新たな操作が開始する。ここで述べるアプローチは、全ての処理要素が常にビジーであるという点で、最大性能を提供する。更に、次の操作が遅延無しに、また任意の処理要素をアイドル状態にすることなく即時開始される。更に、これらの操作は完全に前述のパイプライン・アプローチと両立する。
【０１０６】
ＡＢ mod Ｎを計算する本アルゴリズムの説明の最初で述べたように、計算を値Ｎ0の負の逆数に等しい値ｓで始めることが望ましく、ここで逆数のモジュロＲ（Ｒ＝２k）が取られる。すなわち、ここで採用されるアルゴリズムの初期の説明では、値ｓ＝（−１／Ｎ0）mod Ｒの可用性が仮定された。この計算を実行する回路が図２０に示され、この図の上部には、変数Ｑの連続値を計算する回路が示され、それに応じて、図の下部には、相手の変数Ｓ、すなわち最終的に（−１／Ｎ0）mod ２kを計算する回路が示される。この点で、図２０に示される回路は実際には２つの演算を実行する。第１は、乗法的逆数を２の累乗数で割った剰余を計算し、同時に乗法的逆数の加法的逆数を計算する。通常の非モジュラ演算では、加法的逆数は比較的単純な演算であり、数が記憶される形式に応じて、代表的な数の最左端部の１ビットの加算または変更を要求するか、せいぜい下位の桁への１の加算を要求する程度である。しかしながらモジュラ加算では、演算が通常の非モジュラ演算のように単純に実行できない。従って図２０に示される回路は、実際には、２つの自明でないモジュロＲ演算を同時に実行する。特に、これは乗法的逆数を計算する一方、同時に、最終結果が負の加法的逆数のモジュロＲ（＝２k）であることを保証する。
【０１０７】
本発明の状況では、ＡＢ mod Ｎを計算する前記のアルゴリズムが、変数ｓ＝−１／Ｎ0モジュロＲを採用する。しかしながら、図２０に示される回路は、初期にＮ0レジスタ（５０１）に記憶される任意のｋビットの数Ａの、負の乗法的逆数を生成することができる。所望の負の乗法的逆数を生成するために使用される方法が、以下で述べられる。プロセスへの入力は、値ｋと、その負の乗法的逆数が所望される数すなわちＡである。ここでＡは順序付けられたｋタプルの形式により、（ａk-1，．．．，ａ1，ａ0）として表される。このプロセスの所望の出力は、ｓ＝−１／Ａモジュロ２kである。後述のプロセスでは、変数ｓが初期に値２k−１に等しくセットされる。変数Ａもまた最初に、プロセスの開始時において、Ｑレジスタ（５０４）にロードされる。従って、"開始"信号線が"１"の場合、マルチプレクサ５０５はその出力として値Ｎ0を含む、またはより一般的には、その負の乗法的逆数が生成される変数Ａを含むレジスタ５０１の内容を選択する。マルチプレクサ５０５は入力として、ｋビット加算器５０３の出力を受信する。この加算器は２つの入力、すなわち、Ｑレジスタ５０４からの最左端ｋ−１ビットと、レジスタ５０１に記憶される値Ａのｋビット入力とを有する。加算器５０３はまた、以下で詳述される状況の下で、右シフト操作を効果的に実行し、それにより０の上位ビットが適宜加算され、０が上位桁にシフトされるこのシフト操作を有効にする。
【０１０８】
変数Ｓが−１／Ａ mod ２kに変形される所望の計算を実行するプロセスは、次のように示される。すなわち、
0003703092.tif 000002
【０１０９】
従って、本発明のこの実施例におけるプロセスはｋ−１ステップ発生することがわかる。最後のステップで、Ｓレジスタの内容が、Ａ（または本発明の特定の目的ではＮ0）の所望の負の乗法的逆数に等しくなる。また負の乗法的逆数を計算するプロセスは、２つの変数Ｓ、Ｑの付随的な計算及び更新を採用する。図２０の上半分は、変数Ｑの更新及び計算を示す。特に、Ｑの最右端ビット（すなわちＱ1）が１のとき、ＡＮＤゲート・アレイ５０２を利用して、レジスタ５０１の内容が、Ｑレジスタ５０４からのＱの現在値に加算され、加算器５０３の出力がマルチプレクサ５０５を介して、再度Ｑレジスタに記憶される。この動作ステージにおいて、"開始"信号線は"１"に等しくなく、従って、マルチプレクサ５０５はその入力として、加算器５０３の出力を選択する。それ以外では、Ｑ＝Ａの初期化が実行される。
【０１１０】
図２０の下半分の回路は、プロセスの終わりでの所望の出力である相手の変数Ｓを計算する。変数Ｓの更新において、前述のプロセスに従い、Ｓの現在値から２の累乗に等しい数が減算される（すなわちＳ＝Ｓ−２i）。所望のプロセスを達成するために、Ｓレジスタ５６０に初期に、整数２k−１を表す"オール１"なる値がロードされる。ＡＮＤゲート・アレイ５６１が、Ｓレジスタへの特定のビットの書込みを制御する。特に図２０に示されるように、ＡＮＤゲート・アレイ５６１からのｋビット幅ベクトルが、レジスタ５６０への書込みのために使用可能である。ＡＮＤゲート５６１は各クロック・サイクルの間、必要に応じて、Ｓレジスタ５６０へのｋビット・ベクトルの書込みを可能にする。ベクトルの選択は、カウンタ５６３内の現在値により制御される。このカウンタ５６３は、０からｋ−１まで昇順にカウントし、次にロールオーバして、即時ゼロに向けて降順にカウントする。本発明の前述の例では、ｋは一般に３２ビットである。従って、カウンタ５６３は５ビットを含むだけでよい。一般に、カウンタ５６３はｋ'＝log2ｋを含む。従って、デコーダ・リング５６２はｋ'＝５ビットを受信し、出力として、ｋビット・ベクトルを生成し、そのエントリの１つだけが１である。これはデコーダ回路の本質的な動作機構である。カウンタ５６３は更に、信号線"ゼロ・カウント"を供給し、これはカウンタがオールゼロのとき"１"となる。
この信号線はＡＮＤゲート・アレイ５６１にも供給され、Ｑ（１）が"１"で、"ゼロ・カウント"信号線が偽で、開始信号線が偽のとき、書込み許可ビットをトリガする。従って、これらの状況の下で、ＡＮＤゲート・アレイ５６１が前述のアルゴリズムに従い、レジスタ５６３内の現在値により決定される、Ｓレジスタ５６０内の対応する部分への０ビットの書込みを許可する。レジスタ５６３は実際に、前記のアルゴリズムで述べられた、負の乗法的逆数計算のための変数ｉを含む。このようにして、Ｓの値がＳ＝Ｓ−２iに更新される。最後に計算の終わりに、Ｓレジスタ内の値（これは初期にはオール１にセットされる）が、Ｎ0レジスタ５０１に記憶された値の負の乗法的逆数のモジュロＲに等しくなる。
【０１１１】
（−１／Ａ）mod Ｎの代わりに、（１／Ａ）mod Ｎを計算したい場合、次のアルゴリズムを採用することができる。すなわち、
0003703092.tif 000003
【０１１２】
従って、単一セットの操作内で、所与の数の乗法的逆数のモジュロＲだけでなく、その算術的負の値のモジュロＲ（Ｒは同一値）も生成する回路及びプロセスが提供される。前述のＡＢ mod Ｎの乗算アルゴリズムのために、図２０に示される回路が、変数ｓ＝（−１／Ｎ0）mod Ｒの計算のために好適に使用され、結果が図１のレジスタ６０、図４及び図５ののレジスタ１６０、図１３のレジスタ１６０及び図１５乃至図１６のレジスタ１６０に記憶される。
【０１１３】
前述のように、本発明の基本的な目的は、暗号化のための大きな整数のモジュロＮの乗算である。暗号化はしばしば指数演算を含むので、次に羃法を実行するための本発明の使用について述べることにする。
【０１１４】
前述の関連回路及び資料が、次の属性を揺する特定の関数ｆを実現するために考慮される。すなわち、
ｆ（Ａ，Ｂ）＝ＡＢ２ーmk mod Ｎ；
ｆ（Ａ２mk，Ｂ２mk）＝ＡＢ２mk mod Ｎ；
ｆ（Ａ２mk，１）＝Ａ mod Ｎ；
if Ａ＜２N且つＢ＜２n，then ｆ（Ａ，Ｂ）＜２Ｎ；及び
if Ａ＜２N且つＡ≠Ｎ，then ｆ（Ａ，１）＜Ｎ
【０１１５】
前記において、問題は各々がｋビットのｍ"ワード"に区分化された。ここでｍｋ≧ｎ＋２であり、ｎはＮの２進表現でのビット数である。また前述の通り、Ｎ0はＮの最下位ｋビットである。またＮは勿論奇数である。
【０１１６】
前記の議論において、モジュロＮ乗算は通常、２ステップ・プロセスで実行された。すなわち、
ステップ１：Result1＝ｆ（Ａ，Ｂ）＝ＡＢ２ーmk mod Ｎ
ステップ２：Result2＝ｆ（Result1，２2mk）＝ＡＢ mod Ｎ
【０１１７】
関数ｆの前記の属性から、ＡまたはＢのいずれかと２mkによる事前乗算は、１ステップにおいて、同一の結果を生成することが理解される。すなわち、
Result＝ｆ（Ａ２mk，Ｂ）＝ｆ（Ａ，Ｂ２mk）＝ＡＢ mod Ｎ
【０１１８】
これはモジュラ乗算を１ショットの状況で実行する上で、明らかに好適なアプローチである。なぜなら、２mkによる事前乗算がシフト操作を通じて、容易に実行されるからである。しかしながら羃法の場合、前述のハードウェアで実現されたモジュラ乗算機能を繰り返して使用する。本ケースでは、羃法が繰り返し形式で実行されるが、関数ｆの各繰り返しの出力内に、因数２-mkが存在する事実、すなわち、ｆ（Ａ，Ｂ）＝ＡＢ２ーmk mod Ｎを扱わねばならない。従って、本発明では、ハードウェアにより実現される関数ｆが使用されるが、因数２mkが被乗数Ａ及びＢの両方に、次のように"事前に適用"される。すなわち、
ｆ（Ａ２mk，Ｂ２mk）＝ＡＢ２+mk mod Ｎ
【０１１９】
このように、関数ｆは各ステップで因数２-mkを導入するので、因数２mkを両方のオペランドに事前に適用する繰り返し操作は、一定の因数２mkを結果の一部として保持することになる。最後のステップにおいて、この因数は本ハードウェアにより実現される関数ｆを用いて、次のように削除される。すなわち、
ｆ（Ａ２mk，１）＝Ａ mod Ｎ
従って指数演算の最後の繰り返しにおいて、Ａが関数ｆの前の繰り返し適用からの出力となる。
【０１２０】
このステージにおいて、ｆ関数ハードウェアに入り込むこの値Ａが、適切な指数関数として構築されることを確認するために、値ＡE mod Ｎを生成する一般的な場合について考えてみよう。ここでＥは整数で、特にｔ＋１ビットの２進値、ｅt２t＋ｅtー1２t-1＋・・・＋ｅ2２2＋ｅ1２＋ｅ0＝Σｅi２i(但し０≦ｉ≦ｔ)により表される整数とする。ここでｅiは"１"または"０"である。ここで、指数の和が積になる事実（αx+y＝αxαy）を利用すると、次のようになる。
【数２】
0003703092.tif 000004
【０１２１】
２進整数Ｅに関するＡEのこの式にもとづき、次のアルゴリズムが、関数ｆのためのハードウェアを用いて、結果ＡE mod Ｎを生成する方法を提供することが理解される。このことは暗号化演算において非常に重要であり、特に公開キー暗号化システムにおいて重要である。ここで、Ｎ、Ｋ、Ｍ、Ｎ0及びｓ（＝（−１／Ｎ0）mod Ｒ、但しＲ＝２ｋ）は、前述の通り与えられる。この方法への入力は、値Ａ及びＥであり、Ｅはｔ＋１ビットの２進整数である。この方法は次のように要約される。すなわち、
0003703092.tif 000005
【０１２２】
このように、この方法の終わりにおいて、Ｚレジスタに記憶される値は要望通り、ＡE mod Ｎとなる。このプロシージャはまた、図２１に示されるフローチャートにおいても要約される。
【０１２３】
羃法アルゴリズムの多少異なる形態が、図２２に示される。これは擬似コードにより、次のようにも示される。
0003703092.tif 000006
【０１２４】
モジュラ羃法のためのこれらの方法のいずれかを実現する回路の構築において、ｆ（Ａ，Ｂ）＝ｆ（Ｂ，Ａ）であるように、関数ｆが対称式であるべきである。ｆが代わりに演算子と見なされる場合、この条件はコミューティビティ（commutivity）と呼ばれる。従ってｆを実現する回路は、動作変更無しに、それらの入力を交換され得る。また前記のアルゴリズムにおいて、ｅ0は指数Ｅの２進表現における最下位ビットである。更にここで述べる暗号化のために、Ｎは奇数である。従って、その最下位ビット桁は常に１である。それにより暗号化のために、ｅ0＝０か否かを確認するステップが除去可能である。
【０１２５】
１例として、羃法のアルゴリズムの１つを実現する回路が図２３に示される。
この羃法回路のコアは、ｆ（Ａ，Ｂ）＝ＡＢ２ーmk mod Ｎ関数を実現するエンジンにより提供される。従ってエンジン６００は、この間数を実行する前述のハードウェア・コンポーネントにより実現される。モジュロＮ乗算エンジン６００からの出力は、デコーダ６０３に提供される。デコーダ６０３は有限状態マシン（ＦＳＭ：finite state machine）６０７の制御に従い、この出力をＺレジスタ６０４またはＺ0レジスタ６０５に、或いは必要に応じて（図２１のアルゴリズムでは、Ｚ＝Ｚ0ステップを提供するために）、これらの両方に記憶する。デコーダ６０３は"デコーダ"の標準の動作定義、すなわち、通常情報を伝達する１セットの出力線だけを有するという定義に従い、常に機能するわけではない。図２３の回路が、ここで述べた羃法アルゴリズムのいずれかを実現しようとする場合、レジスタ６０４及び６０５の両方の出力（すなわちＺ及びＺ0）が、マルチプレクサ６０１及び６０２に入力（それぞれ入力Ａ及び入力Ｂ）として提供される。
これらのマルチプレクサは、定数１及びＣ＝２+2mk mod Ｎを提供される。しかしながら、定数"１"は、マルチプレクサ６０１への入力として、代わりに提供されてもよい。しかしながら、定数Ｃ及び入力Ａ（ＡE mod Ｎを計算するために使用される）は、Ｚ0＝ｆ（Ａ，Ｃ）を計算するために、異なるマルチプレクサ６０１または６０２にそれぞれ提供される必要がある。マルチプレクサ６０１、６０２及びデコーダ６０３は、全て制御装置６０７の制御の下で動作する。制御装置６０７は好適には、僅かに６状態しか有さない有限状態マシンとして実現され、これらの状態は、インデックス・カウンタ６０８の内容（０からｔまでカウントして、次に０にリセットされる）と、レジスタ６０６からのｉ番目の選択ビットｅiとに応じて決定される。
【０１２６】
例えば、図２１に示されるアルゴリズムを実現するにおいて、カウンタ６０８が０のとき、制御装置６０７はマルチプレクサ６０１のためにＡ入力を選択し、マルチプレクサ６０２のためにＣ入力を選択する。両方のアルゴリズムにおいて、初期化及び繰り返しの両面は２つのステップを含む。従って、ＦＳＭ６０７は、このステップ状態を示す１ビット・レジスタ６０９（ステップ状態レジスタ）を含む。マルチプレクサ６０１及び６０２を使用して、Ａ及びＣをエンジン６００への入力として選択すると、ＦＳＭ６０７はデコーダ（言うなれば、ルータ）６０３を制御して、出力ｆ（Ａ，Ｃ）＝ＡＣ２-mk mod ＮをＺ0レジスタ６０５に記憶する。こうした目的のためのＦＳＭの設計は標準的で、周知であり、例えば、M. Morris Manoによる教本"Digital Logic and Computer Design"、Copyright 1979 by Prentice-Hallで述べられている。
【０１２７】
ＣＲＴを前記のように使用するにおいて、２+2mk mod Ｎとして定義される定数Ｃが要求される。定数２2mkは一般に容易に決定及び構成できるが、モジュロＮを含まねばならないことは複雑な要因である。ｍｋ≧ｎ＋２は事実であり、ここでｎはＮ内のビット数で、ｍはこの関係を満足する最も小さな整数として選ばれる。従って、２+2mkは常にＮよりも大きくなり、従ってモジュロＮ形式が必要とされる。しかしながら、この定数は前述のｆエンジンを用いて容易に計算できる。まず最初に、ｔの小さな値に対して、Ｔ＝２mk+tを計算する。次にｆエンジンが、次のように繰り返し使用される。すなわち、
【数３】
0003703092.tif 000007
【０１２８】
このプロセスは、結果がＮよりも最初に大きくなるまで繰り返される。
【０１２９】
公開キー暗号化システムでは、情報を受信したい当事者は２つの（大きな）素数Ｎp及びＮqを選出し、それらの積Ｎ＝ＮpＮqだけを公開する。潜在的な受信者は公開キーＥを生成する（またはしばしばランダムに生成する）。この公開キーも公開される。しかしながら公開の前に、受信者であるべき者は、Ｅが積（Ｎp−１）（Ｎq−１）に比べて、かなりプライムであることを確認する。これは容易に行われる。なぜなら、受信者はＮp及びＮqの両方を知っているからである。公衆に知られているＮ及びＥにより、受信者に向けてメッセージＡを送信したい者は、ｃ＝ＡE mod Ｎを計算することにより、メッセージの暗号化バージョンｃを形成する。暗号化はモジュロＮの指数演算である。これを非標準的な算術問題にするのは、正に"モジュロＮ"である。しかしながら、ここで提供されるシステムは特に、ＡE mod Ｎ演算を実行することができる。
【０１３０】
受信の終了時、メッセージがＡ＝ｃD mod Ｎとして解読される。ここで前述の通り、ｃは受信される暗号化メッセージであり、Ｄは受信者にのみ知られている秘密キーであり、Ｄ＝Ｅ-1 mod [（Ｎp−１）（Ｎq−１）]として計算される。
これは受信者側により計算される。なぜなら、受信者だけがＮp及びＮqの値を知っているからである。（たとえＮが知られていても、Ｎ＝ＮpＮqは一般に数千ビットの大きな数なので、その因数すなわち素数Ｎp及びＮqは、決定するのが困難である。そして、この事実が公開キー暗号化の基礎となっている。）受信者はまた、効率的な解読のために有用な幾つかの他の値も計算、実際には再計算する。
特に、受信者は３つの値Ｕ、Ｄp及びＤqを次のように計算する。すなわち、
【数４】
Ｕ＝（１／Ｎq） mod Ｎp
Ｄp＝Ｄ mod （Ｎp−１）
Ｄq＝Ｄ mod （Ｎq−１）
【０１３１】
これらの値は、より効率的に所望の結果ｃD mod Ｎを生成することを可能にする。このプロセスは図２４により詳細に示される。（コード化メッセージｃが、前記使用された定数Ｃ＝２+2mkと混同されない。）
【０１３２】
次に、Ｎp及びＮqを知る受信者が、値Ｕ、Ｄp及びＤqを計算できる事実にもとづき、中国剰余定理が利用される。コード化メッセージｃは、０とＮ＝ＮpＮqとの間の整数であり、ここでgcd（Ｎp，Ｎq）＝１であり、"gcd"は"最大共通分母"（greatest common denominator）を意味する。ｃp＝ｃ mod Ｎp及びｃq＝ｃ mod Ｎqの場合、ＣＲＴはｃが次のように計算されることをほのめかす。すなわち、
【数５】
ｃ＝ｃq＋（Ｎq（（ｃp−ｃq） mod Ｎp）Ｕ） mod Ｎp
【０１３３】
ここでＵは前記のように定義される。この結果は特にｃD mod Ｎの計算に適用され、最初にｃD mod Ｎpとして定義される（ｃD）pが検討される。同様に、ｃD mod Ｎqとして定義される（ｃD）qが検討される。ここで（ｃ mod Ｎp）D mod Ｎp＝（ｃ mod Ｎp）Dpであり、Ｄp＝Ｄ mod （Ｎp−１）である。同様に、（ｃ mod Ｎq）D mod Ｎq＝（ｃ mod Ｎq）Dqであり、Ｄq＝Ｄ mod （Ｎq−１）である。このように、ｃ、Ｄp、Ｄq、Ｎp、Ｎq及びＵが与えられると、指数関数ｃD mod Ｎは次の３つのステップで計算される。すなわち、
【数６】
0003703092.tif 000008
【０１３４】
前記のステップ２は、図２１及び図２２で述べた方法を用いて、容易に実行される。ステップ３は、羃法を含まない直接的な計算である。更に、前述のように、処理要素のシーケンスを、(ｃp)D及び(ｃq)Dを同時に計算する２つのチェーンに分割することが可能である。
【０１３５】
次に、前記ステップ１で示された計算を更に単純化する方法について、考えてみよう。プロセスへの入力は、例えば２０４８ビットもにより表される比較的大きな数なので、計算には時間がかかる。しかしながら、モジュラ縮約は数Ｎp及びＮqにもとづき、これらはしばしば、大ざっぱに言ってその半分のサイズである。より一般的に言うと、Ａp＝Ａ mod Ｎp及び同様にＡq＝Ａ mod Ｎqを計算したいとしよう。一般性を失うことなく、Ｎp＞Ｎqと仮定することができる。またｎp及びｎqが、それぞれＮp及びＮqの２進表現でのビット数とする。更に、次の式を満足する最小の整数となるように、値ｍp及びｍqを選出するとしよう。すなわち、
【数７】
ｍpｋ≧ｎp＋２，及び
ｍqｋ≧ｎq＋２
【０１３６】
ここでｋは、モジュラ乗算における前述の回路のワード・サイズである。これらのパラメータにより、ＡpまたはＡqのいずれを計算したいかに応じて、Ａを次の２つの形式のいずれかで書表すことができる。すなわち、
【数８】
Ａ＝Ａ1p２mpk＋Ａ0p，または
Ａ＝Ａ1q２mqk＋Ａ0q
【０１３７】
前記の両方の式は、前述のようにＣＲＴのアプリケーションにおいて採用することができる。Ａが２０４８ビット程度の場合、ｎp＋ｎq≦２０４８であり、一般に０≦Ａ0p≦２mpk、０≦Ａ0q≦２mqk、０≦Ａ1p＜Ｎp及び０≦Ａ1q＜Ｎpである。更に２つの定数Ｃp＝２+2mpk mod Ｎp及びＣq＝２+2mqk mod Ｎqが定義される。これらの定数は実質的に、前述の定数Ｃ＝２+2mk mod Ｎと同じ役割を有するが、これらの新たな定数は、２つの部分を有するＡの表現に従い（すなわち、Ｎp計算におけるＡ1p及びＡ0p、Ｎq計算におけるＡ1q及びＡ0q）、より小さなスケールでの問題を容易にするために使用される。
【０１３８】
前述のように、本発明は、関数ｆ（Ａ，Ｂ）＝ＡＢ２-2mk mod Ｎを実現するエンジンを構築する回路を提供した。このエンジンまたは回路は、ｍ及びＮパラメータに応じて、異なる関数を実現することもできる。従って、関数ｆp及びｆqは次のように定義される。すなわち、
【数９】
ｆp（Ａ，Ｂ）＝ＡＢ２-mpk mod Ｎp，及び
ｆq（Ａ，Ｂ）＝ＡＢ２-mqk mod Ｎq
【０１３９】
まず最初に、Ａの２部分の表現、すなわちＡ1p２mpk＋Ａ0pの使用にもとづき、Ａpの計算におけるｆpの使用について、考えてみよう。すなわち、
【数１０】
0003703092.tif 000009
【０１４０】
同様に、ここで述べる回路をパラメータｍq及びＮqと共に用いて、Ａqを計算し、ｆqを生成することができる。
【０１４１】
前述の回路及び動作原理を使用する暗号化エンジン７００の好適な実施例の全体構造が図２５に示される。暗号化エンジン７００の主要な特徴は、前述のモジュロＮ乗算器６００を含むことである。ここで実現されたように、独立した処理要素（ＰＥ）のシーケンスとして、乗算器エンジン６００は、処理要素が"ＰＥ0"要素として動作するように電子的に制御することにより、２つの部分に分割可能である。これは解読操作の間に特に有用である。なぜなら、この状況では、受信者はＮp及びＮqの両方を知るのに対し、暗号化の間には、送信者は積Ｎ＝ＮpＮqだけしか知らないからである。
【０１４２】
ＡB mod Ｎの計算のために、レジスタ・セット６５８が次の値、すなわちＡ、Ｂp、Ｂq、Ｎp、Ｎq及びＵを保持するレジスタを含む。ここでＢp＝Ｂ mod （Ｎp−１）及びＢq＝Ｂ mod （Ｎq−１）である。レジスタ・セット６５８はまた、好適には、一時結果及び中間結果を保持する少なくとも２つのユーティリティ・レジスタを含む。特に、２つのこうしたユーティリティ・レジスタは、好適には前述のように、値Ａ1q及びＡ0qを含むために使用され、Ａ0p及びＡ1pはそれぞれＡＨレジスタ及びＡＬレジスタに記憶される。明らかに、これらの２つのユーティリティ・レジスタの役割は、交換可能である。レジスタ・セット６５８はまた、乗算器エンジン６００からの出力結果を含む出力レジスタを含む。
【０１４３】
暗号化エンジン７００は更に、モジュラ縮約ユニット６５３（図２６では補助計算回路としても述べられる）を含み、これは加算演算及び減算演算を実行し、単ショット・モジュラ縮約を実行する。
【０１４４】
レジスタ・セット６５８と、乗算器エンジン６００及びモジュラ縮約ユニット６５３との間のデータ・バス６７０を横断する信号のフローは、有限状態マシン（ＦＳＭ）コマンド制御ユニット６６０の制御の下で、前述の方法、アルゴリズム及びプロトコルのセットに従い実行される。前記の説明から明らかなように、このセットは、モジュラ乗算、定数Ｃ生成、羃法及び中国剰余定理（ＣＲＴ）のいずれか、または全てを実行し、ＣＲＴはモジュラ数を計算し、効率的な羃法のために使用される。
【０１４５】
Ｉ／Ｏ制御ユニット６６５は、デコード機能や、Ａ、Ｂ、Ｎ、Ｂp、Ｂq、Ｎp、Ｎq及びＵなどの値を、データ・バス６７０を介してレジスタ・セット６５８に供給するために必要な制御機能を実現する他に、ＣＲＴによるモジュラ羃法の場合には、２つの重要な機能を提供する。すなわち、第１の重要な機能は、ｍまたはｍp及びｍqの値を動的に計算し、指数ＢまたはＢp及びＢqの長さを計算することである。ｍの各値は、モジュラスの長さ（先行する１の桁）の関数であり、操作全体を通じて使用される主要パラメータである。指数の長さは、単に羃法プロセスを停止する時期を決定するために使用されるだけである。従来の解決法は、この大きなレジスタ内の各ビットの値をモニタするレングス検出器を使用する。このアプローチは、より大きなシリコン面積を要求する点で、またレジスタ上の出力における電気的負荷の点で欠点を有する。Ｉ／Ｏ制御論理で使用されるアプローチは遙かに無駄が少なく、書込まれるｋビット・ワード内の先行する"１"の検出と、関連アドレスとにもとづく。非ゼロのｋビット・ワードが書込まれる度に、小さな論理が、そのワード自身のアドレスにもとづき、書込まれている最上位の"１"の桁を計算し、前のｋビット・ワードのロードの結果、レジスタに記憶された値と比較する。新たに計算された値が、レジスタに記憶された値よりも大きい場合、レジスタが更新される。ｍパラメータの計算も同様のアプローチに従い、従って、ルックアップ・テーブル及び先行する"１"のための別の大きな検出器を必要としない。第２の重要な機能は、ＣＲＴによるモジュラ羃法の実行に備え、Ｉ／Ｏ制御ユニット６６５の制御の下で、前記の値Ａ1p、Ａ0p、Ａ1q及びＡ0qが計算され、別々のレジスタにロードされることである。
【０１４６】
エンジン７００の動作を外部的に管理するコマンドが、Ｉ／Ｏ制御ユニット６６５を介して提供される。次に、前述のモジュラ乗算回路を最も完全に利用するチェック・システム及び方法に目を向けてみよう。一般に、本発明のシステムにより実行されるハードウェア操作の結果をチェックする幾つかの方法が存在する。しかしながら、チェックのためのほとんどの標準のアプローチは、チップのサイズ、コスト及び実行される算術演算がモジュロＮ演算である事実により、否定的な影響を受ける。例えば、ハードウェアの単純な重複にもとづいた結果チェックは、"シリコン面積"の点で非常に高価となる。使用される様々な機能ブロック（乗算器、加算器、制御など）のエラー・チェックもまた、非常に高価で、複雑である。最後に、残余算術チェックサム方法の利用は、前述のＺ＝ｆ（Ａ，Ｂ）＝ＡＢ２-mk mod Ｎ関数を実現するモジュラ乗算ハードウェアのチェックサムには、直接適用できない。例えば、Ｚ'、Ａ'及びＢ'がＺ、Ａ及びＢのそれぞれチェックサムであるとすると、残念ながら、Ｚ'は必ずしもｆ（Ａ'，Ｂ'）に等しくない。従って、ハードウェア操作のチェックのための標準のアプローチの不適切さにより、ここで述べる方法及びシステムは、前述のアーキテクチャに密接に関連づけられ、またシステムが、Ｘ演算フェーズ及びＺ演算フェーズを用いてモジュロＮ乗算を実行し、関連オペランドを複数ｍのｋビット・ワードに区分化する概念にもとづき、複数の処理要素を使用する事実に特に関連付けられる。
【０１４７】
このチェック方法及びシステムを容易に理解するために、前述のプロセスの理解から開始することにする。
プロセス入力：Ａ、Ｂ、Ｎ（Ｎはもちろん奇数）
ｎ＝Ｎの２進表現でのビット数
ｋ＝１ワード（すなわち処理要素の１つにより処理される各チャンク）内のビット数
ｍ＝ｍｋ≧ｎ＋２なる最小の整数
Ｎ0＝Ｎの最下位ｋビット
Ｒ＝２k
ｓ＝（−１／Ｎ0）mod Ｒ
Ａ＝ΣiＡiＲi（但し０≦ｉ≦ｍ−１）
プロセス出力：Ｚ＝ｆ（Ａ，Ｂ）＝ＡＢ２-mk mod Ｎ
0003703092.tif 000010
【０１４８】
前記アルゴリズム、構造及びプロセスにもとづき、次の式は、モジュロＮ乗算回路の動作をチェックするために使用されるモデルの中枢を成す。すなわち、
【数１１】
0003703092.tif 000011
【０１４９】
従って、関数ｆ（Ａ，Ｂ）を計算するハードウェアは、次の関係（以下、式（１）と称す）を用いてチェック可能である。
【数１２】
0003703092.tif 000012
【０１５０】
このチェックサム計算の好都合な点は、オンザフライ式に計算されることである。例えば、ΣiＹi mod （Ｒ−１）（但し０≦ｉ≦ｍ−１）の計算に必要な回路が、図２７に示される。しかしながら図２７に示される回路は、中国剰余定理を使用する特定のケースに対して提供され、そこではＮp及びＮqが知られており、処理要素が２つの独立したチェーンに分割されて、一方はモジュロＮp乗算を計算するための、他方はモジュロＮq乗算を計算するために使用される。モジュロＮp計算では、累算レジスタＹ（アルゴリズムを説明するために上で使用されたｙi変数と混同しないために、参照番号６５２．３ａで示される）は、初期に０にセットされ、その出力が加算器６５２．２ａへの入力として使用される。別の入力は、ｙi値を生成する処理要素区分のためのレジスタの対応部分からの入力ｙi,pである。レジスタ６５２．１ａからの入力は現Ｙp値に加算されて、累算が生成され、これがサイクルの間にレジスタＹ（参照番号６５２．３ａ）に記憶される。ｍサイクルの終わりに、このレジスタの内容が、値Ｙ'p＝ΣＹi,p mod （Ｒ−１）（但し０≦ｉ≦ｍ−１）となる。同様に図２７の下半分に示される対応する回路が同様に動作して、Ｙ'q＝ΣＹi,q mod （Ｒ−１）（但し０≦ｉ≦ｍ−１）を計算する。Ｙ'p及びＹ'q計算の両方において、加算器６５２．２ａ及び６５２．２ｂはそれぞれ、ｋビット整数２進加算器であり、最上位桁からのキャリーが最下位桁へのキャリー入力としてフィードバックされる。このように、モジュロ（Ｒ−１）加算が実行される。
【０１５１】
このように図２７に示される回路は、チェックサム値Ｙp'及びＹq'を、図２８に示されるチェックサム予測回路８００に供給する。図２７の回路と非常に類似する回路（図示せず）が、同様に、値Ａi,p及びＡi,qの累算合計（モジュロ（Ｒ−１））から（但し、ｉ＝０，１，．．，ｍ−１）、それぞれチェックサム値Ａ'p及びＡ'qを生成するために提供される。同様に、チェックサム値Ｂ'p及びＢ'qが同様の回路（図示せず）から生成される。更に類似の回路が、Ｎi,p及びＮi,q値からＮ'p及びＮ'qを生成する。これらの回路は構造及び動作的に同一であり、信号要素の名前付けが異なるだけなので、上で述べた回路同様、ここでは示されていない。
【０１５２】
式（１）で示された加算演算は、加算器８２０により実行される。この加算器はモジュロ（Ｒ−１）加算を実行し、従ってチェックサム・システムの他の加算器同様、図示のように、最下位キャリー入力としてフィードバックされる最上位キャリー出力信号を含む。マルチプレクサ８２４、８２５、８２６及び８２７は、２つの信号線により制御される。第１の制御信号線（ｐ／ｑ）は、マルチプレクサ８２４及び８２６を制御して、Ｎp及びＮq処理のための２つの独立した処理要素チェーンから選択する。第２の制御信号線（加算選択）は、マルチプレクサ８２５及び８２７を制御し、式（１）においてｉ＝０からｍ−１までの総和により示される、累積加算演算を実行する。中間チェックサム値Ａ'p、Ｂ'p及びＡ'q、Ｂ'qを計算するために、最終加算演算が実行され、これは加算選択制御線の操作に従い、Ｐ0レジスタ及びＰ1レジスタ（それぞれ参照番号８２１、８２２）の内容を加算する。加算器８２０も最終加算を請け負い、レジスタ８３１及び８３２に記憶される前のチェックサム値を、累積チェックサム（ＮＹ）'p及び（ＮＹ）'qと加算することにより、（ＡＢ）'p及び（ＡＢ）'qを生成する。この結果、レジスタ８３１及び８３２から、それぞれＰチェックサム値及びＱチェックサム値が生成される。これらの信号線が、主チェックサム生成ブロック６７０（図２６）に供給される。特に、Ｐチェックサム及びＱチェックサム信号線は、図２９に示されるように、比較器６５７ａ及び６５７ｂにそれぞれ供給される。
【０１５３】
従って、図２９の構造及び動作について説明する。ブロック６７０の主な機能は、式（１）の左側の計算である。前述の通り、この回路はＮp演算及びＮq演算にもとづき、計算を分割するための２つの部分を有する。こうした分割は、図９に示される処理要素において、中央の処理要素がＰＥ0モードで動作するように強制的に制御されるとき、達成される。
【０１５４】
各処理要素チェーン（ＮpチェーンまたはＮqチェーン）は、モジュラ乗算演算の結果の２ｋビットを１度に出力する。従って、Ｚ変数のチェックサム値Ｚ'を生成する回路が、それぞれがｋビットの２つの加算器として実現される。更に分割により、実際には図２９に示されるように、合計４つの加算器が存在する。例えば、Ｎpチェーンの場合、加算器６５６ａ1が、乗算演算から出力される上位ビットを処理する。ここでこの乗算演算は、モジュロＮp乗算に関わるチェーンから、それぞれの上位ｋビット出力を生成する。全ての２ｋビット部分が合計されると、マルチプレクサ６５６ａ2が上位レジスタＺ'p,H内の和と、下位レジスタＺ'p,L内の和とを合計する。この結果の合計が、比較器６５７ａによりＰチェックサム値と比較され、不一致が生じる場合、エラー指示ＥＲＲＯＲ2aが生成される。ここで図２９に示される加算器は全てに、モジュロ（Ｒ−１）を実行し、最上位桁から最下位桁へのキャリー・フィードバックを含む。図２９の下半分に示される回路は、上半分の回路と同様に構成され同様に動作する。しかしながら明らかなように、下半分の回路は、前述の処理要素チェーンの分割にもとづき、モジュロＮq計算の間に生成される信号に関連づけられ、またそれらに対して作用する。従って図２９の下半分の回路は、モジュロＮq計算からＺ'qチェックサム信号を生成し、この結果の値が比較器６５７ｂで比較され、不一致が生じる場合、エラー信号ＥＲＲＯＲ2bが生成される。従ってブロック６７０の出力は、ＥＲＲＯＲ2a ＯＲ ＥＲＲＯＲ2bと記述できる。各モジュラ乗算演算の終わりに、全てのハードウェア要素が設計通りに機能し、意図した結果を生成したことを示すエラー信号が入手可能になる。
【０１５５】
更に、図２６は補助計算回路６５３を含むことを示している。この回路は、Ｚ＝Ｊ＋Ｋ、Ｚ＝Ｊ−Ｋ及びＺ＝Ｊ mod Ｎなどの、補助演算を実行するために使用される。これらの計算のチェックサム演算は任意的であるが、実行するのが望ましい。補助計算回路６５３により実行される計算は、モジュラ乗算と比べると、比較的単純である。これらの計算の残余チェックも比較的単純である。加算演算Ｚ＝Ｊ＋Ｋのために、チェック機構は、Ｚ mod （Ｒ−１）の値が、（Ｊ mod Ｒ−１）と（Ｋ mod Ｒ−１）のモジュロ（Ｒ−１）合計の値と同じであることを確認する。ここでＲは偶数の整数である。同様に、Ｚ＝Ｊ−Ｋの演算をチェックするために、Ｚ mod （Ｒ−１）の値が、（Ｊ mod Ｒ−１）と（Ｋ mod Ｒ−１）のモジュロ（Ｒ−１）差の値と同じか否かをチェックする。長い除算により実現されるモジュラ縮約Ｚ＝Ｊ mod Ｎの演算に関しては、ＺはＪをＮで除算した剰余である。従って式Ｊ＝ＱＮ＋Ｚが与えられ、ここでＱは商である。このモジュラ縮約演算のエラー・チェックは、Ｊ mod （Ｒ−１）の値を、（Ｑ mod （Ｒ−１））、（Ｎ mod （Ｒ−１））及び（Ｚ mod （Ｒ−１））のモジュロ合計と比較することにより実行される。
【０１５６】
前述の概念の多くは、一見純粋に数学的なアルゴリズムの観点から表されてきたが、関連する応用例は、実際にはメッセージの暗号化、伝送及び解読に向けられ、そこではメッセージはデジタル形式またはそれに等価なもの（８進数、２進化１０進数、１６進数など）であれば、どのような形式で表現されてもよい。暗号化、伝送及び解読のためのこれらの方法では、メッセージが２進形式の非常に大きな整数で表現されるので、ここで提示される方法及び装置の理論、動作及び値を説明する目的上、説明は必然的に数学的性質を持つことになる。それにも拘わらず、これらの装置及び方法は、確実な通信を保証する実用的な方法を提供する。従ってここで述べられた装置及び方法は、数学的な概念の実用的な実施例を表すと言える。
【０１５７】
また、ここで述べられる回路の動作は、繰り返しサイクル数に渡って発生するものである。またここでの説明は、最も汎用的な状況での適切な動作において一般に要求される、理想サイクル数を示すものである。しかしながらここでの詳述及び請求項の両方とも、最も汎用的なケースに制限されるものではない。特に次善の制御方法ではときに、偶然にまたは設計的に、絶対に必要とされるよりも多くのサイクルに渡って、回路を動作させたりする。従って請求項の範囲は、狭義に解釈されるべきではない。同様に特定の入力状況では、最も汎用的なケースで通常要求される全サイクル数が要求されない。従って、一部の請求項は高々ｔサイクルの動作について主張する。明らかなように、暗号化及び解読における利用に関して、ここで述べた回路は最も汎用的なケースを扱うように設計された。しかしながら請求項はより単純なケースや、必要なサイクル数以上に渡るより意図的なケースを除外するなど、狭義に解釈されるべきではない。
【０１５８】
以前述べたように、前述した全ての目的が、前述した回路及びプロセスにより達成されることが理解されたことであろう。特に、比較的大きな数のモジュロＮの乗算を実行する回路及びプロセスが、乗算器アレイ及び加算器アレイを用いて、或いは、複数のほぼ同一の処理要素を用いて提供された。またこれらの同一の回路が、モジュラ羃法を実現するだけではなく、中国剰余定理にもとづき、問題の解決法を実現するハードウェア回路の一部としても使用されることが、理解できた。更に、一連の処理要素のパイプライン操作を提供する目的が、全ての処理要素が常時機能して、所望の最終結果または中間結果を生成する態様において、達成された。更に、前述のプロセスに付随する機能を実行する回路が提供され、特に、負の乗法的逆数を生成する回路及びプロセスが提供された。こうした逆数はデータ処理システムにおいて、ソフトウェアにより、または従来の（もしくは別々の）計算により提供可能であるが、ここで示されたプロセス及び回路は、この機能を、既存の回路レジスタ及び要素を利用する比較的単純なハードウェアにより、短時間で提供することができる。
【０１５９】
以上から、ここで示された回路が前述の全ての目的を達成することが明らかとなった。更に、この回路の構築は容易であり、乗算プロセスにおいて、オペランドの１つを、各々がｋビットを有するｍブロックとして構成することによりもたらされる並列性を十分利用する。特に、ここで示される回路は、２フェーズ動作を実行し、第１フェーズではＸi及びｙiを計算し、第２フェーズではＺiの値を計算する。そしてこのＺiが最終的に最後のステップにおいて、所望の結果となる。特に、ここで示された回路は、ｎビット×ｎビットのサイズでなければならない乗算器と、各ステップにおいて考慮される因数の１ビットだけに作用する直列回路との間の、所望のトレードオフを提供する。
【０１６０】
以上、本発明は特定の好適な実施例に関連して述べられてきたが、当業者であれば、本発明の趣旨及び範囲から逸れることなく、様々な変更や変形を行うことが可能であろう。
【０１６１】
まとめとして、本発明の構成に関して以下の事項を開示する。
【０１６２】
（１）各々が最大ｎビットを有する２つの２進数Ａ及びＢを乗算する回路であって、乗算がモジュロＮであり、Ｎが奇数であり、数Ａ及びＢの少なくとも１つが、各々がｋビットを有するｍブロックに、ｍｋ≧ｎ＋２なる関係で区分化可能なものにおいて、
直列に接続される複数Ｗのプロセッサ要素を含み、各プロセッサがデータを各々がｄビットのブロックにおいて処理でき、直列の各プロセッサが、数Ａ及びＢからの徐々に上位に向かうｄビットのブロックを処理し、各プロセッサ要素が、各々が第１のフェーズ及び第２のフェーズを有する、複数ｍのプロセッサ要素サイクルの少なくとも１サイクルの間に、中間結果を受信及び保持する２ｋビットの累算レジスタ部分と、
各サイクルの前記第１のフェーズの間に、２ｋビットのデータを出力として選択し、前記出力の最左端ｋビットが、前記直列内の続くプロセッサ内の前記累算レジスタ部分から選択され、前記出力の最右端ｋビットが、前記累算レジスタ部分からの最左端ｋビットから選択され、各サイクルの前記第２のフェーズの間に、前記累算レジスタ部分から完全な２ｋビットのデータを選択する、第１のマルチプレクサと、
前記数Ｂの２ｋビットのブロックを記憶する因数レジスタ部分と、
前記数Ｎの２ｋビットのブロックを記憶するモジュロ・レジスタ部分と、
各サイクルの前記第１のフェーズの間に、前記因数レジスタ部分から、２ｋビットのデータを出力として選択し、各サイクルの前記第２のフェーズの間に、前記モジュロ・レジスタ部分から２ｋビットのデータを選択する、第２のマルチプレクサと、
前記マルチプレクサの出力を記憶する一時レジスタと、
各サイクルの前記第１のフェーズの間に、前記数Ａの２進表現から、データのブロックを表すｋビットのデータを出力として選択し、各サイクルの前記第２のフェーズの間に、出力加算器からフィードバックされるデータの最右端ｋビットを選択する、第３のマルチプレクサと、
入力因数として、前記第３のマルチプレクサからの出力ｋビットと、前記一時レジスタからの最左端ｋビットとを有する、ｋビット×ｋビットの第１の乗算器であって、前記第１の乗算器からの最左端ｋビット出力が、前記直列内の続くプロセッサ要素における部分積として使用可能である、第１の乗算器と、
入力因数として、前記第３のマルチプレクサからの出力ｋビットと、前記一時レジスタからの最右端ｋビットとを有する、ｋビット×ｋビットの第２の乗算器と、
第１及び第２の入力を有する２ｋビットの中間加算器であって、前記第１の入力の最左端部分が、前記第１の乗算器からの最右端ｋビット出力であり、前記第１の入力の最右端部分が、前記第２の乗算器からの最右端ｋビット出力であり、前記第２の入力の最左端部分が、前記第２の乗算器からの最左端ｋビット出力であり、前記第２の入力の最右端部分が、前記直列内の前のプロセッサ要素からのｋビット部分積であり、前記直列内の前のプロセッサ要素から、キャリー入力信号をその最下位桁に受け入れ、前記直列内の続くプロセッサ要素への入力として、キャリー出力信号を生成する、２ｋビットの中間加算器と、
第１及び第２の入力を有する前記の出力加算器であって、前記第１の入力が前記第１のマルチプレクサの出力であり、前記第２の入力が前記中間加算器からの出力であり、前記出力加算器からの出力が前記累算レジスタ部分に供給され、前記出力加算器が、前記直列内の前のプロセッサ要素から、キャリー入力信号をその最下位桁に受け入れ、前記直列内の続くプロセッサ要素への入力として、キャリー出力信号を生成する、出力加算器と
を含む回路。
（２）２つのｎビットの数Ａ及びＢのモジュロＮを乗算する回路で使用されるプロセッサ要素であって、
第１の動作フェーズの間に、Ｘi＝Ｚi＋ＡiＢのｋビット幅部分と、ｙi＝ｓｘi,0とを計算し、第２の動作フェーズの間に、Ｚi+1＝（Ｘi＋ｙiＮ）／Ｒのｋビット幅部分を計算するように構成される、２つの加算器、２つの乗算器及び複数のマルチプレクサ回路を含み、ここでｓ＝−１／Ｎ0 mod Ｒ、Ｒ＝２k、ｘi,0はＸiの最下位ｋビット、Ｎ0はＮの最下位ｋビットである、プロセッサ要素。
【図面の簡単な説明】
【図１】ここで述べるモジュロＮ羃法の方法及びシステムで使用される回路を示すブロック図である。
【図２】計算の第１の、すなわちＸフェーズの間にアクティブとなるデータフロー・パスを特に示す以外は、図１と同一のブロック図である。
【図３】計算の第２の、すなわちＺフェーズの間にアクティブとなるデータフロー・パスを特に示す以外は、図１及び図２と同一のブロック図である。
【図４】図１の回路の区分化された実施例における、一連の処理要素内の最右端処理要素のブロック図である。
【図５】代わりの乗算器と加算器の接続を示す、図４と類似のブロック図である。
【図６】図１に示される回路と同じ演算を実行可能な一連のプロセッサ要素として構成可能な、複数の同一の処理要素の１つを示すブロック図である。
【図７】代わりの乗算器と加算器の接続を示す、図５と類似のブロック図である。
【図８】図１の回路と同じ計算を実行する一連のプロセッサ要素内の最後の、すなわち最左端のプロセッサ要素として迅速に使用される処理要素の形態を示すブロック図である。
【図９】図１に示される回路と同じ結果を生成するために、図４、図５及び図６に示されるプロセッサ要素が接続される様子を示すブロック図である。
【図１０】特にレジスタ記憶及びＸフェーズ動作及びＺフェーズ動作に関連して、時間の経過に伴うプロセッサ要素の論理接続を示すブロック図である。
【図１１】プロセッサ要素をパイプラン式に使用する様子を示すブロック図である。
【図１２】パイプライン・モードで使用されるように構成される典型的なプロセッサ要素を示すブロック図である。
【図１３】最右端位置または最左端位置で使用されるプロセッサ要素を詳細に示す、図１２と類似のブロック図である。
【図１４】クリティカル・パスから加算器を除去することにより処理時間を高速化する、パイプランの利用の変形を示す、図１０と類似のブロック図である。
【図１５】性能改善のためにクリティカル・パス内の加算器が移動された、改善された最右端プロセッサ要素を示すブロック図である。
【図１６】性能改善のためにクリティカル・パス内の加算器が移動された、改善された最右端プロセッサ要素を示すブロック図である。
【図１７】改善されたパイプライン操作において使用される典型的なプロセッサ要素を特に示す、図１５乃至図１６と類似のブロック図である。
【図１８】改善されたパイプライン構成における最左端プロセッサ要素の好適な設計を示すブロック図である。
【図１９】パイプライン操作におけるプロセッサ要素の利用を示す図である。
【図２０】ある数の負のモジュラ逆数を計算する回路を示すブロック図である。
【図２１】更に指数関数を実現するように、モジュラ乗算を実現する回路を使用する方法を示すフローチャートである。
【図２２】モジュラ指数関数を実現する別のアルゴリズムを示す、図２１に類似のフローチャートである。
【図２３】図２１または図２２にアルゴリズムのいずれかを実現する回路のブロック図である。
【図２４】特に指数演算を採用し、より詳細には、効率改善のために使用される信号変数の存在を示す、公開キー暗号化及び解読プロセスを示すブロック図である。
【図２５】本発明に従う暗号化エンジンの１実施例を示すブロック図である。
【図２６】モジュロＮ乗算システムに調和するチェックサム機構の包含関係を示すブロック図である。
【図２７】モジュロ（Ｒ−１）加算を用いて中間チェックサム値を生成する、一般に適用可能な回路を示すブロック図である。
【図２８】エラー指示を提供する最終チェックサム比較演算において使用されるチェックサム演算を実行する回路のブロック図である。
【図２９】モジュロ（Ｒ−１）加算器の対を使用することにより、比較されるチェックサム変数を生成する回路を示すブロック図である。
【符号の説明】
１０、２０、３０、４０、５０、５５、６０、１１０、１２０、１２０’、１３０、１４０、１４０’、１５０、１６０、１９０、１９１、１９２、１９８、２１０、２２０、２２０’、２４０、２４６’、２９０、２９１、２９１’、２９２、２９２’、２９８、３９０、４３２、５０１、５０４、５６０、５６３、６０４、６０５、６０６、６５２．１ａ、６５２．１ｂ、６５２．３ａ、６５２．３ｂ、８２１、８２２、８３１、８３２、８３３、８３４  レジスタ
１１、２１、３１、５２、１２１、１３１、１５２、１９３、２２１、２９３、４０４、４０６、４９３、５０５、６０１、６０２、６５６ａ2、６５６ｂ2、６５９、６６１、８１１、８１２、８２４、８２５、８２６、８２７  マルチプレクサ
６５、７５、８５、１３５、１６５、１７５、１８５、２３５、２７５、２８５、３８５、４３５、４３５’、５０３、６５２．２ａ、６５２．２ｂ、６５６ａ1、６５６ａ3、６５６ｂ1、６５６ｂ3、８２０  加算器
７０、８０、１７１、１７２、１７３、１８０、２７２、２７３、８１０  乗算器
１３１’、１３２、１３３、１３４、２３１、２３２、２３３、２３４、４３３、４３４、４３６、４３７  ラッチ
３７５、４３９  増分キャリー
３９９、４０１、４０２、４０３、４０５、５０２、５６１  ＡＮＤゲート
５６２  デコーダ・リング
６００  モジュロＮ乗算器エンジン
６０３  デコーダ
６０７  有限状態マシン（ＦＳＭ：finite state machine）、制御装置，ＦＳＭ
６５３  モジュラ縮約ユニット
６５７ａ、６５７ｂ  比較器
６５８  レジスタ・セット
６６０  有限状態マシン
６７０  データ・バス
【図１】
0003703092.tif 000013
【図２】
0003703092.tif 000014
【図３】
0003703092.tif 000015
【図４】
0003703092.tif 000016
【図５】
0003703092.tif 000017
【図６】
0003703092.tif 000018
【図７】
0003703092.tif 000019
【図８】
0003703092.tif 000020
【図９】
0003703092.tif 000021
【図１０】
0003703092.tif 000022
【図１１】
0003703092.tif 000023
【図１２】
0003703092.tif 000024
【図１３】
0003703092.tif 000025
【図１４】
0003703092.tif 000026
【図１５】
0003703092.tif 000027
【図１６】
0003703092.tif 000028
【図１７】
0003703092.tif 000029
【図１８】
0003703092.tif 000030
【図１９】
0003703092.tif 000031
【図２０】
0003703092.tif 000032
【図２１】
0003703092.tif 000033
【図２２】
0003703092.tif 000034
【図２３】
0003703092.tif 000035
【図２４】
0003703092.tif 000036
【図２５】
0003703092.tif 000037
【図２６】
0003703092.tif 000038
【図２７】
0003703092.tif 000039
【図２８】
0003703092.tif 000040
【図２９】
0003703092.tif 000041