04密碼學(xué)與網(wǎng)絡(luò)安全第四講new

1、密碼學(xué)與網(wǎng)絡(luò)安全第四講密碼學(xué)基礎(chǔ)(三) n 討論議題 密鑰分配 公鑰密碼算法 Diffie-Hellman密鑰交換算法 背包算法 RSA算法 EIGamal算法 橢圓曲線密碼算法ECCn 密鑰分配（Key Distribution）建立密鑰分本協(xié)議必須考慮兩個(gè)因素：1） 傳輸量和存儲(chǔ)量就盡可能的?。?） 每一對(duì)用戶U和V都能獨(dú)立計(jì)算一個(gè)秘密密鑰。對(duì)于通信方A和B來說密鑰分配方式由以下幾種方式：1） A選擇密鑰并手工傳遞給B；2） 第三方C選擇密鑰分別手工傳遞給A,B；3） 用A、B原有共享密鑰傳送新密鑰(采用舊密作用于+新密鑰方式)；4） 與A、B分別有共享密鑰的第三方C的加密連接，C就可以用

2、加密連接傳送新密鑰給A和/或B。 N個(gè)用戶集需要N(N-1)/2個(gè)共享密鑰。簡(jiǎn)單的密鑰分配：1）A產(chǎn)生公/私鑰對(duì) PUa ，PRa并將PUa和其標(biāo)識(shí)IDa的消息發(fā)送給B；2）B產(chǎn)生秘密鑰KS，并用A的公鑰對(duì)KS，加密后發(fā)送給A；3）A計(jì)算D（PUa E（PUa，KS）得出秘密鑰KS。因?yàn)橹挥蠥能解密該消息，只有A和B知道KS；4）A丟掉PUa ，PRa，B丟掉PUa 。A和B 可以用傳統(tǒng)的密碼和會(huì)話密鑰KS安全通信。l Key Distribution Center密鑰分發(fā)中心 l 問題的提出1）密鑰管理量的困難傳統(tǒng)密鑰管理：兩兩分別用一對(duì)密鑰時(shí)，則n個(gè)用戶需要C(n,2)=n(n-1)/2個(gè)

3、密鑰，當(dāng)用戶量增大時(shí)，密鑰空間急劇增大。如：n=100 時(shí)， C(100,2)=4,995n=5000時(shí)， C(5000,2)=12,497,500（2）數(shù)字簽名的問題傳統(tǒng)加密算法無法實(shí)現(xiàn)抗抵賴的需求。密鑰分發(fā) 1） 每個(gè)用戶與KDC有共享主密鑰(Master Key)；2） N個(gè)用戶，KDC只需分發(fā)N個(gè)Master Key；3） 兩個(gè)用戶間通信用會(huì)話密鑰(Session Key)；（會(huì)話密鑰：端系統(tǒng)之間的通信使用一個(gè)臨時(shí)的密鑰進(jìn)行加密，這個(gè)密鑰叫會(huì)話密鑰）4） 用戶必須信任KDC；5） KDC能解密用戶間通信的內(nèi)容n 公開密鑰密碼起源1） 公鑰密碼又稱為雙鑰密碼和非對(duì)稱密碼，是1976年由D

4、iffie和Hellman在其“密碼學(xué)新方向”一文中提出的，見劃時(shí)代的文獻(xiàn)：W.Diffie and M.E.Hellman, New Directrions inCryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976,PP.644-654；2） RSA公鑰算法是由Rivest,Shamir和Adleman在1978年提出來的, Communitions of the ACM. Vol.21.No.2.Feb. 1978, PP.120-126n 公開密鑰密碼的重要特性1. 加密與解密由不同的密鑰

