第02章 常規(guī)加密的經(jīng)典技術(shù)

第二章常規(guī)加密的經(jīng)典技術(shù)密碼學(xué)基本概念常規(guī)加密模型隱寫術(shù)替代加密和轉(zhuǎn)置加密簡單的XOR一次一用密碼本11.密碼學(xué)基本概念發(fā)送者和接收者在信息傳送過程中，主動提供信息的一方稱發(fā)送者，得到信息的一方稱接收者。發(fā)送者要確保信息安全傳送，使竊聽者不能盜取信息。21.密碼學(xué)基本概念密碼技術(shù)目的：使不知道如何解密的黑客不可能由其截獲的亂碼中得到任何有意義的信息；使黑客不可能偽造任何亂碼型的信息。密碼學(xué)(密碼技術(shù))分類密碼編碼學(xué)：對信息進行編碼實現(xiàn)信息隱蔽密碼分析學(xué)：研究分析破譯密碼31.密碼學(xué)基本概念密碼通信系統(tǒng)模型41.密碼學(xué)基本概念被隱蔽的消息稱作明文密碼可將明文變換成另一種隱蔽形式，稱為密文。由明文到密文的變換稱為加密。由合法接收者從密文恢復(fù)出明文的過程稱為解密（或脫密）。非法接收者試圖從密文分析出明文的過程稱為破譯。對明文進行加密時采用的一組規(guī)則稱為加密算法。對密文解密時采用的一組規(guī)則稱為解密算法。加密算法和解密算法是在一組僅有合法用戶知道的秘密信息，稱為密鑰的控制下進行的。加密和解密過程中使用的密鑰分別稱為加密密鑰和解密密鑰。51.密碼學(xué)基本概念明文消息空間M；密文消息空間C；密鑰空間K1和K2；加密交換Ek1：M—〉C，其中k1∈K1；

