現(xiàn)代密碼學(xué)（第4版）-習(xí)題參考答案

現(xiàn)代密碼學(xué)(第4版)一習(xí)題參考答案

第1章

1、設(shè)仿射變換的加密是：

En23(，")-1+23(mod26)

對(duì)明文“THENATIONALSECURITYAGENCY”加]密，并使用解密變換

A23?=1r'(c-23)(mod26)

驗(yàn)證你的解密結(jié)果。

解：①明文m=THENATIONALSECURITYAGENCY用數(shù)字表示為：

m=[197413019814130111842201781924064

13224]

根據(jù)對(duì)明文中的每一個(gè)字符計(jì)算出相應(yīng)的密文字符

Eu,23(m)Ell*m+23(mod26),

c=[24221510232472110231413151992724123

111510191]

由此得至U密文C=YWPKXYHVKXONPTJCHYBXLPKTB

②使用解密變換驗(yàn)證加密結(jié)果過(guò)程如下：

由11*19=1(mod26)知H-^19

(注：求模逆元可以通過(guò)歐幾里得算法或者直接窮舉1~25)

根據(jù)Du,23(c)三llT*(c-23)(mod26)=19*(c-23)(mod26),對(duì)密文中的每一個(gè)字符計(jì)算出相應(yīng)的

明文字符

m=[197413019814130111842201781924064

13224]

由此得至I」m=THENATIONALSECURITYAGENCY,解密結(jié)果與明文一致，正確。

2、設(shè)由仿射變換對(duì)一個(gè)明文加密得到的密文為：edsgickxhuklzveqzvkxwkzzukvcuh。又已知

明文的前兩個(gè)字符為“if”，對(duì)該明文解密。

解：設(shè)加密變換為c=Ea,b(m)=a*m+b(mod26)

由題目可知，明文前兩個(gè)字符為if,相應(yīng)密文為ed,即有：

E(i)=e,4=a*8+b(mod26)，(i=8,e=4),

E(f)=d,3=a*5+b(mod26),(f=5,d=3),

由上述兩式可求得，a=9,b=10

因此解密變換為D94o(c)三9-1*(010)(mod26)

又由3*9三1(mod26)可知9,=3

密文對(duì)應(yīng)的數(shù)字表示為：

c=[43186821023720101125214162521102322

10252010212207]

根據(jù)D9」O(C)三T*(c-10)(mod26)=3*(c-10)(mod26),對(duì)密文中的每一個(gè)字符計(jì)算出相應(yīng)的明

文字符

c=[85241420201317403197818197013100

194072417]

由此得到明文m=ifyoucanreadthisthankateahcer

3、設(shè)多表代換密碼中

<313219、,1、

151062521

A=,B=

1017488

2372;□

加密為：G=+B(mod26)

對(duì)明文“PLEASESENDMETHEBOOK,MYCREDITCARDNOISSIXONETWOONETHREEEIGHTSIX

ZEROONESIX日GHTFOURNINESEVENZEROTWO”

用解密變換A/,.=A-'+fi(mod26)

驗(yàn)證你的結(jié)果，其中

’2313205、

,010110

A-i-

19111522

、922625,

解：加密時(shí)，先將明文分組，每四個(gè)一組:

