Patent ID: 8700921
Filing Date: 2014-04-15
Classification: G06F,H04L

Abstract:
1. 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, the method comprising the steps, in a device having a processor and m+1 registers R[ 0 ]-R[m] in at least one memory, of: initializing register R[ initializing register R[m] to x initializing the registers other than R[ updating register R[r] to R[r] times x, wherein r is the remainder of a division of d by (m−1) mod N; obtaining a working exponent q that is the quotient of the division of d by (m−1); performing l iterations, starting at i=0, of: where l is the length of q in base m and q verifying the correctness of the result by checking that R[m] equals the product of registers R[ outputting the product of R[j]