现代密码学习题参考答案.pdf

《现代密码学习题参考答案.pdf》由会员分享，可在线阅读，更多相关《现代密码学习题参考答案.pdf（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1.解：明文 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 4 13 2 24 根据En,23(m)三ll*m+23(m od26),对明文中的每个字符计算出相应的密文字符c=24 22 15 10 23 24 7 21 10 23 14 13 15 19 9 2 7 24 123 11 15 10191 由 止 匕 得 至IJ密文 c=YWPKXYHVKXONPTJCHYBXLPKTB使用解密变换验证加密结果过程如下：由11*19=1(mod 26)知注

2、：求模逆元可以通过欧儿里得算法或者直接穷举125)根据Dll,23(c)三l l*(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 4 13 2 24 由此得至Ijm二THE NATIONAL SECURITY AGENCY,解密结果与明文一致，正确。2.解：设加密变换为c=Ea,b(m)三a*m+b(mod26)由题目可知，明文前两个字符为i f,相应密文为e d,即有：E(i)=e,4=a*8+b(mod 26)，(i=8,

3、e=4),E=d,3=a*5+b(mod 26),(f=5,d=3),由上述两式可求得，a=9,b=10因此解密变换为D”o(c)三9-i*(c-10)(mod 26)又由3*9=1(mod 26)可知94=3密文对应的数字表示为：c=4 3 18 6 8 2 10 23 7 20 10 11 25 21 4 16 25 21 1023 22 10 25 20 10 21 2 20 7 根据DR。三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

4、7 0 13 10 0 19 4 0 7 24 17由此得到明文 m=ifyoucanreadthisthankateahcer3.解：加密时，先将明文分组，每四个一组:M i三II4w,三18 418a 阴1414in必6三74%三0k4,1JJ12J0)3(8f4)81782193小 三193IX5 2 2%三13；u)4)J19(2514、18)178184132 34,M s三8=7叫=4 M417 3I电1J伊，8、4 3、(19 72 0132 142 2M l19M o三三4%5151l3!段13jI JG =4 3、162 3C2S1、192229893G8 5，2 3、32C

5、6 g2 4)518J必叫(xp-l)A(x)-(x)q(x)而q(x)的 次 数 为p n,0(x)的 次 数 不 超 过 一 1 ,QT)Z(x)的 次 数 不 超 过-1)=p-L 所以 V i,i 是正整数，都有a,+“=a,.设p=kr+t,ai+n=ai+lr+l=ai+,=a.t =0.n r|p.即周期为P(X)的阶，若P(X)是n次不可约多项式，则序列的最小周期等于P(X)的阶。生成函数N(x)=X,，p(x)Z(x)=(x)H 0,0(x)的次数不超过一1.P(x)A(x)=t=+=44,=|x T p(x)p(0(+a2x-Farxr)=0(x)(/-1)p(x)不可约，

6、所以g c d(p(x),0(x)=L 0(力|卜 一1),又因为？W r,所以r =八3.解：由/.(%,。2，。3，。4)=。1 。4 1 。2 a 3，初 态 为(4，。2，。3，%)=(1，1，1)。线 性 递 归可 得：a5=1 1 1 0 =1。6=侬侬逸0 =1%=0初初初=1%=1初初啰1 =0C l q=1。11 =10=lll0=l可 以 得 到 输 出 序 列 为(1 1 0 1 1 1 1 0 1 1)，周 期 为p =54.解：第m+3个比特上不可能出现1,这是由于：根据线性移位寄存器的的递推关系有：%+i =。田2 s c2a2s-c2sa1=04s+2 =0 m

7、2 5+1 Qd 2 s .C2sa2=1从 而 有 句=0,a2=1%s+i =，己 2 s+2 =1，代 入 卜 式 有：a 2s+3=2 s+2 。2 a 2 s+l.,0 2 s 马=25.解：根据p 2 3定理2-7,在G/（2）上的门长m序列在周期为2 -1的m序列中对于】“一 2 ,长 为i的游程有2 T个，且0,1游程各半，那么就有：1 的 2游程：2 H/2 =2 Y1 的 3游程：2-3 T/2 =2 7I 的 n-2 游程：2 T-2)T/2 =1那么就有：S =2-4+2 5.2 +2-6.3 +2-(/7-4)+1-(/7-3)/2 得 s =2n-5+21-6-2+

8、(-4)+(-3)/2 -得 gs =2 Y+2 T+1-(-3)/2从而有 S=2L2-2 +3 =2-2 +1即共有2 2 -+1个形如(S S/+1)=(1,1)的比特对。6.解：由已知可得相应的密钥流序列为1 1 1 0 1 0 0 1 1 1,又因为是3级线性反馈移位寄存器，可得以下方程:(%4)=(3c2。)2。4将值代入得：（O 1 O）=（C 3 c2）1 1 0a j 1 0 1,1 11 1J o1Y0A*Pii i i p i 1 Y1 p|j|=1 1 0=1=1 1 0 =i1 0 1 1 1 0 1 J Ui r0 11 0,q(c3c2。)=(010)1111 1

9、、0 1 =(101)1 0,由此可得密钥流的递推关系为：aj+3=c3ai=ai+2。7.解：如果敌手仅仅知道长为2 n-2的明密文对，他可以构造出以下的长为2 n的明密文对：不妨设：明文：xx2.x2n_2x2n_x2n密文：-2 y 2 -1 2 其中：匹.“2-2为己知的，工2-小2 为未知的.%.当-2为已知的,为未知的。（歹2）1，2.）的可能取值为R O,。1，1 0,1 1。的可能取值为 ，0 1，1 ，I。共有1 6种组合方案，分别破解得到密钥流，在破解的结果中符合m序列的性质密钥流即为正确的方案，有可能不唯一。38 .解：由J-K 触发器可知/=（4+4+1）C 1 +4=

10、0Ck-也，q _|=l此 时%和 他 分 别 为 3 级 和 4 级 m 序 列，（3,4）=1则 /的 周 期 为（23-1）（24-1）=7X1 5 =1 0 5 c 4 =1 1 0 0 1 0 0 1 0 1 0 1 0 0-9 .解：令基本钟控序列生成器中%的周期为回，4 的周期为小，则输出序列/的周期为p =PP?g cd,P 2)PiT叱=q=2,p 1 =2 2 1 =3,2=23-1=7/=o=P=3 x 7gcd(2,7)2 1记 L F S R 2 产生 4,其 状 态 向 量 为 可 得 的 变 化 情 况 如 下:I b 2 b 3 b 3 b 4 b 5 b 5

