(57)【特許請求の範囲】
【請求項１】
剰余演算機能を有する複数の積和回路と、この積和回路における剰余演算に用いられる補正項を計算する補正項計算ユニットとを備えた剰余演算装置において、
前記補正項計算ユニットは、前記補正項を１ビットずつ逐次計算することにより１ビットデータを出力し、
前記積和回路の各々は、
第一の入力値と第二の入力値とを乗算して乗算結果を得る乗算器と、
前記乗算結果に対して第一のレジスタからのレジスタフィードバック値を加算する加算器と、
前記第二の入力値を保持する第二のレジスタの値を前記加算器に入力するか否かを前記１ビットデータにより制御するスイッチと、
前記加算器による加算結果を前記第二の入力値で除した余りを演算し、前記第一のレジスタに出力する剰余演算器とを具備し、
前記補正項計算ユニットにより計算された前記補正項を逐次反映させて基底変換もしくは基底拡張を行うことを特徴とする剰余演算装置。
【請求項２】
前記積和回路は、モンゴメリ(Montgomery)乗算を行うことを特徴とする請求項１記載の剰余演算装置。
【請求項３】
複数並列に配置された積和回路と、この積和回路における剰余演算に用いられる補正項を計算する補正項計算ユニットとを備えた剰余演算処理装置において、
前記補正項計算ユニットは、前記補正項を１ビットずつ逐次計算することにより１ビットデータを出力し、
前記積和回路の各々は、
第一の入力値と第二の入力値とを乗算して乗算結果を得る乗算器と、
前記乗算結果に対して第一のレジスタからのレジスタフィードバック値を加算する加算器と、
前記第二の入力値を保持する第二のレジスタの値を前記加算器に入力するか否かを前記１ビットデータにより制御するスイッチと、
前記加算器による加算結果を前記第二の入力値で除した余りを演算し、前記第一のレジスタに出力する剰余演算器とを具備し、
前記補正項計算ユニットにより計算された前記補正項を逐次反映させて剰余演算系表現を基数表現に変換する演算を行うことを特徴とする剰余演算装置。
【請求項４】
前記補正項計算ユニットは、除算回路を有し、
前記積和回路で扱われる剰余演算系の基底を２の冪、もしくは２の冪に近接するものとすることを特徴とする請求項１乃至３のいずれか一項に記載の剰余演算装置。
【請求項５】
前記補正項計算ユニットへの入力ビットを選択するビット選択部を更に備えたことを特徴とする請求項１乃至４のいずれか一項に記載の剰余演算装置。
【請求項６】
外部とのデータの入出力を行うＩ／Ｏ部を更に備えたことを特徴とする請求項１乃至５のいずれか一項に記載の剰余演算装置。
【請求項７】
剰余演算系における所定の演算アルゴリズムにおいてある基底を他の基底に基底変換又は基底拡張する剰余演算装置において、
前記基底変換又は基底拡張の未知パラメータｋを、該未知パラメータｋの前回計算結果の累積加算により生じた桁上がりに近似して出力するｋ出力手段と、
基底要素毎に前記基底変換又は基底拡張の計算を行う複数の演算ユニットであって、
第一の入力値と第二の入力値とを乗算して乗算結果を得る乗算器と、
前記乗算結果に対して第一のレジスタからのレジスタフィードバック値を加算する加算器と、
前記第二の入力値を保持する第二のレジスタの値を前記加算器に入力するか否かを前記未知パラメータｋに相当する１ビットデータにより制御するスイッチからなり、前記未知パラメータｋに応じて前記基底変換又は基底拡張における特定項の計算可否を切り替える切替手段と、
前記加算器による加算結果を前記第二の入力値で除した余りを演算し、前記第一のレジスタに出力する剰余演算器とを具備する演算ユニットと、
を具備することを特徴とする剰余演算装置。
【請求項８】
前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似することを特徴とする請求項７に記載の剰余演算装置。
【請求項９】
ビット選択手段をさらに具備し、前記ｋ出力手段は中国剰余定理に基づく前記未知パラメータｋの計算式の分子を、前記ビット選択手段による有効ビット長以外の切り捨てに基づいて近似することを特徴とする請求項７に記載の剰余演算装置。
【請求項１０】
前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似するとともに、該計算式の分子を、有効ビット長以外の切り捨てに基づいて近似することを特徴とする請求項７に記載の剰余演算装置。
【請求項１１】
前記所定の演算アルゴリズムは、入力された整数ｘ，ｙ，Ｎに対して、ｘｙＢ−１ mod ＮまたはｘｙＢ−１ mod Ｎ＋Ｎを出力するモンゴメリ乗算アルゴリズムから構成されることを特徴とする請求項７に記載の剰余演算装置。
【請求項１２】
前記モンゴメリ乗算を用いた所定のアルゴリズムに従ってべき乗剰余算を行う手段を具備することを特徴とする請求項１１に記載の剰余演算装置。
【請求項１３】
中国剰余定理に基づく未知パラメータを含む所定の計算式に従って、剰余演算系表現を基数表現に変換して出力する変換手段を具備することを特徴とする請求項７に記載の剰余演算装置。
【請求項１４】
剰余演算系における所定の演算アルゴリズムにおいてある基底を他の基底に基底変換又は基底拡張する剰余演算装置において、
第一の入力値と第二の入力値とを乗算して乗算結果を得る乗算器と、
前記乗算結果に対して第一のレジスタからのレジスタフィードバック値を加算する加算器と、
前記第二の入力値を保持する第二のレジスタの値を前記加算器に入力するか否かを１ビットデータにより制御するスイッチと、
前記加算器による加算結果を前記第二の入力値で除した余りを演算し、前記第一のレジスタに出力する剰余演算器とを具備し、基底要素毎に前記基底変換又は基底拡張の計算を行う複数の演算ユニットと、
前記複数の演算ユニットのそれぞれに設けられ、前記基底変換又は基底拡張の未知パラメータｋを、該未知パラメータｋの前回計算結果の累積加算により生じた桁上がりに近似し、該未知パラメータｋを前記１ビットデータとして出力するｋ出力手段と、
当該演算ユニットのオペランドを隣接する演算ユニットに送信し、及び隣接する他の演算ユニットからのオペランドを受信する演算ユニット間の接続手段と、を具備することを特徴とする剰余演算装置。
【請求項１５】
前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似することを特徴とする請求項１４に記載の剰余演算装置。
【請求項１６】
前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分子を、有効ビット長以外の切り捨てに基づいて近似することを特徴とする請求項１４に記載の剰余演算装置。
【請求項１７】
前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似するとともに、該計算式の分子を、有効ビット長以外の切り捨てに基づいて近似することを特徴とする請求項１４に記載の剰余演算装置。
【請求項１８】
前記所定の演算アルゴリズムは、入力された整数ｘ，ｙ，Ｎに対して、ｘｙＢ−１ mod ＮまたはｘｙＢ−１ mod Ｎ＋Ｎを出力するモンゴメリ乗算アルゴリズムから構成されることを特徴とする請求項１４に記載の剰余演算装置。
【請求項１９】
前記モンゴメリ乗算を用いた所定のアルゴリズムに従ってべき乗剰余算を行う手段を具備することを特徴とする請求項１８に記載の剰余演算装置。
【請求項２０】
中国剰余定理に基づく未知パラメータを含む所定の計算式に従って、剰余演算系表現を基数表現に変換して出力する変換手段を具備することを特徴とする請求項１４に記載の剰余演算装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、剰余演算系に基づき大きな整数の演算を並列処理により高速に計算する剰余演算処理装置及び方法に関する。
【０００２】
【従来の技術】
大きな整数を効率良く演算するための手法として剰余演算系（Modular ArithmeticまたはResidue Number System）が知られている。剰余演算系では、互いに素な比較的小さな整数の組{a1, a2,…, an}を用意し、表現対象となる大きな整数をこれらの整数で割った余りで表現する。以後、この整数の組を剰余演算系の基底(base)と称する。また、要素数ｎを基底サイズと称する。
【０００３】
例えば基底{a1, a2,…, an}が与えられている場合、整数ｘは、これを基底ai(i=1,2,...,n)で除して得られるｎ個の余り{x1, x2,…, xn}により表現される。このとき、数xが基底要素の積Ａ(=a1a2…an)未満の正整数であれば、数xは基底要素の積Ａを法として一意に表現できる。言いかえれば、数xとその剰余演算系表現{x1, x2,…, xn}は一対一に対応する。
【０００４】
このような剰余演算系表現において２つの整数x，yの積を計算するには、まず、各要素毎の積を求め、さらに、対応する基底aiで除した余りを求める。これは、一般的には、各要素毎に対応する基底aiを法とする積を計算することで基底要素の積Ａを法とする積が求められることと言い換えられる。加算および減算についても同様であり、基底aiに対応する要素xi，yiについて、aiを法とする加算あるいは減算をすればよい。
【０００５】
このような剰余演算系を用いた演算では、乗算・加算・減算は、各要素毎独立に対応する基底を法とする演算を行えば良いのであるが、例えば基底として計算機のワード長以内の値を採用することで、非常に大きな整数の演算を単精度の演算の繰り返しによって実現できる。
【０００６】
また、それらの単精度演算は基底毎で独立して実行できるので、演算器を複数用意することで並列処理が可能になる。例えば、基底サイズがｎの場合、剰余機能付き乗算器をｎ個用意し、これらを並列に動作させることによって、１回の単精度剰余付き乗算と同じ時間内で基底要素の積Ａを法とする乗算を終えることができる。
【０００７】
現在の計算機内では、２進数表現が用いられているのが通常である。２進数表現に基づく大きな整数の演算では、LSB(Least Significant Bit)からMSB(Most Significant Bit)に向けて桁上がり（キャリー）が伝播し、大きな整数の全桁数（あるいはビット長）に比例した処理時間がかかる。したがって、剰余演算系を用いて並列処理した場合に比べて処理速度の点で不利である。
【０００８】
一方、剰余演算系はワード間の桁上りが生じないので２進数表現で代表される基数法(Radix representation)に比べ、大きい整数の乗算・加算・減算を効率良く行うための方式として古くから知られてきた。
【０００９】
しかしながら、除算や２数の大小比較については基数法に比べ効率良く行う手段は知られていなかった。このため公開鍵暗号のような大きな整数の演算を高速に行う応用に剰余演算系が適していると考えられながら、８０年代までは剰余演算系を具体的にどう適用したら良いか知られていなかった。
【００１０】
そして、PoschらはIEEE Transaction on Parallel and Distributed Systems, Vol.6, No.5, May 1995, pp.449-454に掲載された”Modulo Reduction in Residue Number Systems”およびComputer & Security誌 Vol.17, pp.637-650, 1998の”RNS-Modulo Reduction Upon a Restricted Base Value Set and its Applicability to RSA Cryptography”において、剰余演算系を利用し、公開鍵暗号系のRSA暗号法(RSA cryptography)の演算を高速に行う方式を提案した。
【００１１】
また、Kornerupらは13th IEEE Symposium on Computer Arithmetic (Proceedings of ARITH13), IEEE Computer Society, pp234-239の”An RNS Montgomery Modular Multiplication Algorithm”において、またPaillierはSpringer-Verlag, Lecture Notes in Computer Science No.1560 Public Key Cryptography (PKC’99), pp.223-234の“Low-Cost Double-Size Modular Exponentiation or How to Stretch Your Cryptoprocessor”において、類似の高速演算方式を提案した。
【００１２】
RSA暗号法に剰余演算系を用いる主な理由は、同暗号法が十進数２００桁程度以上の非常に大きな整数の剰余乗算演算の繰り返しにより構成され、これまで述べたような剰余演算系の乗算と加減算が高速に行える特性を利用して高速処理を実現することが可能であるためである。
【００１３】
上記Poschら、Kornerupら、およびPaillierのそれぞれの方式において共通するのは、剰余演算系において不利な除算を行うことを避けるために、Montgomeryの演算方式を剰余演算系に組合せている点である。また、処理の途中において、ある基底で剰余系表現された整数を別な基底で表現した値を求めるための基底変換(base conversion)あるいは基底拡張(base extension)が行われている点も３方式に共通している。さらに、いずれの方式とも基底変換または基底拡張を効率良く行うことができるか否かが処理全体の効率にかかわっている。
【００１４】
ここで、基底変換と基底拡張という２種類の用語を用いているが、基底変換とは、ある基底で表現された値をその基底と互いに素な別の基底で表現しなおすことをいう。また、基底拡張とは、サイズｎの基底で表現された値を、元の基底にそれと互いに素な１つの整数を加えた、サイズｎ＋１の基底で表した場合のｎ＋１番目の要素を求めることを指す。基底拡張の方式があれば、それをｎ回実行することにより基底変換を構成できることは明らかである。剰余演算系を用いたRSA暗号法の実現においては、基底変換（または基底拡張）を効率良く行うための方式および装置が必要となる。
【００１５】
しかしながら、上記３つの方式、並びにこれまで提案されている方式は、以下で説明するように、何らかの点で効率が悪い基底変換方式であるといえる。
【００１６】
まず、Poschらの提案した方式において、RSA暗号の演算において示された基底変換の方式は、変換前の値がある値よりも小さい場合には変換後の値に誤差を生じる可能性がある。そこでPoschらは基底変換処理の入力に適当なオフセットを加えることで該入力を基底変換処理において誤差が生じないような値に変換し、その変換結果を基底変換し、得られた基底変換結果からオフセットによる影響を取り除くという手順を提案している。しかし、このようなオフセットのための前処理および後処理は全体の演算量を増加させるので効率が悪い。
【００１７】
またPoschらの方式は与えられた基底で計算可能なRSA暗号の鍵のサイズが著しく限定される上、基底変換に必要な補正項を計算するために乗算器を必要とするので、回路化した際の面積および処理遅延の点でも不利である。
【００１８】
図５は、Poschらの方式によるRSA暗号演算に用いられる剰余演算回路の概略構成を示す図である。
【００１９】
剰余演算機能付き積和回路５０１、RAM５２１、ROM５３１は１つのユニットを構成し、同様の構成のユニットがｎ個並列に並ぶ構成になっている。ここでは基底のサイズをｎとしており、各ユニットは特定の基底に対応した演算を行う。例えば、各ユニットは基底Aのｎ個の各基底要素および基底Bのｎ個の各基底要素にそれぞれ対応しており、例えば積和回路５０１では基底a1，b1に対応した演算が行われる。また、これらｎ個のユニットはそれぞれｒビットの演算を行うよう構成されており、さらにｒビットのバスによって相互に接続されている。
【００２０】
図６に積和回路５０１〜５０ｎの内部構成を示す。ここでは、便宜上、積和回路５０１で示すユニットに関するものとして説明する。入力としては記号a，ｂで表すｒビットのデータと、図中で右側から入力されているｒビットのROM５３１からのデータ入力がある。図中で、aはRAM５２１からの入力、ｂはROM５３１からの入力を表す。a，bはまず乗算器６０１で掛け合わされ、結果は次段の加算器６０２に供給される。加算器６０２では、乗算結果とレジスタ６０４からのフィードバック値が入力され足し合わされる。加算器６０２の結果は剰余演算部６０３に供給され、レジスタ６０５にセットされた値により割った余りに変換される。ここではレジスタ６０５の値を記号ｍｉと書いているが、これは基底a１またはb１を表すものとする。入力a，bには基底サイズと同じｎ組みのデータが供給されるが、ｎ個のデータをすべて計算した後には計算結果がレジスタ６０４に出来上がっており、これはｒビットのバスによってRAM５２１に供給される。
【００２１】
図５の説明に戻って、剰余演算回路には、基底変換において計算結果を補正するための補正項計算ユニット５１０及びこの補正項計算ユニット５１０に外付けされ、該補正項計算ユニット５１０に少なくともｎワードのパラメータを供給するROM５３０が含まれる。
【００２２】
Poschらの提案した補正項計算ユニット５１０は、図７のような積和回路によって実現される。図７に示す回路では、まず入力されたｒビットのデータとＲＯＭ５３０から入力されたデータが乗算器７０１で掛け合わされたのち、加算器７０２によって累積加算される構成となっている。加算結果はレジスタ７０３に記憶され、補正項を完全に計算し終わってから値がフィードバックされる。
【００２３】
ここで注意すべき点は、補正項計算ユニット５１０の回路規模は、図６に示した剰余演算機能付き積和回路の回路規模と同程度以上の大きなものであるという点である。また、ここで計算される補正項は（ｒ＋log2ｎ）ビット程度の大きさであり、図において、積和回路５０１〜５０ｎに向けて補正項を伝えるための伝送バス幅はｒビットではなく、（r+log2ｎ）ビット必要であり、これは回路面積を増大させる要因になる。もっとも、この内ｒビットはＲＡＭから補正項演算ユニットへのバスと共用することが可能であるが、その場合でもlog2ｎビット分はフィードバックのために余計な面積を必要とすることになる。
【００２４】
また、積和回路５０１から５０ｎは、補正項計算ユニット５１０から受け取った補正項をそれまでの計算結果に反映させるために少なくとも剰余乗算を１回行う必要がある。仮に、補正項を他の処理を行っている間に、逐次積和回路にフィードバックすることができれば処理時間の節約になると思われるが、Poschらの構成では補正項を完全に計算し終わってからでなければ値をフィードバックすることはできない。これら具体的な問題点を解決する手段はこれまで考案されていなかった。
【００２５】
他の従来技術であるKornerupらの方式では、前記補正項を計算するために、ShenoyとKumaresanがIEEE Transaction on Computers, Vol.38, No.2, February 1989, pp.292-297の”Fast Base Extension Using a Redundant Modulus in RNS”で提案した方式を用いている。この場合、補正項のサイズはｎ程度でありPoschらの方式に比べ格段に小さいが、この方式の場合にもやはり補正項の計算に乗算を必要とし回路規模、処理遅延の点でより効率の良い補正項演算手順が求められていた。
【００２６】
また、他の従来技術であるPaillierの提案した方式では、任意の基底を選べる訳ではなく、基底に対して基数表現への変換や基数表現から剰余演算系表現への変換が非常に効率良く行えるという条件が課されているために適用範囲が限られている。論文中で具体的に示されている適用可能な例は、基底サイズｎが２の基底二組を用いる場合のみが示されており、それ以外の実用的な例は知られていない。ｎが２程度と小さい場合、基底の各要素は逆に大きく、ｎを大きく取れて基底の各要素を小さく設定できる場合にくらべ処理速度を上げることが困難である。
【００２７】
以上述べたように、RSA暗号の高速処理をねらって剰余演算系を利用することを提案した３種類の方式が知られており、これまでに提案されているRSA暗号の演算方式に比べて処理効率を上げる効果はあるものの、いずれの方式においても処理ステップの中で最も重要な部分である基底変換処理の効率が悪かったり、基底サイズが限られた方式しかなかった。
【００２８】
【発明が解決しようとする課題】
以上の点に鑑み本発明は、従来提案されている基底変換方式に比べ、以下のような点のすべてもしくは一部において優れている新しい基底変換方式を提供することを目的とする。
【００２９】
(a)補正項の値が比較的小さくかつ逐次処理できる。
【００３０】
(b)変換後の値が変換前に表現されていた値と一致し、誤差が生じない。
【００３１】
(c)仮に誤差が生じる場合でも、前後の処理や入力サイズの制限により誤差を容易に制御できる。
【００３２】
(d)RSA暗号への適用においては鍵のサイズへの制限が少ない。
【００３３】
(e)補正項を計算するのに乗算が不要で処理効率が良い。
【００３４】
(f)基底の取り方に制約が少なく汎用性が高い。
【００３５】
そして、このような基底変換方式を、Montgomeryのアルゴリズムと組み合わせることにより、RSA暗号の処理等に用いられる高速な剰余演算装置及び方法を実現することを目的とする。
【００３６】
【課題を解決するための手段】
上記課題を解決し目的を達成するために本発明は次のように構成されている。
【００３７】
（１）本発明の剰余演算装置は剰余演算機能を有する複数の積和回路と、この積和回路における剰余演算に用いられる補正項を計算する補正項計算ユニットとを備えた剰余演算装置において、前記補正項計算ユニットは、前記補正項を１ビットずつ逐次計算し、前記積和回路は、前記補正項計算ユニットにより計算された前記補正項を逐次反映させて基底変換もしくは基底拡張を行うことを特徴とする剰余演算装置である。
【００３８】
（２）本発明の剰余演算装置は上記（１）に記載の装置であって、かつ前記積和回路は、モンゴメリ(Montgomery)乗算を行うことを特徴とする剰余演算装置である。
【００３９】
（３）本発明の剰余演算装置は複数並列に配置された積和回路と、この積和回路における剰余演算に用いられる補正項を計算する補正項計算ユニットとを備えた剰余演算処理装置において、前記補正項計算ユニットは、前記補正項を１ビットずつ逐次計算し、前記積和回路は、前記補正項計算ユニットにより計算された前記補正項を逐次反映させて剰余演算系表現を基数表現に変換する演算を行うことを特徴とする剰余演算装置である。
【００４０】
（４）本発明の剰余演算装置方法は上記（１）乃至（３）のいずれかに記載の装置であって、かつ前記補正項計算ユニットは、除算回路を有し、前記積和回路で扱われる剰余演算系の基底を２の冪、もしくは２の冪に近接するものとすることを特徴とする剰余演算装置である。
【００４１】
（５）本発明の剰余演算装置は上記（１）乃至（４）のいずれかに記載の装置であって、かつ前記補正項計算ユニットへの入力ビットを選択するビット選択部を更に備えたことを特徴とする剰余演算装置である。
【００４２】
（６）本発明の剰余演算装置は上記（１）乃至（５）のいずれかに記載の装置であって、かつ外部とのデータの入出力を行うＩ／Ｏ部を更に備えたことを特徴とする剰余演算装置である。
【００４３】
（７）本発明の剰余演算装置は剰余演算系における所定の演算アルゴリズムにおいてある基底を他の基底に基底変換又は基底拡張する剰余演算装置において、前記基底変換又は基底拡張の未知パラメータｋを、該未知パラメータｋの前回計算結果の累積加算により生じた桁上がりに近似して出力するｋ出力手段と、前記ｋ出力手段から出力された未知パラメータｋに応じて前記基底変換又は基底拡張における特定項の計算可否を切り替える切替手段と、前記特定項の計算を含む乗算、加算及び剰余算の組み合わせにより基底要素毎に前記基底変換又は基底拡張の計算を行う複数の演算ユニットと、を具備することを特徴とする剰余演算装置である。
【００４４】
（８）本発明の剰余演算装置は上記（７）に記載の装置であって、かつ前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似することを特徴とする剰余演算装置である。
【００４５】
（９）本発明の剰余演算装置は上記（７）に記載の装置であって、かつビット選択手段をさらに具備し、前記ｋ出力手段は中国剰余定理に基づく前記未知パラメータｋの計算式の分子を、前記ビット選択手段による有効ビット長以外の切り捨てに基づいて近似することを特徴とする剰余演算装置である。
【００４６】
（１０）本発明の剰余演算装置方法は上記（７）に記載の装置であって、かつ前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似するとともに、該計算式の分子を、有効ビット長以外の切り捨てに基づいて近似することを特徴とする剰余演算装置である。
【００４７】
（１１）本発明の剰余演算装置は上記（７）に記載の装置であって、かつ前記所定の演算アルゴリズムは、入力された整数ｘ，ｙ，Ｎに対して、ｘｙＢ−１ modＮまたはｘｙＢ−１ mod Ｎ＋Ｎを出力するモンゴメリ乗算アルゴリズムから構成されることを特徴とする剰余演算装置である。
【００４８】
（１２）本発明の剰余演算装置は上記（１１）に記載の装置であって、かつ前記モンゴメリ乗算を用いた所定のアルゴリズムに従ってべき乗剰余算を行う手段を具備することを特徴とする剰余演算装置である。
【００４９】
（１３）本発明の剰余演算装置は上記（７）に記載の装置であって、かつ中国剰余定理に基づく未知パラメータを含む所定の計算式に従って、剰余演算系表現を基数表現に変換して出力する変換手段を具備することを特徴とする剰余演算装置である。
【００５０】
（１４）本発明の剰余演算装置は剰余演算系における所定の演算アルゴリズムにおいてある基底を他の基底に基底変換又は基底拡張する剰余演算装置において、特定項の計算を含む乗算、加算及び剰余算の組み合わせにより基底要素毎に前記基底変換又は基底拡張の計算を行うための複数の演算ユニットと、前記複数の演算ユニットのそれぞれに設けられ、前記基底変換又は基底拡張の未知パラメータｋを、該未知パラメータｋの前回計算結果の累積加算により生じた桁上がりに近似して出力するｋ出力手段と、前記ｋ出力手段に対応する前記演算ユニットの前記特定項の計算可否を、該ｋ出力手段から出力された未知パラメータｋに応じて切り替える切替手段と、当該演算ユニットのオペランドを隣接する演算ユニットに送信し、及び隣接する他の演算ユニットからのオペランドを受信する演算ユニット間の接続手段と、を具備する剰余演算装置である。
【００５１】
（１５）本発明の剰余演算装置方法は上記（１４）に記載の装置であって、かつ前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似することを特徴とする剰余演算装置である。
【００５２】
（１６）本発明の剰余演算装置方法は上記（１４）に記載の装置であって、かつ前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分子を、有効ビット長以外の切り捨てに基づいて近似することを特徴とする剰余演算装置である。
【００５３】
（１７）本発明の剰余演算装置は上記（１４）に記載の装置方法であって、かつ前記ｋ出力手段は、中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似するとともに、該計算式の分子を、有効ビット長以外の切り捨てに基づいて近似することを特徴とする剰余演算装置である。
【００５４】
（１８）本発明の剰余演算装置方法は上記（１４）に記載の装置であって、かつ前記所定の演算アルゴリズムは、入力された整数ｘ，ｙ，Ｎに対して、ｘｙＢ−１ mod ＮまたはｘｙＢ−１ mod Ｎ＋Ｎを出力するモンゴメリ乗算アルゴリズムから構成されることを特徴とする剰余演算装置である。
【００５５】
（１９）本発明の剰余演算装置は上記（１８）に記載の装置であって、かつ前記モンゴメリ乗算を用いた所定のアルゴリズムに従ってべき乗剰余算を行う手段を具備することを特徴とする剰余演算装置である。
【００５６】
（２０）本発明の剰余演算装置は上記（１４）に記載の装置であって、かつ中国剰余定理に基づく未知パラメータを含む所定の計算式に従って、剰余演算系表現を基数表現に変換して出力する変換手段を具備することを特徴とする剰余演算装置である。
【００５７】
（２１）本発明の剰余演算方法は剰余演算系における所定の演算アルゴリズムにおいてある基底を他の基底に基底変換又は基底拡張する剰余演算方法において、前記基底変換又は基底拡張の未知パラメータｋを、前回計算結果の累積加算により生じた桁上がりに近似し、前記出力された未知パラメータｋに応じて前記基底変換又は基底拡張における特定項の計算可否を切り替え、前記特定項の計算を含む乗算、加算及び剰余算の組み合わせにより基底要素毎に前記基底変換又は基底拡張の計算を行うことを特徴とする剰余演算方法である。
【００５８】
（２２）本発明の剰余演算方法は上記（２１）に記載の方法であって、かつ中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似することを特徴とする剰余演算方法である。
【００５９】
（２３）本発明の剰余演算方法は上記（２１）に記載の方法であって、かつ中国剰余定理に基づく前記未知パラメータｋの計算式の分子を、有効ビット長以外の切り捨てに基づいて近似することを特徴とする剰余演算方法である。
【００６０】
（２４）本発明の剰余演算装置方法は上記（２１）に記載の方法であって、かつ中国剰余定理に基づく前記未知パラメータｋの計算式の分母を２の冪により近似するとともに、該計算式の分子を、有効ビット長以外の切り捨てに基づいて近似することを特徴とする剰余演算方法である。
【００６１】
（２５）本発明の剰余演算方法は上記（２１）に記載の方法であって、かつ前記所定の演算アルゴリズムは、入力された整数ｘ，ｙ，Ｎに対して、ｘｙＢ−１ mod ＮまたはｘｙＢ−１ mod Ｎ＋Ｎを出力するモンゴメリ乗算アルゴリズムから構成されることを特徴とする剰余演算方法である。
【００６２】
【発明の実施の形態】
以下、本発明の実施形態について、図面を参照しつつ詳細に説明する。
【００６３】
（第１実施形態）
まず、本発明の最も適した例であるRSA暗号法の演算について述べる。
【００６４】
RSA暗号の暗号化および復号は次の式で表されるべき剰余演算によって実現される。
【００６５】
Ｃ＝ｍe  mod  Ｎ      （１）
ここで、m，Nは十進数で数百桁の大きさで処理量が非常に大きいため、これを効率良く計算するために様々な方式が考案されてきた。
RSA暗号の演算を実装する良く知られた方法としてMontgomeryによって提案された剰余付き乗算（以後これをモンゴメリ(Montgomery)乗算と呼ぶ）を繰り返し用いる方法がある。従来の技術でも紹介したように、本発明の具体的適用対象の一つとしてモンゴメリ乗算を剰余演算系で行う場合を取り上げる。ここでは、まず剰余演算系ではない通常のモンゴメリ乗算の処理手続きについて説明する。
【００６６】
モンゴメリ乗算は、入力された整数ｘ，ｙ，Ｎに対して、ｘｙＢ−１ mod ＮまたはｘｙＢ−１ mod Ｎ＋Ｎを出力するアルゴリズムであり、次の５ステップからなる。
【００６７】
（１）ｓ  ←  ｘ・ｙ
（２）ｔ  ←  ｛ｓ・（−Ｎ）−１｝mod Ｂ
（３）ｕ  ←  ｔ・Ｎ
（４）ｖ  ←  ｓ＋ｕ
（５）ｗ  ←  ｖ／Ｂ
ここで、ｓ，ｔ，ｕ，ｖ，ｗは中間変数を表し、ＢはＮより大きく、Ｎと互いに素な任意の整数である。
【００６８】
これを剰余演算系で実現するアイディアはPoschらが初めて提案しており、次のような７ステップで書ける。
【００６９】
（１）ｓA  ←  ｘA・ｙA，    ｓB  ←  ｘB・ｙB
（２）ｔB  ←  ｛ｓB・（−ＮB）−１｝mod Ｂ
（３）ｔB  から基底変換によりｔAを求める。
（４）ｕA  ←  ｔA・ＮA
（５）ｖA  ←  ｓA＋ｕA
（６）ｗA  ←  ｖA ＢA−１
（７）ｗAから基底変換によりｗBを求める。
ここで、添え字AあるいはBをつけた記号はそれぞれ剰余演算系の基底A＝｛a1, a2,…, an｝あるいは基底B=｛b1, b2,…, bn｝によって表現された数を表す。例えば、ｘAは基底要素の積Ａ= a1a2…an を法とする剰余環の要素ｘを基底Aの各要素で割った余りｎ個の組｛x1, x2,…, xn｝を表す。上記の処理により正しく計算ができるためには少なくともＮ＜Ａ，Ｎ＜Ｂが必要条件である。この条件からｘやｙは基底Aのみ、あるいは基底Bのみで一意に表現できるので、ｘA，ｘBのペアでｘを表すこと自体は冗長である。しかし、ｘとｙの積ｓがとる値の範囲は０≦ｓ＜Ｎ2であり、A*Bを基底としてはじめて正しく表現される。このことからｘとｙもA*Bを基底として表現することによりｓが剰余演算系の積として正しく計算できることがわかる。なお、基底Aと基底Bのサイズｎとｍは一般には異なるが、特殊な場合としてｎ=ｍとした場合には基底Aを処理する演算ユニットと基底Bを処理する演算ユニットを共用できるという利点がある。
【００７０】
剰余演算系におけるモンゴメリ乗算の処理においてステップ（３）と（７）を除けば、通常のモンゴメリ演算における５つのステップとの対応関係は明らかであろう。ステップ（１）〜（２）、（４）〜（６）は剰余演算系の乗算または加算によって容易に実現できる。例えば、ステップ（１）のｓAの計算では基底Aの剰余演算系で表されたｘの各要素とｙの各要素を対応する基底要素を法として乗ずることによって計算できる。これに対してステップ（３）、（７）の基底変換についてこれまで幾つかの研究がなされてきた。基底変換をいかに効率良く行うかが上記処理アルゴリズムを効率良く実装するためのポイントとなる。
【００７１】
与えられたｘをまさしく基底要素の積Ａ（= a1a2…an）以下の正の値として表現する手法をまず考察する。いまｘを０≦ｘ＜Ａなる整数とし、その剰余演算系表現を｛x1, x2,…, xn｝とする。この時よく知られた中国剰余定理から次式が成り立つ。
【００７２】
【数１】
0003742293.tif 000002
【００７３】
ここで、Ai はＡ/ ai，Ai-1は法ai におけるAi の乗法逆元である。このとき、
【数２】
0003742293.tif 000003
【００７４】
なるｋが唯一存在する。ここで、未知なパラメータはkのみであり、kを既知のパラメータで表現することを考える。kは第一項で計算された値を０以上Ａ未満の整数にするためのパラメータであり、以後、kを補正項と呼ぶことにする。
【００７５】
式（３）の両辺をＡで割ると、
【数３】
0003742293.tif 000004
従って、
【数４】
0003742293.tif 000005
ここで、０≦x/Ａ＜１を考慮すると、
【数５】
0003742293.tif 000006
が言える。小数部を切り捨てる操作を記号［ ］で表すと、式（６）から次の関係式が導ける。
【００７６】
【数６】
0003742293.tif 000007
【００７７】
これはPoschらの表現に似ているが彼等の方式による補正項ｋ’は次のように書ける。
【００７８】
【数７】
0003742293.tif 000008
【００７９】
このPoschらの式（８）と比べると、本発明に係る式（７）は、ｘi の項が（ ）内に組み込まれ、ai を法としてAi-1と掛け合わされている点が異なる。以後この積を次のように記号ξiで表す。
【００８０】
ξi＝xi *Ai -1mod ai                                （９）
式（７）に基づく補正項kの取りうる値は０以上ｎ未満の値となるのに対し、Poschらの式（８）に基づく補正項k’は最大でΣi=1 n ai 程度の大きさとなる。このPoschらの補正項k’は、
【数８】
0003742293.tif 000009
を満たし、多くの場合ｎを大きく超える値となる。なお、Min，Maxはそれぞれ最小値、最大値をとる関数とする。
【００８１】
式（７）に従って計算される補正項kは、Poschらの方式に比べて値が小さいものが得られる。このように、本発明による補正項kの計算法は式（７）の関係式を出発点として構成される。
【００８２】
ここで、本発明によるモンゴメリ乗算を実現する剰余演算回路の構成を図面を参照しながら説明する。
図１は、モンゴメリ乗算を実現する剰余演算装置の主要部分を図示したものである。剰余演算機能付き積和回路１０１、RAM１２１、ROM１３１は１つのユニットを構成し、同様の構成のユニットがｎ個並列に並ぶ構成になっている。各ユニットは基底Aのｎ個の各基底要素および基底Bのｎ個の各基底要素にそれぞれ対応しており、例えば積和回路１０１では基底a1，b1に対応した演算が行われる。これらｎ個のユニットはそれぞれｒビットの演算を行うよう構成されており、さらにｒビットのバスによって相互に接続されている。これらｎ個のユニット以外の構成要素としてビット選択部１１１と補正計算ユニット１１０とが図示されている。補正項計算ユニット１１０は、上記した式（７）またはその変形式に従って補正項kに相当する値を計算するために必要なユニットである。ビット選択部１１１はｒビットのバスから必要な数の上位ビット（ｑ）を切り出すユニットであるが、実装によってはｒビットをそのまま補正項計算ユニット１１０に供給する場合もある。
【００８３】
図２は、図１に示された積和回路１０１〜１０ｎのうちの一つの積和回路の構成を示している。ここでは、便宜上、積和回路１０１で示すユニットに関するものとして説明する。入力としては、記号ａ，ｂで表すｒビットのデータと、図中で右側から入力されているｒビットのROM１３１からのデータと、１ビットの補正項演算ユニットからの出力とがある。図中でａはRAM１２１からの入力、ｂはROM１３１からの入力を表す。ａ，ｂはまず乗算器２０１で掛け合わされ、結果は次段の加算器２０２に供給される。加算器２０２は乗算結果の他にレジスタ２０４からのフィードバック値と、レジスタ２０５からのデータとが入力され、足し合わされる。ただし、レジスタ２０５からのデータは、スイッチ２０７が閉じているときはそのまま加算器２０２に供給されるが、スイッチ２０７が開いている時は０に置き換えられる。スイッチ２０７の開閉は補正項計算ユニット１１０からの１ビットのデータで制御される。データが１の場合は閉、データが０の場合は開に制御される。加算器２０２の結果は剰余演算部２０３に供給され、レジスタ２０６にセットされた値により割った余りに変換される。ここでは、レジスタ２０６の値を記号ｍｉと書いているが、これは基底a1またはb1を表すものとする。入力ａ，ｂには基底サイズと同じｎ組みのデータが供給されるが、ｎ個のデータをすべて計算した後には計算結果はレジスタ２０４に出来上がっており、これはｒビットのバスによってRAM１２１に供給される。
【００８４】
図３は、補正項計算ユニット１１０の一構成例を示している。この補正項計算ユニット１１０は、入力されたｑビットのデータを加算器３０１によって累積加算する構成を有する。加算結果のｑ＋１ビットはレジスタ３０２に記憶され、レジスタ３０２の最上位ビットが補正項の逐次計算結果として出力される。最上位ビット以外のｑビットは次の処理ステップで再び加算器３０１に供給される。入力として基底サイズと等しいｎ個の値が供給されるので、補正項演算ユニット１１０は、ｎ回にわたって計算結果を出力することになる。
【００８５】
図４は、ビット選択部１１１の構成を示す図である。ここでは入力されたｒビットの内、上位ｑビット（ｑ≦ｒ）が出力される。なお、ｑ＝ｒとする構成の場合は、ビット選択部を設けなくてもよい。
【００８６】
図８は、補正項計算ユニット１１０の他の構成例を示す。この構成例は、入力値をまず除算回路８０１によって除算する点を特徴とする。このような除算回路８０１は一見、図７の構成に比べて不利に見えるかもしれないが、除数が２の冪または２の冪に非常に近ければ、効率良く除算を行う手段が知られており、除算回路８０１での処理は必ずしも大きくない。
【００８７】
ここで、本発明に係る剰余演算装置の第１の実施形態の特徴点として、式（７）に従って補正項を計算するための手順について説明する。なお、本実施形態は図１においてｑ＝ｒとした回路構成を前提とする。また、本実施形態では、図８に示した補正項計算ユニットの構成を用いることとする。この図８の構成では補正項を求める際に除算が行われるが、基底要素の積Ａ未満の任意のｘに対して正しい補正項kを計算できるという長所がある。また、一般には除算の精度と手間が問題になるが、２r、２r−１、２r＋１のような特殊な値を基底とする場合には、この手法により容易に補正項を計算できる。
【００８８】
ここで、基底Aで表現されたｘを基底Bの表現に変換するまでの流れを説明する。
【００８９】
【数９】
0003742293.tif 000010
【００９０】
上式（１１）に基づく演算を実際にハードウェア化するためには、次式のような漸化式で表現される手続きが利用される。
【００９１】
σi = (σi-1 − ki-1 ) +ξi / ai               （１２）
ki = [σi ]                                （１３）
ci = {ci-1 +ξi* (Ai mod bj)+ ki*（bj − Amod bj ）} mod bj（１４）
上式（１２）〜（１４）に基づく手続きを、変換先となるすべての基底要素ｂｊ（j=１,...,m）について、i＝１からｎまで順に繰り返す。
各変数の初期値σ０＝k０＝c０=０とすると、cnが基底変換された結果となる。このように漸化式で表現すると、補正項kは１ビットずつ計算され、上式（１４）に示されるように、その都度、基底変換の途中結果に反映されることがわかる。
【００９２】
式（１２）に基づいて補正項kを逐次計算するためのハードウェア構成が、既に示した図８の補正項計算ユニット１１０である。上式（１１）におけるξiは、図８に示される入力xに対応し、上式（１１）におけるaiは入力yに対応する。
【００９３】
加算器８０２は、除算回路８０１から出力された除算結果(x/y)と、レジスタ８０３に保持されている前回の値とを加算し、その結果をレジスタ８０３に出力する。同図に示されるように、レジスタ８０３においてキャリーが生じた際、そのキャリービット（１ビット）が補正項k（reduction factor）として補正項計算ユニット１１０から出力される。この補正項kは、１または０の値をとる。
【００９４】
補正項計算ユニット１１０から出力されたkに基づき、式（１４）に従って基底変換後の値を並列に計算するためのハードウェア構成が、既に示した図２の積和回路１０１〜１０ｎである。積和回路の一つ、例えば積和回路１０１は、次のような基本演算をサポートするよう構成される。
ci+1 = ( ci + ab + kid ) mod mi              （１５）
上式（１５）において、右辺に含まれるkiは１または０であるため、右辺第三項の計算はスイッチ２０７のみにより実現される。これは、図１に示した補正項演算ユニット１１０から積和回路１０１〜１０ｎへのフィードバックは１ビットの結線のみで足りることを意味している。このような本実施形態の回路構成は、図５に示したPoschらの回路に比べて極めて簡素な構成になっている。フィードバックが１ビットで済むという構成上の利点は、後述する他の実施形態でも同様である。
【００９５】
なお、以上の手続きでは補正項を計算する際、最初にxiをAi-1と掛けてξiを求める必要があるが、剰余演算系のモンゴメリ乗算にこの基底変換を用いる場合には、ステップ（２）で定数（‐NB-1）の各要素にあらかじめAi-1を掛けておくことで、ξiを求める手間が新たに加わることが無くなる。また、ステップ（７）の変換に必要な前処理は、ステップ（６）の定数BA-1に組み込んでおくことができる。この点は、後述する他の実施形態についても同様である。
【００９６】
また、以上の手続きは基底変換のみならず基底拡張にも適用可能であることは明らかである。すなわち、ｍ個すべての基底{bj}について変換を行うのではなく、特定の基底についてのみ変換を行えば、基底拡張を行ったこととになる。
【００９７】
以上説明した第１実施形態の剰余演算装置に適用された、本発明に係る新たな基底変換（拡張）によれば、次のような作用効果を得ることができる。
(a)補正項の値を比較的小さくし、かつこれを１ビット単位で逐次処理できる。
(b)基底変換後の値が変換前に表現されていた値と同じであるから、Poschらの方式のような誤差が生じない。
(c)仮に誤差が生じるとしても、前後の処理や入力サイズの制限により誤差を容易に制御できる。
(d)RSA暗号への適用においては鍵のサイズへの制限が少ない。
(e)補正項の計算に乗算が不要であり処理効率が良い。
(f)基底の取り方に制約が少なく汎用性が高い。
したがって、本実施形態のような基底変換（拡張）によれば、簡素な構成でモンゴメリ乗算を高速化でき、ひいてはRSA暗号法の処理の高速化を実現できる。
【００９８】
また、本実施形態の剰余演算装置は、剰余演算系表現を基数表現に変換する手続にも適用可能である。この手続きの詳細は第２実施形態において説明する。
（第２実施形態）
第２の実施形態は、式（１１）による補正項kの計算式において、右辺の各項の分母を、分母以上で最も分母に近い２の冪に選ぶことで近似を行うものである。
【００９９】
すなわち、
2ri-1 ＜ ai ≦ 2ri                  （１６）
を満たすｒiによって、ai を2riで近似する。なお、一般にriは基底の要素毎で異なるが、実装上はすべての基底要素を同一のビット長にすると、図１の積和演算回路１０１〜１０ｎが共通化できるといった利点が得られる。
適当なμiに対してaiは次式のように表される。
【０１００】
ai ＝ 2ri‐μi                    （１７）
この時、式（１１）で計算される補正項kの近似値lとして
【数１０】
0003742293.tif 000011
を用いる。lもk同様に漸化式で逐次計算すると。
【０１０１】
σi = (σi-1 − li-1 ) +ξi / 2ri                  （１９）
li = [σi]                                    （２０）
ここで、lおよびσの初期値はともに０とする。補正項の計算はこの式（１９）および（２０）にしたがって行うことができる。本実施形態についても第１の実施形態と同様に、図１においてｑ=ｒとした回路構成を前提としている。また、本実施形態以降では図３に示す補正項計算ユニットの構成を用いることとする。
【０１０２】
式（１９）および（２０）に従った補正項計算は、第１実施形態と同様に基底変換および基底拡張に利用できる。しかしながら本実施形態では、これを剰余演算系表現を基数表現に変換する手続きに応用する。次式（２１）は、剰余演算系表現を基数表現に変換する手続きを示している。
【０１０３】
c i = ci-1 +ξi* Ai ‐ li *Ａ                    （２１）
ここで注意すべきは、式（２１）は式（１４）と似ているが、式（１４）では変数ciは最大の基底を表現できる精度さえあれば良かったのに対して、式（２１）の変数ciは基底要素の積Ａ程度の大きさを有する多倍長変数を格納できることを前提としている点である。実際にハードウェアを設計する場合には式（２１）の計算をそのまま実現するのではなく、単精度の演算の繰り返しに分割するなどの工夫が必要であるが、剰余演算系表現から基数法表現に変換する原理を説明するにはこれで十分であろう。また単精度演算への分解は容易である。
【０１０４】
式（１８）に従ってkを近似した場合、式（２１）の変換結果に誤差が生じることがある。ここでその誤差について若干の説明を加える。まず近似誤差の尺度として次式で表されるεを導入する。
ε= Max(μi／2ri )                          （２２）
このεを用いると、入力xが、
nεＡ  ≦ x ＜  Ａ                        （２３）
のとき、式（１７）は正しい補正項kと同じ値を与える。また、
0 ≦ x ＜ nεA                            （２４）
のとき、式（１７）は正しい値ｋまたはk-1を与える。
式（２３）によると、nε＜１を満たし、かつ、必要なだけ小さいεを選ぶことが求められる。一方、μi を十分小さく選ぶと、図２の剰余演算部２０３で行われるmod ai演算が容易になるということも知られている。
【０１０５】
以上説明した第２実施形態によれば、第１実施形態と同様に簡素な構成で高速に補正項lを計算する剰余演算装置により、剰余演算系表現を基数表現に変換する手続を実現できる。
なお、第２の実施形態では、式（１２）の分母を２の冪で近似したが、式（１２）において分母のみならず分子についても近似を行ってもよい。具体的には、次の第３実施形態で説明するように、分子の有効ビット長を許容誤差範囲内で短くしてもよい。
【０１０６】
（第３実施形態）
第３実施形態では、式（１２）の分子をの有効ビット長を許容誤差範囲内で短くすることで近似を行うものである。この近似は、図１においてｑ＜ｒとし、ｒビットの上位ｑビットを補正項計算ユニットで累積加算することに対応する。
【０１０７】
この場合の補正項をｍとおき、例えば次式（２５）によってｍを求める。
【０１０８】
【数１１】
0003742293.tif 000012
【０１０９】
ここで、trunc（ ）は与えられた変数の上位ｑビットはそのままとし、該上位ビットよりも下位のビットを０とする関数である。原理的には、各項毎に取り出すビット数ｑを変えても良いが、すべての項にｑを共通にした方が通常ハードウェア構成は簡単となる。
【０１１０】
ｍを逐次計算するための漸化式は以下の通りである。
σi = (σi-1 − ｍi-1 ) + trunc（ξi ）/ 2ri             （２６）
ｍi = [σi]                                        （２７）
ただし、σとｍの初期値は０とする。
本実施形態の場合、分母のみならず分子についても近似誤差が生じる。これら分母及び分子の近似誤差による影響について説明する。今、分子の近似誤差の尺度として次のようなδiを定義する。
δi = {ξi ‐ trunc(ξi )} / ai                      （２８）
さらに、
δ＝Max(δi )                                （２９）
を定義する。
【０１１１】
このδが導入されると、第２の実施形態の場合に似た以下のような条件が与えられる。
ここで、入力xが、
n(ε＋δ)Ａ  ≦ x ＜  Ａ                        （３０）
のとき、式（２５）は正しい補正項kと同じ値を与える。また、
0 ≦ x ＜ n（ε＋δ）Ａ                        （３１）
のとき、式（２５）は正しい値kまたはk-1を与える。
第３実施形態によれば、式（１２）の分母のみならず、分子についてもその有効ビット長を許容誤差範囲内で短くすることで近似を行っているので、補正項の計算をより簡素化、高速化できる。
なお、第２および３の実施形態によって与えられる補正項l, mは、入力xがある値以上の値の場合は正しい補正項を与え、xがある値よりも小さい場合は正しい補正項を与えないという性質を持っている。
しかし、場合によっては、xがある値以上の場合のみ補正項が誤差を含むことがあり、xがある値以下であれば、任意に小さい値まで正しい補正項が与えられる、という性質の方が好ましい場合がある。例えば、上記したモンゴメリ乗算のステップ（７）の基底Aから基底Bへの変換では、モジュラスNをある値以下しておくだけで常に正しく基底変換がなされるようにしたい場合である。
【０１１２】
（第４実施形態）
次に、第４の実施形態として、xがある値以下であれば、任意に小さい値まで正しい補正項が与えられるような補正項の計算方法を説明する。
【０１１３】
補正項の計算の基本原理は式（１１）に基づくが、分母は２の冪で近似し、分子は上位ｑビットのみ使うという近似を用いるものとする。この方式では、パラメータαとβを導入するが、αは次式のように入力xの大きさを制限するためのパラメータである。
０≦ x ＜ (１−α)Ａ                    （３２）
本実施形態における補正項m’は次式に従って計算する。
【０１１４】
【数１２】
0003742293.tif 000013
【０１１５】
本実施形態は、図１においてｑ＜ｒとしてｒビットの上位ｑビットを補正項演算ユニット１１０（図３）に入力し、内部レジスタ３０２の初期値をβとして累積加算するものである。式（３３）に対応する漸化式は次の通りである。
σ0 =β                                  （３４）
m’0＝０                                  （３５）
σi = (σi-1 − m’i-1 ) + trunc(ξi ) / 2ri        （３６）
m’i = [σi]                                （３７）
このとき、n (ε＋δ)≦β≦α＜１であれば０≦x≦（１−α）Ａなるxは正しく変換される。
【０１１６】
例えば、α=β=１／２とすると、Ａ／２以下の任意のｘに対して常に正しい補正項を計算することが可能である。β=１／２を図１の剰余演算装置で実現するには、図３に示したレジスタ３０２の上位から２番目のビットに１をセットすれば良い。このようにβを２の冪の逆数に選ぶと、レジスタの初期値の設定は、対応する一つのビットを１にセットするだけで良く簡単になる。なお、一般には誤差ｎ（ε＋δ）以上でα以下のβならば、任意の値をオフセットとして設定できる。
【０１１７】
第４実施形態によれば、上記のようにパラメータαとβが導入され、xがある値以下に制限される。そして、該制限されたxの任意の小さい値において正しい補正項が常に与えられるような補正項の計算を実現できる。
【０１１８】
（第５実施形態）
第５実施形態は、パラメータサイズに関する。RSA暗号の場合、１０２４ビット程度のモジュラスサイズを選ぶ必要があり、基底A，Bともに１０２４ビットを若干上回る程度の大きさが必要である。基底A，Bが各々３２ビット程度、すなわちｒ=３２とすると、基底サイズはｎ＝３３程度となる。これはｎ*ｒを１０２４程度とするためである。第４の実施形態においてα＝β=１／２とした場合、誤差の発生を抑えるためにはｎ（ε＋δ）≦１／２であることが必要である。したがって、ε＋δ≦１／２ｎ=１／６６であり、ε＜１／２８、ε＜１／２８はこれを満たす十分条件である。このようなパラメータサイズは、図３に示した加算器３０１の精度に概ね対応しており、補正項の演算には８ビット程度の加算器を用いれば良いことがわかる。
【０１１９】
（第６実施形態）
第６実施形態は、これまでに説明した本発明に係る基底変換（拡張）によるモンゴメリ乗算に基づいてべき乗剰余演算を行う装置に関する。
図９は、本実施形態に係るべき乗剰余演算装置の全体構成を表す図である。入力データおよび出力データは図示されたＩ／Ｏ部１０００を介してやり取りされる。入力データは、まずＩ／Ｏ部１０００を介して所定のＲＡＭ１２０１に格納される。外部からのデータが剰余演算系表現で入力された場合には、それぞれ対応するＲＡＭ１２０１〜１２０ｎに格納される。図中にはＲＡＭがｎ個示されているが、各ＲＡＭにはそれぞれ基底aｉとbｉに対応する要素が書きこまれる。  入力されたデータは、積和回路１１０１〜１１０ｎ及び補正項計算ユニット１１００により、これまでに述べたモンゴメリ乗算を繰り返すことによってべき乗剰余演算結果として与えられる。この演算結果は対応するＲＡＭ１２００〜１２０ｎに格納され、Ｉ／Ｏ部１０００を介して外部に出力される。
【０１２０】
モンゴメリ乗算を繰り返すことによってべき乗剰余演算を行うための手順について、図１０のフローチャートに従って説明する。同図に示されるフローチャートは、入力された剰余演算系表現の値ｘをｅ乗し、Ｎで割った余りを求める処理を表している。ただし、Ｎは既知と仮定し、Ｎの剰余演算系表現を求めるなどの処理については事前に計算してあるものとして図１０には示されていない。なお、Ｎを外部入力とし、Ｎの剰余演算系表現を求めるなどの処理をその都度行うように構成しても良い。
【０１２１】
図１０に示すＭＭは剰余系演算によるモンゴメリ乗算を意味する関数である。入力されたｘの剰余演算系表現は、まず定数ｄの剰余演算系表現された値(dA, dB)とモンゴメリ乗算によって掛け合わされてｘ'に変換される。ただし、ｄ＝Ｂ２ mod Ｎである。次に、変換された値ｘ'（の剰余演算系表現）は、中間結果ｃにコピーされる。
次のステップはループ処理であり、ループ変数ｉはｋ−１から１まで変化する。ここで、外部入力されたべき指数ｅは２進数表現されており、そのビット数はｋビットであって各ビットはｅｉと表現されている。eｋは最上位ビットであり、ここでは１とする。また、ｋは２以上の値とする。
ループ内では、まず中間変数ｃの２乗に相当する値がモンゴメリ乗算を用いて計算される。続いて、ループ変数ｉに対応するｅのビットeｉが１であるか否かを判定し、１でなければループの開始に戻り、１であるならば次のステップに進む。次のステップでは、ｃとｘの積をモンゴメリ乗算によって求める。続いて、ループ変数ｉが１であるか否かを判定し、１でなければループの開始点に戻り、１であるならばループ処理を抜ける。
最終的なステップでは、ここまでの計算結果ｃと、１を剰余演算系表現した値との積をモンゴメリ乗算によって求め、結果ｙ（の剰余演算系表現）を得る。
【０１２２】
以上によりｙ＝ｘｅ mod Ｎが計算される。
【０１２３】
（第７実施形態）
第７実施形態は、剰余演算装置をリング構成としたものに関する。
図１に示したｎ個の積和回路は、ｒビットのバスを介して接続されている。このバス接続によって、あるＲＡＭから出力されたデータを、ｎ個の全ての積和ユニットに伝送し、並列処理することが可能となる。バスによって積和回路を結ぶ構成は、並列処理の実現に有効な構成法の一つであるといえる。
一方、ネットワークアーキテクチャの分野で良く知られているように、複数ユニットを接続する方法としては、このようなバス接続のほかに、リング接続が考えられる。バス型のアーキテクチャはｎ個のユニットに同一のデータを放送（broadcast）するためのバスによって特徴づけられるのに対して、リング接続では隣り合ったユニット間を結ぶ通信路がｎ個のユニットを接続し、全体としてリング状のアーキテクチャとなる。
【０１２４】
本発明による剰余演算装置もリング接続によって実現することが可能である。直列的なリング接続の場合、各ユニットは隣ユニットにデータを送るだけで良いので、複数のユニットにデータを送信しなければならないバス型の構成に比べ、各ユニットのデータ駆動能力が小さくて済む。また全ユニットの動作を全く同じに制御することができる。これに対してバス型の場合には、あるユニットがデータを放送する際には、残りの（ｎ−１）個のユニットはそのデータを受信することになり、全ユニットが同一の動作をする訳ではない。全ユニットの動作が同じであるためにリング型の方が制御が容易である。
【０１２５】
図１１はリング構成の剰余演算装置の構成を示すブロック図である。図１１の構成では、バス接続がリング接続に変更されていると共に、図１に示したビット選択部１１１と補正項計算ユニット１１０が、ｎ個の積和回路のそれぞれに対して設けられるという変更が加えられている。図１に示した構成は、１つの補正項演算ユニットが設けられていただけであり、補正項計算ユニットで計算された補正項をｎ個の積和回路に放送するためには、１ビットのバスを設けるだけで済んだ。一方、本実施形態のようにｎ個の補正項計算ユニットを積和回路のそれぞれに設ける構成とした場合は回路規模が若干増加する。しかし、本発明に係る補正項計算ユニットは図３に示したように極めて簡素な構成であり、このような補正項計算ユニットをｎ個設ける構成としても、全体の回路規模に占める補正項計算ユニットの割合は極めて小さい。
【０１２６】
図１１のリング接続構成では、補正項計算ユニットが積和回路毎に設けられているので補正項を各積和回路に伝送するためのバスが不要になり、その代わりに接続ユニットが設けられる。この接続ユニットの詳細構成を図１２に示す。同図に示される接続ユニットは、２入力のセレクタ９６０とセレクタ９６０からの出力をラッチするｒビットのレジスタ９６１とにより構成されている。ある積和回路において、このレジスタ９６１は今回の演算サイクルで使用されるオペランドの一つを記憶する。次の演算サイクルにおいて、そのオペランドは隣接（図では例えば左隣）する接続ユニットに転送され、また、他の隣接（この場合、図では右隣）のユニットから次のオペランドが受信される。ｎ個の接続ユニットの各々のレジスタ９６１に格納されたｎ個のオペランドは、バケツリレー的に次々と隣接するユニットに転送され、ちょうどｎサイクルの時間で全ユニットにｎ個のオペランドが回覧されることになる。
【０１２７】
［ユニット数のスケーラビリティ］
ここまでは、積和回路の個数ｎ（あるいはユニット数ｎ）は基底サイズｎに等しいものとして説明してきた。しかし、演算ユニット数と基底サイズとが必ずしも一致している必要はないというのが一般的である。そこでユニット数を記号ｎからｍに改めて表すと、ｍ≦ｎの制約の下、ｍがより大きいほど高速処理が可能になる。一方、ＬＳＩ等によるハードウェア実装を考える場合、ｍがより大きいほど、回路規模及び消費電力は大きくなる。このように、ユニット数ｍと演算速度との間にトレードオフが生じる。ここで、ユニット数ｍの典型的な定め方として、ｎの約数を採用する方法が考えられる。たとえば、ｎ＝３３ならば、ｍ＝１，３，１１，あるいは３３がユニット数の候補になる。ｎの約数以外のｍを採用することも当然可能であるが、ｎの約数とすると回路の制御が規則的になり、かつ、演算ユニットの稼働率も高くなるという利点がある。いずれにしても、ｍをｎに限定しないことでＬＳＩ設計等の自由度が格段に広がることが容易に推測されよう。
【０１２８】
【発明の効果】
以上説明したように本発明によれば、新たな基底変換（拡張）が提供され、次のような作用効果を得ることができる。
(a)補正項の値を比較的小さくし、かつこれを１ビット単位で逐次処理できる。
(b)基底変換後の値が変換前に表現されていた値と同じであるから、Poschらの方式のような誤差が生じない。
(c)仮に誤差が生じるとしても、前後の処理や入力サイズの制限により誤差を容易に制御できる。
(d)RSA暗号への適用においては鍵のサイズへの制限が少ない。
(e)補正項の計算に乗算が不要であり処理効率が良い。
(f)基底の取り方に制約が少なく汎用性が高い。
したがって、簡素な構成でモンゴメリ乗算を高速化でき、ひいてはRSA暗号法の処理の高速化を実現できる。
【図面の簡単な説明】
【図１】本発明の実施形態に係る剰余演算装置の構成を示す図
【図２】図１に示された積和回路の構成を示す図
【図３】図１に示された補正項計算ユニットの構成を示す図
【図４】図１に示されたビット選択部の構成を示す図
【図５】従来技術に係る剰余演算装置の構成を示す図
【図６】従来技術に係り図５に示された積和回路の構成を示す図
【図７】従来技術に係り図５に示された補正項計算ユニットの構成を示す図
【図８】本発明の実施形態に係る補正項計算ユニットの他の構成を示す図
【図９】本発明の実施形態に係るべき乗剰余演算装置の構成を示す図
【図１０】本発明の実施形態に係るべき乗剰余演算の処理フローチャート
【図１１】本発明の実施形態に係る剰余演算装置の他の構成を示す図
【図１２】図１１に示した剰余演算装置の接続ユニットの構成を示す図
【符号の説明】
１０１〜１０ｎ…積和回路
１１０…補正項計算ユニット
１１１…ビット選択部
１２１〜１２ｎ…ＲＡＭ（ランダムアクセスメモリ）
１３１〜１３ｎ…ＲＯＭ（リードオンリーメモリ）
２０１…乗算器
２０２…加算器
２０３…剰余演算器
２０４〜２０６…レジスタ
２０７…スイッチ
３０１…加算器
３０２…レジスタ
５０１〜５０ｎ…積和回路
５１０…補正項演算ユニット
５２１〜５２ｎ…ランダムアクセスメモリ
５３０〜５３ｎ…リードオンリーメモリ
６０１…乗算器
６０２…加算器
６０３…剰余演算器
６０４、６０５…レジスタ
７０１…乗算器
７０２…加算器
７０３…レジスタ
８０１…除算回路
８０２…加算回路
８０３…レジスタ
【図１】
0003742293.tif 000014
【図２】
0003742293.tif 000015
【図３】
0003742293.tif 000016
【図４】
0003742293.tif 000017
【図５】
0003742293.tif 000018
【図６】
0003742293.tif 000019
【図７】
0003742293.tif 000020
【図８】
0003742293.tif 000021
【図９】
0003742293.tif 000022
【図１０】
0003742293.tif 000023
【図１１】
0003742293.tif 000024
【図１２】
0003742293.tif 000025