第4章 公鑰密碼系統(tǒng)

第4章公鑰密碼系統(tǒng)4.1RSA密碼系統(tǒng)4.2Diffie-Hellman密鑰交換4.3數(shù)字簽名

習(xí)題4.1RSA密碼系統(tǒng)公鑰密碼體制于1976年由W.Diffie和M.Hellman提出[1]，同時(shí)，R.Merkle也獨(dú)立提出了這一體制。這種密碼體制采用了一對(duì)密鑰——加密密鑰和解密密鑰(且從解密密鑰推出加密密鑰是不可行的)，這一對(duì)密鑰中，一個(gè)可以公開(kāi)(稱之為公鑰)，另一個(gè)為用戶專用(私鑰)。公鑰密碼系統(tǒng)是基于陷門(mén)單向函數(shù)的概念。在第3章中，我們介紹了單向函數(shù)的概念。單向函數(shù)是易于計(jì)算但求逆困難的函數(shù)，而陷門(mén)單向函數(shù)是在不知道陷門(mén)信息情況下求逆困難，而在知道陷門(mén)信息時(shí)易于求逆的函數(shù)。公鑰密碼系統(tǒng)可用于以下三個(gè)方面：(1)通信保密：此時(shí)將公鑰作為加密密鑰，私鑰作為解密密鑰，通信雙方不需要交換密鑰就可以實(shí)現(xiàn)保密通信。這時(shí)，通過(guò)公鑰或密文分析出明文或私鑰是不可行的。如圖4-1所示，Bob擁有多個(gè)人的公鑰，當(dāng)他需要向Alice發(fā)送機(jī)密消息時(shí)，他用Alice公布的公鑰對(duì)明文消息加密，當(dāng)Alice接收到后用她的私鑰解密。由于私鑰只有Alice本人知道，所以能實(shí)現(xiàn)通信保密。圖4-1通信保密(2)數(shù)字簽名：將私鑰作為加密密鑰，公鑰作為解密密鑰，可實(shí)現(xiàn)由一個(gè)用戶對(duì)數(shù)據(jù)加密而使多個(gè)用戶解讀。如圖4-2所示，Bob用私鑰對(duì)明文進(jìn)行加密并發(fā)布，Alice收到密文后用Bob公布的公鑰解密。由于Bob的私鑰只有Bob本人知道，因此，Alice看到的明文肯定是Bob發(fā)出的，從而實(shí)現(xiàn)了數(shù)字簽名。(3)密鑰交換：通信雙方交換會(huì)話密鑰，以加密通信雙方后續(xù)連接所傳輸?shù)男畔ⅰＣ看芜壿嬤B接使用一把新的會(huì)話密鑰，用完就丟棄。本章將先討論RSA密碼系統(tǒng)和Diffie-Hellman密鑰交換，最后介紹數(shù)字簽名。圖4-2數(shù)字簽名公開(kāi)密鑰加密的第一個(gè)算法是由RalphMerkle和MartinHellman開(kāi)發(fā)的背包算法[2]，它只能用于加密。后來(lái)，AdiShamir將其改進(jìn)，使之能用于數(shù)字簽名。背包算法的安全性不好，也不完善。隨后不久就出現(xiàn)了第一個(gè)較完善的公開(kāi)密鑰算法RSA[3](根據(jù)其發(fā)明者命名，即R.Rivest,A.Shamir和L.Adleman)。RSA密碼系統(tǒng)的安全性基于大數(shù)分解的困難性。我們知道，求一對(duì)大素?cái)?shù)的乘積很容易，但要對(duì)這個(gè)乘積進(jìn)行因式分解則非常困難，因此，可以把一對(duì)大素?cái)?shù)的乘積公開(kāi)作為公鑰，而把素?cái)?shù)作為私鑰，從而從一個(gè)公開(kāi)密鑰和密文中恢復(fù)出明文的難度等價(jià)于分解兩個(gè)大素?cái)?shù)之積。公鑰密碼系統(tǒng)一般都涉及數(shù)論的知識(shí)，如素?cái)?shù)、歐拉函數(shù)、中國(guó)剩余定理等等，這在許多密碼學(xué)教材中都有所論述，本書(shū)不作討論。下面介紹RSA密碼系統(tǒng)的細(xì)節(jié)。選擇兩個(gè)不同的大素?cái)?shù)p和q(一般都為100位左右的十進(jìn)制數(shù)字)，計(jì)算乘積：n=pq和歐拉函數(shù)值：φ?(n)=(p?1)(q?1)隨機(jī)取一整數(shù)e，1＜e＜φ?(n)，且e和φ?(n)互素。此時(shí)可求得d以滿足：ed1mod?φ(n)則d=e–1mod?φ(n)這樣可以把e和n作為公開(kāi)密鑰，d作為私人密鑰。其中，p、q、φ?(n)和d就是秘密的陷門(mén)(四項(xiàng)并不是相互獨(dú)立的)，這些信息不可以泄露。RSA加密消息m時(shí)(這里假設(shè)m是以十進(jìn)制表示的)，首先將消息分成大小合適的數(shù)據(jù)分組，然后對(duì)分組分別進(jìn)行加密。每個(gè)分組的大小應(yīng)該比n小。設(shè)ci為明文分組mi加密后的密文，則加密公式為ci=mie(modn)解密時(shí)，對(duì)每一個(gè)密文分組進(jìn)行如下運(yùn)算：mi=cid(modn)這種加/解密方案的可行性證明可以參考本章參考資料[13]。這里將舉一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明RSA的加/解密過(guò)程。選p=5，q=11，則n=pq=55，φ?(n)=(p?1)(q?1)=40于是明文空間為在閉區(qū)間[1,54]內(nèi)且不能被5和11整除的數(shù)。(如果明文m同n不是互為素?cái)?shù)，就有可能出現(xiàn)消息暴露情況，即，這樣我們就可能通過(guò)計(jì)算n與加密以后的m的最大公約數(shù)來(lái)分解出n。通常，一個(gè)明文同n有公約數(shù)的概率小于1/p+1/q，因此，對(duì)于大的p和q來(lái)說(shuō)，這種概率是非常小的。)選擇e=7，則d=23。由加/解密公式可以得到加密表如表4-1所示。表4-1加密表明文密文明文密文明文密文明文密文1114928524248218163629394332342178312646514491817324347536411924343448277282121363149148223123738516942429384752131223261639195337137273414654544.2Diffie-Hellman密鑰交換4.2.1Diffie-Hellman算法Diffie-Hellman算法是第一個(gè)公開(kāi)密鑰算法，發(fā)明于1976年[1]。Diffie-Hellman算法能夠用于密鑰分配，但不能用于加密或解密信息。Diffie-Hellman算法的安全性在于在有限域上計(jì)算離散對(duì)數(shù)非常困難。在此先簡(jiǎn)單介紹一下離散對(duì)數(shù)的概念。定義素?cái)?shù)p的本原根(PrimitiveRoot)為一種能生成1～p?1所有數(shù)的一個(gè)數(shù)，即如果a為p的本原根，則amodp，a2modp，…，ap?1modp兩兩互不相同，構(gòu)成1～p?1的全體數(shù)的一個(gè)排列(例如p=11，a=2)。對(duì)于任意數(shù)b及素?cái)?shù)p的本原根a，可以找到一個(gè)惟一的指數(shù)i，滿足：b=aimodp,0≤i≤p?1稱指數(shù)i為以a為底模p的b的離散對(duì)數(shù)。如果Alice和Bob想在不安全的信道上交換密鑰，他們可以采用如下步驟：(1)?Alice和Bob協(xié)商一個(gè)大素?cái)?shù)p及p的本原根a，a和p可以公開(kāi)；(2)?Alice秘密產(chǎn)生一個(gè)隨機(jī)數(shù)x，計(jì)算X=axmodp，然后把X發(fā)送給Bob；(3)?Bob秘密產(chǎn)生一個(gè)隨機(jī)數(shù)y，計(jì)算Y=aymodp，然后把Y發(fā)送給Alice；(4)?Alice計(jì)算k=Yxmodp；(5)?Bob計(jì)算k'=Xymodp。k和k'是恒等的，因?yàn)閗=Yxmodp=(ay)xmodp=(ax)ymodp=Xymodp=k'線路上的搭線竊聽(tīng)者只能得到a、p、X和Y的值，除非能計(jì)算離散對(duì)數(shù)，恢復(fù)出x和y，否則就無(wú)法得到k，因此，k為Alice和Bob獨(dú)立計(jì)算的秘密密鑰。下面用一個(gè)例子來(lái)說(shuō)明上述過(guò)程。Alice和Bob需進(jìn)行密鑰交換，如圖4-3所示，則：●二者協(xié)商后決定采用素?cái)?shù)p=353及其本原根a=3?！?Alice選擇隨機(jī)數(shù)x=97，計(jì)算X=397mod353＝40，并發(fā)送給Bob?！?Bob選擇隨機(jī)數(shù)y=233，計(jì)算Y=3233mod353＝248，并發(fā)送給Alice?！?Alice計(jì)算k=Yxmodp＝24897mod353=160?！?Bob計(jì)算k'=Xymodp＝40233mod353=160。k和k'?即為秘密密鑰。圖4-3Diffie-Hellman密鑰交換4.2.2中間人攻擊Diffie-Hellman密鑰交換容易遭受中間人攻擊：(1)?Alice發(fā)送公開(kāi)值(a和p)給Bob，攻擊者Carol截獲這些值并把自己產(chǎn)生的公開(kāi)值發(fā)送給Bob。(2)?Bob發(fā)送公開(kāi)值給Alice，Carol截獲它然后把自己的公開(kāi)值發(fā)送給Alice。(3)?Alice和Carol計(jì)算出二人之間的共享密鑰k1。(4)?Bob和Carol計(jì)算出另外一對(duì)共享密鑰k2。這時(shí)，Alice用密鑰k1給Bob發(fā)送消息；Carol截獲消息后用k1解密就可讀取消息；然后將獲得的明文消息用k2加密(加密前可能會(huì)對(duì)消息作某些修改)后發(fā)送給Bob。對(duì)Bob發(fā)送給Alice的消息，Carol同樣可以讀取和修改。造成中間人攻擊的原因是Diffie-Hellman密鑰交換不認(rèn)證對(duì)方。利用數(shù)字簽名可以挫敗中間人攻擊。4.2.3認(rèn)證的Diffie-Hellman密鑰交換密鑰交換雙方通過(guò)數(shù)字簽名和公鑰證書(shū)相互認(rèn)證可以挫敗中間人攻擊。在密鑰交換之前，密鑰交換的雙方Alice和Bob各自擁有公鑰/私鑰對(duì)和公開(kāi)密鑰證書(shū)。下面是Alice和Bob產(chǎn)生共享秘密密鑰的過(guò)程：(1)?Alice產(chǎn)生隨機(jī)數(shù)x并發(fā)送給Bob。(2)?Bob產(chǎn)生隨機(jī)數(shù)y并根據(jù)Diffie-Hellman協(xié)議計(jì)算出共享秘密密鑰k，然后Bob對(duì)x、y簽名并用k加密簽名，最后把加密的簽名和y一起發(fā)送給Alice。(3)?Alice計(jì)算出k，用k解密Bob發(fā)送給他的消息并驗(yàn)證Bob的簽名。驗(yàn)證后對(duì)x、y簽名并用k加密簽名后發(fā)送給Bob。(4)?Bob解密消息并驗(yàn)證Alice的簽名。4.2.4三方或多方Diffie-HellmanDiffie-Hellman密鑰交換協(xié)議很容易擴(kuò)展到三方或多方的密鑰交換。下例中，Alice、Bob和Carol一起產(chǎn)生秘密密鑰，見(jiàn)圖4-4。圖4-4三方或多方的密鑰交換(1)?Alice選取一個(gè)大隨機(jī)整數(shù)x，計(jì)算X=axmodp，然后把X發(fā)送給Bob；(2)?Bob選取一個(gè)大隨機(jī)整數(shù)y，計(jì)算Y=aymodp，然后把Y發(fā)送給Carol；(3)?Carol選取一個(gè)大隨機(jī)整數(shù)z，計(jì)算Z=azmodp，然后把Z發(fā)送給Alice；(4)?Alice計(jì)算Z'=Zxmodp并發(fā)送Z'?給Bob；(5)?Bob計(jì)算X'=Xymodp并發(fā)送X'?給Carol；(6)?Carol計(jì)算Y'=Yzmodp并發(fā)送Y'?給Alice；(7)?Alice計(jì)算k=Y'xmodp；(8)?Bob計(jì)算k=Z'ymodp；(9)?Carol計(jì)算k=X'zmodp。共享秘密密鑰k等于axyzmodp。這個(gè)協(xié)議很容易擴(kuò)展到更多方。4.3數(shù)

