周期為2p的二元序列的2—adic復(fù)雜度

姜麗穎

摘 要：文章提出了一個(gè)快速算法確定周期為2p的二元序列的2-adic復(fù)雜度，給出了具體確定其序列2-adic復(fù)雜度的一個(gè)有效上界。

關(guān)鍵詞：2-adic復(fù)雜度；周期序列；FCSR序列

中圖分類(lèi)號(hào)：TN918.4 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2095-2945（2017）21-0027-02

引言

流密碼是私鑰密碼中一類(lèi)非常重要的密碼體制，流密碼的安全性取決于密鑰流的安全性，要求密鑰流序列盡可能具有隨機(jī)序列的某些特性。根據(jù)不同的攻擊方法，人們提出了很多衡量序列安全性的指標(biāo)，2-adic復(fù)雜度及線性復(fù)雜度是其中兩個(gè)重要指標(biāo)。它們分別是針對(duì)帶進(jìn)位反饋移位寄存器（FCSR）和線性反饋移位寄存器（LFSR）兩種序列發(fā)生器而提出來(lái)的。較高的2-adic復(fù)雜度和線性復(fù)雜度使得密鑰流序列可以有效抵抗有理逼近算法[1]和B-M算法[4]的攻擊。

1994年，Klapper和Goredky提出了帶進(jìn)位反饋移位寄存器模型[3]。

設(shè)q為奇數(shù)，則連接數(shù)為q的FCSR結(jié)構(gòu)圖如圖1：

其中

q+1=q1·2+…+qr·2r，qr=1，qi，an-i∈{0，1}，1？燮i？燮r，mn-1∈Z。具體實(shí)施過(guò)程如下：

（?。┯?jì)算 ；

（ⅱ）右移一位，輸出寄存器最右端的an-r；

（ⅲ）令an=？滓n（mod2）放入寄存器的最左端；

注：稱(chēng)m是記憶。FCSR的一個(gè)狀態(tài)是指記憶m和寄存器的比特，即（mn-1，an-1，...，an-r）是FCSR的一個(gè)狀態(tài)。若這個(gè)狀態(tài)以后還出現(xiàn)，則稱(chēng)該狀態(tài)是周期的。

1 基礎(chǔ)知識(shí)

定義1 設(shè)=（s0，s1，s2，…） 表示一條二元周期序列，稱(chēng)能夠生成的最短的帶進(jìn)位反饋移位寄存器的長(zhǎng)度為的2-adic復(fù)雜度，并記為？準(zhǔn)2（），而稱(chēng)其連接數(shù)q為的最小生成數(shù)。

引理1 令=（s0，s1，s2，…） 為一條二元周期序列，且其可被以q為連接數(shù)的帶進(jìn)位反饋移位寄存器生成，則有？琢（）=？撞si2i=s0+s12+s222+…=-r/q，其中滿足-q？燮r？燮0，gcd（r，q）=1。則此帶進(jìn)位移位寄存器是生成的最短的帶進(jìn)位的反饋移位寄存器。因此，？準(zhǔn)2（）=log2|q|。

令22p-1=（2p+1）（2p-1），L=2p+1，M=2p-1，S=（s0，s1，...，s2p-1）

記S（2）=s0+2s1+…+22p-1s2p-1。

則

引理2 設(shè)n？叟2為整數(shù)，A0，A1，...，Ak-1都是長(zhǎng)度為n的 0，1向量，d為2n-1的因子，則有

定理1 設(shè)p為奇素?cái)?shù)，=（s0，s1，s2，…）是周期為T(mén)=2p的二元序列，將S=（s0，s1，...，s2p-1）等分為2個(gè)長(zhǎng)度為p的向量，S=（S0||S1），其中S0=（s0，s1，...，sp-1），S1=（sp，sp+1，...，s2p-1），則

證明：由T=2p可知

又因?yàn)?/p>

所以

因?yàn)?/p>

所以

顯然，S0（2）=S1（2）和S0=S1等價(jià)。

所以

定理2 設(shè)p為奇素?cái)?shù)，=（s0，s1，s2，…）是周期為T(mén)=2p的二元序列，將S=（s0，s1，...，s2p-1）等分為2個(gè)長(zhǎng)度為p的向量，S=（S0||S1），

其中S0=（s0，s1，...，sp-1），S1=（sp，sp+1，...，s2p-1）。記

則

即

證明：因?yàn)镸=2p-1，所以

因此

由引理1可知

所以

定理3 設(shè)p為奇素?cái)?shù)，=（s0，s1，s2，…）是周期為T(mén)=2p的二元序列，將S=（s0，s1，...，s2p-1）等分為2個(gè)長(zhǎng)度為p的向量，S=（S0||S1），

其中S0=（s0，s1，...，sp-1），S1=（sp，sp+1，...，s2p-1）。記

則

證明：由定理2可知

由于N為長(zhǎng)度為p的向量，

所以 或

即 或

因而 。

2 計(jì)算周期為2p的序列的2-adic復(fù)雜度上界的算法

依據(jù)定理1、定理2和定理3，給出如下算法

算法：

輸入：周期為T(mén)=2p的二元序列=（s0，s1，s2，…）；

輸出：序列的一個(gè)連接數(shù)q和它所對(duì)應(yīng)的2-adic復(fù)雜度的上界？漬。

初值：q=1，？漬=0。

（1）設(shè)B0=（s0，s1，...，sT-1），T=2p，？滋=T/2=p。

將B0等分為2個(gè)長(zhǎng)度為？滋=p的向量，

其中

a. 若B0，0=B0，1，取B=B0，0

b. 若B0，0≠B0，1，計(jì)算B1=B0，0？茌B0，1，q=qL，？漬=？漬+p

（2）將上述B1=B0，0？茌B0，1=（b0，b1，...，bp-1）等分為p個(gè)長(zhǎng)度為l的向量，

其中 。

a. 若 ，取C=B1，0；

b. 否則，計(jì)算

注：

參考文獻(xiàn)：

[1]Klapper A and Goresky M. Cryptanalysis Based on 2-Adic Rational Approximation.in Advances in Cryptology-CRYPTO'95， vol. 963， pp. 262-273，1995.

[2]Klapper A and Goresky M. Feedback Shift Registers， 2-Adic Span， and Combiners with Memory. J. Cryptology， vol. 10， pp. 111-147，1997.

[3]Klapper A and Goresky M. 2-Adic Shift Register. in Fast Software Encryption，vol. 809， pp. 174-178， 1993.

[4]Berlekamp S. R.，Algebraic coding theory， New York： McGraw-Hill， 1968.