高速模乘法方法及装置

摘要

本发明涉及一种高速的模乘法装置及计算方法，适用于密码技术，特别是公开密钥体制如RSA、DSS等对数据加密、解密和数字签名的运算。针对密码学的模乘法数据长度大的特点，采用几个比特并行的短乘法、加法、达到整个数据长度的乘、加运算的结果，避免长的进位延迟，大大提高计算的效率。计算可循环地一次一位、流水一次全部位，或者一次若干位，满足实用对速度-电路面积的各种要求。

主权项

1.一种模乘法装置，由三个输入寄存器，一个输出寄存器，乘法电路，加法电路组成，其特征在于：第一个输入寄存器存放k比特一位的数据A；第二个输入寄存器存放k比特一位的m位数据B；第三个输入寄存器存放k比特一位的m位数据M；一个输出寄存器存放计算出的残余数R；第一个乘法电路把所说的第一个输入寄存器的数据A与第二个输入寄存器的数据B相乘；第一个加法电路把所说的第一个乘法电路的多个部分积相加；第二个加法电路把所说残余数R乘以基数r后再与的所说的乘法电路的积相加，结果放入一个中间寄存器RD；一个计算电路，输入所说加法电路输出的高2K比特及第三个输入寄存器存放的数据M的最高一位，计算并输出k＋1比特的商；第二个乘法电路把所说计算电路输出的k＋1比特的商与第三个寄存器的数据M相乘，结果放到另一个中间寄存器RZ；第三个加法电路把所说的第二个乘法电路的多个部分积相加；一个减法电路把所说的两个中间寄存器RD和RZ的值相减，结果放到残余数寄存器；另外的加法电路，当残余数R小于零时，把残余数R和数据M相加至少一次，结果放到残余数寄存器RR。