第二講之第4章公鑰密碼體制

第二講信息安全技術(shù)第2章密碼技術(shù)基礎(chǔ)第3章對稱密碼體系第4章公鑰密碼體系第5章公鑰基礎(chǔ)設(shè)施PKI第6章信息隱藏技術(shù)第四章內(nèi)容4.1公鑰密學(xué)概述4.2Diffie-Hellman密鑰交換算法4.3RSA算法4.1公鑰密碼概述1976年，Diffie和Hellmann提出了公開密鑰密碼體制（簡稱公鑰體制），它的加密、解密密鑰是不同的，也是不能（在有效的時間內(nèi)）相互推導(dǎo)。所以，它可稱為雙鑰密碼體制。公開密鑰密碼體制的產(chǎn)生，是密碼學(xué)革命性的發(fā)展。一方面，為數(shù)據(jù)的保密性、完整性、真實性提供了有效方便的技術(shù)。另一方面，科學(xué)地解決了密碼技術(shù)的瓶頸──密鑰的分配問題。第一個公鑰體制是1977年由Rivest，Shamir，Adleman提出的，稱為RSA公鑰體制，其安全性是基于整數(shù)的因子分解的困難性。RSA公鑰體制已得到了廣泛的應(yīng)用?；诒嘲鼏栴}的Merkle-Hellman背包公鑰體制基于有限域上離散對數(shù)問題的ElGamal公鑰體制基于橢圓曲線的ECC密碼體制……公鑰體制算法公鑰密碼體制介紹

公鑰密碼體制加解密過程主要有以下幾步：

不一樣的密碼（1）簡化密鑰分配及管理問題

公鑰體制用于數(shù)據(jù)加密時：

用戶將自己的公開（加密）密鑰登記在一個公開密鑰庫或?qū)崟r公開，秘密密鑰則被嚴(yán)格保密。信源為了向信宿發(fā)送信息，去公開密鑰庫查找對方的公開密鑰，或臨時向?qū)Ψ剿魅」€，將要發(fā)送的信息用這個公鑰加密后在公開信道上發(fā)送給對方，對方收到信息（密文）后，則用自己的秘密（解密）密鑰解密密文，讀取信息?？梢姡@里省去了從秘密信道傳遞密鑰的過程。這是公鑰體制的一大優(yōu)點。

安全的公開密鑰密碼達(dá)到的功能一對密鑰（2）保護(hù)信息機(jī)密

任何人均可將明文加密成密文，此后只有擁有解密密鑰的人才能解密。（3）實現(xiàn)不可否認(rèn)功能

公鑰體制用于數(shù)字簽名時：信源為了他人能夠驗證自己發(fā)送的消息確實來自本人，他將自己的秘密（解密）密鑰公布，而將公開（加密）密鑰嚴(yán)格保密。與別人通信時，則用自己的加密密鑰對消息加密──稱為簽名，將原消息與簽名后的消息一起發(fā)送.對方收到消息后，為了確定信源的真實性，用對方的解密密鑰解密簽名消息──稱為（簽名）驗證，如果解密后的消息與原消息一致，則說明信源是真實的，可以接受，否則，拒絕接受。

續(xù)4.2Diffie-Hellman密鑰交換算法W.Diffie和M.E.Hellman于1976年提出的，讓A和B兩個陌生人之間建立共享秘密密鑰的公開密鑰算法，稱為Diffie-Hellman算法，它定義了公開密鑰密碼體制。它的目的是使得兩個用戶安全地交換一個密鑰以便用于以后的報文加密，這個算法本身限于密鑰交換的用途。許多商用產(chǎn)品都使用這種密鑰交換技術(shù)。在Diffie-Hellman密鑰交換算法中的單向函數(shù)是模指數(shù)運算。它的逆過程是離散對數(shù)問題，其Diffie-Hellman算法的保密性基于求modp解離散對數(shù)問題的困難。離散對數(shù)定義素數(shù)p的原元（原始根）為這樣一個數(shù)，他能生成1~p-1所有數(shù)的一個數(shù)?，F(xiàn)設(shè)a為p的原元，則

兩兩互不相同，構(gòu)成一個1~p-1的全體數(shù)的一個排列。對于任意數(shù)b及素數(shù)p的原元a，可以找到一個唯一的指數(shù)i，滿足則稱指數(shù)i為以a為底、模p的b的離散對數(shù)。用戶A用戶B公開秘密秘密會話秘密會話秘密

