密鑰管理技術

1、密鑰管理技術第3章 密鑰管理技術 3.1 密鑰的管理內容 3.2 密鑰的分配技術 3.3 公鑰密碼 3.4 RSA算法 3.5 橢圓曲線密碼體制 3.1 密鑰的管理內容 密鑰是加密算法中的可變部分，利用加密手段對大量數據的保護歸結為對密鑰的保護，而不是對算法或硬件的保護。密碼體制可以公開， 密碼設備可能丟失，但密碼機仍可以使用。然而一旦密鑰丟失或出錯，不但合法用戶不能獲取信息，而且可能使非法用戶竊取信息，因此，網絡系統中密鑰的保密和安全管理問題就成為首要的核心問題。 密鑰管理是處理密鑰自產生到最終銷毀整個過程中的有關問題，包括密鑰的設置、生成、分配、驗證、 啟用/停用、 替換、 更新、 保護、

2、 存儲、 備份/恢復、丟失、銷毀等等。密鑰管理方法實質上因所使用的密碼體制（對稱密碼體制和公鑰密碼體制）而異， 所有的這些工作都圍繞一個宗旨，即確保使用中的密碼是安全的。 1. 密鑰設置協議 目前流行的密鑰管理方案中一般采用層次的密鑰設置，目的在于減少單個密鑰的使用周期，增加系統的安全性?？傮w上密鑰分兩大類： 數據加密密鑰(DK)和密鑰加密密鑰(KK)。前者直接對數據進行操作，后者用于保護密鑰，使之通過加密而安全傳遞。 2. 密鑰生成 算法的安全性依賴于密鑰，密鑰的產生首先必須考慮具體密碼系統的公認的限制， 如果用一個弱的密鑰生成方法，那么整個體制是弱的。因為能破譯密鑰生成算法，所以就不需要去

3、破譯加密算法了。減少的密鑰空間，易受到窮舉攻擊。如果采用姓名等的弱密鑰選擇也易受到窮舉的字典攻擊。因此， 好的密鑰應該是隨機密鑰， 但為了便于記憶， 密鑰不能選得過長，不能選完全隨機的數串， 要選自己易記而別人難以猜中的密鑰，要做到這些可采用密鑰揉搓或碾碎技術?？梢娒荑€的生成是困難的，特別對公鑰密碼體制來說，生成密鑰更加困難，因為密鑰必須滿足某些數學特征（必須是素數的，是二次剩余的，等等）。 3. 密鑰的分配 主要研究密碼系統中密鑰的發(fā)送、 驗證等傳送中的問題， 在3.2節(jié)中進一步介紹。 4. 密鑰的保護 密鑰從產生到終結的整個生存期中，都需要加強安全保護。 密鑰決不能以明文的形式出現，所有密

4、鑰的完整性也需要保護， 因為一個攻擊者可能修改或替代密鑰，從而危機機密性服務。 另外， 除了公鑰密碼系統中的公鑰外，所有的密鑰需要保密。 在實際中，存儲密鑰的最安全的方法是將其放在物理上安全的地方。當一個密鑰無法用物理的辦法進行安全保護時，密鑰必須用其它的方法來保護，可通過機密性（例如，用另一個密鑰加密）或完整性服務來保護。在網絡安全中，用最后一種方法可導致密鑰的層次分級保護。 5. 密鑰的存儲 密鑰存儲時必須保證密鑰的機密性、認證性、完整性、防止泄露和修改。 最不復雜的的密鑰存儲問題是單用戶的密鑰存儲，用戶加密文件以備以后用。因為只涉及他一個人，且只有他一人對密鑰負責。一些系統采用簡單方法：

5、密鑰存放在用戶的腦子中， 而決不放在系統中，用戶只需記住密鑰，并在需要對文件加密或解密時輸入。在某些系統中用戶可直接輸入64 bit密鑰，或輸入一個更長的字符串，系統自動通過密鑰碾碎技術從這個字符串生成64 bit密鑰。 其它解決方案有：將密鑰儲存在磁卡、ROM密鑰卡或智能卡中，用戶先將物理標記插入加密箱上或連在計算機終端上的特殊讀入裝置中， 然后把密鑰輸入到系統中。當用戶使用這個密鑰時，他并不知道它，也不能泄露它。使儲存和保護它更加地直觀。把密鑰平分成兩部分，一半存入終端, 一半存入ROM密鑰使得這項技術更加安全。 美國政府的STU-III 保密 就是用的這種方法。丟失了ROM密鑰并不能使加

