流水线型的蒙哥马利模乘运算方法论文和设计-胡世文

全文摘要

本发明公开了一种流水线型的蒙哥马利模乘运算方法，涉及数据密码算法技术领域，采用流水线型方式来提升蒙哥马利模乘算法性能，增加了单个蒙哥马利模乘器的吞吐量，在吞吐量相同的情况下，本发明比传统使用多个蒙哥马利模乘器的方法消耗更少的硬件资源和面积。如此使本发明数十倍地提升了单位时间里的模乘运算个数，使得本发明比非流水线型的蒙哥马利模乘器具有更高的性能\/资源比。同时，使用流水线型的蒙哥马利模乘器的非对称密钥算法硬件可以用更少的硬件资源达到更高的性能，提高任意长度的蒙哥马利模乘运算的吞吐量。

主设计要求

1.一种流水线型的蒙哥马利模乘运算方法，其特征在于：输入为S和T，输出S*T*2-R模P，其中，在非对称密钥算法中，S,T,和P均为R位的大整数，其中P为素数；算法分为两部分：第一部分是S与T相乘的普通乘法步骤，得到一个2R位的乘积；第二部分是余下的步骤，即将2R位的乘积约减成为R位的最终结果S*T*2-R模P；在这个过程中，R可分解为L*K，以循环K次，每次处理L位的数据；用于实现蒙哥马利模乘运算的硬件乘法器的输入位宽分别为U和V，远小于R；蒙哥马利模乘运算过程：输入：P＆lt;2R,0≤S,T＆lt;P,R=L*K,K0=-P-1模2L输出：S*T*2-R模P1）Z=S*T；循环K次：2）T1=Z模2L；3）Y=T1*K0模2L；4）T2=Y*P；5）T3=(Z+T2)；6）Z=T3\/2L；循环结束；7）如果Z≥P，则X=Z–P；否则X=Z；返回X；整个计算过程分为三个乘法步骤和两个约减步骤，乘法步骤1：通过使用多个输入分别为U和V位的小位宽全流水线型乘法器实现本步骤；输入数据，其中，表示向上取整；则乘法运算式：乘法步骤2：该步骤将乘法步骤1中小位宽全流水线型乘法器的相乘结果按位对齐，获得多个不同长度的整数，并将各整数分别存入不同寄存器中；由于硬件易于实现对齐，即把乘法器输出结果连接至相应寄存器的相应输入，因此该步骤只需要一个时钟周期；乘法步骤3：该步骤将乘法步骤2中获得的所有整数相加，最后得到2*R位的乘法结果；约减步骤1：该步骤采用K个流水线型蒙哥马利约减单元，每一次将结果约减L位；已知参数为P=∑Bi*2i，为椭圆曲线相应素数，其中i=（0,1,2,…,R)；Bi∈(-1,0,1)，以及K0=-P-1模2L；其中，一个流水线型蒙哥马利约减单元将乘法器输出结果从B*L位约减为(B-1)*L位的过程包含以下步骤：其中，B=2K,2K-1,…,K+1，a）对Z进行模2L运算，即取Z的低L位得到T1；b）计算Y=（T1*K0）模2L，计算T1乘K0使用一个全流水的乘法器，两个输入均为L位，输出为2L位，然后取该乘法器结果的低L位得到Y；c）计算T2=Y*P，得到T2=∑Bi*Y*2i，该处乘法使用移位相加实现：每一部分都是Y左移i位，然后添加符号位，最后将这些部分相加得到T2；d）Z与T2相加，得到T3；e）计算Z=T3\/2L，即将T3右移L位，运算结果用于更新Z；其中，步骤a）和步骤e）均仅需单时钟周期即可完成，步骤b）、c）和步骤d）需要若干个时钟周期完成；为了实现流水线型蒙哥马利约减单元，每一个时钟周期都保存输出结果到相应寄存器中；一个蒙哥马利约减器包含K个流水线型蒙哥马利约减单元，使得整个蒙哥马利约减器都支持流水线型；约减步骤2：该步骤通过相应的模减模块确保最终结果在[1,P)范围内，如果上一步骤的结果Z≥P，则输出结果X=Z-P；否则X=Z。

设计方案

1.一种流水线型的蒙哥马利模乘运算方法，其特征在于：输入为S和T，输出S*T*2^{-R<\/sup>模P，其中，在非对称密钥算法中，S, T,和P均为R位的大整数，其中P为素数；算法分为两部分：第一部分是S与T相乘的普通乘法步骤，得到一个2R位的乘积；第二部分是余下的步骤，即将2R位的乘积约减成为R位的最终结果S*T*2 ^{-R<\/sup>模 P；在这个过程中，R可分解为L* K，以循环K次，每次处理L位的数据；}}

