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

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

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

       （1）對(duì)所有，易于計(jì)算。

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

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

       （1）陷門函數(shù)其實(shí)不是單向函數(shù)，因?yàn)閱蜗蚝瘮?shù)是在任何條件下求逆都是困難的。

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

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

      （2）對(duì)“幾乎所有”，當(dāng)只給定和時(shí)，對(duì)“幾乎所有”，“很難”（即“實(shí)際上不可能”）從算出x。

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

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

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

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

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

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

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

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

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

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

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

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

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

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