信息安全原理與實踐-第二版04-公開密鑰加密課件

1、1信息安全原理與實踐Information Security: Principles and Practice, 2nd Edition美Mark Stamp著張 戈譯第4章 公開密鑰加密24.1 引言公開密鑰加密技術(shù)單向陷門函數(shù)公開密鑰私有密鑰數(shù)字簽名公開密鑰加密體系橢圓曲線加密方案34.2 背包加密方案Merkle-Hellman背包加密系統(tǒng)基于一個數(shù)學問題，該問題往往被看成NP完全問題。定義： 給定一個集合，共包含n個權(quán)重值，分別標識為：W0, W1, , Wn-1， 以及期望的和S，要求找到a0, a1, , an-1，其中每一個ai0，1使得等式S=a0W0+ a1W1+ . + a

2、 n-1Wn-1, 能夠成立。例子： 假設(shè)權(quán)重值為85, 13, 9, 7, 47, 27, 99, 86 期望的和S=172 對于這個問題存在一個解決方案： a=(a0, a1, a2, a3, a4, a5, a6, a7)=(11001100) 因為85+13+47+27=1724超遞增的背包問題當將權(quán)重值從小到大排列起來時，每一個權(quán)重值都大于前面所有權(quán)重值相加的和。 - 相對容易解決！ 例子：權(quán)重值集合為：3, 6, 11, 25, 46, 95, 200, 411期望的和S=309我們只需從最大權(quán)重值開始，逐步向最小的權(quán)重值進行計算，就有望在線性時間內(nèi)恢復出ai。5因為S200，那么

3、一定有a6=1，因為剩余所有權(quán)重值的和要小于200。接著計算S=S-200=109，這是新的目標和值。因為S95，我們得到a5=1。然后再計算S=109-95=14。繼續(xù)如法炮制，就得到了最終結(jié)果a=10100110。我們能夠輕松地證實這個問題獲得了解決，因為3+11+95+200=309。構(gòu)造背包加密系統(tǒng)的流程(1) 生成一個超遞增的背包。(2) 將這個超遞增的背包轉(zhuǎn)換為常規(guī)的背包。(3) 公鑰便是常規(guī)背包。(4) 私鑰就是超遞增的背包以及相關(guān)的轉(zhuǎn)換因子。6實例（1）我們選擇如下超遞增的背包：(2, 3, 7, 14, 30, 57, 120, 251)（2）為了將這個超遞增的背包轉(zhuǎn)換成常規(guī)

4、背包，我們必須選擇乘數(shù)m和模數(shù)n，m和n必須是互素的，且n要大于超遞增背包中所有元素值的和。假設(shè)選取的乘數(shù)m=41，模數(shù)n=491。通過模乘法運算，根據(jù)超遞增背包計算常規(guī)背包，得到：（3）公鑰就是這個常規(guī)背包公鑰：(82, 123, 287, 83, 248, 373, 10, 471)（4）私鑰就是這個超遞增背包，加上轉(zhuǎn)換因子的乘法逆，如m1 mod n。對于這個實例，計算結(jié)果如下私鑰：(2, 3, 7, 14, 30, 57, 120, 251)以及41-1 mod 491=127如果Alice想要加密消息M=10010110并發(fā)送給Bob，她就利用消息中值為1的二進制位，據(jù)此來選擇常規(guī)背

5、包中的元素，將這些元素相加求和就得到了對應的密文。Alice執(zhí)行計算：C=82+83+373+10=548要想解密這個密文，Bob使用他的私鑰執(zhí)行如下計算，得到：Cm-1 mod n=54812 mod 491=193然后Bob針對值193求解超遞增背包問題。因為Bob擁有私鑰，所以要從中恢復出明文是比較容易的。最后，明文的二進制表示為M=10010110，其換算成十進制是M=150。8總結(jié)：在背包加密系統(tǒng)里，陷門函數(shù)存在于運用模運算將超遞增背包問題轉(zhuǎn)換為常規(guī)背包問題時，因為該轉(zhuǎn)換因子對于攻擊者來說是無法得到的。該函數(shù)的單向特性在于一個事實：使用常規(guī)背包實施加密非常容易，但是在沒有私鑰的情況下

