山大信息安全課件第3章 公鑰分發(fā)技術

1、 第3章 公鑰分發(fā)技術. 公鑰分配技術 涉及公鑰密碼技術的協(xié)議通常在描述的時候通常假定恰當部分的可信的公鑰已經(jīng)獲得。這樣便允許在一般情況下以各種不同的方式獲取這些秘鑰。分配公鑰過程具有保證機制或可驗證公鑰完整性的方案主要包括以下的幾種：點到點的通過可靠信道傳輸 通過相關用戶之間的個人交流或直接的信道 獲取其他相關用戶的公共秘鑰，并由秘鑰來源方保證其真實性與完整性。這種方法在操作不太頻繁（如用戶的注冊），或小型的封閉系統(tǒng)中較為實用。 另一種相關的方法是通過一非可靠的信道傳輸公鑰及相關信息。 并通過連接一個獨立的，低帶寬的可靠通道獲得其哈希值，由哈希值對這些消息進行認證。這種方法的缺點主要有：使用

2、的不方便；在未保證通信安全的情況下便非自動的對新的用戶提出其公共秘鑰申請；可靠信道的花費。2.直接連接到一個可靠的公共文件(公鑰記錄表) 首先建立一個保證完整性的公共數(shù)據(jù)庫，將每個系統(tǒng)用戶的名字與公鑰保存在其中。該公鑰登記工作由一可信的用戶完成。用戶直接由記錄獲得秘鑰。在被動攻擊下通過非安全信道遠程訪問記錄是可行的。但當存在主動攻擊者時遠程訪問需要有安全的通道。3. 使用可靠的在線服務器。 由一個可靠的在線服務器起到上面公共文件的作用來保管秘鑰，響應（單個地）請求后發(fā)送簽名后的公鑰。這種方法的保密性是不需要特別保證的。發(fā)送請求的用戶保存有服務器的簽名副本?？梢砸灾畬鬏?shù)目煽啃赃M行驗證。這個方

3、案的缺點在于：服務器必須始終在線；服務器有可能成為瓶頸；通信連接必須同時由該可靠的服務器與計劃中的通信方兩方共同確定。4. 使用離線服務器和證書。 用戶A 聯(lián)系一個離線的可靠用戶作為認證中心 certification authority (CA), 用來記錄他的公鑰并獲取CA的簽名驗證公鑰（允許驗證其它用戶的證書）。CA 通過將A的公鑰捆綁在一信息串上驗證A，從而創(chuàng)建證書，用戶們通過交換證書或由公共目錄提取獲得真正的公鑰。5. 使用系統(tǒng)本身公共參數(shù)隱式的可靠性保證。 其中包含基于身份的系統(tǒng)以及包含隱式驗證的系統(tǒng)，通過算法設計,更改公共向量將導致可發(fā)現(xiàn)的結果，即在密碼技術無折衷的失敗產(chǎn)生。下面

4、分類具體論述：基于身份的系統(tǒng)（ID-based systems） 基于身份的系統(tǒng)與通常的公鑰密碼系統(tǒng)相類似，涉及一個私人的傳輸與一個公共的傳輸，但使用者并不象前面擁有隱藏的公鑰，而是由用戶公開可用的身份識別信息代替。用戶的任意公開的可用的信息只要能夠唯一的非否認確認該用戶的均可作為標識信息。定義 基于身份的密碼系統(tǒng)是一個非對稱的系統(tǒng)。其中實體的標識信息起到了公鑰的作用。由可信中心T將之作為輸入信息由其計算實體的私鑰。 當完成計算后，T通過一個安全的信道將實體的私鑰傳送給該實體。該秘鑰并不完全由實體的標識信息計算，但其中必須包含一些僅為T所知的特權信息（T的秘鑰）。這樣對于防止偽造是必需的，其實

5、質是只有T可由給出的標識信息計算出可用的私鑰。而相應的公共的可用的系統(tǒng)數(shù)據(jù)必須同時包含在加密傳輸中，類似于在基于證書的系統(tǒng)中認證權威的公鑰。有時候，除了優(yōu)先權IDA附加的系統(tǒng)定義的數(shù)據(jù)DA也要與用戶A相聯(lián)系。這樣的系統(tǒng)已不再是“純粹的”基于身份識別的了。同樣，也不是單純的DA 或IDA 驗證了。隱式驗證的公鑰系統(tǒng) （Implicitly-certified public keys） 另一種變異的公鑰系統(tǒng)的是利用隱式驗證公鑰的非對稱系統(tǒng)，這里外在于用戶的公鑰是存在的。外在于用戶的公鑰是存在的，但公鑰必須重建（依原樣的）而不是象基于每個基于驗證的系統(tǒng)通過公鑰證書傳遞。帶有隱式驗證公鑰的系統(tǒng)可以這樣

6、設計：1.實體的公鑰可由公共數(shù)據(jù)重建（被其他用戶） ( 這基本取代了證書的作用)。 2. 用來重建公鑰的公共數(shù)據(jù)有： (a) 與可靠用戶相關的公共數(shù)據(jù)。 (b) 使用實體的標識。 (c) 每個用戶的公共附加數(shù)據(jù)3.公鑰重建的完整性是不能直接驗證的。 但一個“正確的”公鑰只能從公鑰的原作者處的公共數(shù)據(jù)重新獲得。對于重建公鑰的檢驗，系統(tǒng)設計中必須滿足：1. 變更一個用戶的標識或變更公共數(shù)據(jù)將導致重 獲的秘鑰不被服務器接受，但不會導致加密數(shù)據(jù) 的爆光 。 2. 對手由任意的用戶的公鑰均無法計算一用戶對 應于公鑰的私鑰或構建用戶身份的匹配信息。對應于某一私鑰的公共數(shù)據(jù)是可計算的。重建公鑰就是通過這樣構

