现代密码学-清华大学-杨波着+习题答案

NCUT密码学-习题与答案2010

（声明：非标准答案，仅供参考）

一、古典密码（1,2,4）

字母ABCDEFGHIJKLMNOPQRSTuVWXYZ

数字012345678910111213141516171819202122232425

I.设仿射变换的加密是En,23(m)=llm+23(mod26),对明文“THENATIONALSECURITY

AGENCY”加密，并使用解密变换Du.23(c月Li(c-23)(mod26)验证你的加密结果。

解：明文用数字表示：M=[19741301981413011184220178192406413224]

密文C=EII,23(M>1l*M+23(mod26)

=[24221510232472110231413151992724123111510191]

=YWPKXYHVKXONPTJCHYBXLPKTB

V11*19=1mod26(说明：求模逆可采用第4章的“4.1.6欧几里得算法“，或者直接穷举1~25)

・••解密变换为D(c)三19*(c-23)三19c+5(mod26)

对密文C进行解密：

M'=D(C>19C+5(mod26)

=[19741301981413011184220178192406413224]

=THENATIONALSECURITYAGENCY

2.设由仿射变换对一个明文加密得到的密文为cdsgickxhuklzvcqzvkxwkzukvcuh.乂已知明文

的前两个字符是对该密文解密。

~设解密变换为m=D(c)三a*c+b(mod26)

由题目可知密文ed解密后为if,即有：

D(e)=i：8=4a+b(mod26)D(d)=f：5三3a+b(mod26)

由上述两式，可求得a=3,b=220

因此，解密变换为m=D(c户3c+22(mod26)

密文用数字表示为：

c=[4318682102372010112521416252110232210252010212207]

则明文为m=3*c+22(mod26)

=[85241420201317403197818197013100194072417]

=ifyoucanreadthisthankateahcer

4.设多表代换密码Ci三AM-B(mod26)中，A是2x2矩阵，B是0矩阵，又知明文“donl”

被加密为“elni”，求矩阵A。

解：dont=(3,14,13,19)=>elni=(4,11,13,8)

[ab

设^=|[cd\,

则有.[41[f3]f131JW[131

IHillIIMII14|(M2^),JiIMIcd\l19|(mod26)

[1013]

可求得/=|[923||

第1页

NCUT密码学-习题与答案2010

二、流密码(1,3,4)

1.3级线性反馈移位寄存器在C3=l时可有4种线性反馈函数，设其初始状态为

(31尸2尸3)二(1,0,1),求各线性反馈函数的输出序列及周期。

解：设反馈函数为f(ai,a2,a3)=aiCc2a2㊉cia3

当cl=0,c2=0时，f(ai,32,33)=ai,输出序列为101101...,周期为3。

当cl=0,c2=l时，f(ai,a2,a3)=ai㊉az,输出序列如下10111001011100...,周期为7。

当cl=l,c2=0时,f(ai,a2,a3)=ai>a3,输出序列为当100111010011...,周期为7。

当cl=l,c2=l时，f(ai,a2,a3)=ai㊉az㊉a3,输出序列为10101010…，周期为2。

3.设n=4,f(ai,a2,a3,a4)=ai©a4㊉1㊉a2a3,初始状态为(ai,a2,a3,a4)=(l,l,0,l),求此非线性

反馈移位寄存器的输出序列及周期。

解：列出该非线性反馈移位寄存器的状态列表和输出列表:

状态(ai,a2,a3,a4)^31,92,33,34)输出

(1,1,0,1)11

(lAlzl)11

(0,1,1」)10

(1,1,1,1)01

(1,1,1,0)11

(1,1,0,1)11

••••••

因此，输出序列为1101111011...»周期为5。

4.密钥流由m=2s级的LFSR产生，前m+2个比特是(01)s+i,即s+1个01,请问第m+3个

比特有无可能是1,为什么？

解：根据题目条件，可知初始状态so为:

5o=\a\,CH,L,am-\,am)=(0,1,...,0,1)注：s个01

设该LFSR的输出序列满足如下递推关系：

CH=c\am^k-\+ciam-\+LCM,421

则第m+1,m+2个比特为：

s

。,计1=而”|+C2Om-\+LCmfll=£C2j-]=0

j=l

s

Cbt，2—iQm-i-C2(dnLcmU2=EC2j=\

而第m+3比特应为：

4m+3=C\am^l+Cia,^\+C34m+CAdm-X+L+Cm-Q+CmCh

X

=ci-1+C2,0+(73-1+(74,0+LL+c«-i-1h£C3-1=0

』=i

Cm,0

即第m+3比特为0,因此不可能为1.M的散歹ij值相同。

第2页

NCUT密码学-习题与答案2010

三、分组密码(1,2,3,4)

1.(1)设M'是M的逐比特取朴，证明在DES中，如果对明文分组和密文分组都逐比特取补，

那么得到的密文也是原密文的逐比特取补，即

如果Y=DESK(X),那么Y'=DESK(X')

提示：对任意两个长度相等的比特串A和B,证明(A㊉B)=A®B°

(i)容易验证，在DES中所有的置换操作，包括初始置换IP、逆初始置换IP-1、选择扩展算

法E、置换运算P以及置换选择PC1、置换选择PC2,都满足如下性质：

如果N=PO(M),则N，=PO(M'),其中PO是某种置换操作

即有(PO(M))=PO(W)

(ii)容易验证，密钥生成过程中的左循环移位LS满足如下性质：

如果N=LS(M),那么N'=LS(M'),

即有(LS(M))=LS(M,)

结合(1)可知，如果记子密钥为(Ki,…,K16),K为初始密钥，KG为密钥生成算法，则有

如下性质：

如果(Ki,...,Ki6)=KG(K),那么(Ki,,...,Ki6')=KG(K,)

(iii)对于任意两个比特a和b,有(a㊉b)'=a^b㊉l=(a㊉l)^b=a'㊉b(=a©(bel)=aeb'),

因此对任意两个长度相等的比特串A和B,有(A㊉B)=A'㊉B=A㊉B'成立。

[IL1—Ri-\

(iv)DES的轮变换为7z其中轮函数F可写为

F(R、K)=P(S(E(R)SK))。因此有如下推理：

Y=DESK(¥)=『=DESK(X')

OR,=LI㊉F(R,T,K)=>R,=L-+尸(RT,K)根据(i)(ii)

O(L-I'根据(iii)

QF(R,T,K)=F(RfK)

oP(S(E(RT)♦K))=P(S)㊉K.))

oE(R-i)㊉K=E(R二)㊉K

根据(位)可知E(R.\)㊉K=(E(RL\)ek,)=(£(/?.-1))㊉Ki

o(E(R-))­㊉K=E(RT)㊉K

o(£(/?,-1))•=E(R-)由⑴知此式成立

(2)对DES进行穷举搜索攻击时，需要在由256个密钥构成的密钥空间进行。能否根据(1)

的结论减少进行穷搜索攻击时所用的密钥空间。

解：(1)根据取补的性质，密钥空间K可分成两部分K1/2和IC1/2,即K=Kl/2UK，/2

对于任意一个k£Ki/2,它的取补k'wlCi/2：对于任意一个k£K、/2,它的取补k'e

K1/2O即，K1/2和ri/2是一一一对应的；它们的空间大小都是256/2=255。

(2)选择明文攻击时，假设有Ek0(x)=y,其中x、y分别为明文和密文，E为DES加密算法,

ko为真实的密钥。

第3页

NCUT密码学-习题与答案2010

么解密后的P1跟加密前一样，同样有一个比特的错误，而对于Gz能够解密得到无

错误的明文。

4.在8比特CFB模式中，如果在密文字符中出现1比特的错误，问该错误能传播多远。

解：该错误将传播到后面的|[(64+8-1)/81]=8个单元，共9个单元解密得到错误的明文。

第5页

NCUT密码学-习题与答案2010

四、公钥密码

1.3.用Fermat定理求3zoimod11。

解：对于模运算，有结论~(axb)modn=[(amodn)x(bmodn)]modn

由Fennat定理，可知3庐1mod11,因此有(3io)k=1mod11

所以32OImod11=[(3IO)2OX3]mod11=[((310)20mod1l)x(3mod11)]mod11=3。

Fermat定理：若p是素数，a是正整数且gcd(a,p)-l,贝Ua-=1mud

若gcd(a,p)=l,则a"。)三1modp。

4.用推广的Euclid算法求67mod119的逆元。

川十.qg14V

-11910

〜670/

1521-1

115-I2

374-7

21-916(注：1=119x(-9)+67x16)

所以67'mod119=16

5.求gcd(4655,12075)。

解：12075=2x4655+2765

4655=1x2765+1890

2765=1x1890+875

1890=2x875+140

875=6x140+35

140=4x35+0所以gcd(4655,12075)=35o

x=2mod3

6.求解下列同余方程组｛x三lmod5。

Ix=1mod7

解：根据中国剩余定理求解该同余方程组,

记ai=2,a2=l,as=l,mi=3,m2=5,ms=7,M=mixm2xm3=105,

Mi=M/mi=35,Mi-imodmi=35-imod3=2,

M2=M/lT12=21,M2-1modm2=2Limod5=1,

M3=M/m3=15,M3-1modm3=15-imod7=1

所以方程组的解为x=(MiMi-tai+M2M2-ia2+M3M3-ia3)modM

=(35x2x2+21x|xi+i5xixi)mod)05

=176mod105=71mod105

10.设通信双方使用RSA加密体制，接收方的公开钥是(e,n)=(5,35),接收到的密文是C=10,

求明文M

第6页

NCUT密码学-习题与答案2010

解：n=35->p=5.q=7

4>(n)=(p-l)(q-1)=24

d三e-imod4)(n)=5-imod24=5mod24….(因为5x5=1mod24)

所以，明文M三Cdmodn三105mod35三5

快速指数算法求模幕105mod35：

5=4+1=(101)2bi=0,d<-d*d

bi-101bi=0,d<-d*d*底

d110305

12.设RSA加密体制的公开钥是(e,n)=(77,2是).

(I)用重复平方法加密明文160,得中间结果为:

k248163264727677

160mod22118519116351203511821723

若敌手得到以上中间结果就很容易分解n,问敌手如何分解n?

(2)求解密密钥do

解：(1)由16016三16064mod221,可知(16064-16016)mod221=0

即16016(16048—1)mod221=0,从而有16048=1mod221«

由Euler定埋及定埋4-7,猜测：

ordn(160)|48且48|—n),即存在整数k满足-n)=48k

由。(n)的定义可知，4)(n)比n略小。

而当取k=4时，Mn)=192为<221且与221最接近，因此猜测。(n)=192。

由。(n)=(p-l)(q-l),n=pq,可知p+q=n-0(n)+I=221-192+I=30

所以p、q为一元二次方程X2-30X+221=0的两人根，求得为13、17。

或:p-q=sqrt((p+q)2-4n),从而p=((p+q)+(p-q))/2,q=((p+q)-(p-q))/2

所以，可得n的分解为：n=221=13x17

(2)解密密钥d为:dse-imod<|>(n)=77-1mod192=5

(V77x5-192x2=1)

13.在ElGamal加密体制中，设素数p=71,本原根g=7,

⑴如果接收方B的公开钥是yB=3,发送方A选择的随机整数k=2,求明文M=30所对应的密

文。

(2)如果A选择另一个随机整数匕使得明文M=30加密后的密文是C=(59,C2),求C1.

解：(1)Ci三gkmodp=72mod71=49,C2=ynkMmodp=(32x30)mod71=57

所以密文为C=(Ci,Ca)=(49,57)»

(2)由7kmod71=59,穷举k可得k=3。

所以C2=(3kx30)mod71=(33x30)mod71=29o

18.椭圆曲线Eu(l,6)表示y三x+x+6mod11,求其上的所有点。

第7双

NCUT密码学-习题与答案2010

解:

X012345678910

X3+X+6mod1168538484974

是否为mod11

NoNoyesyesNoyesNoyesyesNoyes

的

y4,75,62,92,93,82,9

所以，Ell(1,6)上点为{O,(2,4),(2,7),(3,5),(3,6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(10,2),(10,9))

人要确定c是否是一个模P的平方剩余，可以用Euler准则来判断，即

如果P是一个奇素数，则c是模p的平方剩余当且仅当c<p,>/2=lmodp.

：当p三3mod4时，如果c是一个模p的平方剩余，则士cmodp,

即c"W2和p-c切叱，就是c的两个模p的平方根。

19.已知点G=(2,7)在椭圆曲线En(l,6)±,求2G和3G。

解：a=l,b=6,p=l1,y2三X3+X+6mod11

,:2G=G+G,

L=(3X22+1)/(2X7)mod11=13/14mod11=2/3mod11=8(V3-imod11=4)

x3=(82-2-2)mod11=5,y3=[8(2-5)-7]mod11=2

:.2G=(5,2)

V3G=2G+G=(5,2)+(2,7),

L=(7-2)/(2-5)mod11=5/(-3)mod11=5/8mod11=5*7mod11=2(V8*7=1mod11)

X3=(22-5-2)mod11=(-3)mod11=8

y3=[2(5-8)-2]mod11=(-8)mod11=3

:.3G=(8,3)

2曲性卜U的MS工运■

出尸=（.小>）0=区,小）后£则

20.利用椭圆曲线实现ElGamal密码体制,设椭圆曲线是En(l,6),生成元G=(2,7),接收方A

的秘密钥nA=7a

(1)求A的公开钥PA。

(2)发送方B欲发送消息Pm=(10,9),选择随机数k=3,求密文Cm。

(3)显示接收方A从密文Cm恢复消息Pm的过程。

解：(1)A的公开钥PA=nAG=7G=(7,2)

(2)Ci=kG=3G=(8,3)

C2=Pm+kPA=(10,9)+3(7,2)=(10,9)+(3,5)=(10,2)

所以密文Cm={Ci,C2)={(8,3),(10,2)}

(3)解密过程为

C2-nACi=(Pm+kPA)-nA(kG)=(10,2)-7(8,3)=(10,9)=Pm

第8页

NCUT密码学-习题与答案2010

五、消息认证与杂凑函数

1.6.13节的数据认证算法是由CBC模式的DES定义的，其中初始向量取为0,试说明使用CFB

模式也可获得相同结果。

如果要使CFB模式输出结果和CBC模式的相同，那就要选择适当参数和输入。

假设消息为M=DID2...DN,则按如下思路考虑：

(I)CBC中DES加密和法输入输出都为64位，所以CFB中的参数j应取64。此时的CFB

模式变为：

（图3）

(2)比较图1和图2中开始几个分组的处理，考虑DES加密的输入和输出，可知,

IV->D1,P1->D2,...

(3)CBC中最后一个DES加密的输出为消息认证符，即ON=EK(DNEON-I),因此在CFB中,

应取PM为Z64(64比特都为0的分组)，这样有CM=EK(CM-I)®ZM=EK(CM-I)O此时，应取PM-I=

DNO

综上可知：对于消息M=DD2...DN,如果采用DES/CFB的数据认证算法，那么，当其参数

取如下值时，

参数j=64,参数IV=DI,输入消息M'=D2D3...DNZ64

其输出与采用DES/CBC的数据认证算法的输出相同。

第9页

NCUT密码学-习题与答案2010

2.有很多散列函数是由CBC模式的分组加密技术构造的，其中的密钥取为消息分组。例如将

消息M分成分组Ho=初值，迭代关系为Hi=EMi(Hi-i)eHi-i(i=l,2,...,N),杂凑值

取为HN,其中E是分组加密算法。

(1)设E为DES,我们知道如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原

密文的逐比特取补，即如果Y=DESK(X),那么Y'=DESK(X')。利用这一结论证明在上述散列函

数中可对消息进行修改但却保持杂凑值不变。

(2)若迭代关系改为HkEHM(MI)㊉Mi,证明仍可对其进行上述攻击。

解：(1)Hi