A Modular-Multiplication Algorithm Using Lookahead Determination (Special Section on Cryptography and Information Security)

概要

論文の詳細を見る
This paper presents an efficient multi-precision modular-multiplication algorithm which minimizes the calculation RAM space required when implementing public-key schemes with software on general-purpose computers including smart cards and personal computers. Many modular-multiplication algorithms cannot be efficiently realized on small systems due to their high RAM consumption. The Montgomery algorithm,^<(20),(6)> which can rapidly perform modular multiplication, has received a lot of attention. Unfortunately, the Montgomery algorithm is difficult to implement, especially in smart cards which have extremely limited RAM space. Furthermore, when the modulus of modular multiplication is frequently changed, or when the number of permissible repeated modular multiplications is small, pre-and post-processing operations such as conversion from / to the Montgomery space become wasteful. The proposed algorithm avoids these problems because it requires only half the RAM space and no pre-and post-processing operations. The algorithm is a radical extension to the approximation methods^<(2),(4),(5),(19),(21),(22),(28)> that use the most significant bits and our newly proposed lookahead determination method. This paper gives a proof of the completeness of this method, describes implementation results using a smart card, introduces a theory supported by the results, and considers the optimal technique to enhance the speed of this method.
社団法人電子情報通信学会の論文
1993-01-25

A Modular-Multiplication Algorithm Using Lookahead Determination (Special Section on Cryptography and Information Security)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク