1、第三章第三章 公鑰密碼技術公鑰密碼技術 第三章第三章 公鑰密碼技術公鑰密碼技術 1 11. 公鑰密碼的概念 2. 公鑰密碼學的理論基礎 3. 公鑰密碼算法 4. 密鑰交換 5. 公鑰密碼算法的應用 提出公鑰密碼的動因提出公鑰密碼的動因1. 密鑰分配問題。使用對稱加密算法的通信雙方要進行加密通信時，需要通過秘密的安全信道協商加密密鑰，而這種安全信道如何實現呢？機械階段 2. 數字簽名問題。信息的電子化對密碼學提出了新的要求：電子報文和電子文件需要一種與書面材料中使用的簽名等效的認證手段。 公鑰密碼的初始化階段公鑰密碼的初始化階段加密通信階段加密通信階段1. 公鑰密碼的概念 2. 公鑰密碼學的理論

2、基礎 3. 公鑰密碼算法 4. 密鑰交換 5. 公鑰密碼算法的應用 第三章第三章 公鑰密碼技術公鑰密碼技術 2 2計算復雜度與計算復雜度與公鑰密碼公鑰密碼 計算復雜度 P問題和NP完全問題 密碼與計算復雜度的關系 單向陷門函數單向陷門函數單向陷門函數的數學問題單向陷門函數的數學問題1.分解整數問題。2.離散對數問題。 3.RSA問題。 1. 公鑰密碼的概念 2. 公鑰密碼學的理論基礎 3. 公鑰密碼算法 4. 密鑰交換 5. 公鑰密碼算法的應用 第三章第三章 公鑰密碼技術公鑰密碼技術 3 3公開密鑰算法公開密鑰算法公鑰算法的種類很多，具有代表性的三種密碼：v 基于離散對數難題（DLP）的算法體

3、制，例如Diffie-Hellman 密鑰交換算法；v 基于整數分解難題（IFP）的算法體制，例如RSA算法；v 基于橢圓曲線離散對數難題（ECDLP）的算法體制；RSARSA算法算法麻省理工學院的Ron Rivest, Adi Shamir和Len Adleman于1977年研制，并于1978年首次發表；RSA是一種分組密碼，其理論基礎是一種特殊的可逆模冪運算，其安全性基于分解大整數的困難性；既可用于加密，又可用于數字簽名，已得到廣泛采用；RSA已被許多標準化組織(如ISO、ITU、IETF和SWIFT等)接納；RSA-155(512 bit), RSA-140于1999年分別被分解；Eul

4、er Euler 函數函數 歐拉函數 (Eulers totient function)，記為(n)，表示小于n而且與n互素的正整數個數； 對于任一素數p，(p)=p-1; 對于兩個不同的素數p和q，若n=pq， 則(n)= (pq) (p)(q)(p-1)(q-1)；Euler Euler 函數舉例函數舉例 設設p=3, q=5, p=3, q=5, 那么那么 n=pn=pq=15q=15；1 1）小于）小于1515而且與而且與1515互素的正整數是：互素的正整數是： 1 1，2 2，4 4，7 7，8 8，1111，1313，1414 因此，因此， （1515）8 8；2 2）（1515）

