現(xiàn)代密碼學(xué)課后習(xí)題及答案

第一章

1)信息安全的目標(biāo)有哪些？給出英文名詞及其解釋。

2)密碼體制安全性有三種分別是什么？

3)密碼學(xué)歷史中你認(rèn)為重要的事件是什么？從這個(gè)歷史演變中你覺(jué)得有何啟示？

4)對(duì)加密體制的攻擊從敵手具有的能力來(lái)看分為哪些？

5)對(duì)加密體制的攻破包括幾種情況？

第二章

1)單表代換和多表代換的差別是什么，請(qǐng)各舉出3例？

2)單表代換的缺點(diǎn)是什么？

3)一次一密為什么是不可破譯的？

4)多表代換分析的重點(diǎn)是什么？

5)Kasiski測(cè)試的主要目的是什么？其原理是什么？

6)Hill加密的抗CPA攻擊的強(qiáng)度是多少，為什么？

第四章

1)A5算法中的鐘控函數(shù)是多少，它是如何控制LSFR的？

2)A5算法中LSFR的特征函數(shù)分別是多少？

3)RC4算法中的KSA和PRGA分別表示什么,作了哪些工作？

4)畫(huà)同步流密碼系統(tǒng)圖和自同步流密碼系統(tǒng)圖？指出其區(qū)別？

5)為什么自同步流密碼可以做到自同步和有限的錯(cuò)誤傳播？舉例說(shuō)明。

6)畫(huà)有限狀態(tài)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移圖：

有限狀態(tài)集s={sl,s2,S3},有限輸入字符集A={A1,A2,A3},有限輸出字符集B={B1,B2},轉(zhuǎn)移

函數(shù)：

fl(sl,A1)=B1,fl(sl,A2)=B2,fl(s2,A3)=Bl,fl(s3,A2)=B2,fl(s2;A2)=B2,f2(sl,Al)=s2;f2(sl,

A2)=s3,f2(s2,A3)=s3,f2(s3,A2)=s2,f2(s2,A2)=sl.

若初始狀態(tài)為Sl,輸入序列為A1,A3,A2,A2,A2,A2,給出輸出序列。

代碼題：

7)查找下載網(wǎng)上A5算法的代碼，進(jìn)行簡(jiǎn)單的解釋。

8)編寫(xiě)RC4算法的代碼，用自己的名字作為密鑰，加密“中國(guó)地質(zhì)大學(xué)(武漢)”。

設(shè)計(jì)題：

設(shè)計(jì)一個(gè)以LSFR為基礎(chǔ)的算法，以自己的名字命名。算法中有2個(gè)LSFR,特征分別是：f(x)=

l+xA4+xA5,f(x)=l+xA3+xA4,鐘控抽頭在寄存器的中間比特，鐘控函數(shù)是g(x,y)=x*y,初始

密鑰是110011100。輸出前30比特，加密自己的名字。

第一章

6）信息安全的目標(biāo)有哪些？給出英文名詞及其解釋。

①機(jī)密性（Confidentiality）。

指保證信息不泄露給非授權(quán)的用戶或者實(shí)體,確保保存的信息和被傳輸?shù)男畔H能被授

權(quán)的各方得到，而非授權(quán)用戶即使得到信息也無(wú)法知曉信息的內(nèi)容

通常通過(guò)訪問(wèn)控制機(jī)制阻止非授權(quán)的訪問(wèn)，通過(guò)加密機(jī)制阻止非授權(quán)用戶或者信息的內(nèi)

容。

②完整性（Integrity）?

指消息未經(jīng)授權(quán)不能進(jìn)行篡改，要保證消息的一致性，即消息在生成、傳輸、存儲(chǔ)和使

用過(guò)程中不應(yīng)發(fā)生人為或者非人為地非授權(quán)篡改（插入、修改、刪除、重排序等）。

一般通過(guò)訪問(wèn)控制阻止篡改行為，同時(shí)通過(guò)消息摘要算法來(lái)檢測(cè)信息是否被篡改。

③認(rèn)證性（Authentication）。

指確保一個(gè)消息的來(lái)源或者消息本身被正確地標(biāo)識(shí)，同時(shí)確保該標(biāo)識(shí)沒(méi)有被偽造，認(rèn)證

分為消息鑒別和實(shí)體認(rèn)證。

消息鑒別是指接收方保證消息確實(shí)來(lái)自于所聲稱的源；實(shí)體認(rèn)證指能確保被認(rèn)證實(shí)體是

所聲稱的實(shí)體，第三方不能假冒這兩個(gè)合法方中的任何一方。

④不可否認(rèn)性（Non-Repudiation）?

指能保證用戶無(wú)法事后否認(rèn)曾經(jīng)對(duì)信息進(jìn)行的生成、簽發(fā)、接收等行為。

當(dāng)發(fā)送一個(gè)消息時(shí)，接收方能證實(shí)該消息確實(shí)是由既定的發(fā)送方發(fā)來(lái)的，稱為源不可否

認(rèn)性；

⑤可用性（Availability）（,

指保障信息資源隨時(shí)可提供服務(wù)的能力。即授權(quán)用戶根據(jù)需要可以隨時(shí)訪問(wèn)所需信息，

保證合法用戶對(duì)信息資源的使用不被非法拒絕。

典型的對(duì)可用性的攻擊是拒絕服務(wù)攻擊。

除了以上一些主要目標(biāo)外，還有隱私性（Privacy）,匿名性（Anonymity）等。

7）密碼體制安全性有三種分別是什么？

計(jì)算安全、可證明安全、無(wú)條件安全

8）密碼學(xué)歷史中你認(rèn)為重要的事件是什么？從這個(gè)歷史演變中你覺(jué)得有何啟示？

略

9）對(duì)加密體制的攻擊從敵手具有的能力來(lái)看分為哪些？

①唯密文攻擊（COA）o敵手（或密碼分析者）只能通過(guò)考察密文，試圖推到解密密鑰

或明文。

②已知明文攻擊（KPA）。敵手擁有一定量的明文和相應(yīng)的密文。

③選擇明文攻擊（CPA1）,敵手可以選擇明文，接著得到相應(yīng)的密文。之后，敵手使

用所擁有的信息，恢復(fù)以前未見(jiàn)過(guò)的密文的相應(yīng)明文。

④臼適應(yīng)選擇明文攻擊（CPA2）。一種選擇明文攻擊，其中明文的選擇可依賴于以前

產(chǎn)生的密文。

⑤選擇密文攻擊（CCA1）。敵手可以選擇密文，接著得到相應(yīng)的明文。這種攻擊的一

種方法是敵手設(shè)法獲取解密設(shè)備的訪問(wèn)權(quán)（但不是解密密鑰，它可能被安全地嵌入到設(shè)備

中）。然后，在不訪問(wèn)該設(shè)備的情況下，推導(dǎo)出（先前未詢問(wèn)過(guò)解密設(shè)備的）密文的明文。

⑥自適應(yīng)選擇密文攻擊（CCA2）。?種選擇密文攻擊，其中密文的選擇可依賴于以前

輸入所產(chǎn)生的明文。

10）對(duì)加密體制的攻破包括幾種情況？

對(duì)加密體制，攻擊的最終目標(biāo)是得到明文，但如果能得到密鑰，則必然可以得到明文。

加密體制的安全性從低到高主要有以下3類(lèi)：

