| 摘要 |
A processor (120) in a device (100) performs fault-resistant exponentiation using an input x and a secret exponent d to obtain a result S, by using an a priori selected integer r and a chosen random element a ˆˆ {0, ..., r - 1} to form an extended base x is formed such that { x ^ ‰¡ x mod N x ^ ‰¡ 1 + a ‹ r mod �¢ r 2 In a generalization, for an a priori selected integer t = br 2 (where b is an integer) co-prime to a modulus N, the processor (110) has a modular inverse i N = N -1 mod t . The processor (120) generates (S2) the extended base by computing x = x + N · [ i N (1 + ar - x ) mod t ] and then computes (S3) an extended modulus N = Nt , computes (S4) S r = x d mod N , verifies (S5) if S r ‰¡ 1 + dar (mod r 2 ), and if and only if this is so, returns (S6) the result S = S r mod N via the interface (110). |
