現(xiàn)代密碼學(xué)-楊波-清華大學(xué)出版社-課后答案

1、 現(xiàn)代密碼學(xué)（第4版）習(xí)題參考答案第1章1、設(shè)仿射變換的加密是：對明文“THE NATIONAL SECURITY AGENCY”加密，并使用解密變換驗證你的解密結(jié)果。解：明文m=THE NATIONAL SECURITY AGENCY用數(shù)字表示為：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 根據(jù)E11,23(m)11*m+23(mod 26)，對明文中的每一個字符計算出相應(yīng)的密文字符c=24 22 15 10 23 24 7 21 10 23 14 13 15 19 9 2 7 24 1 23 11 15

2、10 19 1 由此得到密文c=YWPKXYHVKXONPTJCHYBXLPKTB使用解密變換驗證加密結(jié)果過程如下：由11*191 (mod 26)知11-1=19(注：求模逆元可以通過歐幾里得算法或者直接窮舉125)根據(jù)D11,23(c)11-1*(c-23) (mod 26)19* (c-23) (mod 26)，對密文中的每一個字符計算出相應(yīng)的明文字符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 由此得到m=THE NATIONAL SECURITY AGENCY，解密結(jié)果與明文一致，正確。2、設(shè)由仿射變

3、換對一個明文加密得到的密文為：edsgickxhuklzveqzvkxwkzzukvcuh。又已知明文的前兩個字符為“if”，對該明文解密。解：設(shè)加密變換為c=Ea,b(m)a*m+b(mod 26)由題目可知，明文前兩個字符為if，相應(yīng)密文為ed，即有：E(i)=e，4a*8+b(mod 26) ，(i=8，e=4)，E(f)=d，3a*5+b(mod 26) ，(f=5，d=3)，由上述兩式可求得，a=9，b=10因此解密變換為D9,10(c)9-1*(c-10) (mod 26)又由3*91 (mod 26)可知9-1=3密文對應(yīng)的數(shù)字表示為：c=4 3 18 6 8 2 10 23 7

4、 20 10 11 25 21 4 16 25 21 10 23 22 10 25 20 10 21 2 20 7 根據(jù)D9,10(c)9-1*(c-10) (mod 26)3*(c-10) (mod 26)，對密文中的每一個字符計算出相應(yīng)的明文字符c=8 5 24 14 20 2 0 13 17 4 0 3 19 7 8 18 19 7 0 13 10 0 19 4 0 7 2 4 17 由此得到明文m=ifyoucanreadthisthankateahcer設(shè)多表代換密碼中加密為：對明文“PLEASE SEND ME THE BOOK,MY CREDIT CARD NO IS SIX O

5、NE TWO ONE THREE EIGHT SIX ZERO ONE SIX EIGHT FOUR NINE SEVEN ZERO TWO”用解密變換 驗證你的結(jié)果，其中解：加密時，先將明文分組，每四個一組：再代入加密變換：，得到計算結(jié)果：知密文為：NQXB BTWB DCJJ IJDT XDCF YFSG LYGD MOXN LLGN HAPC QZZQ ZCRG ZEZJ UIEB RRSQ NEMV QDJE MXNA IERP XAKM YRBY TQFM NEMV OME 同上，解密時，先將密文分組，再代入解密變換：得到明文：PLEA SESE NDME THEB OOKM YCR

6、E DITC ARDN OISS IXON ETWO ONETHREE EIGH TSIX ZERO ONES IXEI GHTF OURN INES EVEN ZERO TWO解密驗證結(jié)果與明文相符。4、設(shè)多表代換密碼中，A是22矩陣，B是零矩陣，又知明文“dont”被加密為“elni”，求矩陣A。解：設(shè)矩陣由m=dont=(3,14,13,19)，c=elni=(4,11,13,8)可知:解得：第2章 3級線性反饋移位寄存器在時可有4種線性反饋函數(shù)，設(shè)其初始狀態(tài)為，求各線性反饋函數(shù)的輸出序列及周期。解：設(shè)3級線性反饋特征多項式為，若則共有種可能，對應(yīng)初態(tài)。4種線性反饋函數(shù)分別記為： 輸出序

7、列，由定義2-2得周期 由定義2-3得是不可約多項式，輸出序列由定理2-5周期是m序列 不可約多項式，輸出序列，周期 是m序列 輸出序列，得周期設(shè)n級線性反饋移位寄存器的特征多項式為，初始狀態(tài)為，證明輸出序列的周期等于的階。 解：的階定義為 的最小的。 因為初始狀態(tài)不為零，設(shè)為序列的最小周期。又因為，所以必存在，使得。 又因為定理2-1有,則而的次數(shù)為，的次數(shù)不超過，的次數(shù)不超過。所以，是正整數(shù)，都有。設(shè)，。即周期為的階，若是n次不可約多項式，則序列的最小周期等于的階。生成函數(shù)，的次數(shù)不超過。 不可約，所以，。又因為，所以。設(shè)，初始狀態(tài)為，求此非線性反饋移位寄存器的輸出序列及周期。解：由，初態(tài)

8、為 。線性遞歸可得： 可以得到輸出序列為，周期為。4.設(shè)密鑰流是由級的LFSR產(chǎn)生，其前個比特是,即個01。問第m+3個比特有無可能是1，為什么？解：第m+3個比特上不可能出現(xiàn)1，這是由于：根據(jù)線性移位寄存器的的遞推關(guān)系有：5.設(shè)密鑰流是由n級LFSR產(chǎn)生，其周期為,是任一整數(shù)，在密鑰流中考慮以下比特對 問有多少形如的比特對。試證明你的結(jié)論。解：根據(jù)p23定理2-7，在上的n長m序列在周期為的m序列中對于,長為i的游程有個，且0，1游程各半，那么就有： 1的2游程： 1的3游程： 1的n-2游程： 那么就有： /2得 -得 從而有 即共有個形如的比特對。6.已知流密碼的密文串101011011