5、完成；加密：XY：Y = EKU(X)；加密密鑰是公開的；解密：YX： X = DKR(Y) = DKR(EKU(X)； 解密密鑰是保密的；2. 知道加密算法,從加密密鑰得到解密密鑰在計(jì)算上是不可行的；3. 兩個(gè)密鑰中任何一個(gè)都可以用作加密而另一個(gè)用作解密(不是必須的)；X = DKR(EKU(X) = EKU(DKR(X)n 基于公開密鑰的加密過程n 基于公開密鑰的鑒別過程n 用公鑰密碼實(shí)現(xiàn)保密用戶擁有自己的密鑰對(duì)(KU,KR)；公鑰KU公開，私鑰KR保密；AB：Y=EKUb(X)B： DKRb(Y)= DKRb(EKUb(X)=Xn 用公鑰密碼實(shí)現(xiàn)鑒別條件：兩個(gè)密鑰中任何一個(gè)都可以用作加密

6、而另一個(gè)用作解密鑒別：AALL: Y=EKRa(X)ALL： DKUa(Y)=DKUa(EKRa(X)=Xn 公鑰密鑰的應(yīng)用范圍加密/解密：發(fā)送方用接收方的公開密鑰加密報(bào)文；數(shù)字簽名(身份鑒別)：發(fā)送用自己的私有密鑰“簽署”報(bào)文；密鑰交換：兩方合作以便交換會(huì)話密鑰。n 基本思想和要求： 涉及到各方：發(fā)送方、接收方、攻擊者； 涉及到數(shù)據(jù)：公鑰、私鑰、明文、密文； 公鑰算法的條件：1） 產(chǎn)生一對(duì)密鑰是計(jì)算可行的；2） 已知公鑰和明文，產(chǎn)生密文是計(jì)算可行的；3） 接收方利用私鑰來解密密文是計(jì)算可行的；4） 對(duì)于攻擊者，利用公鑰來推斷私鑰是計(jì)算不可行的；5） 已知公鑰和密文，恢復(fù)明文是計(jì)算不可行的；6

7、） (可選)加密和解密的順序可交換。這些要求最終可以歸結(jié)為一個(gè)叫陷門單向函數(shù)：?jiǎn)蜗蛳蓍T函數(shù)是滿足下列條件的函數(shù)f：(1)給定x，計(jì)算y=fk(x)是容易的；(2)給定y, 計(jì)算x使x=fk-1(y)是不可行的。(3)存在k，已知k 時(shí)，對(duì)給定的任何y，若相應(yīng)的x存在，則計(jì)算x使fk-1(x) 是容易的。n 公鑰密碼基于的數(shù)學(xué)難題1） 背包問題；2） 大整數(shù)分解問題（The Integer Factorization Problem,RSA體制）；3） 有限域的乘法群上的離散對(duì)數(shù)問題(The Discrete Logarithm Problem,ElGamal體制)；4） 橢圓曲線上的離散對(duì)數(shù)問

8、題（The Elliptic Curve Discrete Logarithm Problem,類比的ElGamal體制） n 經(jīng)典例子：1） Diffie-Hellman密鑰交換算法；2） 背包算法；3） RSA算法；4） EIGamal算法；5） 橢圓曲線密碼算法ECC一、 Diffie-Hellman密鑰交換Diffie-Hellman密鑰交換算法的有效性依賴于計(jì)算離散對(duì)數(shù)的難度。簡(jiǎn)言之，可以如下定義離散對(duì)數(shù)：首先定義一個(gè)素?cái)?shù)p的原根，為其各次冪產(chǎn)生從1 到p-1的所有整數(shù)根，也就是說，如果a是素?cái)?shù)p的一個(gè)原根，那么數(shù)值 a mod p, a2 mod p, ., ap-1 mod p是

9、各不相同的整數(shù)，并且以某種排列方式組成了從1到p-1的所有整數(shù)。對(duì)于一個(gè)整數(shù)b和素?cái)?shù)p的一個(gè)原根a，可以找到惟一的指數(shù)i，使得 b = ai mod p 其中0 i (p-1)指數(shù)i稱為b的以a為基數(shù)的模p的離散對(duì)數(shù)或者指數(shù)。該值被記為inda ,p(b)?；诖吮尘爸R(shí)，可以定義Diffie-Hellman密鑰交換算法。該算法描述如下：1、有兩個(gè)全局公開的參數(shù)，一個(gè)素?cái)?shù)P和一個(gè)整數(shù)a，a是P的一個(gè)原根。2、假設(shè)用戶A和B希望交換一個(gè)密鑰，用戶A選擇一個(gè)作為私有密鑰的隨機(jī)數(shù)XAP，并計(jì)算公開密鑰Ya=aXa mod p。A對(duì)XA的值保密存放而使YA能被B公開獲得。類似地，用戶B選擇一個(gè)私有的隨