①完全攻破：攻擊者能得到使用的密鑰（對(duì)公鑰系統(tǒng)而言指私鑰）。

②部分攻破：攻擊者可能不需要知道密鑰，而對(duì)某些密文能直接得到明文。

③密文區(qū)分：攻擊者能以超過(guò)V2的概率解決以下兩種不同形式描述的問(wèn)題：一是給

攻擊者任意兩個(gè)明文和其中任意明文的密文，攻擊者判斷是哪個(gè)明文的密文；二是給攻擊者

任意一個(gè)明文和該明文的密文，以及一個(gè)和密文等長(zhǎng)的隨機(jī)字符串，讓攻擊者判斷哪個(gè)是密

文。

目前，加密體制的最好安全標(biāo)準(zhǔn)時(shí)適應(yīng)性選擇密文攻擊條件下密文不可區(qū)分，記為

IND-CCA2o

第二章

7）單表代換和多表代換的差別是什么，請(qǐng)各舉出3例？

在單表代換下，字母的頻率、重復(fù)字母的模式和字母組合方式等統(tǒng)計(jì)特性（除了字母名

稱改變以外）均未改變；多表代換密利用從明文字母到密文字母的多個(gè)映射，隱臧單字母的

統(tǒng)計(jì)特征（如頻率特征）。單表代換中密文和明文間有著固定的代換關(guān)系；多表代換將明文

字母劃分為長(zhǎng)度相同的明文分組，然后對(duì)明文分組進(jìn)行代換。這樣，同?個(gè)字母只要在不同

明文分組中的不同位置就會(huì)映射到不同的密文字母（因?yàn)榇鷵Q表不同），從而更好地抵抗密

碼分析。

單表代換：移位密碼、仿射密碼、凱撒密碼

多表代換：playfair密碼、Vigenere密碼、Vernam密碼、Hill密碼

8）單表代換的缺點(diǎn)是什么？

由于密文和明文間有著固定的代換關(guān)系，簡(jiǎn)單地說(shuō)，明文字符出現(xiàn)的頻率沒(méi)有掩蓋，即

明文中常出現(xiàn)的字符在密文中也常出現(xiàn)，這于是被密碼分析所利用，達(dá)到破解的目的。在單

表代換下，字母的頻率、重復(fù)字母的模式和字母組合方式等統(tǒng)計(jì)特性（除了字母名稱改變以

外）均未改變。

9）一次一密為什么是不可破譯的？

①密鑰是真正的隨機(jī)序列；

②密鑰至少和明文一樣長(zhǎng)；

③一個(gè)密鑰只使用一次。

如果這樣，密碼就是不可破譯的，這便是著名的“一次一密"（onetimepad）。然而“一

次一密”在實(shí)際上是行不通的，需要經(jīng)常產(chǎn)生、存儲(chǔ)、安全傳遞大量的很長(zhǎng)的密鑰，這在實(shí)

際中是及其困難的。

10）多表代換分析的重點(diǎn)是什么？

確定密鑰的長(zhǎng)度

11）Kasiski測(cè)試的主要目的是什么？其原理是什么？

確定密鑰長(zhǎng)度

基本原理是：明文中如果兩個(gè)相同的明文片段之間的距離是密鑰長(zhǎng)度的倍數(shù)的話，那么

在密文中，這兩個(gè)明文片段所對(duì)應(yīng)的密文片段一定是相同的（其原因容易思考得到，因

為加密片段的密鑰相同）。反過(guò)來(lái)，如果密文中出現(xiàn)兩個(gè)相同的字母片段，它們所對(duì)應(yīng)

的明文字母片段未必相同，但相同的可能性很大。于是，可以通過(guò)觀察密文中重復(fù)出現(xiàn)

的密文字母片段來(lái)估計(jì)密鑰長(zhǎng)度，即找出相同密文片段的間隔數(shù)，求最大公因子，可能

是密鑰的長(zhǎng)度。

12）Hill加密的抗CPA攻擊的強(qiáng)度是多少，為什么？

Hill加密易受到已知明文攻擊（CPA）。

原因：Hill中某個(gè)明文字母對(duì)應(yīng)的密文字母既與加密矩陣相關(guān)，也與該分組其他字母相

關(guān)

第四章

9）A5算法中的鐘控函數(shù)是多少，它是如何控制LSFR的？

鐘控函數(shù)：g（2,期，=xy+xz+yz

其中x,y,z分別為L(zhǎng)FSR"LFSR〃LFSR3的第9/11/11個(gè)寄存器的值。當(dāng)x和g（s,y,z）

的值相等時(shí)，LFSR1移位，否則重復(fù)輸出前一位。LFSR2和LFSR3的移位過(guò)程與LFSR1類(lèi)似。

10）A5算法中LSFR的特征函數(shù)分別是多少？

①LFSR1的抽頭是13/1^17/lS,特征多項(xiàng)式為：/=1+/4++.T10

②LFSR2的抽頭為1^1^20/21,特征多項(xiàng)式為：/（工：）=1++工”+^21+^22

③LFSR3的抽頭為1力即皿2,特征多項(xiàng)式為：/（工）=1+/18+，9+工22+工23

11）RC4算法中的KSA和PRGA分別表示什么，作了哪些工作？

KSA：初始化S

首先為S賦初始值，并建立256字節(jié)的臨時(shí)矢量T,再循環(huán)重復(fù)用Keylen字節(jié)密鑰K

對(duì)T賦值，直到T所有元素被賦值；然后用T對(duì)S進(jìn)行初始置換，對(duì)每個(gè)S[i],有丁國(guó)將

其置換為S中的另一個(gè)字節(jié)。

PRGA：隨機(jī)序列生成（密鑰流生成）

初始化完成后，丟棄密鑰K,用S⑼到S[255]產(chǎn)生密鑰序列：

