第二章流密码 —— 现代密码学（杨波）课后题答案解析-Toy模板网

这篇具有很好参考价值的文章主要介绍了第二章流密码 —— 现代密码学（杨波）课后题答案解析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第二章作业参考答案

1．3级线性反馈移位寄存器在c₃＝1时可有4种线性反馈函数，设其初始状态为(a₁,a₂,a₃)=(1,0,1)，求各线性反馈函数的输出序列及周期。

解：此时线性反馈函数可表示为f(a₁,a₂,a₃)=a₁Åc₂a₂Åc₁a₃

当c₁＝0，c₂＝0时，f(a₁,a₂,a₃)=a₁Åc₂a₂Åc₁a₃＝a₁，

输出序列为101101…，周期＝3

当c₁＝0，c₂＝1时，f(a₁,a₂,a₃)=a₁Åc₂a₂Åc₁a₃＝a₁Åa₂，

输出序列为10111001011100…，周期＝7

当c₁＝1，c₂＝0时，f(a₁,a₂,a₃)=a₁Åc₂a₂Åc₁a₃＝a₁Åa₃，

输出序列为10100111010011…，周期＝7

当c₁＝1，c₂＝1时，f(a₁,a₂,a₃)=a₁Åc₂a₂Åc₁a₃＝a₁Åa₂Åa₃，

有输出序列为1010…，周期＝2

2．设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a₁,a₂, …,a_n_-1,a_n)=(00…01)，证明输出序列的周期等于p(x)的阶

证：设p(x)的阶为p，由定理2-3，由r|p，所以r£p

设A(x)为序列{a_i}的生成函数，并设序列{a_i}的周期为r，则显然有A(x)p(x)＝f(x)

又A(x)＝a₁+a₂x+…+a_rx^r^-1+x^r(a₁+a₂x+…+a_rx^r^-1)+(x^r)²(a₁+a₂x+…+a_rx^r^-1)+…

＝a₁+a₂x+…+a_rx^r^-1/(1-x^r)＝a₁+a₂x+…+a_rx^r^-1/(x^r-1)

于是A(x)=(a₁+a₂x+…+a_rx^r^-1)/(x^r-1)＝f(x)/p(x)

又(a₁,a₂, …,a_n_-1,a_n)=(00…01)

所以p(x)(a_nxⁿ^-1+…+a_rx^r^-1)=f(x)(x^r-1) 即 p(x)xⁿ^-1(a_n+…+a_rx^r^-ⁿ)=f(x)(x^r-1)

由于xⁿ^-1不能整除x^r-1，所以必有xⁿ^-1|f(x)，而f(x)的次数小于n，所以必有f(x)＝xⁿ^-1

所以必有p(x)|(x^r-1)，由p(x)的阶的定义知，阶p£r

综上所述：p＝r #

