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

《现代密码学（第4版）—习题参考答案.pdf》由会员分享，可在线阅读，更多相关《现代密码学（第4版）—习题参考答案.pdf（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、现代密码学(第4版)一习题参考答案第1章1、设仿射变换的加密是：En 23(，)-1+23(mod 26)对明文“THE NATIONAL SECURITY AGENCY”加 密，并使用解密变换A 2 3 =1 r(c-23)(m od26)验证你的解密结果。解：明文m=THE NATIONAL SECURITY AGENCY用数字表示为：m=19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 17 8 19 24 0 6 413 2 24根据Eu,23(m)Ell*m+23(mod 2 6),对明文中的每一个字符计算出相应的密文字符c=24 22 15 10 23 2

2、4 7 21 10 23 14 13 15 19 9 2 7 24 1 2311 15 10 19 1 由此得至U密文 C=YWPKXYHVKXONPTJCHYBXLPKTB使用解密变换验证加密结果过程如下：由 11*19=1(mod 26)知 H-19(注：求模逆元可以通过欧几里得算法或者直接穷举125)根 据 Du,23(c)三 llT*(c-23)(mod 26)=19*(c-23)(mod 2 6),对密文中的每一个字符计算出相应的明文字符m=19 7 4 13 0 19 8 14 13 0 11 18 4 2 20 17 8 19 24 0 6 413 2 24由此得至I m=THE

3、 NATIONAL SECURITY AGENCY,解密结果与明文一致，正确。2、设由仿射变换对一个明文加密得到的密文为：edsgickxhuklzveqzvkxwkzzukvcuh。又已知明文的前两个字符为“if”，对该明文解密。解：设加密变换为 c=Ea,b(m)=a*m+b(mod 26)由题目可知，明文前两个字符为i f,相应密文为e d,即有：E(i)=e,4=a*8+b(mod 26)，(i=8,e=4),E(f)=d,3=a*5+b(mod 26),(f=5,d=3),由上述两式可求得，a=9,b=10因此解密变换为D94o(c)三 9-1*(010)(mod 26)又由3*9三

4、 1(mod 26)可知9,=3密文对应的数字表示为：c=4 3 18 6 8 2 10 23 7 20 10 11 25 21 4 16 25 21 10 23 2210 25 20 10 21 2 20 7 根据D9O(C)三 T*(c-10)(mod 26)=3*(c-10)(mod 2 6),对密文中的每一个字符计算出相应的明文字符c=8 5 24 14 20 2 0 13 17 4 0 3 19 7 8 18 19 7 0 13 10 019 4 0 7 2 4 17 由此得到明文 m=ifyoucanreadthisthankateahcer3、设多表代换密码中 /=0 ,nr|。

