现代密码学（第4版）-习题参考答案

现代密码学(第4版)一习题参考答案

第1章

1、设仿射变换的加密是：

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

对明文“THENATIONALSECURITYAGENCY”加]密，并使用解密变换

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

验证你的解密结果。

解：①明文m=THENATIONALSECURITYAGENCY用数字表示为：

m=[197413019814130111842201781924064

13224]

根据对明文中的每一个字符计算出相应的密文字符

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

c=[24221510232472110231413151992724123

111510191]

由此得至U密文C=YWPKXYHVKXONPTJCHYBXLPKTB

②使用解密变换验证加密结果过程如下：

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

(注：求模逆元可以通过欧几里得算法或者直接穷举1~25)

根据Du,23(c)三llT*(c-23)(mod26)=19*(c-23)(mod26),对密文中的每一个字符计算出相应的

明文字符

m=[197413019814130111842201781924064

13224]

由此得至I」m=THENATIONALSECURITYAGENCY,解密结果与明文一致，正确。

2、设由仿射变换对一个明文加密得到的密文为：edsgickxhuklzveqzvkxwkzzukvcuh。又已知

明文的前两个字符为“if”，对该明文解密。

解：设加密变换为c=Ea,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

因此解密变换为D94o(c)三9-1*(010)(mod26)

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

密文对应的数字表示为：

c=[43186821023720101125214162521102322

10252010212207]

根据D9」O(C)三T*(c-10)(mod26)=3*(c-10)(mod26),对密文中的每一个字符计算出相应的明

文字符

c=[85241420201317403197818197013100

194072417]

由此得到明文m=ifyoucanreadthisthankateahcer

3、设多表代换密码中

<313219、,1、

151062521

A=,B=

1017488

2372;□

加密为：G=+B(mod26)

对明文“PLEASESENDMETHEBOOK,MYCREDITCARDNOISSIXONETWOONETHREEEIGHTSIX

ZEROONESIX日GHTFOURNINESEVENZEROTWO”

用解密变换A/,.=A-'+fi(mod26)

验证你的结果，其中

’2313205、

,010110

A-i-

19111522

、922625,

解：加密时，先将明文分组，每四个一组:

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

同上，解密时，先将密文分组，再代入解密变换：M,.=A-'+B(mod26)

得到明文：PLEASESENDMETHEBOOKMYCRE

DITCARDNOISSIXONETWOONET

HREEEIGHTSIXZEROONESIX日

GHTFOURNINESEVENZEROTWO

解密验证结果与明文相符。

4、设多表代换密码C,=AM,+8(irod26)中，A是2X2矩阵,B是零矩阵,又知明文“dont”

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

faby

解：设矩阵A三

(cd)

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

(mod26)

(1013]

