公鑰密碼-5.3-基于離散對數(shù)問題的公鑰密碼課件.ppt

《公鑰密碼-5.3-基于離散對數(shù)問題的公鑰密碼課件.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、密碼學(xué)第五章公鑰密碼5.3基于離散對數(shù)問題的公鑰密碼離散對數(shù)問題1Diffie-Hellman密鑰交換協(xié)議2ElGamal公鑰密碼算法35.3基于離散對數(shù)問題的公鑰密碼在實(shí)數(shù)域中，取冪運(yùn)算(計(jì)算bx到一定精度)不比它的逆運(yùn)算(求對數(shù)logbx到一定精度)容易很多。而對有限域，其中的取冪運(yùn)算(計(jì)算bx的值)很容易，但它的逆運(yùn)算(求離散對數(shù)logbx)則是一個(gè)非常困難的問題。一、離散對數(shù)問題有限域Fp上的離散對數(shù)問題：給定一個(gè)素?cái)?shù)p和Fp上的一個(gè)本原元g，對，求整數(shù)x，，使得成立.通常用x=loggy來表示，并稱x為y的以

2、g為底關(guān)于模p的離散對數(shù)。一、離散對數(shù)問題對于等式，給定g、x和p，計(jì)算y是容易的。反過來，若已知y、g和p，當(dāng)p是大素?cái)?shù)時(shí)，找到一個(gè)x，使成立是困難的。對大素?cái)?shù)p，模p指數(shù)運(yùn)算是一個(gè)單向函數(shù)。一、離散對數(shù)問題離散對數(shù)問題是NP問題。按目前的最好算法,求解素域Fp上的離散對數(shù)的計(jì)算復(fù)雜性為但當(dāng)p較小時(shí),求解非素域Fpn上的離散對數(shù)的計(jì)算復(fù)雜性為因此,在利用有限域上的離散對數(shù)問題時(shí),多將有限域選為素域Fp.其中一、離散對數(shù)問題離散對數(shù)問題的求解難度：與離散對數(shù)密切相關(guān)的是Diffie-Hellman問題Diffie-He

3、llman問題(DHP)：Fp*中的Diffie-Hellman問題可以在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化為離散對數(shù)問題。一、離散對數(shù)問題給定一個(gè)素?cái)?shù)p和Fp上的一個(gè)本原元g及gamodp和gbmodp，求gabmodp.Diffie-Hellman密鑰交換協(xié)議是WhitefieldDiffie和MartinHellman在1976年提出的。安全性基礎(chǔ)：離散對數(shù)問題的難解性。二、Diffie-Hellman密鑰交換協(xié)議人工手動(dòng)分配密鑰:問題效率低成本高每個(gè)用戶要存儲與所有用戶通信的密鑰安全性差機(jī)器自動(dòng)分配密鑰:要求任何兩個(gè)用戶能獨(dú)立計(jì)

4、算他們之間的秘密密鑰傳輸量小存儲量小任何一個(gè)(或多個(gè))用戶不能計(jì)算出其他用戶之間的秘密密鑰二、Diffie-Hellman密鑰交換協(xié)議D-H密鑰交換協(xié)議背景:密鑰分配UV二、Diffie-Hellman密鑰交換協(xié)議D-H密鑰交換協(xié)議基本模式Diffie-Hellman密鑰交換協(xié)議具體描述:設(shè)計(jì)過程:Step1選取安全的大素?cái)?shù)p,再選取g是Fp的一個(gè)本原元，并將p和g公開，全網(wǎng)公用；Step2用戶U隨機(jī)選取整數(shù)xu：1≤xu≤p-2,并計(jì)算出，將明傳給用戶V,并暫時(shí)保留xu；二、Diffie-Hellman密鑰交換協(xié)議用

5、戶V算出Step4用戶U算出之后，將k作為雙方協(xié)商的密鑰，同時(shí)不再保留xu和xv。Step3用戶V隨機(jī)選取整數(shù)xv：1≤xv≤p-2,并計(jì)算出，將明傳給用戶U，并暫時(shí)保留xv；二、Diffie-Hellman密鑰交換協(xié)議優(yōu)點(diǎn)：(1)任何兩個(gè)人都可協(xié)商出會話密鑰，不需事先擁有對方的公開或秘密的信息；(2)每次密鑰交換后不必再保留秘密信息，減少了保密的負(fù)擔(dān)。二、Diffie-Hellman密鑰交換協(xié)議前提條件:必須進(jìn)行身份認(rèn)證，確保不是與假冒的用戶進(jìn)行密鑰交換,否則不能抵抗中間人攻擊.中間人攻擊:攻擊者W在信道中間：假冒U

6、，與V進(jìn)行密鑰交換；同時(shí)假冒V，與U進(jìn)行密鑰交換。致使看似U與V交換的密鑰，實(shí)際上都是與攻擊者交換的密鑰。二、Diffie-Hellman密鑰交換協(xié)議二、Diffie-Hellman密鑰交換協(xié)議中間人攻擊基本模式UVW中間人攻擊方案Step1攻擊者W首先截獲，然后隨機(jī)選取整數(shù)xw：1≤xw≤p-2,并算出后，將其明傳給用戶V，同時(shí)暫時(shí)保留xw；Step2攻擊者W再截獲，然后將明傳給用戶U；Step3用戶U算出用戶V算出攻擊者W算出和二、Diffie-Hellman密鑰交換協(xié)議Step4攻擊者W截獲用戶U發(fā)給V的密文后，

7、不傳給用戶V，而是解讀出明文后再將明文用W與V的密鑰加密后傳給V。二、Diffie-Hellman密鑰交換協(xié)議對付中間人攻擊的方法:中間人攻擊利用了D-H協(xié)議中與雙方的身份信息無關(guān)這個(gè)缺點(diǎn)，因而必須利用對方的身份信息對之進(jìn)行身份認(rèn)證。二、Diffie-Hellman密鑰交換協(xié)議ElGamal公鑰密碼體制是ElGamal在1985年提出的。安全性基礎(chǔ)：有限域上離散對數(shù)問題的難解性。三、ElGamal公鑰密碼算法Step2隨機(jī)選取整數(shù)x：1?x?p-2,并計(jì)算出用戶A的密鑰生成過程:用戶A的公鑰是(p,g,gx);私鑰是x

8、。三、ElGamal公鑰密碼算法ElGamal公鑰密碼算法描述:Step1選取安全的大素?cái)?shù)p,再選取g是Fp*的一個(gè)本原元；B加密:B秘密選擇一個(gè)整數(shù)則密文為其中A脫密:對任意密文明文為假定B加密信息m?Fp?給A，A解密。三、ElGamal公鑰密碼算法加、脫密變換:例1：生成密鑰：用戶A選取素?cái)?shù)p=11及F11*的生成元g=2，