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

第1章

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

片1.23(⑼三1+23(mod26)

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

-l

D1123(C)=1l(c-23)(mod26)

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

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

m=[197413019814130111842201781924064

13224]

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

En,23(m)=ll*m+23(mod26),

c=[24221510232472110231413151992724123

111510191]

由此得到密文C=YWPKXYHVKXONPTJCHYBXLPKTB

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

由11*19=1(mod26)知

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

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

明文字符

m=[197413019814130111842201781924064

13224]

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

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

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

解：設(shè)加密變換為c=E，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

因此解密變換為D9」o(c)三9"(c-10)(mod26)

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

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

c=[43186821023720101125214162521102322

10252010212207]

1

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

文字符

c=[85241420201317403197818197013100

194072417]

由此得到明文m=ifyoucanreadthisthankateahcer

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

口13219)’1、

151062521

A=,B=

1017488

2372>□

加密為：G三A叫+8(mod26)

對(duì)明文“PLEASESENDMETHEBOOK,MYCREDITCARDNOISSIXONETWOONETHREEEIGHTSIX

ZEROONESIX日GHTFOURNINESEVENZEROTWO”

用解密變換M三AT+8(mod26)

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

,2313205、

.010110

%一=

9111522

、922625,

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

LYGDMOXNLLGNHAPCQZZQZCRG

ZEZJUIEBRRSQNEMVQDJEMXNA

IERPXAKMYRBYTQFMNEMVOME

同上，解密時(shí)，先將密文分組，再代入解密變換：A/,=AT+3(mod26)

得到明文：PLEASESENDMETHEBOOKMYCRE

DITCARDNOISSIXONETWOONET

HREEEIGHTSIXZEROONESIX日

GHTFOURNINESEVENZEROTWO

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

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

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

b、

解：設(shè)矩陣A三

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

(mod26)

(⑶fa丫13)

、8兒(mod26)

,flO

解得：A三

193

第2章

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

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

3

解:設(shè)3級(jí)線性反饋特征多項(xiàng)式為p(x)=1+。2爐+c3x，若。3=1則。，%共有22=4

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

p,(x)=l+x3輸出序列a=101101101…，由定義2-2得周期p=3

