第5章  雙（公）鑰密碼體制  雙鑰（公鑰）體制于1976年由W. Diffie和M. Hellman提出，同時R. Merkle也獨立提出了這一體制。J. H. Ellis的文章闡述了公鑰密碼體制的發(fā)明史，說明了CESG的研究人員對雙鑰密碼體制發(fā)明所做出的重要貢獻。這一體制的*大特點是采用兩個密鑰將加密和解密能力分開：一個密鑰公開作為加密密鑰，稱為公鑰；一個密鑰為用戶專用，作為解密密鑰，稱為私鑰。通信雙方無須事先交換密鑰就可進行保密通信。但是從公開的公鑰或密文分析出明文或私鑰，則在計算上是不可行的。若以公開鑰作為加密密鑰，以用戶專用鑰作為解密密鑰，則可實現(xiàn)多個用戶加密的消息只能由一個用戶解讀；反之，以用戶專用鑰作為加密密鑰而以公開鑰作為解密密鑰，則可實現(xiàn)由一個用戶加密的消息而使多個用戶解讀。前者可用于保密通信，后者可用于數(shù)字簽名。這一體制的出現(xiàn)是密碼學史上劃時代的事件，它為解決計算機信息網(wǎng)中的安全提供了新的理論和技術基礎。  自1976年以來，雙鑰體制有了飛速發(fā)展，人們不僅提出了多種算法，而且出現(xiàn)了不少安全產(chǎn)品，有些已用于NII和GII之中。本章介紹其中的一些主要體制，特別是那些既有安全性，又有實用價值的算法。其中，包括可用于密鑰分配、加解密或數(shù)字簽名的雙鑰算法。一個好的系統(tǒng)不僅算法要好，還要求能與其他部分（如協(xié)議等）進行有機 組合。  由于雙鑰體制的加密變換是公開的，任何人都可以采用選擇明文來攻擊雙鑰體制，因此，明文空間必須足夠大才能防止窮盡搜索明文空間攻擊。這在雙鑰體制應用中特別重要（如用雙鑰體制加密會話密鑰時，會話密鑰要足夠長）。一種更強有力的攻擊法是選擇密文攻擊，攻擊者選擇密文，然后通過某種途徑得到相應的明文，多數(shù)雙鑰體制對于選擇密文攻擊特別敏感。攻擊者通常采用兩類選擇密文攻擊：            （1）冷漠選擇密文攻擊。在接收到待攻擊的密文之前，可以向攻擊者提供他們所選擇的密文的解密結(jié)果。

     （2）自適應選擇密文攻擊。攻擊者可能利用（或接入）被攻擊者的解密機（但不知其秘密鑰），而可以對他所選擇的、與密文有關的待攻擊的密文，以及以前詢問得到的密文進行解密。  本章介紹雙鑰體制的基本原理和幾種重要算法，如RSA、ElGamal、橢圓曲線、基于身份的密碼體制和中國商用密碼SM2算法等密碼算法。  Diffie [Diffie 1992]曾對雙鑰體制的發(fā)展做了全面論述。   雙鑰密碼體制的基本概念  對于雙鑰密碼體制來說，其安全性主要取決于構造雙鑰算法所依賴的數(shù)學問題。要求加密函數(shù)具有單向性，即求逆的困難性。因此，設計雙鑰體制的關鍵是首先要尋求一個合適的單向函數(shù)。

        5.1.1 單向函數(shù)  定義 5-1 令函數(shù)f是集A到集B的映射，用表示。若對任意 ，有，則稱f為單射，或1-1映射，或可逆的函數(shù)。  f為可逆的充要條件是，存在函數(shù)，使對所有有。  定義5-2 一個可逆函數(shù)，若它滿足：

       （1）對所有，易于計算。

       （2）對“幾乎所有”由求x“極為困難”，以至于實際上不可能做到，則稱f為單向（One-Way）函數(shù)。  定義中的“極為困難”是對現(xiàn)有的計算資源和算法而言。Massey稱此為視在困難性（Apparent Difficulty），相應函數(shù)稱為視在單向函數(shù)，以此來與本質(zhì)上的困難性（Essential Difficulty）相區(qū)分[Massey 1985]。  例5-1 令f是在有限域GF(p)中的指數(shù)函數(shù)，其中p是大素數(shù)，即  （5-1）  式中，，x為滿足的整數(shù)，其逆運算是GF(p)中定義的對數(shù)運算，即  （5-2）  顯然，由x求y是容易的，即使當p很大，例如時也不難實現(xiàn)。為方便計算，以下令(=2。所需的計算量為log次乘法，存儲量為(log p)2b，例如時，需做100次乘法。利用高速計算機由x計算可在0.1ms內(nèi)完成。但是相對于當前計算GF(p)中對數(shù)*好的算法，要從計算x所需的存儲量大約為b，運算量大約為。當p=2100時，所需的計算量為次，用計算指數(shù)一樣快的計算機進行計算需時約秒（1年=秒，故約為1600年。其中假定存儲量的要求能夠滿足）。由此可見，當p很大時，GF(p)中的，為單向函數(shù)。  Pohlig和Hellman對(p-1)無大素因子時給出一種快速求對數(shù)的算法[Pohlig等 1978]。特別是當時，從求x的計算量僅需次乘法。對于，在高速計算機上大約僅需時10ms。因此，在這種情況下，就不能被認為是單向 函數(shù)。  綜上所述，當對素數(shù)p，且p-1有大的素因子時，GF(p)上的函數(shù)是一個視在單向函數(shù)。尋求在GF(p)上求對數(shù)的一般快速算法是當前密碼學研究中的一個重要課題。

        5.1.2 陷門單向函數(shù)  單向函數(shù)是求逆困難的函數(shù)，而陷門單向函數(shù)（Trapdoor One-Way Function）是在不知陷門信息下求逆困難的函數(shù)，當知道陷門信息后，求逆易于實現(xiàn)。這是Diffie和Hellmam[Diffie等 1976]引入的有用概念。  號碼鎖在不知預設號碼時很難打開，但若知道所設號碼則容易開啟。太平門是另一例，從里面向外出容易，若無鑰匙者反向難進。但如何給陷門單向函數(shù)下定義則很棘手，因為：

       （1）陷門函數(shù)其實不是單向函數(shù)，因為單向函數(shù)是在任何條件下求逆都是困難的。

      （2）陷門可能不止一個，通過試驗，一個個陷門就可容易地找到逆。如果陷門信息的保密性不強，求逆也就不難。  定義5-3 陷門單向函數(shù)是一類滿足下述條件的單向函數(shù)：，，Z是陷門信息集。

      （1）對所有，在給定z下容易找到一對算法和，使對所有，易于計算及其逆，即  （5-3）  （5-4）  而且當給定z后容易找到一種算法，稱為可用消息集鑒別函數(shù)，對所有易于檢驗是否，是可用的明文集。

      （2）對“幾乎所有”，當只給定和時，對“幾乎所有”，“很難”（即“實際上不可能”）從算出x。

      （3）對任一z，集必須是保密系統(tǒng)中明文集中的一個“方便”集。即便于實現(xiàn)明文到它的映射（在雙鑰密碼體制中是默認的條件）。（Diffie和Hellman定義的陷門函數(shù)中，，對所有Z成立。實際中的取決于Z）。

       5.1.3 公鑰系統(tǒng)  在一個公鑰系統(tǒng)中，所有用戶共同選定一個陷門單向函數(shù)，加密運算E及可用消息集鑒別函數(shù)F。用戶i從陷門集中選定zi，并公開和。任一要向用戶i發(fā)送機密消息者，可用檢驗消息x是否在許用消息集之中，然后送給用戶x即可。  在僅知y，和的情況下，任一用戶不能得到x。但用戶i利用陷門信息，易于得到。  定義5-4 對和任意，。若  （5-5）  成立，則稱F為可換單向函數(shù)。  可換單向函數(shù)在密碼學中更有用。

       5.1.4 用于構造雙鑰密碼的單向函數(shù)  Diffie和Hellman在1976年發(fā)表的文章雖未給出陷門單向函數(shù)，但大大推動了這方面的研究工作。雙鑰密碼體制的研究在于，給出這種函數(shù)的構造方法以及它們的安全性。  陷門單向函數(shù)的定義并沒有指出這類函數(shù)是否存在，但其中指出：一個單鑰密碼體制，如果能抗擊選擇明文攻擊，就可規(guī)定一個陷門單向函數(shù)。以其密鑰作為陷門信息，則相應的加密函數(shù)就是這類函數(shù)。這是構造雙鑰體制的途徑。  下面是一些單向函數(shù)的例子。目前多數(shù)雙鑰體制是基于這些問題構造的。

       1. 多項式求根  有限域GF(p)上的一個多項式   當給定，p及x時，很容易求y，利用Honer's 法則，即  （5-6）  *多有n次乘法和n－1次加法。反之，已知，要求解x需能對高次方程求根。這至少要次乘法（這里，表示不大于a的*大整數(shù)），當n，p很大時很難求解。

       2. 離散對數(shù)DL（Discrete Logarithm）  給定一大素數(shù)p，p-1含另一大素數(shù)因子q，可構造一乘群，它是一個p-1階循環(huán)群。其生成元為整數(shù)g，。已知x，容易求，這只需次乘法，如，g15= (((1·g)2·g)2·g)2·g mod p，要用3+4?1＝6次乘法。  若已知y, g, p，求為離散對數(shù)問題。*快求解法運算次數(shù)漸近值為  （5-7）  p=512時，。  若離散對數(shù)定義在中的階循環(huán)群上，Shanks和Pohlig-Hellman等的離散對數(shù)算法預計算量的漸近式為  （5-8）  求一特定離散對數(shù)的計算量的漸近式為  （5-9）  具體請參閱[LaMacchia等 1991；McCurley 1990]。  廣義離散對數(shù)問題是在n階有限循環(huán)群G上定義的。  3. 大整數(shù)分解FAC（Factorization Problem）  判斷一個大奇數(shù)n是否為素數(shù)的有效算法，大約需要的計算量是，當n為256或512位的二元數(shù)時，用當前計算機做可在10分鐘內(nèi)完成。  若已知兩個大素數(shù)p和q，求n = p·q只需一次乘法，但若由n，求p和q，則是幾千年來數(shù)論專家的攻關對象。迄今為止，已知的各種算法的漸近運行時間如下：

      （1）試除法：*早的也是*慢的算法，需試驗所有小于sqrt(n)的素數(shù)，運行時間為指數(shù)函數(shù)。

      （2）二次篩（QS）：  （5-10）  該算法為小于110位整數(shù)*快的算法，倍多項式二次篩（MPQS）是QS算法的變型，它比QS算法更快。MPQS的雙倍大指數(shù)變型還要更快一些。

       （3）橢圓曲線（EC）：  （5-11）  （4）數(shù)域篩（NFS）：  （5-12）  式中，p是n的*小的素因子，*壞的情況下。當，要用年（一秒進行100萬次運算）。雖然整數(shù)分解問題已進行了很長時間研究，但至今尚未發(fā)現(xiàn)快速算法。目前對于大于110位的整數(shù)數(shù)域篩是*快的算法，曾用于分解第9個Fermat數(shù)。目前的進展主要是靠計算機資源來實現(xiàn)的。二次篩法可參閱[Pomerance 1984；Carton等 1988]；數(shù)域篩法可參閱[Lenstra等 1993]；橢圓曲線法參閱[Pollard 1993；Lenstra 1987；Montgomery 1987]。  T(n)與L(p)的表示式大致相同，一般當n=p時，解離散對數(shù)要更難些。  RSA問題是FAC問題的一個特例。n是兩個素數(shù)p和q之積，給定n后求素因子p和q的問題稱為RSAP。求分解問題有以下幾種形式：

      （1）分解整數(shù)n為p和q。

      （2）給定整數(shù)M和C，求d使。

      （3）給定整數(shù)e和C，求M使。

      （4）給定整數(shù)x和C，決定是否存在整數(shù)y使（二次剩余問題）。

        4. Diffie-Hellman問題（DHP）  給定素數(shù)p，令(為的生成元，若已知和，求的問題為Diffie-Hellman問題，簡稱DHP。若(為循環(huán)群G的生成元，且已知和為G中的元素，求的問題為廣義Diffie-Hellman問題，簡記為GDHP[den Boer 1988；Maurer 1994b；Waldvogel等1993；McCurley 1988]。  在[Menezes等 1997]一書的第4章對雙鑰密碼體制公鑰參數(shù)的生成和有關算法進行了全面介紹，該書的第3章對密碼中用到的數(shù)學難題進行了全面系統(tǒng)的論述。此外，還可參閱[Pomerance 1990；Adleman等1994；Bach 1990；Lenstra等1990a，1990b]。  RSA密碼體制  1978年，MIT的3位年輕數(shù)學家R.L.Rivest，A.Shamir和L.Adleman發(fā)現(xiàn)了一種用數(shù)論構造雙鑰的方法[Rivest等 1978，1979]，稱為MIT體制，后來被廣泛稱為RSA體制。它既可用于加密，又可用于數(shù)字簽名，易懂且易于實現(xiàn)，是目前仍然安全并且逐步被廣泛應用的一種體制。國際上一些標準化組織（如ISO，ITU和SWIFT等）均已接受RSA體制作為標準。在因特網(wǎng)中所采用的PGP（Pretty Good Privacy）中也將RSA作為傳送會話密鑰和數(shù)字簽名的標準算法。  RSA算法的安全性基于5.1節(jié)介紹的數(shù)論中大整數(shù)分解的困難性。

        5.2.1 RSA密碼體制  獨立選取兩個大素數(shù)和（各100～200位十進制數(shù)字），計算  （5-13）  其歐拉函數(shù)值為  （5-14）  隨機選一整數(shù)e，，。因而在模((n)下，e有逆元  （5-15）  取公鑰為n，e。密鑰為d（，不再需要，可以銷毀）。  加密：將明文分組，各組在mod n下，可*地表示出來（以二元數(shù)字表示，選2的*大冪小于n）。各組長達200位十進制數(shù)字。可用明文集為   注意，是很危險的。的概率