1.本发明涉及密码学中格密码算法领域，尤其涉及基于同态加密的快速模乘运算方法及架构。
背景技术：2.格密码是一种基于格上困难问题的公钥密码体制。格密码系统中算法的并行度高，效率相对较高，速度也更快，同时具有强安全性保障，能够抵抗量子计算机攻击的“抗量子”密码体系。
3.同态加密是一种特殊的加密方式，能够实现密文间的计算功能。同态加密可以实现无密钥方对密文的计算，既可以减少通信代价，也可以提高信息安全性。利用格密码系统，可以构造可行的同态加密系统。为保证良好的加密和计算效果，需要实现大整数模数上的快速模乘计算。
4.传统的barrett模乘等算法，存在下述问题：1)涉及多次高位宽整数的乘法，乘法复杂度较高；2)在特殊数域中算法运行速度较慢。
技术实现要素：5.本发明目的在于克服现有技术中，整数模乘计算中涉及多次高位宽整数的乘法，乘法计算复杂度高，计算速度慢的问题，提出了基于同态加密的快速模乘运算方法及架构，以期能够减少乘法运算的复杂度，提高计算速度。
6.为达到上述发明目的，本发明所采用的技术方案如下：
7.本发明的目的在于克服现有技术中，大整数模乘计算中需要较高的位宽，乘法计算复杂度高的问题，提出来一种基于同态加密的大整数模乘运算方法，可以降低乘法计算复杂度，减少大整数模乘计算所需位宽，且可以保证运算速度。
8.为达到上述发明目的，本发明所采用的技术方案如下：
9.一种基于同态加密的快速模乘运算方法，包括如下步骤：
10.步骤1、接收输入的被乘数a、被乘数b、模数q、指数v1和指数v，其中被乘数a和被乘数b为任意小于模数q的自然数，模数q＝2
v-k*2
v1
+1；指数v1和指数v均为正整数，且指数v1＜指数v；
11.步骤2、计算被乘数a与被乘数b之积，并作为第一计算结果；
12.步骤3、将所述第一计算结果右移v位，得到第二计算结果；
13.步骤4、将模数q右移v
1-1位后与第二计算结果相乘，得到的积左移v
1-1位后加上第二计算结果，获得第三计算结果；
14.步骤5、计算第一计算结果和第二计算结果的差，得到第四计算结果；
15.步骤6、判断所述第四计算结果是否小于模数q的2倍；
16.若不小于，则将第四计算结果赋值给第一计算结果，转到步骤3；
17.若小于，则继续判断是否小于模数q；若是，输出第四计算结果；若否，将第四计算
结果减去模数q，然后输出。
18.一种基于同态加密的快速模乘运算方法，包括以下步骤：
19.步骤1、输入被乘数a、被乘数b和模数q，计算被乘数a*b的积，输出第一计算结果r1＝a*b；其中，被乘数a和被乘数b可为任意小于模数q的自然数，模数2
v-k*2
v1
+1，v1和v为指数，只需满足均为正整数且指数v1《指数v的要求；
20.步骤2、将第一计算结果r1右移v位，得到第二计算结果r2＝(r1＞＞v)，其中＞＞表示右移操作；
21.步骤3、计算需要被约减的量，即第三计算结果，第三计算结果r3＝(r2*(q＞＞(v
1-1)))＜＜(v
1-1)+r2；
22.对第一计算结果r1进行约减，输出第四计算结果r4，r4＝r
1-r3；
23.步骤4、当第四计算结果r4≥2q，重复步骤2-3；当第四计算结果r4《2q时，输出为第五计算结果r5＝r4；
24.步骤5、对于第五计算结果r5进行判断，当第五计算结果r5《q，输出最终结果r＝r5，否则，输出最终结果r＝r
5-q。
25.根据本技术的一个方面，当k*2
v1
《2
v/2
时，只需要两次循环即可快速完成计算；对于汉明权重小于阈值的特定素数，循环次数降为1，从而取消循环。
26.一种基于同态加密的快速模乘器，包括：
27.模数运算模块，用于计算模数包含两个移位寄存器，一个乘法器和一个加法器；指数v1和指数v均为正整数，且指数v1＜指数v；
28.模乘运算模块，包含三个移位寄存器；两个乘法器，一个加法器和一个减法器；用于计算各个中间结果；
29.控制与输出模块，包含一个用于比较中间结果与预定值大小的比较器、一个用于获得中间结果与模数差值的减法器，以及一个选择最终结果并输出的数据选择器。
30.根据本技术的一个方面，所述移位寄存器的位宽为v和v
1-1。
31.根据本技术的一个方面，根据不同运算场景对模数位宽v和v1-1的需求，可将所述模乘运算模块以及控制与输出模块中的比较器设计为多个，构成全流水线结构。
32.本发明采用以上技术方法与现有技术相比，具有以下技术效果：
33.本发明提供的一种基于同态加密的快速模乘运算方法及架构，通过减少乘法运算降低了计算的复杂度，减少了乘法器的面积开销；本发明结合移位约减，对特殊模数的模乘运算进行简化，提升了计算速度。
附图说明
34.图1为本发明的一种基于同态加密的快速模乘运算的流程示意图。
35.图2为本发明的一种基于同态加密的快速模乘运算的电路结构图。
36.图3为本发明中实施例2的电路结果图。
具体实施方式
37.首先，描述本技术的大致过程。本发明基于同态加密的快速模乘运算方法包括以下步骤：
38.定义单个模乘为a
·
b(mod q),其中a和b为被乘数，可以取任意的小于模数q的自然数，模数和v为指数，只需满足均为正整数且v1《v的要求；
39.步骤1，输入被乘数a和被乘数b以及模数q，直接计算被乘数之积a*b，输出第一计算结果r1＝a*b；
40.步骤2，将第一计算结果r1右移v位，得到第二中计算结果r2＝(r1＞＞v)，其中＞＞表示右移操作；
41.步骤3，计算需要被约减的量，即第三计算结果r3，r3＝(r2*(q＞＞(v
1-1)))＜＜(v
1-1)+r2；对第一计算结果r1进行约减，输出第四计算结果r4，r4＝r
1-r3；
42.步骤4，当第四计算结果r4≥2q，重复步骤2-3；当第四计算结果r4《2q时，输出为结果r5；
43.步骤5，对于步骤4的第五计算结果r5进行判断，当第五计算结果r5《q，输出最终结果r＝r5，否则，输出最终结果r＝r
5-q；
44.在实际计算中，合理对v,v1,k赋值后，可以简化运算流程，只需要两次循环即可快速完成计算；对于汉明权重较小的特定素数，可以进一步将循环次数降为1，从而取消循环。
45.本发明还提供了一种基于同态加密的快速模乘器，其硬件架构包括：模数运算模块，模乘运算模块以及控制与输出模块。
46.模数运算模块用于计算模数包含两个移位寄存器(1、2)，一个乘法器(1)和一个加法器(1)。
47.模乘运算模块，包含三个移位寄存器(3，4，5)；两个乘法器(2、3)，一个加法器(2)，一个减法器(1)，用于计算被约减量r3＝(r2*(q＞＞(v
1-1)))＜＜(v
1-1)+r2以及中间结果r1、r2、r3。
48.控制与输出模块，包含一个比较器(1)，用于比较结果r4与2q的大小，如果r4大于2q，结果将送入模乘运算模块循环，直至r4小于2q，输出结果r5。一个减法器(2)，用于计算最终结果r＝r
5-q并输出符号位，一个数据选择器(1)，用于通过减法器(2)输出的符号位来选择输出r5或r
5-q。
49.所述模数运算模块和模乘运算模块所使用的移位寄存器(2、4)与移位寄存器(3、5)，可由两个位宽分别为v和v
1-1移位寄存器代替。所述模数运算模块，可以通过预计算后存储的方法计算模数，从而节省模数运算模块的电路资源开销。
50.所述快速模乘器电路结构，可以通过增加额外的模乘运算模块以及控制与输出模块中的比较器(1)，来展开快速模乘电路结构，从而取消快速模乘器中的循环操作，转为全流水线结构。
51.为进一步了解本发明的内容，结合附图对本发明作详细描述。
52.如图1所示，本发明提供一种基于同态加密的快速模乘算法，包括以下步骤：
53.定义单个模乘为a
·
b(mod q),其中a和b为被乘数，可以取任意的小于q的自然数，q为模数，v1和v为指数，只需满足均为正整数且v1《v的要求；
54.s1、设立第一计算结果，将a*b赋值给第一计算结果；
55.s2、设立第二计算结果，并初始化为0；
56.s3、将第一计算结果右移v位，并赋值给第二计算结果；
57.s4、设置第三计算结果，采用移位拆解的方式计算第二计算结果与模数q相乘的结果，即先将模数q右移v
1-1位后与第二计算结果相乘，得到的中间结果再左移v
1-1位，最终再次加上第二计算结果得到第三计算结果；
58.s5、设立第四计算结果，并赋值为第一计算结果和第三计算结果的差；
59.s6、当第四计算结果大于等于2q，将第四计算结果赋值给第一计算结果，重复步骤s3-s5；当第四计算结果小于2q，设立第五计算结果，将第四计算结果赋值给第五计算结果；
60.s7、对第五计算结果进行判断，当第五计算结果大于等于模数时，输出结果为第五计算结果与模数的差；当第五计算结果小于模数时，输出结果为第五计算结果。
61.实施例1
62.设定模数v和v1满足k*2
v1
《2
v/4
，设定a和b为被乘数，对于软件电路而言，此时快速模乘算法具体步骤如下：
63.步骤1，计算r1＝a*b；
64.步骤2，计算r2＝(r1＞＞v)；
65.步骤3，计算r3＝r
1-r2*q；
66.步骤4，判断r3是否大于模数q，大于模数q则减去模数q并输出结果，小于模数q则输出结果为r3。
67.利用c++对算法进行实现，取k＝1，v1＝3，取v为13、14和15，取a＝b＝q-1。同时和barrett算法进行比较，同样运行100万次，运行结果如表1所示；
68.表1不同参数v下运行时间比较
69.参数v模数q本发明实施例所需时间(秒)barrett模乘算法所需时间(秒)1381850.0030.00514163770.0030.00415327610.0030.004
70.通过此时的模乘算法可以看到，本发明提供的快速模乘算法相对于barrett模乘减少了乘法次数；通过表1的运算时间可见，本发明提供的快速模乘算法的计算时间相对于barrett模乘算法计算时间有所降低。
71.实施例2
72.设定模数取k＝1，v＝30，v1＝14，设定a和b为被乘数，对于硬件电路而言，此时快速模乘算法具体步骤如下：
73.步骤1，计算r1＝a*b；
74.步骤2，计算r2＝(r1＞＞v)；
75.步骤3，计算r3＝(r2*(q＞＞(v
1-1)))＜＜(v
1-1)+r2；
76.步骤4，计算r4＝r
1-r3；
77.步骤5，重复步骤2-4,输出结果为r5；
78.步骤6，对于步骤5的结果r5进行判断，当r5《q，输出最终结果r＝r5，否则，输出最终结果r＝r
5-q。
79.设计了如图3所示的电路结果，虚线框部分的计算均可以通过预计算存储的方式解决。因为预先存储的q的数量比较少，所以存储占用非常小。虚线框之外为该电路设计的
资源消耗，每层需要消耗一个乘法器，和两个加法器，其中在30位的运算中使用到的乘法器最大输出位宽为45。在将两层循环展开为两级流水线的情况下，对比barrett方法中所用到的两个全尺寸乘法器，面积开销上是有所约简的。
80.实施例3
81.对于汉明权重小于阈值的特定素数，该模乘算法的循环次数可以下降为2次甚至一次，从而为汉明权重小于阈值的特定素数提供速度上的提升以及电路资源开销的进一步降低。所设定的阈值分为两类，其结果如表2所示。
82.1、对于模数当满足阈值k*2
v1
＝0时，此时模数变为q＝2v+1的梅森素数，此时步骤3所求结果的r3的数据长度与r1相同，执行完步骤4后即可跳出循环。
83.2、对于模数当满足阈值0《k*2
v1
《2
v/2
时，此时步骤3所求结果的r3的数据长度增加v1后与r1相同，此时再执行一次循环后即可跳出循环。
84.表2不同参数下循环次数比较
[0085][0086]
在上文中结合具体的示例性实施例详细描述了本发明。但是，应当理解，可在不脱离由所附权利要求限定的本发明的范围的情况下进行各种修改和变型。详细的描述和附图应仅被认为是说明性的，而不是限制性的，如果存在任何这样的修改和变型，那么它们都将落入在此描述的本发明的范围内。附图中所示的也只是本发明创造的实施方式之一，实际的结构并不局限于此，权利要求中的任何附图标记不应限制所涉及的权利要求。此外，背景技术旨在为了说明本技术的研发现状和意义，并不旨在限制本发明或本技术和本发明的应用领域。所以，如果本领域的普通技术人员受其启示，在不脱离本创造宗旨的情况下，不经创造性的设计出与该技术方案相似的结构方式及实施例，均应属于本专利的保护范围。
技术特征：1.一种基于同态加密的快速模乘运算方法，其特征在于，包括如下步骤：步骤1、接收输入的被乘数a、被乘数b、模数q、指数v1和指数v，其中被乘数a和被乘数b为任意小于模数q的自然数，模数q＝2
v-k*2
v1
+1；指数v1和指数v均为正整数，且指数v1＜指数v；步骤2、计算被乘数a与被乘数b之积，并作为第一计算结果；步骤3、将所述第一计算结果右移v位，得到第二计算结果；步骤4、将模数q右移v
1-1位后与第二计算结果相乘，得到的积左移v
1-1位后加上第二计算结果，获得第三计算结果；步骤5、计算第一计算结果和第二计算结果的差，得到第四计算结果；步骤6、判断所述第四计算结果是否小于模数q的2倍；若不小于，则将第四计算结果赋值给第一计算结果，转到步骤3；若小于，则继续判断是否小于模数q；若是，输出第四计算结果；若否，将第四计算结果减去模数q，然后输出。2.一种基于同态加密的快速模乘运算方法，其特征在于，包括以下步骤：步骤1、输入被乘数a、被乘数b和模数q，计算被乘数a*b的积，输出第一计算结果r1＝a*b；其中，被乘数a和被乘数b可为任意小于模数q的自然数，模数2
v-k*2
v1
+1，v1和v为指数，只需满足均为正整数且指数v1<指数v的要求；步骤2、将第一计算结果r1右移v位，得到第二计算结果r2＝(r1＞＞v)，其中＞＞表示右移操作；步骤3、计算需要被约减的量，即第三计算结果，第三计算结果r3＝(r2*(q＞＞(v
1-1)))＜＜(v
1-1)+r2；对第一计算结果r1进行约减，输出第四计算结果r4，r4＝r
1-r3；步骤4、当第四计算结果r4≥2q，重复步骤2-3；当第四计算结果r4<2q时，输出为第五计算结果r5＝r4；步骤5、对于第五计算结果r5进行判断，当第五计算结果r5<q，输出最终结果r＝r5，否则，输出最终结果r＝r
5-q。3.根据权利要求1所述的基于同态加密的快速模乘运算方法，其特征在于，当k*2
v1
<2
v/2
时，只需要两次循环即可快速完成计算；对于汉明权重小于阈值的特定素数，循环次数降为1，从而取消循环。4.一种基于同态加密的快速模乘器，其特征在于，包括：模数运算模块，用于计算模数包含两个移位寄存器，一个乘法器和一个加法器；指数v1和指数v均为正整数，且指数v1＜指数v；模乘运算模块，包含三个移位寄存器；两个乘法器，一个加法器和一个减法器；用于计算各个中间结果；控制与输出模块，包含一个用于比较中间结果与预定值大小的比较器、一个用于获得中间结果与模数差值的减法器，以及一个选择最终结果并输出的数据选择器。5.根据权利要求4所述的基于同态加密的快速模乘器，其特征在于，所述移位寄存器的位宽为v和v
1-1。6.根据权利要求4所述的基于同态加密的快速模乘器，其特征在于，根据不同运算场景
对模数位宽v和v
1-1的需求，可将所述模乘运算模块以及控制与输出模块中的比较器设计为多个，构成全流水线结构。
技术总结本发明公开了一种基于同态加密的快速模乘运算方法和模乘器，属于格密码领域。本发明的方法为先计算出被乘数的乘积，在同余的环境下进行多次移位约减，最终通过比较结果和模数的大小再进行一步约减，得到最后的模乘结果。模乘器包括模数运算模块，模乘运算模块以及控制与输出模块。本发明的目的在于克服现有技术中，基于同态加密的模乘算法运算涉及的乘法计算较多，乘法计算复杂度高，运算时间长的问题，本发明可以减少乘法计算复杂度，加快运算速度，减少硬件面积开销。减少硬件面积开销。减少硬件面积开销。
技术研发人员：李丽 王鑫宇 傅玉祥 邵心语 宋文清 何书专 李伟
受保护的技术使用者：南京大学
技术研发日：2022.06.29
技术公布日：2022/11/1