15「18、(13、，⑼(14、,24、

11437142

M三M2M3M4M5此

4181241017

04J41J(04)

、、7、

30'8、[4、(14、

8178231913

%三M,MM=二

198391810141122124

2713J18J2

、

in(12、in7(16、25、

2414110252

6236Go15G=2517

3

3713J27(67

「25、「20、(13、(12、

48174323

C”CC

14金?I7。18

2541812913

9g121J40

、7777

8「23、(24、白3、

401716412

171015124

U5JU2J124；U2J121J

知密文為：NQXBBTWBDCJJIJDTXDCFYFSG

LYGDMOXNLLGNHAPCQZZQZCRG

ZEZJUIEBRRSQNEMVQDJEMXNA

IERPXAKMYRBYTQFMNEMVOME

同上，解密時(shí)，先將密文分組，再代入解密變換：M,.=A-'+B(mod26)

得到明文：PLEASESENDMETHEBOOKMYCRE

DITCARDNOISSIXONETWOONET

HREEEIGHTSIXZEROONESIX日

GHTFOURNINESEVENZEROTWO

解密驗(yàn)證結(jié)果與明文相符。

4、設(shè)多表代換密碼C,=AM,+8(irod26)中，A是2X2矩陣,B是零矩陣,又知明文“dont”

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

faby

解：設(shè)矩陣A三

(cd)

由m=dont=(3,14,13,19),c=elni=(4,ll,13,8)可知:

(mod26)

(1013]

解得：A三[923J

第2章

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

(4，4,4)=(1,0,1),求各線性反饋函數(shù)的輸出序列及周期。

23

解:設(shè)3級(jí)線性反饋特征多項(xiàng)式為p(x)=1+qx+c2x+c3x，若C3=1貝IJq,c2共有22=4

種可能，對(duì)應(yīng)初態(tài)(q,4,q)=(1,0,1)。4種線性反饋函數(shù)分別記為：

Pi(x)=l+d輸出序列a=10110U01…，由定義2-2得周期p=3

P2(x)=l+x+d由定義2-3得是不可約多項(xiàng)式，輸出序列。=1010011101…

由定理2-5周期〃=7是m序列

E,(x)=l+f+x3不可約多項(xiàng)式，輸出序列。=1011100101…，周期p=7是

m序歹！J

23

p4(x)=l+x+x+x輸出序列。=101010…，得周期p=2

2.設(shè)n級(jí)線性反饋移位寄存器的特征多項(xiàng)式為p(x),初始狀態(tài)為

(o1,a2,-.,a?_?an)=(00---01),證明輸出序列的周期等于p(x)的階。

解：p(x)的階定義為〃(刈產(chǎn)-1的最小的〃。

因?yàn)槌跏紶顟B(tài)不為零，設(shè)r為序列的最小周期。又因?yàn)閜(x)\xp-\,所以必存在q(x),

使得M-1=p(x)q(x)。

又因?yàn)槎ɡ?T有p(x)A(x)=^(x),

則p(x)q(x)A(x)=°(x)q(x)-l)A(x)=0(x)q(x)

而q(x)的次數(shù)為p-〃，0(x)的次數(shù)不超過(guò)〃一1,(/'一l)A(x)的次數(shù)不超過(guò)

(〃一")+(〃-1)=〃一1。所以Vi,i是正整數(shù)，都有4+0=%.。

p=kr+t,aj+p=cti+kr+t=ai+l=a,=>/=0,nr|〃。

即周期為p(x)的階,若p(x)是n次不可約多項(xiàng)式，則序列的最小周期等于〃(無(wú))的階。

生成函數(shù)4月=少｛

P(X)A(X)=°(X)H(),0(x)的次數(shù)不超過(guò)〃-1。

p(x

q+Q)X+???+1

A(x)=Z4x'T

MlP(x

rr

p(x)(q-\-a2x-\---1-arx~')=^(x)(x-1j

p(x)不可約，所以gcd(p(x),0(x))=l,p(x)|(x'-l)。又因?yàn)閙Wr,所

以r=機(jī)。

3.設(shè)〃=4,/(q,%,%,〃4)=q十。4十1十。2。3，初始狀態(tài)為(々］,。2，4，4)=。，1，°」)，

求此非線性反饋移位寄存器的輸出序列及周期。

解:由3M4)=4十。4十1十。26，初態(tài)為(4，%嗎,。4)=(1，1，°，1)。線性遞歸

可得：

a5=1十1十1十0=1

4=1十1十1十0=1

%=0十1十1十1=1

%=1十1十1十1=0

“9=1十0十1十1=1

4()=1十1十1十0=1

可以得到輸出序列為(1101111011…)，周期為P=5

4.設(shè)密鑰流是由加=2s級(jí)的LFSR產(chǎn)生，其前m+2個(gè)比特是(01)用，即s+1個(gè)01。問(wèn)第

m+3個(gè)比特有無(wú)可能是1,為什么？

解：第m+3個(gè)比特上不可能出現(xiàn)1,這是由于：

根據(jù)線性移位寄存器的的遞推關(guān)系有：

為s+i=。色S十c2a2ST十???十0/=°

s+2=G2s+l?。/2s=1

馬十，??十C2S<32

從而有a1=0,a?—1,?,^2s+i~°，a2s*2~L代入下式J有：

為5+3=Cia2s+2?C232s+1十’?,十C2S&3=0

5.設(shè)密鑰流是由n級(jí)LFSR產(chǎn)生，其周期為2"-1,i是任一整數(shù)，在密鑰流中考慮以下比特

對(duì)

(Sj,SM),(S)+1,Si+2),...(Sj+2"_3,Sj+2”_2)，(S,+2._2，^,.+2?-l)

問(wèn)有多少形如(S/,Sj+1)=(1,1)的比特對(duì)。試證明你的結(jié)論。

解：根據(jù)p23定理2-7,在GF(2)上的n長(zhǎng)m序列在周期為2"-1的m序列中對(duì)于

1<iW"-2,長(zhǎng)為i的游程有2"-"個(gè)，且0,1游程各半，那么就有：

1的2游程：2"-2T/2=2"M

1的3游程：2"3T/2=2"-5

1的n-2游程:2m/2=1

那么就有：

S=2"4+2"5.2+2i3+……+2-(n-4)+l-(n-3)①

①/2得

^s=2n~5+2n-6-2+……+(〃一4)+(〃-3)/2②

①-②得

-S=2"T+2"T+……+1-(?-3)/2

從而有5=2"-2一2—九+3=2"2—"+1

即共有2"-2一〃+1個(gè)形如(S.,Sj+l)=(1,1)的比特對(duì)。

6.已知流密碼的密文串1010110110和相應(yīng)的明文串0100010001,而且還已知密鑰流是使用

3級(jí)線性反饋移位寄存器產(chǎn)生的，試破譯該密碼系統(tǒng)。

解：由已知可得相應(yīng)的密鑰流序列為1110100111,又因?yàn)槭?級(jí)線性反饋移位寄存器，可

得以下方程:

/4a2a,A(1ir

(%%。6)=(。3,2，1)a2“3a4將值代入得：(010)=(c3c2。)11o

a4a5>J0L

1

(\i1Yiii<iii￥'pii、

|A|=110=1n1i0=101

ioib

0Jb10,

11、

(c3c2。)=(010)101=(101)

10,

由此可得密鑰流的遞推關(guān)系為：ai+3=ciai十qq+2=ai十a(chǎn)j+2。

7.若GF(2)上的二元加法流密碼的密鑰生成器是n級(jí)線性反饋移位寄存器,產(chǎn)生的密鑰是m

序列。2.5節(jié)已知，敵手若知道一段長(zhǎng)為2n的明密文對(duì)就可破譯密鑰流生成器。若敵手僅

知道長(zhǎng)為2n-2的明密文對(duì)，問(wèn)如何破譯密鑰流生成器。

解：如果敵手僅僅知道長(zhǎng)為2n-2的明密文對(duì)，他可以構(gòu)造出以下的長(zhǎng)為2n的明密文對(duì)：

不妨設(shè)：明文：x1x2...x2?_2x2n_lx2n

密文：一必…%

其中：王……W”-2為已知的，X21.X2"為未知的。

必……當(dāng)"-2為己知的，為未知的。

的可能取值為1°，lb。的可能取值為｛oo,。1,io,1"。

共有16種組合方案，分別破解得到密鑰流，在破解的結(jié)果中符合m序列的性質(zhì)密鑰流即為

正確的方案，有可能不唯一。

8.設(shè)J-K觸發(fā)器中｛q｝和｛4｝分別為3級(jí)和4級(jí)m序列，且｛%｝=111O1OO111O1OO--..

｛4｝=001011011011000001011011011000…求輸出序列｛9｝及周期。

解：由J-K觸發(fā)器可知,=（《+bk+\）ck_i+ak

此時(shí)｛4｝和｛仇｝分別為3級(jí)和4級(jí)m序列，（3,4）=1則｛/｝的周期為

（23-1）（24-1）=7x15=105。

｛q｝=H001001010100...o

9.設(shè)基本鐘控序列生成器中｛應(yīng)｝和｛仇｝分別為2級(jí)和3級(jí)m序列，且｛%｝=101101…，

｛bk｝=10011011001101…求輸出序列匕｝及周期。

解：令基本鐘控序列生成器中｛4｝的周期為P-｛仇｝的周期為必，則輸出序列｛q｝的周

期為〃=---—-,W]=￡q=2,P[=2?-1=3,=23-1=7

gcd（w,,p2）i=0

3x7

nP==21o

gcd(2,7)

記LFSR2產(chǎn)生｛4｝,其狀態(tài)向量為％」可得％的變化情況如下:

2b3b3b4b5b5b6bob()b|b2b2b3b4b4b5b6b6bo。1,巧

輸出序列{0}=100011100111000111011…

第3章

1.(1)設(shè)M，和M的逐比特取補(bǔ)，證明在DES中，如果對(duì)明文分組和加密密鑰都逐比特取補(bǔ)，

那么得到的密文也是原密文的逐比特取補(bǔ)，即：

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

提示：對(duì)任意兩個(gè)長(zhǎng)度相等的比特串A和B,證明(A十B)'=AeB。

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

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

(1)證明：

設(shè)L,和氏分別不是第/輪DES變換的左右部分，i=0,l，…,16,則加密過(guò)程為:

4一

“

一

Mbitciphers—/P-f/?[6Zl6)

若將明文和密鑰k同時(shí)取補(bǔ)，則加密過(guò)程為：

LR<-IP

00

L—心

R；-L艮國(guó))

Mbitciphers—IP'(RibLuJ

其中，f(Ri，Kj)的作用是將數(shù)據(jù)的左、右半部分?jǐn)U展后與密鑰進(jìn)行逐比特異或運(yùn)算，

因此/(R,T，KJ=/(R',T，K',),再經(jīng)過(guò)S盒，并將輸出結(jié)果進(jìn)行置換運(yùn)算P之后有：

R：一乙十/(R,T，M十/(R,T,KJ,而&<-J十,所以有

RLE。同時(shí)有〃=乙，所以明文P與密鑰K同時(shí)取補(bǔ)后有丫'=。￡又3)。

(2)答：根據(jù)⑴的結(jié)論進(jìn)行窮搜索攻擊，可將待搜索的密鑰空間減少一半，即255個(gè)。因?yàn)?/p>

給定明文x,則K=DES/X),由⑴知Y2=DES式x')=匕，則一次搜索就包含了x和，兩

種明文情況。

2.證明DES解密變換是加密變換的逆。

證明：

令T(L,R)=(R,L)為左右位置交換函數(shù)，F(xiàn)ki=(L十/(/?,ki),R)，則第i次迭代變換為：

Tki=TFki=T(L?f(R,ki),R)=(R,L@f(R,ki)),

又???T2(L,R)=T(R,L)=I(L,R),有T=T-',

同時(shí)，F(xiàn)^L,R)=F式L?f(R,ki),R)=(L?f(R,ki)?f(R,ki),R)=(L,R),

即Fki=Fj,

：.(FdXTFJ=FkiFki=In(E=FJ,

DES加密過(guò)程在密鑰k作用下為：

DESk=Ip-'Fkl6TFki5T-Fk2TFki(IP),

解密過(guò)程為：

DESJ'=1產(chǎn)'F-TFkJ…F、sTFk、6(IP)，

所以，(DESJ')(DESQ=1，即解密變換是加密變換的逆。(得證)

3.在DES的EBC模式中，如果在密文分組中有一個(gè)錯(cuò)誤，解密后僅相應(yīng)的明文分組

受到影響。然而在CBC模式中，將有錯(cuò)誤傳播。例如在圖3-11中C/中的一個(gè)錯(cuò)誤明顯地

將影響Pi和尸2的結(jié)果。

(1)P2后的分組是否受到影響？

(2)設(shè)加密前的明文分組Pi中有一個(gè)比特的錯(cuò)誤，問(wèn)這一錯(cuò)誤將在多少個(gè)密文分組中傳播？

對(duì)接收者產(chǎn)生什么影響？

答：

(1)在CBC模式中，若密文分組中有一個(gè)錯(cuò)誤G,則解密時(shí)明文分組中4《都將受到

影響，而i=l,2,…后的分組都不受影響，即CBC的錯(cuò)誤傳播長(zhǎng)度為2,具有自恢復(fù)

能力。

(2)若明文分組Pi有錯(cuò)誤，則以后的密文分組都將出現(xiàn)錯(cuò)誤，但對(duì)接收者來(lái)說(shuō)，經(jīng)過(guò)解

密后，除P1有錯(cuò)誤外，其余的明文分組都能正確恢復(fù)。

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

答：

在8比特CFB模式中，若密文有1比特錯(cuò)誤，則會(huì)影響當(dāng)前分組以及后續(xù)分組的解密，

會(huì)使解密輸出連續(xù)9組出錯(cuò)，即錯(cuò)誤傳播的長(zhǎng)度為9。

5.在實(shí)現(xiàn)IDEA時(shí)，最困難得部分是模2僑+1乘法運(yùn)算。以下關(guān)系給出了實(shí)現(xiàn)模乘法的一

種有效方法，其中a和b是兩個(gè)n比特的非0整數(shù)：

(1)證明存在唯一的非負(fù)整數(shù)q和r使得"6=4(2"+D+「；

(2)求q和r的上下界；

(3)證明。+'<2向；

(4)求出丫2")關(guān)于q的表達(dá)式；

(5)求("mod2”)關(guān)于q和「的表達(dá)式；

(6)用(4)和(5)的結(jié)果求r的表達(dá)式，說(shuō)明r的含義。

(1)證明：

假設(shè)存在[”，％，弓使得-=41(2"+1)+4=%(2"+1)+5,有

⑷-%)(2"+l)=q-2，因?yàn)?<不&<2",所以|八一弓區(qū)2",

因此，只能有4=公5=%。

(2)解:0<r=aZ>mod(2n+l)<2n,

顯然，a和b的最大值均為2"-1,則有

…然”=22"-2*1=(2"(2"+1)-2x(2"+l)+2—2"—1)=2?_3

2"+12"+12"+1

JO<^<2n-3,z/(n>2)

所以，<

,<7=0,爐(〃=1)

(3)證明：q+r<2n+2"-3<2n+]

(4)解:根據(jù)ab=g(2"+l)+r,得

qif(q+r)<2"

(ab)div2n—<

q+1if{q+r)>T

(5)解：根據(jù)出?=第2〃+1)+一，得

q+rif(q+r)<2n

(ab)mod2n=<

(q+r)mod2nif(q+r)>2〃

(6)解：當(dāng)皿=4(2"+1)+=時(shí),根據(jù)(皿)由詛"=q及(皿)mod2"=q+r得,

r=(ahm)d2n)-(ahdiv2n)

同理，當(dāng)夕+r之2"時(shí),

r=(abmod2")-(abdivT)+2"+1

余數(shù)r表示ab的n個(gè)最低有效位與ab右移位數(shù)n之差。

6.(1)在IDEA的模乘運(yùn)算中，為什么將模乘取為216+1而不是23？

(2)在IDEA的模加運(yùn)算中，為什么將模乘取為2'6而不是216+1?

答：

(1)在IDEA模乘運(yùn)算中，必須保證運(yùn)算構(gòu)成一個(gè)群，因此模數(shù)必須為素?cái)?shù)，故不能取

216,

(2)同一群內(nèi)的分配律和結(jié)合律都成立，但I(xiàn)DEA算法中要保證模數(shù)的加法和模數(shù)的乘

法，比特異或之間分配律和結(jié)合律不成立，因此模加運(yùn)算不能和模乘運(yùn)算在同一個(gè)群內(nèi)，即

不能選模2歷+1,而在模加運(yùn)算中必為一個(gè)群.

7.證明SM4算法滿足對(duì)合性，即加密過(guò)程和解密過(guò)程一樣，只是密鑰使用的順序相反。

證明：

SM4算法的加密輪函數(shù)分為加密函數(shù)G和數(shù)據(jù)交換E。其中G對(duì)數(shù)據(jù)進(jìn)行加密處理，E

進(jìn)行數(shù)據(jù)順序交換。即加密輪函數(shù)

A=GtE

其中，

Gt=Gi(Xi，Xi+i，M+2，Xi+3,%)(i=0,1,2，…,31)

=(Xj十T(Xi+i,Xi+2，Xi+3，rk)Xi+i,Xi+2，Xi+3)

E(Xi+4，(Xi+i，Xi+2，M+3))=((Xi+i，Xi+2，Xi+3),Xi+4),(i=0,1,2，…，31)

因?yàn)?

⑹)2=[(Xi十7(Xi+i，Xi+2，M+3，rkD，Xi+i，Xi+2，Xi+3，rki)

=(Xi-十T(Xi+i，Xi+2，Xi+3，r/Q)十7(Xi+i，Xi+2，Xi+3，rki),Xi+i，Xi+2，Xi+3，rki)

=何a+1出+2因+3，7母)=I

因此，加密函數(shù)G是對(duì)合的。

E變換為：

E(Xi+4,(Xi+i，Xi+2，Xj+3))=((Xi+i，Xi+2，Xj+3),Xi+4)

E?(Xi+4,(Xi+i，Xi+2，Xi+3))=I

顯然，E是對(duì)合運(yùn)算。

綜上，加密輪函數(shù)是對(duì)合的。

根據(jù)加密框圖，可將SM4的加密過(guò)程寫為：

SM4=GQEG^E...G30EG31R

根據(jù)解密框圖，可將SM4的解密過(guò)程寫為：

SM4T=G31EG30E...G1EG0R

比較SM4與SM4」可知，運(yùn)算相同，只有密鑰的使用順序不同。

所以，SM4算法是對(duì)合的。

第4章

1.證明以下關(guān)系：

(1)(amodn)=(Jbmodn),則a三bmod〃；

(2)a=bmodnfWOb=amodn；

(3)a=bmodnfb=cmodn?則々三。mod〃。

解：(1)設(shè)amod〃=G，bmod〃=/;,由題意得吃二5，且存在整數(shù)，%,使得

a=jn+ra,b=kn+rh^>a—b=(j-k)n,即〃|a—/7,證得々三人mod〃。

(2)已知。三〃mod/z,則存在整數(shù)Z，使得Q=ki+/?nb=(-Z)〃+a,證得三amod〃。

(3)已知a三〃mod〃力三c、mod〃，則存在整數(shù)，次，使得

a=jn+b,b=kn+c=>a=(/+左)〃+c,證得a三cmod〃。

2.證明以下關(guān)系:

(1)[(amodn)-(bmod〃月modn-(a-h)modn；

(2)[(amodn)x(bmodn)]modn=(axh)modn。

解：(1)設(shè)4mod〃=c，0mod〃=以，則存在整數(shù)，上,使得

a=jn+ra,b=kn+rb^>a-h=(j-k)n+(ra-rb')

=>ra-rb=-(j-k)n-h(a-b)

=>(〃-與)modn-(a-b)modn.

即[(〃modn)-(bmod〃)]modn=(a-b)modn0

(2)設(shè)々mod"=弓,。mod〃=5,則存在整數(shù)，攵，使得

a=jn-\-ra,b=kn+rbnaxb=(Jkn+m+行口"+二%

n=-(jkn++krJn+Sxb)

=>(〃7;)modn=(axb)modn.

即[(〃modn)x(hmodn)]modn=(axb)modn。

2

3.用Fermat定理求3"mod11o

解：因?yàn)椤?11是素?cái)?shù)，且gcd(3,ll)=l,則由Fermat定理可得:

3")三1mod11n。心"三1mod11；

又根據(jù)性質(zhì)[(〃mod〃)x(bmod/2)]modn=(axb)modn,可得:

3201mod11=[((3I0)20)mod11)x(3'mod11)]mod11=3mod11。

4.用推廣的Euclid算法求67modl19的逆元。

解：運(yùn)算步驟如下表所示：

循環(huán)次數(shù)Yi丫2丫3

QX1X2X3

初值?101190167

1101671-152

211-152-1215

33-12154-77

424-77-9161

所以677modl19=16。

5.求gcd(4655,12075)。

解：由Euclid算法，得：

12075=2x4655+2765

4655=1x2765+1890

2765=1x1890+875

1890=2x875+140

875=6x140+35

140=4x35+0

所以gcd(4655,12075)=35。

x=2mod3

6.求解下列同余方程組：(X三lmod5

x=1mod7

解：根據(jù)中國(guó)剩余定理求解該同余方程組，記4=2,%=1,%=1，叫=3,牡=5,m,=7,

M=町x機(jī),x丐=105,則有

M=——=35,Mmod町=35Tmod3=2,

町

modm2=21Tmod5=1,,

M=—=15,M-'mod嗎=15Tmod7=l.

im,

所以方程組的解為

x=+M2M^a2+)modM

=(35x2x2+21xlxl+15xlxl)modl05

=176modl05=71modl05.

7.計(jì)算下列Legendre符號(hào)：

解:⑴圓=(-1)小=-1

⑵

(-1)[2+：X3)=(―1(|)=(-1)(-1)^

=1

8.求25的所有本原根。

解：因?yàn)橄?25)=25(1—5=20=22x5,所以°(25)的所有不同的素因子為1=2,=5,

即對(duì)每個(gè)只需計(jì)算叱又因?yàn)橐运杂?/p>

g,824)=24(l—g)(l—；)=8,258個(gè)本

原根。

I10=lmod25,I4=lmod25；210=24mod25?24=16mod25；

3'°=24mod25,34=6mod25；410=1mod25,44=6mod25；

5'°=0mod25,5°=0mod25；610-lmod25,64=21mod25；

7川=24moe125,74=lmod25；8,0=24mod25,84=21mod25；

910=lmod25,94=Hmod25；IO10=0mod25,104=0mod25；

lf°=lmod25,ll4=16mod25；1210=24mod25,124=Hmod25；

1310=24mod25,134=llmod25；1410=lmod25,144=16mod25；

15'°=0mod25,154=0mod25；16l0=lmod25,164=llmod25；

1710=24mod25,174=21mod25；1810=24mod25,184=1mod25；

W°=lmod25,194=21mod25；2O10=0mod25,204=0mod25；

2110=lmod25,214=6mod25；2210=24mod25,224=6mod25；

2310=24mod25,234=16mod25；24'°=1mod25,244=1mod25；

滿足g1°w1mod25且g4Hlmod25的g為25的本原根，即2,3,8,12,13/7,22,23

9.證明當(dāng)且僅當(dāng)〃是素?cái)?shù)時(shí)，<Z",+“，x“〉是域。

證明：(1)若<Z“,+“，x”>是域，則<Z,,+“>,<Z“-{0},x“>均為Abel群。顯然

＜Z",+”＞為Abel群，與〃是否為素?cái)?shù)無(wú)關(guān)；但若＜Z“-{O},x“＞為Abel群，其條件之一

必須保證對(duì)任意XGZ“-{0}有模乘法逆元，即對(duì)任意xeZ“-{0},有yeZ,-{0},使

得xxy三lmod〃，所以gcd(尤,〃)=1,即〃為素?cái)?shù)。

(2)若〃不是素?cái)?shù)，則雙〃)＜〃-1,即至少存在一個(gè)xeZ“一{0},使得gcd(x,〃)Hl,即x

無(wú)模乘法逆元，因此不能保證＜Z〃-{0},x“＞均為Abel群,即＜Z“,+“，x”＞不是域。

10.設(shè)通信雙方使用RSA加密體制，接收方的公開鑰是(e,〃)=(5,35),接收到的密文是

C=10,求明文

解：因?yàn)椤?35=5x7=＞p=5,q=7,則奴〃)=(p_l)(q_l)=4x6=24,所以

dme~[modQ(〃)三5Tmod24=5mod24,即明文M三C"modn=105mod35=5。

11.已知cdmodn的運(yùn)行時(shí)間是OQog]〃)，用中國(guó)剩余定理改進(jìn)RSA的解密運(yùn)算。如果

