计算机工程 ›› 2013, Vol. 39 ›› Issue (7): 16-20,25.doi: 10.3969/j.issn.1000-3428.2013.07.004

• 专栏 • 上一篇    下一篇

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

黄世伟,王云峰   

  1. (厦门大学电子工程系,福建 厦门 361005)
  • 收稿日期:2012-08-10 出版日期:2013-07-15 发布日期:2013-07-12
  • 作者简介:黄世伟(1987-),男,硕士研究生,主研方向:集成电路设计,密码学;王云峰,副教授、博士

Hardware Implementation of Parallel Modular Exponentiation Algorithm Based on Pipelining Technique

HUANG Shi-wei, WANG Yun-feng   

  1. (Department of Electronic Engineering, Xiamen University, Xiamen 361005, China)
  • Received:2012-08-10 Online:2013-07-15 Published:2013-07-12

摘要:

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

关键词: 蒙哥马利算法, 模乘, 模幂, RSA公钥密码体制, 流水线技术, 现场可编程门阵列原型

Abstract:

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.

Key words: Montgomery algorithm, modular multiplication, modular exponentiation, RSA public-key cryptosystem, pipelining technique, Field Programmable Gata Array(FPGA) prototype

中图分类号: