第4章公開密鑰密碼

1、第4章 公開密鑰密碼4.1 公鑰密碼概述l公開密鑰算法中用作加密的密鑰不同于用作解密的密鑰，而且解密密鑰不能根據(jù)加密密鑰計(jì)算出來（至少在合理假定的長(zhǎng)時(shí)間內(nèi)），所以加密密鑰能夠公開，每個(gè)人都能用加密密鑰加密信息，但只有解密密鑰的擁有者才能解密信息。l在公開密鑰算法系統(tǒng)中，加密密鑰叫做公開密鑰（簡(jiǎn)稱公鑰），解密密鑰叫做秘密密鑰（私有密鑰，簡(jiǎn)稱私鑰）。l公開密鑰算法主要用于加密/解密、數(shù)字簽名、密鑰交換。 討論議題討論議題l為什么要設(shè)計(jì)公鑰密碼算法密鑰分配l公鑰密碼體制概述及其應(yīng)用l公鑰密碼算法的實(shí)現(xiàn)Diffie-Hellman密鑰交換算法背包算法RSA算法EIGamal算法橢圓曲線密碼算法ECC1

2、. 為什么要設(shè)計(jì)公鑰密碼體制密鑰分配（Key Distribution）保密通信雙方需共享密鑰共享密鑰要經(jīng)常更換A選擇密鑰并手工傳遞給B第三方C選擇密鑰分別手工傳遞給A,B用A,B原有共享密鑰傳送新密鑰與A,B分別有共享密鑰的第三方C傳送新密鑰給A和/或BN個(gè)用戶集需要N(N-1)/2個(gè)共享密鑰密鑰分發(fā)中心(Key Distribution Center)密鑰分發(fā)中心（KDC）l每個(gè)用戶與KDC有共享密鑰(Master Key)lN個(gè)用戶,KDC只需分發(fā)N個(gè)Master Keyl兩個(gè)用戶間通信用會(huì)話密鑰(Session Key)用戶必須信任KDCKDC能解密用戶間通信的內(nèi)容 （1）密鑰管理量的

3、困難）密鑰管理量的困難 傳統(tǒng)密鑰管理：兩兩分別用一對(duì)密鑰時(shí)，則傳統(tǒng)密鑰管理：兩兩分別用一對(duì)密鑰時(shí)，則n個(gè)用個(gè)用戶需要戶需要C(n,2)=n(n-1)/2個(gè)密鑰，當(dāng)用戶量增大時(shí)，密個(gè)密鑰，當(dāng)用戶量增大時(shí)，密鑰空間急劇增大。如鑰空間急劇增大。如: n=100 時(shí)，時(shí)， C(100,2)=4,995 n=5000時(shí)，時(shí)， C(5000,2)=12,497,500 （2）數(shù)字簽名的問題）數(shù)字簽名的問題 傳統(tǒng)加密算法無法實(shí)現(xiàn)抗抵賴的需求。傳統(tǒng)加密算法無法實(shí)現(xiàn)抗抵賴的需求。問題的提出問題的提出起源l公鑰密碼又稱為雙鑰密碼和非對(duì)稱密碼，是1976年由Diffie和Hellman在其“密碼學(xué)新方向”一文中提出

4、的，見劃時(shí)代的文獻(xiàn)： W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654lRSA公鑰算法是由Rivest,Shamir和Adleman在1978年提出來的, 見 Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126公開密鑰密碼的重要特性加密與解密由不同的密鑰完成加密: mc: c = EK(m)解密: cm: m =

