習題講解3第四章hcy

1、 韓韓 彩彩 蕓蕓答：答： 1 對稱密碼體制密鑰管理的困難性：對稱密碼體制密鑰管理的困難性： 對稱密碼體制中，任何兩個用戶間要進行保密通信就需要對稱密碼體制中，任何兩個用戶間要進行保密通信就需要一個密鑰，不同用戶間進行通信的時候必須使用不同的密鑰一個密鑰，不同用戶間進行通信的時候必須使用不同的密鑰。密鑰為發(fā)送方和接收方所共享，用于消息的加密和解密。密鑰為發(fā)送方和接收方所共享，用于消息的加密和解密。2 系統(tǒng)開放性問題：系統(tǒng)開放性問題： 對稱密碼體制的密鑰分發(fā)方法要求密鑰共享各方面的互相對稱密碼體制的密鑰分發(fā)方法要求密鑰共享各方面的互相信任，因此它不能解決陌生人之間的密鑰傳遞問題。信任，因此它不能

2、解決陌生人之間的密鑰傳遞問題。3 數(shù)字簽名問題：數(shù)字簽名問題： 對稱密碼體制難以從機制上實現(xiàn)數(shù)字簽名問題，也就不對稱密碼體制難以從機制上實現(xiàn)數(shù)字簽名問題，也就不能實現(xiàn)通信中的抗抵賴技術。能實現(xiàn)通信中的抗抵賴技術。4-1 為什么要引用非對稱密碼體制？為什么要引用非對稱密碼體制？4-8設通信雙方使用設通信雙方使用rsa加密接收方的公開密鑰是加密接收方的公開密鑰是（5，35），接收到的密文是），接收到的密文是11，明文是多少？，明文是多少？rsa加密體制：加密體制：設明文為設明文為m，密文為，密文為c，公鑰公鑰(e , n)，私鑰，私鑰d，滿滿足以下關系：足以下關系：解：由題意知：解：由題意知：e=

3、5，n=35，c=11 (35)= (5*7)=(5-1)*(7-1)=24 私鑰私鑰d= e-1mod( (n)=5-1mod 24 ncmnmcneddemodmodmod1由擴展的歐幾里得算法可以求得由擴展的歐幾里得算法可以求得d，其算法，其算法如下：如下： 24=45+4； 5=14+1； gcd (5,24)=1 1 =5-24-(45)=55-24； d=5-1mod 24=5 所以，明文所以，明文 m = cd mod n = 115mod 35 =164-9在在rsa體制中，若給定某用戶的公鑰體制中，若給定某用戶的公鑰e=31，n=3599，那么該用戶的私鑰等于多少？，那么該用

4、戶的私鑰等于多少？ 解解: 所以該用的私鑰為所以該用的私鑰為3031。 348016115961593599n30313480mod4493480mod31)3599(mod3111d解：解：由由elgamal密碼體制可知密碼體制可知： 設（設（p， ，y）作為用戶）作為用戶b的公開密鑰，的公開密鑰，r作為用戶作為用戶a選擇的選擇的隨機數(shù)，隨機數(shù)，明文為明文為m，密文為（，密文為（c1，c2），則有以下等式成立：），則有以下等式成立：4-10 在在elgamal密碼體制中，設素數(shù)密碼體制中，設素數(shù)p=71，本原元，本原元=7=7，（1 1）如果接收方）如果接收方b b公鑰公鑰y=3y=3，發(fā)送

5、方，發(fā)送方a a選擇的隨機整數(shù)選擇的隨機整數(shù)r=2r=2，求明，求明文文m=30m=30所對應的密文二元組（所對應的密文二元組（c c1 1，c c2 2) )。（2 2）如果發(fā)送方）如果發(fā)送方a a選擇另一個隨機整數(shù)選擇另一個隨機整數(shù)r r，使得明文，使得明文m=30m=30加密后加密后的密文（的密文（c c1 1，c c2 2）= =（5959，c c2 2）, ,求求c c2 2 pccmpymcpckrrmodmodmod11221由上式可以求得：由上式可以求得：r=3r=3，n=4n=4，故可以得到密文，故可以得到密文c2c2：（2 2）由題意知：當另外取一個隨機數(shù)）由題意知：當另外

