[电子电路]基于Openssl的数字签名算法的实现.doc

《[电子电路]基于Openssl的数字签名算法的实现.doc》由会员分享，可在线阅读，更多相关《[电子电路]基于Openssl的数字签名算法的实现.doc（46页珍藏版）》请在三一办公上搜索。

1、摘 要随着计算机和互联网技术的不断发展、电子商务的广泛应用，信息安全问题变得越来越重要，而网络信息安全的核心在于密码技术。椭圆曲线密码体制(ECC)是一种公钥密码体制，相对于以往基于有限域上离散对数问题或大整数分解问题的传统公钥算法，椭圆曲线密码算法具有安全性高、速度快、密钥短、实现时所需占用资源少的特点。作为迄今为止每比特具有最高安全强度的密码系统，由于其算法的高效安全性，使其成为优于RSA的PKI体系的核心公钥算法，其224位的ECC安全性相当于2048位的RSA安全性，所以ECC技术在信息安全领域中的应用将会越来越广泛。本设计正是基于这样的背景，在Microsoft Visual Stu

2、dio6.0下的Microsoft Visual C+6.0编译环境中利用标准C语言并且借助密码学领域的开放源代码库OpenSSL设计与实现国家密码管理局21号公告（SM2椭圆曲线公钥密码）中的数字签名算法。关键字: 椭圆曲线， SM2， Microsoft Visual C+6.0， C语言， OpenSSL， 数字签名ABSTRACTWith the development and application of information technology and the electronic commerce,the problem of information security bec

3、omes more and more important,but the network information security core lies in the password technology.Elliptic Curve Cryptography(ECC) systems which is a public-key systems is characterized by higher safety property,faster speed,shorter key lengths and fewer computational resources for implementati

4、on thanother former traditional public-key algorithms based on the discrete logarithm infinite fields or the great integer factorization problem.So far,the ECC provides the highest strength-per-bit of any cryptosystem known.Because of its high efficiency of the algorithm,some people think it is the

5、best public-key cryptosystem that is suitable for current use in future.The security of 224-bit ECC is equal to 2048-bit RSA.So the application of ECC technology in the field of information security will be more and more widely.Based on this background,This design will use C language with open sourc

6、e library OpenSSL of the field of cryptography to design and realize a complete system of Digital Signature of Chinese SM2 Elliptic curve public key crypto system.KEY WORD：Elliptic curve， SM2， Microsoft Visual C+6.0， C language， OpenSSL， Digital Signature目 录摘 要IABSTRACTII目 录III第一章 引言1第二章 数字签名的概念2第三章

7、 椭圆曲线概述83.1 有限域83.2 射影平面和无穷远点93.3 椭圆曲线103.4 密码学中的椭圆曲线13第四章 椭圆曲线数字签名算法实现154.1 椭圆曲线的参数选取154.2 杂凑函数174.3 数字签名算法流程184.4 开放源代码工具OpenSSL简介224.5 基于OpenSSL的椭圆曲线数字签名算法实现26第五章 数字签名结果验证29第六章 结论和感想31致谢语32参考文献33附录A34附录B36英文文献39第一章 引言 随着计算机技术和网络技术的高速发展和广泛应用，社会的信息化程度越来越高，大量的敏感信息通过公共通信设施和网络系统进行交换，尤其是互联网、电子商务和电子政务的迅

8、猛发展，国家、企业和个人的信息都要求严格保密，如：军事机密、企业财务、银行密码等。然而，网络很容易遭受攻击，攻击者可以窃取网络信息，企图偷窥机密或是篡改和破坏信息从而使自身获利，这对网络的发展和用户的利益构成了严重的威胁。因此，如何保护通信过程中信息的安全使之不被窃取、篡改和破坏，已经成为当今备受关注的重大问题。在这样的背景下，网络安全技术应运而生，形成了密码技术、系统入侵检测技术和计算机病毒检测消除技术等多种安全防护技术门类。其中，密码技术在信息保护方面给人留下了深刻印象。说到密码技术，人们可能会马上想到加密技术，的确，经过加密处理的信息在网络上传输能够使攻击者难以窃取通信双方的原文，从而避

