本申请公开了一种结合Karatsuba和蒙哥马利模乘的数据处理方法，涉及数据加密领域，该方法结合Karatsuba和蒙哥马利模乘以快速实现模乘运算，利用小位宽的乘法器即可快速完成乘法运算，Karatsuba可以加速大整数乘法的运算，降低大整数乘法的计算复杂度，而且本申请在设计乘法器位宽时，直接预留进位，使得乘法运算和加法运算可以同步推进，从而可以优化整个数据处理过程的时序，进一步缩短计算耗时，从而可以在占用较小面积的基础上还可以有较少的计算耗时，电路面积与计算时间都有较优的表现。
1.一种结合Karatsuba和蒙哥马利模乘的数据处理方法，其特征在于，所述数据处理方法包括：获取两个模乘操作数 和 ，两个模乘操作数 和 的位宽均为 ；
将两个模乘操作数 和 分别拆分为若干个 位宽的子操作数，通过模乘操作数 和拆分得到的各个子操作数以及子操作数的加法结果利用 位宽的乘法器、基于Karatsuba算法求解得到两个模乘操作数 和 的第一乘积结果 ，其中，乘法器的位宽满足子操作数的加法结果的位宽需求且小于预定阈值；
基于蒙哥马利模乘计算所述第一乘积结果 的低 位结果 与中间参数 的第二乘积结果 ， ， ， 且 和 的最大公约数为1；
将所述第二乘积结果 的低 位结果 以及位宽为 的模乘操作数 分别拆分为若干个 位宽的子操作数，通过 和模乘操作数 拆分得到的各个子操作数以及子操作数的加法结果利用 位宽的乘法器、基于Karatsuba算法求解得到 和模乘操作数 的第三乘积结果 ；
基于所述第三乘积结果 输出 的结果作为 的模乘结果；
其中，所述数据处理方法使用的乘法器的位宽 ，两个模乘操作数 和 的位宽均为 ，对每个模乘操作数拆分得到的4个子操作数的位宽均为 ，每个模乘操作数拆分得到的多个子操作数相加得到的加法结果的位宽最多为66bit；第二乘积结果 的低 位结果 以及模乘操作数 的位宽均为 ，对 拆分得到的4个子操作数的位宽均为 ，且对 拆分得到的多个子操作数相加得到的加法结果的位宽最多为66bit，对模乘操作数 拆分得到的4个子操作数的位宽均为 ，且对模乘操作数 拆分得到的多个子操作数相加得到的加法结果的位宽最多为66bit。
2.根据权利要求1所述的数据处理方法，其特征在于，所述数据处理方法利用单个乘法器通过 个计算周期得到 的模乘结果，其中， ，符号 表示向上取整。
3.根据权利要求1所述的数据处理方法，其特征在于，所述数据处理方法利用 个位宽的乘法器通过 个计算周期得到 的模乘结果，其中， ，符号 表示向上取整， 表示与乘法器的个数 对应的额外计算周期数。
4.根据权利要求1所述的数据处理方法，其特征在于，在基于Karatsuba算法求解得到任意两个位宽均为256bit的乘数 和 的乘积结果 时：对乘数 拆分得到的4个64bit的子操作数 、 、 和 ， 包括乘数 的0到63位， 包括乘数 的64到127位， 包括乘数 的128到191位， 包括乘数 的192到255位；对乘数 拆分得到的4个64bit的子操作数 、 、 和 ， 包括乘数 的0到63位，包括乘数 的64到127位， 包括乘数 的128到191位， 包括乘数 的192到255位；
以及 ；其中， 、 、 和 在加法产生的进位的作用下位宽最多
为65bit， 在加法产生的进位的作用下位宽最多为66bit；
以及 ；其中， 、 、 和 在加法产生的进位的作用下位宽最多为
65bit， 在加法产生的进位的作用下位宽最多为66bit；
使用位宽 的乘法器计算乘数 的子操作数与乘数 的子操作数的乘积，以及使用位宽 的乘法器计算乘数 的子操作数的加法结果与乘数 的子操作数的加法结果的乘积，计算得到乘数 和 的乘积结果 ；
其中，乘数 和 分别为模乘操作数 和 、对应得到的乘积结果 为所述第一乘积结果 ；或者，乘数 和 分别为 和模乘操作数 、对应得到的乘积结果 为所述第三乘积结果 。
5.根据权利要求4所述的数据处理方法，其特征在于，所述数据处理方法使用2个位宽的乘法器并行实现乘法运算，基于Karatsuba算法求解任意两个位宽均为256bit的乘数 和 的乘积结果 的方法包括：在第一个计算周期，利用两个乘法器并行地分别计算 以及 ，计
算 与 之和并在当前计算周期结束后更新存入寄存器 ，计算 和 的位操作结果并在当前计算周期结束后更新存入寄存器 ；
在第二个计算周期，利用两个乘法器并行地分别计算 以及 ，计
算 与 之和并在当前计算周期结束后更新存入寄存器 ，计算 和 的位操作结果并在当前计算周期结束后更新存入寄存器 ，计算 和 的位操作结果与寄存器 存储数据之和、并在当前计算周期结束后更新存入寄存器 ；
在第三个计算周期，利用两个乘法器并行地分别计算 以及 ，计算
与寄存器 存储数据之差并暂时赋值给 ，计算 与寄存器 存储数据之差并暂时赋值给 ，在当前周期结束后将 更新存入寄存器 ，在当前周期结束后将 更新存入寄存器 ；计算 与寄存器 存储数据的位操作结果并在当前周期结束后更新存入寄存器 ，计算 与寄存器 存储数据的位操作结果并在当前周期结束后更新存入寄存器 ；
在第四个计算周期，利用两个乘法器并行地分别计算 以及 ，计算
与 之和并在当前计算周期结束后更新存入寄存器 ，计算寄存器 存储数据与寄存器 存储数据之和、并在当前计算周期结束后更新存储入寄存器 ；计算 和 的位操作结果与寄存器 存储数据之差并在当前计算周期结束后更新存储在寄存器 ；
在第五个计算周期，利用一个乘法器计算 ，计算 减去寄存器 存储数据以及减去寄存器 存储数据的结果并暂时赋值给 ，计算 与寄存器 存储数据的位操作结果并暂时赋值给 ；计算寄存器 存储数据和寄存器 存储数据的位操作结果与之和作为所述乘积结果 。
6.根据权利要求5所述的数据处理方法，其特征在于，在基于Karatsuba算法求解乘数和 的乘积结果 的过程中：在第一个计算周期，将 作为高位部分、将 作为低位部分，直接执行二进制数拼接得到 和 的位操作结果；
在第二个计算周期，将 作为高位部分、将 作为低位部分，直接执行二进制数拼接得到 和 的位操作结果；
在第三个计算周期，对 左移64位并与寄存器 存储数据相加得到位操作结果，对左移64位并与寄存器 存储数据相加得到位操作结果；
在第四个计算周期，对 左移128位并与 相加得到位操作结果；
在第五个计算周期，将 左移64位并与寄存器 存储数据相加得到位操作结果，将寄存器 存储数据作为高位部分、将寄存器 存储数据作为低位部分执行二进制数拼接得到位操作结果。
7.根据权利要求5所述的数据处理方法，其特征在于，基于蒙哥马利模乘计算 与中间参数 的第二乘积结果 的方法包括：在第一个计算周期，利用两个乘法器并行地分别计算 以及 ，计算
与 之和并在当前计算周期结束后更新存入寄存器 以及寄存器 ；
在第二个计算周期，利用两个乘法器并行地分别计算 以及 ，计算
寄存器 存储数据左移64位与 相加后的结果并暂时赋值给 ，在当前计算周期结束后将 更新存入寄存器 ，计算 、寄存器 存储数据以及 之和并在当前计算周期结束后更新存入寄存器 ；
在第三个计算周期，利用两个乘法器并行地分别计算 以及 ，计算
与 之和左移192位的结果 ；将 与寄存器 存储数据，
以及寄存器 存储数据左移128位的结果相加得到的 ，并
在第四个计算周期，利用两个乘法器并行地分别计算 以及 ，计算
左移128位的结果，与寄存器 存储数据，以及 左移128位的结果相加得到的，并在当前计算周期结束后更新存入寄存器 ；
在第五个计算周期，利用两个乘法器并行地分别计算 以及 ，计算
与 之和左移192位的结果与寄存器 存储数据之和得到所述第二乘积结果 ；
其中， 包括 的0到63位， 包括 的64到127位， 包括 的128到191位， 包括的192到255位； 包括中间参数 的0到63位，包括中间参数 的64到127位， 包括中间参数 的128到191位， 包括中间参数 的192到255位。
8.根据权利要求5所述的数据处理方法，其特征在于，所述基于所述第三乘积结果 输出 的结果作为 的模乘结果，包括：当所述第一乘积结果 的低 位结果 ，且 时输出 ；
当所述第一乘积结果 的低 位结果 ，且 时，输出 ；
当所述第一乘积结果 的低 位结果 ，且 时，输出 ；
当所述第一乘积结果 的低 位结果 ，且 时，输出 ；
其中， 表示所述第三乘积结果 与寄存器 存储数据之和。
9.根据权利要求7所述的数据处理方法，其特征在于，用于实现所述数据处理方法的数据处理电路包括两个位宽为66bit的乘法器、第一加法器组、第二加法器组、包含多个寄存器的寄存器组、四个四选一多路选择器MUX1、MUX2、MUX3和MUX4、两个五选二多路选择器MUX5和MUX6、一个数据选择器MUX7以及控制器，所述控制器控制所有四选一多路选择器、五选二多路选择器、数据选择器和寄存器组；
MUX1的四个输入端分别获取模乘操作数 的四个子操作数，MUX2的四个输入端分别获取模乘操作数 的四个子操作数，MUX3的四个输入端分别获取模乘操作数 的四个子操作数，MUX4的四个输入端分别获取中间参数 的四个子操作数；
MUX5的五个输入端分别连接MUX1的输出端、MUX2的输出端、MUX3的输出端、MUX4的输出端以及所述寄存器组的输出端，MUX5的两个输出端连接所述第一加法器组；
MUX6的五个输入端分别连接MUX1的输出端、MUX2的输出端、所述第一加法器组的两个输出端以及所述寄存器组的输出端；MUX6的一个输出端分别连接两个乘法器的一个输入端，MUX6的另一个输出端分别连接两个乘法器的另一个输入端；
MUX7的三个输入端分别连接两个乘法器的输出端以及所述寄存器的输出端，MUX7引出两个输出端连接所述第二加法器组的两个输入端，MUX7还引出输出端连接所述寄存器组的输入端，所述第二加法器组的输出端连接所述寄存器组的输入端。
结合Karatsuba和蒙哥马利模乘的数据处理方法
技术领域
[0001] 本申请涉及数据加密领域，尤其是一种结合Karatsuba和蒙哥马利模乘的数据处理方法。
背景技术
[0002] 公钥密码体制使用不同的加密密钥和解密密钥，其具有运算速度快的优点，被广泛应用于各种高性能数据密集应用场景中，可以为互联网通信提供安全及完整性保障。常见的公钥密码体制的加密算法包括RSA加密算法、ECC（Elliptic Curve Cryptography，椭圆曲线密码学）加密算法、IBC（Identity‑Based Cryptograph，基于标识的密码学）加密算法等。其中，ECC加密算法比如SM2算法，IBC加密算法比如SM9算法。
[0003] 公钥密码体制的各种加密算法的计算最终都会分解成有限域上的基本算数运算，包括模加运算、模减运算、模乘运算和模逆运算等。其中，模乘运算和模逆运算对资源和时间的消耗远大于模加运算和模减运算，而模逆运算的被调用频率较低且通常可以通过多次调用模乘运算来实现，因此高效完成模乘运算是提高加密算法的算法速度的核心。在加密算法中，大整数模乘（Large Integer Modular Multiplication）是常见的模乘运算，也是对计算耗时和资源消耗最严重的基本算数运算。大整数模乘可以表示为 ，其中、、均为二进制的大整数，其运算性能往往直接影响整个加密算法的性能。
[0004] 在普通算法中，在计算模 时，利用的是带余除法，除法运算需要太多次乘法，计算复杂度较高，蒙哥马利（Montgomery）模乘通过将除法计算转化成简单的移位计算，可以大幅度提高大整数模乘的运算速度。但是，以公钥密码体制中操作数 和 常见的有256bit的情况为例，一次完整蒙哥马利模乘需要进行3次完整256bit*256bit二进制乘法，目前常见的实现包括：（1）使用1个256bit*256bit乘法器；（2）使用若干256bit*32bit乘法器和若干加法器；（3）使用若干64bit*64bit乘法器和若干加法器；（4）使用若干2bit*2bit乘法器和若干加法器。在上述各种实现方法中，使用大位宽的乘法器会增加电路面积，消耗较多的硬件资源，尤其是使用256bit*256bit乘法器时往往导致电路面积过大而无法被接受，使用小位宽的乘法器虽然可以减小电路面积，但会导致需要多次运算迭代，使得计算时间大大增加。因此目前在加密算法中引入蒙哥马利模乘虽然可以一定程度上优化加密算法的性能，但是计算效率还是不够理想。
发明内容
[0005] 本申请人针对上述问题及技术需求，提出了一种结合Karatsuba和蒙哥马利模乘的数据处理方法，本申请的技术方案如下：
[0006] 一种结合Karatsuba和蒙哥马利模乘的数据处理方法，该数据处理方法包括：
[0007] 获取两个模乘操作数 和 ，两个模乘操作数 和 的位宽均为 ；
[0008] 将两个模乘操作数 和 分别拆分为若干个 位宽的子操作数，通过模乘操作数和 拆分得到的各个子操作数以及子操作数的加法结果利用 位宽的乘法器、基于Karatsuba算法求解得到两个模乘操作数 和 的第一乘积结果 ，其中，乘法器的位宽满足子操作数的加法结果的位宽需求且小于预定阈值；
[0009] 基于蒙哥马利模乘计算第一乘积结果 的低 位结果 与中间参数 的第二乘积结果 ， ， ， 且 和 的最大公约数为1；
[0010] 将第二乘积结果 的低 位结果 以及位宽为 的模乘操作数 分别拆分为若干个 位宽的子操作数，通过 和模乘操作数 拆分得到的各个子操作数以及子操作数的加法结果利用 位宽的乘法器、基于Karatsuba算法求解得到 和模乘操作数 的第三乘积结果 ；
[0011] 基于第三乘积结果 输出 的结果作为 的模乘结果。
[0012] 本申请的有益技术效果是：
[0013] 本申请公开了一种结合Karatsuba和蒙哥马利模乘的数据处理方法，该方法结合Karatsuba和蒙哥马利模乘可以快速计算模乘的方法，Karatsuba可以加速大整数乘法的运算，且Karatsuba还可以得到想要的指定的计算位宽，通过小位宽的乘法器即可快速完成乘法运算，降低大整数乘法的计算复杂度，而且本申请在设计乘法器位宽时，直接预留进位，使得乘法运算和加法运算可以同步推进，从而可以优化整个数据处理过程的时序，进一步缩短计算耗时，从而可以在占用较小面积的基础上还可以有较少的计算耗时，电路面积与计算时间都有较优的表现。
[0014] 进一步的，在电路面积可接受的基础上，可以增加使用的乘法器结合并行运算设计进一步缩短计算耗时，具有较高的运算并行度，从而可以提高模乘运算的运算效率。
附图说明
[0015] 图1是本申请一个实施例的数据处理方法的方法流程图。
[0016] 图2是本申请一个实施例的数据处理方法的求解示意图。
[0017] 图3是一个实施例中用于实现本申请的数据处理方法的数据处理电路的电路结构图。
具体实施方式
[0018] 下面结合附图对本申请的具体实施方式做进一步说明。
[0019] 本申请公开了一种结合Karatsuba和蒙哥马利模乘的数据处理方法，该数据处理方法用于高效处理得到 的模乘结果，其中，模乘操作数 、和 都是二进制的大整数，所谓的大整数表示模乘操作数的位宽超过预设值，比如模乘操作数的位宽达到64bit或者达到256bit即称为大整数。该数据处理方法得到 的模乘结果的方法包括如下步骤，请参考图1所示的流程图以及图2所示的计算示意图：
[0020] 步骤110，获取两个模乘操作数 和 ，获取到的这两个模乘操作数 和 的位宽均为 ，模乘操作数 和 均为二进制的大整数，也即模乘操作数 和 的位宽 均超过预设值。
[0021] 步骤120，计算两个模乘操作数 和 的乘积记为第一乘积结果 。
[0022] 在本申请中，由于 和 均为大整数，直接计算 和 的全积较为耗时，因此为了降低计算复杂度，将两个模乘操作数 和 分别拆分为若干个 位宽的子操作数，每个子操作数包括相应的模乘操作数的连续 位的内容，且各个子操作数的内容连续而不重合。
[0023] 也即将大位宽的模乘操作数拆分为小位宽的子操作数，然后通过模乘操作数 和拆分得到的各个子操作数以及子操作数的加法结果利用 位宽的乘法器、基于Karatsuba算法求解得到两个模乘操作数 和 的第一乘积结果 。
[0024] 由于本申请将大位宽的模乘操作数拆分为小位宽的子操作数，然后以小位宽的子操作数以及子操作数的加法结果作为处理对象执行乘法运算，因此本申请使用的乘法器的位宽 小于预定阈值，该预定阈值可以自定义设置，也即本申请使用小位宽的乘法器即可，从而减小电路面积，而且乘法规模也较小，从而减少计算耗时。
[0025] 另外，由于本申请不仅要对子操作数执行乘法操作，而且要对子操作数的加法结果执行乘法操作，而子操作数的加法结果由多个子操作数执行加法操作得到，在执行加法操作过程中可能会产生进位，导致子操作数的加法结果的位宽大于子操作数的位宽 。因此为了适应子操作数的加法结果的位宽，本申请使用的乘法器的位宽 且满足子操作数的加法结果的位宽需求，从而可以为进位预留位宽，实现乘法运算与加法运算的同步推进，从而进一步优化计算时序，减少计算耗时。
[0026] 步骤130，基于蒙哥马利模乘计算第一乘积结果 的低 位结果 与中间参数 的第二乘积结果 。上述步骤120计算得到的第一乘积结果 包括高位部分的 以及低位部分的 ，仅取低 位结果 进入步骤130与中间参数 相乘，其中，中间参数， ， 且 和 的最大公约数为1。
[0027] 步骤140，计算第二乘积结果 的低 位结果 与模乘操作数 的乘积记为第三乘积结果 。
[0028] 上述步骤130计算得到的第二乘积结果 包括高位部分 和低位部分 ，高位部分 在计算结束后被丢弃，因此可以不计算它来节省操作，因此该步骤仅取低 位结果与模乘操作数 计算乘法结果。
[0029] 而与上述步骤120类似，该步骤中， 与 的位宽也都为 ， 与 也都是大整数，直接计算 与 的全积同样较为耗时。所以该步骤的计算方法与上述步骤120类似，将第二乘积结果 的低 位结果 以及位宽为 的模乘操作数 分别拆分为若干个 位宽的子操作数，通过 和 拆分得到的各个子操作数以及子操作数的加法结果利用 位宽的乘法器、基于Karatsuba算法求解得到 和模乘操作数 的第三乘积结果 。
[0030] 步骤150，基于第三乘积结果 输出 的结果，即作为 的模乘结果。在得到第三乘积结果 后需要与第一乘积结果 相加得到 ，而使用蒙哥马利模乘的目的是最后得到的 的低位部分 为零，这样对 进行移位操作即能得到最终的模乘结果。因此只需确定是否会通过 的低位部分 和 的低位部分 相加产生进位即可正确计算 的高位部分 来得到最终的模乘结果。通过验证可知，最终计算时并不需要添加 和 ，因为：（1）如果 ，那么会使第二乘积结果 ，继而会使第三乘积结果，因此 ，不会产生进位。（2）如果 ，则 一定是非零的二进制整数，因为结果要为零，此时 总是生成 的进位，那么只需要计算
即可。
[0031] 所以当 时 否则 。当计算得到的 时，输出作为模乘结果，否则输出 作为模乘结果。
[0032] 在本申请提供的方案中，使用Karatsuba算法与蒙哥马利模乘结合来计算的模乘结果，通过Karatsuba算法完成步骤120和步骤140两步中的大整数乘法运算，从而可以减少计算耗时。而且直接预留进位所需的位宽，使用满足子操作数的加法结果的位宽需求的乘法器来实现乘法运算，实现乘法运算与加法运算的同步推进，进一步减少计算耗时。
[0033] 在一个实施例中，针对现有加密算法常见的256bit操作数的应用场景，本申请提供的数据处理方法中两个模乘操作数 和 的位宽均为 ，对每个模乘操作数拆分得到的4个子操作数的位宽均为 。第二乘积结果 的低 位结果 以及模乘操作数 的位宽均为 ，对 拆分得到的4个子操作数的位宽均为 ，对模乘操作数 拆分得到的4个子操作数的位宽均为 。基于本申请提供的方法，对每个模乘操作数拆分得到的多个子操作数相加得到的加法结果的位宽最多为66bit，对 拆分得到的多个子操作数相加得到的加法结果的位宽最多为66bit，对模乘操作数 拆分得到的多个子操作数相加得到的加法结果的位宽最多为66bit。该数据处理方法使用的乘法器的位宽 ，相比于直接使用64bit位宽的乘法器，使用66bit的乘法器时可以直接存储乘数的进位。
[0034] 对于典型的模乘操作数 、和 都是256bit的场景，利用该实施例这种拆分成4个子操作数，使用66bit的乘法器实现的方法可以加快执行速度。同样针对模乘操作数 、和 都是256bit的场景：（1）当直接使用64bit的乘法器完成蒙哥马利模乘需要进行48个计算周期。（2）当基于FIOS(Finely Integrated Operand Scanning)、SOS(Separated Operand Scanning)、CIOS(Coarsely Integrated Operand Scanning)、FIPS(Finely Integrated Operand Scanning)、CIHS(Coarsely Integrated Hybird Scanning) 这五种不同类型的蒙哥马利扩展算法，使用64bit的乘法器完成模乘运算时，可以将计算耗时降低至38个计算周期。（3）在使用本申请的数据处理方法，结合Karatsuba算法与蒙哥马利模乘，并利用单个66bit的乘法器完成时，只需 个计算周期即可得到的模乘结果，其中， ，符号 表示向上取整。在取 的情况下
代入数据可计算得到可以将计算耗时降低至28个计算周期。
[0035] 在另一个实施例中，进一步的，该数据处理方法使用多个乘法器结合并行运算设计，可以进一步减小计算大整数模乘的计算耗时。基于该实施例结合Karatsuba算法与蒙哥马利模乘，并利用 个66bit的乘法器并行运算的场景，该数据处理方法通过个计算周期得到 。其中， 表示与乘法器的个数对应的额外计算周期数，是并行运算时不同电路器件必须增加的必要的等待周期，当使用的乘法器的个数不同的，所需的额外计算周期数也会存在不同。
[0036] 但是增加乘法器会增加电路面积，因此综合考虑计算耗时和电路面积，在一个实施例中，使用两个66bit的乘法器实现该数据处理方法。以取 、 为例，通过并行运算设计可以使得 ，最终总计只需16个计算周期即可。而对比同样使用两个乘法器的FIOS蒙哥马利扩展算法，其在最优情况下需要使用4个额外计算周期数。FIOS、SOS、CIOS依次需要28个计算周期、24个计算周期和24个计算周期。因此本申请中这种方法，并行度更高，可以使用更少的计算周期完成，且所需的额外计算周期数也是相对较小的。
[0037] 接下去，该实施例针对使用两个66bit的乘法器结合并行运算设计实现该数据处理方法的时序过程介绍如下：
[0038] 上述步骤120和步骤140的计算过程是相同的，该实施例以基于Karatsuba算法求解得到任意两个位宽均为256bit的乘数 和 的乘积结果 为例对这两种情况做统一描述。当乘数 和 分别为模乘操作数 和 时，对应得到的乘积结果 即为第一乘积结果。当乘数 和 分别为 和模乘操作数 时，对应得到的乘积结果 即为第三乘积结果 。
[0039] 在对乘数 和 拆分为子操作数时，对乘数 拆分得到的4个64bit的子操作数、 、 和 ，其中， 包括乘数 的0到63位， 包括乘数 的64到127位， 包括乘数的128到191位， 包括乘数 的192到255位。类似的，对乘数 拆分得到的4个64bit的子操作数 、 、 和 ，其中， 包括乘数 的0到63位， 包括乘数 的64到127位， 包括乘数 的128到191位， 包括乘数 的192到255位。
[0040] 计算乘数 的子操作数的加法结果包括： 、 、、 以及 。其中，在由子操作数计算得到 、 、 和
的过程中可能产生进位，所以 、 、 和 在加法产生的进位的作用下位宽最多为
65bit。而 又可能再产生进位，所以 在加法产生的进位的作用下位宽最多为66bit。
[0041] 类似的，计算乘数 的子操作数的加法结果包括： 、 、、 以及 。其中， 、 、 和 在加法产生的进位的作用下
位宽最多为65bit， 在加法产生的进位的作用下位宽最多为66bit。
[0042] 在完成对乘数 和 的拆分后，使用位宽 的乘法器计算乘数 的子操作数与乘数 的子操作数的乘积，以及使用位宽 的乘法器计算乘数 的子操作数的加法结果与乘数 的子操作数的加法结果的乘积，继而计算得到乘数 和 的乘积结果 。经过本申请的并行运算设计，通过五个计算周期即可以得到乘积结果 ，包括如下过程：
[0043] （1）在第一个计算周期，利用两个乘法器并行地分别计算 以及，计算 与 之和并在当前计算周期结束后更新存入寄存器 ，计算 和 的位操作结果并在当前计算周期结束后更新存入寄存器 。在一个实施例中，将 作为高位部分、 作为低位部分，执行二进制数拼接得到 和 的位操作结果，加快运算。
[0044] （2）在第二个计算周期，利用两个乘法器并行地分别计算 以及，计算 与 之和并在当前计算周期结束后更新存入寄存器 ，计算 和 的位操作结果并在当前计算周期结束后更新存入寄存器 。计算 和 的位操作结果与寄存器 存储数据之和、并在当前计算周期结束后更新存入寄存器 。这里的寄存器 存储数据即为第一个计算周期更新存入的数据。在一个实施例中，将 作为高位部分、将 作为低位部分，直接执行二进制数拼接得到 和 的位操作结果。
[0045] （3）在第三个计算周期，利用两个乘法器并行地分别计算 以及，计算 与寄存器 存储数据之差并暂时赋值给 ，计算 与寄存器 存储数据之差并暂时赋值给 。在当前周期结束后将 更新存入寄存器 ，在当前周期结束后将更新存入寄存器 。计算 与寄存器 存储数据的位操作结果并在当前周期结束后更新存入寄存器 ，计算 与寄存器 存储数据的位操作结果并在当前周期结束后更新存入寄存器 。
[0046] 在一个实施例中，对 左移64位并与寄存器 存储数据相加得到位操作结果，对左移64位并与寄存器 存储数据相加得到位操作结果。由于 与寄存器 存储数据的位操作结果可能产生进位，因此为了避免丢位，在该计算周期内执行逻辑运算得到所需的位操作结果，而不直接执行二进制数拼接。对于 与寄存器 存储数据的位操作结果同理。
[0047] （4）在第四个计算周期，利用两个乘法器并行地分别计算 以及。计算 与 之和并在当前计算周期结束后更新存入寄存器 ，计算寄存器存储数据与寄存器 存储数据之和、并在当前计算周期结束后更新存储入寄存器 ；计算和 的位操作结果与寄存器 存储数据之差并在当前计算周期结束后更新存储在寄存器 。在一个实施例中，对 左移128位并与 相加得到位操作结果，同样的，为了避免丢位，通过执行逻辑运算得到所需的位操作结果。
[0048] （5）在第五个计算周期，利用一个乘法器计算 ，计算 减去寄存器 存储数据以及减去寄存器 存储数据的结果并暂时赋值给 ，计算 与寄存器 存储数据的位操作结果并暂时赋值给 ；计算寄存器 存储数据和寄存器 存储数据的位操作结果与 之和作为乘积结果。
[0049] 在一个实施例中，将 左移64位并与寄存器 存储数据相加得到位操作结果，将寄存器 存储数据作为高位部分、将寄存器 存储数据作为低位部分执行二进制数拼接得到位操作结果。同理，为了避免丢位，通过执行逻辑运算得到 与寄存器 存储数据的位操作结果。而寄存器 存储数据与寄存器 存储数据的位操作结果不存在进位，因此可以直接执行二进制数拼接，以减少计算耗时。
[0050] 在上述过程中，暂时赋值的数据可以在当前计算周期中继续使用，而使用到的寄存器存储数据都是当前计算周期取出的、上一个计算周期存入寄存器中的数据。各个计算周期内，除了乘法操作之外，没有数据依赖关系的其他计算步骤也都可以并行操作。
[0051] 在一个实施例中，在使用两个66bit的乘法器结合并行运算设计的基础上，上述步骤130基于蒙哥马利模乘计算 与中间参数 的第二乘积结果 需要使用到5个计算周期，在该步骤中，同样需要对 和 进行拆分，包括将256bit位宽的 拆分为 、 、 和 ，其中， 包括 的0到63位， 包括 的64到127位， 包括 的128到191位， 包括 的192到255位。将中间参数 拆分为 、 、 和 ， 包括中间参数 的0到63位，包括中间参数 的64到127位， 包括中间参数 的128到191位， 包括中间参数 的192到255位。则通过5个计算周期计算得到第二乘积结果 的过程包括：
[0052] （1）在第一个计算周期，利用两个乘法器并行地分别计算 以及，计算 与 之和并在当前计算周期结束后更新存入寄存器 以及寄存器 。
[0053] （2）在第二个计算周期，利用两个乘法器并行地分别计算 以及，计算寄存器 存储数据左移64位与 相加后的结果并暂时赋值给 ，在当前计算周期结束后将 更新存入寄存器 ，计算 、寄存器 存储数据以及 之和并在当前计算周期结束后更新存入寄存器 。
[0054] （3）在第三个计算周期，利用两个乘法器并行地分别计算 以及，计算 与 之和左移192位的结果 ，将 与寄存器 存储数据，以及寄存器 存储数据左移128位的结果相加得到的
，并在当前计算周期结束后更新存入寄存器 。
[0055] （4）在第四个计算周期，利用两个乘法器并行地分别计算 以及，计算左移128位的结果，与寄存器 存储数据，以及 左移128位的结果相加得到的，并在当前计算周期结束后更新存入寄存器 。
[0056] （5）在第五个计算周期，利用两个乘法器并行地分别计算 以及，计算 与 之和左移192位的结果与寄存器 存储数据之和得到所述第二乘积结果 。
[0057] 基于上述实施例提供的利用两个66bit实现的并行运算过程，上述步骤150利用寄存器存储的数据输出所需的模乘结果的方法包括：当第一乘积结果 的低 位结果 ，且 时输出 。当第一乘积结果 的低 位结果 ，且 时，输出 。当第一乘积结果 的低 位结果 ，且 时，输出 。当
第一乘积结果 的低 位结果 ，且 时，输出 。其中， 表示第
三乘积结果 与寄存器 存储数据之和。
[0058] 在经过5个计算周期得到第一乘积结果 ，此时需要先将第一乘积结果 存入寄存器 中，由此会产生额外计算周期数。然后在下一个计算周期再从寄存器 中取出第一乘积结果 的低 位结果 使用并再经过5个计算周期得到第二乘积结果 ，最后经过5个计算周期得到第三乘积结果 后，乘法部分已经全部计算完成，但是这个时候还需要执行若干个加法操作得到最终的模乘结果，但是目前的加法器已经都参与过计算，不能立刻再进行输入，这样会覆盖掉之前的结果，所以也需要先将第三乘积结果 更新存入寄存器 中，再放到下个周期进行计算，由此又产生了额外计算周期数。所以在使用两个66bit乘法器并行运算实现该数据处理方法时，总共产生了2个额外计算周期数，总计需要16个计算周期。在最后一个计算周期中，可以将寄存器中存储的第三乘积结果 取出并按上述逻辑进行加法运算后最终输出模乘结果。
[0059] 基于上述实施例描述的并行运算过程，该实施例对16个计算周期的计算过程分别描述如下：
[0060]
[0061]
[0062]
[0063] 上述16个计算周期中，计算周期1 5中的乘数 和 分别为模乘操作数 和 ，对~应得到的乘积结果 即为第一乘积结果 存入寄存器 。计算周期6将寄存器 中的数据读出得到 ，计算周期6 10基于蒙哥马利模乘计算 与中间参数 的第二乘积结果 并存入~
寄存器 。计算周期11将寄存器 中的数据读出得到 ，计算周期11 15中的乘数 和 分~
别为 和 ，对应得到的乘积结果 即为第三乘积结果 存入寄存器 。计算周期16通过多次加法操作将可能输出的多种结果均计算出来并暂时赋值给 、 、 、 ，最终输出其中一个所需的值作为模乘结果。在上述时序列表中，符号 表示在计算周期结束后更新存入对应的寄存器，符号 表示将计算结果暂时赋值给对应的参数以供当前计算周期后续操作步骤使用，符号 为左移运算符， 表示执行 计算 暂时赋
值给 ，然后在当前计算周期结束后执行 将 更新存入寄存器 ，其他依次类推。
[0064] 在一个实施例中，用于实现上述实施例的数据处理方法的数据处理电路请参考图3，包括两个位宽为66bit的乘法器M1和M2，还包括第一加法器组、第二加法器组、包含多个寄存器的寄存器组、四个四选一多路选择器MUX1、MUX2、MUX3和MUX4、两个五选二多路选择器MUX5和MUX6、一个数据选择器MUX7以及控制器，控制器控制所有四选一多路选择器、五选二多路选择器、数据选择器和寄存器组。
[0065] MUX1的四个输入端分别获取模乘操作数 的四个子操作数，MUX2的四个输入端分别获取模乘操作数 的四个子操作数，MUX3的四个输入端分别获取模乘操作数 的四个子操作数，MUX4的四个输入端分别获取中间参数 的四个子操作数。
[0066] MUX5的五个输入端分别连接MUX1的输出端、MUX2的输出端、MUX3的输出端、MUX4的输出端以及寄存器组的输出端，MUX5的两个输出端连接第一加法器组。
[0067] MUX6的五个输入端分别连接MUX1的输出端、MUX2的输出端、第一加法器组的两个输出端以及寄存器组的输出端。MUX6的一个输出端分别连接两个乘法器的一个输入端，MUX6的另一个输出端分别连接两个乘法器的另一个输入端。
[0068] MUX7的三个输入端分别连接两个乘法器的输出端以及寄存器的输出端，MUX7引出两个输出端连接第二加法器组的两个输入端，MUX7还引出输出端连接寄存器组的输入端，第二加法器组的输出端连接寄存器组的输入端。
[0069] 基于图3所示的数据处理电路，输入的数据首先进入第一加法器组进行处理，输出的结果通过MUX6进入到两个66bit的乘法器中做并行的乘法运算，得到的一部分乘法结果存入寄存器组中的相应寄存器中，等待下次返回给输入。另一部分乘法结果进入第二加法器组中进行加法运算，得到的加法结果存入寄存器组中的相应寄存器中等待下次返回给输入。
[0070] 在一个实施例中，第一加法器组包括4个64bit的加法器。第二加法器组包括2个132bit的加法器、1个256bit的加法器和1个384bit的加法器，该实施例提供的数据处理电路可以在电路面积可接受范围内，使用最少的寄存器和最少的加法器。
[0071] 以上所述的仅是本申请的优选实施方式，本申请不限于以上实施例。可以理解，本领域技术人员在不脱离本申请的精神和构思的前提下直接导出或联想到的其他改进和变化，均应认为包含在本申请的保护范围之内。
