密碼技術(shù)基礎(chǔ)

1、計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.3 非對稱密碼公用密鑰私有密鑰密碼學(xué)又稱公用密鑰密碼。它通過使用兩個(gè)數(shù)字互補(bǔ)密鑰，繞過了排列共享的問題。這兩個(gè)密鑰，一個(gè)是盡人皆知的，而另一個(gè)只有擁有者才知道，盡人皆知的密鑰叫做公用密鑰，而只有密鑰擁有者才知道的密鑰叫做私有密鑰，或稱專用密鑰。這兩種密鑰合在一起稱為密鑰對。公用密鑰可以解決安全分配密鑰問題，因?yàn)樗恍枰c保密密鑰通信，所需傳輸?shù)闹挥泄妹荑€。這種公用密鑰不需要保密，但對保證其真實(shí)性和完整性卻非常重要。如果某一信息用公用密鑰加密，則必須用私有密鑰解密，這就是實(shí)現(xiàn)保密的方法。如果某一信息用私有密鑰加密，那么，它必須用公用密鑰解密。這就是實(shí)現(xiàn)驗(yàn)證的方法。 計(jì)算機(jī)

2、網(wǎng)絡(luò)安全基礎(chǔ)2.3 非對稱密碼公鑰密碼技術(shù)示意圖公鑰密碼技術(shù)示意圖密鑰本密鑰本加密加密C=E(eB ,m)解密解密m=D(dB ,m)公鑰公鑰eBmm密文密文用戶用戶A用戶用戶BceB :用戶用戶B的公開密鑰的公開密鑰(公鑰公鑰) dB :用戶用戶B的秘密密鑰的秘密密鑰(私鑰私鑰)計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.3 非對稱密碼2. 公鑰密碼體制的原理公鑰密碼體制的原理 (1) 單向函數(shù)單向函數(shù)單向函數(shù)單向函數(shù)：一個(gè)可逆函數(shù)：一個(gè)可逆函數(shù)y=f(x)，如果對于給定所如果對于給定所有有x A，能方便地計(jì)算出能方便地計(jì)算出f(x)；對于給定所有對于給定所有y，求求x是困是困難的，以至于實(shí)際上是做不到的難的，以

3、至于實(shí)際上是做不到的。例：例： 有限域有限域GF(p)上，上，y=f(x)=bx ， x GF(p) 逆運(yùn)算：逆運(yùn)算： x=logbN計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.3 非對稱密碼 (2) 構(gòu)造公鑰密碼常用的單向函數(shù)構(gòu)造公鑰密碼常用的單向函數(shù)n多項(xiàng)式求根：多項(xiàng)式求根：n y=f(x)=(Xn+an-1Xn-1+a1x+a0) mod pn離散對數(shù)離散對數(shù)n y=f(x)-ax mod pn逆：逆：x=logby mod pn大整數(shù)分解大整數(shù)分解1)若已知兩個(gè)大素?cái)?shù)若已知兩個(gè)大素?cái)?shù)p、q，求求n=pXq僅需一次乘法，僅需一次乘法，但已知但已知n求求p、q則是一道難題。則是一道難題。計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)公用密

4、鑰系統(tǒng)的最流行的例子是由麻省理工學(xué)院的Rom Rivest、Adi Shamir和Len Adleman開發(fā)的RSA系統(tǒng)。另一個(gè)系統(tǒng)叫做Diffie-Hellman，該系統(tǒng)直接從本身不是密鑰的公用“組成部分”中產(chǎn)生共享保密密鑰。這兩種系統(tǒng)各有優(yōu)點(diǎn)，互為補(bǔ)充，因而常常組合在一起。2.3 非對稱密碼計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)RSARSA是在Diffie-Hellman算法問世兩年之后，由Rivest、Shamir和Adelman在MIT作出的，并于1978年公布。RSA要求每一個(gè)用戶擁有自己的一種密鑰：（1）公開的加密密鑰，用以加密明文；（2）保密的解密密鑰，用于解密密文。2.3 非對稱密碼計(jì)算機(jī)網(wǎng)絡(luò)安全

5、基礎(chǔ)2.3 非對稱密碼n歐拉函數(shù)： 對于一個(gè)正整數(shù)n，小于n且和n互質(zhì)的正整數(shù)的個(gè)數(shù)，記做：(n)。其中(1)被定義為1，但是并沒有任何實(shí)質(zhì)的意義。n對于素?cái)?shù)p，(p)= p -1. 對于兩個(gè)素?cái)?shù)p、q，n = pq 滿足(n) =(p-1)(q-1)n歐拉定理 對于互質(zhì)的整數(shù)a和n，有a(n) 1 mod n計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.3 非對稱密碼RSA參數(shù)建立n找素?cái)?shù)n選取兩個(gè)大的隨機(jī)素?cái)?shù)p,qn計(jì)算模n和Euler函數(shù)(n)nnpqn (n)=(p-1)(q-1)n找ed1 mod (n)n選取數(shù)e，用擴(kuò)展Euclid算法求數(shù)dn發(fā)布n發(fā)布(e,n)，這是公鑰kend保密，(d, n)是私鑰

