This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Großschädl, J. Search for Related Content Social Bookmarking                         What's this?

Architectural Support for Long Integer Modulo Arithmetic on Risc-Based Smart Cards

GRAZ UNIVERSITY OF TECHNOLOGY, INSTITUTE FOR APPLIED INFORMATION PROCESSING AND COMMUNICATIONS, INFFELDGASSE 16A, A-8010 GRAZ, AUSTRIA

Various algorithms for public-key cryptography, such as the Rivest-Shamir-Adleman or Diffie-Hellman algorithms, are based on long integer arithmetic operations, most notably modulo multiplication. To be adequate for long-term security, the modulus should have a length of at least 1024 bits. Long integer arithmetic is difficult to implement efficiently in software, particularly on smart cards due to their constrained resources and relatively slow clock frequency. In this paper we investigate the potential of application-specific instruction set extensions for cryptographic workloads such as long integer arithmetic. We define two special instructions that carry out computations of the form a xb + c + d, whereby a,b,c,d are single-precision words (unsigned integers). These additional instructions can be executed on an optimized multiply/accumulate unit and therefore they are simple to incorporate into common RISC architectures such as the MIPS32. The proposed extensions cause almost no speed or area penalty since no extra functional units are required. Experimental results indicate that the inner-loop operation of a multiple-precision multiplication can be accelerated by a factor of almost 2. We also estimate the execution time of a 1024-bit modulo exponentiation assuming that these special instructions were made available. The presented concept is an alternative solution to a crypto co-processor, especially for multi-application smart cards (e.g. Java cards) with an embedded 32-bit RISC core.

Key Words: Application-specific instruction set processor (ASIP) • processor specialization • public-key cryptography • Montgomery multiplication • coarsely integrated operand scanning (CIOS) • inner-loop operation

International Journal of High Performance Computing Applications, Vol. 17, No. 2, 135-146 (2003)
DOI: 10.1177/1094342003017002004


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?