畢業(yè)設(shè)計（論文）基于混沌的橢圓曲線密碼系統(tǒng)的研究與實現(xiàn)

1、基于混沌的橢圓曲線密碼系統(tǒng)的研究與實現(xiàn) 桂加睿摘要密碼學已經(jīng)有上千年的歷史，一直以來，人們都用代數(shù)方法來研究密碼學問題，并產(chǎn)生了大量的加解密算法，如des,aes,rsa等等。同時，近年來，人們經(jīng)過大量研究發(fā)現(xiàn)混沌系統(tǒng)有以下重要的特性：高度不可預測性、看似隨機性、對初始條件和參數(shù)敏感性等。這些特性與密碼學特性有巨大相似性,促使人們把混沌理論運用到密碼學領(lǐng)域。 橢圓曲線加密系統(tǒng)（ecc）的安全性基于橢圓曲線離散對數(shù)問題的難解性。它是迄今為止每比特具有最高安全強度的密碼系統(tǒng)。同其它非對稱加密體制相比，橢圓曲線密碼系統(tǒng)除了安全性有著高外，還具有計算負載小、密鑰尺寸短、占用帶寬少等優(yōu)點。因此，橢圓曲線

2、密碼系統(tǒng)被認為是下一代最通用的公鑰密碼系統(tǒng)?；煦缦到y(tǒng)和密碼學之間有天然的聯(lián)系和結(jié)構(gòu)上的相似性，啟示著人們把混沌理論應用于密碼學領(lǐng)域，混沌理論與常規(guī)密碼學之間的廣泛聯(lián)系激起了越來越多的密碼學研究者的興趣，利用混沌系統(tǒng)構(gòu)造密碼算法成為信息安全領(lǐng)域的一個重要研究熱點。本文以橢圓曲線加密系（ecc，elliptic curves cryptosystem）為研究對象，分析了橢圓曲線的的數(shù)學原理和工作原理，設(shè)計實現(xiàn)了基于混沌理論的ecc密碼系統(tǒng)，實現(xiàn)了基于混沌ecc用于數(shù)字簽名的基本算法，從性能、安全性等方面分析了系統(tǒng)的技術(shù)優(yōu)勢。關(guān)鍵字：混沌密碼學、離散對數(shù)、群域、橢圓曲線、數(shù)字簽名research a

3、nd 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

4、 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 p

5、ropertieselliptic 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

6、 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

7、 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 informa

8、tion 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,

9、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 橢圓曲線密碼的發(fā)展歷史41.3 混沌理論的發(fā)展歷史51.4 研究的主要內(nèi)容和方法51.5 論文的組織

10、安排62 混沌密碼學原理62.1 混沌的的定義62.2 混沌數(shù)學基礎(chǔ)63 橢圓曲線算法原理分析83.1 基本概念83.1.1 群和域83.1.2 橢圓曲線83.2 ecc算法基礎(chǔ)93.2.1運算分層93.2.2 有限域上的運算93.2.2橢圓曲線的參數(shù)103.2.3 橢圓曲線上的運算113.3 ecc算法原理分析134 基于橢圓曲線的混沌的密碼系統(tǒng)構(gòu)造134.1 混沌理論與密碼學134.2 系統(tǒng)設(shè)計與實現(xiàn)144.2.1 參數(shù)生成144.2.2 加密過程144.2.3 解密過程165 基于混沌與橢圓曲線的數(shù)字簽名算法175.1 方案一 混沌映射消息摘要175. 2 方案二 混沌映射消息后產(chǎn)生摘要

11、196 系統(tǒng)性能及安全性分析216.1 系統(tǒng)運行216.2 性能分析246.3 安全性分析257 總結(jié)與展望26致謝27參考文獻28附錄一 有限域上算法29附錄二 橢圓曲線上算法311 緒論1.1 課題研究的背景和意義1976年diffie和hellman提出公鑰密碼思想以來，國際上提出了許多種公鑰密碼體制的實現(xiàn)方案。一些已經(jīng)被攻破，一些被證明是不可行的。目前，只有3類公鑰密碼體制被認為是安全有效的，按照其所依據(jù)的數(shù)學難題劃分為：基于大整數(shù)分解問題（ifp），如rsa體制和rabin體制；基于有限域離散對數(shù)問題（dlp），如diffie-hellman體制elgamal體制；基于橢圓曲線離散對

12、數(shù)問題（ecdlp ecdlp），如橢圓密碼體制。橢圓曲線應用到密碼學上最早是由victor miller1和neal koblitz2在1985年分別獨立提出的。它是目前已知的公鑰體制中，對每一比特所提供加密強度最高的一種體制。它具有安全性高、密鑰量小、靈活性好的特點，受到了國際上的廣泛關(guān)注。而set協(xié)議的制定者已把它作為下一代set協(xié)議中缺省的公鑰密碼算法。深入研究基于橢圓曲線離散對數(shù)問題的公鑰密碼具有很大的現(xiàn)實意義。混沌現(xiàn)象是非線性確定性系統(tǒng)中的一種類似隨機的過程，把兩個十分相近的初值帶入同一個混沌函數(shù)進行迭代運算，經(jīng)過一定階段的運算后，數(shù)值序列變得毫不相關(guān)。它隸屬于確定性系統(tǒng)卻難于預測