不考慮中國(guó)剩余定理的計(jì)算代價(jià)，證明改進(jìn)后的解密運(yùn)算速度是原解密運(yùn)算速度的4倍。

證明：RSA的兩個(gè)大素因子p,q的長(zhǎng)度近似相等，約為模數(shù)〃的比特長(zhǎng)度log〃的一半，即

(log/?)/2,而在中國(guó)剩余定理中，需要對(duì)模p和模夕進(jìn)行模指數(shù)運(yùn)算，這與c"mod〃的

運(yùn)行時(shí)間規(guī)律相似，所以每一個(gè)模指數(shù)運(yùn)算的運(yùn)行時(shí)間仍然是其模長(zhǎng)的三次累，即

O[(logn/2)3]=O(log3n)/8?

在不考慮中國(guó)剩余定理計(jì)算代價(jià)的情況下，RSA解密運(yùn)算的總運(yùn)行時(shí)間為兩個(gè)模指數(shù)運(yùn)算

的運(yùn)行時(shí)間之和，即。(log3〃)/8+O(log3〃)/8=O(log3〃)/4,證得改進(jìn)后的解密運(yùn)算速

度是原解密運(yùn)算速度的4倍。

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

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

16()2(mod221)三185

1604(mod221)三191

16()8(mod221)三16