解得：A三[923J

第2章

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

(4，4,4)=(1,0,1),求各线性反馈函数的输出序列及周期。

23

解:设3级线性反馈特征多项式为p(x)=1+qx+c2x+c3x，若C3=1贝IJq,c2共有22=4

种可能，对应初态(q,4,q)=(1,0,1)。4种线性反馈函数分别记为：

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

P2(x)=l+x+d由定义2-3得是不可约多项式，输出序列。=1010011101…

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

E,(x)=l+f+x3不可约多项式，输出序列。=1011100101…，周期p=7是

m序歹！J

23

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

2.设n级线性反馈移位寄存器的特征多项式为p(x),初始状态为

(o1,a2,-.,a„_„an)=(00---01),证明输出序列的周期等于p(x)的阶。

解：p(x)的阶定义为〃(刈产-1的最小的〃。

因为初始状态不为零，设r为序列的最小周期。又因为p(x)\xp-\,所以必存在q(x),

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

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

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

而q(x)的次数为p-〃，0(x)的次数不超过〃一1,(/'一l)A(x)的次数不超过

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

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

即周期为p(x)的阶,若p(x)是n次不可约多项式，则序列的最小周期等于〃(无)的阶。

生成函数4月=少｛

P(X)A(X)=°(X)H(),0(x)的次数不超过〃-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)。又因为mWr,所

以r=机。

3.设〃=4,/(q,%,%,〃4)=q㊉。4㊉1㊉。2。3，初始状态为(々］,。2，4，4)=。，1，°」)，

求此非线性反馈移位寄存器的输出序列及周期。

解:由3M4)=4㊉。4㊉1㊉。26，初态为(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.设密钥流是由加=2s级的LFSR产生，其前m+2个比特是(01)用，即s+1个01。问第

m+3个比特有无可能是1,为什么？

解：第m+3个比特上不可能出现1,这是由于：

根据线性移位寄存器的的递推关系有：

为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.设密钥流是由n级LFSR产生，其周期为2"-1,i是任一整数，在密钥流中考虑以下比特

对

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

问有多少形如(S/,Sj+1)=(1,1)的比特对。试证明你的结论。

解：根据p23定理2-7,在GF(2)上的n长m序列在周期为2"-1的m序列中对于

1<iW"-2,长为i的游程有2"-"个，且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个形如(S.,Sj+l)=(1,1)的比特对。

6.已知流密码的密文串1010110110和相应的明文串0100010001,而且还已知密钥流是使用

3级线性反馈移位寄存器产生的，试破译该密码系统。

解：由已知可得相应的密钥流序列为1110100111,又因为是3级线性反馈移位寄存器，可

得以下方程:

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

由此可得密钥流的递推关系为：ai+3=ciai㊉qq+2=ai㊉aj+2。

7.若GF(2)上的二元加法流密码的密钥生成器是n级线性反馈移位寄存器,产生的密钥是m

序列。2.5节已知，敌手若知道一段长为2n的明密文对就可破译密钥流生成器。若敌手仅

知道长为2n-2的明密文对，问如何破译密钥流生成器。

解：如果敌手仅仅知道长为2n-2的明密文对，他可以构造出以下的长为2n的明密文对：

不妨设：明文：x1x2...x2„_2x2n_lx2n

密文：一必…%

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

必……当"-2为己知的，为未知的。

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

共有16种组合方案，分别破解得到密钥流，在破解的结果中符合m序列的性质密钥流即为

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

8.设J-K触发器中｛q｝和｛4｝分别为3级和4级m序列，且｛%｝=111O1OO111O1OO--..

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

解：由J-K触发器可知,=（《+bk+\）ck_i+ak

此时｛4｝和｛仇｝分别为3级和4级m序列，（3,4）=1则｛/｝的周期为

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

｛q｝=H001001010100...o

9.设基本钟控序列生成器中｛应｝和｛仇｝分别为2级和3级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产生｛4｝,其状态向量为％」可得％的变化情况如下:

2b3b3b4b5b5b6bob()b|b2b2b3b4b4b5b6b6bo。1,巧

输出序列{0}=100011100111000111011…

第3章

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

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

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

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

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

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

(1)证明：

设L,和氏分别不是第/轮DES变换的左右部分，i=0,l，…,16,则加密过程为:

4一

“

一

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

若将明文和密钥k同时取补，则加密过程为：

LR<-IP

00

L—心

R；-L艮国)

Mbitciphers—IP'(RibLuJ

其中，f(Ri，Kj)的作用是将数据的左、右半部分扩展后与密钥进行逐比特异或运算，

