一种基于CSA加法器的Montgomery模幂乘硬件实现算法

提出了一种改进的Montgomery模乘和模幂算法,该算法采用5-to-2 CSA加法器来实现Montgomery模乘算法中的超长大数加法。目前使用CSA加法器的其他模乘算法在模乘结果输出时均需要用CPA加法器来处理CSA加法器的输出结果,而本文提出的算法使得模乘运算的输入输出操作数均可采用保留进位形式,避免了进行超长操作数的CPA加法这一耗时的操作,因此显著减少了模乘运算所需时钟周期,提高了数据处理的时间效率,并加快了RSA模幂运算的速度。

A Montgomery modular multiplication hardware implementation algorithm based on CSAs

A modified Montgomery multiplication and associated RSA modular exponentiation algorithm are(presented).The modified multiplier uses a 5-to-2 carry save adder to perform large word length additions.The previously reported Montgomery multiplication approaches,which use CSAs,require that a lengthy conven-(tional addition) is carried out to deal with the output of CSAs.But the modified algorithm makes the output and input data in carry save representation so as to avoid this costly and previously necessary conventional(addition).So it may gain higher time efficiency.