6、密密鑰受到損害換掉它一切就正常如初。丟失終端密鑰情況也如此。這樣，兩者之一被損害都不能損害整個密鑰。 可采用類似于密鑰加密密鑰的方法對難以記憶的密鑰進行加密保存。例如，一個RSA私鑰可用DES(數據加密標準)密鑰加密后存在磁盤上，要恢復密鑰時，用戶只需把DES密鑰輸入到解密程序中即可。如果密鑰是確定性地產生的（使用密碼上安全的偽隨機序列發(fā)生器），每次需要時從一個容易記住的口令產生出密鑰會更加簡單。 6. 密鑰的備份/恢復 密鑰的備份是非常有意義的，在密鑰主管發(fā)生意外的情況下， 以便恢復加密的信息，否則加密的信息就會永遠地丟失了。 有幾種方法可避免這種事情發(fā)生。最簡單的方法稱密鑰托管方案，它要求

7、所有雇員將自己的密鑰寫下來交給公司的安全官， 由安全官將文件鎖在某個地方的保險柜里（或用主密鑰對它們進行加密）。 當發(fā)生意外情況時， 可向安全官索取密鑰。 一個更好的方法是采用一種秘密共享協議，即將密鑰分成若干片，然后，每個有關的人員各保管一部分，單獨的任何一部分都不是密鑰， 只有將所有的密鑰片搜集全，才能重新把密鑰恢復出來。 7. 密鑰的泄露與撤銷 密鑰的安全是所有的協議、技術、算法安全的基本條件， 如果密鑰丟失、被盜、出現在報紙上或以其它方式泄露，則所有的保密性都失去了，惟一補救的辦法是及時更換新密鑰。 如果對稱密碼體制泄露了密鑰，必須更換密鑰，并希望實際損失最小。如果是一個私鑰，問題就大

8、了，公鑰或許就在所有網絡的服務器上。如果其他人得到了泄露的私鑰，這個人就可以在網絡上冒名頂替，讀加密郵件、對信件簽名、簽合同等等。 私鑰泄露的消息通過網絡迅速蔓延是最致命的。任何公鑰數據庫必須立即聲明一個特定私鑰被泄露，以免懷疑有人用該泄露的密鑰加密消息。 如果用戶知道他的密鑰是何時泄密的，并且KDC（密鑰分配中心）正在管理密鑰，用戶應該通知KDC密鑰已經泄露。 如果沒有KDC， 就要通知所有可能接收到用戶消息的人。 如果用戶不知道他的密鑰泄露的確切時間，問題就復雜了， 用戶要求撕毀合同，因為偷密鑰者可能冒名代替他簽了其它合同， 這將引起爭執(zhí)而由法律、 公證機構裁決。 8. 密鑰的有效期 沒有

9、哪個加密密鑰能無限期使用， 其原因如下： (1) 密鑰使用時間越長，它泄露的機會就越大。人們會寫下密鑰，也會丟失，偶然事件也會發(fā)生的。 (2) 如果密鑰已泄露，那么密鑰使用越久，損失就越大。 如果密鑰僅用于加密一個文件服務器上的單個預算文件，它的丟失僅意味著該文件的丟失。如果密鑰用來加密文件服務器上所有預算信息，那么，損失就大得多。 (3) 密鑰使用越久，人們花費精力破譯它的誘惑力就越大甚至采用窮舉攻擊法。破譯了兩個軍事單位使用一天的共享密鑰， 就會使某人能閱讀當天兩個單位之間的通信信息。破譯所有軍事機構使用一年的共享密鑰，就會使同樣的人獲取和偽造通行全球一年的信息。 (4) 對用同一密鑰加密

