淺談密碼學(xué)與混沌理論

淺談密碼學(xué)與混沌理論

信息作為資源，在社會生產(chǎn)和生活中發(fā)揮著越來越重要的作用。信息安全已成為信息社會的中心和難點。信息加密技術(shù)是信息安全的一個重要問題。自從混沌理論問世以來,各個學(xué)科的學(xué)者都把它用于解決許多實際問題。當(dāng)然,混沌現(xiàn)象的獨特特征也受到密碼學(xué)研究者的極大關(guān)注。密碼學(xué)起源較早,自從有了戰(zhàn)爭,就有了密碼。而混沌則是一門新興學(xué)科。隨著計算機(jī)科學(xué)技術(shù)的發(fā)展,信息和信息技術(shù)對密碼學(xué)提出了越來越高的要求,迫切需要發(fā)展密碼理論和先進(jìn)的密碼技術(shù)。目前,國內(nèi)外已陸續(xù)發(fā)表了不少有關(guān)混沌密碼體制及混沌加密在計算機(jī)網(wǎng)絡(luò)和安全通信中應(yīng)用的文章[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]。誠如混沌理論的早期研究者、牛津大學(xué)的梅埃教授所言“這是一種革命科學(xué)、它為解決古老問題開辟了一種新的研究途徑”。1對稱算法與公開密鑰算法密碼學(xué)(Cryptology)包含兩個互相對立的分支,即密碼編碼學(xué)(Cryptography)和密碼分析學(xué)(Cryptanalytics)。前者尋求保證消息保密性或真實性的方法,而后者則研究加密消息的破譯或消息的偽造?，F(xiàn)代密碼學(xué)已發(fā)展成為集代數(shù)、數(shù)論、信息論、概率論等理論于一體,并與通信、計算機(jī)網(wǎng)絡(luò)和微電子等技術(shù)緊密結(jié)合的一門綜合性學(xué)科?；诿荑€的算法通常有兩類:對稱算法和非對稱算法。對稱算法又稱傳統(tǒng)密碼算法,就是加密密鑰能夠從解密密鑰中推算出來,反過來也成立。對稱算法的加密和解密表示為:其中M為明文,C為密文,EK為加密算子,DK為解密算子。在大多數(shù)對稱算法中,加/解密密鑰是相同的。這些算法又稱秘密密鑰算法或單密鑰算法,它要求發(fā)送者和接收者在安全通信之前,商定一個密鑰。對稱算法的安全性依賴于密鑰,泄漏密鑰就意味著任何人都能對消息進(jìn)行加/解密。只要通信需要保密,密鑰就必須保密。針對對稱算法的缺點,1976年,W.Diffie和M.E.Hellman首次證明了從發(fā)送端到接受端無密鑰的保密通信是可能的,這就是公開密鑰算法,簡稱公鑰算法,也叫非對稱算法。該算法的設(shè)計方法是:用作加密的密鑰不同于用作解密的密鑰,而且解密密鑰不能根據(jù)加密密鑰計算出來(至少在合理假定的長時間內(nèi))。加密密鑰可以公開,即陌生者能用加密密鑰加密信息,但只有用相應(yīng)的解密密鑰才能解密信息。目前,公鑰算法主要有3種:D-H算法、RSA算法和橢圓曲線算法。有時,消息用私人密鑰加密而用公開密鑰解密,用于數(shù)字簽名和數(shù)字水印等。信息的混沌加密技術(shù)的應(yīng)用可以分為兩大類,一類是靜態(tài)加密技術(shù),包括圖像加密、數(shù)字水印、數(shù)字簽名等方面的應(yīng)用;另一類是實時動態(tài)加密技術(shù),例如,擴(kuò)跳頻保密通信技術(shù)、電子商務(wù)信息加密技術(shù)等等。2混沌:非線性確定系統(tǒng)的隨機(jī)性目前,信息處理已成為計算機(jī)應(yīng)用的一個重要方面。Internet網(wǎng)每時每刻都在為人們提供大量的信息服務(wù)。但由于Internet網(wǎng)的基礎(chǔ)協(xié)議TCP/IP不是一種安全的協(xié)議,現(xiàn)代高性能的計算機(jī),運(yùn)行自動分析和截獲程序每秒可搜索數(shù)百萬個底碼,因此當(dāng)未經(jīng)特別加密的信息在網(wǎng)絡(luò)上傳送時就會面臨極大的安全威脅,這也對傳統(tǒng)的加密算法構(gòu)成了很大的壓力。混沌理論的發(fā)展為密碼學(xué)注入了新的活力?，F(xiàn)代意義的混沌(Chaos)起源于20世紀(jì)60年代。1963年美國氣象學(xué)家洛侖茲(Lorenz)在用計算機(jī)模擬天氣變化時,發(fā)現(xiàn)一個確定的含有3個變量的自治的方程卻能產(chǎn)生混沌解,使得氣候不能精確重演,指出了非周期性和不可預(yù)見性之間的聯(lián)系。由此拉開了混沌研究的序幕,一類被統(tǒng)稱為“混沌”的復(fù)雜現(xiàn)象在包括數(shù)學(xué)、物理、力學(xué)、天文、化學(xué)、生物、氣象等幾乎所有自然科學(xué)乃至人文學(xué)科中被普遍發(fā)現(xiàn),人類科學(xué)歷史上沒有哪一個概念或理論能與“混沌”相比,把如此眾多的學(xué)科和領(lǐng)域聯(lián)系在一起,成為它們共同的語言?；煦缈茖W(xué)最熱心的倡導(dǎo)者、美國海軍部官員施萊辛格(ShlesingerM)說:“20世紀(jì)科學(xué)將永遠(yuǎn)銘記的只有三件事:相對論、量子力學(xué)與混沌。”物理學(xué)家福特(FordJ)認(rèn)為混沌就是20世紀(jì)物理學(xué)第三次最大的革命?；煦缡欠蔷€性系統(tǒng)所特有的現(xiàn)象,它是確定性系統(tǒng)的隨機(jī)性?；煦鐚W(xué)把這通?？雌饋砘靵y無序(通常意義上的混沌)的現(xiàn)象,作為自己的研究對象。認(rèn)為這些表面上看起來好像是無規(guī)律的東西、實際上有它自己的規(guī)律。混沌學(xué)的任務(wù)就是要尋找其規(guī)律,并對其進(jìn)行處理?；煦缡欠蔷€性確定系統(tǒng)中的一種復(fù)雜的隨機(jī)的現(xiàn)象,在文獻(xiàn)中首先使用混沌(chaos)一詞的是李天巖和約克(J.A.Yorke),他們的“周期3蘊(yùn)涵混沌”一文被大量引用。目前混沌尚無統(tǒng)一嚴(yán)格的定義。對一階系統(tǒng),數(shù)學(xué)家Kloeden在Li-Yorke定理的基礎(chǔ)上給出了混沌的一個定義:令f(x)為區(qū)間I到自身的連續(xù)映射,若滿足條件:1)f(x)的周期點的周期無上界;2)存在I的不可數(shù)子集S,滿足a)對于任何x,y∈S,當(dāng)x≠y時,有對于任何x,y∈S,有。則稱f(x)描述的系統(tǒng)為混沌系統(tǒng)。此定義說明從兩個初始點引出的兩條軌道時而無限靠近、時而相互遠(yuǎn)離,兩種情形無數(shù)次交替出現(xiàn),這說明系統(tǒng)的長期行為沒有規(guī)則,是一種隨機(jī)現(xiàn)象。人類能否駕馭混沌?這是混沌理論研究中的一個重要課題,最近幾年的研究表明,有些混沌是可控制、可利用的,而且是十分可貴的。在增強(qiáng)激光器輻射功率、調(diào)整電子電路輸出實現(xiàn)同步、控制化學(xué)反應(yīng)波動、穩(wěn)定功能異常心臟的心律,以及生成保密通信所需密鑰流等方面,可以派上用場。這是基于混沌所具有的以下幾個特點。首先,混沌系統(tǒng)的行為是許多有序行為的集合,而每個有序分量在正常條件下,都不起主導(dǎo)作用。但是采用適當(dāng)方式擾亂一個混沌系統(tǒng),就可能促使它以其中一個有序行為起主導(dǎo)作用。由于集合中的有序分量足夠多且形式多樣,因而為應(yīng)用提供了很大靈活性和機(jī)會。其次,混沌看起來似為隨機(jī)的,但都是確定的。最后,混沌系統(tǒng)對初始條件極為敏感,兩個幾乎相同的混沌系統(tǒng),對稍異的初始狀態(tài)就會迅速演變成為完全不同的狀態(tài)。混沌序列是一種非線性序列,其結(jié)構(gòu)復(fù)雜,難以分析和預(yù)測,混沌系統(tǒng)可以提供具有良好隨機(jī)性、相關(guān)性和復(fù)雜性的擬隨機(jī)序列,這些都是很有吸引力的特性,使其有可能成為一種可實際被選用的流密碼體制,自從英國數(shù)學(xué)家Matthews明確提出用混沌系統(tǒng)來產(chǎn)生序列密碼及后來Pecora和carroll提出混沌自同步方法以來,混沌同步保密通信在國際電子工程界得到了廣泛的研究[25,26,27,32,33,34,35,36,37]。選用何種混沌系統(tǒng)能產(chǎn)生滿足密碼學(xué)中各項要求的混沌序列是目前各國密碼學(xué)者大力研究的問題。1989年,Matthews提出用Logistic混沌映射經(jīng)改進(jìn)成的迭代混沌系統(tǒng),1992年,Carroll等用Lorenz系統(tǒng),還有m序列擾動混沌系統(tǒng)法等[周1996]。法國Beaancon大學(xué)Goedgebuer等利用可調(diào)激光二極管研制了一個光傳輸數(shù)據(jù)的系統(tǒng),它采用混沌疊加加密方式。研究結(jié)果表明,混沌序列具有了理論上的保密性,使其有可能成為一種實際可用的加密序列。3混沌序列加密通信眾所周知,加密的一般過程是將明文的信息流變換為可逆的類隨機(jī)流,解密過程則是對數(shù)學(xué)變換逆變換的猜測處理過程,將得到的類隨機(jī)流還原為明文。顯然密文的類隨機(jī)性強(qiáng)弱決定了還原為明文的過程難易程度?；煦缂用苤饕抢糜苫煦缦到y(tǒng)迭代產(chǎn)生的序列,作為加密變換的一個因子序列。混沌加密的理論依據(jù)是混沌的自相似性,使得局部選取的混沌密鑰集,在分布形態(tài)上都與整體相似。混沌系統(tǒng)對初始狀態(tài)高度的敏感性,復(fù)雜的動力學(xué)行為,分布上不符合概率統(tǒng)計學(xué)原理,是一種擬隨機(jī)的序列,其結(jié)構(gòu)復(fù)雜,可以提供具有良好的隨機(jī)性、相關(guān)性和復(fù)雜性的擬隨機(jī)序列,使混沌系統(tǒng)難以重構(gòu)、分析和預(yù)測。事實上,混沌序列對解密防護(hù)的重要一點是,即使解密者已掌握產(chǎn)生混沌序列的方程,也難以猜測決定混沌序列的系數(shù)參數(shù)以及混沌序列的初始值。因為這些關(guān)鍵值,來源于有理數(shù)域(盡管這些關(guān)鍵值是定義在實數(shù)域上,但是由于計算機(jī)的舍入誤差,實際上處理混沌加密序列是在有理數(shù)域)在任一個區(qū)域上,有理數(shù)都是稠密的。單純的猜測幾乎得不到系數(shù)參數(shù)?；煦缡欠蔷€性系統(tǒng)所產(chǎn)生的復(fù)雜的動力學(xué)行為,混沌系統(tǒng)對初值條件具有極端的敏感性,因此混沌系統(tǒng)能產(chǎn)生大量的、互不相關(guān)的、具有偽隨機(jī)性的混沌序列。1989年L.M.Pecora發(fā)現(xiàn),一個混沌系統(tǒng)在滿足某種條件下,可以構(gòu)造成一個同步系統(tǒng),用此類同步化混沌可以進(jìn)行通信。同年,Carroll構(gòu)造出第一個可同步混沌電路。從此人們開始了將混沌序列用于密碼的研究工作。在Cryptologia、Eurocrypt、IEEEonCAS、Bifurcation&Chaos等雜志和有關(guān)會議上發(fā)表不少有關(guān)混沌密碼序列的研究成果。混沌加密的基本原理是利用混沌系統(tǒng)產(chǎn)生混沌序列作為密鑰序列,利用該序列對明文加密,密文經(jīng)信道傳輸,接收方用混沌同步(混沌是確定的,由非線性系統(tǒng)的方程、參數(shù)和初始條件完全決定,只要系統(tǒng)參數(shù)和初始條件相同,可以完全重構(gòu)出來。因此,接收方容易構(gòu)造出與發(fā)送方同樣的混沌系統(tǒng),實現(xiàn)同步)的方法將明文信號提取出來實現(xiàn)解密。1997年,加拿大的一所大學(xué)與美國的一家公司簽訂了第一份合作開發(fā)基于混沌同步技術(shù)的加密信用卡項目的合同書。在混沌保密通信系統(tǒng)中,被研究得最多之一的混沌是Logistic混沌映射,簡單的Ligistic映射能生成跳頻碼序列,但計算精度的限制使混沌序列的周期不可能無限長,GhobadHeidari-Bateni等人提出Logistic映射級聯(lián)以產(chǎn)生更長周期的跳頻序列的設(shè)計方法,李文化等人提出多級聯(lián)設(shè)計方法,并討論了Logistic-Kent等級聯(lián)的混沌跳頻序列,凌聰?shù)热颂岢隽嗣扛鬺og2q次(q為頻率數(shù)目)迭代對Logistic映射序列進(jìn)行量化產(chǎn)生一個新頻率的方法,該方法能降低最大漢明相關(guān)值,但平均漢明相關(guān)性沒有得到改善。許多人也對Logistic混沌映射產(chǎn)生的跳頻碼的特性進(jìn)行了討論和研究。4不同密鑰的使用頻率,使用時長為大,其密鑰混沌加密主要是基于混沌系統(tǒng)所具有的獨特性質(zhì):對初值極端的敏感性和具有高度的隨機(jī)性,故將混沌理論應(yīng)用于密碼學(xué)上,具有保密性強(qiáng),隨機(jī)性好,密鑰量大,更換密鑰方便,此外,在抗干擾性、截獲率、信號隱蔽等方面同樣具有潛在的優(yōu)勢。盡管混沌加密具有上述特點和優(yōu)勢,但目前混沌理論在密碼學(xué)上的實際應(yīng)用中還存在著許多問題。比如說,混沌系統(tǒng)在計算機(jī)或其它數(shù)字系統(tǒng)實現(xiàn)時,由于對混沌映射的參數(shù)和狀態(tài)模擬精度的限制,使混沌序列表現(xiàn)出短周期、強(qiáng)相關(guān)及局部線性的缺點,因此在較小精度實現(xiàn)下的混沌系統(tǒng)不適合加密。當(dāng)前混沌加密方法仍存在以下不足:1顯色器的時間長度有現(xiàn)有的混沌序列的研究對于所生成序列的周期性、偽隨機(jī)性、復(fù)雜性、互相關(guān)性等的估計是建立在統(tǒng)計分析上,或是通過實驗測試給出的,這難以保證其每個實現(xiàn)序列的周期足夠大,復(fù)雜性足夠高,因而不能使人放心地采用它來加密。例如,在自治狀態(tài)下,輸入信號為零時,加密器表現(xiàn)為有限周期響應(yīng)。不同的初始狀態(tài)對應(yīng)于不同的周期,其周期長度可能很短。這一缺點在某種程度上降低了混沌加密系統(tǒng)的保密性。2混沌生成器理論研究混沌序列的生成總是要用有限精度器件來實現(xiàn)的,從而混沌序列生成器可歸結(jié)為有限自動機(jī)來描述,這樣,混沌生成器否能超越已有的用有限自動機(jī)和布爾邏輯理論所給出的大量研究成果,是一個很值得研究的課題。大多數(shù)在有限精度下實現(xiàn)的混沌系統(tǒng),其性質(zhì)會與其理論結(jié)果大相徑庭,從而使許多基于混沌系統(tǒng)的應(yīng)用無法實現(xiàn)。甚至有學(xué)者認(rèn)為,有限精度效應(yīng)是目前混沌理論走向應(yīng)用中出現(xiàn)的一大難題。3混沌序列的下一步研究對于分段線性的混沌映射加密系統(tǒng),相鄰的兩個狀態(tài)可能落在同一條直線段上,這樣,在數(shù)字實現(xiàn)精度很高的情況下,解密者就可利用此特點,在知道少量的明文-密文對照的情況下輕易地恢復(fù)出具有足夠精度的密鑰。也就是說,它對于選擇明文攻擊的抵抗力很差,從而在這一意義上不具有保密性。任何特定混沌序列的實現(xiàn)都是由其非線性方程和相應(yīng)的初始條件完全確定了的,有人在研究跟蹤混沌序列進(jìn)行破譯的工作。解決了上述三個問題,混沌序列才可能在密碼設(shè)計中得到廣泛應(yīng)用。且人們已發(fā)現(xiàn),用由低維動力學(xué)系統(tǒng)產(chǎn)生的混沌可短期預(yù)測,所以用它來構(gòu)造保密通訊系統(tǒng)的保密性是脆弱的,這是由于低維系統(tǒng)的混沌序列只有一個正的Lyapunov指數(shù)(LE),正的LE值反映混沌系統(tǒng)對初值的敏感性,因而人們就想到利用高維動力系統(tǒng)產(chǎn)生超混沌,使正的Lyapunov指數(shù)個數(shù)大于1,得到超混沌信號,以提高保密性能,但高維動力學(xué)系統(tǒng)的維數(shù)