虞紅芳，吳 曼，劉 曼，杜宇峰

(1. 電子科技大學(xué)通信與信息工程學(xué)院 成都 611731；2. 中國電子科技集團(tuán)公司第五十四研究所 石家莊 050081)

一種快速準(zhǔn)確適用性廣的偽隨機(jī)擾碼識別方法

虞紅芳1，吳 曼1，劉 曼1，杜宇峰2

(1. 電子科技大學(xué)通信與信息工程學(xué)院 成都 611731；2. 中國電子科技集團(tuán)公司第五十四研究所 石家莊 050081)

針對高誤碼率下的偽隨機(jī)擾碼快速盲識別問題，提出了一種結(jié)合基于m序列統(tǒng)計特征和基于卷積的快速相關(guān)攻擊算法的盲識別方法。該方法通過基于m序列統(tǒng)計特性快速獲得擾碼器生成多項式和通過快速相關(guān)攻擊準(zhǔn)確獲得擾碼器初態(tài)。仿真實驗表明，該方法與基于枚舉法的擾碼識別方法和快速相關(guān)攻擊的擾碼識別方法相比，在識別時間和識別正確率方面都有更好的性能表現(xiàn)。

誤碼率; 盲識別; 快速相關(guān)攻擊; m序列統(tǒng)計特性; 偽隨機(jī)擾碼

在通信領(lǐng)域中，實際的數(shù)字通信系統(tǒng)為了提高性能，信號在傳輸前常采用擾亂編碼技術(shù)以改變其傳輸特性。加擾在提高信號傳輸安全性的同時也使原始信息變?yōu)槌浞蛛S機(jī)化的信號，因此，研究如何快速正確地識別對方采用的擾碼顯得尤為重要。

從擾碼序列是否獨立用于加擾的偽隨機(jī)序列來看，擾碼可以分為自同步擾碼和偽隨機(jī)擾碼兩種。兩種擾碼識別的區(qū)別主要在于自同步擾碼識別只需要識別擾碼器結(jié)構(gòu)；而偽隨機(jī)擾碼識別在識別擾碼器結(jié)構(gòu)的基礎(chǔ)上還需要識別擾碼器的初態(tài)。本文主要研究偽隨機(jī)擾碼的識別問題。

1 研究現(xiàn)狀

文獻(xiàn)[1]采用Walsh變換法對擾碼序列的生成多項式進(jìn)行測定，文獻(xiàn)[2]基于文獻(xiàn)[1]改進(jìn)了對擾碼序列的初態(tài)進(jìn)行恢復(fù)的快速相關(guān)算法。但是Walsh-Hadamard法對自同步擾碼進(jìn)行識別時，當(dāng)輸入信息中含1率在46%～50%時正確率不高；對偽隨機(jī)擾碼，該方法僅能識別出生成多項式，無法對擾碼初態(tài)進(jìn)行識別。

文獻(xiàn)[3]利用信道序列的游程特點粗略估計擾碼器多項式階數(shù)的范圍，然后運用組合枚舉求優(yōu)勢的還原方法對擾碼器結(jié)構(gòu)進(jìn)行識別。文獻(xiàn)[4]充分利用了偽隨機(jī)序列中存在的線性相關(guān)性以及概率論中正態(tài)分布的優(yōu)勢理論，但在識別偽隨機(jī)擾碼的寄存器初態(tài)時，對擾碼器輸入的消息序列中含1率有要求(一般不超過20%)。

文獻(xiàn)[5]提出的基于m序列統(tǒng)計特性的擾碼識別方法，充分利用m序列良好的偽隨機(jī)性進(jìn)行游程特性的統(tǒng)計以及序列本身的遞推關(guān)系，還原產(chǎn)生m序列的線性反饋移位寄存器。該方法適用于自同步擾碼生成多項式的識別分析，但并不適用于對偽隨機(jī)擾碼識別。