6、取一個隨機數(shù)r r時時且滿足且滿足 1 1r rp-1，即，即1 1r r70。5771mod330mod4971mod7mod2221pymcpcrr（1）由題意知：）由題意知：p=71， =7，y=3，r=2，m=30，59n7175971mod7mod1rrrpc可以設2971mod330mod32pymcr解：由解：由ecelg密碼體制可知：接收方的公開密鑰密碼體制可知：接收方的公開密鑰 pa=da g=5g=5（2，7），其中），其中da為接收方的密鑰，為接收方的密鑰，g為為橢圓曲線的基點，因為橢圓曲線可以表示為橢圓曲線的基點，因為橢圓曲線可以表示為 ep（a，b），對照題目得：），

7、對照題目得：a=1，b=6，p=11。設：設：2g=2（x1，y1）=2（2，7）=（x3，y3）帶入如下）帶入如下橢圓曲線上橢圓曲線上倍點公式倍點公式得：得：4-13 利用利用ecelg密碼體制，設橢圓曲線是密碼體制，設橢圓曲線是e11（1，6），），基點基點g=（2，7），接收方），接收方a的秘密密鑰是的秘密密鑰是da=5。求：。求：（1）a的公開密鑰的公開密鑰pa；（2）發(fā)送方）發(fā)送方b欲發(fā)送消息欲發(fā)送消息pm=（7，9），選擇隨機數(shù)），選擇隨機數(shù)r=3，求密文求密文cm=（c1，c2）是多少？）是多少？（3）完成接收方）完成接收方a解密解密cm的計算過程。的計算過程。把把x1，y1，a

8、帶入可以求得帶入可以求得=8，（，（x3，y3）=（5，2）=2g，然，然后再用后再用倍點公式倍點公式求得求得4g為（為（10，2），），最后用最后用加法公式加法公式求得求得 4g+g= (x1，y1)+(x2，y2)=(10，2)+(2，7)=(x3，y3)橢圓曲線上加法公式如下：橢圓曲線上加法公式如下： pyxxyxxpyaxmod2mod231313123111 pyxxypxxxpxxyymodmodmod1313212311212最后求得接收方最后求得接收方a的公鑰的公鑰pa=5g=（3，6)（2）發(fā)送方）發(fā)送方b用接收方用接收方a的公鑰進行加密，加密后的密文的公鑰進行加密，加密后的

9、密文為（為（c1，c2），且加密算法如下：），且加密算法如下：其中其中pm為發(fā)送方為發(fā)送方 b欲發(fā)送的明文，欲發(fā)送的明文，r為用戶為用戶b產生的隨機數(shù)，產生的隨機數(shù)，g為橢圓曲線上的基點，且為橢圓曲線上的基點，且r=3，g=（2，7），），pm=（7，9），），pa=（3，6）故（）故（c1，c2）計算如下：）計算如下：各自根據(jù)各自根據(jù)橢圓曲線加法公式和橢圓曲線上加法公式可計算得橢圓曲線加法公式和橢圓曲線上加法公式可計算得到到amrppcrgc216 , 339 , 733 , 8321amppcgc（c1，c2）=（8，3），（），（3，5）。）。將將da=5，c1=3g，c2=（3，5）代

10、入得）代入得cm=（7，9）（3）接收方）接收方a收到密文（收到密文（c1，c2）后進行解密，解密算法）后進行解密，解密算法如下：如下：12cdccam補充題補充題1. 分別用孫子定理和平方分別用孫子定理和平方-乘法計算：乘法計算：7560mod527解解: (1) 孫子定理孫子定理 設設 x 7560mod 527，由于，由于527=1731，且，且gcd(17,31)=1所以，所以，x 7560mod 527可寫成可寫成 31mod717mod7560560 xx化簡：化簡： 7560 mod17= 7560mod16mod 17 = 1mod 17 7560 mod31 = 7560mo

