一种基于并行结构及编码的蒙哥马利模乘器

1.本发明属于集成电路硬件设计实现以及信息安全领域，具体涉及一种基于并行结构及编码的蒙哥马利模乘器。


背景技术：

2.密码学在信息安全领域起着举足轻重的作用。围绕物联网(iot)技术及其应用的嵌入式和片上系统(soc)形式的设备是当前技术发展的热点，其中各领域物联网设备之间敏感数据的转换是一个关键问题。对于基于公钥加密的安全方案，需要利用硬件模块来实现高吞吐量。
3.通常使用的公钥加密算法，如数字签名算法rsa和ecc，都是基于椭圆曲线密码体制。而基于椭圆曲线体制的运算存在计算量大、结构复杂，存在算法效率不高、资源消耗较多等问题。此外，这些操作通常是在大数上执行的，这使得它们非常耗时。
4.对于椭圆曲线密码体制的实现，依赖于椭圆曲线群上的点加、倍点和点乘的标量运算，而所有的标量运算都可以分解为在有限域上的基础运算。而其中模乘运算是影响整体运算的关键。
5.蒙哥马利模乘器作为一种应用广泛的模乘法器，是一种有效的大操作数模乘的高性能硬件实现技术。该算法使用移位的方式代替了代价高昂的除法，其硬件实现能够达到很好的资源利用率。现有的蒙哥马利模乘器主要采用两种实现方式，一种是基于固定位宽的乘法器和加法器结构，通过多次调用乘法加法和移位运算得到最终的运算结果；一种是基于加法器结构，用循环的加法代替乘法运算，通过加法和移位的方式多次循环迭代计算出最终的结果。该实现方式的硬件结构简单，资源占用少，实现的频率高，但其具有很高的周期延时。
6.对于现有的研究更多是致力于以加速计算时间作为设计目标，这使得硬件资源消耗非常高昂。然而，这种设计思想和当前iot技术及其应用的嵌入式系统形式的轻量化设备相冲突。因此，实现在较小资源消耗情况下的更优速度提升是当前实现轻量级加密系统的核心问题。
7.综上，模乘器作为密码模块中的核心单元，其计算效率和硬件开销能够直接影响到其整体信息安全方案的实现效率及性能优越性。而对于传统的蒙哥马利模乘器，现有的技术在实现轻量化的同时依旧面临着效率不够理想的问题。


技术实现要素：