7、造進行隱式驗證的。隱式公鑰認證的分類 基于身份的公鑰(第一類). 每一個實體A的私鑰由可信的用戶T基于A的身份信息和T的私鑰計算。這同時是A用戶特有的并經(jīng)過T校正的重建用公共數(shù)據(jù)中的一個函數(shù)。A的私鑰由T安全的傳送給A。2. 自我驗證的公鑰(第二類)。 每一個實體A自己計算它的私鑰和相應的公鑰。A的用于重建的公共數(shù)據(jù)，A的身份信息和T的私鑰由T計算。由于第三方具有通向用戶私鑰的入口，第一類方法需要對第三方有更多的信任。作為與第二種情況的不同，后者根據(jù)秘鑰受實體本身的限制強調了“自我驗證”中的“自我”。公鑰分配技術的對比 圖13.7中對非對稱簽名系統(tǒng)的分類做了說明，對比公鑰密碼系統(tǒng)（具有顯式的公

8、鑰），基于身份的系統(tǒng)（公鑰是用戶身份信息）與隱式公鑰認證系統(tǒng)（顯式的公鑰由用戶的公共數(shù)據(jù)重建）.主要的不同有： 基于證書的公鑰系統(tǒng)具有顯式的公鑰，基于身份的系統(tǒng)則沒有；在隱式系統(tǒng)中系統(tǒng)中的明確公鑰由重建得到。公鑰系統(tǒng)中的顯式公鑰(圖 13.7(a)被替代為（a）基于身份驗證的系統(tǒng)(圖13.7(b)中的三元組 其中 是A的身份信息串， 是附加的公共數(shù)據(jù)（由T定義并與 的和A的私鑰相關。 由可靠權威T 的可靠公鑰(或系統(tǒng)參數(shù))構成。 (b) 隱式公鑰系統(tǒng)(圖13.7(c)中的三元組。這時，顯式的公鑰 由這些信息重建。用于重建的公共數(shù)據(jù) 在這里起到了圖13.7(b)中 的作用。2. 在基于證書的系統(tǒng)

9、中公鑰的真實性可以(切必須能)被明確的驗證,但在基于身份的系統(tǒng)和隱式驗證的系統(tǒng)中則不然(也不必)。3. 在基于證書的公鑰系統(tǒng)與隱式驗證系統(tǒng)中的自我公鑰驗證中，可心中心不需知道用戶的私鑰。而在基于身份的系統(tǒng)和隱式驗證系統(tǒng)中的基于身份驗證中需要知道。4. 與基于身份的系統(tǒng)類似，隱式驗證系統(tǒng)的公鑰依賴于實體的身份信息，感覺上也是“基于身份的”。然而，基于身份的系統(tǒng)避免了顯式完整的公鑰，而隱式驗證的系統(tǒng)并不限制使用者計算出公鑰。5. 對比隱式公鑰認證中的兩類，可見其在用于重建的公共數(shù)據(jù)和私鑰的關系上有所不同。(a) 第一類:一個用戶的私鑰作為一個用于重建的公共數(shù)據(jù)的函數(shù)。該公鑰由可心中心計算。(b)

10、第二類:用于重建的公共數(shù)據(jù)是由用戶的公鑰計算的函數(shù)，相應的私鑰由用戶自己產(chǎn)生。.6. 在所有三種方案中。均在某些時段上使用了在某種程度上可靠的第三方用來建立連接。在完全未曾蒙面或除了系統(tǒng)參數(shù)毫無共享的用戶之間傳遞信任。2.秘鑰使用的控制技術秘鑰分離與秘鑰強制使用 密碼技術中的秘鑰信息應同時包括秘鑰的限定屬性和其它操作上的使用信息。包括例如秘鑰擁有者，有效期，預定的使用，秘鑰鑒定者等信息。秘鑰的分離與不當使用的威脅 在一個簡單的秘鑰管理系統(tǒng)中，秘鑰相關信息例如被授權的應用被通過上下文推斷出。為了達到附加的澄清與控制功能，特別顯式指定的授權使用信息可伴隨秘鑰分配與認證，在使用其間，嘗試的使用是得到

11、授權的。如果控制信息是受到操縱的，就將它以一種保證真實性與完整行的方法將其與秘鑰捆綁在一起。 秘鑰的分離原則是指不同用途的秘鑰應當分離。秘鑰的誤用的威脅可通過技術手段來解決，保證秘鑰只被用于在秘鑰生成時便授權的使用范圍內。秘鑰使用上的限制可由程序上的技術,物理保護，或下面討論的密碼技術進行。對稱秘鑰使用的控制技術 下面主要討論的是控制向量的使用，為了講清其發(fā)展過程，秘鑰標記，秘鑰變碼與秘鑰公證也將被提到。(i) 秘鑰標記和秘鑰變碼 秘鑰標記Key tag提供了一種簡單的方法用來制定秘鑰允許的使用。一個秘鑰標記是一個位向量或一個伴隨著秘鑰于其整個生存期的構造的域。秘鑰標記通過加密與秘鑰捆綁在一起

12、，僅當該秘鑰解密時才以明文形式出現(xiàn). 一個早期的分離秘鑰的方法是通過非安全的參數(shù)與函數(shù)由一個單獨的基本秘鑰base key取得秘鑰結果秘鑰被稱為秘鑰變碼 key variants或源秘鑰 derived keys。在這里，一種令秘鑰不同的方法是秘鑰偏移 key offsetting，依靠一個秘鑰加密秘鑰K，K的值每次使用時都會基于一個計數(shù)器變更，該計數(shù)器每次使用完后都會增加。這將防止加密秘鑰的重復。變更的秘鑰 被用于加密其他秘鑰。接受者同樣變更K去加密會話秘鑰 . (ii)公證 秘鑰公證是一種預防秘鑰被替換的技術，主要通過請求與秘鑰相關的用戶的身份的明確說明實現(xiàn)。秘鑰的驗證通過利用這些身份改變

13、一個秘鑰加密秘鑰進行驗證。其中真實身份一定要詳細說明來恰當?shù)幕謴捅槐Ｗo的秘鑰。該秘鑰被稱為將要利用這些身份處理的。在所有的秘鑰協(xié)議中，都需要阻止秘鑰被替換。公證需要合適的控制信息來恢復秘鑰，并提供對隱式驗證的公鑰提供類似的保護?；镜募夹g(簡單的公鑰公證) 包含一個可信的服務器，或一個分享該秘鑰的用戶,使用一個秘鑰加密秘鑰K加密會話秘鑰S。令源用戶為 i 接收的用戶為 j,則可表示為。這里假定 i與j為系統(tǒng)中實體的唯一標識。用戶要想恢復S便必須共享K并明確地以正確地次序了解i與j，否則將恢復隨機秘鑰。這里假定第三方準確的鑒定用戶的身份，并提供一個僅能由這些用戶恢復的會話秘鑰。(iii) 控制向

14、量 相對于秘鑰公證可以被看作是一個秘鑰鑒定的機制，控制向量利用將秘鑰標記與簡單的秘鑰公證機制相結合的方法提供了一個控制秘鑰使用的方法。與每個秘鑰相聯(lián)系的秘鑰S 是一個控制向量C，其中包含一個數(shù)據(jù)域定義了對這個秘鑰的使用授權。類似于秘鑰標記，該數(shù)據(jù)域在一秘鑰加密秘鑰加密（ ）之前便和S捆扎在了一起。 像正確地秘鑰解密秘鑰一樣，秘鑰解密也需要恰當?shù)闹付刂葡蛄俊Ｈ艚Y合值不正確，則一個偽造的秘鑰的恢復對于對手是無用的。在秘鑰S一生成便將控制向量C通過加密與之捆綁起來。阻止非授權的對C的操作,假定只有獲得授權的用戶具有秘鑰加密秘鑰K的入口。 通過利用一個或幾個C的域將公證封裝進C，已知用來說明身份。

15、與存取控制的標準模式相比，一個控制向量可能被用來說明某人的身份 ( )和特權( ) 關于某秘鑰的使用信息( )。. 當用于一個具體的密碼的操作時，控制向量像被保護的秘鑰一樣輸入。然后檢驗請求操作是否依照控制向量執(zhí)行，如果是這樣，則用控制向量解密秘鑰。若控制向量與被保護的秘鑰上捆綁的信息不匹配（或K不正確），則恢復的秘鑰 是假的。這里的安全性依靠假設檢驗與使用是分離的，且在可靠子系統(tǒng)中完成。 若控制信息C與秘鑰K相差很小，可以在配對之前先使用一抗碰撞哈希函數(shù)。這樣便允許控制信息的長度任意，這樣我們可以用一個128位的秘鑰K和一個輸出為128位的哈希函數(shù)加密S。 。三公鑰密碼系統(tǒng) 公鑰密碼的觀點是

16、由Diffie和Hellman于1976年在 們的論文“密碼學的新方向”一文中首次提出的。他們指 明了實現(xiàn)在某些已知的數(shù)學難解問題上建立密碼的具體 途徑。 隨后Rivest, Shamir和Adleman于1977年提出第一個比較完善的RSA公鑰密碼系統(tǒng)。RSA既可以用于保 密也可以用于簽名。公鑰密碼系統(tǒng)是計算復雜性理論發(fā) 展的必然產(chǎn)物。私鑰（對稱）密碼系統(tǒng)的缺陷之一是通 信雙方在進行保密通信之前需要通過安全通道傳送密這點在實際中是非常困難的。而公鑰密碼系統(tǒng)可使通信雙 方無須事先傳送密鑰就可以建立保密通信。公鑰密碼系 統(tǒng)的出現(xiàn)為解決私鑰密碼系統(tǒng)的密鑰分配問題開辟了一 條寬廣的道路。在公鑰密碼系

17、統(tǒng)中每個實體都有自己的公鑰和相應的私鑰。在安全系統(tǒng)中已知公鑰推算出私鑰在計算上是困難的。公鑰密碼系統(tǒng)的加密變換和解密變換分別用和表示。任何實體B要向實體A發(fā)送信息m的步驟如下:實體B首先獲得實體A的真實公鑰 的拷貝(Authentic Copy) 實體B計算密文 并發(fā)送給實體A。實體A使用自己的私鑰，計算 解密密文恢復明文。這里公鑰不需要保密，但要保證它的真實性，即 確實是實體A掌握的私鑰所對應的公鑰?！疤峁┱鎸嵉墓€”比“安全地分配密鑰”實現(xiàn)起來要容易得多。這是公鑰密碼系統(tǒng)的主要優(yōu)點。公鑰密碼系統(tǒng)的主要目的是提供保密性，它不能提供數(shù)據(jù)源認證(Data Origin Authenticatio

18、n)和數(shù)據(jù)完整性 (Data Integrity)。數(shù)據(jù)源認證是指：指定的數(shù)據(jù)是在以前的某個時間確實是由真正的源創(chuàng)建的。數(shù)據(jù)完整性是指：真正的源創(chuàng)建該數(shù)據(jù)后經(jīng)過傳輸或儲存沒有發(fā)生改變。數(shù)據(jù)源認證和數(shù)據(jù)完整性要由其它技術來提供（如：消息認證碼、數(shù)字簽名）從本質上來看，公鑰密碼比私鑰密碼（如：DES、IDEA、RC5等）加密的速度要慢。通常公鑰密碼用在:傳送密鑰。以后用該密鑰作為私鑰密碼系統(tǒng)的密鑰來加密大量數(shù)據(jù) 在數(shù)據(jù)完整性和認證中使用 加密少量數(shù)據(jù) 公鑰解密也可以提供認證保證（如：在實體認證協(xié)議、帶認證的密鑰協(xié)建立協(xié)議等）。公鑰加密中必須有辦法讓發(fā)送消息的人得到想要發(fā)送到的那個人的公鑰的真實拷貝

19、。否則的話就會受到偽裝攻擊。在實踐中有很多方法分發(fā)真實的公鑰，如：使用可信的公共文件、使用在線可信服務器、使用離線服務器和認證。建立在不同計算問題之上的其它幾個公鑰密碼系統(tǒng)是Merkle-Hellman Knapsack (1978) 本系統(tǒng)及相關系統(tǒng)基于“子集和”問題的困難性。然而已證明除Chor-Rivest系統(tǒng)外各種knapsack系統(tǒng)都是不安全的McEliece (1978) McEliece密碼系統(tǒng)基于代數(shù)編碼系統(tǒng)。ElGamal (1985) 它基于有限域中離散對數(shù)問題的困難性橢圓曲線 橢圓曲線密碼系統(tǒng)是用橢圓曲線上運算代替有限域上運算來實現(xiàn)已有的公鑰密碼系統(tǒng)。它的特點是運行速度快

20、、密鑰長度短 從抽象的觀點來看，公鑰密碼系統(tǒng)是一種單向陷門函數(shù)。我們說一個函數(shù)是單向函數(shù)(One Way Function)是指：對它的定義域中的任意元素都容易計算其函數(shù)值，反過來對值域中幾乎所有元素確定它的原象都是不可行的。如果掌握某些輔助信息就容易由值域元素確定它的原象，那么這種單向函數(shù)叫單向陷門函(Trapdoor One Way Function)。這里輔助信息就是陷門。例如：p和q是兩個大素數(shù)，n=p.q，e是正整數(shù)， 是單向陷門函數(shù)，其陷門是 。 3.1 RSA系統(tǒng)和素因子分解3.1.1 RSA密碼系統(tǒng)簡介3.1.2 RSA密碼系統(tǒng)描述3.1.3 RSA實現(xiàn)3.1.4 RSA在實現(xiàn)

21、時要注意的問題3.1.6 有關算法3.1.7 因子分解3.1.1 RSA密碼系統(tǒng)簡介RSA是使用最廣泛的公鑰密碼系統(tǒng)。它可以用在保密性和數(shù)字簽名。1976年Diffie & Hellman提出公鑰密碼系統(tǒng)的思想1977年由Rivest, Shamir, Adleman 首次實現(xiàn)了著名的RSA密碼系統(tǒng)，它的安全基于大整數(shù)素因子分解的困難性上。3.1.2 RSA密碼系統(tǒng)描述每個實體有自己的公鑰(n,e)及私鑰p,q,d，其中n=p.q是兩個大素數(shù)之積, 。 實體B加密消息,將密文在公開信道上傳送給實體A。 實體A接到密文后對其解密。加密算法實體B做如下動作 1.得到實體A的真實公鑰(n,e) 2.

22、把消息表示成整數(shù)m,0mn-1 3.使用平方乘積算法，計算 4.將密文發(fā)送給實體A解密算法 實體A接受到密文C，使用私鑰d計算 ,證明：對任何 有 這里要證明 首先證明 對 ,顯然有 當 時,由Fermat定理知 同理推出 最后得到3.1.3 RSA實現(xiàn)1密鑰生成 每個實體A建立他的RSA公鑰和相應的私鑰 a.生成兩個大的隨機素數(shù)p和q，并且 位長大體相同 b.計算n=p.q， c.選擇隨機數(shù)e, , （推出是奇數(shù)） d.求 ，即用擴展的Euclidean算法求 的解d（推出也是奇數(shù)） e.公布實體A的公鑰（n,e），由實體A秘密保存私鑰p,q,d 2加密和解密的有效性 若能分解n，就能由e公

23、鑰計算出私鑰d。為此應n=p.q足夠長。當前整數(shù)素因子分解算法能分解十進制數(shù)長度是130，故選取的素數(shù)p和q應該是100的十進制數(shù)。目前RSA的一些硬件實現(xiàn)使用512 bit 的n（相當154位十進制數(shù)，所以不能提供長期的安全性），速度達600 Kbit / 秒。由于二次篩法、數(shù)域篩法等因子分解算法的出現(xiàn)，我們推薦768bit，長期安全應該使用1024bit。 粗略地說，RSA硬件實現(xiàn)比DES硬件實現(xiàn)慢1500倍。RSA軟件實現(xiàn)比DES軟件實現(xiàn)慢100倍。為了加速解密，實體A不是簡單平方-乘積算法計算 ，而是利用p，q計算令 ， ，用中國剩余定理解求出明文m。這樣速度可以提高48倍。3RSA安

24、全性分析首先我們研究如下事實的等價性 a.計算 b.求1模n非平凡二次方根 c.分解的素因子由此看出攻擊RSA可能采取的方法,上述事實的等價性分析如下：已知n和 由定義n=p.q和 得知 的它的兩個根為p和q，即能分解n。實際上知道 就可以從公鑰e計算出私鑰d。已知n=p.q的素因子p,q， 中元素1是模p二次剩余，它的兩個二次方根為1，p-1。 中元素1是模q二次剩余，它的兩個二次方根為1，q-1。用中國剩余定理求解下面4個同余方程組得到4個模n同余解z，它們必是(1,n-1,x,n-x)使 。其中x,n-x是模n非平凡二次方根 例如：求出z=1,z=92,z=311,z=402,z=92,

25、311為1模403的非平凡二次方根。反過來,已知1的模n非平凡二次方根,即知道 且 ,顯然 。 用Euclidean算法在多項式時間內能求出或 ，它們就是p或q，故能分解n。例如： ,x=92,311為1模403的非平凡二次方根。gcd (92+1, 403)=31,gcd (92-1, 403)=13 。gcd (311+1, 403)=13, gcd (311-1, 403)=313.1.4 RSA在實現(xiàn)時要注意的問題 1.在構造n時應選擇p和q使得p-1 和q-1 有大的素因子。一般選擇p和 (p-1)/2均是素數(shù)的p。 2.每個用戶必須有自己的模數(shù)n，用戶之間不要共享n。這里有兩個原因

26、: 1某中心選擇公用的RSA模數(shù)n，然后把 分發(fā)給眾多用戶。由 任何一對 都能分解模數(shù)n。從而本質上任何用戶都可以求出共享 該模數(shù)的每個用戶的解密密鑰 。 2如果用戶1公鑰為 , 用戶2公鑰為 , 其中 。用戶3要把同一個消息x發(fā)送給用戶1和用戶2， 它們分別為 ， 。竊聽者截獲就可以計算出x。其步驟是： a.計算 b.計算 3RSA的同態(tài)性質 (Homomorphic Property) RSA的同態(tài)性質是指乘積的密文是密文的乘積，即 的密文 其中對手想解開密文 但是不讓實體A知道m(xù)于是對手隨機選擇整數(shù) 并用代替來掩蓋明文m.讓實體A對 解密得到 對手再計算出明文 對待這種選擇密文攻擊，實踐

27、中可以通過在明文消息中強行加入某個結構來解決。如果密文C解密后不具有這種結構，則實體A發(fā)現(xiàn)是欺騙行為而拒絕C。這種做法以很高的概率使 不具有這種精心選擇的結構，從而對手取不到 。4小的加密指數(shù)為了增強加密的有效性，希望選擇較小的加密指數(shù)e（如=3）.一組實體可以有相同的加密指數(shù)，前面說過每個實體必須有自己各不相同的模數(shù)。如果相同的消息要送給多個實體的話，就不應該使小的加密指數(shù) 例如：實體A要送給m三個不同實體，他們的公鑰分別是 , , ,其中 互素對手竊取到密文 使用中國剩余定理解下面同余方程組 得到x并求它的三次方根就恢復明文m。 為了防止這類攻擊，在加密前把隨機生成的字符串附在明文的后面.

28、這個過程叫“消息加鹽”(Salting the message).對于小的 消息m和e， 也可以采用加鹽的辦法。 小的加密指數(shù)對于小的明文（ ）也存在問題。對手只 需計算密文的e次方根就能恢復明文。選擇小的e或選擇e的二進 制表示中1的位數(shù)少。好處是可以加速加密算法。在實際使用中一 般取 e=3 或者 。 5消息隱藏問題 如果 ，則明文加密后沒有被隱藏。不難看出 共有 個消息未被隱藏（9）為此我們最好選取安全素數(shù)，即對于素數(shù)p，(p-1)/2也是素數(shù)。如果p和q是隨機素數(shù)，e也是隨機選的（或選擇e比較小如e=3或 ），則一般RSA加密未隱藏的消息所占比例小的可以忽略不計。3.1.6 有關算法

29、擴展的輾轉相除法、求逆、中國剩余定理等算法已經(jīng)在前面介紹過?，F(xiàn)在給出求冪的算法和素性測試算法。1）求冪的算法（平方乘積法） 輸入 ， ，的二進制表示為 輸出 ，如果 ，則返回值 。 如果 ，則 對 做 如果 則 例如：求 這里 ，最后求出 = 7。計算過程中各參數(shù)列表如下 0 1 2 3 1 1 0 1 3 9 13 16 3 10 10 7 2）素性測試算法 在實際中為了生成大隨機素數(shù),首先生成大隨機數(shù),然后使用 概率多項式時間Monte Carlo算法測試它們的素性 (Primality)。這些算法速度快,但是有可能出錯,通過多次 運行能使出錯概率降到任意小.它的理論依據(jù)是素數(shù)定理。 該定

30、理告訴我們在1px的所有整數(shù)中是素數(shù)的比例 為 ,即隨機地選一個p,它是素數(shù)的概率約為 例如對于模數(shù)n是512位，它的十進制長度是154位，p和q約為77位。 ，也就是說平均取177個長為77的十進制數(shù)就會有一個是素數(shù)。如果我們只取奇數(shù)，此概率加大一倍為2/177。定義（模二次剩余）p是奇素數(shù)，1xp-1是整數(shù)。如果存在y,0yp-1 使 得 ，則稱x是一個模p二次剩余 ( Quadratic Residue Modulo p )。所有模p二次剩余構成集合 。 若x不是p的倍數(shù)且x不是一個模p二次剩余，則稱x是一個模p非 二次剩余( Quadratic Non-residue Modulo p

31、 )。所有模p 非二次剩余構成集合 。例如:p=11, ,定理（Euler判別準則） p是素數(shù)，x是一個模p二次剩余當且僅當 上例中 ，而 。 驗證了3是模p二次剩余，而10不是。Legendre symbol 若p是素數(shù)，則 Jacobi symbol 令 ，定義如果n是素數(shù)，則對任何a成立 如果n是合數(shù)，則 中至少有一半的整數(shù)使 不成立 證明：設 使得 不成立。使 成立 的所有整數(shù)是 ，當 時 不成立。 對所有 ， 不成立。 例如： 中模21二次剩余集合 ， ， ，8是“21為合數(shù)的Euler證據(jù)”。 ， ，20是“21的素性的Euler謊言”。若n是奇整數(shù)，選擇一個隨機整數(shù)a, 由于公鑰

32、密碼學時代的到來（特別是RSA）使Solovay-Strassen概率素性測試變得大眾化。因為Miler-Rabin測試在有效性和標準性都要好一些，所以現(xiàn)在不再使用這個測試了。但是Solovay-Strassen 算法是概率素性測試的歷史起點?，F(xiàn)在許多軟件中還在沿用這個測試。 所謂判定問題(Decision Problem)是指問題要回答的是“是”或“否”，而概率算法(Probabilistic Algorithm)是使用隨機數(shù)的算法 偏向“是”的(yes-biased) Monte Carlo算法 判定問題的一個概率算法，對“yes”實例回答總是對的，而“no”實例回答可能是錯誤的。偏向“非

33、”的(no- biased)Monte Carlo算法 判定問題的一個概率算法，對“no”實例回答總是對的，而“yes”實例回答可能是錯誤的。Solovay-Strassen 素性測試（對合數(shù)而言是yes-biased Monte Carlo算法） 輸入：奇整數(shù)和安全參數(shù)。 輸出：對問題“是素數(shù)嗎？”回答“是素數(shù)”或“是合數(shù)” 對 做 選擇一個隨機整數(shù)a, 用平方乘積算法計算 如果 ，則返回“是合數(shù)” 計算Jacobi符號 如果與模不同余，則返回“是合數(shù)”。 返回“是素數(shù)” *算法框圖3-9* 如果該算返回“是合數(shù)”，那么一定是合數(shù)，其原因是 “素數(shù)必遵守Euler準則”。換句話說：如果真是素

34、數(shù)， 不管怎樣選取算法總是會返回“是素數(shù)”。如果真是合 數(shù)，對而言至多有 是Euler謊言。所以該算 法返回“是素數(shù)”的概率小于 。 另外，這里不需要測試 。否則的話，必推 出 ，從而 并返回“是合數(shù)”。 Miller-Rabin素性測試 (yes-biased Monte Carlo算法) 輸入：奇整數(shù) ， 安全參數(shù) 輸出：對問題“n是素數(shù)嗎？”給出“是素數(shù)”或“是合數(shù)”回答 令 ，r 是奇數(shù) 對 做Miller-Rabin素性測試 (yes-biased Monte Carlo算法) 選擇一個隨機整數(shù)a, ,計算； 如果 不成立，則 當 且 時做 如果 ，則返回“n是合數(shù)”并退出 如果 ，

35、則返回“n是合數(shù)”并退出 返回“n是素數(shù)”Miller-Rabin素性測試 (yes-biased Monte Carlo算法) 這里依據(jù)的事實是：1)n是奇素數(shù)時，令 ，r是奇數(shù)。對所有滿足gcd (a,n)=1的a， 或對某個 ， 。2)n是奇合數(shù)時，令 ，r是奇數(shù)。a滿足 如果 不滿足且對所有 ， 都不成立，則稱a是“n是合數(shù)的強證據(jù)”(Strong Witness)Miller-Rabin素性測試 (yes-biased Monte Carlo算法) 如果 或存在 ， ，則稱“n是以a為底的強素數(shù)”，“a是n的素性 強謊言”(Strong Liar)。 若是奇合數(shù)，1, 2, , n-

