周建欽，王洪翠

（1.杭州電子科技大學通信工程學院，浙江杭州 310018；2.安徽工業(yè)大學計算機學院，安徽馬鞍山 243032）

非平衡2n－周期二元序列的5－錯誤序列＊

周建欽1，2，王洪翠1

（1.杭州電子科技大學通信工程學院，浙江杭州 310018；2.安徽工業(yè)大學計算機學院，安徽馬鞍山 243032）

線性復雜度和k－錯線性復雜度是密鑰流序列隨機性檢測及其穩(wěn)定性度量的2項重要指標，對衡量密鑰流序列密碼強度具有極其重要的意義.計算序列k－錯線性復雜度的一個行之有效的方法是，分析研究漢明重量最小的錯誤序列.在此基礎之上，給出了5－錯線性復雜度不大于2n－3、等于2n－2－2m和2n－2－2m＋x時錯誤序列的計數(shù)公式，并通過計算機編程進行了驗證.

密鑰流序列；k－錯線性復雜度；k－錯誤序列

流密碼是保密通信中一個重要的密碼體制，線性復雜度和k－錯線性復雜度分別用來度量密鑰流序列的隨機性和穩(wěn)定性.為了防止攻擊者通過B-M算法［1］分析出整個序列，要求密鑰流序列的線性復雜度足夠大.然而現(xiàn)實通信過程中是存在干擾的，當改變序列少量比特時，有的序列的線性復雜度會急劇下降，例如24－周期二元序列s（4）＝｛1100 0000 1000 0000 ｝0000｝，線性復雜度為16，這是其線性復雜度能夠達到的最大值.改變s（4）中1個非0比特，得到＝｛1000 0000 1000 0000｝后，其線性復雜度變?yōu)?，當改變3個非0比特得到全0序列時，其線性復雜度則下降至0.顯然這樣的序列是不穩(wěn)定的，這就是密碼學意義上的弱序列.

?。ぃ瓎危?］最早注意到密鑰流序列的不穩(wěn)定性問題，隨后Stamp M等［3］引入k－錯線性復雜度的概念，將其作為度量序列穩(wěn)定性的一個指標.之后，Kurosawa K等［4］進一步提出錯誤序列的概念.2008年，戚文峰等［5］給出k－錯誤序列的定義，并且認為對數(shù)值較小的k，要有較少的k－錯誤序列，以減少線性復雜度下降的概率.

通過文獻［6］提出的計算k－錯線性復雜度行之有效的方法，即將其轉化為求漢明重量最小的錯誤序列，筆者給出在k＝5時，非平衡2n－周期二元序列當5－錯線性復雜度不超過2n－3或等于2n－2－2m和2n－2－2m＋x時錯誤序列的計數(shù)公式M5（s（n））.

1 預備知識

定義2［8］設周期為N的序列s和e，序列s的k－錯線性復雜度為LCk（s）.若e滿足LC（s＋e）＝LCk（s），1≤WH（e）≤k，則稱e為s的k－錯誤序列.

記序列s的k－錯誤序列總數(shù)為Mk（s）.

引理2［8］設2n－周期二元序列s（n），若LC（s（n））＝2n，則s（n）的一個周期內的漢明重量為奇數(shù)；若LC（s（n））＜2n，則s（n）的一個周期內的漢明重量為偶數(shù).

引理3［8］設Ei是周期為2n的二元序列，且序列一個周期內只有第i位上的元素是1，其他元素全為0，0≤i＜2n.若j－i＝2r（1＋2a），a≥0，0≤i＜j＜2n，r≥0，則LC（Ei＋Ej）＝2n－2r.

2 非平衡2n－周期序列的5－錯誤序列

定理1 設s（n）是2n－周期二元序列，且LC5（s（n））＝c，當1≤c≤2n－3時，有M5（s（n））＝1.

證明 設s（n）＝p（n）＋u（n），s（n）＝q（n）＋v（n），且LC（p（n））＝LC（q（n））＝c，WH（u（n））＝1，3或5，WH（v（n））＝1，3或5.

假設u（n）≠v（n），因為p（n）＋u（n）＝q（n）＋v（n），所以p（n）＋q（n）＝u（n）＋v（n）.根據(jù)引理1，LC（p（n）＋q（n））＜c≤2n－3，而u（n）＋v（n）最多呈8等分分布，由Games-Chan算法可知LC（u（n）＋v（n））≥2n－3.從而假設不成立，u（n）＝v（n），s（n）的5－錯誤序列只能為u（n），即M5（s（n））＝1.

證畢.

例1 當n＝4，c＝2時，序列s（4）＝｛1110 1110 1000 0000｝，LC5（s（4））＝2，只有1個錯誤序列e（4）＝｛0100 0100 0010 1010｝；當n＝4，c＝1時，序列s（4）＝｛1111 1110 1100 1100｝，LC5（s（4））＝1，也只有1個錯誤序列e（4）＝｛0000 0001 0011 0011｝.