9、免了机密信息的泄漏。然而，接收方获取的信息有可能被攻击者恶意篡改或破坏，如果不对收到的信息加以辨别将有可能会给通信双方带来巨大的损失。那么接收方要如何确认收到的信息的确是来自和他合作的对象呢？数字签名技术就是能解决这类问题的关键技术。第二章 数字签名的概念数字签名技术(Digital Signatures)是纸质手写签名的电子版本，是一种能够保证交易者身份的确定性、数据交换的完整性、发送信息的不可否认性的有效的解决方案，是电子商务安全性的重要部分；数字签名技术是密码技术的一个分支，要想充分了解数字签名的原理必须先了解密码学相关概念。密码体制可分为对称密码体制和公钥密码体制两种。对称密码的历史可

10、以追溯到几千年前，它是一种加密密钥能够从解密密钥中推算出来，同时解密密钥也可以从加密密钥中推算出来的加密技术。在大多数的对称算法中，加密密钥和解密密钥是相同的。所以对称密码算法也称为秘密密钥算法或单密钥算法。它要求发送方和接收方在安全通信之前，必须商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都可以对他们发送或接收的消息解密，所以密钥的保密性对通信性至关重要。 对称系统通常非常快速，却易受攻击，因为用于加密的密钥必须与需要对消息进行解密的所有人一起共享。其优缺点如下：优点：(1) 算法实现的效率高、速度快。(2) 满足大量信息的加密要求。缺点:(1) 密钥量问题。在单钥密码系

11、统中，每一对通信者就需要一对密钥，当用 户增加时，必然会带来密钥量的成倍增长，因此在网络通信中，大量密 钥的产生、存放和分配将是一个难以解决的问题。(2) 密钥分发问题。单钥密码系统中，加密的安全性完全依赖于对密钥的保 护，但是由于通信双方使用的是相同的密钥，人们又不得不相互交流密 钥，所以为了保证安全，人们必须使用一些另外的安全通道来分发密钥， 例如用专门的信使来传送密钥。这种做法的代价是相当大的，甚至可以 说是非常不现实的，尤其在计算机网络环境下，人们使用网络传送加密 的档，却需要另外的安全通道来分发密钥。所以传统的对称密码算法 急需改进。虽然对称算法的缺点和优点一样明显，但作为对称算法的

12、经典，由IBM公司开发、并被美国国家标准局于1977年2月采纳作为“非密级”应用标准的DES算法不仅在历史上曾发挥重要作用，到目前为止仍是大量信息加密的首选方案。那么对称算法适用于数字签名吗？答案是不适用，因为有两个(或更多个)实体共享密钥，这样一来利用密钥作用于消息产生的数字签名，无法区分出共享密钥的不同实体的行为，也就是对称密码体系不能实现用于不可否认服务的数字签名。公钥密码也称为非对称密码，它是相对于对称密码而言的，它突破性地解决了对称密码面临的三个难题：密钥分发、密钥管理和提供不可否认性。公钥密码体系与对称密码体系最大的不同是采用两个不相同但有着紧密联系的密钥进行加密和解密，其中一个密

13、钥是公开的称为公钥，另一个密钥是保密的称为私钥，这两个密钥也称为密钥对。公钥密码体系的工作模式有两种：(1) 发送实体用公钥加密得到密文；接收实体用私钥把密文解密成明文。只有与此公钥相对应的私钥才能够将该公钥产生的密文恢复成明文。(2) 发送实体用私钥加密得到密文；接收实体用公钥把密文解密成明文。只有与此私钥相对应的公钥才能够将该私钥产生的密文恢复成明文。这种公私钥的关系是基于一种单向陷门函数。单向陷门函数是有一个陷门的一类特殊单向函数。它首先是一个单向函数，在一个方向上易于计算而反方向却难于计算。但是，如果知道那个秘密陷门，则也能很容易在另一个方向计算这个函数。即已知x，很容易计算出f(x)

14、，而已知f(x)，却很难出计算x。然而，一旦给出f(x)和一些秘密信息k，就很容易计算出x。在公钥密码体系中，计算f(x)相当于加密，陷门k相当于私钥，而利用陷门y求f(x)中的x则相当于解密。在公钥密码体系中，要实现这样一种单向陷门函数，密钥对的选择必须保证从公钥求出私钥等价于要求解一个困难的计算问题。目前构成常用公钥密码基础的困难问题有如下3种：(1) 大整数的因子分解问题；(2) 离散对数问题；(3) 椭圆曲线离散对数问题；有了适合于公钥密码体系用来构造公私钥关系的数学难题，公钥密码的应用才能成为现实。对于公钥体系的工作模式(1)，以公钥作为加密密钥，以用户私钥作为解密密钥，可实现多个用