5、 DB(c) = DB(EK(m)知道加密算法,從加密密鑰得到解密密鑰在計(jì)算上是不可行的兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密(不是必須的)m = DB(EK(m) = EK(DB(m)2. 公鑰密碼體制的應(yīng)用概述公鑰加密算法l傳統(tǒng)加密過程加密和解密使用相同密鑰加密和解密使用相同密鑰明文明文明文明文密文密文公鑰加密算法l公鑰密碼算法加密和解密使用加密和解密使用不同密鑰不同密鑰明文明文明文明文密文密文 用公鑰密碼實(shí)現(xiàn)保密用公鑰密碼實(shí)現(xiàn)保密BBBBkkkkk )kkAliceBobcEmBobDcDEmm用戶擁有密鑰對(duì)（k,公鑰 公開，私鑰 保密： （ ）： （ ）（ ）基于公開密鑰的加

6、密過程 用公鑰密碼實(shí)現(xiàn)用公鑰密碼實(shí)現(xiàn)認(rèn)證認(rèn)證AAAAkkkkk )kkAliceBobcEmBobDcDEmm用戶擁有密鑰對(duì)（k,公鑰 公開，私鑰 保密： （ ）： （ ）（ ）基于公開密鑰的認(rèn)證過程 用公鑰密碼實(shí)現(xiàn)用公鑰密碼實(shí)現(xiàn)保密與認(rèn)證保密與認(rèn)證BAABABABBAkkkkkkkkkkk )kkAliceBobcEDmBobDDDEDmm用戶擁有密鑰對(duì)（k,公鑰 公開，私鑰 保密： （ ）： （E (c)） （E (c)） （E (（ ）)） 公鑰密鑰的應(yīng)用范圍加密加密/解密解密數(shù)字簽名數(shù)字簽名(身份鑒別身份鑒別)密鑰交換密鑰交換算法加/解密數(shù)字簽名密鑰交換RSA是是是Dieffie-He

7、llman否否是DSS否是否3. 公鑰密碼算法基本思想和要求l涉及到各方：發(fā)送方、接收方、攻擊者l涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文l公鑰算法的條件：產(chǎn)生一對(duì)密鑰是計(jì)算可行的已知公鑰和明文，產(chǎn)生密文是計(jì)算可行的接收方利用私鑰來解密密文是計(jì)算可行的對(duì)于攻擊者，利用公鑰來推斷私鑰是計(jì)算不可行的已知公鑰和密文，恢復(fù)明文是計(jì)算不可行的(可選)加密和解密的順序可交換單向陷門函數(shù)函數(shù)單向陷門函數(shù)函數(shù) 滿足下列條件的函數(shù)滿足下列條件的函數(shù)f f： (1) 給定給定x，計(jì)算，計(jì)算y=f(x)是容易的是容易的 (2) 給定給定y, 計(jì)算計(jì)算x使使y=f(x)是困難的是困難的 (3) 存在存在z，已知，已知z 時(shí)

8、時(shí), 對(duì)給定的任何對(duì)給定的任何y，若相應(yīng)的，若相應(yīng)的x存存 在，則計(jì)算在，則計(jì)算x使使y=f(x)是容易的是容易的所謂計(jì)算所謂計(jì)算x= x= f-1(Y)(Y)困難是指計(jì)算上相當(dāng)復(fù)雜，已無困難是指計(jì)算上相當(dāng)復(fù)雜，已無實(shí)際意義實(shí)際意義單向陷門函數(shù)說明單向陷門函數(shù)說明僅滿足僅滿足(1)、(2)兩條的稱為單向函數(shù)；第兩條的稱為單向函數(shù)；第(3)條稱為陷條稱為陷門性，門性，z 稱為陷門信息稱為陷門信息當(dāng)用陷門函數(shù)當(dāng)用陷門函數(shù)f作為加密函數(shù)時(shí)，可將作為加密函數(shù)時(shí)，可將f公開，這相當(dāng)公開，這相當(dāng)于公開加密密鑰，此時(shí)加密密鑰便稱為公開鑰，記為于公開加密密鑰，此時(shí)加密密鑰便稱為公開鑰，記為Pkf函數(shù)的設(shè)計(jì)者將

9、函數(shù)的設(shè)計(jì)者將z保密，用作解密密鑰，此時(shí)保密，用作解密密鑰，此時(shí)z稱為秘稱為秘密鑰匙，記為密鑰匙，記為Sk。由于設(shè)計(jì)者擁有。由于設(shè)計(jì)者擁有Sk，他自然可以解，他自然可以解出出x=f-1(y)單向陷門函數(shù)的第單向陷門函數(shù)的第(2)條性質(zhì)表明竊聽者由截獲的密文條性質(zhì)表明竊聽者由截獲的密文y=f(x)推測(cè)推測(cè)x是不可行的是不可行的 公鑰密碼基于的數(shù)學(xué)難題公鑰密碼基于的數(shù)學(xué)難題 背包問題背包問題 大 整 數(shù) 分 解 問 題 （大 整 數(shù) 分 解 問 題 （ T h e I n t e g e r T h e I n t e g e r Factorization Problem,RSAFactoriz