36、1中至多有 個“n的素性強謊 言”。例如n = 91 = 7*13, 它的強謊言有18個，它們是 1,9,10,12, 16,17, 22, 29, 38, 53, 62, 69,74, 75, 79, 81, 82, 90。 下面用反證法證明：如果是奇素數(shù)，則Miller-Rabin算法一定不會返回“n是合數(shù)”。 Miller-Rabin素性測試 (yes-biased Monte Carlo算法) 假若對某個素數(shù)n返回“n是合數(shù)”，那么在循環(huán) 中必然對 均不滿足 而n是素數(shù) 。由此推出 ，因 不成立，故有 。 如此進行下去，最終得到 從 Miller-Rabin算法得到結論“是素數(shù)”。 3

37、.1.7 因子分解 因子分解比生成大素數(shù)更困難，因子分解模數(shù)是攻擊RSA最直接的方法。RSA公鑰加密系統(tǒng)的出現(xiàn)極大地促進對大整數(shù)因子分解方法研究的熱潮。特別是借助計算機網(wǎng)絡進行分布式計算取得較大進展。 *1983年Davis, Holdredge, Simmons利用二次篩法成功地分解了69位十進制數(shù)（它是 的一個合數(shù)因子） l* 1989年Lenstra, Manasse利用二次篩法使用數(shù)百臺工作站分解了106位十進制數(shù)*位1990年Lenstra, Manasse, Pollar利用數(shù)域篩法使用700臺工作站花費個月時間將155十進制數(shù) 分解成三個素數(shù)（分別為7，49，99位）之積 。*1

