荊 銳，朱 平，楊恒歡，馮 濤

（1. 上海中新科技管理學(xué)院計(jì)算機(jī)系，上海200023；2. 上海第二工業(yè)大學(xué)成人與繼續(xù)教育學(xué)院，上海200041）

線性移位寄存器在圖像加密中的應(yīng)用

荊 銳1，朱 平2，楊恒歡1，馮 濤2

（1. 上海中新科技管理學(xué)院計(jì)算機(jī)系，上海200023；2. 上海第二工業(yè)大學(xué)成人與繼續(xù)教育學(xué)院，上海200041）

圖像加密技術(shù)作為數(shù)字信息保護(hù)的一種有效手段，隨著信息技術(shù)的發(fā)展，人們對(duì)其安全性的要求越來越高。討論了關(guān)于線性移位寄存器（LFSR）在圖像加密中的應(yīng)用。本算法先采用LFSR算法產(chǎn)生偽混沌比特密鑰流，將該密鑰流作為隨機(jī)值映射算法和加密算法的初始參數(shù)。隨機(jī)值映射算法取其中較高位的密鑰流，生成置亂序列用于圖像像素的位置置亂。另一組密鑰流作為加密序列可對(duì)圖像的像素值進(jìn)行加密。實(shí)驗(yàn)結(jié)果表明該方法運(yùn)算速度快，通過隨機(jī)值映射算法產(chǎn)生的偽隨機(jī)置亂和加密序列具有很強(qiáng)的可操作性、保密性，而且截取偽混沌比特密鑰流的位數(shù)也可作為密鑰存在。

線性移位寄存器；比特密鑰流；隨機(jī)值映射算法

0 引言

隨著數(shù)字技術(shù)和電子商務(wù)的迅猛發(fā)展，信息傳輸?shù)陌踩宰兊迷桨l(fā)重要，其中數(shù)字圖像的信息安全引起了人們的密切關(guān)注。據(jù)美國(guó)科研人員的研究成果，圖像和電子郵件為隱藏和傳送信息提供了更多的機(jī)會(huì)，數(shù)字圖像保密技術(shù)作為數(shù)字圖像信息保護(hù)的有效手段，人們對(duì)其安全性的要求也越來越高。目前，主要有三種數(shù)字圖像的安全保護(hù)技術(shù)。

0.1 空間置亂技術(shù)

數(shù)字圖像空間置亂技術(shù)是數(shù)字圖像加密的一種方法。圖像置亂的功能是將圖像中像素的空間位置打亂，將原始圖像變成一個(gè)雜亂無序、不可見的新圖像?；谥脕y技術(shù)的圖像加密技術(shù)一般可以認(rèn)為是對(duì)圖像矩陣進(jìn)行有限步長(zhǎng)的初等矩陣轉(zhuǎn)換，以此打亂圖像像素的排列位置，達(dá)到圖像加密的目的。

目前流行的置亂方法有：

(1) Arnold變換。它是一種常用方法，基本上是連接和裁剪矩陣的過程，將數(shù)字圖像矩陣中的像素位置重新排列。根據(jù)圖像矩陣是有限點(diǎn)集的特點(diǎn)，這種不斷排列的結(jié)果由于動(dòng)力系統(tǒng)固有的特性，在迭代到一定步數(shù)時(shí)會(huì)恢復(fù)到原來的圖像矩陣，即變換具有龐加萊回復(fù)性或周期性。隨著圖像的增大，周期變大，然而單次置亂所需的計(jì)算量急劇增大，導(dǎo)致同樣置亂效果所需的迭代次數(shù)增加，而且，使用窮舉法迭代即可輕易破解，所以該方法不能滿足現(xiàn)代加密、解密的要求，通常僅用做預(yù)處理[1]，或者與其他方法混合加密[2]。

(2) Hilbert曲線變換。這是由德國(guó)數(shù)學(xué)家Hilbert給出的填滿一個(gè)單位正方形的FASS曲線[3]。影響其置亂效果的因素主要有置亂路徑和置亂周期。

如圖1所示，在一張3×3的圖像中各像素按圖中曲線走向作位移，遍歷所有點(diǎn)就可生成一副置亂后的圖像。每個(gè)方陣圖像（大于等于2×2）都有多種FASS曲線，所獲得的結(jié)果都是不同的，因此可通過多周期的不同曲線來組合置亂圖像以提高安全性。此外，空間置亂技術(shù)還有Fibonacci變換和騎士巡游變換等方法。

