基于二維元胞自動機的雙向觸發并行加密模型

摘要：根據二維觸發元胞自動機的特性，提出了一種二維元胞自動機雙觸發并行加//解密模型。仿真實驗表明：與一維耦合觸發元胞自動機相比，二維元胞自動機雙觸發并行加密模型在適度減慢加/解密速度的情況下，大大提高了密鑰空間，具有極高的時間換空間的效率，很好地提高了健壯性和實用性。

關鍵詞：二維觸發元胞自動機； 一維耦合觸發元胞自動機； 雙觸發； 并行加密； 密鑰空間

中圖分類號：TP309.7文獻標志碼：A

文章編號：1001－3695(2008)04－1149－05

信息安全問題已成為世人關注的社會問題，作為信息安全核心的加密技術及其實現愈加復雜[1]。元胞自動機具有組成單元的簡單性、單元之間作用的局部性和信息處理的高度并行性等優點，并表現出復雜的全局特性，使其尤為適合應用于密碼學中[2]。

針對私鑰流的分組密碼以及公鑰系統，研究人員提出了一些基于元胞自動機的加密算法[3~6]。建立在一維二值元胞自動機迭代基礎上的密碼系統較容易破解，因為解決其可逆性問題是P問題；而二維元胞自動機的可逆性問題則是NP問題，可以潛在抵抗密碼分析的攻擊[7]。到目前為止，基于元胞自動機的密碼系統只有極少數是基于二維元胞自動機的[8]。

1二維觸發元胞自動機理論 

元胞自動機最常見的是一維和二維[9，10]。二維元胞自動機被定義為元胞的點陣，有三種相鄰位配置，如圖1[8]所示。可根據一些規則進行編碼[8]：

ai， j=(ai-r， j-r，…，ai， j，…，ai+r， j+r) (1)

在所有2n個規則中有一系列被稱為觸發規則，其特性是在不改變其他相鄰位的前提下，某一位（觸發位）值的改變將會扭轉規則的運算結果[8]。不失普遍性，選擇馮諾依曼型和ai+r，j+r位作為觸發位，該規則表示為

at+1i+r， j+r=(ati-r， j-r，…，ati， j，…，ati+r， j+r-1) XOR ati+r， j+r(2)

遵循式(1)的觸發規則，至少可被定義為用2n-1項確定的真值表的值。項是n-1個非觸發位的所有可能配置，并以升序排列。對于每項，觸發位的值使得規則運算結果為1與規則運算結果為0的所有項的觸發位互補（表1）。

2二維元胞自動機的雙觸發并行加密模型

在設計規則時有觸發規則和非觸發規則。采用觸發規則加密即可以在解密時得到正確的結果；而采用非觸發規則加密在解密時是否能得到正確的結果是不一定的，如圖2所示。

2．1規則設計

因為觸發規則的加密、解密路徑是惟一的，而非觸發規則卻是不惟一的，所以加/解密操作只能選取觸發規則。本模型在設計時回避了對所選取的規則是否為觸發規則的判定，方法如下：在讀入馮諾依曼型相鄰位時，并不讀入觸發位，默認未讀入的那位就是觸發位，這樣真值表的第一列就少了一位；在作十進制規則轉換二進制時，原需轉換為24×r位，現只需轉換為24×r-1。這樣就相當于所用的規則必然是觸發規則的一種，而并非是原來的觸發規則和非觸發規則的總和。通過這種方法即可回避判斷規則是否觸發。

根據上述觸發位互補的性質，產生規則時只需產生一列，另一列取反即可，見表1。當r=1時，規則的取值0~24×r-1，該范圍即為規則的密鑰空間。規則的選取0~65 535。

2．2雙觸發并行加密模型

文獻[8]提出了二維觸發元胞自動機加/解密模型。為了在不降低二維觸發元胞自動機加/解密速度的前提下。提升密鑰空間，本文基于分治法思想，提出了雙觸發并行加/解密模型，最大特點是使用了雙觸發并行思想。雙觸發并行是指將初始明文分成兩塊，同時對兩部分進行加/解密處理。

