| 摘要 |
An apparatus to calculate a remainder of Bc modulo n at high speed with minimum hardware resources, while securing safety of a key comprises: a first circuit to execute a process of calculating B (mod n) and holding the calculation result B1 and to repeat a process of shifting a holding value and calculating a value congruent to the shifted holding value modulo n and holding the calculation result; a first register for storing the B1 as an initial value; a second circuit to cumulate the calculation result of the first circuit when a value of a bit at a predetermined position of the first register is equal to 1; a second register to store 1 as an initial value; a C output circuit to output C; a third circuit to cumulate the calculation result of the first circuit when an output value from said C output circuit is equal to 1 and a value of a bit at a predetermined position of the second register is equal to 1. The bit at the predetermined position of the first register and the second register shifts from LSB to MSB of their stored values. When a process for MSB of a value stored by the first register ends, a value congruent to the cumulated result in the second circuit modulo n is set as the holding value and stored into the first register, the output of the C output circuit changes to a value shifted from LSB to MSB of the C, and when the output of the C output circuit is 1, a value congruent to the cumulated result in the third circuit modulo n is stored in the second register.
|