10、的多個密文進行密碼分析一般比較容易。 對任何密碼應用，必須有一個密鑰的有效期。不同密鑰應有不同有效期，如 就是把通話時間作為密鑰有效期，當再次通話時就啟用新的密鑰。專用通信信道就不這么明顯了，密鑰應當有相對較短的有效期，這主要依賴數據的價值和給定時間里加密數據的數量。 密鑰加密密鑰無需頻繁更換，因為它們只是偶爾地用作密鑰交換，只是給密鑰破譯者提供了很少的密文分析，且相應的明文也沒有特殊的形式。然而，如果密鑰加密密鑰泄露，那么其潛在損失將是巨大的，因為，所有的通信密鑰都經其加密。在某些應用中，密鑰加密密鑰一般是一月或一年更換一次。 用來加密保存數據文件的加密密鑰不能經常地變換。在人們重新使用文件

11、前，文件可以加密儲藏在磁盤上數月或數年， 每天將它們解密， 再用新的密鑰進行加密， 這無論如何都不能加強其安全性，這只是給破譯者帶來了更多的方便。一種解決方法是每個文件用惟一的密鑰加密，然后再用密鑰加密密鑰把所有密鑰加密，密鑰加密密鑰要么被記憶下來，要么被保存在一個安全地點，或在某個地方的保險柜中。當然，丟失該密鑰意味著丟失了所有的文件加密密鑰。 公開密鑰密碼應用中的私鑰的有效期是根據應用的不同而變化的。用作數字簽名和身份識別的私鑰必須持續(xù)數年（甚至終身）， 用作拋擲硬幣協議的私鑰在協議完成之后就應該立即銷毀。即使期望密鑰的安全性持續(xù)終身，兩年更換一次密鑰也是要考慮的。許多網絡中的私鑰僅使用兩

12、年，此后用戶必須采用新的私鑰。舊密鑰仍需保密，以防用戶需要驗證以前的簽名， 但是新密鑰將用作新文件簽名，以減少密碼分析者所能攻擊的簽名文件數目。 9. 控制密鑰使用 控制密鑰使用是為了保證密鑰按預定的方式使用，在一些應用中控制怎樣使用密鑰是有意義的，有的用戶需要控制密鑰或許僅僅是為了加密，有的或許是為了解密?？梢再x予密鑰的控制信息的有：密鑰的主權人、密鑰合法使用期限、 密鑰識別符、 密鑰預定的用途、密鑰限定的算法、密鑰預定使用的系統、密鑰授權用戶、 在密鑰生成、 注冊、證書有關的實體名字等。 運用這些限制的一個方案是在密鑰后面附加一個控制向量（CV， Control Vector）用它來標定密

13、鑰的使用和限制。對CV取單向Hash運算，然后與主密鑰異或，把得到的結果作為密鑰對密鑰進行加密，再把合成的加密了的密鑰跟CV存在一起?；謴兔荑€時，對CV取Hash運算再與主密鑰異或，最后用結果進行解密。 10. 密鑰的銷毀 如果密鑰必須定期替換，舊密鑰就必須銷毀。 舊密鑰是有價值的，即使不再使用，有了它們，攻擊者就能讀到由它加密的一些舊消息。 密鑰必須安全地銷毀。如果密鑰是寫在紙上的那么必須切碎或燒掉； 如果密鑰存在EEPROM硬件中，密鑰就應進行多次重寫；如果密鑰存在EPROM或PROM硬件中，芯片就應被打碎成小碎片；如果密鑰保存在計算機磁盤里，就應多次重寫覆蓋磁盤存儲的實際位置或將磁盤切碎

14、。 3.2 密鑰的分配技術 3.2.1 密鑰分配實現的基本方法 1 基于對稱加密算法的， 建立安全信道 要使通信的雙方保密通信，他們就需要同一密鑰，這種密鑰可當面分發(fā)或通過可靠信使傳遞，傳統的方法是通過郵政或通信員傳送密鑰。這種方法的安全性取決于信使的忠誠和素質， 該方法成本高，適用于高安全級密鑰。為了既安全又減少費用， 可采用分層方式傳送，通信員僅傳送密鑰加密密鑰，而不去傳送大量的數據加密密鑰，這既減少了通信員的工作量，又克服了用一個密鑰加密過多數據的問題。 對密鑰分發(fā)問題的另一個方法是將密鑰分成許多不同的部分， 然后用不同的并行信道發(fā)送出去，有的通過 ，有的通過郵寄等等。即使截獲者能收集到