用于实现蒙哥马利模乘运算的硬件乘法器的输入位宽分别为U和V，远小于R；

蒙哥马利模乘运算过程：

输入：P<2^{R<\/sup>,0≤S,T<P, R=L*K, K0=-P ^{-1<\/sup> 模 2 ^L<\/sup>}}

输出：S*T*2^{-R<\/sup> 模 P}

1）Z=S*T；循环K次：2）T1=Z模2^{L<\/sup>；3）Y=T1*K0模2^{L<\/sup>；4）T2=Y*P；5）T3=(Z+T2)；6）Z=T3\/2^{L<\/sup>；循环结束；7）如果Z≥P，则X=Z–P；否则X=Z；返回X；}}}

整个计算过程分为三个乘法步骤和两个约减步骤，

乘法步骤1：通过使用多个输入分别为U和V位的小位宽全流水线型乘法器实现本步骤；输入数据设计说明书

技术领域

本发明涉及数据密码算法技术领域，具体涉及一种蒙哥马利模乘运算方法及计算装置。

背景技术

信息的安全保障基于安全算法，安全算法有一类是非对称密钥算法。非对称密钥算法的优点是安全性高，缺点是加密速度比分组密码慢很多，所以人们一直在研究如何提升非对称密钥算法的运算速度。目前，非对称密钥算法主要有两种，一是RSA，二是椭圆曲线密码ECC(Elliptic Curve Cryptography)，上述两种公钥密码算法都需要使用模乘计算(S*T mod P)。

模乘算法中效率高、便于实现的算法是蒙哥马利模乘算法。蒙哥马利模乘使用过程中需要把普通数A转换成蒙哥马利数S’=S*R mod P。为使两个蒙哥马利数S’=S*R mod P和T’=T*R mod P相乘的结果为(S*T)’=(S*T)*R mod P，蒙哥马利模乘运算定义为MM(S’,T’) = (S’* T’) * R ^{-1<\/sup> mod P。R通常为一个便于约减的整数，比如2 ^{32<\/sup>或2^{64<\/sup>等。}}}

目前，大多数的硬件模乘器都是基于蒙哥马利算法及其变形算法设计的。但是它们大都通过牺牲性能来节省资源和面积，造成系统性价比的下降以及能耗的上升。单个蒙哥马利模乘运算耗时过长，因此单个蒙哥马利模乘器如果不支持流水线型，很难提高其单位时间里模乘运算个数，即其吞吐量。一种可行的性能提升方案是在一个计算装置中使用多个蒙哥马利模乘器，但是这会造成硬件资源、面积和能耗的成倍增加。

发明内容

本发明针对现有技术的缺陷，提供一种可大幅提升单位时间里的模乘运算个数、可以更少的硬件资源达到更高的性能、可提高任意长度的蒙哥马利模乘运算的吞吐量的流水线型的蒙哥马利模乘运算方法。

为解决上述技术问题，本发明采用如下技术方案：一种流水线型的蒙哥马利模乘运算方法，其特征在于：输入为S和T，输出S*T*2^{-R<\/sup>模 P，其中，在非对称密钥算法中，S、 T和P均为R位的大整数，其中P为素数；算法分为两部分：第一部分是S与T相乘的普通乘法步骤，得到一个2R位的乘积；第二部分是余下的步骤，即将2R位的乘积约减成为R位的最终结果S*T*2 ^{-R<\/sup>模 P。在这个过程中，R可以分解为L* K，这样可以循环K次，每次处理L位的数据。}}

并且，用于实现蒙哥马利模乘运算的硬件乘法器的输入位宽分别为U和V，远小于R。

蒙哥马利模乘运算过程：

输入：P<2^{R<\/sup>,0≤S,T<P, R=L*K, K0=-P ^{-1<\/sup> 模 2 ^L<\/sup>}}

输出：S*T*2^{-R<\/sup> 模 P}

1）Z=S*T；循环K次：2）T1=Z模2^{L<\/sup>；3）Y=T1*K0模2^{L<\/sup>；4）T2=Y*P；5）T3=(Z+T2)；6）Z=T3\/2^{L<\/sup>；循环结束；7）如果Z≥P，则X=Z–P；否则X=Z；返回X。}}}

整个计算过程分为三个乘法步骤和两个约减步骤，

乘法步骤1：通过使用多个输入分别为U和V位的小位宽全流水线型乘法器实现本步骤；输入数据设计图

流水线型的蒙哥马利模乘运算方法论文和设计

流水线型的蒙哥马利模乘运算方法论文和设计-胡世文

全文摘要

主设计要求

设计方案

相关信息详情

猜你喜欢