160'6(mod221)=35

IGO'?(mod221)=120

16()64(mod221)三35

16072(mod221)=118

16076(mod221)=217

16077(mod221)=23

若敵手得到以上中間結(jié)果就很容易分解〃，問(wèn)敵手如何分解〃。

(2)求解密密鑰

解：(1)由以上中間結(jié)果可得：

16016(mod221)三35三WO^Cmod221)

=>16064-160l6=0(mod221)

8

n(16()32—[60s)(16032+16O)=0(mod221)。

=>(120-16)(120+16)=0(mod221)

=>104x136三0(mod221)

由gcd(104,221)=l3,gcd(l36,221)=17,可知分解為221=13x17。

⑵解密密鑰d=eTmod(9(〃))=77Tmod(°(13xl7))=77Tmod(12xl6),由擴(kuò)展的

Eucild算法可得d=5。

13.在ElGamal加密體制中，設(shè)素?cái)?shù)p=71,本原根g=7,

(1)如果接收方B的公開鑰是為=3,發(fā)送方A選擇的隨機(jī)整數(shù)左=2,求明文M=30所

對(duì)應(yīng)的密文。

(2)如果A選擇另一個(gè)隨機(jī)整數(shù)k，使得明文M=30加密后的密文是C=(59,)，求。2。