15、密鑰，但缺少某一部分，他仍然不知道密鑰是什么，所以該方法一般用于除個別特殊情況外的任何場合。 對稱加密體制中對密鑰分配還可以采用多級層次結構來實現， 即將密鑰分成兩類：初始密鑰和密鑰加密密鑰。初始密鑰用于保護數據， 密鑰加密密鑰用于保護初始密鑰。初始密鑰有時也被稱做會話密鑰，密鑰加密密鑰有時也被稱做主密鑰。用主密鑰對會話密鑰加密以后，可通過公用網傳送，或用雙鑰密鑰體制分配來實現，如果采用的加密系統足夠安全，則可將其看成是一種安全通道。如ANSI X9.17標準中規(guī)定了該種密鑰的分配方法。 2基于雙鑰體制的，利用數學上求逆的困難性，建立安全信道 Newman等在1986年提出的SEEK(Secu

16、re Electronic Exchange of Keys)密鑰分配體制系統，采用的是Diffie-Hellman和Hellman-Pohlig密碼體制，這一方法已被用于美國Cylink公司的密碼產品中，在小型網絡中，每對用戶可以很好地使用密鑰加密密鑰。 如果網絡變大，每對用戶必須交換密鑰，n個人的網絡總的交換次數為n（n-1）/2。1000人網絡則需近500 000次，在這種情況下， 建造一個密鑰管理中心進行密鑰分配，會使操作更加有效。 3 基于量子密碼建立安全信道 密碼學的信息理論研究指出，通信雙方A到B可通過先期精選、信息協調、保密增強等密碼技術使A和B共享一定的密碼信息。 3.2.2

17、 密鑰分配實現的基本工具 認證技術和協議技術是分配密鑰的基本工具，認證技術是安全分配密鑰的保障，協議技術是實現認證必須遵守的流程。 3.2.3 密鑰分配系統實現的基本模式 密鑰分配系統實現的基本模式有兩種,一種是對小型網絡， 由于用戶人數較少，每對用戶之間可采用共享一個密鑰的方法， 如圖3.1所示。 圖中k表示A和B之間共享的密鑰。 圖 3.1 另一種是在一個大型網絡中，如由n個用戶組成的系統中，希望相互之間保密通信，則需要生成n(n-1)/2 個密鑰進行分配和存儲， 這樣密鑰的分配問題就變得復雜，因此為了解決這一問題， 常采用密鑰中心管理方式。在這種結構中，每個用戶和密鑰中心共享一個密鑰，保

18、密通信的雙方之間無共享密鑰。 密鑰中心機構有兩種形式：密鑰分配中心(KDC)和密鑰傳送中心(KTC)。在KDC中，當A向KDC請求發(fā)放與B通信用的密鑰時，KDC生成一個密鑰k傳給A, 并通過A傳給B，如圖3.2(a)所示。 或者利用A和B與KDC共享密鑰，由KDC直接傳送給B，如圖3.2(b)所示。 圖 3.2 密鑰傳送中心(KTC)和密鑰分配中心(KDC)十分相似，主要區(qū)別在于由通信方的一方產生需求的密鑰，而不是由中心來產生。當A希望和B通信時，它產生密鑰k并將密鑰發(fā)送給KTC， KTC再通過A轉送給B，如圖3.3(a)所示，或直接送給B，如圖3.3(b)所示。 利用A與B和KTC的共享密鑰

19、來實現。 圖 3.33.2.4 密鑰的驗證 在密鑰分配過程中，需要對密鑰進行驗證，以確保準確無誤地傳送給指定的用戶，防止偽裝信使用假密鑰套取信息，并防止密鑰分配中的錯誤。當你收到密鑰時，如何知道這是對方傳送的而不是其他人傳送的呢？如果是對方親自遞給你的，那自然簡單；如果通過可靠的信使傳送密鑰，必須相信信使，并需要對密鑰進行確認， 例如采用指紋法。而讓信使傳送加密密鑰可能更安全。如果密鑰由密鑰加密，必須相信只有對方才擁有那個加密密鑰；如果運用數字簽名協議來給密鑰簽名，那么當驗證簽名時就必須相信公開密鑰數據庫；如果某個密鑰分配中心（KDC）在對方的公鑰上簽名， 則必須相信KDC的公開密鑰副本不曾被