11、d30mod 31 =720 mod 31=5mod31將式化簡為將式化簡為 根據(jù)中國剩余定理，取根據(jù)中國剩余定理，取 b1=1，b2=5，m1=17，m2=31則則 m=m1m2=527，m1=m/m1=31， m2=m/m2=1731mod517mod1xx費馬定理費馬定理1131mod17mod1117mod1417mod31mod12122111111mmymmy222527mod1276527mod)1711531111 (mod)(222111mmybmybx222527mod7560解解: (2)平方平方-乘法乘法560=1000110000(b)，z=1，a=7，n=527b9

12、=1z z2a1mod n=17mod 527=7b8=0z z2a0mod n=(721)mod 527=49b7=0z z2a0mod n=(4921)mod 527=293b6=0z z2a0mod n=(29321)mod 527=475b5=1z z2a1mod n=(47527)mod 527=483b4=1z z2a1mod n=(48327)mod 527=377b3=0z z2a0mod n=(37721)mod 527=366b2=0z z2a0mod n=(36621)mod 527=98b1=0z z2a0mod n=(9821)mod 527=118b0=0z z2a

13、0mod n=(11821)mod 527=222nazzibimod21補充題補充題2. rsa公開密鑰加密系統(tǒng)中，某用戶選擇公開密鑰加密系統(tǒng)中，某用戶選擇p=43，q=59，并取公開密鑰，并取公開密鑰e=13，計算：，計算：（1）私有密鑰中的指數(shù)）私有密鑰中的指數(shù)d（2）在）在z26空間中對明文空間中對明文“public key encryptions”加加密，求出其密文數(shù)值序列密，求出其密文數(shù)值序列rsa加密體制：加密體制：設明文為設明文為m，密文為，密文為c，公鑰公鑰(e , n)，私鑰，私鑰d，滿足以下關系：滿足以下關系： ncmnmcneddemodmodmod1解：由題意知：解：

14、由題意知：e=13，p=43，q=59 n=p*q=4359=2537， (n)= (4359)=(43-1)(59-1)=2436 私鑰私鑰d= e-1mod (n)=13-1mod 2436正向迭代：正向迭代：2436=13187+513=52+35=31+23=2+1 gcd(13,2436)=1逆向迭代：逆向迭代：1= 32=3(53) = 32 5 = (13 52)2 5 = 132 55 = 132 5(2436 13187) = 13937 52436 d = e-1mod (n)=13-1mod 2436 =937(2) 首先，將明文以兩個字符為一組進行分組為，首先，將明文以

15、兩個字符為一組進行分組為， pu bl ic ke ye nc ry pt io ns數(shù)字化編碼：數(shù)字化編碼：1520 0111 0802 1004 2404 1302 1724 1519 0814 1318公鑰為公鑰為(13, 2537)加密過程：加密過程：c=me mod n，利用平方，利用平方-乘法計算：乘法計算：e= 13=1101(b)，z=1，n=2537對對m1=1520加密，加密，c1 =152013mod2537 = 0095b3=1z z2m11mod n=(121520)mod 2537=1520b2=1z z2m11mod n=(152021520)mod 2537=1

16、268b1=0z z2m10mod n=(126821)mod 2537=1903b0=1z z2m11mod n=(190321520)mod 2537=95對對m2= 0111加密，加密，c2 = 0111 13mod2537 = 1648b3=1z z2m21mod n=(12111)mod 2537=111b2=1z z2m21mod n=(1112111)mod 2537=188b1=0z z2m20mod n=(18821)mod 2537=2363b0=1z z2m21mod n=(23632111)mod 2537=1648對對m3= 0802加密，加密，c3 = 0802 1

17、3mod2537 = 1410b3=1z z2m31mod n=(12802)mod 2537= 802b2=1z z2m31mod n=(8022802)mod 2537=1398b1=0z z2m30mod n=(139821)mod 2537=914b0=1z z2m31mod n=(9142802)mod 2537=1410對對m4= 1004加密，加密，c4 = 1004 13mod2537 = 1299b3=1z z2m41mod n=(121004)mod 2537= 1004b2=1z z2m41mod n=(100421004)mod 2537=709b1=0z z2m40m

18、od n=(70921)mod 2537=355b0=1z z2m41mod n=(35521004)mod 2537=1299對對m5= 2404加密，加密，c5 = 2404 13mod2537 = 1365b3=1z z2m51mod n=(122404)mod 2537= 2404b2=1z z2m51mod n=(240422404)mod 2537=1699b1=0z z2m50mod n=(169921)mod 2537=2032b0=1z z2m51mod n=(203222404)mod 2537=1365對對m7= 1724加密，加密，c7 = 1724 13mod2537

19、 = 2333b3=1z z2m71mod n=(121724)mod 2537= 1724b2=1z z2m71mod n=(172421724)mod 2537=1784b1=0z z2m70mod n=(178421)mod 2537=1258b0=1z z2m71mod n=(125821724)mod 2537=2333對對m6= 1302加密，加密，c6 = 1302 13mod2537 = 1379b3=1z z2m61mod n=(121302)mod 2537= 1302b2=1z z2m61mod n=(130221302)mod 2537=1126b1=0z z2m60mod n=(112621)mod 2537=1913b0=1z z2m61mod n=(191321302)mod 2537=1379對對m9= 0814加密，加密，c9 = 0814 13m