Recursive Double-Size Modular Multiplications without Extra Cost for Their Quotients

RSA Conference 2009 was held over five days from April 20th to 24th, 2009 in San Francisco in United States. This convention including more than 240 presentations and 350 exhibits is one of the largest international conferences related to a topic of information security. In a researchers session called cryptographer's track, there were only 31 papers, which were accepted out of 93 submissions in a competitive review process.

Hitachi, Ltd. Systems Development Laboratory introduced a presentation entitled "Recursive Double-Size Modular Multiplications without Extra Cost for Their Quotients" concerning techniques to increase the operand-size of cryptographic primitive operations (Photo 1). Thanks to our technique, 2048-bit RSA cryptosystem can be processed efficiently on the cryptographic devices which are equipped with the coprocessors for only 512 bits.

RSA has been the de-facto standard of public-key cryptosystem over the world and is critical for information security such as user and device authentications and secure channels. 1024-bit RSA has been commonly used to be secure, and an influential institute for cryptographic communities, NIST recommends 2048 bits for RSA key-length from 2010.

Lightweight devices such as smart cards are generally equipped with a special hardware accelerator to perform heavy RSA cryptosystem. The crypto-coprocessors, which are hard for modification, are restricted to their operand-size; therefore, the techniques to increase the operand-size with software assistant but without any hardware modification has been researched in this decade. However, previous techniques shared with an issue: the computational efficiency results in less than half in the case of more than the twice operand-size (Fig. 1).

This presentation introduced a new technique to increase the operand-size on coprocessors while keeping efficiency even in more than twice the operand-size. Thanks to our techniques, the cryptographic devices equipped with 512-bit crypto-coprocessors require only half the time as the previous approach to perform 2048-bit RSA cryptosystem (Fig. 2).

(By Masayuki Yoshino, Systems Development Laboratory)