11、b 6。2 b 2 b 3 b 4b 5 b 6 b 6 b o b I。2输出序列 cj =1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 1 1 41 .(1)证明：设 L 和 R i分别不是第，轮D E S 变换的左右部分，/三。，,1 6,则加密过程为：LO&J P L R IPA 凡-i A-R、i4-4-i.f(Ri-vKi)R；-4,成 国)6 4 b.c i phe r-I P (Rt 6Ll6)6 4 b i t c i phe r-I P (Ri 6Ll6)若将明文和密钥k同时取补，则加密过程为：其中，/(4T，KJ的作用是将数据的左、右半部分扩

12、展后与密钥进行逐比特异或运算，因此/(a _“K J=/(/?1,K)，再 经 过 S盒，并将输出结果进行置换运算P之 后 包%/(7?,._,，号)=L/(KT,K J ,而 R.-,K J ,所以有 R=即同时有V,=E,所以明文P与密钥K同时取补后有Y=D E S 式父)。(2)答：根据的结论进行穷搜索攻击，可将待搜索的回钥空间减少一半，即 2 s s 个。因为给定明文x,则 X =D E Sk(x),由知Y2=D E S Q )=匕，则一次搜索就包含了 x和x，两种明文情况。2 .证明：令 T(L,R)=(R 为 左右位置交换函数,5=。/(火,灯),火),则第，次迭代变换为：*.=T

13、 Fki=T(L f(R,ki),R)=(R,L f(R,砌，又 T2(A,R)=T(R,L)=I(L,火),有 T =T-,同 时,瑾 ,=F g f(R,k i),R)=(L f(R,ki)*f(R,ki),R)=(L,R),即 七=F 7，(居7)(五)=FkiFki=I n (T F/=FkiT,D E S 加密过程在密钥k作用下为：。峪&%P)，解密过程为：D E S 1 =I P、F EF E F k Q F k M I P),所以，(DE S)(DE Sk)=I，即解密变换是加密变换的逆。(得证)3.答：(1)在 C B C 模式中，若密文分组中有一个错误C/,则解密时明文分组中

14、8,鸟都将受到影响，而6+j,i =1,2,后的分组都不受影响，即 CBC的错误传播长度为2,具有自恢复能力。(2)若明文分组P i 有错误，则以后的密文分组都将出现错误，但对接收者来说，经过解密后，除 P 1 有错误外，其余的明文分组都能正确恢复。4 .答：在 8比特C F B 模式中，若密文有1 比特错误，则会影响当前分组以及后续分组的解密，会使解密输出连续9组出错，即错误传播的长度为9。5 .(1)证明：假设存在.”必，弓使得a b=.(2 +1)+4=%(2 +1)+&,有5(/一%)(2+1)=4-5，因为 八,弓4 2 ,所以|八一2区2,因此，只能有=弓，%=%。(2)解：0=4

15、b mod(2+1)2,显然，a和b的最大值均为2-1,则有,x=2 2-2%1 =(2(2+l)-2 x(2 +l)+2-2 -1)=2 _32+1 2+1 2+1 0 q 2)么,0I 4=0,丁(=1)(3)证明：q+r2+2 -3 2n+l(4)解：根 据 =式2+1)+尸,得(a h)di v 2n=qa+i以q+r)2(5)解：根据 ab =q(2+l)+r,得(a/)mod2?,=q+r(g+r)mod24(1+尸)2”(6)解：当=例2+1)+-时，根据()由v2=q 及(H)m od2=q+r 得，r=(m o d 2)一(M仙2”),同理，当.+厂之2 时,r=(a b m

16、od 2)-a b di v T)+2+1余数r表示ab的n个最低有效位与ab右移位数n之差。6.答：(1)在IDEA模乘运算中，必须保证运算构成一个群，因此模数必须为素数，故不能取2e。(2)同一群内的分配律和结合律都成立，但IDEA算法中要保证模数的加法和模数的乘法,比特异或之间分配律和结合律不成立，因此模加运算不能和模乘运算在同一个群内，即不能选模216+1,而2e在模加运算中必为一个群.7.证明：SM4算法的加密轮函数分为加密函数G和数据交换E。其中G对数据进行加密处理,E进行数据顺序交换。即加密轮函数匕=G jE其中，6=Gj计1 4+2园+3，号）（i=0,1,2,31）=（X j

