(57)【特許請求の範囲】
【請求項１】
正の整数Ｃ，ｐを入力とし、ｐを２進表現したときのビット長をＬとして、ｎ≧Ｌなる整数ｎを用いてＲ＝２ｎ  として定義されたＲを用いて、Ｄ＝Ｃ・Ｒ−１  ｍｏｄ  ｐを計算するモンゴメリ・リダクション装置であって、
Ｃ＝αＲ＋βを満たす整数ペア（α，β）を算出する（α，β）抽出部と、Ｒ−１＝ε（ｍｏｄ  ｐ）を満たすεと前記βとを乗じた結果を求める乗算部と、
前記αと前記乗算部の結果出力とを加算する加算部と、
前記加算部の出力と前記ｐを法として合同なｐ以下の剰余値を求める計算部と
を備えたことを特徴とするモンゴメリ・リダクション装置。
【請求項２】
正の整数Ｃ，ｐを入力とし、ｐを２進表現したときのビット長をＬとして、ｎ≧Ｌなる整数ｎを用いてＲ＝２ｎ  として定義されたＲを用いて、Ｄ＝Ｃ・Ｒ−１  ｍｏｄ  ｐを計算するモンゴメリ・リダクション装置であって、
ｗをワード長とし、Ｒを２ｗ  で割った値をＲ’とするときに、Ｃ＝αＲ’＋βを満たす整数ペア（α，β）を算出する（α，β）抽出部と、
Ｒ’−１＝ε（ｍｏｄ  ｐ）を満たす整数εと前記βとを乗じた結果を求める乗算部と、
前記αと前記乗算部の結果出力とを加算する加算部と、
前記加算部の出力Ｔと前記ｗとを入力として、Ｔ・２−ｗ（ｍｏｄ  ｐ）を求める計算部と
備えたことを特徴とするモンゴメリ・リダクション装置。
【請求項３】
正の整数Ｃ，ｐを入力とし、ｐを２進表現したときのビット長をＬとして、ｎ≧Ｌなる整数ｎを用いてＲ＝２ｎ  として定義されたＲを用いて、Ｄ＝Ｃ・Ｒ−１  ｍｏｄ  ｐを計算するモンゴメリ・リダクション装置を制御するプログラムであって、
Ｃ＝αＲ＋βを満たす整数ペア（α，β）を算出する（α，β）抽出手段と、
Ｒ−１＝ε（ｍｏｄ  ｐ）を満たすεと前記βとを乗じた結果を求める乗算手段と、
前記αと前記乗算手段の結果出力とを加算する加算手段と、
前記加算手段の出力と前記ｐを法として合同なｐ以下の剰余値を求める計算手段として
コンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項４】
正の整数Ｃ，ｐを入力とし、ｐを２進表現したときのビット長をＬとして、ｎ≧Ｌなる整数ｎを用いてＲ＝２ｎ  として定義されたＲを用いて、Ｄ＝Ｃ・Ｒ−１  ｍｏｄ  ｐを計算するモンゴメリ・リダクション装置を制御するプログラムであって、
ｗをワード長とし、Ｒを２ｗ  で割った値をＲ’とするときに、Ｃ＝αＲ’＋βを満たす整数ペア（α，β）を算出する（α，β）抽出手段と、
Ｒ’−１＝ε（ｍｏｄ  ｐ）を満たす整数εと前記βとを乗じた結果を求める乗算手段と、
前記αと前記乗算手段の結果出力とを加算する加算手段と、
前記加算手段の出力Ｔと前記ｗとを入力として、Ｔ・２−ｗ（ｍｏｄ  ｐ）を求める計算手段として
コンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項５】
正の整数Ｃ，ｐを入力とし、ｐを２進表現したときのビット長をＬとして、ｎ≧Ｌなる整数ｎを用いてＲ＝２ｎ  として定義されたＲを用いて、Ｄ＝Ｃ・Ｒ−１  ｍｏｄ  ｐを計算するモンゴメリ・リダクション装置であって、
前記Ｃに基づき、その下位複数ワードからなる整数βと残りの上位ワードからなる整数αとを算出する（α，β）抽出部と、
前記βとパラメータεとを乗じた値をさらに前記αと加算した加算結果が、前記Ｄと合同な値Ｄ’となる条件を満たす前記εを用い、前記加算結果を求める加算部と
を備えたことを特徴とするモンゴメリ・リダクション装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、計算機ネットワークでのデータ通信におけるデータの暗号化や通信相手の確認に利用される公開鍵暗号等、奇数の整数を法とする多倍長の乗算を含む演算処理を繰り返す時の利用に適したモンゴメリ・リダクション装置及び記録媒体に関するものである。
【０００２】
【従来の技術】
情報通信ネットワークや計算機システムでは、電子的な情報の交換・累積が行われる。そのようなシステムが大規模化し、不特定多数のユーザが利用する状況では、悪意のユーザによる情報の盗聴や改ざんなどが問題となる。その対策として公開鍵暗号技術を利用する場合が多い。
【０００３】
ここで公開鍵暗号は、多倍長の奇整数を法（モジュラス）とする演算（剰余演算系）で実現される方式が多く、その高速化が性能に影響を与える。剰余演算系では、特に乗算と除算が処理時間に与える影響が大きい。例えば、ＲＳＡ暗号では奇合成数を法とする剰余演算系でのべき乗計算により暗号化と復号の各処理が実行される。また、素体Ｆｐ上の楕円曲線暗号では、奇素数を法とする加減乗除演算を適切に組み合わせて楕円曲線上の点の加算を構成し、その点の加算演算の繰り返しを用いて暗号化と復号の各処理が実行される。
【０００４】
剰余演算系での乗算（Ａ＊Ｂ  ｍｏｄ  ｐ  の計算）を実現する場合には、多倍長の乗算（Ｃ＝Ａ＊Ｂ  の計算）とその結果に対する多倍長の剰余計算（Ｃ  ｍｏｄ  ｐ  の計算）を構成する場合が多い。この時、多倍長の剰余計算は多倍長の乗算よりも性能が劣ることが多く、剰余計算の効率化について幾つかの検討が行われている。
【０００５】
剰余演算系での乗算の繰り返し実行に適した計算アルゴリズムとして、モンゴメリ算法が知られている。同算法は文献（１）Ｐ．Ｌ．Ｍｏｎｔｇｏｍｅｒｙ，“Ｍｏｄｕｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｗｉｔｈｏｕｔ  ｔｒｉａｌ  ｄｉｖｉｓｉｏｎ”，Ｍａｔｈ．ｏｆ  Ｃｏｍｐ，Ｖｏｌ．４４，Ｎｏ．１７０，ｐｐ，５１９−５２１（１９８５）に詳しい。
【０００６】
モンゴメリ算法では、奇整数を法とする剰余演算系での乗算を、次のように実行する。最初に乗数Ａと被乗数Ｂとの多倍長の乗算を実行し、Ｃを得る。ここでＡとＢは共に法である整数ｐ以下のサイズとする。次に、Ｃに対してモンゴメリ・リダクションと呼ばれる演算を行い、法以下のサイズにする。すなわち、法ｐの２倍程度のサイズであるＣを法ｐのサイズに縮小させるのである。このモンゴメリ・リダクションが通常での剰余計算に相当し、その処理は概ね多倍長同士の乗算１回と同じ処理量である。すなわち、剰余計算処理が効率化される。計算機上の演算処理の中では、除算演算は他の加算，減算又は乗算演算よりも処理に時間がかかるからである。
【０００７】
さて、モンゴメリ算法は剰余演算系での乗算の繰り返し実行に適したアルゴリズムと説明したが、これは次の理由による。モンゴメリ算法はモンゴメリ演算域の元（これも同じ法での剰余系である）の乗算アルゴリズムであり、一般の剰余系での乗算を実現するには以下の処理が必要である。すなわち、まず乗数と被乗数をモンゴメリ演算域に変換し、次にモンゴメリ乗算（乗算とモンゴメリ・リダクション）を行い、最後にモンゴメリ演算域からもとの剰余系に結果を逆変換する必要がある。モンゴメリ演算域ともとの剰余系での元の対応関係はモンゴメリ乗算の前後で保存される。したがって、例えばべき乗など剰余演算系での乗算の繰り返しを行う場合であれば、演算の最初にべき乗の底をモンゴメリ演算域に変換すれば、モンゴメリ乗算の結果をその都度、もとの剰余系での値に逆変換する必要は無く、繰り返しモンゴメリ乗算の入力に適用できる。べき乗の最後にモンゴメリ演算域の値をもとの剰余系での値に逆変換すれば良い。モンゴメリ演算域への変換と逆変換はそれぞれ、剰余計算１回、乗算１回に相当する演算量であり、全体の最初と最後に１回だけ行う場合にはオーバヘッドにはならない。
【０００８】
モンゴメリ演算域の元と一般の剰余系の元との間には、次の対応関係がある。まず、法ｐと互いに素で、法ｐより大きな２のべき乗値をＲとして定める。一般には、Ｒは計算機のワードサイズの倍数とし、法ｐのサイズを越える最も小さな値として定めることが多い。例えば、３２ビットＣＰＵのソフトウェアを想定し、法ｐが１０２４ビットの場合にはＲ＝２１０２４（＝（２３２）３２）、法ｐが１６０ビットならばＲ＝２１６０  （＝（２３２）５  ）とする。
【０００９】
このようなＲのもと、一般の剰余系での元をａ．ｂとすると、それらに対応するモンゴメリ演算域での元はＡ＝ａＲ（ｍｏｄ  ｐ）、Ｂ＝ｂＲ（ｍｏｄ  ｐ）である。モンゴメリ・リダクションでは、Ｃ＝ＡＢに対してＤ＝ＣＲ−１（ｍｏｄｐ）＝（ａｂ）Ｒ（ｍｏｄ  ｐ）なる値が計算される。このモンゴメリ演算域での元Ｄは、一般の剰余系での値  （ａｂ）に対応している。モンゴメリ・リダクションは、このＤ＝ＣＲ−１（ｍｏｄ  ｐ）に相当する演算であるため、例えば、モンゴメリ演算域の元Ｄを一般の剰余系の元ｄに逆変換する場合にも利用できる。すなわち、ｄ＝ＤＲ−１（ｍｏｄ  ｐ）＝ａｂ（ｍｏｄ  ｐ）である。
【００１０】
【発明が解決しようとする課題】
このモンゴメリ・リダクションは、モンゴメリ演算の中心となる演算処理であり、この演算の処理速度が暗号演算等の高速化に与える影響は大きい。同演算は、モンゴメリ演算法以外の演算方法に比べれば多倍長乗算１回程度と効率が良いが、近年の暗号化技術の普及等に鑑みてより高速化を図りたいという要請がある。
【００１１】
すなわち現状では、モンゴメリ・リダクションを多倍長乗算１回程度の処理量より大きく削減する手法は実現されておらず、実際にはモンゴメリ演算系を利用しても演算効率の改善度が必ずしも十分ではないという問題点がある。
【００１２】
本発明は、このような実情を考慮してなされたもので、モンゴメリ・リダクションを少ない計算量で実現でき、大幅に効率化することができるモンゴメリ・リダクション装置及び記録媒体を提供することを目的とする。
【００１３】
【課題を解決するための手段】
上記課題を解決するために、請求項１に対応する発明は、正の整数Ｃ，ｐを入力とし、ｐを２進表現したときのビット長をＬとして、ｎ≧Ｌなる整数ｎを用いてＲ＝２ｎ  として定義されたＲを用いて、Ｄ＝Ｃ・Ｒ−１  ｍｏｄ  ｐを計算するモンゴメリ・リダクション装置であって、Ｃ＝αＲ＋βを満たす整数ペア（α，β）を算出する（α，β）抽出部と、Ｒ−１＝ε（ｍｏｄ  ｐ）を満たすεとβとを乗じた結果を求める乗算部と、αと乗算部の結果出力とを加算する加算部と、加算部の出力とｐを法として合同なｐ以下の剰余値を求める計算部とを備えたモンゴメリ・リダクション装置である。
【００１４】
本発明によれば、例えばεを計算装置の１ワード以下の値とすると、乗算部における計算は１ワード整数×多倍長整数の乗算となる。また、加算部の実行結果は、１ワード程度サイズの大きい結果となるため、最後の計算部では１ワード分だけ縮小する剰余計算処理を行なえば良い。他の部分での演算量はわずかであるため全体として処理量が軽減できる。
【００１５】
次に、請求項２に対応する発明は、正の整数Ｃ，ｐを入力とし、ｐを２進表現したときのビット長をＬとして、ｎ≧Ｌなる整数ｎを用いてＲ＝２ｎ  として定義されたＲを用いて、Ｄ＝Ｃ・Ｒ−１  ｍｏｄ  ｐを計算するモンゴメリ・リダクション装置であって、ｗをワード長とし、Ｒを２ｗ  で割った値をＲ’とするときに、Ｃ＝αＲ’＋βを満たす整数ペア（α，β）を算出する（α，β）抽出部と、Ｒ’−１＝ε（ｍｏｄ  ｐ）を満たす整数εとβとを乗じた結果を求める乗算部と、αと乗算部の結果出力とを加算する加算部と、加算部の出力Ｔとｗとを入力として、Ｔ・２−ｗ（ｍｏｄ  ｐ）を求める計算部と備えたモンゴメリ・リダクション装置である。
【００１６】
本発明によれば、例えばεが計算装置の１ワード以下の値とすると、乗算部での計算は１ワード整数×多倍長整数の乗算程度となる。また、加算部の実行結果は１ワード程度サイズの大きい値となる。最後の計算部は、最下位１ワード分を縮小するモンゴメリ・リダクション演算、すなわち１ワード整数×多倍長整数の乗算相当の処理量で実現できる。他の部分での演算量はわずかであるため全体として処理量が削減できる。
【００１７】
次に、請求項３に対応する発明は、請求項１に対応する発明をコンピュータに実現させるためのプログラムを格納した記録媒体である。
本発明の記録媒体に格納されたプログラムをコンピュータにおいて読み出せば、請求項１に係るモンゴメリ・リダクション装置が実現される。
【００１８】
次に、請求項４に対応する発明は、請求項２に対応する発明をコンピュータに実現させるためのプログラムを格納した記録媒体である。
本発明の記録媒体に格納されたプログラムをコンピュータにおいて読み出せば、請求項２に係るモンゴメリ・リダクション装置が実現される。
【００１９】
次に、請求項５に対応する発明は、正の整数Ｃ，ｐを入力とし、ｐを２進表現したときのビット長をＬとして、ｎ≧Ｌなる整数ｎを用いてＲ＝２ｎ  として定義されたＲを用いて、Ｄ＝Ｃ・Ｒ−１  ｍｏｄ  ｐを計算するモンゴメリ・リダクション装置であって、Ｃに基づき、その下位複数ワードからなる整数βと残りの上位ワードからなる整数αとを算出する（α，β）抽出部と、βとパラメータεとを乗じた値をさらにαと加算した加算結果が、Ｄと合同な値Ｄ’となる条件を満たすεを用い、加算結果を求める加算部とを備えたモンゴメリ・リダクション装置である。
【００２０】
本発明によれば、乗算部における計算は１ワード整数×多倍長整数程度の乗算となる。また、加算部の実行結果はＤと合同な値Ｄ’となるが、このＤ’はβがＣの下位複数ワードであるので、１ワードづつリダクションしていく通常のモンゴメリ・リダクションに比べれば少ない演算量でそのワード数までリダクションされたものである。
したがって、剰余計算の回数を少なくすることができ、モンゴメリ・リダクションを少ない計算量で実現できる。
【００２１】
【発明の実施の形態】
本発明におけるモンゴメリ・リダクション装置及び方法は、剰余計算の効率化アルゴリズムであるモンゴメリ・リダクションをさらに効率的に実現するものである。具体的には、法ｐをモンゴメリ・リダクションでの演算式に適した値として設定することで、その効率的な演算を実現可能とする。
【００２２】
モンゴメリ・リダクションは奇整数を法とする剰余演算系における剰余計算を実行するアルゴリズムである。法ｐに関しては奇数であること以上の制約はないが、実施形態では説明を簡単にするため法ｐは奇素数であることを想定する。
【００２３】
モンゴメリ・リダクションの利用にあたっては、法ｐのビットサイズから決定される定数Ｒを定める必要がある。定数Ｒの条件としては、Ｒ＞ｐであることと、Ｒとｐとが互いに素であることである。但し、モンゴメリ・リダクションの中で、Ｒで剰余をとった結果やＲで割った商を求める手続きがあり、それら処理の効率化のために、Ｒのサイズは実装される計算装置のワード長の倍数に設定することが一般的である。すなわち、計算装置のワード長をｗとするとき、Ｒ＝（２ｗ  ）Ｌ  （但しＬは、Ｒ＞ｐを満足する最小の整数）と設定されることが多い。以下では、設明を簡単にするため、ｐのビットサイズｎはｗの倍数とし、Ｒ＝２ｎ  と設定されるものとして説明する。なお、これらの説明上の都合による想定で、発明自体が限定されるものではない。
【００２４】
モンゴメリ・リダクションでは、法ｐより小さい正の整数Ａ，Ｂの積Ｃに対して、Ｄ＝ＣＲ−１  ｍｏｄ  ｐを計算する。ここで、Ｒ−１はＲ・Ｒ−１＝１  ｍｏｄ
ｐを満たすＲの乗法的逆元を表す。
【００２５】
以下、本発明の各実施形態について説明する。
（発明の第１の実施の形態）
図１は本発明の第１の実施の形態におけるモンゴメリ・リダクション計算法の原理を説明する図である。
【００２６】
この発明では、Ｒ−１＝ε（ｍｏｄ  ｐ）を満たすεの存在するような法ｐを用いることを前提とする。ここでεは計算装置の１ワードで表現できる整数である。なお、図１において、ブロックの１つは１ワードを示している。
【００２７】
Ａ、Ｂはともに法ｐ以下の整数であるため、それらの積Ｃは法ｐの２倍のサイズ以下となる。Ｒは法ｐのサイズｎに対して、２ｎ  なる値として設定されていることに注意すると、Ｃ＝αＲ＋βと分解するとき、法ｐのサイズの位置（図１では下位側から４ワードのところ）でＣを上位側と下位側に分けたうちの上位側の数値がα、下位側の数値がβとなる。
【００２８】
このとき、
Ｄ＝Ｃ×Ｒ−１（ｍｏｄ  ｐ）
＝（αＲ＋β）×Ｒ−１（ｍｏｄ  ｐ）
＝α＋βＲ−１（ｍｏｄ  ｐ）
＝α＋εβ（ｍｏｄ  ｐ）
が成立する。ここで最後の式変形に法ｐの特殊性（Ｒ−１＝ε（ｍｏｄ  ｐ）つまり、この場合Ｒ−１＝εが成り立つ）を利用している。
【００２９】
図１に示すように、まずＣを上位側のαと下位側のβに分割し、βに法ｐから決まるεを掛ける。この結果をαと加算する。以上で、モンゴメリ・リダクションとして求まる値Ｄと法ｐのもとで合同な値Ｄ’が計算できる。
【００３０】
Ｄ’は図１に示したように法ｐよりも１ワードだけサイズが大きな値として計算される。Ｄ’の値から法ｐのもとで合同でｐよりも小さい値Ｄを求めるには、Ｄ’を法ｐで割りその剰余を求める手法、あるいは、予めｐよりも１ワードだけ大きい値に関する剰余値のテーブルを計算しておき、そのテーブルを参照してＤの値を求める手法、などを利用する。
【００３１】
剰余値のテーブルを利用する方法の具体例としては、例えば次の方法がある。剰余テーブルＴＪ  として、ＴＪ  ＝２ｊ  ×Ｒ（ｍｏｄ  ｐ）（ｊ＝０，１，２，…，ｗ−１）を予め計算しておく。Ｄ’を上位１ワードＥとそれ以外の下位側データＦとに分ける。Ｅの各ビットを参照し、その最下位ビット（ＬＳＢ）から第ｉビット（ｉ＝０，１，２，…，ｗ−１）が１であれば、ＦにＴｉ  を加算する。こうして法ｐのもとでＤ’と合同でＤ’よりもサイズの小さい値が求まる。
【００３２】
この結果に対して再びＲを越えた部分とＲ未満の部分にデータを分けて同様の処理を繰り返すことができる。こうした処理により法ｐよりもビットサイズが２〜３ビット程度大きい値にまで縮小された段階で、結果が負にならない範囲でｐを繰り返し減じることで法ｐより小さい剰余値が計算できる。
【００３３】
以上に述べた演算原理を適用できる法ｐは、Ｒ−１＝ε（ｍｏｄ  ｐ）を式変形することによりεＲ−１＝０（ｍｏｄ  ｐ）と記述できることから、ε・２ｎ  −１がｎビットの素数で割り切れる場合には、そのときの素因数ｐとεを利用すれば良い。
【００３４】
次に、上記演算方法を実現する具体的な装置を説明する。
図２は本実施形態におけるモンゴメリ・リダクション装置の構成例を示すブロック図である。
【００３５】
このモンゴメリ・リダクション装置１は、ＣＰＵ，メモリその他の周辺要素を具備する計算機がそのプログラムに制御されることで実現されるものであり、（α，β）抽出部２、Ｔ１乗算部３、Ｔ２加算部４及びＤ剰余計算部５から構成されている。
【００３６】
また、本実施形態のモンゴメリ・リダクション装置１は、モンゴメリ演算系における各演算のうち、モンゴメリ・リダクションのみを実行するものである。この装置１の利用例については後述する。
【００３７】
（α，β）抽出部２は、本装置１におけるモンゴメリ・リダクションの計算対象である多倍長整数Ｃと、法の値ｐと、モンゴメリ演算の補助パラメータである定数Ｒと、Ｒ−１＝ε（ｍｏｄ  ｐ）なる値εとが入力されると、α＝Ｃ／Ｒ、β＝Ｃ（ｍｏｄ  Ｒ）なる両データを抽出する。実際の処理としては、Ｃをワード単位に並べ、Ｒよりも上位側のデータと下位側のデータとして抽出する。
【００３８】
Ｔ１乗算部３は、εと（α，β）抽出部２で抽出されたβとを乗算し、その結果Ｔ１を得る。この部分３は１ワード数と多倍長整数の乗算を行なう計算部である。
【００３９】
Ｔ２加算部４は、Ｔ１乗算部３の結果Ｔ１と（α，β）抽出部２で抽出されたαとを加算処理して結果Ｔ２を得る。
Ｄ剰余計算部５は、Ｔ２加算部４で得られたＴ２と法ｐとからＤ＝Ｔ２（ｍｏｄ  ｐ）が求められる。剰余計算部５は整数の除算回路などで実現できる。この場合、多倍長整数を除数として、被除数は除数より１ワードだけサイズの大きな除算を行なう回路があればよい。
【００４０】
次に、以上のように構成された本発明の実施の形態に係るモンゴメリ・リダクション装置の動作について説明する。
図３は、本実施形態のモンゴメリ・リダクション装置における計算手順を示す流れ図である。
【００４１】
まず、ステップＳ１でモンゴメリ・リダクションの対象であるデータＣ、法の値ｐ、演算補助パラメータであるＲとεとが（α，β）抽出部２に入力される。次にステップＳ２でα＝Ｃ／Ｒとβ＝Ｃ（ｍｏｄ  Ｒ）が（α，β）抽出部２により算出される。この処理はＣを下位側からｎビットまでの部分とそれより上位の部分とに分け、前者をβ、後者をαとすることでよい。
【００４２】
次にステップＳ３でＴ１乗算部３によりＴ１＝ε×βが計算され、続いてステップＳ４でＴ２加算部４によりＴ２＝α＋Ｔ１が計算される。
最後にステップＳ５でＤ剰余計算部５によりＤ＝Ｔ２（ｍｏｄ  ｐ）なるＤが計算され、ステップＳ６でこの値が出力されて終了する。
【００４３】
以上の処理のうちステップＳ３は１ワードの整数と多倍長整数の乗算である。また、Ｓ５を除算で実行する場合には、多倍長整数同士の除算を行うことになるが、被除数の最上位１ワードだけを縮小すれば良いので処理量は少ない。全体として、通常のモンゴメリ・リダクションで行なわれる多倍長整数同士の乗算１回よりも処理量が少なくなる。
【００４４】
上述したように、本発明の実施の形態に係るモンゴメリ・リダクション装置は、法ｐをモンゴメリ・リダクションでの演算式に適した値として設定するようにしたので、モンゴメリ・リダクション演算をより少ない計算量で実現することができる。
【００４５】
なお、本装置１では、本計算手法に適した法ｐを予め選択しておく必要があるが、例えば代表的な暗号アルゴリズムではそのような設定が可能であり、暗号処理に必要な演算量を大きく削減することが可能となる。例えば公開鍵暗号など固定的に用いられる奇整数を法とした剰余演算系において利用されるモンゴメリ・リダクション演算において演算量が削減される。
（発明の第２の実施の形態）
第１の実施形態で説明した演算手法によれば１ワード数×多倍長整数の乗算１回で所望のモンゴメリ・リダクション結果Ｄよりも１ワードだけサイズの大きな結果Ｄ’が求められる。しかし、この場合でもＤ’からＤを求めるのに除算や剰余テーブルなどの演算が必要で、その処理の効率が良くないという問題が残る。本実施形態では、この問題を解決できるモンゴメリ・リダクションの計算法を説明する。
【００４６】
図４は本発明の第２の実施の形態におけるモンゴメリ・リダクション計算法の原理を説明する図である。
本発明では、計算機の１ワードのビット長をｗとしたとき、Ｒ−１２ｗ  ＝ε（ｍｏｄ  ｐ）を満たすような１ワード以内の整数εの存在する法ｐを用いることを前提とする。
【００４７】
図１の場合と同様に、モンゴメリ・リダクションの対象であるＣは法ｐの２倍のサイズ以下となる。この計算方法では、Ｃを上位側データαと下位側データβに分割するときに、Ｒ２−ｗの位置（法ｐのサイズよりも１ワード分だけサイズの小さい位置）でαとβに分割する。すなわち、Ｃ＝α（Ｒ・２−ｗ）＋βとなる。図４の例では下から３ワード目で分割する。
【００４８】
このとき、
Ｄ＝Ｃ×Ｒ−１（ｍｏｄ  ｐ）
＝（α（Ｒ・２−ｗ）＋β）・（Ｒ−１・２ｗ  ）・２−ｗ（ｍｏｄ  ｐ）
＝（α＋β・（Ｒ−１・２ｗ  ））・２  ｗ  （ｍｏｄ  ｐ）
＝（α＋βε）・２−ｗ（ｍｏｄ  ｐ）
が成立する。ここで最後の式変形にｐの特殊性（Ｒ−１２ｗ  ＝ε（ｍｏｄ  ｐ）＝ε）を利用している。
【００４９】
ここで、Ｄ’＝α＋βεとおくとＤ’は法ｐのワード数よりも１ワードだけ大きい数となるが、Ｄ＝Ｄ’・２−ｗ（ｍｏｄ  ｐ）は、文献（１）Ｐ．Ｌ．Ｍｏｎｔｇｏｍｅｒｙ，“Ｍｏｄｕｌａｒ  ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｗｉｔｈｏｕｔ  ｔｒｉａｌ  ｄｉｖｉｓｉｏｎ”，Ｍａｔｈ．ｏｆ  Ｃｏｍｐ．，Ｖｏｌ．４４，Ｎｏ．１７０，ｐｐ．５１９−５２１（１９８５）などに示されているモンゴメリ・リダクション計算法をＤ’の最下位ワードのみに適用することで計算でき、その結果は法ｐ以下のサイズになる。Ｄ’からＤを求める計算量は１ワード数×多倍長整数の乗算１回程度である。
【００５０】
以上に述べた演算原理を適用できる法ｐは、Ｒ−１・２ｗ  ＝ε（ｍｏｄ  ｐ）を式変形することによりε（Ｒ・２−ｗ）−１＝０（ｍｏｄ  ｐ）となることから、ｐ＝ε×２ｎ−ｗ  −１となる形式を満たすものとなる。
【００５１】
次に、上記演算方法を実現する具体的な装置を説明する。
図５は本実施形態におけるモンゴメリ・リダクション装置の構成例を示すブロック図である。
【００５２】
このモンゴメリ・リダクション装置１１は、第１の実施形態と同様に計算機により実現されるものであり、図５はハードウエアとソフトウエアの結合からなる機能実現ブロックを示している。すなわちモンゴメリ・リダクション装置１１は、（α，β）抽出部１２、Ｔ１乗算部１３、Ｔ２加算部１４及びＤ計算部１５から構成されている。
【００５３】
（α，β）抽出部１２は、本装置１１にモンゴメリ・リダクションの計算対象である多倍長整数Ｃと、法の値ｐと、モンゴメリ演算の補助パラメータである定数Ｒと、Ｒ−１・２ｗ  ＝ε（ｍｏｄ  ｐ）なる値ε及びｗとが入力されると、α＝Ｃ／（Ｒ２−ｗ）、β＝Ｃ（ｍｏｄ（Ｒ２−ｗ））なる両データを抽出する。
【００５４】
Ｔ１乗算部１３は、１ワード数と多倍長整数の乗算を行なう計算部であり、εと（α，β）抽出部１２で抽出されたβとを乗算し、その結果Ｔ１を得る。
Ｔ２加算部１４は、Ｔ１乗算部１３での計算結果Ｔ１と、（α，β）抽出部１２で抽出されたαとを加算処理して結果Ｔ２を得る。
【００５５】
Ｄ計算部１５は、Ｔ２加算部１５で得たＴ２と、法ｐとからＤ＝Ｔ２・２−ｗ（ｍｏｄ  ｐ）を求める。このＤ計算部１５は１ワードと多倍長整数の乗算器と多倍長の加算器で構成される。
【００５６】
次に、以上のように構成された本発明の実施の形態に係るモンゴメリ・リダクション装置の動作について説明する。
図６は、本実施形態のモンゴメリ・リダクション装置における計算手順を示す流れ図である。
【００５７】
まず、ステップＳ１１でモンゴメリ・リダクションの対象であるデータＣ、法の値ｐ、演算補助パラメータであるＲ及びε、計算機のワード長ｗが（α，β）抽出部１２に入力される。次にステップＳ１２で（α，β）抽出部１２によりα＝Ｃ／（Ｒ２−ｗ）とβ＝Ｃ（ｍｏｄ（Ｒ２−ｗ））が求められる。この処理はＣを下位側から法ｐのサイズより１ワードだけ小さいビット位置までの部分とそれより上位の部分とに分け、前者をβ、後者をαとすることでよい。
【００５８】
次にステップＳ１３でＴ１乗算部１３によりＴ１＝ε×βが計算され、さらにステップＳ１４でＴ２加算部１４によりＴ２＝α＋Ｔ１が計算される。
最後にステップＳ１５でＤ計算部１５によりＤ＝Ｔ２・２−ｗ（ｍｏｄ  ｐ）なるＤが計算され、ステップＳ１６でこの値が演算結果として出力されて終了する。
【００５９】
以上の処理のうちステップＳ１３は１ワードの整数と多倍長整数の乗算である。また、ステップＳ１５は１ワード分のモンゴメリ・リダクション演算を実行することで計算でき、この部分の処理量も１ワードの整数と多倍長整数の乗算である。従って、全体として１ワードの整数と多倍長整数の乗算２回で計算可能でとなる。
【００６０】
次に、ステップＳ１５の具体的な計算手順である１ワード分のモンゴメリ・リダクション演算の手順を説明する。
図７はＤ計算部における計算処理を示す流れ図である。
【００６１】
まず、ステップＳ２１で計算対象であるデータＴ２、法の値ｐ、演算補助パラメータである計算機のワード長ｗを入力する。次にステップＳ２２でδ’＝δ・ｖ（ｍｏｄ  ２ｗ  ）を計算する。ここで、δはＴ２の最下位の１ワードであり、ｖは法ｐの最下位の１ワードをｐ０とした場合に、ｖ・ｐ０＝−１（ｍｏｄ  ２ｗ  ）を満たす値ｖである。
【００６２】
この演算法で用いる法ｐはｐ＝ε×２ｎ−ｗ  −１なる形式となるため、必ずｐ０＝−１（ｍｏｄ  ２ｗ  ）となり、ｖ＝１である。従って、ステップＳ２１の処理はＴ２の最下位ワードを取り出し、その値をδ’に格納することでよい。
【００６３】
次にステップＳ２３でＴ３＝Ｔ２＋δ’ｐを計算する。このとき、Ｔ３の最下位１ワードは０となることに注意する。
次に、ステップＳ２４でＴ４＝Ｔ３／（２ｗ  ）を求める。この処理は、Ｔ３の最下位１ワードを除いたデータをＴ４とすることと等価である。
【００６４】
こうして得られた結果はｐよりも１ビット程度大きいことがある。そこでステップＳ２５でＴ４とｐの大小比較を行ないＴ４がｐ以上ならばステップＳ２６でＴ４からｐを引く。これを繰り返すことでＴ４は法ｐ以下になるのでステップＳ２７でＴ４を出力して終了する。
【００６５】
上述したように、本発明の実施の形態に係るモンゴメリ・リダクション装置は、法ｐをモンゴメリ・リダクションでの演算式に適した値として設定するようにしたので、第１の実施形態と比べてもモンゴメリ・リダクション演算をより一層少ない計算量で実現することができる。
【００６６】
すなわち、従来は多倍長整数×多倍長整数の乗算１回程度の計算量で行なわれていたモンゴメリ・リダクション計算を、単精度整数×多倍長整数の乗算２回程度の計算量で実現する。暗号処理で用いる典型的なサイズでは、多倍長整数は単精度整数の５〜６４倍の長さを持つため、約２．５〜３２倍もの処理量削減につながる。
【００６７】
なお、各実施形態における本発明のモンゴメリ・リダクション方法および装置の応用分野としては、暗号装置などの情報セキュリティが挙げられる。例えば、鍵配送方式の典型的なアルゴリズムであるＤｉｆｆｉｅ−Ｈｅｌｌｍａｎ法や公開鍵暗号におけるＥｌＧａｍａｌ暗号、楕円曲線暗号、ディジタル署名方式におけるＤＳＡ．ＥＣＤＳＡなどでは法ｐは固定的である。そこで、法ｐとして本発明の処理方法が可能となるパラメータを選択すれば、鍵配送や暗号などの処理効率を大きく改善できる。
【００６８】
図８は本発明に係るモンゴメリ・リダクション手法の利用対象の一例を示す図である。
同図において、本発明のモンゴメリ・リダクション装置はモンゴメリ演算による楕円曲線暗号計算部分２１で用いられる。
【００６９】
【実施例】
以下、実施形態で説明したモンゴメリ・リダクション装置１／１１を楕円曲線暗号装置に適用する場合を実施例として説明する。
図９は本実施例に係る楕円曲線暗号装置の構成例を示すブロック図である。
【００７０】
この楕円曲線暗号装置３１はパーソナルコンピュータやワークステーション等の計算機からなり、モンゴメリ変換部３２と、暗号化パラメータ格納部３３と、暗号計算部３４と、モンゴメリ逆変換部３５とから構成されている。なお、暗号計算部３４は、図８では楕円曲線暗号計算部分２１に対応する。
【００７１】
モンゴメリ変換部３２は、装置３１に入力された暗号化対象データをＦｐ  領域からモンゴメリ演算域へ変換するものである。
暗号化パラメータ格納部３３は、暗号化に必要な各種パラメータを暗号計算部３４に提供する。
【００７２】
モンゴメリ逆変換部３５は、暗号計算部３４により得られた暗号化データをモンゴメリ領域からＦｐ  領域へ逆変換するものである。
暗号計算部３４は、モンゴメリ変換部３２で変換されたデータを暗号化パラメータを用いて暗号化する。この暗号計算部３４は、モンゴメリ演算装置４１と暗号制御装置４２とを備えている。
【００７３】
モンゴメリ演算装置４１は、モンゴメリ加減乗除演算を行うものであり、モンゴメリ加算装置５１と、モンゴメリ減算装置５２と、モンゴメリ乗算装置５３と、モンゴメリ除算装置５４とから構成されている。
【００７４】
まず、モンゴメリ乗算装置５３は、さらに乗算器５５とモンゴメリ・リダクション装置１／１１とから構成される。また、モンゴメリ除算装置５４は、モンゴメリ逆元装置５６とモンゴメリ・リダクション装置１／１１とから構成される。ここで各部５３，５４に設けられるモンゴメリ・リダクション装置１／１１は、第１もしくは第２の実施形態で説明した装置である。
【００７５】
暗号制御装置４２は、モンゴメリ演算装置４１に設けられた各演算装置５１，５２，５３，５４を用い、また暗号化パラメータ格納部３３のパラメータに基づき、入力データを暗号化するための処理を制御する。
【００７６】
このように構成された楕円曲線暗号装置３１では、モンゴメリ・リダクション装置１又は１１において効率的なモンゴメリ・リダクションが行われるので、入力データを高速に暗号化処理し暗号化データとして出力することができる。
【００７７】
なお、本発明は、上記各実施形態又は実施例に限定されるものでなく、その要旨を逸脱しない範囲で種々に変形することが可能である。
また、実施形態又は実施例に記載した手法は、計算機（コンピュータ）に実行させることができるプログラム（ソフトウエア手段）として、例えば磁気ディスク（フロッピーディスク、ハードディスク等）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤ等）、半導体メモリ等の記憶媒体に格納し、また通信媒体により伝送して頒布することもできる。なお、媒体側に格納されるプログラムには、計算機に実行させるソフトウエア手段（実行プログラムのみならずテーブルやデータ構造も含む）を計算機内に構成させる設定プログラムをも含むものである。本装置を実現する計算機は、記憶媒体に記録されたプログラムを読み込み、また場合により設定プログラムによりソフトウエア手段を構築し、このソフトウエア手段によって動作が制御されることにより上述した処理を実行する。
【００７８】
【発明の効果】
以上詳記したように本発明によれば、法ｐをモンゴメリ・リダクションでの演算式に適した値として設定するようにしたので、モンゴメリ・リダクションを少ない計算量で実現でき、大幅に効率化することができるモンゴメリ・リダクション装置及び記録媒体を提供することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態におけるモンゴメリ・リダクション計算法の原理を説明する図。
【図２】同実施形態におけるモンゴメリ・リダクション装置の構成例を示すブロック図。
【図３】同実施形態のモンゴメリ・リダクション装置における計算手順を示す流れ図。
【図４】本発明の第２の実施の形態におけるモンゴメリ・リダクション計算法の原理を説明する図。
【図５】同実施形態におけるモンゴメリ・リダクション装置の構成例を示すブロック図。
【図６】同実施形態のモンゴメリ・リダクション装置における計算手順を示す流れ図。
【図７】Ｄ計算部における計算処理を示す流れ図。
【図８】本発明に係るモンゴメリ・リダクション手法の利用対象の一例を示す図。
【図９】本発明の実施例に係る楕円曲線暗号装置の構成例を示すブロック図。
【符号の説明】
１…モンゴメリ・リダクション装置
２…（α，β）抽出部
３…Ｔ１乗算部
４…Ｔ２加算部
５…Ｄ剰余計算部
１１…モンゴメリ・リダクション装置
１２…（α，β）抽出部
１３…Ｔ１乗算部
１４…Ｔ２加算部
１５…Ｄ計算部
２１…楕円曲線暗号計算部分
３１…楕円曲線暗号装置
３２…モンゴメリ変換部
３３…暗号化パラメータ格納部
３４…暗号計算部
３５…モンゴメリ逆変換部
４１…モンゴメリ演算装置
４２…暗号制御装置
５１…モンゴメリ加算装置
５２…モンゴメリ減算装置
５３…モンゴメリ乗算装置
５４…モンゴメリ除算装置
５５…乗算器
５６…モンゴメリ逆元装置
【図１】
0003542278.tif 000002
【図２】
0003542278.tif 000003
【図３】
0003542278.tif 000004
【図４】
0003542278.tif 000005
【図５】
0003542278.tif 000006
【図６】
0003542278.tif 000007
【図７】
0003542278.tif 000008
【図８】
0003542278.tif 000009
【図９】
0003542278.tif 000010