15、户加密的消息只能由一个用户解密，适用于加密，因为私钥的保密性确保了只有一个实体能进行解密；对于公钥体系的工作模式(2)，以私钥作为加密密钥，以公钥作为解密密钥，则可实现由一个用户加密的消息可以由多个用户解密，适用于数字签名，因为同一个实体产生的多个签名应该能被不同的接收实体验证，这也正是数字签名的基本要求。 本设计研究的是数字签名，以下就不对公钥密码的加密体系进行介绍了。数字签名技术是不对称加密算法的典型应用。数字签名的应用过程是：数据源发送方使用自己的私钥对数据和其他与数据内容有关的信息进行加密处理，完成对数据的合法“签名”，数据接收方利用对方的公钥来解读收到的“数字签名”，并将解读结果用于

16、对数据来源和完整性的认证，以确认签名的合法性。最早的数字签名方案有RSA数字签名方案、DSA数字签名方案和ECDSA数字签名方案。此三种签名方案于2000年2月15日被美国国家标准技术研究所(NIST)在新标准法案FIPSl86-2中指定为美国的数字签名标准，同时他们也是目前世界上普遍使用的数字签名方案，都已经形成商业的签名软件供商家和个人使用。其中RSA数字签名方案是由RSA公司提出的基于RSA公钥密码体制的签名方案，其数学基础是大数因子分解的困难性。DSA数字签名方案是基于E1Gamal提出的E1Gamal公钥密码体制，其数学基础是在有限域上求解离散对数的困难性。ECDSA数字签名方案是基

17、于椭圆曲线密码体制的签名方案，它是将DSA签名方案移植到椭圆曲线密码体制中来得到的，它的数学基础是求解椭圆曲线上离散对数的困难性。目前由于椭圆曲线密码体制较其他公钥密码体制有密钥短、速度快、安全性高的优点使得椭圆曲线密码体制和ECDSA数字签名方案越来越受到更高的重视。下面对本设计采用的椭圆曲线密码体系进行详细介绍。人们对椭圆曲线的研究已有100多年的历史，而椭圆曲线密码是Neal Koblitz和Victor Miller于1985年提出来的。目前椭圆曲线密码已成为除RSA密码之外呼声最高的公钥密码之一。它可以提供同RSA相同的功能。然而它的安全性建立在椭圆曲线离散对数问题(ECDLP)的困

18、难性之上。现在求解ECDLP的最好算法具有全指数时间复杂度，与此不同，整数因子分解问题却有亚指数时间算法，所谓亚指数算法就是其算法复杂度还未到达指数级别。这意味着要达到期望的安全强度，椭圆曲线密码可以使用较RSA密码更短的密钥。普遍认为224位的椭圆曲线密码可提供相当于2048位RSA密码的安全强度。由于密钥短，所以工程实现加解密速度较快，并且可节省能源、带宽和存储空间。正因为如此，一些国际标准化组织已把椭圆曲线密码作为新的信息安全标准。由于椭圆曲线密码具有上述优点，因此椭圆曲线密码特别适于在航空、航天、卫星及智能卡的系统中的应用。在椭圆曲线密码体制的标准化方面，IEEE、ANSI、ISO、F

19、IPS、SEC等都作了大量的工作，它们所开发的椭圆曲线标准的文档有：IEEE P1363-2000 和P1363a、ANSI X9.62和X9.63、 ISO/IEC15946、FIPS186-2、SEC1和SEC2等。根据研究，以目前计算整数分解问题、离散对数问题和椭圆曲线离散对数问题的最好算法进行计算，表1-1比较了RSA、DSA和ECC在等价安全强度下所需的密钥尺寸(其中MIPS(Million Instructions Per Second)年是每秒运算100万条指令运行1年的时间): 表2-1 三种典型的公钥密码体系性能比较破解密钥时间（MIPS年）RSA、DSA密钥长度（bit）E

