专利申请报告姓名：郭政明学号：06一、发明名称一种适用于FPGA实现的大整数乘法二、现有技术当前的密码体制一般可划分为两种类型，即对称密码体制和公钥密码体制。对称密钥体制需要通信双方A和B共享同一密钥K，并且要保证A和B在协商密钥的时候，信道是保密且保真的。这就导致了它的密钥分发的问题和密钥的管理问题，除此之外由于两个或多个实体共享密钥，所以对称密钥体制不能实现用于认证和不可否认服务的数字签名。与对称密钥体制不同，公钥密码体制仅要求密钥的交换是保真的，并不要求其是保密的。每个实体选择一个密钥对（公钥，私钥），其中公钥对外是公开的，私钥自己保密，这种密钥对需具备一个特点：仅由公钥不能计算出私钥。由于每一个实体都具有唯一的私钥，因此可以提供数据源和数据完整性的认证以及不可否认性服务。这样，公钥密码圆满地解决了上述对称密码面临的三个问题。在公钥加密机制中，虽然RSA是目前主流的加密机制，但是RSA目前却面临着越来越严重的来自安全方面的挑战。第六届国际密码学会议对应用于公钥密码系统的加密算法推荐了两种：RSA算法和ECC算法。RSA算法的特点之一是数学原理简单，在工程应用中比较易于实现，但它的单位安全强度相对较低。椭圆曲线密码算法建立在深奥和复杂的数学理论之上，它的单位安全强度相对较高。这两种算法安全强度比较如附图1所示。需要指出的是，由于ECC的复杂度较高，它的运算通常比较慢。需要找到一种用硬件来实现ECC密码体制的方案去提高运算速度。ECC密码体制主要是由有限域层、椭圆曲线层、椭圆曲线密码协议层和一些特殊功能算法组成的见附图2，其中有限域是基础，因此首先要找到一种适合硬件来实现的有限域。有限域包括二进制域和素数域。二进制域里的元素都是用0和1表示，而构成二进制域有一种方法是采用正规基表示法，在正规基表示法下域中元素的加法、减法以及平方开方运算分别对应异或和移位操作，而这在硬件中如FPGA是非常容易实现的。但是即便我们作此选择，在椭圆曲线密码协议中，除了二进制域正规基下的运算之外，还有一部分是素数域的运算，主要是ECDSA数字签名算法里的一些步骤。下面是ECDSA具体的算法。ECDSA签名的生成：输入：参数组(,,,,,,,)DqFRSabPnh，私钥d，消息m。输出：签名(,)rs。(1)选择[1,1]kn。(2)计算11(,)kPxy，并将1x转换为整数1x。(3)计算1modrxn。若0r，则跳至步骤(1)。(4)计算()eHm。(5)计算1()modskedrn。若0s，则跳至步骤(1)。(6)返回(,)rs。ECDSA签名的验证：输入：参数组(,,,,,,,)DqFRSabPnh,公钥Q,消息m，签名(,)rs。输出：判断签名是否合法。(1)检验r和s是否区间[1,1]n内的整数。若任何一个检验失败，则返回（“拒绝该签名”）。(2)计算()eHm。(3)计算1modwsn。(4)计算1moduewn和2modurwn。(5)计算12XuPuQ。(6)若X，则返回（“拒绝该签名”）。(7)将X的横坐标1x转换为整数1x；计算1modvxn。(8)若vr，则返回（“接收该签名”）；否则，返回（“拒绝该签名”）。ECDSA签名生成算法中的第五步和ECDSA签名验证算中的第四步都需要用到素数域上的乘法。根据附图1所示，为了满足密码算法的安全性，密钥等参数的位宽至少要在160bit以上，而160bit位宽以上的素域乘法就是一些大整数的乘法运算，在FPGA里如果不采用特殊算法直接做160bit位宽以上的大整数乘法，会造成时钟主频过低，综合出的频率最高不会超过50MHZ，进而会影响整个ECDSA签名的性能。如果不能找到一种好的FPGA实现方法来提高大整数的乘法运算效率，那么将无法体现出ECC在二进制域正规基表示下的硬件实现优势。三、发明内容1．发明目的鉴于上述存在的问题，本发明的目的是提供一种适用于FPGA实现的大整数乘法算法，这种算法在FPGA中实现的速度很快，可以解决上述问题。2．技术解决方案本算法将大整数A和B间的乘法分成五个步骤进行，分别是A：做大整数分解运算，将乘数A和被乘数B分解成位长度相等且等于l的小整数1321,...,,nnAAAAA和1321,...,,mmBBBBB，为了方便说明不妨设nm。B：排列乘法矩阵，将被分解的小整数1321,...,,nnAAAAA和1321,...,,mmBBBBB之间按乘法矩阵的规则排列组合。C：做小整数乘法运算，将矩阵中被组合在一起...
