《網(wǎng)絡(luò)安全加密技術(shù)》PPT課件

1、9.1 對(duì)稱加密體制-DES,教材5.3 密碼學(xué)基本原理 6.3 加密技術(shù) p134 DES簡(jiǎn)介 第一個(gè)也是最重要的現(xiàn)代對(duì)稱加密算法。1977.1 美國(guó)國(guó)家標(biāo)準(zhǔn)局，非國(guó)家安全級(jí)保密數(shù)據(jù)，用于銀行保護(hù)資金轉(zhuǎn)帳安全。5年+3*5使用期 分組密碼 每一分組稱為一個(gè)消息 M=C=0,164 K=0,156,9.1.1 數(shù)據(jù)加密標(biāo)準(zhǔn)-DES,DES算法總描述： 對(duì)輸入分組進(jìn)行固定的初始置換IP 將下面的運(yùn)算迭代16輪 Li= R i-1 R i= L i-1 f(R i-1, Ki ) 16輪迭代結(jié)果輸入到IP的逆置換。,ki,9.1.1 數(shù)據(jù)加密標(biāo)準(zhǔn)DES,DES-2（核心）：16輪迭代，一輪迭代過(guò)程

2、如下圖：,9.1.1 數(shù)據(jù)加密標(biāo)準(zhǔn)-DES,DES的核心：消息的隨機(jī)非線性分布 第i輪, f(R i-1, Ki )做下面兩個(gè)子運(yùn)算 Ri-1（32b）擴(kuò)展置換運(yùn)算(48b) 異或 ki（56b）收縮置換運(yùn)算（48b） 8個(gè)代換盒（S盒）， S盒非線性置換函數(shù) 8個(gè)S盒 （8*6b 8*4b） 6b地址（1 6b 行 2 3 4 5b 列 ） S盒該位置數(shù)字?jǐn)?shù)字4b 。例 第一組011011 對(duì)應(yīng)：S 盒S1第一行13列的數(shù)字 S盒 4行*16列 每行是0-15的一個(gè)排列 S盒的非線性對(duì)DES的安全非常重要,9.1.1 數(shù)據(jù)加密標(biāo)準(zhǔn)DES,F函數(shù)-1:擴(kuò)展運(yùn)算E: P28 E表， 標(biāo)出比特位的

3、讀出順序，其中16位被讀了兩次（32-48） F函數(shù)-2：與子密鑰（Ki 48位）的異或運(yùn)算 F函數(shù)-3：選擇壓縮運(yùn)算(S), P29 8個(gè)S盒（4*16） 48位被分成8組,每組6位 ，每組對(duì)應(yīng)一個(gè)S盒， 1，6 位確定在S盒中的行數(shù)，2,3,4,5確定列數(shù)，根據(jù)行列位置在S盒中選取給該位置對(duì)應(yīng)的數(shù)字（0-15），得到4位的二元組.例子 F函數(shù)-4：置換表P,E盒擴(kuò)展運(yùn)算,S1 ，S2S8盒選擇函數(shù),S盒運(yùn)算舉例,假設(shè)r i-1經(jīng)過(guò)擴(kuò)展運(yùn)算，并與Ki異或得到48位二進(jìn)制數(shù) ，分為八組：011011 110110 111000 010010 000011 010101 110011 11011

4、0輸入8個(gè)S盒。 第一組011011 對(duì)應(yīng)S 盒S1 1、6位組成二進(jìn)制數(shù)：01 -1 確定在S1中行數(shù)1 2 3 4 5位 1101-13 確定列數(shù)13 在S1盒1行13列的數(shù)字是5，換為二進(jìn)制4位：0101。 注意：所有S盒中的數(shù)字都小于等于15，相當(dāng)于4位二進(jìn)制數(shù)（15-1111），實(shí)現(xiàn)6位（位置：行 列）向4位內(nèi)容的轉(zhuǎn)換,9.1.2 DES的核心,S盒的非線性對(duì)DES的安全非常重要 代換密碼是非線性的，移位密碼仿射密碼線性 線性密碼減小密鑰空間，對(duì)差分分析的脆弱 例差分分析攻擊仿射密碼 DES的安全性 密鑰長(zhǎng)度較短： 窮舉（強(qiáng)力）測(cè)試 利用已知明文和密文消息對(duì) 解決方法：不同密鑰加密-