13、，隱含于復雜系統(tǒng)但又不可分解，看似“混亂無序”，實則頗有規(guī)律。shannon在他的論文3中寫到，一個好的加密系統(tǒng)，它的函數(shù)必須是復雜的，并且一個小的變化必然導致結(jié)果發(fā)生很大的變化。這些密碼學特性與混沌系統(tǒng)的特性有著巨大的相似性，促使人們把混沌理論運用到密碼學領(lǐng)域。由于混沌系統(tǒng)對初值和參數(shù)極其敏感，同時還具有非周期性和偽隨機性的特點，近來，它引起了密碼學領(lǐng)域的廣泛關(guān)注，據(jù)此提出了密碼學中用于指導密碼設(shè)計的兩個基本原則：擴散和混亂,并產(chǎn)生出大量富有成效的研究成果。混沌和密碼學之間計有的天然的聯(lián)系和結(jié)構(gòu)上的相似性，啟示著人們把混沌應用于密碼學領(lǐng)域，混沌理論與常規(guī)密碼學之間的廣泛聯(lián)系激起了越來越多的密

14、碼學研究者的興趣,利用混沌系統(tǒng)構(gòu)造密碼算法成為信息安全領(lǐng)域的一個重要研究熱點。1.2 橢圓曲線密碼的發(fā)展歷史人類從十七世紀就開始研究橢圓曲線了，但真正把其應用到密碼學中是1985年由victor miller1和neal koblitz2分別獨立提出的。他們利用橢圓曲線上的點構(gòu)造了橢圓曲線密碼系統(tǒng)。之后出現(xiàn)了很多針對橢圓曲線密碼系統(tǒng)的研究，主要集中在三個方面:1. 橢圓曲線密碼系統(tǒng)的構(gòu)造:包括有限域的選擇和安全曲線的選擇以及密碼體制的構(gòu)造。2. 橢圓曲線密碼系統(tǒng)的分析：就是在僅知道由ecc加密的密文的情況下，恢復出明文。包括對ecc的攻擊方法的選擇、驗證等等。3. 橢圓曲線密碼系統(tǒng)的快速實現(xiàn)：

15、大體可分為軟件和硬件兩個方面的快速實現(xiàn)。1990年，menezes使用了一類特殊的曲線超奇異橢圓曲線這種曲線有理點群的階可以很容易的得到并且實現(xiàn)速度也很快。但是到1993年，menezes本人和他的兩個合作者發(fā)現(xiàn)了對這種曲線的一種有效的攻擊方法，稱為“mov攻擊”，這種方法可以把橢圓曲線離散對數(shù)問題化約到某個次數(shù)較低的域上，從而在多項式時間內(nèi)求解。但與此同時，橢圓曲線上有理點個數(shù)的計算問題得到了很大的突破。1989到1992年間，atikin和elkie對1985年提出的schoof算法作出了重大改進，到1995年，人們在這一問題上取得的成就己經(jīng)達到密碼學上的實用標準了。另外，由于這一時期計算

16、機軟件和硬件技術(shù)的突飛猛進，橢圓曲線點加也可以很容易的實現(xiàn)了。1998年以后，ansi,ieee,iso,nist等國際組織陸續(xù)地將橢圓曲線密碼系統(tǒng)列為標準,2000年，koblitz,menezes和vanstonc等大師對橢圓曲線密碼系統(tǒng)的整體發(fā)展狀況做了客觀的分析，為其商業(yè)應用打下了堅實的基礎(chǔ)。1.3 混沌理論的發(fā)展歷史最早對混沌進行研究的是法國龐加萊(h.poincare)9。1913年，他在研究能否從數(shù)學上證明太陽系的穩(wěn)定性問題時，把動力學系統(tǒng)和拓撲學有機地結(jié)合起來，并提出三體問題在一定范圍內(nèi)其解是隨機的。1964年，法國天文學m.henon發(fā)現(xiàn)，一個自由度為2的不可積的保守哈密頓系

17、統(tǒng)，當能量漸高時其運動軌跡在相空間中分布越來越無規(guī)律，給出了henon映射。1975年，美籍華人學者李天巖(t.y.li)和他的導師美國數(shù)學家j.a.yorke發(fā)表period three implies chaos一文5,首次使用“混沌”這個名詞，并為后來學者所接受。1976年，美國數(shù)學生態(tài)學家r.may在文章具有極復雜動力學的簡單數(shù)學模型中詳細描述了logistic映射的混沌行為，并指出生態(tài)學中一些非常簡單的數(shù)學模型，可能具有非常復雜的動力學行為。進入20世紀80年代，人們著重研究了系統(tǒng)如何以有序到新的混沌以及混沌的性質(zhì)和特點，并進入了混沌理論的應用階段。90年代以來，隨著非線性科學和混沌

18、理論的發(fā)展，混沌科學與其他應用學科相互交互、相互滲透、相互促進，其在電子學、信息科學、圖像處理等領(lǐng)域有了廣泛應用，混沌密碼學就是其中之一。1.4 研究的主要內(nèi)容和方法 本文的主要內(nèi)容有:1. 研究了目前流行的的幾種加密算法:橢圓曲線加密算法、混沌加密2. 研究了混沌密碼和ecc算法所涉及的數(shù)學原理和實現(xiàn)方法，分析了兩種算法的優(yōu)點和不足，提出了基于混沌與ecc的混合密碼體制，并通過大量材料證明該混合密碼體制優(yōu)于其他密碼體制。3. 通過混沌和ecc相結(jié)合的加密解密系統(tǒng)的實現(xiàn)來驗證該混合密碼體制能夠正確的進行加密和解密。4. 提出兩種基于混沌橢圓曲線用于數(shù)字簽名的方案，并分析設(shè)計并實現(xiàn)了兩種方案。1

