Digital signature is by far one of the most important cryptographic techniques used in the e-government and e-commerce applications. It provides authentication of senders or receivers and offers non-repudiation of transmission (senders cannot deny their digital signature in the signed documents and the document cannot be altered in transmission without being detected). This paper presents our implementation results of digital signature algorithms on IC cards by using byte-unit modular arithmetic algorithm method. We evaluated the performance of well-known ESIGN and RSA digital signature algorithms on the dedicated IC card chips and showed that ESIGN is more efficient than RSA.

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, 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 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.