38、994年Atkins, Graff, Lenstra, Lerland利用二次篩法動用臺計算機聯(lián)網(wǎng)花費個月時間分解了129位十進制數(shù) 3.1.7 因子分解由此可以看出，目前的分解能力對154位十進制數(shù)（512bit）的模長已經(jīng)造成威脅，人們建議使用308位十進制數(shù)（1024bit）模長。因子分解算法分成特殊目的和一般目的兩類。當被分解的數(shù)具有特殊形式，可以為它量身定做因子分解算法。算法運行速度與因子的特定性質有關。例如： *Pollard rho算法找合數(shù)小的因子 *l Pollard 算法找合數(shù)n的素因子p，如果所有滿足 的素數(shù)因子 ，即所謂 關于小的界B是平滑的。*橢圓曲線算法它是在 上隨

39、機的橢圓曲線群上的Pollard 算法 :*3.1.7 因子分解 *特殊數(shù)域篩對于型為 ，其中 都較小的n使用數(shù)域篩進行分解 一般目的分解算法的運行時間只與n的大小有關。例如 *二次篩對于預先選定的小素數(shù)集合B，找整數(shù)x使 的所有素因子都在B中，最后將某些x相乘似的每個在B中的因子出現(xiàn)偶數(shù)次，即找到同余方程 ，從而分解 n*一般數(shù)域篩試圖尋找x和y使 成立，但是 不成立。這里要使用兩個因子庫，其中一個是小于某個界的所有素因子，另一個是在適當選擇的代數(shù)數(shù)域中范數(shù)小于某個界的所有素理想。 3.1.7 因子分解基于RSA公鑰密碼系統(tǒng)安全性考慮應滿足 *p,q要足夠大，一般應在十進制100位到125位

