【正文】 )、(2)兩條的稱為單向函數(shù)；第(3)條稱為陷門性，δ 稱為陷門信息。,第五章 密碼學的應用,78,一、 RSA算法概述,2*. 當用陷門函數(shù)f作為加密函數(shù)時，可將f公開，這相當于公開加密密鑰。此時加密密鑰便稱為公開密鑰，記為Pk。 f函數(shù)的設計者將δ 保密，用作解密密鑰，此時δ 稱為秘密鑰匙，記為Sk。由于加密函數(shù)是公開的，任何人都可以將信息x加密成y=f(x)，然后送給函數(shù)的設計者（可以通過不安全信道傳送）；由于設計者擁有Sk，他自然可以解出x=f1(y)。 3*.單向陷門函數(shù)的第(2)條性質表明竊聽者由截獲的密文y=f(x)推測x是不可行的。,第五章 密碼學的應用,79,DiffieHellman 密鑰交換算法,Diffie 和Hellman 并沒有給出公鑰密碼實例，也既沒能找出一個真正帶陷門的單向函數(shù)。然而，他們給出單向函數(shù)的實例，并且基于此提出DH密鑰交換算法。這個算法是基于有限域中計算離散對數(shù)的困難性問題之上的：對任意正整數(shù)x，計算gx 是容易的；但是已知g和y求x使y= gx，是計算上幾乎不可能的。這稱為有限域上的離散對數(shù)問題。公鑰密碼學中使 最廣泛的有限域為素域FP 。DH密鑰交換算法擁有美國和加拿大的專利。,第五章 密碼學的應用,80,DH密鑰交換協(xié)議：A和B協(xié)商一個大素數(shù)p和大整數(shù)g，1gp，g最好是FP中的本原元，即gx mod p可生成1~p1中的各整數(shù)，例：2是11的本原元。p和g公開。 當A和B按如下步驟進行保密通信： (1)A取大的隨機數(shù)x，并計算 X= gx (mod P) (2)B選取大的隨機數(shù)y，并計算Y = gy (mod P) (3)A將X傳送給B；B將Y傳送給A。 (4)A計算K=YX(mod P)；B計算K ? ＝Xy (mod P),易見，K=K ? =g xy (mod P)。 A和B已獲得了相同的秘密值K。雙方以K作為加解密鑰以傳統(tǒng)對稱密鑰算法進行保密通信。,第五章 密碼學的應用,81,公開密鑰算法的主要特點如下： １）用加密密鑰PK對明文A加密后得到密文，再用解密密鑰SK對密文解密，即可恢復出明文A。 DSK(EPK(A))＝A ２）加密密鑰不能用來解密，即： DPK(EPK(A))≠A ；DSK(ＥSK(A))≠A ３）用SK加密的信息只能用PK解密；用PK加密的信息只能用SK解密。 ４）從已知的PK不可能推導出SK。 ５）加密和解密的運算可對調：EPK(DSK(A))＝A,第五章 密碼學的應用,82,一、RSA算法概述,1978年，美國麻省理工學院(MIT)的研究小組成員：李維斯特(Rivest)、沙米爾(Shamir)、艾德曼(Adleman)提出了一種基于公鑰密碼體制的優(yōu)秀加密算法——RSA算法。 RSA算法是一種分組密碼體制算法，它的保密強度是建立在具有大素數(shù)因子的合數(shù)，其因子分解是困難的。是否是NP問題尚未確定。 RSA得到了世界上的最廣泛的應用，ISO在1992年頒布的國際標準X.509中,將RSA算法正式納入國際標準。1999年美國參議院已通過了立法，規(guī)定電子數(shù)字簽名與手寫簽名的文件、郵件在美國具有同等的法律效力。,公開密鑰算法,83,數(shù)論知識簡介,互素：若gcd(a,b)=1，則整數(shù)a和b互素。 歐拉數(shù)：設m是正整數(shù)，稱1，2，…，m中與m互素的數(shù)的個數(shù)為m的歐拉數(shù)，記 計算方法： （1）若p是素數(shù)，則 （2）若 是兩個素數(shù)，則,84,歐拉定理：設n=p.q ,其中 是兩個素數(shù),85,數(shù)論知識簡介,模運算性質： 同余 模運算滿足自反性、對稱性、傳遞性； a=a mod n； 若a=b mod n，則b=a mod n； 若a=b mod n，b=c mod n，則a=c mod n 若a mod n=b mod n，則(ab)mod n=0； [(a mod n) +(b mod n)]mod n=(a + b) mod n； ； * * ； 例：152 mod 12 =(3*3) mod 12=9,86,Euler定理：a φ(n) mod n =1 推論：若a與n互素，則a與a φ(n)1 互為逆元。 例：a=4，n=7， φ(7)=6， a φ(7)1 =45=1024 所以，4和1024在模7下互為逆元。 驗證：4x1024 mod7 =1,87,二、RSA算法的實現(xiàn),公開密鑰算法,RSA加密算法的過程 1．取兩個隨機大素數(shù)p和q（保密） 2．計算公開的模數(shù)r=p*q(公開) 3．計算秘密的歐拉函數(shù)?(r) =（p1)*(q1)（保密），丟棄p和q，不要讓任何人知道。 4．隨機選取整數(shù)e,滿足 gcd(e, ?(r))=1(公開e加密密鑰) 5．計算d滿足de≡1(mod ?(n))(保密d解密密鑰) 6．將明文x（按模為r自乘e次冪以完成加密操作，從而產(chǎn)生密文y（x、y值在0到r1范圍內）。y=xe mod r 7．解密：將密文y按模為r自乘d次冪。 x=yd mod r,88,二、RSA算法的實現(xiàn),公開密鑰算法,大數(shù)的運算 上百位大數(shù)之間的運算是實現(xiàn)RSA算法的基礎,因此程序設計語言本身提供的加減乘除及取模算法都不能使用，否則會產(chǎn)生溢出，必須重新編制算法。在編程中要注意進位和借位，并定義幾百位的大數(shù)組來存放產(chǎn)生的大數(shù)。,89,素數(shù)的檢驗,素數(shù)的產(chǎn)生 在 2到X的區(qū)間中，隨機選擇一個值為素數(shù)的概率近似等于?(X)/(X1)?？梢宰C明，在找到一個素數(shù)之前，平均要進行(X1)/ ?(X)≈LN(X)次實驗。 目前，適用于RSA算法的最實用的辦法是概率測試法。該法的思想是隨機產(chǎn)生一個大奇數(shù)，然后測試其是否滿足條件，如滿足，則該大奇數(shù)可能是素數(shù)，否則是合數(shù)。素數(shù)定理說明素數(shù)有無窮多個，同時也說明通過隨機產(chǎn)生一個大奇數(shù)來判斷其素性是具有實用性的。,90,公開密鑰算法,關于素數(shù)的分布 1 100 25 101 200 21 201 300 16 301 400 16 401 500 17 501 600 14 601 700 16 701 800 14 801 900 15 901 1000 14,素數(shù)定理：當X變得很大時，從2到X區(qū)間的素數(shù)數(shù)目?(X)與X/ln(X)的比值趨近于1，即,?(X),X/ln(X),= 1,lim x??,X ?(X) X/ln(X),?(X) X/ln(X),1000 168 145 1.159 10,000 1,229 1,086 1.132 100,000 9,592 8,686 1.104 1,000,000 78,498 72,382 1.084,10,000,000 664,579 620,421 1.071 100,000,000 5,761,455 5,428,681 1.061 1,000,000,000 50,847,478 48,254,942 1.054,91,高次冪剩余的運算,公開密鑰算法,要計算 gn mod p，因g、n、p都是大數(shù)而不能采用先高次冪再求剩余的方法來處理，而要采用平方取模的算法，即每一次平方或相乘后，立即取模運算。 歐幾里德算法 歐幾里德算法可以迅速地找出給定的兩個整數(shù)a和b的最大公因數(shù) gcd（a，b），并可判斷a與b是否互素，因此該算法可用來尋找加密密鑰和解密密鑰。,92,RSA 的安全性,公開密鑰算法,依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能證明。不管怎樣，分解n是最顯然的攻擊方法。 1994年4月26日，美國各大媒體報道：由RSA發(fā)明人在17年前出的129位數(shù)字已被因子分解，并破解了附帶的密語： The magic words are squeamish ossifrage. 目前，已能分解140位十進制的大素數(shù)。因此，模數(shù)n必須選大一些。 RSA最快的情況也比DES慢上100倍，無論是軟件還是硬件實現(xiàn)。速度一直是RSA的缺陷。一般只用于少量數(shù)據(jù)加密。,93,RSA算法的脆弱性,公開密鑰算法,不能證明RSA密碼破譯等同于大數(shù)因子分解 速度問題 提高p?q將使開銷指數(shù)級增長 至少有9個明文，加密后不變，即me mod n=m 普通用戶難于選擇p、q。對p、q的基本要求： p、q不相同，即不要太接近，又不能差別太大 pq1都有大素數(shù)因子，增加猜測φ(r) 難度 gcd( p1,q1)應當小,94,RSA算法的脆弱性,公開密鑰算法,p、q選擇不當，則變換周期性、封閉性而泄密 例：p=17，q=11，e=7，則n=187。設m=123，則 C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文m經(jīng)過4次加密，恢復成明文。 總之，RSA對用戶要求太苛刻，密鑰不能常更換。,95,其它公鑰密碼體制,背包體制 1978年提出 5年后被 Shamir破解 ElGamal 體制 1985年 基于有限域上計算離散對數(shù)難解性，已用于DSS(數(shù)字簽名標準） 例：3x mod 17=5，解得：x=6 3x mod 13=7， 無解 橢圓曲線體制(ECC) 1985年 基于離散對數(shù) 優(yōu)點：安全性高；密鑰短；靈活性好。 同等安全下的密鑰長度： RSA:512 1024 2048 21000 ECC:106 160 211 600,