混沌動力學Logistic模型在工程加密中的應用*

安建偉 何永前

(92852部隊 湛江 524002)

1 引言

密碼技術的基本思想是隱藏信息,未授權者不能得到信息的真實含義。加密就是對信息進行一組可逆的數學變換。如果我們采用軟件完成數據加密的全過程,加密算法很容易被跟蹤或篡改,并且實現加密算法的速度也受到限制等缺點將不可避免,這是由于軟件加密自身特點決定的。由于數據加密領域中某些要求的特殊性,這些缺點帶來了許多的問題。作為實現數據加密的一種重要方式,利用硬件電路實現數據加密具有軟件無法比擬的高速度,尤其是利用專用電路實現某些算法,由于硬件加密的封閉性使加密算法很安全;如果計算機除了加密任務還有其他任務時,多種任務可以并行處理,計算機資源的利用率可大大提高。由于硬件加密具有以上突出優點,文章中以混沌密碼學技術中的Logistic加密模型及現代ASIC設計等技術相結合,介紹具體的實現方法。

2 Logistic模型的基本特性

Logistic模型:

該模型只有一個變量 x,屬于一維方程,但具有極其復雜的動力學規律。根據模型的定義,我們可以通過Logistic模型的分岔圖可以直觀了解 u的取值對迭代過程的影響和迭代結果的分布情況。

圖1 Logistic映射的倍周期分岔圖

在圖1中以u為x軸,迭代多次的 xn的平均值為y軸,從圖中可以看出該模型的迭代值強烈依賴 u,隨著 u的不同 xn的最終分布可以分為兩個區域:周期區和混沌區。當u的值很小時,當迭代次數趨于無窮大時,迭代值趨于一個定值;隨著u的增大,迭代值的周期數以倍周期分岔的方式不斷地增長。當u值大于3.57時,時間序列x0,x1,x2,…,xn,…依次排列得到的時間序列如同分布在區間[0,1]上的隨機數,稱之為混沌狀態。

1)周期區

結論1 通過分析圖1可以得出結論1:從周期2n-1到2n(n≥1),各分岔點un存在如下關系:

即各分岔點之間的距離以比例δ倍縮小,且δ為一無理數,這個數被稱為費根包姆(Feigenbaum)δ常數。

結論2 通過分析圖2我們得出每分岔一次,在x方向上的結構也在較小的標度上重復出現一次。周期2n中接近于xi處各x之間的距離 Δ 1,Δ 2,…,Δ n漸近的按因子α衰減:

這里的費根包姆δ和α常數是一種普適常量,在倍周期分岔現象中具有普遍意義,與函數的形式無關。這兩個常數也說明了倍周期分岔進入混沌是一種相當普遍的自然現象。

圖2 周期2n中接近于xi處各 x之間的距離

2)混沌區

指出在混沌區也存在一些周期窗口,如周期3,5,6…等,并且通過這些周期又不斷岔分出周期3*21,3*22,…等,最終進入混沌。混沌區中包含周期窗口,窗口區內又有混沌,這種不斷重復的自相似結構有無窮多個層次,最終形成了我們現在看到的混沌區域。這里需要說明的是由于圖形分辨率的限制,周期大于5的窗口在圖1中沒能被直觀體現。

3 Logistic算法器的設計

在這一節中將著重介紹算法的設計思想和具體實現。

3.1 算法器數字電路的工作狀態

在本次設計中要實現的迭代乘法算法為:

通過分析算法特點和加密過程,我們將實現一次加密工作乘法器內部要經歷的狀態分為四種狀態,其狀態圖如圖3所示。

圖3 Logistic映射乘法器的狀態圖

狀態1:算法器處于復位狀態,由輸入信號sta控制

狀態2:算法器處于初始化狀態,X(64Bit),U(64Bit),NUM(迭代次數)的順序依次輸入初始化數據。

狀態3:算法器完成規定的迭代次數后Ready有效,進入混沌態

狀態4:算法器將需加密的數據在寫信號有效時的第一個時鐘周期生成密文,當密文被讀走的同時,并準備好下一次加密數據時所需的數據,直至加密全過程結束,sta腳重新回到有效態。這樣就可以周而復始的加密任意大小的文件。

3.2 Logistic模型算法的實現

為了保證迭代運算保持在混沌態,U的取值為3.8～4之間的數,在帶入運算前先將U值通過除4轉換為小數(64Bit),然后在每一次的迭代運算中積分兩次乘以二。X?(1-X)的積最大為1/4,所以在每一次的迭代運算不會產生大于1的數。

圖4 乘法器的流程圖

在實現迭代運算的設計中,設計的重點之一是超長度數據間的乘法。乘法運算占用的資源是最大的,如果對一些無效位不進行處理,64位與64位數據相乘后生成128位的結果中冗余數據還將占用大量的硬件資源;并且如果直接利用兩個寬為64位的數據相乘,這里采用的Xilinx公司軟件2.1版的Foundation將不能對設計進行綜合(synthesis)形成宏單元。對算法進行改進,將兩個64位數據A[63:0]、B[63:0]分成兩部分同時相乘,將結果處理后再相加,得到精度仍為64位的積。這樣在輸出時宏單元就可以少占用64位的輸出,內部珍貴的資源就可以節省下來。其工作流程圖如圖4所示。