10、ation Problem,RSA體制）體制） 有限域的乘法群上的離散對(duì)數(shù)問題有限域的乘法群上的離散對(duì)數(shù)問題 (The Discrete Logarithm Problem,(The Discrete Logarithm Problem, ElGamal ElGamal體制）體制） 橢圓曲線上的離散對(duì)數(shù)問題（橢圓曲線上的離散對(duì)數(shù)問題（The EllipticThe Elliptic Curve Discrete Logarithm Problem, Curve Discrete Logarithm Problem, 類比的類比的ElGamalElGamal體制）體制）一、背包問題l背包問題：已

11、知一長(zhǎng)度為B的背包，及長(zhǎng)度分別為a1,a2,.,an的n個(gè)物品。假定這些物品的半徑和背包相同，若從這n個(gè)物品中選出若干個(gè)正好裝滿這個(gè)背包?，F(xiàn)在反過來問：究竟是哪些物品？背包問題數(shù)學(xué)描述ii112x011,2,., ,a,.,bniininxba aa求 或 ，使其滿足：其中和 都是整數(shù)背包問題求解NPNP背包問題屬于完備類（問題中難度最大的一類）對(duì)這一問題沒有有效算法11(2,3,., )ijja in12ni但是，如果序列a ,a ,.,a 是超遞增序列：a背包問題有多項(xiàng)式解法超遞增序列背包問題求解方法123456248163243xxxxxxn12n例:已知序列a ,a ,.,a 是超遞增

12、序列：1,2,4,8,.,2求 背包問題的解思路：思路：xi取值只可能為取值只可能為0或者或者1；如果為；如果為0，表示，表示不能裝入對(duì)應(yīng)的物體，否則可以裝入。不能裝入對(duì)應(yīng)的物體，否則可以裝入。超遞增序列背包問題求解方法123456123452481632432481611xxxxxxxxxxx（2）帶入：1116,05（3）因?yàn)樗杂衳（不能選）123451234248161124811xxxxxxxxx（4）帶入：16(1)對(duì)于體積為32的物體，因?yàn)?243，所以x（可以選）1246121xxxxxx（ 5 ） 繼 續(xù) 上 述 過 程 ， 可 得 ： 0MerkleHellman背包公鑰算

13、法122c.nnma ma m1（ 2 ） 利 用 公 鑰 加 密 如 下 ： a1212a ,.,.nnaamm mm（1）選取一組正整數(shù)作為公鑰予以公布是n位0，1明文符號(hào)串。12c.nm mm（3）從密文 求明文等價(jià)于背包問題MerkleHellman背包公鑰算法12明文： m 10110110，m 11001001123456782832aaaaaaa例如：已知: a ， ， 11， 08 71， 51， 43， 6712分別加密得到密文： c2 8 + 1 1 + 8 + 5 1 + 4 3 1 4 1 c2 8 + 3 2 + 7 1 + 4 7 = 1 9 8MerkleHell

14、man背包公鑰算法l問題：如何解密？對(duì)公鑰密碼算法的誤解l公開密鑰算法比對(duì)稱密鑰密碼算法更安全？任何一種算法都依賴于密鑰長(zhǎng)度、破譯密碼的工作量，從抗分析角度，沒有一方更優(yōu)越l公開密鑰算法使對(duì)稱密鑰成為過時(shí)了的技術(shù)？公開密鑰很慢，只能用在密鑰管理和數(shù)字簽名，對(duì)稱密鑰密碼算法將長(zhǎng)期存在l使用公開密鑰加密，密鑰分配變得非常簡(jiǎn)單？事實(shí)上的密鑰分配既不簡(jiǎn)單，也不有效 自從自從19761976年公鑰密碼的思想提出來年公鑰密碼的思想提出來以后，國(guó)際上已經(jīng)提出許多種公鑰密碼以后，國(guó)際上已經(jīng)提出許多種公鑰密碼體制，但比較流行的主要有兩類：一類體制，但比較流行的主要有兩類：一類是基于大整數(shù)因子分解問題的，其中最是