解：(1)密文c=(q，G)，其中：

k22

G-gmodp-7mod71=49,C2=(yjM)modp=(3x30)mod71=57。

所以明文M=30對(duì)應(yīng)的密文為C=(49,57)。

⑵由G=8卜mod〃n59=7kmod71,窮舉法可得k=3。

所以G=(y)modp=(33x30)mod71=29。

14.設(shè)背包密碼系統(tǒng)的超遞增序列為(3,4,9/7,35),乘數(shù)r=19,模數(shù)左=73,試對(duì)good

night力口密。

解：由4=(3,4,9,17,35),乘數(shù)1=19，模數(shù)左=73,可得

B-txAmodk=(57,3,25,31,8)。

明文“goodnight”的編碼為“00111”,“01111”,“01111”,“00100”，“00000”,"OHIO”,"01001”,

“00111”,“01000”,“10100”,則有：

/(00111)=25+31+8=64,

/(01111)=3+25+31+8=67,

/(01111)=3+25+31+8=67,

/(00100)=25,

/(00000)=0,

/(01110)=3+25+31=59,

/(01001)=3+8=11,

/(00111)=25+31+8=64,

/(01000)=3,

/(10100)=57+25=82=9mod73.

所以明文“goodnight”相應(yīng)的密文為(64,67,67,25,0,59,11,64,3,9)。

