1、密碼協(xié)議結構模塊,協(xié)議介紹,密碼學的用途是解決種種難題（實際上，這也是計算機的主要用途）。密碼學解決的各種難題圍繞機密性、鑒別、完整性和不誠實的人。 協(xié)議是一系列步驟，它包括兩方或多方，設計它的目的是要完成一項任務。這個定義很重要 ：“一系列步驟”意味著協(xié)議是從開始到結束的一個序列，每一步必須依次執(zhí)行，在前一步完成前，后面的步驟都不能執(zhí)行 ；“包括兩方或多方”意味著完成這個協(xié)議至少需要兩個人，單獨的一個人不能構成協(xié)議，當然單獨的一個人也可采取一系列步驟去完成一個任務（例如烤蛋糕），但這不是協(xié)議（另外一些人必須吃蛋糕才構成協(xié)議）；最后，“設計它的目的是要完成一項任務”意味著協(xié)議必須做一些事。有些

2、東西看起來像協(xié)議，但不完成一個任務，那也不是協(xié)議，只是浪費時間而已。,協(xié)議介紹,協(xié)議還有其他特點： （1）協(xié)議中的每人都必須了解協(xié)議，并且預先知道所要完成的所有步驟。 （2）協(xié)議中的每人都必須同意遵循它。 （3）協(xié)議必須是不模糊的，每一步必須明確定義，并且不會引起誤解。 （4）協(xié)議必須是完整的，對每種可能的情況必須規(guī)定具體的動作。,協(xié)議介紹,密碼協(xié)議是使用密碼學的協(xié)議。參與該協(xié)議的伙伴可能是朋友和完全信任的人，或者也可能是敵人和互相完全不信任的人。 密碼協(xié)議包含某種密碼算法，但通常，協(xié)議的目的不僅僅是為了簡單的秘密性。參與協(xié)議的各方可能為了計算一個數(shù)值想共享它們的秘密部分、共同產生隨機系列、確

3、定互相的身份、或者同時簽署合同。在協(xié)議中使用密碼的目的是防止或發(fā)現(xiàn)偷聽者和欺騙。如果你以前沒有見過這些協(xié)議，它們會從根本上改變你的思想，相互之間不信任的各方也能夠在網絡上完成這些協(xié)議。一般地，這能夠被陳述為： 不可能完成或知道得比協(xié)議中規(guī)定的更多。 這看起來很難。接下來的幾節(jié)課中會討論許多協(xié)議。在其中的一些協(xié)議中，參與者中的一個有可能欺騙其他人。偷聽者也可能暗中破壞協(xié)議或獲悉秘密信息。一些協(xié)議之所以失敗，是因為設計者對需求不是定義得很完備。其它一些失敗是因為協(xié)議的設計者分析得不夠充分。就像算法一樣，證明它不安全比證明它安全容易得多。,協(xié)議的目的,在日常生活中，幾乎所有的事情都有非正式的協(xié)議：電

4、話訂貨、玩撲克、選舉中投票，沒有人認真考慮過這些協(xié)議，這些協(xié)議隨著時間的推移而發(fā)展，人們都知道怎樣使用它們，而且它們也很有效。 越來越多的人通過計算機網絡交流，從而代替了面對面的交流。計算機需要正式的協(xié)議來完成人們不用考慮就能做的事情。如果你換了一個購物網站進行購物，可能會發(fā)現(xiàn)支付方式與你以前使用的完全不同，你會很容易去適應它。但計算機就不那么靈活了。,協(xié)議的目的,許多面對面的協(xié)議依靠人的現(xiàn)場存在來保證公平和安全。你會交給陌生人一疊現(xiàn)金去為你買食品嗎？如果你沒有看到他洗牌和發(fā)牌，你愿意和他玩撲克嗎？ 那種假設使用計算機網絡的人都是誠實的想法，是天真的。天真的想法還有：假設計算機網絡的管理員是誠