15、基于大整數(shù)因子分解問題的，其中最典型的代表是典型的代表是RSA;RSA;另一類是基于離散對(duì)另一類是基于離散對(duì)數(shù)問題的，比如數(shù)問題的，比如ElGamaLElGamaL公鑰密碼和影公鑰密碼和影響比較大的橢圓曲線公鑰密碼。下面對(duì)響比較大的橢圓曲線公鑰密碼。下面對(duì)這三個(gè)公鑰方法進(jìn)行闡述。這三個(gè)公鑰方法進(jìn)行闡述。一、公鑰密碼4.2 基于大整數(shù)分解的公開密鑰密碼體系l一、大整數(shù)分解問題：已知整數(shù)n，n是兩個(gè)素?cái)?shù)的乘積，即n=q*p，求解p與q的值。l大整數(shù)分解是計(jì)算上的難題，目前還不存在一般性的有效解決算法。lRSA就是基于大整數(shù)分解問題的公開密鑰密碼體制代表算法1. 1. RSA算法概述算法概述 197

16、8年，美國(guó)麻省理工學(xué)院(MIT)的研究小組成員：李維斯特(Rivest)、沙米爾(Shamir)、艾德曼(Adleman)提出了一種基于公鑰密碼體制的優(yōu)秀加密算法RSA算法。 RSA算法是一種分組密碼體制算法，它的保密強(qiáng)度是建立在具有大素?cái)?shù)因子的合數(shù)，其因子分解是困難的。是否是NP問題尚未確定。RSA得到了世界上的最廣泛的應(yīng)用，ISO在1992年頒布的國(guó)際標(biāo)準(zhǔn)X.509中,將RSA算法正式納入國(guó)際標(biāo)準(zhǔn)。1999年美國(guó)參議院已通過了立法，規(guī)定電子數(shù)字簽名與手寫簽名的文件、郵件在美國(guó)具有同等的法律效力。2.數(shù)論知識(shí)簡(jiǎn)介數(shù)論知識(shí)簡(jiǎn)介數(shù)論概念數(shù)論概念: 研究研究“離散數(shù)字集合離散數(shù)字集合”運(yùn)算是運(yùn)算是

17、“+” ,“”例例:整數(shù)整數(shù): 5 + 9 = 14; 5 5 + 9 = 14; 5 3 = 5 + 5 + 5 = 15 3 = 5 + 5 + 5 = 15 多項(xiàng)式多項(xiàng)式: x x2 2+1 + x = x+1 + x = x2 2+x+1; x +x+1; x x x2 2+1 = x+1 = x3 3+x+x l運(yùn)算： （1）模數(shù)運(yùn)算（2）模多項(xiàng)式運(yùn)算l進(jìn)一步運(yùn)算:指數(shù)運(yùn)算,逆運(yùn)算數(shù)論是理解公鑰算法的基礎(chǔ)1 1）運(yùn)算概念）運(yùn)算概念l對(duì)整數(shù) b!=0 及 a , 如果存在整數(shù)如果存在整數(shù) m 使得 a=mb,稱 b 整除 a, 也稱b是a的因子l記作 b|a l例 1,2,3,4,6,

18、8,12,24 整除 24 2 2）整除）整除l素?cái)?shù): 只有因子 1 和自身l1 是一個(gè)平凡素?cái)?shù)l例 2,3,5,7 是素?cái)?shù), 4,6,8,9,10 不是l素多項(xiàng)式或不可約多項(xiàng)式irreducible: l 不可寫成其他因式的乘積l x2+x = x x+1 是非不可約多項(xiàng)式; x3+x+1 是不可約多項(xiàng)式3 3）素?cái)?shù)與不可約多項(xiàng)式）素?cái)?shù)與不可約多項(xiàng)式l200 以內(nèi)的素?cái)?shù):l 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149

