基于流水线技术的并行模幂算法硬件实现

Hardware Implementation of Parallel Modular Exponentiation Algorithm Based on Pipelining Technique

针对R-L模幂算法并行硬件实现成本高的问题,提出一种流水线形式的模幂运算结构。采用流水线技术对模幂算法中Montgomery模乘运算进行硬件设计,并由此构建模幂运算结构,实现并行模幂运算,降低硬件成本。同时对模幂算法中预处理和后处理步骤进行优化,以减少迭代次数。Virtex-2系列现场可编程门阵列原型的实现结果表明,在保证并行模幂运算速度的前提下,该结构的硬件实现成本近似为传统并行结构的1/2,且数据吞吐率更高,可达14 Mb/s。

An efficient pipelined architecture is presented in this paper for solving the problem of high hardware cost of R-L modular exponentiation algorithm, which is formed of Montgomery modular multiplication built by using pipelining technique. The parallel calculation of algorithm can be executed and the hardware cost can be also reduced in the new architecture. Besides, two extra pre-processing and post-processing for converting an integer to its N-residue format in the conventional modular exponentiation algorithm are avoided to reduce the iteration time. The result shows that the new architecture can achieve high data throughput rate of more than 14 Mb/s on Xilinx Field Programmable Gata Array（FPGA） of Virtex-2 series when performs modular exponentiation, while occupy only about half hardware resources when compared with the conventional parallel architecture.