有限域大整数乘法器及基于SSA算法的大整数乘法的实现方法[发明专利]

(12)发明专利申请

(10)申请公布号 CN 1103291 A(43)申请公布日 2019.12.06

(21)申请号 201910502766.2(22)申请日 2019.06.11

(71)申请人 南通大学

地址 226019 江苏省南通市崇川区啬园路9

号(72)发明人 谢星　孙玲　孙海燕　杨玲玲　(74)专利代理机构 江苏隆亿德律师事务所

32324

代理人 倪金磊(51)Int.Cl.

G06F 7/53(2006.01)H04L 9/00(2006.01)

权利要求书2页 说明书7页 附图5页

CN 1103291 A()发明名称

有限域大整数乘法器及基于SSA算法的大整数乘法的实现方法(57)摘要

本发明公开一种有限域大整数乘法器，大数乘法器为基于SSA算法的768K-bit大整数乘法器，其包括：用于接收第一输入数据的第一输入端；用于接收第二输入数据的第二输入端；输出端；第一有限域处理模块和第二有限域处理模块，用于对接收到的输入数据进行NTT变换处理；控制模块，用于对第一输入数据和第二输入数据进行排序处理，并将排序后的第一输入数据输出至第一有限域处理模块。进位处理模块，用于对经过NTT逆变换处理的数据进行进位处理，生成最终计算结果通过所述输出端输出。本发明还提供了基于SSA算法进行大数乘法的实现方法，根据本发明公开的乘法器和方法，可以在公钥加密方案中得到广泛应用。

CN 1103291 A

权　利　要　求　书

1/2页

1.有限域大整数乘法器，其特征在于，所述大整数乘法器为基于SSA算法的768K-bit大整数乘法器，其包括：

用于接收第一输入数据的第一输入端；用于接收第二输入数据的第二输入端；输出端；

第一有限域处理模块和第二有限域处理模块，用于对接收到的输入数据进行NTT变换处理；

控制模块，用于对第一输入数据和第二输入数据进行排序处理，并将排序后的第一输入数据输出至第一有限域处理模块，将排序后的第二输入数据输出至第二有限域处理模块，以及从所述第二有限域处理模块获取NTT变换处理后的第二输入数据输出至所述第一有限域处理模块；和

进位处理模块，用于对经过NTT逆变换处理的数据进行进位处理，生成最终计算结果通过所述输出端输出；

其中，所述第一有限域处理模块还用于对NTT变换处理后的第一输入数据和NTT变换处理后的第二输入数据进行点积模乘计算，并对点积模乘计算的计算结果进行NTT逆变换处理后输出至上述进位处理模块。

2.根据权利要求1所述的有限域大整数乘法器，其中，所述第一有限域处理模块和第二有限域处理模块均实现为包括用于对输入数据进行第一级运算处理的第一级处理组件和用于对第一级运算处理结果进行第二级运算处理的第二级处理组件，其中

所述第一级处理组件包括六十四个连续的1024点NTT处理单元，所述1024点NTT处理单元由两级基-32点NTT处理单元串行而成；

所述第二级处理组件包括用于进行模乘运算的模乘法器和基-点NTT处理单元。3.根据权利要求2所述的有限域大整数乘法器，其中，所述基-32点NTT处理单元实现为包括三十二个移位单元和树形大数求和处理单元，所述基-点NTT处理单元实现为包括六十四个移位单元和树形大数求和处理单元；

所述移位单元用于对输入数据进行移位运算，并输出移位后的数据至所述树形大数求和处理单元；

所述树形大数求和处理单元用于对移位运算后的输出数据进行累加求和运算，得到求和结果输出。

4.根据权利要求3所述的有限域大整数乘法器，其中，所述树形大数求和处理单元包括32输入四级串联结构的进位保留加法器，用于对移位处理后的数据进行加法运算；模约减器，用于对所述进位保留加法器的加法运算结果进行位数转换；模加器，用于对位数转换后的数据进行模加法运算，得到求和结果输出。5.根据权利要求2至4任一项所述的有限域大整数乘法器，其中，还包括用于存储运算数据的存储模块，所述存储模块包括