19、 151 157 163 167 173 179 181 191 193 197 199 4 4）一些素?cái)?shù)）一些素?cái)?shù)l把整數(shù)n寫成素?cái)?shù)的乘積l分解整數(shù)要比乘法困難l整數(shù) n的素?cái)?shù)分解是把它寫素?cái)?shù)的乘積 eg. 91 = 7 13 ; 3600 = 24 32 52 5 5）素?cái)?shù)分解）素?cái)?shù)分解( (PrimeFactorisation）l整數(shù) a, b 互素是指 它們沒有除1之外的其它因子l8 與15 互素 l8的因子1,2,4,8 l15的因子 1,3,5,15 l1 是唯一的公因子6 6）整數(shù)互素）整數(shù)互素l除法取余運(yùn)算 l同余( congruence) for a = b mod n l如

20、果a,b 除以n,余數(shù)相同leg. 100 = 34 mod 11 lb 叫做a模n的剩余 l通常 0=b=n-1 leg. -12mod7 = -5mod7 = 2mod7 = 9mod7 l可以進(jìn)行整數(shù)運(yùn)算 7 7）模算式）模算式l加法加法 a+b mod n l減法減法 a-b mod n = a+(-b) mod n l乘法乘法 a.b mod n 重復(fù)加法l除法除法 a/b mod n 乘以b的逆元: a/b = a.b-1 mod n 如果n是素?cái)?shù), b-1 mod n 存在 s.t b.b-1 = 1 mod n 例. 2.3=1 mod 5 hence 4/2=4.3=2 mo

21、d 58 8）模算術(shù)運(yùn)算）模算術(shù)運(yùn)算數(shù)論基礎(chǔ)la與b的最大公因數(shù)：gcd（a, b）gcd（20, 24）=4 , gcd（15, 16）=1l如果gcd（a, b）=1 ，稱a與b 互素l模運(yùn)算 moda= q n +r 0rn ; q=a/n ; x 表示小于或等于x的最大整數(shù)a=a/nn + （a mod n） , r = a mod n 如果 （a mod n ）= （b mod n） ，則稱a 與b 模模n同余同余，記為 a b mod n 例如， 23 8 mod 5 , 8 1 mod 7數(shù)論基礎(chǔ)（續(xù)）l模運(yùn)算對(duì)加法和乘法是可交換的、可結(jié)合的、可分配的（a+b） mod n =

22、（a mod n ） + （b mod n） ） mod n（a-b） mod n = （a mod n） （b mod n） ） mod n（ab） mod n = （a mod n ） （b mod n） ） mod n （a （b+c） ） mod n = （ a b） mod n + （a c） mod n） mod nl冪,模運(yùn)算 ma mod n m2 mod n = （mm） mod n = （m mod n ） 2 mod n m4 mod n = （m2 mod n ） 2 mod nm8 mod n = （m2 mod n ）2 mod n ）2 mod n m25 mod

23、 n = （m m8 m16） mod n 數(shù)論基礎(chǔ)（續(xù)）l歐拉函數(shù)(n)n是正整數(shù)， (n)是比n小且與n 互素的正整數(shù)的個(gè)數(shù)(2) = |1| =1(3) = |1, 2| =2 (4) = |1, 3| =2 (5) = |1, 2, 3, 4 | =4 (6) = |1, 5| =4 (7) = |1, 2, 3, 4, 5, 6| =6(10) = |1, 3, 7, 9| =4 (11) = |1, 2,3,4,5,6, 7,8, 9,10| =10 如果p是素?cái)?shù)，則(p)=(p-1), 比如(2), (5)， (11)如果p,q 是素?cái)?shù)，則(pq)=(p)(q) (p-1)(q-

24、1),比如, (10)數(shù)論基礎(chǔ)（續(xù)）例如： m=3, n=10; (10)=4 m(n)=34=81 ; 81 mod 10 = 1 即 81 1 mod 10 34+1 = 243 3 mod 10 (等價(jià)形式等價(jià)形式)歐拉定理歐拉定理 若整數(shù)若整數(shù)m 和和n 互素，則互素，則等價(jià)形式等價(jià)形式nmmn mod 1)(nmn mod 1)(n若m是素?cái)?shù)， gcd （a，m）=1，則am-1 1（mod m）。 或者：若m是素?cái)?shù)，則am mod m=a例：46 mod 7=4096 mod 7=1 mod 7 費(fèi)馬（費(fèi)馬（Fermat）小定理）小定理數(shù)論基礎(chǔ)（續(xù)）數(shù)論基礎(chǔ)（續(xù)）l定理2：給定兩個(gè)

