(57)【要約】【課題】改善されたモジュラー減少演算子を提供する。【解決手段】本発明は改善されたモジュラー減少装置に関する。該モジュラー減少装置は、４以上の高い記数法の底ｒを用いたモンゴメリー乗算プロセスの変形を使用する、乗算器（１２）を含む。それはとりわけ非対称の暗号法に用いられる計算要素に適用される。【選択図】図１
2008304921.tif 000002
【特許請求の範囲】
【請求項１】
４以上の高い記数法の底ｒを用いた、モンゴメリー乗算の演算を使用する乗算器（１２）を含むことを特徴とする、モジュラー減少装置。
【請求項２】
乗算器（１２）が次のアルゴリズム：
ｉ．Ｓ←ｐ０．ｑ
ｉｉ．０≦ｉ≦ｔｎ−１であるｉに対し、以下を用いる：
ａ．ｍｉ←Ｓ０．ｎ’ｍｏｄ  ｒ
ｂ．Ｓ←ｐｉ．ｑ＋（ｍｉｎ＋Ｓ）／ｒ
ｉｉｉ．ｍｔｎ←Ｓ０．ｎ’ｍｏｄ  ｒ
ｉｖ．Ｓ←（ｍｔｎ．ｎ＋Ｓ）／ｒ
を用い、
ここで、ｔｎは複数の機械語におけるモジュールｎのサイズを指し、ｐ及びｑは乗算されるべき演算数、ｍｉは中間係数、Ｓは乗算結果であり、そしてｎ’の値は−ｎ−１ｍｏｄ  ｒに等しいことを特徴とする、請求項１に記載のモジュラー減少装置。
【請求項３】
加算されるべき、及び乗算されるべき幾つかの数字を受け取る、ｐ組のパイプライン方式で実行される論理−レジスタの対と、（最）下位ビット及び（最）上位ビットに対応する少なくとも二つの出力とを備える乗算−加算器、ならびに該乗算−加算器から二つの出力を受け取る加算器とを含み、ここでｐは乗算−加算器の最大周波数Ｆ１ｍａｘが加算器の最大周波数Ｆ２ｍａｘ以上であるようなやり方で選定されることを特徴とする、請求項１〜２のいずれか一項に記載のモジュラー減少装置。
【請求項４】
シーケンサ（１１）、加算器ブロック（１３）、及びメモリモジュール（１４）をまた含み、シーケンサの一つの出力が乗算器の制御入力に接続され、シーケンサの一つの出力が加算器ブロックの制御入力に接続され、そしてメモリモジュールがデータ交換のために乗算器及び加算器に接続されることを特徴とする、請求項１〜３のいずれか一項に記載のモジュラー減少装置。
【請求項５】
請求項１〜４のいずれか一項に記載のモジュラー減少装置を含む暗号化構成要素。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は改善されたモジュラー減少装置に関する。それは特に非対称の暗号法に用いられる計算要素に適用される。
【背景技術】
【０００２】
一般に、公開鍵暗号化プロセスは代数的数のモジュラーリングにおいて行なわれる計算に適用される。暗号の演算はそれゆえモジュラー演算で行なわれ、そしてモジュラー減少演算がしばしば必要とされる。実際、この演算はリングＺｎにおいて、ｎよりも大きい第一の数を、ｎよりも小さく前者と適合する数へ変換することを可能にする。暗号の計算要素の性能に関連する主な問題点はこの演算に関わる。
【０００３】
モジュラー減少を得る一つの自然な方法は、ユークリッド除算を計算することであり、その結果は除算の剰余に等しい。しかしながら、このような演算の性能はとりわけ月並みであり、除算の計算は一般にマイクロプロセッサの使用を必要とする。現在のところ、幾つかのモジュラー減少プロセスは非常に短い計算時間で結果が得られることを可能にするが、それらは一般に処理される数のサイズにより制限される。他のプロセスはフレキシブルである。それらは対照的にあらゆるサイズの数の処理が可能であるが、しばしば非常に長い計算時間を要することをそれは意味する。（特許文献１）の番号の下で発行された特許もまたモンゴメリー法によるモジュラー減少プロセスを提案している。しかしながら、このプロセスは幾つかのアプリケーションに対して無用と考えられる計算である、パラメータＨの計算を必要とする。その上、従来の実施形態においては、他の計算モジュールを含む暗号の構成要素へ容易に組み込まれ得る解決策がない。
【０００４】
【特許文献１】欧州特許第０７１２０７１号明細書
【発明の開示】
【課題を解決するための手段】
【０００５】
本発明の一つの目的は、低減された計算時間であらかじめ決定されていないサイズの数を処理することができ、そのような装置が、例えば暗号の計算要素へ容易に組み込まれ得るモジュラー減少プロセスを実行する装置を作り出すことである。このため、本発明は４以上の高い記数法の底ｒを用いて、モンゴメリー乗算の演算を実行する乗算器を含むことを特徴とする、モジュラー減少装置を作り出すように設計される。
【０００６】
該乗算器は以下のアルゴリズムを実行することができる。
Ｓ←ｐ０．ｑ
０≦ｉ≦ｔｎ−１であるｉに対し、以下を適用：
ｍｉ←Ｓ０．ｎ’ｍｏｄ  ｒ
Ｓ←ｐｉ．ｑ＋（ｍｉｎ＋Ｓ）／ｒ
ｍｔｎ←Ｓ０．ｎ’ｍｏｄ  ｒ
Ｓ←（ｍｔｎ．ｎ＋Ｓ）／ｒ
ここで、ｔｎは多数の機械語におけるモジュールｎのサイズを指し、ｐ及びｑは乗算されるべき演算数、ｍｉは中間係数、Ｓは乗算結果であり、そしてｎ’の値は−ｎ−１ｍｏｄ  ｒに等しい。
【０００７】
一つの実施形態によれば該乗算器は、加算されるべき、及び乗算されるべき幾つもの数字を受け取る、ｐ組のパイプライン方式で実行される論理−レジスタの対と、（最）下位ビット及び（最）上位ビットに対応する少なくとも二つの出力とを備える乗算−加算器、ならびに該乗算−加算器から二つの出力を受け取る加算器とを含み、ここでｐは乗算−加算器の最大周波数Ｆ１ｍａｘが加算器の最大周波数Ｆ２ｍａｘ以上であるようなやり方で選定される。
【０００８】
モジュラー減少装置は又シーケンサ、加算器ブロック、及びメモリモジュールを含むことができ、シーケンサの一つの出力は加算器ブロックの制御入力に接続され、別のシーケンサの出力は乗算器の制御入力に接続され、そしてメモリモジュールはデータを交換するため乗算器及び加算器に接続される。
【０００９】
本発明の目的はまた上記のようなモジュラー減少装置を含む暗号法の構成要素である。
【００１０】
他の特徴は添付図に対して以下に続く、例として、そして制限されずに与えられる詳細な記述を読むことにより明らかになるであろう。
【発明を実施するための最良の形態】
【００１１】
図１は本発明によるモジュラー減少装置のブロック線図を示す。モジュラー減少装置１はシーケンサ１１、乗算器ブロック１２、加算器ブロック１３、及びメモリモジュール１４を含む。乗算器ブロック１２及び加算器ブロック１３はシーケンサ１１から指令を受け、各データをメモリモジュール１４と交換する。ユーザ・アプリケーション１５は該指令をシーケンサ１１に送り、そしてデータをメモリモジュール１４と交換する。
【００１２】
取り扱われたデータは各々ｂビットから成る機械語で記録される。機械語のサイズｂは一般に２の累乗である。記数法の底ｒは２ｂに等しいと定義される。係数ｎはｔｎの機械語において記録される奇数である。Ｒは記数法の底ｒの累乗として定義され、ここでＲは係数ｎよりも大きい。数ｘは底ｒにおいて、次のようにｔ＋１個の数ｘｉへと分解され得る。
ｘ＝ｘ０＋ｘ１．ｒ＋ｘ２．ｒ２＋．．．＋ｘｔ．ｒｔ
ここで、各々の数ｘｉは機械語のサイズである。
最後に、数ｇｉの組は次のように定義される。：ｇｉ＝Ｒ２＋ｉｍｏｄ  ｎ、ここでｉは０〜ｋ−１まで変化し、ｋは例えば本発明のユーザ・アプリケーション１５により決定される最大値である。ｇｉの値は例えば、他のモジュラー減少方法により、本発明のユーザ・アプリケーション１５によって予め計算される。実際、ｇｉの値は、これらのｇｉの値がモジュラー減少装置の演算のために必要であるため、該モジュラー減少装置１によって予め計算出来ない。一旦これらのｇｉの値が計算されると、モジュラー減少装置１は多くてもＲｋ＋１−１に等しいｘの値に対するｘ  ｍｏｄ  ｎを計算することが可能である。
【００１３】
本発明によるモジュラー減少装置１は、数ｘを減少させるために次のプロセスを用いる。
Ｓｅｔ  ｓ＝０，ｕ＝０
０≦ｉ≦ｋ−１であるｉに対して、次の演算を実行する：
ｕ←ＭＭｕｌ（ｘｉ，ｇｉ）
ｓ←ＭＡｄｄ（ｓ，ｕ）
ｒｅｔｕｒｎ  ＭＭｕｌ（ｓ，１）
ここで、ｕ及びｓは一時的数値変数、ＭＭｕｌ（）は乗算器ブロック１２において実行され、下記に説明されるモジュラー乗算アルゴリズムであり、ＭＡｄｄ（）は加算器ブロック１３において用いられるモジュラー加算アルゴリズムである。
【００１４】
メモリモジュール１４は数ｎ、ｇｉ、ｘの数字ｘｉ、及び値ｕとｓを記憶する。シーケンサ１１はメモリモジュール１４内に記憶されたデータを用いて、モジュラー減少アルゴリズムを実施するために、乗算器ブロック１２及び加算器ブロック１３を制御する。
【００１５】
乗算器ブロック１２は高い記数法の底ｒ（ｒ≧４）において作用するモンゴメリー・アルゴリズムの変形を用いる。それはＲ＝ｒｔｎ＋１の値と共に作用する。シーケンサ１１により使用される数字ｘは、それゆえｔｎ＋１ワードのサイズを有する。
【００１６】
ｎ’として言及され、−ｎ−１ｍｏｄ  ｒに等しい別の値は、例えば本発明のユーザ・アプリケーション１５により予め計算されなければならない。乗算器ブロック１２は例えば、ｔｎの値を記憶している初期レジスタ、及びｎ’の値を記憶している第二レジスタを有する。これら二つのレジスタはブロックが初期化される際にローディングされる。
【００１７】
乗算器ブロック１２はそこからパラメータを取り、計算結果を位置付けるメモリモジュール１４とインターフェースで接続される。入力において、それはｔｎ＋１ワードのサイズを有する二つの数を取り、その結果はｔｎ＋１ワードの数である。モジュールｎのサイズはｔｎワードであるため、入力ｐとｑをｐ＝ｐ’＋ｅｐ．ｎとｑ＝ｑ’＋ｅｑ．ｎの形で表わすことができ、ここでｐ’とｑ’はｎよりも小さく、そしてｅｐとｅｑは２ｂビット以下のバイナリ・サイズを有する。乗算器ブロック１２はｃ＝ｃ’＋ｅｃ．ｎであるようにｃの値を計算し、ここでｅｃは２ｂビット以下のバイナリ・サイズを有し、ｃ’はａ．ｂ．Ｒ−１  ｍｏｄ  ｎに適合する。その後に、底ｒにおける数Ｎの数字はＮｉと呼ばれる。
二つの数ｐとｑのモンゴメリー・モジュラー乗算の演算を行なうことが出来るように、乗算器ブロック１２は次のプロセスを実行する。：
ｉ．Ｓ←ｐ０．ｑ
ｉｉ．０≦ｉ≦ｔｎ−１であるｉに対し、以下を用いる：
ａ．ｍｉ←Ｓ０．ｎ’ｍｏｄ  ｒ
ｂ．Ｓ←ｐｉ．ｑ＋（ｍｉｎ＋Ｓ）／ｒ
ｉｉｉ．ｍｔｎ←Ｓ０．ｎ’ｍｏｄ  ｒ
ｉｖ．Ｓ←（ｍｔｎ．ｎ＋Ｓ）／ｒ
ここで、ｍｉの値は計算の中間係数であり、Ｓはその結果である。
【００１８】
演算ｉｉ．ｂ及びｉｖは乗算−加算器「機械語ｘ数＋数」により実施され得る。演算ｉは乗算器「機械語ｘ数」により実施される。ｒによる除算の演算は、機械語の結果を最下位ビットの方へシフトさせるハードウェアにより行なわれる。
【００１９】
乗算器ブロック１２は、プロセスの各段階においてそれぞれがｐ、ｑ、及びｎを受け取る、ｂビットの三つの並列入力：Ｐｉ、Ｑｉ、及びＮｉを含む。乗算器ブロック１２への入力演算数の伝送は、従って直列／並列モードで行われる。乗算器ブロック１２はまた、各段階で機械語を生み出すｂビットの並列出力を含む。その結果の出力は従って直列／並列モードで行われる。
【００２０】
モジュラー減少装置１は次のステップ、
ｉ．ｎ、ｇｉ、ｘｉの値をメモリブロック１４内へ書き込むステップと、
ｉｉ．減少アルゴリズムを実行するためにシーケンサ１１に指令するステップと、
ｉｉｉ．メモリブロック１４においてその結果を読み取るステップと
を実行するために、マイクロプロセッサ又は他のハードウェア・ブロックにより制御される。
ｎ及びｇｉの値は、各々の新たなモジュラー減少の前に、これらの値をメモリ内に再度書き込む必要がないように、ｎを法とする低減されるべき値ｘに無関係である。
【００２１】
ｔｎ及びｎ’の値は乗算器ブロック１２により用いられる。加算器ブロック１３はｔｎの値のみを使用する。
【００２２】
一例として、第一ステップ（ｉ．）の間、メモリ１４内に記録された値は次のアドレスに置かれ得る。
ｎは０〜ｔｎのアドレスで機械語を占める。
ｇ０はｔｎ＋１〜２ｔｎのアドレスで機械語を占める。
ｇ１は２ｔｎ＋１〜３ｔｎのアドレスで機械語を占める。
・・・
ｇｋ−１はｋ．ｔｎ＋１〜（ｋ＋１）．ｔｎのアドレスで機械語を占める。
ｘは（ｋ＋１）．ｔｎ＋１〜２ｋ．ｔｎのアドレスで機械語を占める。
ｕは（２ｋ）ｔｎ＋１〜（２ｋ＋１）ｔｎのアドレスで機械語を占める。
ｓは（２ｋ＋１）ｔｎ＋１〜（２ｋ＋２）ｔｎのアドレスで機械語を占める。
一時的数値変数ｕ及びｓはゼロに初期化され、位置はアドレス（２ｋ＋２）ｔｎ＋１〜（２ｋ＋３）ｔｎに結果を記録するために割り当てられる。
【００２３】
各呼び出しにおいて、三つのパラメータが乗算器ブロック１２に渡される。第一のパラメータは第一演算数のメモリ１４内におけるアドレスであり、第二のパラメータは第二演算数のメモリ１４内におけるアドレスであり、第三のパラメータは乗算の結果を記録するように意図される位置の、メモリ１４内におけるアドレスである。
【００２４】
二つのパラメータが加算器ブロック１３に渡され、該二つのパラメータはメモリ１４における二つの演算数のアドレスに対応する。加算の結果は第二演算数のアドレスに置かれる。
【００２５】
シーケンサ１１は次にメモリ内のデータを用いて、以下のようにモジュラー減少プロセスを実行することができる。
ＭＭｕｌ（（ｋ＋１）ｔｎ＋１，ｔｎ＋１，（２ｋ）ｔｎ＋１）（ｘ０のアドレス、ｇ０のアドレス、ｕのアドレス）
ＭＡｄｄ（（２ｋ）ｔｎ＋１，（２ｋ＋１）ｔｎ＋１）（ｕのアドレス、ｓのアドレス）
・・・
ＭＭｕｌ（（２ｋ−１）ｔｎ＋１，ｔｎ＋１，（２ｋ）ｔｎ＋１）（ｘｋのアドレス、ｇ０のアドレス、ｕのアドレス）
ＭＡｄｄ（（２ｋ）ｔｎ＋１，（２ｋ＋１）ｔｎ＋１）（ｕのアドレス、ｓのアドレス）
ＭＭｕｌ（（２ｋ＋１）ｔｎ＋１，ａｄｄｒｅｓｓ（１），（２ｋ＋３）ｔｎ＋１）（第二のパラメータは１の値に設定される）。
ＭＭｕｌ（ｓ，１）の計算が、１の値をメモリ１４内の特定のアドレスに設定することによって、又は第二のパラメータがその中で１の値に設定されるブロックの特別なシーケンスによって達成され得るように、乗算器ブロック１２の入力パラメータはメモリ内のアドレスとなっている。
【００２６】
乗算器ブロック１２により用いられるモンゴメリー・プロセスは、ｎを法とする従来の結果に適合する、０と２ｎ−１の間に含まれる結果を生じる。ＭＭｕｌ（ｓ，１）の演算は従来の結果を与える。
【００２７】
乗算器ブロック１２は２ｎを法とするデータを取り扱い、加算器ブロック１３は従って２ｎを法とする加算をしなければならない。それはこれらの加算を多倍精度加算器、多倍精度減算器、及び多倍精度比較器を用いて行なう。従って、二つの数ａとｂのモジュラー加算の演算ａ＋ｂ  ｍｏｄ  ２ｎは次のように実行される。
ｔ＝ａ＋ｂを計算する
もしｔ≧２ｎならば、ｔ＝ｔ−２ｎを計算する
ｒｅｔｕｒｎ  ｔ
ここでｔは加算結果を含む変数である。
【００２８】
図２は上記のプロセスの演算Ｓ←ｐｉ．ｑ＋（ｍｉｎ＋Ｓ）／ｒを実行するために、乗算器ブロック１２により用いられる乗算−加算セルの一例である。該セルはその性能を改善するため、パイプライン方式で実行される。パイプラインは、クリティカルパスを減らし、従って（理論的にはｒにおける加算器の）最大動作周波数を増加させるために、論理フェーズ同士の間へレジスタのバリアを加えることにある。
【００２９】
基本的構成要素のパイプラインの深さは、その内部レジスタの数により定義される。我々は出力レジスタはカウントしない。
【００３０】
図２において与えられる例は、深さｐを持つパイプライン方式で実行される乗算−加算器１を我々が自由に使うことを前提としている。
【００３１】
特にそれは一組の論理−レジスタの対（ｌｉ，ｒｉ）を含む。これらの対の数ｐは特に、パイプライン方式で実行される乗算−加算器の最大周波数Ｆ１ｍａｘが、加算器の最大周波数Ｆ２ｍａｘ以上であって、これら二つの周波数の値が共に出来るだけ近いように選ばれる。
【００３２】
パイプライン方式で実行される乗算−加算器の最大動作周波数が、ｐステージの内のただ一つの実行時間の逆数により与えられるのに対して、乗算−加算器の最大動作周波数は、乗算−加算演算の実行時間の逆数により与えられる。最適な演算のために、我々は加算器の実行時間を与える加算器の最大周波数を決定し、そして我々は乗算−加算器を、該加算器の実行時間以下ではあるが、それに出来る限り近いｐ個の横断時間のステージへと細分する。
【００３３】
乗算−加算器２１の入力は三つの数字、ｐｉ，ｑｊ，及びｖｊに対応し、出力はＬＳＢ（ｐｉｑｊ＋ｖｊ）及びＭＳＢ（ｐｉｑｊ＋ｖｊ）に対応する数字の対である。該出力は二つの数字内に含まれている。
【００３４】
乗算−加算器の結果は、参照番号２２である三入力の加算器に伝送される：数字＋数字＋桁繰上げ→数字＋桁繰上げは、周波数Ｆ２ｍａｘにおいて１サイクル（パイプライン０）内で動作する。
【００３５】
ｃのストレージに対応するＴｅｍｐレジスタは次の計算に必要とされる。：ｃと次のＬＳＢとの加算及び前の桁繰上げ。
【００３６】
データ（数字ｐ×Ｑ＋Ｖ）は従って、桁繰上げの伝播と同じ方向に、（最）下位ビットを先頭にして各サイクルにおいて連続して出力される。
【００３７】
図３は乗算の下部に適合する装置３と、レジスタ及びマルチプレクサを含む装置５とを有する、乗算器ブロック１２の一例を説明している。
【００３８】
この例において、回路の主要な構成要素は：パイプライン方式で実行される乗算−加算器２１、参照番号２２の三入力を有する加算器、下部の乗算器２３及び、２４で示される２ビット＋１ビット〜２ビットの加算器、２５で示されるｎｒｅｇ−ｍａｘ−１レジスタのバリア及びマルチプレクサである。
【００３９】
マルチプレクサ及びレジスタの数は、とりわけ回路に固有のデータ、パイプラインｐとｋの深さ、及びデータ数字の数に依存する。
【００４０】
図３の例において、ｎｒｅｇ−ｍａｘ−１レジスタのバリア及びマルチプレクサ（参照番号２５の構成要素）は、特に乗算−加算器１へのデータ入力を遅らせるように設計される。
【００４１】
乗算下部−構成要素３
アルゴリズムのメインループ内で、各反復において我々はｒで除算可能な量Ｓ＋ｍｉＮを表現する数字であるｍｉを決定する。
【００４２】
ｍｉは与えられた母数Ｎに関する全てに対して一度予め計算された、定数Ｎ’を有するＳの（最）下位ビットの部分的な乗算により決定される。この乗算において、下部のみが我々に関係する。我々はこのｒを法とする演算を実行する。
【００４３】
この演算は加算よりも遅く、それは又パイプライン方式で実行される。我々はこの演算子のパイプラインの深さをｋと呼び、そしてｋ<ｐであることを前提とする。
【００４４】
ラップアラウンド、待ち時間、及び追加のレジスタ
従来の乗算ａｉＢ＋Ｔ→Ｓ，（１），から乗算及びシフト（ｍｉ×Ｎ＋Ｓ）／ｒ→Ｔ，（２），への変化、及び遅れが同じではない（２）から（１）への変化の二つのケース間の識別が行なわれる。
【００４５】
この遅れは特に、場合により使用されるべきレジスタの数：ｎ’ｒｅｇ又はｎｒｅｇｋを決定する。従って例えば、（２）から（１）への変化の際、及びｐ＋２≦ｎの場合（ｎ’ｒｅｇが定義される場合）に、使用されるべきレジスタの数はｎ’ｒｅｇである。我々はｎｒｅｇ−ｍａｘ−１を有するため、ｎｒｅｇ−ｍａｘ−１−ｎ’ｒｅｇへジャンプする必要がある。これはそれに応じて配置されるマルチプレクサを用いて行なわれる。
【００４６】
（１）から（２）への変化
（１）と（２）の乗算−加算を何ら時間的ロスなしに（如何なる待ち時間も加えることなく）つなぐことが出来るように、我々は乗算途中の全ての数字をカバーする前にｍｉを決定する必要がある。
【００４７】
従って条件：ｐ＋ｋ＋２≦ｎを得ることが望ましい。
【００４８】
実際に、乗算−加算結果の（最）下位ビットは、インデックス数字ｐ＋１が乗算−加算器の入力において現れるときに利用可能である。
【００４９】
加算はそれに続くサイクルの間に行なわれる。Ｓ０が利用可能であり、ｍｉの計算が従って開始できる。
【００５０】
ｋ＋１回の追加的クロック信号ストローク後に、ｍｉは下部の乗算器の出力において利用可能である。従ってそれは次のクロック信号ストロークにおいて、乗算−加算器への入力として使用され得る。これは条件ｐ＋ｋ＋２≦ｎを説明する。
【００５１】
ラップアラウンド
いかなる時間ロスもなく（１）と（２）の乗算−加算を共につなぎたい場合、我々はｐ＋ｋ＋２≦ｎを選択する。
【００５２】
この場合、データｍｉは現在の乗算−加算の数字のトラバースが終了する前に利用可能である。我々はこの値を乗算−加算器へのその入力を遅らせるためにラップアラウンドする。我々は次にこの値の必要なラップアラウンドの数に相当する、ｎｒｅｂｋ＝ｎ−ｐ−ｋ−２を定義する。
【００５３】
ｎｒｅｂｋ＝０である特定の場合、データｍｉは乗算−加算器の新たな入力と同期する。
【００５４】
しかしあらゆる場合に、Ｎの全ての数字に対して入力が同じであるように、我々はｍｉの値をｎ回ラップアラウンドする。
【００５５】
反対にｎ−ｐ−ｋ−２が負である場合、これはｍｉの計算における遅れに相当し、従って待ち時間を更に加える必要がある。
【００５６】
待ち時間
条件ｐ＋ｋ＋２≦ｎが得られないとき、これは出力が入力に対して遅れることを意味し、データを同期させるために待機時間（待ち時間）が加えられる。
【００５７】
これらの待ち時間の間、（（Ｓの最後の桁繰上げを考慮に入れるため）我々が新しい入力０として受け止める、という点において）入力は止められ、計算は既に入力されたデータに関して続く。
【００５８】
この場合（ｐ＋ｋ＋２>ｎ）、我々はｎｌａｔｋ＝ｐ＋ｋ＋２−ｎを定義する。このサイズは、新たなデータが乗算−加算器に与えられる前に適用されるべき待ち時間のストローク数を表わす。
【００５９】
ｍｉが決定されると直ちに、それは乗算−加算用の入力として使用される。Ｓ０に関する限り、それはｍｉよりも前に決定される必要があり、そしてｍｉが計算されるまで（Ｓ１、Ｓ２．．．と一緒に）格納されなければならない。
【００６０】
この理由のため、我々は乗算−加算器の入力における結果の到着を遅らせるようにレジスタを更に加える。
【００６１】
追加のレジスタ
二つの可能なケースが存在する。ｐ＋ｋ＋２がｎよりも大きいか小さいかによって、加えられるレジスタの数及び利用法は同じではない。
【００６２】
ケース１：ｐ＋ｋ＋２≦ｎ
この場合、Ｓ０とｍｉのグループはデータ数字のトラバースの終了前に決定される。
【００６３】
ｍｉに関してはラップアラウンドにおけるセクションを参照されたい。我々は上記の方法をラップアラウンドのセクションにおいて使用する。
【００６４】
Ｓ０に関して我々は乗算−加算器の入力におけるその到着を遅らせ、それによってシフトレジスタを更に加える。
【００６５】
次に我々はｎｒｅｇをｎｒｅｇ＝ｎ−ｐ−１によって定義する。この数量は乗算−加算結果の最下位ビットの到着を次の（最）下位データと同期させるために、更に加えられるべきレジスタの数に相当する。
【００６６】
ケース２：ｐ＋ｋ＋２>ｎ
ｐがｎよりも大きいか否かによって二つの下位ケースが存在する。実際、ｐの値がどうであろうとｍｉはＳ０の後に決定されるであろう。
【００６７】
従って我々はレジスタを更に加えることにより、乗算−加算器の入力におけるＳ０の到着を遅らせる。レジスタのこの数は従って下部の乗算演算子のパイプライン深さである、ｋのみに依存するであろう。
【００６８】
この場合、我々は乗算器の入力におけるＳ０の到着を遅らせるために、更に加えられるべきレジスタの数である、ｎｒｅｇｋ＝ｋ＋１を定義する。
【００６９】
（２）から（１）への変化
ここで、我々は（２）から（１）への変化に関心を持つ。決定されるべきｍｉがない場合、その代わりにシフト（ｒによる除算）を考慮に入れる必要があろう。
【００７０】
前と同じように、結果の到着は新しいデータの入力と同期させられる。ここで、ｐの数量のみが重要であり、ｍｉを決定する必要はなく、そしてｋは介在しない。
【００７１】
それに反して、我々はシフトを考慮に入れる（すなわち、我々は（最）下位ビットとして、ゼロであるｔ−１よりもむしろｔ０を考慮する）。これは追加のパイプラインのレベルとして見ることが出来る。
【００７２】
追加のレジスタ及び待ち時間
ｐ＋２>ｎか否かによって、前と同様に二つのケースの間で識別が行なわれる。
【００７３】
ケース１：ｐ＋２≦ｎ
この場合、ｔ０はデータ数字のトラバースの終了前に利用できる。従って我々は遅れを考慮に入れるためにレジスタを更に追加する。次に我々は遅れを考慮に入れるために更に追加されるべきレジスタの数を示すｎ’ｒｅｇ＝ｎ−ｐ−２を定義する。
【００７４】
ケース２：ｐ＋２>ｎ
この場合、ｔ０はデータ数字のトラバースの終了後に利用できる。従って、我々は新しいデータの入力を遅らせる。これは前のように待機ストローク（待ち時間）を更に追加することにより行なわれる。我々は適用されるべき待機ストロークの数を表わすｎ’ｌａｔ＝ｐ＋２−ｎを定義する。
【００７５】
補足の加算器及びラップアラウンド
ｔｎの決定はｓｎ＋１とｃの加算によって得られ、ｓｎ＋１≦２、ｃ≦１である。このために、我々は２ビット＋１〜２ビットの（論理）加算器（ｔｎ≦３）（構成要素２４で示される）を備える。
【００７６】
Ｔの計算において、シフトはレジスタの使用を節減する方法である。それはｓｎ＋１を格納するために用いられる。この値はｃが決定されるまで格納され、次にｓｎ＋１の格納レジスタを開放するためにその二つの加算が行なわれる。
【００７７】
従って我々はｓｎ＋１のために必要なラップアラウンドの数である、ｎｒｅｂ＝ｎ＋ｎｌａｔｋ−１を定義する。
【００７８】
修正パラメータ
構成要素の最終的な設計は特に、パイプラインｐとｋの深さ及び、それに対して最初に計画された長い整数における数字ｎの数に依存する。特に、更に加えられるべきレジスタの数は、それが（１）から（２）への変化において、（２）から（１）への変化における場合と同じではないため微妙な点である。
【００７９】
次の総括表１は数量ｐ、ｋ、及びｎを前に定義された修正パラメータと関連づける。
【００８０】
【表１】
2008304921.tif 000003
【００８１】
実際には、更に加えられるべきレジスタの数はｎｒｅｇ−ｍａｘ＝ｍａｘ（ｎｒｅｇｋ，ｎｒｅｇ）により定義され、ｐ＋ｋ＋２≦ｎの場合にはｎ−ｐ−１に等しく、そうでない場合にはｋ＋１に等しい。特に、ｎｒｅｇ−ｍａｘ≧１である。
【００８２】
より少ないレジスタしか要さないステップは、レジスタのストリングを短くし、マルチプレクサを更に加えることにより行なわれる。
【００８３】
図３に記述されたシーケンス
演算のシーケンスの一例は図３に関連して記述されている。我々は次のクロック・ストロークを制御するために、現在のクロック・ストロークの終りにおけるマルチプレクサの状態を定義する慣例を採用する。
【００８４】
一般的なマルチプレクサの挙動
待ち時間がここに介在する。事実、待ち時間が存在するか否かによって、状態の変化は同時には生じない。
【００８５】
しかしながら、マルチプレクサの一般的な挙動を定義するために、回路の待ち時間修正パラメータ（ｎ’ｌａｔ及びｎｌａｔｋ）を用いることができる。
【００８６】
確かに、Ｂの初期値ｎ’ｌａｔを伴う、｜Ｂ｜＝ｎ＋１＋ｎ’ｌａｔはゼロであることが想定され得る。（明らかにａｏＢの計算を除く。）
【００８７】
同様に、Ｎの初期値ｎｌａｔｋを伴う、｜Ｎ｜＝ｎ＋１＋ｎｌａｔｋはゼロであることが想定され得る。
【００８８】
更に、我々は待ち時間（Ｂの初期値０のｎ’ｌａｔ）を考慮に入れない、ａｏＢの初期計算の特定の場合を分離する。
【００８９】
次に、この特定の場合が過ぎた後、我々は乗算−加算器の入力において連続的に与えられるデータが、２ｎ＋２＋ｎ’ｌａｔ＋ｎｌａｔｋのデータの組にグループ化されることに注目する。ｎｌａｔｋ＋ｎ＋１は最初にデータｍｉ及びＮｊに対応する。ｎ’ｌａｔ＋ｎ＋１は最後にデータａｉとｂｊに対応する。
【００９０】
これは２ｎ＋２＋ｎ’ｌａｔ＋ｎｌａｔｋの期間を有するマルチプレクサの周期的動作を伴うであろう。
【００９１】
ｍｕｘ１
ｍｕｘ１は乗算−加算器に関して考慮されるべき入力のタイプを象徴する、二つの状態のマルチプレクサである。該二つの状態は：
−  ０：ｘ＝ａｉ及びｙ＝ｂｊが乗算−加算器の入力として考えられる。
−  １：ｘ＝ｍｉ及びｙ＝Ｎｊが乗算−加算器の入力として考えられる。
【００９２】
定数ｎ’ｌａｔ及びｎｌａｔｋの使用は特に、状態の変化はＢ（又はＮ）の全ての数字がトラバースを終了した時に生じるということの確認を可能にする。
【００９３】
ａ０に対して、我々は初期値０のｎ’ｌａｔを考慮に入れない。計算はデータａ０ｂｎ’ｌａｔで直接始まる。
【００９４】
従って初期に０に設定（リセット）されたｍｕｘ１は、クロックの最初のｎストロークの間はこの状態に留まり、次にｎ＋１回目のストロークにて状態１に移る。
【００９５】
このｎ＋１回目のストロークの終りに、乗算−加算器の入力に与えられるデータはａ０及びｂｎに設定され、そしてＢの全ての数字は既にトラバースを終了しているであろう。
【００９６】
ｍｕｘ１はこのクロック・ストロークの終りには１であり、従って次のクロック・ストロークの終りには、ｍｉおよびＮ０が乗算−加算器の入力において与えられるであろう。
【００９７】
クロック・ストロークに依存するｍｕｘ１の一般的挙動は、次のステップにより要約され得る。
もしｃｌｏｃｋ<ｎ＋１であれば、ｍｕｘ１＝０
そうでない場合：
もし（ｃｌｏｃｋ−（ｎ＋１）ｍｏｄ（２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔ））<ｎ＋１＋ｎｌａｔｋならば、ｍｕｘ１＝１
そうでなければｍｕｘ１＝０
【００９８】
ｍｕｘ２
ｍｕｘ２はそのときに加算ｓｎ＋２＋ｃが実行される必要がある時間を象徴する、二つの状態のマルチプレクサである。ｓｎ＋２はＳｔａｂ１に格納されることに注意されたい。
【００９９】
更に、この加算が行なわれるとき、新たな加算が始まるため、三入力の加算器の桁繰上げは０に初期化されなければならない。該二つの状態は：
−  ０：加算ｓｎ＋１＋ｃを行なうことが出来ず、ｃは未決定。
−  １：入力ｓｎ＋１とｃが次のクロック・ストロークにおいて加えられるように設定され、三入力の加算器の桁繰上げは０に初期化される。
【０１００】
この加算は主要な反復（ｉにおけるループ）により一回のみ行なわれ、Ｎの数字に対する第二ループ内に位置する。
【０１０１】
これはｍｕｘ２が決して２度続けて状態１には無いことを意味する。
【０１０２】
その上、この加算はＳｔａｂ１レジスタの値に関係し、それゆえｍｕｘ２の挙動を決定するために関与する、パイプラインｐの深さに関係する。
【０１０３】
積ａ０×ｂ０の（最）下位ビット（ｓ０）は、クロックｐ＋３（＝１（ｌｏａｄ）＋（ｐ＋１）（ＬＳＢにおけるｓ０）＋１（加算器の出力レジスタにおけるｓ０）において、加算器の出力レジスタ内にある。
【０１０４】
ｓｎは従ってクロックｐ＋３＋ｎにおいて、この同じレジスタ内にある。ｓｎはａ０×ｂｎの（最）下位ビットに相当するため、次の入力は従ってＮ及びｍｉに対する数字である。
【０１０５】
そのとき、我々はｔｎを決定するためにｓｎ＋１に加えられるべき、正しい桁繰上げ値を有するため、しかしながら加算はｔｎ−１が加算器の出力レジスタ内にある時に行なわれなければならない
【０１０６】
ｍｕｘ２は従ってｔｎ−１が加算器の出力レジスタ内にある時、すなわちクロック・ストロークｐ＋３＋ｎ＋ｎｌａｔｋ＋ｎ＋１＝ｐ＋２ｎ＋ｎｌａｔｋ＋４にある時に、状態１になければならない。（シフトを伴うとき、ｔｎ−１はｍｉ×Ｎｎの計算に対応することを忘れてはならない。）
【０１０７】
周期性により、我々はまたｍｕｘ２の一般的な挙動を説明することができる。
もしｃｌｏｃｋ＝ｐ＋２ｎ＋４＋ｎｌａｔｋ  ｍｏｄ  ２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔならば、ｍｕｘ２＝１
そうでなければｍｕｘ２＝０
【０１０８】
ｍｕｘ３
Ｎの数字に対するループの間、ｒによる除算を考慮に入れるために、右へのシフトが出力の数字に対してなされなければならない。
【０１０９】
ｍｕｘ３は（レジスタのジャンプによりモデル化される）シフトが行なわれる時を正に象徴する二状態のマルチプレクサである。該二つの状態は：
−  ０：シフトは行なわれない。
−  １：シフトは行なわれる。
【０１１０】
このインデックスのシフトはレジスタのジャンプによりハードウェアで行なわれる。
【０１１１】
シフトはデータｓｎ＋１がＳｔａｂ１レジスタ内に現れるときに発生する。その時、加算器のレジスタＳはｎｌａｔｋの値に応じて、０（待ち時間のストロークの結果）か、あるいはｔ０の値のいずれかを含む。ｔ０は従来の乗算に対する遅れ時間（ｓ０）を有し、それはこの遅れ時間を挽回するために、レジスタをジャンプさせなければならない。このシフトは従って、ｔｎ−１までのＴの全数字（待ち時間を含む）が決定されるまで実行されなければならない。実際、ｔｎ−１が（すなわち、加算器のレジスタＳ内で）次のクロック・ストロークにおいて決定されるとき、ｔｎはｃとｓｎ＋１の加算によりＳｔａｂ１内で決定され、そしてｔｎ−１はＳｔａｂ２レジスタ内で見出される。次にシフトは終了し、ｔｎ−１及びｔｎのデータは二つの連続したレジスタ内で再び見出される。従ってｍｕｘ３はｎ＋ｎｌａｔｋ＝ｎｒｅｂ＋１ストロークの間、状態１に留まる。
【０１１２】
上述されたように、シフトはそのときｓｎ＋１のラップアラウンド用に使用されるＳｔａｂ１レジスタのジャンプに対応する。ｓｎ＋１のラップアラウンドは従ってシフトと同時に生じる。それゆえｍｕｘ３の状態０から１への変化は又、ｓｎ＋１の値をＳｔａｂ１レジスタ内でラップアラウンドすることが必要であることを示す。このラップアラウンドはｎｒｅｂ回行なわれる。
【０１１３】
当初、ｍｕｘ３は状態０（従来の乗算）にある。それはｓｎ＋１がＳｔａｂ１レジスタ内にあるとき１に変化する。しかしｓｎはクロック・ストロークｐ＋３＋ｎにおいてＳ内にある（ｍｕｘ２の挙動を参照）。従ってｓｎ＋１はストロークｐ＋ｎ＋４においてその同じレジスタ内にあり、次のストローク、ｐ＋ｎ＋５においてＳｔａｂ１内にある。
【０１１４】
周期性により、我々はｍｕｘ３の一般的挙動を結論付ける。
もしｃｌｏｃｋ<ｐ＋ｎ＋５ならば、ｍｕｘ３＝０
そうでなければ、
もし（ｃｌｏｃｋ−（ｐ＋ｎ＋５）ｍｏｄ（２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔ））<ｎｒｅｂ＋１ならば、ｍｕｘ３＝１
そうでなければｍｕｘ３＝０
【０１１５】
これまでの考察はｒｅｂ制御を定義し、説明することを可能にする。
【０１１６】
ｒｅｂ制御
この制御は、ｓｎ＋１がＳｔａｂ１レジスタ内でラップアラウンドされるべき瞬間を表わす。該二つの状態は：
−  ０：ラップアラウンドしない
−  １：ラップアラウンドする
【０１１７】
ｒｅｂの挙動はｍｕｘ３の挙動と同時に説明される。我々は従って、以下を結論付ける。
もしｃｌｏｃｋ<ｐ＋ｎ＋５ならば、ｒｅｂ＝０
そうでなければ、
もし（ｃｌｏｃｋ−（ｐ＋ｎ＋５）ｍｏｄ（２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔｋ））<ｎｒｅｂならば、ｒｅｂ＝１
そうでなければｒｅｂ＝０
【０１１８】
ｍｕｘ４
ｍｕｘ４は新たなレジスタのバリアの部分である、二状態のマルチプレクサである。
【０１１９】
このマルチプレクサが存在する場合、それはｎ’ｒｅｇ又はｎｒｅｇｋレジスタを用いる必要があるか否かを示す。該二つの状態は：
−  ０：全てのレジスタを使用（乗算（２）に対応）
−  １：ｎ’ｒｅｇレジスタを使用（乗算（１）に対応）
【０１２０】
ｍｕｘ４はｔ０がＳ内で決定されるとき、状態１になければならない。我々はクロック＝ｐ＋ｎ＋４においてｓｎ＋１がＳ内に存在することを確認した（ｍｕｘ３参照）。従ってｎｌａｔｋ＋１のクロック・ストローク後に、それはｃｌｏｃｋ＝ｐ＋ｎ＋５＋ｎｌａｔｋにあり、ｔ０はＳ内にある。
【０１２１】
ｍｕｘ４はｔｎがＳｔａｂ１内に入るまで、すなわちｎ＋１クロック・ストロークの間、１に留まらなければならない。
【０１２２】
周期性により、我々はｍｕｘ４の一般的挙動を結論付ける。
もしｃｌｏｃｋ<ｐ＋ｎ＋５＋ｎｌａｔｋならば、ｍｕｘ４＝０
そうでなければ、
もし（ｃｌｏｃｋ−（ｐ＋ｎ＋５＋ｎｌａｔｋ）ｍｏｄ（２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔ））<ｎ＋１ならば、ｍｕｘ４＝１
そうでなければｍｕｘ４＝０
【０１２３】
ｒｅｂｋ制御
ｒｅｂｋ制御は、どの瞬間に下部の乗算器の出力レジスタにおけるｍｉの値をラップアラウンドすることが必要かを示す。
該二つの状態は：
−  ０：ラップアラウンドしない
−  １：ラップアラウンドする
初期にはｒｅｂｋ＝０である。
【０１２４】
ｍ１はクロック・ストロークの最後、ｃｌｏｃｋ＝ｐ＋ｋ＋４において決定される（すなわち、下部の乗算器の出力レジスタ内に存在する）。確かに、ｍ１はクロック・ストロークの最後、ｃｌｏｃｋ＝ｐ＋３におけるレジスタＳ内に存在するｓ０から決定される（ｍｕｘ２参照）。従ってそれはｋ＋１クロック・ストローク後、又はｃｌｏｃｋ＝ｐ＋ｋ＋４において結果を与える、加算器の下部に対する入力として使用され得る。
【０１２５】
従って、我々はこの入力がＮの全ての数字に対して同じであるように、この瞬間から開始して少なくともｎ＋１回は、この値をラップアラウンドする必要がある。Ｂの全ての数字がトラバースされる前にｍ１が決定される場合、ｍ１のために必要なラップアラウンドの数であるｎｒｅｂｋの値を考慮に入れる必要がある。
【０１２６】
ｍ１の合計のラップアラウンド回数は、従って：ｎ＋１＋ｎｒｅｂｋである。
【０１２７】
周期性により、我々はｒｅｂｋの一般的挙動を結論付ける。
もしｃｌｏｃｋ<ｐ＋ｎ＋４ならば、ｒｅｂｋ＝０
そうでなければ、
もし（ｃｌｏｃｋ−（ｐ＋ｎ＋４）ｍｏｄ（２ｎ＋２＋ｎｌａｔｋ＋ｎ’ｌａｔ））<ｎ＋１＋ｎｒｅｂｋならば、ｒｅｂｋ＝１
そうでなければｒｅｂｋ＝０
【０１２８】
一つの実施形態によれば、モジュラー減少装置１は、例えばモジュラー指数演算子のような、他の演算子と結合される。それはまた同じハードウェア・ブロック内で、加算の基本的機能１２とモジュラー乗算の基本的機能１２、及びメモリブロック１４を共有することができる。低減されるべきｘの値は、そのとき他のハードウェア・ブロックの演算子により実行された演算結果であり得る。そしてモジュラー減少の結果は他の演算子のための入力として使用可能である。
【０１２９】
乗算器ブロックと加算器ブロックの構成、及びシーケンサにより実行されるモジュラー減少プロセスは、あらゆるサイズの数に対して働くことを可能にする。暗号システムによって用いられる暗号化キーのサイズが年を追って一様に増加することを念頭に置いて、本発明による装置は非常に大きな数を処理することが出来るという利点を提供する。
【０１３０】
該モジュラー減少装置は、使用される乗算器の非常に良好な性能と柔軟性の恩恵に浴する。
【０１３１】
本発明によるモジュラー減少装置の他の利点は、それが別の計算機能を提案する暗号化構成要素へ容易に組み込まれ得る解決策を提案することである。
【図面の簡単な説明】
【０１３２】
【図１】本発明によるモジュラー減少装置のブロック線図である。
【図２】本発明に従うモジュラー減少装置によって用いられる乗算−加算セルの一例である。
【図３】本発明に従うモジュラー減少装置によって用いられるモンゴメリー・モジュラー乗算器の一例である。
【符号の説明】
【０１３３】
１  モジュラー減少装置
１１  シーケンサ
１２  乗算器、乗算器ブロック
１３  加算器ブロック
１４  メモリモジュール、メモリブロック
１５  ユーザ・アプリケーション
２１  乗算−加算器
２２  三入力の加算器
２３  下部の乗算器
２４  ２ビット＋１ビット〜２ビットの加算器
２５  ｎｒｅｇ−ｍａｘ−１レジスタのバリア及びマルチプレクサ
【図１】
2008304921.tif 000004
【図２】
2008304921.tif 000005
【図３】
2008304921.tif 000006
【外国語明細書】
2008304921000001.pdf