A modular operation device for handling a Montgomery multiplication in a public-key cryptographic algorithm, comprising:
- a storage device configured to store a plurality of multiplicand words AW0-AWe, a plurality of multiplier words BW0-BWe, a plurality of modulus words PW0-PWe, a first plurality of carry results Sc0-Sce, and a first plurality of sum results Ss0-Sse, wherein e≥1;
- a controller, coupled to the storage device, configured to:
- divide a multiplicand A into the plurality of multiplicand words AW0-AWe, a multiplier B into the plurality of multiplier words BW0-BWe, and a modulus P into the plurality of modulus words PW0-PWe;
- and
- initialize the first plurality of carry results Sc0-Sce and the first plurality of sum results Ss0-Sse to 0;
- a first plurality of K processing elements PE0-PEK−1, coupled to the controller and the storage device, configured to compute a first plurality of updated carry results and a first plurality of updated sum results, wherein K≥2, and each processing element PEj is configured to, in an i-th outer iteration and a u-th inner iteration where 0≤u<┌(e+1)/K▴:
- perform a first read operation to read AWuK+j, BWi, ScuK+j, and SsuK+i+1 from the storage device;
- perform a first process operation to compute an updated carry result McuK+j and an updated sum result MsuK+j in parallel according to AWuK+j×BWi+ScuK+j+SsuK+j+1;
- and
- perform a first write operation to store McuK+j and MsuK+j in the storage device,
- wherein a (u+1)-th first read operation, a u-th first process operation, and a (u−1)-th first write operation are performed in parallel;
- wherein one of the first plurality of K processing elements is further configured to compute an extra quotient qi according to a least significant result Ms0 of the first plurality of updated sum results and an inverse word in the i-th outer iteration and a u-th inner iteration, wherein the inverse word is a remainder of an inverse of a least significant word PW0 of the plurality of modulus words divided by a radix;
- a second plurality of K processing elements, coupled to the controller and the storage device, configured to compute a second plurality of updated carry results and a second plurality of updated sum results, wherein each of the second plurality of K processing elements is configured to, in the i-th outer iteration and a v-th inner iteration where 0≤v<┌(e+1)/K┐:
- perform a second read operation to read PWvK+j, and MsvK+j from the storage device;
- perform a second process operation to compute an updated carry result ScvK+j and an updated sum result SsvK+j in parallel according to PWvK+j×qi+McvK+j−1+MsvK+j;
- and
- perform a second write operation to store ScvK+j and SsvK+j in the storage device,
- wherein a (v+1)-th second read operation, a v-th second process operation, and a (v−1)-th second write operation are performed in parallel;
- wherein the controller is further configured to:
- determine whether ┌(e+1)/K▴ inner iterations are completed for the first plurality of K processing elements, and if not, continue performing the first read, process, and write operations;
- determine whether ┌(e+1)/K┐ inner iterations are completed for the second plurality of K processing elements, and if not, continue performing the second read, process, and write operations;
- and
- determine whether (e+1) outer iterations are completed, and if not, continue performing the operations of the first and second plurality of K processing elements;
- and
- a reduction element, coupled to the controller and the storage device, configured to compute a resulting remainder S according to the second plurality of updated carry results Sc0-Sce and the second plurality of updated sum results Ss0-Sse after completion of the (e+1) outer iterations;
- wherein the controller, the first plurality of K processing elements PE0-PEK−1, the second plurality of K processing elements, and the reduction element are implemented as part of an application specific integrated circuit;
- wherein in the public-key cryptographic algorithm, the modular operation device receives the modulus P, a key, and a cryptographic data as inputs for a cryptographic operation, and the modular operation device performs the Montgomery multiplication using the modulus P, the key, and the cryptographic data, and generating the resulting remainder as a cryptographic output of the cryptographic operation.