Fault-resistant exponentiation algorithm

Abstract

A method for performing a m-ary right-to-left exponentiation using a base x, a secret exponent d and a modulus N, wherein m is a power of 2. A device having a processor and m+1 registers R[]−R[m] in at least one memory: initializes register R[] to h for a chosen value h, wherein the order of the value h is a divisor of m*(m−1)/2, register R[m] to xand the registers other than R[] and R[m] to the value h; updates register R[r] to R[r] times x, wherein r is the remainder of a division of d by (m−1) mod N; obtains a working exponent q that is the quotient of the division of d by (m−1); performs l iterations, starting at i=0, of: setting R[q] to R[q] times R[m] and raising R[m] to the power of m, where l is the length of q in base m and qis the i-th digit of the representation of q in base m and qis non-zero; verifies the correctness of the result by checking that R[m] equals the product of registers R[]-R[m−1] to the power of m−1; and outputs the product of R[j], where 1≦j≦m−1, only if the correctness is successfully verified.