第一存储单元，用于1024点NTT处理单元和基-点NTT处理单元的运算数据；和第二存储单元，用于存储基-32点NTT处理单元和基-点NTT处理单元的旋转因子。6.根据权利要求5所述的有限域大整数乘法器，其特征在于，所述第一存储单元实现为六十四个RAM存储组，每个RAM存储组包括三十二个RAM存储器。

2

CN 1103291 A

权　利　要　求　书

2/2页

7.根据权利要求6所述的有限域大整数乘法器，其特征在于，所述第二存储单元实现为一个ROM存储器。

8.根据权利要求5所述的有限域大整数乘法器，其特征在于，所述第一有限域处理模块和第二有限域处理模块设置为共用所述第二存储单元。

9.根据权利要求6所述的有限域大整数乘法器，其特征在于，所述控制模块，包括：预处理单元，用于对获取的第一输入数据和第二输入数据分别进行分组和排序处理，生成32K个样本数据组分别存储至相应的三十二个RAM存储器中；和

读写单元，用于利用同址运算和无冲突算法获取所述输入数据的读写地址，对输入数据进行读写操作输出至所述第一有限域变换模块和第二有限域变换模块。

10.基于SSA算法进行有限域大数乘法的实现方法，其特征在于，包括如下步骤：

将第一输入数据和第二输入数据分别通过第一输入端和第二输入端输入至大整数数乘法器，其中，所述大整数数乘法器为权利要求1至9任一项所述的有限域大整数数乘法器；

对所述第一输入数据和第二输入数据分别进行分组和排序处理并存储至相应的RAM存储器；

读取所述RAM存储器获取第一输入数据和第二输入数据，将所述第一输入数据和第二输入数据分别输出至第一有限域处理模块和第二有限域处理模块进行有限域变换的计算；

从第二有限域处理模块获取变换处理结果输出至第一有限域处理模块，通过第一有限域处理模块对变换后的第一输入数据和第二输入数据进行点积模乘运算和逆变换处理；

对逆变换处理结果进行进位处理，得到最终处理结果输出。11.根据权利要求10所述的方法，其特征在于，通过第一有限域处理模块和第二有限域处理模块进行有限域变换的计算实现为包括

在ROM存储器中配置旋转因子；

依次从六十四个RAM存储组中读取三十二位输入数据，输出到1024点NTT处理单元进行第一级NTT运算，并将每个RAM存储组的运算结果写入到相应的RAM存储组中，直至六十四个RAM存储组均进行完1024点NTT处理；

分别从六十四个RAM存储组中读取第一级NTT运算的计算结果，将读取的计算结果与旋转因子进行模乘运算；

将模乘运算结果输出至基-点NTT处理单元进行第二级NTT运算，得到有限域变换的计算结果输出。

3

CN 1103291 A

说　明　书

1/7页

有限域大整数乘法器及基于SSA算法的大整数乘法的实现

方法

技术领域

[0001]本发明涉及加密技术领域，特别是一种有限域大整数乘法器及用于进 行全同态加密运算的大整数乘法的方法。

背景技术

[0002]随着云计算时代的到来和云服务需求的不断增加，用户数据的安全性 和隐私性成为人们关注的热点。尽管云平台存放的是用户经过加密的数据， 但同时密钥被云服务商所获知，不能确保用户数据的安全和隐私。对于这 一问题，现有技术的全同态加密可以允许云服务器在密文上直接做任意运 算，运算过程中数据始终处于加密状态，不会暴露任何原文信息，被认为 是保障云时代用户数据安全的有效技术之一。[0003]然而，以Gentry为代表的全同态加密(Fully Homomorphic Encryption, FHE)算法为保证同态计算安全，需要的密钥长度很长，从而导致同态加 密方案运算复杂度极高，就会导致在现有微处理器上运行效率极低。例如， 对于维度为2048的最低安全设置而言，1bit原码加密后的大小约为785000 bit，每加密1bit需要时间为1s，并且随后对这些密文进行的操作都是大数 运算，计算延时阻碍了FHE方案的实际应用。发明内容

