专利申请报告

1、姓名：郭政明 学号： 06一、发明名称 一种适用于FPG故现的大整数乘法二、现有技术当前的密码体制一般可划分为两种类型，即对称密码体制和公钥密码体制。对称密钥体制需要通信双方A 和 B 共享同一密钥K， 并且要保证A 和 B 在协商密钥的时候， 信道是保密且保真的。 这就导致了它的密钥分发的问题和密钥的管理问题， 除此之外由于两个或多个实体共享密钥， 所以对称密钥体制不能实现用于认证和不可否认服务的数字签名。与对称密钥体制不同， 公钥密码体制仅要求密钥的交换是保真的， 并不要求其是保密的。每个实体选择一个密钥对(公钥，私钥) ，其中公钥对外是公开的，私钥自己保密， 这种密钥对需具备一个特点：

2、仅由公钥不能计算出私钥。 由于每一个实体都具有唯一的私钥， 因此可以提供数据源和数据完整性的认证以及不可否认性服务。这样，公钥密码圆满地解决了上述对称密码面临的三个问题。在公钥加密机制中，虽然RSA是目前主流的加密机制，但是RSA目前却面临 着越来越严重的来自安全方面的挑战。 第六届国际密码学会议对应用于公钥密码系统的加密算法推荐了两种：RSA算法和ECCB法。RSAJJ法的特点之一是数学 原理简单， 在工程应用中比较易于实现， 但它的单位安全强度相对较低。 椭圆曲 线密码算法建立在深奥和复杂的数学理论之上， 它的单位安全强度相对较高。 这 两种算法安全强度比较如附图 1 所示。需要指出的是，

3、由于ECC勺复杂度较高，它的运算通常比较慢。需要找到一 种用硬件来实现ECCg码体制的方案去提高运算速度。ECCg码体制主要是由有 限域层、 椭圆曲线层、 椭圆曲线密码协议层和一些特殊功能算法组成的见附图 2， 其中有限域是基础，因此首先要找到一种适合硬件来实现的有限域。有限域包括二进制域和素数域。二进制域里的元素都是用 0 和 1 表示，而构成二进制域有一种方法是采用正规基表示法，在正规基表示法下域中元素的加法、减法以及平方开方运算分别对应异或和移位操作，而这在硬件中如FPGA非常容易实现的。 但是即便我们作此选择， 在椭圆曲线密码协议中， 除了二进制 域正规基下的运算之外，还有一部分是素数

4、域的运算，主要是ECDS做字签名算 法里的一些步骤。下面是ECDS似体的算法。ECDS解名的生成：输入：参数组 D (q, FR, S,a,b, P, n, h) ，私钥 d ，消息 m 。输出：签名 (r,s) 。选择 k 1,n 1 。(2)计算kP (xi, yi),并将xi转换为整数xi。计算 r x1 modn 。若 r 0 ，则跳至步骤 (1) 。计算 e H (m) 。计算 s k 1(e dr) mod n 。若 s 0 ，则跳至步骤 (1) 。返回 (r,s) 。ECDS解名的验证：输入：参数组D (q,FR,S,a,b,P,n,h),公钥Q,消息m,签名(r,s)。输出：判

5、断签名是否合法。(1)检验r和s是否区间1,n 1内的整数。若任何一个检验失败，则 返回(“拒绝该签名”) 。计算eH(m) 。计算ws 1 mod n 。计算u1ew mod n 和u2 rw mod n 。计算Xu1P u2Q 。若 X ，则返回(“拒绝该签名”) 。将 X 的横坐标x1 转换为整数x1 ；计算v x1 modn 。若 v r ， 则返回 (“接收该签名”) ； 否则， 返回 (“拒绝该签名”) 。ECDS签名生成算法中的第五步和ECDS筮名验证算中的第四步都需要用到素数域上的乘法。 根据附图 1 所示， 为了满足密码算法的安全性， 密钥等参数的位宽至少要在160bit 以