〃2(力=1+工+{由定義2-3得是不可約多項(xiàng)式，輸出序列a=1010011101…

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

〃3(6=1+/+丁不可約多項(xiàng)式，輸出序列。=1011100101…，周期p=7是

m序列

〃4(%)=1+1+”2+/輸出序列4=101010…，得周期p=2

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

(q…Miq)=(00…01),證明輸出序列的周期等于p(x)的階。

解：p(x)的階定義為p(x)|M—l的最小的p。

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

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

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

則P(x)4(x)4(x)=0(x)4(x)n(M-1)A(x)=°("夕(x)

而以力的次數(shù)為〃一〃，@(力的次數(shù)不超過(guò)"1,(x"—lj4(x)的次數(shù)不超過(guò)

(p-H)+(w-l)=p-1o所以Vi,i是正整數(shù)，都有4+p=q。

設(shè)〃=b+r,4”=q?，.，=4+,=%=>￡=()，=川〃。

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

生成函數(shù)A

*)=44,p(x)A(x)=°(x)工0,的次數(shù)不超過(guò)〃-1。

P(x)

3)￡尸=尸票

：=1X-1p\x)

r-lr

p(x)(q4-a2x+---+arx1=^(x)fx-1)

〃(x)不可約，所以gcd(p(x)，0(x))=l,p(x)|(xr-l)o又因?yàn)樗?/p>

3.設(shè)〃=4,/(q,叼,4M4)=4十。4十1十44，初始狀態(tài)為(4,出,6,。4)=(1，1，°，1)，

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

解：由/(%,%,%,%)=%十(十18%%,初態(tài)為(％02gM4)=(1，1，°」)。線性遞歸

可得：

6=1十1十1十0=1

。6=1十?十0=1

%=0十1十1十1=1

6=1十1十1十1=0

4=1十0十1十1=1

aXQ=1十1十1十0=1

可以得到輸出序列為(1101111011...),周期為p=5。

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

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

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

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

%S+1=。色S十。2a2s-\十…十C2sa\=°

*=G%+i十3%十…十QsW=1

從而有馬=0,弓=1'?-%+1=0,%+2=L代入下式有：

為s+3=G馬S+2十C2a2S+1十???十。2.?3=0

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

對(duì)

(Sj,SM),(5/+I,Sj+2),...(Sj+2-，Sj+2“-2%(Sj+2J2?Sj+2"T)

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

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

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

1的2游程：2^/2=2n~4

1的3游程：2〃-a/2=2"r

1的n-2游程：2"12=1

那么就有：

S=2"T+2”-5.2+2”Y.3+……+2(H-4)+1-(H-3)①

①/2得

L=2"T+2”-6.2+……+(〃-4)+(〃-3)/2②

2

①-②得

3s=21十2'T+……+1-(/1-3)/2

從而有S=2〃-2-2-〃+3=2”<一〃+1

即共有2"<一〃+1個(gè)形如區(qū),S刑）=（1,1）的比特對(duì)。

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

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

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

得以下方程:

%a2%]p

（的$4）=（。3c2。）a24%將值代入得：(oio)=(c3c2。)110

1

%%)I0b

(\11Y1111(111Y'11、

110同=110=1=>110=101

J。101J0"J10;

qir

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

J10/

由此可得密鑰流的遞推關(guān)系為：4+3=。3勾十G4+2=ai十4+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è)：明文：xxx2...x2n_2x2n_｛xiti

密文：…為“-2y22%

其中：2……”2〃-2為已知的，入21,“2“為未知的。

M...為已知的,力1為未知的。

（力〃?132“）的可能取值為｛0。，°】，I。，ID。的可能取值為｛00，°1，10，I1｝。

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

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

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

他｝=001011011011000001011011011000…求輸出序列匕｝及周期。

解：由J-K觸發(fā)器可知4=3+4+1）7]+4

%，ck-\=°

c.=<—

43=1

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

（23-1）（24-1）=7X15=105O

｛q｝=11001001010100...o

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

｛4｝=10011011001101…求輸出序列｛/｝及周期。

解：令基本鐘控序列生成器中｛《｝的周期為小，｛4｝的周期為外，則輸出序列｛cj的周

pDPi-I

23

期為P=—~7，/=Xq=2，Pi=2-1=3,p2=2-1=7

gcd（卬],p2）,=o

3x7

P21

gcd(2,7)

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

5)5b|b2b3b6bo5)0b2b2b30"Q4b5b6b6bo50"1%

輸出序列{4}=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)'=A'十B。

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

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

(1)證明：

設(shè)L和用分別不是第i輪DES變換的左右部分，歸),1，…,16,則加密過(guò)程為：

k)R)JP

Li—品

《心十/火，()

64bitcipher—

/R'(/?16LI6)

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

LR<-IP

00

工一&

&-L-i十凡,KJ

64bitcipher<—/P'(/?16￡16)

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

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

Q—7/“十/(R1,K：)=LL十/(串口匕),而R,<-L一十,所以有

R\=卻同時(shí)有4=如所以明文P與密鑰K同時(shí)取補(bǔ)后有y'=OESM￡)。

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

給定明文x,則X=DESJx),由⑴知Y2=DESk.(￡)=匕,則一次搜索就包含了x和，兩

種明文情況。

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

證明：

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

Tki=TFk,=T(L十R)=(R,￡十f(R,k玲,

又丁T2(￡,/?)=T(R,L)=Z(L,R),有T=T-1,

同時(shí)，F(xiàn)*L,R)=F式L十以R,ki),R)=(L十f(R,ki)十f(R,ki),R)=(L,R),

即匕產(chǎn)成，

1

