資源描述：
《第8章 公鑰密碼學》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、公鑰密碼學張原西北工業(yè)大學電子信息學院內(nèi)容提要公開密鑰密碼算法的基本思想公開密鑰密碼算法的數(shù)學基礎一些經(jīng)典算法對稱算法的不足密鑰管理的困難：傳統(tǒng)密鑰管理：兩兩分別用一個密鑰時，則n個用戶需要C(n,2)=n(n-1)/2個密鑰，當用戶量增大時，密鑰空間急劇增大。如:n=100時，C(100,2)=4,995n=5000時，C(5000,2)=12,497,500密鑰發(fā)布的困難：密鑰必須通過某一信道協(xié)商，對這個信道的安全性的要求比正常的傳送消息的信道的安全性要高數(shù)字簽名的問題傳統(tǒng)加密算法無法實現(xiàn)抗抵賴的需求。對稱算法的優(yōu)點：速度快公鑰
2、密碼的起源公鑰密碼又稱為雙鑰密碼和非對稱密碼，是1976年由Diffie和Hellman在其“密碼學新方向”一文中提出的，見劃時代的文獻：W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公鑰算法是由Rivest,Shamir和Adleman在1978年提出來的,見CommunitionsoftheACM.Vol.21.No.2.Feb.197
3、8,PP.120-126公開密鑰密碼的重要特性基于公開密鑰的加密過程用公鑰密碼實現(xiàn)保密用戶擁有自己的密鑰對(KU,KR)公鑰KU公開,私鑰KR保密A?B:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X))=X基于公開密鑰的鑒別過程用公鑰密碼實現(xiàn)鑒別條件：兩個密鑰中任何一個都可以用作加密而另一個用作解密鑒別（不提供保密）：A?ALL:Y=DKRa(X)ALL：EKUa(Y)=EKUa(DKRa(X))=X鑒別+保密：A?B：Z=EKUb(DKRa(X))B：EKUa(DKRb(Z))=X公鑰密鑰的應用范圍加密/解密數(shù)字簽
4、名(身份鑒別)密鑰交換：交換會話密鑰基本要求和思想涉及到各方：發(fā)送方、接收方、攻擊者涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文公鑰算法的條件：產(chǎn)生一對密鑰是計算可行的已知公鑰和明文，產(chǎn)生密文是計算可行的接收方利用私鑰來解密密文是計算可行的對于攻擊者，利用公鑰來推斷私鑰是計算不可行的已知公鑰和密文，恢復明文是計算不可行的(可選)加密和解密的順序可交換思想：陷門單向函數(shù)單向陷門函數(shù)是滿足下列條件的函數(shù)f：給定x，計算y=fk(x)是容易的；給定y，計算x使x=fk-1(y)是不可行的。存在k，已知k時，對給定的任何y，若相應的x存在，則計算x使
5、x=fk-1(y)是容易的。公鑰密碼基于的數(shù)學難題背包問題大整數(shù)分解問題（TheIntegerFactorizationProblem,RSA體制）離散對數(shù)問題有限域的乘法群上的離散對數(shù)問題(TheDiscreteLogarithmProblem,ElGamal體制）定義在有限域的橢圓曲線上的離散對數(shù)問題（TheEllipticCurveDiscreteLogarithmProblem,類比的ElGamal體制）內(nèi)容提要公開密鑰密碼算法的基本思想公開密鑰密碼算法的數(shù)學基礎一些經(jīng)典算法數(shù)的整除性設Z為全體整數(shù)的集合，若b≠0且a,b,
6、m∈Z使得a=mb,此時稱b整除a。記為b
7、a,還稱b為a的因數(shù)(因子)，a叫作b的倍數(shù)。如果不存在整數(shù)m,使得a=mb,則稱b不能整除a或a不能被b整除，記為b
8、a。模運算給定任意一個正整數(shù)n和任意整數(shù)a，如果將n除a，則得到整數(shù)商q和整數(shù)余數(shù)r，且它們之間滿足以下關系：其中是小于或等于x的最大整數(shù)。r記為：r＝amodn如果amodn=bmodn，稱整數(shù)a和b模n同余，記為：a≡bmodn模運算的性質(zhì)如果n
9、(a-b)，那么a≡bmodna≡bmodn隱含b≡amodna≡bmodn和b≡cmodn隱含a≡cmodn模算術運算(
10、modn)運算將所有的整數(shù)映射到{0,1,…,n-1}組成的集合，可以在該集合上進行算術運算，稱為模算術，模算術有如下性質(zhì)：[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)x(bmodn)]modn=(axb)modn定義：比n小的非負整數(shù)集合Zn：Zn={0,1,…,n-1}，稱該集合為模n的剩余類。如果a和n互素，那么a乘以Zn中的所有元素再模n，將得到和Zn相同的集合。素數(shù)(PrimeNumbers)一個大于1的整數(shù)，如果它的正因數(shù)只有
11、1和它本身，就叫做質(zhì)數(shù)（素數(shù)），否則就叫做合數(shù)。eg.2,3,5,7素數(shù)，4,6,8,9,10不是素數(shù)在數(shù)論中具有重要的地位小于200的素數(shù)有:235711131719232931374143475359616771737983899