19、.5 論文的組織安排第一章 緒論：對本文的研究內(nèi)容、研究目標、研究方法和預期研究結(jié)果進行了概述，多層次反應了本課題的科學意義和實用價值。 第二章 混沌密碼學原理：學習了混沌密碼學的基本概念和原理,研究了混沌映射logistic的數(shù)學基礎(chǔ)。 第三章 橢圓曲線算法原理分析:學習了有限域的的基本概念和運算。研究了橢圓曲線的算法原理以及在有限域上的運算。 第四章 基于橢圓曲線的混沌的密碼系統(tǒng)構(gòu)造：混沌與ecc混合加密體制方案的提出，設(shè)計并實現(xiàn)系統(tǒng)。 第五章 基于混沌與橢圓曲線的數(shù)字簽名算法：提出兩種基于混沌橢圓曲線用于數(shù)字簽名的方案，分析設(shè)計并實現(xiàn)了兩種方案。 第六章 系統(tǒng)性能及安全性分析。 第七章

20、總結(jié)與展望。2 混沌密碼學原理2.1 混沌的的定義混沌現(xiàn)象是非線性確定性系統(tǒng)中的一種類似隨機的過程，把兩個十分相近的初值帶入同一個混沌函數(shù)進行迭代運算，經(jīng)過一定階段的運算后，數(shù)值序列變得毫不相關(guān)。它隸屬于確定性系統(tǒng)卻難于預測，隱含于復雜系統(tǒng)但又不可分解，看似“混亂無序”，實則頗有規(guī)律?；煦缑艽a是鑒于混沌系統(tǒng)對系統(tǒng)的參數(shù)和初始條件變化非常敏感這一事實來設(shè)計的。其基本思想，一是采用流密碼的思想，將混沌系統(tǒng)作為偽隨機序列發(fā)生器，由混沌系統(tǒng)產(chǎn)生的偽隨機序列與明文進行加密操作輸出密文；二是采用分組密碼的思想，將加密系統(tǒng)的密鑰設(shè)置為混沌系統(tǒng)的參數(shù)，而將明文設(shè)置為混沌系統(tǒng)的初始條件，或者不改變混沌系統(tǒng)的參數(shù)

21、，而是將加密系統(tǒng)的密鑰設(shè)置為混沌系統(tǒng)的初始條件，將明文設(shè)置為混沌系統(tǒng)的另一部分初始條件。2.2 混沌數(shù)學基礎(chǔ)混沌現(xiàn)象是在非線性動力系統(tǒng)中出現(xiàn)的確定性的、類似隨機的過程，這種過程既非周期又不收斂，并且對切始值有極其敏感的依賴性，一維離散時間非線性動力系統(tǒng)定義如下： 其中, xkp ,k=0,1,2,3,，我們稱其為狀態(tài)。而: pp 是一個映射，將當前狀態(tài)xk映射到下一個狀態(tài)xk+1。如果我們從一個初始值x0 開始，反復應用， 就得到一個序列xk, k=0,1,2,3,。該序列稱為該離散時間動力系統(tǒng)的一條軌跡。一類非常簡單卻被廣泛研究的動力系統(tǒng)是logistic映射，其定義如下：其中， 0 4 稱

22、為分枝參數(shù)，xk (0,1)。混沌動力系統(tǒng)的研究工作指出，當3.5699456< 4 時，logistic映射工作于混沌狀態(tài)。也就是說，由初始條件x0 在logistic映射的作用下所產(chǎn)生的序列 xk ; k=0,1,2,3.是非周期的、不收斂的并對初始值非常敏感。matlab下仿真代碼如下：x=0.1;u=2:0.001:4;for i=1:2000 x=u.*(x-x.2); if i>=1900 plot(u,x); title('logistic map'); xlabel('a'); ylabel('x(n)'); hold

23、 on; endend 圖1 matlab下logistic 映射從上圖可以看出，當>3.6時，logistic映射處于混沌狀態(tài)。3 橢圓曲線算法原理分析3.1 基本概念3.1.1 群和域定義3.1 如果一個非空的集合g，對于代數(shù)運算來說滿足以下條件： g對于運算是封閉的：對于任意的a, bg，滿足abg；結(jié)合律成立：對于任意的a, b, cg，滿足(ab)ca(bc)；存在單位元e，對于任意的ag，滿足eaa；對于g中的每一個元a，g中存在逆元a1使a1ae。則稱g對于運算做成一個群。定義3.2 如果群g的運算“”還滿足交換律，即對任意a,bg，有ab=ba，則稱g為一個交換群，或阿貝

24、爾(abel)群。定義3.3 如果一個非空集合r，對于一個稱為加法的代數(shù)運算和另一個稱為乘法的代數(shù)運算滿足：r對于加法運算構(gòu)成一個交換群（加法單位元稱為零元）；r中至少含有一個非零元；r對于乘法運算封閉，且滿足結(jié)合律；有乘法單位元；非零元有乘法逆元；乘法交換律成立；左右分配律都成立。則稱r對于該加法和乘法構(gòu)成一個域。元素個數(shù)有限的域稱為有限域。由于它首先由e伽羅華所發(fā)現(xiàn)，因而又被稱為伽羅華域(galois field),兩種常用的有限域是素數(shù)域gf(p)和特征為2的有限域gf(2m)。3.1.2 橢圓曲線橢圓曲線密碼體制來源于對橢圓曲線的研究，所謂橢圓曲線指的是由韋爾斯特拉斯（weierstr

