RNS Montgomery Multiplication Algorithm for Duplicate Processing of Base Transformations(Special Section on Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• This paper proposes a new algorithm to achieve about two-times speedup of modular exponentiation which is implemented by Montgomery multiplication based on Residue Number Systems (RNS). In RNS Montgomery multiplication, its performance is determined by two base transformations dominantly. For the purpose of realizing parallel processing of these base transformations, i.e. "duplicate processing," we present two procedures of RNS Montgomery multiplication, in which RNS bases a and b are interchanged, and perform them alternately in modular exponentiation iteration. In an investigation of implementation, 1.87-times speedup has been obtained for 1024-bit modular multiplication. The proposed RNS Montgomery multiplication algorithm has an advantage in achieving the performance corresponding to that the upper limit of the number of parallel processing units is doubled.

• 社団法人電子情報通信学会の論文
• 2003-01-01

著者

• Shimbo A

  Toshiba Corp. Kawasaki‐shi Jpn

• Shimbo Atsushi

  Corporate Research And Development Center Toshiba Corporation

• Kawamura Shinichi

  Corporate Research & Development Center Toshiba Corporation

• NOZAKI Hanae

  Corporate Research & Development Center, Toshiba Corporation

• Nozaki Hanae

  Corporate Research & Development Center Toshiba Corporation

• SHIMBO Atsushi

  Corporate Research & Development Center, Toshiba Corporation

関連論文

• An SPA-Based Extension of Schindler's Timing Attack against RSA Using CRT(Tamper-Resistance)(Cryptography and Information Security)
• RNS Montgomery Multiplication Algorithm for Duplicate Processing of Base Transformations(Special Section on Cryptography and Information Security)

スポンサーリンク