摘? 要: 利用Logistic映射迭代產生的混沌序列作為二維置換網絡的置換地址,構造二維置換網絡對明文進行置換加密。同時提出了一種Logistic混沌映射的整數實現方法,給出了它的FPGA實現,并通過硬件裝置實現了Logistic映射的混沌二維置亂網絡。
關鍵詞: Logistic映射? 混沌序列? 置換網絡
?
在密碼學研究中,置換網絡起著中心作用,明文字母之間的雙射變換可以由一個輸入和輸出字母相同的置換網絡實現。一個置換網絡可看作是有n個多輸入和n個多輸出變量的黑盒子,其每個輸出變量都是n個輸入的布爾函數,它的好壞直接影響到分組密碼的抗破譯性。置換網絡的研究涉及電話交換、開關理論和密碼學等多個領域[1]。密碼學中,使用置換來進行數據變換,主要有兩種作用,其一是對數據內容作不可預測的替換,其二是改變數據在數據序列中的位置,即隨機換位。對于第二種置換網絡也稱為置亂網絡,本文主要研究一種二維混沌置亂方法來對數據進行換位加密。
混沌現象是非線性動力系統中一種確定性的類隨機過程,混沌信號具有對初始值的高度敏感性、不可預測性,并具有遍歷性[2，3]等特點。因此,特別適合于混沌保密通信。本文將Logistic映射生成的混沌序列引入置換網絡,它可以作為理想的置換網絡地址產生器[4]。
FGPA(現場可編程門陣列)是由掩膜可編程門陣列PLD演變而來的,并將二者的特性結合在一起,使FPGA既有掩膜可編程門陣列的高邏輯密度和通用性,又有PLD的可編程性。FPGA技術的發展使得單個芯片上集成的邏輯門數越來越多,其實現的功能越來越復雜。它以編程方便、集成度高、速度快等特點受到設計人員的青睞。人們可以通過硬件編程的方法設計和開發ASIC(專用集成電路)芯片,極大地提高了芯片的研制效率、降低了開發費用。本文用它來作為混沌序列發生器,產生置換網絡的置換地址。
1 Logistic映射及其FPGA實現
Logistic映射由下式定義:
Logistic映射的輸入和輸出都分布在(0,1)上,可以用概率統計方法定量分析其序列的特性,Schuster H.G證明了[5]式(2)產生的混沌序列{xk:k=0，1，2，…}的概率分布密度函數ρ(x)如下式所示:
從式(3)可以看出,Logistic映射生成的混沌序列具有遍歷性,同時它還具有δ-like型自相關函數和零的互相關函數[6],因而可以作為良好的置換網絡地址產生器。
對于式(2)所表示的Logistic混沌映射,如果用浮點運算,計算的精度與產生混沌序列的周期長度有以下近似關系:
從式(4)可以看出如果運算精度比較小,運算結果將很快脫離混沌態,但運算精度過大又會造成運算時間過長、使用資源較多,不利于硬件電路的實現。這里提出一種Logistic混沌映射的整數實現方法,在降低運算精度的情況下,可以使混沌序列仍保持混沌態。下面在給出Logistic混沌映射整數實現方法的基礎上,給出了它的FPGA實現方法。
Logistic映射的輸入和輸出都分布在區間(0,1)上,把區間上的小數x寫成精度L的二進制小數形式:
對于式(6)確定的混沌系統經計算機模擬試驗表明,當L=32時,計算得到的序列未脫離混沌態,因此只要實現32位乘32位的整數計算就能得到混沌序列。(6)式對于硬件的實現是很有利的,2L-Xk是Xk的補,乘4和除2L分別利用寄存器左移和右移就可以實現,所以關鍵是實現32位乘以32位的整數計算。
Logistic 映射的FPGA實現原理框圖[7]如圖1所示,其工作過程是:首先將上一次迭代結果Xk放入L比特寄存器,如果位是第一次迭代,則將外部輸入的迭代初值X0放入寄存器;然后將其分成兩路,一路將Xk存入2L比特寄存器,另一路取反后加1得到Xk的補
;對于將其右移一位,并將移出的最低位分別送到2L個2輸入與門的其中一個輸入端,同時將Xk左移一位后,將2L比特寄存器中的內容送入與門的另2L個輸入端,并將結果送到2L位加法器,經過L次后移位、與和加運算后,即得到XK(2L-XK);對于2L比特移位寄存器中的XK(2L-XK)左移2位后,其中的高L位即為Xk+1,將其輸出并重新輸入到上面的L比特寄存器Xk,令Xk=Xk+1,重復執行以上過程,即生成所需要的混沌序列。
?
2 混沌二維置換網絡的設計
置換網絡的目的是利用若干步驟的變換,打亂原來每個元素的位置,使原來有規則的元素分布在多次變換后顯現無規則、接近隨機的分布,從而起到信息保密的作用。這里利用兩個Logistic 映射產生的混沌序列具有對初始值的高度敏感性、不可預測性及其遍歷性等特點,來產生置換網絡的置換地址。
混沌二維置換網絡框圖如圖2所示,二維m×n置換陣列的存儲單元存放m×n個明文數據,混沌序列產生器a和b分別提供二維置換陣列的行地址和列地址,用來選擇要輸出的數據,如果這一位置的數據已經輸出,則混沌序列產生器a和b再進行一次迭代,直到產生未輸出數據的地址為止。這里采用Logistic映射來作為混沌序列產生器。圖中si是置換前的明文序列,sτ(i)是置換后的序列。這里si和sτ(i)的關系由混沌序列產生器a和b來確定。
?
?
置換網絡的硬件實現原理圖[8]如圖3所示,這里將RAM1和RAM2分別映射成E0000～E1FFF和E2000～E3FFF的計算機的4K內存,并采用DMA方式對其存取,從而降低了主機的負擔,提高了加密的速度。當對一個文件等進行加密時,首先對XC4010進行初始化,并將Logistic映射的迭代初值(密鑰)存入XC4010的寄存器中;然后將加密的明文數據文件分成以2K為單位的數據段,通過DMA方式將一個數據段存入RAM1中,這時隔離器2選通,其它隔離器為三態;數據傳送完后,用中斷方式通知單片機W77e58,單片機按順序讀出RAM1中的數據,并利用XC4010內部兩個Logistic混沌映射產生的序列的高5位和高6位作為RAM2(6116)的11位地址,將讀出的數據存入RAM2中,如果兩個Logistic混沌序列組成的地址與前面的地址一樣,則再進行一次迭代;當所有RAM1中的數據存入RAM2中以后,利用中斷通知計算機數據置換完成,計算機用DMA方式將RAM2中的數據儲存入密文文件中,這樣就完成了一個2K數據段的加密。重復上述過程將明文文件的其它數據進行置換加密,從而完成整個文件的置換加密。解密置換過程與加密置換過程類似,只是數據流向相反,即首先將解密數據放入RAM2中,再利用XC4010產生的置換地址讀出,并按順序存入RAM1中,RAM1中的數據是解密置換后的數據。
?
這里采用具有密集布線資源的Xilinx公司的X4010,來實現圖1所示的Logistic 映射的迭代運算過程。單片機采用華邦公司的Turbo51系列的W77e58,因為它具有速度高(10M的指令周期)、內置RAM和ROM、豐富的I/O資源等優點。
3 實驗及其結果分析
本文用兩個Logistic映射產生的混沌序列作為置換網絡的置換地址,其實現精度為32位。圖4是由圖3裝置對圖像的加密置換和解密置換試驗結果。
?
?
這里兩個Logistic映射的迭代初值分別為x01=0.3和x02=0.4,圖4(b)即為圖4(a)加密置換后的圖像,圖4(c)為兩個Logistic映射的初值分別取x01=0.3+0.1-16和x02=0.4+0.1-16時進行解密置換時得到的圖像,圖4(d)為兩個Logistic映射的初值與加密置換取值相同時進行解密置換時得到的圖像。可以看出,當用來產生加密置換和解密置換的混沌序列初始值相差很小時,也無法置換出正確的圖像。如果用窮舉搜索法對此加密方法進行破譯時,其密鑰的搜索量為22×32,可以通過多次置換來增加抗破譯的強度。
本文利用混沌序列對初始值的高度敏感性、不可預測性及其遍歷性等特點來產生置換網絡,克服了以往用簡單的移位、取模、線性變換等實現置換網絡的缺點。通過硬件方式實現了Logistic映射的混沌置亂網絡,并提出一種Logistic混沌映射的整數實現方法,給出了它的FPGA實現方法。試驗結果表明這種置亂方法具有置換速度快的優點,是一種高抗破譯性置換算法。
?
參考文獻
1 王育民,劉建偉.通信網的安全~理論與技術 [M]. 西安:西安電子科技大學出版社, 1999
2 Hao B L.Elementary symbolic dynamics and chaos in?dissipative systems [M].Singapore:World Scientific Pub-
lishing Co Ltd,1989
3 Sakai H,Tokumaru H.Auto correlation of a certain chaos [J]. IEEE Trans ASSP,1980;289(5):588~590
4 孫 楓,秦紅磊.基于混沌的分組密碼置換網絡的設計[J]. 中國工程科學,2000;(9):47～49
5 Collet P,Eckmann J.P. Iterated maps on the interval?as dynamical system [M]. Boston:Birkhauser,1980
6 王 亥,胡建棟.Logistic-Map混沌擴頻序列[J]. 電子學報,1997;(1):19~23
7 The Programmable Logic Date Book,1998
8 Walter A .Triebel著,王克義,王鈞譯.硬件、軟件及接口技術教程[M].北京:清華大學出版社,1998