(57)【要約】  ＮｍｏｄＭを決定するための技術が提示され、ここで、Ｎはｎ−ビット幅を有する数値で、また、Ｍはｍ−ビット幅を有する数値である。本技術は、一般に、Ｎ’＝ＮＨ２ｆｍｏｄＭ＋ＮＬを決定することに続いてＮ’ｍｏｄＭを決定することを含む。
2009540394.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ読取り可能な格納媒体に配置され、回路にＮｍｏｄＭを決定させる命令からなるコンピュータ・プログラムにおいて、Ｎはｎ−ビット幅を有する数値で、Ｍはｍ−ビット幅を有する数値であり、前記プログラムは、
Ｎ’＝ＮＨ２ｆｍｏｄＭ＋ＮＬを決定し、
ここにおいて、
ＮＨは、Ｎのより高位な部分からなり、
ＮＬは、Ｎのより低位な部分からなり、および、
ｆは、ＮをＮＨとＮＬへ分ける位置からなり、
Ｎ’ｍｏｄＭを決定する、
ことを特徴とするコンピュータ・プログラム。
【請求項２】
ｆは、Ｎ内に２１．５ｍに対応するビットを含むことを特徴とする請求項１記載のコンピュータ・プログラム。
【請求項３】
Ｎ’ｍｏｄＭを決定する前記命令は、２ｆｍｏｄＭの事前に計算された値にアクセスする命令を含むことを特徴とする請求項１記載のコンピュータ・プログラム。
【請求項４】
Ｎ’ｍｏｄＭを決定する前記命令は、Ｎ’ｍｏｄＭのバレット・モジュール削減を実行する命令を含むことを特徴とする請求項１記載のコンピュータ・プログラム。
【請求項５】
前記Ｎ’ｍｏｄＭのバレット・モジュール削減を決定する前記命令は、ｆｌｏｏｒ（２ｆ／Ｍ）の事前に計算された値にアクセスする命令を含むことを特徴とする請求項４記載のコンピュータ・プログラム。
【請求項６】
Ｎ’ｍｏｄＭを決定する前記命令は、
Ｎ”＝Ｎ’Ｈ２ｆｍｏｄＭ＋Ｎ’Ｌを決定し、
ここにおいて、
Ｎ’Ｈは、Ｎ’のより高位な部分からなり、
Ｎ’Ｌは、Ｎ’のより低位な部分からなり、および、
ｆは、Ｎ’をＮ’ＨとＮ’Ｌへ分ける位置からなり、
Ｎ”ｍｏｄＭを決定する、
ことを特徴とする請求項１記載のコンピュータ・プログラム。
【請求項７】
ｆは、Ｎ’内に２１．２５ｍに対応するビットを含むことを特徴とする請求項６記載のコンピュータ・プログラム。
【請求項８】
Ｎ”ｍｏｄＭを決定する前記命令は、２ｆｍｏｄＭの事前に計算された値にアクセスする命令を含むことを特徴とする請求項６記載のコンピュータ・プログラム。
【請求項９】
Ｎ”ｍｏｄＭを決定する前記命令は、Ｎ”ｍｏｄＭのバレット・モジュール削減を実行する命令を含むことを特徴とする請求項６記載のコンピュータ・プログラム。
【請求項１０】
前記Ｎ”ｍｏｄＭのバレット・モジュール削減を決定する前記命令は、ｆｌｏｏｒ（２ｆ／Ｍ）の事前に計算された値にアクセスする命令を含むことを特徴とする請求項９記載のコンピュータ・プログラム。
【請求項１１】
Ｍは、公開鍵のモジュラを含むことを特徴とする請求項１記載のコンピュータ・プログラム。
【請求項１２】
システムにおいて、
ＮｍｏｄＭを決定する回路であって、Ｎはｎ−ビット幅を有する数値で、Ｍはｍ−ビット幅を有する数値であり、
Ｎ’＝ＮＨ２ｆｍｏｄＭ＋ＮＬを決定し、
ここにおいて、
ＮＨは、Ｎのより高位な部分からなり、
ＮＬは、Ｎのより低位な部分からなり、および、
ｆは、ＮをＮＨとＮＬへ分ける位置からなり、
Ｎ’ｍｏｄＭを決定する、
前記回路、
を含むことを特徴とするシステム。
【請求項１３】
ｆは、Ｎ内に２１．５ｍに対応するビットを含むことを特徴とする請求項１２記載のシステム
【請求項１４】
Ｎ’ｍｏｄＭを決定する前記回路は、
Ｎ”＝Ｎ’Ｈ２ｆｍｏｄＭ＋Ｎ’Ｌを決定し、
ここにおいて、
Ｎ’Ｈは、Ｎ’のより高位な部分からなり、
Ｎ’Ｌは、Ｎ’のより低位な部分からなり、および、
ｆは、Ｎ’をＮ’ＨとＮ’Ｌへ分ける位置からなり、
Ｎ”ｍｏｄＭを決定する、
ことを特徴とする請求項１２記載のシステム。
【請求項１５】
Ｍは、公開鍵のモジュラを含むことを特徴とする請求項１２記載のシステム。
【請求項１６】
前記回路は、Ｎ’およびＮ’ｍｏｄＭを決定する命令を実行するためのプログラム可能な回路を含むことを特徴とする請求項１２記載のシステム。
【請求項１７】
前記回路と同じダイ上に集積され、かつ前記回路に通信可能に結合された複数のプログラム可能なコアをさらに含むことを特徴とする請求項１２記載のシステム。
【請求項１８】
ＮｍｏｄＭを決定するコンピュータで実行される方法において、Ｎはｎ−ビット幅を有する数値で、Ｍはｍ−ビット幅を有する数値であり、前記方法は、
Ｎ’＝ＮＨ２ｆｍｏｄＭ＋ＮＬを決定する段階と、
ここにおいて、
ＮＨは、Ｎのより高位な部分からなり、
ＮＬは、Ｎのより低位な部分からなり、および、
ｆは、ＮをＮＨとＮＬへ分ける位置からなり、
Ｎ’ｍｏｄＭを決定する段階と、
を含むことを特徴とするコンピュータで実行される方法。
【請求項１９】
ｆは、Ｎ内に２１．５ｍに対応するビットを含むことを特徴とする請求項１８記載のコンピュータで実行される方法。
【請求項２０】
前記Ｎ’ｍｏｄＭを決定する段階は、２ｆｍｏｄＭの事前に計算された値にアクセスする段階を含むことを特徴とする請求項１８記載のコンピュータで実行される方法。
【請求項２１】
前記Ｎ’ｍｏｄＭを決定する段階は、Ｎ’ｍｏｄＭのバレット・モジュール削減を実行する段階を含むことを特徴とする請求項１８記載のコンピュータで実行される方法。
【請求項２２】
前記Ｎ’ｍｏｄＭを決定する段階は、
Ｎ”＝Ｎ’Ｈ２ｆｍｏｄＭ＋Ｎ’Ｌを決定する段階と、
ここにおいて、
Ｎ’Ｈは、Ｎ’のより高位な部分からなり、
Ｎ’Ｌは、Ｎ’のより低位な部分からなり、および、
ｆは、Ｎ’をＮ’ＨとＮ’Ｌへ分ける位置からなり、
Ｎ”ｍｏｄＭを決定する段階と、
を含むことを特徴とする請求項１８記載のコンピュータで実行される方法。
【請求項２３】
ｆは、Ｎ’内に２１．２５ｍに対応するビットを含むことを特徴とする請求項２２記載のコンピュータで実行される方法。
【請求項２４】
前記Ｎ”ｍｏｄＭを決定する段階は、Ｎ”ｍｏｄＭのバレット・モジュール削減を実行する段階を含むことを特徴とする請求項２２記載のコンピュータで実行される方法。
【請求項２５】
Ｍは、公開鍵のモジュラを含むことを特徴とする請求項１８記載のコンピュータで実行される方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号演算に関し、さらに詳しくは暗号演算においてフォールディングを用いるモジュール削減に関する。
【背景技術】
【０００２】
暗号は、望まれないアクセスからデータを保護する。暗号は、典型的にはデータに対して数学的な操作（暗号化）を行ない、元のデータ（平文）を理解できなくする（暗号文）。逆の数学的な操作（解読）は、暗号文から元のデータを復元する。暗号は、データの暗号化および解読を越えた広範囲の様々な応用をカバーする。例えば、暗号は、認証（つまり、通信エージェントの同一性を信頼して決定）、デジタル署名の生成などでしばしば使用される。
【０００３】
現在の暗号技術は、集約的な数学的操作に極度に依存する。例えば、多くのスキームは、べき剰余（modular exponentiation）として知られる一種のモジュール演算を用い、それは大きな数にある数の累乗を行ない、モジュラ（modulus：法数）（つまり、剰余は所与のモジュラで除したときの余り）に関してそれを削減することを含む。数学上、べき剰余は、ｅが指数でＭがモジュラである場合、ｇｅｍｏｄＭとして表現される。
【０００４】
概念的に、乗法およびモジュール削減は直線的な演算である。しかしながら、多くの場合、これらのシステムで使用される数のサイズは極めて大きく、プロセッサの固有の語長を著しく越えてしまう。例えば、暗号プロトコルは、１０２４から４０９６あるいはそれより大きいビット長に対するモジュラ演算を要求する一方で、多くのプロセッサは３２あるいは６４ビットの固有の語長を有するに過ぎない。このような大きな数を操作するには、時間の観点から、および演算資源の観点から非常に高価なものになるであろう。
【発明の開示】
【０００５】
上述のように、広範囲の様々な暗号演算は、非常に大きな数および／またはモジュール削減の乗算を含む。計算集中的な演算および暗号システムの高速演算の負担を軽減する様々な技術がここに記述される。これらの技術は、より汎用的な目的、非暗号的な計算設定に適用することもできる。そのような技術の１つは、カラツバ（Ｋａｒａｔｓｕｂａ）乗算として知られている大きな数を乗算するための技術の効率性を改善することを含む。別の技術は、モジュール削減の効率性を改善することを含む。
【０００６】
カラツバ乗算
２つの数の乗算を行なうために広範囲の様々なアプローチが行なわれてきている。教科書的な乗算として知られている共通のアプローチは、オペランドをセグメントに分けて、より小さなセグメント上で乗算操作を行なうことを含む。例として、２つのｎビット幅の数ＡおよびＢを、次のような一組のより小さなサイズのサブセグメントとして表現することができる。              
Ａ＝ａ1２s＋ａ０                                ［１］
Ｂ＝ｂ1２s＋ｂ０                                ［２］
ここで、ａ０およびｂ０項は、ＡとＢのｓ最下位ビットを、ａ１およびｂ１項は、残余の上位ビットを表わす。この表記法では、ａｘとｂｘ中の添字ｘは、数字内のセグメントの順序を表わす（例えば、ａ０は、Ａの最下位ビットを、ａ１は次の上位ビット表わすなど）。
【０００７】
従来の教科書的な乗算を用いると、ＡおよびＢの乗算は、４回のより小さな乗算を用いて計算される。
Ａ×Ｂ＝ａ１ｂ１２２ｓ＋（ａ０ｂ１＋ｂ０ａ1）２s＋ａ０ｂ０    ［３］
【０００８】
カラツバ乗算として知られている乗算技術は、セグメント乗算の回数を削減することができる。例えば、上記ＡおよびＢの乗算における［３］中の項、
（ａ０ｂ１＋ｂ０ａ1）                                ［４］
の結果は、
［（ａ０＋ａ1）（ｂ０＋ｂ１）］−ａ1ｂ１−ａ０ｂ０    ［５］
として計算することができる。
ａ1ｂ１とａ０ｂ０が方程式［３］中で別の項を形成するので、方程式［５］中でａ1ｂ１とａ０ｂ０の値を使用することは、追加計算を強いることを表わすものではない。方程式［３］中の方程式［４］に方程式［５］を代入すると、Ａ×Ｂのカラツバ乗算は次のように計算することができる。
Ａ×Ｂ＝ａ1ｂ１２２ｓ＋（［（ａ０＋ａ1）（ｂ０＋ｂ１）］−ａ1ｂ１−ａ０ｂ０）２s＋ａ０ｂ０    ［６］
この代入によって、２回の乗算に対して２回の加算と１回の乗算で済ませられる。大抵の場合、これは計算効率の上で極めて大きな利益をもたらす。
【０００９】
上記の例において、カラツバ法は、２つのセグメントへ分けた数を乗算した（つまり「２つの項のカラツバ乗算」）。しかしながら、カラツバ法は、他の数のセグメントに適用することもできる。例えば、３つの項のカラツバ乗算は、数値ＡおよびＢに対して次のように定義することができる。
Ａ＝ａ２２２s＋ａ1２s＋ａ０                        ［７］
Ｂ＝ｂ２２２s＋ｂ1２s＋ｂ０                        ［８］
Ａ×Ｂ＝ａ２ｂ２２４ｓ＋ａ1ｂ１２２ｓ＋ａ０ｂ０＋［（ａ２＋ａ1）（ｂ２＋ｂ１）−ａ２ｂ２−ａ１ｂ１］２３s＋［（ａ２＋ａ０）（ｂ２＋ｂ０）−ａ２ｂ２−ａ０ｂ０］２２s＋［（ａ０＋ａ１）（ｂ０＋ｂ１）−ａ０ｂ０−ａ１ｂ１］２s    ［９］
ここで、ＡおよびＢは、それぞれ３つのｓ−ビット・セグメントに分割される。
【００１０】
２項のカラツバ乗算［６］と同様に、３項のカラツバ乗算［９］は、異なる順序のセグメント間の乗算（つまり、ａｘｂｙ）の代わりに同じ順序のセグメント上の乗算（つまり、ａｘｂｘ）および同じ数のセグメントの加算（つまり、ａｘ+ａｙ）を用いた。方程式は５項のカラツバ乗算に対しても定義された。これらのカラツバ方程式は、多くても（ｔ２＋ｔ）／２回の乗算を要求するという属性を共有し、ここでｔは項数である。
【００１１】
カラツバ乗算は、帰納を使用して実行することができる。例えば、次の２項のカラツバ乗算では、
Ａ×Ｂ＝ａ1ｂ１２２ｎ＋（（ａ０＋ａ1）（ｂ０＋ｂ１）−ａ1ｂ１−ａ０ｂ０）２ｎ＋ａ０ｂ０    ［６］
より小さいセグメント乗算は、それぞれカラツバ法を使用して順番に実行することができる。例えば、Ａ×Ｂのカラツバ乗算の実行は、ａ1ｂ１，ａ０ｂ０，（ａ０＋ａ1）（ｂ０＋ｂ１）のカラツバ乗算を含めることができる。これらの乗算は、さらに小さなサブセグメントのカラツバ乗算を含めてもよい。例えば、ａ1ｂ１の決定はサブセグメントの複数の項へａ1とｂ１をセグメントに分けてもよい。
【００１２】
しかしながら、このアプローチにおける潜在的な問題は、異なるサイズのオペランドが生成されるということである。すなわち、（ａ０＋ａ1）項および（ｂ０＋ｂ１）項は両方とも、加算操作からのキャリー（けた上げ）を生成することがある。（ａ０＋ａ1）と（ｂ０＋ｂ１）の結果に続く乗算が追加の固有ワードにあふれ出すことがある。これは、カラツバ法の実行効率の高さを弱めることになる。
【００１３】
「キャリー」問題に取り組むために、図１−図３は、２つのオペランドの最下位ビッツ（bits）上でカラツバ乗算を行ない、次に最上位ビッツ（bits）に基づいて結果を修正するサンプル実行例を示す。図１は、乗算される２つのオペランドＡ１００，Ｂ１０２をより詳細に示す。この例において、各オペランドは、ｎ＋１ビット長であり、ここでｎはあるプロセッサの固有ワードサイズｓの２倍である。この例において、各オペランドは、２つの項と付加的な高位ビットのセグメントに分けられる。例えば、Ａの最下位ｓビッツはａ０を形成し、次の上位ｓビッツはａ1を形成する一方、Ａの最上位ビットは、ａｈを形成する。
【００１４】
図示されるように、カラツバ乗算は、ｓサイズの項上で次のように実行される。
２２ｓａ１ｂ１＋２s［（ａ1＋ａ０）（ｂ１＋ｂ０）−ａ1ｂ１−ａ０ｂ０］＋ａ０ｂ０      ［１０］
その後、その結果は、最上位ビットａｈ，ｂｈの値に基づいて調整される。例えば、図示されるように、その結果は、
２ｎａｈＢ［ｂ１：ｂ０］                    １０６［１１］
および
２ｎｂｈＡ［ａ１：ａ０］                    １０８［１２］
だけ増やされる場合がある。
言い換えれば、ａｈが「１」である場合、その結果は、ｎビットだけシフトしたｂｌ：ｂ０のｎ−ビットによって増加させられる。同様に、ｂｈが「１」である場合、その結果は、ｎビットだけシフトしたａｌ：ａ０のｎ−ビットによって増加させられる。例えば、これらの調整は追加の操作として実行される。
ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２ｎａｈＢ［ｂ１：ｂ０］
ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２ｎｂｈＡ［ａ１：ａ０］
あるいは加算に続く分岐として、
ｉｆ（ａｈ）ｔｈｅｎ  ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２ｎＢ［ｂ１：ｂ０］
ｉｆ（ｂｈ）ｔｈｅｎ  ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２ｎＡ［ａ１：ａ０］
が実行される。
最後に、もしａｈ，ｂｈ両方が「１」である場合、その結果は２ｎ（つまり、ａｈｂｈ）だけ増加させられる。これは、例えば、ブランチを使用して次のように実行される。
ｉｆ（ａｈｂｈ）ｔｈｅｎ  ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２２ｎ
加算および１またはそれ以上のブランチ・ステートメントのこのコンビネーションは、キャリーがより低いレベルの帰納へ下流伝搬するのを防ぐことができる。
【００１５】
図２は、４６９の値を有するＡ１００を３６９の値を有するＢ１０２と乗算させる上述した手続の操作を示す。図示されるように、最上位ａｈ，ｂｈビットを除いて、Ａ［２ｓ−１：０］とＢ［２ｓ−１：０］のカラツバ乗算は、２４，０６９の値を生成する。この値は、最初にａｈのために１０７，５２５に調整され、それからｂｈのために７８，５９７に調整される。最後に、ａｈ，ｂｈ両方が「１」であるので、２２ｎ＝１６に対する最上位ビットが最終的な答えである１７３，０６１を生成するために加えられる。再び、ａｘｂｘの値は、カラツバ技術の再帰的な適用によって決定することができる。ａｈ，ｂｈビットを切り取ることによって、その再帰は、便利な同じサイズのオペランド上で操作する。
【００１６】
図３は、再帰的なスキームでのこのカラツバ技術の実行を示す。上述するように、オペランドＡ，Ｂのカラツバ乗算は、Ａ［ｎ：０］とＢ［ｎ：０］の乗算によって行なわれ（１１４）、ＡとＢの最上位ビットａｈ，ｂｈに対する訂正１１６が続く。その演算結果値は、再帰スタックに返される（１１８）。
【００１７】
オペランドの長さがプロセッサ固有のワードサイズよりはるかに長い場合、カラツバ乗算は特に望ましい。例えば、プロセッサは、より長いオペランドと比較して単にｓのワードサイズを有している。ｎがｓに接近する場合、カラツバの効率は低下し、教科書的な乗算がより魅力的になる。このように、図３に示されるように、再帰１１２の現在の深さに依存して、教科書的乗算１２０，１２２あるいはカラツバ１１４，１１６，１１８のいずれかの手順を使用することになるであろう。実際上、教科書的乗算を使用して、最終２レベル（つまりＬ＝２）を再帰的に行なうことにより、最良の総合特性を提供するであろう。
【００１８】
図１−図３は、実行例を示すが、一方多くの変形が可能である。例えば、図１−図３において、各カラツバ項は、ｓ−ビット長として示されている。しかしながら、その項は、同じビット長である必要がなく、単一の固有ワードを占有する必要もない。同様に、ａｈ，ｂｈが単一のビットとして示されているが、他の実行例では、ａｈ，ｂｈが複数のビットを含んでいてもよい。
【００１９】
上述するように、異なる項数（例えば、２，３，５）に対して異なるカラツバ方程式が定義される。標準カラツバ分解（canonical Karatsuba decomposition）は、次の６つの長さの数値である。
ｎ＝２ｋ
ｎ＝３・２ｋ
ｎ＝３２・２ｋ
ｎ＝３３・２ｋ
ｎ＝３３・２ｋ
ｎ＝５・２ｋ
ここで、ｎは数値の長さであり、ｋは整数である。
【００２０】
カラツバ分解を最適化するために、数値にゼロを付加し、より大きな標準形に適合するようにしてもよい。どの標準カラツバ分解を作業ｗに使用すべきかを識別するために、各々に対し計算され、最小のものが選択される。
【数１】
2009540394.tif 000003
【００２１】
ｗ値は、異なるｎ値に対して計算されてもよい。その結果は、例えば、所与のｎに対する最小のｗ値に基づいて、所与の数値を付与する量を示すルックアップ表を形成するために使用してもよい。
【００２２】
フォールディングを用いるモジュール削減
乗算に加えて、多くの暗号スキームにはモジュール削減（例えば、ＮｍｏｄＭの計算）を含む。モジュール削減操作の費用を削減するために、いくつかのシステムは、バレット（Ｂａｒｒｅｔｔ）のモジュール削減として知られている技術を使用する。バレットは、本質的に、商の推定を計算する。
ｑ＝ｆｌｏｏｒ（ｆｌｏｏｒ（Ｎ／２ｍ）μ／Ｍ）  ［１３］
ここで、ｍはモジュラＭの幅で、μは次式で決定される定数である。
μ＝ｆｌｏｏｒ（２２ｎ／Ｍ）                    ［１４］
ここでｎは数値Ｎの幅である。ＮｍｏｄＭの値は、Ｎ−ｑＭを計算することにより決定され、最終値がＭ未満であることを保証するために必要な場合、Ｍだけ減じる最終減算が続く。バレットの効率への寄与はμに対する予め計算された値にアクセスする能力である。すなわち、μの値は、Ｎの特定の値にアクセスしなくても、Ｎのサイズのみに基づいて決定される。
【００２３】
バレットのモジュール削減のような技術は、モジュール削減の費用を減少させることができる。図４−図６は、モジュール削減の計算上のコストをさらに低減することができる技術を示す。図４は、特に、数値Ｎ２０２をより小さな幅数Ｎ’２０６に「畳込む（ｆｏｌｄ）」技術を示す。より小さな幅数にもかかわらず、フォールディング（folding）操作は、Ｎ’ｍｏｄＭがＮｍｏｄＭと同じであるようなＮ’を決定する。その後、古典的なバレット・モジュール削減のような従来の操作は、より小さなＮ’上で行なわれる。オペランドＮを「縮める（shrinking）」ことによって、後続の操作は、モジュラの剰余を決定するために使用される乗算を削減することができる、より小さなサイズの数値を含む。加えて、数値Ｎがより大きくなれば、効率がよくなることがより明白になる。例えば、サンプルテストでは、５１２ビットサイズのＮに対しては速度が２７％増加し、４０９６ビットサイズのＮに対しては１７７％の速度増加にジャンプすると推定される。
【００２４】
より詳細には、図４は、ｎの幅を有する数値Ｎ２０２、および、ｍの幅を有するモジュラＭ２００を示す。ＮｍｏｄＭを決定するために、「フォールディング」操作２１２は、ＮからＮ’を生成する。図示されるように、フォールディング２１２がフォールディング・ポイントｆで生じ、それは、Ｎをより高位のＮＨおよびより低位のＮＬの部分へ線引きをする。例えば、フォールディング・ポイントｆは、モジュラの長さおよびＮの長さの中央ポイントになるように選ばれてもよい。例えば、Ｎが２ｍ（モジュラ幅の２倍）の幅を有すると仮定すると、フォールディング・ポイントは、２１．５ｍによって識別されるビット位置にあってもよい。このようなフォールディング・ポイントは、Ｎ’の結果幅を最小限にすることができる。すなわち、ＮＨまたはＮＬを拡張あるいは縮小するいずれかの方向へフォールディング・ポイントを移動させることにより、実際にＮ’のサイズが増加することになる。
【００２５】
フォールディング・ポイントに基づいて、Ｎ’は次のように決定することができる。
Ｎ’＝ＮＨ２ｆｍｏｄＭ+ＮＬ                ２１２［１５］
その後、より小さなＮ’は、例えば古典的バレット技術を使用して、モジュール削減を行なうために使用される。
【００２６】
図示されるように、Ｎ’の決定２１２は、２ｆｍｏｄＭ２０８（Ｍ’と称される）の項を含む。２ｆｍｏｄＭの値は、特定のＮ値に配慮をせずに事前に計算することができる。Ｍとｆの様々な値に対するこの値を事前に計算しておくことは、高価な乗算を時間的に重要でない期間へ移すことにより、Ｎ’のリアルタイム計算を促進させる。Ｍとｆの値に対して事前に計算された値は、高速アクセスのためにメモリ中のテーブルに格納することができる。ＮＨ（２ｆｍｏｄＭ）の乗算は、上述するように、例えば、カラツバ乗算を使用して達成される。
【００２７】
図示するように、図５は、Ｎが２５２（１１１１，１１００ｂ）の値を有する８ビット長の数で、Ｍが１３（１１０１ｂ）の値を有する４ビット長の数である場合のフォールディング例を示す。図示されるように、フォールディング・ポイントはｆ＝２１．５ｍ＝２６として選択される。Ｎ’の計算は、９６の値を生成する。図示されるように、Ｎとそのフォールドされた対Ｎ’はモジュラ１３に対するのと同じモジュラの残余５を生成する。Ｎ’のモジュール削減は、バレットのような様々なモジュール削減・アプローチのうちのどれでも使用して行なうことができる。
【００２８】
図６は、上述の技術を使用して、ＮｍｏｄＭの完全な決定例を示す。この例において、Ｎ２０２は幅ｎ＝４ｓであり、また、Ｍ２０４は幅ｍ＝２ｓである。図示のように、フォールディング・ポイントｆは２３ｓである。図示されるように、Ｍ’＝２３ｓｍｏｄＭ２２２に対する事前の計算は、（Ｍ’）（ＮＨ）２２４を決定するにために用いられる。図６は、ＮＨをｆｌｏｏｒ（Ｎ／２３ｓ）の値として表現する一方で、ＮＨの値は、ＮＨ＝Ｎ［４ｓ−１：３ｓ］を設定することによってより速く獲得することができる。（Ｍ’）（ＮＨ）の値２２４は、Ｎ’の計算を完了するためにＮＬ２２６に加えられる。再び、図６は、Ｎｍｏｄ２３ｓとしてＮＬを表現しているが、ＮＬの値は、ＮＨ＝Ｎ［３ｓ−１：０］を設定することによってより速く獲得することができる。
【００２９】
Ｎ’の決定の後に、Ｎ’ｍｏｄＭは、古典的バレット・リダクションを使用して計算することができる。この場合、バレット・リダクションは、２３０，２３４で次式のように計算される。
Ｒ＝Ｎ’−ｆｌｏｏｒ（ｆｌｏｏｒ（Ｎ’／２２ｓ）（μ／２ｓ）Ｍ      ［１６］
ここで、μは、ｆｌｏｏｒ（２３ｓ／Ｍ）として決定される。Ｍ’の値のように、μの値は、ｓやＭの様々な値に対して事前に計算される。この事前計算は、高価な操作をリアルタイム処理が必要でない期間へ再び時間シフトすることができる。
【００３０】
結果Ｒ２３６は、モジュラＭ２００より大きくてもよい。この比較的まれな場合に、Ｒ＝Ｒ−Ｍの減算は、Ｒ＜Ｍを保証するために使用される。
【００３１】
単一のフォールディング操作は、モジュール削減の効率およびリアルタイム特性を著しく改善する。図７に示されるように、反復フォールディングは、乗算の総数およびＡＬＵ操作（つまり、加算、減算、およびシフト）に関して一層の効率改善を提供する。図示されるように、Ｎ  ２０２はＮ’２０４に再びフォールディングされる。その結果Ｎ’は、多くの場合幅ｆのものである。Ｎ’が幅ｆ＋１のものである場合、Ｎ’＝Ｎ’−（Ｍ２ｍ）の減算操作は、必ずしも必要ではないが、Ｎ’を「整える（trim）」ために使用されてもよい。図示されるように、付加的なフォールディング操作は、Ｎ’をＮ”２０６に変形し、ここでＮ”ｍｏｄＭ＝Ｎ’ｍｏｄＭである。この第２のフォールディングは、再び計算上の効率を向上させる。
【００３２】
異なるフォールディングの反復中に使用されるフォールディング・ポイントは、第１の反復に対する２１．５ｍから第２に対する２１．２５ｍへ移動する。より一般的には、所与の反復に対するフォールディング・ポイントは、２（１＋２∧−ｉ）ｍとして決定され、ここでｉは反復番号である。
【００３３】
図７は、２つのフォールディングを示すが、付加的なフォールディングも可能である。しかしながら、付加的なフォールディングは、リターンを減らし、および／または、実際に乗算操作の回数を増加させるかもしれない。
【００３４】
べき剰余の実行例
上述された技術は、様々な暗号演算を行なうために使用することができる。例えば、上述されたカラツバ乗算およびフォールディング技術は、べき剰余を実行するために組み合わせることができる。
【００３５】
べき剰余はｇｅｍｏｄＭを決定することを含む。べき剰余の実行は、様々な暗号アルゴリズムの中心にある。例えば、ＲＳＡでは、公開鍵は、公開指数、ｅ−公開、およびモジュラＭによって形成される。秘密鍵は、秘密指数、ｅ−秘密、およびモジュラＭによって形成される。メッセージ（例えば、パケットまたはパケットのペイロード）を暗号化するために、次の操作が行なわれる。
ｃｉｐｈｅｒｔｅｘｔ＝ｃｌｅａｒｔｅｘｔｅ−ｐｕｂｌｉｃｍｏｄＭ    ［１７］
メッセージを解読するために、次の操作が行なわれる．
ｃｌｅａｒｔｅｘｔ＝ｃｉｐｈｅｒｔｅｘｔｅ−ｐｒｉｖａｔｅｍｏｄＭ    ［１８］
【００３６】
べき剰余を行なうための１つの手続きは、指数ｅ中のビットを左から右へ順に処理する。Ａ＝１の初期値から始めて、その手続きは、遭遇した各「０」ビットに対する値を２乗する（つまり、Ａ＝Ａ＊Ａ）。各「１」ビットに対して、この手続きは、その値を２乗し、ｇを乗じる両方を行なう（つまり、Ａ＝Ａ＊Ａ＊ｇ）。最終結果は、モジュール削減操作で使用することができる。例えば、３１０１０ｂｍｏｄ５を決定するために、この手続きは、以下のように開始する、ここでｇ＝３、ｅ＝「１０１０」、またＭ＝５である。
Ａ
１
ｅｘｐｏｎｅｎｔ  ｂｉｔ１−１    １＊１＊３      ＝３
ｅｘｐｏｎｅｎｔ  ｂｉｔ２−０    ３＊３          ＝９
ｅｘｐｏｎｅｎｔ  ｂｉｔ３−１    ９＊９＊３      ＝２４３
ｅｘｐｏｎｅｎｔ  ｂｉｔ４−０    ２４３＊２４３  ＝５９０４９
ＡｍｏｄＭ                        ４
非常に大きな数値が乗算された際の終わりでモジュール削減を実行する代わりに、すべての指数ビットあるいはいくつかの指数ビット毎に処理した後にモジュール削減を乗算操作内に挿入するようにしてもよい。例えば、３１０１０ｂｍｏｄ５を決定するために、この手続きは以下のように進む。
Ａ
１
ｅｘｐｏｎｅｎｔ  ｂｉｔ１−１    １＊１＊３      ＝３
ＡｍｏｄＭ                        ３
ｅｘｐｏｎｅｎｔ  ｂｉｔ２−０    ３＊３          ＝９
ＡｍｏｄＭ                        ４
ｅｘｐｏｎｅｎｔ  ｂｉｔ３−１    ４＊４＊３      ＝４８
ＡｍｏｄＭ                        ３
ｅｘｐｏｎｅｎｔ  ｂｉｔ４−０    ３∧２          ＝９
ＡｍｏｄＭ                        ４
特定の実行にもかかわらず、２乗および「ｇ」乗算の双方に、上述されたカラツバ乗算技術を使用することにより、べき剰余を著しく促進させることができる。加えて、フォールディングを使用することで、リダクション操作は、処理資源の使用を著しく軽減させる。
【００３７】
付加的な計算効率は、繰り返し用いられる値を格納することにより獲得することができる。例えば、例として、ｇの値が２つの異なる乗算に必要とされているとする。２０４８ビット指数という現実の世界での例では、ｇを使用する数の乗算ははるかに大きくなる。ｇを含むカラツバ乗算の効率を改善するために、ｇｉ＝（ｇＨ（ｉ）＋ｇＬ（ｉ））という異なる値が反復使用のためにテーブルに格納され、ここで、ｉは、カラツバ再帰の深さを表わす。このキャッシングは、同じ加算を重複して実行する極めて大きいサイクル回数を削減することができる。モジュール削減が同じモジュラを使用して複数回発生する場合、フォールディングで使用されるＭ’およびμのような他で頻繁に用いられる値をキャッシングすることは、さらに特性を向上させるであろう。
【００３８】
１ｋサイズの数を２ｋサイズの数で乗算するような不均等なサイズの数の乗算を行なう場合、付加的な最適化が使用されてもよい。このような乗算が、バレットのｑＭ値を決定する際に、またＮＨ２ｆｍｏｄＭを決定する際に生じることがある。カラツバを利用するために、１ｋ＊２ｋの乗算をｑ＊ｍｈおよびｑ＊ｍｌのような２つの１ｋ＊１ｋの操作へ分割することができる。ｑが両方の操作中で使用されるので、（ｑｈ＋ｑｌ）の値を２度演算する必要はなく、その代り、先の使用のために格納される。
【００３９】
上記は単に例であり、カラツバおよびフォールディング技術を広範囲の様々な他の暗号演算を実行するだけでなく他の汎用的な目的の数学的な適用に使用することができる。
【００４０】
本技術は、様々な方法で、また様々なシステムで実行することができる。例えば、本技術は、専用デジタルまたはアナログ・ハードウェア（例えば、Ｖｅｒｉｌｏｇ（ｔｍ）のようなハードウェア記述言語に上述されたプログラミング技法によって決定される）、ファームウェア、および／またはＡＳＩＣ（特定用途向けＩＣ）またはプログラム可能なゲート・アレイ（ＰＧＡ）中で実行されてもよい。本技術は、またプロセッサ実行のために、コンピュータ読取り可能な媒体上に配置されたコンピュータ・プログラムとして実行されてもよい。例えば、そのプロセッサは、汎用プロセッサであってもよい。
【００４１】
図８に示されるように、本技術は、暗号演算を処理することができるプロセッサ・モジュール３００によって実行されるコンピュータ・プログラムで実現される。図示されるように、モジュール３００は、複数のプログラム可能な処理ユニット３０６−３１２および専用ハードウェア乗算器３１６を含む。処理ユニット３０６−３１２は、コア３０２によって管理される共有メモリ・ロジック３０４からダウンロードされるデータ上でプログラムを実行する。他のプロセッサおよび／またはプロセッサ・コアは、データおよび実行すべき命令を指定してモジュール３００へ命令を送出する。例えば、プロセッサ・コアは、ＲＡＭ３１４に格納されたｇ，ｅ，およびＭ値でのべき剰余を行なうためにモジュール３００へ命令を送出する。コア３０２は、べき剰余プログラムを処理ユニット３０６−３１２にダウンロードし、かつ操作されるべきデータをＲＡＭ３１４から共有メモリ・ロジック３０４へ、そして最後に処理ユニット３０６−３１２へダウンロードするための命令を共有メモリ３０４へ送出することによって応答する。処理ユニット３０６−３１２は、順番に、プログラム命令を実行する。特に、処理ユニット３０６−３１２は、２乗あるいは「ｇ」乗算を行なうために使用されるカラツバ乗算のような掛け算を行なうために乗算器３１６を使用する。最後に、処理ユニット３０６−３１２は、要求コアへ転送するために共有メモリ・ロジック３０４にその結果を戻す。プロセッサ・モジュール３００は、プログラム可能なコアとして同じダイ上に、あるいは異なるダイ上に集積されてもよい。
【００４２】
図８は、上述されたカラツバおよびフォールディング技術を実行するために使用するアーキテクチャ例を単に示す。しかしながら、本技術は、プログラムされた従来の汎用プロセッサのような広範囲の様々な他のアーキテクチャ中で使用することができる。
【００４３】
他の実施例は、次の請求項の範囲内にある。
【図面の簡単な説明】
【００４４】
【図１】カラツバ乗算を示す。
【図２】カラツバ乗算を示す。
【図３】カラツバ乗算の実行例を示すフローチャートである。
【図４】数値Ｎを数値Ｎ’へフォールディングする例を示し、Ｎ≡Ｎである。
【図５】数値Ｎを数値Ｎ’へフォールディングする例を示し、Ｎ≡Ｎである。
【図６】ＮｍｏｄＭの決定を示す。
【図７】数値Ｎの反復フォールディングを示す。
【図８】カラツバ乗算および／またはモジュール削減を実行するアーキテクチャを示す。
【図１】
2009540394.tif 000004
【図２】
2009540394.tif 000005
【図３】
2009540394.tif 000006
【図４】
2009540394.tif 000007
【図５】
2009540394.tif 000008
【図６】
2009540394.tif 000009
【図７】
2009540394.tif 000010
【図８】
2009540394.tif 000011
【国際調査報告】
2009540394.tif 000012