毕业设计（论文）-基于混沌的椭圆曲线密码系统的研究与实现.doc

基于混沌的椭圆曲线密码系统的研究与实现 桂加睿摘要密码学已经有上千年的历史，一直以来，人们都用代数方法来研究密码学问题，并产生了大量的加解密算法，如des,aes,rsa等等。同时，近年来，人们经过大量研究发现混沌系统有以下重要的特性：高度不可预测性、看似随机性、对初始条件和参数敏感性等。这些特性与密码学特性有巨大相似性,促使人们把混沌理论运用到密码学领域。 椭圆曲线加密系统（ecc）的安全性基于椭圆曲线离散对数问题的难解性。它是迄今为止每比特具有最高安全强度的密码系统。同其它非对称加密体制相比，椭圆曲线密码系统除了安全性有着高外，还具有计算负载小、密钥尺寸短、占用带宽少等优点。因此，椭圆曲线密码系统被认为是下一代最通用的公钥密码系统。混沌系统和密码学之间有天然的联系和结构上的相似性，启示着人们把混沌理论应用于密码学领域，混沌理论与常规密码学之间的广泛联系激起了越来越多的密码学研究者的兴趣，利用混沌系统构造密码算法成为信息安全领域的一个重要研究热点。本文以椭圆曲线加密系（ecc，elliptic curves cryptosystem）为研究对象，分析了椭圆曲线的的数学原理和工作原理，设计实现了基于混沌理论的ecc密码系统，实现了基于混沌ecc用于数字签名的基本算法，从性能、安全性等方面分析了系统的技术优势。关键字：混沌密码学、离散对数、群域、椭圆曲线、数字签名research and implementation of elliptic curve cryptography algorithm base on chaos gui,jia-rui abstractcryptography has been for thousands of years, people have to use algebraic methods to study the problem of cryptography, and produce a large number of cryptographic systems, such as des, aes, rsa etc. on the other hand, in recent years, people has done a lot of research on the chaotic system, recognized some of its important features, such as: very unpredictability nature of seemingly random, on the initial conditions and parameter sensitivity. these features are great similarities with cryptographic propertieselliptic curve cryptography (ecc) security is based on elliptic curve discrete logarithm problem of intractability, so far, the elliptic curve cryptosystem (ecc) provides the highest strength-per-bit of any cryptosystem known. in addition to its high security, ecc also has many other merits over other public-key cryptosystems such as less computation overheads shorter key size, considerable bandwidth savings, and so on. therefore, the elliptic curve cryptosystem is considered the next generation of the most common public-key cryptosystem. between chaos and cryptography has the natural link and structural similarity, reveals to people the chaotic field of applied cryptography, chaos theory and conventional cryptography and extensive links between the more and more aroused interest in cryptography researchers, to construct the cryptographic algorithm using chaotic field of information security to become an important research focus. in this paper, the elliptic curves cryptosystem(ecc) as the research object. illustrates the elliptic curve mathematical principle and the principle, combined with chaos theory, design and implementation of ecc based on chaos theory cryptography, finally, implemented the basic ecc digital signature algorithm with chaos. analyze technological advantages of the system on performance, security etc.keywords: chaos cryptography, ecc, ecdlp, digital signature, group, field目录1 绪论41.1 课题研究的背景和意义41.2 椭圆曲线密码的发展历史41.3 混沌理论的发展历史51.4 研究的主要内容和方法51.5 论文的组织安排62 混沌密码学原理62.1 混沌的的定义62.2 混沌数学基础63 椭圆曲线算法原理分析83.1 基本概念83.1.1 群和域83.1.2 椭圆曲线83.2 ecc算法基础93.2.1运算分层93.2.2 有限域上的运算93.2.2椭圆曲线的参数103.2.3 椭圆曲线上的运算113.3 ecc算法原理分析134 基于椭圆曲线的混沌的密码系统构造134.1 混沌理论与密码学134.2 系统设计与实现144.2.1 参数生成144.2.2 加密过程144.2.3 解密过程165 基于混沌与椭圆曲线的数字签名算法175.1 方案一 混沌映射消息摘要175. 2 方案二 混沌映射消息后产生摘要196 系统性能及安全性分析216.1 系统运行216.2 性能分析246.3 安全性分析257 总结与展望26致谢27参考文献28附录一 有限域上算法29附录二 椭圆曲线上算法311 绪论1.1 课题研究的背景和意义1976年diffie和hellman提出公钥密码思想以来，国际上提出了许多种公钥密码体制的实现方案。一些已经被攻破，一些被证明是不可行的。目前，只有3类公钥密码体制被认为是安全有效的，按照其所依据的数学难题划分为：基于大整数分解问题（ifp），如rsa体制和rabin体制；基于有限域离散对数问题（dlp），如diffie-hellman体制elgamal体制；基于椭圆曲线离散对数问题（ecdlp ecdlp），如椭圆密码体制。椭圆曲线应用到密码学上最早是由victor miller1和neal koblitz2在1985年分别独立提出的。它是目前已知的公钥体制中，对每一比特所提供加密强度最高的一种体制。它具有安全性高、密钥量小、灵活性好的特点，受到了国际上的广泛关注。而set协议的制定者已把它作为下一代set协议中缺省的公钥密码算法。深入研究基于椭圆曲线离散对数问题的公钥密码具有很大的现实意义。混沌现象是非线性确定性系统中的一种类似随机的过程，把两个十分相近的初值带入同一个混沌函数进行迭代运算，经过一定阶段的运算后，数值序列变得毫不相关。它隶属于确定性系统却难于预测，隐含于复杂系统但又不可分解，看似“混乱无序”，实则颇有规律。shannon在他的论文3中写到，一个好的加密系统，它的函数必须是复杂的，并且一个小的变化必然导致结果发生很大的变化。这些密码学特性与混沌系统的特性有着巨大的相似性，促使人们把混沌理论运用到密码学领域。由于混沌系统对初值和参数极其敏感，同时还具有非周期性和伪随机性的特点，近来，它引起了密码学领域的广泛关注，据此提出了密码学中用于指导密码设计的两个基本原则：扩散和混乱,并产生出大量富有成效的研究成果。混沌和密码学之间计有的天然的联系和结构上的相似性，启示着人们把混沌应用于密码学领域，混沌理论与常规密码学之间的广泛联系激起了越来越多的密码学研究者的兴趣,利用混沌系统构造密码算法成为信息安全领域的一个重要研究热点。1.2 椭圆曲线密码的发展历史人类从十七世纪就开始研究椭圆曲线了，但真正把其应用到密码学中是1985年由victor miller1和neal koblitz2分别独立提出的。他们利用椭圆曲线上的点构造了椭圆曲线密码系统。之后出现了很多针对椭圆曲线密码系统的研究，主要集中在三个方面:1. 椭圆曲线密码系统的构造:包括有限域的选择和安全曲线的选择以及密码体制的构造。2. 椭圆曲线密码系统的分析：就是在仅知道由ecc加密的密文的情况下，恢复出明文。包括对ecc的攻击方法的选择、验证等等。3. 椭圆曲线密码系统的快速实现：大体可分为软件和硬件两个方面的快速实现。1990年，menezes使用了一类特殊的曲线超奇异椭圆曲线这种曲线有理点群的阶可以很容易的得到并且实现速度也很快。但是到1993年，menezes本人和他的两个合作者发现了对这种曲线的一种有效的攻击方法，称为“mov攻击”，这种方法可以把椭圆曲线离散对数问题化约到某个次数较低的域上，从而在多项式时间内求解。但与此同时，椭圆曲线上有理点个数的计算问题得到了很大的突破。1989到1992年间，atikin和elkie对1985年提出的schoof算法作出了重大改进，到1995年，人们在这一问题上取得的成就己经达到密码学上的实用标准了。另外，由于这一时期计算机软件和硬件技术的突飞猛进，椭圆曲线点加也可以很容易的实现了。1998年以后，ansi,ieee,iso,nist等国际组织陆续地将椭圆曲线密码系统列为标准,2000年，koblitz,menezes和vanstonc等大师对椭圆曲线密码系统的整体发展状况做了客观的分析，为其商业应用打下了坚实的基础。1.3 混沌理论的发展历史最早对混沌进行研究的是法国庞加莱(h.poincare)9。1913年，他在研究能否从数学上证明太阳系的稳定性问题时，把动力学系统和拓扑学有机地结合起来，并提出三体问题在一定范围内其解是随机的。1964年，法国天文学m.henon发现，一个自由度为2的不可积的保守哈密顿系统，当能量渐高时其运动轨迹在相空间中分布越来越无规律，给出了henon映射。1975年，美籍华人学者李天岩(t.y.li)和他的导师美国数学家j.a.yorke发表period three implies chaos一文5,首次使用“混沌”这个名词，并为后来学者所接受。1976年，美国数学生态学家r.may在文章具有极复杂动力学的简单数学模型中详细描述了logistic映射的混沌行为，并指出生态学中一些非常简单的数学模型，可能具有非常复杂的动力学行为。进入20世纪80年代，人们着重研究了系统如何以有序到新的混沌以及混沌的性质和特点，并进入了混沌理论的应用阶段。90年代以来，随着非线性科学和混沌理论的发展，混沌科学与其他应用学科相互交互、相互渗透、相互促进，其在电子学、信息科学、图像处理等领域有了广泛应用，混沌密码学就是其中之一。1.4 研究的主要内容和方法 本文的主要内容有:1. 研究了目前流行的的几种加密算法:椭圆曲线加密算法、混沌加密2. 研究了混沌密码和ecc算法所涉及的数学原理和实现方法，分析了两种算法的优点和不足，提出了基于混沌与ecc的混合密码体制，并通过大量材料证明该混合密码体制优于其他密码体制。3. 通过混沌和ecc相结合的加密解密系统的实现来验证该混合密码体制能够正确的进行加密和解密。4. 提出两种基于混沌椭圆曲线用于数字签名的方案，并分析设计并实现了两种方案。1.5 论文的组织安排第一章 绪论：对本文的研究内容、研究目标、研究方法和预期研究结果进行了概述，多层次反应了本课题的科学意义和实用价值。 第二章 混沌密码学原理：学习了混沌密码学的基本概念和原理,研究了混沌映射logistic的数学基础。 第三章 椭圆曲线算法原理分析:学习了有限域的的基本概念和运算。研究了椭圆曲线的算法原理以及在有限域上的运算。 第四章 基于椭圆曲线的混沌的密码系统构造：混沌与ecc混合加密体制方案的提出，设计并实现系统。 第五章 基于混沌与椭圆曲线的数字签名算法：提出两种基于混沌椭圆曲线用于数字签名的方案，分析设计并实现了两种方案。 第六章 系统性能及安全性分析。 第七章 总结与展望。2 混沌密码学原理2.1 混沌的的定义混沌现象是非线性确定性系统中的一种类似随机的过程，把两个十分相近的初值带入同一个混沌函数进行迭代运算，经过一定阶段的运算后，数值序列变得毫不相关。它隶属于确定性系统却难于预测，隐含于复杂系统但又不可分解，看似“混乱无序”，实则颇有规律。混沌密码是鉴于混沌系统对系统的参数和初始条件变化非常敏感这一事实来设计的。其基本思想，一是采用流密码的思想，将混沌系统作为伪随机序列发生器，由混沌系统产生的伪随机序列与明文进行加密操作输出密文；二是采用分组密码的思想，将加密系统的密钥设置为混沌系统的参数，而将明文设置为混沌系统的初始条件，或者不改变混沌系统的参数，而是将加密系统的密钥设置为混沌系统的初始条件，将明文设置为混沌系统的另一部分初始条件。2.2 混沌数学基础混沌现象是在非线性动力系统中出现的确定性的、类似随机的过程，这种过程既非周期又不收敛，并且对切始值有极其敏感的依赖性，一维离散时间非线性动力系统定义如下： 其中, xkp ,k=0,1,2,3,，我们称其为状态。而: pp 是一个映射，将当前状态xk映射到下一个状态xk+1。如果我们从一个初始值x0 开始，反复应用， 就得到一个序列xk, k=0,1,2,3,。该序列称为该离散时间动力系统的一条轨迹。一类非常简单却被广泛研究的动力系统是logistic映射，其定义如下：其中， 0 4 称为分枝参数，xk (0,1)。混沌动力系统的研究工作指出，当3.5699456=1900 plot(u,x); title(logistic map); xlabel(a); ylabel(x(n); hold on; endend 图1 matlab下logistic 映射从上图可以看出，当3.6时，logistic映射处于混沌状态。3 椭圆曲线算法原理分析3.1 基本概念3.1.1 群和域定义3.1 如果一个非空的集合g，对于代数运算来说满足以下条件： g对于运算是封闭的：对于任意的a, bg，满足abg；结合律成立：对于任意的a, b, cg，满足(ab)ca(bc)；存在单位元e，对于任意的ag，满足eaa；对于g中的每一个元a，g中存在逆元a1使a1ae。则称g对于运算做成一个群。定义3.2 如果群g的运算“”还满足交换律，即对任意a,bg，有ab=ba，则称g为一个交换群，或阿贝尔(abel)群。定义3.3 如果一个非空集合r，对于一个称为加法的代数运算和另一个称为乘法的代数运算满足：r对于加法运算构成一个交换群（加法单位元称为零元）；r中至少含有一个非零元；r对于乘法运算封闭，且满足结合律；有乘法单位元；非零元有乘法逆元；乘法交换律成立；左右分配律都成立。则称r对于该加法和乘法构成一个域。元素个数有限的域称为有限域。由于它首先由e伽罗华所发现，因而又被称为伽罗华域(galois field),两种常用的有限域是素数域gf(p)和特征为2的有限域gf(2m)。3.1.2 椭圆曲线椭圆曲线密码体制来源于对椭圆曲线的研究，所谓椭圆曲线指的是由韦尔斯特拉斯（weierstrass）方程： (1)所确定的平面曲线。其中系数ai(i=1,2,6)定义在某个域上，可以是有理数域、实数域、复数域，还可以是有限域gf，椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。该曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个abel群。在等式 mp=p+p+p=q (2) 中，已知m和点p求点q比较容易，反之已知点q和点p求m却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题。定义3.4：设 gf(p)是一个特征p2,3的有限域，a ,bgf (p)，满足。满足方程的点(x ,y )gf (p) gf (p)和特殊点o(称为无穷远点)组成的集合称为基于有限域gf(p)上的椭圆曲线，记为ep(a,b)。3.2 ecc算法基础3.2.1运算分层根据椭圆曲线上的点构成abel群的运算特点，点乘运算需要转化为点加运算来实现，但椭圆曲线上的点重合的时候点运算就变成了倍点运算，所以实际上需要的是点加、点乘与倍点运算。而椭圆曲线上的点加、点乘与倍点运算则必须转换成有限域上的运算来实现，需要转化为有限域上的模逆、模乘、模平方与模逆。 图2 ecc分层结构图3.2.2 有限域上的运算 有限域的元素的个数称为有限域的阶。存在一个q阶的有限域f，当且仅当g是一个素数p的幂，即q=pn，其中p是一个素数并称之为域f的特征，n是一个正整数。当n=1时，则域f就称为素域，否则称为扩域。有限域上的算法包括：多精度加法，多精度减法、加法、减法、乘法、求逆素数域fp上算法如下表，详见附录1。 表1 有限域上算法算法输入输出1多精度加法整数a, b0,2wt(e,c),其中c=a+b mod 2wt, e是进位2多精度减法整数a, b0,2wt(e,c),其中c=a-b mod 2wt, e是借位3模加模数p和整数a, b0,p-1c=(a+ b) mod p4模减模数p和整数a, b0,p-1c=(a-b) mod p5模乘模数p和整数a, b0,p-1c=(a. b) mod p6模平方模数p和整数a 0,p-1c=a2 mod p7模幂奇数模p，r=2wt,p=-p-1 mod r,x0,p),e=(el,e1,e0)xe mod p8模逆素数p，域fp上的非零元素a1,ak域元素a1-1,ak-1,其中ai.ai-11 mod p3.2.2椭圆曲线的参数 椭圆曲线的阶定义为曲线上点的个数，记作#e(fp)。p是椭圆曲线e上的一点，若存在最小的正整数n，使得npo，其中o是无穷原点，则称n是p点的阶。椭圆曲线上的点的个数，记做e(a, b)。描述一条有限域fp 上椭圆曲线，常用到六个参量：t=(p, a, b, g, n, h)。p、a、b 用来确定一条椭圆曲线，g 为基点，n 为点g 的阶,h 是椭圆曲线上所有点的个数m 与n 相除的整数部分这几个参量取值的选择，直接影响了加密的安全性。参参量值一般要求满足以下几个条件：1. p当然越大越安全，但越大，计算速度会变慢，200 位左右可以满足一般安全要求；2. pnh；3. pt1(mod n)，1t0,则qq+pu；否则，若u0,则q=q+p4.5 ii+15. 返回(q)3.3 ecc算法原理分析椭圆曲线密码算法(ecc)的安全性依赖于有限域上点群元素求阶，属于离散对数难题。令为有限域，e是上的椭圆曲线，p是e上的点，且阶是素数n，并记为d=1,2,n-1.算法描述如下：1) 信息传递各方通过参数组(p,e,p,n)选取密钥dd，并计算公钥q=dp。2) 信息发送方表示明文m为e上的点。3) 随机选取kd,并利用接收者的公钥q计算和发送c4) 信息接收者用自己的私钥d通过下公式进行解密 4 基于椭圆曲线的混沌的密码系统构造4.1 混沌理论与密码学混沌现象是非线性确定性系统中的一种类似随机的过程，把两个十分相近的初值带入同一个混沌函数进行迭代运算，经过一定阶段的运算后，数值序列变得毫不相关。它隶属于确定性系统却难于预测，隐含于复杂系统但又不可分解，看似“混乱无序”，实则颇有规律。shannon在他的论文3中写到，一个好的加密系统，它的函数必须是复杂的，并且一个小的变化必然导致结果发生很大的变化。这些密码学特性与混沌系统的特性有着巨大的相似性。如下表：表1 混沌理论与密码学的相似与不同之处 混沌理论与密码学的相似与不同之处相似点对初始条件和控制参数的极端敏感性扩散类似随机的行为和长周期的不稳定轨道伪随机信号混沌映射通过迭代将初始域扩散到整个相空间密码算法通过加密产生预期的扩散和混乱混沌映射参数加密算法密钥不同点混沌映射定义在实数域上加密算法定义在有限集上？（目前还没有相对关系）密码系统安全性和性能的分析理论混沌的轨道混合(mixing)特性(与轨道发散和初值敏感性直接相关)对应于传统加密系统的扩散特性，而混沌信号的类随机特性和对系统参数的敏感性对应于传统加密系统的混乱特性。可见，混沌具有的优异混合特性验证了混沌加密器的扩散和混乱作用可以和传统加密算法一样好。混沌和密码学之间具有的天然的联系和结构上的某些相似性，启示着人们把混沌应用于密码学领域。shannon在其经典文章3中已将混沌理论所具有的混合、对参数和初值的敏感性等基本特征应用到密码学中，并提出了密码学中用于指导密码设计的两个原则：扩散(diffusion)和混乱(confusion)。扩散方式是将明文冗余度分散到密文中使之分散开来，以便隐藏明文的统计结构，实现方式是使得明文的每一位影响密文中多位的值。混乱则是用于掩盖明文、密文和密钥之间的关系，使密钥和密文之间的统计关系变得尽可能复杂，导致密码攻击者无法从密文推理得到密钥。混沌和密码学之间具有天然联系和结构上的某种相似性,利用混沌系统,可以产生数量众多、非相关、类似噪声、可以再生的混沌序列,这种序列难于重构和预测,从而使密码分析者难以破译。4.2 系统设计与实现4.2.1 参数生成1) 信息传递各方通过参数组(p, e, p，n)选取密钥dd，并计