6、上， 而 160bit 位宽以上的素域乘法就是一些大整数的乘法运算，在FPGAM如果不采用特殊算法直接做160bit位宽以上的大整数乘法，会造成时钟主频过低，综合出的频率最高不会超过 50MHz进而会影响整个ECDSA 签名的性能。如果不能找到一种好的FPG故现方法来提高大整数的乘法运算效率，那么将无法体现出ECCft二进制域正规基表示下的硬件实现优势。三、发明内容1 发明目的鉴于上述存在的问题，本发明的目的是提供一种适用于FPGAS现的大整数乘法算法，这种算法在FPG/fr实现的速度很快，可以解决上述问题。2技术解决方案本算法将大整数A和B间的乘法分成五个步骤进行，分别是A:做大整数分解运算

7、，将乘数A和被乘数B分解成位长度相等且等于l的小整数 An,An 1.A,4,A1 和 Bm,Bm1.B3, B2,B1，为了方便说明不妨设 A m。B：排列乘法矩阵，将被分解的小整数An,An 1.A3,A2,A和Bm,Bm1&B,B1之间按乘法矩阵的规则排列组合。C:做小整数乘法运算，将矩阵中被组合在一起的小整数Aj,Bk做乘积AjBk ,其中 j 1,n,k 1,m 。D:做小整数加法运算，将矩阵相邻列在位宽上重合的部分做带进位相加，得到交错列和Lj 。E:做位拼接运算，将所有的交错列和做一次位拼接运算Lj,直接得到大整数A和B的乘积。从算法步骤中可以看出，整个大整数A和B的乘法运算主要

8、被分解成长度为 l 的小数乘法运算，和长度为 l 的小整数加法运算以及位拼接运算，这三种运算在FPG/fr的运算速度是非常快的，因此通过合理的设计，由这三种运算组成的 大整数乘法可以解决之前所述的问题。3技术效果从算法步骤中可以看出，整个大整数A和B的乘法运算主要被分解成长度为 l 的小数乘法运算，和长度为 l 的小整数加法运算以及位拼接运算，这三种运算在FPG/fr的运算速度是非常快的，因此通过合理的设计，由这三种运算组成的 大整数乘法可以解决之前所述的问题。四、附图及附图的简单说明图1为公钥体制中RS用口 ECCe全密钥长度的比较图。图 2 为椭圆曲线密码体制的组成结构图。图 3 为本发明

9、中大整数A 和 B 的分解流程图。图 4 为本发明中乘法矩阵的结构示意图。图 5 为本发明中交错列求和过程的示意图。五、具体实施方式假设我们需要在FPG/fr做大整数A和B的乘法运算，那么根据本文所发明 的算法，需要先将大整数 A和B做分解运算见附图3。一般来说，大整数的位数 都在百位级或以上，对于一款性能尚可的 FPGAfB言，它内部集成的DSP模块里 都带有众多固定位宽的乘法单元，但是位宽较小如 9bit*9bit 。理论上，大整数A和B的分解位宽l越小，整个乘法运算速度将越快，但同时占用的资源也会比 较多，相反大整数A和B的分解位宽l越大，整个乘法的运算速度将会降低，但 用的资源也相对较

10、少。原则上，为了节省FPG秋部的DS睐法单元，位宽l的选 择应该为DS噪法单元位宽的整数倍，且位宽l最大值最好不要超过50bit ,否 则，时序电路的时钟频率会很低，实验中甚至无法达到100MHz确定分解位宽l 之后，根据大整数A和B的实际位宽长度进行高位补零直至成为位宽l的整数倍。 至此根据本发明中附图3所示，将输入的位宽为L的大整数A和位宽为S的大整 数B分解成位长度相等且等于l的小整数An,An 1A3,A2,A和Bm, Bm1&后出并 暂存在FPG秋部的寄存器中，不妨设n m。接着，被分解的小整数 An, An 1.A3A, Ai和Bm,Bm 1.B3, B2,Bi需按照附图4 所示的