3．设n＝4，f(a₁,a₂,a₃,a₄)=a₁Åa₄Å1Åa₂a₃，初始状态为(a₁,a₂,a₃,a₄)＝(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。

解：由反馈函数和初始状态得状态输出表为

(a₄a₃a₂a₁) 输出 (a₄a₃a₂a₁) 输出

1 0 1 1 1 1 1 1 1 1

1 1 0 1 1 0 1 1 1 1

1 1 1 0 0 1 0 1 1 1（回到初始状态）

所以此反馈序列输出为：11011…周期为5

4．设密钥流是由m＝2s级LFSR产生，其前m+2个比特是(01)^s⁺¹，即s＋1个01。问第m+3个比特有无可能是1，为什么？

解：不能是1。

可通过状态考察的方法证明以上结论。

首先m级LFSR的状态是一个m维的向量，则前m个比特构成一个状态S₀，可表示为(01)^s，

第m＋1个比特是0，所以S₀的下一个状态是S₁＝(10)^s，

第m＋2个比特是1，所以S₁的下一个状态是S₂＝(01)^s＝S₀，回到状态S₀，

所以下一个状态应是S₃=S₁＝(10)^s，也即第m+3个比特应该为0。

5．设密钥流是由n级LFSR产生，其周期为2ⁿ－1，i是任一正整数，在密钥流中考虑以下比特对

(S_i, S_i₊₁), (S_i₊₁, S_i₊₂), …, (S_i₊₂ⁿ_－3, S_i₊₂ⁿ_－2), (S_i₊₂ⁿ_－2, S_i₊₂ⁿ_－1),

问有多少形如(S_j, S_j₊₁)＝(1,1)的比特对？证明你的结论。

答：共有2^(n-2)

证明：

证明方法一：由于产生的密钥流周期为2ⁿ－1，且LFSR的级数为n，所以是m序列

以上比特对刚好是1个周期上，两两相邻的所有比特对，其中等于(1,1)的比特对包含在所有大于等于2的1游程中。由m序列的性质，所有长为i的1游程(1£ i £n-2)有2ⁿ^-ⁱ^-1/2个，没有长为n－1的1游程，有1个长为n的1游程。

长为i (i>1)的1游程可以产生i-1个(1,1)比特对，

所以共有(1,1)比特对的数目N＝2ⁿ^-2-2×(2－1)＋2ⁿ^-3-2×(3－1)＋…＋2ⁿ^-i-2×(i－1)＋…＋2ⁿ^-(ⁿ^－2)－2×(n－2－1)＋n－1＝＋n－1＝2^(n-2)

证明方法2：考察形如11*…*的状态的数目，共有2^(n-2)个

6．已知流密码得密文串为1010110110和相应明文串0100010001，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。

解：由二元加法流密码的加密算法可知，将密文串和相应的明文串对应位模2加可得连续的密钥流比特为1110100111

设该三级线性反馈移位寄存器的反馈函数为f(a₁,a₂,a₃)=c₃a₁Åc₂a₂Åc₁a₃

取其前6比特可建立如下方程

(a₄a₅a₆)＝(c₃,c₂,c₁)，

即(c₃,c₂,c₁)＝(a₄a₅a₆)＝(0 1 0) =(0 1 0) =(1 0 1)

所以f(a₁,a₂,a₃)=a₁Åa₃，即流密码的递推关系式为a_i₊₃=a_i₊₂Åa_i

7．若GF(2)上的二元加法流密码的密钥生成器是n级线性反馈移位寄存器，产生的密钥是m序列。2.5节已知，敌手若知道一段长为2n的明密文对就可破译密钥流生成器。如果敌手仅知道长为2n－2的明密文对，问如何破译密钥流生成器。

解：破译n－LFSR所产生的m序列，需要2n个连续比特，现在仅有2n－2个连续的密钥比特(由长为2n－2的明密文对逐位异或得到)，因此需要猜测后两个比特。这有00，01，10，11四种情况，对这些情况按下式逐一试破译

(a_n+₁a_n+₂..a₂_n)＝(c_nc_n_-1..c₁) =(c_nc_n_-1..c₁) X

首先验证矩阵X的可逆性，如果不可逆则可直接排除此情况

其次对于可逆的情况，求解出(c_nc_n_-1..c₁)，然后验证多项式p(x)=1+c₁x+…+c_nxⁿ是否是本原多项式，如果是，则是一解。

结果可能会多余1个。

8.设J-K触发器中{a_k}和{b_k}分别为3级和4级m序列，且

{a_k}＝11101001110100…

{b_k}＝001011011011000 001011011011000…

求输出序列{c_k}及周期。

解：由于gcd(3，4)=1且a₀＋b₀＝1所以序列{c_k}的周期为(2³-1)(2⁴-1)=105

又由J-K触发器序列的递推式c_k=( a_k+b_k+1) )c_k_-1+a_k，令c_-1=0可得输出序列为：

{c_k}=11001001…

9．设基本钟控序列产生器中{a_k}和{b_k}分别为2级和3级m序列，且

{a_k}＝101101…

{b_k}＝10011011001101…

求输出序列{c_k}及周期。

解：序列{a_k}的周期p₁＝2²－1＝3，序列{b_k}的周期p₂＝2³－1＝7，w₁＝a₀＋a₁＋a₂＝2

而gcd(w₁, p₂)=1。所以序列{c_k}的周期p＝p₁p₂＝3×7＝21

记LFSR2(产生序列{b_k})的状态向量为σ_k，则σ₀＝(100)，在LFSR1(产生序列{a_k})的控制下，状态转移为：

{a_k} 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1