10、機(jī)數(shù)XBP，并計(jì)算公開密鑰Yb=aXb mod p。B對(duì)XB的值保密存放而使YB能被A公開獲得。3、用戶A產(chǎn)生共享秘密密鑰的計(jì)算方式是K=YbXa mod p。同樣，用戶B產(chǎn)生共享秘密密鑰的計(jì)算是K=YaXb mod p。這兩個(gè)計(jì)算產(chǎn)生相同的結(jié)果： K = (YB)XA mod P = (aXB mod P)XA mod P = (aXB)XA mod P （根據(jù)取模運(yùn)算規(guī)則得到） = aXBXA mod P = (aXA)XB mod P = (aXA mod P)XB mod P = (YA)XB mod P因此相當(dāng)于雙方已經(jīng)交換了一個(gè)相同的秘密密鑰。4、因?yàn)閄A和XB是保密的，一個(gè)敵對(duì)方

11、可以利用的參數(shù)只有P、a、YA和YB。因而敵對(duì)方被迫取離散對(duì)數(shù)來確定密鑰。例如，要獲取用戶B的秘密密鑰，敵對(duì)方必須先計(jì)算 XB = inda ,P(YB)然后再使用用戶B采用的同樣方法計(jì)算其秘密密鑰K。Diffie-Hellman密鑰交換算法的安全性依賴于這樣一個(gè)事實(shí)：雖然計(jì)算以一個(gè)素?cái)?shù)為模的指數(shù)相對(duì)容易，但計(jì)算離散對(duì)數(shù)卻很困難。對(duì)于大的素?cái)?shù)，計(jì)算出離散對(duì)數(shù)幾乎是不可能的。下面給出例子。密鑰交換基于素?cái)?shù)P = 97和97的一個(gè)原根a = 5。A和B分別選擇私有密鑰XA = 36和XB = 58。每人計(jì)算其公開密鑰 YA = 536 = 50 mod 97 YB = 558 = 44 mod 9

12、7在他們相互獲取了公開密鑰之后，各自通過計(jì)算得到雙方共享的秘密密鑰如下： K = (YB)XA mod 97 = 4436 = 75 mod 97 K = (YA)XB mod 97 = 5058 = 75 mod 97從|50，44|出發(fā)，攻擊者要計(jì)算出75很不容易。 下圖給出了一個(gè)利用Diffie-Hellman計(jì)算的簡(jiǎn)單協(xié)議。 用戶A 用戶BYbYa產(chǎn)生隨機(jī)的Xa p計(jì)算Ya=aXa mod p計(jì)算K=YbXa mod p產(chǎn)生隨機(jī)的Xb aj (j = 1,i-1)，這樣的背包也被稱為簡(jiǎn)單背包 求解： 從最大的ai開始，如果S大于這個(gè)數(shù)，則減去ai，記xi為1，否則記xi為0 如此下去，

13、直到最小的ai 例如背包序列2, 3, 6, 13, 27, 52：求解70的背包；結(jié)果為2, 3, 13, 52；所以，密文70對(duì)應(yīng)的明文為110101。3、基于背包問題的公鑰密碼系統(tǒng)MH公鑰算法 加密 將明文分為長度為n的塊X=(x1,xn) 然后用公鑰A = (a1, , an)，將明文變?yōu)槊芪?S = E(X) = ai xi 解密 先計(jì)算S = w-1S mod m，再求解簡(jiǎn)單背包問題S = aixi4、Eaxmple-從私鑰計(jì)算公鑰 私鑰2,3,6,13,27,52，且 n=31, m=1052*31 mod 105= 623*31 mod 105=936*31 mod 105=8

14、113*31 mod 105= 8827*31 mod 105=10252*31 mod 105= 37 公鑰62,93,81,88,102,375、Eaxmple-加密6、Eaxmple-解密7、背包密碼系統(tǒng)的意義：1） 是第一個(gè)公鑰密碼系統(tǒng)；2） 有較好的理論價(jià)值；3） 在實(shí)踐過程中，大多數(shù)的背包方案都已被破解，或者證明存在缺陷。 三、RSA算法 1977年由Ron Rivest、Adi Shamir和Len Adleman發(fā)明，1978年公布 是一種分組加密算法。 明文和密文在0n-1之間,n是一個(gè)正整數(shù) 應(yīng)用最廣泛的公鑰密碼算法 只在美國申請(qǐng)專利，且已于2000年9月到期1、RSA算法