11、排列规则排列出一乘法矩阵。 从图上可以看出， 乘法矩阵里的元素都是由小 整 数 An,An 1.A3,A2,A1 和 Bm,Bm 1.B3, B2,B1 的 乘 积 项 AjBk 组 成 的 ，j 1, n, k 1,m ，乘积项 AjBk 的位宽是 2l 。实际情况中，对于具体的大整数A和 B， m 和 n 之间的数值关系是固定的， 而乘法矩阵每一列的元素也会随之确定，为了方便说明附图4中假设m=n-2,从低位到高位，列按照 A,B,C,DK的顺序 排列，且矩阵的总列数为 m+n-1,附图4中，K=m+n-1在确定了乘法矩阵和矩 阵 中每 列 的 元 素后 ， 便可把 先前 存储 在 寄存器

12、 中 的 An, An 1.A3,A2,A1 和 Bm,Bm 1B3,B2,B1依次做l*l位宽的乘法，求得矩阵列中的元素 AjBk。可根据资 源多少的实际情况选择一次性完成所有的Aj Bk运算，或是按周期每次完成部分AjBk运算。并将求得的AjBk运算结果存入FPG秋的寄存器中。再下一步是做交错列的加法运算。 值得提出的是， 本发明中的附图 4 并不能 真实的反应矩阵里各个列之间的关系。 对于附图 4 中相邻两列的数据， 如果将其 值映射到大整数A和B的最终乘法结果上来，会发现其实列与列之间并非真正意 义的相邻，或是说相切，而是相互交错。附图 5 给出了列与列之间真实的情况：A列里元素的低l

13、位数据相对其它列独立，但是A列的高l位数据却和B列的低l位 数据重叠，同样，B列的高l位又与C列的低l位重叠最后一列K列的低l位 和 J 列的高 l 位重叠， K 列的高 l 位相对其它列独立。除了第一列的低l 位和最后一列的高 l 位是与其它列相互独立之外，其余列间都是重叠交错的。附图 4 中， 总列数K=m+n-1,其中交错白列数为（m+n-1） -1=m+n-2个，且每个交错列的位 宽都是l,因此交错列的总位宽为（m+n-2） * l,如果把A列的低l位和K列的 高l位算人其中，那么交错列的总位宽为（m+3*l ,这刚好对应着大整数A和B 的乘法结果的总位宽（m+n） * l 。本发明正

14、式基于这一点，并结合verilog 硬件编程语言里特殊的位拼接运算发明了这种适用于FPGA勺大整数乘法算法。交错列和的具体算法遵循以下步骤：先将寄存器中第一列 A 列元素的低l 位做加法，得到结果的低l 位就被看做交错列和 LA, 高位被看做是进位ca ，事实上，A列只有一个2l位宽长度的元素A1B1,因此A1B1的低l就是交错列和La,而进位 Ca=0；再将寄存器中A列元素的高l位和B列元素的低l位以及进位Ca做加法运 算，得到结果的低l 位便作为交错列和L AB , 结果的高位看成进位cab ，以此类推，每次加法运算后得到一个交错列和和一个进位，直到K列的高l位和进位 染做加法直接得到 l 位的交错列和LK ， 理论上不会产生新的进位。 可以看出， 计算交错列和的步骤主要是由多个l 位数据间的加法组成的。计算完所有的交错列和，并将其保存在寄存器中。如果之前计算矩阵列中的元素AjBk 时，采用的是按周期每次完成部分AjBk运算，那么可以在每次求得相邻两列所有的元素后便做一次 相应的交错列和加法运算。最后将所有的交错列和 Lj 做位拼接运算 ， 直接得到 m+n 位结果 Lk , Ljk , LjjLab，La,也就是大整数A和B的乘法结果。这种位拼接运算在FPGA 中是非常易于实现的，同时也是 FPGA!算的特点之一。综上，在FPG冲我们其实只做了三