解密變換Dk2：CM，其中k2∈K2；稱總體（M，C，K1，K2，Ek1，Dk2）為密碼系統(tǒng)。對于給定明文消息m∈M，密鑰k1∈K1，加密交換將明文m變換為密文c：c＝f(m,k1)＝Ek1(m)m∈M，k1∈K161.密碼學(xué)基本概念合法接收者，利用其知道的解密密鑰k2對收到的密文進行變換，恢復(fù)出明文消息m＝Dk2(c)m∈M，k2∈K2黑客則利用其選定的變換函數(shù)h，對截獲的密文c進行變換，得到的明文是明文空間的某個元素m’＝h(c)m∈M，k2∈K2一般m’≠m。如果m’＝m，則黑客破譯成功。71.密碼學(xué)基本概念認證，完整性和不許抵賴認證：信息接受者應(yīng)有可能核查信息來源，任何闖入者無力裝扮成原有的發(fā)送者。完整性：信息接收者應(yīng)有可能驗證信息在傳播中未經(jīng)修改，闖入者無力用假信息代替合法的原有信息。不可抵賴：發(fā)送者在發(fā)送出信息后無法抵賴他所發(fā)出的信息。81.密碼學(xué)基本概念算法和密鑰密碼算法，稱為加密算法，是用來加密和解密的數(shù)學(xué)函數(shù)。為給明文信息加密，用加密算法函數(shù)。為給密文信息解密，用解密算法函數(shù)。如果算法的安全性基于算法工作的保安，這是一個受約算法。近代密碼術(shù)用密鑰來解決安全性問題。91.密碼學(xué)基本概念算法和密鑰加密和解密函數(shù)表示EK(M)=CDK(C)=M若加密和解密密鑰相同：DK(EK(M))＝M若加密和解密密鑰不同：EK1(M)＝CDK2(C)=MDK2(EK1(M))=M101.密碼學(xué)基本概念密碼系統(tǒng)分類用于將明文轉(zhuǎn)換為密文操作的類型。所有加密算法基于兩個基本原則：①替代，即明文中的每個元素（比特、字母、比特組合或字母組合）被映射為另一個元素；②轉(zhuǎn)置，即在明文中的元素被重排列，對它們的基本要求是不丟失信息（即所有操作都是可逆轉(zhuǎn)的）。被稱為乘積系統(tǒng)的多數(shù)系統(tǒng)涉及多個階段的替代和轉(zhuǎn)置。所使用密鑰的數(shù)量。如果發(fā)送者和接收者雙方使用相同的密鑰，該系統(tǒng)稱為對稱加密、單密鑰加密、秘密密鑰加密或常規(guī)加密。如果發(fā)送者和接收者各自使用一個不同的密鑰，則該系統(tǒng)稱為非對稱加密、雙密鑰加密或公開密鑰加密。明文處理的方式。分組加密一次處理一塊元素的輸入，對每個輸入塊產(chǎn)生一個輸出塊。流（序列）加密連續(xù)地處理輸入元素，并隨著該過程的進行，一次產(chǎn)生一個元素的輸出。111.密碼學(xué)基本概念單鑰密碼的特點是無論加密還是解密都使用同一個密鑰，因此，此密碼體制的安全性就是密鑰的安全。如果密鑰泄露，則此密碼系統(tǒng)便被攻破。最有影響的單鑰密碼是1977年美國國家標(biāo)準(zhǔn)局頒布的DES算法。優(yōu)點：安全性高、加解密速度快。缺點：1)隨著網(wǎng)絡(luò)規(guī)模的擴大，密鑰的管理成為一個難點；2)無法解決消息確認問題；3)缺乏自動檢測密鑰泄露的能力。121.密碼學(xué)基本概念雙鑰體制特點加密密鑰與解密密鑰不同，此時不需要安全信道來傳送密鑰而只需利用本地密鑰發(fā)生器產(chǎn)生解密密鑰k2∈K2。并以此來控制解密操作D。雙鑰密碼是1976年W.Diffie和M.E.Hellman提出的一種新型密碼體制。優(yōu)點：由于雙鑰密碼體制的加密和解密不同，且能公開加密密鑰，而僅需保密解密密鑰，所以雙鑰密碼不存在密鑰管理問題。雙鑰密碼還有一個優(yōu)點是可以擁有數(shù)字簽名等新功能。最有名的雙鑰密碼是1977年由Rivest，Shamir和Adleman三人提出的RSA密碼體制。缺點：雙鑰密碼算法一般比較復(fù)雜，加解密速度慢。131.密碼學(xué)基本概念序列密碼加密過程是把明文序列與等長的密鑰序列進行逐位模2加。解密過程則是把密文序列與等長的密鑰序列進行逐位模2加。安全性：主要依賴于密鑰序列。最著名的序列密碼是“一次一密密碼”，它的密鑰序列是真正的隨機二元序列。優(yōu)點：1)處理速度快，實時性好；2)錯誤傳播??；3)不存在串破譯問題；4)適用于軍事、外交等保密信道。缺點：1)明文擴散性差；2)插入信息的敏感性差；3)需要密鑰同步。141.密碼學(xué)基本概念分組密碼加密方式是首先將明文序列以固定長度進行分組，每一組明文用相同的密鑰和加密函數(shù)進行運算。為了減少存儲量和提高運算速度，密鑰的長度一般不大，因而加密函數(shù)的復(fù)雜性成為系統(tǒng)安全的關(guān)鍵。分組密碼設(shè)計的核心是構(gòu)造既具有可逆性又有很強的非線性的算法。加密函數(shù)重復(fù)地使用代替和置換兩種基本的加密變換。優(yōu)點：1)明文信息良好的擴散性；2)對插入的敏感性；3)不需要密鑰同步；4)較強的適用性，適宜作為加密標(biāo)準(zhǔn)。缺點：1)加密速度慢；2)錯誤易擴散和傳播。151.密碼學(xué)基本概念密碼破譯密碼破譯則是無須取得密鑰而能將密文信息恢復(fù)成明文的科學(xué)。密碼破譯成功，不僅恢復(fù)明文也可得到密鑰。并且發(fā)現(xiàn)密碼系統(tǒng)中導(dǎo)致上述結(jié)果的弱點。僅知密文攻擊已知明文攻擊選擇明文攻擊選擇文本（自適應(yīng)選擇明文攻擊）選擇密文攻擊選擇密鑰攻擊牛皮筋式破譯161.密碼學(xué)基本概念僅知密文攻擊在這種攻擊中，密碼破譯員有幾個信息的密文，所有的信息使用相同加密算法加密。為將相同密鑰加密的信息解密，密碼破譯員會盡可能多地恢復(fù)信息的明文，或者更好地是導(dǎo)出用于加密信息的密鑰。已知：C1=EK(P1)，C2=EK(P2)，…，Ci=EK(Pi)導(dǎo)出：P1、P2…Pi、K或?qū)С鰪腃i+1=EK(Pi+1)得知Pi+1的算法