[0004]为了解决上述的对于加密运算效率低，计算速度慢的问题，发明人构 建了一种有限域大整数乘法器，对于全同态加密，大数的模乘运算效率是 加密效果的关键。通过该大数乘法器可以允许云服务器在密文上直接做任 意运算，并且由于基于SSA算法，在运算过程中运行速度较快，并且数据 始终处于加密状态，不会暴露任何原文信息，提高了用户的数据安全性。 基于SSA(

–Strassen algorithm)这种高效的二进制乘法算法，对 

加密数据进行全同态计算，大大的提高了运算速度和效率，并且不需要设 置过长的密钥，有利于保护数据安全。

[0005]根据本发明的一个方面，提供了大整数乘法器，大整数乘法器为基于 SSA算法的768K-bit大整数乘法器，其包括：用于接收第一输入数据的第 一输入端；用于接收第二输入数据的第二输入端；输出端；第一有限域处 理模块和第二有限域处理模块，用于对接收到的输入数据进行NTT变换处 理；控制模块，用于对第一输入数据和第二输入数据进行排序处理，并将 排序后的第一输入数据输出至第一有限域处理模块，将排序后的第二输入 数据输出至第二有限域处理模块，以及从第二有限域处理模块获取NTT变 换处理后的第二输入数据输出至所述第一有限域处理模块；和进位处理模 块，用于对经过NTT逆变换处理的数据进行进位处理，生成最终计算结果 通过输出端输出；其中，第一有限域处理模块还用于对NTT变换处理后的 第一输入数据和NTT变换处理后的第二输入数据进行点积模乘计算，并对 点积模乘计算的计算结果进行NTT逆变换处理后输出至下述进位处理模 块。由于SSA的大数算法需要计算操作数和的NTT，并且用NTT逆变换 运算两个操作数的点积结果。

4

CN 1103291 A

说　明　书

2/7页

因此，第一有限域处理模块和第二有限域处 理模块是由为重要的。通过控制模块将输入的第一数据和第二数据进行排 序操作后再分别输入到第一有限域处理模块和第二有限域处理模块满足于 SSA算法的需求。对于进位处理模块，通过进位处理的操作可以克服现有 技术中直接做乘法运算而导致的NNT运算复杂的问题。由此，可以实现提 高大数运算的效率，并且有效的保护了信息的安全性。[0006]在一些实施方式中，第一有限域处理模块和第二有限域处理模块均实 现为包括用于对输入数据进行第一级运算处理的第一级处理组件和用于对 第一级运算处理结果进行第二级运算处理的第二级处理组件，其中第一级 处理组件包括六十四个连续的1024点NTT处理单元，1024点NTT处理单 元由两级基-32点NTT处理单元串行而成；第二级处理组件包括用于进行 模乘云端的模乘法器和基-点NTT处理单元。由于在实现NTT运算时所 涉及到的模加、模减和模乘都是基于2的幂次方，如果要实现位或其它 宽的操作时，每一个运算结果都要进行取模操作，这就占用了大量的硬件 资源，由此，在两个有限域处理模块中分别设置第一级运算处理组件和第 二级运算处理组件可以实现对输入的数据进行分级化运算，避免了直接运 算的复杂性，且两个模块均以基-32点NTT处理和基-点NTT处理为基 本单元，运算过程只需进行移位和模加操作，可以降低NTT运算的复杂性。[0007]在一些实施方式中，基-32点NTT处理单元实现为包括三十二个移位 单元和树形大数求和处理单元，基-点NTT处理单元实现为包括六十四 个移位单元和树形大数求和处理单元；移位单元用于对输入数据进行移位 运算，并输出移位后的数据至所述树形大数求和处理单元；树形大数求和 处理单元用于对移位运算后的输出数据进行累加求和运算，得到求和结果 输出。在实际的NTT运算中，如果直接计算点、32点NTT将十分复 杂，由于位、32位和16位等NTT运算的单位根都是2的幂次方，因此 可以做移位操作，而不用直接乘法运算，这样可以降低NTT运算的复杂性。 因此，通过在基-32点NTT和基-点NTT中设置移位单元，并且通过大 数求和处理单元对移位单元处理后的结果进行累加就可以得到计算结果。

