TOP > 国内特許検索 > 乗算剰余演算器及び情報処理装置 > 明細書

明細書 :乗算剰余演算器及び情報処理装置

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4170267号 (P4170267)
公開番号 特開2006-023647 (P2006-023647A)
登録日 平成20年8月15日(2008.8.15)
発行日 平成20年10月22日(2008.10.22)
公開日 平成18年1月26日(2006.1.26)
発明の名称または考案の名称 乗算剰余演算器及び情報処理装置
国際特許分類 G09C   1/00        (2006.01)
G06F   7/72        (2006.01)
FI G09C 1/00 650A
G06F 7/72
請求項の数または発明の数 17
全頁数 16
出願番号 特願2004-203435 (P2004-203435)
出願日 平成16年7月9日(2004.7.9)
審査請求日 平成17年8月16日(2005.8.16)
特許権者または実用新案権者 【識別番号】302062931
【氏名又は名称】NECエレクトロニクス株式会社
【識別番号】899000068
【氏名又は名称】学校法人早稲田大学
発明者または考案者 【氏名】東 邦彦
【氏名】久門 亨
【氏名】後藤 敏
【氏名】池永 剛
個別代理人の代理人 【識別番号】100123788、【弁理士】、【氏名又は名称】宮崎 昭夫
【識別番号】100106138、【弁理士】、【氏名又は名称】石橋 政幸
【識別番号】100127454、【弁理士】、【氏名又は名称】緒方 雅昭
審査官 【審査官】速水 雄太
参考文献・文献 特開2003-216034(JP,A)
特表2001-527673(JP,A)
特開2000-322239(JP,A)
鈴木大輔 他,FPGA上で効果的なモンゴメリ乗算回路の一構成法について,2003年暗号と情報セキュリティシンポジウム(SCIS2003),2003年
Alan Daly, William Marnane,Efficient architectures for implementing montgomery modular multiplication and RSA modular exponentiation on reconfigurable logic,Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays,2002年,pp. 40-49
調査した分野 G09C 1/00
G06F 7/72
特許請求の範囲 【請求項1】
被乗数をA、uとし、乗数をB、Nとし、乗算剰余演算結果をSとしたとき、S=S+A×B+u×Nを算出するための乗算剰余演算器であって、
複数のビット数q単位で供給される前記乗数Bの値に応じて前記被乗数Aまたは0の値を切換えて出力し、前記ビット数q単位で供給される前記乗数Nの値に応じて前記被乗数uまたは0の値を切換えて出力するセレクタと、
前記セレクタから順次出力される値を用いてA×B+u×Nの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数q単位で出力される前記A×B+u×Nの演算結果と、前記ビット数q単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Sとして出力する加算器と、
を有する乗算剰余演算器。
【請求項2】
前記被乗数Aを保持し、前記セレクタに供給する第1の記憶素子と、
前記被乗数uを保持し、前記セレクタに供給する第2の記憶素子と、
前記乗数Bを保持し、前記セレクタに前記ビット数q単位で供給する第3の記憶素子と、
前記乗数Nを保持し、前記セレクタに前記ビット数q単位で供給する第4の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Sを保持し、前記ビット数q単位で該乗算剰余演算結果Sを前記加算器に供給する第5の記憶素子と、
をさらに有する請求項1記載の乗算剰余演算器。
【請求項3】
前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項1または2記載の乗算剰余演算器。
【請求項4】
前記制御部は、
前記第1の記憶素子に前記被乗数Aをセットし、
前記第2の記憶素子に前記被乗数uをセットし、
前記第3の記憶素子に前記乗数Bをセットし、
前記第4の記憶素子に前記乗数Nをセットし、
前記セレクタに0を供給する請求項3記載の乗算剰余演算器。
【請求項5】
予め算出された、前記被乗数A、前記乗数B、前記乗数N、及び前記乗算剰余演算結果Sの値に対する前記被乗数uの値の関係が格納されるu生成部をさらに有し、
前記制御部は、
前記S=S+A×B+u×Nの演算時に前記u生成部を参照することで前記被乗数uの値を決定する請求項3または4記載の乗算剰余演算器。
【請求項6】
前記ビット数qは2である請求項1乃至5のいずれか1項記載の乗算剰余演算器。
【請求項7】
前記ビット数qは4である請求項1乃至5のいずれか1項記載の乗算剰余演算器。
【請求項8】
前記第1の記憶素子及び前記第2の記憶素子はラッチ回路である請求項2乃至7のいずれか1項記載の乗算剰余演算器。
【請求項9】
前記第3の記憶素子、前記第4の記憶素子及び前記第5の記憶素子はシフトレジスタである請求項2乃至8のいずれか1項記載の乗算剰余演算器。
【請求項10】
請求項1に記載の乗算剰余演算器と、
前記被乗数Aを保持し、前記セレクタに供給する第1の記憶素子と、
前記被乗数uを保持し、前記セレクタに供給する第2の記憶素子と、
前記乗数Bを保持し、前記セレクタに前記ビット数q単位で供給する第3の記憶素子と、
前記乗数Nを保持し、前記セレクタに前記ビット数q単位で供給する第4の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Sを保持し、前記ビット数q単位で該乗算剰余演算結果Sを前記加算器に供給する第5の記憶素子と、
を有する情報処理装置。
【請求項11】
前記桁上げ保存加算器の動作を制御する制御部をさらに有する請求項10記載の情報処理装置。
【請求項12】
前記制御部は、
前記第1の記憶素子に前記被乗数Aをセットし、
前記第2の記憶素子に前記被乗数uをセットし、
前記第3の記憶素子に前記乗数Bをセットし、
前記第4の記憶素子に前記乗数Nをセットし、
前記セレクタに0を供給する請求項11記載の情報処理装置。
【請求項13】
予め算出された、前記被乗数A、前記乗数B、前記乗数N、及び前記乗算剰余演算結果Sの値に対する前記被乗数uの値の関係が格納されるu生成部をさらに有し、
前記制御部は、
前記S=S+A×B+u×Nの演算時に前記u生成部を参照することで前記被乗数uの値を決定する請求項11または12記載の情報処理装置。
【請求項14】
前記ビット数qは2である請求項10乃至13のいずれか1項記載の情報処理装置。
【請求項15】
前記ビット数qは4である請求項10乃至13のいずれか1項記載の情報処理装置。
【請求項16】
前記第1の記憶素子及び前記第2の記憶素子はラッチ回路である請求項10乃至15のいずれか1項記載の情報処理装置。
【請求項17】
前記第3の記憶素子、前記第4の記憶素子及び前記第5の記憶素子はシフトレジスタである請求項10乃至16のいずれか1項記載の情報処理装置。

