二元周期序列復雜度的分析.pdf

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

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

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

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