現代密碼學(第4版)一習題參考答案

第1章

1、設仿射變換的加密是：

片1.23(⑼三1+23(mod26)

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

-l

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

驗證你的解密結果。

解；①明文m=THENATIONALSECURITYAGENCY用數字表示為：

m=[197413019814130111842201781924064

13224]

根據對明文中的每一個字符計算出相應的密文字符

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

c=[24221510232472110231413151992724123

111510191]

由此得到密文C=YWPKXYHVKXONPTJCHYBXLPKTB

②使用解密變換驗證加密結果過程如下：

由11*19=1(mod26)知

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

根據Du,2水)三ll1*(c-23)(mod26)=19*(c-23)(mod26),對密文中的每一個字符計算出相應的

明文字符

m=[197413019814130111842201781924064

13224]

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

2、設由仿射變換對-?個明文加密得到的密文為：edsgickxhuklzveqzvkxwkzzukvcuho又已知

明文的前兩個字符為“if”，對該明文解密。

解：設加密變換為c=E，b(m)三a*m+b(mod26)

由題目可知，明文前兩個字符為if,相應密文為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

密文對應的數字表示為：

c=[43186821023720101125214162521102322

10252010212207]

1

根據D9,IO(C)=9*(C-1O)(mod26)=3*(c-10)(mod26),對密文中的每一個字符計算出相應的明

文字符

c=[85241420201317403197818197013100

194072417]

由此得到明文m=ifyoucanreadthisthankateahcer

3、設多表代換密碼中

口13219)’1、

151062521

A=,B=

1017488

2372>□

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

對明文“PLEASESENDMETHEBOOK,MYCREDITCARDNOISSIXONETWOONETHREEEIGHTSIX

ZEROONESIX日GHTFOURNINESEVENZEROTWO”

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

驗證你的結果，其中

,2313205、

.010110

%一=

9111522

、922625,

解：加密時，先將明文分組，每四個一組:

LYGDMOXNLLGNHAPCQZZQZCRG

ZEZJUIEBRRSQNEMVQDJEMXNA

IERPXAKMYRBYTQFMNEMVOME

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

得到明文：PLEASESENDMETHEBOOKMYCRE

DITCARDNOISSIXONETWOONET

HREEEIGHTSIXZEROONESIX日

GHTFOURNINESEVENZEROTWO

解密驗證結果與明文相符。

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

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

b、

解：設矩陣A三

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

(mod26)

(⑶fa丫13)

、8兒(mod26)

,flO

解得：A三

193

第2章

1.3級線性反饋移位寄存器在。3=1時可有4種線性反饋函數，設其初始狀態為

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

3

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

種可能，對應初態(q，4，q)=(l,0,l)。4種線性反饋函數分別記為：

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

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

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

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

m序列

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

2.設n級線性反饋移位寄存器的特征多項式為p(x),初始狀態為

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

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

因為初始狀態不為零，設廠為序列的最小周期。又因為〃(x)IK,所以必存在q(x),

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

又因為定理2T有p(x)A(JC)=^(x),

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

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

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

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

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

生成函數A

*)=44,p(x)A(x)=°(x)工0,的次數不超過〃-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又因為所

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

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

解：由/(%,%,%,%)=%十(十18%%,初態為(％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.設密鑰流是由m=2s級的LFS?產生，其前加+2個比特是(01)*,即s+1個01。問第

ni+3個比特有無可能是1,為什么？

解.：第m+3個比特上不可能出現1,這是由于：

根據線性移位寄存器的的遞推關系有：

%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.設密鑰流是由n級LFSR產生，其周期為2〃-1,i是任一整數，在密鑰流中考慮以下比特

對

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

問有多少形如(5,,5加)=(1,1)的比特對。試證明你的結論。

解：根據p23定理2-7,在G/Q)上的n長m序列在周期為2”-1的m序列中對于

〃—2,長為i的游程有2"一1個，且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個形如區,S刑）=（1,1）的比特對。

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

3級線性反饋移位寄存器產生的，試破譯該密碼系統。

解：由己知可得相應的密鑰流序列為1110100111,又因為是3級線性反饋移位寄存器，可

得以下方程:

%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/

由此可得密鑰流的遞推關系為：4+3=。3勾十G4+2=ai十4+2。

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

序列。2.5節已知，敵手若知道?段長為2n的明密文對就可破譯密鑰流生成器。若敵手僅

知道長為2n-2的明密文對，問如何破譯密鑰流生成器。

解：如果敵手僅僅知道長為2n-2的明密文對，他可以構造出以下的長為2n的明密文對：

不妨設：明文：xxx2...x2n_2x2n_｛xiti

密文：…為“-2y22%

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

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

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

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

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

8.設J-K觸發器中｛6｝和｛4｝分別為3級和4級m序列，且｛%｝=11101001110100…，

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

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

%，ck-\=°

c.=<—

43=1

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

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

｛q｝=11001001010100...o

9.設基本鐘控序列生成器中｛%｝和｛4｝分別為2級和3級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產生｛4｝,其狀態向量為可得q的變化情況如下:

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

輸出序列{4}=100011100111000111011…

第3章

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

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

,,

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

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

(2)對DES進行窮搜索攻擊時，需要在由256個密鑰構成的密鑰空間進行，能否根據⑴的

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

(1)證明：

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

k)R)JP

