Patent ID: 6968354

Claim:
A tamper-resistant modular multiplication method for decreasing the relationship between data processing and consumption current therefor in an information-processing device which includes an input/output port communicating with an external device, a memory device for storing both programs and data, a central processing unit executing the data processing in accordance with said programs, and a bus connecting among the input/output port, the memory device and the central processing unit, when calculating a modular multiplication, A*B*R^(−1) mod N, which appears during performing crypto-processing as the data processing, said method comprising the steps of: (1) selecting either of the following steps (2) and (3) at random; (2) calculating S 1 =A*B*R^(−1) mod N where B is a multiplier, A is a multiplicand, N is a product of large primes, and R is 2^(a bit length of a bit string of data) according to the Montgomery's method of calculating a modular multiplication for the data; (3) calculating S 2 ={sN+A*(−1)^f}*{tN+B*(−1)^g}R^(−1) mod N, (among arbitrary integers s, t, f, g, at least one is an integer excepting 0, and f, g are both 0 or 1); (4) repeating the above-mentioned steps (1), (2), (3) for each bit block consisting of the data, wherein finally when the step (2) is selected for a last bit block of the data, for a calculation result S 1 , T 1 =S 1 *R^(−1) mod Nis calculated to output T 1 , and when the step (3) is selected, for a calculation result S 2 , T 2 =S 2 *R^(−1) mod N is calculated to output N−T 2 ; and (5) using T 1 and N−T 2 as a calculation result of a modular multiplication, A*B*R^(−1) mod N.