Top > Search of Japanese Patents > METHOD, DEVICE, AND PROGRAM FOR COMPUTING RESIDUE SYSTEM

METHOD, DEVICE, AND PROGRAM FOR COMPUTING RESIDUE SYSTEM commons foreign

Patent code P06P004242
File No. NU-0064
Posted date Mar 23, 2007
Application number P2005-242956
Publication number P2007-057811A
Patent number P4182226
Date of filing Aug 24, 2005
Date of publication of application Mar 8, 2007
Date of registration Sep 12, 2008
Inventor
  • (In Japanese)▲高▼木 直史
  • (In Japanese)カイハラ、マルセロ エミリオ
Applicant
  • (In Japanese)国立大学法人名古屋大学
Title METHOD, DEVICE, AND PROGRAM FOR COMPUTING RESIDUE SYSTEM commons foreign
Abstract PROBLEM TO BE SOLVED: To provide a method, a device, and a program for fast repeated computation of modular multiplication in a residue system.
SOLUTION: In an area for newly defining variables U and V in the residue system, they are converted into X=U×R mod M and Y=V×R mod M, respectively, and the modular multiplication U×V mod M is replaced with X×Y×R-1 mod M=U×V×R mod M. Here, when R is set as R=rm (0<m<n, m is an integer), the multiplier U is converted into X=U×rm mod M, and the multiplicand V is converted into Y=V×rm mod M (S101, S102), that is, U and V are converted into X and Y in a newly defined area. The modular multiplication U×V mod M is replaced (S104) with X×Y×r-m mod M in the newly defined area. Thus, by introducing a parameter m, the multiplier Y is divided into two parts - a high-order part YH and a low-order part YL - so that these parts can be processed in parallel.
Outline of related art and contending technology (In Japanese)


従来、ネットワーク上で送受信されるデータのセキュリティを確保するために、データを暗号化・復号化するRSA(Rivest-Shamir-Adleman)等の公開鍵暗号システムが用いられている。



その公開鍵暗号システムでは、使用される公開鍵のサイズ(桁数)を大きくすれば、不正な方法による暗号の解読が困難となり、情報を送受信する際のセキュリティをより強化することができる。



ところが、RSA等の公開鍵暗号システムでは、暗号化と復号化のために剰余系指数演算を行う必要があり、その剰余系指数演算の量は公開鍵のサイズにともなって多くなる。
そして、ほとんどの場合、その剰余系指数演算は非常に大きな整数の乗算剰余算(剰余系乗算)を繰返し計算することにより実現されており、その乗算剰余算の繰返し計算には膨大な時間が必要であった。



したがって、この乗算剰余算の繰り返し計算の実行速度を速くすることができれば、使用する鍵のサイズをさらに大きくでき、ネットワーク上で送受信されるデータのセキュリティ強化を図ることができる。



乗算剰余算の繰返し計算を高速化する方法として、変数をモンゴメリの領域に変換して個々の乗算剰余算をモンゴメリ乗算に置き換える方法があり(例えば、非特許文献1参照)、さらに、そのモンゴメリ乗算の高速化法として基数を増す方法がある(例えば、非特許文献2参照)。



また、個々の乗算剰余算の高速化の方法としてインターリーブ法で基数を増す方法がある(例えば、非特許文献3参照)。
【非特許文献1】
P.L. Montgomery, "Modular Multiplication without Trial Division," Mathematics of Computation, vol.44,no.170,pp.519-521, Apr.1985.
【非特許文献2】
S.E Eldridge and C.D. Walter, "Hardware Implementation of Montgomery's Modular Multiplication Algorithm," IEEE Transactions on Computers, vol.42,no.6,pp.693-699,Jun.1993.
【非特許文献3】
N. Takagi, "A Radix-4 Modular Multiplication Hardware Algorithm for Modular Exponentiation," IEEE Transactions on Computers, vol.41, no.8, pp.949-956, Aug. 1992.

Field of industrial application (In Japanese)


本発明は、剰余系の計算方法及び装置並びにプログラムに関する。

Scope of claims (In Japanese)
【請求項1】
 
r進の整数Mを法とする剰余系において(ただし、Mとrとは互いに素)、前記法M、r進でn桁の変数Y及び変数Xが入力されたときに前記変数Yを上位(n-m)桁のYH
及び下位m桁のYLに分割する分割手段と、
前記変数Yを分割した上位(n-m)桁のYH、前記変数X及び前記法Mで
X・YH mod M
を計算して出力する第1乗算剰余算器と、
前記変数Yを分割した下位m桁のYL、前記変数X及び前記法Mで
X・YL・r-m mod M
を計算して出力する第2乗算剰余算器と、
前記第1乗算剰余算器の出力及び前記第2乗算剰余算器の出力を加算し、その加算結果を出力する加算器と、
を備えたことを特徴とする乗算剰余演算装置。

【請求項2】
 
請求項1に記載の乗算剰余演算装置において、
前記加算器の加算結果を入力し、前記法Mによる剰余算を行って出力する剰余算器を備えたことを特徴とする乗算剰余演算装置。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2005242956thum.jpg
State of application right Registered
(In Japanese)名古屋大学の公開特許情報を掲載しています。ご関心のある案件がございましたら、下記まで電子メールでご連絡ください。


PAGE TOP

close
close
close
close
close
close
close