密鑰交換過程1.基本原理

公開密鑰交換過程(1)選擇一個素數(shù)P和它的一個原元a;(2)通信方A選擇自己的秘密密鑰XA,并計算自己的公開密鑰YA:YA=a

XA

modP(3)通信方B選擇自己的秘密密鑰XB,并計算自己的公開密鑰YB:YB=a

XB

modP(4)通信雙方A和B交換YA和YB；(5)A獨立計算會話密鑰，B獨立計算會話密鑰KS；(6)通信雙方利用會話密鑰KS進(jìn)行通信。2.交換示例

為了計算簡單，使用很小數(shù)字。設(shè)P=47和47的一個原元，a=3。A選擇秘密密鑰XA=8，B選擇秘密密鑰XB=10，各自計算其公開密鑰。（1）雙方各自計算用戶A計算：YA=38mod47=6561mod47=28mod47用戶B計算：YB=310mod47=59049mod47=17mod472.交換示例（續(xù)）（2）交換YA和YB；（3）交換密鑰后，A、B分別計算共享的秘密會話密鑰KA、KB：用戶A計算：KA=YBXAmod47=178mod47=4

mod47用戶B計算：KB=YAXBmod47=2810mod47=4

mod47A和B雙方獨立地決定采用數(shù)據(jù)“4”作為會話密鑰。

特征與不足特征：（1）僅當(dāng)需要時才產(chǎn)生密鑰，減少儲存時間，減少受攻擊的機(jī)會；（2）除對全局參數(shù)的約定外，密鑰交換不需要事先存在的基礎(chǔ)結(jié)構(gòu)。不足：（1）沒有通信雙方身份的信息；（2）計算是密集性的，容易受到阻塞性攻擊；（3）沒辦法防止重放攻擊；（4）容易受到中間人攻擊。4.3RSA算法1978年由RonRivest、AdiShamir和LenAdleman發(fā)明。“Amethodforobtainingdigitalsignaturesandpublickeycryptosystem”是一種塊加密算法。明文和密文在0~n-1之間,n是一個正整數(shù)應(yīng)用最廣泛的公鑰密碼算法只有美國專利，且已于2000年9月到期1．RSA算法要點算法產(chǎn)生一對密鑰，一個人可以用密鑰對中的一個加密消息，另一個人則可以用密鑰對中的另一個解密消息。同時，任何人都無法通過公鑰確定私鑰，也沒有人能使用加密消息的密鑰解密。只有密鑰對中的另一把可以解密消息。2.RSA算法描述加密：C=MemodN,where0≤M<N解密：M=CdmodN

公鑰為（e，N），私鑰為（d，N）必須滿足以下條件：計算Me和Cd是比較容易的由e和N確定d是不可行的3.RSA密鑰產(chǎn)生過程隨機(jī)選擇兩個互質(zhì)大素數(shù)p,q(p，q必須保密)計算n=p.q計算z

=(p-1)(q-1)隨機(jī)選擇整數(shù)

e，使得1<e<z且gcd(e,z)=1計算d：d=e-1modz且0≤d≤n公布公鑰:KU={e，n}保存私鑰:KR={d，n}4.RSA的使用發(fā)送方要加密明文M:獲得接收方的公鑰KU={e,N}

計算:C=MemodN,where0≤M<N接收方解密密文C:

使用自己的私鑰KR={d,N}

計算:M=CdmodN

注意：M必須比N小5．RSA例1①取兩個質(zhì)數(shù)p=11，q=13，p和q的乘積為n=p×q=143，算出另一個數(shù)z=(p-1)×(q-1)=120；②再選取一個與z=120互質(zhì)的數(shù)，例如e=7，則公開密鑰=（n，e）=（143，7）。③對于這個e值，可以算出其逆：d=103。④因為e×d=7×103=721，滿足e×dmodz=1；即721mod120=1成立。則秘密密鑰=（n，d）=（143，103）。6．RSA例2張小姐需要發(fā)送機(jī)密信息（明文）m=85給李先生，她已經(jīng)從公開媒體得到了李先生的公開密鑰(n，e)=(143，7)，于是她算出加密值：