Li—品

《心十/火，()

64bitcipher—

/R'(/?16LI6)

若將明文和密鑰k同時取補，則加密過程為：

LR<-IP

00

工一&

&-L-i十凡,KJ

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

其中，/(R“，Kj)的作用是將數據的左、右半部分擴展后與密鑰進行逐比特異或運算，

因此/(/?“，KJ=K'j),再經過S盒，并將輸出結果進行置換運算P之后有：

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

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

(2)答：根據⑴的結論進行窮搜索攻擊，可將待搜索的密鑰空間減少一半，即255個。因為

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

種明文情況。

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

證明：

令T(L,R)=(R,L)為左右位置交換函數，Fki=(L十R),則第i次迭代變換為：

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

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

同時，F*L,R)=F式L十以R,ki),R)=(L十f(R,ki)十f(R,ki),R)=(L,R),

即匕產成，

1

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

DES加密過程在密鑰k作用下為：

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

解密過程為：

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

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

3.在DES的EBC模式中，如果在密文分組中有一個錯誤，解密后僅相應的明文分組

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

將影響尸/和尸2的結果。

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

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

對接收者產生什么影響？

答：

(1)在CBC模式中，若密文分組中有一個錯誤&,則解密時明文分組中［，鳥都將受到

影響，而月+"i=l,2,…后的分組都不受影響，即CBC的錯誤傳播長度為2,具有自恢復

能力。

(2)若明文分組P有錯誤，則以后的密文分組都將出現錯誤，但對接收者來說，經過解

密后，除P1有錯誤外，其余的明文分組都能正確恢復。

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

答：

在8比特CFB模式中，若密文有1比特錯誤，則會影響當前分組以及后續分組的解密，

會使解密輸出連續9組出錯，即錯誤傳播的長度為9。

5.在實現IDEA時，最困難得部分是模皆6+1乘法運算。以下關系給出了實現模乘法的一

種有效方法，其中a和b是兩個「比特的非0整數：

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

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

(3)證明〃+

(4)求(。人揣2”)關干q的表達式：

⑸求("md2”)關于4和「的表達式；

(6)用(4)和(5)的結果求r的表達式，說明r的含義。

(1)證明：

假設存在0"國2,弓使得=+1)+。=%(2"+1)+優有

@一%)(2"+1)=6-公因為與k2"，所以一與區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)解：根據。：=夕(2'+1)+/，得

qVG7+r)<2"

(ab)div2n=,

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

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

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

(ab)mod2=<

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

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

r-(abiTod2")-{abdivT)

同理，當g+r之2"時,

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

余數r表示ab的n個最低有效位與ab右移位數n之差。

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

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

答：

(1)在IDEA模乘運算中，必須保證運算構成一個群，因此模數必須為素數，故不能取

2,6o

(2)同一群內的分配律和結合律都成立，但IDEA算法中要保證模數的加法和模數的乘

法，比特異或之間分配律和結合律不成立，因此模加運算不能和模乘運算在同一個群內，即

不能選模2m+1,而在模加運算中必為一個群.

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

證明：

SM4算法的加密輪函數分為加密函數G和數據交換Eo其中G對數據進行加密處理，E

進行數據順序交換。即加密輪函數

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)

因為,

(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,叫)=/

因此，加密函數G是對合的。

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是對合運算。

綜上，加密輪函數是對合的。

根據加密框圖，可將SM4的加密過程寫為：

SM4=GqEG^E…G30EG31R

根據解密框圖，可將SM4的解密過程寫為：

-1

SM4=G3IEG30E...G1EG0R

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

所以，SM4算法是對合的。

第4章

1.證明以下關系：

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

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

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

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

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

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

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

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

2.證明以下關系:

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

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

解：(1)設4mo==則存在整數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)設〃mod〃=%〃mod〃=?;,則存在整數,使得

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

解：因為p=11是素數，且gcd(3,ll)=l,則由Fermat定理可得:

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

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

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

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