15.設(shè)背包密碼系統(tǒng)的超遞增序列為(3,4,8,17,35),乘數(shù)，=17,模數(shù)％=67,試對(duì)

25,2,72,92解密。

解：因?yàn)?mod%=17一|mod67=4mod67，則4x(25,2,72,92)mod67=(33,8,20,33)。

所以其對(duì)應(yīng)的明文分組為(0()001,0010(),10010,000()1),由課本120頁(yè)表4-7可得明文為

“ADRA”。

16.己知〃=網(wǎng)，p,q都是素?cái)?shù)，x,ywZ：,其Jacobi符號(hào)都是1,其中Z：=Z“一{0},

證明：

⑴肛(mod〃)是?！ǖ钠椒绞Ｓ?，當(dāng)且僅當(dāng)都是?！ǖ钠椒绞Ｓ嗷蚨际悄！ǖ姆?/p>

平方剩余。

(2)Vy5(mod〃)是模〃的平方剩余，當(dāng)且僅當(dāng)尤,y都是?！钡钠椒绞Ｓ嗷蚨际悄！ǖ?/p>

非平方剩余。

證明：（1）①必要性：若孫（mod〃）是?！ǖ钠椒绞Ｓ?，即存在f使得xy=rmod”，而

n-pq,顯然必有xy=rmodp,xy-rmodg,所以刈也同時(shí)是模p和模q的平方剩余,