17、7&+1园+2岗+3，泌。X+1岗+2岗+3）E（X i+4，（X i+i，X+2，X i+3）=（区+1/+2/+3）禺+4）,（i=0,l,2,.,31）因为，（Gi）2=G G i T（X i+i，X i+2，X i+3，%），X i+i，X i+2，X i+3，%）=（X i9 T（X i+iX i+2，X i+3，r k i）9 T（X i+i，X i+2，X i+3，r k i）,X i+iX i+2，X i+3，%）=（X iX t+i，X t+2，X i+3，r k。=/因此，加密函数G 是对合的。E 变换为：E（X i+4，（X i+i，X j+2，X i+3）=（X i+i

18、，X i+2，X j+3），X i+4）2氏+4，&+1岗+2*+3）=/显然，E 是对合运算。综上，加密轮函数是对合的。根据加密框图，可将SM 4的加密过程写为：S M 4=GQEG-E根据解密框图，可将SM 4的解密过程写为：S M 4 T =G3IEG30E.G1EG（）R比较SM4与 SM4”可知I,运算相同，只有密钥的使用顺序不同。所以，SM 4算法是对合的。71.解：(1)设am od =7 b m o d =，由题意得=，且存在整数，左，使得。=协 +=(/一人)，即 证得 Q 三 b mod。(2)已知 a=Z?modw,则存在整数%,使得 Q=kn+b n b=(k)n+a,

19、证得 Z?=a mod n。(3)已知。三b mod,b三cmod，则存在整数，A,使得a-jn+b,b=kn+c=a=(J+k)n+c,证得 Q 三 cmod。2.解：(1)设。mod =c，/?mod =，则存在整数，左，使得=%一%=-(j-k)n +(a-b)即(mod n)-(b mod n)mod n=(ab)mod n。(2)设am od”=/,b m o d =，则存在整数，左，使得a=jn+ra,b=kn+rb n axb=(jkn+j%+krjn+5=小=Tjkn+jrh+kra)n+(a x 力)=(rjb)mod =(axb)modn.即(amodn)x(/?mod)m