圖1 (a) Hilbert曲線1 (b) Hilbert曲線2Fig.1 (a) Hilbert line 1 (b) Hilbert line 2

0.2 像素變換技術(shù)

數(shù)字圖像像素變換技術(shù)是通過將圖像各像素的灰度值改變，來達(dá)到隱藏圖像的目的?，F(xiàn)有的像素變換方法大多基于混沌理論，其中應(yīng)用最為廣泛的是Logistic映射。如文獻(xiàn)[4]提出了一種基于離散數(shù)字混沌序列的圖像加密方法。文獻(xiàn)[5]在Logistic映射的基礎(chǔ)上，采用3個(gè)由離散數(shù)字混沌序列進(jìn)行異或運(yùn)算獲得長(zhǎng)周期的離散數(shù)字混沌序列，將產(chǎn)生的混沌序列用于圖像的加、解密。混沌加密方法的安全性主要取決于密鑰流產(chǎn)生器所產(chǎn)生的信號(hào)與隨機(jī)數(shù)的近似程度，密鑰流越接近隨機(jī)數(shù)則安全性越高，但由于現(xiàn)今的混沌技術(shù)只能產(chǎn)生偽隨機(jī)數(shù)，故安全性較低。

0.3 數(shù)字水印技術(shù)

目前針對(duì)圖像數(shù)據(jù)的水印算法繁多，現(xiàn)有的數(shù)字水印嵌入方法主要有：空域算法、變換域算法等。文獻(xiàn)[6]中采用的空域算法是通過用密鑰的方式控制水印嵌入，以保證水印分布在圖像中多處不同位置，由此來提高水印的魯棒性，但對(duì)于圖像的抗旋轉(zhuǎn)、抗裁剪能力較弱?；诙S離散余弦變換的變換域方法的主要思想是在圖像的DCT2變換域上選擇中低頻系數(shù)疊加水印信息。數(shù)字水印技術(shù)存在水印的魯棒性與不可見性的矛盾，目前沒有更好的方法使這對(duì)矛盾得到完美的平衡。

1 背景技術(shù)介紹

1948年香農(nóng)（Shannon）從理論上證明：如果密鑰流序列是一真正的隨機(jī)序列，那么相應(yīng)的流密碼就是絕對(duì)安全的，即實(shí)現(xiàn)了完善保密性。但是一個(gè)隨機(jī)序列是無法完全得到的，只能用偽隨機(jī)序列來代替隨機(jī)序列以達(dá)到相對(duì)安全的目的。在信息安全的許多應(yīng)用領(lǐng)域，都需要偽隨機(jī)數(shù)發(fā)生器產(chǎn)生長(zhǎng)周期的隨機(jī)整數(shù)序列，這些整數(shù)或者作為隱藏秘密信息的位置索引，或者作為加（解）密運(yùn)算的密鑰。一般可認(rèn)為偽隨機(jī)序列的隨機(jī)性越高，其加密信息在對(duì)抗如剪裁、噪聲等攻擊后的還原效果越好。

在保密通信中，為了提高流密碼的抗攻擊能力，密鑰流通常需滿足以下三個(gè)要求：大的線性復(fù)雜度、不可預(yù)測(cè)性和長(zhǎng)周期[7]。傳統(tǒng)的信息加密方法可分為分組密碼和序列密碼。序列密碼的安全性要高于分組密碼。LFSR是產(chǎn)生序列密碼的方法之一，其反饋函數(shù)是寄存器中某些位的簡(jiǎn)單異或所得，這些位也稱之為抽頭序列。由于其反饋函數(shù)為線性，因此稱為線性反饋移位寄存器（LFSR∶line feedback shift register）。一個(gè)n位的LFSR能夠產(chǎn)生2n-1位長(zhǎng)的偽隨機(jī)序列。一個(gè)n級(jí)線性反饋移位寄存器（FLSR）由一個(gè)n位寄存器r = r0,…, rn-1和一個(gè)n位的抽頭序列t = t0,…, tn-1組成。為了得到密鑰的一個(gè)位，要利用rn-1，使寄存器向右移動(dòng)一位，并且插入新的比特（位）（r0t0⊕ … ⊕rn–1tn–1）。假設(shè)四級(jí)FLSR的抽頭序列為1001，寄存器的初始值是0010，抽取密鑰流和寄存器的值做異或，第一次生成的值為0001（寄存器向右移1位得0001），密鑰為1，循環(huán)重復(fù)，第二次的密鑰為01，一直到一個(gè)周期結(jié)束。下表通過LFSR產(chǎn)生的是周期為15的密鑰流，010001111010100是最終產(chǎn)生的密鑰流。LFSR方法可以通過使用少量信息來產(chǎn)生較長(zhǎng)的密鑰序列，以模擬一次一密，其生成的密鑰流滿足流密碼的三個(gè)要求。密鑰生成過程如表1所示。