5、即周期为p(x)的阶,若p(x)是n次不可约多项式，则序列的最小周期等于(无)的阶。生成函数4月=少 p(xP(X)A(X)=(X)H(),0(x)的次数不超过-1。A(x)=Z 4 x TMlq +Q)X+1P(xp(x)(q -a2x-1-arxr)=(x)(xr-1 jp(x)不可约，所以g c d(p(x),0(x)=l,p(x)|(x -l)。又因为mWr,所以r=机。3 .设=4,/(q,%,%,4)=q 。4 1 。2。3，初始状态为(,。2，4，4)=。，1，)，求此非线性反馈移位寄存器的输出序列及周期。解:由3 M 4)=4。4 1。2 6，初 态 为(4，%吗,。4)=(1

6、，1，1)。线性递归可得：a5=1 110 =14=1 110 =1%=0111 =1%=1 111=0“9=1 0 11=14()=1 1 1 0 =1可以得到输出序列为(110 11110 11)，周期为P=54 .设密钥流是由加=2s级 的 L FS R 产生，其前m+2 个比特是(0 1)用，即s+1个 0 1。问第m+3 个比特有无可能是1,为什么？解：第 m+3 个比特上不可能出现1,这是由于：根据线性移位寄存器的的递推关系有：为s+i=。色S c 2 a2S T 0/=马s+2=G2 s+l 。/2s ，C2S32=1从 而 有a1=0,a?1,2s+i ，a 2s*2 L 代入

7、下式J有：为5+3 =Cia2s+2 C23 2s+1 ,C 2S&3 =05 .设密钥流是由n 级 L FS R 产生，其周期为2 -1,i是任一整数，在密钥流中考虑以下比特对(S j,SM),(S)+1,Si+2),.(S j+2 _ 3,S j+2”_ 2)，(S,+2._ 2，,.+2-l)问有多少形如(S/,S j+1)=(1,1)的比特对。试证明你的结论。解：根据p23 定理2-7,在 G F(2)上的n 长 m 序 列 在 周 期 为 2-1 的m序 列 中 对 于1 Ji r1 o0 L(i 1 Y1i i i i|A|=1 1 0 =1 n 1i o i bi p0 =1J

8、bi i、0 11 0,ii0(c 3 c 2。)=(0 10)11 1、0 1=(10 1)1 0,由此可得密钥流的递推关系为：ai+3=ciaiq q+2=aiaj+2。7.若 G F(2)上的二元加法流密码的密钥生成器是n 级线性反馈移位寄存器,产生的密钥是m序列。2.5节已知，敌手若知道一段长为2 n 的明密文对就可破译密钥流生成器。若敌手仅知道长为2n-2的明密文对，问如何破译密钥流生成器。解：如果敌手仅仅知道长为2n-2的明密文对，他可以构造出以下的长为2n的明密文对：不妨设：明文：x1x2.x2_2x2n_lx2n密文：一必%其中：王 W”-2为已知的，X 21.X 2 为未知的

9、。必 当-2为己知的，为未知的。的 可 能 取 值 为 1，l b。的可能取值为 oo,。1,io,1。共 有 16 种组合方案，分别破解得到密钥流，在破解的结果中符合m序列的性质密钥流即为正确的方案，有可能不唯一。8.设 J-K触发器中 q 和 4 分别为3级和4级 m序列，且%=111O 1O O 111O 1O O-.4 =0 0 10 110 110 110 0 0 0 0 10 110 110 110 0 0 求输出序列 9 及周期。解：由J-K触发器可知,=（+bk+）ck_i+ak此 时 4和 仇分 别 为 3 级 和 4 级m 序 列，（3,4）=1则 /的 周 期 为（23-

10、1）（24-1）=7 x15 =10 5。q =H0 0 10 0 10 10 10 0.o9.设基本钟控序列生成器中 应 和 仇 分别为2 级 和 3 级 m序列，且%=10 110 1，bk =10 0 110 110 0 110 1 求输出序列匕 及周期。解：令基本钟控序列生成器中 4 的周期为P-仇 的周期为必，则输出序列 q 的周期为 =-,W =q=2,P =2?-1=3,=23-1 =7g c d（w,p2）i=0n P=3x 7g c d(2,7)=21 o记 L FS R 2产生 4 ,其状态向量为 可得的变化情况如下:2 b 3 b 3 b 4 b 5 b 5 b 6 b

11、o b()b|b 2 b 2 b 3 b 4 b 4 b 5 b 6 b 6 b o。1,巧输出序列 0 =10 0 0 1110 0 1110 0 0 1110 11 第3章1.(1)设M，和M的逐比特取补，证明在D ES中，如果对明文分组和加密密钥都逐比特取补，那么得到的密文也是原密文的逐比特取补，即：如果 Y=DESK(X),那么 Y，=DESK(X，)提示：对任意两个长度相等的比特串A和B,证明(AB)=A eB。(2)对D ES进行穷搜索攻击时，需要在由256个密钥构成的密钥空间进行，能否根据(1)的结论减少进行穷搜索攻击时所用的密钥空间。(1)证明：设L,和 氏分别不是第/轮D E

12、S变换的左右部分，i=0,l，,16,则加密过程为:一“4一Mbi t ci ph e rs/P-f/?6Zl 6)若将明文和密钥k同时取补，则加密过程为：L R -IP0 0L 心R；-L艮国)Mbi t ci ph e rs IP (Ri bLuJ其中，f(R i，Kj)的作用是将数据的左、右半部分扩展后与密钥进行逐比特异或运算，因此/(R,T，K J =/(R,T，K,),再 经 过S盒，并将输出结果进行置换运算P之后有：R：一 乙/(R,T，M/(R,T,K J ,而&-J ,所 以 有RLE。同 时 有 =乙，所以明文P与密钥K同时取补后有丫=。又3)。(2)答：根据的结论进行穷搜索

13、攻击，可将待搜索的密钥空间减少一半，即255个。因为给定明文x,则K =D E S/X),由知Y2=D E S式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-,同时，FL,R)=F式 L f(R,ki),R)=(L f(R,ki)f(R,ki),R)=(L,R),即 Fki=F j,：.(FdXTFJ=FkiFki=

14、I n(E=F J,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模式中

15、，若密文分组中有一个错误G,则解密时明文分组中4都将受到影响，而i=l,2,后的分组都不受影响，即CBC的错误传播长度为2,具有自恢复能力。(2)若明文分组Pi有错误，则以后的密文分组都将出现错误，但对接收者来说，经过解密后，除P1有错误外，其余的明文分组都能正确恢复。4.在 8比特C F B 模式中，如果在密文字符中出现1 比特的错误，问该错误能传播多远？答：在 8比特C F B 模式中，若密文有1 比特错误，则会影响当前分组以及后续分组的解密，会使解密输出连续9组出错，即错误传播的长度为9。5 .在实现I D E A 时，最困难得部分是模2 侨+1 乘法运算。以下关系给出了实现模乘法的一种

16、有效方法，其中a 和 b是两个n比特的非0整数：(1)证明存在唯一的非负整数q和 r 使得 6 =4(2 +D +；(2)求 q和 r 的上下界；(3)证明。+2向；(4)求出 丫 2 )关于q的表达式；(5)求(m o d 2”)关于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 mod(2n+l)2n,显然，a 和 b的最大值均为2 -1,则有然”=22-2*1=(2 (2 +1)

17、-2 x(2 +l)+2 2 1)=2 _32 +1 2 +1 2+1JO 2)所以，,7 =0,炉(=1)(3)证明：q+r 2n+2 -3 2n+(4)解:根据 ab =g(2 +l)+r,得(ab)di v2n q i f(q+r)T(5)解：根据出?=第2 +1)+一，得q+r(ab)m o d 2n=i f(q+r)2(6)解：当 皿=4(2 +1)+=时,根 据(皿)由诅 =q及(皿)mod 2 =q +r 得,r=(ah m)d 2n)-(ah di v2n)同理，当夕+r 之2时,r=(ab mod 2)-(abdi vT)+2 +1余数r 表示ab 的 n个最低有效位与ab

