现代密码学第4章习题.pdf

第第 4 章习题章习题 1证明以下关系 ；，nbanbnamod则)mod()mod)(1 (= ；，则nabnbamodmod)2( 。，则，ncancbnbamodmodmod)3( 证明： （1）设，rnbrna=)mod()mod(则存在整数kj、使得。，rknbrjna+=+= 因此，则bankjba=|n)(所以。nbamod （2）因为。，所以，nababmbamnbmod|moda （3） ，得，由cacbbancbnbanncbnba=+)()( |modmod 所以。ncamod 2证明以下关系 ；nbannbnamod)(mod)mod()mod)(1 (= 。nbannbnamod)(mod)mod()mod)(2(= 证明： （1）设， ba rnbrna=)mod()mod(则存在kj、使得。， ba rknbrjn+=+=a 则nrrnrrnkjnba baba mod)(mod)(mod)(=+= nnbnamod)mod()mod(= （2）设， ba rnbrna=)mod()mod(则存在kj、使得。， ba rknbrjn+=+=a 则nrrnrrnkrjrjknnba babaab mod)(mod)(mod)(=+= nnbnamod)mod()mod(= 3用 Fermat 定理求。11mod3201 解：因 11 是素数，且，1)113gcd(则有 Fermat 定理得，11mod1310又根据性质 ，nbannbnamod)(mod)mod()mod(= 得，11mod13200。11mod311mod)11mod3()11mod3(11mod3 1200201 = 4用推广的 Euclid 算法求119mod67的逆元。 解：用用推广的 Euclid 算法求119mod67的逆元运算步骤如下： 循环次数 Q X1 X2 X3 Y1 Y2 Y3 初值 1 0 119 0 1 67 1 1 0 1 67 1 -1 52 2 1 1 -1 52 -1 2 15 3 3 -1 2 15 4 -7 7 4 2 4 -7 7 -9 16 1 所以。16119mod67 1 = 5求。)12075,4655gcd( 解：27654655212075+= 1890276514655+= 875189012765+== 351406875+= 0354140+= 所以。35)12075,4655gcd(= 6求解下列同余方程组： 7mod1 5mod1 3mod2 x x x 解：，152135105753 321 =MMMM易求 , 17mod, 15mod, 23mod 1 33 1 22 1 11 MeMeMe 所以。71105mod) 111511212235(105mod+x 。即105mod71x 7计算下列 Legendre 符号： 。； 107 65 )3( 53 6 )2( 59 2 ) 1 ( 解： ；1) 1( 59 2 ) 1 ( 8 1592 = ( )() = + = 3 2 ) 1( 3 3172 ) 1( 3 53 ) 1( 53 3 1 53 3 53 2 53 6 28 1532 1) 1)(1( 8 132 = = = = = = 65 7 65 3 ) 1( 65 7 65 3 65 2 65 7 65 6 65 42 65 107 107 65 ) 3( 8 1652 1) 1() 1( 7 2 3 2 7 792 3 3212 7 65 3 65 8 17 8 13 22 = = + + = = 8求 25 的所有本原根。 解：)25(5220) 5 1 1 (25)25( 2 ，=的所有不同素因子，52q 21 =q所以对每 个，g只需计算。和 410 gg又因，8) 3 1 1)( 2 1 1 (24)24(=所以 25 有 8 个本原根。 ；，；， ；，；， ；，；， ；，；， ；，；， ；，；， ；，；， ；，；， ；，；， ；，；， ；，；， ；，；， 25mod12425mod12425mod162325mod2423 25mod62225mod242225mod62125mod121 25mod02025mod02025mod211925mod119 25mod11825mod241825mod211725mod2417 25mod111625mod11625mod01525mod015 25mod161425mod11425mod111325mod2413 25mod111225mod241225mod161125mod111 25mod01025mod01025mod11925mod19 25mod21825mod24825mod1725mod247 25mod21625mod1625mod0525mod05 25mod6425mod1425mod6325mod243 25mod16225mod24225mod1125mod11 410410 410410 410410 410410 410410 410410 410410 410410 410410 410010 410410 410410 = = = = = = = = = = = = 25mod125mod1 410 gg且都为 25 本原根即：2，3，8，12，13，17，22，23。 9设通信双方使用 RSA 加密体制，接收方的公开钥是)355()(，=ne，接收到的密文是 10=C，求明文M。 解： ，因为524mod2464)35(7535 1 = en 。，所以535mod10mod5 5 =nCMd d 10在 ELGamal 加密体制中，设素数71=p，本原根7=g， （1） 如果接收方B的公开钥是3= B y， 发送方A选择的随机整数2=k， 求明文30=M 所对应的密文。 （ 2 ） 如 果A选 择 另 一 个 随 机 数k， 使 得 明 文30=M加 密 后 的 密 文 是 。，求， 22) 59(CCC = 解：；573304971mod7mod 2 2 2 2 1 = B k MyCpgC 所以 M 所对应的密文为（49，57） 。 。，得由2971mod33035971mod7 3 2 3 =Ck 11设背包密码系统的超递增序列为(3，4，9，17，35)，乘数19=t，模数73=k，试对 good night 加密。 解：，得，由，)83125357(54321mod)3517943(=BikatbA ii 因为A长为 5，所以应将明文分成长为 5 比特的分组 g,o,o,d,n,i,g,h,t 相应的二元序列和密文为： 973mod)2557(10100 373mod) 3(01000 6473mod)83125(00111 1173mod)83(01001 5973mod)31253(01110 073mod000000 2573mod)25(00100 6773mod)831253(01111 6773mod)831253(01111 6473mod)83125(00111 + + + + + + + ct ch cg ci cn c cd co co cg 所以密文为（64，67，67，25，0，59，11，64，3，9） 。 12设背包密码系统的超递增序列为(3，4，8，17，33)，乘数17=t，模数67=k，试对 密文 25，2，72，92 解密。 解：67mod4 1 t 。，密文为，解背包得二元序列为由 ，密文为解背包得二元序列为由 ；，密文为解背包得二元序列为由 ；，密文为解背包得二元序列为由 A R D A 0000167mod33492 ;10010,67mod20472 00100,67mod842 00001,67mod33425 所以密文为（A，D，R，A） 13在 Rabin 密码体制中设5953=qp， （1）确定 1 在模n下的 4 个平方根。 （2）求明文消息 2347 所对应的密文。 （3）对于上述密文，确定可能的 4 个明文。 解：(1)由,3127mod1 2 x和，59533127=由中国剩余定理可得到等价方程组： 59mod1 53mod1 2 2 x x 又因为，59mod1) 1(53mod1) 1( 22 所以，59mod153mod1xx 经组合可得到以下四个方程组： 59mod1 53mod1 x x 59mod1 53mod1 x x 59mod1 53mod1 x x 59mod1 53mod1 x x 根据中国剩余定理，4959mod53953mod59 1 22 1 11 = MMMM 第一个方程组的解为；13127mod) 149531959(+ 第二个方程组的解为；10613127mod)1(49531959(+ 第三个方程组的解为；20663127mod) 14953) 1(959(+ 第四个方程组的解为；31263127mod)1(4953) 1(959(+ 所以nmod1的四个平方根为。，nnnnmod3126mod2066mod1061mod1 (2)2347 对应的密文为。17623127mod23472c (3)解密就是求，的平方根，即解模3127mod1762 2 xnc由中国剩余定理可得到等价 方程组： = = 5159mod1762 1353mod1762 2 2 x x 又因为，59mod51)13(53mod13)15( 22 所以，59mod1353mod15xx 经组合可得到以下四个方程组： 59mod13 53mod15 x x 59mod13 53mod15 x x 59mod13 53mod15 x x 59mod13 53mod15 x x 根据中国剩余定理，4959mod53953mod59 1 22 1 11 = MMMM 第一个方程组的解为；10753127mod+ 第二个方程组的解为；23473127mod)13(495315959(+ 第三个方程组的解为；7803127mod)134953)15(959(+ 第四个方程组的解为；20523127mod)13(4953)15(959(+ 所以四个可能的明文为 1075，2347，780，2052。 14椭圆曲线)6 , 1 ( 11 E表示，11mod6 32 +xxy求其上的所有点。 解： 相对于的点；曲线无与这一xxxx; 111mod6 11 6 , 86mod6, 0 2/ )111(3 = += 相对于的点；曲线无与这一xxxx; 111mod8 11 8 , 811mod6, 1 2/ )111(3 = += ；和得点为)7 , 2()4 , 2(, 411mod5 ; 111mod5 11 5 , 511mod6, 2 4 111 2/ )111(3 = += + xxx ；和得点为)6 , 3()5 , 3(, 511mod3 ; 111mod3 11 3 , 311mod6, 3 4 111 2/ )111(3 = += + xxx 以下过程类似，汇集点表如下： (2,4) (2,7) (3,5) (3,6) (5,9) (5,2) (7,9) (7,2) (8,3) (8,8) (10,9) (10,2) 15已知点)72(，=G在椭圆曲线)6 , 1 ( 11 E，求G2和G3。 解： 11mod8 3 2 14 13 72 123 2 3 22 = + = + = y ax 11mod27)52(8)(11mod52264 22 2 2 =yxxyxxx GGG ； 即。，)25(2=G 11mod2 25 72 2 2 = = xx yy G G 11mod37)82(2)(11mod8524 332 2 3 =yxxyxxx GGGG ； 即。， )38(3=G 16利用椭圆曲线实现 ELGamal 密码体制，设椭圆曲线是)6 , 1 ( 11 E，生成元)72(，=G， 接受方A的秘密钥7= A n。 （1）求A的公开钥 A P。 （2）发送方B欲发送消息)910(，= m P，选择随机数3=k，求密文 m C。 （3）显示接收方A从密文 m C恢复消息 m P的过程。 解： （1）),7 , 2(7=GnP AA 由 15 题知)38(3，=G，这里先求GGG336+= 11mod1 6 193 32 183 2 = + = 11mod93)78( 111mod7881 6 2 6 = GG yx， 再求GGG+= 67 11mod7 2 3 6 9 5 2 72 97 = = = 11mod29)77(7, 7277 7 2 7 = GG yx 所以 A 公开钥为（7，2） 。 （2） AmAmm PPGkPPkGC3,3,+=+= 下面先求 AAAAAA PPPPPP+=+= 23 11mod437 4 148 22 173 2 = + = 11mod72)27(4,11mod2774 2 2 2 = AA PP yx 11mod10 5 6 27 72 = = 11mod57) 32(10,11mod37210 3 2 3 = AA PP yx 所以)53(3，= A P接下来计算 Am PP3+ 11mod10 4 7 7 4 103 95 = = = 11mod29)1010(10,11mod1031010 3 2 3 = + A