15、描述RSA加、解密算法(1978 Rivest,Shamir,Adelman) 分組大小為k, 2k n 2k+1 公開密鑰n（兩素?cái)?shù)p和q的乘積）（推薦p,q等長）e（與(p-1)(q-1)互素）ed1(mod(p-1)(q-1) 私人密鑰d（e-1 mod(p-1)(q-1) ） 加密c=me mod n 解密m=cdmod n 2、RSA密鑰生成原理 3、RSA密碼體制的實(shí)現(xiàn)（p139）實(shí)現(xiàn)的步驟如下：Bob為實(shí)現(xiàn)者(1)Bob尋找出兩個(gè)大素?cái)?shù)p和q(2)Bob計(jì)算出n=pq和 (n)=(p-1)(q-1).(3)Bob選擇一個(gè)隨機(jī)數(shù)e(0e (n)，滿足（e， (n)）1(4)Bob使

16、用輾轉(zhuǎn)相除法計(jì)算d=e-1(mod (n)(5)Bob在目錄中公開n和e作為她的公開鑰。選好這些參數(shù)后，將明文劃分成塊，使得每個(gè)明文報(bào)文P長度m滿足0mn。加密P時(shí)，計(jì)算CPe(mod n)，解密C時(shí)計(jì)算PCd(mod n)。由于模運(yùn)算的對(duì)稱性，可以證明，在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。為實(shí)現(xiàn)加密，需要公開(e, n)，為實(shí)現(xiàn)解密需要(d, n)。4、example（1）若Bob選擇了p=101和q113（2）那么，n=11413, (n)=10011211200；（3）然而1120026527，一個(gè)正整數(shù)e能用作加密指數(shù)，當(dāng)且僅當(dāng)e不能被2，5，7所整除。假設(shè)Bob選擇了e=3533

17、，（4）那么用Euclidean算法將求得：d=e -1 6597(mod 11200), 于是Bob的解密密鑰d=6597.（5）Bob在一個(gè)目錄中公開n=11413和e=3533（6）現(xiàn)假設(shè)Alice想發(fā)送明文9726給Bob，她計(jì)算：97263533(mod 11413)=5761，且在一個(gè)信道上發(fā)送密文5761。（7）當(dāng)Bob接收到密文5761時(shí)，他用他的秘密解密指數(shù)（私鑰）d6597進(jìn)行解密：57616597（mod 11413)=97265、實(shí)現(xiàn)要求若使RSA安全，p與q必為足夠大的素?cái)?shù)，使分析者沒有辦法在多項(xiàng)式時(shí)間內(nèi)將n分解出來。建議選擇p和q大約是100位的十進(jìn)制素?cái)?shù)。模n的長

18、度要求至少是512比特。EDI攻擊標(biāo)準(zhǔn)使用的RSA算法中規(guī)定n的長度為512至1024比特位之間，但必須是128的倍數(shù)。國際數(shù)字簽名標(biāo)準(zhǔn)ISO/IEC 9796中規(guī)定n的長度位512比特位。至1996年，建議使用768位的模n。6、素?cái)?shù)的選取 為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)RSA模n的素因子p和q還有如下要求：(1)|p-q|很大，通常p和q的長度相同；(2)p-1 和q-1分別含有大素因子p1和q1(3)P1-1和q1-1分別含有大素因子p2和q2(4)p+1和q+1分別含有大素因子p3和q37、加密指數(shù)e的選取 為了提高加密速度，通常取e為特定的小整數(shù)，如EDI國際標(biāo)準(zhǔn)中規(guī)定e216 +1，ISO/IEC9796中甚至允許取e3。這時(shí)加密速度一般比解密速度快10倍以上。e2161優(yōu)于e3之處在于它能夠抵抗對(duì)RSA的小加密指數(shù)攻擊8、 RSA 加密算法的缺點(diǎn)1)產(chǎn)生密鑰很麻煩，受到