9、0和相應(yīng)的明文串0100010001，而且還已知密鑰流是使用3級線性反饋移位寄存器產(chǎn)生的，試破譯該密碼系統(tǒng)。解：由已知可得相應(yīng)的密鑰流序列為1110100111，又因為是3級線性反饋移位寄存器，可得以下方程：將值代入得: , 由此可得密鑰流的遞推關(guān)系為：。7.若GF(2)上的二元加法流密碼的密鑰生成器是n級線性反饋移位寄存器，產(chǎn)生的密鑰是m序列。2.5節(jié)已知，敵手若知道一段長為2n的明密文對就可破譯密鑰流生成器。若敵手僅知道長為2n-2的明密文對，問如何破譯密鑰流生成器。解：如果敵手僅僅知道長為2n-2的明密文對，他可以構(gòu)造出以下的長為2n的明密文對：不妨設(shè)：明文： 密文： 其中：為已知的，為

10、未知的。 為已知的，為未知的。 的可能取值為00,01,10,11。的可能取值為00,01,10,11。共有16種組合方案，分別破解得到密鑰流，在破解的結(jié)果中符合m序列的性質(zhì)密鑰流即為正確的方案，有可能不唯一。8.設(shè)J-K觸發(fā)器中和分別為3級和4級m序列，且，求輸出序列及周期。解：由J-K觸發(fā)器可知 此時和分別為3級和4級m序列，則的周期為。9.設(shè)基本鐘控序列生成器中和分別為2級和3級m序列，且，求輸出序列及周期。解：令基本鐘控序列生成器中的周期為，的周期為，則輸出序列的周期為，。記LFSR2產(chǎn)生，其狀態(tài)向量為，可得的變化情況如下：輸出序列第3章 (1) 設(shè)M和M的逐比特取補，證明在DES中，

11、如果對明文分組和加密密鑰都逐比特取補，那么得到的密文也是原密文的逐比特取補，即： 如果Y=DESK(X)，那么Y=DESK(X)提示：對任意兩個長度相等的比特串A和B，證明。對DES進行窮搜索攻擊時，需要在由256個密鑰構(gòu)成的密鑰空間進行，能否根據(jù)(1)的結(jié)論減少進行窮搜索攻擊時所用的密鑰空間。（1）證明：設(shè)Li和Ri分別不是第i輪DES變換的左右部分，i=0,1,16, 則加密過程為:若將明文和密鑰k同時取補，則加密過程為：其中，的作用是將數(shù)據(jù)的左、右半部分擴展后與密鑰進行逐比特異或運算，因此，再經(jīng)過S盒，并將輸出結(jié)果進行置換運算P之后有：，而，所以有。同時有，所以明文P與密鑰K同時取補后有

12、。（2）答：根據(jù)(1)的結(jié)論進行窮搜索攻擊, 可將待搜索的密鑰空間減少一半，即255個。因為給定明文x，則，由(1)知，則一次搜索就包含了x和x 兩種明文情況。2. 證明DES解密變換是加密變換的逆。證明：令為左右位置交換函數(shù)，,則第i次迭代變換為:,又 有,同時，,即， ,DES加密過程在密鑰k作用下為:,解密過程為: ,所以，即解密變換是加密變換的逆。（得證）3.在DES的EBC模式中，如果在密文分組中有一個錯誤，解密后僅相應(yīng)的明文分組受到影響。然而在CBC模式中，將有錯誤傳播。例如在圖3-11中C1中的一個錯誤明顯地將影響P1和P2的結(jié)果。 (1) P2后的分組是否受到影響？(2) 設(shè)加

13、密前的明文分組P1中有一個比特的錯誤，問這一錯誤將在多少個密文分組中傳播？對接收者產(chǎn)生什么影響？答：（1）在CBC模式中，若密文分組中有一個錯誤C1，則解密時明文分組中都將受到影響，而后的分組都不受影響，即CBC的錯誤傳播長度為2，具有自恢復(fù)能力。（2）若明文分組P1有錯誤，則以后的密文分組都將出現(xiàn)錯誤，但對接收者來說，經(jīng)過解密后，除P1有錯誤外，其余的明文分組都能正確恢復(fù)。4. 在8比特CFB模式中，如果在密文字符中出現(xiàn)1比特的錯誤，問該錯誤能傳播多遠？答：在8比特CFB模式中，若密文有1比特錯誤，則會影響當前分組以及后續(xù)分組的解密，會使解密輸出連續(xù)9組出錯，即錯誤傳播的長度為9。5. 在實

14、現(xiàn)IDEA時，最困難得部分是模乘法運算。以下關(guān)系給出了實現(xiàn)模乘法的一種有效方法，其中a和b是兩個n比特的非0整數(shù)：(1) 證明存在唯一的非負整數(shù)q和r使得；(2) 求q和r的上下界；(3) 證明;(4) 求關(guān)于q的表達式；(5) 求關(guān)于q和r的表達式；(6) 用(4)和(5)的結(jié)果求r的表達式，說明r的含義。 (1) 證明： 假設(shè)存在使得，有 因為，所以，因此，只能有。（2）解：，顯然，a和b的最大值均為，則有所以，(3)證明：(4)解：根據(jù)，得(5)解：根據(jù)，得解：當時，根據(jù)及得，同理，當 時，余數(shù)r表示ab的n個最低有效位與ab右移位數(shù)n之差。6. (1) 在IDEA的模乘運算中，為什么將

15、模乘取為而不是？(2) 在IDEA的模加運算中，為什么將模乘取為而不是？答：(1) 在IDEA模乘運算中，必須保證運算構(gòu)成一個群，因此模數(shù)必須為素數(shù)，故不能取216。(2) 同一群內(nèi)的分配律和結(jié)合律都成立，但IDEA算法中要保證模數(shù)的加法和模數(shù)的乘法，比特異或之間分配律和結(jié)合律不成立，因此模加運算不能和模乘運算在同一個群內(nèi)，即不能選模216+1，而216在模加運算中必為一個群.證明SM4算法滿足對合性，即加密過程和解密過程一樣，只是密鑰使用的順序相反。證明： SM4算法的加密輪函數(shù)分為加密函數(shù)G和數(shù)據(jù)交換E。其中G對數(shù)據(jù)進行加密處理，E進行數(shù)據(jù)順序交換。即加密輪函數(shù) Fi=GiE其中，Gi=G