本文先采用LFSR算法產(chǎn)生偽混沌比特密鑰流，將該密鑰流作為隨機(jī)值映射算法的初始參數(shù)。隨機(jī)值映射算法分別按不同位數(shù)截取偽混沌比特密鑰流并產(chǎn)生兩種數(shù)據(jù)序列，將其中一個(gè)作為置亂序列可用于圖像像素的位置置亂，其二作為加密序列可對(duì)圖像的像素值進(jìn)行加密。實(shí)驗(yàn)結(jié)果表明，本文算法所生成的置亂結(jié)合加密的圖像加密程度高，還原損耗低，在運(yùn)算量和安全性上達(dá)到了很好的平衡。

表1 LFSR密鑰流生成表Tab. 1 The table of LFSR key generation

2 基于混沌加密和移位寄存器的圖像加密算法

本文算法通過線性反饋移位寄存器（LFSR）生成兩種不同位數(shù)的偽隨機(jī)密鑰流，作為隨機(jī)值映射算法的初始參數(shù)，其中生成的10 bit密鑰流作為置亂序列用于圖像位置置亂；同時(shí)，其中生成的8 bit密鑰流作為加密密鑰，與置亂后的圖像做異或運(yùn)算，得到混合加密圖像，在解密時(shí)只需要將加密后圖像重新代入上述算法即可得到原始圖像。算法包括四部分：1) 載入初始數(shù)據(jù)并歸一化；2) 生成LFSR密鑰流；3) 隨機(jī)值映射置亂；4) 圖像像素加密。流程圖見圖（3）所示：

圖3 加密流程圖Fig. 3 Flow diagram of encryption

2.1 載入初始數(shù)據(jù)并歸一化

需要載入的數(shù)據(jù)有原始圖像和用戶密鑰。由于圖像信息的數(shù)據(jù)格式與系統(tǒng)做運(yùn)算時(shí)的數(shù)據(jù)格式不符，須進(jìn)行歸一化操作才能夠再加密。初始讀入的灰度圖像數(shù)為二維矩陣，是數(shù)值范圍為0～255的整型數(shù)據(jù)。將圖像格式轉(zhuǎn)為一維向量M，其像素?cái)?shù)值以1/256為階，范圍在0～1之間的Double型數(shù)據(jù)與本文中加密時(shí)密鑰的范圍相同。圖像歸一化使得圖像像素之間的差異性降低，對(duì)數(shù)據(jù)加密所需變化的要求更小。

2.2 生成LFSR密鑰流

在本文算法中的圖像置亂和圖像像素加密算法，都需要定義初始條件參數(shù)初始條件參數(shù)直接關(guān)系到最終圖像的加密效果。在本文算法中，與圖像進(jìn)行置亂或加密的偽隨機(jī)密鑰流的長(zhǎng)度至少要長(zhǎng)于原始圖像一維向量M。本文通過用戶輸入初始密鑰，確定LFSR的初始參數(shù)（寄存器級(jí)數(shù)），可生成所需長(zhǎng)度的密鑰。

傳統(tǒng)LFSR算法的抽頭序列和寄存器初始值是由密鑰發(fā)生器生成的隨機(jī)數(shù)確定，其密鑰長(zhǎng)度由寄存器級(jí)數(shù)確定。在傳統(tǒng)LFSR的加密算法中，需要記錄運(yùn)行移位寄存器和密鑰算法發(fā)生器的時(shí)鐘，即在不同時(shí)間所得的隨機(jī)值是不同的，數(shù)據(jù)恢復(fù)所需時(shí)鐘應(yīng)與其同步。由于需要嚴(yán)格同步，因此計(jì)算復(fù)雜、運(yùn)算量大且速度慢。本文通過用戶控制初始參數(shù)確定時(shí)鐘，同時(shí)增加寄存器級(jí)數(shù)，以獲得較長(zhǎng)的密鑰流，該方法計(jì)算簡(jiǎn)單、速度快。其具體流程如下：

