第8章 公鑰密碼學(xué)

《第8章 公鑰密碼學(xué)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、公鑰密碼學(xué)張?jiān)鞅惫I(yè)大學(xué)電子信息學(xué)院內(nèi)容提要公開(kāi)密鑰密碼算法的基本思想公開(kāi)密鑰密碼算法的數(shù)學(xué)基礎(chǔ)一些經(jīng)典算法對(duì)稱算法的不足密鑰管理的困難：傳統(tǒng)密鑰管理：兩兩分別用一個(gè)密鑰時(shí)，則n個(gè)用戶需要C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶量增大時(shí)，密鑰空間急劇增大。如:n=100時(shí)，C(100,2)=4,995n=5000時(shí)，C(5000,2)=12,497,500密鑰發(fā)布的困難：密鑰必須通過(guò)某一信道協(xié)商，對(duì)這個(gè)信道的安全性的要求比正常的傳送消息的信道的安全性要高數(shù)字簽名的問(wèn)題傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的需求。對(duì)稱算法的優(yōu)點(diǎn)：速度快公鑰

2、密碼的起源公鑰密碼又稱為雙鑰密碼和非對(duì)稱密碼，是1976年由Diffie和Hellman在其“密碼學(xué)新方向”一文中提出的，見(jiàn)劃時(shí)代的文獻(xiàn)：W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公鑰算法是由Rivest,Shamir和Adleman在1978年提出來(lái)的,見(jiàn)CommunitionsoftheACM.Vol.21.No.2.Feb.197

3、8,PP.120-126公開(kāi)密鑰密碼的重要特性基于公開(kāi)密鑰的加密過(guò)程用公鑰密碼實(shí)現(xiàn)保密用戶擁有自己的密鑰對(duì)(KU,KR)公鑰KU公開(kāi),私鑰KR保密A?B:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X))=X基于公開(kāi)密鑰的鑒別過(guò)程用公鑰密碼實(shí)現(xiàn)鑒別條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密鑒別（不提供保密）：A?ALL:Y=DKRa(X)ALL：EKUa(Y)=EKUa(DKRa(X))=X鑒別+保密：A?B：Z=EKUb(DKRa(X))B：EKUa(DKRb(Z))=X公鑰密鑰的應(yīng)用范圍加密/解密數(shù)字簽

4、名(身份鑒別)密鑰交換：交換會(huì)話密鑰基本要求和思想涉及到各方：發(fā)送方、接收方、攻擊者涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文公鑰算法的條件：產(chǎn)生一對(duì)密鑰是計(jì)算可行的已知公鑰和明文，產(chǎn)生密文是計(jì)算可行的接收方利用私鑰來(lái)解密密文是計(jì)算可行的對(duì)于攻擊者，利用公鑰來(lái)推斷私鑰是計(jì)算不可行的已知公鑰和密文，恢復(fù)明文是計(jì)算不可行的(可選)加密和解密的順序可交換思想：陷門單向函數(shù)單向陷門函數(shù)是滿足下列條件的函數(shù)f：給定x，計(jì)算y=fk(x)是容易的；給定y，計(jì)算x使x=fk-1(y)是不可行的。存在k，已知k時(shí)，對(duì)給定的任何y，若相應(yīng)的x存在，則計(jì)算x使

5、x=fk-1(y)是容易的。公鑰密碼基于的數(shù)學(xué)難題背包問(wèn)題大整數(shù)分解問(wèn)題（TheIntegerFactorizationProblem,RSA體制）離散對(duì)數(shù)問(wèn)題有限域的乘法群上的離散對(duì)數(shù)問(wèn)題(TheDiscreteLogarithmProblem,ElGamal體制）定義在有限域的橢圓曲線上的離散對(duì)數(shù)問(wèn)題（TheEllipticCurveDiscreteLogarithmProblem,類比的ElGamal體制）內(nèi)容提要公開(kāi)密鑰密碼算法的基本思想公開(kāi)密鑰密碼算法的數(shù)學(xué)基礎(chǔ)一些經(jīng)典算法數(shù)的整除性設(shè)Z為全體整數(shù)的集合，若b≠0且a,b,

6、m∈Z使得a=mb,此時(shí)稱b整除a。記為b

7、a,還稱b為a的因數(shù)(因子)，a叫作b的倍數(shù)。如果不存在整數(shù)m,使得a=mb,則稱b不能整除a或a不能被b整除，記為b

8、a。模運(yùn)算給定任意一個(gè)正整數(shù)n和任意整數(shù)a，如果將n除a，則得到整數(shù)商q和整數(shù)余數(shù)r，且它們之間滿足以下關(guān)系：其中是小于或等于x的最大整數(shù)。r記為：r＝amodn如果amodn=bmodn，稱整數(shù)a和b模n同余，記為：a≡bmodn模運(yùn)算的性質(zhì)如果n

9、(a-b)，那么a≡bmodna≡bmodn隱含b≡amodna≡bmodn和b≡cmodn隱含a≡cmodn模算術(shù)運(yùn)算(

10、modn)運(yùn)算將所有的整數(shù)映射到{0,1,…,n-1}組成的集合，可以在該集合上進(jìn)行算術(shù)運(yùn)算，稱為模算術(shù)，模算術(shù)有如下性質(zhì)：[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)x(bmodn)]modn=(axb)modn定義：比n小的非負(fù)整數(shù)集合Zn：Zn={0,1,…,n-1}，稱該集合為模n的剩余類。如果a和n互素，那么a乘以Zn中的所有元素再模n，將得到和Zn相同的集合。素?cái)?shù)(PrimeNumbers)一個(gè)大于1的整數(shù)，如果它的正因數(shù)只有

11、1和它本身，就叫做質(zhì)數(shù)（素?cái)?shù)），否則就叫做合數(shù)。eg.2,3,5,7素?cái)?shù)，4,6,8,9,10不是素?cái)?shù)在數(shù)論中具有重要的地位小于200的素?cái)?shù)有:235711131719232931374143475359616771737983899