參考二維元胞自動機相鄰位配置的三種類型：摩爾型相鄰位不允許半并行的反向迭代；而馮諾依曼型的相鄰位和擴展馮諾依曼型的相鄰位允許半并行操作，可以實現快速編碼；擴展馮諾依曼型比馮諾依曼型具有更多的連接位，結構過于笨重，實現過于復雜。因此，本模型采用馮諾依曼型相鄰位的配置，根據二維觸發元胞自動機的性質，可以構建如圖3所示的雙觸發并行加密系統。

二維元胞自動機的雙觸發加密系統加密過程由R步反向迭代組成，使用兩組相互獨立的密鑰[8]：第一組密鑰由兩組上述的觸發規則組成，分別應用于初始明文的兩部分；第二組密鑰由兩組連接位組成，同樣是分別應用于初始明文的兩部分。每一組連接位的數目應為2×r×(X+Y)，所以共有22×r×(X+Y)種可能。其中：X和Y是迭代矩陣的維數，即為信息位矩陣的邊長;r為二維元胞自動機的規則半徑。也可以用正方形來代替矩陣，那么連

接位的數目即變為2×r×(N+N)。根據文獻[8]中所述，將信息位矩陣的維數設計成32×32。首先將明文轉換為二進制0/1流，每次讀入32×32位，即1 024位進行相應操作。

在設計雙觸發模型時須考慮雙觸發的位置，即對明文進行分塊的位置，可以從除邊界以外的任意位置進行分割。因此對于N×N的信息矩陣，選擇雙觸發的位置應有(N-1)×(N-1)種。圖4為了簡化模型，以4×4矩陣為例，從(4-1)×(4-1)=9種位置中選擇了中間等分位置為雙觸發位置。詳述加

密過程如下：

首先將明文從中間等分并填入兩個迭代矩陣；再將隨機產生的連接位分別填入（兩個矩陣可以采用不同的連接位，圖4中采用了相同的連接位）；最后對矩陣中未填位進行補足（可以用隨機產生的0/1位進行補足，圖4中為了簡化實現均填充了0位）。加密的實質是反向迭代的過程，就是按照規則，將t+1時刻觸發位的值編碼為t時刻的值。首先按馮諾依曼型配置按序讀入除觸發位以外的其他相鄰位；然后按照與規則相對應的真值表核查。這種編碼操作是并行的，可對第一列同時進行編碼，互相之間沒有影響；第一列編碼完畢后再對第二列進行編碼，直至將矩陣中所有位編碼完畢。所謂雙觸發并行是對兩個迭代矩陣同時進行編碼操作，從而達到并行處理的效果。

令N為待操作矩陣的維數，r為元胞自動機的規則半徑，n表示迭代輪數，選擇最右邊的元胞為觸發位，令ai， j為在馮諾依曼型相鄰位配置中處于中央位置的元胞，針對兩矩陣的變量參數分別輔以L和R進行表示。

這樣做還有另一個優點，因為讓待加密矩陣進行旋轉而連接位保持不動，可以確保編碼操作依舊按式(3)和(4)，即不用更換觸發位的位置。否則若采用讓連接位進行旋轉而待加密矩陣保持不動，不僅加大了坐標編碼工作的復雜度，而且每次旋轉后還要變換觸發位，使其工作量增加了三倍。所以，該方法的采用大大降低了系統實現的難度。

按照上述一輪加密四步迭代過程，完成兩個迭代矩陣的第一輪加密操作。重復該加密操作，每次迭代輪數增1，直至其值為n停止，完成兩個迭代矩陣n輪加密操作。將加密結果保存在與寄存器data同樣大小的寄存器Newdata中；再從寄存器data中讀入1 024位明文二進制位重復同樣的加密操作，直至處理完data中的所有明文二進制位，等待至并行操作的雙線程結束。

Newdata中的二進制流由兩部分組成，第一部分是加密后的明文，即密文二進制流；第二部分是填充位經加密操作后的結果。將第二部分保存在寄存器redundant中，將密文二進制流經解碼器轉換為密文輸出。

2．3雙觸發并行解密模型

從原理上來說，解密是加密的逆過程，解密與加密迭代步驟的順序和操作完全相反。而且解密為正向迭代過程，即按照規則將t時刻觸發位的值編碼為t+1時刻的值。