25、素?cái)?shù)p, q , 兩個(gè)整數(shù) n, m ，使得n=pq, 0mn ； 則對(duì)于任意整數(shù)k ，下列關(guān)系成立： m k(n)+1 m mod n4.2.2 RSA4.2.2 RSA算法描述算法描述1取兩個(gè)隨機(jī)大素?cái)?shù)p和q（保密）2計(jì)算公開的模數(shù)n=p*q(n公開)3計(jì)算秘密的歐拉函數(shù)(n) =（p-1)*(q-1)，丟棄p和q，不要讓任何人知道。4隨機(jī)選取整數(shù)e,滿足 gcd(e, (n)=1(公開e加密密鑰)5計(jì)算d滿足de1(mod (n)(保密d解密密鑰) 6加密：將明文x（按模為n自乘e次冪以完成加密操作，從而產(chǎn)生密文y（X、Y值在0到n-1范圍內(nèi)）。 Y=xe mod n7解密：將密文y按模

26、為n自乘d次冪。 X=Yd mod n例例設(shè)設(shè)p=13,q=17,n=pq=13*17=221, (n)=(p-1)(q-1) =12*16 =192, 取取e=71,根據(jù)（擴(kuò)展）歐幾里得算法求根據(jù)（擴(kuò)展）歐幾里得算法求e的逆元的逆元dd=e-1 mod (n)= 71-1 mod 192 =119將將e 與與n公開，而保密公開，而保密p、q及及d。即公鑰是（即公鑰是（e，n） 私鑰是（私鑰是（d，p，q）加密加密 c=me mod n = 571 mod 221 =112解密解密m=cd mod n = 112119 mod 221=5=mRSA舉例：舉例：1選擇選擇p=7,q=17。2計(jì)算

27、計(jì)算n=p*q=119，(n）=(p-1)*(q-1)=96。3選選e=5，因?yàn)椋驗(yàn)?和和96互素?；ニ?。4根據(jù)根據(jù)5d mod 96=1，得，得d=77。5公鑰為公鑰為(5,117),密鑰為密鑰為77。如：明文為如：明文為P=6密文密文: C=Pe mod n = 65 mod 119 =41。解密：解密：P=Cd mod n = 4177 mod 119= 6。RSA: 例例選擇兩個(gè)素?cái)?shù): p=17 & q=11計(jì)算 n = pq =1711=187計(jì)算 (n)=(p1)(q-1) =1610=160選擇 e : gcd(e,160)=1; 其中e=7RSA: 例例1計(jì)算d: de=1

28、mod 160 且d 160 ，則 d=23 （因?yàn)?37=161= 10160+1）公布公鑰KU=7,187保存私鑰KR=23,17,11l如果待加密的消息 M = 88 (注意： 88187)l加密：C = 887 mod 187 = 11 l解密:M = 1123 mod 187 = 88 RSA：例RSA：例lBob選擇 p=885320693， q=238855417， 則可以計(jì)算 n=p*q=211463707796206571， 設(shè)加密系數(shù)為 e=9007，將n和e發(fā)送給Alice。l假設(shè)Alice傳遞的信息是cat。 令a=01 c=03 t=20，則cat=030120=30