已知明文攻擊密碼破譯員不但利用幾個信息的密文，而且有這些信息的明文。導(dǎo)出用于加密信息的密鑰或用相同的密鑰加密任何新的信息的解密算法。已知：P1，C1=EK(P1)，P2，C2=EK(P2)，…，Pi，Ci=EK(Pi)導(dǎo)出：K或?qū)С鰪腃i+1=EK(Pi+1)得知Pi+1的算法171.密碼學(xué)基本概念選擇明文攻擊密碼破譯員不但利用密文和涉及到的信息的明文，而且能選擇加密的明文。這比已知明文攻擊更強有力，因為密碼破譯員能選擇專用的明文塊加密，可能產(chǎn)生更多關(guān)于密鑰的信息。導(dǎo)出用于加密信息的密鑰或用相同的密鑰加密任何新的信息的解密算法。已知：P1，C1=EK(P1)，P2，C2=EK(P2)，…，Pi，Ci=EK(Pi)其中密碼分析者選擇P1、P2…Pi導(dǎo)出：K或?qū)С鰪腃i+1=EK(Pi+1)得知Pi+1的算法

選擇文本（自適應(yīng)選擇明文攻擊）這是選擇明文攻擊的一個特例。密碼破譯員不但選擇加密的明文，而且能依據(jù)以前加密的結(jié)果修改選擇。在選擇明文攻擊中，密碼破譯員可以選擇一大塊明文加密；在自適應(yīng)選擇明文攻擊中，選擇一個較小的明文塊，然后依據(jù)第一次的結(jié)果選擇另一塊，等等。

181.密碼學(xué)基本概念選擇密文攻擊密碼破譯員能選擇不同的將要解密的密文和已解的明文，將它們放入一個自動解密的分解判別的工具箱中，導(dǎo)出密鑰。已知：C1，P1=DK(C1)，C2，P2=DK(C2)，…Ci，Pi=DK(Ci)導(dǎo)出：K這種攻擊主要應(yīng)用于公開密鑰加密系統(tǒng)。選擇密文攻擊有時對對稱算法一樣有效。選擇密鑰攻擊這種攻擊并不意味破譯員能選擇密鑰。只不過破譯員對不同密鑰之間的關(guān)系有所了解。它較新奇和含混但并不實用。牛皮筋式破譯破譯員威脅、寫黑信或折磨某人直至給出密鑰，或用金錢收買，所以也稱購買密鑰攻擊，這已不是科學(xué)技術(shù)的內(nèi)容了，但在現(xiàn)實社會中卻也常有奏效。