20、篡改過。這些都需要對公開密鑰認證。 如果被篡改，任何一個人都可以傳送一個加密和簽名的消息而將它偽裝成來自對方，當你訪問公開密鑰數據庫以驗證對方的簽名時， 卻認為是正確的。利用該缺陷的一些人聲稱公鑰密碼體制是無用的，公鑰體制對提高安全性一點用處也沒有， 但實際情況卻復雜得多。采用數字簽名和可信賴KDC的公鑰體制， 使得一個密鑰代替另一個密鑰變得非常困難。你可以通過 核實對方的密鑰，那樣他可以聽到你的聲音。聲音辨別是一個真正的好的鑒別方案。如果是一個秘密密鑰，他就用一個單向Hash函數來核實密鑰，AT&T、TSD就是用這種方法對密鑰進行驗證的。 有時，核實一個公開密鑰到底屬于誰并不重要，核實它是否

21、屬于去年的同一個人或許是有必要的。如果某人送了一個簽名提款的信息到銀行，銀行并不關心到底誰來提款，它僅關心是否與第一次來存款的人屬同一個人。 3.3 公鑰密碼 公開密鑰密碼體制是現代密碼學的最重要的發(fā)明和進展。 一般理解密碼學(Cryptography)就是保護信息傳遞的機密性，但這僅僅是當今密碼學主題的一個方面。對信息發(fā)送與接收人的真實身份的驗證、對所發(fā)出/接收信息在事后的不可抵賴以及保障數據的完整性是現代密碼學主題的另一方面。公開密鑰密碼體制對這兩方面的問題都給出了出色的解答，并正在繼續(xù)產生許多新的思想和方案。在公鑰體制中，加密密鑰不同于解密密鑰，人們將加密密鑰公諸于眾，誰都可以使用；而解

22、密密鑰只有解密人自己知道。 迄今為止的所有公鑰密碼體制中，RSA系統是最著名、使用最廣泛的一種。 1976年提出公共密鑰密碼體制，其原理是加密密鑰和解密密鑰分離，這樣，一個具體用戶就可以將自己設計的加密密鑰和算法公諸于眾， 而只保密解密密鑰。任何人利用這個加密密鑰和算法向該用戶發(fā)送的加密信息，該用戶均可以將之還原。 公共密鑰密碼的優(yōu)點是不需要經安全渠道傳遞密鑰，大大簡化了密鑰管理。 它的算法有時也稱為公開密鑰算法或簡稱為公鑰算法。 3.3.1 公鑰密碼體制的基本概念 1. 密鑰對 在基于公鑰體系的安全系統中，密鑰是成對生成的，每對密鑰由一個公鑰和一個私鑰組成。在實際應用中，私鑰由擁有者自己保存

23、， 而公鑰則需要公布于眾。為了使基于公鑰體系的業(yè)務（如電子商務等）能夠廣泛應用，一個基礎性關鍵的問題就是公鑰的分發(fā)與管理。公鑰本身并沒有什么標記，僅從公鑰本身不能判別公鑰的主人是誰。在很小的范圍內，比如A和B這樣的兩人小集體，他們之間相互信任，交換公鑰，在互聯網上通信，沒有什么問題。這個集體再稍大一點，也許彼此信任也不成問題， 但從法律角度講這種信任也是有問題的，如再大一點， 信任問題就成了一個大問題。 2. 證書 互聯網絡的用戶群決不是幾個人互相信任的小集體，在這個用戶群中，從法律角度講用戶彼此之間都不能輕易信任。所以公鑰加密體系采取了另一個辦法，將公鑰和公鑰的主人名字聯系在一起，再請一個大

24、家都信得過有信譽的公正、權威機構確認，并加上這個權威機構的簽名，這就形成了證書。由于證書上有權威機構的簽字，因此大家都認為證書上的內容是可信任的；又由于證書上有主人的名字等身份信息， 別人就很容易地知道公鑰的主人是誰。 3. 電子簽證機關 前面提及的權威機構就是電子簽證機關（即CA）。CA也擁有一個證書（內含公鑰），當然，它也有自己的私鑰，所以它有簽字的能力。 網上的公眾用戶通過驗證CA的簽字從而信任CA，任何人都可以得到CA的證書（含公鑰），用以驗證它所簽發(fā)的證書。如果用戶想得到一份屬于自己的證書，他應先向CA提出申請, 在CA判明申請者的身份后，便為他分配一個公鑰， 并且CA將該公鑰與申請

