JP5116770B2 - フォールディングを用いるモジュール削減 - Google Patents

Description

本発明は、暗号演算に関し、さらに詳しくは暗号演算においてフォールディングを用いるモジュール削減に関する。

暗号は、望まれないアクセスからデータを保護する。暗号は、典型的にはデータに対して数学的な操作（暗号化）を行ない、元のデータ（平文）を理解できなくする（暗号文）。逆の数学的な操作（解読）は、暗号文から元のデータを復元する。暗号は、データの暗号化および解読を越えた広範囲の様々な応用をカバーする。例えば、暗号は、認証（つまり、通信エージェントの同一性を信頼して決定）、デジタル署名の生成などでしばしば使用される。

現在の暗号技術は、集約的な数学的操作に極度に依存する。例えば、多くのスキームは、べき剰余（modular exponentiation）として知られる一種のモジュール演算を用い、それは大きな数にある数の累乗を行ない、モジュラ（modulus：法数）（つまり、剰余は所与のモジュラで除したときの余り）に関してそれを削減することを含む。数学上、べき剰余は、ｅが指数でＭがモジュラである場合、ｇ^ｅｍｏｄＭとして表現される。

概念的に、乗法およびモジュール削減は直線的な演算である。しかしながら、多くの場合、これらのシステムで使用される数のサイズは極めて大きく、プロセッサの固有の語長を著しく越えてしまう。例えば、暗号プロトコルは、１０２４から４０９６あるいはそれより大きいビット長に対するモジュラ演算を要求する一方で、多くのプロセッサは３２あるいは６４ビットの固有の語長を有するに過ぎない。このような大きな数を操作するには、時間の観点から、および演算資源の観点から非常に高価なものになるであろう。

上述のように、広範囲の様々な暗号演算は、非常に大きな数および／またはモジュール削減の乗算を含む。計算集中的な演算および暗号システムの高速演算の負担を軽減する様々な技術がここに記述される。これらの技術は、より汎用的な目的、非暗号的な計算設定に適用することもできる。そのような技術の１つは、カラツバ（Ｋａｒａｔｓｕｂａ）乗算として知られている大きな数を乗算するための技術の効率性を改善することを含む。別の技術は、モジュール削減の効率性を改善することを含む。

カラツバ乗算
２つの数の乗算を行なうために広範囲の様々なアプローチが行なわれてきている。教科書的な乗算として知られている共通のアプローチは、オペランドをセグメントに分けて、より小さなセグメント上で乗算操作を行なうことを含む。例として、２つのｎビット幅の数ＡおよびＢを、次のような一組のより小さなサイズのサブセグメントとして表現することができる。
Ａ＝ａ₁２^s＋ａ_０ ［１］
Ｂ＝ｂ₁２^s＋ｂ_０ ［２］
ここで、ａ_０およびｂ_０項は、ＡとＢのｓ最下位ビットを、ａ_１およびｂ_１項は、残余の上位ビットを表わす。この表記法では、ａ_ｘとｂ_ｘ中の添字ｘは、数字内のセグメントの順序を表わす（例えば、ａ_０は、Ａの最下位ビットを、ａ_１は次の上位ビット表わすなど）。

従来の教科書的な乗算を用いると、ＡおよびＢの乗算は、４回のより小さな乗算を用いて計算される。
Ａ×Ｂ＝ａ_１ｂ_１２^２ｓ＋（ａ_０ｂ_１＋ｂ_０ａ₁）２^s＋ａ_０ｂ_０ ［３］

カラツバ乗算として知られている乗算技術は、セグメント乗算の回数を削減することができる。例えば、上記ＡおよびＢの乗算における［３］中の項、
（ａ_０ｂ_１＋ｂ_０ａ₁） ［４］
の結果は、
［（ａ_０＋ａ₁）（ｂ_０＋ｂ_１）］−ａ₁ｂ_１−ａ_０ｂ_０ ［５］
として計算することができる。
ａ₁ｂ_１とａ_０ｂ_０が方程式［３］中で別の項を形成するので、方程式［５］中でａ₁ｂ_１とａ_０ｂ_０の値を使用することは、追加計算を強いることを表わすものではない。方程式［３］中の方程式［４］に方程式［５］を代入すると、Ａ×Ｂのカラツバ乗算は次のように計算することができる。
Ａ×Ｂ＝ａ₁ｂ_１２^２ｓ＋（［（ａ_０＋ａ₁）（ｂ_０＋ｂ_１）］−ａ₁ｂ_１−ａ_０ｂ_０）２^s＋ａ_０ｂ_０ ［６］
この代入によって、２回の乗算に対して２回の加算と１回の乗算で済ませられる。大抵の場合、これは計算効率の上で極めて大きな利益をもたらす。

上記の例において、カラツバ法は、２つのセグメントへ分けた数を乗算した（つまり「２つの項のカラツバ乗算」）。しかしながら、カラツバ法は、他の数のセグメントに適用することもできる。例えば、３つの項のカラツバ乗算は、数値ＡおよびＢに対して次のように定義することができる。
Ａ＝ａ_２２^２s＋ａ₁２^s＋ａ_０ ［７］
Ｂ＝ｂ_２２^２s＋ｂ₁２^s＋ｂ_０ ［８］