29、120。 Alice計(jì)算： c me 301209007 113535859035722866(mod n) 她將c傳給Bob。RSA：例：例lBob已知p和q的值，他用擴(kuò)展歐幾里德算法計(jì)算d： de 1(mod(p-1)(q-1)， 得到 d=116402471153538991 然后Bob計(jì)算： cd 113535859035722866116402471153538991 30120(mod n) 由此他可以得到最初的信息。RSA 算法的性能l速度軟件實(shí)現(xiàn)比DES 慢100倍硬件實(shí)現(xiàn)比DES慢1000倍512位768位1024位加密0.030.050.08解密0.160.480.93簽名

30、0.160.520.97驗(yàn)證0.020.070.08RSA算法的脆弱性算法的脆弱性不能證明不能證明RSA密碼破譯等同于大數(shù)因子分解密碼破譯等同于大數(shù)因子分解速度問題速度問題 提高提高pq將使開銷指數(shù)級(jí)增長(zhǎng)將使開銷指數(shù)級(jí)增長(zhǎng)至少有至少有9個(gè)明文，加密后不變，即個(gè)明文，加密后不變，即me mod n=m普通用戶難于選擇普通用戶難于選擇p、q。對(duì)。對(duì)p、q的基本要求：的基本要求： p、q不相同，即不要太接近，又不能差別太大不相同，即不要太接近，又不能差別太大 p-1、q-1都有大素?cái)?shù)因子，增加猜測(cè)都有大素?cái)?shù)因子，增加猜測(cè)(r) 難度難度 gcd( p-1,q-1)應(yīng)當(dāng)小應(yīng)當(dāng)小P、q選擇不當(dāng)，則變換周

31、期性、封閉性而泄密選擇不當(dāng)，則變換周期性、封閉性而泄密 例：例：p=17，q=11，e=7，則，則n=187。設(shè)。設(shè)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)過經(jīng)過4次加密，恢復(fù)成明文。次加密，恢復(fù)成明文?？傊?，總之，RSA對(duì)用戶要求太苛刻，密鑰不能常更換。對(duì)用戶要求太苛刻，密鑰不能常更換。RSARSA算法的特點(diǎn)之一是數(shù)學(xué)原理簡(jiǎn)單、在工算法的特點(diǎn)之一是數(shù)學(xué)原理簡(jiǎn)單、在工程應(yīng)用中比較易于實(shí)現(xiàn)，但它的單位安全程應(yīng)用中比較易于實(shí)現(xiàn)，但它的單位安全強(qiáng)度相對(duì)較低。

32、目前用國(guó)際上公認(rèn)的對(duì)于強(qiáng)度相對(duì)較低。目前用國(guó)際上公認(rèn)的對(duì)于RSARSA算法最有效的攻擊方法算法最有效的攻擊方法-一般數(shù)域篩一般數(shù)域篩(NFS)(NFS)方法去破譯和攻擊方法去破譯和攻擊RSARSA算法，它的破算法，它的破譯或求解難度是亞指數(shù)級(jí)的。譯或求解難度是亞指數(shù)級(jí)的。 依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能證依賴于大數(shù)分解，但是否等同于大數(shù)分解一直未能證明。不管怎樣，分解明。不管怎樣，分解n是最顯然的攻擊方法。是最顯然的攻擊方法。 1994年年4月月26日，美國(guó)各大媒體報(bào)道：由日，美國(guó)各大媒體報(bào)道：由RSA發(fā)明人在發(fā)明人在17年前出的年前出的129位數(shù)字已被因子分解位數(shù)字已被因子分解

33、. 目前，已能分解目前，已能分解140位十進(jìn)制的大素?cái)?shù)。因此，模數(shù)位十進(jìn)制的大素?cái)?shù)。因此，模數(shù)n必須選大一些。必須選大一些。 RSA最快的情況也比最快的情況也比DES慢上慢上100倍，無論是軟件還倍，無論是軟件還是硬件實(shí)現(xiàn)。速度一直是是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般只用于少量的缺陷。一般只用于少量數(shù)據(jù)加密。數(shù)據(jù)加密。RSA 的安全性的安全性4.3基于離散對(duì)數(shù)的公開密鑰密碼體制4.3.1 對(duì)數(shù)與Zp上的離散對(duì)數(shù)問題lc=adld=logac lZp 上的離散對(duì)數(shù)問題是指對(duì)于循環(huán)群Zp（p是一個(gè)素?cái)?shù)）a Zp是群Zp的生成元，對(duì)于任意c Zp，尋找唯一整數(shù)d（0=d=p-1)滿足cad（mod p)l我們把整數(shù)d記為logac ，并稱之為離散對(duì)數(shù)4.3.1 對(duì)數(shù)與Zp上的離散對(duì)數(shù)問題l建立在Zp上的公開密鑰算法：Diffie-Hellman密