20、CC密钥长度（bit）RSA与ECC密钥长度比1045121065:11087681326:1101110241607:11020204822410:110782100060035:1表2-1说明，在等价安全强度下，ECC较RSA和DSA的密钥尺寸小的多，而且随着密钥长度的增加它们的比例将更为悬殊。以下从几个方面对三种公钥密码体系进行比较：（1）安全性能 加密算法的安全性能一般通过该算法的抗攻击强度来反映。ECC和其他几 种公钥系统相比，其抗攻击性具有绝对的优势。椭圆曲线的离散对数计算困难性(ECDLP)在计算复杂度上目前是完全指数级，而RSA是亚指数级的。这体现ECC比RSA的每bit安全性

21、能更高。 （2）计算量和处理速度 在一定的相同的计算资源条件下，虽然在RSA中可以通过选取较小的公钥 (可以小到3)的方法提高公钥处理速度，即提高加密和签名验证的速度，使其在加密和签名验证速度上与ECC有可比性，但在私钥的处理速度上(解密和签名)，ECC远比RSA，DSA快得多。因此ECC总的速度比RSA，DSA要快得多。同时ECC系统的密钥生成速度比RSA快百倍以上。因此在相同条件下，ECC有更高的加密性能。 （3）存储空间 ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多。160位ECC与1024位RSA，DSA具有相同的安全强度，224位ECC则与2048位RSA，DSA具有相同的

22、安全强度。意味着它所占的存贮空间要小得多。这对于加密算法在资源受限环境上(如智能卡等)的应用具有特别重要的意义。 （4）带宽要求 当对长消息进行加解密时，三类密码系统有相同的带宽要求，但应用于短消息时ECC带宽要求却低得多。而公钥加密系统多用于短消息，例如用于数字签名和用于对称系统的会话密钥传递。带宽要求低使ECC在无线网络领域具有广泛的应用前景。 此外，人们已经知道利用量子计算机进行整数因子分解、求解离散对数问题和求解椭圆曲线离散对数问题的有效算法。然而。人们尚不知道大型量子计算机是否能够实际制造出来。在传统计算机上求解256位的ECDLP实例大致相当于3072位的因数分解问题的实例。然而，

23、前者可在1448-qubit量子计算机上求解，而后者需要6144-qubit量子计算机。到目前为止，最重大的实验结果是2001年使用Vandersypen等464建造的7-qubit量子计算机来以Shor算法对整数15进行因数分解。类似的实验能否大规模用于密码学意义的因数分解和求解ECDLP实例，还有待进一步研究。也就是说虽然量子计算机以其自身的优势对于以上3大难题的求解比普通大型计算机有更好的解决方案，但是目前的量子计算机技术的发展还远未达到可以解决3大难题的规模。现在，普通的认为2048位的RSA才能保证信息的安全，而224位的ECC便能达到这一安全水平，随着大型计算机的不断发展，椭圆曲线

24、密码凭借其密钥长度短的优势将在未来的安全领域应用中越来越多的得到客户的青睐。目前，数字签名已经是一种十分成熟的技术。鉴于数字签名技术在各个领域的重要性，国内外尤其是国外的研究发展水平一直很高，国外发明的数字签名方法有很多，其中DSA是主流算法；椭圆密码体制的不断发展正在逐步挑战RSA在公钥密码学的地位，其更少的密钥长度和每比特更高的安全性，更适合数字签名这类短消息加密需求。国外发明的基于椭圆曲线密码学的数字签名算法为ECDSA，国家密码管理局也于2010年12月17日发布了SM2椭圆曲线公钥密码，内容包括公钥加密算法、数字签名算法和密钥交换协议，其中的数字签名部分给出了中国标准的基于椭圆曲线的

25、数字签名方案，其与ECDSA原理一致，只是在签名验证算法的实现上有所不同。数字签名技术已经广泛应用于各种电子政务和电子商务等对安全性要求很高的领域中，从技术发展的水平来看，并没有存在明显的问题。第三章 椭圆曲线概述3.1 有限域在椭圆曲线密码体制中，我们关心的是基于有限域上的椭圆曲线。有限域上的椭圆曲线加密算法涉及数论、群论、有限域理论及椭圆曲线等数学知识。 域是对常见的数系(如有理数域Q，实数域R和复数域C)及其基本特性的抽象。域由一个集合F及两种运算共同组成。这两种运算分别为加法(用+表示)和乘法(用*表示)，且满足下列算术特性： （1）(F，+)对于加法运算构成加法交换群，单位元用0表示