6、 kd計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.3 非對稱密碼n加密n明文分組m做為整數(shù)須小于nc=me mod nn解密m=cd mod n計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.3 非對稱密碼RSA參數(shù)建立n找素?cái)?shù)n選取兩個(gè)大的隨機(jī)素?cái)?shù)p,qn計(jì)算模n和Euler函數(shù)(n)nnpqn (n)=(p-1)(q-1)n找ed1 mod (n)n選取數(shù)e，用擴(kuò)展Euclid算法求數(shù)dn發(fā)布n發(fā)布(e,n)，這是公鑰kend保密，(d, n)是私鑰 kd計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)RSA實(shí)例n選選p7，q17則則npq119且且(n)(p-1)(q-1)61696n取取e5則則d77 (57738549611 mod 96)n公鑰（公鑰（5，1

7、19），私鑰（），私鑰（77，119） n加密加密m19則則cme mod n= 195 mod 119 = 66 mod 119n解密解密c66mcd mod n = 6677mod 11919 mod 119計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)RSA需要考慮的因素n素?cái)?shù)素?cái)?shù)n必須夠大，否則對手可能很快分解必須夠大，否則對手可能很快分解nn判定，試除法不可行判定，試除法不可行n判定，采用判定，采用Miller-Rabin概率測試方法概率測試方法n強(qiáng)素?cái)?shù)強(qiáng)素?cái)?shù)n(p-1)/2和和(q-1)/2應(yīng)是素?cái)?shù)應(yīng)是素?cái)?shù)n選取較小的選取較小的e（較大的（較大的d）ne：3、65537n快速計(jì)算快速計(jì)算 XY%Z計(jì)算機(jī)網(wǎng)絡(luò)安

8、全基礎(chǔ)Diffie-Hellman密鑰交換算法 Diffie-Hellman密鑰交換算法 常用做密鑰的分配并滿足：k gx mod p（在g自乘冪x后，然后除以p，k為余數(shù)）Diffie-Hellman密鑰交換算法 計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)如果知道g、x和p，則很容易計(jì)算k。但是，如果知道k、g和p，則很難在合理的時(shí)間內(nèi)以類似規(guī)模的數(shù)計(jì)算x。當(dāng)所有的數(shù)都很大時(shí)，p是很大的素?cái)?shù)。在此情況下，數(shù)y叫做公用分量，而x叫做私有分量或?qū)Ｓ梅至?。這些分量本身不是密鑰，但是，它們可以用來制作共享保密密鑰。Diffie-Hellman密鑰交換算法 計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ) Diffie-Hellman體制：確定一個(gè)大數(shù)p

9、及GF(p)的本原元素a.一用戶設(shè)為A選擇一隨機(jī)數(shù)xA,計(jì)算 ： 將yA公開, xA保密.只有x自己掌握，用戶B要與A進(jìn)行保密通信，查得yA，計(jì)算他們建的通信密鑰：A收到密文后，可以先計(jì)算出通信密鑰 ：即：A可以查得公開的密鑰yB,計(jì)算出kAB,然后利用它來解密。公開yA或yB要求xA或xB等價(jià)于求離散對數(shù)loga(yA)或loga(yB). 計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ) n證明證明KKKYbXa mod qKYaXb mod q (gXb)Xa mod q (gXa)Xb mod q g(XbXa) mod q g(XaXb) mod qn舉例舉例 q97，g5A選選Xa36，B選選Xb58，則則Ya

10、5369750，Yb5589744交換交換50，44A算算K44369775，B算算K50589775n分析（別人怎么計(jì)算分析（別人怎么計(jì)算K?）別人看到了別人看到了Ya和和Yb，但需要計(jì)算但需要計(jì)算Xa或或Xb，即要算離散對數(shù)即要算離散對數(shù)YagXa mod q，或或YbgXb mod qDiffie-Hellman密鑰交換算法 計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4 密鑰分配與管理技術(shù)密鑰分配方案：解決網(wǎng)絡(luò)環(huán)境中需要進(jìn)行安全通信的密鑰分配方案：解決網(wǎng)絡(luò)環(huán)境中需要進(jìn)行安全通信的實(shí)體間建立共享密鑰的問題。實(shí)體間建立共享密鑰的問題。 1. 密鑰分配的基本方法：密鑰分配的基本方法： （對于通信雙方（對于通信雙方

11、A和和B）(1)密鑰由密鑰由A決定，然后通過物理方法安全傳遞給決定，然后通過物理方法安全傳遞給B.(2)密鑰由可信的第三方密鑰由可信的第三方C選取，并通過物理方法安全傳選取，并通過物理方法安全傳 遞給遞給A和和B.(3)如果如果A和和B事先已有一密鑰，那么其中一方選取新密鑰事先已有一密鑰，那么其中一方選取新密鑰后，用已有的密鑰加密新密鑰送給另一方。后，用已有的密鑰加密新密鑰送給另一方。(4)如果如果A和和B都有一個(gè)到可信的第三方都有一個(gè)到可信的第三方C的保密信道，那的保密信道，那么么C就可以為就可以為A和和B選取密鑰后安全地發(fā)送給選取密鑰后安全地發(fā)送給A和和B。(5)如果如果A和和B都在可信的