根據(jù)當(dāng)前S的值，將S[口與S中的另一字節(jié)S[j]置換，置換完成后，由S[i]和S[j]的值產(chǎn)

生1字節(jié)密鑰K。

當(dāng)全部256字節(jié)完成置換后，從S[0]重復(fù)開(kāi)始，直到產(chǎn)生實(shí)際需要長(zhǎng)度的密鑰為止。

12）畫(huà)同步流密碼系統(tǒng)圖和自同步流密碼系統(tǒng)圖？指出其區(qū)別？

同步流密碼系統(tǒng)圖如下：

特點(diǎn)：

①同步要求：在同步密碼中，消息的發(fā)送者和接收者必須同步才能做到正確的加密和

解密，即雙方使用相同的密鑰，并用其對(duì)同一狀體進(jìn)行操作。一旦由于密文字符在傳遞過(guò)程

中被插入或刪除而破壞了這種同步性，那么解密工作將失敗。這時(shí)只有借助其他方式重建同

步，解密才能繼續(xù)進(jìn)行。重置同步的技術(shù)包括：重新初始化，在密文的規(guī)則間隔中設(shè)置特殊

符號(hào)，或如果明文包含足夠的冗余度，那么就可以嘗試密鑰流的所有可能偏移。

②無(wú)錯(cuò)誤傳播：密文字符在傳輸過(guò)程中被修改（但未必刪除）并不影響其他的密文字

符解密。

③主動(dòng)攻擊（的方法）：作為性質(zhì)1）的結(jié)果，一個(gè)主動(dòng)攻擊者對(duì)密文字符進(jìn)行的插入、

刪除或從重復(fù)都會(huì)立即破壞系統(tǒng)的同步性，從而可能被解密器檢測(cè)出來(lái)。作為性質(zhì)2）的結(jié)

果，主動(dòng)攻擊者可能有選擇地對(duì)密文字符進(jìn)行改動(dòng)，并準(zhǔn)確地知道這些改動(dòng)對(duì)明文的影響。

因此，必須采用附加技術(shù)為數(shù)據(jù)提供數(shù)據(jù)源認(rèn)證，并保證數(shù)據(jù)的完整性。

自同步流密碼系統(tǒng)圖如下:

特點(diǎn)：

①自同步：由于對(duì)當(dāng)前密文字的解密僅僅依賴于固定個(gè)數(shù)的以前的密文字，因此，當(dāng)

密文字被插入或者刪除時(shí)，密碼的自同步性就會(huì)體現(xiàn)出來(lái)。這種密碼在同步性遭到破壞時(shí)，

可以自動(dòng)地重建正確的解密，而且僅有固定數(shù)量的明文字不可恢復(fù)。

②有限的錯(cuò)誤傳播：假設(shè)一個(gè)自同步流密碼系統(tǒng)的狀態(tài)依賴于t個(gè)以前的密文字。在

傳輸過(guò)程中，當(dāng)一個(gè)單獨(dú)的密文字被改動(dòng)（或被插入、刪除）時(shí)，至多會(huì)有t個(gè)隨后的密文

字解密出錯(cuò)，然后再恢復(fù)正確解密。

③主動(dòng)攻擊（的方法）：從性質(zhì)2）看出，主動(dòng)攻擊對(duì)密文字的任何改動(dòng)都會(huì)引發(fā)一些

密文字的解密出錯(cuò)。因此，與同步流密碼相比，自同步流密碼具有更高的被（解密器）檢測(cè)

出來(lái)的可能性。作為性質(zhì)1）的結(jié)果，這種密碼在檢測(cè)主動(dòng)攻擊者發(fā)起的對(duì)“密文字”的插

入、刪除、重復(fù)等攻擊時(shí)，就更加困難，必須采用一些附加的技術(shù)來(lái)提供消息源鑒別和消息

完整性。

④明文統(tǒng)計(jì)擴(kuò)散：每個(gè)明文字都會(huì)影響其后的整個(gè)密文，即明文的統(tǒng)計(jì)學(xué)特征被擴(kuò)散

到了密文中。因此，自同步流密碼在抵抗利用明文冗余度而發(fā)起地攻擊方面要強(qiáng)于同步流密

碼。

13）為什么自同步流密碼可以做到自同步和有限的錯(cuò)誤傳播？舉例說(shuō)明。

14）畫(huà)有限狀態(tài)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移圖：

有限狀態(tài)集s={sl,s2,S3},有限輸入字符集A={A1,A2,A3},有限輸出字符集B={B1,B2},轉(zhuǎn)移

函數(shù)：fl(sl,A1)=B1,fl(sl,A2)=B2,fl(s2,A3)=Bl,fl(s3,A2)=B2,fl(s2,A2)=B2,f2(sl,Al)=s2,f2(sl,

A2)=s3,f2(s2,A3)=s3,f2(s3,A2)=s2,f2(s2,A2)=sl.

若初始狀態(tài)為si,輸入序列為A1,A3,A2,A2,A2,A2,給出輸出序列。

代碼題：

15）查找下載網(wǎng)上A5算法的代碼，進(jìn)行簡(jiǎn)單的解釋。

網(wǎng)上可下載，以張文彬同學(xué)的為例：

擲——'?小

If叫

>ot?n>?Win?nU>?V：>(

A.8ASrf?i*t?l>1—

???MI>

?r?ctI

S3,ISC;

tUtlC1?ttkrnMUtrl.rj,r)i

“Ml?ntHi

OMItnHlotr))

Mcth

rl|

FE(rl)|

Mts出口aMg

科jMCEtlc.8“.1??》;

cw??，(】-ti,1.).?3.tj.ai：

forC1-0;l?I00;***>d?U(l)-?i

($_ke/(k.*v>;

45,e?WtU.e?w.l)s

R?177：:**)a4flM?0；

?eti?tf<,o?crypt?w?eHHXn,)i

16）編寫(xiě)RC4算法的代碼，用自己的名字作為密鑰，加密“中國(guó)地質(zhì)大學(xué)（武漢）”。

設(shè)計(jì)題：

設(shè)計(jì)一個(gè)以LSFR為基礎(chǔ)的算法，以自己的名字命名。算法中有2個(gè)LSFR,特征分別是：f（x）=

l+xA4+xA5,f（x）=l+x"3+xM,鐘控抽頭在寄存器的中間比特，鐘控函數(shù)是g（x,y）=x*y,初始

密鑰是110011100。輸出前30比特，加密自己的名字。

第4章（續(xù)）

1、3級(jí)LFSR的特征多項(xiàng)式為f（x）=l+x+x3,初始態(tài)為（0,0,1）。求輸出序列及其周期。

第5章分組密碼

1）分組密碼中的重要組成部分是P盒和S盒，分別有何作用？

2）分組密碼為何要采用迭代結(jié)構(gòu)？

3）分組長(zhǎng)度和密鑰長(zhǎng)度分別為4,則加密的置換占全部置換的比例是多少？

4）畫(huà)DES加密中的Feistel結(jié)構(gòu)圖，并在其上用紅筆改寫(xiě)為解密圖，指出為什么這個(gè)結(jié)構(gòu)是

天然可逆的。

5）DES加密中的設(shè)計(jì)重點(diǎn)是什么函數(shù)？

6）簡(jiǎn)單描述DES中S盒的計(jì)算方法，舉例說(shuō)明。

7）AES的S盒設(shè)計(jì)為什么是公開(kāi)的不會(huì)有暗藏后門(mén)？

8）AES的主要結(jié)構(gòu)是哪4個(gè)步驟？

9）說(shuō)明AES和DES設(shè)計(jì)的不同之處？

10）分組密碼的4種工作模式是什么，有何特點(diǎn)？

11）分組模式中可以并行的有哪些，不能并行的有哪些，有反饋的有哪些，可以自同步的有

哪些，有錯(cuò)誤傳遞的有哪些？

12）畫(huà)ECB和CBC的解密圖，給出CBC加密和解密的數(shù)學(xué)表達(dá)式？

13）如果有n個(gè)分組，單個(gè)分組加密的時(shí)間為m秒，則ECB整個(gè)加密時(shí)間為多少？CBC整

個(gè)加密時(shí)間為多少？說(shuō)明CBC的加密和解密過(guò)程中為什么不能并行？

14）畫(huà)CFB和OFB的解密圖，說(shuō)明這兩種模式中為什么不需要分組密碼的解密電路D?這

種方法為什么可以利用分組密碼提供序列密碼的功能？指出這兩種工作模式中加密的明文

和密文的長(zhǎng)度實(shí)際為多少？移位寄存器的作用是什么？

15)利用CFB或者OFB設(shè)計(jì)一種算法來(lái)替代GSM中的A5算法和Windows中的RC4算法。

16)解釋如果CFB中加密序列的長(zhǎng)度為s,移位寄存器的長(zhǎng)度為L(zhǎng),則1個(gè)在傳遞中被修改