25、者的身份信息綁在一起，并為之簽字后， 便形成證書發(fā)給那個用戶（申請者）。 如果一個用戶想鑒別另一個證書的真?zhèn)?，他就用CA的公鑰對那個證書上的簽字進行驗證（如前所述， CA簽字實際上是經過CA私鑰加密的信息，簽字驗證的過程還伴隨使用CA公鑰解密的過程），一旦驗證通過，該證書就被認為是有效的。CA除了簽發(fā)證書之外，它的另一個重要作用是證書和密鑰的管理。 由此可見， 證書就是用戶在網上的電子個人身份證， 同日常生活中使用的個人身份證作用一樣。 CA相當于網上公安局，專門發(fā)放、驗證身份證。 3.3.2 公鑰密碼體制的原理 單向函數 定義3-1可逆函數 令f是集A到集B的一個映射，如果對任意的x1x2，

26、x1, x2A，有y1y2, y1, y2B，則稱f是從A到B的單射， 或一對一映射，或可逆的函數，記為y=f(x)。 定義3-2單向函數 一個可逆函數y=f(x), 如果滿足以下兩條就稱為一個單向函數: 對于給定所有xA，能方便地計算出f(x); 對于給定的所有y，求x是困難的，以致于實際是做不到的。 例3.1 有限域GF(p)中的指數函數f(x)=bx，其中p是素數，即y=f(x)=bx, xGF(p)也就是x為滿足0 xp-1的整數。其逆運算是求離散對數，即x=logbN 給定x求y是容易的，即是當p足夠大時，如b=2, p=2100需做100次乘法，利用高速計算機可在0.1ms內完成。

27、但是從x=logbN中要計算x是非常困難的，如b=2, p=2100，所需計算量為1600年， 可見，當p很大時，有限域GF(p)中的指數函數f(x)=bx是一個單向函數。 用于構造公約密碼常用的單向函數 ） 多項式求根 有限域GF(p)上的一個多項式y=f(x)=(xn+an-1xn-1+a1x+a0) mod p當給定多項式中的系數a和x, p以后，利用Honer算法，最多進行n次乘法，n-1次加法，就可求出y值。但已知多項式的系數a和y, p以后，要求x，就需要對高次方程求根，至少要進行不少于n2（lbp)2的整數次乘法, 當n, p很大時很難求解。 ） 離散對數 如果p是一足夠大的素數

28、，a是0, 1, 2, , p-1中與p互素的數。 則已知p, a, x, 計算y=f(x)-ax mod p并不困難; 若已知p, a, y, 計算x=logby mod p(稱為離散對數問題)，就很困難了。如p=512, 則計算乘法次數為1077。 ） 大整數分解(Factorrization Problme) 若已知兩個大素數p, q，求n=pq僅需一次乘法，但已知n求p, q則是幾千年來數論專家的一道難題。已知的各種算法有： 試除法、二次篩、數域篩、橢圓曲線, 其中RSA問題是FAC問題的特例。n是兩個素數p, q之積，給定n以后求p, q的問題稱為RSA問題。求n=pq分解問題有以下