5、實的，假設計算機網絡的設計者是誠實的。當然，絕大多數(shù)人是誠實的，但是不誠實的少數(shù)人可能招致很多損害。通過規(guī)定協(xié)議，可以查出不誠實者企圖欺騙的把戲，還可開發(fā)挫敗這些欺騙者的協(xié)議。,游戲角色,為了幫助說明協(xié)議，我們設定一些角色。Alice和Bob是開始的兩個人。他們將完成所有的兩人協(xié)議。按規(guī)定，由Alice 發(fā)起所有協(xié)議，Bob響應。如果協(xié)議需要第三或第四人，Carol和Dave將扮演這些角色。由其他人扮演的專門配角，將在后面介紹。 Alice所有協(xié)議中的第一個參加者 Bob所有協(xié)議中的第二個參加者 Carol在三、四方協(xié)議中的參加者 Dave在四方協(xié)議中的參加者 Eve竊聽者 Mallory惡意

6、的主動攻擊者 Trent值得信賴的仲裁者 Walter監(jiān)察人：在某些協(xié)議中保護Alice和Bob Peggy證明人 Victor驗證者,仲裁協(xié)議,仲裁者是在完成協(xié)議的過程中，值得信任的公正的第三方，仲裁者能幫助互不信任的雙方完成協(xié)議。 “公正”意味著仲裁者在協(xié)議中沒有既得利益，對參與協(xié)議的任何人也沒有特別的利害關系?！爸档眯湃巍北硎緟f(xié)議中的所有人都接受這一事實，即仲裁者說的都是真實的，他做的是正確的，并且他將完成協(xié)議中涉及他的部分。仲裁者能幫助互不信任的雙方完成協(xié)議。,仲裁協(xié)議,在現(xiàn)實社會中，律師經常作為仲裁者。例如，Alice要賣汽車給不認識的Bob。Bob想用支票付帳，但Alice不知道支

7、票的真假。在Alice將車子轉給Bob前，她必須查清支票的真?zhèn)巍Ｍ瑯?，Bob也并不相信Alice，就像Alice不相信Bob一樣，在沒有獲得所有權前，也不愿將支票交與Alice。 這時就需要雙方都信任的律師。在律師的幫助下，Alice和Bob能夠用下面的協(xié)議保證互不欺騙。 （1）Alice將車的所有權交給律師。 （2）Bob將支票交給Alice。 （3）Alice在銀行兌現(xiàn)支票。 （4）在等到支票鑒別無誤能夠兌現(xiàn)的時間之后，律師將車的所有權交給Bob。如果在規(guī)定的時間內支票不能兌現(xiàn)，Alice將證據出示給律師，律師將車的所有權和鑰匙交還給Alice。,仲裁協(xié)議,這種思想可以轉化到計算機世界中，

8、但計算機仲裁者有下面幾個問題： （1）如果你知道對方是誰，并能見到他的面，就很容易找到和相信中立的第三方?；ハ鄳岩傻碾p方很可能也懷疑在網絡別的什么地方并不露面的仲裁者。 （2）計算機網絡必須負擔仲裁者的費用。就像我們知道的律師費用，誰想負擔那種網絡費用呢？ （3）在任何仲裁協(xié)議中都有延遲的特性。 （4）仲裁者必須處理每一筆交易。任何一個協(xié)議在大范圍執(zhí)行時，仲裁者是潛在的瓶頸。增加仲裁者的數(shù)目能緩解這個問題，但費用將會增加。 （6）由于在網絡中每人都必須相信仲裁者，對試圖破壞網絡的人來說，仲裁者便是一個易受攻擊的弱點。 盡管如此，仲裁者仍扮演一個角色。在使用可信任的仲裁協(xié)議中，這個角色將由Tre

9、nt來扮演。,裁決協(xié)議,由于雇用仲裁者代價高昂，仲裁協(xié)議可以分成兩個低級的子協(xié)議。一個是非仲裁子協(xié)議，這個子協(xié)議是想要完成協(xié)議的各方每次都必須執(zhí)行的；另一個是仲裁子協(xié)議，僅在例外的情況下執(zhí)行的，即有爭議的時候才執(zhí)行，這種特殊的仲裁者叫做裁決人。,裁決人也是公正的和可信的第三方。他不像仲裁者，并不直接參與每一個協(xié)議。只有為了要確定協(xié)議是否被公平地執(zhí)行，才將他請來。,裁決協(xié)議,法官是職業(yè)的裁決者。法官不像公證人，僅僅在有爭議時才需要他出場，Alice和Bob可以在沒有法官的情況下訂立合同。除非他們中有一個人把另一人拖到法院，否則法官決不會看到合同。 合同簽字協(xié)議可以歸納為下面形式： 非仲裁子協(xié)議（

