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

字

簽

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