TOP > 国内特許検索 > 剰余系の計算方法及び装置並びにプログラム

剰余系の計算方法及び装置並びにプログラム コモンズ 外国出願あり

国内特許コード P06P004242
整理番号 NU-0064
掲載日 2007年3月23日
出願番号 特願2005-242956
公開番号 特開2007-057811
登録番号 特許第4182226号
出願日 平成17年8月24日(2005.8.24)
公開日 平成19年3月8日(2007.3.8)
登録日 平成20年9月12日(2008.9.12)
発明者
  • ▲高▼木 直史
  • カイハラ、マルセロ エミリオ
出願人
  • 学校法人名古屋大学
発明の名称 剰余系の計算方法及び装置並びにプログラム コモンズ 外国出願あり
発明の概要

【課題】 剰余系における乗算剰余算の繰返し計算を高速化するための計算方法を提供する。
【解決手段】剰余系における変数U,Vを新たに定義する領域において、X=U・R mod M、Y=V・R mod Mに変換し、乗算剰余算U・V mod MをX・Y・R-1 mod M=U・V・R mod Mに置き換える。ここで、R=rm(ただし、0<m<n、m:整数)とすると、乗数UはX=U・rm mod Mに、被乗数VはY=V・rm mod Mに変換される(S101,S102)。つまり、U,Vが新たに定義する領域のX,Yに変換される。そして、乗算剰余算は、U・V mod Mから、新たに定義する領域におけるX・Y・r-m mod Mに置換される(S104)。このようにして、パラメータmを導入することにより、乗数Yを上位部分YHと下位部分YLとの二つの部分に分割し、これらを並列に処理することが可能となる。
【選択図】 図1

従来技術、競合技術の概要


従来、ネットワーク上で送受信されるデータのセキュリティを確保するために、データを暗号化・復号化する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.

産業上の利用分野


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

特許請求の範囲 【請求項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)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2005242956thum.jpg
出願権利状態 権利存続中
名古屋大学の公開特許情報を掲載しています。ご関心のある案件がございましたら、下記まで電子メールでご連絡ください。


PAGE TOP

close
close
close
close
close
close
close