5、解密-加密三重DES方案 DES的短密鑰弱點(diǎn)90 年代變明顯： 1998.7.15 250,000 $,構(gòu)造DES解密高手，56個(gè)小時(shí)成功找到密碼。,9.2 公鑰密碼體制,公鑰密碼體制是密碼 史上一次革命。 編碼系統(tǒng)基于數(shù)學(xué)中的單向陷門(mén)函數(shù) 采用了兩個(gè)不同的密鑰，對(duì)在公開(kāi)網(wǎng)絡(luò)上進(jìn)行保密通信、密鑰分配、數(shù)字簽名和認(rèn)證有深遠(yuǎn)影響。 內(nèi)容 公鑰密碼體制的基本原理 RSA算法 重點(diǎn),9.2 .1 公鑰密碼體制基本原理,對(duì)稱密碼體制的一個(gè)缺點(diǎn)：雙雙如何建立會(huì)密鑰話；密鑰分配成本高。尤其是對(duì)公開(kāi)網(wǎng)絡(luò)的電子商務(wù)安全應(yīng)用。 1976年，Diffie 和Hellman提出：密碼學(xué)利用NP復(fù)雜性理論；陷門(mén)單向函數(shù)

6、 單向函數(shù)：一個(gè)函數(shù)f 對(duì)定義域上任意一個(gè)x, f(x)容易計(jì)算；但對(duì)f值域上的任意y, f-1(y)都在計(jì)算上不可行。 陷門(mén)單向函數(shù)：?jiǎn)蜗蚝瘮?shù)f(x)，如果進(jìn)一步給定某些輔助信息（如解密密鑰），計(jì)算f-1(y)又變得容易。,9.2.1 公鑰密碼體制基本原理,可信單向函數(shù)舉例： 假設(shè)n是兩個(gè)大素?cái)?shù)p和q 的乘積，分解n 是一個(gè)非常困難的問(wèn)題（NP-完全問(wèn)題）。 設(shè)b是一個(gè)正整數(shù)，定義函數(shù)f: ZnZn, f(x)=x b mod n , f是一個(gè)單向函數(shù)。但知道n的因子是p或q時(shí)，計(jì)算f-1是容易，因而f是陷門(mén)單向函數(shù)。 秘密的陷門(mén)被嵌在單向函數(shù)求逆問(wèn)題中。這個(gè)陷門(mén)信息就是私人密鑰。,9.2.

7、2 RSA算法,1978年，Rivest Shamir和Adleman 三人最早實(shí)現(xiàn)Diffie和 Hellman的想法。 RSA算法安全： 利用陷門(mén)單向函數(shù)的一種可逆模指數(shù)運(yùn)算，安全性基于大整數(shù)分解因子的困難性。,9.2.2 RSA算法-描述,建立RSA密碼體制的過(guò)程 選擇兩個(gè)大素?cái)?shù)p ,q 計(jì)算乘積n=pq 和(n) = (p-1)(q-1) 選擇大于1小于(n) 的隨機(jī)數(shù)e,使得gcd(e, (n) )=1 計(jì)算d 使得 de=1 mod(n) ) 對(duì)每一個(gè)密鑰k=(n,p,q,d,e),定義加密變換為：Ek(x)=xe mod n, 解密變換為：Dk(x)=yd mod n,這里x,y

8、Zn; 以e,n為公開(kāi)密鑰， p,q,d為私有密鑰 。,陷門(mén),9.2.2 RSA算法-描述,如上建立一個(gè)明文空間P和密文空間C為P=C= Zn,密鑰空間為K=n,p,q,d,e:n=pq，p和q是大素?cái)?shù)，1e,d (n) :de=1 mod (n) 的RSA密碼體制。,9.2.2 RSA算法-正確性,RSA算法基礎(chǔ)（解密正確性證明-歐拉定理） 對(duì)任意的e Zn *,有e (n) =1 mod n, 其中Zn*=x Zn | gcd(n,x)=1,函數(shù)是歐拉函數(shù)。 由于選擇的ed=1 mod (n) 所以 ed=k (n) +1 Cd = Med = M k (n) +1=( M (n) k *

9、M M mod n 注,9.2.2 RSA算法-實(shí)例,RSA算法實(shí)例： P=7,q=17; N=pq=7*17=119 ， (n) =(p-1)(q-1) =(7-1)(17-1)=96； 選擇隨機(jī)整數(shù)5 (n) ,且與96互素； 求出d, de=1 mod 96, 得到d=77,因?yàn)?7*5=96*4+1； 輸入明文M=19,計(jì)算C=Me=195=66 mod 119 接收密文C=66,解密計(jì)算M=Cd=6677=19 mod119 實(shí)際計(jì)算中p,q,n,e,d要大得多。,9.2.2 RSA算法中的計(jì)算技巧,加密和解密運(yùn)算。 模運(yùn)算性質(zhì)(基礎(chǔ)) ： (a b) mod n = (a mod

10、n)(b mod n) mod n 標(biāo)準(zhǔn)的RSA要求p q是128以上，e,d也接近這樣的數(shù)量級(jí)。 計(jì)算Me, e化成二進(jìn)制形式b kb k-1b0, e = bi0 2i Me=M bi0 2 i =(M bk)2M bk-1) 2 ) 2 M b2)2M b1 )2M b0,例 6677 mod 119 77=1*26+ 0*25 +1*23+1*22+1*20 = （(1*2+0)*2+)*2+1 6677 = ( ( (661)2*660)2)2*661 mod 119,9.2.2 RSA算法中的計(jì)算技巧,構(gòu)造Me mod n 的算法 d=1 For i=k down to 0 do