的密文分組會(huì)導(dǎo)致接收方解密時(shí)L/s+1個(gè)明文分組與原來(lái)發(fā)送方加密的明文分組有不同。

代碼題：

17)查找下載網(wǎng)上OPENSSL/CRYPTO++/CODEGURU/SOURCEFORGE中AES算法的代碼，進(jìn)行

簡(jiǎn)單的解釋。

實(shí)驗(yàn)題(選作)：

1)編寫(xiě)AES算法的Java/C/Python/C#代碼。

2)編寫(xiě)SM4算法的Java/C/Python/C#代碼。

設(shè)計(jì)題：

設(shè)計(jì)一個(gè)4輪Feistel結(jié)構(gòu)的分組加密，分組的長(zhǎng)度為8比特。半個(gè)分組為4個(gè)，即L和R

長(zhǎng)度各為4比特。

輪函數(shù)f=P(S(E(R)+Ki)),i=l,2,3,4,這里+表示異或。

假設(shè)R=①②③④，后低1②①②③④③；

S盒取DES的S盒，或者自己設(shè)計(jì)一個(gè)S盒，做一個(gè)表格即可，輸入為6比特，輸出為4比

特，S(①②③④⑤⑥)=①②③④；P(①②③④)=②④①③。

輪密鑰編排從略，假定KUllllll,K2=111000,K3=000111,K4=000000

明文是自己的姓名。給出程序。給出密文。

第6章Hash函數(shù)

1)SHA-1算法的設(shè)計(jì)特點(diǎn)是什么？

2)SHA-1算法的壓縮函數(shù)輸入和輸出分別是多少？

3)利用分組密碼的CBC模式如何構(gòu)造Hash函數(shù)？

4)Hash函數(shù)的一般模型是什么？

5)HASH函數(shù)安全性的3個(gè)要求是什么？為什么不抗弱碰撞就不抗強(qiáng)碰撞？

6)生日攻擊是什么意思？如果一個(gè)Hash函數(shù)輸出為64比特，則嘗試多少次會(huì)以50%概率

產(chǎn)生碰撞。

7)你覺(jué)得這個(gè)hash函數(shù)是否可行：將任意長(zhǎng)度進(jìn)行分組，每組64比特，長(zhǎng)度不是64整數(shù)

倍，采用SHA-1一樣的填充方式。然后采用ECB模式加密分組，分組的結(jié)果進(jìn)行XOR,產(chǎn)生

的結(jié)果作為hash值。(提示：是否滿足單向性，弱碰撞性，強(qiáng)碰撞性)

8)帶密鑰的Hash函數(shù)為什么可以用來(lái)做消息鑒別和身份識(shí)別？

9)CBC-MAC的工作原理是什么？

10)HMAC的基本構(gòu)造是什么？

代碼題：

1)查找下載網(wǎng)上SHA-1算法的代碼，進(jìn)行簡(jiǎn)單的解釋?zhuān)伎甲约耗芊駥?xiě)出這樣的代碼。

2)(選作)查找代碼眾籌平臺(tái)，開(kāi)源代碼平臺(tái)等，例如：GitHub、CodeGuru等中相關(guān)項(xiàng)目，

看是否有自己感興趣的Hash函數(shù)、區(qū)塊鏈、比特幣等相關(guān)項(xiàng)目。

3)(選作)查找下載網(wǎng)上FPGA實(shí)現(xiàn)SHA-1的代碼，簡(jiǎn)單解釋其功能。

4）（選作）利用Ruby語(yǔ)言、Python語(yǔ)言、Java>Javascript,MatlabScript,匯編語(yǔ)言實(shí)現(xiàn)SHA-1。

設(shè)計(jì)題：

1）現(xiàn)在有DES加密模塊E,移位寄存器模塊LFSR,設(shè)計(jì)一個(gè)序列密碼裝置，加密長(zhǎng)度為

S=1byte的字節(jié)流。

設(shè)計(jì)一個(gè)Hash函數(shù)裝置，產(chǎn)生64比特散列值。畫(huà)結(jié)構(gòu)圖（輸入，輸出，內(nèi)部結(jié)構(gòu)）。

2）（選作）利用第五章的設(shè)計(jì)題設(shè)計(jì)的分組密碼的CBC模式構(gòu)造一個(gè)Hash函數(shù)，看是否滿

足抗弱碰撞性。

3）（選作）模仿SHA-1設(shè)計(jì)一個(gè)hash函數(shù)，迭代10輪，每輪壓縮函數(shù)為{0,1}64+16->

{0,1}第（即吸掉64比特），用代碼實(shí)現(xiàn)，并分析其安全性。

研究題：

1）（選作）描述SHA-2方案，與SHA-1進(jìn)行比較，思考其安全性是否提高了？

2）查找文獻(xiàn)和網(wǎng)絡(luò)資源，回答W1FI或者3G加密標(biāo)準(zhǔn)中是否用到分組密碼的CBC模式、CTR

模式？

第5章（續(xù)）

1、3級(jí)LFSR的特征多項(xiàng)式為f（x）=l+x+x3,初始態(tài)為（0,0,1）?求輸出序列及其周期。

輸出序列：0011101

周期：7

第5章分組密碼

17）分組密碼中的重要組成部分是P盒和S盒，分別有何作用？

P盒：擴(kuò)散

S盒：混淆

18）分組密碼為何要采用迭代結(jié)構(gòu)？

實(shí)現(xiàn)擴(kuò)散和混淆

19）分組長(zhǎng)度和密鑰長(zhǎng)度分別為4,則加密的置換占全部置換的比例是多少？

272"

20）畫(huà)DES加密中的Feistel結(jié)構(gòu)圖，并在其上用紅筆改寫(xiě)為解密圖，指出為什么這個(gè)結(jié)構(gòu)

是天然可逆的。

Ri—i-L"

J=凡十/(JK)

可逆原因:

21)DES加密中的設(shè)計(jì)重點(diǎn)是什么函數(shù)？

輪函數(shù)F是DES設(shè)計(jì)的核心

22)簡(jiǎn)單描述DES中S盒的計(jì)算方法，舉例說(shuō)明。

S盒代換(S-boxSubstitution)。將異或后的48bits依次分成8組，每組6bits,分別送入8個(gè)

S盒中進(jìn)行代換。每個(gè)S盒由一個(gè)4行16列的表確定。表5.3給出一個(gè)S盒的例子。圖5.11

給出了示意圖。

表5.4S盒(Si|)

OPIP223。4P5P6P7P8。9。10^1*12。13r14一15-

IS4^13"2。15ca3210^加12《5。9。0P7。

1POP15,7P*132。13-1236P12^IP925P3。8。

2。4^1。14,8Q13。和2P11215,12,9。7*3。10^

3-15,12,8Q2/4^9。12725~1*3。1310^OP加134

011101

0001

圖5.11盒計(jì)算方法舉例

每個(gè)S盒的輸入是6位，不妨設(shè)為bib263b465b6。S盒的輸出為4位,

通過(guò)查找「行C列的數(shù)據(jù)得到。這里仇為為您］二進(jìn)制表示，

即r=26i+%，b2b3b4b5為C的二進(jìn)制表示。例如：8(011001)產(chǎn)生

r=l,c=12輸出為9。即二進(jìn)制數(shù)1001。

23)AES的S盒設(shè)計(jì)為什么是公開(kāi)的不會(huì)有暗臧后門(mén)？

