一種優(yōu)化的CJS型快速相關(guān)攻擊算法

劉好莉++任義++楊晗

摘 要快速相關(guān)攻擊是序列密碼的重要分析方法，本文提出了一種基于CJS型算法的優(yōu)化算法，利用線性分組碼的譯碼方法來解決流密碼的攻擊問題，通過尋找校驗等式對，構(gòu)造子線性分組碼，該碼維數(shù)較小，譯碼速度提高。采用ML-譯碼算法對子碼進行譯碼，通過對LFSR的狀態(tài)進行分割，獨立實施ML-譯碼，可最終獲得序列的初始狀態(tài)，該算法顯著降低了算法中的譯碼復(fù)雜度。

【關(guān)鍵詞】快速相關(guān)攻擊 序列密碼 奇偶校驗碼 分段譯碼

1 引言

快速相關(guān)攻擊核心思想是利用非線性組合生成器的輸入和輸出的相關(guān)性，并且將LFSR的初始狀態(tài)的恢復(fù)問題轉(zhuǎn)化為糾錯碼的譯碼問題。文獻[1]提出算法A和算法B只適于與抽頭數(shù)較少的情況，抽頭數(shù)較少時（t<10）算法攻擊效果很好，而當抽頭數(shù)較大（t>10）時，其算法復(fù)雜度趨近于無窮，此時其攻擊并不是很有效。文獻[2]提出的CJS型算法與截取長度N和子碼信息長度k有關(guān)，而與抽頭數(shù)t無關(guān)。與文獻[1]相比，文獻[2]的算法不受制于反饋多項式抽頭數(shù)的限制。但是算法的缺點在于查找校驗等式對的復(fù)雜度為0（NlogN），從而限制譯碼器輸出。本文給出一種基于文獻[2]的改進算法，對查找校驗等式對的算法部分進行優(yōu)化，顯著降低文獻[2]中算法的計算復(fù)雜度和譯碼復(fù)雜度。

2 問題描述

典型的二元加法序列密碼由n個線性反饋移位寄存器序列通過一個非線性組合生成器生成密鑰流{zi}，明文序列與密鑰序列逐位模2加能夠得到密文序列{ci}。移位寄存器的反饋多項式是已知的，各個移位寄存器的初始狀態(tài)為密碼的密鑰。相關(guān)攻擊認為各個移位寄存器序列與密鑰序列存在一定的相關(guān)性。利用這一性質(zhì)，可以逐個攻擊各個寄存器的初始狀態(tài)，從而最終破解該密碼。

已知條件：反饋多項式為f（x），階數(shù)為L=60。CJS算法是利用已知組合生成器生成序列的截短序列構(gòu)成[N，L]線性分組碼C，通過LFSR的生成矩陣G的列向量L，構(gòu)造出一個維數(shù)比較小的線性分組碼[n2，k]（k0.5，i=1，2，...，N.（p接近0.5）這樣序列z可以看成是序列 a通過一個誤碼率為1-p的二元對稱信（BSC）后的輸出，而寄存器的初態(tài)攻擊問題也就轉(zhuǎn)化為線性分組碼的譯碼問題。譯碼時采用最大似然譯碼算法進行恢復(fù)，通過對LFSR的狀態(tài)進行分割，分別獨立實施ML-譯碼。

3 基于CJS算法的快速相關(guān)攻擊算法

3.1 算法描述

設(shè)發(fā)送端序列為{ai}，接收端序列為{zi}，根據(jù)LFSR的特征多項式，得到（N-L）*N校驗矩陣H。生成矩陣和校驗矩陣是正交的，即H*GT=0。

根據(jù)gi（x）=xi-1mod f（x），i=1，2，...N，

得出線性分組碼的（L*N）生成矩陣G。

（1）

假設(shè)k

（2）

構(gòu)成一個[n2，k]的線性分組碼C2，信息比特是（a1，a2，…ak），信息維數(shù)k，則C2的生成矩陣表示為G2=[gi1k+gj1k]；則在接收端有Z1=zi+zj（0

3.2 算法優(yōu)化

在查找校驗等式對時的算法改進：

建立兩個數(shù)組，在第一次遍歷后第一個數(shù)組中順序放置已查找到的相同的列，另一數(shù)組中放置與已查找到的不同的列。再次遍歷時便可直接從第二個數(shù)組中的第一個列數(shù)開始，以此類推。遍歷完畢后，可直接從第一個數(shù)組中顯示查找到的等式對，大大降低了原算法的復(fù)雜度。

4 相關(guān)數(shù)學(xué)問題的算法實現(xiàn)

通過理論部分對本題題意以及算法的分析，得到如下解題步驟：

Ⅰ.數(shù)據(jù)：已知LFSR的級數(shù)L=60，特征多項式如下：

f（x）=x60⊕x56⊕x47⊕x37⊕x35⊕x16⊕x9⊕x3⊕1

Ⅱ.預(yù)計算：將k置為一固定值且k

Ⅲ.譯碼：輸入數(shù)據(jù)作為接收序列（z1，z2，...zN）。

Step 1：計算子序列（）

Step 2：利用最大似然譯碼算法使生成矩陣G2對線性分組碼C2譯碼，對C2的2k個碼字進行窮舉搜索從中選擇相關(guān)概率較高的信息比特（a1，a2，...，ak），接下來做類似處理便可以得到LFSR的初始狀態(tài)（此處所用的方法為分段譯碼）。

5 結(jié)束語

本文對文獻[2]提出的CJS型快速相關(guān)攻擊算法進行改進，利用線性分組碼的譯碼方法來解決流密碼的攻擊問題，通過尋找校驗等式對，并采用ML-譯碼算法對子碼進行譯碼，最終獲得序列的初始狀態(tài)。通過優(yōu)化尋找校驗等式對的計算復(fù)雜度，大幅度降低了算法的譯碼復(fù)雜度。

參考文獻

[1]Meier W.and Staffelbach O.：Fast correlation attacks on certain stream ciphers， Journal of Cryptology，1（03），pp.159-176，1989.

[2]ChepyzhovV.V.，Johansson T.，Smeets B.：Asimplealgorithm for fastcorrelationattacks on stream ciphers.In： GoosG.，HartmanisJ.，vanLeeuwen J.， Schneier B.（eds） Fast Software Encryption， FSE 2000，Lecture Notes in Computer Science，vol.1978，181-195.Springer，Berlin，Heidelberg.

[3]李興旺.基于LDPC碼的截短線性序列快速相關(guān)攻擊及其在極低信噪比通信的應(yīng)用[D].電子科技大學(xué)，2010.

[4]伍文君，唐貴林，黃芝平.一種快速相關(guān)攻擊算法[J].計算機工程，2009，35（17）：129-131.

作者單位

沈陽建筑大學(xué)信息學(xué)院 遼寧省沈陽市 110168