20、odn=(axb)modn。3.解：因为p=11是素数，且g cd(3,ll)=l,则由Fermat定理可得：310=1 mod 11=(310)A=lm odll；又根据性质(amod)x(6mod)mod”=(axb)m od”,可得：3201 modi 1 =(310)20)modl 1)X(3,mod 11)mod 11=3mod 11 04.解：运算步骤如下表所示：循环次数QXiX2X3YiY2丫3初值1011901671101671-152211-152-121533-12154-77424-77-9161所以 677 m odll9=16。5.解：由Euclid算法，得：1207

21、5=2x4655+27654655=1x2765+18902765=1x1890+875 匚 匚”所以 gcd(4655,12075)=35。1890=2x875+140875=6x140+35140=4x35+086.解：根据中国剩余定理求解该同余方程组，记q =2,%=1,%=L=3,加2 =5,4 =7,M-mx x 加2 x%=1 0 5 ,则有M=35,mod ml=35-mod 3=2,叫M?二 21,modm2=21 mod5=1,m2=15,A/j1 mod w3=15 mod 7=1.?3x=(MM%+M2M22+M3M a3)modM所以方程组的解为三(3 5 x2 x2

22、+2 1 x1 x1+1 5 x1 xl)m o d l 0 5=1 76 m o d l 0 5=71 m o d l 0 5.=(T)7.解：倨)=(_芦=_1=(-1)2+17x3图=(1)1 ,8.解:因为例2 5)=25(1-)=20=22 X 5，所以夕(2 5)的所有不同的素因子为4 =2,%=5 ,即对每个g,只需计算g ，又因为夕(2 4)=2 4(1-；)(1一；)=8,所以2 5有8个本原根。9I10=1 mod 25,I4=1 mod 25：310=24 mod 25,34=6 mod 25；5=0 mod 25,50=0 mod 25；710=24 mod 25,74

23、=lmod25；9=1 mod25,94=llm od25；1110=1 mod25,H4=16mod25；13=24 mod 25,134=llm od25；15=0mod25,154=0mod25：1710=24 mod 25,174=21 mod 25：19=1 mod 25,194=21mod25；2I10=lmod25,214=6mod25；23M=2 4 m o d 25,23=16 mod 25；2=24mod25,24=16mod25；4=1 mod 25,44=6 mod 25；6=1 mod25,64=21mod25；8=24mod25,8=21mod25；IO10=0 m

24、od 25,104=0 mod 25；12l0=24 mod 25,12=11 mod 25；14=1 mod 25,144=16mod25；1610=1 mod 25,164=11 mod 25：1810=24 mod 25,18=1 mod 25；20=0 mod 25,20=0 mod 25；22=24 mod 25,22=6 mod 25；24=1 mod 25,24=1 mod 25；满足w l m o d 2 5且g 4 H l m 0(1 2 5 的 g为2 5 的本原根，即 2,3,8,1 2,1 3,1 7,2 2,2 3。9.证明：若 是 域，则 ,均为 A b e l 群

25、。显然为A b e l群，与N是否为素数无关；但若 为 八6”群，其条件之一必须保证对任意x w Z“-0 有模乘法逆元，即对任意x e Z“-0,有0,使得x x y =l m o d w,所以g c d(x,)=l,即9()=-1,为素数。(2)若 不是素数，则 夕 1,即至少存在一个x e Z“-0,使得g c d(x,)H l,即x无模乘法逆元,因此不能保证均为A b e l群，即不是域。1 0.解：因为“=3 5 =5 x7=p =5,q =7,则夕()=(p l)(q l)=4 x6 =2 4 ,所以d=e m o d 火)三 5 1 m o d 2 4 三 5 m o d 2 4