Ａ×Ｂ＝ａ_２ｂ_２２^４ｓ＋ａ₁ｂ_１２^２ｓ＋ａ_０ｂ_０＋［（ａ_２＋ａ₁）（ｂ_２＋ｂ_１）−ａ_２ｂ_２−ａ_１ｂ_１］２^３s＋［（ａ_２＋ａ_０）（ｂ_２＋ｂ_０）−ａ_２ｂ_２−ａ_０ｂ_０］２^２s＋［（ａ_０＋ａ_１）（ｂ_０＋ｂ_１）−ａ_０ｂ_０−ａ_１ｂ_１］２^s ［９］
ここで、ＡおよびＢは、それぞれ３つのｓ−ビット・セグメントに分割される。

２項のカラツバ乗算［６］と同様に、３項のカラツバ乗算［９］は、異なる順序のセグメント間の乗算（つまり、ａ_ｘｂ_ｙ）の代わりに同じ順序のセグメント上の乗算（つまり、ａ_ｘｂ_ｘ）および同じ数のセグメントの加算（つまり、ａ_ｘ+ａ_ｙ）を用いた。方程式は５項のカラツバ乗算に対しても定義された。これらのカラツバ方程式は、多くても（ｔ^２＋ｔ）／２回の乗算を要求するという属性を共有し、ここでｔは項数である。

カラツバ乗算は、帰納を使用して実行することができる。例えば、次の２項のカラツバ乗算では、
Ａ×Ｂ＝ａ₁ｂ_１２^２ｎ＋（（ａ_０＋ａ₁）（ｂ_０＋ｂ_１）−ａ₁ｂ_１−ａ_０ｂ_０）２^ｎ＋ａ_０ｂ_０ ［６］
より小さいセグメント乗算は、それぞれカラツバ法を使用して順番に実行することができる。例えば、Ａ×Ｂのカラツバ乗算の実行は、ａ₁ｂ_１，ａ_０ｂ_０，（ａ_０＋ａ₁）（ｂ_０＋ｂ_１）のカラツバ乗算を含めることができる。これらの乗算は、さらに小さなサブセグメントのカラツバ乗算を含めてもよい。例えば、ａ₁ｂ_１の決定はサブセグメントの複数の項へａ₁とｂ_１をセグメントに分けてもよい。

しかしながら、このアプローチにおける潜在的な問題は、異なるサイズのオペランドが生成されるということである。すなわち、（ａ_０＋ａ₁）項および（ｂ_０＋ｂ_１）項は両方とも、加算操作からのキャリー（けた上げ）を生成することがある。（ａ_０＋ａ₁）と（ｂ_０＋ｂ_１）の結果に続く乗算が追加の固有ワードにあふれ出すことがある。これは、カラツバ法の実行効率の高さを弱めることになる。

「キャリー」問題に取り組むために、図１−図３は、２つのオペランドの最下位ビッツ（bits）上でカラツバ乗算を行ない、次に最上位ビッツ（bits）に基づいて結果を修正するサンプル実行例を示す。図１は、乗算される２つのオペランドＡ１００，Ｂ１０２をより詳細に示す。この例において、各オペランドは、ｎ＋１ビット長であり、ここでｎはあるプロセッサの固有ワードサイズｓの２倍である。この例において、各オペランドは、２つの項と付加的な高位ビットのセグメントに分けられる。例えば、Ａの最下位ｓビッツはａ_０を形成し、次の上位ｓビッツはａ₁を形成する一方、Ａの最上位ビットは、ａ_ｈを形成する。

図示されるように、カラツバ乗算は、ｓサイズの項上で次のように実行される。
２^２ｓａ_１ｂ_１＋２^s［（ａ₁＋ａ_０）（ｂ_１＋ｂ_０）−ａ₁ｂ_１−ａ_０ｂ_０］＋ａ_０ｂ_０ ［１０］
その後、その結果は、最上位ビットａ_ｈ，ｂ_ｈの値に基づいて調整される。例えば、図示されるように、その結果は、
２^ｎａ_ｈＢ［ｂ_１：ｂ_０］ １０６［１１］
および
２^ｎｂ_ｈＡ［ａ_１：ａ_０］ １０８［１２］
だけ増やされる場合がある。
言い換えれば、ａ_ｈが「１」である場合、その結果は、ｎビットだけシフトしたｂｌ：ｂ０のｎ−ビットによって増加させられる。同様に、ｂ_ｈが「１」である場合、その結果は、ｎビットだけシフトしたａｌ：ａ０のｎ−ビットによって増加させられる。例えば、これらの調整は追加の操作として実行される。
ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２^ｎａ_ｈＢ［ｂ_１：ｂ_０］
ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２^ｎｂ_ｈＡ［ａ_１：ａ_０］
あるいは加算に続く分岐として、
ｉｆ（ａ_ｈ）ｔｈｅｎ ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２^ｎＢ［ｂ_１：ｂ_０］
ｉｆ（ｂ_ｈ）ｔｈｅｎ ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２^ｎＡ［ａ_１：ａ_０］
が実行される。
最後に、もしａ_ｈ，ｂ_ｈ両方が「１」である場合、その結果は２^ｎ（つまり、ａ_ｈｂ_ｈ）だけ増加させられる。これは、例えば、ブランチを使用して次のように実行される。
ｉｆ（ａ_ｈｂ_ｈ）ｔｈｅｎ ｒｅｓｕｌｔ＝ｒｅｓｕｌｔ＋２^２ｎ
加算および１またはそれ以上のブランチ・ステートメントのこのコンビネーションは、キャリーがより低いレベルの帰納へ下流伝搬するのを防ぐことができる。