(100),(001),(001),(011),(110),(110),(101),(011),(011),(110),(100),(100),(001),(011),(011),(110)

1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1

{a_k} 1 0 1 1 0 1 1 0 1

(101),(101),(011),(110),(110),(100),(001), (001),(011)

1 1 0 1 1 1 0 0 0

所以输出序列为100011100111000111011 1000…

复习题&&答案

4.3. 已知一有限状态自动机的状态转移图如图所示，则当初始状态为s₁，且输入字符序列为A₁⁽¹⁾A₂⁽¹⁾A₁⁽¹⁾A₃⁽¹⁾A₃⁽¹⁾A₁⁽¹⁾时，输出的状态序列和输出符号序列分别是什么？

解：根据有限状态机转移图有

(1) 输出的状态序列 s₁, s₂, s₂, s₃, s₂, s₁, s₂

(2) 输出的符号序列 A₁⁽²⁾A₁⁽²⁾ A₂⁽²⁾ A₁⁽²⁾ A₃⁽²⁾A₁⁽²⁾

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)＝a₁+a₂x+…+a_rx^r^-1+x^r(a₁+a₂x+…+a_rx^r^-1)+(x^r)²(a₁+a₂x+…+a_rx^r^-1)+…

＝a₁+a₂x+…+a_rx^r^-1/(1-x^r)＝a₁+a₂x+…+a_rx^r^-1/(x^r-1)

于是A(x)=(a₁+a₂x+…+a_rx^r^-1)/(x^r-1)＝1/p(x)

所以p(x) (a₁+a₂x+…+a_rx^r^-1)= x^r+1

由于p(x)的次数为n，所以(a₁+a₂x+…+a_rx^r^-1)的最大次数为r-1-n，也就是说从x^r^-1-ⁿ⁺¹开始系数都为0

即从x^r^-ⁿ到x^r^-1共n-1个系数都为0，由0的最大游程长度是n-1，所以0的n-1游程出现在一个周期的最后n-1bit

必要性：

如果0的n-1游程出现在最后n-1bit，我们考察p(x) (a₁+a₂x+…+a_rx^r^-1)＝f(x) (x^r-1)，其中f(x)满足A(x)p(x)＝f(x)，由于p(x)次数为n，而根据0的n-1游程出现在最后n-1bit 知(a₁+a₂x+…+a_rx^r^-1)的最大次数是

r-1-(n-1)，所以方程左边p(x) (a₁+a₂x+…+a_rx^r^-1)的次数为n+ r-1-(n-1)=r，所以方程右边f(x)=1，即A(x)=1/p(x) #

6.2 已知一序列的前10比特为0010001111

(1) 试用B-M算法求出产生该序列极小多项式和线性复杂度

(2) 给出产生该序列的LFSR的递推式、结构图和周期

(3) 破译该序列最少需要知道多少连续的密钥流比特

解：(1) 产生该序列的极小多项式和线性复杂度分别是1+x+x⁴和4

n	a¹⁰	d_n	f_n(x)	l_n	m	f_m(x)
0	0	0	1	0
1	0	0	1	0
2	1	1	1	0	2	1
3	0	0	1-d₂x²⁺¹=1+x³	2+1=3
4	0	0	1+x³	3
5	0	1	1+x³	3
6	1	1	(1+x³)+x^5-2(1)=1	3	6	1
7	1	1	1+ x^6-2(1)=1+x⁴	4
8	1	0	1+x⁴+x^7-6(1)=1+x+x⁴	4
9	1	0	1+x+x⁴	4
10			1+x+x⁴	4

(2)结构图、递推式和周期

递推式 a_k₊₄=a_k₊₃Åa_k

周期：由于是本原多项式，所以周期为2⁴-1=15

(3) 需要知道至少2x4=8个连续的密钥流比特文章来源地址https://www.toymoban.com/news/detail-746129.html

到了这里，关于第二章流密码 —— 现代密码学（杨波）课后题答案解析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

第二章流密码 —— 现代密码学（杨波）课后题答案解析

第二章作业参考答案

复习题&&答案

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

第二章 流密码 —— 现代密码学（杨波）课后题答案解析

第二章作业参考答案

复习题&&答案

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2

第二章流密码 —— 现代密码学（杨波）课后题答案解析