一種基于GF（ ）的流密碼設計

舒景辰　張志佳　張丹

摘 要：為滿足密碼學安全領域對安全性和加密速度的需求，本文設計了一種高效流密碼。本算法基于流密碼體制進行設計，最小數據處理長度為128位，每次分組密鑰長為560位。在數據加密過程中向明文混入無效信息，擴充密文數據量并能有效避免特殊數據帶來的不安全隱患。算法的加、解密結構具有很大的相似性，易于進行并行計算以及在硬件上實現。針對真隨機數發生器和偽隨機數發生器兩種方式產生的密鑰給出不同的優化算法，降低存儲代價。

關鍵詞：流密碼；分組結構；數據冗余；有限域GF（ ）

中圖分類號：TP309.7 文獻標識碼 A 文章編號：2095-2163（2014）02-

An Algorithm of Stream Cryptography based on GF（ ）

SHU Jingchen，ZHANG Zhijia，ZHANG Dan

（School of Software， Shenyang University of Technology， Shenyang Liaoning， 110870， China）

Abstract： In order to satisfy the needs of security and efficiency of cryptography， this paper designed an algorithm， which is based on stream cipher. The minimum length of data processing is 128 bits and length of each grouping key is 560 bits. The plaintext data is mixed with invalid information in the process of encrypted， expands ciphertext data and effectively prevented hidden dangers that specific data brings. Encryption and decryption algorithm have a lot similarities in structure， which are easy to be implemented in parallel computing and hardware. Depending on the way to generate true-random number generator and pseudo-random number generator， different optimization algorithms are given to reduce storage costs.

Key words： Stream Cryptography；Block Structure；Data Redundancy；Finite Field GF（ ）

0引 言

密碼學是信息安全技術的核心，主要由密碼編碼技術和密碼分析技術兩個分支組成[1]。密碼學是在編碼與破譯的對抗實踐中逐步發展起來的，并隨著先進科學技術的應用，已日漸成為一門綜合性的尖端技術科學。密碼學是一門交叉學科，集語言學、數學、電子學、聲學、信息論、計算機科學以及通信與信息系統等多學科于一體，涉及的內容非常廣泛[2]。密碼是通信雙方按約定的法則進行信息特殊變換的一種重要保密手段。早期密碼僅是對文字或數字進行加、解密變換，隨著通信技術的發展，對語音、圖像、數據等都可實施加、解密變換。現今信息網絡的普及，給人們帶來高效信息共享便利的同時，也帶來了安全隱患，所以當今各國對密碼學的編碼和分析研究均表現了濃厚的興趣，并給予了高度的重視。除了能夠保證信息的機密性，密碼技術還能完成數字簽名、身份驗證、系統安全等高級功能，從而在提供了安全性的同時又保證了信息的完整性[3]。

密碼學理論主要有三大體制，即基于數學的公鑰密碼、對稱密碼和基于量子力學的量子密碼[4]。從密碼學的發展史來看，密碼學經歷了傳統密碼學和現代密碼學兩個階段。現代密碼學是建立在精確的安全假設基礎上，通過使用安全證明的方法，可證明方案已達到精確陳述的安全要求。現代密碼學的一個發展分支即是理論密碼學，這一分支為現代密碼學提供了理論基礎和基本原則[5]。下面即對密碼學理論的三大體質進行逐一地分析和闡述。

公鑰密碼體制主要有兩類，一類基于大整數因式分解，另一類基于離散對數[6]。在公鑰密碼體制中，基于大整數因式分解的RSA應用最為廣泛，是目前最有影響力的公鑰密碼。由于RSA基于一個簡單的數論事實且又能抵抗已知的所有密碼攻擊，因而得到了廣泛的應用。隨著科學技術的發展，分解大整數的能力日益增強，768位模長的RSA密碼體制已經面臨威脅，而要保證RSA的安全性就要相應地增加模長。但是分組長度太大，密鑰產生的運算代價會很高，由此而導致加密速度將比DES等傳統密碼的速度低得多，所以RSA只適用于較小文件[7]。