因此/(R,T，KJ=/(R',T，K',),再经过S盒，并将输出结果进行置换运算P之后有：

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

RLE。同时有〃=乙，所以明文P与密钥K同时取补后有丫'=。£又3)。

(2)答：根据⑴的结论进行穷搜索攻击，可将待搜索的密钥空间减少一半，即255个。因为

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

种明文情况。

2.证明DES解密变换是加密变换的逆。

证明：

令T(L,R)=(R,L)为左右位置交换函数，Fki=(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-',

同时，F^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加密过程在密钥k作用下为：

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

解密过程为：

DESJ'=1产'F-TFkJ…F、sTFk、6(IP)，

所以，(DESJ')(DESQ=1，即解密变换是加密变换的逆。(得证)

3.在DES的EBC模式中，如果在密文分组中有一个错误，解密后仅相应的明文分组

受到影响。然而在CBC模式中，将有错误传播。例如在图3-11中C/中的一个错误明显地

将影响Pi和尸2的结果。

(1)P2后的分组是否受到影响？

(2)设加密前的明文分组Pi中有一个比特的错误，问这一错误将在多少个密文分组中传播？

对接收者产生什么影响？

答：

(1)在CBC模式中，若密文分组中有一个错误G,则解密时明文分组中4《都将受到

影响，而i=l,2,…后的分组都不受影响，即CBC的错误传播长度为2,具有自恢复

能力。

(2)若明文分组Pi有错误，则以后的密文分组都将出现错误，但对接收者来说，经过解

密后，除P1有错误外，其余的明文分组都能正确恢复。

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

答：

在8比特CFB模式中，若密文有1比特错误，则会影响当前分组以及后续分组的解密，

会使解密输出连续9组出错，即错误传播的长度为9。

5.在实现IDEA时，最困难得部分是模2侨+1乘法运算。以下关系给出了实现模乘法的一

种有效方法，其中a和b是两个n比特的非0整数：

(1)证明存在唯一的非负整数q和r使得"6=4(2"+D+「；

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

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

(4)求出丫2")关于q的表达式；

(5)求("mod2”)关于q和「的表达式；

(6)用(4)和(5)的结果求r的表达式，说明r的含义。

(1)证明：

假设存在[”，％，弓使得­=41(2"+1)+4=%(2"+1)+5,有

⑷-%)(2"+l)=q-2，因为0<不&<2",所以|八一弓区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)解:根据ab=g(2"+l)+r,得

qif(q+r)<2"

(ab)div2n—<

q+1if{q+r)>T

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

q+rif(q+r)<2n

(ab)mod2n=<

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

(6)解：当皿=4(2"+1)+=时,根据(皿)由诅"=q及(皿)mod2"=q+r得,

r=(ahm)d2n)-(ahdiv2n)

同理，当夕+r之2"时,

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

余数r表示ab的n个最低有效位与ab右移位数n之差。

6.(1)在IDEA的模乘运算中，为什么将模乘取为216+1而不是23？

(2)在IDEA的模加运算中，为什么将模乘取为2'6而不是216+1?

答：

(1)在IDEA模乘运算中，必须保证运算构成一个群，因此模数必须为素数，故不能取

216,

(2)同一群内的分配律和结合律都成立，但IDEA算法中要保证模数的加法和模数的乘

法，比特异或之间分配律和结合律不成立，因此模加运算不能和模乘运算在同一个群内，即

不能选模2历+1,而在模加运算中必为一个群.

7.证明SM4算法满足对合性，即加密过程和解密过程一样，只是密钥使用的顺序相反。

证明：

SM4算法的加密轮函数分为加密函数G和数据交换E。其中G对数据进行加密处理，E

进行数据顺序交换。即加密轮函数

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)

因为,

⑹)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

因此，加密函数G是对合的。

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是对合运算。

综上，加密轮函数是对合的。

根据加密框图，可将SM4的加密过程写为：

SM4=GQEG^E...G30EG31R

根据解密框图，可将SM4的解密过程写为：

SM4T=G31EG30E...G1EG0R

比较SM4与SM4」可知，运算相同，只有密钥的使用顺序不同。

所以，SM4算法是对合的。

第4章

1.证明以下关系：

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

(2)a=bmodnfWOb=amodn；

(3)a=bmodnfb=cmodn»则々三。mod〃。

解：(1)设amod〃=G，bmod〃=/;,由题意得吃二5，且存在整数，%,使得

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

(2)已知。三〃mod/z,则存在整数Z，使得Q=ki+/?nb=(-Z)〃+a,证得三amod〃。

(3)已知a三〃mod〃力三c、mod〃，则存在整数，次，使得

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

2.证明以下关系:

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

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

解：(1)设4mod〃=c，0mod〃=以，则存在整数，上,使得

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)设々mod"=弓,。mod〃=5,则存在整数，攵，使得

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

解：因为〃=11是素数，且gcd(3,ll)=l,则由Fermat定理可得:

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

又根据性质[(〃mod〃)x(bmod/2)]modn=(axb)modn,可得:

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

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

解：运算步骤如下表所示：

循环次数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

解：根据中国剩余定理求解该同余方程组，记4=2,%=1,%=1，叫=3,牡=5,m,=7,

M=町x机,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.计算下列Legendre符号：

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

⑵

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

=1

8.求25的所有本原根。

解：因为夕(25)=25(1—5=20=22x5,所以°(25)的所有不同的素因子为1=2,=5,

即对每个只需计算叱又因为以所以有

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

原根。

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.证明当且仅当〃是素数时，<Z",+“，x“〉是域。

证明：(1)若<Z“,+“，x”>是域，则<Z,,+“>,<Z“-{0},x“>均为Abel群。显然

＜Z",+”＞为Abel群，与〃是否为素数无关；但若＜Z“-{O},x“＞为Abel群，其条件之一

必须保证对任意XGZ“-{0}有模乘法逆元，即对任意xeZ“-{0},有yeZ,-{0},使

得xxy三lmod〃，所以gcd(尤,〃)=1,即〃为素数。

(2)若〃不是素数，则双〃)＜〃-1,即至少存在一个xeZ“一{0},使得gcd(x,〃)Hl,即x

无模乘法逆元，因此不能保证＜Z〃-{0},x“＞均为Abel群,即＜Z“,+“，x”＞不是域。

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

C=10,求明文

解：因为“=35=5x7=＞p=5,q=7,则奴〃)=(p_l)(q_l)=4x6=24,所以

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

11.已知cdmodn的运行时间是OQog]〃)，用中国剩余定理改进RSA的解密运算。如果

不考虑中国剩余定理的计算代价，证明改进后的解密运算速度是原解密运算速度的4倍。

证明：RSA的两个大素因子p,q的长度近似相等，约为模数〃的比特长度log〃的一半，即

(log/?)/2,而在中国剩余定理中，需要对模p和模夕进行模指数运算，这与c"mod〃的