図２は、４６９の値を有するＡ１００を３６９の値を有するＢ１０２と乗算させる上述した手続の操作を示す。図示されるように、最上位ａ_ｈ，ｂ_ｈビットを除いて、Ａ［２ｓ−１：０］とＢ［２ｓ−１：０］のカラツバ乗算は、２４，０６９の値を生成する。この値は、最初にａ_ｈのために１０７，５２５に調整され、それからｂ_ｈのために７８，５９７に調整される。最後に、ａ_ｈ，ｂ_ｈ両方が「１」であるので、２^{２ｎ＝１６}に対する最上位ビットが最終的な答えである１７３，０６１を生成するために加えられる。再び、ａ_ｘｂ_ｘの値は、カラツバ技術の再帰的な適用によって決定することができる。ａ_ｈ，ｂ_ｈビットを切り取ることによって、その再帰は、便利な同じサイズのオペランド上で操作する。

図３は、再帰的なスキームでのこのカラツバ技術の実行を示す。上述するように、オペランドＡ，Ｂのカラツバ乗算は、Ａ［ｎ：０］とＢ［ｎ：０］の乗算によって行なわれ（１１４）、ＡとＢの最上位ビットａ_ｈ，ｂ_ｈに対する訂正１１６が続く。その演算結果値は、再帰スタックに返される（１１８）。

オペランドの長さがプロセッサ固有のワードサイズよりはるかに長い場合、カラツバ乗算は特に望ましい。例えば、プロセッサは、より長いオペランドと比較して単にｓのワードサイズを有している。ｎがｓに接近する場合、カラツバの効率は低下し、教科書的な乗算がより魅力的になる。このように、図３に示されるように、再帰１１２の現在の深さに依存して、教科書的乗算１２０，１２２あるいはカラツバ１１４，１１６，１１８のいずれかの手順を使用することになるであろう。実際上、教科書的乗算を使用して、最終２レベル（つまりＬ＝２）を再帰的に行なうことにより、最良の総合特性を提供するであろう。

図１−図３は、実行例を示すが、一方多くの変形が可能である。例えば、図１−図３において、各カラツバ項は、ｓ−ビット長として示されている。しかしながら、その項は、同じビット長である必要がなく、単一の固有ワードを占有する必要もない。同様に、ａ_ｈ，ｂ_ｈが単一のビットとして示されているが、他の実行例では、ａ_ｈ，ｂ_ｈが複数のビットを含んでいてもよい。

上述するように、異なる項数（例えば、２，３，５）に対して異なるカラツバ方程式が定義される。標準カラツバ分解（canonical Karatsuba decomposition）は、次の６つの長さの数値である。
ｎ＝２^ｋ
ｎ＝３・２^ｋ
ｎ＝３^２・２^ｋ
ｎ＝３^３・２^ｋ
ｎ＝３^３・２^ｋ
ｎ＝５・２^ｋ
ここで、ｎは数値の長さであり、ｋは整数である。

カラツバ分解を最適化するために、数値にゼロを付加し、より大きな標準形に適合するようにしてもよい。どの標準カラツバ分解を作業ｗに使用すべきかを識別するために、各々に対し計算され、最小のものが選択される。

ｗ値は、異なるｎ値に対して計算されてもよい。その結果は、例えば、所与のｎに対する最小のｗ値に基づいて、所与の数値を付与する量を示すルックアップ表を形成するために使用してもよい。

フォールディングを用いるモジュール削減
乗算に加えて、多くの暗号スキームにはモジュール削減（例えば、ＮｍｏｄＭの計算）を含む。モジュール削減操作の費用を削減するために、いくつかのシステムは、バレット（Ｂａｒｒｅｔｔ）のモジュール削減として知られている技術を使用する。バレットは、本質的に、商の推定を計算する。
ｑ＝ｆｌｏｏｒ（ｆｌｏｏｒ（Ｎ／２^ｍ）μ／Ｍ） ［１３］
ここで、ｍはモジュラＭの幅で、μは次式で決定される定数である。
μ＝ｆｌｏｏｒ（２^２ｎ／Ｍ） ［１４］
ここでｎは数値Ｎの幅である。ＮｍｏｄＭの値は、Ｎ−ｑＭを計算することにより決定され、最終値がＭ未満であることを保証するために必要な場合、Ｍだけ減じる最終減算が続く。バレットの効率への寄与はμに対する予め計算された値にアクセスする能力である。すなわち、μの値は、Ｎの特定の値にアクセスしなくても、Ｎのサイズのみに基づいて決定される。