文獻(xiàn)[6-10]提出了基于卷積相關(guān)攻擊法的擾碼識別方法。特別地，文獻(xiàn)[8]提出一種針對序列密碼改進(jìn)的快速相關(guān)攻擊算法，其將序列密碼的攻擊問題轉(zhuǎn)化為線性分組碼的譯碼問題，但是該算法也需要窮舉擾碼器初始狀態(tài)，在擾碼器級數(shù)較大時需要大量的窮舉時間；文獻(xiàn)[9]提出了一種自同步式偽隨機(jī)擾碼的盲識別法，通過組合枚舉法確定生成多項式，并利用基于卷積碼的快速相關(guān)攻擊算法識別初態(tài)，但是該方法需要窮舉LFSR的所有抽頭情況，且當(dāng)誤碼率較大時恢復(fù)無誤碼的初態(tài)需要找到上萬個校驗方程，這會導(dǎo)致計算量的急劇增加；文獻(xiàn)[10]針對在高誤碼率下多抽頭系數(shù)的偽隨機(jī)擾碼的盲識別問題，提出了結(jié)合BM算法與基于卷積碼的快速相關(guān)攻擊算法的盲識別方法，該方法可以對級數(shù)較低的偽隨機(jī)擾碼器進(jìn)行快速準(zhǔn)確識別，但當(dāng)級數(shù)較大時，隨著預(yù)估計生成多項式急劇增多，識別初態(tài)的時間也急劇增加，識別準(zhǔn)確率明顯下降。

針對現(xiàn)有偽隨機(jī)擾碼盲識別方法在識別時間效率、識別準(zhǔn)確率和識別適用范圍的局限性，以及各種方法的優(yōu)勢，本文提出了一種新的盲識別方法。

2 算法原理及過程

本文擾碼識別算法在現(xiàn)有方法的基礎(chǔ)上，有效地結(jié)合了基于m序列統(tǒng)計特性的擾碼識別和基于卷積相關(guān)攻擊的擾碼識別方法，可以較好地解決在高誤碼率以及擾碼器級數(shù)較高情況下偽隨機(jī)擾碼盲識別的問題。其主要由兩部分組成，即基于m序列統(tǒng)計特性的擾碼器結(jié)構(gòu)識別和基于卷積相關(guān)攻擊的擾碼器初態(tài)識別。

2.1 基于m序列統(tǒng)計特性的擾碼器結(jié)構(gòu)識別

經(jīng)擾碼器加擾后的信道序列具有與組成該擾碼器的寄存器產(chǎn)生的m序列相近的特性，按照游程統(tǒng)計特征，確定級數(shù)l的范圍。對每一個可能的l值，在每種可能的抽頭位置下，統(tǒng)計滿足m序列遞推關(guān)系的個數(shù)：

式中，0

2.2 基于卷積相關(guān)攻擊的擾碼器初態(tài)識別

1) 構(gòu)造生成矩陣和編碼矩陣

對g(x)有LFSR序列un滿足：

并且根據(jù)

2) 對卷積碼序列進(jìn)行Viterbi譯碼

在信道序列位置Location(構(gòu)造卷積碼序列對應(yīng)的信道序列位置，其初始值為1)處，分別截取信道序列Z和Z*(Z*為將接收到的信道序列中1變?yōu)?，0變?yōu)?得到的序列)，分別與生成矩陣GLFSR構(gòu)造卷積碼序列rn和在譯碼時遍歷2B個譯碼初始狀態(tài)以得到準(zhǔn)確的譯碼結(jié)果。

3) 通過誤碼率與閾值比較確定擾碼器初態(tài)

當(dāng)Comp<ρ(ρ為設(shè)置比較誤碼率Comp的閾值，其初始值為0.1)，且ρ<0.5，則為最后識別的擾碼器初態(tài)，識別結(jié)束。

當(dāng)Comp*>*ρ(*ρ為設(shè)置比較誤碼率Comp*的閾值，其初始值為0.9)，且*ρ>0.5，則為最后識別的擾碼器初態(tài)，識別結(jié)束。

當(dāng)Comp>ρ(或Comp*<*ρ)且ρ<0.5(或*ρ>0.5)，將Location值增加1；

當(dāng)Location值小于10l，重復(fù)以上步驟；當(dāng)Location值大于10l，閾值ρ增加0.05，閾值*ρ減少0.05，同時將Location值恢復(fù)成初始值，重復(fù)以上步驟。

2.3 算法流程

圖1為基于m序列統(tǒng)計特性和卷積相關(guān)攻擊的擾碼識別算法流程圖。