26、 ,即明文 V 三m o d/i=1 05 m o d 3 5 =5。I L证明：R S A的 两 个 大 素 因 子 的 长 度 近 似 相 等，约为模数的比特长度l o g的一半，即(l o g)/2,而在中国剩余定理中，需要对模P和模4进行模指数运算，这与c m o d的运 行 时 间规律相似，所以每一个模指数运算的运行时间仍然是其模长的三次嘉，即O (l o g/2)=160M-16016=0(mod221)=(16032-l 60s)(16032+1608)=0(mod 221)=(120-16)(120+16)=0(mod221)=104xl36s0(mod221)由 g c d(

27、1 0 4,2 2 1)=1 3,g c d(1 3 6,2 2 1)=1 7,可知分解为 2 2 1=1 3 x 1 7。(2)解密密钥 d-e m o d(e()=77-1 m o d(破 1 3 x 1 7)=77 1 m o d(1 2 x 1 6),由扩展的 E uc il d算法可得4 =5。io1 3.解：密文。二(。卜。2)，其中：G=gk modp=7?mod71=49,C2=(y jA/)mod72=(32 x 30)mod71=57。所以明文M=30对应的密文为C=(49,57)。(2)由0 =gA.modp=59=7m od71,穷举法可得左=3。所以 g=(力 M)m

28、od p=x 30)mod 71 =2 9。1 4.解：由 4=(3,4,9,17,35),乘 数 r=1 9 ,模 数 k=73,可 得B=tx A mod A:=(57,3,25,31,8)。明文“good n i ght”的编码为“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”，“0 1 1 1 0”，“0 1 0 0 1”,“0 0 1 1 1”，“0 1 0 0 0”，“1 0 1 0 0”,则有：/(0 0 U 1)=2 5+3 1+8 =6 4,/(0 1 1 1 1)=3 +2 5+3 1+8 =6 7,/(

29、0 1 1 1 1)=3 +2 5+3 1+8 =6 7,7(0 0 1 0 0)=2 5,/(0 0 0 0 0)=0,/(0 1 1 1 0)=3 +2 5 +3 1 =5 9,7(0 1 0 0 1)=3 +8 =1 1,/(0 0 1 1 1)=2 5+3 1+8 =6 4,/(0 1 0 0 0)=3,/(1 0 1 0 0)=5 7+2 5 =8 2 =9 m od 73.所以明文“good night”相应的密文为(64,67,67,25,0,59,11,64,3,9)。15.解：因为厂mod=17-1 mod67=4mod67,则 4 x(25,2,72,92)mod 67=(

30、33,8,20,33)。所以其对应的明文分组为(00001,00100,10010,00001),由课本120页 表4 7可得明文为“ADRA”。16.证明：(1)必要性：若 中(mod”)是模胃的平方剩余，即存在，使得中mod”，而 7 =pq,显然必有中=modp,中modq,所以孙也同时是模p和模9的平方剩余,即 卢)=i,(当=1=(与 心=i,(与(与=1。p q p p q q又由题意得(3 =l,g)=l,即()(当=1,(马(马=1。所以:n n p q p q当(二)=1时，有(马=1 =(4 =1 n ()=1,即x同时是模p和模夕的平方剩余，也同p p q q11时是模p

31、和模q的平方剩余，即x,歹都是模的平方剩余；当（土）=-1时,有（2）=_ 1=心=_1 n（）=一1,即x同时是模p和模夕的非平方剩余,p p q qy也同时是模夕和模4的非平方剩余，即x,歹都是模n的非平方剩余。充 分 性：若 都 是 模 的 平 方 剩 余，则x,歹也 是 模p和 模4的 平 方 剩 余，即（-）=（-）=（马=g）=1，即9同时是模p和模q的平方剩余，所以孙是模的平方剩余;p q p q若 都 是 模 的 非 平 方 剩 余，则它们对于模p和模q至少有一种情况是非平方剩余，不妨设（-）=-1,=（-）=-1,则有（与=一1,（4=一1，即x,尸也都是模夕和模4的非平方剩

32、余。p p q q所以（土）（2）=（9）=（T）（T）=1，同理（2）=1，即个同时是模夕和模q的平方剩余，所P P P以 孙 是模的平方剩余。q若g o d”）是模的平方剩余，则 同 时 是 模0和 模q的 平 方 剩 余，所以(3 5、x y1 =（日）3（上）5,由于勒让德符号的偶数次方肯定为1 （川 情况除外），即有P Pi =（-）（z）,余下证明同（1）。p P提示:yn1217.解：已知一 三imod3127,=网=53x59=3125,由中国剩余定理可得到等价方程,x2=lmod53组：x2=1 mod 59因为(1)2 三lmod53,(l)2 三lmod59,所以x三土l

33、mod53,x=1 mod59 o 经组合可得到以下四个方程组:x=lmod53 x=lmod53(x=-lmod53 x=-lmod53 三 13mod53(13)2 三 51mod59,所以 x三土15mod53,x三13mod59,经组合可得到以下四个方程组：x 三 15moe153x=13mod59x=15 mod 53x=-13mod59x=-15mod53 0 卜-1 )(c-2 J (l-l)g-2 )=8(x-2)(x-4)6 +7(x-1 )(x-4 )8 m od l7=2x2 4-10 x4-13s =/(0)=1 36 .解：由题设可得s 应满足1 1 =4 s mxm

34、2=6 3因为=2,=3,叫=7 ,m2=9 ,%=1 1,3个子密钥分别是6,3,4,那么用=用1x 加2 x m3 =7 x 9 x 1 1 =6 9 3=9 9,N,=M；(m odmt)=9 9-1 m o d 7=1m 718M2=693m2 9N2=Af2-(mod w2)=77T mod9=2Mi=63,N3=M-(mod w,)=63-mod 11=7加3 1 1由m=6,S2=3可得s=sMN+s2M 2 N2(mod 63)=6x99xl+3x77x 2(mod 63)=1056(mod 63)=48由$2=3,s3=4可得s=S2M2N2 4-S3MN3(mod99)=3

35、x77x2+4x63x7(mod99)=2226(mod99)=48由S=6,*=4可得s-s、M、N+s3M M lm od77)=6x99x1+4x63x7(mod 77)=2358(mod77)=48即秘密数据s为48191 .6,1.3 节用C B C 模式的D E S 设计数据认证算法为：O i=E”(Di)。2 =岳晨。2 。1)。3 =EK(D3 。2)=ON=EK(DN EK(DN-I EKD2 EK。)ON=EK(DN O/v-i)如果改用C F B 模式来实现，由于输出为6 4 位，所以必须取j=6 4，也就是每次移位寄存器 左 移 整 个 64位。为 了 达 到 相 同

36、的 结 果，可 取 CF B模 式 中W =D、,P,=1,N-1),PN=0，则有：0 1=5 E M A)。2 =。3 EK(O1)。3 =。4 呢(。2)=ON=EK(ON-I)=EK(DN EK(DN T EKD2 EK(DD)N T =DN EK(ON-2)ON=。EK(ON-I)比较两式，OM作为消息认证码，结果相同。2 .(1)答：敌 手 主 要 是 通 过 修 改 函 数 的 输 入 值,MN和H e 来构造碰撞。乩=DESMI(%)/H2=DE SM2(H1)H1HN=DESMN(HN)*利用y=DESJ(x)和x y=x y两个性质可知，若 敌 手 同 时 对 和 逐 比

37、特 取补，则由性质一知DESm(H c)也被逐比特求补,由性质二知从保持不变，所以H),小也都不受影响，所以有：=HN(2)答：改迭代关系为H,=EH,_/M,)M,，则敌手也可同时对M 和 逐 比 特 取 补，由性质一知DESHCCMJ也被逐比特求补，由 性 质 二 知 H z 都不受影响，故仍可进行上述攻击。3 .证明：对任一分组C i，可构造g 如下：Q=RS AC)R SA C&)，则“(。1，。2)=R s a(R s a(C D c?)=R SA(R SA(C 1)R S A(Q)RSA(B J B2)=R S 4(R S 4(B i)B2)=H(BI，B2)设 哈 希 函 数 的

38、 输 入 消 息 分 组 为 MN，则可任取M；替代M 1，并由上述方法构造M；替代购,可得=M”)，攻击成功。4 .答：20%陷 s为消息分组的16个字，初始放在移位寄存器中，如上图连接电路。CLS,的输出反馈到移位寄存器右边的输入端，则每个时钟到来时，移位寄存器从左边输出端移出一个字W,(i=0,79)。5.对 S H A,计算 W e，W17，W18,W|9答：W 16=CLSWo勿2皿8皿13)Wl7=CLSWX “3 勿9“14)Ww=CLS1(W2 叩4 皿15)W19=CLSX(W3/5 W11/16)6.(1)答：由于MD5使用little-endian结构，而 X,丫使用的是

39、b ig-endian存储结构，因此必须把 X,丫 转换成 little-endian 格式，设转换成：X=丫=y；y；y；4，则有%j22 4+X2216+X328+X4=X4224+X3216+x22s+x；=%1=%4，%2=%3，3=2，4=(2)答：由于SHA使用b ig endian结构，而 X,Y 使用的是little-endian存储结构，因此必须把X,Y 转换成b ig endian格式，设 转 换 成:=丫 =/久 心 则有%4224+X3216+xz28+=xt224+X2216+x 1328+x4=x=X4,%2=x3fx3=X2,X4=%1211.解：(1)签名过程：

40、为了简化，用M代替H(M),则用户对消息M的签名为(r,s)。计算r=(gK modp)modq=(423mod83)mod41=51mod41=10,k mod q=23“mod 41=25,s-A:-1(M+x?)mod q-25 x(56+57 x 10)mod41=29。所以签名(r,s)=(10,29)。(2)验证过程：接收方收到的消息为A T,签名为&,s)=(10,29)。计算w=(s)T mod7=29-mod41=17,%=(Mvv)modq=(56xl7)mod41=9，u2=(rw)mod7=(10 xl7)mod41=6，v=Kg”)mod py mod T m odq

41、。因此，参数左泄漏将导致签名秘密钥的泄漏，攻击者可以伪造任意消息的签名。221.解一：设背包向量为4,证明者P 知道一个背包容积X 的解纥，即/8、=x,P 以零知识证明方式向验证者证明自己掌握秘密纥 的协议如下：P随机选取一向量纥，计算4 6,.=y，将 N 发给V。V 随机选e e O,l,将 e 发给P；P计算。=纥+吗.，即e=0 时，C =BV；e=l 时，C=B,+BX,将 C 发给V。注：如果e=0,P展示歹的解，即 纥；如果e=l,P展示被加密的y 的解，即 纥+及。若/C =y+ex,V 接受P 的证明。协议的完备性、正确性和安全性(1)完备性：如果P和 V 遵守协议，且 P

42、 知道x 的解纥.，则应答。使得NC=y+ex,V 接受 P 的证明。(2)正确性：假冒的证明者E 可按以下方式以 的概率骗得V 接受自己的证明：2E 随机选取一向量4 和0 w O,l,计 算/纥=y，将 y-法 发给V。V 随机选e e O,l,将 e发给E；E 将 纥 发 给 V。V 的验证方程为4 约=丁 一 次+ex。当2=e 时，方程成立，V 接受E 的证明，E 欺骗成功。因2=0 的 概 率 是 所 以 E 成功的概率是上。2 2另一方面，工 是E成功的最好概率，否则假定E 以大于工的概率使V 相信自己的证明，那么2 2E 知道一个y,对这个y,他可以正确回答V 的两个询问e=0

43、 和 e=l,意味着E 能计算A C,=y,AC2=y+x,由此可计算x=/(C2-6)，因此得秘密纥=(C2 一0。(3)安全性：根据以上的讨论知，假冒的证明者E 欺骗V 成功的概率为1,这个概率太大了。2为减少这个概率，可以将协议重复执行多次，设执行，次，则欺骗成功的概率将减少到2一。解二：构造背包问题23先选大素数N,g,l g N ,N是素数，且(N-l)/2也为素数，g为N的本原根。P随机选取f个整数百，$2,，S,(不用超递增序列)，计算匕=gs m o d NV2=g m o d NIIIVt=gs,m o d N式中S-S ,S,为秘密密钥；N,g,匕,V2,匕为公开。(2)零

44、知识证明协议1)P随机选择尸，计 算x =g m o dN,并将x传送给V；2)V随机选择f个二进制比特序列伉，人，,b,并将其传送给P；3)P计算M=y M+r,并将其传送给V。Z=14)V验证，计算z=1也=0 i =l，2,tiy x Z.Z-Z,比较y =_/是否成立，若成立，说明P了解秘密密钥每，52,S,；反之，P为假冒。(3)安全性此类算法的安全威胁主要来自P欺骗V或V假冒P。假如使用的背包和离散对数没有问题，P欺骗V和V假冒P成功的概率都基于。(i K i K f)的随机性，若每一个。(i Vi K/)的选取为0或1的概率为1/2,则假冒或欺骗成功的几率为1/2 ；若该协议重复