26、。（2）(F0，*)对于乘法运算构成乘法交换群，单位元用l表示。（3）分配律成立：对于所有的a，b，cF，都有(a+b)*c=a*c+b*c。若集合F是有限集合，则称此域为有限域。 有限域算术运算的有效实现是实现椭圆曲线密码的重要先决条件，因为椭圆曲线运算是基于有限域算术运算的。椭圆曲线密码体制的有效实现主要用到两大特征的有限域，它们分别是素域和二进制域。3.1.1 素域设p是一个素数，以p为模，则模p的全体余数的集合0,1,2,.,p-1关于模p的加法和乘法构成一个p阶有限域，并用符号Fp表示。我们称p为Fp的模。对于任意的整数a，a mod p表示用p除a所得到的余数r，0rp-1,并称这

27、种运算为求模p的剩余。Fp中元素具有以下算术运算： (1) 加法：如果a,bFp，则a+b=r，其中r是被p除所得的剩余，OrP一1。 (2) 乘法：如果a,bFp，则a*b=s，其中s是被p除所得的剩余，OsP一1。 (3) 求逆：如果a是Fp中的非零元素，a模q的逆元，记为，是唯一的整数c Fp，c满足a*c=1。 3.1.2 二进制域阶为的域称为二进制域或特征为2的有限域。构成的一种方法是采用多项式基表示法。在这种方法中，域的元素是次数最多为m-1次的二进制多项式(多项式的系数取自=0，1)， 的公式见公式3-1。= 公式3-1选择一个二进制域上的m次既约多项式f(z)（对任意的m，这样

28、的多项式一定存在，并能够有效产生）f(z)的既约性意味着f(z)不能被分解成次数低于m的二进制域上的多项式的乘积。域元素的加法是两个多项式系数的模2相加。域元素的乘法是两个多项式相乘后取模f(z)。对于任意一个二进制域上的多项式a(z)，a(z) mod f(z)表示一个次数低于m的余式多项式r(z)。余式多项式r(z)可用f(z)辗转相除a(z)得到，这一运算成为求模f(z)的余式。3.2 射影平面和无穷远点通常情况下两条平行直线永不相交，但可以假设两条平行直线相交于一个无穷远点，从而可以在原来平面坐标系的基础上建立射影坐标系。 对于普通平面直角坐标系上的点坐标(x，y)做如下变换： 令x=

29、X/Z，y=Y/Z，Z0，则A点可以表示为(X，Y，Z)。这样就将二维的坐标变成了三维的坐标，同时，对于平面上的点建立了一个新的坐标体系。同时得到直线的方程aX+bY+cZ=0(普通平面直角坐标系下直线一般方程是ax+by+c=0)。无穷远点是两条平行直线的交点，将两条平行线直线对应的方程联立求解： aX+bY+Z=0 公式3-2 aX+bY+Z=0公式3-3解得Z=Z=-aX-bY,因为，所以Z=0，即无穷远点可以用(X，Y，0)表示。注意，平常点Z0，无穷远点Z=0，因此无穷远直线对应的方程是Z=0。 下面列出无穷远点的几个性质，以统一平行与相交： （1）直线L上的无穷远点只能有一个。 （

30、2）平面上一组相互平行的直线有公共的无穷远点。 （3） 平面上任何相交的两直线L1，L2有不同的无穷远点。 （4） 平面上全体无穷远点构成一条无穷远直线。 （5） 平面上全体无穷远点与全体平常点构成射影平面。 3.3 椭圆曲线3.3.1 椭圆曲线定义域K上的椭圆曲线E的方程定义见公式3-4：E:公式3-4其中K且，是E的判别式，具体定义如下:方程E被称为Weierstrass方程；我们称E是域K上的椭圆曲线，这是因为系数均为域K的元素；条件是确保椭圆曲线是“光滑”的，即曲线的所有点都没有两个或两个以上不同的切线。椭圆曲线的形状，并不是椭圆的，椭圆曲线的一个典型图形如图2-1 所示。只是因为椭圆

