(57)【特許請求の範囲】
【請求項１】
複数の加算器と複数のレジスタとを有し、乗数と被乗数とのモジュラ・乗算を遂行するための超小形電子系装置であって、該超小形電子系装置は、
前記乗数、部分的な結果およびモジュロをそれぞれ格納するように動作する第１のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０）、第２のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１１）、および、第３のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１２）と、
予め定められたモントゴメリ定数を格納するように動作するモントゴメリ定数レジスタ（１７）と、
前記被乗数の複数の部分の各々について、前記第１のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０）から前記乗数を受け取ると共に、被乗数レジスタ（１６）から前記被乗数の現在の部分を受け取り、前記被乗数の現在の部分に対し前記乗数を乗算し、乗算により得られる積を含む出力を発生させるように動作する第１の多重化された直列／並列形の乗算デバイス（１９）と、
前記第２のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１１）の内容から前記モジュロを減算し、当該レジスタ（１１）の内容に対してより限定された意味における合同の関係にある出力を生成するための第１の減算器（２８）とを備え、
ここで、前記被乗数の複数の部分が、前記第１の多重化された直列／並列形の乗算デバイス（１９）により処理された後は、前記部分的な結果が、前記乗数と前記被乗数との前記モジュラ・乗算を遂行した結果に関してより限定された意味における合同を形成し、
前記超小形電子系装置は、さらに、
前記第１の多重化された直列／並列形の乗算デバイス（１９）の前記出力と前記第１の減算器（２８）の前記出力とを加算し、一つの出力を生成するように動作する第１の直列形の加算器（３０）と、
第１の段階にて、前記第１の直列形の加算器（３０）の前記出力と前記モントゴメリ定数レジスタ（１７）の内容とを受け取り、第２の段階にて、前記第３のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１２）から前記モジュロを受け取ると共に、前記第１の段階で得られる出力を受け取る第２の多重化された直列／並列形の乗算デバイス（２０）であって、前記第１の段階にて、前記モントゴメリ定数と前記第１の直列形の加算器（３０）の前記出力の一部との乗算により得られる第１の段階の積を算出するように動作し、前記第２の段階にて、前記第１の段階の積に対し前記モジュロを乗算するように動作し、これによって、第２の直列形の加算器（３１）において前記第１の直列形の加算器（３０）の前記出力と結合したときに前記部分的な結果を生成するような前記第２の段階の出力を発生させるように動作する第２の多重化された直列／並列形の乗算デバイス（２０）と、
少なくとも前記第２の多重化された直列／並列形の乗算デバイス（２０）に対し、前記第１の段階における入力および前記第２の段階における入力をそれぞれ提供し、ここで、前記第１の段階における入力は、前記第２の段階の入力とは異なっているスイッチング素子（２３、２６）と、
前記第１のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０）の内容から前記モジュロを減算し、該モジュロにより減じられた当該レジスタ（１０）の内容を生成するための第２の減算器（２７）とを備え、
ここで、前記第１の多重化された直列／並列形の乗算デバイス（１９）は、前記モジュロにより減じられた当該レジスタ（１０）の内容を直列形式で受け取ると共に、前記被乗数の現在の部分を並列形式で受け取り、
前記超小形電子系装置は、さらに、
前記第２の直列形の加算器（３１）の出力を受け取り、前記第２の直列形の加算器（３１）の前記出力が、前記モジュロより大きいかもしくは該モジュロに等しいかを決定するように動作するボロー検出デバイス（３５）とを備え、
前記第１の多重化された直列／並列形の乗算デバイス（１９）のビットの長さ、および、前記第２の多重化された直列／並列形の乗算デバイス（２０）のビットの長さが共にｋであり、ここに、ｋは任意の正の整数であり、
前記第２の直列形の加算器（３１）は、実質的にｋクロック・サイクルの遅延をもって前記第１の直列形の加算器（３０）の出力を受け取ると共に、前記第２の多重化された直列／並列形の乗算デバイス（２０）の前記第２の段階の出力を受け取り、前記第１の直列形の加算器（３０）の前記出力と前記第２の多重化された直列／並列形の乗算デバイス（２０）の前記第２の段階の出力とを加算し、これによって、ｋビット長の最下位のビットが０であるような第２の加算器出力を発生させ、前記第１のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０）または前記第２のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１１）の中から選択された一つのレジスタに対する入力として、前記第２の加算器出力を当該レジスタに供給するように動作し、
前記超小形電子系装置は、さらに、
前記第１の直列形の加算器（３０）と前記第２の直列形の加算器（３１）との中間に配設され、実質的にｋクロック・サイクルの遅延を付与するように動作するｋビットのディレイ素子（３４）とを備えることを特徴とする超小形電子系装置。
【請求項２】
前記第１の多重化された直列／並列形の乗算デバイス（１９）が、前記被乗数の現在の部分を受け取る第１の入力ラッチ（２１）を有する請求項１記載の装置。
【請求項３】
前記第２の多重化された直列／並列形の乗算デバイス（２０）が、前記スイッチング素子（２３）の出力を受け取る第２の入力ラッチ（２２）を有する請求項１または２記載の装置。
【請求項４】
前記超小形電子系装置が、前記第１および第２の多重化された直列／並列形の乗算デバイス（１９、２０）以外の乗算デバイスを使用しない請求項１から３のいずれか一項に記載の装置。
【請求項５】
前記スイッチング素子（２３）が、前記第１の段階にて、前記第２の多重化された直列／並列形の乗算デバイス（２０）に対し前記モントゴメリ定数レジスタ（１７）の内容を供給するように動作し、前記第２の段階にて、前記第２の多重化された直列／並列形の乗算デバイス（２０）に対し該第２の多重化された直列／並列形の乗算デバイス（２０）の前記第１の段階の出力を供給するように動作する２対１形のマルチプレクサのアレイを備える請求項１から４のいずれか一項に記載の装置。
【請求項６】
前記超小形電子系装置が、さらに、前記第１の段階にて、前記第２の多重化された直列／並列形の乗算デバイス（２０）の出力を直列形式で受け取り、前記第２の段階にて、前記マルチプレクサのアレイを介して、前記第２の多重化された直列／並列形の乗算デバイス（２０）に対し前記出力を並列形式で供給する直列／並列形のレジスタ（１８）を備える請求項５記載の装置。
【請求項７】
前記マルチプレクサのアレイが、ｋ個の２対１形のマルチプレクサを有しており、前記直列／並列形のレジスタ（１８）のビットの長さがｋである請求項６記載の装置。
【請求項８】
前記第２の減算器（２７）が、前記第１のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０）の内容を受け取って当該レジスタ（１０）の内容から前記モジュロを減算し、これによって、前記モジュロにより減じられた乗数を算出し、前記第２の加算器出力が前記モジュロより大きいかもしくは該モジュロに等しいときに、該モジュロにより減じられた乗数を、前記第１の多重化された直列／並列形の乗算デバイス（１９）に供給する請求項１記載の装置。
【請求項９】
前記超小形電子系装置が、さらに、前記第２の加算器出力が前記モジュロより大きいかもしくは該モジュロに等しいかを決定するコンパレータを備え、
該コンパレータは、前記第２のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１１）の内容からの前記モジュロの減算を制御することができるように、前記第１の減算器（２８）に結合されている請求項８記載の装置。
【請求項１０】
前記超小形電子系装置が、さらに、前記第２の直列形の加算器（３１）の出力が前記モジュロより大きいかもしくは該モジュロに等しいかを決定するコンパレータを備え、
該コンパレータは、前記第１のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０）の内容からの前記モジュロの減算を制御することができるように、前記第２の減算器（２７）に結合されている請求項９記載の装置。
【請求項１１】
前記第１の減算器（２８）が、前記第２のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１１）の内容を受け取って当該レジスタ（１１）の内容から前記モジュロを減算し、これによって、前記モジュロにより減じられた乗数を算出し、前記第１の直列形の加算器（３０）の出力が前記モジュロより大きいかもしくは該モジュロに等しいときに、該モジュロにより減じられた当該レジスタ（１１）の出力を、前記第２の多重化された直列／並列形の乗算デバイス（２０）に供給する請求項１記載の装置。
【請求項１２】
前記第２の直列形の加算器（３１）が、直列形の加算器を有する請求項１記載の装置。
【請求項１３】
前記第１の段階の期間が実質的にｋクロック・サイクルである請求項１記載の装置。
【請求項１４】
前記第１の直列形の加算器（３０）が、前記第１の多重化された直列／並列形の乗算デバイス（１９）の前記出力に対して作用すると共に、前記モジュロにより減じられた前記第２のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１１）の内容に対して作用する請求項１記載の装置。
【請求項１５】
前記第１、第２および第３のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０、１１および１２）が細分化される請求項１記載の装置。
【請求項１６】
前記第２の段階の出力が、直列形の出力を有する請求項１記載の装置。
【請求項１７】
モジュラ・２乗、および、乗数と被乗数とのモジュラ・乗算を遂行するために、べき乗の機能を有する超小形電子系装置を使用する方法であって、
細分化された第１のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０）、細分化された第２のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１１）、および、細分化された第３のメインシフト形およびクロック式の直列／並列形のレジスタ（１２）の中に、前記乗数、部分的な結果およびモジュロをそれぞれ格納するステップと、
予め定められたモントゴメリ定数をモントゴメリ定数レジスタ（１７）に格納するステップと、
前記被乗数の複数の部分の各々について、前記第１のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０）から前記乗数を受け取ると共に、被乗数レジスタ（１６）から前記被乗数の現在の部分を受け取り、前記被乗数の現在の部分に対し前記乗数を乗算し、乗算により得られる積を含む出力を発生させるステップと、
第１の減算器（２８）において、前記第２のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１１）の内容から前記モジュロを減算し、当該レジスタ（１１）の内容に対してより限定された意味における合同の関係にある出力を生成するステップとを有し、
ここで、前記被乗数の複数の部分が、前記第１の多重化された直列／並列形の乗算デバイス（１９）により処理された後は、前記部分的な結果が、前記乗数と前記被乗数との前記モジュラ・乗算を遂行した結果に関してより限定された意味における合同を形成し、
前記方法は、さらに、
第１の直列形の加算器（３０）により、前記第１の多重化された直列／並列形の乗算デバイス（１９）の前記出力と前記第１の減算器（２８）の前記出力とを加算し、一つの出力を生成するステップと、
第２の多重化された直列／並列形の乗算デバイス（２０）において、第１の段階にて、前記第１の直列形の加算器（３０）の前記出力と前記モントゴメリ定数（１７）の内容とを受け取り、第２の段階にて、前記第３のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１２）から前記モジュロを受け取ると共に、前記第２の多重化された直列／並列形の乗算デバイス（２０）の前記第１の段階で得られる出力を受け取るステップであって、前記第１の段階にて、前記モントゴメリ定数レジスタ（１７）の内容と前記第１の直列形の加算器（３０）の前記出力の一部とを乗算し、これによって、前記第２の多重化された直列／並列形の乗算デバイス（２０）の前記第１の段階の出力を生成し、前記第２の段階にて、前記第１の段階の積と前記モジュロとを乗算し、これによって、前記第２の多重化された直列／並列形の乗算デバイス（２０）の前記第２の段階の出力を生成するステップと、
前記第２の直列形の加算器（３１）において、前記第２の段階の出力を前記第１の直列形の加算器（３０）の出力に結合させ、これによって、前記部分的な結果を生成するステップと、
第２の減算器（２７）において、前記第１および第２のメインシフト形およびクロック式の直列入力／直列出力形のレジスタ（１０）の内容から前記モジュロを減算し、当該レジスタ（１０）の内容に関して限定された意味における合同を生成するステップと、
前記第１の減算器（２８）および前記第２の減算器（２７）を活性化するように動作するボロー検出デバイス（３５）を活性化するステップと、
少なくとも前記第２の多重化された直列／並列形の乗算デバイス（２０）に対し、前記第１の段階における入力および前記第２の段階における入力をそれぞれ提供し、ここで、前記第１の段階における入力は、前記第２の段階の入力とは異なっているステップと、
複数のディレイ素子（３２、３３および３４）により、少なくとも前記第１の段階および前記第２の段階を同期化するステップと、
モジュラ・乗算動作およびモジュラ・２乗動作の少なくとも一方を遂行するために、前記超小形電子系装置を使用するステップとを有することを特徴とする、べき乗の機能を有する超小形電子系装置を使用する方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、複数種の素数および複合形素数モジュールからなるガロアの領域において、大きな数に対しモジュラ処理を遂行するための手法に関する。
さらに詳しくいえば、本発明は、大きな数に対するモジュラ・乗算およびモジュラ・べき乗を遂行するための超小形電子系装置ならびにその遂行方法について言及するものである。このようなモジュラ・乗算およびモジュラ・べき乗は、公開キー暗号の認証や暗号化プロトコル（Protocol）に不可欠な演算を遂行する場合に適している。この種の演算は、小規模のマイクロプロセッサによっては通常の処理時間内に実行することが不可能である。
【０００２】
【従来の技術、および、発明が解決しようとする課題】
本発明は、インタリービング方式によるモントゴメリ（Montgomery）の多倍精度の乗算方法」として知られている手続きを、ハードウェアによって遂行することに関係する。このモントゴメリの乗算方法は、暗号化のソフトウェア指向システムに度々使用される。ここでは、モジュラ・べき乗を促進するために、唯一のオリジナルな方法が提供される。さらに、このモジュラ・べき乗を遂行するためのアーキテクチュアを簡単化し、かつ、通常使用されるような数の領域内でモジュラ・べき乗を遂行する装置の適用範囲を拡大するために、欠くことのできないプルーフが使用される。
【０００３】
上記の手続きに関する基本的な処理は、モントゴメリの方法論に基づきモジュラ・乗算を遂行するための手法に関連するような３つの公知の方法のいずれか一つにより実行される。これらの公知の方法の１つめは、Ｐ．Ｌ．モントゴメリ著の「試行除算を行わない方式のモジュラ・乗算（Modular Multiplication without trial division ）」｛計算の数学（Mathematics of Computation）、第４４巻、５１９〜５２１頁、１９８５年発行｝に記載されている。なお、これ以降は、上記の１つめの方法は、単にモントゴメリの方法とよぶこととする。公知の方法の２つめは、Ｓ．Ｒ．デュッセ（Dusse ）およびＢ．Ｓ．カリスキー  ジュニア（Kaliski Jr. ）著の「モトローラ社製のＤＳＰ５６０００に向けられた暗号のライブラリ（A Cryptographic Library for the Motorola DSP 56000）」｛９０年代の欧州暗号化の議事録（Proc. Eurocrypt ‘90 ）、１９９０年にベルリンのシュプリンガ出版社（Springer-Verlag ）により発行｝に記載されている。なお、これ以降は、上記の２つめの方法は、単にデュッセの方法とよぶこととする。
【０００４】
上記の手続きをハードウェアにより遂行する場合、機密保護機構や、オンザフライ（On the Fly）式の加算、減算、および、けた移動が付加される。さらに、総合的な出力が不適切であるような処理が除去される。さらにまた、シリコンを利用した設計に基づき、比較的容易に遂行できるような手段が開発されて集積化される。この集積化により実現された装置は、実際には、８ビット、１６ビットまたは３２ビットの中央処理装置（ＣＰＵ）の従装置として、内部のデータ／アドレスバスに付加される。
【０００５】
本発明に関係する乗算／２乗機器は、簡単な同期形のけた送り式の設計がなされているために、これまでに達成された速度の何倍ものクロック速度で動作することが可能である。このクロック速度は、ボード上に実装されかつ不揮発性の記憶装置（メモリ）を支援するＣＰＵにより実現される。乗算／２乗機器を用いた手法は、ＣＰＵのメモリのアーキテクチュアにおける設計変更を必要としない。この種のアーキテクチュアは、例えばフィリップ回路のように、並列形の乗算器とデュアルポートのメモリを用いることによって大きな数に対する高速のモジュラ・乗算を遂行する場合に規定されるものである。このモジュラ・乗算を遂行するための複数の手法の３つめは、フィリップ社製の電子部品「８３Ｃ８５２（条件付きのアクセス・アプリケーション用の機密保持機能付きの８ビット・マイクロコントローラ）」｛１９９０年８月にアインホーヘン（Einhoven）にて発表｝により実行される方法である。なお、これ以降は、上記の３つめの方法は、単にフィリップの方法とよぶこととする。
【０００６】
上記のような基本的なアーキテクチュアは、任意のマイクロコントローラの設計に際し集積化が可能であり、かつ、メモリへのマッピングが可能であるような機器に適用される。さらに、この種の機器はまた、コマンドおよびオペランドを常時ロードし、かつ、最終的な応答結果を取り出して転送することが必要なマイクロコントローラと並列に動作することも可能でなければならない。
【０００７】
このような要求に対する新奇な解は、２つの直列／並列式の乗算器のみを用いると共に、完全な直列形のパイプライン方式のアプローチを採用することである。このようなパイプライン方式のアプローチを採用することにより、シリコンの面積を節減することが可能になる。現在一般に用いられている周知の技術によれば、メモリ付きのマイクロコントローラを有すると共に上記の解を完全に満足するような装置を、４×４．５×０．２の大きさの電子系回路上に集積化することが可能である。このようにして得られる電子系回路は、ＩＳＯ７８１６の規格を満足するものである。ここで、ＩＳＯとは、国際標準化機構（International Organization for Standardization）の略号であり、認証カード、すなわち、集積回路カード（ＩＣカード）において特定される。上記ＩＳＯの中のＩＳＯ７８１６は、下記の３つの部分から構成される。
【０００８】
▲１▼第１部…ＩＳＯ７８１６−１（物理特性）、１９８７年制定
▲２▼第２部…ＩＳＯ７８１６−２（接点の位置の寸法）、１９８８年制定
▲３▼第３部…ＩＳＯ／ＩＥＣ７８１６−３（電子信号および通信プロトコル）、１９８９年制定
なお、これ以降は、これらの３つの部分を併せてＩＳＯ７８１６とよぶこととする。
【０００９】
本発明は、モントゴメリにより開示された数学的な革新事項に基づいて上記の新奇な解のアーキテクチュアを実現することに向けられている。本発明では、後述するように、モジュラ・べき乗の遂行に要求される時間を、公知の処理方法およびモントゴメリの方法を用いた場合に必要な処理時間の半分の時間とほとんど変わらない値にまで減らすために、幾つかの変形や、改良や、機能的な方法が提供される。
【００１０】
ここで、本発明のモジュラ・乗算およびモジュラ・べき乗を遂行する装置および方法を述べる前に、一般的な計算の数学について大まかに説明することとする。
数学上の定義、一般的な法則および処理方法
素数および複合形基本モジュールからなる数の領域において、我々は、ＡおよびＢを、それぞれ被乗数および乗数として定義する。さらに、通常は、ＡまたはＢよりも大きい数としてＮを定義する。ただし、場合によっては、Ｎは、Ａよりも小さい数になり得る。さらに、Ａ、ＢおよびＮの各々を、ｍ×ｋ（積の記号は、×の代わりに、・または＊で表すこともある）＝ｎビット長のオペランドとして定義する。各ｋビットのグループは、キャラクタとよばれる。それゆえに、Ａ、ＢおよびＮの各々は、ｍキャラクタ長のオペランドから構成される。ここでは、モジュラ・乗算およびモジュラ・べき乗の最初の遂行過程の理解と、１ステップ毎にモジュラ・乗算およびモジュラ・べき乗を遂行する手続の説明を容易にするために、我々は、Ａ、ＢおよびＮの各々を、５１２ビット長（ｎ＝５１２）のオペランドとして定義する。さらに、ｋを３２ビット長に設定する。この３２ビットは、現在、乗算器のコストに見合ったｋの長さとみなせる。さらに、ｍ＝１６としてｍの値を設定する。このｍの値１６は、一つのオペランドにおけるキャラクタの数であり、かつ、５１２ビットのオペランドに対する２乗ループまたは乗算ループの繰り返しの回数である。この場合、明らかに、いずれのオペランドも整数である。
【００１１】
さらに、我々は、モジュールの数の合同を表すために、記号“≡”を使用する。例えば、１６≡２ｍｏｄ７と記載されている場合、１６が２モジュロ７と合同であり、かつ、１６を７で割ったときの剰余が２であることを意味する。また、ＹｍｏｄＮ≡ＸｍｏｄＮと記載されている場合、ＸおよびＹの両方が、Ｎよりも大きい可能性がある。さらに、ＸおよびＹが正であるときは、それぞれの剰余は同一の値になるであろう。さらに、Ｙが負の整数である場合に、Ｙの合同はＹ＋ｕＮで表されることに注意すべきである。この場合、Ｙの合同がＮよりも小さい値であるならば、ｕは、Ｙの合同を正の値にするための最小の数として設定されるであろう。
【００１２】
さらに、我々は、より限定された意味における合同を表すために、記号“￥”を使用する。ここで述べる処理過程においては、各種の値は、度々、望ましい値か、または、望ましい値とモジュールとの和になる。例えば、Ｘ￥２ｍｏｄ７と記載されている場合、Ｘは、２または９のいずれかに等しい。このときに、Ｘは、２ｍｏｄ７に対し限定された合同を有するものとして定義される。
【００１３】
さらに、Ｘ＝ＡｍｏｄＮと記載されて場合、我々は、ＡをＮで割った場合の剰余としてＸを定義する。例えば、３＝４５ｍｏｄ６のように表される。
数の理論においては、モジュラ・逆数が基本的な概念になる。例えば、Ｘのモジュラ逆数は、Ｘ-1と表される。この場合、モジュラ逆数Ｘ-1は、ＸＸ-1ｍｏｄＮ＝１の関係式により定義される。もし、Ｘの値が３に等しく（Ｘ＝３）、かつ、Ｎの値が１３に等しければ（Ｎ＝１３）、Ｘ-1の値は９になる（Ｘ-1＝９）。すなわち、積３・９を１３により割った値は１になる。
【００１４】
この場合、参照すべきビット、キャラクタおよび全オペランドの値の最上位または最下位を表示するために、頭字語ＭＳおよびＬＳがそれぞれ使用されることがある。
本明細書中で、Ｎは、値Ｎ、および、この値Ｎを含むシフトレジスタの名前の両方を意味している。ＡおよびＮは、べき乗処理の全過程を通して一定の値である。さらに、Ａは、べき乗処理がなされるべき数の値である。べき乗処理の最初の繰り返し動作においては、ＢはＡに等しい。Ａはまた、累算された値が存在するレジスタの名前でもある。この場合、累算された値は、最終的に、べき乗処理の望ましい結果に等しくなる。Ｓは、一時的な値を示すと共に、値Ｓに対し限定された合同（￥）の関係を有する値が記憶されるようなレジスタを示す。Ｓ（ｉ−１）は、ｉ回目の繰り返し動作の始まりにおけるＳの値を意味する。Ｓ0 は、Ｓ（ｉ）の値の最下位（ＬＳ）のキャラクタを示す。
【００１５】
ここで、我々は、ρ領域（この“ρ”はベクトルで表示すべきものであるが、電子出願の形式では、ρをベクトルにて表示することができないので、やむを得ず通常のギリシャ文字で表示することとする）における乗算ρ（Ａ・Ｂ）Ｎの処理過程を簡単に説明する。なお、乗算ρ（Ａ・Ｂ）Ｎの詳しい定義は、後ほど行うこととする。
【００１６】
このρ（Ａ・Ｂ）Ｎ以外の記号は、算術計算の中で通常使用されるものである。
モントゴメリ方式のモジュラ・乗算
モジュラ・乗算Ａ・ＢｍｏｄＮを遂行するための古典的なアプローチにおいては、積Ａ・Ｂの剰余は、除算処理を利用することにより計算される。しかしながら、このような除算動作を実行することは、乗算動作を実行することよりも難しい。
【００１７】
モントゴメリのモジュラ・縮小法を用いることにより、上記の除算処理は、実質的に、前もって計算された定数を使用した乗算処理に置き換えられる。
モントゴメリの関数ρ（Ａ・Ｂ）Ｎは、ρ領域内で積Ａ・Ｂの乗算モジュロＮを遂行する。ρ領域から通常のモジュールの領域への検索処理は、ρ（Ａ・Ｂ）Ｎの結果と前もって計算された定数Ｈをもとにρを規定することにより遂行される。ここで、Ｐがρ（Ａ・Ｂ）Ｎと合同である場合（Ｐ≡ρ（Ａ・Ｂ）Ｎ）、ρ（Ａ・Ｂ）ＮはＡ・ＢｍｏｄＮに等しくなる（ρ（Ａ・Ｂ）Ｎ＝Ａ・ＢｍｏｄＮ）。それゆえに、ρ領域での２つの乗算処理によって通常のモジュラ・乗算がなされることになる。
【００１８】
効果的なモジュラ・縮小法を使用する意図は、ｎビット長および２ｎビット長のオペランドに対する一連の乗算および除算動作を回避することにある。このような乗算動作および除算動作の回避は、元の値がｎビット長であってかつ最高値がｎビット長の最終結果を生成するようなオペランドに対し一連の乗算、加算および減算を実行することにより実現される。上記のようなモントゴメリの指針を証明するために、我々は、所定のＡ、Ｂ、および奇数のＮ（この奇数のモジュールは、常に、単純な大きな素数かまたは複合形の大きな素数のいずれかである）に対し、次のようなＱが最終的に存在することに注意すべきである。すなわち、Ａ・Ｂ＋Ｑ・Ｎが、最下位のｎビットの値が０になるような数になるという条件を満足するＱが存在することである。さらに詳しくは、このような条件を下記の式(1) に示す。
【００１９】
【数１】
0003636740.tif 000002
【００２０】
この式(1) は、最下位のｎビットの値が０になるような２ｎビット長の表現が可能であることを意味する。
ここで、Ｉ・２n がＩｍｏｄＮと合同である（Ｉ・２n ≡ＩｍｏｄＮ）と仮定する。この場合、Ｉはすべての奇数のＮに対して存在する。前述の式(１)の両辺にＩを掛けることにより、式(1) の左辺では、下記の式(2) に示すような合同の関係が導き出される。
【００２１】
【数２】
0003636740.tif 000003
【００２２】
また一方で、式(１)の左辺では、下記の式(3) に示すような合同の関係が導き出される。
【００２３】
【数３】
0003636740.tif 000004
【００２４】
この結果、前述の式(2) および式(3) より下記の式(４)が導き出される。
【００２５】
【数４】
0003636740.tif 000005
【００２６】
残念なことではあるが、この式(4) より、ρ領域の乗算が実行される度に寄生因子（寄生関数）Ｉが導入されることがわかる。
ここで、ρ演算子を下記の式(5) のように定義する。
【００２７】
【数５】
0003636740.tif 000006
【００２８】
さらに、式(5) のＰを、“ρ領域におけるＡとＢとの乗算”とよぶこととする。ρ領域からの検索処理は、下記の式(6) に示すように、Ｐ・Ｈに対しρを演算することにより遂行される。
【００２９】
【数６】
0003636740.tif 000007
【００３０】
この式(6) のような合同の関係におけるＰを式(4) のＰで置き換えることにより、Ｈの値が導き出される。この経過を下記の式(7) に示す。
【００３１】
【数７】
0003636740.tif 000008
【００３２】
ここで、Ｈが、Ｉ2 の逆数と合同である場合、式(7) は有効となり、下記の式(8) が成立する。
【００３３】
【数８】
0003636740.tif 000009
【００３４】
Ａ・Ｂに対しρ演算子を規定するために、前もって計算された定数Ｊを用いて下記のステップ１）からステップ５）までの処理を遂行することとする。この場合、最終的に、ステップ５）において、下記の式(9) が成立する。
【００３５】
【数９】
0003636740.tif 000010
【００３６】
これらの処理に続き、下記の式(10)が導き出される。
【００３７】
【数１０】
0003636740.tif 000011
【００３８】
さらに、下記の式(11)が導き出される。
【００３９】
【数１１】
0003636740.tif 000012
【００４０】
ここで、Ｚが２n （Ｚの最下位のｎビットが０でなければならない）により割り切れるためには、下記の式(12)に示す合同が存在することが必要である。
【００４１】
【数１２】
0003636740.tif 000013
【００４２】
さらに、この式(12)のような合同が存在するためには、Ｎ・Ｊｍｏｄ２n が−１と合同であることが必要である。すなわち、下記の式(13)が成立しなければならない。
【００４３】
【数１３】
0003636740.tif 000014
【００４４】
この式(13)により、定数Ｊが求まる。
ここで、ＪはＮのみの関数なので、前もって計算された定数となる。さらに、明らかなことではあるが、我々は、Ｎよりも小さい正の値のＪを選定しなければならない。
これまでの説明より当業者にとっては明らかなように、上記の処理過程において、所定のＡ、Ｂ、Ｎ、および、前もって計算された定数に対し、３つの乗算処理と、１つの加算処理と、最高の減算処理とを遂行することによってρ（Ａ・Ｂ）Ｎが得られる。さらに、このようにして得られた結果と、同じような処理過程と、前もって計算された定数Ｈ（モジュールＮの関数）とを用いることにより、Ａ・ＢｍｏｄＮが求められる。この場合、ＡはＢに等しくなるので、モジュラ・算術計算により２乗または乗算を行うための装置に対し、このような演算子を使用することが可能になる。
【００４５】
インタリービング方式によるモントゴメリのモジュラ・乗算
前述のセクションにおいては、すべてｎビット長の複数のオペランド、および、２ｎ＋１ビットの記憶領域が要求される複数の計算結果に対して乗算を必要とするようなモジュラ・乗算の方法を述べてきた。
ここで、さらに、モントゴメリのインタリービング方式による縮小法（既に記載済みのデュッセの論文に記述されている）を利用することにより、より短いオペランド、レジスタ、およびハードウェア乗算器を用いた乗算動作を実行することができる。この結果として、論理ゲートの数が比較的少ない電子装置による処理が可能になる。
【００４６】
さらに、ｋビットの乗算器を用いることにより、ｋビット長のキャラクタを定義することが容易に行える。この場合、ｎビット中にｍ個のキャラクタが存在する（ｍ・ｋ＝ｎ）。
Ｊの最下位の文字としてＪO を定義することにより、下記の式(14)が導き出される。
【００４７】
【数１４】
0003636740.tif 000015
【００４８】
ここで、前述のモントゴメリのインタリービング方式による縮小法を用い下記のステップ１）〜ステップ５）を遂行することによって、次のような初期条件の下でｍ回の繰り返し動作の後にρ（Ａ・Ｂ）Ｎが規定される。本発明の回路は、これらの複数のステップを並列方式により実行する。
初期条件：Ｓ（０）＝０（最初（１回目）の繰り返し動作の始まりにおけるＳに対し限定された合同の関係を有する値）
【００４９】
【数１５】
0003636740.tif 000016
【００５０】
ここで、ステップ５）の除算処理は、Ｚ中の最下位のｋビットが常に０である場合の右方向へのｋビットのけた移動（シフト動作）に相当する。または、除算処理回路に見られるように、Ｚ中の最下位のｋビットが単純に無視される。上記のように、最後の繰り返し動作の後に、式(15)が得られる。あるいは、必要に応じて、Ｎを引いた後に式(15)が得られる。Ｆ＝Ａ・ＢｍｏｄＮを導き出すために、我々は、ρ領域におけるρ（Ｃ・Ｈ）Ｎの計算を実行しなければならない。
【００５１】
ここで、我々は、すべてのＳ（ｉ）に対し、Ｓ（ｉ）の値が２Ｎよりも小さいことを証明する（モントゴメリの証明には含まれていない）。
ここでの処理過程に使用されるオペランドに対し、下記の式(16)のような３つの不等式が成立することに注意すべきである。
【００５２】
【数１６】
0003636740.tif 000017
【００５３】
（これらの不等式中の最初の２つは、Ｓ（ｉ−１）およびＢがＮに等しいかまたは大きい場合に、繰り返し動作の始まりにおいて、これらのＳ（ｉ−１）およびＢからＮを引いたときに成立する。さらに、２k が、最上位（ＭＳ）のビットが１であるようなｋ＋１ビット長の数であり、かつ、Ａi-1 がｋビット長のオペランドである場合に、３つめの不等式が成立する。）
定義により、上記の式(17)が成立する。
【００５４】
【数１７】
0003636740.tif 000018
【００５５】
前述の一揃いの式において置換を行うことにより、下記の式(18)が成立する。
【００５６】
【数１８】
0003636740.tif 000019
【００５７】
ここで、式(18)における各要素の最高値を取り入れることにより、下記の式(19)のようなＺに関する不等式が成立する。
【００５８】
【数１９】
0003636740.tif 000020
【００５９】
この不等式より、下記の式(20)が確実に成立する。
【００６０】
【数２０】
0003636740.tif 000021
【００６１】
ここで、式(20)の不等式の両辺を２K で割ることにより、式(21)が得られる。
【００６２】
【数２１】
0003636740.tif 000022
【００６３】
この式(21)の不等式より、いかなる場合にも、Ｓ（ｉ）またはＢを調整するためには、Ｎを１回だけ減算すればよいことが証明された。
例１
インタリービング方式によるモジュラ・乗算
１６進法のモードの手動形計算機を使用することにより、インタリービング方式によるモジュラ・乗算を利用した計算の有効性が容易に証明される。まず初めに、１６進法のフォーマットを用いて次のように数を設定する。
【００６４】
Ｎ＝ａ５９（モジュロ）、Ａ＝９９ｂ（乗数）、Ｂ＝５ｃ３（被乗数）、ｎ＝１２（Ｎのビット長）、ｋ＝４（乗数のビットの大きさであり、キャラクタの大きさでもある）、および、ｍ＝３（ｎ＝ｋ・ｍ）
さらに、Ｊ0 ＝７（７・９≡−１ｍｏｄ１６）、および、Ｈ≡２2x12ｍｏｄａ５９≡４４ｂが設定される。
【００６５】
ここで要求される結果は、Ｆ≡Ａ・ＢｍｏｄＮ≡９９ｂ・５ｃ３ｍｏｄａ５９≡３７５８１１ｍｏｄａ５９＝２２０16である。
インタリービング方式によるモジュラ・乗算を利用した計算の処理過程を下記に示す。
初期条件：Ｓ（０）＝０
【００６６】
【数２２】
0003636740.tif 000023
【００６７】
【数２３】
0003636740.tif 000024
【００６８】
最終的に得られた値は、９９ｂ・５ｃ３ｍｏｄａ５９であり、前述の要求される結果に一致する。
上記の乗算動作の有効性は、各ステップにおいて最下位の０のｋビットを無視する場合には、基本的に、上位のｎビットに対し２k を掛けることになることを我々が認識したときに、直観的に理解することができる。さらに、各ステップにおいて、乗数のｉ番目の部分は、２ikにより乗算される数である。このような乗算処理により、上記の部分は、Ｓ（ｉ）と同じランクになる。
【００６９】
モントゴメリの機器における１つの乗算処理過程内のモジュラ・縮小法
例えば、ＮＩＳＴのディジタル記号の標準化や、中国式の剰余定理を用いたモジュラ・べき乗のような多くの暗号化過程では、第２のモジュロよりも大きい（大抵の場合、２倍よりも大きい）数を減らすことが要求される。これらのモジュラ・縮小法は、インタリービング方式による１つのモジュラ・乗算処理過程において効果的に実行され得る。このモジュラ・乗算処理過程は、本発明に係る機器や、モントゴメリのアルゴリズムへの機能的な拡張を利用している。
【００７０】
前述の幾つかの例では、モジュロの長さであるようなオペランドのｎビットが、Ｎの正確な長さでもあることが暗に示されている。このような関係は、通常のべき乗および乗算に対しては、ひじょうに効果的である。しかしながら、数の大きさの縮小が必要な場合には、第２の定数Ｉ-1＝２n ｍｏｄＮを使用することが有効である。この第２の定数は、所定の数により乗算されるモントゴメリの数値を縮小することが要求される場合、１つの乗算処理の規模を最小のレベルにまで縮小するものである。上記の定数Ｉ-1は、定数Ｈを計算する場合（Ｈパラメータの計算に関するセクションを参照のこと）と同様のメカニズムによって計算される。さらに詳しくいえば、このＩ-1の計算は、除数レジスタの最上位のビットにおいて１のビット値が存在するように、除数のオペランドの最上位の部分にモジュールＮを配置することにより実行される。ここで、けた移動／試行減算の回数は、明らかにｎ÷Ｉ−Ｌでなければならない。ただし、Ｌは、Ｎが関係するビットの数である。この場合、Ｉ-1は、Ｌビット長のオペランドになることに注意すべきである。
【００７１】
上記の前提条件を証明するために、まず初めに、我々は、Ａ・ＢｍｏｄＮ（ρ（Ａ・Ｂ）Ｎ）に対するモントゴメリの乗算処理によってＡ・Ｂ・ＩｍｏｄＮと合同の関係を有するものが生成されることを繰り返し述べる。ＢがＩ-1に等しい（Ｂ＝Ｉ-1）と仮定した場合、下記の式(24)が成立する。
【００７２】
【数２４】
0003636740.tif 000025
【００７３】
例２
インタリービング方式によるモントゴメリの縮小法
ｔがモジュロｑに縮小され得ること（ｔ  ｍｏｄｑ）を証明するために、乗数レジスタの長さが、ｑの長さよりも大きくなるように設定する。ここで、最初に記憶されるｔは、２４ビットの長さを有する。
【００７４】
さらに、ワードの長さ（機器の乗数の大きさ）が８ビットであるとし、かつ、次のような変数を仮定する。
ｎ＝２４、ｋ＝８、ｔ＝０ａｆ５９ｂ、ｑ＝２ｂ１３、および、
Ｒ＝Ｉ-1＝２24ｍｏｄｑ＝１４１ｄ
単純な除算の計算処理を用いて比較を行うことにより、ｔｍｏｄｑが５ｃ８に等しいこと（ｔｍｏｄｑ＝５ｃ８）がわかる。このような処理過程を下記に示す。
【００７５】
この場合、一回のモントゴメリの乗算処理において縮小および検索が遂行されることに注意すべきである。
【００７６】
【数２５】
0003636740.tif 000026
【００７７】
最終的に、前述のように、ｔｍｏｄｑが５ｃ８に等しいことが確認される。
べき乗
ここでは、Ｄ．ヌース（Nuth）著による「コンピュータ・プログラミングの技術（The Art of Computer Programming ）」｛半数学的アルゴリズム（Seminumerical Algorithms）、第２巻、アディソン−ウェスリ（Addison-Wesley）社、読書協会（Reading Mass）、１９８１年発行｝による処理手順の方法をもとに、モジュラ・べき乗を遂行するための２乗および乗算の処理手順を説明する。なお、これ以降は、上記の方法をヌースの方法とよぶこととする。
【００７８】
まず初めに、我々は、前のセクションにおいて定数を予め計算していると仮定する。我々はまた、本発明の装置が、ρ領域内で２乗および乗算の両方を遂行することができると仮定する。このときに、我々は下記の式(26)のような計算を行うこととする。
【００７９】
【数２６】
0003636740.tif 000027
【００８０】
この式(26)の計算処理過程を下記に示す。ここで、Ｅ（ｉ）は、指数Ｅに対し２進法のビット表示を行ったときのｉ番目のビットを示す。このｉ番目のビットは、インデックスが１の最上位のビットで始まり、インデックスがｑの最下位のビットで終わる。
【００８１】
【数２７】
0003636740.tif 000028
【００８２】
各ステップから次のステップに移行する際に、ＢがＮに等しいかまたは大きい場合には、常に、ＢからＮが引かれる。
最後の繰り返し動作の後に、Ｂの値は、ＡE ｍｏｄＮに対し限定された合同の関係を有するようになる（Ｂ￥ＡE ｍｏｄＮ）。
本発明の回路を用いてモジュラ・べき乗を遂行する場合に、より効果的に利用され得るような特許権を有する複数のプロトコルが存在する。ここで、我々は、本発明で述べる方法において、通常のべき乗処理の速度が２倍になるような２つの暗号化プロトコルを挙げることとする。
【００８３】
１つめの暗号化プロトコルは、Ｒ．Ｌ．リベスト（Rivest）他著の「ディジタル記号および公開キ−暗号化システム（A Method for Obtaining Digital Signatures and Public Key Cryptosystems）」｛ＡＣＭ委員会（Comm. of the ACM）、第２１巻、１２０〜１２６頁、１９７８年発行｝に記載されている。なお、これ以降は、上記の１つめのプロトコルを、ＲＳＡの方法とよぶこととする。２つめの暗号化プロトコルは、Ｗ．ディッフィ（Diffie）およびＭ．Ｅ．ヘルマン（Hellman ）著の「暗号手法に関する新しい指針（New Directions in Cryptography）」｛情報理論のＩＥＥＥ議事録（IEEE Trans. on Inform. Theory ）、ＶＯＬ．ＩＴ−２２、６４４〜６５４頁、１９７６年発行｝に記載されている。なお、これ以降は、上記の２つめのプロトコルを、ディッフィ−ヘルマンの方法とよぶこととする。これらの２つの方法においては、一定の指数を用いて大部分の難しいべき乗が遂行される。
【００８４】
次のセクションで述べる方法（ρ領域からの検索のために効果的な方法）は、一定の指数を使用することによって計算処理に必要な計算時間を減らすことに言及する。この方法が用いられた場合、前述のステップｂ）′のべき乗処理過程（すべてのρ（Ａ・Ｂ）Ｎの乗算処理）が取り除かれる。さらに、べき乗処理に関するｑ回目の繰り返し動作の後に得られるＢの最終値が、モントゴメリのρ領域において、前もって計算された定数Ｔにより乗算される。
【００８５】
上記の暗号化プロトコルに従事する人々にとっては、中国式の剰余定理（前述のヌースの文献中に記述されている）を用いた回路によってＲＳＡの記号を運用することにより、計算時間が７０％より小さい値にまで節減され得ることは、明らかなことである。
ρ領域からの検索のために効果的な方法
ここでは、前述のセクションのべき乗処理および乗算処理のプロトコルが改善され得る。さらに、繰り返し動作がなされる間に、新たに前もって計算された定数Ｔを取り入れることにより、ρ領域内での乗算の回数を減らすことが可能になる。この場合、Ｔは、モジュロＮおよび指数Ｅの関数である。このような方法を、下記の処理過程に示す。
【００８６】
【数２８】
0003636740.tif 000029
【００８７】
この場合、モジュラ・べき乗は、下記の手順にて遂行される。
【００８８】
【数２９】
0003636740.tif 000030
【００８９】
ここで、各ステップから次のステップに移行する際に、ＢがＮに等しいかまたは大きい場合には、常に、ＢからＮが引かれることを再び仮定する。
さらに、ρ領域内でのすべての乗算は、同じ因子Ｉによるモジュラ・乗算（例えば、ρ（Ｘ・Ｙ）＝Ｘ・Ｙ・ＩｍｏｄＮ）に相当する点に再び注意すべきである。
【００９０】
例３
この例３は、ＡE ｍｏｄＮの計算におけるＴの有用性を証明し、かつ、Ｔの定義を明らかにするためのものである。この例３の処理過程を下記に示す。
【００９１】
【数３０】
0003636740.tif 000031
【００９２】
さらに、下記の処理過程を遂行する。
【００９３】
【数３１】
0003636740.tif 000032
【００９４】
ＡE を計算するために、次のようなステップが続けて実行される場合には、パラメータＴの導入が回避され得る。
ここで、我々は、前もって計算されたモントゴメリの定数が存在すると仮定し、かつ、本発明の装置が、Ｐ領域内で２乗および乗算の両方の処理を遂行すると仮定することにより、下記の計算を実行する。
【００９５】
Ｃ＝ＡE ｍｏｄＮ
この場合、Ｅ（ｊ）は、指数Ｅに対し２進法のビット表示を行ったときのｊ番目のビットを示す。このｊ番目のビットは、インデックスが１の最上位のビットで始まり、インデックスがｑの最下位のビットで終わる。奇数の指数に対しては、次のような処理過程によりべき乗を遂行することができる。
【００９６】
【数３２】
0003636740.tif 000033
【００９７】
各ステップから次のステップに移行する際に、ＢがＮに等しいかまたは大きい場合には、常に、ＢからＮが引かれる。
最後の繰り返し動作の後に、Ｂの値は、ＡE ｍｏｄＮに対し限定された合同の関係（Ｂ￥ＡE ｍｏｄＮ）を有するようになる。そして、最終値としてＣが得られる。
【００９８】
また一方で、偶数の指数に対しては、前述の最後のステップが下記の式(33)によって置き換えられる。
【００９９】
【数３３】
0003636740.tif 000034
【０１００】
さらに、ここでの処理過程をより明確にするために、下記のような具体例を掲載する。
【０１０１】
【数３４】
0003636740.tif 000035
【０１０２】
Ｈパラメータの計算
Ｈパラメータは、モントゴメリの領域内での計算に際し不可欠なものであり、かつ、一定の値である。ある種のプロトコルを用いた場合、Ｈは、比較的大きなコンピュータで予め計算されるような定数になる。あるいは、他のプロトコルを用いた場合、Ｈは、より有効な定数を計算する際に使用される第１段階のパラメータであるような有用性のある定数にもなり得る。この点に関しては、前述のセクションを参照されたい。
【０１０３】
通常の通信においては、Ｈが前もって計算されることを仮定している。しかしながら、幾つかのプロトコル、例えば、ＲＳＡにおけるランダムな通信の際の記号の暗号化に対しては、本発明の装置、例えば、ＳＭＡＲＴカードを使用してＨを計算することも必要である。
Ｈパラメータは、下記の式(35)により計算される。
【０１０４】
【数３５】
0003636740.tif 000036
【０１０５】
この式(35)は、Ｈパラメータが通常の除算動作の剰余であることを意味する。この場合、最上位の１ビットと、これに続く最下位のビット値０の２ｎビット（２ｎ＋１ビット長のオペランド）とから構成されるビット列が、モジュールの基数Ｎにより除算されることになる。
ビット値１の１ビット、および、ビット値０のビット列からなる被除数に対し除数Ｎによる２進法の除算を遂行することは、Ｎによる順次の試行減算を実行することに相当する。すなわち、上記の除算処理は、最上位のｎ＋１ビットがＮよりも大きい場合に、残りの試行過程の被除数からＮを引くことに相当するものである（下記の例を参照のこと）。
【０１０６】
この場合、元の被除数は２ｎ＋１ビット長であるが、除算処理により生成される残りの試行過程の被除数は、明らかに、ｎ＋１ビット長を超えることはない。さらに、最下位のけたが０になることも明らかである。
例えば、次のような例を挙げる。
すなわち、Ｎ＝１１10＝１０１１n （したがって、Ｎのビット長は、４になる、したがって、ｎ＝４）のときに、Ｈを求める例を挙げる。
【０１０７】
除算の基数を２として、長い除算を手動により実行する。
【０１０８】
【数３６】
0003636740.tif 000037
【０１０９】
最終的に、Ｈ＝３10であることが確認された。
上記の除算処理では、ｎ＋１回の試行減算が存在する。さらに、試行減算により得られる被除数もまた、ｎ＋１ビット長になることに注意すべきである。このような減算処理の手順は、後述の本発明のハードウェアの説明箇所で詳しく述べることとする。
【０１１０】
【課題を解決するための手段、および、作用】
本発明は、大きな数に対しモジュラ・乗算およびモジュラ・べき乗を遂行するための超小形電子系装置に係り、適切なクロック手段および制御手段を有する標準のマイクロプロセッサに対するコンパクトな同期式の電子系超小形周辺機器からなる。
【０１１１】
さらに、本発明この超小形電子系装置は、各々が細分化される共に、切替制御可能であり、かつ、前記クロック手段により制御される複数種のシフトレジスタと、多重化され、かつ、直列／並列形の２つのみのマルチプレクサと、ボロー検出器と、補助的な減算器および加算器と、ディレイ・レジスタおよび切替素子とを備えている。
【０１１２】
このような超小形電子系装置は、モジュラ・乗算、モジュラ・２乗およびモジュラ・べき乗を同時処理かつ同期方式により遂行するために、前述のすべての構成部品を集積化して形成する。
好ましくは、本発明の超小形電子系装置は、ハードウェアの乗算、２乗およびべき乗に対し設計されたモントゴメリの方法をもとに展開されるような新奇かつ複合形で同期式のハードウェア装置により実現される。
【０１１３】
さらに、好ましくは、本発明の超小形電子系装置は、モントゴメリの方法を展開することにより、並列動作方式に直列動作方式を取り入れた多数の同時処理と直列処理との複合形、すなわち、乗算、減算、加算、記憶形ディレイおよび２k による除算を遂行する装置として機能する。
さらに、好ましくは、本発明の超小形電子系装置は、モントゴメリの方法を展開することにより、モジュラ・乗算、モジュラ・２乗およびモジュラ・べき乗のための多数の直列処理を遂行し、かつ、膨大な内部バスの使用を回避し得る。
【０１１４】
さらに、好ましくは、本発明の超小形電子系装置は、モントゴメリの方法を展開することにより、モジュラ・乗算、モジュラ・２乗およびモジュラ・べき乗のための多数の直列処理を遂行し、一般の１μｍ技術を用いたＳＭＡＲＴカード用のＩＳＯ７８１６の標準規格により規定されるマイクロチップ上に形成される程度に充分コンパクトである。
【０１１５】
さらに、好ましくは、本発明の超小形電子系装置は、モントゴメリの方法を展開することにより、モジュラ・乗算、モジュラ・２乗およびモジュラ・べき乗のための多数の直列処理を遂行し、基本のアーキテクチュアを変えることなく、特に、デュアルポート・アクセスのためのメモリを再設計することなく、かつ、ファームウェアの要求が少ない状態で、１つの内部バスを備えた任意のマイクロプロセッサにより制御することが可能である。
【０１１６】
さらに、好ましくは、本発明の超小形電子系装置は、マイクロプロセッサを使用してカスケード形のρ領域内での２乗および乗算の処理手順を規定する。
さらに、前記超小形電子系装置は、ｎビット長のシフトレジスタを含み、かつ、モジュラ・乗算、モジュラ・２乗およびモジュラ・べき乗を遂行する多重化部を備えている。この多重化部内に指数Ｅを記憶することが不要であるために、この多重化部による制御を簡単にし、また一方で、ほんのわずかな付加的なマイクロコントローラのＲＯＭコードしか必要としない。
【０１１７】
さらに、好ましくは、本発明の超小形電子系装置は、Ｂのレジスタが回転動作を行っている間に、オンザフライ方式により２乗の被乗数を用いてＡi のレジスタをロードする結果として、前記Ａi のレジスタを前記Ｂのレジスタにより再ロードする際に、マイクロコントローラによりＢおよび／またはＢ−Ｎの前回の計算処理の最終値が取り出されるおそれが回避される。
【０１１８】
このために、このマイクロコントローラのＲＡＭが節減され、かつ、２乗の繰り返し動作の各々において少なくともｎクロック分の実効的なクロック・サイクルを除去することが可能になる。
本発明の構成によれば、Ｚ／２k がＮよりも大きいか、またはＮに等しいかを決定し、たった１回の直列形の減算のみ行うような比較的小さいＮオペランドを達成することにより、モントゴメリの方法による簡単な装置から、２つの記憶用レジスタおよび独立の直列形の減算処理が除去されると共に、Ｚ／２k −Ｎに関する単一の直列形の検出を行うことが可能になる。
【０１１９】
さらに、本発明の構成によれば、３つの同時乗算処理を遂行する際に２つの直列／並列形の乗算器のみが使用されるように、半並列形式で回路の同期をとっている。
このために、シリコンを用いた装置において全シリコン領域に対し直列／並列形の乗算器の占める面積の割合が４０％に抑えられる。
【０１２０】
さらに、本発明の構成によれば、ｋビットのシフトレジスタからなる１つのディジタルのディレイ素子を使用してＸの直列形の加算と乗算器の直列形の乗算結果との同期をとるので、直列／並列形の乗算器の積または繰り返し処理が二重に記憶されることが防止される。
さらに、本発明の好ましい実施態様においては、シフトレジスタが、ｎビット長またはｎ／２ビット長で構成され、ｎ／２の長さのモジュールに対するべき乗が、ｎビット長のべき乗に対し必要であろうと思われる実効的なクロック・サイクル期間の１／８より幾分少ない時間で遂行される。
【０１２１】
さらに、本発明の好ましい実施態様においては、オンザフライ方式によりＡのレジスタをロードし、かつ、オンザフライ方式によりＳのレジスタの内容の大きさを予測し、さらに、オンザフライ方式により一部のオペランドの同期をとることにより、ｎビットの数の乗算処理ρ（Ａ・Ｂ）Ｎが、実効的なｍ（ｎ＋２ｋ）クロック・サイクルで完全に遂行される。
【０１２２】
さらに、本発明の好ましい実施態様においては、小規模のボロー検出回路が付加され、かつ、制御メカニズムに簡単な付加物が付加されているようなモントゴメリの乗算処理に対し使用されるものと同じ機器の同じレジスタを用い、第２のモ−ドにおいてＨパラメータの計算を行うことができる。
本発明のモジュラ・乗算を遂行するための方法においては、被乗数Ａ、乗数ＢおよびモジュロＮの各々が、ｋビット長のｍキャラクタから構成され、乗数ＢはモジュロＮよりも大きくない値に設定される。
【０１２３】
前記の方法は、下記のステップにより実行される。
第１のステップで、Ｈパラメータと、他のパラメータの少なくとも最下位のキャラクタＪ0 とを前もって計算し、かつ、このキャラクタＪ0 をｋビットのレジスタにロードし、
第２のステップで、前記乗数ＢおよびモジュロＮを、それぞれ対応するｎビット長のレジスタにロードし、ここで、ｎ＝ｍ・ｋのように表され、
第３のステップで、ｎビット長のレジスタＳのビット値をすべて０にし、
第４のステップで、ｉ番目の繰り返し動作をｍ回遂行し、ここで、ｉは０からｍ−１までの数であり、さらに、ｉ番目の繰り返し動作の各々は、以下の動作を含み、
（ａ）前記被乗数Ａのｉ番目のキャラクタＡi を、Ａi のレジスタ手段から、レジスタおよびラッチ手段から選定された記憶手段へ転送し、
（ｂ）Ｘ＝Ｓ（ｉ−１）＋Ａ（ｉ−１）＊Ｂにより表されるＸの値を生成し、ここで、Ｓ（ｉ−１）はＳの更新された値であり、Ｓの更新は、次のように定義され、
▲１▼乗算手段に対し、Ｂのレジスタを周期的に右方向へシフトし、
▲２▼直列形式でＢをＡi により乗算し、
▲３▼前記モジュロＮを周期的に右方向へシフトし、
▲４▼Ｓ（ｉ−１）がＮよりも大きくない場合、（ｉ−１）番目の繰り返し動作の後にＳのレジスタに記憶される値をＳ（ｉ−１）の更新された値として決定し、Ｓ（ｉ−１）がＮよりも大きい場合、直列形式でＳ（ｉ−１）からＮを引くことにより得られる値をＳ（ｉ−１）の更新された値として決定し、さらに、この結果として得られるＳ（ｉ−１）の更新された値を設定し、
▲５▼Ｓのレジスタを周期的に右方向へシフトし、さらに、各ビット毎に、乗算Ａ（ｉ−１）＊ＢをＳ（ｉ−１）の更新された値に加算し、
（ｃ）Ｘ（Ｘ0 ）の最下位のキャラクタをＪ0 により乗算し、ＮおよびＸがｋクロック・サイクルだけ遅延されている間に、Ｘ0 ＊Ｊ0 ｍｏｄ２k の値をＹ0 のレジスタ手段に入れ、
（ｄ）Ｚ＝Ｘ＋Ｙ0 ＊ＮのＺの値を計算し、この計算は、次のように行われ、
▲１▼Ｎのレジスタに対し遅延かつ右方向へのシフトがなされた状態でＹ0 をＮにより乗算し、同時に、この乗算結果に対し、前述の周期的な右方向へのシフトがなされ、
▲２▼ＸをＹ0 ＊Ｎの値に加算し、
（ｅ）Ｚの最下位のキャラクタを無視し、残りのキャラクタをＳのレジスタに入れ、このときに、最後の繰り返し動作以外は、Ｚ／２k を入れることになり、
（ｆ）前述と同様の方法によりＳ（ｉ−１）の更新された値を決定するために、各ビット毎にＺ／２k とＮとを比較し、
（ｇ）前記被乗数Ａのｉ番目のキャラクタＡi を、前記の動作期間において、Ａのレジスタ手段にロードし、
第５のステップで、最後（ｍ回目）の繰り返し動作においては、Ｚ／２k の最下位のキャラクタを無視し、残りのキャラクタを、Ｃ￥ρ（Ａ＊Ｂ）ＮとしてＢのレジスタに入れ、
第６のステップで、前記第３および第４のステップを繰り返し、ここで、ＣがＮよりも大きい場合には、ＣまたはＣ−ＮがＢにとって代わり、さらに、ＨがＡにとって代わることによってＰ＝ρ（Ｃ＊Ｈ）Ｎを計算し、
第７のステップで、最後の繰り返し動作により得られるＰの値を、Ａ＊ＢｍｏｄＮと仮定する。
【０１２４】
さらに、本発明の方法によれば、被乗数Ａと乗数Ｂとが同じ数である場合に、モジュラ・２乗およびモジュラ・乗算が遂行される。
さらに、本発明の方法によれば、Ｄ＝ＡE ｍｏｄＮにより表されるモジュラ・乗算およびモジュラ・べき乗が遂行される。
さらに、本発明の方法は、
１．モジュロをレジスタＮに格納する工程、
２．レジスタＳを０に設定する工程、
３．べき乗化されるべきベースＡをレジスタＢに格納する工程、
４．べき指数Ｅをコンピュ−タ−のレジスタに格納する工程、
５．該べき指数Ｅを左にシフトさせる工程、
６．第１番目の１ビットに先行する全ての０ビットを無視すると共に、該べき指数Ｅと下記の工程７および８の操作を実行するためのビットに続く全てに対して、第１番目の１ビットを無視する工程、
７．該ビットのそれぞれについて、０か１かに関係なく、前記のステップで定義された乗算方法により該レジスタＢの内容を２乗すると同時に、該ベースＡの連続する特性値が該レジスタＢからレジスタＡi に格納される工程、
８．もし、べき指数Ｅに関する現在のビットが、１であるか、或いは１にすぎない場合に、前記の工程７の操作終了後該レジスタＢの内容を該ベースＡで乗算する工程、および
９．べき指数Ｅの全てのビットについて、前記の工程６〜８の操作が実行された後に、Ｄ￥ＡE ｍｏｄＮとしての最後の操作についての結果を該レジスタＢに格納する工程とから構成されている。
【０１２５】
さらに、本発明の方法は、
１．モジュロをレジスタＮに格納する工程、
２．レジスタＳを０に設定する工程、
３．べき乗化されるべきベースＡをレジスタＢに格納する工程、
４．べき指数Ｅをコンピュ−タのレジスタに格納すると共に、以下に定義する事前演算パラメータＴをＣＰＵのメモリに格納する工程、
【０１２６】
５．該べき指数Ｅを左にシフトさせる工程、
６．第１番目の１ビットに先行する全ての０ビットを無視すると共に、該べき指数Ｅと下記の工程７および８の操作を実行するためのビットに続く全てに対して、第１番目の１ビットを無視する工程、
７．該ビットのそれぞれについて、０か１かに関係なく、前記のステップで定義された乗算方法に関して前記の工程４および５を実行すると同時に、被乗数と乗数とがベースＡであり、且つ該ベースの連続する特性値が該レジスタＢからレジスタＡi に格納される工程、
８．もし、べき指数Ｅに関する現在のビットが、１であるか、或いは１にすぎない場合に、工程７の操作終了後、前記のステップで定義された乗算方法に関して工程４及び５を実行し、その際、該被乗数がレジスタＢの内容であり、且つ該乗数がベースＡである工程、および
９．べき指数Ｅの全てのビットについて、前記の工程７および８の操作が実行された後に、レジスタＢの内容を前記パラメータで付加的に乗算し、ＴＤ＝ＡE ｍｏｄＮとしての最後の操作についての結果を該レジスタＢに格納する工程とから構成されていることを特徴とし、段落番号〔０１２３〕に記載の方法による繰り返し操作を実行することにより、モジュラ・べき乗Ｄ￥ＡE ｍｏｄＮを実行する工程とを含む。
【０１２７】
さらに、本発明の方法は、
ＣＰＵと乗算回路を含む制御手段から構成されている段落番号〔０１２３〕に記載の方法により、モジュラ・乗算を実行する装置であって、該乗算回路は、乗数としてのｎビットのシフト形のレジスタＢ、モジュロとしてのｎビットのシフト形のレジスタＮ、値Ｓとしてのｎビットのシフト形のレジスタＮ、被乗数としてのｋビットのシフト形のレジスタＡi 、値Ｊ0 およびＹ0 としてのｋビットのレジスタ手段、該レジスタＢの内容と該レジスタＡi の内容とを掛け合わせる乗算器手段、付加的なｎビットの乗算器手段、および、加算手段、減算手段、多重化手段およびディレイ手段を含んでいる。
【０１２８】
さらに、本発明の方法は、
該ｎビットのシフト形のレジスタとその他の構成部分との間の接続、およびラッチ回路以外の構成部分間の接続が、１ビット接続である。
さらに、本発明の方法は、
１．べき指数Ｅをコンピュ−タの記憶手段に格納する工程、
２．モジュロをレジスタＮに格納する工程、
３．レジスタＳを０に設定する工程、
４．Ａ＊＝ρ（ＡＨ）N の乗算操作を実行する工程、
（ここで、Ａは、べき乗化されるべきオペランドであり、Ｈは、事前演算パラメータである）
５．該Ａ＊をレジスタＢに格納する工程、
６．該レジスタＢの内容に対して２乗演算操作を実行する工程、
７．該べき指数Ｅを左にシフトさせる工程、
８．第１番目の１ビットに先行する全ての０ビットを無視すると共に、該べき指数Ｅと下記の工程９および１０の操作を実行するためのビットに続く全てに対して、第１番目の１ビットを無視する工程、
９．該べき指数Ｅに対応するビットのそれぞれについて、０か１かに関係なく、前記の工程１〜８で定義された２乗方法による前記の工程４および５の操作を実行する工程であって、被乗数と乗数とが共に該レジスタＢから派生されるものであり、且つモントゴメリの乗算器における連続する特性値が該レジスタＢからレジスタＡi に格納される工程、
１０．もし、べき指数Ｅに関する現在のビットが、１であるか、或いは１にすぎない場合に、工程９の操作終了後、前記で定義された２乗方法に関して前記の工程４および５を実行し、その際、該被乗数がレジスタＢの内容であり、且つ該乗数がベースＡ＊である工程、および
１１．べき指数Ｅの全てのビットについて、前記の工程８〜１０の操作が実行された後に、レジスタＢの内容をオリジナルの前記ベースＡで付加的に乗算し、Ｄ￥ＡE ｍｏｄＮとしての最後の操作についての結果を該レジスタＢに格納する工程とから構成されている。
【０１２９】
さらに、本発明の方法は、
平均有効長がｎ／２ビットである２つの数値について一般的な乗算を実行する方法であって、該方法は、段落番号〔０１２３〕に記載の方法にて定義されている乗算方法により該数値に対してモジュラ・乗算処理を実行するものであって、前記モジュロＮは全てが１（fffffff......fff) で構成されたｎビット数で、Ｊ0 は１に等しくされており、被乗数をレジスタＢに格納し且つ前記乗算方法に従ってＡを取り扱うものであり、
全てが１になっているプリローディング用のレジスタＮを使用するか、或いは一連のハード１を出力するためにＮの値を出力するマルチプレクサをセットすることにより、Ｎの値が全て１となり得るものである。
【０１３０】
【実施例】
本発明のモジュラ・乗算およびモジュラ・べき乗を遂行する超小形電子系装置ならびにその遂行方法は、添付図面（図１〜図９）を参照しながら、本発明の好ましい実施例を具体的に説明することにより、より良く理解されるであろう。
これらの添付図面は、本発明の装置を全体的に理解するために必要な複数種の論理的概念を示すものである。すべての場合において、クロック信号に従い回路が動作する。そして、リセット信号がある場合には、このリセット信号は、回路を零の状態にすることを目的としている。
【０１３１】
以下、図１〜図９の添付図面を参照しながら、本発明の実施例を詳細に説明する。
図１は、本発明の一実施例の装置構成を示すブロック図である。ここでは、本発明の装置が集積化されたモノリシック回路のブロック図が例示されている。
図１において、多重化部（ＭＵＬＴ部と記載されることもある）は、本発明の基礎となるハードウェア装置を備える。状態マシンは、多重化部の回路を駆動するための制御部を構成する。ＲＯＭ（読み出し専用回路）部は、すべて不揮発性メモリ（ＲＯＭおよびＥＰＲＯＭ）から構成される。このＲＯＭ部には、ＳＭＡＲＴカードを制御するためのプログラム、高信頼性の３つのグループからなる公開キー、および、多重化部や状態マシンを駆動するためのプログラムが格納されている。ＲＡＭ（ランダムアクセス回路）部は、一時的に存在するオペランドを記憶するための揮発性メモリから構成される。この種のオペランドとして、べき乗処理がなされる予定のメッセージ、暗号化されるべき公開キー、多重化部に転送されるべきデータ等が挙げられる。ＣＰＵ（中央処理装置）は、実際は、８ビットまたはそれより大きなビットの内部バスを有するような任意のマイクロコントローラである。
【０１３２】
図２は、本発明の一実施例のモジュラ・乗算回路を示すブロック図である。
この場合、モジュラ・乗算回路は、モジュラ・２乗およびモジュラ・べき乗を実行するために用いられる。
図２において、参照番号１０、１１および１２は、Ｂ、ＳおよびＮのレジスタをそれぞれ構成するようなｎビット長（ｎ＝ｋ・ｍ）の３つのレジスタを示すものである。これらのレジスタの各々には、乗数の値Ｓとモジュロの値がロードされる。上記レジスタは、好ましくは、２つのｎ／２レジスタに分割されている。さらに、上記レジスタは、好ましくは、ＮおよびＢのレジスタに対し、ｋビットの最下位ビット部分を含む。マルチプレクサ１３、１４および１５は、それぞれ、上記レジスタの前部に配置される。この場合、もし、これらのマルチプレクサが細分化されて個々の部品として形成されているならば、各マルチプレクサが、各々のレジスタ前部に配置される。さらに、図２のブロック図に示すように、３つのレジスタは、直列形式でロードされるように意図されている。しかしながら、並列形式によるロードも可能である。
【０１３３】
１６、１７および１８は、いずれもｋビット長であり、かつ、Ａi 、Ｊ0 、およびＹ0 の値をそれぞれ受け入れる３つのレジスタを示すものである。レジスタ１６、１７は、それぞれ、直列ロード／並列出力形のシフトレジスタと、直列および並列ロード／並列出力形シフトレジスタである。レジスタ１８は、好ましくは、直列入力／並列出力形シフトレジスタである。これらのレジスタの内容は、それぞれ、構成要素２１、２２を介して乗算手段１９、２０により処理されるように意図されている。これらの構成要素２１、２２は、好ましくは、ｋビットのラッチである。これらの構成要素２１、２２がラッチである場合、これらの構成要素２１、２２は、ｋビットのバスを通してレジスタ１６、１７および１８からロードされる。また一方で、上記の構成要素２１、２２がレジスタである場合、これらの構成要素２１、２２は、１ビットの接続部を通して直列形式でロードされ得る。
【０１３４】
参照番号２３、２４、２５、２５′、２６、３６、３７および３８は、マルチプレクサを示している。乗算手段（乗算器）１９、２０は、直列入力Ａ、並列入力Ｂ、および直列出力を有する乗算手段か、または、その他の直列／並列入力、および直列出力を有する乗算手段である。マルチプレクサ３８は、通常の数の領域内で乗算処理を実行するために、モジュロＮのビット値を強制的にすべて１（オール１）にするものである。
【０１３５】
参照番号２７、２８、２９、３０および３１は、１ビットの全加算／減算手段または半加算／減算手段を示している。この内、３１は、全加算／減算手段を示している。参照番号３２、３３および３４は、ディジタル信号を遅延させることが可能なｋビットかつｋクロック・サイクルのディレイ手段を示している。これらのディレイ手段は、アナログ素子またはディジタル素子のいずれによっても構成され得るが、アナログ素子により構成するのが好ましい。３５は、ボロー検出器を示している。このボロー検出器は、２ビットのラッチ／記憶手段である。図２からわかるように、本発明の装置は、例えば５１２ビットのような大きい数を取り扱うように意図されているにもかかわらず、わずかな数のｋビットのバスをオプションで持っている以外には、バスを備えていない。このために、本発明の装置では、ハードウェアの節減が図れる。Ｂ、ＳおよびＮのレジスタが、ｎ／２ビットの部分を有する場合、本発明の装置は、２５６ビットの数に対し乗算動作およびべき乗動作を遂行するために使用することが可能である。このために、本発明では、装置を使用する際の柔軟性を備えるという利点が生ずる。
【０１３６】
図３は、本発明の一実施例の特殊なモジュラ・乗算回路を示すブロック図である。ここでは、本発明の一実施例のモジュラ・乗算回路を論理セルにより構成している。図３において、オペランドは、直列の接続部ＤＩを介し、Ａi のラッチと、Ｊ0 のレジスタと、Ｂのレジスタと、Ｎのレジスタとに供給される。そして、オペランドによる処理結果は、直列の接続部ＤＯを介し、ＢのレジスタまたはＮのレジスタから取り出される。
【０１３７】
信号Ｘは、ＢとＡi とＳとの積Ｂ・Ａi ・Ｓのビットの流れを合計した結果（和）に相当する（ＳとＢの積は、Ｎよりも小さいと仮定する）。信号Ｙ0 は、Ｊ0 とＸの積Ｊ0 ・Ｘにおける最下位のｋビットの流れに相当する。信号Ｚは、Ｙ0 とＮの積Ｙ0 ・Ｎと、Ｘとの和に相当する。ここでは、Ｚ中の最下位のｋビットはすべて０なので、この最下位のｋビットは無視される。この結果、最上位のｎビットのみが、ＳまたはＢに対し直列に供給される。
【０１３８】
ボロー検出器は、Ｚ／２k の値がＮより大きいか否かを検出するための論理回路である。
減算器（通常、Ｓｕｂと略記される、図３では、単に減算と記す）１および減算器２は、ＢおよびＳの値がＮよりも大きい場合は、常に、ＢおよびＳのビットの流れからＮのビットの流れを減算するように動作する。
【０１３９】
加算器（通常、Ａｄと略記される、図３では、単に加算と記す）１および加算器２は、Ｘの流れとＺの流れを生成するために、ビットの流れを加算するように動作する。
ディレイ素子（図３では、単にディレイと記す）１およびディレイ素子２は、シフトレジスタから構成される。これらのディレイ素子は、数学的処理の同期をとるための記憶手段を提供するために必要なものである。
【０１４０】
図３では、クロックの制御は図示していない。ここでは、クロックは、状態マシンから供給されると仮定している。このクロックの供給は、前述の直列入力／直列出力形の論理回路の１つからデータを送り出したりこれらの論理回路の１つにデータを提供したりしなければならないときは、いつでも行われる。
他の制御、すなわち、マルチプレクサのアドレス制御や、ラッチ転送信号の制御等もまた、詳しく開示していない。なぜならば、これらの制御は、本明細書に含まれる説明事項より、当業者にとっては明らかであるからである。
【０１４１】
さらに、図２および図３の装置が、どのようにして本発明の乗算の方法に関係する複数の動作を遂行するかは、当業者にとっては明らかであろう。しかしながら、これらの複数の動作のタイミング関係は、念のために、次の図４に示す。
図４は、本発明の一実施例による繰り返し動作（イテレーション）と乗算動作との間の時間的な関係を示す図である。この図においては、本発明の一実施例による実効的かつ連続的なクロック・サイクルにおいて遂行されるようなすべての各種動作が、図式的に示されている。この場合、ｎ＝５１２、および、ｍ＝１６に設定される。このような設定条件は、暗号化技術においては、比較的一般的な条件である。前述の図３に例示された実施例に従って本発明を実施する場合、ｎ＝２５６の条件下で本発明を実行するために、図４と同じ装置が使用される。
【０１４２】
図４においては、一連の各種動作が、実効的なクロック・サイクルの関数として図示されている。この実効的なクロック・サイクル（実効クロック）に関しては、横軸に目盛りがふられている。各種動作の始まり、および、すべての繰り返し動作前のタイミングでは、Ｂ、ＳおよびＮの値が、それぞれ対応するレジスタにロードされる。上記の繰り返し動作は、本発明の乗算の方法の一部をなす。Ａの最初のキャラクタもまた、対応するレジスタにロードされる。ｋクロック・サイクルの期間において繰り返し動作が始まるや否や、ＢおよびＳのレジスタの内容のシフト動作が行われる。ｎ＋ｋの実効的なクロック・サイクルの期間においてＸの値が発生する。最初のｋクロック・サイクルは、Ｘ0 の値を取り入れることにより占有される。最初の実効的なｋクロック・サイクルの期間において、Ｙ0 の値が取り入れられる。次の実効的なｎ＋ｋクロック・サイクルの期間において、乗算器２０に既に取り入れられているＸの値がシフトするか、または、このＸの値がディレイ素子３４により遅延された後に加算器３１に取り入れられる。Ｎの値は、３つの異なる時間位相にて使用される。初めの位相は、ＳおよびＢを更新するために使用される。第２番目の位相は、実効的なｋクロック・サイクルの遅延期間の後に、Ｙ0 による乗算を遂行するために使用される。第２番目の位相は、２回目の実効的なｋクロック・サイクルの遅延期間の後に、ＳまたはＢの次の値がどのようにして更新されるかを検知するために使用される。同様の実効的なｎ＋ｋクロック・サイクルの期間において、Ｚが計算され、かつ、Ｚ／２k が計算される。最初の実効的なｋクロック・サイクルの始まりのタイミングで、Ａi のロードが始まる。さらに、繰り返し動作が連続している間は、Ａi のロードも続けて行われる。Ｚ／２k の最終値は、最初の実効的な２ｋクロック・サイクルの期間後のｎクロック・サイクルの期間において、Ｓ（またはＢ）のレジスタに取り入れられる。
【０１４３】
図５は、直列／並列乗算器のセルの構成を示す回路図である（この回路図の作成に際しては、専門の技術に精通している技術陣の助けを借りているが、彼らは、本発明に関係する直列／並列乗算器のセル構成の研究に関しては関与していない）。これらの複数のセルの各々は、後述の図６に示すような乗算器（通常、ＭＰＬと略記される）を備える。
【０１４４】
図６は、８ビットの直列／並列乗算器の構成を示す回路図である。この直列／並列乗算器は、符号のない直列／並列乗算器の乗算動作に対しブース（Booth ）の乗算アルゴリズムを実行する。図３の乗算器（通常、ＭＬと略記される、図３では、単に乗算と記す）１および乗算器２に示すような直列／並列乗算器は、ｋビット長である。この場合、ＭＳセル、すなわち、最上位ビットのセルが退化していることに注意すべきである。並列の８ビットの被乗数が、ＸＩの接続部に入力される。さらに、ｎビット長の直列の乗数がＹの接続部に入力される（乗数の最上位の１ビットの後に、最初に現れる最下位のｋビットの列はすべて０である）。さらに、乗算器による乗算結果である積は、出力側の接続部ＭＯにおいて、最下位のｋビットが最初に現れ、最上位のビットが最後に現れる。この場合、積の全体は、ｎ＋ｋビット長になる。
【０１４５】
図７は、直列加算器の構成を示す回路図である。ここでは、Ａの接続部とＢの接続部に現れる２つのビットの流れを加算するための直列加算器が例示されている。この直列加算器においては、出力側の接続部Ｓにおいて、ビットの流れの和が出力される。図７においては、最下位のビットが最初に入力される。さらに、ｍビット長のオペランドに対する出力の流れは、ｍ＋１ビット長になる。ｍ回の実効的なクロック・サイクルの最後の部分では、ＣＩの出力は、数のビット列中のｍ＋１番目のビットに相当する。
【０１４６】
図８は、直列減算器の構成を示す回路図である。ここでは、Ａの接続部とＢの接続部に現れる２つのビットの流れの差を出力するための直列減算器が例示されている。この直列減算器においては、出力側の接続部Ｄにおいて、ビットの流れの差が出力される。図７においては、最下位のビットが最初に入力される。さらに、ｍビット長のオペランドに対する出力の流れは、ｍビット長になる。ｍ回の実効的なクロック・サイクルの最後の部分では、ＢＩの出力は、数のビット列中のｍ＋１番目のビットに相当する。同様に、このＢＩの出力は、ボローを表示するためのボロー表示手段として機能する。
【０１４７】
図９は、Ｈパラメータを計算するためのアーキテクチュアを示すブロック図である。ここでは、ｎビット長のモジュール（すなわち、モジュロ）Ｎに対しＨパラメータを計算するためのハードウェア構成が例示されている。このような動作モードの期間では、ｎビット長のモジュールに対し、Ｎのレジスタがｎ＋１回だけ回転動作を遂行する。この回転動作は、Ｓのレジスタの回転動作に同期した状態で行われる。この場合、Ｓのレジスタは、減算器１を介し、最下位のビットの遅延と一緒に回転動作を遂行する｛最下位のビット値０は、最初のクロック・サイクルにおいてマルチプレクサ（Ｍ２  １；１）に挿入される｝。ボロー検出器は、回転動作が完了するような最後のタイミングで、次回の丸めにおいてＳの流れからＮが引かれるか否かを認識する。さらに、ボロー検出器は、次回の丸めに応じて前回の減算マルチプレクサを切り替える。
【０１４８】
前述のように、図１は、本発明の方法を遂行するための装置をブロック図の形で表したものである。図１の装置における制御部は、下記の構成要素を備える。
(1) 完備した形のＣＰＵ（中央処理装置）
(2) カウンタ
(3) 状態マシン
さらに、ＣＰＵは、不揮発性メモリおよび揮発性メモリを有する。これらの不揮発性メモリおよび揮発性メモリの幾つかは、乗算処理過程に使用され得る。さらにまた、上記ＣＰＵは、回路内のモジュールの計算機能ブロックを制御する。
【０１４９】
さらに詳しくいえば、上記ＣＰＵは、下記の機能を有する。
(1) ホストと交信すること
(2) チップにデータをロードし、かつ、チップからデータを取り出すこと
(3) 回路に対し一連の数学的動作を遂行するように指示すること
(4) 他の暗号化システムおよび非暗号化システムに応答してデータ処理動作を遂行すること
カウンタは、実際の状態マシンに対するアドレスを生成する。
【０１５０】
状態マシンは、アドレスを復号化し、多重化部（ＭＵＬＴ部）に対する複数種の制御信号を生成する。これらの制御信号は、多重化部に対し、ρ（Ａ・Ｂ）Ｎ変換の計算を実行するために必要とされる適切な動作手順を遂行するように指示する（ここで、ＡはＢに等しい）。
図３は、本発明の物理的な形態（多重化部）を実施するためのハードウェアの装置をブロック図の形で表したものである。さらに、図３は、本発明に係る特許により保護されるべきアーキテクチュアの幾つかの概念に焦点を絞る際の補助手段となるように意図されている。図３のブロックは、同時に、モントゴメリのモジュラ・乗算にて既述したような式(1) 〜(5) により規定された手順を遂行する。さらに、図３のブロックは、同期クロックを変えることなく、かつ、限定された合同の関係を有するＳおよびＢの変換を行うことなく上記の手順を遂行する。このセクションにおいて、我々は、定数（Ｎの関数）Ｊ0 およびＨが前もって計算されることを仮定している。  図３の回路は、ρ（Ａ・Ｂ）Ｎを遂行する。この回路の機能を利用することにより、この回路は、次の計算を行うために使用され得る。
【０１５１】
(1) Ｂ・ＡｍｏｄＮ
(2) Ｂ2 ｍｏｄＮ
ただし、いかなる場合でも、ＢはＮよりも小さくなければならない。
ここで、Ｃ＝Ｂ・ＡｍｏｄＮを遂行する手順を詳細に説明する。
(1) まず、プロセッサが、オペランドＢをＢのレジスタに前もってロードする。同様に、プロセッサは、オペランドＮをＮのレジスタに前もってロードする。
【０１５２】
(2) 多重化部内の回路が次回のＳの値を計算し始める度に、回路は、次回のＡi を前もってロードすることを（フラグを立てることにより）ＣＰＵに知らせる。Ｓ（ｍ）回の繰り返し動作の後に、Ｂに対し限定された合同の関係を有する数がＢのレジスタに残る。
(3) 多重化部が、Ｆ＝ρ（Ｂ・Ｈ）Ｎを計算する。ここで、プロセッサがＨi のキャラクタの処理手順を前もってロードする場合を除けば、Ｈは、上記のステップ(1) および(2) に記載された手順において、前もって計算された定数である（プロセッサがＡi のキャラクタを前もってロードする場合も同じことがいえる）。
【０１５３】
また一方で、Ｃ＝Ｂ2 ｍｏｄＮを遂行する手順を詳細に説明する。
(1) まず、Ｂのレジスタが、Ｂに対し限定された合同の関係を有することがわかっている数を保持していると仮定する。さらに、Ｎのレジスタが、モジュールＮを保持していると仮定する（２乗処理においては、一般にいえることである）。ここで、多重化部は、Ｂ0 とＢ0 の最下位のキャラクタでもってＡi のレジスタを予めロードしておくことにより、２乗処理を進めることができる。
【０１５４】
(2) Ｂ＝ρ（Ｂ・Ｂ）Ｎの計算処理は、上記の乗算動作における第２のステップ（ステップ(2) ）と同様の処理過程で進行する。ただし、Ｂのレジスタが回転動作を行っている場合に、Ｂi のキャラクタの連続するローディング動作が、Ｂのレジスタから直列式かつオンザフライ方式になされるときは、この限りではない。
【０１５５】
(3) 必要な場合には、上記の乗算動作における第３のステップ（ステップ(3) ）と同様のρ（Ｂ・Ｈ）の計算を行う。
当業者にとっては明らかなことなので、発明者は、直列／並列形乗算器および一般の構成部品が本発明そのものの一部を構成することは、敢えて主張しない。今後の説明は、一般に普及している標準の論理セルを使用していることを明確にするためになされるものである。ただし、論理セルの幾つかは、それほど度々一般に使用されていないかもしれない。ここで図示したゲート構成は、本発明の証明のために例示しているにすぎない。熟練された技術者は、これらの論理セルを最適化するであろう。
【０１５６】
オペランドＡ、ＢおよびＮは、いずれもｎビット長であり、ｋビット長のキャラクタからなるｍ個のグループにより構成される。それゆえに、ｎ＝ｋ・ｍが成り立つ。ｋ＝３２のハードウェア装置においては、ｍは、８ビットまたは１６ビットの２進数のビット長になる。
乗算器１および乗算器２
これらの乗算器（ＭＬ）は、符号のない乗算動作に対しブースの乗算アルゴリズムを実行する。この場合、並列のオペランドは、ｋセル（ビット）長になっており、直列のロードされるオペランドは、任意の要望されるビット長になっている。
【０１５７】
各々の直列／並列乗算器は、ｋ−１のＭＰＬセルからなる（図５参照）。ＭＳビットに相当する最上位のセルは、ＡＮＤゲートのみから構成される。
各々のＭＰＬセルは、Ｙの直列の入力ビットと、ＸＩの並列の入力ビットとの乗算動作を行う。さらに、この乗算動作により、前段のＭＰＬユニットの直列出力と、それ自身の前回のサイクルのキャリー出力ビットが生成される。上記のＭＰＬセルは、これらの出力結果を合計する。
【０１５８】
図５からわかるように、各々のＭＰＬセルは、２ビットの乗算加算器である。ＭＰＬセルのブロックは、ＸＩの入力ビットと、Ｙの直列の入力ビットとの乗算動作を行う。さらに、このブロックは、ＤＩ（データ入力）からの乗算結果と、前回のサイクルからのＣＩ（キャリー入力）との加算処理を行う。最終の結果として、ＤＯ（データ出力）と、次のサイクルに対するＣＯ（キャリー出力）が得られる。このキャリー出力ＣＯは、Ｄフリップフロップに記憶される。データ出力ＤＯは、下記の式(37)により表される。
【０１５９】
【数３７】
0003636740.tif 000038
【０１６０】
このようにして記憶されたキャリー出力ＣＯは、次のサイクルに対するキャリー入力ＣＩになる。このキャリー出力ＣＯは、ブーリアン（Boolean ）の和により、下記の(38)により表される。
加算器１および加算器２
ここで使用される各々の加算器（Ａｄ）は、Ｄフリップフロップからなる単純な１ビットの全加算器である。この加算器は、次のクロック・サイクルで出力されるキャリービットを記憶するために使用される（図７参照）。
【０１６１】
図７に示すように、２つの入力Ａ、Ｂは、前回のクロック・サイクルからのキャリー入力ＣＩと一緒に加算される。この結果、モジュロ２の和が生成される。この和は、出力信号Ｓを取り出すために、Ｄフリップフロップに記憶される。加算器がリセットされたときは、キャリービットは０になる。
減算器１、減算器２および減算器３
図８に示すように、減算器（Ｓｕｂ）の各ブロックは、前段のボローを記憶するためのＤフリップフロップからなる全減算器である。このブロックは、前述の加算器のブロックとほぼ同じ構成になっている。ただし、減算器においては、Ａの流れからＢの流れを直列に引く点が加算器と異なる。
【０１６２】
ディレイ素子１、ディレイ素子２およびディレイ素子３
これらのディレイ素子（Ｄｅｌａｙ）は、ｋ１ビットの連結された状態の記憶素子から構成される。これらのディレイ素子は、数学的処理において各種のオペランドの同期をとるために使用される。これらの同期動作は、回路を説明すれば明らかになるであろう。
【０１６３】
Ａi 、Ｊ0 、およびＹ0 
これらのブロックは、ｋビット長の直列入力／並列出力形シフトレジスタである。この場合、ｋビットの入力ビットは、直列に入力される。ｋビットの実効的なクロック・サイク期間の後に、これらのｋビットは、並列形式で出力側に現れる。
【０１６４】
図２においては、細い線が直列の１ビットの導体線を示し、太い線が並列のｋビットの導体線を示している。
Ｍ４  １；ｘ、Ｍ３  １；ｘ、およびＭ２  １；ｘ
これらのブロックは、１ビット出力のマルチプレクサである。Ｍ４  １；ｘは、４つの入力から１つの出力を取り出すものである。Ｍ３  １；ｘは、３つの入力から１つの出力を取り出すものである。Ｍ２  １；ｘは、２つの入力から１つの出力を取り出すものである。ｘは、特定の構成部品に対する明瞭なインデックスを示している。
Ｂ（０：ｋ−１）、Ｂ（ｋ：ｎ１−１）、Ｂ（ｎ１：ｎ２）、Ｓ（０：ｎ１−１）、Ｓ（ｎ１：ｎ２）、Ｎ（０：ｋ−１）、Ｂ（ｋ：ｎ１−１）、およびＢ（ｎ１：ｎ２）
これらのブロックは、シフトレジスタである。比較的ビット長の長いレジスタのビット列の大きさおよび位置が、括弧（  ）内の数字によって示されている。例えば、Ｘ（ｓ：ｔ）は、ｔ−ｓ＋１ビット長のシフトレジスタである。ここで、ｓは、レジスタＸ（ｓ：ｔ）の最初のビットのインデックスであり、ｔは、レジスタＸ（ｓ：ｔ）の最後のビットのインデックスである。例えば、Ｂ（０：５１１）は、次のような３つの比較的短いカスケード接続形のレジスタから構成される。すなわち、Ｂ（０：３１）、Ｂ（３２：２５５）、およびＢ（２５６：５１１）から構成される。
【０１６５】
ｎ１は、一般に、ｎ／２（例えば、２５６）に等しい。ｎ１は、ｋの倍数でなければならない。
ｎ２は、ｎ−１に等しい。
ｋは機器のキャラクタの長さ、すなわち、直列／並列乗算器の大きさである。
したがって、最初の処理過程においては、次の値が予測される。
【０１６６】
ｎ１＝２５６、ｎ２＝５１１、ｎ＝５１２、およびｋ＝３２
ラッチ１およびラッチ２
これらの２つのラッチは、ｋビットのレジスタである。これらのラッチは、乗算器内の並列データを保持するために使用される。このようなラッチの動作により、乗算処理において単一のクロックを用いた並列変換が可能になる。
【０１６７】
多重化部（ＭＵＬＴ部）の動作…ρ領域内での乗算およびべき乗
説明を簡単にするために、我々は、レジスタ内のデータが実際に移動するクロック・サイクルのみを指定することとする。すなわち、我々は、このようにデータが移動するサイクルを実効的なクロック・サイクルと定義する。
ρ（Ａ・Ｂ）Ｎの乗算
第１段階：初期ローディング
この段階では、ＤＩを介して下記のレジスタがロードされる。
【０１６８】
(1) Ｊ0 のレジスタにＪ0 をロード（ＣＰＵにより前もって計算される）
(2) ＢのレジスタにＢをロード
(3) ＮのレジスタにＮをロード
(4) Ａ2 のレジスタにＡ、Ａ0 の最初のキャラクタをロード
同時に、ステップ(2) において、レジスタＳに対しビット値０がロードされる。
【０１６９】
これらの５つのレジスタに所定の値をロードした後に、符号のな２つの直列／並列乗算器ＭＬ１およびＭＬ２と、直列加算器Ａｄ１およびＡｄ２と、直列減算器Ｓｕｂ１、Ｓｕｂ２およびＳｕｂ３とがリセットされる。
第２段階：Ｂ・Ａ0 の繰り返し動作の実行
レジスタＡi にロードされたデータＡ0 は、ラッチ１に転送される。レジスタＢは、周期的に右方向へのシフト動作を行う。繰り返し動作の始まりにおいては、ボロー検出器２の制御信号はビット値０になっている。それゆえに、Ｂの内容は、Ｓｕｂ１を通過しても変化しないままでいる。さらに、Ｂの内容は、ＭＬ１においてＡ0 により乗算される。レジスタＢの出力は、変化しない状態で、その入力される。
【０１７０】
このような乗算の結果は、Ａｄ１において、レジスタＳの内容に直列に加算される。最初の繰り返し動作のときは、レジスタＳの内容はすべて０である。この動作により、前述のようにＸが生成される。
上記の処理過程が進行している間に、ＣＰＵは、Ａの次のキャラクタであるＡ1 をラッチ１に予めロードしておく。
【０１７１】
さらに、Ｊ0 のレジスタからラッチ１にＪ0 がロードされる。ＸがＭＬ２に直列に入力され、Ｊ0 により乗算される。実効的なｋクロック・サイクルが経過した後に、レジスタＹ0 の内容は、積Ｘ0 ・Ｊ0 の最下位のｋビットになる。
さらに、最初の実効的なｋクロック・サイクルが経過した後に、ＭＬ２はリセットされる。ここで、直列入力形のマルチプレクサ  Ｍ３  １；４は、Ｘの流れをＮの流れに切り替える。レジスタＹ0 内のデータは、Ｊ0 に取って代わり、ラッチ２に並列にロードされる。さらに、ラッチ２の出力は、Ｙ0 ・Ｎの流れに切り替えられる。次のｎ＋ｋクロック・サイクル期間においては、ＭＬ２からの直列の出力結果は、Ｙ0 ・Ｎになる。実効的なｋクロック・サイクル期間だけ遅延されたＸは、今度は、Ａｄ２において加算処理がなされ、ＭＬ２の積を生成する。この結果、Ｚ＝Ｘ＋Ｙ0 ・Ｎが得られる。ここで、Ｚは、最下位のｋビットがすべて０であるような数である。
【０１７２】
Ａｄ２の最初のｋビットはすべて０なので、この最初のｋビットは無視される。そして、次のｎビットが、Ｓのレジスタに直列に戻される。繰り返し動作の最終的な値は、Ｎに等しいかまたは大きい（この場合には、この値をＮから引くことが必要である）。すなわち、Ｓ（１）￥Ｓ（１）ｍｏｄＮが成立する。
ＳがＮよりも大きいか否かを検出するために、Ｓｕｂ３においては、ｎビット長の（Ｚ／２n ）の流れからＮが減算される。しかしながら、この場合、ｎ回目のボロービットのみが、ボロー保持用フリップフロップに記憶される。
【０１７３】
もし、このボロービットのビット値が０であるか、または、Ａｄ２の最終キャリービットＣＯのビット値が１であれば、Ｓのレジスタの最新の値はＮよりも大きい。
最初の繰り返し動作の始まりにおいては、Ｓ（１）ｍｏｄＮに対し限定された合同の関係を有する数がＳのレジスタ内に存在する。Ｊ0 、ＢおよびＮのレジスタは、最初にロードされたオリジナルな値を保持する。そして、データを前もって保持するためのＡi のレジスタはＡ1 を保持する。
【０１７４】
第３段階：その後のＢ・Ａi の繰り返し動作の実行
Ａの次のキャラクタであるＡ1 が、ラッチ１およびＭＬ１の並列入力に転送される。
次のＢ・Ａi の繰り返し動作およびそれに続く繰り返し動作の期間中、各々の繰り返し動作の最後において、Ｓ（ｉ）ｍｏｄＮに対し限定された合同の関係を有する数Ｓが存在する。もし、Ｓ（ｉ）がＮよりも大きければ、Ｓｕｂ２においてＳ（ｉ）からＮが引かれる。
【０１７５】
各々の繰り返し動作が始まるときに、ＣＰＵは、Ａの次のキャラクタであるＡ1 を、データを前もって保持するためのＡi のレジスタにロードしておく。
ρ（Ｂ・Ｂ）Ｎの２乗動作
通常のべき乗処理の最初の動作は、２乗動作である。この２乗動作は、Ｂのレジスタにロードされた乗数Ａと、Ａi のレジスタにロードされた被乗数との通常の乗算と同じような手順で行われる。ただし、この場合、ビット数は、前述したようにｋビット分だけ増加する。さらにその後の２乗動作は、Ｂのレジスタ内に存在するような限定された合同の関係を有するオペランド（乗数および被乗数）により遂行される。
【０１７６】
上記のρ（Ｂ・Ｂ）Ｎのような２乗動作が遂行されている間、Ｊ0 、Ｓ、ＢおよびＮの各レジスタは、その出力側で、前回の乗算および２乗処理により得られた値を変えることなくそのままロードされる。しかしながら、この場合は、繰り返し動作において、Ａi のレジスタは、Ｂのレジスタ内に存在するｋビットのキャラクタから派生する新しいキャラクタをロードしなければならない。
【０１７７】
上記の連続的な２乗動作において、Ａi のレジスタは、Ｂのレジスタからオンザフライ式に予めロードされる。ＣＰＵが、一度、２乗処理を遂行するように指示を与えると、それ以降の２乗動作は問題なく遂行される。ＢのレジスタにロードされるＢ（ｉ）′は、Ｓｕｂ１を通って流れるＢの一部分である（Ｂi の中で、既にＮよりも小さい部分）
第１段階：Ｂ・Ｂ0 の繰り返し動作
先ず、前回の計算処理から導き出されるような、Ｓに対し限定された合同の関係を有する最新の数が、Ｂのレジスタ内に存在するものとする。
【０１７８】
レジスタＢ、Ｎの最下位のｋビットは、周期的に右方向へのシフト動作を行う。さらに、実効的なｋクロック・サイクルの後に、レジスタＢ、Ｎは、オリジナルの状態に復帰する。レジスタＢ内の値は、適当なＢの値か、または、次のρ領域での乗算を遂行するために使用されるＢ−Ｎの値である。したがって、最初の丸めにおいて、レジスタＡi は、Ｂ0 またはＢ−Ｎの最下位のｋビットでもって予めロードしなければならない。ここで、Ｂ0 は、レジスタＢ内に存在する値である。
【０１７９】
この最初のｋビットの回転動作の目的はレジスタＡｉへのプリロードの最初のｋビットがＳｕｂ（すなわち、減算器）１を通って流れることを可能にするためである。直列にロードされた直後に、ＡｉはLatch （すなわち、ラッチ）１にアンロードされ、ＡｉプリロードレジスタはＢの第２の文字であるＢ1 をロードするために自由にされる。
このおよび引き続く操作の間、Borrow（すなわち、ボロー）２信号がセットあるいはリセットされた時にSub １からの出力は正であり、常にＮより小である。
【０１８０】
全ての値がレジスタにロードされると、説明されるようにＢがローテイトした時にＢ1 がＡｉレジスタ中にロードされる点（乗算においてＣＰＵはＡｉレジスタにロードすることを思い出すこと。）を除くと、以前に説明したようにこの最初の乗算はＢ・Ａ0 に対して実行される。
第２のｋビット文字Ｂ1 はＢストリームから発生するために、この最初のＢ・Ｂ0 処理の間にＢ1 セグメントは、次の開平演算、すなわちＢ・Ｂ1 繰り返しのために直列的にＡｉプリロードレジスタ中にオンザフライ処理で切り換えられる。
第２段階：Ｂ・Ｂ1 繰り返し動作
Ａi のレジスタ中にロードされた値Ｂ1 は出力ラッチLatch １に転送される。次のｎ＋２ｋ（すなわちｎ＋６４）クロックサイクル中にＢ・Ｂ1 に対する乗算処理が上述のように実行される。
【０１８１】
前回と同様Borrow１およびBorrow２信号は、ＢおよびＳレジスタから発生する流れからＮが減算されうるか否かを決定する。もしＳレジスタ中の値がＮより大であるかあるいは等しければBorrow１はセットされ、減算器Sub １においてＮはＳから減算される。もし必要であればｍ繰り返し乗算ループ完了の間にＮはＳから減算される。このような状況は先行する乗算あるいは開平演算の終わりにBorrow２で検知される。
【０１８２】
フリップフロップBorrow１およびBorrow２はSub ３からの条件付きのボロー出力の最終値を記憶している。Borrow１は各Ｓの繰り返しの後にセットあるいはリセットされる。Borrow２はＢがＳ（ｍ）にロードされる最後のＳ（ｍ）繰り返しの後にセットあるいはリセットされる。この条件付きのボロー出力はＳ（ｉ）がＮより大であるか否かを示す信号である。
【０１８３】
Ｂ・Ｂ1 処理の間、文字Ｂ2 が減算器Sub １中に存在する場合に文字Ｂ2 はオンザフライ処理でＡｉプリロードレジスタ中にロードされる。
第３段階：次のＢ・Ｂ1 乗算繰り返し
文字Ｂ1 が減算器Sub １中に存在する時には文字Ｂ1 の値がＡｉレジスタにロードされる間に残りのｍ−２回の繰り返しが次のループの準備のために実行される。
【０１８４】
限定された一致の最終結果はＳおよびＢレジスタ中に存在する。このデータはＤＯを通して直列に出力されるために、もし必要であればSub １で修正されるであろう。
乗算ブロックの操作−Ｈパラメータの演算
Ｈを演算するために、マシンは図９に示されるようにレジスタＳおよびＮを使用するために再構成される。上記で既に使用した数値例を用いて演算子の操作を説明する。この構成はＨの演算をｎ＋１回で実行する。各回の実行においてＳおよびＮは共にローテイトされ、各ローテイトはｎクロックである。各実行回においてＮは回転し変化せずに帰還する。ｉ回目の実行において、Ｓおよび次の減算（Next Subtract ）信号はＳ（ｉ）の限定された￥一致の同等値を含んでいる。初期条件−第１回実行
第１回目の実行の最初で、ＮはＮレジスタ中にロードされ、第１回目の試行減算が成功したことを表すボロー検出フラグはリセットされ、Sub １の出力フリップフロップはゼロにリセットされる。第１回目の実行中、試行除算のｎ番目のＭＳビットは“１”である。このビットは次の減算用フリップフロップ（Ｓ中にスペースはない。）を推論して記憶される。次の減算は、第１回目の実行においてＳ−Ｎ減算を命令する。
上述のｎ＝４ビットの数値例を使用して例証する。
0003636740.tif 000039
0003636740.tif 000040
【０１８５】
0003636740.tif 000041
0003636740.tif 000042
【０１８６】
0003636740.tif 000043
【０１８７】
0003636740.tif 000044
【０１８８】
0003636740.tif 000045
【図面の簡単な説明】
【図１】本発明の一実施例の装置構成を示すブロック図である。
【図２】本発明の一実施例のモジュラ・乗算回路を示すブロック図である。
【図３】本発明の一実施例の特殊なモジュラ・乗算回路を示すブロック図である。
【図４】本発明の一実施例による繰り返し動作と乗算動作との間の時間的な関係を示す図である。
【図５】直列／並列乗算器のセルの構成を示す回路図である。
【図６】８ビットの直列／並列乗算器の構成を示す回路図である。
【図７】直列加算器の構成を示す回路図である。
【図８】直列減算器の構成を示す回路図である。
【図９】Ｈパラメータを計算するためのアーキテクチュアを示すブロック図である。
【符号の説明】
１０〜１２…レジスタ
１３〜１５…マルチプレクサ
１６〜１８…レジスタ
２７〜３１…加算／減算手段
３２〜３４…ディレイ手段
３５…ボロー検出器
【図１】
0003636740.tif 000046
【図２】
0003636740.tif 000047
【図３】
0003636740.tif 000048
【図４】
0003636740.tif 000049
【図５】
0003636740.tif 000050
【図６】
0003636740.tif 000051
【図７】
0003636740.tif 000052
【図８】
0003636740.tif 000053
【図９】
0003636740.tif 000054