8.本发明的目的在于克服现有的蒙哥马利模乘器在轻量化领域，在资源受限环境下，运算速度慢、难以并行、高运算周期延时等问题，提供一种2基两路并行的蒙哥马利模乘器，结合两路并行设计的特征，采用预计算以及对输入数据编码的方式来减少计算所涉及到的部分积，优化电路模块并行所带来的额外面积开销，并缩短关键路径。使得本设计能够更好的部署于轻量化应用场景。
9.本发明的目的是通过以下技术方案来实现的：一种基于并行结构及编码的蒙哥马利模乘器，包括预计算存储单元、控制单元和两组迭代计算模块，迭代计算模块包括输入选择控制单元、多路选择器、csa加法单元、输出移位单元、寄存器组；
10.其中预计算存储单元根据输入参数进行预计算以及相应数据的存储，用于后续迭代计算模块的多路输入数据选择和迭代计算；控制单元通过计数值控制预计算存储单元的使能、输出移位以及结合输入进行计算模块的多路输入的选择控制；迭代计算模块通过选择控制单元实现对输入数据的编码，完成预计算输出数据的多路选择，并将选择的数据通过csa加法单元累加，然后再经过输出移位单元，通过反复迭代的方式实现两路并行的迭代计算，最后将两路迭代计算的结果相加得到最终求得的模乘结果。
11.所述预计算存储单元的输入包括：来自外部的复位信号以及外部时钟信号；来自控制单元的控制信号，用于所述蒙哥马利模乘器在每次新计算前的预计算使能；外部发送的蒙哥马利模乘电路输入数据，包括乘数b、大素数的域参数m；
12.预计算存储单元的输出包括：发送给控制单元的预计算完成信号；发送给两路计算模块中多路选择器的8路选择数据，其值为乘数b和域参数m通过预计算得到的输出0、b、m、2m、3m、b+m、b+2m、b+3m；发送给两路选择控制单元的乘数b和域参数m的关键位数据b[1:0]和m[1]，用于多路选择器的选择控制。
[0013]
所述控制单元的输入包括：来自外部的复位信号和时钟信号；来自预计算存储单元的预计算完成信号，用于控制开始数据迭代计算和周期计数；外部发送的蒙哥马利模乘电路输入，乘数a；
[0014]
控制单元的输出包括：根据周期计数值i将输入信号的乘数a分为两路信号位的输出a
(2*i)
以及a
(2*i+1)
，将两路信号位的输出分别作为两个迭代计算模块的选择控制单元的输入；发送给迭代计算模块的输出移位单元的迭代周期计数值i以及对应的控制信号，用于控制输出移位单元，以及迭代的开始和结束。
[0015]
将两组迭代计算模块的编号分别记为0和1；
[0016]
所述迭代计算模块的输入包括：来自预计算存储单元以及控制单元的选择控制信号b[1:0]、m[1]、a
(2*i)
、a
(2*i+1)
以及来自内部寄存器y0、y1迭代反馈的选择控制信号y0[3:2]、y1[3:2]；来自预计算存储单元的多路选择器的8路数据输入；以及来自控制单元的迭代计数信号i和对应计数信号的控制信号；
[0017]
迭代计算模块的输出包括：基于并行结构及编码的蒙哥马利模乘器的最终计算结果p；
[0018]
迭代计算模块中的寄存器组包括：多路选择器的输出寄存器x0、x1，csa加法单元的输出寄存器y0、y1，输出移位单元的输出寄存器z0、z1；分别统一记为x、y、z；
[0019]
两组迭代计算模块的选择控制单元记为s0和s1，其输入控制信号为b[1:0]、m[1]、a＝a
(2*i)
or a
(2*i+1)
以及内部反馈信号y[3:2]＝y0[3:2]or y1[3:2]；输出基于编码的多路选择信号s[2:0]，其中s[2]＝a，选择信号s[2:0]，其中s[2]＝a，
[0020]
多路选择器的输入包括：输入预计算存储单元的8路数据输出，以及来自选择控制单元的选择信号s[2:0]；根据s[2:0]的数值为3'b000、3'b001、3'b010、3'b011、3'b100、3'b101、3'b110、3'b111分别选择输出数据x为0、2m、m、3m、b、b+2m、b+m、b+3m；
[0021]
csa加法单元的输入包括：寄存器x的数据以及寄存器z的数据，然后输出相加结果传递到寄存器y；
[0022]
输出移位单元的输入包括：控制单元的计数信号i及控制信号，以及寄存器y的数据；根据控制信号当处于最后一次迭代时候将数据y0向右移位》》1，y1向右移位》》2；其他迭代期间均将数据y向右移位》》2，然后输出给寄存器z；
[0023]
最后根据控制单元信号，若处于最后一次迭代，则寄存器z0和z1的相加结果p即为蒙哥马利模乘器的最终计算。
[0024]
本发明的有益效果是：本发明的模乘器通过添加额外的移位补偿运算，将部分积的循环迭代计算拆解成两组并行的计算，实现了2基蒙哥马利模乘的两路并行，实现将原本的2基蒙哥马利模乘的周期延时缩减为原本的1/2。结合所述两路并行设计的特征，通过对输入数据进行重新编码，并对所添加的额外移位补偿运算和部分积进行预计算，将原本的三次加法转换成了一个多路选择和一次加法，优化了对电路模块并行所带来的额外面积开销，并缩短了整体运算的关键路径。使得所述的发明电路在实现更少周期延时的同时能够缩短每个周期的关键路径延时，并且只带来了较少的额外面积开销。使得本设计能够更好地部署于轻量化应用场景。
附图说明
[0025]
图1为本发明基于并行结构及编码的蒙哥马利模乘器的结构示意图；
[0026]
图2为本发明的选择控制单元示意图。
具体实施方式
[0027]
下面结合附图进一步说明本发明的技术方案。
[0028]
如图1所示，本发明的一种基于并行结构及编码的蒙哥马利模乘器，包括预计算存储单元1、控制单元2、两组迭代计算模块3和4，迭代计算模块3包括输入选择控制单元6(s0)、多路选择器mux0 7、csa加法单元csa0 9、输出移位单元11、寄存器组；迭代计算模块4包括输入选择控制单元5(s1)、多路选择器mux0 8、csa加法单元csa0 10、输出移位单元12、寄存器组
[0029]
其中预计算存储单元根据输入参数进行预计算以及相应数据的存储，用于后续迭代计算模块的多路输入数据选择和迭代计算；控制单元通过计数值控制预计算存储单元的使能、输出移位以及结合输入进行计算模块的多路输入的选择控制；迭代计算模块通过选择控制单元实现对输入数据的编码，完成预计算输出数据的多路选择，并将选择的数据通过csa加法单元累加，然后再经过输出移位单元，通过反复迭代的方式实现两路并行的迭代计算，最后通过加法单元13将两路迭代计算的结果相加得到最终求得的模乘结果。
[0030]
所述预计算存储单元1的输入包括：来自外部的复位信号以及外部时钟信号；来自控制单元2的控制信号en，用于所述蒙哥马利模乘器在每次新计算前的预计算使能；外部发送的蒙哥马利模乘电路输入数据，包括乘数b、大素数的域参数m；
[0031]
预计算存储单元1的输出包括：发送给控制单元2的预计算完成信号；发送给两路计算模块中多路选择器7和8的8路选择数据，其值为乘数b和域参数m通过预计算得到的输出0、b、m、2m、3m、b+m、b+2m、b+3m；发送给两路选择控制单元5和6的乘数b和域参数m的关键
位数据b[1:0]和m[1]，用于多路选择器的选择控制。
[0032]
所述控制单元2的输入包括：来自外部的复位信号和时钟信号；来自预计算存储单元1的预计算完成信号done，用于控制开始数据迭代计算和周期计数；外部发送的蒙哥马利模乘电路输入，乘数a；
[0033]
控制单元2的输出包括：根据周期计数值i将输入信号的乘数a分为两路信号位的输出a
(2*i)
以及a
(2*i+1)
，将两路信号位的输出分别作为两个迭代计算模块的选择控制单元5和6的输入；发送给迭代计算模块的输出移位单元11和12的迭代周期计数值i以及对应的控制信号，用于控制输出移位单元，以及迭代的开始和结束。
[0034]
将两组迭代计算模块的编号分别记为0和1；
[0035]
所述迭代计算模块3和4的输入包括：来自预计算存储单元1以及控制单元2的选择控制信号b[1:0]、m[1]、a
(2*i)
、a
(2*i+1)
以及来自内部寄存器y0、y1迭代反馈的选择控制信号y0[3:2]、y1[3:2]；来自预计算存储单元1的多路选择器7和8的8路数据输入；以及来自控制单元2的迭代计数信号i和对应计数信号的控制信号；
[0036]
迭代计算模块的输出包括：基于并行结构及编码的蒙哥马利模乘器的最终计算结果p；
[0037]
迭代计算模块中的寄存器组包括：多路选择器7和8的输出寄存器x0、x1，csa加法单元9和10的输出寄存器y0、y1，输出移位单元11和12的输出寄存器z0、z1；分别统一记为x、y、z；
[0038]
两组迭代计算模块的选择控制单元记为s0和s1，其输入控制信号为b[1:0](b[1]和b[0])、m[1]、a＝a
(2*i)
ora
(2*i+1)
以及内部反馈信号y[3:2]＝y0[3:2]ory1[3:2](y[3]、y[2])；输出基于编码的多路选择信号s[2:0]，其中s[2]＝a，[2])；输出基于编码的多路选择信号s[2:0]，其中s[2]＝a，其详细电路结构图如图2所示；
[0039]
多路选择器的输入包括：输入预计算存储单元的8路数据输出，以及来自选择控制单元的选择信号s[2:0]；根据s[2:0]的数值为3'b000、3'b001、3'b010、3'b011、3'b100、3'b101、3'b110、3'b111分别选择输出数据x为0、2m、m、3m、b、b+2m、b+m、b+3m；
[0040]
csa加法单元的输入包括：寄存器x的数据以及寄存器z的数据，然后输出相加结果传递到寄存器y；
[0041]
输出移位单元的输入包括：控制单元的计数信号i及控制信号，以及寄存器y的数据；根据控制信号当处于最后一次迭代时候将数据y0向右移位》》1，y1向右移位》》2；其他迭代期间均将数据y向右移位》》2，然后输出给寄存器z；
[0042]
最后根据控制单元信号，若处于最后一次迭代，则寄存器z0和z1的相加结果p即为蒙哥马利模乘器的最终计算。
[0043]
结合上述说明，本发明的蒙哥马利模乘器具体运算过程如下：
[0044]
输入：a＝{a
n-1
,a
n-2
,,a1,a0}，
[0045]
b＝{b
n-1
,b
n-2
,b,1b,0，
[0046]
m＝{m
n-1
,m
n-2
,m,1m,0，radix 2，其中0＜a,b＜m，gcd(m,2)＝1
[0047]
输出：p＝a
·b·
2-n
mod m
[0048]
1、若rst＝1，寄存器x、y、z以及预计算存储单元1置0；
[0049]
2、若预计算使能信号en＝1，计算存储数据2m、3m、b+m、b+2m、b+3m。
[0050]
迭代计算模块：
[0051]
3、
[0052]
4、计算s0和s1(对应s0,a＝a
(2*i+1)
,y＝y0，对应s1,a＝a
(2*i)
,y＝y1)；
[0053]
s[2:0]＝{s2,s1,s0}；
[0054]
s2＝a；
[0055]
5、如果s0/s1＝3'b000、3'b001、3'b010、3'b011、3'b100、3'b101、3'b110、3'b111；
[0056]
x0/x1＝0、2m、m、3m、b、b+2m、b+m、b+3m；
[0057]
6、y0＝x0+z0，y1＝x1+z1；
[0058]
7、z1＝y1＞＞2
[0059]
else z0＝y0＞＞2，z1＝y1＞＞2
[0060]
8、end for
[0061]
9、p＝z0+z1
[0062]
本发明的模乘器通过设计了一种2基两路并行的方式来减少蒙哥马利模乘的周期延时。同时结合所述两路并行设计的特征，采用预计算以及对输入数据编码的方式来减少计算所涉及到的部分积，优化电路模块并行所带来的额外面积开销，并缩短关键路径。使得本设计能够更好的部署于轻量化应用场景。
[0063]
本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的原理，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。

技术特征：
1.一种基于并行结构及编码的蒙哥马利模乘器，其特征在于，包括预计算存储单元、控制单元和两组迭代计算模块，迭代计算模块包括输入选择控制单元、多路选择器、csa加法单元、输出移位单元、寄存器组；其中预计算存储单元根据输入参数进行预计算以及相应数据的存储，用于后续迭代计算模块的多路输入数据选择和迭代计算；控制单元通过计数值控制预计算存储单元的使能、输出移位以及结合输入进行计算模块的多路输入的选择控制；迭代计算模块通过选择控制单元实现对输入数据的编码，完成预计算输出数据的多路选择，并将选择的数据通过csa加法单元累加，然后再经过输出移位单元，通过反复迭代的方式实现两路并行的迭代计算，最后将两路迭代计算的结果相加得到最终求得的模乘结果。2.根据权利要求1所述的基于并行结构及编码的蒙哥马利模乘器，其特征在于，所述预计算存储单元的输入包括：来自外部的复位信号以及外部时钟信号；来自控制单元的控制信号，用于所述蒙哥马利模乘器在每次新计算前的预计算使能；外部发送的蒙哥马利模乘电路输入数据，包括乘数b、大素数的域参数m；预计算存储单元的输出包括：发送给控制单元的预计算完成信号；发送给两路计算模块中多路选择器的8路选择数据，其值为乘数b和域参数m通过预计算得到的输出0、b、m、2m、3m、b+m、b+2m、b+3m；发送给两路选择控制单元的乘数b和域参数m的关键位数据b[1:0]和m[1]，用于多路选择器的选择控制。3.根据权利要求1所述的基于并行结构及编码的蒙哥马利模乘器，其特征在于，所述控制单元的输入包括：来自外部的复位信号和时钟信号；来自预计算存储单元的预计算完成信号，用于控制开始数据迭代计算和周期计数；外部发送的蒙哥马利模乘电路输入，乘数a；控制单元的输出包括：根据周期计数值i将输入信号的乘数a分为两路信号位的输出a
(2*i)
以及a
(2*i+1)
，将两路信号位的输出分别作为两个迭代计算模块的选择控制单元的输入；发送给迭代计算模块的输出移位单元的迭代周期计数值i以及对应的控制信号，用于控制输出移位单元，以及迭代的开始和结束。4.根据权利要求1所述的基于并行结构及编码的蒙哥马利模乘器，其特征在于，将两组迭代计算模块的编号分别记为0和1；所述迭代计算模块的输入包括：来自预计算存储单元以及控制单元的选择控制信号b[1:0]、m[1]、a
(2*i)
、a
(2*i+1)
以及来自内部寄存器y0、y1迭代反馈的选择控制信号y0[3:2]、y1[3:2]；来自预计算存储单元的多路选择器的8路数据输入；以及来自控制单元的迭代计数信号i和对应计数信号的控制信号；迭代计算模块的输出包括：基于并行结构及编码的蒙哥马利模乘器的最终计算结果p；迭代计算模块中的寄存器组包括：多路选择器的输出寄存器x0、x1，csa加法单元的输出寄存器y0、y1，输出移位单元的输出寄存器z0、z1；分别统一记为x、y、z；两组迭代计算模块的选择控制单元记为s0和s1，其输入控制信号为b[1:0]、m[1]、a＝a
(2*i) or a
(2*i+1)
以及内部反馈信号y[3:2]＝y0[3:2] or y1[3:2]；输出基于编码的多路选择信号s[2:0]，其中s[2]＝a，择信号s[2:0]，其中s[2]＝a，多路选择器的输入包括：输入预计算存储单元的8路数据输出，以及来自选择控制单元
的选择信号s[2:0]；根据s[2:0]的数值为3'b000、3'b001、3'b010、3'b011、3'b100、3'b101、3'b110、3'b111分别选择输出数据x为0、2m、m、3m、b、b+2m、b+m、b+3m；csa加法单元的输入包括：寄存器x的数据以及寄存器z的数据，然后输出相加结果传递到寄存器y；输出移位单元的输入包括：控制单元的计数信号i及控制信号，以及寄存器y的数据；根据控制信号当处于最后一次迭代时候将数据y0向右移位>>1，y1向右移位>>2；其他迭代期间均将数据y向右移位>>2，然后输出给寄存器z；最后根据控制单元信号，若处于最后一次迭代，则寄存器z0和z1的相加结果p即为蒙哥马利模乘器的最终计算。

技术总结
本发明公开了一种基于并行结构及编码的蒙哥马利模乘器，包括预计算存储单元、控制单元和两组迭代计算模块，迭代计算模块包括输入选择控制单元、多路选择器、CSA加法单元、输出移位单元、寄存器组。本发明的模乘器通过添加额外的移位补偿运算，将部分积的循环迭代计算拆解成两组并行的计算，实现了2基蒙哥马利模乘的两路并行，将原本的2基蒙哥马利模乘的周期延时缩减为原本的1/2。结合两路并行设计的特征，通过对输入数据进行重新编码，并对所添加的额外移位补偿运算和部分积进行预计算，将原本的三次加法转换成了一个多路选择和一次加法，优化了对电路模块并行所带来的额外面积开销，缩短了整体运算的关键路径，能够更好地部署于轻量化应用场景。部署于轻量化应用场景。部署于轻量化应用场景。


技术研发人员：李磊 胡世纪
受保护的技术使用者：电子科技大学
技术研发日：2023.05.16
技术公布日：2023/10/19