Modular-Exponentiation Timing with MAXQ30 Microcontrollers

Introduction

Modular exponentiation is used in several cryptographic algorithms, notably the RSA public key algorithm and the elliptic curve digital signature algorithm (ECDSA). It is also used to discover prime numbers and to find modular inverses. This application note describes what modular exponentiation is, provides an overview of the MAA, and lists typical times to execute various sized exponentiations.

The MAXQ30 architecture uses a reduced instruction set computer (RISC) where all instructions are 16 bits in length and execute in a single cycle. The 32-bit arithmetic and logic unit (ALU) works with 32-bit registers and values while connected to a 32-bit bus.

Modular Exponentiation

Modular exponentiation is described by the equation:

result = base^exponent mod modulus.

For example: 9 = 7² mod 10.

In this example, 9 is the result, 7 is the base, 2 is the exponent, and 10 is the modulus. In this case, since the modulus 10 is 4 bits long in binary, the size is four.

The MAA performs modular addition, subtraction, multiplication, squaring, squaring followed by a multiplication, and modular exponentiation. All these operations can be done with a modulus size up to 2048 bits in length.

The MAA operates from the cryptographic clock. This clock may be sourced from the system clock, which is determined by the external crystal frequency or run from the cryptographic ring. The internal cryptographic ring for the DeepCover^® Secure Microcontrollers (MAXQ1050 and MAXQ1850) runs from 55MHz to 75MHz with a typical speed of 65MHz. The internal cryptographic ring for the DeepCover Secure Microcontroller (MAXQ1103) can run at a speed from 45MHz to 65MHz with a typical speed of 55MHz.

The MAA on the MAXQ1050 and MAXQ1850 are identical, so the timings when running from the cryptographic ring are the same. The MAA on these two parts use a 32 × 16-bit multiplier with a 32-bit data bus. The implementation of the MAA on the MAXQ1103 has a 64 × 32-bit multiplier and has a 64-bit data bus. The MAA on the MAXQ1103 executes faster at the expense of using more silicon area.

Power analysis attacks such as simple power analysis (SPA) and differential power analysis (DPA) might be able to extract exponent information when running with optimization enabled. It is recommended that nonoptimized calculations always be done with private keys.

The data presented in Tables 1 to 3 are typical run times. Each entry is the average time of 400 calculations using uniform random numbers for the base, modulus, and exponent, with the most significant bit set in the modulus. In the case of public key calculations, the hex value of 0x10001 was used instead of a random number. This is a typical value for the public exponent in RSA. The time calculated is from when the operation starts until it is finished. The time to load values into memory for the calculations is not included.

A significant speed improvement in modular-exponential operations can be realized by employing the Chinese remainder theorem (CRT). Using the CRT requires two smaller modular-exponentiation operations rather than one large one. Instead of performing a modular-exponential calculation on the large modulus, modular-exponential calculations are done on the two factors of the modulus. For example, in RSA, the modulus is the product of two prime numbers, p and q. If p and q are both 1024 bits, doing two modular-exponential operations on these would take approximately 165ms using the MAXQ1103. Without the CRT, a 2048-bit modular-exponential operation is required and will take approximately 557ms. The CRT algorithm requires additional calculations which will increase the total time, but it is expected to be better than twice as fast.

The data in the left side of Table 1 is the most interesting. These are the typical elapsed times to perform a modular exponentiation when running from the cryptographic ring in a nonoptimized mode. Typical elapsed times using optimization and a public key are in the right two columns.

Table 2 lists the typical times to perform a modular exponentiation with a private key data in both optimized and nonoptimized modes. Table 3 lists the typical times to perform a modular exponentiation with a public key in optimized and nonoptimized modes for the three parts.