バレットのモジュール削減のような技術は、モジュール削減の費用を減少させることができる。図４−図６は、モジュール削減の計算上のコストをさらに低減することができる技術を示す。図４は、特に、数値Ｎ２０２をより小さな幅数Ｎ’２０６に「畳込む（ｆｏｌｄ）」技術を示す。より小さな幅数にもかかわらず、フォールディング（folding）操作は、Ｎ’ｍｏｄＭがＮｍｏｄＭと同じであるようなＮ’を決定する。その後、古典的なバレット・モジュール削減のような従来の操作は、より小さなＮ’上で行なわれる。オペランドＮを「縮める（shrinking）」ことによって、後続の操作は、モジュラの剰余を決定するために使用される乗算を削減することができる、より小さなサイズの数値を含む。加えて、数値Ｎがより大きくなれば、効率がよくなることがより明白になる。例えば、サンプルテストでは、５１２ビットサイズのＮに対しては速度が２７％増加し、４０９６ビットサイズのＮに対しては１７７％の速度増加にジャンプすると推定される。

より詳細には、図４は、ｎの幅を有する数値Ｎ２０２、および、ｍの幅を有するモジュラＭ２００を示す。ＮｍｏｄＭを決定するために、「フォールディング」操作２１２は、ＮからＮ’を生成する。図示されるように、フォールディング２１２がフォールディング・ポイントｆで生じ、それは、Ｎをより高位のＮ_Ｈおよびより低位のＮ_Ｌの部分へ線引きをする。例えば、フォールディング・ポイントｆは、モジュラの長さおよびＮの長さの中央ポイントになるように選ばれてもよい。例えば、Ｎが２ｍ（モジュラ幅の２倍）の幅を有すると仮定すると、フォールディング・ポイントは、２^１．５ｍによって識別されるビット位置にあってもよい。このようなフォールディング・ポイントは、Ｎ’の結果幅を最小限にすることができる。すなわち、Ｎ_ＨまたはＮ_Ｌを拡張あるいは縮小するいずれかの方向へフォールディング・ポイントを移動させることにより、実際にＮ’のサイズが増加することになる。

フォールディング・ポイントに基づいて、Ｎ’は次のように決定することができる。
Ｎ’＝Ｎ_Ｈ２^ｆｍｏｄＭ+Ｎ_Ｌ ２１２［１５］
その後、より小さなＮ’は、例えば古典的バレット技術を使用して、モジュール削減を行なうために使用される。

図示されるように、Ｎ’の決定２１２は、２^ｆｍｏｄＭ２０８（Ｍ’と称される）の項を含む。２^ｆｍｏｄＭの値は、特定のＮ値に配慮をせずに事前に計算することができる。Ｍとｆの様々な値に対するこの値を事前に計算しておくことは、高価な乗算を時間的に重要でない期間へ移すことにより、Ｎ’のリアルタイム計算を促進させる。Ｍとｆの値に対して事前に計算された値は、高速アクセスのためにメモリ中のテーブルに格納することができる。Ｎ_Ｈ（２^ｆｍｏｄＭ）の乗算は、上述するように、例えば、カラツバ乗算を使用して達成される。

図示するように、図５は、Ｎが２５２（１１１１，１１００ｂ）の値を有する８ビット長の数で、Ｍが１３（１１０１ｂ）の値を有する４ビット長の数である場合のフォールディング例を示す。図示されるように、フォールディング・ポイントはｆ＝２^１．５ｍ＝２^６として選択される。Ｎ’の計算は、９６の値を生成する。図示されるように、Ｎとそのフォールドされた対Ｎ’はモジュラ１３に対するのと同じモジュラの残余５を生成する。Ｎ’のモジュール削減は、バレットのような様々なモジュール削減・アプローチのうちのどれでも使用して行なうことができる。

図６は、上述の技術を使用して、ＮｍｏｄＭの完全な決定例を示す。この例において、Ｎ２０２は幅ｎ＝４ｓであり、また、Ｍ２０４は幅ｍ＝２ｓである。図示のように、フォールディング・ポイントｆは２^３ｓである。図示されるように、Ｍ’＝２^３ｓｍｏｄＭ２２２に対する事前の計算は、（Ｍ’）（Ｎ_Ｈ）２２４を決定するにために用いられる。図６は、Ｎ_Ｈをｆｌｏｏｒ（Ｎ／２^３ｓ）の値として表現する一方で、Ｎ_Ｈの値は、Ｎ_Ｈ＝Ｎ［４ｓ−１：３ｓ］を設定することによってより速く獲得することができる。（Ｍ’）（Ｎ_Ｈ）の値２２４は、Ｎ’の計算を完了するためにＮ_Ｌ２２６に加えられる。再び、図６は、Ｎｍｏｄ２^３ｓとしてＮ_Ｌを表現しているが、Ｎ_Ｌの値は、Ｎ_Ｈ＝Ｎ［３ｓ−１：０］を設定することによってより速く獲得することができる。