解密算法即重復與加密迭代輪數相反的操作，先轉置再編碼。需要注意的有三點：a）加密迭代過程中是連接位保持不動，待編碼矩陣逆時針旋轉90°；所以解密迭代過程與之相反，連接位保持不動，待編碼矩陣順時針旋轉90°。b）解密操作編碼時相鄰位的讀入順序應與加密時一致。c）加密操作是按順序從第1列一直編碼到第32列，所以解密過程必須是相反順序，從第32列逆序編碼到第1列。

密文經編碼器輸出為二進制位串，存放在寄存器data中。從寄存器linkarray中讀出連接位，填入兩個迭代矩陣p_lmessarray和p_rmessarray中的相應位置。從寄存器data中讀入1 024位密文二進制位，存入N×N的二維指針數組p_messarray中；再根據加密時選擇的雙觸發位置對p_messarray進行分割；將分割的兩部分分別存于p_lmessarray和p_rmessarray中的相應位置。從寄存器redundant中按序讀入填充位的加密結果，分別填入p_lmessarray和p_rmessarray的相應位置中。開辟雙線程同時對兩個矩陣進行解密編碼操作。 

編碼開始時，p_lmessarray與p_rmessarray的最后一列元胞被激活。根據馮諾依曼型相鄰位配置依次讀入最后一列元胞的相鄰位，轉換為十進制數后根據該數值查找ltogglearray和rtogglearray數組的相應位，獲得后繼元胞狀態值。

解密過程的實質就是將加密過程的四步迭代反置過來，由連接位順時針旋轉變為逆時針旋轉，按圖5所示完成兩個迭代矩陣的第一輪解密操作。執行與加密同樣的n輪解密，即可得到明文編碼，合并后經解碼器輸出明文信息。

3通信實例及其相似性分析

假設主機A和B進行通信，主機A將32個單詞“alex”組成的信息傳送給主機B。為了防止主機C竊取信息，A利用本文提出的密碼系統對信息進行加密，B在接收到密文后運用同樣的密碼系統進行解密。由于A和B 共享同樣的私有密鑰，即同樣的觸發規則、規則半徑和迭代輪數，同樣的雙觸發位置、連接位和冗余位，可順利實現加/解密；而C即使知道加/解密算法，但沒有確切的密鑰，也就無法獲知消息的內容。

由表2，明文“alex”經編碼器輸出的二進制序列“01100001011011000110010101111000”用32×32矩陣進行處理。隨機選擇規則6 458和9 823進行16輪數據加密，選擇中間等分位置為雙觸發位置，確定規則半徑為1，構建兩個迭代矩陣；由隨機源產生256位連接位，以0作為填充位，將連接位和填充位填入迭代矩陣相應位置，開辟雙線程，同時處理1 024位明文序列。

從表3可以看出明文與密文中相等位的出現概率接近于50%，即相等位與不等位接近于相等。所以，二維元胞自動機雙觸發加密系統具有良好的擴散特性，即明文與密文之間的統計關系較為復雜，敵手無法得到密鑰。



兩個迭代矩陣的相似性對比數據如表4所示。當明文相同時，采用不同的密鑰經過16輪加密后，密文之間相等位的出現概率接近于50%。數據表明密文和密鑰之間的統計關系較為復雜，敵手很難得到密鑰，二維元胞自動機雙觸發加密系統具有良好的混淆特性。

良好的擴散和混淆特性使得二維元胞自動機雙觸發加密模型能夠較好地抗擊敵手對密碼系統的統計分析，成功實現了分組密碼的本質屬性[11]。

4模型性能分析

4．1安全性分析

常規加密的安全性取決于密鑰的安全性，而不是算法的安全性。因此，密鑰空間對于安全性來說非常重要[12]。本文提出的二維元胞自動機雙觸發加密模型采用的是維數為32×32的信息矩陣。令r為觸發元胞自動機規則半徑；l為明文長度。本系統密鑰空間由以下六部分組成：