31、曲线的描述方程，类似于计算一个椭圆周长的方程。定义在实数域R上的椭圆曲线，其点和画在图3-1中（其中为无穷远点）：图3-1 R上的椭圆曲线若E是定义在域上的椭圆曲线，那么椭圆曲线E（）的点的个数记为#E（）,并称其为域上的椭圆曲线E的阶。若椭圆曲线上的一点P，存在最小的正整数n使得nP=，则称n为P的阶。若n不存在，我们说P是无限阶的。事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在的。3.3.2 椭圆曲线的运算法则设P和Q是椭圆曲线E上的两个的点，若是不同的两点，则L是P和Q的连线；若是重合的点，则L是该点的切线；L与曲线相交的另一个点，过作y轴的平行线，与曲线交另一点R，定义点加运

32、算R=P+Q。不同点和重合点的点加运算的图形描述分别图3-2和图3-3：图3-2 不同点相加运算图3-3 重合点倍点运算椭圆曲线的运算法则如下：（1） 单位元。对于所有的PE（K），P+=+P=P。点为单位元。（2） 负元素。若P=（x,y）E（K），则（x,y）+（x,-y）=。记点（x,-y）为-P，并称其为P的负。注意，-P也是E(K)上的一个点，此外-=。（3）不同点相加。令，则。其中： 和 （4）相同点倍点。令，则。其中： 和 （5）标量乘。椭圆曲线上的标量乘是椭圆曲线密码体制的核心操作。曲线E上的一点P，其标量乘Q=KP定义为对P进行了（K-1）次的倍点运算。标量乘是椭圆曲线密码体

33、制中最耗时的运算，它决定着椭圆曲线密码体制的运算速度。3.3.3 射影平面坐标系下的椭圆曲线椭圆曲线在射影平面上的投影形式为： 公式 3-5曲线E上唯一的一个无穷远点是（0:1:0）。射影坐标的点加和倍点运算不涉及域上的求逆。首先把点转化为仿射坐标，然后利用其运算法则进行点加，最后去掉分母，便得到射影坐标点的计算公式。 由于在普通平面直角坐标系下，域K上的求逆存在比乘法费时的情况，那么采用射影坐标来表示点将是非常好的一种解决办法。3.4 密码学中的椭圆曲线椭圆曲线密码体制基于的数学难题是椭圆曲线离散对数问题，前面提及的椭圆曲线是连续的，并不适合加密，所以我们必须把椭圆曲线转化为离散的点，这就需

34、要将椭圆曲线定义在有限域上。并不是所有的椭圆曲线都适合加密。是一类可以用来加密的椭圆曲线，也是最为简单的一类，本设计正是基于有限域上的这类曲线来实现加解密算法的。下面我们就把 这条曲线定义在有限域Fp上： 选择两个满足下列条件的小于p(p为素数)的非负整数a、b并且满足 (mod p)。则满足方程 (mod p)的所有点(x,y)，再加上无穷远点 ，构成一条椭圆曲线。其中 x,y属于0到p-1间的整数，并将这条椭圆曲线记为Ep(a,b)。令p=29，a=4，b=20，考虑定义在素域上的椭圆曲线E: 公式3-6注意，所以曲线E确实是椭圆曲线。椭圆曲线的点如下： (2,6) (4,19) (8,1

35、0) (13,23) (16,2) (19,16) (27,2)(0,7) (2,23) (5,7) (8,19) (14,6) (16,27) (20,3) (27,27)(0,22) (3,1) (5,22) (10,4) (14,23) (17,10) (20,26)(1,5) (3,28) (6,12) (10,25) (15,2) (17,19) (24,7)(1,24) (4,10) (6,17) (13,6) (15,27) (19,13) (24,22)椭圆曲线在不同的数域中会呈现出不同的样子，但其本质仍是一条椭圆曲线。椭圆曲线在有限域上的运算法则同实数域上的运算法则类似。椭圆

36、曲线离散对数问题（ECDLP）定义为:给定定义于有限域的椭圆曲线E，基点，阶为n，点,寻找一个整数使得。整数称为Q的基于的离散对数，表示为。椭圆曲线离散对数问题的困难性是所有椭圆曲线密码方案安全性的基础。但需要注意的是，ECDLP的难解并没有数学上的证明。目前还没有证明不存在求解ECDLP的有效算法。然而，通过很多年的考验说明了ECDLP的难解性。自从1985年椭圆曲线密码被提出来，该问题被许多学者研究，到目前为止还没有发现亚指数时间的通用算法。第四章 椭圆曲线数字签名算法实现4.1 椭圆曲线的参数选取4.1.1 参数组为了抵抗所有已知的对ECDLP的攻击，密码方案中使用的椭圆曲线的参数应该谨