Ｎ’の決定の後に、Ｎ’ｍｏｄＭは、古典的バレット・リダクションを使用して計算することができる。この場合、バレット・リダクションは、２３０，２３４で次式のように計算される。
Ｒ＝Ｎ’−ｆｌｏｏｒ（ｆｌｏｏｒ（Ｎ’／２^２ｓ）（μ／２^ｓ）Ｍ ［１６］
ここで、μは、ｆｌｏｏｒ（２^３ｓ／Ｍ）として決定される。Ｍ’の値のように、μの値は、ｓやＭの様々な値に対して事前に計算される。この事前計算は、高価な操作をリアルタイム処理が必要でない期間へ再び時間シフトすることができる。

結果Ｒ２３６は、モジュラＭ２００より大きくてもよい。この比較的まれな場合に、Ｒ＝Ｒ−Ｍの減算は、Ｒ＜Ｍを保証するために使用される。

単一のフォールディング操作は、モジュール削減の効率およびリアルタイム特性を著しく改善する。図７に示されるように、反復フォールディングは、乗算の総数およびＡＬＵ操作（つまり、加算、減算、およびシフト）に関して一層の効率改善を提供する。図示されるように、Ｎ ２０２はＮ’２０４に再びフォールディングされる。その結果Ｎ’は、多くの場合幅ｆのものである。Ｎ’が幅ｆ＋１のものである場合、Ｎ’＝Ｎ’−（Ｍ２^ｍ）の減算操作は、必ずしも必要ではないが、Ｎ’を「整える（trim）」ために使用されてもよい。図示されるように、付加的なフォールディング操作は、Ｎ’をＮ”２０６に変形し、ここでＮ”ｍｏｄＭ＝Ｎ’ｍｏｄＭである。この第２のフォールディングは、再び計算上の効率を向上させる。

異なるフォールディングの反復中に使用されるフォールディング・ポイントは、第１の反復に対する２^１．５ｍから第２に対する２^{１．２５ｍ}へ移動する。より一般的には、所与の反復に対するフォールディング・ポイントは、２^{（１＋２∧−ｉ）ｍ}として決定され、ここでｉは反復番号である。

図７は、２つのフォールディングを示すが、付加的なフォールディングも可能である。しかしながら、付加的なフォールディングは、リターンを減らし、および／または、実際に乗算操作の回数を増加させるかもしれない。

べき剰余の実行例
上述された技術は、様々な暗号演算を行なうために使用することができる。例えば、上述されたカラツバ乗算およびフォールディング技術は、べき剰余を実行するために組み合わせることができる。

べき剰余はｇ^ｅｍｏｄＭを決定することを含む。べき剰余の実行は、様々な暗号アルゴリズムの中心にある。例えば、ＲＳＡでは、公開鍵は、公開指数、ｅ−公開、およびモジュラＭによって形成される。秘密鍵は、秘密指数、ｅ−秘密、およびモジュラＭによって形成される。メッセージ（例えば、パケットまたはパケットのペイロード）を暗号化するために、次の操作が行なわれる。
ｃｉｐｈｅｒｔｅｘｔ＝ｃｌｅａｒｔｅｘｔ^{ｅ−ｐｕｂｌｉｃ}ｍｏｄＭ ［１７］
メッセージを解読するために、次の操作が行なわれる．
ｃｌｅａｒｔｅｘｔ＝ｃｉｐｈｅｒｔｅｘｔ^{ｅ−ｐｒｉｖａｔｅ}ｍｏｄＭ ［１８］

べき剰余を行なうための１つの手続きは、指数ｅ中のビットを左から右へ順に処理する。Ａ＝１の初期値から始めて、その手続きは、遭遇した各「０」ビットに対する値を２乗する（つまり、Ａ＝Ａ＊Ａ）。各「１」ビットに対して、この手続きは、その値を２乗し、ｇを乗じる両方を行なう（つまり、Ａ＝Ａ＊Ａ＊ｇ）。最終結果は、モジュール削減操作で使用することができる。例えば、３^{１０１０ｂ}ｍｏｄ５を決定するために、この手続きは、以下のように開始する、ここでｇ＝３、ｅ＝「１０１０」、またＭ＝５である。
Ａ
１
ｅｘｐｏｎｅｎｔ ｂｉｔ１−１ １＊１＊３ ＝３
ｅｘｐｏｎｅｎｔ ｂｉｔ２−０ ３＊３ ＝９
ｅｘｐｏｎｅｎｔ ｂｉｔ３−１ ９＊９＊３ ＝２４３
ｅｘｐｏｎｅｎｔ ｂｉｔ４−０ ２４３＊２４３ ＝５９０４９
ＡｍｏｄＭ ４
非常に大きな数値が乗算された際の終わりでモジュール削減を実行する代わりに、すべての指数ビットあるいはいくつかの指数ビット毎に処理した後にモジュール削減を乗算操作内に挿入するようにしてもよい。例えば、３^{１０１０ｂ}ｍｏｄ５を決定するために、この手続きは以下のように進む。
Ａ
１
ｅｘｐｏｎｅｎｔ ｂｉｔ１−１ １＊１＊３ ＝３
ＡｍｏｄＭ ３
ｅｘｐｏｎｅｎｔ ｂｉｔ２−０ ３＊３ ＝９
ＡｍｏｄＭ ４
ｅｘｐｏｎｅｎｔ ｂｉｔ３−１ ４＊４＊３ ＝４８
ＡｍｏｄＭ ３
ｅｘｐｏｎｅｎｔ ｂｉｔ４−０ ３^∧２ ＝９
ＡｍｏｄＭ ４
特定の実行にもかかわらず、２乗および「ｇ」乗算の双方に、上述されたカラツバ乗算技術を使用することにより、べき剰余を著しく促進させることができる。加えて、フォールディングを使用することで、リダクション操作は、処理資源の使用を著しく軽減させる。

