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

1基于混沌的椭圆曲线密码系统的研究与实现桂加睿摘要密码学已经有上千年的历史，一直以来，人们都用代数方法来研究密码学问题，并产生了大量的加解密算法，如DES,AES,RSA等等。同时，近年来，人们经过大量研究发现混沌系统有以下重要的特性高度不可预测性、看似随机性、对初始条件和参数敏感性等。这些特性与密码学特性有巨大相似性,促使人们把混沌理论运用到密码学领域。椭圆曲线加密系统（ECC）的安全性基于椭圆曲线离散对数问题的难解性。它是迄今为止每比特具有最高安全强度的密码系统。同其它非对称加密体制相比，椭圆曲线密码系统除了安全性有着高外，还具有计算负载小、密钥尺寸短、占用带宽少等优点。因此，椭圆曲线密码系统被认为是下一代最通用的公钥密码系统。混沌系统和密码学之间有天然的联系和结构上的相似性，启示着人们把混沌理论应用于密码学领域，混沌理论与常规密码学之间的广泛联系激起了越来越多的密码学研究者的兴趣，利用混沌系统构造密码算法成为信息安全领域的一个重要研究热点。本文以椭圆曲线加密系（ECC，ELLIPTICCURVESCRYPTOSYSTEM）为研究对象，分析了椭圆曲线的的数学原理和工作原理，设计实现了基于混沌理论的ECC密码系统，实现了基于混沌ECC用于数字签名的基本算法，从性能、安全性等方面分析了系统的技术优势。关键字混沌密码学、离散对数、群域、椭圆曲线、数字签名2RESEARCHANDIMPLEMENTATIONOFELLIPTICCURVECRYPTOGRAPHYALGORITHMBASEONCHAOSGUI,JIARUIABSTRACTCRYPTOGRAPHYHASBEENFORTHOUSANDSOFYEARS,PEOPLEHAVETOUSEALGEBRAICMETHODSTOSTUDYTHEPROBLEMOFCRYPTOGRAPHY,ANDPRODUCEALARGENUMBEROFCRYPTOGRAPHICSYSTEMS,SUCHASDES,AES,RSAETCONTHEOTHERHAND,INRECENTYEARS,PEOPLEHASDONEALOTOFRESEARCHONTHECHAOTICSYSTEM,RECOGNIZEDSOMEOFITSIMPORTANTFEATURES,SUCHASVERYUNPREDICTABILITYNATUREOFSEEMINGLYRANDOM,ONTHEINITIALCONDITIONSANDPARAMETERSENSITIVITYTHESEFEATURESAREGREATSIMILARITIESWITHCRYPTOGRAPHICPROPERTIESELLIPTICCURVECRYPTOGRAPHYECCSECURITYISBASEDONELLIPTICCURVEDISCRETELOGARITHMPROBLEMOFINTRACTABILITY,SOFAR,THEELLIPTICCURVECRYPTOSYSTEMECCPROVIDESTHEHIGHESTSTRENGTHPERBITOFANYCRYPTOSYSTEMKNOWNINADDITIONTOITSHIGHSECURITY,ECCALSOHASMANYOTHERMERITSOVEROTHERPUBLICKEYCRYPTOSYSTEMSSUCHASLESSCOMPUTATIONOVERHEADSSHORTERKEYSIZE,CONSIDERABLEBANDWIDTHSAVINGS,ANDSOONTHEREFORE,THEELLIPTICCURVECRYPTOSYSTEMISCONSIDEREDTHENEXTGENERATIONOFTHEMOSTCOMMONPUBLICKEYCRYPTOSYSTEMBETWEENCHAOSANDCRYPTOGRAPHYHASTHENATURALLINKANDSTRUCTURALSIMILARITY,REVEALSTOPEOPLETHECHAOTICFIELDOFAPPLIEDCRYPTOGRAPHY,CHAOSTHEORYANDCONVENTIONALCRYPTOGRAPHYANDEXTENSIVELINKSBETWEENTHEMOREANDMOREAROUSEDINTERESTINCRYPTOGRAPHYRESEARCHERS,TOCONSTRUCTTHECRYPTOGRAPHICALGORITHMUSINGCHAOTICFIELDOFINFORMATIONSECURITYTOBECOMEANIMPORTANTRESEARCHFOCUSINTHISPAPER,THEELLIPTICCURVESCRYPTOSYSTEMECCASTHERESEARCHOBJECTILLUSTRATESTHEELLIPTICCURVEMATHEMATICALPRINCIPLEANDTHEPRINCIPLE,COMBINEDWITHCHAOSTHEORY,DESIGNANDIMPLEMENTATIONOFECCBASEDONCHAOSTHEORYCRYPTOGRAPHY,FINALLY,IMPLEMENTEDTHEBASICECCDIGITALSIGNATUREALGORITHMWITHCHAOSANALYZETECHNOLOGICALADVANTAGESOFTHESYSTEMONPERFORMANCE,SECURITYETCKEYWORDSCHAOSCRYPTOGRAPHY,ECC,ECDLP,DIGITALSIGNATURE,GROUP,FIELD3目录1绪论411课题研究的背景和意义412椭圆曲线密码的发展历史413混沌理论的发展历史514研究的主要内容和方法515论文的组织安排62混沌密码学原理621混沌的的定义622混沌数学基础63椭圆曲线算法原理分析831基本概念8311群和域8312椭圆曲线832ECC算法基础9321运算分层9322有限域上的运算9322椭圆曲线的参数10323椭圆曲线上的运算1133ECC算法原理分析134基于椭圆曲线的混沌的密码系统构造1341混沌理论与密码学1342系统设计与实现14421参数生成14422加密过程14423解密过程165基于混沌与椭圆曲线的数字签名算法1751方案一混沌映射消息摘要1752方案二混沌映射消息后产生摘要196系统性能及安全性分析2161系统运行2162性能分析2463安全性分析257总结与展望26致谢27参考文献28附录一有限域上算法29附录二椭圆曲线上算法3141绪论11课题研究的背景和意义1976年DIFFIE和HELLMAN提出公钥密码思想以来，国际上提出了许多种公钥密码体制的实现方案。一些已经被攻破，一些被证明是不可行的。目前，只有3类公钥密码体制被认为是安全有效的，按照其所依据的数学难题划分为基于大整数分解问题（IFP），如RSA体制和RABIN体制；基于有限域离散对数问题（DLP），如DIFFIEHELLMAN体制ELGAMAL体制；基于椭圆曲线离散对数问题（ECDLPECDLP），如椭圆密码体制。椭圆曲线应用到密码学上最早是由VICTORMILLER1和NEALKOBLITZ2在1985年分别独立提出的。它是目前已知的公钥体制中，对每一比特所提供加密强度最高的一种体制。它具有安全性高、密钥量小、灵活性好的特点，受到了国际上的广泛关注。而SET协议的制定者已把它作为下一代SET协议中缺省的公钥密码算法。深入研究基于椭圆曲线离散对数问题的公钥密码具有很大的现实意义。混沌现象是非线性确定性系统中的一种类似随机的过程，把两个十分相近的初值带入同一个混沌函数进行迭代运算，经过一定阶段的运算后，数值序列变得毫不相关。它隶属于确定性系统却难于预测，隐含于复杂系统但又不可分解，看似“混乱无序”，实则颇有规律。SHANNON在他的论文3中写到，一个好的加密系统，它的函数必须是复杂的，并且一个小的变化必然导致结果发生很大的变化。这些密码学特性与混沌系统的特性有着巨大的相似性，促使人们把混沌理论运用到密码学领域。由于混沌系统对初值和参数极其敏感，同时还具有非周期性和伪随机性的特点，近来，它引起了密码学领域的广泛关注，据此提出了密码学中用于指导密码设计的两个基本原则扩散和混乱,并产生出大量富有成效的研究成果。混沌和密码学之间计有的天然的联系和结构上的相似性，启示着人们把混沌应用于密码学领域，混沌理论与常规密码学之间的广泛联系激起了越来越多的密码学研究者的兴趣,利用混沌系统构造密码算法成为信息安全领域的一个重要研究热点。12椭圆曲线密码的发展历史人类从十七世纪就开始研究椭圆曲线了，但真正把其应用到密码学中是1985年由VICTORMILLER1和NEALKOBLITZ2分别独立提出的。他们利用椭圆曲线上的点构造了椭圆曲线密码系统。之后出现了很多针对椭圆曲线密码系统的研究，主要集中在三个方面1椭圆曲线密码系统的构造包括有限域的选择和安全曲线的选择以及密码体制的构造。2椭圆曲线密码系统的分析就是在仅知道由ECC加密的密文的情况下，恢复出明文。包括对ECC的攻击方法的选择、验证等等。53椭圆曲线密码系统的快速实现大体可分为软件和硬件两个方面的快速实现。1990年，MENEZES使用了一类特殊的曲线超奇异椭圆曲线这种曲线有理点群的阶可以很容易的得到并且实现速度也很快。但是到1993年，MENEZES本人和他的两个合作者发现了对这种曲线的一种有效的攻击方法，称为“MOV攻击”，这种方法可以把椭圆曲线离散对数问题化约到某个次数较低的域上，从而在多项式时间内求解。但与此同时，椭圆曲线上有理点个数的计算问题得到了很大的突破。1989到1992年间，ATIKIN和ELKIE对1985年提出的SCHOOF算法作出了重大改进，到1995年，人们在这一问题上取得的成就己经达到密码学上的实用标准了。另外，由于这一时期计算机软件和硬件技术的突飞猛进，椭圆曲线点加也可以很容易的实现了。1998年以后，ANSI,IEEE,ISO,NIST等国际组织陆续地将椭圆曲线密码系统列为标准,2000年，KOBLITZ,MENEZES和VANSTONC等大师对椭圆曲线密码系统的整体发展状况做了客观的分析，为其商业应用打下了坚实的基础。13混沌理论的发展历史最早对混沌进行研究的是法国庞加莱HPOINCARE9。1913年，他在研究能否从数学上证明太阳系的稳定性问题时，把动力学系统和拓扑学有机地结合起来，并提出三体问题在一定范围内其解是随机的。1964年，法国天文学MHENON发现，一个自由度为2的不可积的保守哈密顿系统，当能量渐高时其运动轨迹在相空间中分布越来越无规律，给出了HENON映射。1975年，美籍华人学者李天岩TYLI和他的导师美国数学家JAYORKE发表PERIODTHREEIMPLIESCHAOS一文5,首次使用“混沌”这个名词，并为后来学者所接受。1976年，美国数学生态学家RMAY在文章具有极复杂动力学的简单数学模型中详细描述了LOGISTIC映射的混沌行为，并指出生态学中一些非常简单的数学模型，可能具有非常复杂的动力学行为。进入20世纪80年代，人们着重研究了系统如何以有序到新的混沌以及混沌的性质和特点，并进入了混沌理论的应用阶段。90年代以来，随着非线性科学和混沌理论的发展，混沌科学与其他应用学科相互交互、相互渗透、相互促进，其在电子学、信息科学、图像处理等领域有了广泛应用，混沌密码学就是其中之一。14研究的主要内容和方法本文的主要内容有1研究了目前流行的的几种加密算法椭圆曲线加密算法、混沌加密2研究了混沌密码和ECC算法所涉及的数学原理和实现方法，分析了两种算法的优点和不足，提出了基于混沌与ECC的混合密码体制，并通过大量材料证明该混合密码体制优于其他密码体制。63通过混沌和ECC相结合的加密解密系统的实现来验证该混合密码体制能够正确的进行加密和解密。4提出两种基于混沌椭圆曲线用于数字签名的方案，并分析设计并实现了两种方案。15论文的组织安排第一章绪论对本文的研究内容、研究目标、研究方法和预期研究结果进行了概述，多层次反应了本课题的科学意义和实用价值。第二章混沌密码学原理学习了混沌密码学的基本概念和原理,研究了混沌映射LOGISTIC的数学基础。第三章椭圆曲线算法原理分析学习了有限域的的基本概念和运算。研究了椭圆曲线的算法原理以及在有限域上的运算。第四章基于椭圆曲线的混沌的密码系统构造混沌与ECC混合加密体制方案的提出，设计并实现系统。第五章基于混沌与椭圆曲线的数字签名算法提出两种基于混沌椭圆曲线用于数字签名的方案，分析设计并实现了两种方案。第六章系统性能及安全性分析。第七章总结与展望。2混沌密码学原理21混沌的的定义混沌现象是非线性确定性系统中的一种类似随机的过程，把两个十分相近的初值带入同一个混沌函数进行迭代运算，经过一定阶段的运算后，数值序列变得毫不相关。它隶属于确定性系统却难于预测，隐含于复杂系统但又不可分解，看似“混乱无序”，实则颇有规律。混沌密码是鉴于混沌系统对系统的参数和初始条件变化非常敏感这一事实来设计的。其基本思想，一是采用流密码的思想，将混沌系统作为伪随机序列发生器，由混沌系统产生的伪随机序列与明文进行加密操作输出密文；二是采用分组密码的思想，将加密系统的密钥设置为混沌系统的参数，而将明文设置为混沌系统的初始条件，或者不改变混沌系统的参数，而是将加密系统的密钥设置为混沌系统的初始条件，将明文设置为混沌系统的另一部分初始条件。22混沌数学基础混沌现象是在非线性动力系统中出现的确定性的、类似随机的过程，这种过程既非周期又不收敛，并且对切始值有极其敏感的依赖性，一维离散时间非线性动力系统定义如下1KKX7其中,XKP,K0,1,2,3,，我们称其为状态。而PP是一个映射，将当前状态XK映射到下一个状态XK1。如果我们从一个初始值X0开始，反复应用，就得到一个序列XK,K0,1,2,3,。该序列称为该离散时间动力系统的一条轨迹。一类非常简单却被广泛研究的动力系统是LOGISTIC映射，其定义如下1KKXX其中，04称为分枝参数，XK0,1。混沌动力系统的研究工作指出，当356994561900PLOTU,XTITLELOGISTICMAPXLABELAYLABELXNHOLDONENDEND图1MATLAB下LOGISTIC映射8从上图可以看出，当36时，LOGISTIC映射处于混沌状态。3椭圆曲线算法原理分析31基本概念311群和域定义31如果一个非空的集合G，对于代数运算来说满足以下条件G对于运算是封闭的对于任意的A,BG，满足ABG；结合律成立对于任意的A,B,CG，满足ABCABC；存在单位元E，对于任意的AG，满足EAA；对于G中的每一个元A，G中存在逆元A1使A1AE。则称G对于运算做成一个群。定义32如果群G的运算“”还满足交换律，即对任意A,BG，有ABBA，则称G为一个交换群，或阿贝尔ABEL群。定义33如果一个非空集合R，对于一个称为加法的代数运算和另一个称为乘法的代数运算满足R对于加法运算构成一个交换群（加法单位元称为零元）；R中至少含有一个非零元；R对于乘法运算封闭，且满足结合律；有乘法单位元；非零元有乘法逆元；乘法交换律成立；左右分配律都成立。则称R对于该加法和乘法构成一个域。元素个数有限的域称为有限域。由于它首先由E伽罗华所发现，因而又被称为伽罗华域GALOISFIELD,两种常用的有限域是素数域GFP和特征为2的有限域GF2M。312椭圆曲线椭圆曲线密码体制来源于对椭圆曲线的研究，所谓椭圆曲线指的是由韦尔斯特拉斯（WEIERSTRASS）方程1232146YAXYAX所确定的平面曲线。其中系数AII1,2,6定义在某个域上，可以是有理数域、实数域、复数域，还可以是有限域GF，椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。9该曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个ABEL群。在等式MPPPPQ2中，已知M和点P求点Q比较容易，反之已知点Q和点P求M却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题。定义34设GFP是一个特征P2,3的有限域，A,BGFP，满足。满足方程的点X,YGFPGFP和特殊32470AB23YXAB点O称为无穷远点组成的集合称为基于有限域GFP上的椭圆曲线，记为EPA,B。32ECC算法基础321运算分层根据椭圆曲线上的点构成ABEL群的运算特点，点乘运算需要转化为点加运算来实现，但椭圆曲线上的点重合的时候点运算就变成了倍点运算，所以实际上需要的是点加、点乘与倍点运算。而椭圆曲线上的点加、点乘与倍点运算则必须转换成有限域上的运算来实现，需要转化为有限域上的模逆、模乘、模平方与模逆。控制接口MKQ倍点点加模乘模平方模加模逆点乘群操作层域操作层图2ECC分层结构图322有限域上的运算有限域的元素的个数称为有限域的阶。存在一个Q阶的有限域F，当且仅当G是一个素数P的幂，即QPN，其中P是一个素数并称之为域F的特征，N是一个正整数。当N1时，则域F就称为素域，否则称为扩域。有限域上的算法包括多精度加法，多精度减法、加法、减法、乘法、求逆素数域FP上算法如下表，详见附录1。10表1有限域上算法算法输入输出1多精度加法整数A,B0,2WT,C,其中CABMOD2WT,是进位2多精度减法整数A,B0,2WT,C,其中CABMOD2WT,是借位3模加模数P和整数A,B0,P1CABMODP4模减模数P和整数A,B0,P1CABMODP5模乘模数P和整数A,B0,P1CABMODP6模平方模数P和整数A0,P1CA2MODP7模幂奇数模P，R2WT,PP1MODR,X0,P,EEL,E1,E0XEMODP8模逆素数P，域FP上的非零元素A1,AK域元素A11,AK1