有嚴(yán)格的數(shù)學(xué)計(jì)算

24)AES的主要結(jié)構(gòu)是哪4個(gè)步驟？

字節(jié)代換(ByteSub)、行移位變換(ShiftRow)、列混合變換(MixColumn)、輪密鑰加變換

(AddRoundKey)

25)說(shuō)明AES和DES設(shè)計(jì)的不同之處？

7.AES和DES的比較

相似之處在于，兩者的輪函數(shù)都由3層構(gòu)成，即非線性層、線性混合層、子密鑰異或，

只是順序不同。AES的輪密鑰異或?qū)?yīng)于DES中S盒之前的輪密鑰異或。AES的列混合運(yùn)

算的目的是讓不同的字節(jié)相互影響，而DES中F函數(shù)的輸出與左邊一半數(shù)據(jù)相加有類(lèi)似的

效果。AES中的非線性運(yùn)算字節(jié)代換，對(duì)應(yīng)于DES中的唯一非線性變換S盒。AES中行移

位保證了每一行的字節(jié)不僅僅影響其他行對(duì)應(yīng)的字節(jié)，而且影響其他行所有的字節(jié)，這與

DES中的置換P類(lèi)似。

不同之處在于：AES的密鑰長(zhǎng)度（128位、192位、256位）是可變的，而DES的密鑰

長(zhǎng)度固定為56位。DES是面向比特的運(yùn)算，AES是面向字節(jié)的運(yùn)算。AES的加密運(yùn)算和解

密運(yùn)算不一致，因而加密電路（或程序）不能同時(shí)用作解密電路（或程序），DES的加密和

解密的電路（或程序）則是一樣的。

26）分組密碼的4種工作模式是什么，有何特點(diǎn)？

①ECB：簡(jiǎn)單高效，可以實(shí)現(xiàn)并行操作。ECB有良好的差錯(cuò)控制，一個(gè)密文塊（或明文

塊）的改變，在解密（或加密）時(shí)，只會(huì)引起相應(yīng)的明文塊（或密文塊）的改變，不會(huì)

影響其他明文塊（或密文塊）的改變。J.

ECB的最大特性是明文中相同的分組，在密文也是相同的。這也是其缺點(diǎn)，因?yàn)檫@樣在

加密長(zhǎng)消息時(shí)，敵手可能得到多個(gè)明文密文對(duì)，進(jìn)行已知明文攻擊。

因此，ECB特別適合加密的數(shù)據(jù)隨機(jī)且較短的情形，如加密一個(gè)會(huì)話密鑰。

②CBC：引入了反饋機(jī)制。CBC不能自動(dòng)恢復(fù)同步錯(cuò)誤。如果密文中偶爾丟失或添加?

些數(shù)據(jù)位，那么整個(gè)密文序列將不能正確的解密，除非有幀結(jié)構(gòu)能夠重新劃分和排列分

組的邊界。

CBC對(duì)于加密長(zhǎng)于64bits的消息非常合適。另外，CBC除了能獲得保密性外，還能用于

認(rèn)證

③CFB:可以將分組密碼轉(zhuǎn)變?yōu)樾蛄忻艽a，變成面向字符的流密碼工作模式，與CBC

一樣，引入反饋機(jī)制，CFB的密文塊是前面所有明文塊的函數(shù)。

④OFB：內(nèi)部反饋，失去同步（即移位寄存器沒(méi)有保持一致），將是致命的；如果密文

某個(gè)位反轉(zhuǎn)，則相應(yīng)的明文那一位也反轉(zhuǎn)。這一缺點(diǎn)有可能被攻擊者利用

優(yōu)點(diǎn)：簡(jiǎn)單高效，可并行，無(wú)錯(cuò)誤擴(kuò)

(ECBCi=E*(pJ散，適于加密短密鑰（密鑰傳遞）：

Pi=Dk.(ci),l<i<ii缺點(diǎn)：相同明文分組的密文相同

引入反饋機(jī)制

優(yōu)點(diǎn)：密文錯(cuò)誤擴(kuò)散?。ㄓ绊懞?個(gè)分

；組），還可用于認(rèn)證；

ICBCc=Ek(pi

Pi=Dk(ci)?c,_i,1<i<n,cn=IV缺點(diǎn)：同ECB一樣，

不能自動(dòng)恢復(fù)同步錯(cuò)誤，不可并行；

將分組密

碼變成流

密碼

有反

饋

ki=E*(rgs￡i)優(yōu)點(diǎn)：自同步，密文錯(cuò)誤擴(kuò)散（影響，

不

,CFBc,=m十ki[s](rgsti)=IVA<i<nd/s個(gè)分組），還可用于認(rèn)證：能

并

行

rqsti={rqstji缺點(diǎn)：不可并行；

ki=EMrgstji)僅需

優(yōu)點(diǎn)：無(wú)密文錯(cuò)誤擴(kuò)散；分組

OFBCi=piki[s\(rgsto=IV.!</<//缺點(diǎn)：不可并行，不能失去同步；密碼

rgsti={r(]sti-x((Gllfchl)的加

密操

A-,=E(CTR.)彳乍

k優(yōu)點(diǎn)：可并行，可預(yù)處理，無(wú)密文錯(cuò)誤7

d=p；?,1</<n擴(kuò)散；

缺點(diǎn)：保證CTR狀態(tài)，不能失去同步：

27）分組模式中可以并行的有哪些，有反饋的有哪些，可以自同步的有哪些，有錯(cuò)誤傳遞的

有哪些？

并行：ECB

反饋：CBC,EFB,OFB

自同步：CFB

有錯(cuò)誤傳遞：CBC,CFB

代碼題：

18）查找下載網(wǎng)上OPENSSL/CRYPTO++/CODEGURU/CODEFORGE中AES算法的代碼，進(jìn)行簡(jiǎn)

單的解釋。

實(shí)驗(yàn)題（選作）：

3）編寫(xiě)AES算法的Java/C/Python/C#代碼。

4）編寫(xiě)SM4算法的Java/C/Python/C#代碼。

設(shè)計(jì)題：

設(shè)計(jì)一個(gè)4輪Feistel結(jié)構(gòu)的分組加密，分組的長(zhǎng)度為8比特。半個(gè)分組為4個(gè)，即L和R

長(zhǎng)度各為4比特。

輪函數(shù)f=P（S（E（R）+Ki））,i=l,2,3,4,這里+表示異或。

假設(shè)R=①②③④，后⑻二②①②③④③；

S盒取DES的S盒，或者自己設(shè)計(jì)一個(gè)S盒，做一個(gè)表格即可，輸入為6比特，輸出為4比

特，S（①②③④⑤⑥）=①②③④；P（①②③④）=②④①③。

輪密鑰編排從略，假定Kimill,K2=111000,K3=000111,K4=000000

明文是自己的姓名。給出程序。給出密文。

第6章Hash函數(shù)

11)SHA-1算法的設(shè)計(jì)特點(diǎn)是什么？

具有壓縮特性的單向函數(shù)

12)SHA-1算法的壓縮函數(shù)輸入和輸出分別是多少？

SHA-1算法的輸入消息的最大長(zhǎng)度小于bit,輸入消息以512bit的分組為單位進(jìn)行處

理，輸出是160bit的消息摘要。

13)利用分組密碼的CBC模式如何構(gòu)造Hash函數(shù)？

1.基于分組密碼CBC工作模式構(gòu)造Hash函數(shù)

構(gòu)造過(guò)程如圖6.4所示。首先選取一個(gè)初始值加=IV€GF(2)n,

然后依次計(jì)算

Ui=Ek(xi十y￡-i),(l<i<L)

最后定義散列值為：HCBC⑺=VL，即最后一個(gè)密文分組。

圖6.4基于分組密碼CBC工作模式構(gòu)造Hash函數(shù)

14)Hash函數(shù)的一般模型是什么?

預(yù)處理，迭代處理和輸出變換

原始輸入X

輸M0=g(Hr)

15)HASH函數(shù)安全性的3個(gè)要求是什么？為什么不抗弱碰撞就不抗強(qiáng)碰撞？

6.1.5Hash函數(shù)的安全性(生日攻擊)

敵手攻擊Hash函數(shù)的目標(biāo)是：

1.攻擊單向性(攻擊抗原像)：給定Hash函

數(shù)的散列值y,找到一個(gè)原像x,使得y=h(x)。

2.攻擊抗弱碰撞性(攻擊抗第二原像)：給

定一對(duì)(Xjl(x)),找到第二原像X，，使得

,

h(x)=h(x)o

3.攻擊抗強(qiáng)碰撞性：找到任意兩個(gè)輸入XX，

使得h(x)=h(x>

16)生日攻擊是什么意思？如果一個(gè)Hash函數(shù)輸出為64比特，則嘗試多少次會(huì)以50%概率

產(chǎn)生碰撞。

生日迷題是指：假定每個(gè)人的生日是等概率

的，不考慮閏年的情況，在k個(gè)人中至少有兩個(gè)人

的生日相同的概率大于1/2,問(wèn)k的最小值是多少？

計(jì)算結(jié)果與人的直覺(jué)相差很大，因此有地方

稱為生日迷題或生日悖論(BirthdayParadox)。

把每個(gè)人的生日看成［1,365］中的隨機(jī)變量，則個(gè)

人生日重復(fù)的概率為：

p=1-(1-1/365)(1-2/365)(1-(k-1)/365)

由于=1-r+//2!+X3/3!+,當(dāng)x較小時(shí)

有這里x=1/365較小)，不妨用N表示

365,因此，有

l-pyntje-k/N=e-kf/2N

即

出—ky—2Nln(l—p)

當(dāng)N比k大很多時(shí)，忽略一次項(xiàng)k,得

k?，(-2Nln,(l—())

代入N=365,p=0.5,得卜122.49,故每23個(gè)人

中會(huì)同生日的概率超過(guò)50%。

生日攻擊就是指隨機(jī)選取消息，使其發(fā)生碰撞。

例如對(duì)于輸出長(zhǎng)度為128b4的Hash函數(shù)，攻擊者

的計(jì)算量達(dá)到264個(gè)消息時(shí)，便有高于05的概率

發(fā)現(xiàn)一對(duì)碰撞。因此，輸出長(zhǎng)度為N的Hash函數(shù)，

其碰撞蠻力搜索的計(jì)算量為2/2

代碼題：

1)查找下載網(wǎng)上SHA-1算法的代碼，進(jìn)行簡(jiǎn)單的解釋?zhuān)伎甲约耗芊駥?xiě)出這樣的代碼。