解：運算步驟如下表所示：

循環次數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

解：根據中國剩余定理求解該同余方程組，記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二生+時也；&)1110(]”

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

=176modl05=71modl05.

7.計算下列Legendre符號：

2165

59>￡107

=(-1)8=-1

⑵

3、

—=(-1)

53)

32-1

2+17x3

=(-1)=(一1)(一產

3

8.求25的所有本原根。

1

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

即對每個g,只需計算g叫屋。又因為0(24)=24(1-；)(1-}=8,所以25有8個本

原根。

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.證明當且僅當〃是素數時，是域。

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

為Abel群，與〃是否為素數無關；但若＜Z“-{0},x“＞為Abel群，其條件之一

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

得xxy三lmod〃，所以gcd(苞〃)=1,即以〃)="一1,〃為素數。

(2)若〃不是素數，則奴〃)＜〃一1,即至少存在一個XEZ“-{0},使得gc不工〃)X1,即x

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

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

C=1O,求明文

解:因為〃=35=5x7n〃=5/=7,則以〃)=(p-l)(g-l)=4x6=24,所以

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

11.已知，mod〃的運行時間是O(log3〃)，用中國剩余定理改進RSA的解密運算。如果

不考慮中國剩余定理的計算代價，證明改進后的解密運算速度是原解密運算速度的4倍。

證明：RSA的兩個大素因子p,夕的長度近似相等，約為模數〃的比特長度log〃的一半，即

(logn)/2,而在中國剩余定理中，需要對模p和模q進行模指數運算，這與，mod〃的

運行時間規律相似，所以每一個模指數運算的運行時間仍然是其模長的三次幕，即

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

在不考慮中國剩余定理計算代價的情況下，RSA解密運算的總運行時間為兩個模指數運算

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

度是原解密運算速度的4倍。

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

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

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

若敵手得到以上中間結果就很容易分解〃，問敵手如何分解〃O

(2)求解密密鑰d。

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

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),由擴展的

Eucild算法可得d=5。

13.在ElGamal加密體制中，設素數”-71,本原根g-7,

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

對應的密文。

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

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

22

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

所以明文M=30對應的密文為C=(49,57)。

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

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

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

night力口密。

解：由4=(3,4,9,17,35),乘數1=19,模數左=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”相應的密文為(64,67,67,25,0,59,11,64,3,9)0

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

25,2,72,92解密。

解：因為"mod4=177mod67=4mod67，貝ij4x(25,2,72,92)mod67=(33,8,20,33)。

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

“ADRA”。

16.已知枕=pq,p,夕都是素數，x,yGZ*,其Jacobi符號都是1,其中Z：=Z“一{0},

證明：

(1)刈(mod〃)是模〃的平方剩余，當且僅當都是模〃的平方剩余或都是模〃的非

平方剩余。

⑵Jy5(mod〃)是模〃的平方剩余，當且僅當都是模〃的平方剩余或都是模〃的

非平方剩余。

證明：（1）①必要性：若xy（inod，z）是模〃的平方剩余，即存在，使得孫=Jniod〃，而

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

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

pqppqq

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

nnpqpq

當（土）=1時，W（^）=l=＞（-）=l^＞（-）=b即x同時是模p和模》的平方剩余,y也

ppqq

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

當（與二一1時，有g）=_in（2）=_in（與二-1,即無同時是模p和模q的非平方剩

ppqq

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

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

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

pqpq

余；

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

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

ppqq

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

pppq

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

⑵若/y5（mod〃）是模〃的平方剩余，則Vy5同時是模〃和模夕的平方剩余，所以

/35\

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

\P）PP

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

pP

提不:

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

(1)確定1在模〃下的4個平方根。

(2)求明文消息2347所對應的密文。

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

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

組:

x2三1mod53

x2三lmod59

因為(±1>三1mod53,(±1尸三1mod59,所以xm±lmod53,x三±1mod59。經組合可

得到以下四個方程組：

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

<<<?

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

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

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

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

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

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

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

(2)2347對應的密文為c三23472mod3127三1762。

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

x2=1762mod53=13

<

X2=1762mod59=51

因為(±15>三13mod53,(±13>三51mod59,所以x三±15mod53,x三±13mod59,經

組合可得到以下四個方程組：

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

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

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

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

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

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

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

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

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

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

x=l,4,6時，y2=8mod11,無解，曲線無與這一x相對應的點；

x=9時，y2=7mod11,無解，曲線無與這一x相對應的點；

x=0時，y2=6mod11,無解，曲線無與這一x相對應的點；

x=2時，J2=2mod1l,y=4或7；

x