Modular multiplication processing apparatus
View Patent ↗A modular multiplication processing apparatus is provided that can process modular multiplication of data exceeding a bit length which a coprocessor can process, by using the coprocessor based upon Montgomery multiplication In the modular multiplication processing apparatus, data to be subjected to modular multiplication is decomposed, and the decomposed data elements are transformed into a form suitable for Montgomery multiplication, respectively. Further, after respective data elements are transformed to have sizes that can be inputted into a coprocessor, Montgomery multiplication is repeatedly performed in the coprocessor. A remainder of Montgomery multiplication of an original bit length is restored from the obtained remainder.
1. A modular multiplication processing apparatus comprising:
a coprocessor for performing modular multiplication according to Montgomery multiplication,
wherein, in order to compute modular multiplication of data having a bit length which the coprocessor cannot calculate, the apparatus further comprises a first processing unit, which, using a calculated result of the Montgomery multiplication outputted by the coprocessor and a Montgomery constant defined by a calculation equation of the Montgomery multiplication, is configured to compute a quotient of the Montgomery multiplication and to output the quotient and a remainder of the Montgomery multiplication.
2. The modular multiplication processing apparatus according to claim 1 ,
wherein the quotient and the remainder of Montgomery multiplication computed in the first processing unit correspond to data Q and data R which satisfy an Equation of XY=QN+RM using data X, data Y, data N, and Montgomery constant M used in Montgomery multiplication.
3. The modular multiplication processing apparatus according to claim 2 ,
wherein processing in the first processing unit is processing for changing the data X and the data Y to be equal to or less than the maximum bit length of the coprocessor and computing the quotient Q and the remainder R of the Montgomery multiplication from a remainder of modular multiplication of the data X and the data Y by using the coprocessor.
4. The modular multiplication processing apparatus according to claim 1 , further comprising: a second processing unit which is configured to supply data to be computed to the first processing unit and to compute the modular multiplication by the Montgomery multiplication regarding data having a bit length which the coprocessor, performing the modular multiplication by the Montgomery multiplication, cannot process, by using the quotient and the remainder of the Montgomery multiplication computed by the first processing unit.
5. The modular multiplication processing apparatus according to claim 4 , further comprising: a fifth processing unit which instructs repetition of modular exponentiation of data having a bit length which the coprocessor cannot process in order for the second processing unit to compute modular exponentiation of data having a bit length which the coprocessor cannot process.
6. The modular multiplication processing apparatus according to claim 5 , further comprising: a sixth processing unit which transforms the quotient and the remainder of the Montgomery multiplication so that the quotient and the remainder of the Montgomery multiplication fall within a fixed bit length.
7. The modular multiplication processing apparatus according to claim 4 , further comprising: a third processing unit which transforms a format of data inputted into the modular multiplication processing apparatus to a format suitable for the Montgomery multiplication.
8. The modular multiplication processing apparatus according to claim 7 , further comprising: a fourth processing unit which inversely transforms a remainder of modular multiplication obtained by the second processing unit from the format suitable for the Montgomery multiplication to the format of the inputted data.
9. The modular multiplication processing apparatus according to claim 7 ,
wherein processing in the third processing unit is processing for calculating data A 1 and data A 0 which satisfy an Equation of A=A 1 Z+A 0 M using Montgomery constant M and an integer Z for the Montgomery multiplication regarding data A inputted to the modular multiplication processing apparatus.
10. The modular multiplication processing apparatus according to claim 9 ,
further comprising a fourth processing unit for calculating data A 1 ′ and data A 0 ′ which satisfy an Equation of A 1 ′2 n +A 0 ′=A 1 Z+A 0 M using the data A 1 and the data A 0 which have been transformed to the format suitable for the Montgomery multiplication and the Montgomery constant M and the integer Z used in the Montgomery multiplication.