c=memodn=857mod143=123，并發(fā)送給李先生。李先生在收到密文c=123后，利用只有他自己知道的秘密密鑰計算：m=cdmodn=123103mod143=85，所以，李先生可以得到張小姐發(fā)給他的真正的信息m=85，實現(xiàn)了解密。7．RSA算法的安全性

依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能證明。不管怎樣，分解n是最顯然的攻擊方法。1994年4月26日，美國各大媒體報道：由RSA發(fā)明人在17年前出的129位數(shù)字已被因子分解，并破解了附帶的密語：

Themagicwordsaresqueamishossifrage.

目前，已能分解140位十進(jìn)制的大素數(shù)。因此，模數(shù)n必須選大一些。

RSA最快的情況也比DES慢上100倍，無論是軟件還是硬件實現(xiàn)。速度一直是RSA的缺陷。一般只用于少量數(shù)據(jù)加密。8．RSA算法的脆弱性不能證明RSA密碼破譯等同于大數(shù)因子分解速度問題：增大p?q將使開銷指數(shù)級增長至少有9個明文，加密后不變，即memodn=m普通用戶難于選擇p、q。對p、q的基本要求：p、q不相同，即不要太接近，又不能差別太大p-1、q-1都有大素數(shù)因子，增加猜測φ(r)難度gcd(p-1，q-1)應(yīng)當(dāng)小RSA算法的脆弱性(續(xù))4)p、q選擇不當(dāng)，則變換周期性、封閉性而泄密例：p=17，q=11，e=7，則n=187。設(shè)m=123，則

C1=1237mod187=183C2=1837mod187=72C3=727mod187=30C4=307mod187=123

明文m經(jīng)過4次加密，恢復(fù)成明文?？傊?，RSA對用戶要求太苛刻，密鑰不能常更換。9．RSA算法的攻擊方法（1）選擇密文攻擊（2）過小加密指數(shù)e（3）

RSA的公共模數(shù)攻擊（4）RSA的計時攻擊法10.RSA的實用性公開密鑰密碼體制有優(yōu)點,但它的運算量大,計算復(fù)雜。結(jié)合對稱密鑰密碼體制使用RSA算法在互聯(lián)網(wǎng)的許多方面得以廣泛應(yīng)用?；赗SA算法的公鑰加密系統(tǒng)具有數(shù)據(jù)加密、數(shù)字簽名(DigitalSignature)、信息源識別及密鑰交換等功能。11.RSA算法的優(yōu)缺點優(yōu)點密鑰空間大缺點1)產(chǎn)生密鑰很麻煩，受到素數(shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。2)速度太慢。RSA速度比DES慢得多，無論是軟件還是硬件實現(xiàn)，速度一直是RSA的缺陷。3)為保證安全性，n至少也要600bits以上，且還在增加。在運算上要付出代價。12.RSA算法和DES算法比較比較1

在加密、解密的處理效率方面，DES算法優(yōu)于RSA算法。因為DES密鑰的長度只有５６比特，可以利用軟件和硬件實現(xiàn)高速處理；RSA算法需要進(jìn)行諸如２００比特整數(shù)的乘冪和求模等多倍字長的處理，處理速度明顯慢于DES算法。續(xù)（1）比較2

在密鑰的管理方面，RSA算法比DES算法更加優(yōu)越。因為RSA算法可采用公開形式分配加密密鑰，對加密密鑰的更新也很容易，并且對不同的通信對象，只需對自己的解密密鑰保密即可；DES算法要求通信前對密鑰進(jìn)行秘密分配，密鑰的更換困難，對不同的通信對象，DES需產(chǎn)生和保管不同的密鑰。續(xù)（2）比較3

在安全性方面，DES算法和RSA算法的安全性都較好，還沒有在短時間內(nèi)破譯它們的有效的方法。比較4

在簽名和認(rèn)證方面，DES算法從原理上不可能實現(xiàn)數(shù)字簽名和身份認(rèn)證，但RSA算法能夠容易地進(jìn)行數(shù)字簽名和身份認(rèn)證。13.基于DES和RSA的加密方案設(shè)發(fā)送方為A(加密密鑰為Kea,解密密鑰為Kda),接收方為B(加密密鑰為Keb,解密密鑰為Kdb)。具體實現(xiàn)步驟:

(1)發(fā)送方A生成用于DES加密的密鑰K,為了提高數(shù)據(jù)的安全性,每一個密鑰Ｋ只用一次。