???(FkiT)(TFki)=FkiFki=I=(7FJ-=FJ,

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

OE51/K/可口…七巧i(")，

解密過(guò)程為：

DESJ=//胤??%5"U6(/P)，

所以，(DES「)(DESk)=I，即解密變換是加密變換的逆。(得證)

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

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

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

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

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

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

答：

(1)在CBC模式中，若密文分組中有一個(gè)錯(cuò)誤&,則解密時(shí)明文分組中［，鳥(niǎo)都將受到

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

能力。

(2)若明文分組P有錯(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í)，最困難得部分是模皆6+1乘法運(yùn)算。以下關(guān)系給出了實(shí)現(xiàn)模乘法的一

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

(1)證明存在唯一的非負(fù)整數(shù)q和r使得"二夕Q"+1)+J

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

(3)證明〃+

(4)求(。人揣2”)關(guān)干q的表達(dá)式：

⑸求("md2”)關(guān)于4和「的表達(dá)式；

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

(1)證明：

假設(shè)存在0"國(guó)2,弓使得=+1)+。=%(2"+1)+優(yōu)有

@一%)(2"+1)=6-公因?yàn)榕ck2"，所以一與區(qū)2",

因此，只能有q=公％=%,

(2)解：0V〃="mod(2"")V2"，

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

…L=22”-2=+1=(2”(2"+1"2x(2〃+l)+2-2")=y_3

2"+12”+12〃+1

所以，

4=0,/(〃=1)

(3)證明：^+r<2w+2M-3<2n+,

(4)解：根據(jù)。：=夕(2'+1)+/，得

qVG7+r)<2"

(ab)div2n=,

9+1if(q+r)>2n

(5)解：根據(jù)，山=式2"+1)+-，得

..q+rif(q+r)<2"

(ab)mod2=<

(<7+r)mod2Hif(q+r)>2n

(6)解：當(dāng)"=冢2"+1)+「時(shí)，根據(jù)(次?"42"二［及(")1口0<12”二夕+廣得,

r-(abiTod2")-{abdivT)

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

r=(abmod2")-{abdiv2n)+2”+1

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

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

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

答：

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

2,6o

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

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

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

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

證明：

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

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

Ft=GtE

其中，

Gi=Gi(Xi，Xi+i，Xi+2，Xi+3，rkD(i=0,1,2,...,31)

=&十7(吊+i，X*2,凡+3,rki),Xi+i,Xi+2,眉+3)

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

因?yàn)?

(G)2=?十]名十2，用十3，%)，%十1，眉十2，凡十3，%)

r

=(X[?T(Xj+i，Xj+2,Xj+3，rkj)十7(Xj+i，Xi+2>^i+3>泌i)，^i+l>^i+2>^i+3>^i)

二(X〃Xi+i，Xj+2，Xi+3,叫)=/

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

E變換為：

E(M+4，(Xi+i，Xi+2，Xi+3))=((Xi+i，Xi+2，Xi+3)，Xi_4)

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

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

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

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

SM4=GqEG^E…G30EG31R

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

-1

SM4=G3IEG30E...G1EG0R

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

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

第4章

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

(1)(amodn)=(bmodn),則〃三bmod〃；

(2)a三Z?modn,則。三。modn；

(3)4三。mod〃,Z?=cmodw,則a三cmod〃。

解：(1)設(shè)amod〃=〃,bmod〃=/;,由題意得且存在整數(shù)j,左，使得

a=jn+ra,b=kn+^^>a-b=(j-k)n,BPn\a—b,證得a三人mod〃。

(2)已知。三人mod〃，則存在整數(shù)上，使得a=E+b=>b=(一％)〃+〃，證得Z?三amod〃。

(3)己知。三bmod〃力三cmod〃，則存在整數(shù)，火，使得

a=jn+b,b=kn+c=>a=(J+k)n+c,證得a三cmod〃。

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

(1)[(?modn)-(bmodn)]modn=(a-b)modn：

(2)[(amodn)x(bmod〃)]modn=(axb)modn。

解：(1)設(shè)4mo==則存在整數(shù)j,2,使得

a=jn+ra,b=kn+rha-b=(j-k)n+(ra-rh)

ra-rh=-(j-k)n+(a-b)

n(〃一^)mod〃=(a-b)mod".

即modn)-(bmodn)\modn=(a-h)modn。

(2)設(shè)〃mod〃=%〃mod〃=?;,則存在整數(shù),使得

a=jn+ra,b=kn+rh^>axb=(jkn+jrb+kra)n+rarh

=G4=Tjkn+jrb+kra)n+(axb)

=>(rarb')modn=(axb)mod”.

即[(amod/?)x(bmod〃)]modn=(axb)modn。

3.用Fermat定理求32tHmodi1o

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

310三1mod11=>(3,0/三1mod11；

又根據(jù)性質(zhì)[(amodn)x(hmod〃)]modn=(axb)modn,可得:

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

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

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

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

初值?101190167

1101671-152

211-152-1215

33-12154-77

424-77-9161

所以677mod119=16。

5.求gcd(4655/2075)。

解：由Euclid算法，得：

12075=2x4655+2765

4655=1x2765+1890

2765=1x1890+875

1890=2x875+140

875=6x140+35

140=4x35+0

所以gcd(4655/2075)=35。

x=2mod3

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

x=1mod7

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

M=〃qxm2xmj=105,則有

=—=35,mod=35-1mod3=2,

—=modm2=21Tmod5=1,,

niy

=—=15,M^1mod嗎=15"mod7=1.

所以方程組的解為

x三(必”「4+M2M二生+時(shí)也；&)1110(]”

三(35x2x2+21x1x1+15x1x1)mod105

=176modl05=71modl05.

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

2165

59>￡107

=(-1)8=-1

⑵

3、

—=(-1)

53)

32-1

2+17x3

=(-1)=(一1)(一產(chǎn)

3

8.求25的所有本原根。

1

解：因?yàn)?(25)=25(1--)=20=292x5,所以以25)的所有不同的素因了?為％=2,%=5,

即對(duì)每個(gè)g,只需計(jì)算g叫屋。又因?yàn)?(24)=24(1-；)(1-}=8,所以25有8個(gè)本

