劉好莉++任義++楊晗

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

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

1 引言

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

2 問(wèn)題描述

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

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

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

3.1 算法描述

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

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

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

（1）

假設(shè)k

（2）

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

3.2 算法優(yōu)化

在查找校驗(yàn)等式對(duì)時(shí)的算法改進(jìn)：

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

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

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

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

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

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

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

Step 1：計(jì)算子序列（）

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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].計(jì)算機(jī)工程，2009，35（17）：129-131.

作者單位

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