37、慎选择。最简单的求解ECDLP问题的算法是穷举搜索:连续计算一系列点P,2P,3P,4P,.,直到得到Q，该方法最坏的情况下为n步，平均情况下为n/2步。因此可以通过选择参数n足够大的椭圆曲线，使得穷举攻击的计算量不可实际实现（如）。对于ECDLP，已知最好的通用攻击方法是将Pohlig-Hellman算法和Pollards rho相结合，该方法的运行时间为完全指数时间，其中是n的最大素因子。为了抵抗该种攻击，椭圆曲线参数的选择要求n含有大素数因子，应该足够大，以使得的计算量不可实现（如）。另外椭圆曲线的参数选择还要防止其他所有的已知攻击方法。密码学中，描述一条上的椭圆曲线，参数组D=(,FR

38、,a,b,G,n,h)。其中:域的阶p 、系数a 和b 用来确定一条椭圆曲线；FR即Fp中元素的表示；有穷远点G为基点，n为点G的阶，h =，称为余因子。为了避免针对ECDLP的Pohlig-Hellman攻击和Pollards攻击，必须能被足够大的素数n整除，最小应该保证。给定域，为了最大限度地抵抗Pohlig-Hellman攻击和Pollards攻击，应选择E使得为素数或者近似素数，即=hn，其中n为素数，h非常小（如h=1,2,3或4）。这几个参量取值的选择，直接影响了加密的安全性。参量值一般要求满足以下几个条件：（1） p当然越大越安全，但越大计算速度越慢，200位左右可以满足一般安全

39、要求。（2） p n h。（3） pt 1 (mod n)，其中1t20。（4） 。（5） n为素数。（6） h 4。为了防止针对特殊类型椭圆曲线的攻击，应随机选择满足能被大素数整除的椭圆曲线E。因为随机曲线满足已知的同构攻击的条件的概率非常小而可忽略，因此已知攻击仍可避免。可证明的随机选择一条椭圆曲线，这能保证椭圆曲线的用户不被通过故意构造有潜在弱点的曲线而窃取用户的私钥。然而随机生成一条满足要求的椭圆曲线，有时需要的时间是很长的。在FIPS 186-2标准中，NIST推荐了美国政府使用的15个不同安全级别的椭圆曲线。另外，我国在SM2椭圆曲线公钥密码算法的标准中，也推荐了1种安全曲线。使用

40、这些经国际或国家验证过的椭圆曲线显然更加有安全性保障。本设计出于对程序正确性的验证，采用了国家密码管理局21号公告（SM2椭圆曲线公钥密码算法）中数字签名算法附录A中数字签名与验证示例所用的椭圆曲线，曲线方程为：，其参数如下：p = 0x 8542D69E 4C044F18 E8B92435 BF6FF7DE 45728391 5C45517D 722EDB8B 08F1DFC3a = 0x 787968B4 FA32C3FD 2417842E 73BBFEFF 2F3C848B 6831D7E0 EC65228B 3937E498b = 0x 63E4C6D3 B23B0C84 9CF842

41、41 484BFE48 F61D59A5 B16BA06E 6E12D1DA 27C5249An = 0x 8542D69E 4C044F18 E8B92435 BF6FF7DD 29772063 0485628D 5AE74EE7 C32E79B7x = 0x 421DEBD6 1B62EAB6 746434EB C3CC315E 32220B3B ADD50BDC 4C4E6C14 7FEDD43Dy = 0x 0680512B CBB42C07 D47349D2 153B70C4 E5D7FDFC BFA36EA1 A85841B9 E46E09A2h = 1其中: 素域的阶。a,b :

42、椭圆曲线的系数，满足。n : 基点G的（素数）阶。h : 余因子。x,y : 基点G的x和y坐标。4.1.2 密钥对椭圆曲线密钥对与参数组D中的一系列参数相关。其选择过程为:随机选择作为私钥,然后计算P=dG作为公钥。从公钥P中计算私钥d的问题（）显然就是椭圆曲线离散对数问题。因此至关重要的是参数组D的选择要使得ECDLP不可求解。此外数d的生成一定要是“随机”的，以防止攻击者基于概率搜索策略获得额外信息。4.2 杂凑函数杂凑函数在中文中有很多译名，有些人根据Hash的英文原意译为“散列函数”或“杂凑函数”，有些人干脆把它音译为“哈希函数”，还有些人根据Hash函数的功能译为“压缩函数”、“消