1) 判斷用戶輸入密鑰（Lkey）大小，如果密鑰Lkey數(shù)值過低則采用系統(tǒng)默認(rèn)值（Lkey= 32）；

2) 將Lkey數(shù)值輸入至?xí)r鐘，生成偽隨機(jī)數(shù)列R1（數(shù)值范圍0～1的double型）和抽頭序列R2（序列中各數(shù)值為0或1）；

3) 將R1轉(zhuǎn)為二進(jìn)制，生成二值序列R1’，以Lkey數(shù)值作為循環(huán)數(shù)，將R1與抽頭序列R2做異或循環(huán)，得到足夠長(zhǎng)的二值LFSR密鑰流；

4) 將所得的二值LFSR密鑰流以n（n ≥2）位截段轉(zhuǎn)為密鑰流K（double型數(shù)據(jù)），n為可控參數(shù)。

為了取得更高的安全性，在步驟4) 中根據(jù)截?cái)辔粩?shù)不同可產(chǎn)生不同的密鑰流，在本文算法中，生成的第一個(gè)密鑰流K1是以n =10，即10位截?cái)嗨茫诙€(gè)密鑰流K2，則是以8位截?cái)嗨谩1與K2密鑰流有很大的差異性，可極大地提高安全性。

本方法將隨機(jī)值的確定和用戶密鑰聯(lián)系起來，可相應(yīng)擴(kuò)大密鑰的循環(huán)范圍以及密鑰復(fù)雜度。如果將此處生成的偽混沌二值密鑰流直接用于加密圖像，雖能取得一定的加密效果，但其安全性較低。因此，本文僅將其用作后續(xù)算法的初始條件，通過后續(xù)算法更加接近混沌的密鑰流。這樣加密的圖像安全性更高，幾乎不可能被強(qiáng)制破解。

2.3 隨機(jī)值映射置亂與圖像像素加密

本文提出一種簡(jiǎn)單解決上述安全性問題的方法，以2.2中截?cái)辔粩?shù)為10位所產(chǎn)生的十進(jìn)制密鑰流K1作為初始條件，將其重新排序（由大到小）并記錄其元素排序位置變化。按K1的排序位置將原始圖像像素的空間位置映射到對(duì)應(yīng)位置，得到置亂的圖像。最后將置亂后的圖像與另一個(gè)8 bit的十進(jìn)制密鑰流K2異或加密，取得混合加密效果，其流程如下：

1) 建立與所需加密圖像M等長(zhǎng)的圖像空間序列S，記錄S的原始空間位置；

2) 由系統(tǒng)將2.2中生成的10bit偽混沌密鑰流K1作循環(huán)運(yùn)算；尋找K1中的最大值并將其賦值為?1，將找到的最大值的位置對(duì)應(yīng)記錄到向量S中；重復(fù)循環(huán)，直至K1中均為?1；

3) 將圖像向量M像素的空間位置按變換矩陣S映射，得到圖像向量M1，置亂完成；4) 將圖像向量M1與8 bit十進(jìn)制密鑰流K2異或加密，得到加密圖像M2，加密完成。本文置亂算法采用的是8 bit密鑰流和10 bit密鑰流復(fù)合加密置亂圖像，安全性高，相對(duì)傳統(tǒng)LFSR計(jì)算機(jī)的計(jì)算量小。如果還需要提高安全性，可增加置亂所需密鑰的比特位數(shù)。

3 試驗(yàn)結(jié)果與結(jié)論

本算法采用測(cè)試圖像為“世博會(huì)中國(guó)館”圖像，像素?cái)?shù)大小為128×128，計(jì)算機(jī)硬件為CPU 2.6GHz；內(nèi)存512MB；軟件環(huán)境為WINDOWS-XP, MATLAB 7。輸入的用戶密鑰為默認(rèn)值32。所需時(shí)間包括繪圖時(shí)間，結(jié)果取小數(shù)點(diǎn)后3個(gè)有效位。試驗(yàn)中分別對(duì)圖像做了兩種測(cè)試。

