Montgomery Multiplication with Twice the Bit-Length of Multipliers

Masayuki YOSHINO  Katsuyuki OKEYA  Camille VUILLAUME  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.1   pp.203-210
Publication Date: 2008/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.1.203
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Implementation
Montgomery multiplication,  RSA,  crypto-coprocessor,  smartcard,  

Full Text: PDF>>
Buy this Article

We present a novel approach for computing 2n-bit Montgomery multiplications with n-bit hardware Montgomery multipliers. Smartcards are usually equipped with such hardware Montgomery multipliers; however, due to progresses in factoring algorithms, the recommended bit length of public-key schemes such as RSA is steadily increasing, making the hardware quickly obsolete. Thanks to our double-size technique, one can re-use the existing hardware while keeping pace with the latest security requirements. Unlike the other double-size techniques which rely on classical n-bit modular multipliers, our idea is tailored to take advantage of n-bit Montgomery multipliers. Thus, our technique increases the perenniality of existing products without compromises in terms of security.