[0008]在一些实施方式中，树形大数求和处理单元包括32输入四级串联结构 的进位保留加法器，用于对移位处理后的数据进行加法运算；模约减器， 用于对所述进位保留加法器的加法运算结果进行位数转换；模加器，用于 对位数转换后的数据进行模加法运算，得到求和结果输出。为了提高计算 效率，通过进位保留加法器的原理进行计算，由于进位保留器有3个位操 作数输入端口，其中两个为加法数据和，还有一个为来自低位的进位；输 出端口为进位输出。使用两个进位保留加法器串联可以实现一个4输入的 进位保留加法器，因此采用32输入4级串联结构作为树形大数求和处理单 元。再通过模约减器和模加器对计算结果进行位数转化和模加运算，大大 的提高了运算速度。[0009]在一些实施方式中，还包括用于存储运算数据的存储模块，存储模块 包括第一存储单元，用于1024点NTT处理单元和基-点NTT处理单元 的运算数据；和第二存储单元，用于存储基-32点NTT处理单元和基-点 NTT处理单元的旋转因子。由于在NTT运算中需要大量的存储模块，通过 设置第一存储单元和第二存储单元可以实现无冲突算法。由于每次参与运 算的旋转因子都是固定值，而且都为2的幂次方。而当前主流硬件电路恰 好非常适合计算2的幂次方运算，因为只需要在存储单元中配置旋转因子， 就可以在进行移位时直接得出计算结果。

5

CN 1103291 A[0010]

说　明　书

3/7页

在一些实施方式中，第一存储单元实现为六十四个RAM存储组，每个 RAM存储组包

括三十二个RAM存储器。这样在NTT实际的运算时，可以 重复调用不同的RAM存储器获取计算数据，减少了设计的资源开销。[0011]在一些实施方式中，第二存储单元实现为一个ROM存储器。第一有限 域处理模块和第二有限域处理模块设置为共用第二存储单元。为了提高计 算效率，减少ROM存储器的使用，基-32点NTT处理单元和基-点NTT 处理单元都使用同一ROM存储器的旋转因子，从而达到同址计算的效果。

[0012]在一些实施方式中，控制模块，包括预处理单元，用于对获取的第一 输入数据和第二输入数据分别进行分组和排序处理，生成32K个样本数据 组分别存储至相应的三十二个RAM存储器中；和读写单元，用于利用同址 运算和无冲突算法获取输入数据的读写地址，对输入数据进行读写操作输 出至第一有限域变换模块和第一有限域变换模块。通过对第一输入数据和 第二输入数据进行分组和排序处理后，存储至RAM存储器中，不占用过多 的数据资源，再通过读写单元对输入数据的读写地址即用即读，且数据的 存储基于同址运算和无冲突算法实现了复用，大大的提高了运算的处理效 率。[0013]根据本发明的另一个方面，提供了一种基于SSA算法进行大数乘法的 实现方法，包括如下步骤：将第一输入数据和第二输入数据分别通过第一 输入端和第二输入端输入至全同态大整数数乘法器，其中，有限域大整数 数乘法器为上述的有限域大整数数乘法器；对第一输入数据和第二输入数 据分别进行分组和排序处理并存储至相应的RAM存储器；读取RAM存储 器获取第一输入数据和第二输入数据，将第一输入数据和第二输入数据分 别输出至第一有限域处理模块和第二有限域处理模块进行有限域变换的计 算；从第二有限域处理模块获取变换处理结果输出至第一有限域处理模块， 通过第一有限域处理模块对变换后的第一输入数据和第二输入数据进行点 积模乘运算和逆变换处理；对逆变换处理结果进行进位处理，得到最终处 理结果输出。通过将第一输入数据和第二输入数据做预处理并存储至RAM 存储器中，根据第一有限域处理模块和第二有限域处理模块对数据进行基 于SSA算法的有限域计算，在运算过程中运行速度较快，并且数据始终处 于加密状态，提高了用户的数据安全性。[0014]在一些实施方式中，通过第一有限域处理模块和第二有限域处理模块 进行有限域变换的计算实现为包括在ROM存储器中配置旋转因子；依次从 六十四个RAM存储组中读取三十二位输入数据，输出到1024点NTT处理 单元进行第一级NTT运算，并将每个RAM存储组的运算结果写入到相应 的RAM存储组中，直至六十四个RAM存储组均进行完1024点NTT处理； 分别从六十四个RAM存储组中读取第一级NTT运算的计算结果，将读取 的计算结果与旋转因子进行模乘运算；将模乘运算结果输出至基-点NTT 处理单元进行第二级NTT运算，得到有限域变换的计算结果输出。通过 ROM存储器中存储的旋转因子和RAM存储组中存储的处理数据，可以有 效的节约数据资源，大大的提高运算速度。附图说明