16、iXi,Xi+1,Xi+2,Xi+3,rki (i=0,1,2,31)=(XiTXi+1,Xi+2,Xi+3,rki,Xi+1,Xi+2,Xi+3)EXi+4,(Xi+1,Xi+2,Xi+3)=Xi+1,Xi+2,Xi+3,Xi+4, (i=0,1,2,31)因為， (Gi)2=Gi(XiTXi+1,Xi+2,Xi+3,rki,Xi+1,Xi+2,Xi+3,rki)=(XiTXi+1,Xi+2,Xi+3,rkiTXi+1,Xi+2,Xi+3,rki,Xi+1,Xi+2,Xi+3,rki)=Xi,Xi+1,Xi+2,Xi+3,rki=I因此，加密函數(shù)G是對合的。E變換為：EXi+4,(Xi+1,

17、Xi+2,Xi+3)=( Xi+1,Xi+2,Xi+3, Xi+4)E2Xi+4,(Xi+1,Xi+2,Xi+3)=I顯然，E是對合運算。綜上，加密輪函數(shù)是對合的。根據(jù)加密框圖，可將SM4的加密過程寫為：SM4=G0EG1EG30EG31R根據(jù)解密框圖，可將SM4的解密過程寫為：SM4-1=G31EG30EG1EG0R比較SM4與SM4-1可知，運算相同，只有密鑰的使用順序不同。所以，SM4算法是對合的。第4章1. 證明以下關(guān)系：(1) ，則；(2) ，則；(3) ，則。解：(1)設(shè)，由題意得，且存在整數(shù)，使得，即，證得。(2)已知，則存在整數(shù)，使得，證得。(3)已知，則存在整數(shù)，使得，證得。

18、2. 證明以下關(guān)系：(1) ；(2) 。解：(1)設(shè)，則存在整數(shù)，使得即。(2)設(shè)，則存在整數(shù)，使得即。3. 用Fermat定理求。解：因為是素數(shù)，且，則由Fermat定理可得：；又根據(jù)性質(zhì)，可得：。4. 用推廣的Euclid算法求的逆元。解：運算步驟如下表所示：循環(huán)次數(shù)QX1X2X3Y1Y2Y3初值1011901671101671-152211-152-121533-12154-77424-77-9161所以。5. 求。解：由Euclid算法，得：所以。6. 求解下列同余方程組：解：根據(jù)中國剩余定理求解該同余方程組，記，則有，所以方程組的解為7. 計算下列Legendre符號：(1) ；(2

19、) ；(3) 。解：(1)(2)(3)8. 求的所有本原根。解：因為，所以的所有不同的素因子為，即對每個，只需計算。又因為，所以有8個本原根。滿足且的為的本原根，即。9. 證明當且僅當是素數(shù)時，是域。證明：(1)若是域，則，均為Abel群。顯然為Abel群，與n是否為素數(shù)無關(guān)；但若為Abel群，其條件之一必須保證對任意有模乘法逆元，即對任意，有，使得，所以，即，為素數(shù)。(2)若不是素數(shù)，則，即至少存在一個，使得，即無模乘法逆元，因此不能保證均為Abel群，即不是域。10. 設(shè)通信雙方使用RSA加密體制，接收方的公開鑰是，接收到的密文是，求明文。解：因為，則，所以，即明文。11. 已知的運行時間

20、是，用中國剩余定理改進RSA的解密運算。如果不考慮中國剩余定理的計算代價，證明改進后的解密運算速度是原解密運算速度的4倍。證明：RSA的兩個大素因子的長度近似相等，約為模數(shù)的比特長度的一半，即，而在中國剩余定理中，需要對模和模進行模指數(shù)運算，這與的運行時間規(guī)律相似，所以每一個模指數(shù)運算的運行時間仍然是其模長的三次冪，即。在不考慮中國剩余定理計算代價的情況下，RSA解密運算的總運行時間為兩個模指數(shù)運算的運行時間之和，即，證得改進后的解密運算速度是原解密運算速度的4倍。12. 設(shè)RSA加密體制的公開鑰是(1) 用重復(fù)平方法加密明文，得中間結(jié)果為：若敵手得到以上中間結(jié)果就很容易分解，問敵手如何分解。

21、(2) 求解密密鑰。解：(1)由以上中間結(jié)果可得：。由，可知分解為。(2)解密密鑰，由擴展的Eucild算法可得。13. 在ElGamal加密體制中，設(shè)素數(shù)，本原根，(1) 如果接收方B的公開鑰是，發(fā)送方A選擇的隨機整數(shù)，求明文所對應(yīng)的密文。(2) 如果A選擇另一個隨機整數(shù)，使得明文加密后的密文是，求。解：(1)密文，其中：。所以明文對應(yīng)的密文為。(2)由，窮舉法可得。所以。14. 設(shè)背包密碼系統(tǒng)的超遞增序列為，乘數(shù)，模數(shù)，試對good night加密。解：由，乘數(shù)，模數(shù)，可得。明文“good night”的編碼為“00111”，“01111”，“01111”，“00100”，“00000”，

22、“01110”，“01001”，“00111”，“01000”，“10100”，則有：所以明文“good night”相應(yīng)的密文為。15. 設(shè)背包密碼系統(tǒng)的超遞增序列為，乘數(shù)，模數(shù)，試對解密。解：因為，則。所以其對應(yīng)的明文分組為，由課本120頁表4-7可得明文為“ADRA”。16. 已知，都是素數(shù)，其Jacobi符號都是，其中，證明：(1) 是模的平方剩余，當且僅當都是模的平方剩余或都是模的非平方剩余。(2) 是模的平方剩余，當且僅當都是模的平方剩余或都是模的非平方剩余。證明：(1)必要性：若是模的平方剩余，即存在使得，而，顯然必有，所以也同時是模和模的平方剩余，即。又由題意得，即。所以：當時

