VLSI array algorithms and architectures for RSA modularmultiplication

摘要

We present two novel iterative algorithms and their arraynstructures for integer modular multiplication. The algorithms arendesigned for Rivest-Shamir-Adelman (RSA) cryptography and are based onnthe familiar iterative Horner's rule, but use precalculated complementsnof the modulus. The problem of deciding which multiples of the modulusnto subtract in intermediate iteration stages has been simplified usingnsimple look-up of precalculated complement numbers, thus allowing anfiner-grain pipeline. Both algorithms use a carry save adder scheme withnmodule reduction performed on each intermediate partial product whichnresults in an output in carry-save format. Regularity and localnconnections make both algorithms suitable for high-performance arraynimplementation in FPGA's or deep submicron VLSI. The processing nodesnconsist of just one or two full adders and a simple multiplexor. Thenstored complement numbers need to be precalculated only when the modulusnis changed, thus not affecting the performance of the main computation.nIn both cases, there exists a bit-level systolic schedule, which meansnthe array can be fully pipelined for high performance and can alsoneasily be mapped to linear arrays for various space/time tradeoffs