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

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

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

已知明文攻擊密碼破譯員不但利用幾個(gè)信息的密文，而且有這些信息的明文。導(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é)基本概念選擇明文攻擊密碼破譯員不但利用密文和涉及到的信息的明文，而且能選擇加密的明文。這比已知明文攻擊更強(qiáng)有力，因?yàn)槊艽a破譯員能選擇專(zhuān)用的明文塊加密，可能產(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)選擇明文攻擊）這是選擇明文攻擊的一個(gè)特例。密碼破譯員不但選擇加密的明文，而且能依據(jù)以前加密的結(jié)果修改選擇。在選擇明文攻擊中，密碼破譯員可以選擇一大塊明文加密；在自適應(yīng)選擇明文攻擊中，選擇一個(gè)較小的明文塊，然后依據(jù)第一次的結(jié)果選擇另一塊，等等。

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

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

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

255us=1142年10.01小時(shí)1282128=3.4x1038

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

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

ABCDEFGHIJKLMNOPQRSTUVWXYZ

0

12345678910111213141516171819202122232425

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

密文：PHHWPHDIWHOWKHWRJDSDUWB

實(shí)際算法為：有

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

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

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

對(duì)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,易見(jiàn)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è)ｍ為某個(gè)固定的正整數(shù)，P=C=(Z/(26))m,

K={Z/(26)上的m×m可逆矩陣}對(duì)每一個(gè)k∈K,定義ek(x)=xK(mod26)和dk(y)=yK-1(mod26)注：明文與密文都是m元的向量（x1,x2…,xm);(y1,y2,…,ym)，Z/(26)為同余類(lèi)環(huán)。在這個(gè)環(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時(shí)，明文元素x=(x1,x2),密文元素y=(y1,y2)(y1,y2)=(x1,x2)

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

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

xm)

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

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

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

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

383.1替代加密維吉尼亞密碼(Vigenere)設(shè)m為一固定的正整數(shù)，定義P=C=K=(Z/(26))m,對(duì)一個(gè)密鑰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這里的所有的運(yùn)算都是在（mod26)中進(jìn)行的。注：維吉尼亞密碼是多表替換體制，分析起來(lái)更困難。密鑰空間大，如當(dāng)m=5時(shí)，密鑰空間所含密鑰的數(shù)量是>1.1×107393.替代加密和置換加密置換技