付加的な計算効率は、繰り返し用いられる値を格納することにより獲得することができる。例えば、例として、ｇの値が２つの異なる乗算に必要とされているとする。２０４８ビット指数という現実の世界での例では、ｇを使用する数の乗算ははるかに大きくなる。ｇを含むカラツバ乗算の効率を改善するために、ｇ_ｉ＝（ｇ_Ｈ（ｉ）＋ｇ_Ｌ（ｉ））という異なる値が反復使用のためにテーブルに格納され、ここで、ｉは、カラツバ再帰の深さを表わす。このキャッシングは、同じ加算を重複して実行する極めて大きいサイクル回数を削減することができる。モジュール削減が同じモジュラを使用して複数回発生する場合、フォールディングで使用されるＭ’およびμのような他で頻繁に用いられる値をキャッシングすることは、さらに特性を向上させるであろう。

１ｋサイズの数を２ｋサイズの数で乗算するような不均等なサイズの数の乗算を行なう場合、付加的な最適化が使用されてもよい。このような乗算が、バレットのｑＭ値を決定する際に、またＮ_Ｈ２^ｆｍｏｄＭを決定する際に生じることがある。カラツバを利用するために、１ｋ＊２ｋの乗算をｑ＊ｍ_ｈおよびｑ＊ｍ_ｌのような２つの１ｋ＊１ｋの操作へ分割することができる。ｑが両方の操作中で使用されるので、（ｑ_ｈ＋ｑ_ｌ）の値を２度演算する必要はなく、その代り、先の使用のために格納される。

上記は単に例であり、カラツバおよびフォールディング技術を広範囲の様々な他の暗号演算を実行するだけでなく他の汎用的な目的の数学的な適用に使用することができる。

本技術は、様々な方法で、また様々なシステムで実行することができる。例えば、本技術は、専用デジタルまたはアナログ・ハードウェア（例えば、Ｖｅｒｉｌｏｇ（ｔｍ）のようなハードウェア記述言語に上述されたプログラミング技法によって決定される）、ファームウェア、および／またはＡＳＩＣ（特定用途向けＩＣ）またはプログラム可能なゲート・アレイ（ＰＧＡ）中で実行されてもよい。本技術は、またプロセッサ実行のために、コンピュータ読取り可能な媒体上に配置されたコンピュータ・プログラムとして実行されてもよい。例えば、そのプロセッサは、汎用プロセッサであってもよい。

図８に示されるように、本技術は、暗号演算を処理することができるプロセッサ・モジュール３００によって実行されるコンピュータ・プログラムで実現される。図示されるように、モジュール３００は、複数のプログラム可能な処理ユニット３０６−３１２および専用ハードウェア乗算器３１６を含む。処理ユニット３０６−３１２は、コア３０２によって管理される共有メモリ・ロジック３０４からダウンロードされるデータ上でプログラムを実行する。他のプロセッサおよび／またはプロセッサ・コアは、データおよび実行すべき命令を指定してモジュール３００へ命令を送出する。例えば、プロセッサ・コアは、ＲＡＭ３１４に格納されたｇ，ｅ，およびＭ値でのべき剰余を行なうためにモジュール３００へ命令を送出する。コア３０２は、べき剰余プログラムを処理ユニット３０６−３１２にダウンロードし、かつ操作されるべきデータをＲＡＭ３１４から共有メモリ・ロジック３０４へ、そして最後に処理ユニット３０６−３１２へダウンロードするための命令を共有メモリ３０４へ送出することによって応答する。処理ユニット３０６−３１２は、順番に、プログラム命令を実行する。特に、処理ユニット３０６−３１２は、２乗あるいは「ｇ」乗算を行なうために使用されるカラツバ乗算のような掛け算を行なうために乗算器３１６を使用する。最後に、処理ユニット３０６−３１２は、要求コアへ転送するために共有メモリ・ロジック３０４にその結果を戻す。プロセッサ・モジュール３００は、プログラム可能なコアとして同じダイ上に、あるいは異なるダイ上に集積されてもよい。

図８は、上述されたカラツバおよびフォールディング技術を実行するために使用するアーキテクチャ例を単に示す。しかしながら、本技術は、プログラムされた従来の汎用プロセッサのような広範囲の様々な他のアーキテクチャ中で使用することができる。

他の実施例は、次の請求項の範囲内にある。