40、 *如果 ，要求 差不宜太小，最好與p,q位數(shù)接近。但是p與q數(shù)值不要接近。 *gcd (p-1,q-1)盡可能小 3.2 Rabin密碼系統(tǒng) Rabin于1979年提出一種變形的RSA算法，稱之為Rabin算法?？梢宰C明它的安全性等價于大整數(shù)因子分解問題。 3.2.1 Rabin算法 Rabin算法中n 和B是公鑰，其中n是Blum數(shù)( ， 且 ), 。p和q是私鑰。對于Blum數(shù)有如下事實：*若n是Blum數(shù)， ，則在 中有且僅有a的一個二次方根稱為主根(Principal Square Root)。例如 ，1，4，16的主根分別為1，16，4。*n是Blum數(shù)， ，則 3.2.1 Rab

41、in算法Rabin公鑰密碼系統(tǒng)的加解密算法如下 加密運算 解密運算 只要 不被分解，Rabin密碼系統(tǒng)是計算安全的能夠抵抗選擇明文攻擊。如果掌握n的素因子分解，即已知p, q, y, B, 由密文y經(jīng)由如下步驟得到明文x。 令 ，3.2.1 Rabin算法*求 的解*求 的解*再求四個聯(lián)立同余方程得到 的四個解。8逐個檢驗哪個是明文?？梢酝ㄟ^在明文中引如冗余，以方便識別解密得到的明文。 注：因 ，A是p模二次剩余，有 ，故 。 ， 3.2.1 Rabin算法例如：n = 7*11 = 77是Blum數(shù), B = 9, ( n, B )是公鑰。首先計算出 ， , , .Rabin算法中 加密算法

