(2025年)应用密码学序列密码体制习题参考答案

(2025年)应用密码学序列密码体制习题参考答案1.已知8级线性反馈移位寄存器（LFSR）的特征多项式为f(解答：LFSR的周期由其特征多项式的阶决定。首先需验证f(x)是否为既约多项式。通过试除法，检查f验证是否有一次因式：f(0)验证是否有二次因式：二次既约多项式为+x+1，计算f(x)mod(+x+1)。令≡类似地，验证三次及以上因式（过程略），确认f(接下来计算f(x)的阶ord(f(x))，即最小正整数T使得f(x计算modf(x)：利用递推关系=++x同理，modf(x)≠q12.给定二进制序列s=1,0,解答：B-M算法通过迭代构造连接多项式(x)，目标是找到最小的L使得s满足线性递推关系初始化：(x)=1，L=0，迭代过程：n=0：误差=·(0)=1·1=n=1：误差=+=0+0·1n=2：误差=++=1+0·n=3：误差=++=1+0·1+n=4：误差=+++=0+0·1+1·1n=5：误差=++=0+1·0+1·1=n=6：误差=++++=1+0·0+1·n=7：误差=++++=0+0·1+0·n=8：误差=+++++=0+0·0+0n=9：误差=++++=验证该多项式是否能提供原序列：递推关系=+=++=修正后，正确极小多项式应为1+x+3.设布尔函数f(解答：（1）代数次数：布尔函数的代数次数为各单项式的最高次数。,,（2）相关免疫阶：k阶相关免疫要求对于任意1≤t≤k，任意t个变元的子集S，f与S中变元的和（模2）统计独立，即计算单变元（t=1）的相关系数：对：固定=0，f=0++0固定=1，f=1·++1·+1++=++由于Pr[f取(0,0,0):0+0+0+0+0+0=0→f=0(0,0,1):0+0+0+0+0+1=1→f=1(0,1,0):0+0+0+0+1+0=1→f=1(0,1,1):0+1+0+0+1+1=1→f=1(1,0,0):0+0+0+1+0+0=1→f=1(1,0,1):0+0+1+1+0+1=1→f=1(1,1,0):1+0+0+1+1+0=1→f=1(1,1,1):1+1+1+1+1+1=3≡1mod2→f=1故全局Pr[f=0]=1/（3）扩散性：扩散要求输入变元的改变尽可能影响输出的多个位。对于3变元函数，若改变任意一个输入位，输出变化的概率应接近1/2。例如，改变从0到1，输入(0,0,0)→(1,0,0)，f从0→1（变化）；输入(0,0,1)→(1,0,1)，f从1→1（不变）；输入(0,1,0)→(1,1,0)，f从1→1（不变）；输入(0,1,1)→(1,1,1)，f从1→1（不变）。变化概率为1/4，低于1/2，故扩散性较弱。4.某序列密码方案采用两个5级LFSR（LFSR1和LFSR2）通过模2加（异或）提供密钥流=⊕，其中LFSR1的特征多项式为(x)解答：（1）安全性分析：周期：密钥流周期为LFSR1和LFSR2周期的最小公倍数lc线性复杂度：异或组合的线性复杂度L=相关性：由于异或为线性操作，密钥流的统计特性可能继承LFSR的弱点（如m序列的良好自相关，但异或后可能引入新的相关性）。例如，若已知LFSR1的输出，可直接异或得到LFSR2的输出，反之亦然，导致已知明文攻击可行。（2）改进建议：引入非线性组合：将异或替换为非线性函数（如模2加后通过S盒混淆，或使用乘法、逻辑与等非线性操作），提高线性复杂度和抗相关攻击能力。增加LFSR级数：使用更多LFSR（如3个或以上），或采用不同长度的LFSR（如8级和13级），增大周期和线性复杂度。引入记忆部件：在组合函数中加入记忆（如反馈移位寄存器的状态作为输入），使密钥流提供具有非线性动态特性，破坏线性结构。定期更新密钥：缩短密钥流的使用周期，避免长序列泄露统计特性。5.证明：若序列密码的密钥流满足H(,,…证明：完善保密要求对任意明文m和密文c，有Pr由序列密码加密规则=⊕，得=⊕。因此，已知密文c和明文m，可恢复密钥流z；反之，已知密文c和密钥流z，可恢复明文