《密码学原理与实践(第三版)》课后习题参考答案
(由华中科技大学信安09级提供)
第一章
1.1（李怡）
(a)51 (b)30 (c)81 (d)7422
1.2（贾同彬）
证明：令t1= (-a)mod m ,t2=m-(a mod m),则t1≡t2(mod m).
又 0 1.3 （张天翼） 证明充分性： 若a?b(modm)，则可得a?b?km，设b?jm?r，0?r?m，j?N，则有 a?(k?j)m?r，故有amodm?r,由假设得bmodm?r，故amodm?bmodm 证明必要性： 若amodm?bmodm，则可设amodm?bmodm?r，则有a?km?r，b?jm?r，其中j,k?N，因此a?b?(k?j)m，即ma?b，故a?b(modm) 综上，问题得证 1.4 （李怡） 令a?km?r,0?r?m,则r?amodm?a?而r?a?km,所以只需证明k???. m??a?raa?a?因为k?,?m?-r?0,所以?1?k?,即k???mmm?m? 1.5 (李志远) 穷举密钥法来破解移位密码即将这个字符串每个字母移位1，2，3…26次，然后判断这26个字符串哪个符合英语规则。故我编写 如下的C++来实现如此功能 #include if(word=='Z')return 'A'; else return word+1; } int main() { cout<<\ char string1[43]; cin>>string1; int n; for(n=1;n<=26;n++) { int num; for(num=0;num<43;num++) { string1[num]=change(string1[num]); } cout< 解释：1.代码专为本题编写，故输入字符数不能多于43个，且输入范围仅限大写英语字母 2.将题中的42个字母BEEAKFYDJXUQYHYJIQRYHTYJIQFBQFBQDUYJIIKFUHC输入并回车 3.得到的结果 CFFBLGZEKYVRZIZKJRSZIUZKJRGCREVZKJJLGVIDRE for turn 1 DGGCMHAFLZWSAJALKSTAJVALKSHDSFWALKKMHWJESF for turn 2 EHHDNIBGMAXTBKBMLTUBKWBMLTIETGXBMLLNIXKFTG for turn 3 FIIEOJCHNBYUCLCNMUVCLXCNMUJFUHYCNMMOJYLGUH for turn 4 GJJFPKDIOCZVDMDONVWDMYDONVKGVIZDONNPKZMHVI for turn 5 HKKGQLEJPDAWENEPOWXENZEPOWLHWJAEPOOQLANIWJ for turn 6 ILLHRMFKQEBXFOFQPXYFOAFQPXMIXKBFQPPRMBOJXK for turn 7 JMMISNGLRFCYGPGRQYZGPBGRQYNJYLCGRQQSNCPKYL for turn 8 KNNJTOHMSGDZHQHSRZAHQCHSRZOKZMDHSRRTODQLZM for turn 9 LOOKUPINTHEAIRITSABIRDITSAPLANEITSSUPERMAN for turn 10 MPPLVQJOUIFBJSJUTBCJSEJUTBQMBOFJUTTVQFSNBO for turn 11 NQQMWRKPVJGCKTKVUCDKTFKVUCRNCPGKVUUWRGTOCP for turn 12 ORRNXSLQWKHDLULWVDELUGLWVDSODQHLWVVXSHUPDQ for turn 13 PSSOYTMRXLIEMVMXWEFMVHMXWETPERIMXWWYTIVQER for turn 14 QTTPZUNSYMJFNWNYXFGNWINYXFUQFSJNYXXZUJWRFS for turn 15 RUUQAVOTZNKGOXOZYGHOXJOZYGVRGTKOZYYAVKXSGT for turn 16 SVVRBWPUAOLHPYPAZHIPYKPAZHWSHULPAZZBWLYTHU for turn 17 TWWSCXQVBPMIQZQBAIJQZLQBAIXTIVMQBAACXMZUIV for turn 18 UXXTDYRWCQNJRARCBJKRAMRCBJYUJWNRCBBDYNAVJW for turn 19 VYYUEZSXDROKSBSDCKLSBNSDCKZVKXOSDCCEZOBWKX for turn 20 WZZVFATYESPLTCTEDLMTCOTEDLAWLYPTEDDFAPCXLY for turn 21 XAAWGBUZFTQMUDUFEMNUDPUFEMBXMZQUFEEGBQDYMZ for turn 22 YBBXHCVAGURNVEVGFNOVEQVGFNCYNARVGFFHCREZNA for turn 23 ZCCYIDWBHVSOWFWHGOPWFRWHGODZOBSWHGGIDSFAOB for turn 24 ADDZJEXCIWTPXGXIHPQXGSXIHPEAPCTXIHHJETGBPC for turn 25 BEEAKFYDJXUQYHYJIQRYHTYJIQFBQDUYJIIKFUHCQD for turn 26 经过英语分析，发现当移位密码密钥为17时，字符串有英文含义 LOOK UP IN THE AIR ITS A BIRD ITS A PLANE ITS SUPERMAN (看天上，是一只鸟，是一架飞机，是一位超人) 故移位密码密钥为17 1.6（司仲峰） 对合密钥为 0和13 1.7（陈诗洋） (a) m=30=2*3*5 φ(30)=30*(1-1/2)*(1-1/3)*(1-1/5)=8 故密钥量是 8*30=240 (b)m=100=22*52 φ(100)=100*(1-1/2)*(1-1/5)=40 故密钥量是 40*100=4000 (c)m=1225=52*72 φ(1225)=1225*(1-1/5)*(1-1/7)=840 故密钥量是 840*1225=1029000 1.8（周玉坤） 解： 在 中若元素有逆，则必有gcd(a,m)=1; =1,利用广义欧几里得除法，找到整数s和 、 的解法都相 若元素a存在逆使得a t，使得： sa+tm=1，则=s(modm)是a的逆。 似，直接给出结果。 （1）、 gcd(a,28)=1,则a=1,3,5,9,11,13,15,17,19,23,25,27. （2）、 =1，=15， =19， =5， =17， =3， =25， =11， =23， =9， =27 gcd(a,33)=1,则a=1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26, 28,29,31,32 （3）、 =1，=10，=7，=13， =17， =25， =20， =19，=31，=4，=32 =29 =2， =14， =28，=5，=8， =26，=23，=16， gcd（a,35）=1,则a=1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23, 24,26,27,29,31,32,33,34 =1，=16， =18， =3， =12， =9， =6，=11， =22，=33， =4， =2 =27， 1.9（薛东） =24，=29， =8，=26， =32，=23， =19，=17， =31，=34 =13 设1≤a≤28,利用反复试验的方法求出a-1mod29 的值。 解：由乘法逆存在条件gcd(a,29)=1知a=1,2,3, …,28均存在逆元。 计算可得： 1-1=1 2-1=15 3-1=10 4-1=22 5-1=6 6-1=5 7-1=25 8-1=11 9-1=13 10-1=3 11-1=8 12-1=17 13-1=9 14-1=27 15-1=2 16-1=20 17-1=12 18-1=21 19-1=26 20-1=16 21-1=18 22-1=4 23-1=24 24-1=23 25-1=7 26-1=19 27-1=14 28-1=28 1.10 (a) dK(y)=6y+19(mod 29) (b) 略 1.11（程玲） （a）证明：加密函数为e(x)=(ax+b) mod n，即可令ax+b≡y( mod n)， 等价ax≡y-b( mod n)，即x≡aˉ1(y-b)( mod n)，即x≡(aˉ1y-aˉ1b)( mod n) 要使k为对合密钥，则a≡aˉ1( mod n)，b≡-aˉ1b( mod n) 即aˉ1 mod n ≡a且b(1+aˉ1)≡0( mod n)，也就是b(1+a)≡0( mod n) 反过来，当aˉ1 mod n ≡a且b(1+a)≡0( mod n)可得 b(1+aˉ1)≡0( mod n)，即b≡-aˉ1b( mod n)，K为对合密钥 （b）解：假设对合密钥为K=（a,b） a要满足gcd(a，15)=1，可得a=1，2，4，7，8，11，13，14 又因为a要满足aˉ1 mod 15≡a，则a=1，4，11，14 b需满足b(1+a)≡0( mod 15) 当a=1，即2b≡0( mod 15)，可得b≡0( mod 15) 当a=4，即5b≡0( mod 15)，可得b=0，3，6，9，12 当a=11，即12b≡0( mod 15)，可得b=0，5，10 当a=14，即15b≡0( mod 15)，可得b={x|x?Z15}