现代密码学杨波课后习题讲解课件

习题习题1第一章第一章2习题1.设仿射变换的加密是E11,23(m)≡11m+23(mod26)，对明文“THENATIONALSECURITYAGENCY”加密，并使用解密变换D11,23(c)≡11-1(c-23)(mod26)验证你的加密结果。解：明文用数字表示：m=[19741301981413011184220178192406413224]密文C=E11,23(m)≡11*m+23(mod26)=[24221510232472110231413151992724123111510191]=YWPKXYHVKXONPTJCHYBXLPKTB

习题1.设仿射变换的加密是E11,23(m)≡11m+3习题∵11*19≡1mod26(说明：求模逆元可采用第4章的“4.1.7欧几里得算法”，或者直接穷举1~25)对密文C进行解密：m’=D(C)≡19*(c-23)(mod26)=[19741301981413011184220178192406413224]=THENATIONALSECURITYAGENCY习题∵11*19≡1mod264习题2.设由仿射变换对一个明文加密得到的密文为edsgickxhuklzveqzvkxwkzukvcuh，又已知明文的前两个字符是“if”。对该密文解密。解：设加密变换为c=Ea,b(m)≡a*m+b(mod26)由题目可知明文前两个字为if，相应的密文为ed,即有：E(i)=e：4≡8a+b(mod26)E(f)=d：3≡5a+b(mod26)由上述两式，可求得a=9，b=10。

习题2.设由仿射变换对一个明文加密得到的密文为edsgi5习题因此，解密变换为

m=D(c)≡9-1(c-10)(mod26)

密文对应的数字表示为：c=[4318682102372010112521416252110232210252010212207]则明文为c=9-1(c-10)(mod26)=[85241420201317403197818197013100194072417]=ifyoucanreadthisthankateahcer习题因此，解密变换为6习题3.设多表代换密码中加密为：明文为：PLEASESEND……解密变换：习题3.设多表代换密码中加密为：7习题解：将明文分组：……将明文分组带入加密变换：可得密文：NQXBBTWBDCJJ……解密时，先将密文分组，再将密文分组带入解密变换：可证得明文习题解：将明文分组：8习题4.设多表代换密码

中，A是2×2矩阵，B

是0矩阵，又知明文“dont”被加密为“elni”，求矩阵A。解：设矩阵，dont=(3,14,13,19)elni=(4,11,13,8)解得：习题4.设多表代换密码9第二章流密码第二章流密码10知识点流密码：利用密钥k产生密钥流，明文与密钥流顺次对应加密线性反馈移位寄存器：产生密钥流

图2.1

GF(2)上的n级反馈移位寄存器知识点流密码：利用密钥k产生密钥流，明文与密钥流顺次对应加密11习题1.3级线性反馈移位寄存器在c3=1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。解：设反馈函数为f(a1,a2,a3)=a1⊕c2a2⊕c1a3当c1=0，c2=0时，f(a1,a2,a3)=a1，输出序列为101101…，周期为3。当c1=0，c2=1时，f(a1,a2,a3)=a1⊕a2，输出序列如下10111001011100…，周期为7。当c1=1，c2=0时，f(a1,a2,a3)=a1⊕a3，输出序列为10100111010011…，周期为7。当c1=1，c2=1时，f(a1,a2,a3)=a1⊕a2⊕a3，输出序列为10101010…，周期为2。习题1.3级线性反馈移位寄存器在12习题2．设n级线性反馈移位寄存器的特征多项式为

，初始状态为

，证明输出序列的周期等于