10、每次都執(zhí)行）： （1）Alice和Bob談判合同的條款。 （2）Alice簽署合同。 （3）Bob簽署合同。 裁決子協(xié)議（僅在有爭議時執(zhí)行）： （1）Alice和Bob出現(xiàn)在法官面前。 （2）Alice提出她的證據。 （3）Bob也提出他的證據。 （4）法官根據證據裁決。,裁決協(xié)議,裁決者和仲裁之間的不同是裁決者并不總是必需的。如果有爭議，法官被請來裁決。如果沒有爭議，就沒有必要請法官。 目前已有計算機裁決協(xié)議。這些協(xié)議依賴于與協(xié)議有關的各方都是誠實的；如果有人懷疑欺騙時，一個中立的第三方能夠根據存在的數(shù)據正文文本判斷是否有人在欺騙。在好的裁決協(xié)議中，裁決者還能確定欺騙人的身份。裁決協(xié)議是為了

11、發(fā)現(xiàn)欺騙，而不是為了阻止欺騙。發(fā)現(xiàn)欺騙是起了防止和阻礙欺騙的作用。,自動執(zhí)行的協(xié)議,自動執(zhí)行的協(xié)議是協(xié)議中最好的。協(xié)議本身就保證了公平性。不需要仲裁者來完成協(xié)議，也不需要裁決者來解決爭端。協(xié)議的構成本身不可能發(fā)生如何爭端。如果協(xié)議中的一方試圖欺騙，其他各方馬上就能發(fā)覺并且停止執(zhí)行協(xié)議。無論欺騙方想通過欺騙來得到什么，他都不能如愿以償。,最好，讓每個協(xié)議都能自動執(zhí)行。不幸的是，在現(xiàn)實所有情形下，沒有一個是自動執(zhí)行的協(xié)議。,對協(xié)議的攻擊,密碼攻擊可以直接攻擊協(xié)議中所用的密碼算法、用來實現(xiàn)該算法和協(xié)議的密碼技術、或者攻擊協(xié)議本身。在此我們僅討論協(xié)議。我們假設密碼算法和密碼技術是安全的，只關注對協(xié)議本

12、身的攻擊。 被動攻擊：與協(xié)議無關的人能夠偷聽協(xié)議的一部分或全部。因為攻擊者不可能影響協(xié)議，所有他能做的事是觀察協(xié)議并試圖獲取信息。由于被動攻擊難于發(fā)現(xiàn)，因此協(xié)議應阻止被動攻擊而不是發(fā)現(xiàn)這種攻擊。在這種協(xié)議中，偷聽者的角色將由Eve扮演。 主動攻擊：他可能假裝是其它一些人，在協(xié)議中引入新的信息，刪掉原有的信息，用另外的信息代替原來的信息，重放舊的信息，破壞通信信道，或者改變存貯在計算機中的信息等。,對協(xié)議的攻擊,被動攻擊試圖獲取協(xié)議中各方的信息。他們收集協(xié)議各方所傳送的信息，并試圖對它們進行密碼分析。而主動攻擊可能有更多的目的。攻擊者可能對獲取信息感興趣，也可能降低系統(tǒng)性能，破壞已有的信息，或者

13、獲得非授權的資源存取。 主動攻擊嚴重得多，特別是在那些各方都不必彼此信任的協(xié)議中。攻擊者不一定都是入侵者，他可能是合法的系統(tǒng)用戶，他們可能是系統(tǒng)管理員。甚至有很多主動攻擊者，他們都在一起工作，每人都是合法的系統(tǒng)用戶。這個惡意的主動攻擊者的角色將由Mallory扮演。,對協(xié)議的攻擊,攻擊者也可能是與協(xié)議有關的各方中的一方。他可能在協(xié)議期間撒謊，或者根本不遵守協(xié)議，這類攻擊者叫做騙子。被動騙子遵守協(xié)議，但試圖獲取協(xié)議外的其他信息。主動騙子在協(xié)議的執(zhí)行中試圖通過欺騙來破壞協(xié)議。 如果與協(xié)議有關的各方中的大多數(shù)是主動騙子，就很難保持協(xié)議的安全性。但合法用戶發(fā)覺是否有主動欺騙卻是可能的。當然，協(xié)議對被動