45、左次，成功的几率为241/2。2.解：(1)要求p,三%三3m od4是为了保证同一数a在模=p/%下的两个平方根有相反的Jacob i符号。(2)B 先计算 Jacob i 符号 和 x；mod/,)=1,2?三 mod55=4,将(4,一1)发给 A。接下来A计算4mod55的平方根，求出4在mod 5时的平方根为2,4在modi 1时的平方根为 2,可得以下四个方程组:x=2mod5 fx 三 2mod5x=2 mod 11 x=-2 mod 11x=-2 mod 5x=2 mod 11x=-2 mod 5x=-2 mod 11由M=u,M 1 mod5=1；2=5，A/丁 m o d

46、三9,第一个方程组的解为(2*llxl+_2x5 x9)mod 55=2；第二个方程组的解为j2 x llx l 2x5x9)m od55三42：第三个方程组的解为j-2 x llx l+2x5x9)mod55m l3；第四个方程组的解为j 2 x llx l 2x5x9,m od55m 53；-1,A 将 42或 53发给B。当A将42发给B时,B由gcd(55,42+2)=11得至ij 的一个因子,从而得到n的分解式11x5,从而获得A的秘密与。当A将53发给B时，因53三2m od55,所 以B不能计算出的一个因子，没有得到任何新信息，从而不能获得A的秘密s,。3.解：因为g不是Z；的生