圖1 基于m序列統(tǒng)計特性和卷積相關(guān)攻擊的擾碼識別算法流程圖

3 應(yīng)用及結(jié)果分析

3.1 實例分析

為驗證本文算法，以接收信道序列長度為20 kb，擾碼器生成多項式為g(x)=1+x2+x11，初態(tài)為10000001000，誤碼率為0.3，設(shè)置比較誤碼率為0.35為例，進(jìn)行擾碼盲識別和恢復(fù)的仿真試驗。

表1 偽隨機(jī)擾碼游程統(tǒng)計結(jié)果

1) 先進(jìn)行游程統(tǒng)計和寄存器級數(shù)初識別。表1為偽隨機(jī)擾碼的游程統(tǒng)計結(jié)果，由統(tǒng)計結(jié)果可以看出，在l=5附近，1/2遞減規(guī)律開始不明顯；在l=16附近，游程個數(shù)開始趨于0，由判決標(biāo)準(zhǔn)可以確定級數(shù)l的范圍為5<1<16。

表2 基于m序列統(tǒng)計特征得到的優(yōu)勢值與抽頭(k)關(guān)系

表2中列出了每個可能的級數(shù)對應(yīng)的一定抽頭數(shù)下最大優(yōu)勢值。

2) 對5<1<16，分別統(tǒng)計可以發(fā)現(xiàn)01000000001結(jié)構(gòu)對應(yīng)的優(yōu)勢值(0.527 89)最大，故得到擾碼器生成多項式為g(x)=1+x2+x11；再根據(jù)該生成多項式構(gòu)造出其生成矩陣以及編碼矩陣；最后將構(gòu)造的卷積碼序列進(jìn)行Viterbi譯碼，得到預(yù)估計初態(tài)為10000001000，根據(jù)誤碼率比較可以確定該預(yù)估計初態(tài)即為擾碼器初態(tài)。不同抽頭情況下的優(yōu)勢值，其統(tǒng)計結(jié)果如表2所示。

3.2 性能分析

采用本文提出的擾碼識別方法對不同擾碼器結(jié)構(gòu)以及不同誤碼率分別進(jìn)行測試，并與基于枚舉法的擾碼識別方法和基于相關(guān)攻擊的擾碼識別方法進(jìn)行了比較。

圖2所示為基于m序列統(tǒng)計特性和卷積相關(guān)攻擊的擾碼識別方法在不同誤碼率P值的情況下，不同擾碼器級數(shù)對應(yīng)的識別時間，通過該圖可以看出新方法隨著擾碼器的移位寄存器個數(shù)的增多識別時間并沒有急劇增加，即擾碼器級數(shù)越大本文方法在識別時間上的優(yōu)勢越明顯，這是因為該方法首先采用m序列的統(tǒng)計特性得到了擾碼器結(jié)構(gòu)，而在已知擾碼器結(jié)構(gòu)的情況下，利用卷積相關(guān)攻擊算法就可以較快地識別出擾碼器初態(tài)。

圖2 不同擾碼器級數(shù)在不同誤碼率時的識別時間

圖3為在擾碼器級數(shù)9l=的情況下，3種擾碼識別方法在不同誤碼率時的識別時間，其中方法一代表基于枚舉法的擾碼識別方法，方法二代表基于卷積相關(guān)攻擊的擾碼識別方法，方法三代表基于m序列統(tǒng)計特性和卷積相關(guān)攻擊的擾碼識別方法。從圖中可以看出，基于枚舉的擾碼識別方法和基于卷積相關(guān)攻擊的擾碼識別方法隨著誤碼率向0.5靠近時，識別的時間急劇增加，而基于m序列統(tǒng)計特性和卷積相關(guān)攻擊的擾碼識別方法在各誤碼率情況下變化不大，這是由于基于枚舉法的擾碼識別對擾碼器輸入的消息序列中含1量要求較高，而基于卷積相關(guān)攻擊的擾碼識別方法當(dāng)誤碼率較大時，恢復(fù)無誤碼的初態(tài)需要找到上萬個校驗方程，這都會導(dǎo)致計算量的急劇增加。

圖3 9l=，在不同誤碼率下3種方法的識別時間

