[[380512]]

對(duì)稱(chēng)密碼可以實(shí)現(xiàn)對(duì)任意明文的高效加密，通常用于通信會(huì)話的加密，但隨著對(duì)稱(chēng)加密應(yīng)用越來(lái)越廣，會(huì)話密鑰的管理問(wèn)題也隨之面臨挑戰(zhàn)。假設(shè)網(wǎng)絡(luò)中有n個(gè)實(shí)體需要兩兩通信，那么每個(gè)實(shí)體必須維護(hù)一把與其他任意一個(gè)實(shí)體之間的會(huì)話密鑰，總的會(huì)話密鑰數(shù)量為，即達(dá)到O(n2)的量級(jí)，密鑰管理的復(fù)雜度明顯增加。另一方面，分組加密主要依賴于多輪復(fù)合的擴(kuò)散和混淆運(yùn)算，安全強(qiáng)度有待進(jìn)一步增強(qiáng)。

公鑰密碼也稱(chēng)非對(duì)稱(chēng)密碼，即加密密鑰和解密密鑰不同，一個(gè)可被公開(kāi)的密鑰被稱(chēng)為公鑰，一個(gè)私人專(zhuān)用保管的密鑰被稱(chēng)為私鑰。公鑰與私鑰在數(shù)學(xué)上是有緊密關(guān)系的，用公鑰加密的信息只能用對(duì)應(yīng)的私鑰解密，反之亦然。由于公鑰算法不需要聯(lián)機(jī)密鑰服務(wù)器，密鑰分配變得簡(jiǎn)單。一個(gè)人可以在與許多人交往時(shí)使用相同的密鑰對(duì)，而不必與每個(gè)人分別使用不同的密鑰。只要私鑰是保密的，就可以隨意分發(fā)其公鑰，用戶可以與任意數(shù)目的人員共享一個(gè)密鑰對(duì)，而不必為每個(gè)人單獨(dú)設(shè)立一個(gè)密鑰，顯著降低了密鑰管理復(fù)雜度，簡(jiǎn)化了密鑰管理操作，有效提高了密碼學(xué)的可用性。

公鑰加密是一種干擾信息的方法，使用該方法的雙方擁有一對(duì)密鑰，其中一個(gè)可以公開(kāi)分享，而另一個(gè)只有預(yù)定的目標(biāo)接收方才知曉。任何人都可能使用私人的公開(kāi)密鑰對(duì)信息進(jìn)行加密。但是，只要預(yù)定接收方的解密密鑰被安全地保護(hù)起來(lái)，信息就無(wú)法被解密。一般而言，公鑰算法的設(shè)計(jì)依賴于經(jīng)典的數(shù)論難題，即將攻擊者在沒(méi)有私鑰的情況下，破解一個(gè)公鑰加密系統(tǒng)，等效映射到求解數(shù)論難題。這樣，攻擊者若能在沒(méi)有私鑰的情況下破解公鑰加密，等效于其求解了公知的數(shù)論難題。這樣的模型假設(shè)也因此成為公鑰密碼安全的保障基石。

1976年，Whitfield Diffie和Martin Hellman 共同發(fā)表了學(xué)術(shù)論文《New Direction in Cryptography》，創(chuàng)建了公鑰加密體制。公鑰加密是重大的創(chuàng)新，從根本上改變了加密和解密的過(guò)程，也成為40年來(lái)信息安全應(yīng)用領(lǐng)域的一項(xiàng)核心技術(shù)。2015年，Diffie和Hellman兩位密碼學(xué)家也因創(chuàng)立發(fā)明公鑰加密技術(shù)而獲得有著計(jì)算機(jī)領(lǐng)域諾貝爾美譽(yù)的圖靈獎(jiǎng)。

1. Diffie-Hellman密鑰交換算法

下面以Alice和Bob為例介紹以Diffie和Hellman命名的DH密鑰交換原理。

（1）選定一個(gè)可公開(kāi)的大質(zhì)數(shù)p和底數(shù)g。

（2）Alice和Bob分別選定一個(gè)私有的素?cái)?shù)a和b。

圖1給出了Alice和Bob通過(guò)公開(kāi)交換g、p、A、B，最終各自計(jì)算獲得共享密鑰K=gab的基本過(guò)程。DH密鑰協(xié)商的目的是讓Alice和Bob安全獲得共享密鑰，任何第三方實(shí)體即使截獲雙方通信數(shù)據(jù)，也無(wú)法計(jì)算得到相同的密鑰。