定理2 設s（n）是2n－周期二元序列，LC（s（n））＝2n，LC5（s（n））＝2n－2－2m，n≥4，0≤m≤n－4，則M5（s（n））＝1，2或3.

證明 設序列s（n）＝p（n）＋u（n），LC（p（n））＝2n－2－2m，WH（u（n））＝1，3或5，另設序列v（n），WH（v（n））＝1，3或5，使得LC5（s（n））＝LC5（p（n）＋u（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m.

（1）當LC（u（n）＋v（n））＜2n－2－2m時，根據(jù)引理1，有LC5（s（n））＝LC5（p（n）＋u（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m.此時，u（n）＋v（n）呈4等分分布，根據(jù)引理2，有WH（u（n）＋v（n））＝8.

（Ⅰ）WH（u（n））＝3時，根據(jù)引理3，將u（n）分成2m＋1個子序列，每個子序列中任意2bit間的距離均為2m＋1的整數(shù)倍，即子序列中的各個比特之間的位置關系滿足｛i，i＋2m＋1，...，i＋（2n－m－1－2）·2m＋1，i＋（2n－m－1－1）·2m＋1｜0≤i≤2m＋1－1｝.

此時，u（n）中的3個非0比特只能在同一子序列，且僅有2個非0比特相距2n－2的整數(shù)倍.在這種情況下，滿足WH（v（n））＝5，LC5（s（n））＝LC5（p（n）＋u（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m的序列v（n）只有1個，亦或v（n）＝u（n），故有M5（s（n））＝2.

（Ⅱ）當WH（u（n））＝5時，同樣將u（n）分成2m＋1個子序列，子序列中每個比特之間的距離為2m＋1的整數(shù)倍.

（ⅰ）若u（n）中的5個非0比特屬于同一子序列.

（a）當u（n）中有3個非0比特（z1，z2，z3），它們之間的距離均為2n－2的整數(shù)倍，另外2個非0比特（z4，z5）之間的距離也為2n－2的整數(shù)倍時，僅存在1個序列v（n），WH（v（n））＝3，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m，亦或v（n）＝u（n），故有M5（s（n））＝2.

（b）當非0比特（z1，z2，z3）之間的距離仍為2n－2的整數(shù)倍，而（z4，z5）之間的距離不為2n－2的整數(shù)倍時，則有2個序列v（n），WH（v（n））＝5，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m，亦或v（n）＝u（n），故有M5（s（n））＝3.

（c）當分別有2對非0比特的距離為2n－2的整數(shù)倍時，僅有1個v（n），WH（v（n））＝5，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m，亦或v（n）＝u（n），故有M5（s（n））＝2.

（ⅱ）若u（n）中有4個非0比特在同一個子序列.

（a）此時，若4個非0比特中的3個比特間兩兩相距2n－2的整數(shù)倍，則只有1個序列v（n），WH（v（n））＝5，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m，亦或v（n）＝u（n），故有M5（s（n））＝2.

（b）若分別有2對非0比特間的距離為2n－2的整數(shù)倍，也只有1個序列v（n），WH（v（n））＝5，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m，亦或v（n）＝u（n），故有M5（s（n））＝2.

（2）當LC（u（n）＋v（n））＞2n－2－2m時，根據(jù)引理1，有LC5（s（n））＞2n－2－2m.然而LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m，此時有M5（s（n））＝1.

綜上所述，M5（s（n））＝1，2或3.

證畢.

例2 當n＝4，m＝0時，序列s（4）＝｛1100 1100 1001 1000｝，LC5（s（4））＝3，其5－錯誤序列有2個，分別為＝｛0000 0000 0101 0100｝＝｛0101 0101 0000 0001｝.

定理3 設2n－周期二元序列s（n），LC（s（n））＝2n，LC5（s（n））＝2n－2－2m＋x，n≥5，2≤m＜n－3，0＜x＜2m－1，則M5（s（n））＝1，2，3或2n－m－2.

證明 設序列s（n）＝p（n）＋u（n），LC（p（n））＝2n－2－2m＋x，WH（u（n））＝1，3或5，另設序列v（n），WH（v（n））＝1，3或5，使得LC5（s（n））＝LC5（p（n）＋u（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m＋x.此時，u（n）＋v（n）呈4等分分布，根據(jù)引理2，有WH（u（n）＋v（n））＝8.

（1）LC（u（n）＋v（n））＜2n－2－2m＋x時，LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m＋x.

（Ⅰ）WH（u（n））＝3時，根據(jù)引理3，將u（n）分成2m個子序列，每個子序列中的任意2bit間的距離均為2m的整數(shù)倍.為了滿足情況（1），u（n）中的3個非0比特只能在同一個子序列中.