即（現(xiàn)）=1,（現(xiàn)）=1n（￡）￡）=1,（-）A=1.

pqppqq

又由題意得（2）=1,（2）=1,BP（-）（-）=1,（-）（-）=1?所以：

nnpqpq

當(dāng)（±）=1時(shí)，有（2）=ln（2）=ln（土）=1,即x同時(shí)是模p和模q的平方剩余，y也

ppqq

同時(shí)是模p和模夕的平方剩余，即都是模"的平方剩余；

當(dāng)（土）=7時(shí)，有（馬=_10（馬=_1=（為=_1,即x同時(shí)是模p和模q的非平方剩

ppqq

余，y也同時(shí)是模p和模q的非平方剩余，即都是?！ǖ姆瞧椒绞Ｓ唷?/p>

②充分性：若都是?！暗钠椒绞Ｓ啵瑒t演y也是模p和模9的平方剩余，即

（土）=（當(dāng)=（馬=（?）=1,即孫同時(shí)是模p和模q的平方剩余，所以孫是?！ǖ钠椒绞?/p>

pqpq

余；

若演y都是?！ǖ姆瞧椒绞Ｓ?，則它們對(duì)于模p和模q至少有一種情況是非平方剩余，不妨

設(shè)（土）=-1,=（2）=一1，則有（與=-1,（馬=一1,即尤,y也都是模p和模q的非平方剩