47、成元，记循环群(g)为显然H是Z；的子群，且|可厂是一个大于1的正整数，所 以 乌Zp r 2在Z；中均匀、随机选取一元素，若hw H ,则可在“上找到一个x,使得 三g m o d p成立。而/z e 的概率至多是；，所以人三g m odp成立的概率至多是(2)V在Z：中任意取一个元素人，发送给P。P知道了,使得三g*m odp。P在Z：中随机取一个元素左，计算九三g m odp并25发送给VV 随机选e e O,l ,将 e 发给P；P计算b =k +e x 并发送给VV 验证8 =不，若成立，则接受P的证明。P和 V 重复以上过程次。(3)以上的证明可以在多项式时间内完成。因为，是一个有

48、限值，三g*m o d 夕可以在多项式时间内完成。4.解：(1)对于给定的y(),y i 和x 0,x i,证明者P都能够回答c =0或 c =1的两个挑战；故说明y 0 和y x o 都是模n的二次剩余或者力和力打都是模n的二次剩余；根据数论知识可得：孙或与至少有一个是模n的二次剩余。(2)若 P r o v e r 和 V e r i f i e r 都是诚实的，且(1)是正确的，显然，验证者最终会接受证明者的证明。261.答：语义安全：一个安全的加密方案应使敌手通过密文得不到任何信息，即使是1比特的信息。此概念可用于抵抗被动的多项式时间有界敌手和主动的多项式有界敌手，但不能抵抗被动的多项