6、，要想解密顯然是非常困難的。當然，有了私鑰，我們就能夠?qū)栴}轉(zhuǎn)換為超遞增背包問題，解決起來就容易了。背包問題看起來確實是對癥下藥了。首先，構(gòu)造包含公鑰和私鑰的密鑰對是相當容易的。而且，給定了公鑰，實施加密是非常容易的，而了解了私鑰則會使解密過程非常容易。最后，在沒有私鑰的情況下，攻擊者就將不得不去解決NP完全問題了。可惜這個精巧的背包加密系統(tǒng)是不安全的。該方案于1983年被Shamir使用一臺Apple II計算機破解。該攻擊依賴于一種稱為格基規(guī)約的技術(shù)。問題的根本在于該方案中從超遞增背包問題派生出的所謂“常規(guī)背包問題”并不是真正的常規(guī)背包問題事實上，它是一種非常特殊的高度結(jié)構(gòu)化的背包案例，而

7、格基規(guī)約攻擊能夠利用這種結(jié)構(gòu)的特點比較容易地恢復出明文(可以較高的概率完成)。94.3 RSARSA體制的命名來自于它的三個公認的發(fā)明者：Rivest、Shamir和Adleman。10為了生成RSA算法的公鑰和私鑰的密鑰對，先要選擇兩個大素數(shù)p和q：計算出它們的乘積N=pq。選擇與乘積(p-1) (q-1)互素的數(shù)e。計算出數(shù)e的模(p-1) (q-1)的乘法逆元素，命名該逆元素為d。這些數(shù)值滿足公式ed = 1 mod (p-1) (q-1)。數(shù)N是模數(shù)，e是加密指數(shù)，而d是解密指數(shù)。RSA密鑰對的組成如下：公鑰：(N, e)私鑰：d加密：將明文文本消息M視為一個數(shù)，對其按指數(shù)e求冪并模N

8、C=M e mod N解密：要解密C，求冪模運算使用解密指數(shù)d完成相應的操作過程M=C d mod NRSA加密體制真的確實有效嗎？ 給定C=M e mod N，我們必須證明如下等式：M=C d mod N=M ed mod N 歐拉定理：如果數(shù)x與數(shù)n互素，那么x(n)= 1 mod n。再回顧之前對e和d的選取符合等式：ed=1 mod (p-1)(q-1)， 而且N = pq，這意味著： (N)=(p-1)(q-1)這兩個事實結(jié)合在一起，就意味著下面的等式成立：ed-1=k(N)11這就證實了RSA體制的解密指數(shù)確實解密了密文C。4.3.1教科書式的RSA體制范例12AliceBob生成

9、Alice的密鑰對：選擇兩個“大的”素數(shù)：p=11，q=3。模數(shù)就是N=pq=33，并且可以計算出 (p-1)(q-1)=20。選取加密指數(shù)為e=3。計算相應的解密指數(shù)d=7，因為ed=37=1 mod 20。Alice的公鑰：(N, e) = (33,3)Alice的私鑰：d=7假定Bob想要發(fā)送一條消息M=15 給Alice。Bob先查找Alice的公鑰(N, e) = (33, 3)，再計算密文 C=M e mod N=153 =3375=9 mod 33 =9Alice使用她的私鑰d=7進行解密計算：M=C d mod N=97=4,782,969 =144,93833+15 =15

10、mod 33 =15存在的問題所謂“大的”素數(shù)其實并不大，對Trudy來說分解這個模數(shù)將是小菜一碟。在現(xiàn)實世界中，模數(shù)N典型的大小通常至少是1024位，而長度為2048位或更大的模數(shù)值也是常常會用到的?？赡茉馐芮跋驒z索攻擊。134.3.2 重復平方方法重復平方方法通過每次構(gòu)建一個二進制位的方式來生成指數(shù)并完成計算。在每個步驟中，我們將當前的指數(shù)值乘以2，如果其二進制擴展形式在相應的位置有值1，我們就還要對指數(shù)計算的結(jié)果再加上1。例子： 計算520。 指數(shù)20以二進制形式表示為10100，指數(shù)10100可以一次一位地被構(gòu)建出來，從高階二進制位開始，如下：(0, 1, 10, 101, 1010,

11、 10100)=(0, 1, 2, 5, 10, 20)現(xiàn)在計算520，重復平方方法的執(zhí)行過程如下：14So easy！4.3.3 加速RSA加密體制另外一個可用于加速RSA加密體制的技巧是，對于所有用戶使用同一加密指數(shù)e。而這并不會在任何方面削弱RSA加密體制的強度。通常加密指數(shù)的合適選擇是e=3。選擇這個e值，每一次公鑰加密僅僅需要兩次乘法運算。不過，私鑰的運算操作仍然代價高昂。如果多個用戶都使用e=3作為他們的加密指數(shù)，那么還存在另一種類型的立方根攻擊。如果對于同一個消息M，使用三個不同用戶的公鑰分別加密，生成的密文比如是C0、C1和C2，那么中國剩余定理可用于恢復明文消息M。在實踐中，