18、右移位数n 之差。6.(1)在 I D E A 的模乘运算中，为什么将模乘取为2 1 6 +1 而不是2 3？(2)在 I D E A 的模加运算中，为什么将模乘取为2 6而不是21 6+1?答：(1)在 ID E A 模乘运算中，必须保证运算构成一个群，因此模数必须为素数，故不能取21 6,(2)同一群内的分配律和结合律都成立，但 I D E A 算法中要保证模数的加法和模数的乘法，比特异或之间分配律和结合律不成立，因此模加运算不能和模乘运算在同一个群内，即不能选模2 历+1,而在模加运算中必为一个群.7.证明S M 4 算法满足对合性，即加密过程和解密过程一样，只是密钥使用的顺序相反。证明

19、：S M 4 算法的加密轮函数分为加密函数G和数据交换E。其中G对数据进行加密处理，E进行数据顺序交换。即加密轮函数A =G tE其中，G t=G i(X i，X i+i，M+2，X i+3,%)(i =0,1,2，,31)=(X j T(X i+i,X i+2，X i+3，r k)X i+i,X i+2，X i+3)E(X i+4，(X i+i，X i+2，M+3)=(X i+i，X i+2，X i+3),X i+4),(i =0,1,2，31)因为,)2=(X i 7(Xi+i，Xi+2，M+3，rkD，Xi+i，Xi+2，Xi+3，rk i)=(Xi-T(Xi+i，Xi+2，Xi+3，r

20、/Q)7(Xi+i，Xi+2，Xi+3，rki),X i+i，Xi+2，Xi+3，rk i)=何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=GQEGE.G3 0E G31R根据解密框图，可将SM 4的解密过程写为：SM4T=G31E G30E .G1E G0R比较SM4与 SM4 可知，运算相同，只有密钥的使用顺序不同。所以，SM4

21、算法是对合的。第4章1.证明以下关系：(1)(am odn)=(Jbm odn),则 a 三bm od；(2)a=b m o d n f W O b=am odn；(3)a=b m o d n f b=c m o d n 则 三。m od。解：(1)设am o d =G，bm od =/;,由题意得吃二5，且存在整数，%,使得a=j n+ra,b=kn+rh a b=(j -k)n,即|a /7,证得三人m od。(2)已知。三m od/z,则存在整数Z，使得Q=k i+/?n b =(-Z)+a,证 得 三 am od。(3)已知a 三m od力三c、m od，则存在整数，次，使得a=j n

22、+b,b=kn+c=a=(/+左)+c,证得 a 三 cm od。2.证明以下关系:(1)(am o dn)-(bm o d 月 m o dn-(a-h)m o dn；(2)(am o dn)x(bm o dn)m o dn=(axh)m o dn。解：(1)设4m o d =c，0m o d =以，则存在整数，上,使得a=j n+ra,b=kn+rb a-h =(j-k)n+(ra-rb)=ra-rb=-(j-k)n-h(a-b)=(-与)m o d n-(a-b)m o d n.即(m o d n)-(b m o d )m o d n=(a-b)m o d n 0(2)设 m o d =弓

23、,。m o d =5,则存在整数，攵，使得a=j n-ra,b=kn+rb n a x b =(Jkn+m+行 口 +二%n=-(jk n+krJn+S x b)=(7;)m o d n=(ax b)m o d n.即(m o dn)x(hm o dn)m o dn=(axb)m o dn。3.用 F er m a t 定理求 32 m o d 11 o解：因为=1 1 是素数，且g c d(3,l l)=l,则由F er m a t 定理可得:3)三 1 m o d 11 n。心三 1 m o d 11；又根据性质(m o d )x(bm o d/2)m o dn=(axb)m o dn,可

24、得:3201 m o d 11=(3I 0)20)m o d 11)x(3 m o d 11)m o d 11 =3m o d 11。4.用推广的E u c l i d 算法求6 7 m o d l 19 的逆元。解：运算步骤如下表所示：循环次数QX1X2X3Y i丫2丫3初值10119016 711016 71-15 2211-15 2-121533-12154-77424-77-9161所以 6 77 m o d l 19 =16。5.求 g c d(46 5 5,12075)。解：由E u c l i d算法，得：12075 =2x 46 5 5 +276 546 5 5 =1x 276