42、解密算法 若明文 ，它的密文 3.2.1 Rabin算法解密過程如下：令 ， 。得出C是模7的二次剩余和模11的二次剩余 , 又 求出解下面四個同余方程組 3.2.1 Rabin算法分別得出 并代入 ,求出各自對應的明文 。令u是1模n的方根， 即密文 對應的明文為 。如果事先利用私鑰p和q計算出1模n的方根 ，從而 , 和 是密文對應的四個明文。 3.2.1 Rabin算法這樣我們只要解一個同余方程組，其中 ， 。解出z代入 得到明文x。四個明文分別是 ， ， 。上例中1模77的二次方根為 =（1，76，34，43）。從解出z并求出x= 24，四個明文分別為24，44，2和66。3.2 EI

43、Gamal公鑰密碼系統(tǒng)3.2.1離散對數(shù)問題 EIGamal公鑰密碼系統(tǒng)在眾多協(xié)議中廣泛應用。它的安全性是基于離散對數(shù)問題的困難性。離散對數(shù)問題： p是素數(shù),是 的本原元素， 。求唯一的整數(shù)a， 使得 。記整數(shù)為 。 若小心選擇p，對于離散對數(shù)問題尚沒有多項式時間算法，故認為它是困難問題。為了抵抗已經(jīng)知道的攻擊，一般p至少150 bit，p-1應至少有大的素因子。 3.2.2 ElGamal公鑰密碼系統(tǒng) P是素數(shù),是 的本原元素, .整數(shù)a, 0ap-2使得 .其中p,是公開的,a是秘密的. 加密算法選擇隨機數(shù) ，密文 ， 其中 , 解密算法 ElGamal公鑰密碼系統(tǒng)是非確定的，它的密文依賴

