专利申请报告.doc

专利申请报告姓名：郭政明 学号：0849390086一、发明名称 一种适用于FPGA实现的大整数乘法二、现有技术当前的密码体制一般可划分为两种类型，即对称密码体制和公钥密码体制。对称密钥体制需要通信双方A和B共享同一密钥K，并且要保证A和B在协商密钥的时候，信道是保密且保真的。这就导致了它的密钥分发的问题和密钥的管理问题，除此之外由于两个或多个实体共享密钥，所以对称密钥体制不能实现用于认证和不可否认服务的数字签名。与对称密钥体制不同，公钥密码体制仅要求密钥的交换是保真的，并不要求其是保密的。每个实体选择一个密钥对（公钥，私钥），其中公钥对外是公开的，私钥自己保密，这种密钥对需具备一个特点：仅由公钥不能计算出私钥。由于每一个实体都具有唯一的私钥，因此可以提供数据源和数据完整性的认证以及不可否认性服务。这样，公钥密码圆满地解决了上述对称密码面临的三个问题。在公钥加密机制中，虽然RSA是目前主流的加密机制，但是RSA目前却面临着越来越严重的来自安全方面的挑战。第六届国际密码学会议对应用于公钥密码系统的加密算法推荐了两种： RSA算法和ECC算法。RSA算法的特点之一是数学原理简单，在工程应用中比较易于实现，但它的单位安全强度相对较低。椭圆曲线密码算法建立在深奥和复杂的数学理论之上，它的单位安全强度相对较高。这两种算法安全强度比较如附图1所示。需要指出的是，由于ECC的复杂度较高，它的运算通常比较慢。需要找到一种用硬件来实现ECC密码体制的方案去提高运算速度。ECC密码体制主要是由有限域层、椭圆曲线层、椭圆曲线密码协议层和一些特殊功能算法组成的见附图2，其中有限域是基础，因此首先要找到一种适合硬件来实现的有限域。有限域包括二进制域和素数域。二进制域里的元素都是用0和1表示，而构成二进制域有一种方法是采用正规基表示法，在正规基表示法下域中元素的加法、减法以及平方开方运算分别对应异或和移位操作，而这在硬件中如FPGA是非常容易实现的。但是即便我们作此选择，在椭圆曲线密码协议中，除了二进制域正规基下的运算之外，还有一部分是素数域的运算，主要是ECDSA数字签名算法里的一些步骤。下面是ECDSA具体的算法。 ECDSA签名的生成：输入：参数组，私钥，消息。输出：签名。(1) 选择。(2) 计算，并将转换为整数。(3) 计算。若，则跳至步骤(1) 。(4) 计算。(5) 计算。若，则跳至步骤(1) 。(6) 返回。ECDSA签名的验证：输入：参数组,公钥,消息，签名。输出：判断签名是否合法。(1) 检验 和是否区间内的整数。若任何一个检验失败，则返回（“拒绝该签名”）。(2) 计算 。(3) 计算 。(4) 计算 和。(5) 计算 。(6) 若，则返回（“拒绝该签名”）。(7) 将的横坐标转换为整数；计算。(8) 若，则返回（“接收该签名”）；否则，返回（“拒绝该签名”）。ECDSA签名生成算法中的第五步和ECDSA签名验证算中的第四步都需要用到素数域上的乘法。根据附图1所示，为了满足密码算法的安全性，密钥等参数的位宽至少要在160bit以上，而160bit位宽以上的素域乘法就是一些大整数的乘法运算，在FPGA里如果不采用特殊算法直接做160bit位宽以上的大整数乘法，会造成时钟主频过低，综合出的频率最高不会超过50MHZ，进而会影响整个ECDSA签名的性能。如果不能找到一种好的FPGA实现方法来提高大整数的乘法运算效率，那么将无法体现出ECC在二进制域正规基表示下的硬件实现优势。三、发明内容1 发明目的鉴于上述存在的问题，本发明的目的是提供一种适用于FPGA实现的大整数乘法算法，这种算法在FPGA中实现的速度很快，可以解决上述问题。2技术解决方案本算法将大整数A和B间的乘法分成五个步骤进行，分别是A：做大整数分解运算，将乘数A和被乘数B分解成位长度相等且等于的小整数和，为了方便说明不妨设。B：排列乘法矩阵，将被分解的小整数和之间按乘法矩阵的规则排列组合。 C：做小整数乘法运算，将矩阵中被组合在一起的小整数做乘积，其中。D：做小整数加法运算，将矩阵相邻列在位宽上重合的部分做带进位相加，得到交错列和。E：做位拼接运算，将所有的交错列和做一次位拼接运算，直接得到大整数A和B的乘积。从算法步骤中可以看出，整个大整数A和B的乘法运算主要被分解成长度为的小数乘法运算，和长度为的小整数加法运算以及位拼接运算，这三种运算在FPGA中的运算速度是非常快的，因此通过合理的设计，由这三种运算组成的大整数乘法可以解决之前所述的问题。3技术效果从算法步骤中可以看出，整个大整数A和B的乘法运算主要被分解成长度为的小数乘法运算，和长度为的小整数加法运算以及位拼接运算，这三种运算在FPGA中的运算速度是非常快的，因此通过合理的设计，由这三种运算组成的大整数乘法可以解决之前所述的问题。四、附图及附图的简单说明图1为公钥体制中RSA和ECC安全密钥长度的比较图。图2为椭圆曲线密码体制的组成结构图。图3为本发明中大整数A和B的分解流程图。图4为本发明中乘法矩阵的结构示意图。图5为本发明中交错列求和过程的示意图。五、具体实施方式假设我们需要在FPGA中做大整数A和B的乘法运算，那么根据本文所发明的算法，需要先将大整数A和B做分解运算见附图3。一般来说，大整数的位数都在百位级或以上，对于一款性能尚可的FPGA来言，它内部集成的DSP模块里都带有众多固定位宽的乘法单元，但是位宽较小如9bit*9bit。理论上，大整数A和B的分解位宽越小，整个乘法运算速度将越快，但同时占用的资源也会比较多，相反大整数A和B的分解位宽越大，整个乘法的运算速度将会降低，但用的资源也相对较少。原则上，为了节省FPGA内部的DSP乘法单元，位宽的选择应该为DSP乘法单元位宽的整数倍，且位宽最大值最好不要超过50bit，否则，时序电路的时钟频率会很低，实验中甚至无法达到100MHZ。确定分解位宽之后，根据大整数A和B的实际位宽长度进行高位补零直至成为位宽的整数倍。至此根据本发明中附图3所示，将输入的位宽为L的大整数A和位宽为S的大整数B分解成位长度相等且等于的小整数和并暂存在FPGA内部的寄存器中，不妨设。接着，被分解的小整数和需按照附图4所示的排列规则排列出一乘法矩阵。从图上可以看出，乘法矩阵里的元素都是由小整数和的乘积项组成的，乘积项的位宽是2。实际情况中，对于具体的大整数A和B， m和n之间的数值关系是固定的，而乘法矩阵每一列的元素也会随之确定，为了方便说明附图4中假设m=n-2，从低位到高位，列按照A,B,C,DK的顺序排列，且矩阵的总列数为m+n-1，附图4中，K=m+n-1。在确定了乘法矩阵和矩阵中每列的元素后，便可把先前存储在寄存器中的和依次做*位宽的乘法，求得矩阵列中的元素。可根据资源多少的实际情况选择一次性完成所有的运算，或是按周期每次完成部分运算。并将求得的运算结果存入FPGA内的寄存器中。再下一步是做交错列的加法运算。值得提出的是，本发明中的附图4并不能真实的反应矩阵里各个列之间的关系。对于附图4中相邻两列的数据，如果将其值映射到大整数A和B的最终乘法结果上来，会发现其实列与列之间并非真正意义的相邻，或是说相切，而是相互交错。附图5给出了列与列之间真实的情况：A列里元素的低位数据相对其它列独立，但是A列的高位数据却和B列的低位数据重叠，同样，B列的高位又与C列的低位重叠最后一列K列的低位和J列的高位重叠，K列的高位相对其它列独立。除了第一列的低位和最后一列的高位是与其它列相互独立之外，其余列间都是重叠交错的。附图4中，总列数K=m+n-1，其中交错的列数为（m+n-1）-1=m+n-2个，且每个交错列的位宽都是，因此交错列的总位宽为（m+n-2）* ，如果把A列的低位和K列的高位算人其中，那么交错列的总位宽为（m+n）*，这刚好对应着大整数A和B的乘法结果的总位宽（m+n）*。本发明正式基于这一点，并结合verilog硬件编程语言里特殊的位拼接运算发明了这种适用于FPGA的大整数乘法算法。交错列和的具体算法遵循以下步骤：先将寄存器中第一列A列元素的低位做加法，得到结果的低位就被看做交错列和,高位被看做是进位，事实上，A列只有一个2位宽长度的元素，因此的低就是交错列和，而进位=0；再将寄存器中A列元素的高位和B列元素的低位以及进位做加法运算，得到结果的低位便作为交错列和,结果的高位看成进位，以此类推，每次加法运算后得到一个交错列和和一个进位，直到K列的高位和进位做加法直接得到位的交错列和，理论上不会产生新的进位。可以看出，计算交错列和的步骤主要是由多个位数据间的加法组成的。计算完所有的交错列和，并将其保存在寄存器中。如果之前计算矩阵列中的元素时，采用的是按周期每次完成部分运算，那么可以在每次求得相邻两列所有的元素后便做一次相应的交错列和加法运算。 最后将所有的交错列和做位拼接运算，直接得到m+n位结果， 也就是大整数A和B的乘法结果。这种位拼接运算在FPGA中是非常易于实现的，同时也是FPGA运算的特点之一。综上，在FPGA中我们其实只做了三种简单的运算：位宽的乘法运算，位的加法运算和一个位拼接运算。在运算量方面，位宽的乘法运算一共有m*n个，位的加法运算一共有2mn-3个。在FPGA实