43、息摘要函数”、“指纹函数”、“单向散列函数”等等。杂凑算法是把任意长度的输入数据经过算法压缩，输出一个尺寸小了很多的固定长度的数据，即杂凑值。杂凑值也称为输入数据的数字指纹（Digital Fingerprint）或消息摘要（Message Digest）等。杂凑函数具备以下2点性质：(1) 给定输入数据，很容易计算出它的杂凑值；反过来，给定杂凑值，算出输入数据则很难，计算上不可行。这就是杂凑函数的单向性，在技术上称为抗原像攻击性。(2) 给定杂凑值，想要找出能够产生同样的杂凑值的两个不同的输入数据（这种情况称为碰撞-Collision），这很难，计算上不可行，在技术上称为抗碰撞攻击性。杂凑函

44、数在实际中有多种应用，在信息安全领域中更受到重视。从杂凑函数的特性，我们不难想象，我们可以在某些场合下，让杂凑值来“代表”信息本身。例如，检验杂凑值是否发生改变，借以判断信息本身是否发生了改变。正是因为杂凑算法的特性，在数字签名算法中加入杂凑算法的应用能验证通信中的信息是否被人恶意篡改。目前，已经发明的Hash函数有多种，如Snefru、N-Hash、LOKI、AR、GOST、MD、SHA等。它们在数学上实现的方法各有不同，安全性也各有不同。目前比较常用的Hash函数是MD5和SHA-1。 MD5杂凑函数以512位来处理输入数据，每一分组又划分为16个32位的子分组。算法的输出由4个32位分组

45、组成，将它们级联起来，形成一个128位的固定长度的杂凑值，即输入数据的摘要。SHA-1杂凑函数在MD4的基础上增加了数学运算的复杂程度，即SHA=MD4+扩展转换+附加轮+更好的雪崩效应（杂凑值中，为0的比特和为1的比特，其总数应该大致相等；输入数据中一个比特的变化，将导致杂凑值中一半以上的比特变化，这就叫做雪崩效应）。对SHA还没有已知的密码攻击，并且由于它产生的杂凑值位数长于MD5，所以它能更有效地抵抗穷举攻击（包括生日攻击）。我国颁布的杂凑算法标准是SM3密码杂凑算法，结果为256位，其大体上与SHA256相同。对长度为比特的消息m，SM3杂凑算法经过填充和迭代压缩，生成杂凑值，杂凑值长

46、度为256比特。4.3 数字签名算法流程椭圆曲线本身并不是一种密码算法，但可以将已知密码算法移植到椭圆曲线上。与ECDSA一样，SM2椭圆曲线公钥密码算法中的数字签名算法也是DSA算法在椭圆曲线上的移植。DSA是一种基于有限域上离散对数问题的数字签名算法，其安全性依赖于计算有限域上离散对数这一难题。而SM2椭圆曲线公钥密码算法中的数字签名算法是基于有限域上椭圆曲线离散对数问题，其安全性依赖于计算有线域上椭圆曲线离散对数问题。SM2椭圆曲线公钥密码算法的数字签名算法的签名过程如下： 设待签名的消息为M，为了获取消息M的数字签名(r,s)，作为签名者的用户A应实现以下运算步骤：图4-1签名流程图(1) 置；其中，作为签名者的用户A具有长度为比特的可辨别标识，记是由整数转换而成的两个字节。如：为ALICE132YAHOO.COM时，为：0x0090。即是用户身份和椭圆曲线参数拼接后经过杂凑函数计算出的杂凑值。、分别是基点G、公钥P的横纵坐标。(2) 计算，将e的数据类型转化为整数。e是和消息M拼接后经过杂凑函数计算出的杂凑值，一般称为消息的摘要。(3) 用随机数发生器产生随机数;(4) 计算椭圆曲线点，将的数据类型转化为整数;(5) 计算，则返回(3)；(6) 计算，若则返回(3)，其中为私钥。(7) 将r、s的数据类型转换为字节串，消息M的签名为(r,s)。