RSA算法硬件实现的几个关键技术

尹绪昆,黄世中

(河北省科学院应用数学研究所,河北石家庄 050081)

RSA算法硬件实现的几个关键技术

尹绪昆,黄世中

(河北省科学院应用数学研究所,河北石家庄 050081)

介绍了RSA算法硬件实现的关键技术的基本思想。通过这些技术,可以极大增加算法的运行效率。

RSA;中国剩余定理;Montgomery;进位保留加法器;超前进位加法器

RSA算法是当前世界首选的公钥加密算法。目前在美国和欧洲的商务和政务一直使用。著名密码学家Steve Burnett和Stephen Paine在《security official guide to cryp tography》指出:自1977年以来,尽管世界各国的研究人员发明了许多公钥算法,但排在第一位的是仍然是RSA,其次是DH,然后是ECC。

大数模幂乘运算是很多公钥密码体制例如RSA的核心运算,它由一系列的模乘运算组成,大数的位数往往多达1024 bit或更多,运算量极大,是提高加解密运算速度的瓶颈。开发一种高速、实时并且安全的RSA密码系统,仍然是一个挑战。采用超大规模集成电路来实现RSA算法的运算,这种实现方法比普通的PC机用软件进行1024位数字签名要快上百倍。

下面介绍一下RSA硬件实现的关键技术。

1 Montgomery模乘法算法

模乘幂运算是由一系列的模乘法运算完成。在实现大整数的模乘法运算的所有算法中,Montgomery模乘法算法不依赖于大整数的比较和除法,是一种便于硬件实现的算法。

1985年Montgomery提出了一种模乘的算法,其设计思想是借助一个新的特殊剩余系数,将普通模乘转化为易计算的模乘。Montgomery算法是基于以下结论:

假设2n-1≤N≤2n,R=2n且N与R互素,A,B

这样算法中的整数模R约化和整数除以R运算只需要通过简单的截取或移位就能实现,从而避免了复杂耗时的除法运算。……