191.密碼學(xué)基本概念攻擊的類型密碼破譯者己知的東西僅有密文加密算法待破譯的密文已知明文加密算法待破譯的密文由密鑰形成的一個或多個明文——密文對選擇明文加密算法待破譯的密文由密碼破譯者選擇的明文消息，連同它對應(yīng)的由其密鑰生成的密文選擇文本加密算法待破譯的密文由密碼破譯者選擇的明文消息，連同它對應(yīng)的由密鑰生成的密文由密碼破譯者選擇的猜測性的密文，連同它對應(yīng)的由密鑰生成的已破譯的明文加密算法待破譯的密文由密碼破譯者選擇的猜測性的密文，連同它對應(yīng)的由密鑰生成的已破譯的明文密碼破譯方法小結(jié)201.密碼學(xué)基本概念算法安全性算法根據(jù)攻破的難易標(biāo)定了不同的安全程度。如攻破某算法的費用大于加密數(shù)據(jù)的代價，該算法認為是安全的。如攻破某算法的時間長于數(shù)據(jù)的保密期，該算法也認為是安全的。同樣如攻破某算法所需的數(shù)據(jù)量多于密鑰加密的數(shù)據(jù)量，該算法仍認為是安全的。以上所說的安全并非絕對，因為在密碼破譯中新的攻破機遇頻頻發(fā)生，另一方面大部分數(shù)據(jù)的價值會隨時間流逝而貶低。所以，安全的要點是數(shù)據(jù)的價值要繼續(xù)保持低于攻破安全屏障所花的代價。211.密碼學(xué)基本概念LarsKnudsen按攻破算法難易的遞降順序，分類如下：全攻破，密碼破譯員找到密鑰K，于是解密DK(C)=M。全局推導(dǎo)，密碼破譯員找到另一算法A，無須知道K，因為A等價于DK(C)而解密。局部推導(dǎo)，密碼破譯員找到竊聽來的密文的明文而解密。信息推導(dǎo)，密碼破譯員得到關(guān)于密鑰信息或是有關(guān)明文格式的信息。利用這些信息而解密。如果無論破譯員有多少密文，仍無足夠信息能恢復(fù)明文，這樣的算法是無條件安全的。事實上只有一次一用的密碼本是不可攻破的。其它所有密碼系統(tǒng)在惟密文攻擊下都是可以攻破的。221.密碼學(xué)基本概念加密算法的安全準(zhǔn)則：破譯該密碼的成本超過被加密信息的價值。破譯該密碼的時間超過該信息有用的生命周期。攻擊復(fù)雜性的度量：數(shù)據(jù)復(fù)雜性，為攻擊所需數(shù)據(jù)的攻擊量。處理復(fù)雜性，執(zhí)行攻擊所須的時間，又稱工作因子。存儲需求，做攻擊所須的存儲量。231.密碼學(xué)基本概念自然界常用大數(shù)物理類似物數(shù)字到下個冰世紀(jì)的時間14,000（214）年到太陽銷毀的時間109（230）年行星的壽命109（230）年宇宙的壽命（如果宇宙是開放的）1011（267）年到小質(zhì)量恒星冷卻時間1016（261）秒到行星脫離恒星時間1015（230）年到所有恒星離開銀河的時間1019（264）年到天體軌道因向心輻射而消逝時間1020（267）年到黑洞因Hawking過程而消逝時間1064（2213）年到所有物質(zhì)冷卻成零度液體的時間1065（2216）年到所有物質(zhì)衰變成鐵的時間101026年到所有物質(zhì)陷落到黑洞的時間101076年241.密碼學(xué)基本概念密鑰長度與安全性評估密鑰長度（bit）密鑰數(shù)量每微秒加密1次所需時間每微秒加密100萬次所需時間32232=4.3x109

231us=35.8分2.15微秒56256=7.2x1016

255us=1142年10.01小時1282128=3.4x1038

2127us=5.4x1024年5.4x1018年26字符（排列）26!=4x1026

2x1026us=6.4x1012年6.4x106年252.常規(guī)加密模型常規(guī)加密的簡化模型262.常規(guī)加密模型常規(guī)密碼系統(tǒng)的模型272.隱寫術(shù)字符標(biāo)記：印刷或打印的文本字母經(jīng)選擇用鉛筆重寫。該標(biāo)記通常不可見，除非該紙以一定的角度對著亮光看。不可見墨水：使用一些物質(zhì)來書寫，但不留下任何可見痕跡，除非加熱該紙或在該紙上涂上某種化學(xué)藥品。扎小孔：在所選的字母上扎小孔，這些小孔通常不可見，除非把該紙放在光的前面。打字機改正帶：用于行間與一根黑帶一同打印，用改正帶打印的結(jié)果僅在強光下才可見。格孔密寫卡：將它覆蓋在一張紙上從格孔中寫入密件，然后在紙上余下部分填入其它字句，使它像一般信件。282.隱寫術(shù)示例：293.替代加密和置換加密替代技術(shù)置換技術(shù)轉(zhuǎn)子機（RotorMachine）303.替代加密和置換加密替代技術(shù)替代技術(shù)是這樣一種技術(shù)，其中明文的字母由其他字母或數(shù)字或符號所代替。如果該明文被視為一個比特序列，則替代涉及到用密文比特模式代替明文比特模式。在經(jīng)典密碼學(xué)中，替代加密算法有四種基本類型：簡單替代加密算法或稱單字符加密，明文每一字符被替代成密文中的相應(yīng)字符。新聞密電就是用這種方法。同音替代加密算法，類似于簡單替代加密算法，但明文中的單一字符能對應(yīng)密文中的幾個字符。例如“A”可能相應(yīng)于5、13、25或“B”可能相應(yīng)于7、19、31或42等等。多元替代加密算法，成塊的字符加密成一組其它字符。如“ABA”相應(yīng)于“RTQ”，“ABB”相應(yīng)于“SLL”等等。多字母替代加密算法，由多次簡單替代加密組成。例如用5次不同的簡單替代加密，具體所用的次數(shù)隨每一字符在明文中的位置而變化。313.1替代加密移位密碼體制設(shè)P=C=K=Z/(26),對k∈K,定義ek(x)=x+k(mod26)=y∈C同時dk(y)=y-k(mod26)注1*：26個英文字母與模26剩余類集合{0,….,25}建立一一對應(yīng)：