44、于明文與加密者所選擇的隨機數(shù)k。相同的密文加密得到的密文不一定相同。 是明文的x掩碼 (masked)。 顯然 。 為攻破ElGamal公鑰密碼系統(tǒng)直接的方法是計算離散對數(shù)。當 所有的因子都是小素數(shù)時可以采用PohligHellman算法。此外可以仿照因子分解算法引入因子庫，先計算因子庫中素數(shù)的離散對數(shù)，然后計算期望元素的離散對數(shù)，這就是目前最有效的指標計算方法。（應密106110頁） EIGamal公鑰密碼系統(tǒng)可以在任何循環(huán)群上實現(xiàn)。選擇群的標準是： 群中的運算容易實現(xiàn)，以保證有效性 在群中離散對數(shù)問題在計算上是困難的，以保證安全性 目前最受關注的是 、 和定義在有限域上的橢圓曲線的點所構成

45、的循環(huán)群。橢圓曲線群的特點是對同一個基域F上可以選擇不同的橢圓曲線。這樣，域的運算相同使用可采用相同芯片實現(xiàn)。3.2.3 橢圓曲線令素數(shù)p3, . 上的橢圓曲線E: 是滿足同余方程 的解 ,和一個無窮遠點O組成。這里 不成立.在橢圓曲線E上定義二元運算“+”。假設P,Q 是E上的兩點， , P+O=O+P=P不難證明(E, +)為交換群，O為零元。對任何 ,例如： 上的橢圓曲線 。首先確定該曲線上的點 上有13個點O, (2,4), (2,7), (3,5), (3,6), (5,2), (5,9), (7,2), (7,9), (8,3), (8,8), (10,2),(10,9), 它對前