25、ass）方程： (1)所確定的平面曲線。其中系數(shù)ai(i=1,2,6)定義在某個域上，可以是有理數(shù)域、實數(shù)域、復數(shù)域，還可以是有限域gf，橢圓曲線密碼體制中用到的橢圓曲線都是定義在有限域上的。該曲線上所有的點外加一個叫做無窮遠點的特殊點構(gòu)成的集合連同一個定義的加法運算構(gòu)成一個abel群。在等式 mp=p+p+p=q (2) 中，已知m和點p求點q比較容易，反之已知點q和點p求m卻是相當困難的，這個問題稱為橢圓曲線上點群的離散對數(shù)問題。定義3.4：設(shè) gf(p)是一個特征p2,3的有限域，a ,bgf (p)，滿足。滿足方程的點(x ,y )gf (p) ×gf (p)和特殊點o(稱為

26、無窮遠點)組成的集合稱為基于有限域gf(p)上的橢圓曲線，記為ep(a,b)。3.2 ecc算法基礎(chǔ)3.2.1運算分層根據(jù)橢圓曲線上的點構(gòu)成abel群的運算特點，點乘運算需要轉(zhuǎn)化為點加運算來實現(xiàn)，但橢圓曲線上的點重合的時候點運算就變成了倍點運算，所以實際上需要的是點加、點乘與倍點運算。而橢圓曲線上的點加、點乘與倍點運算則必須轉(zhuǎn)換成有限域上的運算來實現(xiàn)，需要轉(zhuǎn)化為有限域上的模逆、模乘、模平方與模逆。 圖2 ecc分層結(jié)構(gòu)圖3.2.2 有限域上的運算 有限域的元素的個數(shù)稱為有限域的階。存在一個q階的有限域f，當且僅當g是一個素數(shù)p的冪，即q=pn，其中p是一個素數(shù)并稱之為域f的特征，n是一個正整數(shù)

27、。當n=1時，則域f就稱為素域，否則稱為擴域。有限域上的算法包括：多精度加法，多精度減法、加法、減法、乘法、求逆素數(shù)域fp上算法如下表，詳見附錄1。 表1 有限域上算法算法輸入輸出1多精度加法整數(shù)a, bÎ0,2wt(e,c),其中c=a+b mod 2wt, e是進位2多精度減法整數(shù)a, bÎ0,2wt(e,c),其中c=a-b mod 2wt, e是借位3模加模數(shù)p和整數(shù)a, bÎ0,p-1c=(a+ b) mod p4模減模數(shù)p和整數(shù)a, bÎ0,p-1c=(a-b) mod p5模乘模數(shù)p和整數(shù)a, bÎ0,p-1c=(a. b) mo

28、d p6模平方模數(shù)p和整數(shù)a Î0,p-1c=a2 mod p7模冪奇數(shù)模p，r=2wt,p=-p-1 mod r,xÎ0,p),e=(el,e1,e0)xe mod p8模逆素數(shù)p，域fp上的非零元素a1,ak域元素a1-1,ak-1,其中ai.ai-1º1 mod p3.2.2橢圓曲線的參數(shù) 橢圓曲線的階定義為曲線上點的個數(shù)，記作#e(fp)。p是橢圓曲線e上的一點，若存在最小的正整數(shù)n，使得npo，其中o是無窮原點，則稱n是p點的階。橢圓曲線上的點的個數(shù)，記做e(a, b)。描述一條有限域fp 上橢圓曲線，常用到六個參量：t=(p, a, b, g, n,

29、h)。p、a、b 用來確定一條橢圓曲線，g 為基點，n 為點g 的階,h 是橢圓曲線上所有點的個數(shù)m 與n 相除的整數(shù)部分這幾個參量取值的選擇，直接影響了加密的安全性。參參量值一般要求滿足以下幾個條件：1. p當然越大越安全，但越大，計算速度會變慢，200 位左右可以滿足一般安全要求；2. pn×h；3. pt1(mod n)，1t<20；4. 4a3+27b20(mod p)； 曲線非奇異當且僅當：,因為16與p互素，所以0(mod p)，即5. n為素數(shù)；6. h4算法詳見附錄2。3.2.3 橢圓曲線上的運算3.2.3.1 加法定理3.1：若p和q是曲線e上任意兩點，p、q

30、的連線l交e于另一點r，則： 1.(p q )r =o; 2. p o =p； 3. p q =q p； 4. e上存在一點q，使得p q =o，這樣的點記為“-p”； 5. 對于p上的任意點p、q、r，有(p q) r =p (q r)；設(shè)p和q是橢圓曲線ep(a,b)上的兩個點，若p=o，則-p=o，且p+q=q+p=q；令p=(x1 ,y1)，q=(x2 ,y2)，則-p= (x1,-y1)，且p+(-p)=o；如果q p，則p+q=(x3 ,y3)，這里 定義3.5 在e上定義運算，r是過p，q的直線與曲線的另一關(guān)于x軸的對稱點，則稱r為p與q的點加，記為r =p q，如圖 圖3 橢圓