12、這也很容易避免，方法就是對每個消息M隨機附加填充信息，或者在每個消息M中增加一些用戶指定的信息，這樣每個消息實際上就會互不相同了。另一個流行的通用加密指數(shù)是e=216+1。選取這個e值，每個加密運算僅需要執(zhí)行17個重復平方算法的步驟。e=216+1的另一個優(yōu)勢是，在運用中國剩余定理的攻擊者成功破解消息密文之前，同樣的加密消息密文必須已經(jīng)先行發(fā)送給e=216+1個用戶。154.4 Diffie-Hellman密鑰交換算法Diffie-Hellman密鑰交換算法，或簡稱為DH，是由英國政府通信總部(GCHQ)的Malcolm Williamson所發(fā)明，其后不久，該算法又被它的命名者Whitfie

13、ld Diffie和Martin Hellman獨立地再次發(fā)明。這里討論的Diffie-Hellman算法版本是密鑰交換算法，因為它僅僅能夠用于建立共享的秘密。DH算法的安全性依賴于離散對數(shù)問題的計算難度。假設(shè)給定g以及x=gk。那么，要想確定k，就需要計算對數(shù)logg(x)。16DH算法的數(shù)學構(gòu)造設(shè)定p為素數(shù)，并假定g是生成器，即對于任何的x1, 2, . ,p -1，都存在指數(shù)n，使得x=gn mod p。素數(shù)p和生成器g是公開的。對于實際的密鑰交換過程，Alice隨機地選擇秘密的指數(shù)a，Bob隨機地選擇秘密的指數(shù)b。Alice計算ga mod p，并將結(jié)果發(fā)送給Bob，而Bob計算gb

14、mod p，也將結(jié)果發(fā)送給Alice。Alice執(zhí)行如下計算：(gb)a mod p=gab mod pBob執(zhí)行如下計算：(ga)b mod p=gab mod p最后，gab mod p就是共享的秘密，其典型的用途是作為對稱密鑰。17DH密鑰交換攻擊者Trudy能夠看到ga mod p 和 gb mod p，而且看起來她距離那個共享秘密gab mod p也非常接近。但是：gagb=ga+bgab mod p顯然，Trudy需要找到a或b，看起來這就需要她去解決一個困難的離散對數(shù)問題。18DH算法容易遭受中間人攻擊（簡稱為MiM攻擊）Trudy將自己置于Alice和Bob之間，截獲從Alic

15、e發(fā)送給Bob的消息，同樣也截獲從Bob發(fā)送給Alice的消息。Trudy如此部署，將使DH密鑰交換很容易地就被徹底破壞了。在這個過程中，Trudy建立共享的秘密，比方說，和Alice共享gat mod p，和Bob共享另一個秘密gbt mod p。無論是Alice還是Bob，都不會覺察到這其中有任何問題，于是，Trudy就能夠讀到或改寫Alice和Bob之間傳遞的任何消息了。19預防中間人攻擊的方法使用共享對稱密鑰對DH密鑰交換過程實施加密。使用公鑰對DH密鑰交換過程實施加密。使用私鑰對DH密鑰交換過程中的值進行數(shù)字簽名。204.5 橢圓曲線加密橢圓曲線加密體制(Elliptic Curve

16、 Cryptography，ECC)提供了另一個“實施復雜難解的數(shù)學操作”的方法。優(yōu)勢：要獲得同樣等級的安全性，需要的二進制位數(shù)較少缺點：橢圓曲線體制的數(shù)學計算更加復雜，因此，橢圓曲線體制中的每個數(shù)學操作的代價都相對而言更加昂貴。典型的橢圓曲線圖214.5.1橢圓曲線的數(shù)學原理從加密技術(shù)的角度來說，我們希望處理的是離散的點集。這可以通過在通用橢圓曲線的計算等式上執(zhí)行“mod p”運算來輕松地實現(xiàn)。y2=x3+ax+b(mod p)例子：y2=x3+2x+3(mod 5)對于x的所有取值，逐個選取并計算相應的y值(一個或多個值)。因為我們是基于模數(shù)5實施運算，所以我們只需考慮x=0, 1, 2,