11、d=d2 mod n; if bi=1 then d=(d * m) mod n; return d,Me=M bi0 2 i =(M bk)2M bk-1) 2 ) 2 M b2)2M b1 )2M b0,9.2.2 RSA算法中的計(jì)算技巧-求逆,從e計(jì)算d, 其中g(shù)cd( (n) ,e)=1， 求 d=e-1 mod (n) ，計(jì)算e mod (n) 的逆元 方法：推廣的歐幾里德算法。注 xe+y (n) =1 mod (n),擴(kuò)展歐幾里德算法不但能計(jì)算(a,b)的最大公約數(shù)，而且能計(jì)算a模b及b模a的乘法逆元。 intgcd(inta,intb,int if(0=a) /有一個(gè)數(shù)為0，就

12、不存在乘法逆元,x1=1;x2=0;x3=a;y1=0;y2=1;y3=b;intk;,for(t3=x3%y3;t3!=0;t3=x3%y3)k=x3/y3;t2=x2-k*y2;t1=x1-k*y1;x1=y1;x1=y2; x2x3=y3;y1=t1;y2=t2;y3=t3;,if(y3=1)/有乘法逆元ar=y2;br=x1;return1;else/公約數(shù)不為1，無(wú)乘法逆元ar=0;br=0;returny3;,算法2,Function euclid(a,b:longint; var x,y:longint):longint;Var t:longint;Beginif b=0 the

13、n begineuclid:=a; x:=1; y:=0;endElsebegineuclid:=euclid(b,a mod b,x,y);t:=x; x:=y; y:=t-(a div b)*y;end;End; 例子： 157 1 mod 2668=17 5-1 mod 96=-19 (-19+96=77),9.2.3 RSA算法的安全性,安全：采用大的密鑰，e,d 的比特?cái)?shù)越大越好， 但加解密速度慢，二者之間折中。 對(duì)RSA算法的攻擊難度相當(dāng)于對(duì)模數(shù)n進(jìn)行乘積因子分解。 目前密鑰長(zhǎng)度界于1024 -2048比特之間，RSA算法是安全的。 RSA限制條件：素?cái)?shù)p q的長(zhǎng)度不能相差太大，p

14、-1,q-1都應(yīng)該有大的素?cái)?shù)因子，gcd(p-1,q-1)應(yīng)該偏小。,9.2.4 RSA試驗(yàn),試驗(yàn)?zāi)康模?掌握有關(guān)RSA密碼體制編程計(jì)算方法 掌握使用特定的平臺(tái)Vb, VC,Turbo c 對(duì)算法正確編程調(diào)試正確運(yùn)行。 實(shí)驗(yàn)報(bào)告分析編程的約束條件。,實(shí)驗(yàn)過(guò)程及算法 1 小程序過(guò)程：試除法判斷大奇數(shù)p是否素?cái)?shù) 循環(huán)判斷p是否能被一個(gè)小于p 的數(shù)（2+奇數(shù)）整除，如果被整除，p不是素?cái)?shù); 否則 循環(huán)數(shù)+1，回到循環(huán)開(kāi)頭 都不能整除，p 是素?cái)?shù) 2. 輸入給出大素?cái)?shù)p1,p2, e ,判斷e是否合法，計(jì)算d 根據(jù)1，判斷輸入的p1,p2是否素?cái)?shù) 計(jì)算n=p1*p2 , vn=(p1-1)（p2-1） 判斷e,vn是否互素（最大公約數(shù)為1） 計(jì)算d de=1 mod vn,實(shí)驗(yàn)思考問(wèn)題,實(shí)驗(yàn)要求在實(shí)驗(yàn)結(jié)論分析中回答下列問(wèn)題： 在vb 中，程序正確運(yùn)行的p1,p2的最大值，在實(shí)際RSA應(yīng)用中，p1,p2的取值范圍是多少，微機(jī)系統(tǒng)可以計(jì)算嗎？ e,vn 為什么必須互素？舉一個(gè)反例說(shuō)明原因。 本實(shí)驗(yàn)中E取值較小時(shí)的好