原根。

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

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

5,0=Omod25,5°=0mod25；6,0=lmod25,64=21mod25；

=24mod25,74=Imod25；810=24mod25,84=21mod25；

910=1mod25,94=1lmod25；IOI。=0mod25,104=0mod25；

H,0=lmod25,ll4=16mod25；12'°=24mod25,124=llmod25；

1310=24mod25,134=llmod25；14,0=lmod25,I44=16mod25；

15,0=Omod25,154=0mod25；16,0=lmod25,164=llmod25；

17'°=24mod25,174=21mod25；1810=24mod25,18」=1mod25；

19,0=lmod25,194=21mod25；20,0=0mod25,204=0mod25；

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

23'°=24mod25,234=16mod25；2410=1mod25,244=1mod25；

滿足腔工1mod25且屋w1mod25的g為25的本原根,即2,3,8,12,13,17,22,23。

9.證明當(dāng)且僅當(dāng)〃是素?cái)?shù)時(shí)，是域。

證明：⑴若＜Z",+",x“＞是域.則＜Z.,+〃＞,vZ〃-{0},x〃＞均為Abel群。顯然

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

必須保證對(duì)任意xwZ”一{0}有模乘法逆元，即對(duì)任意xwZ”—{0},有yeZ〃—{0},使

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

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

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

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

C=1O,求明文

解:因?yàn)椤?35=5x7n〃=5/=7,則以〃)=(p-l)(g-l)=4x6=24,所以

d=e~1modw(〃)=5-1mod24=5mod24,即明文A/三C"modn=105mod35=5o

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

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

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

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

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

O[(logn/2)3]=O(log3〃)/8。

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

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

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

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

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

1602(mod221)三185

1604(mod221)=191

160s(mod221)三16

16()16(mod221)三35

16032(mod221)三120

160w(mod221)三35

16072(mod221)三118

16076(mod221)=217

16077(mod221)=23

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

(2)求解密密鑰d。

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

16016(mod221)三35三160M(mod221)

=>16064-160l6=0(mod221)

=>(16032-1608)(16032+1608)=0(mod221)。

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

=>104xl36=0(mod221)

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

(2)解密密鑰d=/mod"。)=7丁'mod(*(l3x17))=77Tmod(12x16),由擴(kuò)展的

Eucild算法可得d=5。

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

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

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

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

解：⑴密文。XGG),其中：

22

C,=modp=7mod71=49,C2=()，/M)modp=(3x30)mod71=57。

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

⑵由G=g*mod〃=>59=7*mod71,窮舉法可得攵=3。

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

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

night力口密。

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

B=fxAmod4=(57,3,25,31,8)。

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

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

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

“01111)=3+25+31+8=67,

“01111)=3+25+31+8=67,

“00100)=25,

")0000)=0,

7(01110)=34-25+31=59,

/(01001)=3+8=11,

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

")1000)=3,

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

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

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

25,2,72,92解密。

解：因?yàn)?mod4=177mod67=4mod67，貝ij4x(25,2,72,92)mod67=(33,8,20,33)。

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

“ADRA”。

16.已知枕=pq,p,夕都是素?cái)?shù)，x,yGZ*,其Jacobi符號(hào)都是1,其中Z：=Z“一{0},

證明：

(1)刈(mod〃)是?！ǖ钠椒绞Ｓ?，當(dāng)且僅當(dāng)都是模〃的平方剩余或都是?！ǖ姆?/p>