17、 3, 4的情況。在這個例子中，我們最后獲得如下這些點：x=0 y2=3 no solution mod 5x=1 y2=6=1 y=1,4 mod 5x=2 y2=15=0 y=0 mod 5x=3 y2=36=1 y=1,4 mod 5x=4 y2=75=0 y=0 mod 5y2=x3+2x+3(mod 5)曲線對應的點為：(1, 1)(1, 4) (2, 0) (3, 1) (3, 4) (4, 0)和22在橢圓曲線上增加兩個點的代數(shù)計算方法的說明為了確定橢圓曲線上的點P3 = (1,4)+(3,1)，首先進行如下計算：m=(1-4)/(3-1)=-32-1=-33=1 mod 5然后

18、計算x3=12-1-3=-3=2 mod 5y3=1(1-2)-4=-5=0 mod 5這樣，在橢圓曲線y2 =x3+2x+3(mod 5)上，就得到(1, 4)+(3, 1)=(2, 0)。請注意這個和值，點(2, 0)也位于該橢圓曲線上234.5.2 基于橢圓曲線的Diffie-Hellman密鑰交換方案探討Diffie-Hellman密鑰交換方案的橢圓曲線版本，其公開信息包括一條橢圓曲線及該曲線上的一點。例子： 對于橢圓曲線y2= x3+11x+b(mod 167)，暫時不給定b的值。我們選擇任何一點(x, y)以及b的值，使得這一點位于最終的橢圓曲線之上。我們選擇了(x, y)=(2,

19、7)。將x=2和y=7代入曲線中，就可以確定b=19。于是，該方案的公開信息就是y2= x3+11x+19(mod 167) 和 點(2,7)Alice和Bob每人都必須隨機選擇他們自己的秘密乘法因子。24Alice和Bob就已經(jīng)建立了共享的秘密，共享秘密可用作對稱密鑰。25Alice執(zhí)行如下計算：A(2, 7)=15(2, 7)=(102, 88)并將她的計算結(jié)果發(fā)送給BobBob執(zhí)行如下計算：B(2, 7)=22(2, 7)=(9, 43)也將他的計算結(jié)果發(fā)送給Alice假設(shè)Alice選擇了A=15，而Bob選擇了B=22。 Alice將從Bob那接收的值乘以她自己的秘密乘法因子A：A(9

20、, 43)=15(9, 43)=(131, 140)Bob執(zhí)行類似計算：B(102, 88)=22(102, 88)=(131, 140)Diffie-Hellman密鑰交換方案的橢圓曲線版本之所以能夠有效工作，全在于ABP=BAP，其中A和B分別是秘密乘法因子，而P是橢圓曲線上指定的點。這個方案的安全性依賴于如下事實：即使Trudy能夠看到AP和BP，但是很顯然，她也必須找到A或B，然后才能夠確定共享秘密。據(jù)目前所知，這個Diffie-Hellman密鑰交換方案的橢圓曲線版本和常規(guī)的Diffie-Hellman密鑰交換方案同樣難于破解。事實上，對于給定長度的二進制位數(shù)，橢圓曲線版本的Diff

21、ie-Hellman密鑰交換方案要難破解得多，而且它使得我們可以使用更小的數(shù)值獲得同等級別的安全性。因為數(shù)值越小，其算法的效率越高。264.5.3 現(xiàn)實中的橢圓曲線加密案例設(shè)定p = 564538252084441556247016902735257a = 321094768129147601892514872825668b = 430782315140218274262276694323197考慮橢圓曲線E：y2 = x3+ax +b(mod p)，我們令P點為(97339010987059066523156133908935,14967037284616928576068237197889

22、8)該點位于橢圓曲線E之上，再令k=281183840311601949668207954530684。然后，將P點與自身相加k次，表示為kP，于是我們得到點(44646769697405861057630861884284,522968098895785888047540374779097)這個點也位于橢圓曲線E上。274.6 公開密鑰體制的表示方法對于公開密鑰加密體制中的加密、解密和簽名，我們將采用下面的表示方法：使用Alice的公鑰加密消息M：C=MAlice使用Alice的私鑰解密密文消息C：M=CAliceAlice簽名的消息M的表示方法：S=MAlice花括號表示使用公鑰的操作，方

