高速模乘法装置

摘要

本发明涉及一种高速的模乘法装置及计算方法，适用于密码技术，特别是公开密钥体制如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；其中的两个乘法电路由m个k+1位的小乘法单元组成，第一个乘法电路的每个单元输入相同数值的k比特数据A，与不同数值的k比特数据B，第二个乘法电路的每个单元输入相同数值的k+1比特数据商，与不同数值的k比特数据M；其中的所有的加法电路由两组m个k+1的小加法单元组成，第一组每个单元输出的进位存放到进位锁存器及输出的和存放到和锁存器，每个进位锁存器输出与其左邻的高一位和锁存器的输出经一个k+1端的与门检测，根据所说的与门的输出决定其左邻的高一位的进位锁存器的值，每个进位锁存器输出与其左邻，即高一位的和锁存器的输出于另一组中对应的加法单元相加，输出最后的和；这里的数据A、B、M和R的长度皆为二进制的n比特，采用高阶基数表示时，r为数的基，r＝2k，k是2的幂，k＞2，十六进制数时k＝4比特，其中m＝n/k，为n比特二进制数据的高价基数表示时的位数。