一種快速準確適用性廣的偽隨機擾碼識別方法

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

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

一種快速準確適用性廣的偽隨機擾碼識別方法

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

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

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

誤碼率; 盲識別; 快速相關攻擊; m序列統計特性; 偽隨機擾碼

在通信領域中，實際的數字通信系統為了提高性能，信號在傳輸前常采用擾亂編碼技術以改變其傳輸特性。加擾在提高信號傳輸安全性的同時也使原始信息變為充分隨機化的信號，因此，研究如何快速正確地識別對方采用的擾碼顯得尤為重要。

從擾碼序列是否獨立用于加擾的偽隨機序列來看，擾碼可以分為自同步擾碼和偽隨機擾碼兩種。兩種擾碼識別的區別主要在于自同步擾碼識別只需要識別擾碼器結構；而偽隨機擾碼識別在識別擾碼器結構的基礎上還需要識別擾碼器的初態。本文主要研究偽隨機擾碼的識別問題。

1 研究現狀

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

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

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

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

針對現有偽隨機擾碼盲識別方法在識別時間效率、識別準確率和識別適用范圍的局限性，以及各種方法的優勢，本文提出了一種新的盲識別方法。

2 算法原理及過程

本文擾碼識別算法在現有方法的基礎上，有效地結合了基于m序列統計特性的擾碼識別和基于卷積相關攻擊的擾碼識別方法，可以較好地解決在高誤碼率以及擾碼器級數較高情況下偽隨機擾碼盲識別的問題。其主要由兩部分組成，即基于m序列統計特性的擾碼器結構識別和基于卷積相關攻擊的擾碼器初態識別。

2.1 基于m序列統計特性的擾碼器結構識別

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

式中，0

2.2 基于卷積相關攻擊的擾碼器初態識別

1) 構造生成矩陣和編碼矩陣

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

并且根據

2) 對卷積碼序列進行Viterbi譯碼

在信道序列位置Location(構造卷積碼序列對應的信道序列位置，其初始值為1)處，分別截取信道序列Z和Z*(Z*為將接收到的信道序列中1變為0，0變為1得到的序列)，分別與生成矩陣GLFSR構造卷積碼序列rn和在譯碼時遍歷2B個譯碼初始狀態以得到準確的譯碼結果。

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

當Comp<ρ(ρ為設置比較誤碼率Comp的閾值，其初始值為0.1)，且ρ<0.5，則為最后識別的擾碼器初態，識別結束。

當Comp*>*ρ(*ρ為設置比較誤碼率Comp*的閾值，其初始值為0.9)，且*ρ>0.5，則為最后識別的擾碼器初態，識別結束。

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

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

2.3 算法流程

圖1為基于m序列統計特性和卷積相關攻擊的擾碼識別算法流程圖。

圖1 基于m序列統計特性和卷積相關攻擊的擾碼識別算法流程圖

3 應用及結果分析

3.1 實例分析

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

表1 偽隨機擾碼游程統計結果

1) 先進行游程統計和寄存器級數初識別。表1為偽隨機擾碼的游程統計結果，由統計結果可以看出，在l=5附近，1/2遞減規律開始不明顯；在l=16附近，游程個數開始趨于0，由判決標準可以確定級數l的范圍為5<1<16。

表2 基于m序列統計特征得到的優勢值與抽頭(k)關系

表2中列出了每個可能的級數對應的一定抽頭數下最大優勢值。

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

3.2 性能分析

采用本文提出的擾碼識別方法對不同擾碼器結構以及不同誤碼率分別進行測試，并與基于枚舉法的擾碼識別方法和基于相關攻擊的擾碼識別方法進行了比較。

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

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

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

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

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

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

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

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

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

4 結 束 語

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

[1] 伍文君, 黃芝平, 唐貴林, 等. 含錯擾碼序列的快速恢復[J]. 兵工學報, 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函數在解二元域方程組上的應用[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] 黃芝平, 周靖, 璟蘇紹. 基于游程統計的自同步擾碼多項式階數估計[J]. 電子科技大學學報, 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]. 科技風, 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序列統計特性的序列密碼攻擊[J].通信技術, 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] 伍文君, 唐貴林, 黃芝平. 一種快速相關攻擊算法[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]. 信號處理, 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].電路與系統學報, 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 ? )，女，博士，教授，主要從事網絡虛擬化、軟件定義網絡、云計算、星地融合光網絡等方面研究.