31、曲線上點加定義3.6 當p=q時r是p點的切線與曲線的另一交點關(guān)于x軸的對稱點。即p p =2p =r，稱為曲線上點的倍乘，如圖 圖4 橢圓曲線上倍點3.2.3.2 標量乘法橢圓曲線上的點不能直接進行乘法操作，標量乘法可以轉(zhuǎn)換成點加操作，量乘法實際上執(zhí)行的是對同一點的反復相加的操作，即 算法1 計算點乘的從右到左二進制方輸入：k=(kt-1,k2,k1,k0)2,pÎe(fp)輸出：kp1. q¬¥2. 對于i從0到t-1，重復執(zhí)行2.1 若ki=1，則q¬q+p。2.2 p¬2p3. 返回(q)算法2 計算一個正整數(shù)的naf輸入：正整數(shù)k輸出

32、：naf（k）1. i¬02. 當k³1時，重復執(zhí)行2.1 若k是奇數(shù)， 則ki¬2-(k mod 4),k¬k-ki2.2 否則，ki=02.3 k¬k/2，i=i+13. 返回（ki-1,ki-2,k1,k0）算法3 計算點乘的滑動窗口算法輸入：窗口寬度w，正整數(shù)k，pÎe(fp)輸出：kp1. 計算naf(k)= 2. 對于iÎ1,3,2(2w-(-1)w)/3-1,計算pi=ip。3. q¬¥,i¬l-14. 當i³0,重復執(zhí)行4.1 若ki=0，則t¬1,u

33、2;04.2 否則，尋找一個最大的t£w，使得u¬（ki,ki-t+1）4.3 q¬2tq4.4 若u>0,則q¬q+pu；否則，若u<0,則q=q+p4.5 i¬i+15. 返回(q)3.3 ecc算法原理分析橢圓曲線密碼算法(ecc)的安全性依賴于有限域上點群元素求階，屬于離散對數(shù)難題。令為有限域，e是上的橢圓曲線，p是e上的點，且階是素數(shù)n，并記為d=1,2,n-1.算法描述如下：1) 信息傳遞各方通過參數(shù)組(p,e,p,n)選取密鑰dÎd，并計算公鑰q=dp。2) 信息發(fā)送方表示明文m為e上的點。3) 隨機選取k&

34、#206;d,并利用接收者的公鑰q計算和發(fā)送c4) 信息接收者用自己的私鑰d通過下公式進行解密 4 基于橢圓曲線的混沌的密碼系統(tǒng)構(gòu)造4.1 混沌理論與密碼學混沌現(xiàn)象是非線性確定性系統(tǒng)中的一種類似隨機的過程，把兩個十分相近的初值帶入同一個混沌函數(shù)進行迭代運算，經(jīng)過一定階段的運算后，數(shù)值序列變得毫不相關(guān)。它隸屬于確定性系統(tǒng)卻難于預測，隱含于復雜系統(tǒng)但又不可分解，看似“混亂無序”，實則頗有規(guī)律。shannon在他的論文3中寫到，一個好的加密系統(tǒng)，它的函數(shù)必須是復雜的，并且一個小的變化必然導致結(jié)果發(fā)生很大的變化。這些密碼學特性與混沌系統(tǒng)的特性有著巨大的相似性。如下表：表1 混沌理論與密碼學的相似與不同

35、之處 混沌理論與密碼學的相似與不同之處相似點對初始條件和控制參數(shù)的極端敏感性擴散類似隨機的行為和長周期的不穩(wěn)定軌道偽隨機信號混沌映射通過迭代將初始域擴散到整個相空間密碼算法通過加密產(chǎn)生預期的擴散和混亂混沌映射參數(shù)加密算法密鑰不同點混沌映射定義在實數(shù)域上加密算法定義在有限集上？（目前還沒有相對關(guān)系）密碼系統(tǒng)安全性和性能的分析理論混沌的軌道混合(mixing)特性(與軌道發(fā)散和初值敏感性直接相關(guān))對應于傳統(tǒng)加密系統(tǒng)的擴散特性，而混沌信號的類隨機特性和對系統(tǒng)參數(shù)的敏感性對應于傳統(tǒng)加密系統(tǒng)的混亂特性。可見，混沌具有的優(yōu)異混合特性驗證了混沌加密器的擴散和混亂作用可以和傳統(tǒng)加密算法一樣好?；煦绾兔艽a學之間

36、具有的天然的聯(lián)系和結(jié)構(gòu)上的某些相似性，啟示著人們把混沌應用于密碼學領(lǐng)域。shannon在其經(jīng)典文章3中已將混沌理論所具有的混合、對參數(shù)和初值的敏感性等基本特征應用到密碼學中，并提出了密碼學中用于指導密碼設(shè)計的兩個原則：擴散(diffusion)和混亂(confusion)。擴散方式是將明文冗余度分散到密文中使之分散開來，以便隱藏明文的統(tǒng)計結(jié)構(gòu)，實現(xiàn)方式是使得明文的每一位影響密文中多位的值?；靵y則是用于掩蓋明文、密文和密鑰之間的關(guān)系，使密鑰和密文之間的統(tǒng)計關(guān)系變得盡可能復雜，導致密碼攻擊者無法從密文推理得到密鑰?；煦绾兔艽a學之間具有天然聯(lián)系和結(jié)構(gòu)上的某種相似性,利用混沌系統(tǒng),可以產(chǎn)生數(shù)量眾多、非