カラツバ乗算を示す。 カラツバ乗算を示す。 カラツバ乗算の実行例を示すフローチャートである。 数値Ｎを数値Ｎ’へフォールディングする例を示し、Ｎ≡Ｎである。 数値Ｎを数値Ｎ’へフォールディングする例を示し、Ｎ≡Ｎである。 ＮｍｏｄＭの決定を示す。 数値Ｎの反復フォールディングを示す。 カラツバ乗算および／またはモジュール削減を実行するアーキテクチャを示す。

Claims (25)

1. コンピュータ読取り可能な格納媒体に配置され、回路にＮｍｏｄＭを決定させる命令からなるコンピュータ・プログラムにおいて、Ｎはｎ−ビット幅を有する数値で、Ｍはｍ−ビット幅を有する数値であり、前記回路は、ハードウェア乗算器に結合された少なくとも１つのプログラム可能な処理ユニットを含み、前記プログラムは、
   前記回路の少なくとも１つのプログラム可能な処理ユニットがＮ’＝Ｎ_Ｈ２^ｆｍｏｄＭ＋Ｎ_Ｌを決定し、かつ前記少なくとも１つのプログラム可能な処理ユニットによってアクセス可能な記憶要素に格納し、
   ここにおいて、
   Ｎ_Ｈは、Ｎのより高位な部分からなり、
   Ｎ_Ｌは、Ｎのより低位な部分からなり、および、
   ｆは、ＮをＮ_ＨとＮ_Ｌへ分ける位置からなり、かつ
   Ｎは、ｅを指数とすると、Ｎ＝ｇ ^ｅ が成立し、
   前記回路は、少なくともいくつかの乗算を計算するためのハードウェア乗算器を用いて、ｇ ^ｅ を決定し、
   前記回路の前記少なくとも１つのプログラム可能な処理ユニットが前記格納されたＮ’値にアクセスし、そのアクセスされたＮ’値に基づいて、Ｎ’ｍｏｄＭを決定し、かつ前記少なくとも１つのプログラム可能な処理ユニットによってアクセスされる記憶要素に格納する、
   ことを特徴とするコンピュータ・プログラム。
2. ｆは、Ｎ内に２^１．５ｍに対応するビットを含むことを特徴とする請求項１記載のコンピュータ・プログラム。
3. Ｎ’ｍｏｄＭを決定する前記命令は、２^ｆｍｏｄＭの事前に計算された値にアクセスする命令を含むことを特徴とする請求項１記載のコンピュータ・プログラム。
4. Ｎ’ｍｏｄＭを決定する前記命令は、Ｎ’ｍｏｄＭのバレット・モジュール削減を実行する命令を含むことを特徴とする請求項１記載のコンピュータ・プログラム。
5. 前記Ｎ’ｍｏｄＭのバレット・モジュール削減を決定する前記命令は、ｆｌｏｏｒ（２^ｆ／Ｍ）の事前に計算された値にアクセスする命令を含むことを特徴とする請求項４記載のコンピュータ・プログラム。
6. Ｎ’ｍｏｄＭを決定する前記命令は、
   Ｎ”＝Ｎ’_Ｈ２^ｆｍｏｄＭ＋Ｎ’_Ｌを決定し、
   ここにおいて、
   Ｎ’_Ｈは、Ｎ’のより高位な部分からなり、
   Ｎ’_Ｌは、Ｎ’のより低位な部分からなり、および、
   ｆは、Ｎ’をＮ’_ＨとＮ’_Ｌへ分ける位置からなり、
   Ｎ”ｍｏｄＭを決定する、
   ことを特徴とする請求項１記載のコンピュータ・プログラム。
7. ｆは、Ｎ’内に２^{１．２５ｍ}に対応するビットを含むことを特徴とする請求項６記載のコンピュータ・プログラム。
8. Ｎ”ｍｏｄＭを決定する前記命令は、２^ｆｍｏｄＭの事前に計算された値にアクセスする命令を含むことを特徴とする請求項６記載のコンピュータ・プログラム。
9. Ｎ”ｍｏｄＭを決定する前記命令は、Ｎ”ｍｏｄＭのバレット・モジュール削減を実行する命令を含むことを特徴とする請求項６記載のコンピュータ・プログラム。
10. 前記Ｎ”ｍｏｄＭのバレット・モジュール削減を決定する前記命令は、ｆｌｏｏｒ（２^ｆ／Ｍ）の事前に計算された値にアクセスする命令を含むことを特徴とする請求項９記載のコンピュータ・プログラム。
11. Ｍは、公開鍵のモジュラを含むことを特徴とする請求項１記載のコンピュータ・プログラム。
12. システムにおいて、
    ＮｍｏｄＭを決定する回路であって、Ｎはｎ−ビット幅を有する数値で、Ｍはｍ−ビット幅を有する数値であり、前記回路は、ハードウェア乗算器に結合された少なくとも１つのプログラム可能な処理ユニットを含み、前記回路は、
    前記回路の少なくとも１つのプログラム可能な処理ユニットがＮ’＝Ｎ_Ｈ２^ｆｍｏｄＭ＋Ｎ_Ｌを決定し、かつ前記少なくとも１つのプログラム可能な処理ユニットによってアクセス可能な記憶要素に格納し、
    ここにおいて、
    Ｎ_Ｈは、Ｎのより高位な部分からなり、
    Ｎ_Ｌは、Ｎのより低位な部分からなり、および、
    ｆは、ＮをＮ_ＨとＮ_Ｌへ分ける位置からなり、かつ
    Ｎは、ｅを指数とすると、Ｎ＝ｇ ^ｅ が成立し、
    前記回路は、少なくともいくつかの乗算を計算するためのハードウェア乗算器を用いて、ｇ ^ｅ を決定し、
    前記回路の前記少なくとも１つのプログラム可能な処理ユニットが前記格納されたＮ’値にアクセスし、そのアクセスされたＮ’値に基づいて、Ｎ’ｍｏｄＭを決定し、かつ前記少なくとも１つのプログラム可能な処理ユニットによってアクセスされる記憶要素に格納する、
    ことを特徴とするシステム。