2)(選作)查找代碼眾籌平臺(tái)，開(kāi)源代碼平臺(tái)等，例如：GitHub、CodeGuru等中相關(guān)項(xiàng)目,

看是否有自己感興趣的Hash函數(shù)、區(qū)塊鏈、比特幣等相關(guān)項(xiàng)目。

3)(選作)查找下載網(wǎng)上FPGA實(shí)現(xiàn)SHA-1的代碼，簡(jiǎn)單解釋其功能。

4)(選作)利用Ruby語(yǔ)言、Python語(yǔ)言開(kāi)發(fā)SHA-1。

設(shè)計(jì)題:

1）利用上一章的設(shè)計(jì)題設(shè)計(jì)的分組密碼的CBC模式構(gòu)造一個(gè)Hash函數(shù)，看是否滿足抗弱

碰撞性。

2）（選作）模仿SHA-1設(shè)計(jì)一個(gè)hash函數(shù)，用代碼實(shí)現(xiàn)，并分析其安全性。

研究題（選作）：

1）描述SHA-2方案，與SHA-1進(jìn)行比較，思考其安全性是否提高了？

2）查找文獻(xiàn)，回答WIFI或者3G加密標(biāo)準(zhǔn)中是否用到分組密碼的CBC模式、CTR模式？

第7章公鑰加密（基礎(chǔ)）

28）公鑰加密的提出是為了解決對(duì)稱加密方法的什么缺陷？

29）畫(huà)公鑰加密的加密模型和認(rèn)證模型？

30）Merkle提出在非安全信道上安全通信，他的方案是如何做到的？他的方案為何可以對(duì)

抗竊聽(tīng)者或者確保通信的保密性？

31）背包加密中普通背包和簡(jiǎn)單背包的區(qū)別是什么？為什么針對(duì)簡(jiǎn)單背包，給出S和集合A,

可以很快得到選擇的是集合中的哪些元素。

32）描述背包加密方案。

假設(shè)A的私鑰是A=（1,3,5,10,20,41,83,170）,W=7,M=351,寫(xiě)出A的公鑰。

假設(shè)B要加密的明文為10010110,計(jì)算密文。

為什么敵人看到密文不能求出明文？

A收到密文后，如何對(duì)密文進(jìn)行解密，解密結(jié)果是否等于明文。

實(shí)驗(yàn)題（實(shí)習(xí)課再完成）：

5）編寫(xiě)背包加密算法的Java/C/Python/C#代碼。

探索題（選作，思考）：

子集求和問(wèn)題是困難的嗎？

給你一個(gè)困難問(wèn)題，你可以設(shè)計(jì)一個(gè)加密方案嗎？

第8章公鑰加密（高級(jí)）

1）寫(xiě)Diffie-Hellman密鑰交換協(xié)議圖？

2）寫(xiě)EIGamal加密方案，畫(huà)圖指出其與Diffie-Hellman協(xié)議的對(duì)應(yīng)關(guān)系。

3）描述EIGamal版本橢圓曲線加密方案，并畫(huà)圖指出與日Gamal密碼方案的對(duì)應(yīng)關(guān)系。

實(shí)驗(yàn)題（實(shí)習(xí)課再完成）：

1）編寫(xiě)橢圓曲線加密算法的Java/C/Python/C#代碼。

2）編寫(xiě)EIGamal力口密和解密的Java/C/Python/C#/Ruby/Matlab/…代碼。

設(shè)計(jì)題：

1）畫(huà)出橢圓曲線EH（1,1）離散點(diǎn)圖形。

2）取P=（l,5）,Q=（3,3）,計(jì)算P+Q。圖上標(biāo)記。

提示：X=（y2-y1）/（x2-x1）,x3=X2-xl-x2,y3=X（xl-x3）-yl

3）計(jì)算2P,3P,4P,圖上標(biāo)記。

提示：X.=（3xl+a）/（2yl）,x3=X2-x1-x2,y3=X（xl-x3）-yl

4）計(jì)算10P,圖上標(biāo)記。

5）ECDH協(xié)議中，假設(shè)生成元是P,Alice隨機(jī)取a=6,發(fā)送給Bob什么？Bob隨機(jī)取b=7,