對稱密碼體制是密碼算法的重要組成部分，不僅可用于數據加密，也可用于消息的認證。根據對明文消息加密方式的不同，對稱密碼可以分為分組密碼和流密碼兩種，并廣泛應用于商業和軍事系統中[8]。關于分組密碼分析的方法中最具影響的兩個攻擊方法就是差分分析和線性分析。在密碼的破譯方面，國內外的研究工作則主要集中在積分分析、功耗分析和代數攻擊的方法上[9]。

流密碼的分析和設計在軍事和外交保密通信中有著重要價值，流密碼的設計基本上都是保密的，國內外少有專門論述流密碼學的著作，公開的文獻也不多。盡管如此，由于流密碼具有長度可靈活變化以及運算速度快等優點，業已成為國際密碼應用的主流，其中基于偽隨機序列的流密碼則是當今最通用的密碼系統[10]。

本文提出的基于GF（ ）的流密碼借鑒了分組密碼結構化明顯及流密碼加密速度快的特點，在現有算法的基礎上加以改進，通過混入部分無效信息、有限域運算等方式增強了密文的安全性。該算法具有較強并行計算能力，易于軟硬件實現。由于此技術的密鑰空間龐大且運算簡單，所以能對大文件進行快速加密，適用于數據傳輸及安全認證等方面。

1研究內容

本算法基于流密碼體制進行設計，借鑒分組加密的處理結構，每次可處理256位數據，有較高的加解密速率，在64位機上的算法效率可達948KB/S。密鑰可由偽隨機數發生器和真隨機發生器兩種方式產生。使用偽隨機數發生器產生密鑰時只需存儲種子，而且占用空間也很小。然而使用真隨機數發生器產生密鑰時卻需要較大的存儲空間，本算法對其存儲進行了優化設計。算法還提供了對特殊數據處理的解決方案，能有效避免明文在全0、全1狀態下所帶來的安全隱患。每次分組密鑰為560位，由三種密鑰構成，分別實現了有限域運算、矩陣混淆以及異或操作的功能。在數據加密的過程中向明文混入無效信息，擴充密文數據量。算法加解密結構具有很大的相似性，因此代碼實現簡單，且易于開展并行計算。

2密碼結構設計

2.1設計思路

在流密碼體制中，產生密鑰有兩種方式。一種是基于物理信息的真隨機數發生器，一種是基于數學函數的偽隨機數發生器。本算法同時適用于兩種密鑰發生器，并對真隨機發生器產生的密鑰進行壓縮。目前常用偽隨機數發生器來生成易于保存的非主觀的密鑰[11]。根據偽隨機數的性質，不同的種子將生成不同的隨機序列。傳統密碼學是通過置換等方式改變位置，不能從根本上解決數據安全問題，而利用GF（ ）上的有限域計算則能提供更高級別的安全保障。同時，在數據的處理方面，進一步加入了與明文等長的冗余信息，數據量擴充一倍。

2.1.1 加解密流程

明文字節流進入處理機后，首先，與等長的隨機二進制數據進行隔位混入；其次，對其進行GF（ ）上的乘法模運算；再次，寫入矩陣進行混淆；最后，對前幾階段處理后的數據進行異或操作，實現對數據的三次加密。

解密是加密的逆序操作，首先，對密文先進行異或操作；其次，寫入矩陣進行數據還原；再次，通過計算GF（ ）上的乘法逆元還原數據；最后，去除混入的隨機二進制數。

2.1.2 密鑰組成

系統共分為三種密鑰，分別負責三種加密方式，均有不同的種子，這些種子分別是U1、U2、U3密鑰。每次分組處理時密鑰長度為560位，共分為3組，U1密鑰（GF（ ）密鑰，256位）對數據進行多項式模運算，U2密鑰（矩陣混淆密鑰，48位）對數據進行矩陣列混淆，U3密鑰（異或密鑰，256位）與256位數據進行異或。

2. 2無效信息混入

明文數據流進入密碼系統后，每次分組128位獲取，每隔一位插入一個隨機二進制數。每次數據分組處理完成后，數據長度由128位擴展至256位，數據量擴大了1倍。由于偽隨機數概率分布的穩定性，此時倘若無效信息是通過這種方式產生的，就能有效避免全0、全1等特殊數據的出現。

2.3在GF（ ）上的模運算