23、括號代表使用私鑰的操作，下標用來表明使用誰的密鑰。既然公鑰操作和私鑰操作是互相消解的，于是可以得到如下等式：MAliceAlice=MAliceAlice=M公鑰是公開的，因而任何人都能夠去計算MAlice。私鑰是私密的，所以只有Alice能夠執(zhí)行計算CAlice或MAlice。這意味著任何人都能夠為Alice加密消息，但是僅有Alice本人能夠解密相應密文。284.7 公開密鑰加密體制的應用能夠使用對稱密鑰加密方案完成的任何事情，也都可以通過公開密鑰加密方案來完成，只不過要慢一些，包括保護數(shù)據(jù)的機密性，類似的應用形式還有：通過不安全的通道傳送數(shù)據(jù)，或者在不安全的媒介上安全地存儲數(shù)據(jù)等。此外，

24、我們還能夠?qū)⒐_密鑰加密體制用于保護數(shù)據(jù)的完整性數(shù)字簽名就能夠起到對稱密鑰加密體制中消息認證碼(MAC)的作用。相比對稱密鑰加密體制，公開密鑰加密體制提供了兩大主要優(yōu)點。第一個主要優(yōu)點是，基于公開密鑰加密體制，我們不需要事先建立共享的密鑰。第二個主要優(yōu)點是，數(shù)字簽名提供了完整性和不可否認性。294.7.1真實世界中的機密性相比公開密鑰加密技術(shù)，對稱密鑰加密技術(shù)的主要優(yōu)勢是效率。我們是否能夠既擁有對稱密鑰加密方案的效率，又不必提供事先的預共享密鑰呢？要得到這樣超級完美的結(jié)果，方法就是構(gòu)建混合加密系統(tǒng)，其中公開密鑰加密體制用于建立對稱密鑰，將這個生成的對稱密鑰用于加密數(shù)據(jù)。304.7.2 數(shù)字簽名

25、和不可否認性不可否認性 假設(shè)Alice從她最中意的股票商Bob那里訂購了100股股票。為了確保她的訂單的完整性，Alice使用共享的對稱密鑰KAB計算消息認證碼MAC?，F(xiàn)在，假定在Alice下訂單后不久，并且恰恰在她向Bob進行支付之前，股票交易系統(tǒng)丟失了該交易的所有數(shù)據(jù)。事情發(fā)生在這個節(jié)骨眼上，這提供了一種可能，即Alice可以聲明她并未下過訂單，也就是說，她能夠否認這次交易。 Bob是否能夠證明Alice下過訂單呢？如果他所擁有的只是Alice的消息認證碼MAC，那么他不能證明。因為既然Bob也知道共享的對稱密鑰KAB，他就能夠偽造一條消息，并在該消息中顯示“Alice下了訂單”。這里請注

26、意，Bob是知道Alice下過訂單的，但是他不能夠在法庭上證明這一點，他缺少證據(jù)。31在同樣的場景下，假設(shè)Alice使用數(shù)字簽名，而不是消息認證碼MAC。和消息認證碼MAC一樣，數(shù)字簽名也能夠提供數(shù)據(jù)完整性的驗證。我們再一次假定股票交易系統(tǒng)丟失了交易的所有數(shù)據(jù)，并且Alice試圖否認這次交易。這時Bob能夠證實來自Alice的訂單嗎？是的，他能夠做到，因為只有Alice可以訪問她自己的私鑰。于是，數(shù)字簽名就提供了數(shù)據(jù)完整性和不可否認性，而消息認證碼MAC卻只能夠用于保護數(shù)據(jù)完整性。這是因為對稱密鑰是Alice和Bob都知道的，然而Alice的私鑰則僅有Alice本人可知。324.7.3 機密性

27、和不可否認性假設(shè)Alice和Bob有公開密鑰加密系統(tǒng)可用，Alice想要發(fā)送一條消息M給Bob。為了機密性起見，Alice將使用Bob的公鑰加密消息M。另外，為了獲得數(shù)據(jù)完整性和不可否認性保護，Alice可以使用她自己的私鑰對消息M進行簽名。但是，如果Alice是個非常關(guān)注安全性的人，想要既有機密性，又有不可否認性，她就不能只對消息M簽名，因為那樣不能提供數(shù)據(jù)機密性保護，她也不能只對消息M加密，因為這不能提供數(shù)據(jù)完整性保護。如何同時提供機密性和不可否認性？Alice可以對消息進行簽名和加密，然后再將其發(fā)送給Bob，具體操作為：MAlice Bob或者先加密消息M，再對該結(jié)果實施簽名：MBobAlice33先簽名再加密方式的缺陷34先加密后簽名方式的缺陷35結(jié)論消息的接收者并不是清楚地理解公開密鑰加密技術(shù)的工作原理和方式。對于公開密鑰加密技術(shù)，有一些