5、= =（3-13-1）* *（5-15-1）=8=8歐拉定理歐拉定理 對于任何互素的整數a和n， (mod n)，或者寫作 a(mod n) 給定兩個素數p和q，以及整數n=pq，和m，其中0mn，則 mod n mod n1)(na1)(nammmqpn1)1)(1(1)(mmmqpknk1)1)(1(1)(RSARSA算法的描述算法的描述 對于明文分組M和密文分組C，加密解密形式分別為：C = Me mod nM = Cd mod n = (Me)d mod n = Med mod n 因此，公鑰 KU=e,n,私鑰 KR=d,n,公鑰算法必須滿足: 1）有可能找到e、d、n的值，使得對所

6、有Mn有Med =M mod n；2）對于所有Mn，要計算Me和Cd相對簡單；3）給定e和n時，判斷出d是不可行的；RSARSA算法的描述算法的描述 如何找到：？參考歐拉定理可以得到：ed= k(n)+1也就是說：nMMMqpknkmod1)1)(1(1)()(mod1ned)(mod1nednMMedmodRSARSA算法的實現算法的實現 實現的步驟如下：Bob為實現者 (1) Bob尋找出兩個大素數p和q (2) Bob計算出n=pq 和(n)=(p-1)(q-1) (3) Bob選擇一個隨機數e (0e (n)，滿足(e,(n)=1 (4) Bob使用輾轉相除法計算d=e-1mod(n)

7、 (5) Bob在目錄中公開n和e作為公鑰 密碼分析者攻擊RSA體制的關鍵點在于如何分解n。若分解成功使n=pq，則可以算出(n)（p-1)(q-1)，然后由公開的e，解出秘密的dRSARSA算法舉例算法舉例 設 p=7, q=17, n=7*17=119; 參數T=n=119; (n)=(7-1)(17-1)=96; 選擇e=5, gcd(5,96)=1; 計算d, d*e =1 mod 96; d=77; 因為7753854961設:明文m=19 加密：（19）5 mod 119 = 66 解密：（66）77 mod 119 = 19RSARSA算法的安全性分析算法的安全性分析 密碼分析者

8、攻擊RSA體制的關鍵在于分解n,若分解成功使n=pq，則可以算出(n)（p-1)(q-1)，然后由公開的e，解出秘密的d; 若使RSA安全，p與q必為足夠大的素數，使分析者沒有辦法在多項式時間內將n分解出來,建議選擇p和q大約是100位的十進制素數,模n的長度要求至少是512比特;RSARSA算法的安全性分析算法的安全性分析 EDI攻擊標準使用的RSA算法中規定n的長度為512至1024比特位之間，但必須是128的倍數; 國際數字簽名標準ISO/IEC 9796中規定n的長度位512比特位; 為了提高加密速度，通常取e為特定的小整數,如EDI國際標準中規定 e2161;ISO/IEC9796中

9、甚至允許取e3;這時加密速度一般比解密速度快10倍以上;RSARSA算法的安全性分析算法的安全性分析 為了抵抗現有的整數分解算法，對RSA模n的素因子p和q還有如下要求： (1) |p-q|很大，通常 p和q的長度相同； (2) p-1 和q-1分別含有大素因子p1和q1； (3) P1-1和q1-1分別含有大素因子p2和q2； (4) p+1和q+1分別含有大素因子p3和q3；橢圓曲線密碼編碼學橢圓曲線密碼編碼學ECCECC1985年Miller,Koblitz 獨立提出y2+axy+by=x3+cx2+dx+e表示曲線上的點連同無窮遠點O的集合加法:若曲線三點在一條直線上,則其和為O；倍數

10、:一個點的兩倍是它的切線與曲線的另一個交點；橢圓曲線上的加法規則橢圓曲線上的加法規則 加法公式加法公式: :O 作為加法的單元，O=-O，P+O=P如果P=(x,y)，則P+(x,-y)=O，(x,-y)點是P的負點，記為-P,而且(x,-y)也在EP(a,b)中如果P=(x1,y1)，Q=(x2,y2)，則 P+Q=(x3,y3)為x3=2-x1-x2 (mod p)y3=(x1-x3)-y1 (mod p)其中，如果PQ，則 = (y2-y1)/(x2-x1) 如果P=Q，則 = (3x12+a)/(2y1)橢圓曲線示例橢圓曲線示例橢圓曲線上的加法: P + Q = -R 橢圓曲線上一點的

11、2倍: Q+Q=-S 有限域上的橢圓曲線有限域上的橢圓曲線有限域上的橢圓曲線定義如下：y2x3+ax+b (mod p) p是素數,a,b為非負整數，且滿足4a3+27b2 (mod p) 0 針對所有的0= x p，可以求出有效的y，得到曲線上的點 (x,y)，其中x,y p。曲線記為EP(a,b),EP(a,b)中也包括O點例如，令P=23，a=b=1，橢圓曲線為y2x3+x+1，4132712(mod 23)=8 0滿足模23橢圓群的條件橢圓曲線上的密鑰交換橢圓曲線上的密鑰交換1）雙方選擇EP(a,b)以及EP(a,b)的一個元素G,使得nG=0的最小n值是一個非常大的素數；2）A選擇私

12、鑰Xn,計算公鑰PA=XG；3）B選擇私鑰Yn,計算公鑰PB=YG； 4）A計算秘密密鑰:K=X(PB)=XYG5）B計算秘密密鑰:K=Y(PA)=YXG=XYG因此，雙方獲得了一個共享會話密鑰(XYG)橢圓曲線上的密鑰交換攻擊橢圓曲線上的密鑰交換攻擊雙方選擇EP(a,b)以及EP(a,b)的一個元素G,使得G的階n是一個大素數A選擇私鑰Xn,計算公鑰PA=XG, AB: PAE截獲PA,選私鑰Z,計算PE=ZG,冒充AB:PEB選擇私鑰Yn,計算公鑰PB=YG, BA: PBE截獲PB,冒充BA: PEA計算: XPE = XZGB計算: YPE = YZGE計算: ZPA=ZXG, ZPB

13、 =ZYGvE無法計算出XYGvE永遠必須實時截獲并冒充轉發,否則會被發現.橢圓曲線加密橢圓曲線加密/ /解密解密1）雙方選擇橢圓群EP(a,b)以及EP(a,b)的一個元素G,使得nG=0的最小n值是一個非常大的素數；2）A選擇私鑰Xn,計算公鑰PA=XG；3）B選擇私鑰Yn,計算公鑰PB=YG； 4）A若想加密和發送報文Pm給B，選擇隨機數k，并產生一對點組成的密文Cm=kG,Pm+kPB；5）B解密密文， Pm+kPB-YkG Pm+kYG- YkG= Pm除了A，無人知道k，因此無法破譯兩類加密算法比較兩類加密算法比較保密密鑰算法保密密鑰算法RSA 算法算法橢圓曲線算法橢圓曲線算法40

14、 位56 位400 位64 位512 位80 位768 位90 位1024 位160 位112 位1792 位195 位120 位2048 位210 位128 位2304 位256 位1. 公鑰密碼的概念 2. 公鑰密碼學的理論基礎 3. 公鑰密碼算法 4. 密鑰交換 5. 公鑰密碼算法的應用 第三章第三章 公鑰密碼技術公鑰密碼技術 4 4Diffie-HellmanDiffie-Hellman密鑰交換算法密鑰交換算法 若用戶A和用戶B希望交換一個密鑰，如何進行？1）全局公開參數：一個素數q和其一個原根a；2）用戶A選擇一個隨機數XAq，計算YA=aXA mod q，YA公開；3）用戶B選擇一

15、個隨機數XBq，計算YB=aXB mod q ，YB公開；4）用戶A計算密鑰K=(YB)XAmod q;5）用戶B計算密鑰K=(YA)XBmod q;Diffie-HellmanDiffie-Hellman密鑰交換算法密鑰交換算法證明：K = (YB)XA mod q = (aXB mod q)XA mod q =(aXB)XA mod q =a XBXA mod q =(aXA)XB mod q =(aXA mod q)XB mod q =(YA)XB mod q攻擊分析：公開數據 q，a，YA和YB，若想攻擊用戶B的秘密密鑰，攻擊者必須計算 XB = inda,q(YB)；安全性分析：計算模一個素數的指數相對容易，計算離散對數卻很難；Diffie-HellmanDiffie-Hellman密鑰交換算法舉例密鑰交換算法舉例1）密鑰交換基于素數q=97和q的一個原根a=5；2）A和B分別選擇密鑰 XA=36和XB=58，并分別計算其公開密鑰YA = 536= 50 mod 97YB = 558= 44 mod 973）交換了公開密鑰后，每人計算共享的秘密密鑰如下K= (Y