[0015]图1为本发明一实施方式的有限域大整数乘法器的原理框图；

[0016]图2为本发明一实施方式的有限域大整数乘法器的第一有限域处理模 块原理框图；

6

CN 1103291 A[0017]

说　明　书

4/7页

图3为本发明一实施方式的有限域大整数乘法器的第二有限域处理模 块原理框图4为本发明一实施方式的有限域大整数乘法器的基32点NTT处理 单元原理框图5为本发明一实施方式的有限域大整数乘法器的基点NTT处理 单元原理框

图；

[0018]

图；

[0019]

图；

[0020]

图6为本发明一实施方式的有限域大整数乘法器的树形求和单元的原 理示意图；

[0021]图7为本发明一实施方式的基于SSA算法进行大数乘法的实现方法流 程图；[0022]图8为本发明一实施方式的基-32点NTT处理单元32的三十二个RAM 存储器读写地址运算原理框图。

具体实施方式

[0023]下面结合附图对本发明作进一步详细的说明。

[0024]图1示意性地显示了根据本发明的一种实施方式的有限域大整数乘法 器的原理框图。如图1所示，

[0025]该大整数乘法器1为基于SSA算法的768K-bit大整数乘法器，其包括： 用于接收第一输入数据的第一输入端11、用于接收第二输入数据的第二输 入端12、输出端13、第一有限域处理模块22、第二有限域处理模块23、 控制模块21和进位处理模块24。在本实施例的768k-bit的大数乘法器中， 第一输入端11和第二输入端12分别接收k组第一输入数据和第二输入 数据，每组数据为bit，这样大数乘法器的输出数据就共有768kbit。第一 有限域处理模块22和第二有限域处理模块23用于对由第一输入端11和第 二输入端12接收到的输入数据进行NTT(有限域变换)处理，分别实现为 两个k点的有限域处理模块，由于SSA的大数算法需要计算输入数据和 的NTT，并且用INTT运算(NTT逆变换)经过NTT处理后的操作数的点 积结果，所以第一有限域处理模块22和第二有限域处理模块21为关键模 块。控制模块21用于对第一输入数据和第二输入数据进行排序处理，可以 在控制模块中设定根据数据的类型进行排序，并将排序后的第一输入数据 输出至第一有限域处理模块22，将排序后的第二输入数据输出至第二有限 域处理模块23。该控制模块21还从第二有限域处理模块23获取NTT变换 处理后的第二输入数据输出至第一有限域处理模块22进行进一步的NTT 操作。进位处理模块24用于对经过NTT逆变换处理的数据进行进位处理， 生成最终计算结果通过输出端13输出。其中，为了减少资源开销，第一有 限域处理模块22还用于对NTT变换处理后的第一输入数据和NTT变换处 理后的第二输入数据进行点积模乘计算，并对点积模乘计算的计算结果进 行NTT逆变换处理后输出至上述进位处理模块24。[0026]具体地，作为一种优选实施方式，如图2和图3所示，第一有限域处 理模块22和第二有限域处理模块23均实现为包括用于对输入数据进行第 一级运算处理的第一级处理组件221和用于对第一级运算处理结果进行第 二级运算处理的第二级处理组件222，其中第一级处理组件221包括六十四 个连续的1024点NTT处理单元31，1024点NTT处理单元31由两级基-32 点NTT处理单元32串行而成。第二级处理组件222包括用于进行模乘运 算的模乘法器41和基-点NTT处理单元42。由于有限域变换中，实现 NTT变换所涉及到的模加、模减和模乘都是基于2的幂次方，对于本实施 例要实现的位宽的操作，每一个运算结果都要

7

CN 1103291 A

说　明　书

5/7页

