Top > Search of Japanese Patents > MULTIPLICATION RESIDUES CALCULATING DEVICE AND INFORMATION PROCESSING DEVICE

MULTIPLICATION RESIDUES CALCULATING DEVICE AND INFORMATION PROCESSING DEVICE

Patent code P05A008298
File No. WASEDA-409
Posted date Mar 3, 2006
Application number P2004-203435
Publication number P2006-023647A
Patent number P4170267
Date of filing Jul 9, 2004
Date of publication of application Jan 26, 2006
Date of registration Aug 15, 2008
Inventor
  • (In Japanese)東 邦彦
  • (In Japanese)久門 亨
  • (In Japanese)後藤 敏
  • (In Japanese)池永 剛
Applicant
  • (In Japanese)ルネサスエレクトロニクス株式会社
  • (In Japanese)学校法人早稲田大学
Title MULTIPLICATION RESIDUES CALCULATING DEVICE AND INFORMATION PROCESSING DEVICE
Abstract PROBLEM TO BE SOLVED: To provide a multiplication residues calculating device and an information processing device capable of shortening the operation time without increasing the circuit scale.
SOLUTION: This is a multiplication residues calculating device for the expression of S=S+A×B+u×N. It has a selector to switch to output a multiplicand A or a value 0 depending on the values of a plurality of multipliers B supplied in the unit of the number q of bits and to switch to output a multiplicand u or a value 0 depending on the value of a multiplier N supplied by the count q of bits; a carrying storage adder to calculate A×B+u×N by using the values output sequentially from the selector; and an adder to add the calculated results of A×B+u×N output in the unit of the number q of bits from the carrying storage adder and the past calculated results supplied in the unit of the number q of bits in order to output the added results as the result S of the multiplication residues calculation.
Outline of related art and contending technology (In Japanese)


近年、パーソナルコンピュータやPDA(Personal Digital(Data) Assistants)あるいは携帯電話機等の各種情報処理装置の処理能力が飛躍的に向上し、さらに各種記録メディアの大容量化や通信インフラストラクチャーの整備が進んだことで、個人情報や企業情報等がネットワークや無線手段を介して送受信される機会が増大している。そのため、それらの情報を秘匿化し第三者への漏洩を防ぐ技術が益々重要になってきている。



送受信データを秘匿化するための一般的な手法としては、データを送受信する端末装置どうしが共通の鍵を用いて該データの暗号化と復号を行う共通鍵暗号方式がよく知られている。さらに、近年ではBtoB、BtoC等の電子商取引の拡大に伴ってPKI(Public Key Infrastructure)技術が注目されている。



PKIの基本技術である公開鍵暗号方式は、公開鍵を用いて送信データを暗号化し、該公開鍵とペアとなる公開することのない秘密鍵を用いて受信データを復号する方式である。この公開鍵暗号方式は、送信側と受信側で異なる鍵を用い、かつ秘密鍵を通信相手に通知する必要が無いため、上述した共通鍵暗号方式に比べて秘匿化性能が向上する。



公開鍵暗号方式では、現在、RSA(Rivest, Shamir Adleman)暗号が主として用いられている(例えば、非特許文献1参照)。RSA暗号は、任意の2つの素数を乗算した値Nを素因数分解する際の困難性とNを法とする数の世界の性質とを利用する暗号化方式であり、暗号化及び復号化のためにべき乗剰余演算(MdmodN)を実行する。



べき乗剰余演算は、通常、以下に示す乗算剰余演算の繰り返し処理に置き換えて実行される。



例えば、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
=(((((M12M02M02M12M1modN
=(((M222M)2MmodN
となる。このようにdを分解すれば、Mを単純にd回掛けるよりも演算回数を低減できるため、演算時間を短縮できる。なお、dの分解方法については様々な方法が知られており、上記はその一例を示している。



しかしながら、このような乗算剰余演算も、乗算によって演算桁数が倍になり、さらにその乗算結果をNで除算するため、ハードウェアまたはソフトウェアのいずれを利用しても効率よく処理するのが非常に困難な演算である。そのため、乗算剰余演算を効率化するための様々な手法が検討され、代表的な例としてモンゴメリ(Montgomery)法と呼ばれるアルゴリズムを応用した演算方法が知られている(例えば、特許文献1参照)。



モンゴメリ法を応用すると、除算を実質的に行わずに乗算と加減算で上記乗算剰余演算が実現可能であり、乗算剰余演算P(AB)N=AB・r-nmodN=Sは、例えば、以下の(1)~(8)で示す手順で求めることができる。但し、0≦N<rn、Nは奇数(Nとrは互いに素である)、0≦A<N、0≦B<N、A=An-1An-2…A0(例えばA=A3A2A1A0=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に示すような構成になる。



図6は従来の乗算剰余演算器の構成を示すブロック図である。



図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に供給される。



図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)の演算処理が完了することになる。



セレクタ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号公報

Field of industrial application (In Japanese)


本発明はべき乗剰余演算を効率よく処理するための乗算剰余演算器及びそれを備えた情報処理装置に関する。

Scope of claims (In Japanese)
【請求項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項記載の情報処理装置。

IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2004203435thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close