圖1  DH密鑰交換原理

下面再看一個(gè)簡(jiǎn)單的實(shí)例，來(lái)說(shuō)明Alice和Bob協(xié)商計(jì)算會(huì)話密鑰K的過(guò)程。

1）Alice與Bob協(xié)定使用p=23，g=5。

2）Alice選擇一個(gè)秘密整數(shù)a=6，計(jì)算A=gamodp并發(fā)送給Bob：A=56mod 23=8。

3）Bob選擇一個(gè)秘密整數(shù)b=15，計(jì)算B=gbmodp并發(fā)送給Alice：B=515mod 23=19。

4）Alice計(jì)算K=Bamodp，即196mod 23=2。

5）Bob計(jì)算K=Abmodp，即815mod 23=2。

DH是一個(gè)公鑰算法，應(yīng)用的數(shù)論難題是大數(shù)的離散對(duì)數(shù)求解難題，即已知g、a，計(jì)算A=ga是容易的，但反之，已知A和g，求解a是困難的。這樣，攻擊者即便截獲得到A和B，也無(wú)法計(jì)算得到a和b，因而也無(wú)法計(jì)算獲得K。

2. RSA公鑰算法

公開(kāi)密鑰算法是在 1976年由當(dāng)時(shí)在美國(guó)斯坦福大學(xué)的 Diffie和Hellman 兩人首先發(fā)明的，但是目前最流行的RSA算法則是1977年由MIT教授Ronald L.Rivest、Adi Shamir和Leonard M.Adleman共同發(fā)明的。RSA也是分別取自3名數(shù)學(xué)家人名的第一個(gè)字母。RSA算法依賴于大數(shù)因子分解難題，即給定兩個(gè)大素?cái)?shù)p、q，計(jì)算它們的乘積n=pq是容易的，但反之，給定n，求解p和q是一個(gè)經(jīng)典的數(shù)論難題。

（1）密鑰生成

①選擇兩個(gè)大素?cái)?shù)：p和q。

②計(jì)算歐拉函數(shù)：φ(n)=(p−1)(q−1)。

③選擇一個(gè)正整數(shù)e，使gcd(e,φ(n))=1，即e和φ(n)互為素?cái)?shù)。

④根據(jù)de=1(modφ(n))，利用Euclid算法計(jì)算出d。

⑤公鑰即為K=<e,n>。

⑥私鑰即為S=<d,p,q>。

（2）公鑰加密

①記明文信息為m（二進(jìn)制），將m分成等長(zhǎng)數(shù)據(jù)塊m1,m2,…,mi，塊長(zhǎng)s，其中2s≤n。

②加密：ci≡mi^e(modn)

③解密：mi≡ci^d(modn)

一開(kāi)始，RSA選用的n長(zhǎng)度達(dá)到512 bit時(shí)，以當(dāng)時(shí)的計(jì)算機(jī)運(yùn)算能力，安全性已公認(rèn)足夠強(qiáng)大。隨著并行計(jì)算水平的飛速發(fā)展以及量子計(jì)算等新型計(jì)算的出現(xiàn)，RSA的安全強(qiáng)度也開(kāi)始受到威脅。目前，RSA選用的公鑰長(zhǎng)度已達(dá)到了4 096 bit。

相比于對(duì)稱(chēng)密碼，公鑰密碼具有實(shí)現(xiàn)難度大、安全強(qiáng)度大、計(jì)算耗費(fèi)大等特點(diǎn)。因此，在日常應(yīng)用時(shí)，RSA算法和AES算法混合使用，通常被稱(chēng)作數(shù)字信封技術(shù)，如圖2所示。

圖2  數(shù)字信封技術(shù)

雖然安全強(qiáng)度大，但由于 RSA 公鑰加密需耗費(fèi)較大資源，因此通常會(huì)話加密采用的是AES分組密碼，而AES會(huì)話密鑰則可通過(guò)RSA公鑰加密，AES密鑰的加密結(jié)果隨會(huì)話密文一起發(fā)送給接收方，這樣的技術(shù)就叫數(shù)字信封，可以確保僅有持有RSA私鑰的合法的接收方才能解開(kāi)AES密鑰，從而獲得最終的會(huì)話明文。