12、第三方都在可信的第三方C發(fā)布自己的公開密鑰，發(fā)布自己的公開密鑰，那么他們用彼此的公開密鑰進(jìn)行保密通信那么他們用彼此的公開密鑰進(jìn)行保密通信。計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4 密鑰分配與管理技術(shù)2. 對稱密碼技術(shù)的密鑰分配方案對稱密碼技術(shù)的密鑰分配方案集中式密鑰分配方案集中式密鑰分配方案由由KDC或一組節(jié)點(diǎn)組成的層次結(jié)構(gòu)負(fù)責(zé)密鑰的產(chǎn)生和分或一組節(jié)點(diǎn)組成的層次結(jié)構(gòu)負(fù)責(zé)密鑰的產(chǎn)生和分配。配。假定假定A和和B分別與分別與KDC有一個(gè)共享密鑰有一個(gè)共享密鑰Ka和和Kb，則則:AKDC: IDA/IDB/N1KDC A : EkaKs/ IDA/IDB/N1/EkbKs/IDAA B : EkbKs/IDAB A

13、: EksN2A B : Eksf(N2)KDCAB12345計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4 密鑰分配與管理技術(shù)(2) 分布式密鑰分配方案分布式密鑰分配方案 各節(jié)點(diǎn)具有相同的地位，他們之間的密鑰分配取決于他各節(jié)點(diǎn)具有相同的地位，他們之間的密鑰分配取決于他們之間的協(xié)商，不受任何其他方限制。們之間的協(xié)商，不受任何其他方限制。設(shè)設(shè)A和和B已共享一主密鑰已共享一主密鑰MKm，則過程如下：則過程如下：AB: IDA/N1BA : EMKmKs/ IDA/IDB/f(N1)/N2A B : EKsf(N2)AB123計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4 密鑰分配與管理技術(shù)3. 非對稱密碼技術(shù)的密鑰分配方案非對稱密碼技術(shù)的密

14、鑰分配方案 在非對稱密碼體制中，要求私鑰只有只有通信一方知道，在非對稱密碼體制中，要求私鑰只有只有通信一方知道，而公鑰則是公開的。而公鑰則是公開的。(1)公鑰的分配公鑰的分配公開發(fā)布公開發(fā)布公用目錄公用目錄公鑰機(jī)構(gòu)公鑰機(jī)構(gòu)公鑰證書公鑰證書計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4 密鑰分配與管理技術(shù)(1)利用非對稱技術(shù)分配對稱密碼技術(shù)密鑰利用非對稱技術(shù)分配對稱密碼技術(shù)密鑰簡單分配簡單分配ABPKA/IDAEPKAKs計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4 密鑰分配與管理技術(shù)具有保密和認(rèn)證功能的密鑰分配具有保密和認(rèn)證功能的密鑰分配 假定假定A和和B已完成了公鑰交換，則：已完成了公鑰交換，則：ABEPKBN1/IDAEPKBN2

15、EPKAN1/N2EPKAEKAKs計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4.2 密鑰管理技術(shù)1. 密鑰生成密鑰生成密鑰空間的大小密鑰空間的大小密鑰長度密鑰長度對于公鑰密碼體制，需要滿足一定的數(shù)學(xué)特征對于公鑰密碼體制，需要滿足一定的數(shù)學(xué)特征計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4.2 密鑰管理技術(shù)2. 密鑰的使用密鑰的使用從存儲介質(zhì)上獲得密鑰進(jìn)行加密和解密的技術(shù)活從存儲介質(zhì)上獲得密鑰進(jìn)行加密和解密的技術(shù)活動(dòng)。動(dòng)。計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4.2 密鑰管理技術(shù)3. 密鑰的存儲密鑰的存儲保證密鑰在存儲過程中的機(jī)密性、認(rèn)證性、保證密鑰在存儲過程中的機(jī)密性、認(rèn)證性、完整性，防止泄露和修改。完整性，防止泄露和修改。計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4.2 密鑰管理技術(shù)4. 密鑰的備份密鑰的備份/恢復(fù)恢復(fù)密鑰主管無法提供密鑰時(shí)讀取加密數(shù)據(jù)。密鑰主管無法提供密鑰時(shí)讀取加密數(shù)據(jù)。計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4.2 密鑰管理技術(shù)5. 密鑰的泄露與撤消密鑰的泄露與撤消密鑰安全是所有協(xié)議、技術(shù)、算法安全的基本條件；密鑰安全是所有協(xié)議、技術(shù)、算法安全的基本條件；密鑰可能會丟失、被盜、或以其它方式被泄露。密鑰可能會丟失、被盜、或以其它方式被泄露。計(jì)算機(jī)網(wǎng)絡(luò)安全基礎(chǔ)2.4.2 密鑰管理技術(shù)6. 密鑰的有效期密鑰的有效期密鑰使用時(shí)間越長，泄露的機(jī)會越大；密鑰使用時(shí)間越長，泄露的機(jī)會越大；如果密鑰已泄露，使用越久，損失越大；如果密鑰已泄露，使用越