37、相關(guān)、類似噪聲、可以再生的混沌序列,這種序列難于重構(gòu)和預測,從而使密碼分析者難以破譯。4.2 系統(tǒng)設(shè)計與實現(xiàn)4.2.1 參數(shù)生成1) 信息傳遞各方通過參數(shù)組(p, e, p，n)選取密鑰dÎd，并計算公鑰q=dp。1. 隨機生成大素數(shù)p, a, b構(gòu)成橢圓曲線e:y2=x3+ax+b2. 選取基點p3. 計算p點的階n4. 隨機生成大素數(shù)d私鑰，d<n;5. 計算公鑰q=dp算法詳見附錄2。2) 信息傳遞各方通過參數(shù)組（x, u），混沌參數(shù)。隨機生成浮點數(shù)x，u，其中0<x<1, 3.57< 44.2.2 加密過程作為一個公鑰加密系統(tǒng)，混沌橢圓曲線加密系統(tǒng)也具

38、有公鑰加密系統(tǒng)的所有特點。公鑰加密系統(tǒng)的加密雙方都需要兩個密鑰:公開的公鑰與保密的私鑰。每一方的公鑰都是通過自己的私鑰得到的，加密明文的時候都要用到對方的公鑰，解密密文的時候使用自己的私鑰。現(xiàn)在假設(shè)有兩個用戶:用戶a與用戶b，用戶a想要得到用戶b的某份文件m,那么利用橢圓曲線加密系統(tǒng)傳輸文件m的過程如下所示:1、用戶a選定一條橢圓曲線ep(a, b)，并取橢圓曲線上一點，作為基點p。2、用戶a選擇一個私有密鑰d，并生成它的公開密鑰q=dp。3、用戶a將ep(a,b)和點q、 p傳給用戶b。4、用戶a、b通過秘密通道協(xié)商混沌參數(shù)(x0,u)5、用戶b接到信息后，產(chǎn)生一個隨機整數(shù)k (k<n

39、,n為橢圓曲線上基點的階數(shù))，k就是用戶b的私鑰。6、然后用戶b需要進行下列計算 c1=m+kq c2=kpc1就是橢圓曲線上的點m經(jīng)過加密之后的密文，c2為用戶b的公鑰。7、用戶b使用混沌參數(shù)（x0，u）對消息（c1，c2）進行l(wèi)ogistic映射混沌加密： c=logistic（c1,c2，x0，u）；8、用戶b將c傳給用戶a。算法4 ecc加密算法輸入：基點p，隨機數(shù)k，明文點m,公鑰q輸出: ecc密文 c1 標量乘法計算c1=kp2 標量乘法計算c0=kq3 計算c2=m+c04 生成密文c=c1+c2算法5 logistic混沌映射輸入：明文流mn，混沌參數(shù)x0，u輸出：密文流cn

40、1. x=x02. i從0到n-1y=u*x*(1-x)ci=ymix=y3. 返回(cn)混沌ecc加密流程如下圖 圖5 logistic 映射下ecc加密流程4.2.3 解密過程算法描述如下：1、信息接受方收到密文c。2、利用混沌映射參數(shù)(x0,u)計算中間明文（c1，c2）（c1，c2=logistic（lc，x，u）3、用戶a計算c1-kc2,，結(jié)果就是m。因為 算法6 ecc解密算法輸入：私鑰q，密文c（c1,c2）輸出: ecc明文m1. 標量乘法計算c0=dc12. 計算m=c2-c0流程如下：圖6 logistic 映射下ecc解密流程 經(jīng)過上面的過程，用戶a從用戶b處得到了想

41、要的文件m。如果用戶a與用戶b是第一次傳送文件，那么需要步驟1到步驟4，也就是說需要用戶a.選擇橢圓曲線、確定基點、產(chǎn)生私鑰與公鑰、向用戶b傳輸基本參數(shù)。如果用戶a與用戶b己經(jīng)建立了聯(lián)系，那么用戶a可以直接解密用戶b傳送來的密文。經(jīng)過這個過程就實現(xiàn)了使用橢圓曲線加密系統(tǒng)加解密信息。5 基于混沌與橢圓曲線的數(shù)字簽名算法5.1 方案一 混沌映射消息摘要在本方案中，對源文件產(chǎn)生hash摘要，之后對摘要用ecc公鑰進行加密產(chǎn)生數(shù)字簽名，然后對數(shù)字簽名進行l(wèi)ogistic混沌映射。5.1.1簽名生成過程在選擇好域參數(shù) d=(q, f, a, b, g, n, h) 、密鑰對 (d,q)以及混沌密鑰kc后

42、，用戶a為對消息m進行簽名。算法流程如下：1. hash（m）產(chǎn)生消息摘要h(m)2. ecc加密h（m）生成密文c3. 產(chǎn)生混沌序列seq4. 密文c與混沌序列異或cseq,生成密文c 圖7 混沌ecc簽名方案一簽名流程圖5.1.2 簽名驗證過程 圖8 混沌ecc簽名方案一簽名驗證流程圖算法流程：1. 產(chǎn)生混沌序列seq2. 密文c與混沌序列異或cseq,生成密文c 3. ecc解密c生成明文m，h（m）4. hash（m）產(chǎn)生消息摘要hash(m)5. 對比h（m），hash(m)5. 2 方案二 混沌映射消息后產(chǎn)生摘要在本方案中，先對源文件進行l(wèi)ogistic混沌映射，然后再對密文產(chǎn)生h

