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

周建欽，王洪翠

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

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

周建欽1，2，王洪翠1

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

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

密鑰流序列；k－錯(cuò)線性復(fù)雜度；k－錯(cuò)誤序列

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

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

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

1 預(yù)備知識(shí)

定義2［8］設(shè)周期為N的序列s和e，序列s的k－錯(cuò)線性復(fù)雜度為L(zhǎng)Ck（s）.若e滿足LC（s＋e）＝LCk（s），1≤WH（e）≤k，則稱e為s的k－錯(cuò)誤序列.

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

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

引理3［8］設(shè)Ei是周期為2n的二元序列，且序列一個(gè)周期內(nèi)只有第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－錯(cuò)誤序列

定理1 設(shè)s（n）是2n－周期二元序列，且LC5（s（n））＝c，當(dāng)1≤c≤2n－3時(shí)，有M5（s（n））＝1.

證明 設(shè)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.

假設(shè)u（n）≠v（n），因?yàn)閜（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.從而假設(shè)不成立，u（n）＝v（n），s（n）的5－錯(cuò)誤序列只能為u（n），即M5（s（n））＝1.

證畢.

例1 當(dāng)n＝4，c＝2時(shí)，序列s（4）＝｛1110 1110 1000 0000｝，LC5（s（4））＝2，只有1個(gè)錯(cuò)誤序列e（4）＝｛0100 0100 0010 1010｝；當(dāng)n＝4，c＝1時(shí)，序列s（4）＝｛1111 1110 1100 1100｝，LC5（s（4））＝1，也只有1個(gè)錯(cuò)誤序列e（4）＝｛0000 0001 0011 0011｝.

定理2 設(shè)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.

證明 設(shè)序列s（n）＝p（n）＋u（n），LC（p（n））＝2n－2－2m，WH（u（n））＝1，3或5，另設(shè)序列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）當(dāng)LC（u（n）＋v（n））＜2n－2－2m時(shí)，根據(jù)引理1，有LC5（s（n））＝LC5（p（n）＋u（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m.此時(shí)，u（n）＋v（n）呈4等分分布，根據(jù)引理2，有WH（u（n）＋v（n））＝8.

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

此時(shí)，u（n）中的3個(gè)非0比特只能在同一子序列，且僅有2個(gè)非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個(gè)，亦或v（n）＝u（n），故有M5（s（n））＝2.

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

（?。┤魎（n）中的5個(gè)非0比特屬于同一子序列.

（a）當(dāng)u（n）中有3個(gè)非0比特（z1，z2，z3），它們之間的距離均為2n－2的整數(shù)倍，另外2個(gè)非0比特（z4，z5）之間的距離也為2n－2的整數(shù)倍時(shí)，僅存在1個(gè)序列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）當(dāng)非0比特（z1，z2，z3）之間的距離仍為2n－2的整數(shù)倍，而（z4，z5）之間的距離不為2n－2的整數(shù)倍時(shí)，則有2個(gè)序列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）當(dāng)分別有2對(duì)非0比特的距離為2n－2的整數(shù)倍時(shí)，僅有1個(gè)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個(gè)非0比特在同一個(gè)子序列.

（a）此時(shí)，若4個(gè)非0比特中的3個(gè)比特間兩兩相距2n－2的整數(shù)倍，則只有1個(gè)序列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對(duì)非0比特間的距離為2n－2的整數(shù)倍，也只有1個(gè)序列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）當(dāng)LC（u（n）＋v（n））＞2n－2－2m時(shí)，根據(jù)引理1，有LC5（s（n））＞2n－2－2m.然而LC5（s（n））＝LC（p（n）＋u（n）＋v（n））＝2n－2－2m，此時(shí)有M5（s（n））＝1.

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

證畢.

例2 當(dāng)n＝4，m＝0時(shí)，序列s（4）＝｛1100 1100 1001 1000｝，LC5（s（4））＝3，其5－錯(cuò)誤序列有2個(gè)，分別為＝｛0000 0000 0101 0100｝＝｛0101 0101 0000 0001｝.

定理3 設(shè)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.

證明 設(shè)序列s（n）＝p（n）＋u（n），LC（p（n））＝2n－2－2m＋x，WH（u（n））＝1，3或5，另設(shè)序列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.此時(shí)，u（n）＋v（n）呈4等分分布，根據(jù)引理2，有WH（u（n）＋v（n））＝8.

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

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

當(dāng)3個(gè)非0比特中只有2個(gè)比特的距離為2n－2的整數(shù)倍時(shí)，只存在1個(gè)序列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.

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

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

（b）若其中有3個(gè)非0比特（z1，z2，z3）的距離為2n－2的整數(shù)倍，而另外2個(gè)非0比特（z4，z5）之間的距離也為2n－2的整數(shù)倍時(shí)，則有1個(gè)序列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個(gè)非0比特間的距離是2n－2的整數(shù)倍，則有2個(gè)序列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對(duì)非0比特之間的距離為2n－2的整數(shù)倍，則僅有1個(gè)序列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個(gè)非0比特屬于同一個(gè)子序列.

（b）若其中3個(gè)非0比特之間的距離為2n－2的整數(shù)倍，或者分別有2對(duì)非0比特間的距離為2n－2的整數(shù)倍時(shí)，則只有1個(gè)序列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）當(dāng)LC（u（n）＋v（n））＞2n－2－2m＋x時(shí)，根據(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 結(jié)語(yǔ)

基于Games-Chan算法，分析了2n－周期非平衡二元序列s（n）的5－錯(cuò)線性復(fù)雜度所對(duì)應(yīng)的錯(cuò)誤序列，給出了5－錯(cuò)線性復(fù)雜度不大于2n－3、等于2n－2－2m和2n－2－2m＋x時(shí)5－錯(cuò)誤序列的個(gè)數(shù)M5（s（n）），并通過(guò)計(jì)算機(jī)編程給予驗(yà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－錯(cuò)誤序列［J］.電子與信息學(xué)報(bào)，2008，30（11）：2 592－2 595.

［6］ 周建欽.具有2n線性復(fù)雜度的2n－周期二元序列的3－錯(cuò)線性復(fù)雜度［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，2013，36（3）：399－413.

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

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

（責(zé)任編輯 向陽(yáng)潔）

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

安徽省自然科學(xué)基金資助項(xiàng)目（1208085MF106）

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