(2)發(fā)送方從密鑰服務(wù)器中獲取接收方的RSA的公開加密密鑰Keb,并用Keb加密DES的密鑰K形成密文Ck。續(xù)（1）

(3)發(fā)送方A生成需要簽名的信息,并用自己的RSA的解密密鑰Kda和Keb共同形成數(shù)字簽名。

(4)發(fā)送方用K加密明文和簽名的信息,然后連同Ck一起形成密文C發(fā)往接收方。

(5)接收方接收到C后,先用自己的解密密鑰Kdb解密出C中的DES密鑰K,再利用K解密出明文和簽名信息。

續(xù)（2）(6)接收方用發(fā)送方的公開密鑰Kea和自己的解密密鑰Kdb對簽名信息進(jìn)行身份認(rèn)證,然后對簽名信息作適當(dāng)處理后(例如填寫自己的標(biāo)識號等),再形成自己的數(shù)字簽名信息發(fā)往發(fā)送方。

(7)發(fā)送、接收雙方均刪除DES密鑰K。思考題1.對稱密碼體制和非對稱密碼體制各有何優(yōu)缺點？2.在使用RSA公鑰中如果截取了發(fā)送給其他用戶的密文C＝10，若此用戶的公鑰為e＝5，n＝35，請問明文的內(nèi)容是什么?3.已知有明文publickeyencryptions，先將明文以2個字母為組分成10塊，如果利用英文字母表的順序，即a＝00，b＝01…，將明文數(shù)據(jù)化?，F(xiàn)在令p＝53，q＝58，請計算得出RSA的加密密文。4.試簡要比較DES算法和RSA算法的優(yōu)缺點。5.假定A和B要用RSA方法進(jìn)行一次保密又認(rèn)證的通信。A的公鑰是(nA,eA)=(33,7),B的公鑰是(nB,eB)=(15,5)。

(a)A和B的秘密密鑰dA和dB各是什么?(b)A送消息m=2給B，保密又認(rèn)證，密文C是什么?(c)B如何從C解得m？6.用Diffie-Hellman密鑰交換方法在Alice和Bob之間建立一個會話密鑰。Alice向Bob送去(p,α,αxA)=(719,3,191)，Bob以543回答。Alice的秘密xA為16，求他們之間形成的會話密鑰。結(jié)束選擇密文攻擊由于RSA密文是通過公開渠道傳播的，攻擊者可以獲取密文。假設(shè)攻擊者為H，密文收件人為T，H得到了發(fā)往T的一份密文c，他想不通過分解質(zhì)因數(shù)的方法得到明文m。換句話說，H需要m=c^d。

為了恢復(fù)m，H找一個隨機(jī)數(shù)r，r<n，當(dāng)然他有T的公匙(e,n)。

續(xù)他計算：

x=r^e%n（用T的公匙加密r）

y=x*c%n（將臨時密文x與c相乘）

t=r^-1%nA知道RSA具有下面的一個特性：

如果x=r^e%n，那么r=x^d%n

因此他想辦法讓T對y用T自己的私匙簽名（實際上就是把y解密了），然后將結(jié)

果u=y^d%n寄回給A。A只要簡單地計算：

m=t*u%n

上面結(jié)論的推導(dǎo)是這樣的：

t*u%n=(r^-1)*(y^d)&n

=(r^-1)*(x^d)(c^d)%n

=(c^d)%n

=m

要防止這種攻擊的辦法就是不要對外來的隨機(jī)信息簽名，或者只對信息的MD5特征

值簽名。在這里就很容易明白為什么要強(qiáng)調(diào)MD5的單向性了，因為MD5的結(jié)果是不能預(yù)定的，就是說A難以湊出一份剛好能產(chǎn)生y這樣的MD5特征值的明文來讓T簽名。過小的加密指數(shù)ee是一個小數(shù)并不降低RSA的安全性。從計算速度考慮，e越小越好。可是，當(dāng)明文也是一個很小的數(shù)時就會出現(xiàn)問題。例如取e=3，而且明文m比n的三次方根要小，那么密文c=m^e%n就會等于m^3。這樣只要對密文開三次方就可以得到明文。RSA的公共模數(shù)攻擊若系統(tǒng)中共有一個模數(shù)，只是不同的人擁有不同的e和d，系統(tǒng)將是危險的。最普遍的情況