23、，有，即同時是模和模的平方剩余，也同時是模和模的平方剩余，即都是模的平方剩余；當時，有，即同時是模和模的非平方剩余，也同時是模和模的非平方剩余，即都是模的非平方剩余。充分性：若都是模的平方剩余，則也是模和模的平方剩余，即，即同時是模和模的平方剩余，所以是模的平方剩余；若都是模的非平方剩余，則它們對于模和模至少有一種情況是非平方剩余，不妨設(shè)，則有，即也都是模和模的非平方剩余。所以，同理，即同時是模和模的平方剩余，所以是模的平方剩余。(2)若是模的平方剩余，則同時是模和模的平方剩余，所以，由于勒讓德符號的偶數(shù)次方肯定為（情況除外），即有，余下證明同(1)。提示：17. 在Rabin密碼體制中設(shè)：

24、(1) 確定在模下的4個平方根。(2) 求明文消息所對應(yīng)的密文。(3) 對上述密文，確定可能的4個明文。解：(1)已知，由中國剩余定理可得到等價方程組：因為，所以。經(jīng)組合可得到以下四個方程組：根據(jù)中國剩余定理，則有：第一個方程組的解為；第二個方程組的解為；第三個方程組的解為；第四個方程組的解為。所以，的四個平方根為。(2)對應(yīng)的密文為。(3)解密即解，由中國剩余定理可得到等價方程組：因為，所以，經(jīng)組合可得到以下四個方程組： 根據(jù)中國剩余定理，則有：第一個方程組的解為；第二個方程組的解為；第三個方程組的解為；第四個方程組的解為。所以，四個可能的明文為。18. 橢圓曲線表示，求其上的所有點。解：模

25、的平方剩余有。時，無解，曲線無與這一相對應(yīng)的點；時，無解，曲線無與這一相對應(yīng)的點；時，無解，曲線無與這一相對應(yīng)的點；時，；時，；時，；時，。所以橢圓曲線上的所有點為：。19. 已知點在橢圓曲線上，求和。解：(1)求。所以。(2)易知。所以。20. 利用橢圓曲線實現(xiàn)ElGamal密碼體制，設(shè)橢圓曲線是，生成元，接收方A的秘密鑰。(1) 求A的公開鑰。(2) 發(fā)送方B欲發(fā)送消息，選擇隨機數(shù)，求密文。(3) 顯示接收方A從密文恢復(fù)消息的過程。解：(1)易知公開鑰。求。所以。由題19可得，即。所以。(2)密文。求：。求：。所以。求：。所以。綜上：。(3)從密文恢復(fù)消息的過程如下：其中：a)計算先計算。

26、所以。 = 2 * GB3 計算。所以。 = 3 * GB3 計算。所以。 = 4 * GB3 計算。所以。b)計算。所以。第5章在公鑰體制中，每一用戶U都有自己的公開鑰和秘密鑰。如果任意兩個用戶A,B按以下方式通信，A發(fā)給B消息，B收到后，自動向A返回消息，以使A知道B確實收到報文m，（1）問用戶C怎樣通過攻擊手段獲取報文m？解：當A發(fā)給B消息時，A的身份“A”并沒有認證，而B在收到消息后也無法對發(fā)送者進行檢驗，且身份A，B均明文傳輸，因此用戶C可通過如下手段獲得報文m：當A發(fā)給B消息時，C截取該消息并將身份A替換為自己的身份C，將修改后的消息發(fā)給接收者B；B提取消息后，根據(jù)身份“C”將返回

27、消息；C再次劫取B返回的消息，用自己的私鑰解密出消息m，并用A的公鑰對m加密后將消息發(fā)給A。這樣，用戶C獲得了報文m而沒有影響A,B之間的正常通信，實現(xiàn)了攻擊。（2）若通信格式變?yōu)椋篈發(fā)給B消息B向A返回消息這時的安全性如何？分析這時A、B如何相互認證并傳遞消息m。解：根據(jù)消息格式，先對消息m進行了簽名，然后再進行加密，傳送的消息具有了保密性和認證性，敵手無法獲得報文明文，安全性提高。A，B之間相互認證傳遞消息的過程如下：B收到消息時，先用B自己的私鑰解密得到消息，然后根據(jù)提取的身份信息A，用A的公鑰對消息m的簽名的正確性進行驗證，如果驗證通過，則說明消息確實來自A。反之A用相同的方法可驗證確

28、實來自B，從而實現(xiàn)了相互認證。Diffie-Hellman密鑰交換協(xié)議易受中間人攻擊，即攻擊者截獲通信雙方通信的內(nèi)容后可分別冒充通信雙方，以獲得通信雙方協(xié)商的密鑰。詳細分析攻擊者如何實施攻擊。解：雖然Diffie-Hellman密鑰交換算法十分巧妙，但由于沒有認證功能，存在中間人攻擊。當Alice和Bob交換數(shù)據(jù)時，Trudy 攔截通信信息，并冒充Alice欺騙Bob，冒充Bob欺騙Alice。其過程如下：（1）Alice選取大的隨機數(shù)x，并計算，Alice將g、P、X傳送給Bob，但被Trudy攔截；（2）Trudy冒充Alice選取大的隨機數(shù)z，并計算，Trudy將Z傳送給Bob；（3）T

29、rudy冒充Bob，再將傳送給Alice；（4）Bob選取大的隨機數(shù)y，并計算，Bob將Y傳送給Alice，但被Trudy攔截。由（1）、（3）Alice與 Trudy 共享了一個秘密密鑰，由（2）、（4）Trudy與Bob共享了一個秘密密鑰。以后在通信過程中，只要Trudy作中間人，Alice和 Bob不會發(fā)現(xiàn)通信的異常，但 Trudy可以獲取所有通信內(nèi)容。Diffie-Hellman密鑰交換過程中，設(shè)大素數(shù)p=11，a=2是p的本原根，（1）用戶A的公開鑰，求其秘密鑰。解：滿足即，所以有=6。（2）設(shè)用戶B的公開鑰，求A和B的共享密鑰K。解：由Diffie-Hellman協(xié)議可知。線性同余