进行模操作，这就占用了 大量的硬件资源。由此，发明人构思将位宽的操作数扩展为192位，采 用“0填充”的方式进行数据位的扩展，这样就避免了每次操作都进行模运 算，由此选择基-32点NTT处理单元32和基-点NTT处理单元作为基本 单元，这样在运算过程只需要移位和模加操作。其中，如图4所示，基-32 点NTT处理单元32实现为包括三十二个移位单元321和树形大数求和处 理单元322。如图5所示，基-点NTT处理单元42实现为包括六十四个 移位单元321和树形大数求和处理单元322。其中，移位单元321用于对输 入数据进行移位运算，并输出移位后的数据至树形大数求和处理单元322， 树形大数求和处理单元322用于对移位运算后的输出数据进行累加求和运 算，得到求和结果输出。对于树形大数求和处理单元322，包括32输入四 级串联结构的进位保留加法器61、模约减器62和模加器63，进位保留加 法器61(CSA)用于对移位处理后的数据进行加法运算，模约减器62用于 对进位保留加法器61的加法运算结果进行位数转换，模加器63用于对位 数转换后的数据进行模加法运算，得到求和结果输出。在基-32点NTT处 理单元32中，有限域NTT和INTT的计算公式分别为：

[0027]

[0028][0029]

其中，k表示序数，取值为0#k 31，n表示采样点，取值为0#n 31， p为Solinas素数，

取值为2-232+1。

[0030]将三十二个移位单元321经过上述运算处理后的数据经过树形大数求 和处理单元322进行累加，如图6所示，CSA有3个位操作数输入端口， 其中两个为第一输入数据和第二输入数据的加法数据和，还包括一个为来 自低位的进位数据，输出端口包括部分和输出，输出端口为进位输出。给 定3个输入数据a、b、c，其部分和为a排b c，进位为ab+bc+ac。使用两 个进位保留加法器串联可以实现一个4输入的CSA，然后经过模加法运算 得到求和结果

[0031]在基-点NTT处理单元32中，有限域NTT和INTT的计算公式分别 为：

[0032]

[0033][0034]

其中，k表示序数，取值为0#k 63，n表示采样点，取值为0#n 63， p为Solinas素数，取值为2-232+1。

[0035]将六十四个移位单元321经过上述运算处理后的数据经过树形大数求 和处理单元322进行累加。

[0036]该乘法器还包括用于存储运算数据的存储模块7，存储模块7包括第一 存储单元71和第二存储单元72，第一存储单元71用于1024点NTT处理 单元31和基-点NTT处理单元42的运算数据，实现为六十四个RAM存 储组，每个RAM存储组包括三十二个RAM存储器。为了提高数据在计算 过程中的效率，通过同址运算将处理过程中的运算数据存储至各RAM存储 

8

CN 1103291 A

说　明　书

6/7页

器，即在计算时总是用当前层替代前一层，从而使得输出数据使用原输入 数据结点所占用的内存。这种输出、输入数据利用同一内存单元的蝶形计 算称为同址计算，该算法在计算全部分析点数据时具有很高的效率。第二 存储单元72用于存储基-32点NTT处理单元32和基-点NTT处理单元 42的旋转因子(2的幂次方的固定值)，实现为一个ROM存储器。为了减 少ROM存储器的使用，节约资源，第一有限域处理模块22和第二有限域 处理模块23设置为共用第二存储单元中的旋转因子，即共用同一存储单元。[0037]控制模块21，包括预处理单元(图中未示)和读写单元(图中未示)， 预处理单元用于对获取的第一输入数据和第二输入数据分别进行分组和排 序处理，生成32K个样本数据组分别存储至相应的三十二个RAM存储器 中。读写单元用于获取输入数据的读写地址，对输入数据进行读写操作输 出至第一有限域变换模块22和第二有限域变换模块23。其中，读写单元采 用同址运算的方式来获取数据的读写地址，具体地，如图8所示，以对基 -32点NTT处理单元32的三十二个RAM存储器获取数据读写地址进行数 据的读写为例，实现为：将图8中各个RAM存储器的存储地址转换为二维 地址，即以存储器编号表示块地址，数据地址表示点地址。块地址用0-31 表示，点地址用0-1023表示，比如数据32的地址为(1，1)。设置输入 数据的地址为Data_cout＝[dn-1,dn-2,L,d2,d1,d0]r，其中n为块数，取值为 

