一种可重构模乘器的硬件设计.pdf

第37卷第13期
计算机工程
2011年7月
Vol 37 No13
Computer Engineering
July 2011
?工程应用技术与实现。文章编号1003418201)-023803文标识码A
中图分类号:1P391
种可重构模乘器的硬件设计
杨同杰,彬,杨晓
(信息工程大学电子技术学院,郑州45000)
要:提出一种改进的基于剩余数系的 Montgomery模乘算法。该算法通过对相对固定的参数进行预计算,从而减少运算过程中模乘运
算的次数,与 Bajard J C提出的算法(EE计算机会刊,2004年第6期)相比减少300(2k+8)。同时基于改进算法提出数据长度可伸缩的硬
件模乘器结构设计,并在0.18 Hm SMIC工艺下进行综合。性能分析表明,该设计在运算速度上有明显的提高。
关词:剩余数系;模乘;可伸缩设计;硬件实现
Hardware Design of Scalable Modular Multiplier
YANG Tong-jie, DAI Zi-bin, YANG Xiao-hui
( nstitute of Electronic Technology, Information Engineering University, Zhen zhou 450004. China)
Absract This aper presents an improved Resiu Num s MR Mo me mula mullican algorithm which is optimized by
pre-computing the constant paamete mpae o e Baja EEE Transactions n mpue 004 N.6)al hm, the number of modula
multiplication is reduced by 300/(2k+)percent A hardware design of scalable modular multiplier is proposed, which is implemented on 0.18 m
SMIIC process. Result shows that the design has advanced performance
T Key words Residue Number S s m(RN) modular multiplication; salable design; hardware implementation
DO:10.39695js9n.10003428.201.13.078
概述
一个基=(,m2…,m)来解決这个问题,令M=Tam。
模乘运算作为最基本的有限域运算,广泛应用于公钥密
根据中国剩余定理,大整数A在2个基和の下可以
码体制当中。比如椭圆曲线密码的执行时间基本上取決于点唯一表示为(4,a2…4)和(4,ら…“,4),其中,4=?,=
乘运算的时间,而点乗运算又以模乗运算为核心,同样 RSA Amod my,d=?= A mod m'。同样,B在2个基和d下
中的模幂运算也以模乘运算为基础。因此,作为提高公钥密
码实现性能的关键,如何快速实现大整数的模乘运算逐渐成
也可以唯一表示为(,b2…,b)和(出,2…,)。定义运算
为一个热门课题,与此同时,如何提高模乘器的灵活性,使
8∈{+,-メ,那么A8B=(a,a28b2…a8b)。
其能够支持多种媺据长度下的运算,并且具备抗旁道攻击的
通过计算q=(a1xb)×(-N)'modm,可以得到Q在基の
能力,同样受到国内外研究者的广泛关注。
下的表示,然后将Q转换到基下,表示为(,92,…;q),
1985年, Montgomery PL提出了 Montgomery模乘算法,在基⊙下,R可以通过计算イ=(4xb1+4XN) X. mod my得
其利用完全剩余系的性质,避免了最复杂的除法运算,成为到,其中,M的逆元在基下是存在的,最后将R转换到
硬件实现最高效的模乘算法,因而得到广泛的研究与应用。基の下,得到R=ABM'modN。
文献[1对 Montgomery模乘算法进行了改进,按字进行扫描
RNS中相同基下的运算可以并行执行,因此,算法的复
运算,硬件设计上采用流水线缩短了运算时间,并且支持操杂度就取决于整数在基之间的转换,目前,实现一个整数在
作数长度可变的模乘运算。文献[]提出一种基4的2个基之闻的转换有2种方法:一种方法基于CRT( Chinese
Montgomery模乘算法及优化的硬件结构,将传统基2模乘运 Remainder Theorem);另一种方法基于MRS( Mixed Radix
算迭代次数减少近一半。文献[3将 Montgomery算法扩展到 System),具体描述见文献41。
剩余数系( Residue Number System,RNS),利用RNS并行无进
算法1优化 RNS Montgomery模乘算法
位的特性,提高了模乘器的运算效率,并具有低功耗、抗能
入(a1…,a)a1,d,…,g4)a
量攻击等优点。
,b,…b(4-,62…,),b
本文在文献3]提出的RNS模乘算法基础上,对算法进
满足ABgcd(N, M)=gcd( N, M)=gcd(M M)=
行优化,并提出一种可重构的模乘器硬件设计电路。
0<(k+2)N2算法分析与优化
预计算:T=(-NxM)mod
RNS模乘算法的基本思想与 Montgomery i模乘算法相同,
U, =(MXM.)mod m,
对于2个大整数A和B,模数N,存在整数Q,使得(AxB+QxM)
是M的整数倍,并且除以M可以通过乘以M的逆元实现
金项目:国家“863”计划基金资助项目(2008AAO1Z103)
那么R=(AxB+QxN)/ M mod N= ABM mod N。选取一组互作着介:杨同态(1987-),男,硕土研究生,主研方向:信息安全
素的整数⊙=(四,m2…;m)作为RNS的一个基,令M=,m,模乘器硬件设计;戴紫彬,教授、博士生导师;杨晓辉,博士研究生
根据RNS的性质,M的逆元在基Φ下不存在,因此引入另散蒋日期:2010-1206E-mail: carpente8126com
万方数据