30、算法，問：（1）該算法產(chǎn)生的數(shù)列的最大周期是多少？解：由于模因此它沒有原根，又由遞推式不難得知。因此該算法產(chǎn)生的序列的最大周期為的最大階l，而，但。若l=4，則不難驗證，時，數(shù)列周期為4，因此該算法產(chǎn)生數(shù)列的最大周期是4。（2）a的值是多少？解：a必須滿足，所以a在中取值。周期為4的有，即為a的取值（3）對種子有何限制？解：種子必須滿足。在Shamir秘密分割門限方案中，設(shè)k=3，n=5，q=17，5個子密鑰分別是8、7、10、0、11，從中任選3個，構(gòu)造插值多項式并求秘密數(shù)據(jù)s。解：取，構(gòu)造插值多項式在基于中國剩余定理的秘密分割門限方案中，設(shè)，三個子秘鑰分別是6、3、4，求秘密數(shù)據(jù)s。解：

31、由題設(shè)可得s應(yīng)滿足因為，3個子密鑰分別是6，3，4，那么，由， 可得=48由，可得=48由，可得= 即秘密數(shù)據(jù)s為48第6章16.1.3節(jié)介紹的數(shù)據(jù)認證算法是由CBC模式的DES定義的，其中初始向量取為0，試說明使用CFB模式也可獲得相同結(jié)果。 6.1.3節(jié)用CBC模式的DES設(shè)計數(shù)據(jù)認證算法為： QUOTE O1=EK(D1) O1=EK(D1)O2=EK(D2O1)O3=EK(D3O2)ON=EK(DNEK(DN-1EK(D2EK(D1)ON=EK(DNON-1) 如果改用CFB模式來實現(xiàn)，由于輸出為64位，所以必須取 QUOTE j=64 j=64，也就是每次移位寄存器左移整個64位。為

32、了達到相同的結(jié)果，可取CFB模式中 QUOTE IV=D1,Pi=Di+1(i=1,?N-1),PN=0 IV=D1,Pi=Di+1(i=1,?N-1),PN=0，則有： QUOTE O2=D3EK(O1)O3=D4EK(O2)ON=EK(ON-1)=EK(DNEK(DN-1EK(D2EK(D1)ON-1=DNEK(ON-2)ON=0EK(ON-1)比較兩式， QUOTE ON ON作為消息認證碼，結(jié)果相同。2有很多哈希函數(shù)是由CBC模式的分組加密技術(shù)構(gòu)造的，其中的密鑰取為消息分組。例如將消息M分成分組M1, M2,MN，H0=初值，迭代關(guān)系為 QUOTE (i=1,2,N),哈希值取為HN，

33、其中E是分組加密算法。（1）設(shè)E為DES，第3章的習(xí)題已證明如果對明文分組和加密密鑰都逐比特取補，那么得到的密文也是原密文的逐比特取補，即如果Y=DESK（X），那么Y=DESK（X）。利用這一結(jié)論證明在上述哈希函數(shù)中可對消息進行修改但卻保持哈希值不變。答：敵手主要是通過修改函數(shù)的輸入值 QUOTE M1,M2,?,MN M1,M2,?,MN和 QUOTE H0 H0來構(gòu)造碰撞。H1=DESM1(H0)H0H2=DESM2(H1)H1HN=DESMN(HN)HN-1利用 QUOTE Y=DESK(X) Y=DESK(X)和 QUOTE 兩個性質(zhì)可知，若敵手同時對 QUOTE M1 M1和 QU

34、OTE H0 H0逐比特取補，則由性質(zhì)一知 QUOTE DESM1(H0) DESM1(H0)也被逐比特求補，由性質(zhì)二知 QUOTE H1 H1保持不變，所以 QUOTE H2,?HN H2,?HN也都不受影響，所以有： QUOTE H(M1M2?MN)=H(M1M2?MN)=HN H(M1M2?MN)=H(M1M2?MN)=HN（2）若迭代關(guān)系Hi=EHi-1(Mi)Mi，證明仍可對其進行上述攻擊。答：改迭代關(guān)系為 QUOTE ，則敵手也可同時對 QUOTE M1 M1和 QUOTE H0 H0逐比特取補，由性質(zhì)一知 QUOTE DESH0(M1) DESH0(M1)也被逐比特求補，由性質(zhì)二

35、知 QUOTE H1,?HN H1,?HN都不受影響，故仍可進行上述攻擊。3考慮用公鑰加密算法構(gòu)造哈希函數(shù)，設(shè)算法是RSA，將消息分組后用公開鑰加密第一個分組，加密結(jié)果與第二個分組異或后，再對其加密，一直進行下去。設(shè)一消息被分成兩個分組B1和B2，其哈希值為H(B1, B2)=RSA(RSA(B1)B2)。證明對任一分組C1可選C2，使得H(C1, C2)= H(B1, B2)。證明用這種攻擊法，可攻擊上述用公鑰加密算法構(gòu)造的哈希函數(shù)。證明：對任一分組 QUOTE C1 C1，可構(gòu)造 QUOTE C2 C2如下： QUOTE ，則H(C1,C2)=RSA(RSA(C1)C2)=RSA(RSA(

36、C1)RSA(C1)RSA(B1)B2)=RSA(RSA(B1)B2)=H(B1,B2)設(shè)哈希函數(shù)的輸入消息分組為 QUOTE M1M2?MN M1M2?MN，則可任取 QUOTE M1 M1替代 QUOTE M1 M1，并由上述方法構(gòu)造 QUOTE M2 M2替代 QUOTE M2 M2，可得 QUOTE H(M1M2?MN)=H(M1M2?MN) H(M1M2?MN)=H(M1M2?MN)，攻擊成功。在圖6-11中，假定有80個32比特長的字用于存儲每一個Wt，因此在處理信息分組前，可預(yù)先計算出這80個值。為節(jié)省存儲空間，考慮有16個字的循環(huán)移位寄存器，其初值存儲前16個值（即W0，W1，

37、, W15），設(shè)計一個算法計算以后的每一個Wt。答：XORCLS1 QUOTE Wi WiW0W1W2W3W4W5W6W7W8W9W10W11W12W13W14W15 QUOTE W0W15 W0W15為消息分組的16個字，初始放在移位寄存器中，如上圖連接電路。 QUOTE CLS1 CLS1的輸出反饋到移位寄存器右邊的輸入端，則每個時鐘到來時，移位寄存器從左邊輸出端移出一個字 QUOTE Wi(i=0,?,79) Wi(i=0,?,79)。5.對SHA，計算W16，W17，W18，W19答：W16=CLS1(W0W2W8W13)W17=CLS1(W1W3W9W14)W18=CLS1(W2W4

38、W10W15)W19=CLS1(W3W5W11W16)6設(shè)a1a2a3a4是32比特長的字中的4個字節(jié)，每一給ai可看作由二進制表示的0255之間的整數(shù)，在大端方式中，該字表示整數(shù)a1224+a2216+a328+a4，在小端結(jié)構(gòu)中，該字表示整數(shù)a4224+a3216+a228+a1。（1）MD5使用小端結(jié)構(gòu)，因消息的摘要值不應(yīng)依賴于算法所用的結(jié)構(gòu)，因此在MD5中為了對以大端方式存儲的兩個字X=x1x2x3x4和Y=y1y2y3y4進行模2加法運算，必須要對這兩個字進行調(diào)整，問如何進行？答：由于MD5使用little-endian結(jié)構(gòu)，而X，Y使用的是big-endian存儲結(jié)構(gòu)，因此必須把X

39、，Y轉(zhuǎn)換成little-endian格式，設(shè)轉(zhuǎn)換成： QUOTE X=x1x2x3x4 X=x1x2x3x4， QUOTE Y=y1y2y3y4 Y=y1y2y3y4，則有x1224+x2216+x328+x4=x4224+x3216+x228+x1x1=x4,x2=x3,x3=x2,x4=x1（2）SHA使用大端方式，問如何對以小端結(jié)構(gòu)存儲的兩個字X和Y進行模2加法運算。答：由于SHA使用big-endian結(jié)構(gòu)，而X，Y使用的是little-endian存儲結(jié)構(gòu)，因此必須把X，Y轉(zhuǎn)換成big-endian格式，設(shè)轉(zhuǎn)換成： QUOTE X=x1x2x3x4 X=x1x2x3x4， QUOTE

40、 Y=y1y2y3y4 Y=y1y2y3y4，則有x4224+x3216+x228+x1=x1224+x2216+x328+x4x1=x4,x2=x3,x3=x2,x4=x1第7章 1. 在DSS數(shù)字簽名標準中，于是，若取，則。在對消息簽名時，選擇，計算簽名并進行驗證。解：(1)簽名過程：為了簡化，用代替，則用戶對消息的簽名為。計算，。所以簽名。(2)驗證過程：接收方收到的消息為，簽名為。計算，。因為，所以認為簽名有效，即驗證通過。2. 在DSA簽名算法中，參數(shù)泄露會產(chǎn)生什么后果？解：若攻擊者得到了一個有效簽名，并且知道了DSA簽名算法中的參數(shù)，那么在簽名方程中只存在一個未知數(shù)，即用戶的秘密鑰

41、，所以攻擊者可以求得秘密鑰。因此，參數(shù)泄漏將導(dǎo)致簽名秘密鑰的泄漏，攻擊者可以偽造任意消息的簽名。第8章假設(shè)你知道一個背包問題的解，試設(shè)計一個協(xié)議，以零知識證明方式證明你的確知道問題的解。解一：設(shè)背包向量為，證明者P知道一個背包容積的解，即，P以零知識證明方式向驗證者證明自己掌握秘密的協(xié)議如下： P隨機選取一向量，計算，將發(fā)給V。 V隨機選，將發(fā)給P； P計算，即時，；時，將發(fā)給V。注：如果，P展示的解，即；如果，P展示被加密的的解，即。 若，V接受P的證明。協(xié)議的完備性、正確性和安全性(1) 完備性：如果P和V遵守協(xié)議，且P知道的解，則應(yīng)答使得，V接受P的證明。 (2) 正確性：假冒的證明者E

42、可按以下方式以的概率騙得V接受自己的證明： E隨機選取一向量和，計算，將發(fā)給V。 V隨機選，將發(fā)給E； E將發(fā)給V。V的驗證方程為。當時，方程成立，V接受E的證明，E欺騙成功。因的概率是，所以E成功的概率是。另一方面，是E成功的最好概率，否則假定E以大于的概率使V相信自己的證明，那么E知道一個，對這個，他可以正確回答V的兩個詢問和，意味著E能計算，由此可計算，因此得秘密。(3) 安全性：根據(jù)以上的討論知，假冒的證明者E欺騙V成功的概率為，這個概率太大了。為減少這個概率，可以將協(xié)議重復(fù)執(zhí)行多次，設(shè)執(zhí)行次，則欺騙成功的概率將減少到。解二：(1)構(gòu)造背包問題先選大素數(shù)， ，是素數(shù)，且 也為素數(shù)，為的

43、本原根。P隨機選取個整數(shù)， (不用超遞增序列)，計算式中，為秘密密鑰；， 為公開。(2)零知識證明協(xié)議1)P隨機選擇，計算 ，并將傳送給V；2)V隨機選擇個二進制比特序列，并將其傳送給P；3)P計算，并將其傳送給V。4)V驗證，計算 比較是否成立，若成立，說明P了解秘密密鑰，；反之，P為假冒。(3)安全性此類算法的安全威脅主要來自P欺騙V或V假冒P。假如使用的背包和離散對數(shù)沒有問題，P欺騙V和V假冒P成功的概率都基于 的隨機性，若每一個的選取為0或1的概率為，則假冒或欺騙成功的幾率為；若該協(xié)議重復(fù)次，成功的幾率為。在8.1.4節(jié)，基于大數(shù)分解問題的“多傳一”不經(jīng)意傳輸協(xié)議中為什么要求？設(shè)，B選

44、擇，且想獲得A的秘密，分析B是否能成功獲得。解：(1) 要求是為了保證同一數(shù)在模下的兩個平方根有相反的Jacobi符號。(2) B先計算Jacobi符號和，將4,-1發(fā)給A。接下來A計算4 mod55的平方根，求出4在mod 5時的平方根為2，4在mod11時的平方根為2，可得以下四個方程組： 由第一個方程組的解為；第二個方程組的解為；第三個方程組的解為；第四個方程組的解為；因，A將42或53發(fā)給B。當A將42發(fā)給B時，B由得到的一個因子，從而得到的分解式，從而獲得A的秘密。當A將53發(fā)給B時，因,所以B不能計算出的一個因子，沒有得到任何新信息，從而不能獲得A的秘密。設(shè)是素數(shù)，群的元素是群的生

45、成元，當且僅當對每一，存在一整數(shù)，使得。(1) 在中均勻、隨機選取一元素，證明，如果不是的生成元，則存在一整數(shù)，使得成立的概率至多是。(2) 給出是的生成元的零知識證明。(3) 在(2)中的零知識證明中，證明者能否在多項式時間內(nèi)完成證明，為什么？解：(1) 因為不是的生成元，記循環(huán)群為，顯然是的子群，且，設(shè)，是一個大于1的正整數(shù)，所以。在中均勻、隨機選取一元素，若，則可在上找到一個，使得成立。而的概率至多是，所以成立的概率至多是。(2) V在中任意取一個元素，發(fā)送給P。 P知道，使得。P在中隨機取一個元素，計算并發(fā)送給V。V隨機選，將發(fā)給P；P計算并發(fā)送給VV驗證，若成立，則接受P的證明。P和

46、V重復(fù)以上過程次。(3) 以上的證明可以在多項式時間內(nèi)完成。因為，是一個有限值，可以在多項式時間內(nèi)完成。設(shè)n是兩個未知大素數(shù)p和q的乘積，x0,x1Zn*且其中至少一個是模n的二次剩余。又設(shè)x0,x1模n的Jacobi符號都為1，考慮下面交互證明系統(tǒng)，其中x0,x1和n作為輸入，P為證明者，V為驗證者：P隨機選擇iR0,1,vb,v1-bRZn*，計算ybvb2 mod n及y1-bv1-b2x1-bi-1 mod n，將y0,y1發(fā)送給V。V隨機選擇cR0,1，將c發(fā)送給P。P計算zbuicvbmodn,z1-bv1-b，將zb,z1發(fā)送給V。V檢查z02y0 mod n和z12x1cy1

47、mod n是否成立，或z02x0y0 mod n和z12x11-cy1 mod n是否成立。如果不成立，則拒絕并終止。以上過程重復(fù)log2v次。證明以上協(xié)議證明了x0,x1中至少有一個是模n的二次剩余。證明以上協(xié)議是完備的。解：對于給定的y0,y1和x0,x1,證明者P都能夠回答c=0或c=1的兩個挑戰(zhàn)；故說明y0和y0 x0都是模n的二次剩余或者y1和y1x1都是模n的二次剩余；根據(jù)數(shù)論知識可得：x0或x1至少有一個是模n的二次剩余。若Prover和Verifier都是誠實的，且(1)是正確的，顯然，驗證者最終會接受證明者的證明。第9章 可證明安全習(xí)題1、解釋主義安全的概念，這一概念可用于抵

48、抗如下攻擊嗎？ 1）、被動的多項式時間有界敵手； 2）、被動的多項式時間無界敵手； 3）、主動的多項式時間有界敵手。答：語義安全：一個安全的加密方案應(yīng)使敵手通過密文得不到任何信息，即使是1比特的信息。此概念可用于抵抗被動的多項式時間有界敵手和主動的多項式有界敵手，但不能抵抗被動的多項式無界敵手。2. Rabin密碼體制是IND-CPA安全的嗎？是IND-CCA安全的嗎？是IND-CCA2安全的嗎？答：Rabin密碼體制Rabin密碼體制是RSA密碼體制的一種修正，假定模數(shù)不能被分解，該類體制對于選擇明文攻擊是計算安全的。因此，Rabin密碼體制提供了一個可證明安全的密碼體制的例子：假定分解整數(shù)

49、問題是整數(shù)上不可行的，那么Rabin密碼體制是安全的。Rabin密碼體制：密鑰生成設(shè)，其中和是素數(shù)，且，即這兩個素數(shù)形式為，計算。為公鑰，為私鑰。加密其中 是明文分組，是對應(yīng)的密文分組。解密解密也就是求模的平方根，即解，該方程等價于方程組：由于，所以可以解出每個方程有兩個解：兩兩組合可得4個同余方程組： = 1 * GB3 、 = 2 * GB3 、 = 3 * GB3 、 = 4 * GB3 、由中國剩余定理可解出每一個方程組的解，共四個，即每一密文對應(yīng)的明文不唯一。為有效確定明文一般在中加入某些代表性信息，如：發(fā)送者身份號、接受者身份號、時間、日期等下面證明，當時，兩個方程，的平方根都很容

50、易求出。由得，即是一個整數(shù)。因是模的平方剩余，故設(shè)的根為，即，則所以和是方程的兩個根。同理，和是方程的兩個根。當時，求解方程與分解是等價的，所以破譯Rabin密碼體制的困難程度等價于大整數(shù)的分解。所以Rabin密碼體制對選擇明文攻擊是可證明安全的，然而該體制對選擇密文攻擊是完全不安全的，因諭言機用實際解密算法來代替，就可以攻破密碼體制。所以Rabin密碼體制是IND-CPA安全的，但不是IND-CCA安全的，也不是IND-CCA2安全的。3.計算性Diffie-Hellman問題（Computational Diffie-Hellman,CDH問題）是已知，計算。離散對數(shù)問題（Discrete

51、 Logarithm問題，DL問題）是已知，計算。證明如下關(guān)系：證明：1）、證明定義DDH假設(shè): 設(shè)是階為大素數(shù)的群，為的生成元。則以下兩個分布：隨機四元組。四元組（稱為Diffie-Hellman四元組，簡稱DH四元組）。是計算上不可區(qū)分的，稱為DDH假設(shè)。具體地說，對任一敵手，區(qū)分和的優(yōu)勢是可忽略的。設(shè)是構(gòu)成的集合，是構(gòu)成的集合下面構(gòu)造一個敵手，利用來攻擊CDH問題。設(shè),輸入四元組,目標是判斷還是，如果則說明，輸出；否則則說明，終止。此時選中t的概率是，故獲勝的概率是2）、證明由CDH問題可知，對任一敵手，在已知情況下，計算的優(yōu)勢是可忽略的。那么下面構(gòu)造一個敵手，利用來攻擊DL問題。則已知

52、，目標是計算。設(shè)，且；如果：，則;或,則；否則終止。此時敵手選中的概率為又因為計算的優(yōu)勢是，所以獲勝的概率為。4.設(shè)是單鑰加密方案，將9.2.2節(jié)中的加密方案修改如下：輸入公開鑰和消息，選擇一個隨機數(shù)，輸出密文 。證明如果RSA問題是困難的，則修改后的加密方案是IND-CPA安全的公鑰加密方案。證明：設(shè)GenRSA是RSA加密方案的密鑰生成算法，它的輸入為，輸出為模數(shù)（為2個比特素數(shù)的乘積），整數(shù)滿足。又設(shè)是一個哈希函數(shù)，其中是一個任意的多項式。加密方案如下：密鑰產(chǎn)生過程： ； ，。加密過程（其中）: ；輸出（，）解密過程：: ；輸出。定理：設(shè)是一個隨機諭言機，如果與方案GenRSA相關(guān)的RS

53、A問題是困難的，則方案是IND-CPA安全的。即，設(shè)存在一個IND-CPA敵手以的優(yōu)勢攻破方案，那么一定存在一個敵手至少以的優(yōu)勢解決RSA問題。證明：的IND-CPA游戲如下：: ; ,; ; ;，其中；，； 如果，則返回1，否則返回0敵手的優(yōu)勢定義為安全參數(shù)的函數(shù)： 下面證明方案可歸約到RSA假設(shè)。敵手已知，以（攻擊方案）作為子程序，進行以下過程，目標是計算。選取一個隨機串，作為的猜測值，將公鑰發(fā)給。H詢問：建立一個表（初始為空），元素類型，在任何時候都能發(fā)出對的詢問，做如下應(yīng)答（設(shè)詢問為）如果已經(jīng)在，則以中的應(yīng)答；如果以應(yīng)答，將存入表中，并記下。否則隨機選擇以應(yīng)答，并將存入表中。挑戰(zhàn)：輸出

54、兩個挑戰(zhàn)的消息和，隨機選擇，并令，將給作為密文。在執(zhí)行結(jié)束后（在輸出其猜測之后），輸出第2）步記下的。設(shè)表示事件：在模擬中發(fā)出詢問，即出現(xiàn)在中。斷言1：在以上模擬過程中，的模擬是完備的。證明 在以上模擬中，的視圖與其在真實攻擊中的視圖是同分布的，這是因為1) 的詢問中的每一個都是用隨機值來回答的。而在對的真實攻擊中，得到的是的函數(shù)值，由于假定是隨機諭言機，所以得到的的函數(shù)值是均勻的。2）對來說，為對做一次密加密。由的隨機性，對來說是隨機的。所以兩種視圖不可區(qū)分。斷言2：在上述模擬攻擊中。證明：顯然有。又由在真實攻擊中的定義，可知的優(yōu)勢大于等于，得在模擬攻擊中的優(yōu)勢也為。=又知：所以即模擬攻擊中

55、。由以上兩個斷言，在上述模擬過程中以至少的概率出現(xiàn)在。若發(fā)生，則在第（2）步可找到滿足，即。所以成功的概率與發(fā)生的概率相同。5.Cramer-Shoup密碼體制也使用哈希函數(shù)，其安全性證明為什么不是隨機諭言機模型？答：首先回顧隨機諭言機的定義。在對方案進行安全性分析時，將其中的哈希函數(shù)視為隨機諭言機。隨機諭言機是一個魔盒 ，對用戶（包括敵手）來說，魔盒內(nèi)部的工作原理及狀態(tài)都是未知的。用戶能夠與這個魔盒交互，方式是向魔盒輸入一個比特串，魔盒輸出比特串（對用戶來說，是均勻分布的）。這一過程稱為用戶向隨機諭言機詢問。由于這種哈希函數(shù)工作原理和內(nèi)部狀態(tài)是未知的，因此不能用通常的公開哈希函數(shù)。在安全性的

56、歸約證明中，敵手需要哈希函數(shù)值時，只能由敵手為他產(chǎn)生。之所以以這種方式使用哈希函數(shù)，是因為要把欲攻擊的困難問題嵌入到哈希函數(shù)值中。這種安全性稱為隨機諭言機模型下的。如果不把哈希函數(shù)當作隨機諭言機，則安全性稱為標準模型下的。 而Gramer-Shoup的證明過程無需把困難問題嵌入到哈希函數(shù)中，所以它是標準模型下的證明過程。 6.（1）在Paillier方案1中，設(shè)，在對加密時，取，計算密文，并驗證解密過程。（2）在Paillier方案2中，設(shè)，計算的密文，并驗證解密過程。答：因為在Paillier方案1中，加密算法為：解密算法為：所以當，時，其密文為：解密過程：解密為：即第10章下面是X.509三向認證的最初版本假定協(xié)議不使用時間戳，可在其中將所有時間戳設(shè)置為0，則攻擊者C如果截獲A、B之前執(zhí)行協(xié)議時的消息，就可假冒A和B，以使A(B)相信通信的對方是B(A).請?zhí)岢鲆环N不使用時間戳的、防中間人欺騙的簡單