专利申请报告

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

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

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

4、的一些步骤。下面是ECDS似体的算法。ECDS解名的生成：输入：参数组D (q,FR,S,a,b,P,n,h),私钥d ,消息m。输出：签名(r,s) o(1)选才?k 1,n 10(2)计算kP (xi, yi),并将xi转换为整数xi。(3)计算r ximodn。若r 0 ,则跳至步骤(1)。(4)计算 e H (m)。(5)计算s k 1(e dr) mod n 0若s 0 ,则跳至步骤(1)。(6)返回(r,s)。ECDS解名的验证：输入：参数组D (q,FR,S,a,b,P,n,h),公钥Q,消息m,签名(r,s)输出：判断签名是否合法。(1)检验r和s是否区间1,n 1内的整数。若

5、任何一个检验失败，则 返回(”拒绝该签名”)。(2)计算 e H(m)。(3)计算 w s 1 mod n。(4) 计算 u1 ewmod n 和 u2 rw mod n。(5)计算 X u1P u2Q。(6)若X ,则返回(“拒绝该签名”)。(7)将X的横坐标x1转换为整数x1 ;计算v xmodn。(8)若v r ,则返回(“接收该签名”)；否则，返回(”拒绝该签名”)。ECDS签名生成算法中的第五步和ECDS筮名验证算中的第四步都需要用到 素数域上的乘法。根据附图1所示，为了满足密码算法的安全性，密钥等参数的 位宽至少要在160bit以上，而160bit位宽以上的素域乘法就是一些大整数的

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

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

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

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

10、宽的整数倍，且位宽l最大值最好不要超过50bit ,否 则，时序电路的时钟频率会很低，实验中甚至无法达到100MHz确定分解位宽l之后，根据大整数A和B的实际位宽长度进行高位补零直至成为位宽l的整数倍。 至此根据本发明中附图3所示，将输入的位宽为L的大整数A和位宽为S的大整 数B分解成位长度相等且等于l的小整数An, An 1.A3,A2,A和Bm,Bm1&,B2,B" 暂存在FPG秋部的寄存器中，不妨设n m。接着，被分解的小整数 An, A 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在确定了乘法矩阵和矩 阵中每列的元素后，便可把先前存储在寄存器中的An, A i.A3,A2,Ai和 Bm,Bm >.B3,B2,B1依次做l*l位宽的乘法，求得矩阵

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

13、和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+力*l ,这刚好对应着大整数A和B 的乘法结果的总位宽（m+n * l o本发明正式基于这一点，并结合 verilog硬件 编程语言里特殊的位拼接运算发明了这种适用于FPGA勺大整数乘法算法。交错列和的具体算法遵循以下步骤：先将寄存器中第

14、一列A列元素的低l位做加法，得到结果的低l位就被看做交错列和La,高位被看做是进位Ca,事实上，A 列只有一个21位宽长度的元素AiBi,因此ABi的低l就是交错列和La,而进位 Ca=0；再将寄存器中A列元素的高1位和B列元素的低1位以及进位Ca做加法运 算，得到结果的低1位便作为交错列和Lab,结果的高位看成进位Cab,以此类推， 每次加法运算后得到一个交错列和和一个进位， 直到K列的高1位和进位Cjk做加 法直接得到1位的交错列和Lk ,理论上不会产生新的进位。可以看出，计算交错 列和的步骤主要是由多个1位数据间的加法组成的。计算完所有的交错列和，并 将其保存在寄存器中。如果之前计算矩阵

15、列中的元素AjBk时，采用的是按周期每次完成部分AjBk运算，那么可以在每次求得相邻两列所有的元素后便做一次 相应的交错列和加法运算。最后将所有的交错列和Lj做位拼接运算，直接得到m+n位结果 Lk , Ljk , Lij .Lab，La,也就是大整数A和B的乘法结果。这种位拼接运算在FPGA 中是非常易于实现的，同时也是 FPG阳算的特点之一。综上，在FPG9我们其实只做了三种简单的运算：1位宽的乘法运算，1位 的加法运算和一个位拼接运算。在运算量方面，1位宽的乘法运算一共有 m*n个， 1位的加法运算一共有2mn-3个。在FPGAS验中，将位宽长度近200的两个大整 数做乘法，如果采用将两个大整数直接相乘的办法去实现，则乘法电路时钟频率最高只能达到 30MHZ而采用本文提出的算法可根据1的大小将频率提高到100MHz200MHz解决了文中所述的FPG9大整数乘法运算效率低的问题。说明书附图攻破需要的时闾JRSA密相长度ECC密翎长度v密相长度比.（单位士 M1FE年）