発明の詳細な説明 【技術分野】
【0001】
本発明はべき乗剰余演算を効率よく処理するための乗算剰余演算器及びそれを備えた情報処理装置に関する。
【背景技術】
【0002】
近年、パーソナルコンピュータやPDA(Personal Digital(Data) Assistants)あるいは携帯電話機等の各種情報処理装置の処理能力が飛躍的に向上し、さらに各種記録メディアの大容量化や通信インフラストラクチャーの整備が進んだことで、個人情報や企業情報等がネットワークや無線手段を介して送受信される機会が増大している。そのため、それらの情報を秘匿化し第三者への漏洩を防ぐ技術が益々重要になってきている。
【0003】
送受信データを秘匿化するための一般的な手法としては、データを送受信する端末装置どうしが共通の鍵を用いて該データの暗号化と復号を行う共通鍵暗号方式がよく知られている。さらに、近年ではBtoB、BtoC等の電子商取引の拡大に伴ってPKI(Public Key Infrastructure)技術が注目されている。
【0004】
PKIの基本技術である公開鍵暗号方式は、公開鍵を用いて送信データを暗号化し、該公開鍵とペアとなる公開することのない秘密鍵を用いて受信データを復号する方式である。この公開鍵暗号方式は、送信側と受信側で異なる鍵を用い、かつ秘密鍵を通信相手に通知する必要が無いため、上述した共通鍵暗号方式に比べて秘匿化性能が向上する。
【0005】
公開鍵暗号方式では、現在、RSA(Rivest, Shamir Adleman)暗号が主として用いられている(例えば、非特許文献1参照)。RSA暗号は、任意の2つの素数を乗算した値Nを素因数分解する際の困難性とNを法とする数の世界の性質とを利用する暗号化方式であり、暗号化及び復号化のためにべき乗剰余演算(MdmodN)を実行する。
【0006】
べき乗剰余演算は、通常、以下に示す乗算剰余演算の繰り返し処理に置き換えて実行される。
【0007】
例えば、d=19とするとき、C=MdmodNは、
d=19=1+2×(1+2×(0+2×(0+2×1)))により、
C=M19modN
=M1+2×(1+2×(0+2×(0+2×1)))modN
=(((((M120202121modN
=(((M222M)2MmodN
となる。このようにdを分解すれば、Mを単純にd回掛けるよりも演算回数を低減できるため、演算時間を短縮できる。なお、dの分解方法については様々な方法が知られており、上記はその一例を示している。
【0008】
しかしながら、このような乗算剰余演算も、乗算によって演算桁数が倍になり、さらにその乗算結果をNで除算するため、ハードウェアまたはソフトウェアのいずれを利用しても効率よく処理するのが非常に困難な演算である。そのため、乗算剰余演算を効率化するための様々な手法が検討され、代表的な例としてモンゴメリ(Montgomery)法と呼ばれるアルゴリズムを応用した演算方法が知られている(例えば、特許文献1参照)。
【0009】
モンゴメリ法を応用すると、除算を実質的に行わずに乗算と加減算で上記乗算剰余演算が実現可能であり、乗算剰余演算P(AB)N=AB・r-nmodN=Sは、例えば、以下の(1)~(8)で示す手順で求めることができる。但し、0≦N<rn、Nは奇数(Nとrは互いに素である)、0≦A<N、0≦B<N、A=An-1n-2…A0(例えばA=A3210=1234)である。
(1)v=-N-1modr
(2)S=0
(3)for i=0 to n-1 {
(4) S=S+Ai・B
(5) u=S・vmodr
(6) S=S+u・N
(7) S=S/r
(8)}
乗算剰余演算は、上記アルゴリズムからS=S+Ai×B+u×N(i=0~n-1)の繰り返し演算処理に置き換え可能であり、この処理を実現するための回路である乗算剰余演算器は、例えば図6に示すような構成になる。
【0010】
図6は従来の乗算剰余演算器の構成を示すブロック図である。
【0011】
図6に示すように、従来の乗算剰余演算器は、被乗数である上記Aの値を保持する第1のラッチ回路51と、被乗数である上記uの値を保持する第2のラッチ回路52と、A+uの値を保持する第3のラッチ回路53と、1ビット毎に供給される乗数B、Nの値に応じて被乗数A、u、A+u、または0H(全ビット0)を選択し出力するセレクタ57と、セレクタ57から出力される値を用いてA×B+u×Nの演算を行う周知の桁上げ保存加算器(Carry Save Adder:以下、CSAと称す)56と、CSA56から出力される乗算剰余演算結果Sと外部で保持された算出済みの乗算剰余演算結果Sとを加算し、該加算結果を乗算剰余演算結果Sとして出力する加算器59とを有する構成である。なお、A、u、及びA+uの各値は、例えば不図示の制御部により第1のラッチ回路51~第3のラッチ回路53に供給され、乗数B、N、及び0Hの各値は、例えば不図示の制御部によりセレクタ57に供給される。
【0012】
図6に示す乗算剰余演算器では、乗算剰余演算器の処理ビット長(例えば、512bit)の乗数B、Nがそれぞれ1ビット単位でセレクタ57に供給される。また、被乗数A、u、A+uは、CSA56の処理ビット長(図6ではmビット)に対応して、該ビット長単位でラッチ回路に格納され、CSA56に供給される。したがって、例えば乗算剰余演算器の処理ビット長が512bitであり、CSA56の処理ビット長が128bitの場合、図6に示す構成では、被乗数A、u、A+uの選択処理を512回繰り返すことでA(128bit)×B(512bit)+u(128bit)×N(512bit)の演算が完了し、さらにそれを4回繰り返すことでA(512bit)×B(512bit)+u(512bit)×N(512bit)の演算処理が完了することになる。
【0013】
セレクタ57は、1ビットづつ供給される乗数B、Nの値に応じて、第1のラッチ回路51~第3のラッチ回路53から供給される被乗数A、u、A+u、または0Hを選択しCSA56に供給する。CSA56は、セレクタ57から順次供給される被乗数A、u、A+uまたは0Hをシフト加算することでA×B+u×Nを算出し、その中間演算結果を保持しつつ乗算剰余演算結果Sを1ビット単位で出力する。

【非特許文献1】三谷政昭著、「やり直しのための工業数学」、第5版、CQ出版社、2003年2月1日、p.115-122
【特許文献1】特表2001-527673号公報
【発明の開示】
【発明が解決しようとする課題】
【0014】
現在、公開鍵暗号方式では、上記べき乗剰余演算のC、M、N、dに1024ビットの数値を用いたRSA暗号が広く利用され、さらにビット数が増えることも予想される。そのため、暗号化及び復号化に膨大な量の乗算剰余演算を実行しなければならない。公開鍵暗号方式は、暗号化及び復号化に要する処理時間が共通鍵暗号方式に比べて長いことが問題であり、乗算剰余演算に要する演算時間の短縮が重要な課題となっている。
【0015】
なお、市場では、携帯電話機、PDA、パーソナルコンピュータやサーバ装置等の情報処理装置の普及に伴い、処理性能が高く、かつ低コストな製品が求められている。したがって、このような要求を満たすためには、乗算剰余演算に要する演算時間を短縮すると共に、回路規模の削減を実現できる乗算剰余演算器が必須となる。
【0016】
本発明は上記したような従来の技術が有する問題点を解決するためになされたものであり、演算時間をより短縮できる乗算剰余演算器及び情報処理装置を提供することを目的とする。
【0017】
また、本発明のさらなる目的は、回路規模を増大させることなく演算時間を短縮できる乗算剰余演算器及び情報処理装置を提供することにある。
【課題を解決するための手段】
【0018】
上記目的を達成するため本発明の乗算剰余演算器は、被乗数をA、uとし、乗数をB、Nとし、乗算剰余演算結果をSとしたとき、S=S+A×B+u×Nを算出するための乗算剰余演算器であって、
複数のビット数q単位で供給される前記乗数Bの値に応じて前記被乗数Aまたは0の値を切換えて出力し、前記ビット数q単位で供給される前記乗数Nの値に応じて前記被乗数uまたは0の値を切換えて出力するセレクタと、
前記セレクタから順次出力される値を用いてA×B+u×Nの演算を実行する桁上げ保存加算器と、
前記桁上げ保存加算器から前記ビット数q単位で出力される前記A×B+u×Nの演算結果と、前記ビット数q単位で供給される過去の該演算結果とを加算し、該加算結果を前記乗算剰余演算結果Sとして出力する加算器と、
を有する構成である。
【0019】
一方、本発明の情報処理装置は、上記乗算剰余演算器と、
前記被乗数Aを保持し、前記セレクタに供給する第1の記憶素子と、
前記被乗数uを保持し、前記セレクタに供給する第2の記憶素子と、
前記乗数Bを保持し、前記セレクタに前記ビット数q単位で供給する第3の記憶素子と、
前記乗数Nを保持し、前記セレクタに前記ビット数q単位で供給する第4の記憶素子と、
前記加算器から出力される前記乗算剰余演算結果Sを保持し、前記ビット数q単位で該乗算剰余演算結果Sを前記加算器に供給する第5の記憶素子と、
を有する構成である。
【0020】
上記のように構成された乗算剰余演算器及び情報処理装置では、乗数を複数のビット数q単位でセレクタに供給し、セレクタにより該乗数の値に応じて被乗数または0の値を切換えてCSAに供給するため、CSAの処理ビット長をビット数qの値に反比例して短縮できる。
【0021】
また、本発明の乗算剰余演算器及び情報処理装置は、予め算出された、前記被乗数A、前記乗数B、前記乗数N、及び前記乗算剰余演算結果Sの値に対する前記被乗数uの値の関係が格納されるu生成部をさらに有し、
制御部により、前記S=S+A×B+u×Nの演算時に前記u生成部を参照することで前記被乗数uの値を決定する構成である。
【0022】
なお、前記ビット数qは2または4であることが望ましい。
【0023】
上記のような乗算剰余演算器は、ビット数qを2または4とすることで、u生成部の回路規模の増大を抑制できる。
【発明の効果】
【0024】
本発明の乗算剰余演算器及び情報処理装置は、CSAの処理ビット長をビット数qの値に反比例して短縮できるため、従来の乗算剰余演算器よりも演算時間を短縮できる。
【0025】
また、CSAの処理ビット長を短縮することで、CSAが備えるフリップフロップ数が低減するため、乗算剰余演算器の回路規模が低減する。特に、ビット数qを2または4とすれば、u生成部の回路規模が増大することがないため、回路規模を増大させることなく演算時間を短縮できる。
【発明を実施するための最良の形態】
【0026】
次に本発明について図面を参照して説明する。
【0027】
図1は本発明の乗算剰余演算器の一構成例を示すブロック図であり、図2は本発明の情報処理装置の一構成例を示すブロック図である。
【0028】
図1に示すように、本発明の乗算剰余演算器は、被乗数Aの値を保持する第1のラッチ回路1と、被乗数uの値を保持する第2のラッチ回路2と、乗数Bの値を保持する第1のシフトレジスタ4と、乗数Nの値を保持する第2のシフトレジスタ5と、第1のシフトレジスタ4から複数ビット(図1では2bit)毎に供給される乗数Bの値に応じて被乗数Aまたは0Hを選択しCSA6に供給する第1のセレクタ(Sel1)71及び第2のセレクタ(Sel2)72と、第2のシフトレジスタ5から複数ビット(図1では2bit)毎に供給される乗数Nの値に応じて被乗数uまたは0Hを選択しCSA6に供給する第3のセレクタ(Sel3)73及び第4のセレクタ(Sel4)74と、第1~第4のセレクタ71~74から供給される値を用いてA×B+u×Nの演算を行う周知のCSA6と、CSA6から複数ビット(図1では2bit)単位で出力される乗算剰余演算結果Sを保持し、複数ビット(図1では2bit)単位で出力する第3のシフトレジスタ8と、CSA6から出力されるA×B+u×Nの演算結果と第3のシフトレジスタ8の出力とを加算し、加算結果を乗算剰余演算結果Sとして第3のシフトレジスタ8に再び格納する加算器9と、被乗数uの値を生成するためのテーブルが格納されるu生成部10と、被乗数A、uの値を第1のラッチ回路1及び第2のラッチ回路2に供給し、乗数B、Nの値を第1のシフトレジスタ4及び第2のシフトレジスタ5に供給し、0Hを第1~第4のセレクタ71~74に供給すると共に、CSA6、u生成部10及び第3のシフトレジスタ8の動作を制御する制御部11とを有する構成である。
【0029】
本発明の乗算剰余演算器は、制御部11による被乗数A、uのラッチ回路へのセット、及び乗数B、Nのシフトレジスタへのセットを契機に、外部から供給される所定周波数のクロック(CK)にしたがって動作する回路であり、制御部11は、例えばプログラムにしたがって動作するCPU、DSPあるいは論理回路等によって実現される。
【0030】
このような構成において、本発明の乗算剰余演算器では、被乗数A、uが、CSA6の処理ビット長に対応して複数に分割され、制御部11により該分割単位で第1及び第2のラッチ回路1、2に格納される。一方、乗数B、Nは、制御部11により、例えば乗算剰余演算器の処理ビット長で第1及び第2のシフトレジスタに格納される。なお、乗数B、Nも、所定のビット長毎に複数に分割され、制御部11により該分割単位で第1及び第2のシフトレジスタに格納されてもよい。
【0031】
各セレクタには、第1のラッチ回路1及び第2のラッチ回路2から上記分割単位で被乗数A、uが供給され、第1のシフトレジスタ4及び第2のシフトレジスタ5から複数ビット単位で乗数B、Nが供給される。図1では、乗数B、Nがそれぞれ2bit単位で第1~第4のセレクタ71~74に供給される例を示しているが、乗数B、Nは、4bit単位、あるいはそれ以上のビット数単位でセレクタに供給されてもよい。なお、図1では4つのセレクタを用いて被乗数A、uまたは0Hを切換える構成を示しているが、乗数B、Nの値に対応する被乗数A、uまたは0Hを選択できれば、セレクタの数はいくつであってもよい。
【0032】
第1のセレクタ71及び第2のセレクタ72は、第1のシフトレジスタ4から複数ビットづつ供給される乗数Bの値に応じて、被乗数A(1A、2A)または0Hを選択しCSA6に供給する。同様に、第3のセレクタ73及び第4のセレクタ74は、第2のシフトレジスタ5から複数ビットづつ供給される乗数Nの値に応じて、被乗数u(1u、2u)または0Hを選択しCSA6に供給する。
【0033】
ここで、1Aは被乗数Aの1倍の値であり、2Aは被乗数Aの2倍の値である。また、1uは被乗数uの1倍の値であり、2uは被乗数uの2倍の値である。2A、2uは、例えば被乗数A、uの値を1ビットシフトさせれば得られるため容易に生成できる。図1では第1のセレクタ71で2Aを生成し、第3のセレクタ73で2uを生成する例を示しているが、2A、2uはCSA6内で生成してもよい。
【0034】
CSA6は、各セレクタから順次供給される被乗数または0Hをシフト加算することでA×B、及びu×Nをそれぞれ算出し、それらの加算結果(乗算剰余演算結果)Sを複数ビット単位で出力する。CSA6から出力された演算結果は、第3のシフトレジスタ8の出力(過去の乗算剰余演算結果S)と複数ビット単位で加算され、加算結果は第3のシフトレジスタ8に再び格納される。
【0035】
なお、図1に示した第1のラッチ回路1、第2のラッチ回路2、第1シフトレジスタ4、第2のシフトレジスタ5、第3のシフトレジスタ8、及びu生成部10は、乗算剰余演算器の内部に備えている必要はなく、乗算剰余演算器を利用する情報処理装置に備えていてもよい。同様に、制御部11も乗算剰余演算器の内部に備えている必要はなく、乗算剰余演算器を利用する情報処理装置が備える処理装置(CPU)によって実現してもよい。すなわち、乗算剰余演算器は、図1の点線内の構成要素のみを備えていればよい。
【0036】
また、被乗数A、uは、ラッチ回路に格納する必要はなく、例えばシフトレジスタやRAM等のようにデータを一時的に保持できる記憶素子であればどのようなものを用いてもよい。同様に、乗数B、N、及び演算結果Sは、シフトレジスタに格納する必要はなく、例えばRAMのように格納されたデータを複数ビット単位で出力できる記憶素子であればどのようなものを用いてもよい。
【0037】
図2に示すように、本発明の情報処理装置は、例えばパーソナルコンピュータやサーバ装置等のコンピュータシステムであり、プログラムにしたがって所定の処理を実行する処理装置20と、処理装置20に対してコマンドや情報等を入力するための入力装置30と、処理装置20の処理結果をモニタするための出力装置40とを有する構成である。
【0038】
処理装置20は、CPU21と、CPU21の処理に必要な情報を一時的に記憶する主記憶装置22と、CPU21に上記制御部11の処理を実行させるプログラムが記録された記録媒体23と、処理に必要なデータ等を蓄積するデータ蓄積装置24と、主記憶装置22、記録媒体23、及びデータ蓄積装置24とのデータ転送を制御するメモリ制御インタフェース部25と、入力装置30及び出力装置40とのインタフェース装置であるI/Oインタフェース部26と、図1に示した乗算剰余演算器27と、ネットワーク等との通信を制御するインタフェースである通信制御装置28とを備え、それらがバス29等を介して接続された構成である。なお、処理装置20には、乗算剰余演算器27の構成に応じて、被乗数A、uを保持するラッチ回路、及び乗数B、N、及び演算結果Sを保持するシフトレジスタ等を備えていてもよい。
【0039】
処理装置20は、記録媒体23に記録されたプログラムにしたがってCPU21により上記制御部11の処理を実行し、乗算剰余演算器27を用いてS=S+Ai×B+u×Nの演算を実行する。なお、記録媒体23は、磁気ディスク、半導体メモリ、光ディスクあるいはその他の記録媒体であってもよい。
【0040】
次に、本発明の乗算剰余演算器の動作について図面を用いて具体的に説明する。
【0041】
以下では、A、u、B、Nがそれぞれ512bitであり、処理ビット長が64bitのCSA6を用い、第1及び第2のシフトレジスタ4、5がそれぞれ2bit単位で各セレクタに乗数B、Nを供給し、第3のシフトレジスタ8が2bit単位で乗算剰余演算結果Sを入出力する場合を例にして説明する。また、第1及び第2のシフトレジスタ4、5には乗数B、Nがそれぞれ512bit単位で格納され、第1及び第2のラッチ回路1、2には被乗数A、uがCSA6の処理ビット長に合わせて64bit単位で格納されるものとする。
【0042】
処理ビット長が64bitのCSA6を用い、乗数B、Nを2bit単位で出力する場合、A、u、B、Nがそれぞれ512bitの乗算剰余演算(512bit×512bit×2-512 mod 512bit)は、64bit×512bit×2-64 mod 512bit(A×B×2-64 mod N)の演算を繰り返し実行すればよい。
【0043】
本発明の乗算剰余演算器では、モンゴメリ法による乗算剰余演算の特徴である、下位ビットが0になることを利用して(ここでは、下位64bitが0H)、上記S、A、B、Nの値に対応するuを予め算出し、u生成部10にテーブル形式で格納しておく。
【0044】
例えば、乗数を2bit単位で出力する場合、uの値は以下のように求める(但し、Nは奇数)。
【0045】
N[1:0]=01,(S+AiB)[1:0]=00のとき、
S=S+AiB+uN=00となるuは、u[1:0]=00
N[1:0]=01,(S+AiB)[1:0]=01のとき、
S=S+AiB+uN=00となるuは、u[1:0]=11
N[1:0]=01,(S+AiB)[1:0]=10のとき、
S=S+AiB+uN=00となるuは、u[1:0]=10
N[1:0]=01,(S+AiB)[1:0]=11のとき、
S=S+AiB+uN=00となるuは、u[1:0]=01
N[1:0]=11,(S+AiB)[1:0]=00のとき、
S=S+AiB+uN=00となるuは、u[1:0]=00
N[1:0]=11,(S+AiB)[1:0]=01のとき、
S=S+AiB+uN=00となるuは、u[1:0]=01
N[1:0]=11,(S+AiB)[1:0]=10のとき、
S=S+AiB+uN=00となるuは、u[1:0]=10
N[1:0]=11,(S+AiB)[1:0]=11のとき、
S=S+AiB+uN=00となるuは、u[1:0]=11
以上をまとめると、表1のようになる。
【0046】
【表1】
JP0004170267B2_000002t.gif

【0047】
ここで、A、B、Nはいずれも既知の値(第1のラッチ回路1、第1のシフトレジスタ4及び第2のシフトレジスタ5に格納する値)であり、Sは0H(演算開始時)または直前の64bit×512bit×2-64 mod 512bitの演算結果を用いるため既知である。なお、Nは奇数であるため、N[1:0]=01または11で固定である。したがって、A、B、及びSの各値を基に算出した被乗数uの値をテーブル形式でu生成部10に格納しておき、制御部11は該テーブルを参照して被乗数uの値を決定する。なお、参考として表2に乗数B、Nを4bit単位で出力する場合に用いるuを生成するためのテーブルを示す。
【0048】
【表2】
JP0004170267B2_000003t.gif

【0049】
本発明の乗算剰余演算器では、まず、制御部11により、第1のラッチ回路1に被乗数A(512bit)の最下位64bitのデータをセットし、第1のシフトレジスタ4に乗数B(512bit)のデータをセットし、第2のシフトレジスタ5に乗数N(512bit)のデータをセットする。
【0050】
続いて、制御部11は、64bitの被乗数A、64bitの乗数B、64bitの乗数Nからu生成部10に格納されたテーブルを参照してu(64bit分)の値を求め、第2のラッチ回路2に格納する。
【0051】
制御部11による第1のラッチ回路1、第2のラッチ回路2、第1のシフトレジスタ4及び第2のシフトレジスタ5に対する被乗数または乗数のセットが完了すると、乗算剰余演算器はS=S+A×B+u×Nの演算を開始する。
【0052】
乗算剰余演算器は、まず、第1のセレクタ71及び第2のセレクタ72にて、第1のシフトレジスタ4から出力される2bitの乗数Bの値から被乗数A(64bit)または0Hを選択しCSA6へ供給する。ここでは、第1のセレクタ71により0H/2Aを切換え、第2のセレクタ72により0H/1Aを切換える。
【0053】
同様に、乗算剰余演算器は、第3のセレクタ73及び第4のセレクタ74にて、第2のシフトレジスタ5から出力される2bitの乗数Nの値から被乗数u(64bit)または0Hを選択しCSA6へ供給する。ここでは、第3のセレクタ73により0H/2uを切換え、第4のセレクタ74により0H/1uを切換える。
【0054】
CSA6は、各セレクタから順次供給される被乗数または0Hの値を、桁合わせを実行しつつ加算することでA×B、及びu×Nを算出し、それらの加算結果(乗算剰余演算結果)Sを2bit単位で出力する。CSA6から出力された演算結果は、第3のシフトレジスタ8の出力と2bit単位で加算器9にて加算され、加算後の値が第3のシフトレジスタ8に再び格納される。
【0055】
図3は本発明の乗算剰余演算器が実行する演算処理のうち、A×Bの演算処理の手順を示している。u×Nの演算処理も図3に示すA×Bの演算処理と同様である。図3に示すA×Bの演算結果の下位2ビット(φ1)と、同様にして求めたu×Nの演算結果の下位2ビットの加算結果が、CSA6の出力(2bit)となる。
【0056】
この処理を第1のシフトレジスタ4及び第2のシフトレジスタ5内の全てのビットデータに対して繰り返し実行することで、64bit×512bit×2-64 mod 512bitの演算が終了する。但し、この段階ではCSA6の内部に部分積の演算結果の上位64bitが残っているため、このデータを制御部11の指示により第3のシフトレジスタ8に格納する。その結果、第3のシフトレジスタ8に64bit×512bit×2-64 mod 512bitの演算結果Sが格納される。
【0057】
乗算剰余演算器は、64bit×512bit×2-64 mod 512bitの演算が完了すると、制御部11により第1のラッチ回路1に被乗数A(512bit)の次の下位64bitのデータ(最下位から65bit目~128bit目のデータ)をセットし、上記と同様にu生成部10のテーブルを参照して被乗数uの値を求め、求めた値を第2のラッチ回路2に格納した後、再び64bit×512bit×2-64 mod 512bitの演算を開始する。
【0058】
以降、第1のラッチ回路1に格納される被乗数A(512bit)の全てのビットデータに対して同様の処理を繰り返し実行する。すなわち、上記64bit×512bit×2-64 mod 512bitの演算を8回繰り返す。その結果、本発明の乗算剰余演算器による512bit×512bit×2-512 mod 512bitの演算が終了する。
【0059】
次に、本発明の乗算剰余演算器の効果について図面を用いて説明する。
【0060】
図4は乗数を1bit単位で出力する従来の乗算剰余演算器の回路規模及び乗数を2bitまたは4bit単位で出力する本発明の乗算剰余演算器の回路規模を示すグラフである。また、図5は乗数を1bit単位で出力する従来の乗算剰余演算器の処理クロック数及び乗数を2bitまたは4bit単位で出力する本発明の乗算剰余演算器の処理クロック数を示すグラフである。なお、図5は、乗算剰余演算器の処理ビット長を512bitとしたときの乗算剰余演算に必要な処理クロック数を示している。
【0061】
図4及び図5に示す1bit構成とは乗数を1bit単位で出力する従来の乗算剰余演算器の構成を示し、2bit構成とは乗数を2bit単位で出力する本発明の乗算剰余演算器の構成を示し、4bit構成とは乗数を4bit単位で出力する本発明の乗算剰余演算器の構成を示している。以降の説明でも1bit構成、2bit構成、あるいは4bit構成と称した場合は同様の構成を示しているものとする。
【0062】
また、図4及び図5に示すグラフの横軸は、乗算剰余演算器の処理ビット長(128bit、256bit、512bit)を示し、以下では、乗算剰余演算器の処理ビット長が同じである場合、乗数の出力ビット単位に反比例してCSA6の処理ビット長が短縮されるものとする。それらの関係を表3に示す。ここで、表3の各エントリは(CSAの処理ビット長)*(出力ビット数)を示している。
【0063】
【表3】
JP0004170267B2_000004t.gif

【0064】
図4から分かるように、乗算剰余演算器の処理ビット長が同じである場合、乗数を複数ビット単位で出力する本発明の乗算剰余演算器は、乗数を1bit単位で出力する従来の乗算剰余演算器に比べて回路規模が低減する。
【0065】
図4を基に1bit構成の従来の乗算剰余演算器と4bit構成の本発明の乗算剰余演算器を比較した場合、本発明の乗算剰余演算器は、従来の約半分の回路規模となる。これは2bit構成とすることでCSA6の処理ビット長を従来の半分にできるためであり、4bit構成とすることでCSA6の演算ビット長を従来の1/4にできるためである。
【0066】
例えば、乗算剰余演算器の処理ビット長を128bitとした場合、従来の乗算剰余演算器では、CSAでSUM(加算結果)の値とCARRY(桁上げ)の値をそれぞれ128個ずつ保持する必要があるため、256個のフリップフロップ(Data-F/F)が必要になる。
【0067】
それに対して、2bit構成の本発明の乗算剰余演算器が備えるCSA6では、処理ビット長が従来の半分の64bitで済むため、SUMの値とCARRYの値を保持するフリップフロップも128個で済む。すなわち、本発明のように乗数を複数ビット単位で出力すると、CSA6が備えるフリップフロップの数を大きく削減できるため、回路規模を低減できる。
【0068】
一方、図5から分かるように、乗算剰余演算器の処理ビット長が同じである場合、乗数を複数ビット単位で出力する本発明の乗算剰余演算器は、乗数を1bit単位で出力する従来の乗算剰余演算器に比べて処理クロック数が少なくなる。これはCSA6内に残る演算結果を出力する処理時間の差から生じる結果である。
【0069】
本発明の乗算剰余演算器では、上述したようにCSA6の処理ビット長を従来の半分あるいは1/4にできるが、被乗数を分割して処理するため、乗算剰余演算を複数回繰り返すことになる。そのため、本発明の乗算剰余演算器では、従来の乗算剰余演算器よりも繰り返し演算の回数が増え、CSA6内に残る部分積の演算結果を出力する回数も増えてしまう。
【0070】
しかしながら、本発明の乗算剰余演算器では、CSA6の処理ビット長を短縮できることから、CSA6内に残る演算結果を出力する処理時間も2bit構成の場合で従来の半分となり、4bit構成の場合で従来の1/4となる。そのため、僅かではあるが、1つのA、u、B、Nに対する乗算剰余演算の処理時間は従来よりも低減する。
【0071】
本発明の乗算剰余演算器は、処理時間の大幅な低減は実現できないが、多数の数字の配列に対して大きな値のべき乗剰余演算を行うRSAによる暗号化及び復号に本発明の乗算剰余演算器を用いる場合は、この僅かな処理時間の向上が非常に有益となる。
【0072】
ところで、被乗数uは、乗数B、Nの出力ビット数をqとすると、上記モンゴメリ法を応用したアルゴリズムの(1)、(5)から以下の式で算出できる。
【0073】
v=-N-1mod2q
u=Svmod2q
ここで、vは演算開始時に一度だけ計算する値である。なお、rに代えて2qとしているのはrを2進数で表したためである。
【0074】
q=1となる従来の乗算剰余演算器では、Nが奇数であることからv=1となるため、u=Smod2=S[0]となり、被乗数uはSの下位ビットに等しくなる。したがって、被乗数uを実施的に計算する必要はない。
【0075】
しかしながら、q>1となる本発明の乗算剰余演算器では、u=S[0]が成立しないため、上記2つの演算が必要になる。但し、qの値が小さい場合(例えば、q=2、4)は、v、uも2bitまたは4bitであり、その演算に必要なN、Sも2bitまたは4bitである。そのため、本発明ではA、B、S、Nの値から予めuの値を算出してテーブルを作成しておき、該テーブルを参照することで第2のラッチ回路2に格納するuを決定している。このqの値を大きくすれば、CSA6の処理ビット長をさらに短縮できるため、乗算剰余演算の処理時間をさらに短縮することができる。
【0076】
しかしながら、q>4の場合、すなわち乗数B、Nを8ビット以上で出力する構成では、被乗数uをテーブル内から選択するために必要な、例えばデコーダ等の回路規模が増大するため、記憶素子を含むu生成部10の回路規模が増大し、上述したCSA6の処理ビット長を短縮することによる乗算剰余演算器の回路規模の低減効果を相殺してしまう。
【0077】
表4にqの値に対するu生成部10のレイアウト面積(単位:mm2)を示し、表5にqの値に対するCSAとu生成部とを含む総レイアウト面積(単位:mm2)を示す。
【0078】
【表4】
JP0004170267B2_000005t.gif

【0079】
【表5】
JP0004170267B2_000006t.gif

【0080】
表4及び表5から分かるように、例えばCSAの処理ビット長を256bitとしたとき、q=1のときの総レイアウト面積に対して、CSAの処理ビット長を128bitにできるq=2の場合及びCSAの処理ビット長を64bitにできるq=4の場合の総レイアウト面積は低減する。しかしながら、q=8にすると総レイアウト面積が増大してしまう。
【0081】
したがって、本発明の乗算剰余演算器では、qの値が2または4であることが回路規模の増大を抑制しつつ演算時間を短縮できるために望ましい。但し、回路規模よりも演算時間の向上を優先する場合は、qの値を8以上に設定してもよい。その場合、qの値はu生成部10のレイアウト面積の増大を考慮しつつ最適な値を選択すればよい。
【図面の簡単な説明】
【0082】
【図1】本発明の乗算剰余演算器の一構成例を示すブロック図である。
【図2】本発明の情報処理装置の一構成例を示すブロック図である。
【図3】本発明の乗算剰余演算器が実行する演算処理のうち、A×Bの演算処理の手順を示す模式図である。
【図4】本発明の乗算剰余演算器の回路規模を示すグラフである。
【図5】本発明の乗算剰余演算器の処理クロック数を示すグラフである。
【図6】従来の乗算剰余演算器の構成を示すブロック図である。
【符号の説明】
【0083】
1 第1のラッチ回路
2 第2のラッチ回路
4 第1のシフトレジスタ
5 第2のシフトレジスタ
6 CSA
1 第1のセレクタ
2 第2のセレクタ
3 第3のセレクタ
4 第4のセレクタ
8 第3のシフトレジスタ
9 加算器
10 u生成部
11 制御部
20 処理装置
21 CPU
22 主記憶装置
23 記録媒体
24 データ蓄積装置
25 メモリ制御インタフェース部
26 I/Oインタフェース部
27 乗算剰余演算器
28 通信制御装置
29 バス
30 入力装置
40 出力装置
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5