29、幾種形式： (1) 分解整數n為p, q; (2) 給定整數M, C，求d使得CdM mod n; (3) 給定整數k, C，求M使得MkC mod n; (4) 給定整數x, C，決定是否存在y使得xy2 mod m（二次剩余問題）。 ） 菲-赫爾曼(Diffie-Hellman）問題 給定素數p，可構造一乘群Z*p，令為Z*p的生成元，若已知a, b，求ab問題為菲-赫爾曼問題。 ） 二次剩余問題 給定一個奇合數n和整數a，決定是a否為mod n平方剩余問題就稱為二次剩余問題。 公鑰密碼體制的原理 若用戶A有一加密密鑰ka, 有一解密密鑰ka，可將加密密鑰ka公開，而解密密鑰ka保密，若B

30、要向A傳送明文m，可查A的加密密鑰ka，若用A的加密密鑰ka加密的密文 則A收到密文c以后，用只有自己才知道的解密密鑰ka對c進行解密得 由于加密密鑰ka不同于解密密鑰ka，因此公鑰密碼體制也稱為非對稱密碼體制。若任何第三者竊得密文，但由于無解密密鑰ka ，便無法恢復明文。 其加、解密碼模型如圖3.4(a)所示。 公鑰密碼體制的另一種模型是認證模型， 用于數據起源的認證， 以確保信息的完整性。在這種情況下，任何人都可以獲得解密密鑰，解讀信息，但只有具有相應加密密鑰的人才能產生該信息，其模型如圖3.4(b)所示。 圖 3.4 (a) 加解密模型； (b) 認證模型 3.4 RSA 算 法 公開密

31、鑰算法是在1976年由當時在美國斯坦福大學的迪菲（Diffie）和赫爾曼(Hellman)兩人首先發(fā)明的。但目前最流行的RSA是1977年由MIT Ronald L.Rivest,Adi Shamir和Leonard M.Adleman三名數學家共同開發(fā)的, RSA分別取自三名數學家的名字的第一個字母。 RSA的基礎是數論的歐拉定理， 它完全依賴于大數的因子分解的困難性。 歐拉定理 若整數a和m互素，則 a(m)1 mod m 其中, (m)是比m小，且與m互素的正整數個數。 3.4.1 RSA算法描述 1. RSA密鑰的產生 (1) 選擇兩個大素數p#, q（保密）。 (2) 計算n=pq(

32、p, q分別為兩個互異的大素數，n的長度大于512 bit，這主要是因為RSA算法的安全性依賴于因子分解大數問題)。 歐拉函數(n)=(p-1)(q-1) (3) 隨機選擇加密密鑰e，要求e和(n)互質。 (4) 利用Euclid算法計算解密密鑰d, 滿足de1 mod(n)。 其中n和d也要互素。數e和n是公鑰，d是私鑰。兩個素數p, q不再需要，應該丟棄，不要讓任何人知道。 2. 加密 (1) 加密信息m（二進制表示）時， 首先把m分成等長數據塊m1、m2、mi塊長s，其中2sn，s要盡可能的大。 (2) 對應的密文是： cimei mod n。 3. 解密解密時計算： 例3.2 p=43

33、, q=59, n=pq=4359=2539(n)=4258=2436, e=13 解方程de=1 mod 2436 2436=13187+5 13=52+35=3+23=2+11=3-2， 2=5-3， 3=13-255=2436-131871=3-2=3-(5-3)=23-5 =2(13-25)-5 =213-55 =213-5(2436-13187) =93713-52436 即 937131 mod 2436取 e=13, d=937 若取明文public key encryptions，先將明文按兩個一組進行分塊，再將明文數字化，如按英文字母表的順序得： pu=1520, bl=01

34、11, ic=0802, ke=1004, ye=2404, nc=1302, ry=1724, pt=1519, io=0814, ns=1418。 利用加密得到密文：pu=0095, bl=1648, ic=1410, ke=1299, ye=1365, nc=1379, ry=2333, pt=2332, io=1751, ns=1289。 3.4.2 RSA算法中的計算問題 RSA算法中首先遇到的問題就是如何選取大的素數， 數百年來，人們對素數的研究一直感興趣，那么，是否有一個簡單的公式可以產生素數？答案是否定的。 有人曾猜想若n|2n-2，則n為素數。n=3,3|23-2，n341時

35、是正確的，但n=341時，猜想是錯誤的。 有人曾猜想若p為素數，則Mp=2p-1為素數, 但M11, M67, M257不是素數, 猜想錯誤。如果p為素數，Mp也為素數，則稱Mp為Mersenne數。Fermat推測Fn=22n+1為素數, n為正整數, 但n=5時是錯誤的。 人們感興趣的另一個問題是素數的個數到底有多少？答案是有無窮多。素數在數軸上的分布情況是 ,如x=10, (x)=4, 該式所含的素數為2、3、5、7。 64 bit大的素數中有素數的個數為2.051017; 128bit大的素數中有素數的個數為1.91036; 256 bit大的素數中有素數的個數為3.251074。 可見素數的個數相當多。到底如何產生一個