平方剩余。

⑵Jy5(mod〃)是?！ǖ钠椒绞Ｓ啵?dāng)且僅當(dāng)都是?！ǖ钠椒绞Ｓ嗷蚨际悄！ǖ?/p>

非平方剩余。

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

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

即盧）=1,盧）=1nQ馬=0）（馬=1。

pqppqq

又由題意得（土）=1,（上）=1,即（為（為=1,（』）（￡）二1。所以：

nnpqpq

當(dāng)（土）=1時(shí)，W（^）=l=＞（-）=l^＞（-）=b即x同時(shí)是模p和?！返钠椒绞Ｓ?y也

ppqq

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

當(dāng)（與二一1時(shí)，有g(shù)）=_in（2）=_in（與二-1,即無(wú)同時(shí)是模p和模q的非平方剩

ppqq

余，y也同時(shí)是模p和模g的非平方剩余，即都是模〃的非平方剩余。

②充分性：若都是模〃的平方剩余，則也是模p和模夕的平方剩余，即

（￡）=（￡）=（Z）=（Z）=i,即v同時(shí)是模P和模q的平方剩余，所以孫是模九的平方剩

pqpq

余；

若都是模〃的非平方剩余，則它們對(duì)于模p和模夕至少有一種情況是非平方剩余，不妨

設(shè)（土）=-1,=（馬二一1,貝|」有（土）二-1,（馬二一1,即大,），也都是模p和模q的非平方剩

ppqq

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

pppq

余，所以孫是模〃的平方剩余。

⑵若/y5（mod〃）是?！ǖ钠椒绞Ｓ?，則Vy5同時(shí)是模〃和模夕的平方剩余，所以

/35\

3-=1=（土人工了，由于勒讓德符號(hào)的偶數(shù)次方肯定為1（p|x情況除外），即有

\P）PP

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

pP

提不:

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

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

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

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

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

組:

x2三1mod53

x2三lmod59

因?yàn)?±1>三1mod53,(±1尸三1mod59,所以xm±lmod53,x三±1mod59。經(jīng)組合可

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

x=1mod53fx=lmod53fx=-lmod53fx=-lmod53

<<<?

A?三lmod59[x=-lmod59[x=lmod59[x=-lmod59

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

第一個(gè)方程組的解為(59?94+53-49」)mod3127三1；

第二個(gè)方程組的解為(59?9?1+53?49?(-1))mod3127=1061；

第三個(gè)方程組的解為(599(—l)+53?494)mod3127三2066；

第四個(gè)方程組的解為(599(-1)+53?49?(一l))mod3127三3126。

所以，1mod〃的四個(gè)平方根為1mod〃,1061mod〃,2066mod126mod"。

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

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

x2=1762mod53=13

<

X2=1762mod59=51

因?yàn)?±15>三13mod53,(±13>三51mod59,所以x三±15mod53,x三±13mod59,經(jīng)

組合可得到以下四個(gè)方程組：

x=15mod53pc三15mod53=-15mod53[x=-15mod53

x三13moe159[x=-13mod591xm13moe159[x三一13mod59

根據(jù)中國(guó)剩余定理此=59,"Jmod53三9,以=53,M2'mod59=49,則有：

第一個(gè)方程組的解為(59915+53?4943)mod3127三1075；

第二個(gè)方程組的解為(59?945+53?49?(一13))mod3127三2347；

第三個(gè)方程組的解為(599(—15)+53?4943)mod3127三780：

第四個(gè)方程組的解為(599(—15)+53?49-(—13))mod3127三2052。

所以，四個(gè)可能的明文為1075,2347,780,2052。

18.橢圓曲線E”(l,6)表示V三f+x+6modll,求其上的所有點(diǎn)，

解：模11的平方剩余有1,4,9,5,3。

x=l,4,6時(shí)，y2=8mod11,無(wú)解，曲線無(wú)與這一x相對(duì)應(yīng)的點(diǎn)；

x=9時(shí)，y2=7mod11,無(wú)解，曲線無(wú)與這一x相對(duì)應(yīng)的點(diǎn)；

x=0時(shí)，y2=6mod11,無(wú)解，曲線無(wú)與這一x相對(duì)應(yīng)的點(diǎn)；

x=2時(shí)，J2=2mod1l,y=4或7；

x