現(xiàn)代密碼學(xué)-清華大學(xué)-楊波著+習(xí)題答案

NCUT密碼學(xué)-習(xí)題與答案2010

（聲明：非標(biāo)準(zhǔn)答案，僅供參考）

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

字母ABCDEFGHIJKLMNOPQRSTuVWXYZ

數(shù)字012345678910111213141516171819202122232425

I.設(shè)仿射變換的加密是En,23(m)=llm+23(mod26),對明文“THENATIONALSECURITY

AGENCY”加密，并使用解密變換Du.23(c月Li(c-23)(mod26)驗證你的加密結(jié)果。

解：明文用數(shù)字表示：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.設(shè)由仿射變換對一個明文加密得到的密文為cdsgickxhuklzvcqzvkxwkzukvcuh.乂已知明文

的前兩個字符是對該密文解密。

~設(shè)解密變換為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)

密文用數(shù)字表示為：

c=[4318682102372010112521416252110232210252010212207]

則明文為m=3*c+22(mod26)

=[85241420201317403197818197013100194072417]

=ifyoucanreadthisthankateahcer

4.設(shè)多表代換密碼Ci三AM-B(mod26)中，A是2x2矩陣，B是0矩陣，又知明文“donl”

被加密為“elni”，求矩陣A。

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