發(fā)送Alice什么？最后協(xié)商的密鑰是什么？

6)EIGamal的ECC版本，，Alice的私鑰是d=ll,則公鑰是多少。

7)Bob用Alice的公鑰進(jìn)行加密，如果明文Pm=(4,5),則加密后的明文是多少？

8)Alice收到密文后，如何進(jìn)行解密?

用代碼實(shí)現(xiàn)這個(gè)題目，寫(xiě)3個(gè)函數(shù)，KEYGEN,ENC,DEC。

第7章公鑰加密(基礎(chǔ))

33)公鑰加密的提出是為了解決對(duì)稱加密方法的什么缺陷？

(1)密鑰分發(fā)問(wèn)題。使用對(duì)稱密鑰體制進(jìn)行保密通信時(shí)，通信雙方需要事先通過(guò)安全(保

密)信道傳遞密鑰，但是安全信道不易實(shí)現(xiàn)。因此，對(duì)稱密鑰的分發(fā)問(wèn)題一直困擾著密碼專(zhuān)

家.

(2)密鑰管理問(wèn)題。對(duì)稱密碼體制的密鑰量太大。在n個(gè)用戶的通信網(wǎng)絡(luò)中，每個(gè)用戶想

要和其他n-1個(gè)用戶進(jìn)行通信，必須使用n-1個(gè)密鑰，從而系統(tǒng)的總密鑰量達(dá)到n(n-l)/2o

當(dāng)n較大時(shí)，這樣龐大的密鑰量在產(chǎn)生、保存、傳遞、使用和銷(xiāo)毀等各個(gè)環(huán)節(jié)中都會(huì)變得很

復(fù)雜，存在安全隱患。

(3)不可抵賴性(不可否認(rèn)性)。在對(duì)稱密鑰體制中通信雙方擁有同樣的密鑰，所以接收方

可以偽造發(fā)送方的消息和消息鑒別碼，發(fā)送方也可以否認(rèn)發(fā)送過(guò)某個(gè)消息。公鑰密碼體制的

數(shù)字簽名解決了這個(gè)問(wèn)題。

34)畫(huà)公鑰加密的加密模型和認(rèn)證模型？

35)Merkle提出在非安全信道上安全通信，他的方案是如何做到的？他的方案為何可以對(duì)

抗竊聽(tīng)者或者確保通信的保密性？

下面介紹Alice如何不需要先和Bob交換系統(tǒng)密鑰就能把加密信息發(fā)給Bob：

(1)Bob產(chǎn)生大量的謎題，每個(gè)需要一定的計(jì)算才能解開(kāi)，例如這些謎題可以采用這種形

式：用一個(gè)未知的密鑰加密，密鑰長(zhǎng)度必須足夠短，以允許蠻力攻擊；

(2)Bob發(fā)送所有的謎題給Alice；

(3)Alice隨機(jī)選擇一個(gè)謎題然后通過(guò)窮舉法(蠻力攻擊)解決該謎題。解決后的謎題中包

含一個(gè)標(biāo)識(shí)，以及一個(gè)會(huì)話密鑰，這樣Alice可以用解決的謎題中的密鑰與Bob進(jìn)行通信(即

用會(huì)話密鑰加密，并傳輸標(biāo)識(shí)給Bob,Bob于是知道Alice使用的是哪個(gè)會(huì)話密鑰)。

竊聽(tīng)者即使看到Bob發(fā)送的謎題，以及Alice發(fā)送的密文和標(biāo)識(shí)，想猜測(cè)會(huì)話密鑰，必須(依

靠蠻力攻擊)解出所有的謎題。如果猜測(cè)每個(gè)謎題的需要的時(shí)間為0(n),謎題數(shù)量為m,

則Alice需要0(n)時(shí)間破解一個(gè)謎題，從而和Bob共享一個(gè)密鑰。然而竊聽(tīng)者需要O(m*n)

的時(shí)間才能破解所有的謎題，從而發(fā)現(xiàn)Alice和Bob之間共享的密鑰。如果n約等于m,則

竊聽(tīng)者的耗時(shí)約為Alice的平方。

上述方案保證了“發(fā)送者和接受者解決謎題比竊聽(tīng)者容易”，從而確保通信的保密性。

36)背包加密中普通背包和簡(jiǎn)單背包的區(qū)別是什么？為什么針對(duì)簡(jiǎn)單背包，給出S和集合A,

可以很快得到選擇的是集合中的哪些元素。

區(qū)別：簡(jiǎn)單背包問(wèn)題更容易求解。當(dāng)給定了背包向量A之后，普通背包問(wèn)題求解x需要通過(guò)

窮舉搜索法且時(shí)間復(fù)雜度為0(2，、')；簡(jiǎn)單背包問(wèn)題求解x通過(guò)

=(J-f即可得到*的值。

XNI0.S<ay

其原因易知：如果S>a,時(shí)ar=0(沒(méi)有“、?)，其它的加起來(lái)也不會(huì)比aw大，自然也不會(huì)

達(dá)到5因此，簡(jiǎn)單背包很容易得到選擇的是集合中的哪些元素。

37)描述背包加密方案。

假設(shè)A的私鑰是A=(1,3,5,10,20,41,83,170),W=7,M=351,寫(xiě)出A的公鑰。

假設(shè)B要加密的明文為10010110,計(jì)算密文。

為什么敵人看到密文不能求出明文？

A收到密文后，如何對(duì)密文進(jìn)行解密，解密結(jié)果是否等于明文.

簡(jiǎn)單背包向量A=(1,3,5,10,20,41,83,170)設(shè)為(bi)2…一)，模數(shù)M=351,正整數(shù)

W=7<>顯然1<W<M—1且gcd(W,=1>計(jì)算山=WbimodM(i=1,2,,n)公鑰

為⑶幽,…aj,即(7,21,35,70,140,287,230,137)。

加密算法

(1)把明文表示成長(zhǎng)度為"的比特串，即m=(mi,m2,…,mJ；

(2)計(jì)算密文c=miai+m2a2+…+?1前。

把明文表示成長(zhǎng)度為n的比特串,即m=(mi,m2,...,mn),密文c=miai+m2a2+...+01冏=594.

解密算法：

(1)計(jì)算，=W-1^modM-

(2)求出(以，〃，…,rjr,G{0.1},使得d=nbi+r2b2+...+%%；

明文即m=…,/n)=(mi，?U2,這里”"=rtJ,=1.2....,??<)

敵人沒(méi)有私鑰(bl,b2,…,bn,W,M)因此即使看到密文也很難解出明文。

由于d=W-1cmodM=印一1￡屋mmmodM—S.L,mibimodM

所以，d=(l+10+41+83)mod351=135,由此可以求出(口.*..…r”)，r,€(0.1}，使得

d=ribi+r2b2+...+rnb”明文即7n=(，1&rIt)=(m］，m，2,…，?”n)，這里

mi==1.2...n-至此，不難得出解密結(jié)果就是明文。

實(shí)驗(yàn)題(實(shí)習(xí)課再完成)：

6)編寫(xiě)背包加密算法的Java/C/Python/C#代碼。

探索題(選作，思考)：

子集求和問(wèn)題是困難的嗎？

給你一個(gè)困難問(wèn)題，你可以設(shè)計(jì)一個(gè)加密方案嗎？

第9章公鑰加密(高級(jí))

4)寫(xiě)Diffie-Hellman密鑰交換協(xié)議圖?