46、面定義的加法構成循環(huán)群，生成元為(2, 7)。下面計算= (2, 7) + (2, 7) , , ,所以 2= (5, 2) 同樣可以算出一般，橢圓曲線上點數(shù)|E| 我們要找E的循環(huán)子群，在它上面離散對數(shù)是難解問題，所以需要研究E的結構?？梢宰C明：在 上定義的橢圓曲線E，存在整數(shù) 使得 ，而且 ， 由此如果能計算出整數(shù) ，我們就知道E有循環(huán)子群同構于 把它用到ElGamal公鑰密碼系統(tǒng)中。3.2.4 Menozes-Vanstone橢圓曲線密碼系統(tǒng) Menozes-Vanstone于1993年提出一個新版本的橢圓曲線密碼系統(tǒng)。它只把橢圓曲線用在掩碼上。 令E是 （素數(shù) 3）上的橢圓曲線，E的循

47、環(huán)子群H上的離散對數(shù)是難解問題。取 ， ，保存密鑰a,公開橢圓曲線方程 、。 加密算法 明文 隨機選取 , , , , 解密算法 利用自己的私鑰a ,計算 上面有下劃線的公式計算是在橢圓曲線上進行。例如 前例中取 ， ， ， ， 。 , 其中 , 利用私鑰 計算 ，解同余方程 和 得出 。 3.3 Merkle-Hellman背包公鑰密碼系統(tǒng) Merkle-Hellman背包公鑰密碼系統(tǒng)是Merkle和Hellman于1978年首次提出的。該密碼系統(tǒng)和它的幾個變形在80年代初已被攻破。但是它的設計思想仍然值得學習和借鑒。該系統(tǒng)的安全性是基于背包（子集和）問題的困難性。子集和問題 是正整數(shù)，問是

48、否有0-1向量 使得 子集和問題是判定問題，它只要回答“是”或“不 是”。它是NP-完全問題，不知道解它的多項式時間算法。注意：我們這里是一種搜索問題，即對于任何回答“是”的實例, 找到相應的向量。背包公鑰加密算法利用一類稱之為超遞增背包問題的存在性?；舅枷胧菢嬙煲粋€超遞增背包問題并偽裝成普通的背包問題。解前者有快速算法，而解后者是一個非常困難的問題。 超遞增背包序列是滿足 的序列 超遞增背包問題 可在O(n)時間容易地解決，其的算法的輸入為T，超遞增整數(shù)序列 ，如果有解則輸出 。例如: 是超遞增整數(shù)序列, 由上面算法求出 ，從而有 2 + 9 + 21 +215 + 450 + 946 = 1643背包公鑰密碼系統(tǒng) 令 是超遞增整數(shù)序列，取素數(shù) , , 其中 t是公開的，s,