字

簽

名4.3.1基本概念在計(jì)算機(jī)通信中，當(dāng)接收者接收到一個(gè)消息時(shí)，往往需要驗(yàn)證消息在傳輸過(guò)程中有沒(méi)有被篡改；有時(shí)接收者需要確認(rèn)消息發(fā)送者的身份。所有這些都可以通過(guò)數(shù)字簽名來(lái)實(shí)現(xiàn)。數(shù)字簽名可以用來(lái)證明消息確實(shí)是由發(fā)送者簽發(fā)的，而且，當(dāng)數(shù)字簽名用于存儲(chǔ)的數(shù)據(jù)或程序時(shí)，可以用來(lái)驗(yàn)證數(shù)據(jù)或程序的完整性。它和傳統(tǒng)的手寫(xiě)簽名類(lèi)似，應(yīng)滿足以下條件：(1)簽名是可以被確認(rèn)的，即收方可以確認(rèn)或證實(shí)簽名確實(shí)是由發(fā)方簽名的；(2)簽名是不可偽造的，即收方和第三方都不能偽造簽名；(3)簽名不可重用，即簽名是消息(文件)的一部分，不能把簽名移到其它消息(文件)上；(4)簽名是不可抵賴的，即發(fā)方不能否認(rèn)他所簽發(fā)的消息；(5)第三方可以確認(rèn)收發(fā)雙方之間的消息傳送但不能篡改消息。使用對(duì)稱密碼系統(tǒng)可以對(duì)文件進(jìn)行簽名，但此時(shí)需要可信任的第三方仲裁。公開(kāi)密鑰算法也能用于數(shù)字簽名。此時(shí)，發(fā)方用私鑰對(duì)文件進(jìn)行加密就可以獲得安全的數(shù)字簽名。在實(shí)際應(yīng)用中，由于公開(kāi)密鑰算法的效率較低，發(fā)送方并不對(duì)整個(gè)文件簽名，而只對(duì)文件的散列值簽名。一個(gè)數(shù)字簽名方案一般由兩部分組成：簽名算法和驗(yàn)證算法。其中，簽名算法或簽名密鑰是秘密的，只有簽名人知道，而驗(yàn)證算法是公開(kāi)的。4.3.2數(shù)字簽名算法1991年8月，美國(guó)NIST公布了用于數(shù)字簽名標(biāo)準(zhǔn)DSS的數(shù)字簽名算法DSA，1994年12月1日正式采用為美國(guó)聯(lián)邦信息處理標(biāo)準(zhǔn)[5]。DSA中用到了以下參數(shù)：(1)?p為L(zhǎng)位長(zhǎng)的素?cái)?shù)，其中，L為512～1024之間且是64倍數(shù)的數(shù)。(2)?q是160位長(zhǎng)的素?cái)?shù)，且為p?1的因子。(3)?g=h(p?1)/qmodp，其中，h是滿足1＜h＜p?1且h(p?1)/qmodp大于1的整數(shù)。(4)?x是隨機(jī)產(chǎn)生的大于0而小于q的整數(shù)。(5)?y=gxmodp。(6)?k是隨機(jī)產(chǎn)生的大于0而小于q的整數(shù)。前三個(gè)參數(shù)p、q、g是公開(kāi)的；x為私鑰，y為公鑰；x和k用于數(shù)字簽名，必須保密；對(duì)于每一次簽名都應(yīng)該產(chǎn)生一次k。對(duì)消息m簽名：r=(gkmodp)modqs=(k?1(SHA?1(m)+xr))modqr和s就是簽名。驗(yàn)證簽名時(shí)，計(jì)算：w=s?1modqu1=(SHA?1(m)×w)modqu2=(rw)modqv=((gu1×yu2)modp)modq如果v=r，則簽名有效。4.3.3RSA簽名方案前面提到RSA可以用于數(shù)字簽名。根據(jù)4.1中的描述，我們可以獲得私鑰d，公鑰e和n，則對(duì)消息m簽名有r=sig(m)=(H(m))dmodn其中，H(m)計(jì)算消息m的消息摘要，可由散列函數(shù)SHA?1或MD5得到；r即為對(duì)消息的簽名。驗(yàn)證簽名時(shí)，驗(yàn)證：H(m)≡remodn