ppqq

余。所以（土）（上）=（?）=（—1）（—1）=1,同理（與）=1,即孫同時(shí)是模p和模q的平方剩

pppq

余，所以孫是?！ǖ钠椒绞Ｓ唷?/p>

⑵若x，5（mod〃）是?！ǖ钠椒绞Ｓ?，則丁尸同時(shí)是模p和模q的平方剩余，所以

<35\

4L=1=（二）3（2）5,由于勒讓德符號(hào)的偶數(shù)次方肯定為1（p|x情況除外），即有

<pJpP

1=（A）（2）,余下證明同（1）。

pP

提示:

目訃1

V、

XX|yy

、p人“p人力

=[￡(?

17.在Rabin密碼體制中設(shè)p=53,q=59：

(1)確定1在?！ㄏ碌?個(gè)平方根。

(2)求明文消息2347所對(duì)應(yīng)的密文。

(3)對(duì)上述密文，確定可能的4個(gè)明文。

解：(1)已知/三lmod3127,〃=pq=53x59=3125,由中國(guó)剩余定理可得到等價(jià)方程

組:

x1=1mod53

x2simod59

因?yàn)?±1)2三1mod53,(±iy三lmod59,所以x三土lmod53,x三±lmod59。經(jīng)組合可

得到以下四個(gè)方程組:

x三lmod53x=\mod53x=-lmod53x=-lmod53

x=lmod59x=-lmod59x=lmod59x=-lmod59

]

根據(jù)中國(guó)剩余定理M=59,mod53=9,M2=53,M；mod59=49,則有:

第一個(gè)方程組的解為(59?9?l+53?49?l)mod3127ml；

第二個(gè)方程組的解為(59?9?l+53?49?(—l))mod3127三1061；

第三個(gè)方程組的解為(59?9?(—1)+53?49?1)mod3127三2066；

第四個(gè)方程組的解為(59.9?(—1)+53?49.(—l))mod3127三3126。

所以，1mod/?的四個(gè)平方根為1mod()61mod〃,2066mod〃,3126modn。

(2)2347對(duì)應(yīng)的密文為c三23472mod3127三1762。

(3)解密即解尤2三I762mod3127,由中國(guó)剩余定理可得到等價(jià)方程組：

X2三1762mod53=13

x2三1762mod59