49、式无界敌手。2.答：Rab in密码体制Rab in密码体制是RSA密码体制的一种修正，假定模数=p q不能被分解，该类体制对于选择明文攻击是计算安全的。因此，Rab in密码体制提供了一个可证明安全的密码体制的例子：假定分解整数问题是整数上不可行的，那么Rab in密码体制是安全的。Rabin密码体制：(一)密钥止应=pq,其中p和q是素数，且p三q三3(mod 4),即这两个素数形式为4k+3,计算n=p q。为公钥，P均为私钥。(二)加密c=rrr mod n其中“是明文分组，c是对应的密文分组。(三)解密解密也就是求。模的平方根，即 解 三c m o d ,该方程等价于方程组：x1=c

50、mod px2=cmodq由于P三4三3(m od4),所以可以解出每个方程有两个解：x=y mod p,x=-y mod px=z mod q,x=-z mod q两两组合可得4个同余方程组：c x=y mod px=jmod p x=-y modp x=-y mod px=z mod q x=-z mod q x=z mod q x=-z mod q由中国剩余定理可解出每一个方程组的解，共四个，即每一密文对应的明文不唯一。为有效确定明文一般在机中加入某些代表性信息，如：发送者身份号、接受者身份号、时间、日期等下面证明，当夕三三3(mod4)时，两个方程X：三cm odp,f三cm odq的