第二章 流密码
一、填空
1. 分组密码和流密码的根本区别在于____________________________
2. n-LFSR最大周期是__________
3. 已知一3-FSR，其反馈函数为f(a1,a2,a3)=a1⊕a2a3，且当前的状态(a3,a2,a1)=(101)，则其前两个状态分别是____________，输出序列的周期是____________
4. n级m序列的异相自相关函数值为____________________
5. 序列{ai}为m序列的充要条件是_________________________________
6. 已知{ai}为m序列，且在该序列中最大0游程为4，则该序列的周期是_______
7. 已知p(x)=x3+x+1, 则其产生的非0序列的异相自相关函数值是________
8. n级M序列的周期是____________
9. 已知一钟控生成器由LFSR1控制LFSR2，极小多项式分别为f1(x)=1+x+x3和f2(x)=1+x2+x3，则产生序列的周期为___________________，线性复杂度为______________________。
10. 已知LFSR1为一10级m序列，LFSR2为以5级m序列，则构成的钟控序列的周期为______,线性复杂度为______________
11. n级m序列中长为i的1游程有多少_____，长为n的1游程有多少_____，长为n的0游程有几个___
12. 至少知道_________个连续的密钥流bit可以破译m序列
13. RC4算法的最大密钥长度是___________
14. 已知某一n级LFSR其非零状态的状态转移图为一个大圈，则其产生的非0序列的周期是________
15. eSTREAM计划候选算法Grain v1的密钥长度______是针对硬件还是软件开发的__________
二、选择：每一项有1个或多个选项是正确的
1. 下面哪些多项式可以作为非退化的5-LFSR的反馈函数(状态转移函数)_____
A. 1+x+x4 B. x1⊕x2⊕x4x5 C. 1+x+x5 D. x4+x5
2．对于一个n-LFSR，设其序列生成函数为A(x)，特征多项式p(x)，全0状态除外，则下面那个要素与其它要素不是一一对应的________
A. Ф(x)，满足A(x)=Ф(x)/p(x) B. 初始状态 C. p(x) D. G(p(x))中的序列
3. 一个LFSR的极小多项式为p(x)，其所生产的序列也都能由特征多项式为t(x)的LFSR产生，则gcd(p(x),t(x))=_________
A. p(x) B. t(x) C. 1 D. 次数大于1的某个g(x)，且不等于p(x)和t(x)
4. 下面哪个选项不是Golomb对伪随机周期序列提出的随机性公设_________
A. 在一个周期内0和1个数至多差1 B. 长为i的游程占游程总数的1/2i
C. 异相自相关函数为常数 D. 任意比特的下一比特不可预测
5. 哪些组合通常作为密钥流产生器的状态转移函数和输出转移函数______
A. 线性的φ和线性的ψ B. 线性的φ和非线性的ψ
C. 非线性的φ和线性的ψ D. 非线性的φ和非线性的ψ
三、判断：(正确的划”√”，错误的划”×”，以下同)
1. 在流密码中，只要被加密的明文长度小于密钥流序列的周期，就可以达到无条件安全了 （ ）
2. 只要LFSR产生的序列的周期足够大，就能够达到计算上安全的，可用于作为密钥流序列 （ ）
3. 流密码中如果第i个密钥比特与前i-1个明文有关则称为同步流密码 ( )
4. LFSR的初始状态对其产生序列的周期没有任何影响 ( )
5. 序列{ai}的生成函数为A(x)=Ф(x)/p(x)，p(x)的次数大于1，则必有G(p(x))中的一个序列，满足A(x)=x/p(x) ( )
6. LFSR产生的序列中有一条序列是m序列，则所有非0序列都是m序列（ ）
7. 钟控序列的线性复杂度是指产生钟控序列的密钥流产生器中包含的移位寄存器的总级数 （ ）
8. n级m序列中，存在两个0的n-1游程。 （ ）
9. m序列生成器产生的非0序列之间互相是移位关系。 ( )
10. 任何给定的GF(2)上的密钥流序列都可以用一个LFSR来生成 ( )
四、简答与计算
1. 试画出二元加法同步流密码的结构.
2. 如图所示的用有限状态自动机描述的密钥流产生器，请问哪部分是驱动部分，哪部分是非线性组合部分？或者说目前普遍采用的密钥流产生器中，哪部分一般采用线性函数，哪部分采用非线性的？
3. 已知一有限状态自动机的状态转移图如图所示，则当初始状态为s1，且输入字符序列为A1(1)A2(1)A1(1)A3(1)A3(1)A1(1)时，输出的状态序列和输出符号序列分别是什么？
4. *在线性反馈移位寄存器LFSR中，LFSR的结构图，特征多项式p(x)和递推式三者中任给一个，求另外两个，及产生序列的周期。
5. 已知一明文串为00011001，相应的密文串为10111110，密钥流序列由3级m序列生成，试破译之。
6. 使用一个n级m序列加密t(t>4n)比特消息U，如果敌手猜测出U的奇数位都是1，则敌手能否破译出该消息？如何破译？
7. 给出Geffe序列的结构，周期和线性复杂度
8. 给出钟控生成器的结构和周期
五、证明题
1. 试证定理2-2和定理2-4
2. 试证定理2.6 设{ai}∈G(p(x))，{ai}为m序列的充要条件是p(x)为本原多项式
3. n次不可约多项式p(x)的周期为r，试证A(x)=1/p(x)的充要条件是0的n－1游程出现在一个周期的最后n-1bit
4. 已知序列{ai}∈G(p(x))，同时也满足{ai}∈G(q(x))，已知p(x)=x7+x5+x3+x2+1, q(x)= x4+x3+x2+1, 试证{ai}为m序列。
5. 试证，对于特征多项式一样，而仅初始条件不同的两个m输出序列，对应位相加后所得的新的序列也是m序列，并且这个新的m序列与前两个m序列的特征多项式相同，相互之间满足移位关系
6. 试证，m序列的异相自相关函数为-1/T，T是序列的周期。
六、综合题
1. 一个LFSR的特征多项式p(x)是不可约多项式，该LFSR的状态转移图由若干个圈组成，试问(1)这些圈中包含的状态数目与该线性反馈移位寄存器的特征多项式的周期有何关系，(2)共有多少个圈，并给出说明。
2. 已知一序列的前10比特为0010001111
(1) 试用B-M算法求出产生该序列极小多项式和线性复杂度
(2) 给出产生该序列的LFSR的递推式、结构图和周期
(3) 破译该序列最少需要知道多少连续的密钥流比特
|
n |
a10 |
dn |
fn(x) |
ln |
m |
fm(x) |
|
0 |
||||||
|
1 |
||||||
|
2 |
||||||
|
3 |
||||||
|
4 |
||||||
|
5 |
||||||
|
6 |
||||||
|
7 |
||||||
|
8 |
||||||
|
9 |
||||||
|
10 |
答案
一、填空题
- 有无记忆性
- 2^n -1
- 101 110 1011101110111...周期为4
- 设{ai}∈G(p(x)),{ai}为m序列的充 要条件是p(x)为本原多项式
- 2^5-1 = 31
- 1和 -1/7（当0<=i<=2^n-2）
- 2
- 49 21
- 2
- 2^(n-i-2) 1 0
- 2n
- 256B
- 2
- 选择
四、简答与计算：
4.3. 已知一有限状态自动机的状态转移图如图所示，则当初始状态为s1，且输入字符序列为A1(1)A2(1)A1(1)A3(1)A3(1)A1(1)时，输出的状态序列和输出符号序列分别是什么？
解：根据有限状态机转移图有
- 输出的状态序列 s1, s2, s2, s3, s2, s1, s2
- 输出的符号序列 A1(2) A1(2) A2(2) A1(2) A3(2) A1(2)
五、证明题：
5.3 n次不可约多项式p(x)的周期为r，试证A(x)=1/p(x)的充要条件是0的n－1游程出现在一个周期的最后n-1bit
证：由于p(x)是不可约多项式，则由p(x)生成的非0序列的周期等于p(x)的周期r
由A(x)＝a1+a2x+…+arxr-1+xr(a1+a2x+…+arxr-1)+(xr)2(a1+a2x+…+arxr-1)+…
＝a1+a2x+…+arxr-1/(1-xr)＝a1+a2x+…+arxr-1/(xr-1)
于是A(x)=(a1+a2x+…+arxr-1)/(xr-1)＝1/p(x)
所以p(x) (a1+a2x+…+arxr-1)= xr+1
由于p(x)的次数为n，所以(a1+a2x+…+arxr-1)的最大次数为r-1-n，也就是说从xr-1-n+1开始系数都为0
即从xr-n到xr-1共n-1个系数都为0，由0的最大游程长度是n-1，所以0的n-1游程出现在一个周期的最后n-1bit
必要性：
如果0的n-1游程出现在最后n-1bit，我们考察p(x) (a1+a2x+…+arxr-1)＝φ(x) (xr-1)，其中φ(x)满足A(x)p(x)＝φ(x)，由于p(x)次数为n，而根据0的n-1游程出现在最后n-1bit 知(a1+a2x+…+arxr-1)的最大次数是
r-1-(n-1)，所以方程左边p(x) (a1+a2x+…+arxr-1)的次数为n+ r-1-(n-1)=r，所以方程右边φ(x)=1，即A(x)=1/p(x) #
六、综合题
6.2 已知一序列的前10比特为0010001111
(1) 试用B-M算法求出产生该序列极小多项式和线性复杂度
(2) 给出产生该序列的LFSR的递推式、结构图和周期
(3) 破译该序列最少需要知道多少连续的密钥流比特
解：(1) 产生该序列的极小多项式和线性复杂度分别是1+x+x4和4
|
n |
a10 |
dn |
fn(x) |
ln |
m |
fm(x) |
|
0 |
0 |
0 |
1 |
0 |
||
|
1 |
0 |
0 |
1 |
0 |
||
|
2 |
1 |
1 |
1 |
0 |
2 |
1 |
|
3 |
0 |
0 |
1-d2x2+1=1+x3 |
2+1=3 |
||
|
4 |
0 |
0 |
1+x3 |
3 |
||
|
5 |
0 |
1 |
1+x3 |
3 |
||
|
6 |
1 |
1 |
(1+x3)+x5-2(1)=1 |
3 |
6 |
1 |
|
7 |
1 |
1 |
1+ x6-2(1)=1+x4 |
4 |
||
|
8 |
1 |
0 |
1+x4+x7-6(1)=1+x+x4 |
4 |
||
|
9 |
1 |
0 |
1+x+x4 |
4 |
||
|
10 |
1+x+x4 |
4 |
(2)结构图、递推式和周期
递推式 ak+4=ak+3⊕ak
周期：由于是本原多项式，所以周期为24-1=15
（3）需要知道至少2x4=8个连续的密钥流比特