25、 5 +18 9 0276 5=1x 18 9 0+8 7518 9 0=2x 8 75 +1408 75 =6 x 140+35140=4x 35 +0所以 g c d(46 5 5,12075)=35。x=2 m o d 36.求解下列同余方程组：(X三l m o d 5x=1 m o d 7解：根据中国剩余定理求解该同余方程组，记4=2,%=1,%=1，叫=3,牡=5,m,=7,M=町 x 机,x丐=105 ,则有M=35,M m o d 町=35 T m o d 3=2,町m o dm2=21T m o d 5 =1,Mi=15,M-m o d 吗=15T m o d 7=l.m,所以

26、方程组的解为x=+M2M a2+)m o d M=(35 x 2x 2+21x l x l +15 x l x l)m o d l 05=176 m o d l 05 =71m o d l 05.7.计算下列L eg en d r e符号：解:圆=(-1)小=-1(-1)2+：X3)=(1(|)=(-1)(-1)=18.求25的所有本原根。解：因为夕(25)=25(1 5 =20=22x5,所以(25)的所有不同的素因子为1=2,即对每个g,只需计算8叱 又 因 为 以24)=24(l g)(l；)=8,所以25有8原根。=5,个本I10=lmod25,I4=lmod25；3=24mod25,

27、34=6mod25；5=0mod25,5=0mod25；7川=24moe125,74=lmod25；910=lmod25,94=Hmod25；lf=lmod25,ll4=16mod25；1310=24mod25,134=llmod25；15=0mod25,154=0mod25；1710=24mod25,174=21 mod25；W=lmod25,194=21mod25；2110=lmod25,214=6mod25；2310=24mod25,234=16mod25；210=24mod25 24=16mod25；410=1 mod25,44=6mod25；610-lmod25,64=21 mod2

28、5；8,0=24mod25,84=21mod25；IO10=0mod25,104=0mod25；1210=24mod25,124=Hmod25；1410=lmod25,144=16mod25；16l0=lmod25,164=llmod25；1810=24 mod 25,184=1 mod 25；2O10=0mod25,204=0mod25；2210=24mod25,224=6 mod 25；24=1 mod 25,244=1 mod 25；满足 g 1 w 1 mod 25 且 g4Hlmod 25 的 g 为 25 的本原根，即 2,3,8,12,13/7,22,239.证明当且仅当是素数时

29、，Z,+“，x“是域。证明：(1)若 是域，则,均为 Abel 群。显然Z,+”为A b el群，与是否为素数无关；但若Z“-O ,x“为A b el群，其条件之一必须保证对任意XGZ“-0有模乘法逆元，即对任意x e Z“-0,有yeZ,-0,使得x x y三l m o d，所以g c d(尤,)=1,即为素数。(2)若不是素数，则双)-1,即至少存在一个x e Z“一0,使得g c d(x,)H l,即x无模乘法逆元，因此不能保证 Z -0,x“均为A b el群,即Z“,+“，x”不是域。10.设通信双方使用R S A加密体制，接收方的公开钥是(e,)=(5,35),接收到的密文是C =

