二元周期序列復(fù)雜度的分析.pdf

1、在通信系統(tǒng)中，流密碼是保證通信安全最重要的一種手段，大量應(yīng)用于軍事、政治和電子商務(wù)中。其安全性得到研究學(xué)者的大量關(guān)注，特別是衡量密鑰流安全性強(qiáng)度的度量。
　　 線性復(fù)雜度是衡量密鑰流安全強(qiáng)度的一個(gè)重要指標(biāo)，如何提高線性復(fù)雜度的計(jì)算效率是流密碼學(xué)中一直研究的問題。此外，在各種編碼（如Reed-Muller碼）中，線性復(fù)雜度也可作為基本的度量。然而，高線性復(fù)雜度并不意味著難以預(yù)測。若改變序列若干位，線性復(fù)雜度馬上降下來，加密信息很容

2、易遭到已知明文攻擊。為了解決上面的問題，Stamp-Martin引入周期序列線性復(fù)雜度穩(wěn)定性的概念以衡量序列的穩(wěn)定性，定義序列在較大干擾的情況下，仍然能夠保持較為理想的線性復(fù)雜度。
　　 本文首先介紹了隨機(jī)序列的生成過程，序列隨機(jī)性的描述，線性移位寄存器的特性。然后引入線性復(fù)雜度算法，包括求任意長度序列線性復(fù)雜度的B-M算法，以及求周期為2n序列的線性復(fù)雜度的算法，以及給出了在CUDA(ComputeUnified Device

3、 Architecture)平臺(tái)下，并行加速2n序列線性復(fù)雜度的算法，實(shí)驗(yàn)結(jié)果得到比較理想的加速比，能夠在足夠短的時(shí)間內(nèi)求得序列線性復(fù)雜度。
　　 序列線性復(fù)雜度即使達(dá)到最大，而序列復(fù)雜度卻可能很不穩(wěn)定，理想中的隨機(jī)序列不僅要線性復(fù)雜度最大，穩(wěn)定性需要保證，希望在一定的擾動(dòng)下，序列仍能夠保持較大的線性復(fù)雜度。為了衡量序列的穩(wěn)定性，本文介紹k錯(cuò)線性復(fù)雜度的定義，表示擾動(dòng)k位序列后序列的最小線性復(fù)雜度，因?yàn)閗錯(cuò)(k-error)線性

4、復(fù)雜度是在序列線性復(fù)雜度基礎(chǔ)上引入的概念，所以求k錯(cuò)線性復(fù)雜度的算法也是由求線性復(fù)雜度的算法擴(kuò)展而來，并且由于數(shù)據(jù)的相互依賴性更小，適合CUDA并行化計(jì)算。
　　 針對周期為2n的二元序列，若線性復(fù)雜度錯(cuò)誤譜具有較多的關(guān)鍵點(diǎn)(critica] point)，表明序列具有很好的穩(wěn)定性。本文中，給出n=7時(shí)存在最多關(guān)鍵點(diǎn)個(gè)數(shù)為34（2n(∶)2(G)2）的周期序列。在篩選穩(wěn)定序列的過程中，發(fā)現(xiàn)了一些序列的相似特性，進(jìn)而把這部分序列歸