13. ｆは、Ｎ内に２^１．５ｍに対応するビットを含むことを特徴とする請求項１２記載のシステム
14. Ｎ’ｍｏｄＭを決定する前記回路は、
    Ｎ”＝Ｎ’_Ｈ２^ｆｍｏｄＭ＋Ｎ’_Ｌを決定し、
    ここにおいて、
    Ｎ’_Ｈは、Ｎ’のより高位な部分からなり、
    Ｎ’_Ｌは、Ｎ’のより低位な部分からなり、および、
    ｆは、Ｎ’をＮ’_ＨとＮ’_Ｌへ分ける位置からなり、
    Ｎ”ｍｏｄＭを決定する、
    ことを特徴とする請求項１２記載のシステム。
15. Ｍは、公開鍵のモジュラを含むことを特徴とする請求項１２記載のシステム。
16. 前記回路は、Ｎ’およびＮ’ｍｏｄＭを決定する命令を実行するためのプログラム可能な回路を含むことを特徴とする請求項１２記載のシステム。
17. 前記回路と同じダイ上に集積され、かつ前記回路に通信可能に結合された複数のプログラム可能なコアをさらに含むことを特徴とする請求項１２記載のシステム。
18. ＮｍｏｄＭを決定するコンピュータで実行される方法において、Ｎはｎ−ビット幅を有する数値で、Ｍはｍ−ビット幅を有する数値であり、前記方法は、
    コンピュータ・プロセッサによって、Ｎ’＝Ｎ_Ｈ２^ｆｍｏｄＭ＋Ｎ_Ｌを決定し、記憶要素に格納する段階と、
    ここにおいて、
    Ｎ_Ｈは、Ｎのより高位な部分からなり、
    Ｎ_Ｌは、Ｎのより低位な部分からなり、および、
    ｆは、ＮをＮ_ＨとＮ_Ｌへ分ける位置からなり、かつ
    Ｎは、ｅを指数とすると、Ｎ＝ｇ ^ｅ が成立し、
    前記コンピュータ・プロセッサは、少なくともいくつかの乗算を計算するためのハードウェア乗算器を用いて、ｇ ^ｅ を決定し、
    前記コンピュータ・プロセッサによって、前記格納されたＮ’値にアクセスし、そのアクセスされたＮ’値に基づいて、Ｎ’ｍｏｄＭを決定する段階と、
    を含むことを特徴とするコンピュータで実行される方法。
19. ｆは、Ｎ内に２^１．５ｍに対応するビットを含むことを特徴とする請求項１８記載のコンピュータで実行される方法。
20. 前記Ｎ’ｍｏｄＭを決定する段階は、２^ｆｍｏｄＭの事前に計算された値にアクセスする段階を含むことを特徴とする請求項１８記載のコンピュータで実行される方法。
21. 前記Ｎ’ｍｏｄＭを決定する段階は、Ｎ’ｍｏｄＭのバレット・モジュール削減を実行する段階を含むことを特徴とする請求項１８記載のコンピュータで実行される方法。
22. 前記Ｎ’ｍｏｄＭを決定する段階は、
    Ｎ”＝Ｎ’_Ｈ２^ｆｍｏｄＭ＋Ｎ’_Ｌを決定する段階と、
    ここにおいて、
    Ｎ’_Ｈは、Ｎ’のより高位な部分からなり、
    Ｎ’_Ｌは、Ｎ’のより低位な部分からなり、および、
    ｆは、Ｎ’をＮ’_ＨとＮ’_Ｌへ分ける位置からなり、
    Ｎ”ｍｏｄＭを決定する段階と、
    を含むことを特徴とする請求項１８記載のコンピュータで実行される方法。
23. ｆは、Ｎ’内に２^{１．２５ｍ}に対応するビットを含むことを特徴とする請求項２２記載のコンピュータで実行される方法。
24. 前記Ｎ”ｍｏｄＭを決定する段階は、Ｎ”ｍｏｄＭのバレット・モジュール削減を実行する段階を含むことを特徴とする請求項２２記載のコンピュータで実行される方法。
25. Ｍは、公開鍵のモジュラを含むことを特徴とする請求項１８記載のコンピュータで実行される方法。

Images