d为原始序列编号,r为NTT点数，N为NTT的长度；存储数据 的地址为：

Address＝[dn-1,dn-2,L,d2,d1]r，

[0039]Bank_index＝(dn-1+dn-2+L+d2+d1+d0)modr；[0040]其中r取为32，N为1024。在具体处理过程中，控制模块先通过预处理单 元对输入数据进行排序，排序好的数据经由读写单元根据同址运算获取读 写地址后，将数据存储到双口RAM存储器中，并通过读写地址控制单元对 数据进行读写操作，读出的数据经过基-32点NTT处理单元进行运算，运 算结果与ROM存储器中存储的旋转因子进行模乘运算后再储存到RAM存 储器中。

[0041]根据本实施例公开的基于SSA算法的768kbit大数乘法器，利用基-32 点NTT处理单元与基-点NTT处理单元实现了关键模块第一有限域处理 模块和第二有限域处理模块，使得运算过程只需进行移位和模加操作，提 高了运算效率。并且数据运算过程中，采用了同址运算和无冲突算法实现 了存储模块的数据存取，减少了资源的耗费，提高了其运算速度，大大的 保护了用户的数据安全性。

[0042]图7示意性地显示了根据本发明一实施方式的基于SSA算法进行全同 态大数乘法的实现方法流程图，如图7所示，本实施方式中包括如下步骤：[0043]步骤S701：将第一输入数据和第二输入数据分别通过第一输入端和第 二输入端输入至全同态大整数数乘法器，其中，全同态大整数数乘法器为 上述的全同态大整数数乘法器。

[0044]步骤S702：对第一输入数据和第二输入数据分别进行分组和排序处理 并存储至相应的RAM存储器。[0045]步骤S703：读取RAM存储器获取第一输入数据和第二输入数据，将 第一输入数据和第二输入数据分别输出至第一有限域处理模块和第二有限 域处理模块进行有限域变换的计算。再通过控制模块21中的读写单元对数 据进行读写操作，将读出的数据经过基-32NTT模块进行运算，将运算结果 与ROM单元中存储的旋转因子进行模乘运算后再储存到

9

[0038]

CN 1103291 A

说　明　书

7/7页

RAM中。其中， 具体实现为：先在ROM存储器中配置旋转因子，依次从六十四个RAM存 储组中读取三十二位输入数据，输出到1024点NTT处理单元进行第一级 NTT运算，并将每个RAM存储组的运算结果写入到相应的RAM存储组中， 直至六十四个RAM存储组均进行完1024点NTT处理；再分别从六十四个RAM存储组中读取第一级NTT运算的计算结果，将读取的计算结果与旋 转因子进行模乘运算，将模乘运算结果输出至基-点NTT处理单元进行 第二级NTT运算，得到有限域变换的计算结果输出。[0046]步骤S704：从第二有限域处理模块获取变换处理结果输出至第一有限 域处理模块，通过第一有限域处理模块对变换后的第一输入数据和第二输 入数据进行点积模乘运算和逆变换处理。[0047]步骤S705：对逆变换处理结果进行进位处理，得到最终处理结果输出。[0048]根据本实施例提供的方法可以通过采用加法和移位操作以保证大数乘 法的过程中并行处理的最大化，有效提高了处理速度，并且保证了用户数 据的安全性。[0049]最后应说明的是：以上实施例仅用以说明本申请的技术方案，而非对 其；尽管参照前述实施例对本申请进行了详细的说明，本领域的普通 技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修 改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不 使相应技术方案的本质脱离本申请各实施例技术方案的精神和范围。

10

CN 1103291 A

说　明　书　附　图

1/5页

图1

图2

11

CN 1103291 A

说　明　书　附　图

2/5页

图3

图4

12

CN 1103291 A

说　明　书　附　图

3/5页

图5

图6

13

CN 1103291 A

说　明　书　附　图

4/5页

图7

14

CN 1103291 A

说　明　书　附　图

5/5页

图8

15