GF（ ）在現代密碼學中有重要的意義，其計算原理是基于多項式有限域運算。在GF（ ）上進行的乘法模運算是封閉的，不會超出數據的取值范圍。GF（ ）具有較高的生成效率，但不能對整字節進行計算。GF（ ） 能計算整字節數據，但由于其最大素數為251，不能在 范圍內取值，造成空間浪費[12]。考慮到后者的整字節處理能力，本算法選用GF（ ）有限域進行計算。

無效信息混入處理后的數據按1字節分段，然后對其進行乘法模運算。式（1）中T為U1密鑰，P為經無效信息混入處理后的1字節二進制數據。

本文定義‘ 符號為連接符，且數據右為高位，密鑰左為高位。

， （1）

2.3.1 加密

加密進行最高次為8的乘法模運算，既約多項式為：

根據密鑰計算和明文G（x）和F（X）：

對兩函數求積并進行模運算，如式（2）所示：

（2）

將 拆分為二進制形式即為通過GF（ ）運算后加密的結果。

2.3.2 解密

利用擴展歐幾里得算法可求出在GF（ ）上的乘法模運算逆元 。對相同次冪的系數進行異或，那么

（3）

即為解密后的數據[13]。

2.4矩陣混淆

本部分對U1密鑰處理后的數據進行二次加工，數據按行方向寫入矩陣，通過行位移后，利用16位全排列對矩陣進行列置換。

2.4.1 矩陣混淆加密

定義一個 的矩陣，將數據利用矩陣進行混淆。經過無效信息混入處理后的數據從128位擴增至256位，將其倒序按行方向寫入矩陣，隨后對第 行數據進行左移 位操作，處理后結果如圖1所示（ 表示行， 表示列）。

圖1 混淆矩陣

Fig.1 Chaotic matrix

倒序寫入將不同分組的數據順序打亂，行位移和列讀取的混淆方式使每個分組中的數據從字節級別分散開。 為矩陣混淆密鑰（U2密鑰）， 為加密后的數據，具體操作方式遵循下列公式：

（4）

（5）

2.4.2 矩陣混淆解密

解密過程與加密相似，是加密的逆序。 為矩陣混淆密鑰（U2密鑰）， 為密文數據，密鑰和明文的定義如下：

（6）

（7）

定義 為數據中間量，利用映射關系還原矩陣的列混淆，那么（ 表示矩陣中 行第 個元素）：

（8）

T為未經過行位移的數據。對第 行數據進行右移 位操作，完成了矩陣的還原。然后，再按行讀取即完成了二位矩陣至一維向量的轉換。

2.4.3 矩陣混淆密鑰的產生

事實上，矩陣混淆密鑰是16位數的全排列，每位均不同。本算法利用遞減進制位法生成全排列序列，需借助遞降輔助序列 [14]。規定

（9）

（10）

令 初值取15，每次取 ，進行 賦值，為一次操作。每次操作后， 值減1，至 為0止，快速生成了16位數的一種全排列，即為矩陣混淆密鑰U2。

2.4.2 矩陣混淆密鑰的壓縮

使用真隨機數產生密鑰時，若直接存儲將占用8字節，由于本算法密鑰量大，需對其進行壓縮。16！=20 922 789 888 000 小于248=281 474 976 710 656 ，因此可將排列數進行散列后存儲在6字節空間內[15]。其中全排列

與常進制數相似，變進制數第 位的位權為 ，且滿 進1[16]。可利用變進制計數法進行散列，其位權值為：

（11）

規定 是 的個數，將變進制數轉為10進制數：

（12）

即為壓縮后的矩陣混淆密鑰U2，與直接存儲相比，每個分組節省了2字節空間。

2.4.5 矩陣混淆密鑰的解壓

將 按權值展開后，得

（13）

那么逆序數 可得。解壓過程同樣需要借助遞降輔助序列，設 初始值為15，每次進行 操作。每次操作后 高位數值逐次向低位補齊，經過15次操作，解壓得到完整的矩陣混淆密鑰。

算法如下：

for i ← 15 to 0 do

S[ i ] ← T[ Q[ i ] ]

for j ← Q[i] to i-1 do

T[ j ] ← T[ j + 1 ]

2.5異或處理

由于模運算無法生成251以上的數據，存在不安全因素。為此，對數據進行異或處理可使數據具有更高的安全性。這一部分對數據進行第三次加密，密鑰為U3，密鑰長度與數據長度相等。加密前數據為 ，那么加密后的數據 按如下公式計算：