B隨機(jī)選擇be[2,p-2]

計(jì)算Yb=gbmodp

b

=(Ya)modp

Diffie-Hellman密鑰協(xié)商過(guò)程

5)寫(xiě)日Gamal加密方案，畫(huà)圖指出其與Diffie-Hellman協(xié)議的對(duì)應(yīng)關(guān)系。

日Gamal方案的描述如下：

-~1.密鑰生成

(1)隨機(jī)選擇一個(gè)滿足安全性要求的大素?cái)?shù)〃，且要求1有大素?cái)?shù)因子，g€

是一個(gè)生成元；

(2)選一個(gè)隨機(jī)數(shù)〃(1Wd40—2)，計(jì)算"三mod",則公鑰為①,q,〃)，私鑰為

c。

2.加密過(guò)程

與RSA密碼體制相同，加密時(shí)首先對(duì)明文比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)

小于小即分組長(zhǎng)度小于log?0然后對(duì)每個(gè)明文分組作加密運(yùn)算。具體過(guò)程為：

(1)把消息，”分組為長(zhǎng)度為L(zhǎng)(L＜-gap)的消息分組m=mim????mu

(2)隨機(jī)選擇整數(shù)小1＜行＜p-1(1，力；

(3)計(jì)算Q=(/'modp,d=rriiy'-modp(1(〃W方)；

(4)將密文。=(cig)。.6)???(5《)發(fā)送給接收發(fā)。

3.解密過(guò)程

(1)接收方收到的密文為。=伍1《)伍2,⑹…際4);

(2)使用私鑰)和解密算法〃“二(d/c?)modp(1W匕Wt)；

(3)得到明文m??■皿。

A

A隨機(jī)選擇dG[2,p-2]

計(jì)算y=gdmodp

B隨機(jī)選擇re[2,p-2]

c7cd=mk/k=m計(jì)算c=g「modp

K=cdmodpK=yrmodp

Diffie-Hellman密鑰協(xié)商過(guò)程和ElGamal加密的關(guān)系

6)描述ElGamal版本橢圓曲線加密方案，并畫(huà)圖指出與ElGamal密碼方案的對(duì)應(yīng)關(guān)系。

一個(gè)直接構(gòu)造橢圓曲線上的公鑰密碼體制的方法是使用某種編碼的方法,將明文編碼為

橢圓曲線上的一個(gè)點(diǎn)，然后利用日Gamal的思路，利用DHP的困難性，構(gòu)造一個(gè)共享密鑰

來(lái)作為明文的“mask”，加密明文(某個(gè)橢圓曲線上的點(diǎn))。

類(lèi)比日Gamal密碼體制(運(yùn)算從模乘變?yōu)闄E圓曲線群的加)，容易給出一種密碼體制如

下(ElGamal的橢圓曲線版本):

1.密鑰生成

設(shè)&是有限域GF(p)上的橢圓曲線，G是E“中具有較大素?cái)?shù)階n的一個(gè)點(diǎn)。隨機(jī)選擇一個(gè)

整數(shù)，/,使得2《d。一1,計(jì)算戶=力式，/是私鑰，(P,G,E.n促公鑰。

2.加密算法

將明文編碼為E"中的元素(即橢圓曲線上的一個(gè)點(diǎn))，再選取隨機(jī)數(shù)r：2<r<n-l,計(jì)算

c=r?G

c#=Pm+r?P

3.解密算法

利用私鑰d,計(jì)算出Pm=c—d?c。對(duì)Pm解碼得到明文m。

實(shí)驗(yàn)題(實(shí)習(xí)課再完成)：

3)編寫(xiě)橢圓曲線加密算法的Java/C/Python/C#代碼。

4)編寫(xiě)ElGamal加密和解密的Java/C/Python/C#/Ruby/Matlab/...代碼。

設(shè)計(jì)題：

9)畫(huà)出橢圓曲線En(l,l)離散點(diǎn)圖形。

10)取P=(l,5),Q=(3,3),計(jì)算P+Q。圖上標(biāo)記。

提示：X=(y2-yl)/(x2-xl),x3=X2-xl-x2,y3=X(xl-x3)-yl

11)計(jì)算2P,3P,4P,圖上標(biāo)記。

提示：X=(3xl+a)/(2yl),x3=X2-x1-x2,y3=X(xl-x3)-y1

12)計(jì)算10P,圖上標(biāo)記。

13)ECDH協(xié)議中，假設(shè)生成元是P,Alice隨機(jī)取a=6,發(fā)送給Bob什么？Bob隨機(jī)取b=7,

發(fā)送Alice什么？最后協(xié)商的密鑰是什么？

14)ElGamal的ECC版本，，Alice的私鑰是d=ll,則公鑰是多少。

15)Bob用Alice的公鑰進(jìn)行加密，如果明文Pm=(4,5),則加密后的明文是多少？

16)Alice收到密文后，如何進(jìn)行解密?

用代碼實(shí)現(xiàn)這個(gè)題目，寫(xiě)3個(gè)函數(shù)，KEYGEN,ENC,DEC。

第9章數(shù)字簽名

38)數(shù)字簽名的5元組分別表示什么？

定義9.1一個(gè)數(shù)字簽名方案是一個(gè)5元組(M,S,K,SIGN,VRFY),滿足如下的條件:

(1)M是一個(gè)可能消息的有限集；

(2)S是一個(gè)可能簽名的有限集；

(3)密鑰空間K是一個(gè)可能密鑰的有限集；

(4)對(duì)每一個(gè)-都對(duì)應(yīng)一個(gè)簽名函數(shù)€S/GN和驗(yàn)證算法

Vrftjk,.€VRFYc每一?個(gè)Sign*.:M—>S和驗(yàn)證函數(shù)l'r/探”：MxS—>{True.False}

是一個(gè)對(duì)任意消息m0股和任意簽名sc￡滿足下列方程的函數(shù)：

Trues=Signjm)

Vrfy(m,s)=

Falses*Signk?(m)

對(duì)每一個(gè)〃cK,函數(shù)52加.和1。了?底都是多項(xiàng)式時(shí)間可計(jì)算的函數(shù)。Vr/協(xié)“是一個(gè)

公開(kāi)函數(shù)，鼠為公鑰(驗(yàn)證密鑰)；島是一個(gè)密碼函數(shù)，晨為私鑰(簽名密鑰)，要秘密

保存。

39)Rabin和RSA數(shù)字簽名的簽名函數(shù)和驗(yàn)證函數(shù)分別是什么？

Rabin數(shù)字簽名描述如下：

(1)密鑰生成

兩個(gè)隨機(jī)選取的相異的大素?cái)?shù)〃和(7,n=p(f,其中“為公鑰，〃和。需要保密。消息空

間和簽名空間都是由同為?！ㄆ椒绞Ｓ嗪湍！Ｆ椒绞Ｓ嗟恼麛?shù)構(gòu)成的集合。

(2)簽名生成

如果消息小€Z”簽名時(shí)，首先要確保，”既是〃的平方剩余，又是(7的平方剩余。如果不

能滿足這一條件，可先對(duì)，”做一個(gè)變換，將其映射成符合要求的，假設(shè)對(duì)"，簽名，

s=Sign(m)=y/rnmod

(3)簽名驗(yàn)證

Vrfy(m,s)=true<=>m=s2mod