當3個非0比特中只有2個比特的距離為2n－2的整數(shù)倍時，只存在1個序列v（n），WH（v（n））＝5，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m＋x，亦或v（n）＝u（n），故有M5（s（n））＝2.

（Ⅱ）當WH（u（n））＝5時，同樣先將u（n）分成2m個子序列，子序列中的每個比特之間的距離為2m的整數(shù)倍.

（?。┤魎（n）中的5個非0比特在同一子序列中.

（b）若其中有3個非0比特（z1，z2，z3）的距離為2n－2的整數(shù)倍，而另外2個非0比特（z4，z5）之間的距離也為2n－2的整數(shù)倍時，則有1個序列v（n），WH（v（n））＝3，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m＋x，亦或v（n）＝u（n），故有M5（s（n））＝2.

（c）若僅有3個非0比特間的距離是2n－2的整數(shù)倍，則有2個序列v（n），WH（v（n））＝5，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m＋x，亦或v（n）＝u（n），故有M5（s（n））＝3.

（d）若分別有2對非0比特之間的距離為2n－2的整數(shù)倍，則僅有1個序列v（n），WH（v（n））＝5，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m＋x，亦或v（n）＝u（n），故有M5（s（n））＝2.

（ⅱ）若4個非0比特屬于同一個子序列.

（b）若其中3個非0比特之間的距離為2n－2的整數(shù)倍，或者分別有2對非0比特間的距離為2n－2的整數(shù)倍時，則只有1個序列v（n），WH（v（n））＝5，使得LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m＋x，亦或v（n）＝u（n），故有M5（s（n））＝2.

（2）當LC（u（n）＋v（n））＞2n－2－2m＋x時，根據(jù)引理1，有LC5（s（n））＝LC（q（n）＋u（n）＋v（n））＞2n－2－2m＋x.然而LC5（s（n））＝LC（q（n）＋u（n）＋v（n））＝2n－2－2m＋x，故有M5（s（n））＝1.

綜上所述，M5（s（n））＝1，2，3或2n－m－2.

證畢.

3 結語

基于Games-Chan算法，分析了2n－周期非平衡二元序列s（n）的5－錯線性復雜度所對應的錯誤序列，給出了5－錯線性復雜度不大于2n－3、等于2n－2－2m和2n－2－2m＋x時5－錯誤序列的個數(shù)M5（s（n）），并通過計算機編程給予驗證.

［1］ BERLEKAMP S R.Algebraic Coding Theory［M］.New York：Mcgraw-Hill，1968.

［2］ DING Cun-sheng，XIAO Guo-zhen，SHAN Wei-juan.The Stability Theory of Stream Ciphers.LNCS 561［M］.Berlin：Springer-Verlag，1991：85－88.

［3］ STAMP M，MARTIN C F.An Algorithm for the k-Error Linear Complexity of Binary Sequences with Period 2n［J］.IEEE Transactions on Information Theory，1993，39（4）：1 398－1 401.

［4］ KUROSAWA K，SATO F，SAKATA T，et al.A Relationship Between Linear Complexity and k-Error Linear Complexity［J］.IEEE Transactions on Information Theory，2000，46（2）：694－698.

［5］ 譚 林，戚文峰.F2上2n－周期序列的k－錯誤序列［J］.電子與信息學報，2008，30（11）：2 592－2 595.

［6］ 周建欽.具有2n線性復雜度的2n－周期二元序列的3－錯線性復雜度［J］.應用數(shù)學學報，2013，36（3）：399－413.

［7］ 李鶴齡，戚文峰.Fp上pn－周期序列的k－錯誤序列［J］.通信學報，2010，31（6）：19－24.

［8］ 周建欽，劉 軍.2n－周期二元序列的3－錯誤序列分布［J］.電子與信息學報，2012，34（8）：1 923－1 927.

（責任編輯 向陽潔）

5-Error Sequences of 2n-Periodic Unbalanced Binary Sequences

ZHOU Jian-qin1，2，WANG Hong-cui1

（1.Telecommunication School，Hangzhou Dianzi University，Hangzhou 310018，China；2.Computer Science School，Anhui University of Technology，Ma’anshan 243032，Anhui China）

The linear complexity and k-error linear complexity have been used to measure the randomness and the stability of key stream sequences.Both of them are extremely important for studying key stream strength.An effective method to calculate k-error linear complexity is to study error sequences with minimal Hamming weight.On this basis，the counting functions on the 5-error sequences with 5-error linear complexity up to 2n－3or equal to 2n－2－2m，2n－2－2m＋xare derived，and are verified by computer program.

key stream sequence；k-error linear complexity；k-error sequence

TN918

A

10.3969／j.issn.1007－2985.2013.05.007

1007－2985（2013）05－0027－04

2013－03－29

安徽省自然科學基金資助項目（1208085MF106）

周建欽（1963－），男，山東巨野人，安徽工業(yè)大學計算機學院教授，碩士，主要從事通信、密碼學與理論計算機科學研究.