[ab

設(shè)^=|[cd\,

則有.[41[f3]f131JW[131

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

[1013]

可求得/=|[923||

第1頁

NCUT密碼學(xué)-習(xí)題與答案2010

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

1.3級線性反饋移位寄存器在C3=l時可有4種線性反饋函數(shù)，設(shè)其初始狀態(tài)為

(31尸2尸3)二(1,0,1),求各線性反饋函數(shù)的輸出序列及周期。

解：設(shè)反饋函數(shù)為f(ai,a2,a3)=aiCc2a2十cia3

當(dāng)cl=0,c2=0時，f(ai,32,33)=ai,輸出序列為101101...,周期為3。

當(dāng)cl=0,c2=l時，f(ai,a2,a3)=ai十a(chǎn)z,輸出序列如下10111001011100...,周期為7。

當(dāng)cl=l,c2=0時,f(ai,a2,a3)=ai>a3,輸出序列為當(dāng)100111010011...,周期為7。

當(dāng)cl=l,c2=l時，f(ai,a2,a3)=ai十a(chǎn)z十a(chǎn)3,輸出序列為10101010…，周期為2。

3.設(shè)n=4,f(ai,a2,a3,a4)=ai?a4十1十a(chǎn)2a3,初始狀態(tài)為(ai,a2,a3,a4)=(l,l,0,l),求此非線性

反饋移位寄存器的輸出序列及周期。

解：列出該非線性反饋移位寄存器的狀態(tài)列表和輸出列表:

狀態(tài)(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產(chǎn)生，前m+2個比特是(01)s+i,即s+1個01,請問第m+3個

比特有無可能是1,為什么？

解：根據(jù)題目條件，可知初始狀態(tài)so為:

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

設(shè)該LFSR的輸出序列滿足如下遞推關(guān)系：

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比特應(yīng)為：

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密碼學(xué)-習(xí)題與答案2010

三、分組密碼(1,2,3,4)

1.(1)設(shè)M'是M的逐比特取樸，證明在DES中，如果對明文分組和密文分組都逐比特取補，

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

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

提示：對任意兩個長度相等的比特串A和B,證明(A十B)=A?B°

(i)容易驗證，在DES中所有的置換操作，包括初始置換IP、逆初始置換IP-1、選擇擴展算

法E、置換運算P以及置換選擇PC1、置換選擇PC2,都滿足如下性質(zhì)：

如果N=PO(M),則N，=PO(M'),其中PO是某種置換操作

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

(ii)容易驗證，密鑰生成過程中的左循環(huán)移位LS滿足如下性質(zhì)：

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

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

結(jié)合(1)可知，如果記子密鑰為(Ki,…,K16),K為初始密鑰，KG為密鑰生成算法，則有

如下性質(zhì)：

如果(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其中輪函數(shù)F可寫為

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

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

OR,=LI十F(R,T,K)=>R,=L-+尸(RT,K)根據(jù)(i)(ii)

O(L-I'根據(jù)(iii)

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

oP(S(E(RT)?K))=P(S)十K.))

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

根據(jù)(位)可知E(R.\)十K=(E(RL\)ek,)=(￡(/?.-1))十Ki

o(E(R-))-十K=E(RT)十K

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

(2)對DES進行窮舉搜索攻擊時，需要在由256個密鑰構(gòu)成的密鑰空間進行。能否根據(jù)(1)

的結(jié)論減少進行窮搜索攻擊時所用的密鑰空間。

解：(1)根據(jù)取補的性質(zhì)，密鑰空間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是一一一對應(yīng)的；它們的空間大小都是256/2=255。

(2)選擇明文攻擊時，假設(shè)有Ek0(x)=y,其中x、y分別為明文和密文，E為DES加密算法,

ko為真實的密鑰。

第3頁

NCUT密碼學(xué)-習(xí)題與答案2010

么解密后的P1跟加密前一樣，同樣有一個比特的錯誤，而對于Gz能夠解密得到無

錯誤的明文。

4.在8比特CFB模式中，如果在密文字符中出現(xiàn)1比特的錯誤，問該錯誤能傳播多遠。

解：該錯誤將傳播到后面的|[(64+8-1)/81]=8個單元，共9個單元解密得到錯誤的明文。

第5頁

NCUT密碼學(xué)-習(xí)題與答案2010

四、公鑰密碼

1.3.用Fermat定理求3zoimod11。

解：對于模運算，有結(jié)論~(axb)modn=[(amodn)x(bmodn)]modn

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

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

Fermat定理：若p是素數(shù)，a是正整數(shù)且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

解：根據(jù)中國剩余定理求解該同余方程組,

記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.設(shè)通信雙方使用RSA加密體制，接收方的公開鑰是(e,n)=(5,35),接收到的密文是C=10,

求明文M

第6頁

NCUT密碼學(xué)-習(xí)題與答案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

快速指數(shù)算法求模幕105mod35：

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

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

d110305

12.設(shè)RSA加密體制的公開鑰是(e,n)=(77,2是).

(I)用重復(fù)平方法加密明文160,得中間結(jié)果為:

k248163264727677

160mod22118519116351203511821723

若敵手得到以上中間結(jié)果就很容易分解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),即存在整數(shù)k滿足-n)=48k

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

而當(dāng)取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加密體制中，設(shè)素數(shù)p=71,本原根g=7,

⑴如果接收方B的公開鑰是yB=3,發(fā)送方A選擇的隨機整數(shù)k=2,求明文M=30所對應(yīng)的密

文。

(2)如果A選擇另一個隨機整數(shù)匕使得明文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密碼學(xué)-習(xí)題與答案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準(zhǔn)則來判斷，即

如果P是一個奇素數(shù)，則c是模p的平方剩余當(dāng)且僅當(dāng)c<p,>/2=lmodp.

：當(dāng)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=區(qū),?。┖蟆陝t

20.利用橢圓曲線實現(xiàn)ElGamal密碼體制,設(shè)橢圓曲線是En(l,6),生成元G=(2,7),接收方A

的秘密鑰nA=7a

(1)求A的公開鑰PA。

(2)發(fā)送方B欲發(fā)送消息Pm=(10,9),選擇隨機數(shù)k=3,求密文Cm。

(3)顯示接收方A從密文Cm恢復(fù)消息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密碼學(xué)-習(xí)題與答案2010

五、消息認(rèn)證與雜湊函數(shù)

1.6.13節(jié)的數(shù)據(jù)認(rèn)證算法是由CBC模式的DES定義的，其中初始向量取為0,試說明使用CFB

模式也可獲得相同結(jié)果。

如果要使CFB模式輸出結(jié)果和CBC模式的相同，那就要選擇適當(dāng)參數(shù)和輸入。

假設(shè)消息為M=DID2...DN,則按如下思路考慮：

(I)CBC中DES加密和法輸入輸出都為64位，所以CFB中的參數(shù)j應(yīng)取64。此時的CFB

模式變?yōu)椋?/p>

（圖3）

(2)比較圖1和圖2中開始幾個分組的處理，考慮DES加密的輸入和輸出，可知,

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

(3)CBC中最后一個DES加密的輸出為消息認(rèn)證符，即ON=EK(DNEON-I),因此在CFB中,

應(yīng)取PM為Z64(64比特都為0的分組)，這樣有CM=EK(CM-I)?ZM=EK(CM-I)O此時，應(yīng)取PM-I=

DNO

綜上可知：對于消息M=DD2...DN,如果采用DES/CFB的數(shù)據(jù)認(rèn)證算法，那么，當(dāng)其參數(shù)

取如下值時，

參數(shù)j=64,參數(shù)IV=DI,輸入消息M'=D2D3...DNZ64

其輸出與采用DES/CBC的數(shù)據(jù)認(rèn)證算法的輸出相同。

第9頁

NCUT密碼學(xué)-習(xí)題與答案2010

2.有很多散列函數(shù)是由CBC模式的分組加密技術(shù)構(gòu)造的，其中的密鑰取為消息分組。例如將

消息M分成分組Ho=初值，迭代關(guān)系為Hi=EMi(Hi-i)eHi-i(i=l,2,...,N),雜湊值

取為HN,其中E是分組加密算法。

(1)設(shè)E為DES,我們知道如果對明文分組和加密密鑰都逐比特取補，那么得到的密文也是原

密文的逐比特取補，即如果Y=DESK(X),那么Y'=DESK(X')。利用這一結(jié)論證明在上述散列函

數(shù)中可對消息進行修改但卻保持雜湊值不變。

(2)若迭代關(guān)系改為HkEHM(MI)十Mi,證明仍可對其進行上述攻擊。

解：(1)Hi