（14）

解密只需將密文與密鑰進行按位異或即可，公式如下：

（15）

2.6安全性分析

流密碼結構因其具有較高的安全性，一直應用于軍事系統中。本算法的安全性完全基于密鑰安全，每次分組處理的密鑰長為560位。其中256位為GF（ ）密鑰，48位為矩陣混淆密鑰，256位即為異或密鑰。在加密與處理過程中混入了無效信息，數據量擴大1倍，杜絕了全0、全1事件的出現，在此基礎上又進行了GF（ ）上的計算，使得密碼系統具有較大的不穩定性，導致數據每改變一位，明文改變多位。

2.7效率分析

算法支持多線程編程，但使用單線程編程便于測算算法效率。經過對10MB大小的數據進行1 000次測試發現，得到的加密和解密時間非常相近。但當采用不同位寬生成偽隨機數時，代碼效率會有較大的差異。算法速率與偽隨機數發生器位寬的關系如表1所示。

雖然算法位寬的增加，會使得算法效率提升，但算法效率不會無休止地面、增長。隨著位寬的增加，其增長速率表現出遞減的趨勢。隨機數位寬的擴大會減少隨機數產生的次數，但同時也會增加數據拆分等相關工作的運算代價，由此造成的效率降低會更明顯于隨機數計算次數減少所帶來的好處。本算法的結構化明顯、原理簡單，因而代碼實現容易。在數據處理過程中，向明文添加冗余信息，能有效避免特殊值產生的不安全因素，增強了密文的安全性。

3結束語

該文設計了一款基于GF（ ）的流密碼算法，能夠滿足密碼學安全領域對安全性和加密速度的需求，具有一定的現實意義。該設計以流密碼體制為理論基礎，提出了無效信息混入的概念，結合了有限域封閉運算、矩陣混淆和異或的三種加密方式。這種設計思想既適合在軟、硬件上高速實現，又能滿足密碼學安全應用的需求。

參考文獻：

[1]馮登國.國內外密碼學研究現狀及發展趨勢[J].通信學報，2002，23（05）：18-26.

[2]曾輝，張躍進.信息工程專業密碼學課程理論教學研究： 2010年亞太地區信息論學術會議[C].西安：出版者不詳，2010：69-72.

[3]呂彩霞.密碼學技術在網絡信息安全中的應用[J].科技廣場，2011，（09）：104-107.

[4]林德敬，林柏鋼.三大密碼體制：對稱密碼、公鑰密碼和量子密碼的理論與技術[J].電訊技術，2003，（03）.

[5]任偉.密碼學與現代密碼學研究[J]. 信息網絡安全，2011，（08）：1-3.

[6]陳曉峰，王育民.公鑰密碼體制研究與進展[J].通信學報，2004，25（08）：109-118.

[7]王水勇，石冰心.基于RSA的安全應用及漏洞分析[J].計算機與數字工程，2005，33（3）：34-38.

[8]付安民，張玉清.對稱密碼算法暴力破解的研究現狀和進展： 2006北京地區高校研究生學術交流會[C].北京：出版者不詳，2006：2011-2017.

[9]肖國鎮，白恩健，劉曉娟.AES密碼分析的若干新進展[J].電子學報，2003，（10）：1549-1554.

[10]羅啟彬，張健.流密碼的現狀和發展[J].信息與電子工程，2006，4（01）：75-80.

[11]胡濤，郭立，黃昊，劉軍.一種新的混沌隨機數生成器實現方案[J].電子技術應用，2006，（06）：51-53.

[12]STALLINGS W. Cryptography and Network Security[M].New York：Pearson，2010.

[13]蔡永泉，趙磊，靳巖巖.基于有限域GF（2～n）上圓錐曲線的公鑰密碼算法[J].電子學報，2010，（09）：1464-1468.

[14]李模剛.全排列生成算法在克萊姆法則中的應用[J].現代計算機（專業版），2010，（09）：13-15.

[15]周云才.利用排列的逆序數實現排列生成算法[J].信息科技，2006，（01）：151.

[16]李淑芝，王顯珉.基于m-n變進制規則的動態圖軟件水印算法[J].計算機工程，2012，38（21）：17-21.