Fast Multi-precision Multiplication for Public-Key Cryptography on Embedded Microprocessors

  • PDF / 494,816 Bytes
  • 19 Pages / 439.37 x 666.142 pts Page_size
  • 4 Downloads / 163 Views

DOWNLOAD

REPORT


Fast Multi-precision Multiplication for Public-Key Cryptography on Embedded Microprocessors∗ Michael Hutter Rambus Cryptography Research Division, 425 Market Street, 11th Floor, San Francisco, CA94105, United States Institute for Applied Information Processing and Communications (IAIK), Graz University of Technology, Inffeldgasse 16a, 8010Graz, Austria [email protected]

Erich Wenger Institute for Applied Information Processing and Communications (IAIK), Graz University of Technology, Inffeldgasse 16a, 8010Graz, Austria [email protected] Communicated by Mitsuru Matsui Received 3 October 2012 / Revised 21 September 2017

Abstract. Multi-precision multiplication is one of the most fundamental operations on microprocessors to allow public-key cryptography such as RSA and elliptic curve cryptography. In this paper, we present a novel multiplication technique that increases the performance of multiplication by sophisticated caching of operands. Our method significantly reduces the number of needed load instructions which is usually one of the most expensive operations on modern processors. We evaluate our new technique on an 8-b ATmega128 and a 32-b ARM7TDMI microcontroller and compare the results with existing solutions. For the ATmega128, our implementation needs only 2395 clock cycles for a 160-b multiplication. The number of required load instructions is reduced from 167 (needed for the best known hybrid multiplication) to only 80. On the ARM7TDMI, our implementation needs only 281 clock cycles as opposed to 357. For both platforms, the proposed technique outperforms related work by a factor of about 10–23%. We also show that the method scales very well even for larger integer sizes (required for RSA) and limited register sets. It fully complies with existing multiply–accumulate instructions that are integrated in most of the available processors. Keywords. Multi-precision arithmetic, Microprocessors, Elliptic curve cryptography, RSA, Embedded devices.

∗ This work was done while the authors were at Graz University of Technology (IAIK)

© International Association for Cryptologic Research 2020

M. Hutter, E. Wenger

1. Introduction Multiplication is one of the most important arithmetic operations in public-key cryptography. It engrosses most of the resources and execution time of modern microprocessors (up to 80% for elliptic curve cryptography (ECC) and RSA implementations [8]). In order to increase the performance of multiplication, most effort has been put by researchers and developers to reduce the number of instructions or minimize the amount of memory-access operations. Common multiplication methods are the schoolbook or Comba [5] technique which are widely used in practice. They require at least 2n 2 load instructions to process all operands and to calculate the necessary partial products. In 2004, Gura et al. [8] presented a new method that combines the advantages of these methods (hybrid multiplication). They reduced the number of load instructions to only 2n 2 /d where the parameter d