43、ash摘要，之后對摘要用ecc公鑰進行加密產(chǎn)生數(shù)字簽名。5. 2.1簽名生成過程算法流程如下：1. 對消息進行l(wèi)ogistic混沌映射加密，產(chǎn)生密文c1=lc（m）2. hash（c1）產(chǎn)生消息摘要c2=h(c1)=h(lc(m)3. ecc加密h（c2）生成數(shù)字簽名c圖9 混沌ecc簽名方案二簽名流程圖5. 2.2簽名驗證過程算法流程如下：1. 對消息進行l(wèi)ogistic混沌映射加密，產(chǎn)生密文c1=lc（m）2. hash（c1）產(chǎn)生消息摘要c2=h(c1)=h(lc(m)3. ecc解密數(shù)字簽名d（c）4. 比較c2與d(c)圖10 混沌ecc簽名方案二簽名驗證流程圖6 系統(tǒng)性能及安全性分

44、析6.1 系統(tǒng)運行整個系統(tǒng)在win 7平臺上，利用microsoft visual studio 2008開發(fā)工具進行了開發(fā)，在intel core2 2.2ghz、ram 2g的系統(tǒng)上運行。系統(tǒng)用vc實現(xiàn)，并設(shè)計了易于操作的圖形化界面，如下圖圖11 系統(tǒng)界面1.系統(tǒng)可以對消息進行加密，同時完成消息的解密工作。首先，生成橢圓曲線以及密鑰，并存于文件key.dat,如下圖 圖12 密鑰文件原文件內(nèi)容如下： 圖13 待加密源文件密文件內(nèi)容如下： 圖14 密文件解密后文件內(nèi)容如下： 圖15 解密后文件2.系統(tǒng)可以對消息進行加密和簽名，同時完成消息的解密和簽名驗證工作。 圖15 數(shù)字簽名界面生成數(shù)字簽

45、名并存于文件 圖16 數(shù)字簽名驗證數(shù)字簽名圖17 hash摘要6.2 性能分析根據(jù)shannon的理論在密碼算法中設(shè)置了混淆與擴散過程，使得密碼具有較好的安全性?；煦缦到y(tǒng)的特性使得它在數(shù)值分布上不符合概率統(tǒng)計學原理, 得不到一個穩(wěn)定的概率分布特征；另外, 混沌數(shù)集是實數(shù)范圍, 還可以推廣到復數(shù)范圍。因此，從理論上講, 利用混沌原理對數(shù)據(jù)進行加密，可以防范頻率分析攻擊、窮舉攻擊等攻擊方式, 使得密碼難于分析、破譯。公鑰算法采用的是橢圓曲線公鑰算法。對于q元有限域上的橢圓曲線，q為200 bits時，rsa密碼體制需要2048 bits的模數(shù)才能達到同等的安全強度，即橢圓曲線密碼體制在相同的安全強

46、度下所要求的密鑰強度僅是rsa的1/10。數(shù)字簽名采用了基于混沌與橢圓曲線的數(shù)字簽名算法。它增強了ecdsa的安全性，使其能夠抵抗隨機數(shù)泄漏、隨機數(shù)重復使用以及偽造簽名等攻擊。評價公鑰算法的效率主要從以下三方面來考慮:(1) 計算負荷(computational overhead):進行公鑰和私鑰轉(zhuǎn)換所需要的計算量。在本算法中，計算負荷主要體現(xiàn)在ecc上，在幾m以內(nèi)混沌映射的計算負荷可以忽略不計。下表是對系統(tǒng)的性能測試 表1 系統(tǒng)性能測試混沌ecc混沌ecdsa加密解密簽名驗證1k 2.450s1.502s0.120s0.080s10k44.787s24.598s0.222s0.105s100

47、k388.115s236.837s0.220s0.105s1m4279.585s2527.478s0.210s0.110s(2) 密鑰大小(key size):存儲密鑰對和系統(tǒng)參數(shù)所需要的bit數(shù)。系統(tǒng)使用200bits的密鑰長度，相當于2048bit的rsa算法，而國際標準推薦ecc算法的密鑰長度不小于160bits6 ，所以認為本系統(tǒng)有較高的安全性。下表是ecc與rsa密鑰長度的比較。 表2 ecc與rsa的比較(3) 帶寬(bandwidth):要傳輸?shù)募用芟⒑秃灻腷it數(shù)。 在評價一個加密算法的效率時，一般采取對不同算法進行分析對比的方法，當然，比較應在提供類似安全級的系統(tǒng)間進行，

48、如密鑰長度為160 bits的ecc應和密鑰長度為1024 bits的rsa進行比較。從整體上來看，系統(tǒng)所采用的算法運算速度較快、安全性較高。6.3 安全性分析ecc的安全性是基于橢圓曲線群上離散對數(shù)的困難性，即山公鑰q=dp求出私鑰d是數(shù)學困難問題。一般認為，橢圓曲線群上的離散對數(shù)問題是比大因數(shù)分解和離散對數(shù)更困難的問題。在已知的公鑰系統(tǒng)中，基于模運算的大整數(shù)因數(shù)分解問題和離散對數(shù)問題都存在亞指數(shù)時間的通用算法。這些亞指數(shù)時間算法意味著問顆仍然是困難的，但是沒有個指數(shù)時間算法那么難。目前用最好的通用算法來計算這兩類問題所需時間: 已經(jīng)知道的對橢圓曲線的攻擊方法主要有以下幾種，設(shè)橢圓曲線上的基

49、點p，p的階為n。1 窮舉搜索法 計算2p，3p，4p，直到找到q，這種算法最多需要n步橢圓曲線的點加。2 大步小步法 這種算法的思想在于測試p的倍點運算是否等于q，利用一種數(shù)據(jù)結(jié)構(gòu)，具 體的做法是，預先計算并存儲一些p的某些倍點(小步)運算的結(jié)果，然后對 于某個整數(shù)，計算q一lp，q一2lp，(大步)，直到qilp在預存表中出現(xiàn),這種放是把窮搜索中的部分時間換為存儲，即以空間換取時間，它需要存儲n個點，最壞需要計算n步。3 pollards rho算法這種算法是小步大步算法的隨機版本，它的運行時間和小步大步算法差不多，只是需要很小的存儲空間，該算法可以在幾種處理器上并行，其運行時間為m步點加

50、運算。4 pohlig-hellman算法設(shè)橢圓曲線的基點p，它的階是n，q=lp，首先分解n=pe1 pe2 . pel,然后，將找l的問題歸結(jié)到尋找l mod pei,最后，利用中國剩余定理計算出l。當n全是小素數(shù)因子乘積時，這種算法非常有效，所以，為了抗擊這種攻擊，n必須有大素數(shù)因子。pohlig和hellman發(fā)現(xiàn)，abel群的階的平滑性對于g中求解離散結(jié)數(shù)問題是有幫助的。借助中國剩余定理和相關(guān)變換，算法的時間復雜度為助的。借助中國剩余定理和相關(guān)變換，算法的時間復雜度為5 分布式pollard rho算法van oorschot wiener將pollard rho算法并行處理，使得算

51、法分m個過程并行處理，運行時間大約是n/2m步。分布式pollard rho算法是目前已知的對一般橢圓曲線離散對數(shù)問題最好的攻擊方法之一。對特殊橢圓曲線的攻擊1 mov攻擊其核心思想是將橢圓曲線離散對數(shù)問題轉(zhuǎn)化為某個有限域的乘法群上的離散對數(shù)問題，此類攻擊只對超奇異橢圓曲線有效，該算法導致出現(xiàn)了亞指數(shù)的ecdlp求解算法，所以在對橢圓曲線的參數(shù)進行選擇的時候，避免出現(xiàn)這一情況的出現(xiàn)。2 ssas攻擊1997，smart和satoh及araki分別獨立同時提出了對素數(shù)域上一類非常規(guī)橢圓曲線的離散對數(shù)攻擊，不久，semaev也得到了同樣的結(jié)果，所以稱ssas攻擊 根據(jù)上面對橢圓曲線密碼體制安全性的

52、探討，存在著對某些特殊類型的橢圓曲線的亞指數(shù)攻擊，所以，在對橢圓曲線以及它的基點的選擇上，必須避免以下幾種情況：1. 滿足e(gf(2m)=2m的橢圓曲線。2. 橢圓曲線的基點的階不是素數(shù)。3. 橢圓曲線不可以是超奇異橢圓曲線。 要保證橢圓曲線密碼的安全性，就是要使所選取的曲線能抵抗上述的關(guān)于ecdlp解決的方法和算法，所以選取一條安全的橢圓曲線，是一個深刻的數(shù)學難題7 總結(jié)與展望混沌加密算法本身的非周期、高度不可預測性，看似隨機性，對初始條件和參數(shù)敏感性等特點使得加密的數(shù)據(jù)更加安全可靠，利用混沌原理對數(shù)據(jù)進行加密，可以防范頻率分析攻擊、窮舉攻擊等攻擊方式, 使得密碼難于分析、破譯,同時公鑰密

53、碼體制保證了密碼傳輸過程的安全性。所以本文在常見的幾種加密方式基礎(chǔ)上，提出了混沌密碼和ecc 組合這樣一種混合體制， 相信它的使用可以更好地實現(xiàn)快速、安全的數(shù)據(jù)加密傳輸。致謝本文是在導師許紅星老師悉心指導下完成的。從選題到具體論文寫作工作，導師都傾注了大量的心血，給我多次改稿，耐心講解。導師的知識結(jié)構(gòu)、研究方法、思維模式和學術(shù)風格均使我獲益匪淺;導師忘我的工作熱情、嚴謹求實的治學風范都給我以極大的教育;導師淵博的知識、學術(shù)上不斷創(chuàng)新的思想方法、獨到的見解給了我莫大的啟迪。這些將激勵我在今后的工作中不懈努力、不斷進取。在即將畢業(yè)之際，謹向許老師表示衷心的感謝和深切的敬意! 參考文獻1 v.s.m

54、iller. use of elliptic curves in cryptography. advances in cryptology crypto85.lecture notes in computer science no.218.spring-verlag berlin. 1985.417-426.2 n.koblitz, elliptic curve cryptosystem, mathematic of computers, 48:203-209,1987.3 shannon c e. communication theory of secrecy systemj bell systems technical journal,1949;28:6567154 r matthews. on the derivation of chaotic encryption algorithm j.cryptologia,1989;13(1):29425 tien-yien li; james a. yorke,