Research On Fast Modular Multiplication And Realization

A new partitioning Montgomery modular multiplication algorithm(PMMM) is proposed in this paper together with two hardware architectures proper for it to get high simultaneity and performance. And the architectures are liner systolic array that is refined from the one proposed by C.D. Walter[8].While Walter use (n + 1)(n + 2) PEs to accomplish Montgomery modularmultiplication, for the liner systolic array I ,we use n + 2 ones, it takes 3n/2 + 2 clockcycles to compute one Montgomery modular multiplication and the latency is n + 2 for multiplicands have n digits, the performance of our hardware device is 50% faster than the liner systolic array referred in [14]. For the liner systolic array II ,we provide methods to realize Modular multiplication and exponentiation with n/2 + 1 PEs, Of course, to keep balancebetween speed and hardware resource, we also provide four methods to realize Modular multiplication, for which we have also provided comprehensive analysis. We also design two hardware architecture of the Montgomery modular exponentiation. And two powerful threats of RSA security as timing attack and power attack are discussed and we introduce some methods of how to prevent these threaten.