基于改进的蒙哥马利算法的模乘器

摘要

本发明属于计算机加/解密技术领域，其特征在于：该模乘器用了两个7级流水的64位乘法器来分解操作数以提高系统的时钟频率，用预计算单元把在外部状态机控制下提前输入的数据分期送入乘法器，所属分期是按照计算操作数中前一位值的那个阶段中存在的三个等待计算结果的时钟周期来划分的。从i＝0时计算第一阶段开始，重复上述步骤，直到操作数中个位数全部模乘结束为止。从而解决了流水线停顿的问题，提高了系统的并行性，减少了所需的时钟数。所述模乘器位长233位，基于SMIC 0.18um最坏的工艺，关键路径最大时延3.8ns，面积2mm²，一次模乘需要110个时钟周期。与现有其它结构相比，具有面积小速度快的特点，适用于ECC密码体制和RSA密码体制。

主权项

1.基于改进的蒙哥马利算法的模乘器，其特征在于，该模乘器是一种在外部状态机的控制下对输入数据按改进的蒙哥马利算法操作的，位长233位的模乘器，该算法把位长很长的大数分解为相对较小的数来分别进行计算，即把n位2进制的被乘数A视为s位的r进制数，表示为：A＝as-1as-2…a1a0，ai为r进制数，把n位2进制的乘数B视为s位的r进制数，表示为：B＝bs-1bs-2…b1b0，bi为r进制数，把n位2进制的模N视为s位的r进制数，表示为：N＝ns-1ns-2…n1n0，ni为r进制数，其中s＝4，r＝264，i＝0，1，2，3，所述基于改进的蒙哥马利算法的模乘器含有：输入单元、中间单元、预计算单元、输出单元和一个多路选择器，其中：输入单元，含有：第一采用7级流水的64位乘法器，输入数据为a和b；第二采用7级流水的64位乘法器，输入数据为n和中间结果m：第一128位寄存器，该寄存器的输入端与所述的第一采用7级流水的64位乘法器的输出端相连；第二128位寄存器，该寄存器的输入端与所述的第二采用7级流水的64位乘法器的输出端相连；中间单元，含有：一个128位加法器，该加法器的两个输入端分别与所述第一128位寄存器和第二128位寄存器的输出端相连；一个129位寄存器，该寄存器的输入端与所述128位加法器的输出端相连；预计算单元，含有：133位加法器I、133位加法器II、133位加法器III，所述各133位加法器的一个输入端分别和所述129位寄存器的输出端相连；133位寄存器I、133位寄存器II、133位寄存器III，所述各133位寄存器的输入端分别依次与所对应133位加法器的输出端相连，所述各133位寄存器的输出端分别依次与所述个133位加法器的另一个输入端相连，多路选择器，该选择器的各输入端分别同时与所述个133位寄存器的输出端相连；输出单元，含有：一个133位加法器IV，该加法器IV的两个输入端分别于所述多路选择器、129位寄存器的输出端相连；一个133位寄存器IV，该寄存器IV的输入端与所述133位加法器的输出端相连，该寄存器的输出端在输出数据的同时又与所述第二采用7级流水的64位乘法器的输入中间结果m用的输入端相连；在外部状态机的控制下，在i＝0的循环内，所述第一采用7级流水的64位乘法器被依次按以下步骤输入数据：在第一次等待计算结果S＝a0b0的时钟周期内，被提前输入i＝1时循环内用的与前一级运算结果无关的包括a0、b1、a1、b0在内的数据，产生相应的部分积a0b1、a1b0，在外部状态机的控制下送入所述预计算单元累加并寄存在寄存器I中；在第二次等待计算结果m1＝sn’0时钟周期内，被提前输入i＝2时的循环内的数据a0、b2、a1、b1、a2、b0，产生相应的部分积a0b2、a1b1、a2b0，在外部状态机的控制下送入预计算单元累加并寄存在寄存器II中，n’0为只与N有关常数且满足n0n0’modr＝1；在第三次等待计算结果m1n0时钟周期内，被提前输入i＝2时的循环内的数据a0、b3、a1、b2、a2、b1、a3、b0，产生相应的部分积a0b3、a1b2、a2b1、a3b0，在外部状态机的控制下送入预计算单元累加并寄存在寄存器III中；在所述外部状态机的控制下，在i＝1、i＝2、i＝3的循环内，同样按i＝0循环内所属的步骤依次进行；所述的129位寄存器和多路选择器，按照i＝0，1，2，3各个不同的循环周期，把所寄存的各相应数据送往所述133位加法器IV累加后送往所述133位寄存器IV寄存，该寄存器IV把中间结果m送往第二采用7级流水的64位加法器，直到所有各循环结束，输出最终运算结果，以上所述的基于改进的蒙哥马利模乘器是在数字集成电路上实现的。