Modulo Exponentiation Timing with the DS5250 Microcontroller

Introduction

Modulo exponentiation is used in many cryptographic algorithms. Anyone implementing one of these algorithms must know approximately how long the operation will take. This application note describes how modulo exponentiation is done on the DS5250 high-speed, secure microcontroller. It lists typical times to run various expressions, and describes the code flow to obtain the timings.

Basic MAA Operation

Modulo exponentiation is the function, (base^exponent) mod modulus. For example, (2⁹ mod 10) is equal to (512 mod 10) which is equal to 2. The answer is always a number between 0 and modulus-1.

The MAA (Modulo Arithmetic Accelerator) on the DS5250 always uses MAA register "a" for the base, MAA register "e" for the exponent, and MAA register "m" for the modulus. The MAA register "b" is initialized to 1 before the operation, and contains the result after the operation. The MAA Size registers (MAS1 and MAS0 at A2h and A1h) tell the MAA the maximum number of bits in these registers. The m register must have the highest bit set to work. The size register can have values from 2 to 4096.

The Modular Arithmetic Accelerator Control register (MACT at A3h) contains the bits used to control the operation of the MAA. The Calculation Configuration bits (CLC1 and CLC0 of the MACT register) determine which of four operations is to be executed. The operations can be modulo multiply; modulo square; modulo square and multiply; and the operation discussed here, modulo exponentiation.

Modulo exponentiation is calculated with repeated squares and multiplies. The square operation is done for every bit in the exponent. The multiply operation only has to be done when the corresponding bit in the exponent is set. Figure 1 gives the pseudo code for the modulo exponentiation operation. The Optimized Calculation Control bit (OCALC of the MACT register) determines if a multiply operation is done for every bit. When the OCALC bit is enabled, every time a 1 bit is found in the exponent, a multiply operation is done. When the OCALC bit is disabled, a multiply is done for every bit, zero or 1, in the exponent, thus giving us similar time calculations for any specific modulus size. All private key calculations should be done with OCALC=0 (disabled) along with running from the ring (RNGSEL=1) to avoid timing attacks.

The MAA can run using the system clock, or it can be run from the ring. The MAA runs at half the system clock speed when this option is selected. Thus, for a 22.1MHz crystal, the MAA will run at 10.05MHz. It will take the same time to execute the same values when running from the system clock. When the MAA is run from the ring, the execution time can vary depending on voltage, temperature, and the inherent speed of the ring which will vary from part to part. The MAA runs at the full speed of the ring. In the typical data presented in Tables 1 and 2, the ring is running near 22Mhz. Ring Oscillator Select (RNGSEL) of the MACT register controls which clock is used for the modulo exponentiation operation.

Typical MAA Timings

The timings that have been collected are broken into two groups. The first group looks at large numbers in each of the modulus, base and exponent. The second group looks at the timing when using a small exponent that only has 2 bits set, specifically, the value 10001h. This number is sometimes used as a public exponent in the RSA algorithm. In each group, there are two halves. The first half has optimization enabled (OCALC=1) and the second half has optimization disabled. Within each half, typical timing values are listed for different clock sources. These timings are all displayed in millisecond (ms) units.

The typical timing values given in the table are the average of ten different calculations using random values in each of the registers. The modulus is random up to the most significant digit, which is always a 1. In general, about half the bits are set in each of the parameters.

The timing of each calculation was measured using Timer 0 as a divide-by-12 clock. When the 16-bit Timer 0 rolls over, an interrupt occurs and a 1 is added to the six external count bytes. At the end of the calculation the timer is stopped, and the external count bytes and the 16-bit timer count are displayed as a 64-bit number that gives the length of the calculation. A 22.1MHz oscillator will have a 543ns resolution per timer tic. The resolution is 1.085µs at 11.0592MHz. Figure 2 has the pseudo code for timing a MAA calculation.