觸發規則：其密鑰空間為224×r×224×r；連接位：其數目為2×r×(N+N)×2，當N=32時，其密鑰空間為2128×r×2；迭代輪數：其密鑰空間從原理上說是正無窮大，在實現時須考慮合理的范圍，本系統在實現時的密鑰空間為232×2；填充位：其密鑰空間為2「l/1 024×1 024；雙觸發位置：(32-1)×(32-1)=961；規則半徑：其密鑰空間從原理上說是正無窮大，在實現時須考慮合理的范圍，本系統在實現時設定了其密鑰空間為23×23，默認規則半徑為1。

由表5可見，二維元胞自動機系統的密鑰空間遠遠大于一維元胞自動機系統，且二維元胞自動機雙觸發加密系統的密鑰空間又比二維觸發元胞自動機系統大得多。使用強行攻擊是不可行的，因此系統是安全的。

4．2加/解密速度分析

假設更新一列元胞所需要的時間為t，L為明文長度，采用N×N的信息矩陣，迭代輪數為n，元胞自動機規則半徑為r，則二維元胞自動機雙觸發加密系統完成整個加密過程需要時間為

TB=「L/ 1 024Nt(11)

而一維耦合觸發元胞自動機系統完成整個加密過程需要時間為[13]

TC=Lnt+(2r+…+2rn)t=[Ln+rn(1+n)]t(12)

使用計算機軟件模擬二維元胞自動機的雙觸發加密系統和一維耦合觸發元胞自動機加密系統，在Visual C++6.0環境下運行的結果如圖6所示。

由圖6、7可以看出，在規則半徑為1，迭代4輪的情況下，二維元胞自動機雙觸發加密系統加/解密時間約為一維耦合觸發元胞自動機加密系統的2．5倍。但從表5可以看出，前者的密鑰空間至少是后者的2360倍以上，具有更強的實用性。因此，這里采用的是一種時間換空間的方法。就轉換效率來說，本系統是相當高效的。

5結束語

本文基于二維觸發元胞自動機系統提出了二維元胞自動機雙觸發加密系統。該系統的優點在于采用了高效的時間換空間的方法，大大提高了密鑰空間，具備良好的擴散和混淆特性，更能抗擊密碼分析的攻擊，具有更好的實用意義。

參考文獻：

[1]楊波. 現代密碼學[M]. 北京:清華大學出版社， 2003.

[2]張傳武，沈野樵，彭啟琮. 細胞自動機反向迭代加密技術研究[J]. 計算機學報，2004，27(1):125－129.

[3]GUTOWITZ H. Cryptography with dynamical systems in cellular automata and cooperative systems[M]. [s.l.]: Kluwer Academic Pub－lishers， 1993:237－274.

[4]TOSHIKI N Y H， IWAO S，SHINSAKU M，et al. A secret key cryptosystem using a chaotic map[J]. Trans of the IEICE， 1990，73(7):1041－1044.

[5]NANOI S， KAR B， and CHAUOHURI P P. Theory and applications of cellular automata in cryptography[J]. IEEE Trans on Computers，1994，43(12):1346－1356.

[6]GUAN P. Cellular automata public－key cryptosystems[J]. Complex System， 1987，1(1): 51－57.

[7]DURAND B. A random NP－complete problem for inversion of 2D cellular automata[J]. Theoretical Computer Science，1995， 148(1):19－32.

[8]MADIAROVA M， KAKUTA M，OBI T， et al. Opto－electronic block_cipher based on iteration of the 2－D toggle cellular automata: algorithm[J].Optical Review，1999，6(2):110－117.

[9]張傳武，彭啟琮，朱甫臣. 細胞自動機置換群加密技術研究[J]. 計算機科學， 2003，30(3): 171－173.

[10]張文濤，卿斯漢，吳文玲. 對一個基于細胞自動機的分組密碼變形的分析[J]. 軟件學報，2004，15(5):767－771.

[11]楊波. 現代密碼學[M]. 北京:清華大學出版社， 2003.

[12]STALLINGS W. 密碼編碼學與網絡安全: 原理與實踐[M]. 2版.楊明， 胥光輝， 齊望東，譯. 北京: 電子工業出版社，2001.

[13]平萍，趙學龍，張宏，等. 基于耦合觸發元胞自動機的并行加密模型[J]. 信息與控制，2006，35（3）：368－373.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”