14、欺騙來說應該是安全的。,使用對稱密碼術的通信,通信雙方怎樣安全地通信呢？當然，他們可以對通信加密。完整的協(xié)議比它更復雜，讓我們來看看Alice發(fā)送加密的信息給Bob會發(fā)生什么情況吧： （1）Alice和Bob協(xié)商用同一密碼系統(tǒng)。 （2）Alice和Bob協(xié)商同一密鑰。 （3）Alice用加密算法和選取的密鑰加密她的明文信息，得到了密文信息。 （4）Alice發(fā)送密文信息給Bob。 （5）Bob用同樣的算法和密鑰解密密文，然后讀它。,使用對稱密碼術的通信,位于Alice和Bob之間的竊聽者Eve監(jiān)聽這個協(xié)議，她能做什么呢？如果她聽到的是在第（4）步中發(fā)送的密文，她必須設法分析密文，這是唯密文的被

15、動攻擊法；有很多算法能夠阻止Eve，使她不可能得到問題的解答。 盡管如此，但Eve卻不笨，她也想竊聽步驟（1）和步驟（2），這樣她就知道了算法和密鑰，她就和Bob知道的一樣多。當步驟（4）中的信息通過信道傳送過來時，她所做的全部工作就是解密密文信息。 好的密碼系統(tǒng)的全部安全性只與密鑰有關，和算法沒有任何關系。這就是為什么密鑰管理在密碼學中如此重要的原因。有了對稱算法，Alice和Bob能夠公開地實現(xiàn)步驟（1），但他們必須秘密地完成步驟（2）。在協(xié)議執(zhí)行前、執(zhí)行過程上和執(zhí)行后，只要信息必須保持秘密，密鑰就必須保持秘密，否則，信息就將不再秘密了。,使用對稱密碼術的通信,主動攻擊者Mallory可能

16、做其他一些事情，他可能企圖破壞在（4）中使用的通信信道，使Alice和Bob根本不可能通信。他也可能截取Alice的信息并用他自己的信息替代它。如果他也知道密鑰（通過截?。?）的通信或者破譯密碼系統(tǒng)），他可能加密自己的信息，然后發(fā)送給Bob，用來代替截取的信息。Bob沒有辦法知道接收到的信息不是來自Alice。如果Mallory不知道密鑰，他所產生的代替信息，被解密出來是無意義的，Bob就會認為從Alice那里來的信息是網絡或者是Alice有嚴重的問題。 Alice又怎么樣呢？她能做什么來破壞這個協(xié)議嗎？她可以把密鑰的副本給Eve。現(xiàn)在Eve可以讀Bob所發(fā)的信息，他還不知道Eve已經把他的話

17、散播了出去。雖然問題很嚴重，但這并不是協(xié)議的問題。在協(xié)議過程的任何一點都不可能阻止Alice把明文的副本交給Eve。當然Bob也可能做Alice所做的事。協(xié)議假定Alice和Bob互相信任。,使用對稱密碼術的通信,總之，對稱密碼算法存在下面的問題： （1）密鑰必須秘密地分配，它們比任何加密的信息更有價值，因為知道了密鑰意味著知道了所有信息。對于遍及世界的加密系統(tǒng)，這可能是令人沮喪的任務，需經常派信使將密鑰傳遞到目的地。 （2）如果密鑰被損害了（被偷竊，猜出來，被逼迫交出來，受賄等等），那么Eve就能用該密鑰去解密所有傳送的信息，也能夠假裝是幾方中的一方，產生虛假信息去愚弄另一方。 （3）假設網

18、絡中每對用戶使用不同的密鑰，那么密鑰總數(shù)隨著用戶數(shù)的增加迅速增多。N個用戶的網絡需要n（n-1）/2個密鑰。例如，10個用戶互相通信需要45個不同的密鑰，100個用戶需要4950個不同的密鑰，這個問題可以通過將用戶數(shù)量控制在較小數(shù)目來減輕，但這并不總是可能的。,單向函數(shù),單向函數(shù)的概念是計算起來相對容易，但求逆卻非常困難。也就是說，已知x，我們很容易計算f（x）。但已知f（x），卻難于計算出x。在這里，“難”定義成：即使世界上所有的計算機都用來計算，從f（x）計算出x也要花費數(shù)百萬年的時間。 打碎盤子就是一個很好的單向函數(shù)的例子。把盤子打碎成數(shù)千片碎片是很容易的事情，然而，要把所有這些碎片再拼成為一個完整的盤子，卻是非常困難的事情。