圖4為在不同擾碼器級數(shù)情況下，3種擾碼識別方法識別的平均正確率。從圖中可以看出，基于枚舉的擾碼識別方法和基于卷積相關(guān)攻擊的擾碼識別方法隨著擾碼器移位寄存器個數(shù)增加識別的平均正確率下降，這是因為隨著擾碼器級數(shù)的增加，枚舉法要遍歷的初態(tài)成指數(shù)增加，卷積相關(guān)攻擊法譯碼長度也增加，導(dǎo)致了這兩種方法識別正確率下降。本文提出的擾碼識別方法識別的平均正確率反而提高，表明該方法更適用于擾碼器級數(shù)較高的情況。

圖4 不同擾碼器級數(shù)，3種方法識別的平均正確率

圖5為在擾碼器級數(shù)9l=的情況下，3種擾碼識別方法在不同誤碼率時的識別正確率。從圖中可以看出，在擾碼器級數(shù)為9時，基于枚舉法的擾碼識別方法只能正確識別誤碼率低于0.2的偽隨機(jī)擾碼，基于卷積相關(guān)攻擊的擾碼識別方法和基于m序列統(tǒng)計特性和卷積相關(guān)攻擊的擾碼識別方法都可以得到較好的識別正確率。

圖5 9l=，3種方法識別正確率的比較

綜上，基于枚舉法的擾碼識別方法識別結(jié)果的正確性受到誤碼率的限制，這是由于該算法本身是基于擾碼序列自相關(guān)性的強弱來判斷擾碼器結(jié)構(gòu)的，而當(dāng)誤碼率較大時，對擾碼序列的自相關(guān)性有較大影響，即會影響擾碼識別的結(jié)果；對基于卷積相關(guān)攻擊的擾碼識別方法，當(dāng)擾碼器生成多項式級數(shù)越大時，識別的時間越長。當(dāng)多項式級數(shù)較低時，基于m序列統(tǒng)計特性和卷積相關(guān)攻擊的擾碼識別方法與快速相關(guān)攻擊算法比較，其時間效率較低，即沒有明顯優(yōu)勢；但隨著多項式級數(shù)增加，特別是當(dāng)級數(shù)增加到10以上時，其正確識別的時間效率明顯地提高了。所以新方法識別的時間效率有所提高，且準(zhǔn)確率也大大提高。

4 結(jié) 束 語

本文創(chuàng)新點在于將傳統(tǒng)識別方法中的基于m序列統(tǒng)計特性法和卷積相關(guān)攻擊法相融合，得到一種全新的識別偽隨機(jī)碼的方法——結(jié)合了m序列統(tǒng)計特性識別擾碼器生成多項式和卷積相關(guān)攻擊識別擾碼器初態(tài)的優(yōu)勢。與基于m序列統(tǒng)計特性的擾碼識別方法比較，本文方法可以對偽隨機(jī)擾碼器的初態(tài)進(jìn)行識別，并且在進(jìn)行初態(tài)識別時不需要對所有初態(tài)進(jìn)行遍歷，而是利用卷積相關(guān)攻擊快速求解初態(tài)，大大降低了識別高級數(shù)的擾碼器初態(tài)的時間，即在識別時間效率上得到提高。與卷積相關(guān)攻擊方法比較，本文方法不用求解預(yù)估計生成多項式集合，而是利用基于m序列統(tǒng)計特性的擾碼識別方法求解出準(zhǔn)確的生成多項式，提高了識別多項式和初態(tài)的準(zhǔn)確率。另外，現(xiàn)有的偽隨機(jī)擾碼識別方法需要知道擾碼器輸入信息序列1、0比例，且限制1、0比例不在0.4左右。本文方法不需要提前知道該比例，且可以快速準(zhǔn)確識別輸入序列1、0比例在0～0.4和0.6～1之間的擾碼器生成多項式和初態(tài)，擴(kuò)大了適用性。

[1] 伍文君, 黃芝平, 唐貴林, 等. 含錯擾碼序列的快速恢復(fù)[J]. 兵工學(xué)報, 2009, 30(8): 1134-1138. WU Wen-jun, HUANG Zhi-ping, TANG Gui-lin, et al. Fast recovery of interfered scrambling code sequence[J]. Acta Armamentarii Sinica, 2009, 30(8): 1134-1138.