1) 進(jìn)行先置亂后加密及先加密后置亂兩種測(cè)試，測(cè)試結(jié)果見表2。從表2可得：先置亂后加密與先加密后置亂得到的混合加密圖像雖然不同，但是加密效果是幾乎一樣，都有著較高的不可見性，并且兩者所需的運(yùn)行時(shí)間幾乎相等。

表2 測(cè)試表1Tab. 2 Test table 1

2) 在不同位數(shù)密鑰的初始條件（K1分別為6bit、8bit、10bit; K2為8bit）下置亂加密圖像，與Arnold置亂效果作對(duì)比，測(cè)試結(jié)果見表3。由表3可得：傳統(tǒng)Arnold加密對(duì)本圖像的Arnold變換次數(shù)至少需要140次（變換次數(shù)對(duì)運(yùn)算時(shí)間影響很大），才能取得與本文算法相近的加密效果，此時(shí)運(yùn)算時(shí)間略多于本文算法，如果需要較好的置亂效果，效率較差。 本文算法只需要很短的密鑰就可取得良好的加密效果，密鑰比特位越長(zhǎng)，置亂加密效果越好，并且增加置亂算法密鑰位數(shù)對(duì)計(jì)算量的增加不明顯。

表3 測(cè)試表2Tab. 3 Test table 2

[1] SUJATHA S S, MOHAMED SATHIK M. Feature based warermarking algorithm by adopting arnold transform[J].ICT,CCIS, 2010, 101: 78-82.

[2] 馮茂巖, 馮波, 沈春林. 基于分塊DCT變換和Anrold置亂的自適應(yīng)圖像水印算法[J]. 計(jì)算機(jī)應(yīng)用, 2008, 28(1): 171-173.

[3] 齊東旭. 分形及計(jì)算機(jī)生成[M]. 北京: 北京科學(xué)出版社, 1997.

[4] 陳帥, 鐘先信, 石軍鋒,等. 基于離散數(shù)字混沌序列的圖像加密[J]. 電子與信息學(xué)報(bào), 2007, 29(4): 898-900.

[5] 黃曉生, 顧景文. 基于復(fù)合混沌序列與小波變換的圖像加密算法[J]. 計(jì)算機(jī)工程, 2007, 33(14): 128-135.

[6] 陳灝. 空域數(shù)字圖像水印算法研究與實(shí)現(xiàn)[J]. 現(xiàn)代電子技術(shù), 2007, 30(10): 149-165.

[7] BETH T, PIPER F C, The Stop-and-Go Generator[C]//Proc of the EUROCRYPT 84 Workshop on Advances in Cryptology Theory and Application of Cryptographic Techniques, Paris France, 1984: 88-92.

The Application in Image Encryption by Line Feedback Shift Register

JING Rui1, ZHU Ping2, YANG Heng-huan1, FENG Tao2
(1. Department of Computer, Shanghai Science and Technology Management College, Shanghai 200233, P. R. China; 2. School of Adult and Continuing Education, Shanghai Second Polytechnic University, Shanghai 200041, P.R.China)

For digital information protection, image encryption is an effective technology. As the development of information technology, people also need more and more security on image encryption. This thesis discussed the application in image encryption by line feedback shift register. At first the system generated the initial pseudo-chaos bit key stream by LSFR. The key stream becomed the initial parameter of the random value mapped scrambling algorithm and chaos encryption algorithm. Mapping the image with the mapped stream which was generated by the random value mapped scrambling algorithm with the higher digital key stream, then encrypted the image with the encrypted stream which was generated by another key stream. The result shows this system runs fastly. The pseudo-random mapped stream and pseudo-encrypted stream that were generated by the random value scrambling algorithm both had a strong operational, confidentiality. Also the chosen pseudo-chaos bit key stream can become the keywords.

Line Feedback Shift Register; bit key stream; random value scrambling algorithm

TP391.41

A

1001-4543(2011)04-0293-05

2011-04-06;

2011-10-05

荊銳（1987－），男，吉林省吉林市人，學(xué)士，主要研究方向?yàn)閳D像圖形學(xué)應(yīng)用與信息系統(tǒng)安全，電子郵箱jingrui110@hotmail.com