运行时间规律相似，所以每一个模指数运算的运行时间仍然是其模长的三次累，即

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

在不考虑中国剩余定理计算代价的情况下，RSA解密运算的总运行时间为两个模指数运算

的运行时间之和，即。(log3〃)/8+O(log3〃)/8=O(log3〃)/4,证得改进后的解密运算速

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

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

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

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

若敌手得到以上中间结果就很容易分解〃，问敌手如何分解〃。

(2)求解密密钥

解：(1)由以上中间结果可得：

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

Eucild算法可得d=5。

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

(1)如果接收方B的公开钥是为=3,发送方A选择的随机整数左=2,求明文M=30所

对应的密文。

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

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

k22

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

所以明文M=30对应的密文为C=(49,57)。

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

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

14.设背包密码系统的超递增序列为(3,4,9/7,35),乘数r=19,模数左=73,试对good

night力口密。

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

15.设背包密码系统的超递增序列为(3,4,8,17,35),乘数，=17,模数％=67,试对

25,2,72,92解密。

解：因为"mod%=17一|mod67=4mod67，则4x(25,2,72,92)mod67=(33,8,20,33)。

所以其对应的明文分组为(0()001,0010(),10010,000()1),由课本120页表4-7可得明文为

“ADRA”。

16.己知〃=网，p,q都是素数，x,ywZ：,其Jacobi符号都是1,其中Z：=Z“一{0},

证明：

⑴肛(mod〃)是模〃的平方剩余，当且仅当都是模〃的平方剩余或都是模〃的非

平方剩余。

(2)Vy5(mod〃)是模〃的平方剩余，当且仅当尤,y都是模”的平方剩余或都是模〃的

非平方剩余。

证明：（1）①必要性：若孙（mod〃）是模〃的平方剩余，即存在f使得xy=rmod”，而

n-pq,显然必有xy=rmodp,xy-rmodg,所以刈也同时是模p和模q的平方剩余,

即（现）=1,（现）=1n（£）£）=1,（-）A=1.

pqppqq

又由题意得（2）=1,（2）=1,BP（-）（-）=1,（-）（-）=1»所以：

nnpqpq

当（±）=1时，有（2）=ln（2）=ln（土）=1,即x同时是模p和模q的平方剩余，y也

ppqq

同时是模p和模夕的平方剩余，即都是模"的平方剩余；

当（土）=7时，有（马=_10（马=_1=（为=_1,即x同时是模p和模q的非平方剩

ppqq

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

②充分性：若都是模“的平方剩余，则演y也是模p和模9的平方剩余，即

（土）=（当=（马=（»）=1,即孙同时是模p和模q的平方剩余，所以孙是模〃的平方剩

pqpq

余；

若演y都是模〃的非平方剩余，则它们对于模p和模q至少有一种情况是非平方剩余，不妨

设（土）=-1,=（2）=一1，则有（与=-1,（马=一1,即尤,y也都是模p和模q的非平方剩

ppqq

余。所以（土）（上）=（?）=（—1）（—1）=1,同理（与）=1,即孙同时是模p和模q的平方剩

pppq

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

⑵若x，5（mod〃）是模〃的平方剩余，则丁尸同时是模p和模q的平方剩余，所以

<35\

4L=1=（二）3（2）5,由于勒让德符号的偶数次方肯定为1（p|x情况除外），即有

<pJpP

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

pP

提示:

目讣1

V、

XX|yy

、p人“p人力

=[£(»

17.在Rabin密码体制中设p=53,q=59：

(1)确定1在模〃下的4个平方根。

(2)求明文消息2347所对应的密文。

(3)对上述密文，确定可能的4个明文。

解：(1)已知/三lmod3127,〃=pq=53x59=3125,由中国剩余定理可得到等价方程

组:

x1=1mod53

x2simod59

因为(±1)2三1mod53,(±iy三lmod59,所以x三土lmod53,x三±lmod59。经组合可

得到以下四个方程组:

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

x=lmod59x=-lmod59x=lmod59x=-lmod59

]

根据中国剩余定理M=59,mod53=9,M2=53,M；mod59=49,则有:

第一个方程组的解为(59・9・l+53・49・l)mod3127ml；

第二个方程组的解为(59・9・l+53・49・(—l))mod3127三1061；

第三个方程组的解为(59•9•(—1)+53・49・1)mod3127三2066；

第四个方程组的解为(59.9・(—1)+53・49.(—l))mod3127三3126。

所以，1mod/?的四个平方根为1mod()61mod〃,2066mod〃,3126modn。

(2)2347对应的密文为c三23472mod3127三1762。

(3)解密即解尤2三I762mod3127,由中国剩余定理可得到等价方程组：

X2三1762mod53=13

x2三1762mod59