(57)【要約】【課題】ＢＭＭ法による乗算剰余算を高速化する剰余演算法を提供する。【解決手段】ＰＢＭＭ法において、Ｘ＊Ｙ＝Ｘ・Ｙ・ｒ-m  ｍｏｄ Ｍにおいて、ｒ進ｎ桁の整数である法Ｍ、ｒ進でｎ桁の被乗数Ｘ及び乗数Ｙを入力とする。そして、ステップ１では、各変数を初期化する。次に、ステップ２−１でタスクＴ1b，タスクＴ2bを並列に実行できるようにするために前処理を行う。次に、ステップ２−２においては、次に、ステップ２−２においては、サイクルｋを１からｎ／２まで１ずつ増加させ、各サイクルｋにおいて、タスクＴ1bとタスクＴ2bとを並列に実行する。次に、ステップ２−３において、ｋ＝ｎ／２となったところで、Ｃn/2とＤn/2の加算した結果を法Ｍで剰余をとり、その結果をＤn/2+1とする。続くステップ３において、Ｄn/2+1を出力Ｚとして処理を終了する。【選択図】図１
2007219261.tif 000002
【特許請求の範囲】
【請求項１】
ｒ進ｎ桁の整数Ｍ（ただし、ｒn-1＜Ｍ＜ｒn）を法とする剰余系において、前記法Ｍと互いに素でＭより小さな定数Ｒ及びｒ進ｎ桁の変数Ｘ，Ｙを用いて行う
Ｘ・Ｙ・Ｒ-1 ｍｏｄ Ｍ・・・式１
（ただし、Ｒ＝ｒm、ｍは０＜ｍ＜ｎを満たす整数）の計算において、
前記変数Ｙを、
Ｙ＝ＹH・ｒm＋ＹL・・・式２
を用いて、上位ｒ進（ｎ−ｍ）桁のＹHと下位ｒ進ｍ桁のＹLとに分割し、
前記分割したＹHをｒH進ｈ桁で表し、
Ｘ・ｙHi・ｒHi ｍｏｄ Ｍ・・・式３
（ただし、ｙHiはＹHのｉ番目の桁）をＹHの下位桁側から計算サイクルｉが０からｈ−１になるまで順次計算し、
前記分割したＹLをｒL進ｇ桁（ただし、ｒLg＝ｒm）で表し、
Ｘ・ｙLg-j・ｒL-j ｍｏｄ Ｍ・・・式４
（ただし、ｙLg-jは、ＹLのｇ−ｊ番目の桁）をＹLの上位桁側から計算サイクルｊが１からｇになるまで順次計算し、
前記式３に基づいて計算した結果と前記式４に基づいて計算した結果とを累積することによって、前記式１の計算結果を得ることを特徴とする剰余系の計算方法。
【請求項２】
変数を分割する分割手段（５）と、
変数を格納する第１格納手段（１６）及び第２格納手段（１８）と、
剰余計算を行う第１剰余算手段（２０）及び第２剰余算手段（２２）と、
２つの変数の部分積を生成する第１部分積生成手段（２４）及び第２部分積生成手段（２６）と、
計算値の累積を行いその累積結果を格納する累積値生成格納手段（２８，３０，３２，３４）と、
を備え、
前記分割手段（５）は、
ｒ進ｎ桁の整数Ｍを法とする剰余系において（ただし、Ｍとｒとは互いに素）、ｒ進でｎ桁の変数Ｙ及び変数Ｘと前記法Ｍとが入力されたときに、前記変数Ｙを上位（ｎ−ｍ）桁のＹH及び下位ｍ桁のＹLに分割し、
前記第１格納手段（１６）は、初期値を前記変数Ｘの値とする変数Ｑを格納し、
前記第２格納手段（１８）は、初期値を前記変数Ｘの値とする変数Ｓを格納し、
前記第１剰余算手段（２０）は、
計算サイクルｉに応じて、その計算サイクルｉが０からｈ−１になるまで、前記第１格納手段（１６）に格納された変数Ｑを用いて、Ｑ・ｒH ｍｏｄ Ｍを生成して新たな変数Ｑとして前記第１格納手段（１６）に格納し、
前記第１部分積生成手段（２４）は、
前記計算サイクルｉに応じて、前記第１格納手段（１６）に格納された前記変数Ｑと前記ｒH進ｈ桁で表されるＹHのｉ番目の桁ｙHiにより、Ｑ・ｙHi ｍｏｄ Ｍを生成して前記累積値生成格納手段（２８，３０，３２，３４）へ出力し、
前記第２剰余算手段（２２）は、
計算サイクルｊに応じて、その計算サイクルｊが０からｇ−１になるまで、前記第２格納手段（１８）に格納した変数Ｓを用いて、Ｓ・ｒL-1 ｍｏｄ Ｍを生成して新たな変数Ｓとして前記第２格納手段（１８）に格納し、
前記第２部分積生成手段（２６）は、
前記計算サイクルｊが１からｇになるまで、前記第２格納手段（１８）に格納された前記変数Ｓと前記ｒL進ｇ桁で表されるＹLのｇ−ｊ番目の桁ｙLg-jにより、Ｓ・ｙLg-j ｍｏｄ Ｍを生成して前記累積値生成格納手段（２８，３０，３２，３４）へ出力し、
前記累積値生成格納手段（２８，３０，３２，３４）は、
前記第１部分積生成手段（２４）の出力と前記第２部分積生成手段（２６）の出力とそれまでに生成した累積値とを前記法Ｍで加算し、その加算結果を新たな累積値として格納することを特徴とする剰余系の計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、剰余系の計算を効率よく行うための計算方法及び装置に関する。
【背景技術】
【０００２】
乗算剰余算の計算法として、二つの方法がよく知られている。一つはインターリーブ乗算剰余算アルゴリズムであり、乗数が最上位桁から順に処理される。もう一つはモンゴメリアルゴリズムであり、乗数が最下位桁から順に処理される。
【０００３】
これに対し本願発明者は、上述の二つの計算法を結合して乗算剰余算をさらに高速化した、二分乗算剰余算法（以下、ＢＭＭ（Ｂｉｐａｒｔｉｔｅ  Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎの略）法とも呼ぶ。）という計算法を提案した。
【０００４】
この方法では、乗数を二つの部分に分け、並列に処理することが可能である。法Ｍは基数ｒでｎ桁の整数とし、ｒn-1＜Ｍ＜ｒn 及び ｇｃｄ（Ｍ，ｒ）＝１ を満たすものとする。Ｕを［０，Ｍ−１］の範囲の整数とするとき、ＵのイメージあるいはＫＴ剰余Ｘを Ｘ＝Ｕ・ｒm ｍｏｄ Ｍ と定義する。ここにｍは、０＜ｍ＜ｎの整数である。これらイメージの集合はＫＴ剰余系と呼ぶ剰余系を形成する。二つのイメージＸとＹが与えられたとき、ＫＴ剰余系におけるＭを法とする乗算を下記式５
Ｘ＊Ｙ＝Ｘ・Ｙ・ｒ-m  ｍｏｄ Ｍ・・・式５
と定義する。
【０００５】
ｒmとＭとが互いに素であれば、ｒ-m  ｍｏｄ Ｍ  は必ず存在する。暗号においては、Ｍは奇数であるから、ｒ＝２kとすれば、互いに素であるという条件が満たされる。
整数の元の表現から新しい剰余系への変換は、その整数と定数ｒmとの通常の乗算剰余算により行える。新しい剰余系から元の表現への逆変換は、イメージと定数ｒ-mとの乗算剰余算で行え、モンゴメリアルゴリズムにより計算できる。
【０００６】
図５に示すように、元の整数集合ＺMとその上で定義された通常の乗算剰余算と、ＫＴ剰余系ＺM＊とその上で定義された演算＊との間には、同型の関係が成り立つ。図５において、ＸとＹはそれぞれＵとＶのイメージである。
【０００７】
この新しい剰余系表現を用いる利点は、乗算剰余算を並列に行えることにある。すなわち、ＫＴ剰余系におけるイメージＸとＹのＭを法とする乗算は、乗数ＹをＹ＝ＹH・ｒm＋ＹLとなるようにＹHとＹLの二つの部分に分けると、以下の式６により、効率よく計算できる。
【０００８】
Ｘ＊Ｙ＝（Ｘ・ＹH ｍｏｄ Ｍ ＋ Ｘ・ＹL・ｒ-m ｍｏｄ Ｍ）ｍｏｄ Ｍ・・・式６
式６のうち、Ｘ・ＹH  ｍｏｄ Ｍの項はインターリーブ乗算剰余算アルゴリズムにより計算でき（例えば、非特許文献１参照）、Ｘ・ＹL・ｒ-m  ｍｏｄ Ｍの項はモンゴメリアルゴリズムにより計算できる（例えば、非特許文献２参照）。
【０００９】
分割後の演算数ＹHとＹLはＹより短いので、Ｘ・ＹH  ｍｏｄ Ｍ 及び Ｘ・ＹL・ｒ-m  ｍｏｄ Ｍ の計算は、それぞれ、分割しない演算数で通常の乗算剰余算あるいはモンゴメリ乗算を行う場合に比べ、高速に行える。
【００１０】
この二つの計算がほぼ同じ計算速度で行え、乗数を同じ大きさの二つの部分に分割すれば、分割しない演算数に対してそれぞれのアルゴリズムを単独で用いる場合に比べ、理論的に最大二倍の高速化が可能である（例えば、非特許文献３参照）。
【００１１】
さらに、モンゴメリ法に比べ、元の剰余系とＫＴ剰余系との間の変換が最大二倍高速になり、変換に必要な定数の事前計算も不要になる。また、Ｘ・ＹH  ｍｏｄ Ｍ 及び Ｘ・ＹL・ｒ-m  ｍｏｄ Ｍの計算のそれぞれを高速化する方法が、独立に適用可能である。
【非特許文献１】E.F.Brickell, "A fast modular multiplication algorithm with application to two key cryptography," in Advances in Cryptology, Proc. CRYPTO'82, D.Chaum et al., Eds. New York: Plenum, 1983, pp.51-60.
【非特許文献２】P.L.Montgomery, "Modular Multiplication without Trial Division," Mathematics of Computation, vol.44, no.170, pp.519-521, Apr.1985.
【非特許文献３】M.E.Kaihara and N.Takagi, "Bipartite Modular Multiplication," in Cryptographic Hardware and Embedded Systems - CHES 2005, J R. Rao et al., Eds. LNCS 3659, Springer, Aug. /set. 2005,pp201-210.
【発明の開示】
【発明が解決しようとする課題】
【００１２】
ところが、上記のＢＭＭ法による計算では、このＹHに関する上位部分の計算とＹLに関する下位部分の計算との並列計算において、各々の並列処理での中間累積結果をシフトし、これに剰余計算あるいはモンゴメリ剰余計算を施していた。
【００１３】
つまり、各々の並列処理において、累積計算が必要であるので、その累積計算のためのハードウエア構成を少なくすることが困難であった。
本発明は、このような問題に鑑みなされたものであり、ＢＭＭ法による乗算剰余算を効率よく計算するとともにより簡単なハードウエア構成により乗算剰余の計算を実行できる計算方法を提供することを目的としている。
【課題を解決するための手段】
【００１４】
かかる問題を解決するためになされた請求項１に記載の剰余系の計算方法は、ｒ進ｎ桁の整数Ｍ（ただし、ｒn-1＜Ｍ＜ｒn）を法とする剰余系において、法Ｍと互いに素でＭより小さな定数Ｒ及びｒ進ｎ桁の変数Ｘ，Ｙを用いて行う、Ｘ・Ｙ・Ｒ-1 ｍｏｄ Ｍ・・・式１（ただし、Ｒ＝ｒm、ｍは０＜ｍ＜ｎを満たす整数）の計算において、変数Ｙを、Ｙ＝ＹH・ｒm＋ＹL・・・式２を用いて、上位ｒ進（ｎ−ｍ）桁のＹHと下位ｒ進ｍ桁のＹLとに分割し、分割したＹHをｒH進ｈ桁で表し、Ｘ・ｙHi・ｒHi ｍｏｄ Ｍ・・・式３（ただし、ｙHiはＹHのｉ番目の桁）をＹHの下位桁側から計算サイクルｉが０からｈ−１になるまで順次計算し、分割したＹLをｒL進ｇ桁（ただし、ｒLg＝ｒm）で表し、Ｘ・ｙLg-j・ｒL-j ｍｏｄ Ｍ・・・式４（ただし、ｙLg-jは、ＹLのｇ−ｊ番目の桁）をＹLの上位桁側から計算サイクルｊが１からｇになるまで順次計算し、式３に基づいて計算した結果と式４に基づいて計算した結果とを累積することによって、式１の計算結果を得ることを特徴とする。
【００１５】
また、「計算サイクルｉ」、「計算サイクルｊ」とは、各々式３及び式４の計算を順次実行する際のタイミングを表すものである。計算サイクルｉや計算サイクルｊの具体的な例としては、計算をＣＰＵで実行する際には、ＣＰＵを作動させるクロック等となる。
【００１６】
また、「ｙHiはＹHのｉ番目の桁」とは、ｙHiがＹHをｒH進で表したときの各桁を示していることを意味している。具体的には、ＹHがｈ桁の場合、ＹH＝［ｙHh-1，…，ｙH0］であり、最下位桁がｙH0、最上位桁がｙHh-1となる。
【００１７】
また、「ｙLg-jは、ＹLのｇ−ｊ番目の桁」とは、ｙLg-jがＹLをｒL進で表したときの各桁を示していることを意味している。具体的には、ＹLがｇ桁の場合、ＹL＝［ｙLg-1，…，ｙL0］であり、最下位桁がｙL0、最上位桁がｙLg-1となる。
【００１８】
このような、計算方法によれば、式１で示される剰余系の計算を式２で示されるように乗数Ｙを上位部分のＹHと下位部分のＹLとに分割して並列に計算できる。
そして、上位部分ＹH及び下位部分ＹLの計算結果を１箇所で累積し、最終的な計算結果を得ている。つまり、上位部分ＹH及び下位部分ＹL各々の計算で累積を行う必要がないので従来のＢＭＭ法に比べ累積計算を行う部分を減らすことができる。
【００１９】
請求項２に記載の剰余系の計算装置は、変数を分割する分割手段（５：この欄においては、発明に対する理解を容易にするため、必要に応じて「発明を実施するための最良の形態」欄において用いた符号を付すが、この符号によって請求の範囲を限定することを意味するものではない。）と、変数を格納する第１格納手段（１６）及び第２格納手段（１８）と、剰余計算を行う第１剰余算手段（２０）及び第２剰余算手段（２２）と、２つの変数の部分積を生成する第１部分積生成手段（２４）及び第２部分積生成手段（２６）と、計算値の累積を行いその累積結果を格納する累積値生成格納手段（２８，３０，３２，３４）と、を備えていることを特徴とする。
【００２０】
分割手段（５）は、ｒ進ｎ桁の整数Ｍを法とする剰余系において（ただし、Ｍとｒとは互いに素）、ｒ進でｎ桁の変数Ｙ及び変数Ｘと法Ｍとが入力されたときに、変数Ｙを上位（ｎ−ｍ）桁のＹH及び下位ｍ桁のＹLに分割する。
【００２１】
第１格納手段（１６）は、初期値を変数Ｘの値とする変数Ｑを格納し、第２格納手段（１８）は、初期値を変数Ｘの値とする変数Ｓを格納する。
第１剰余算手段（２０）は、計算サイクルｉに応じて、その計算サイクルｉが０からｈ−１になるまで、第１格納手段（１６）に格納された変数Ｑを用いて、Ｑ・ｒH ｍｏｄ Ｍを生成して新たな変数Ｑとして第１格納手段（１６）に格納する。
【００２２】
第１部分積生成手段（２４）は、計算サイクルｉに応じて、第１格納手段（１６）に格納された変数ＱとｒH進ｈ桁で表されるＹHのｉ番目の桁ｙHiにより、Ｑ・ｙHi ｍｏｄ Ｍを生成して累積値生成格納手段（２８，３０，３２，３４）へ出力する。
【００２３】
第２剰余算手段（２２）は、計算サイクルｊに応じて、その計算サイクルｊが０からｇ−１になるまで、第２格納手段（１８）に格納した変数Ｓを用いて、Ｓ・ｒL-1 ｍｏｄ Ｍを生成して新たな変数Ｓとして第２格納手段（１８）に格納する。
【００２４】
第２部分積生成手段（２６）は、計算サイクルｊが１からｇになるまで、第２格納手段（１８）に格納された変数ＳとｒL進ｇ桁で表されるＹLのｇ−ｊ番目の桁ｙLg-jにより、Ｓ・ｙLg-j ｍｏｄ Ｍを生成して累積値生成格納手段（２８，３０，３２，３４）へ出力する。
【００２５】
累積値生成格納手段（２８，３０，３２，３４）は、第１部分積生成手段（２４）の出力と第２部分積生成手段（２６）の出力とそれまでに生成した累積値とを法Ｍで加算し、その加算結果を新たな累積値として格納する。
【００２６】
このような構成の剰余系の計算装置によれば、従来のＢＭＭ法による剰余系の計算装置に比べ、累積計算をする部分を減らすことができるので、ハードウエアの構成を少なくすることができる。
【００２７】
つまり、従来のＢＭＭ法による剰余系の計算装置では、式１で示されるＸ・Ｙ・Ｒ-1 ｍｏｄ Ｍの計算を式２で示されるＹ＝ＹH・ｒm＋ＹLによって分割した後の上位部分ＹH及び下位部分ＹLの各々の計算において、桁のシフトと部分積の計算と累積計算とを行い、各々の計算で得られた結果を加算して最終的な計算結果を得ていた。
【００２８】
それに対し、請求項２に記載の剰余系の計算装置では、分割手段（５）で式１の乗数Ｙを上位部分ＹHと下位部分ＹLとに分割した後、分割した上位部分ＹHの計算を基数ｒHで、第１格納手段（１６）と、第１剰余算手段（２０）と、第１部分積生成手段（２４）とで計算し、下位部分ＹLの計算を基数ｒLで、第１格納手段（１８）と、第２剰余算手段（２２）と、第２部分積生成手段（２６）とで計算する。そして、各々の計算結果を１箇所で累積して最終的な計算結果を得ている。
【００２９】
すなわち、請求項２に記載の剰余系の計算装置では、上位部分ＹH及び下位部分ＹLの各々計算で累積を行う必要がないので、従来のＢＭＭ法による剰余系の計算装置に比べ累積計算を行う部分を減らすことができるのである。
【発明を実施するための最良の形態】
【００３０】
以下、本発明が適用された実施形態について図を用いて説明する。なお、本発明の実施の形態は、下記の実施形態に何ら限定されることはなく、本発明の技術的範囲に属する限り種々の形態を採りうる。
【００３１】
［第１実施形態］
本発明の１つの実施形態として、本発明に係る剰余系の計算方法を適用したパイプライン二分乗算剰余算（以下、ＰＢＭＭ法：Ｐｉｐｅｌｉｎｅｄ  Ｂｉｐａｒｔｉｔｅ  Ｍｏｄｕｌａｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ法の略、とも呼ぶ。）の処理について、図１に基づき説明する。なお、ＰＢＭＭ法においては、計算を高速化するために、累積の計算ステップを二段パイプライン化してある。図１は、ＰＢＭＭ法の処理ステップを示した図である。
【００３２】
ＰＢＭＭ法においては、前述した式５
Ｘ＊Ｙ＝Ｘ・Ｙ・ｒ-m  ｍｏｄ Ｍ・・・式５
において、ｒ進ｎ桁の整数である法Ｍ（ただし、ｒとＭとは互いに素），ｒ進でｎ桁の被乗数Ｘ及び乗数Ｙを入力とする。また、ここでは、簡単のためにｍがｎ／２である場合の処理について述べる。ここに、ｎは偶数とする。なお、ｎが奇数の場合は、乗数Ｙの最上位に０を付加すればよい。
【００３３】
したがって、本処理の出力Ｚは下記式７となる。
Ｚ＝Ｘ・Ｙ・ｒ-m ｍｏｄ Ｍ・・・式７
ステップ１では、各変数を初期化する。具体的には、ｎ桁の変数Ｑkと変数Ｓkとを用意し、各々を被乗数Ｘの値に初期化する。つまり、Ｑ0＝Ｘ、Ｓ0＝Ｘとする。
【００３４】
また、乗数Ｙをｎ／２桁の上位桁ＹHとｎ／２桁の下位桁ＹLに分割し、各々の最上位に０を付加し、０を付加したＹHとＹLとを各々（ｎ／２＋１）桁の変数Ａと変数Ｂとに格納する。つまり、Ａ＝ＹH、Ｂ＝ＹLとする。
【００３５】
なお、図１中の｛０，ＹH｝及び｛０，ＹL｝は、各々、ＹH及びＹLの最上位に０を付加した数を表わしている。
変数Ｑkと変数Ａとは、Ｘ・ＹH  ｍｏｄ Ｍ の部分積を生成するために用い、変数Ｓkと変数ＢとはＸ・ＹL・ｒ-m  ｍｏｄ Ｍ の部分積を生成するために用いる。
【００３６】
ステップ２では、まず、ステップ２−１において、後述するステップ２−２で２つのタスク（タスクＴ1b，タスクＴ2b）を並列に実行できるようにするために前処理を行う。
具体的には、
（１）中間累算結果を格納するためのｎ桁の変数Ｄを０に初期化する。
【００３７】
（２）ステップ１において初期化された変数Ｑ0を上位桁方向にシフトし、法Ｍで剰余をとってＱ1とする。
（３）ステップ１において初期化された変数Ｓ0を下位桁方向にシフトし、法Ｍで剰余をとってＳ1とする。
【００３８】
（４）変数Ａの最下位桁ａ0とＱ0との部分積及び変数Ｂの最上位桁（ｎ／２桁目）ｂn/2とＳ0との部分積を加算し、その加算結果の法Ｍによる剰余をｎ桁の変数Ｃ0に格納することによって、変数Ｃを初期化する。
【００３９】
なお、変数Ａ、変数Ｂのｋ番目の桁（ｋ＝０，１，２，・・・，ｎ／２）をａk，ｂkと表す。すなわち、下記式８ａ、式８ｂとなる。
【００４０】
【数１】
2007219261.tif 000003
【００４１】
このステップ２−１においては、（１）〜（４）を並列処理で実行する。
次に、ステップ２−２においては、サイクルｋを１からｎ／２まで１ずつ増加させ、各サイクルｋにおいて、タスクＴ1bとタスクＴ2bとを並列に実行する。
【００４２】
タスクＴ1b
（５）Ｑkを上位桁方向にシフトし、法Ｍで剰余をとってＱk+1とする。
（６）Ｓkを下位桁方向にシフトし、法Ｍで剰余をとってＳk+1とする。
【００４３】
（７）変数Ａのｋ桁目ａkとＱkとの部分積及び変数Ｂの（ｎ／２−ｋ）桁目ｂn/2-kとＳkとの部分積を加算し、その加算結果の法Ｍによる剰余をとる。そして、その剰余をＣkに格納する。
【００４４】
つまり、Ａの桁は下位から順に処理し、Ｂの桁は上位から順に処理する。各桁はシフトにより取り出す。
このタスクＴ1bにおいては、（５）〜（７）を並列に実行する。
【００４５】
タスクＴ2b
（８）１サイクル前の値Ｃk-1，Ｄk-1を加算し、その加算結果の法Ｍによる剰余をとり、Ｄkに格納する。
【００４６】
次に、ステップ２−３において、ｋ＝ｎ／２となったところで、Ｃn/2とＤn/2の加算した結果を法Ｍで剰余をとり、その結果をＤn/2+1とする。
続くステップ３において、Ｄn/2+1を出力Ｚとして処理を終了する。
【００４７】
以上に説明した処理のうちステップ２中では、パイプライン処理が実行されており、そのパイプライン処理のタスクの依存グラフを図２に示す。
このように、ＰＢＭＭ法の処理の各ステップの１回の繰返し計算を１サイクルで行うと、タスクＴ1bとタスクＴ2bとを１サイクルごとにパイプライン処理を行うので、乗算剰余算がｎ／２＋４サイクルで実行できる。
【００４８】
なお、ここでは、ｍがｎ／２、つまり、ＹHとＹLとが同じ桁数であるとして説明したが、ｍがｎ／２でない場合には、ＹHに対する計算とＹLに対する計算とがほぼ同じサイクル数で行えるように基数ｒHとｒLとを調整すればよい。例えば、ｍ＝２ｎ／３ならｒH＝２，ｒL＝４とすればよい。
【００４９】
［第２実施形態］
次に、第２実施形態として、ＰＢＭＭ法の処理を行うためのパイプライン二分乗算剰余算器（以下、ＰＢＭＭ乗算器とも呼ぶ。）について図３に基づき説明する。
【００５０】
本第２実施形態においては、基数４で乗数Ｙを分割した上位部分ＹHと下位部分ＹLとが同じ桁数の場合の実施形態を示す。すなわち、ｒ＝４、ｍ＝ｎ／２である。また、法Ｍは２進表現でｎ’ビットであるとする。つまり、２n'-1＜Ｍ＜２nで、ｎ’が偶数であればｎ＝ｎ’／２であり、ｎ’が奇数であればｎ＝（ｎ’＋１）／２である。また、ｒH＝ｒL＝４とする。
【００５１】
さらに、すべての加算及び減算を桁上げの伝搬なしに行うため、基数２の符号付きディジット表現（ＳＤ２表現）を用いる。このＳＤ２表現については、文献１「Ｎ. Takagi and S. Yajima, "Modular multiplication hardware algorithms with a redundant representation and their application to RSA cryptosystem," IEEE Trans. Computers, vol.41, no.7, pp.887-891, July 1992.」等に示されているので説明は省略する。
【００５２】
ＳＤ２表現では、桁集合は｛１，０，−１｝である。（ｎ’＋１）桁のＳＤ２整数 Ｑ＝［ｑn' ｑn'-1・・・ｑ0］（ｑi∈｛１，０，−１｝）は、下記式９で示される値をもつ。
【００５３】
【数２】
2007219261.tif 000004
【００５４】
ここで、２つのＳＤ２数の加算は桁上げの伝搬なしに行える。
暗号処理においては、乗算剰余算が連続して行われる。各乗算で、出力をＳＤ２表現から通常の２進表現へ変換することなくそのまま次の乗算の入力として用いるために、入力と出力を同じＳＤ２表現で表す。ＸとＹ、Ｚは、［−Ｍ＋１，Ｍ−１］の範囲のｎ’＋１桁のＳＤ２数となる。
【００５５】
（全体構成の説明）
図３は、基数ｒ＝４の場合のＰＢＭＭ乗算器１のブロック図である。図３に示すようにＰＢＭＭ乗算器１は、法Ｍを格納するためのレジスタ１０、分割された２つの乗数を格納するための２つのＳＤ２シフトレジスタ１２，１４、ＳＤ２数を格納するための３つのＳＤ２レジスタ１６，１８，３０、２つの剰余算器２０，２２、２つの加算剰余算器２８，３２、部分積を計算するための部分積生成器２４，２６、中間累積結果を格納するためのＳＤ２レジスタ３４等を備えている。
【００５６】
（各構成要素の説明）
レジスタ１０は、入力されたｒ（＝４）進、ｎ桁の法Ｍを格納するためのＳＤ２レジスタである。
【００５７】
分割回路５は、入力されたｒ進、ｎ桁の変数Ｙを上位ｎ／２桁のＹHと下位ｎ／２桁のＹLとに分割するための回路である。
ＳＤ２シフトレジスタ１２は、分割された上位部分ＹHを格納し、各サイクルで１桁下位桁側にシフトするためのレジスタであり、ｎ／２桁に加え、最上位に少なくとも１つの０を付加できるだけの桁数を有している。ＳＤ２シフトレジスタ１４は、分割された下位部分ＹLを格納し、各サイクルで１桁上位桁側にシフトするためのレジスタであり、ｎ／２桁に加え最上位に少なくとも１つの０を付加できるだけの桁数を有している。
【００５８】
ＳＤ２レジスタ１６，１８は、入力されたｒ進、ｎ桁の変数Ｘを複製したｒ進、ｎ桁の変数Ｑ及びＳを格納するためのレジスタであり、ＳＤ２レジスタ３０は、加算剰余算器２８の計算結果を格納するためのｒ進、ｎ桁のレジスタである。
【００５９】
剰余算器２０は、ＳＤ２レジスタ１６に格納された変数Ｑをｒ倍した値の剰余算を行うものであり、剰余算器２２は、ＳＤ２レジスタ１８に格納された変数Ｓをｒ-1倍した値の乗算剰余算を行うものである。
【００６０】
部分積生成器２４は、ＳＤ２レジスタ１６に格納されている変数ＱとＳＤ２シフトレジスタ１２に格納されている変数Ａの最下位桁のａ0との積を計算し、加算剰余算器２８に出力するためのものである。また、部分積生成器２６は、ＳＤ２レジスタ１８に格納されている変数ＳとＳＤ２シフトレジスタ１４に格納されている変数Ｂの最上位桁のｂn/2との積を計算し、加算剰余算器２８に出力するためのものである。
【００６１】
加算剰余算器２８は、部分積生成器２４，２６の計算結果を加算し、法Ｍで剰余計算を行ってＳＤ２レジスタ３０に変数Ｃとして格納する。
また、加算剰余算器３２は、ＳＤ２レジスタ３０に格納された変数ＣとＳＤ２レジスタ３４に格納された変数Ｄを加算したものを法Ｍで剰余計算を行い、ＳＤ２レジスタ３４に変数Ｄとして格納する。
【００６２】
変数Ｃを格納するＳＤ２レジスタ３０及び変数Ｄを格納するＳＤ２レジスタ３４は、−２・Ｍ＜Ｃ＜２・Ｍを満たす（ｎ’＋２）桁のＳＤ２数を格納するレジスタである。
（ＰＢＭＭ乗算器１における計算処理）
以上のように構成されたＰＢＭＭ乗算器１における計算処理について説明する。
【００６３】
ＰＢＭＭ乗算器１には、ｒ進、ｎ桁の変数Ｙ、変数Ｘ及び法Ｍが入力される。
入力された変数Ｙは、分割回路５に入力され、変数Ｘは、ＳＤ２レジスタ１６及びＳＤ２レジスタ１８に各々変数Ｑ及びＳとして格納される。また、法Ｍは、レジスタ１０に格納される。
【００６４】
分割回路５に入力された変数Ｙは、ｎ／２桁の上位部分ＹHとｎ／２桁の下位部分ＹLとに分割され、各々ＳＤ２シフトレジスタ１２及びＳＤ２シフトレジスタ１４に変数Ａ，Ｂとして格納される。
【００６５】
なお、計算を高速化するために、変数Ａ及びＢに２ビット冗長ブースの方法を適用する。この２ビット冗長ブースの方法については、文献２「N. Takagi, "A radix-4 modular multiplication hardware algorithm for modular exponentiation," IEEE Trans. Comput., vol.41, no.8, pp.949-956, Aug,1990.」等に示されているので詳細の説明は省略する。
【００６６】
ｎ’／２ビットの２進表現の（分割された）乗数はｎ／２＋１桁の基数４の数にリコードされる。リコード後のＡのｋ桁目をａkとする。リコード後のＢのｋ桁目をｂkとする。変数Ｂのリコードの規則を表１に示す。変数Ａも同じ規則でリコードできる。桁上げの伝搬方向を考慮すると、規則を簡単化できる。
【００６７】
【表１】
2007219261.tif 000005
【００６８】
また、前述の記法に従うと、分割された上位部分のＹHに関する乗算剰余算であるＸ・ＹH  ｍｏｄ Ｍ の計算に用いる変数Ｑは、数γ∈ＺMを−ｄ・Ｍ＜Ｑ＜ｄ・Ｍ かつ Ｑ≡γ（ｍｏｄ  Ｍ）を満たす（ｎ’＋１）桁のＳＤ２表現で保持している。ｄはパラメータであり、５／８≦ｄ≦２／３を満たす数である。
【００６９】
ここで、これらの値の導出過程を説明する。シフトと剰余計算は次の漸化式に基づく。
Ｑk+1：＝４・Ｑk−ｐk・Ｍ
ｐkは｛２，１，０，−１，−２｝から選ぶ。これにより、剰余計算は、０ 又は ±Ｍ 又は ±２Ｍ、すなわち、シフト及び補数計算で求まる数の加算により実現できる。Ｑk+1が −ｄ・Ｍ＜Ｑ＜ｄ・Ｍ を満たすには、下記式１０が成り立たなければならない。
【００７０】
４・ｄ・Ｍ−２・Ｍ≦ｄ・Ｍ・・・式１０
この式より、ｄ≦２／３を得る。
次に、ｐkを決定するために何桁を調べなければならないかを考える。４・Ｑkと±Ｍ／２、±３Ｍ／２を、α桁目まで比較するものとする。下記式１１を満たす最大のαを求めればよい。
【００７１】
２・２α≦（ｄ−１／２）・Ｍ・・・式１１
Ｍは２n'-1＋１以上であるから、α≦ｎ’−２＋ｌｏｇ2（ｄ−１／２）でなければならない。ｄ≦２／３であるから、αは最大ｎ’−５である。逆に、ｄ≧５／８であればα
はｎ’−５となる。剰余計算を表すロバートソン図を図４に示す。
【００７２】
次に、剰余計算の手順について説明する。ｐkは、４・Ｑkと±Ｍ／２、±３Ｍ／２をｎ’−５桁目まで比較して、｛２，１，０，−１，−２｝から選ぶ。ｔｏｐ（Ｗ）を数Ｗの最上位のｎ’−５桁目までの部分の値を求める関数とすると、ｐkを決定する規則は、下記式１２に示すようになる。
【００７３】
【数３】
2007219261.tif 000006
【００７４】
ｔｏｐ（Ｑk）はＱkの上位６桁から求められる。ｔｏｐ（Ｍ／２）はＭの上位４桁から求められる。ｔｏｐ（３Ｍ／２）は、｜３Ｍ／２−ｔｏｐ（３Ｍ／２）｜≦２n`-4を満たすように、Ｍの上位５桁から求められる。Ｍは非冗長表現であるから、Ｑk+1を求めるための±Ｍあるいは±２Ｍの加算は通常のＳＤ２数の加算より簡単である。詳しくは前述の文献２に記載されているので説明は省略する。
【００７５】
このようにして計算された変数Ｑは、部分積生成器２６に出力される。
一方、分割された下位部分ＹLに関する乗算剰余算であるＸ・ＹL・ｒ-n/2  ｍｏｄ Ｍ の計算に用いる変数Ｓは、−２・Ｍ＜Ｓ＜２・Ｍを満たす（ｎ’＋２）桁のＳＤ２数を保持している。
【００７６】
そして、剰余算器２２及びＳＤ２レジスタ１８で実行されるシフトとモンゴメリ剰余計算、すなわち、Ｓ／４  ｍｏｄ  Ｍ の計算は、関数ＭＱＲＴＲ（Ｒ，Ｍ）を用いて行う。この関数の実現法については、文献３「M.E.Kaihara and N.Takagi," A Hardware Algorithm for Modular Multiplication/Division," IEEE Trans. Computers, vol. 54, no.1, pp 12-, Jan.2005.」等に示されているので説明は省略する。
【００７７】
このようにして計算された変数Ｑは、部分積生成器２４に出力される。
以上に説明した、上位部分ＹH（変数Ｑ）及び下位部分ＹL（変数Ｓ）の計算は並列処理される。そして、得られた計算結果（変数Ｑ，変数Ｓ）に基づき部分積の生成が実行される。
【００７８】
部分積の生成のうち上位桁ＹHに関する部分積、ａk・Ｑkの生成は、ＳＤ２シフトレジスタ１２、ＳＤ２レジスタ１６、部分積生成器２４で実行される。このとき、Ａは、サイクルごとに下位桁側へシフトされるので、ａkは最下位桁から取り出すことができる。
【００７９】
また、下位桁ＹLに関する部分積、ｂn/2-k・Ｓkの生成は、ＳＤ２シフトレジスタ１４、ＳＤ２レジスタ１８、部分積生成器２６で実行される。このとき、Ｂは、サイクルごとに上位桁側へシフトされるので、ｂn/2-kは、最上位桁から取り出すことができる。
【００８０】
そして、上位部分と下位部分の部分積が生成されたら、その結果に基づき、加算剰余算器２８で部分積の加算、すなわち、Ｃk＝（ａk・Ｑk＋ｂn/2-k・Ｓk）ｍｏｄ  Ｍ の計算が行われ、結果Ｃkは、ＳＤ２レジスタ３０に格納される。
【００８１】
この計算においては、剰余計算を簡単にするため、より冗長度の大きな数表現を用いる。剰余計算後の和を記憶する変数Ｃは、−２・Ｍ＜Ｃ＜２・Ｍを満たす（ｎ’＋２）桁のＳＤ２数を保持する。
【００８２】
部分積を足し合わせた後、ａk・Ｑk＋ｂn/2-k・Ｓkの上位３桁の値が負か０か正であるかにより、２Ｍか０か２Ｍ’を加える。ここに、Ｍ’＝[１０ｍ’n'-2・・・ｍ’1１]は、値が−Ｍの（ｎ’＋１）桁のＳＤ２数で、m’i はｍiが０なら１、１なら０である。この加算剰余算の計算法については、前述した文献１に説明されているためここでは説明を省略する。
【００８３】
次に、上述の加算結果をＤに保持されている中間累算結果に加える。Ｄも、−２・Ｍ＜Ｄ＜２・Ｍを満たす（ｎ’＋２）桁のＳＤ２数を保持している。加算後の剰余計算は、上述の部分積の和に対する剰余計算と同じように行う。ステップ３で得られた結果を−Ｍ＜Ｄ＜Ｍの範囲に戻すには、シフトを行い、同じ規則で剰余計算を行えばよい。Ｄの上位ｎ’＋１桁が最終結果となる。
【００８４】
ここで述べた基数ｒが４の場合のハードウェアアルゴリズムは、２つの剰余算器２０，２２、２つの加算剰余算器２８，３２、ＳＤ２数を保持する３つのＳＤ２レジスタ１６，１８，３４、中間累算結果を保持するＳＤ２レジスタ３０、法Ｍを保持するレジスタ１０、分割された２つの乗数を保持する２つのＳＤ２シフトレジスタ１２，１４によって実現できる。
【００８５】
ＳＤ２加算器が桁上げ保存加算器で実現できること（詳細は、P.Kornerup, "Reviewing 4-to-2 Adders for Multi-Operand Addition," Proc. The IEEE Int. Conf, Application-Specific Systems, Architectures, and Processors, ASAP02, San Jose, California, pp.218-229, July 17-19, 2002に示されているので省略する。）、及び、ここでの実現における剰余計算にＡＮＤゲート一段分の遅延が余分にかかることを考慮すると、ＰＢＭＭ乗算剰余算器は、基数１６のパイプラインモンゴメリ乗算器（詳細は、H.Orup, "Simplifying quotient determination in higher-radix modular multiplication,"  Proc. 12th IEEE Symp.  Computer Arithmetic, S.Knowles and W.H.McAllister, eds., pp.193-199, Bath,  England, 1995.に示されているので省略する。)と同程度のパーフォーマンスを有するといえる。
【００８６】
以上に説明したＰＢＭＭ乗算器１では、初期値として被乗数Ｘを記憶している変数に対する剰余計算が、生成された部分積の加算と並列に行えるので、このときサイクル時間は増加しない。
【００８７】
したがって、パイプラインステージ数を減らすことができ、中間結果を記憶するステージ間のレジスタの数も減らすことができる。具体的には、基数１６のパイプラインモンゴメリ乗算器と比べ、同程度の性能を得るのに、パイプラインステージが２つ少なくなり、加算器が１つ、ｎ桁のＳＤ２レジスタが３つ、そして複雑なマルチプレクサが少なくて済む。
【００８８】
以上、本発明の実施形態について説明したが、本発明は、前述した実施形態に限定されるものではなく、種々の態様を採ることができる。
例えば、本実施形態では、乗算剰余算の効率よい計算法として、基数を４とし、ｍ＝ｎ／２の場合（すなわち乗数を同じ大きさの二つの部分に分ける場合）について説明したが、剰余計算とモンゴメリ剰余計算のクリティカルパス遅延が異なるときにはｍに異なる値を割り当てればよい。その場合、ｍの値は両者の効率（遅延）の差から計算され、一方の計算は高基数で行えばよい。
【００８９】
その場合、分割回路５において、ｎ桁の変数Ｙを（ｍ−ｎ）桁の上位部分のＹHとｍ桁の下位部分のＹLとに分割するためにパラメータｍを、分割回路５の内部にあらかじめ設定していてもよいし、外部から入力されるようになっていてもよい。
【図面の簡単な説明】
【００９０】
【図１】ＰＢＭＭ法の処理ステップを示した図である。
【図２】ＰＢＭＭ法の処理のうちステップ２中のタスクの依存グラフの図である。
【図３】基数ｒ＝４のＰＢＭＭ乗算器１のブロック図である。
【図４】剰余計算を表すロバートソン図である。
【図５】元の整数集合ＺＭとその上で定義された通常の乗算剰余算と、ＫＴ剰余系ＺＭ＊とその上で定義された演算＊との間の関係を示す図である。
【符号の説明】
【００９１】
１…ＰＢＭＭ乗算器、５…分割回路、１０…レジスタ、１２，１４…ＳＤ２シフトレジスタ、１６，１８，３０，３４…ＳＤ２レジスタ、２０，２２…剰余算器、２４，２６…部分積生成器、２８、３２…加算剰余算器。
【図１】
2007219261.tif 000007
【図２】
2007219261.tif 000008
【図３】
2007219261.tif 000009
【図４】
2007219261.tif 000010
【図５】
2007219261.tif 000011