周期為2p的二元序列的2—adic復雜度

姜麗穎

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

關鍵詞：2-adic復雜度；周期序列；FCSR序列

中圖分類號：TN918.4 文獻標志碼：A 文章編號：2095-2945（2017）21-0027-02

引言

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

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

設q為奇數，則連接數為q的FCSR結構圖如圖1：

其中

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

（ⅰ）計算 ；

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

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

注：稱m是記憶。FCSR的一個狀態是指記憶m和寄存器的比特，即（mn-1，an-1，...，an-r）是FCSR的一個狀態。若這個狀態以后還出現，則稱該狀態是周期的。

1 基礎知識

定義1 設=（s0，s1，s2，…） 表示一條二元周期序列，稱能夠生成的最短的帶進位反饋移位寄存器的長度為的2-adic復雜度，并記為？準2（），而稱其連接數q為的最小生成數。

引理1 令=（s0，s1，s2，…） 為一條二元周期序列，且其可被以q為連接數的帶進位反饋移位寄存器生成，則有？琢（）=？撞si2i=s0+s12+s222+…=-r/q，其中滿足-q？燮r？燮0，gcd（r，q）=1。則此帶進位移位寄存器是生成的最短的帶進位的反饋移位寄存器。因此，？準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 設n？叟2為整數，A0，A1，...，Ak-1都是長度為n的 0，1向量，d為2n-1的因子，則有

定理1 設p為奇素數，=（s0，s1，s2，…）是周期為T=2p的二元序列，將S=（s0，s1，...，s2p-1）等分為2個長度為p的向量，S=（S0||S1），其中S0=（s0，s1，...，sp-1），S1=（sp，sp+1，...，s2p-1），則

證明：由T=2p可知

又因為

所以

因為

所以

顯然，S0（2）=S1（2）和S0=S1等價。

所以

定理2 設p為奇素數，=（s0，s1，s2，…）是周期為T=2p的二元序列，將S=（s0，s1，...，s2p-1）等分為2個長度為p的向量，S=（S0||S1），

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

則

即

證明：因為M=2p-1，所以

因此

由引理1可知

所以

定理3 設p為奇素數，=（s0，s1，s2，…）是周期為T=2p的二元序列，將S=（s0，s1，...，s2p-1）等分為2個長度為p的向量，S=（S0||S1），

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

則

證明：由定理2可知

由于N為長度為p的向量，

所以 或

即 或

因而 。

2 計算周期為2p的序列的2-adic復雜度上界的算法

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

算法：

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

輸出：序列的一個連接數q和它所對應的2-adic復雜度的上界？漬。

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

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

將B0等分為2個長度為？滋=p的向量，

其中

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

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

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

其中 。

a. 若 ，取C=B1，0；

b. 否則，計算

注：

參考文獻：

[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.