30、1 0,求明文解：因为“=3 5=5x 7=p =5,q =7,则奴)=(p _ l)(q _ l)=4 x 6=2 4 ,所以d m e m o d Q()三 5T m o d 24=5 m o d 2 4,即明文 M 三 C m o d n =1 05 m o d 3 5=5。1 1 .已知cd m o d n的运行时间是O Q o g )，用中国剩余定理改进R S A的解密运算。如果不考虑中国剩余定理的计算代价，证明改进后的解密运算速度是原解密运算速度的4倍。证明：R S A的两个大素因子p,q的长度近似相等，约为模数的比特长度l o g的一半，即(l o g/?)/2,而在中国剩余定理

31、中，需要对模p和模夕进行模指数运算，这与c m o d的运行时间规律相似，所以每一个模指数运算的运行时间仍然是其模长的三次累，即O (l o gn/2)3 =O(l o g3n)/8 在不考虑中国剩余定理计算代价的情况下，R S A解密运算的总运行时间为两个模指数运算的运行时间之和，即。(l o g3)/8 +O(l o g3)/8 =O(l o g3)/4,证得改进后的解密运算速度是原解密运算速度的4倍。1 2 .设R S A加密体制的公开钥是(e,)=(77,2 2 1)(1)用重复平方法加密明文1 60,得中间结果为:1 6()2 (m o d 2 2 1)三 1 8 51 604(m

32、o d 2 2 1)三 1 9 11 6()8 (m o d 2 2 1)三 1 61 60 6(m o d 2 2 1)=3 5I G O?(m o d 2 2 1)=1 2 01 6()64 (m o d 2 2 1)三 3 51 6072(m o d 2 2 1)=1 1 81 6076(m o d 2 2 1)=2 1 71 6077(m o d 2 2 1)=2 3若敌手得到以上中间结果就很容易分解，问敌手如何分解。(2)求解密密钥解：(1)由以上中间结果可得：1 601 6(m o d 2 2 1)三 3 5 三 W O Cm o d 2 2 1)=1 6064-1 60l 6=0