ABCDEFGHIJKLMNOPQRSTUVWXYZ

0

12345678910111213141516171819202122232425

2*.當(dāng)k=3時，為Caesar密碼：明文：meetmeafterthetogaparty

密文：PHHWPHDIWHOWKHWRJDSDUWB

實際算法為：有

同時有，d3(y)=y-3(mod26)323.1替代加密替換密碼體制設(shè)P=C=Z/(26)，K是由26個符號0，1,..,25的所有可能置換組成。任意π∈K，定義eπ(x)=π(x)=y且dπ(y)=-1(y)=x,π-1是π的逆置換。

注：1*.置換π的表示：

π＝2*密鑰空間K很大，|k|=26!≈4×1026，破譯者窮舉搜索是不行的，然而，可由統(tǒng)計的方式破譯它。3*移位密碼體制是替換密碼體制的一個特例，它僅含26個置換做為密鑰空間(0123..2324250'1'2'3'..23'24'25')333.1替代加密仿射密碼體制替換密碼的另一個特例就是仿射密碼。加密函數(shù)取形式為

e(x)=ax+b(mod26),a,b∈Z/(26)

要求唯一解的充要條件是gcd(a,26)=1

該體制描述為：

設(shè)P=C=Z/(26)K={(a,b)∈Z/(26)×Z/(26)|gcd(a,26)=1},

對k=(a,b)∈K,

定義ek(x)=ax+b(mod26)和dk(y)=a-1(y-b)(mod26)x,y∈Z/(26)34例子，設(shè)k＝（7，3），注意到7-1(mod26)=15,加密函數(shù)是ek(x)=7x+3,相應(yīng)的解密函數(shù)是dk(y)=15(y-3)=15y-19,易見dk(ek(x))=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)

若加密明文：hot，首先轉(zhuǎn)換字母h,o,t成為數(shù)字7,14,19,然后加密：解密：353.1替代加密Hill密碼體制設(shè)ｍ為某個固定的正整數(shù)，P=C=(Z/(26))m,

K={Z/(26)上的m×m可逆矩陣}對每一個k∈K,定義ek(x)=xK(mod26)和dk(y)=yK-1(mod26)注：明文與密文都是m元的向量（x1,x2…,xm);(y1,y2,…,ym)，Z/(26)為同余類環(huán)。在這個環(huán)上的可逆矩陣Amxm,是指行列式detAmxm的值∈Z*/(26),它為Z/(26)中全體可逆元的集合。Z*/(26)={a∈Z/(26)|(a,26)=1}，

Z*/(26)={1,3,5,7,9,11,15,17,19,21,23,25}例子：當(dāng)m=2時，明文元素x=(x1,x2),密文元素y=(y1,y2)(y1,y2)=(x1,x2)

K36事實上yi為x1,x2的線性組合，y1=11x1+3x2;y2=8x1+7x2，一般，將取m×m的矩陣K作為我們的密鑰：有

y=(y1,y2,…,ym,)=(x1,x2,…,

xm)

換言之，y=xK;且有x=yK-1

若K=,可得K-1=若對明文july加密，它分成2個元素（j,u),(l,y),分別對應(yīng)于（9,20）,（11,24）,有37（9,20）＝（99＋60,72＋140）＝（3,4）

且（11,24）＝(121＋72,88＋168)＝（11,22）于是對july加密的結(jié)果為DELW。為了解密，Bob計算

且因此，得到了正確的明文“july”

383.1替代加密維吉尼亞密碼(Vigenere)設(shè)m為一固定的正整數(shù)，定義P=C=K=(Z/(26))m,對一個密鑰K＝（k1,k2,…,km),定義ek(x1,x2,…,xm)=(x1+k1,x2+k2,…,xm+km)=y

dk(y1,y2,…,ym)=(x1-k1,x2-k2,…,xm-km)=x這里的所有的運算都是在（mod26)中進行的。注：維吉尼亞密碼是多表替換體制，分析起來更困難。密鑰空間大，如當(dāng)m=5時，密鑰空間所含密鑰的數(shù)量是>1.1×107393.替代加密和置換加密置換技