的阶。定义2.2设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。定理2.3若序列{ai}的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则{ai}的周期r|p。习题2．设n级线性反馈移位寄存器的特征多项式为，初13习题习题14习题3.设n=4,n=f(a1,a2,a3,a4)=a1⊕a4⊕1⊕a2a3，初始状态为(a1,a2,a3,a4)=(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。解：列出该非线性反馈移位寄存器的状态列表和输出列（如右图）：……输出序列为1101111011…，周期为5。f(a1,a2,a3,a4)输出(1,1,0,1)11(1,0,1,1)11(0,1,1,1)10(1,1,1,1)01(1,1,1,0)11(1,1,0,1)11….….….习题3.设n=4,n=f(a1,a2,a3,a4)=a115习题6.已知流密码的密文串1010110110和相应的明文串0100010001，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。解：由已知可得相应的密钥流序列为1010110110⊕0100010001=1110100111，又因为是3级线性反馈移位寄存器，可得以下方程：将值代入得:习题6.已知流密码的密文串1010110110和相应的明文16习题,由此可得密钥流的递推关系为：

习题,由此可得密钥流的递推关系为：17第三章分组密码体制第三章分组密码体制18习题2.证明DES的解密变换是加密变换的逆。明文分组、密钥加密阶段：初始置换、16轮变换、逆初始置换每轮迭代的结构和Feistel结构一样：习题2.证明DES的解密变换是加密变换的逆。每轮迭代19习题习题20习题3.

在

DES

的

ECB

模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组受到影响。然而在

CBC

模式中，将有错误传播。例如在图

3-11

中

C1

中的一个错误明显地将影响到

P1和

P2

的结果。(1)P2

后的分组是否受到影响?(2)

设加密前的明文分组

P1

中有

1

比特的错误，问这一错误将在多少个密文分组中传播?对接收者产生什么影响?ECB模式：每个明文组独立地以同一密钥加密CBC模式：加密算法的输入是当前明文组与前一密文组的异或习题3.在DES的ECB模式中，如果在密文分组中21习题习题22习题4.在8比特CFB模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远。CFB模式：每次只处理输入的j比特，将上一次的密文用作加密算法的输入以产生伪随机输出，该输出再与当前明文异或以产生当前密文。习题4.在8比特CFB模式中，如果在密文字符中出23习题习题24习题5.在实现IDEA时，最困难的部分是模216+1乘法运算。以下关系给出了实现模乘法的一种有效方法，其中a和b是两个n比特的非0整数。

，，注意：(ab

mod

2n)相当于ab的n个有效最低位，(ab

div

2n)是ab右移n位。IDEA：明文、分组、密钥、8轮迭代（不是传统的feistel）、输出变换习题5.在实现IDEA时，最困难的部分是模216+125习题习题26习题习题27习题习题28第四章公钥密码第四章公钥密码29习题1.证明以下关系：(1)

(2)

(3)（2）由，则存在整数k使a=b+kn，则b=a+(-k)n解：（1）设，由题意得，且存在整数，使得可得即证得习题1.证明以下关系：（2）由，则30习题2.证明以下关系：(1)

(2)

习题2.证明以下关系：31习题3.用Fermat定理求3201mod11Fermat定理：若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp。解：p=11，a=3，gcd（3,11）=1由Fermat定理，可知310≡1mod11，则(310)k≡1mod11

所以3201mod11=[(310)20×3]mod11=[((310)20mod11)×(3mod11)]mod11=3。习题3.用Fermat定理求3201mod1132习题4.

用推广的

Euclid

算法求

67mod119

的逆元。因此，Euclid算法（辗转相除法）推广的Euclid（P97）解：习题4.用推广的Euclid算法求67mod133习题5.

求gcd(4655,12075)。解：12075=2×4655+27654655=1×2765+18902765=1×1890+8751890=2×875+140875=6×140+35

140=4×35+0

所以gcd(4655,12075)=35。习题5.求gcd(4655,12075)。解：134习题6.求下列同余方程组（中国剩余定理）习题6.求下列同余方程组（中国剩余定理）35习题10.设通信双方使用RSA加密体制，接收方的公钥是(e,n)=(5,35)，接收到的密文是C=10，求明文M解：

(n)=35=5*7

(n)=

(5)*(7)=(=(5-1)*(7-1)=24因为d*e≡1mod

(n)，解得d=5M=cdmodn=105mod35=5RSA？密钥产生、加密、解密习题10.设通信双方使用RSA加密体制，接收方的公钥36习题13.

在

ElGamal

加密体制中，设素数

p=71，本原根

g=7，(1)如果接收方

B

的公开钥是

yB=3，发送方

A

选择的随机整数

k=2，求明文

M=30

所对应的密文。(2)如果

A

选择另一个随机整数

k，使得明文

M=30

加密后的密文是

C=(59,C2)，求

C2。Elgamal：y,p,g,x；密文对解：(1)C1≡gkmodp=