[2] 游凌, 朱中梁. Walsh函數(shù)在解二元域方程組上的應(yīng)用[J].信號處理, 2000, 16(12): 27-30. YOU Ling, ZHU Zhong-liang. The application of Walsh function in resolving of F(2) equations[J]. Signal Processing, 2000, 16 (12): 27- 30.

[3] 黃芝平, 周靖, 璟蘇紹. 基于游程統(tǒng)計的自同步擾碼多項式階數(shù)估計[J]. 電子科技大學(xué)學(xué)報, 2013, 42(4): 541-545. HUANG Zhi-ping, ZHOU Jing, SU Shao-jing. Order estimation of self-synchronizing scrambling polynomial based on run statistic[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(4): 541-545.

[4] 朱洪斌. 對偽隨機(jī)擾碼和自同步擾碼的盲識別[J]. 科技風(fēng), 2010(14): 220-221. ZHU Hong-bin. Blind recognition of pseudo-random scrambling and self-synchronizing scrambling[J]. Technological Wind, 2010(14): 220-221.

[5] 朱華安, 謝端強. 基于m序列統(tǒng)計特性的序列密碼攻擊[J].通信技術(shù), 2003(8): 96-98. ZHU Hua-an, XIE Duan-qiang. Attacks upon stream cipher based on m-sequence’s statistical property[J]. Communications Technology, 2003(8): 96-98.

[6] THOMAS J, FREDRIK J. Theotetical analysis of a correlation attack based on convolutional codes[J]. IEEE Transactions on information theory, 2002, 48(8): 2173-2181.

[7] THOMAS J, FREDRIK J. Improved fast correlation attacks on stream ciphers via convolutional codes[DB/OL]. [2009-05-20]. http://www.springerlink.com/ content/.

[8] 伍文君, 唐貴林, 黃芝平. 一種快速相關(guān)攻擊算法[J]. 計算機(jī)工程, 2009, 35(17): 129-131. WU Wen-jun, TANG Gui-lin, HUANG Zhi-ping. Fast correlation attack algorithm[J]. Computer Engineering, 2009, 35(17): 129-131.

[9] 羅向陽, 沈利, 陸佩忠, 等. 高容錯偽隨機(jī)擾碼的快速盲恢復(fù)[J]. 信號處理, 2004, 20(6): 552-558. LUO Xiang-yang, SHEN Li, LU Pei-zhong, et al. Fast blind restore of LFSR sequences with error tolerance[J]. Signal Processing, 2004, 20(6): 552-558.

[10] 郝士琦, 戚林, 王勇. 一種新的偽隨機(jī)擾碼識別方法[J].電路與系統(tǒng)學(xué)報, 2011, 16(4): 6-12. HAO Shi-qi, QI Lin, WANG Yong. A new blind recognition method of pesudo-randomizer code sequence [J]. Journal of Circuits and System, 2011, 16(4): 6-12.

編輯張 俊

Fast and Correct Recognition Method for Pseudo-Randomizer Code

YU Hong-fang1, WU Man1, LIU Man1, and DU Yu-feng2
(1. Institute of Communication and Information Engineering, University of Electronic Science and Technology of China Chengdu 611731; 2. China Electronics Technology Group Corporation 54th Research Institute Shijiazhuang 050081)

To solve the recognition of pseudo-randomizer code under the condition of high bit-error rate, a new blind recognition method is proposed. Combining the statistical property of m-sequence and fast correlation attack mechanism based on convolutional codes, this method can fast recognize the generating polynomial based on m-sequence’s statistical property and correctly find the initial state of linear feedback shift register (LFSR) through fast correlation attack mechanism. The simulation results show that this method outperforms exiting solutions (e.g., enumeration based solution and fast correlation attack based solution) in terms of recognition time and correct rate.

bit-error rate; blind recognition; fast correlation attack; m-sequence’s statistical property; pseudo-randomizer code

TP911.4

A doi:10.3969/j.issn.1001-0548.2015.04.004

2014 ? 03 ? 18;

2014 ? 12 ? 11

國家973計劃(2013CB329103)

虞紅芳(1975 ? )，女，博士，教授，主要從事網(wǎng)絡(luò)虛擬化、軟件定義網(wǎng)絡(luò)、云計算、星地融合光網(wǎng)絡(luò)等方面研究.