33、(m o d 2 2 1)n(1 6()3 2 6 0s)(1 603 2 +1 6O8)=0(m o d 2 2 1)。=(1 2 0-1 6)(1 2 0 +1 6)=0(m o d 2 2 1)=1 0 4 x 1 3 6 三 0(m o d 2 2 1)由 gc d(1 0 4,2 2 1)=l 3,gc d(l 3 6,2 2 1)=1 7,可知分解为 2 2 1 =1 3 x 1 7。解密密钥 d =e T m o d(9()=77T m o d(1 3 x l 7)=77T m o d(1 2 x l 6),由扩展的E u c i l d算法可得d =5。1 3.在E l G a

34、 m a l加密体制中，设素数p =7 1,本原根g=7,(1)如果接收方B的公开钥是为=3,发送方A选择的随机整数左=2,求明文M=3 0所对应的密文。(2)如果A选择另一个随机整数k，使得明文M=3 0加密后的密文是C=(5 9,)，求。2。解：(1)密文c =(q，G)，其中：G-gk m o d p-72 m o d 71 =4 9,C2=(y j M)m o d p=(32 x 3 0)m o d 71 =5 7。所以明文M=3 0对应的密文为C =(4 9,57)。由G=8卜m o d n 59 =7 k m o d 7 1,穷举法可得k=3。所以 G=(y)m o d p =(3

35、3 x 3 0)m o d 71 =2 9。1 4 .设背包密码系统的超递增序列为(3,4,9/7,3 5),乘数r=1 9,模数左=7 3,试对go o dn i gh t 力 口 密。解：由 4 =(3,4,9,1 7,3 5),乘 数1=1 9 ，模 数 左=73 ,可 得B-t x A m o d k=(57,3,2 5,3 1,8)。明文“go o d n i gh t”的编码为“0 0 1 1 1”,“0 1 1 1 1”,“0 1 1 1 1”,“0 0 1 0 0”，“0 0 0 0 0”,O H I O”,0 1 0 0 1”,“0 0 1 1 1”,“0 1 0 0 0”,

36、“1 0 1 0 0”,则有：/(0 0 1 1 1)=2 5+3 1 +8 =64,/(0 1 1 1 1)=3 +2 5+3 1 +8 =67,/(0 1 1 1 1)=3 +2 5+3 1 +8 =67,/(0 0 1 0 0)=2 5,/(0 0 0 0 0)=0,/(0 1 1 1 0)=3 +2 5+3 1 =59,/(0 1 0 0 1)=3 +8 =1 1,/(0 0 1 1 1)=2 5+3 1 +8 =64,/(0 1 0 0 0)=3,/(1 0 1 0 0)=57+2 5=8 2 =9 m o d 73.所以明文“go o d n i gh t”相应的密文为(64,67

37、,67,2 5,0,59,1 1,64,3,9)。1 5.设背包密码系统的超递增序列为(3,4,8,1 7,3 5),乘 数，=17,模数=6 7,试对2 5,2,72,9 2 解密。解：因 为 m o d%=1 7一|m o d 67=4 m o d 6 7，则 4 x (2 5,2,72,9 2)m o d 67=(3 3,8,2 0,3 3)。所以其对应的明文分组为(0()0 0 1,0 0 1 0(),1 0 0 1 0,0 0 0()1),由课本1 2 0 页表4-7可得明文为“A D R A”。1 6.己知=网，p,q 都是素数，x,y w Z：,其 J a c o b i 符号都

38、是1,其中Z：=Z“一0,证明：肛(m o d)是模的平方剩余，当 且 仅 当 都 是 模 的 平 方 剩 余 或 都 是 模 的 非平方剩余。(2)V y 5(m o d)是模的平方剩余，当且仅当尤,y都是模”的 平 方 剩 余 或 都 是 模 的非平方剩余。证明：（1）必要性：若 孙（m o d ）是模的平方剩余，即存在f使得x y=rm o d”，而n-p q,显然必有xy=r mo d p,x y-r m o d g,所以刈 也同时是模p和模q的平方剩余,即（现）=1,（现）=1 n（）=1,（-）A =1.p q p p q q又由题意得（2）=1,（2）=1,BP（-）（-）=1,

39、（-）（-）=1 所以：n n p q p q当（）=1 时，有（2）=l n（2）=l n（土）=1,即x同时是模p和模q的平方剩余，y 也p p q q同时是模p和模夕的平方剩余，即 都 是 模 的 平 方 剩 余；当（土）=7 时，有（马=_1 0（马=_1 =（为=_1,即x同时是模p和模q的非平方剩p p q q余，y 也同时是模p和模q的非平方剩余，即 都 是 模 的 非 平 方 剩 余。充 分 性：若都是模“的 平 方 剩 余，则 演 y 也 是 模 p和 模 9 的 平 方 剩 余，即（土）=（当=（马=（）=1,即孙同时是模p和模q的平方剩余，所以孙是模的平方剩p q p q

40、余；若演y 都是模的非平方剩余，则它们对于模p和模q至少有一种情况是非平方剩余，不妨设（土）=-1,=（2）=一1，则有（与=-1,（马=一 1,即尤,y 也都是模p和模q的非平方剩p p q q余。所以（土）（上）=（?）=（1）（1）=1,同理（与）=1,即孙同时是模p和模q的平方剩p p p q余，所以孙是模的平方剩余。若 x，5（m o d ）是模的平方剩余，则 丁 尸 同 时 是 模p和 模q的平方剩余，所以 3 5 4L =1 =（二）3（2）5,由于勒让德符号的偶数次方肯定为1（p|x 情况除外），即有 p J p P1 =（A）（2）,余下证明同（1）。p P提示:目讣1X X

41、|、p人“V 、y yp人 力=(17.在Rabin密码体制中设p=53,q=59：(1)确定1在模下的4个平方根。(2)求明文消息2347所对应的密文。(3)对上述密文，确定可能的4个明文。解：(1)已知/三lmod3127,=pq=53x59=3 1 2 5,由中国剩余定理可得到等价方程组:x1=1 mod 53x2 s i mod 59因为(1)2 三 1 mod53,(iy 三lmod59,所以x三土lmod53,x三lm od59。经组合可得到以下四个方程组:x 三 lmod53x=lmod59x=mod53x=-lm od59x=-lm od53x=lmod59x=-lm od53

42、x=-lm od59根据中国剩余定理M =59,mod53=9,M2=53,M；mod59=4 9,则有:第一个方程组的解为(59 9 l+53 49 l)mod3127ml；第二个方程组的解为(59 9 l+53 49(l)mod3127三1061；第三个方程组的解为(59 9 (1)+53 49 1)mod 3127三2066；第四个方程组的解为(59.9(1)+53 49.(l)mod3127三3126。所以，1 mod/?的四个平方根为 1 mod()61 mod ,2066mod ,3126mod n。(2)2347 对应的密文为 c 三 23472 mod 3127 三 1762。

43、(3)解密即解尤2三I762m od3127,由中国剩余定理可得到等价方程组：X2 三 1762mod53=13x2 三 1762mod59=51因为(15)2 三 13mod53,(13)2 三51m od59,所以 x三15mod53,x三13mod59,经组合可得到以下四个方程组：x=15mod53(x=15mod53(x=-15mod53 x=-15mod53x s 13mod59 x=-13mod59 x=13mod59 x=-13mod59根据中国剩余定理必=59,M jm od53三9,2=53,M jm od59三4 9,则有：第一个方程组的解为(59915+53 4943)m

44、od3127三1075；第二个方程组的解为(59 9 15+53 49 (-13)mod 3127 三 2347：第三个方程组的解为(59 9 (-15)+53 49 13)mod 3127三780；第四个方程组的解为(5 9 9(15)+53 49-(13)mod3127三2052。所以，四个可能的明文为1075,2347,780,2052。18.椭圆曲线片|(1,6)表示V三V+x +G m o d ll,求其上的所有点。解：模11的平方剩余有1,4,9,5,3。x=l,4,6时，y2=8mod 1 1,无解，曲线无与这一x相对应的点;x=9时，y2=7 mod 1 1,无解，曲线无与这一

45、 x相对应的点；x=0时，y2=6mod 1 1,无解，曲线无与这一 x相对应的点；x=2时，y2=2mod 11,y=4c7；x=3 时，y?三 3 modl 1,y=5或6；x=5,7,10时，y2=4mod 11,y=2或9；x=8时，/三9m odll,y=3或8。所以椭圆曲线E”(l,6)上的所有点为:(2,4),(2,7),(3,5),(3,6),(5,2),(5,9),(7,2),(7,9),(8,3),(8,8),(1 0,2),(1(X 9),。1 9.已知点G =(2,7)在椭圆曲线E”(l,6)上，求2G和3 G。解：(1)求 2G。2 =3x2上 mo d 1 1=(1

46、 3x 4)mo d 1 1 =8 mo d 1 1,2 x 7x2G=(82-2-2)mo d 1 1 =5mo d 1 1,y2G=8 x(2-5)-7 1 mo d 1 1 =8 mo d 1 1,所以 2 G =(5,2)。(2)易知3G =2 G +G=(5,2)+(2,7)。2 -|mo d 1 1 =(5x 7)mo d 1 1 =2 mo d 1 1,x3G=(22-5-2)mo d 1 1 =8 mo d 1 1,y3G=2 x(5 8)-2 mo d 1 1 =3 mo d 1 1,所以 3G =(8,3)。2 0.利用椭圆曲线实现E lG a ma l密码体制，设桶圆曲线

47、是E”。,6),生成元G =(2,7),接收方A的秘密钥%=7。(1)求A的公开钥“。(2)发送方B欲发送消息匕,=(1 0,9),选择随机数=3,求密文(3)显示接收方A从密文C,“恢复消息Pm的过程。解：(1)易知公开钥5=7 G =2 x 2 G +3 G。求2 x 2 G。3x 52+1A.=-1-mo d 1 1 =(1 0 x 3)mo d 1 1 =8 mo d 1 1,2 x 2x4C=(82-5-5)mo d ll=1 0 mo d ll,y4G =8 x (5 1 0)-2 mo d 1 1 =2 mo d 1 1,所以 2 x 2 G =(1 0,2)。由题 1 9可得3

48、G =(8,3),即2=2乂2 6+36=(1 0,2)+(8,3)。3-22 =-mo d 1 1 =(1 x 5)mo d 1 1=5 mo d 1 1,xlc-(52-1 0-8)mo d i 1 -7 mo d 1 1,y7 G=5x(1 0-7)-2 mo d ll=2 mo d ll,所 以 乙=(7,2)。密文C,“=(攵G,吊+%)。求 k G：k G -3G =(8,3)求狂3%以=2 2 +=3G +7 G =(2,7)+(7,2)。2-72 =-mo d 1 1 =一 1 mo d 1 1,7-2=(-I)2-2-7)mo d l 1 =3mo d l 1,y3l,A=(

49、-1)x (2 -3)-7)mo d 1 1 =5 mo d 1 1,所以5=(3,5)。求 月+%：尺,+%=(1 0,9)+(3,5)。5-92 =-mo d 1 1 =-lmo d 1 1,3-1 0 xPm+kPA=(I p 1 0 3)mo d 1 1 =1 0 mo d 1 1,yp+kP=(-l)x(1 0-1 0)-9)mo d ll=2 mo d ll,所以&+S=(io .综上：Cm=(kG,与+俎)=(8,3),(1 0,2)。从密文c,“恢复消息pm的过程如下：Pm=(Pm+kPA)-nA(kG)=(1 0,2)-7(8,3)=(1 0,2)-(3,5)=(1 0,2)

50、+(3,6)=(1 0,9).其中：a)计算 7(8,3)先计算2(8,3)。,3X82+1A-2x3三 1 mod 11,“2(8 3)=18 8=7 mod 11,%(8,3)=l(8 _ 7)_ 3m9mo d ll,所以 2(8,3)=(7,9)。计算 3(8,3)=2(8,3)+(8,3)。,3 9A=-=5 mod 11,8-7七(8,3)=5?7 8 m lOmodll,%(8.3)=5(7 10)-9m 9m odll,所以 3(8,3)=(10,9)。计算 6(8,3)=3(8,3)+3(8,3)。A 3 x102+1 吧 三 lOmodll,2x918尤6(8,3)=121