在每一次Logistic運算中要進行兩次乘法運算,為了節省資源,兩次乘法用同一個乘法器,這樣是以降低運算速度為代價,損失大約一半時間。通過外部控制信號(sel)和時鐘信號(clk)來控制乘法運算的順序:在第一個時鐘周期完成z=x?(1-x),有效數據取前[126:63]位,實現乘 2;在第2個時鐘周期完成y=u?z,有效數據仍取前[126:63]位,實現乘2。所得結果反饋給Logistic函數發生器的控制部分作為下一次運算的x。

在乘法器中,我們將每組的u值存入一個模塊中,這個控制模塊負責控制64×64位的乘法模塊的輸入和時鐘信號;并且1-x產生64位有效數據的運算過程也由它完成。

4 算法器的具體實現及分析

4.1 算法器的原理圖和時序仿真

u13是算法器中的控制器,通過握手信號和外部交換信息,控制每次加密過程中初始化、明文輸入、和密文輸出的全過程;H1實現乘法的宏器件,u13利用控制信號線控制乘法器實現Logistic算法。

圖5 算法器的原理圖

我們將原理圖通過綜合過程后,利用產生的時間延遲參數進行后時序仿真來校驗設計功能。因為篇幅原因,這里僅分析算法器在數據加密狀態下的時序。

圖6 加密過程中的讀寫時序

通過后時序仿真可以看出,算法器達到設計要求。當將初始化數據寫入算法器,輸入要求的時鐘數目后,算法器進入混沌狀態,ready變為高電平。通過寫命令wr將要加密的明文數據流和混沌產生密鑰流異或形成密文,然后通過讀命令rd將密文取走。由于明文寫入和密文輸出公用一個總線,所以設計使用讀信號控制數據總線方向引腳dir的電氣特性。這里讀信號和寫信號的操作均是在其有效后的第一個時鐘開始進行,寫信號需一個時鐘,讀信號需兩個時鐘。從圖6中可以看出硬件完成每項動作的時序,包括施加控制信號到得到響應的延時,如rd和dir邊沿間的延時等,這些特征只能在后時序仿真中才能觀察到。通過對仿真后時序結果進行分析后重新設計,有效避免這些特殊延時可能導致的設計對象的邏輯功能混亂。

4.2 乘法器的原理圖和時序仿真

本設計依據頂層設計的方法實現了乘法器MMM,由它具體實現乘法,乘數和被乘數均為64位。其管腳定義如表1所示。

圖7 乘法運算的具體實現的原理圖

表1 乘法器的管腳定義

同樣在后時序仿真時,我們也測試了作為算法器中最重要的部件—乘法器的功能。

通過后時序仿真圖8可以清楚地看到乘法器實現兩次乘法的全過程,這里需要說明的是:因為進行每次的乘法運算均在load的上升沿發生,load由控制器的clk_out信號驅動。而clk_out信號是由讀信號和時鐘信號共同驅動的,所以要求讀密文時的讀信號的有效時間長度必須大于兩個時鐘周期。

圖8 乘法器的后時序仿真圖

5 結語

通過分析Logistic算法的特點和加密過程的特點,本文利用Foundation軟件設計了[64:64]的超長二進制乘法器和完成加密解密功能的算法器,并且通過后時序仿真利用模擬外部控制信號實現了算法器的初始化,進入規定的混沌狀態,明文的輸入、密文的輸出和退出混沌狀態等規定操作,并且在連續加密(解密)解密過程中,完成單字節加密(解密)過程所需時間僅需300ns左右,速度是軟件不能比擬的,設計結果極為理想。

[1]黃潤生.混沌及其應用[M].武漢:武漢大學出版社,2000:112～175

[2]孟憲元.可編程ASIC集成數子系統[M].北京:電子工業出版社,1998:175～186

[3]蔡國權,宋國文,于大鵬.Logistic映射混沌擴頻序列的性能分析[J].通信學報,2000(1):60～63

[4]王亥,胡健棟.Logistic-Map混沌擴頻序列[J].電子學報,1997(1):19～23

[5]XILINX公司.The Programmable Logic Data Book.XILINX公司,2000:5_1～5_19

[6]Lin.T,Chua.L.O.A New class of pseudo-random number generator based on chaos in digital filters.International Journal of Circuit Theory anApplications,1993,21:473～480

[7]曾繁泰,陳美金.VHDL程序設計[M].北京:清華大學出版社,2000:5～22

[8]Heidari-Bateni.G,Mcgillem.C.D.A chaotic direct sequence spread-spectrum communication system[J].IEEE Trans Communications,1994,42:1524～1527

[9]Chua.L.O,Yao.Y,Yang.Q.Generation randomness from chaos and constructing chaos with desired randomness.Int.J.Circuit Theory and Applications,1990,18:215～240