基为64的可扩展模乘法器设计*

2011-08-13刘建国管文强杨同杰杨晓辉

电子技术应用 2011年7期

关键词：设计

刘建国,管文强,杨同杰,杨晓辉

(1.解放军信息工程大学电子技术学院，河南郑州 450004；2.72850部队，山东济南 250031)

模乘运算在公钥密码系统中(例如RSA算法、椭圆曲线密码算法（ECC）以及 ElGamal算法等)有着广泛的应用。Montgomery模乘算法利用易于硬件实现的加法和移位操作来实现大整数的模乘运算，避免了复杂的除法运算，从而大大提高了模乘运算的效率[1]。

本文提出一种高速可扩展的Montgomery乘法器设计方案，该方案是在Tenca提出的Booth-8 Montgomery模乘法器的基础上，采用Booth-64编码进行改进，使速度平均提高了48%。同时对数据通路进行了优化，使得流水线数据通路的平均延迟大大降低。

1 MWR2kMM算法分析

Tenca等人在参考文献[2]中提出一种MWR2kMM算法，MWR2kMM算法如下：

其中，k表示基，X为模乘运算的乘数，Y是被乘数，M是模数。其中，操作数长度为N，部分积用为S表示，Y、M和S分成NW个BPW bit的字进行运算，xj表示 X的第 j bit，Sk(i)表示第 i个字的第 k 位，Ca、Cb表示进位，qYj、qMj分别是在计算部分积过程中Y和M的系数。

核心数据路径采用流水线组织结构，每一级之间用寄存器隔开。每个MMcell单元完成一轮外循环，每个时钟输入 Y、M、SS、SC的一个字参与运算，并把 Y、M和计算出来的SS、SC传递该下一级。为了能使数据路径可伸缩，加入了两个FIFO分别用来存储SS和SC。如图1所示，NS是流水线级数，由面积和时间需求来决定。