Lecture06_公鑰密碼體制

1、l學(xué)習(xí)要點(diǎn)：學(xué)習(xí)要點(diǎn)：了解非對(duì)稱密碼體制的提出背景、基本思想了解非對(duì)稱密碼體制的提出背景、基本思想了解非對(duì)稱密碼體制的基本應(yīng)用方向了解非對(duì)稱密碼體制的基本應(yīng)用方向掌握三種典型的公鑰密碼體制掌握三種典型的公鑰密碼體制l DH密鑰交換算法密鑰交換算法lRSAlECCl問(wèn)題的提出：?jiǎn)栴}的提出： l密鑰管理困難密鑰管理困難傳統(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,950n

2、= 5000 時(shí)時(shí)C( 5000,2)= 12,497,500l陌生人間的保密通信問(wèn)題陌生人間的保密通信問(wèn)題 l數(shù)字簽名的問(wèn)題數(shù)字簽名的問(wèn)題傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的需求傳統(tǒng)加密算法無(wú)法實(shí)現(xiàn)抗抵賴的需求l公鑰密碼又稱為雙鑰密碼、非對(duì)稱密碼公鑰密碼又稱為雙鑰密碼、非對(duì)稱密碼l公鑰密碼體制提出的標(biāo)志性文獻(xiàn)：公鑰密碼體制提出的標(biāo)志性文獻(xiàn)：W.Diffie and M.E.Hellman, New Directions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654

3、（1）參與方）參與方B容易通過(guò)計(jì)算產(chǎn)生一對(duì)密鑰（公開密鑰容易通過(guò)計(jì)算產(chǎn)生一對(duì)密鑰（公開密鑰KUb和私和私有密鑰有密鑰KRb）。）。（2）在知道公開密鑰和待加密報(bào)文）在知道公開密鑰和待加密報(bào)文M的情況下，對(duì)于發(fā)送方的情況下，對(duì)于發(fā)送方A，很容易通過(guò)計(jì)算產(chǎn)生對(duì)應(yīng)的密文：很容易通過(guò)計(jì)算產(chǎn)生對(duì)應(yīng)的密文：CEKUb（M）（3）接收方）接收方B使用私有密鑰容易通過(guò)計(jì)算解密所得的密文以便使用私有密鑰容易通過(guò)計(jì)算解密所得的密文以便恢復(fù)原來(lái)的報(bào)文：恢復(fù)原來(lái)的報(bào)文：MDKRb（C）DKRb（EKUb（M）（4）敵對(duì)方即使知道公開密鑰）敵對(duì)方即使知道公開密鑰KUb，要確定私有密鑰，要確定私有密鑰KRb在計(jì)在計(jì)算上是

4、不可行算上是不可行（5）敵對(duì)方即使知道公開密鑰）敵對(duì)方即使知道公開密鑰KUb和密文和密文C，要想恢復(fù)原來(lái)的，要想恢復(fù)原來(lái)的報(bào)文報(bào)文M在計(jì)算上也是不可行的。在計(jì)算上也是不可行的。（6）加密和解密函數(shù)可以以兩個(gè)次序中的任何一個(gè)來(lái)使用）加密和解密函數(shù)可以以兩個(gè)次序中的任何一個(gè)來(lái)使用: M = DKRb(EKUb(M) (機(jī)密性機(jī)密性) M = DKUb(EKRb(M) （數(shù)字簽名）（數(shù)字簽名）注注：1 1* *. . 僅滿足僅滿足(1)(1)、(2)(2)兩條的稱為單向函數(shù)；第兩條的稱為單向函數(shù)；第(3)(3)條稱為陷門性，條稱為陷門性，s s 稱為陷門信息。稱為陷門信息。 2 2* *. . 加密

5、密鑰便稱為公開密鑰，記為加密密鑰便稱為公開密鑰，記為PkPk。 f f函數(shù)的設(shè)計(jì)者將函數(shù)的設(shè)計(jì)者將s s 保保密，用作解密密鑰，此時(shí)密，用作解密密鑰，此時(shí)s s 稱為秘密密鑰，記為稱為秘密密鑰，記為SkSk。由于加密函。由于加密函數(shù)是公開的，任何人都可以將信息數(shù)是公開的，任何人都可以將信息x x加密成加密成y y= =f f( (x x) )，然后送給函，然后送給函數(shù)的設(shè)計(jì)者（當(dāng)然可以通過(guò)不安全信道傳送）；由于設(shè)計(jì)者擁有數(shù)的設(shè)計(jì)者（當(dāng)然可以通過(guò)不安全信道傳送）；由于設(shè)計(jì)者擁有SkSk，他自然可以解出，他自然可以解出x x= =f f-1-1( (y y) )。 3 3* *. .單向陷門函數(shù)的

6、第單向陷門函數(shù)的第(2)(2)條性質(zhì)表明竊聽者由截獲的密文條性質(zhì)表明竊聽者由截獲的密文y y= =f f( (x x) )推測(cè)推測(cè)x x是不可行的。是不可行的。是滿足下列條件的函數(shù)是滿足下列條件的函數(shù)f：(1)給定給定x，計(jì)算，計(jì)算y=f(x)是容易的是容易的(2)給定給定y, 計(jì)算計(jì)算x使使x=f-1(y)是困難的是困難的(3)存在存在s，已知，已知s 時(shí)時(shí),對(duì)給定的任何對(duì)給定的任何y，若相應(yīng)的，若相應(yīng)的x存在，則存在，則計(jì)算計(jì)算x使使x=f-1(y)是容易的是容易的陷門單向函數(shù)陷門單向函數(shù)l蠻力攻擊蠻力攻擊(與對(duì)密鑰類似與對(duì)密鑰類似)。l公開密鑰算法本身可能被攻破。公開密鑰算法本身可能被攻

7、破。尚未從數(shù)學(xué)上嚴(yán)格證明這種攻擊是不可能的尚未從數(shù)學(xué)上嚴(yán)格證明這種攻擊是不可能的l可能報(bào)文攻擊可能報(bào)文攻擊(對(duì)報(bào)文本身的蠻力攻擊對(duì)報(bào)文本身的蠻力攻擊)。l加密加密/解密解密l數(shù)字簽名數(shù)字簽名l會(huì)話密鑰交換會(huì)話密鑰交換l本原元：本原元：對(duì)于一個(gè)素?cái)?shù)對(duì)于一個(gè)素?cái)?shù)q，如果數(shù)值：，如果數(shù)值： ，是各不相同的整數(shù)，并且以某，是各不相同的整數(shù)，并且以某種排列方式組成了種排列方式組成了從從1到到q-1的所有整數(shù)的所有整數(shù)則稱整數(shù)則稱整數(shù)a是素?cái)?shù)是素?cái)?shù)q的一個(gè)本原元的一個(gè)本原元qamodqa mod2qaqmod1l離散對(duì)數(shù)問(wèn)題：離散對(duì)數(shù)問(wèn)題：對(duì)于一個(gè)整數(shù)對(duì)于一個(gè)整數(shù)b和素?cái)?shù)和素?cái)?shù)q的一個(gè)本原元的一個(gè)本原元a

8、，可，可以找到一個(gè)唯一的指數(shù)以找到一個(gè)唯一的指數(shù)i，使得：，使得：b=ai mod q (i 0, q-1) 成立，則指數(shù)成立，則指數(shù)i稱為稱為b的以的以a為底為底的模的模q的離散對(duì)數(shù)。的離散對(duì)數(shù)。l已知已知a, i, q, 容易計(jì)算出容易計(jì)算出bl給定給定b, a, q, 計(jì)算計(jì)算i非常困難，即離散對(duì)數(shù)問(wèn)題非常困難，即離散對(duì)數(shù)問(wèn)題l一個(gè)素?cái)?shù)一個(gè)素?cái)?shù)q和一個(gè)整數(shù)和一個(gè)整數(shù)a（均公開），（均公開），a是是q的一個(gè)本原元的一個(gè)本原元l用戶用戶A選擇一個(gè)隨機(jī)數(shù)選擇一個(gè)隨機(jī)數(shù)XAq，并計(jì)算，并計(jì)算 l類似地，用戶類似地，用戶B選擇一個(gè)隨機(jī)數(shù)選擇一個(gè)隨機(jī)數(shù)XBq,并計(jì)算并計(jì)算 l每一方都對(duì)每一方都對(duì)X的

9、值保密存放而使得的值保密存放而使得Y的值對(duì)于另一方可以公的值對(duì)于另一方可以公開得到開得到l用戶用戶A計(jì)算密鑰：計(jì)算密鑰： l用戶用戶B計(jì)算密鑰：計(jì)算密鑰：l雙方以雙方以K作為加、解密密鑰，以對(duì)稱密鑰算法進(jìn)行保密通信作為加、解密密鑰，以對(duì)稱密鑰算法進(jìn)行保密通信qaYAXAmodqaYBXBmodqYKAXBmod)(qYKBXAmod)(l素?cái)?shù)素?cái)?shù)q=97,它的一個(gè)本原元它的一個(gè)本原元a=5lA和和B分別選擇隨機(jī)數(shù)分別選擇隨機(jī)數(shù)Xa=36和和Xb=58lA計(jì)算公開密鑰：計(jì)算公開密鑰：Ya=536mod97=50mod97 lB計(jì)算公開密鑰：計(jì)算公開密鑰：Yb=558mod97=44mod97 l

10、A計(jì)算會(huì)話密鑰：計(jì)算會(huì)話密鑰：K= 4436mod97=75mod97lB計(jì)算會(huì)話密鑰：計(jì)算會(huì)話密鑰：K= 5058mod97=75mod97由由Rivest,Shamir和和Adleman在在1978年提出來(lái)的年提出來(lái)的數(shù)學(xué)基礎(chǔ)數(shù)學(xué)基礎(chǔ): Euler定理，其安全性建立在定理，其安全性建立在大整數(shù)因子分解大整數(shù)因子分解的的困難性之上困難性之上l明文空間明文空間P密文空間密文空間C=Znl密鑰的生成密鑰的生成選擇互異素?cái)?shù)選擇互異素?cái)?shù)p,q，計(jì)算，計(jì)算n=p*q, (n)=(p-1)(q-1), 選選擇整數(shù)擇整數(shù)e使使( (n),e)=1,0e (n),計(jì)算計(jì)算d,使使 d=e-1mod (n)公

11、鑰公鑰Pk=e,n私鑰私鑰Sk=d,nl加密加密 (用用e,n)明文：明文：Mn 密文：密文：C=Me( mod n )l解密解密 (用用d,n) 密文：密文：C 明文：明文：M=Cd（mod n )l若若BobBob選擇了選擇了p=7p=7和和q q1717l則則n=119, n=119, (n)=6 (n)=6161696962 25 53 3，一個(gè)正整數(shù)，一個(gè)正整數(shù)e e能用作加密能用作加密指數(shù)，當(dāng)且僅當(dāng)指數(shù)，當(dāng)且僅當(dāng)e e不能被不能被2 2，3 3所整除所整除l假設(shè)假設(shè)BobBob選擇選擇e=5e=5，那么用輾轉(zhuǎn)相除法將求得：，那么用輾轉(zhuǎn)相除法將求得： d=e d=e -1-1 77(

12、mod 77(mod 96)96)lBobBob的解密密鑰的解密密鑰d=77,119d=77,119，公開，公開5,1195,119 l現(xiàn)假設(shè)現(xiàn)假設(shè)AliceAlice想發(fā)送明文想發(fā)送明文1919給給BobBob步驟步驟：Bob為實(shí)現(xiàn)者為實(shí)現(xiàn)者lBob尋找出兩個(gè)大素?cái)?shù)尋找出兩個(gè)大素?cái)?shù)p和和qlBob計(jì)算出計(jì)算出n=pq和和 (n)=(p-1)(q-1).lBob選擇一個(gè)隨機(jī)數(shù)選擇一個(gè)隨機(jī)數(shù)e(0e (n)，滿足（，滿足（e， (n)）1lBob使用輾轉(zhuǎn)相除法計(jì)算使用輾轉(zhuǎn)相除法計(jì)算d=e-1(mod (n)l Bob在目錄中公開在目錄中公開n和和e作為她的公開鑰作為她的公開鑰密碼分析者攻擊密碼分

13、析者攻擊RSA體制的關(guān)鍵點(diǎn)在于如何分解體制的關(guān)鍵點(diǎn)在于如何分解n。若。若分解成功使分解成功使n=pq，則可以算出，則可以算出(n)（p-1)(q-1)，然后，然后由公開的由公開的e，解出秘密的，解出秘密的d。要求：要求：若使若使RSA安全，安全，p與與q必為足夠大的素?cái)?shù)，使必為足夠大的素?cái)?shù)，使分析者沒(méi)有辦法在有效時(shí)間內(nèi)將分析者沒(méi)有辦法在有效時(shí)間內(nèi)將n分解出來(lái)。建議選擇分解出來(lái)。建議選擇p和和q大約是大約是100位的十進(jìn)制素?cái)?shù)。位的十進(jìn)制素?cái)?shù)。 模模n的長(zhǎng)度要求至少是的長(zhǎng)度要求至少是512比特。比特。 為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì)RSA模模n的素因子的素因子p和和

14、q還有如下要求：還有如下要求：(1)p, q的值應(yīng)當(dāng)不是很接近；的值應(yīng)當(dāng)不是很接近；(2)p-1 和和q-1分別含有大素因子分別含有大素因子(3)gcd(p-1,q-1)應(yīng)比較小。應(yīng)比較小。為了提高加密速度，通常取為了提高加密速度，通常取e為特定的小整數(shù)，如為特定的小整數(shù)，如EDI（電子數(shù)據(jù)交換）國(guó)際標(biāo)準(zhǔn)中規(guī)定（電子數(shù)據(jù)交換）國(guó)際標(biāo)準(zhǔn)中規(guī)定 e2161，ISO/IEC9796（國(guó)際標(biāo)準(zhǔn)化組織（國(guó)際標(biāo)準(zhǔn)化組織/國(guó)際電工委員會(huì)）中甚至國(guó)際電工委員會(huì)）中甚至允許取允許取e3。這時(shí)加密速度一般比解密速度快。這時(shí)加密速度一般比解密速度快10倍以上。倍以上。QX1X2X3Y1Y2Y310276001167

15、16011671168811168811779111779233982339172817117281719314231931427412231用用RSA算法加密與解密的過(guò)程：算法加密與解密的過(guò)程：例：明文例：明文=“RSA ALGORITHM”(1) 明文用數(shù)字表示明文用數(shù)字表示 空白空白=00， A=01, B=02, , Z=26 (兩位兩位十進(jìn)制數(shù)表示十進(jìn)制數(shù)表示)1819 0100 0112 0715 1809 2008 1300(2) 利用加密變換公式利用加密變換公式 C=mPK mod r, 即即C = 18191223 mod 2867=2756PK=1223=100110001

16、11 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223 (mod 2867) =18191024 1819128 181964 18194 18192 18191(mod 2867) =27562756 2001 0542 0669 2347 0408 1815選擇兩個(gè)大素?cái)?shù)選擇兩個(gè)大素?cái)?shù)p和和q，通常要求每個(gè)均大于，通常要求每個(gè)均大于10100。u計(jì)算計(jì)算npq和和z(p1)(q1)。u選擇一與選擇一與z互素的數(shù)、令其為互素的數(shù)、令其為d 。u找到一個(gè)找到一個(gè)e滿足滿足ed1 (mod z)。 選好這些參數(shù)后，將明文劃分成塊，使得每個(gè)明文報(bào)文

17、選好這些參數(shù)后，將明文劃分成塊，使得每個(gè)明文報(bào)文P長(zhǎng)度長(zhǎng)度m滿足滿足0mn。加密。加密P時(shí)，計(jì)算時(shí)，計(jì)算CPe(mod n)，解密，解密C時(shí)計(jì)算時(shí)計(jì)算PCd(mod n)。可以證明，在確定的范圍內(nèi)，加密。可以證明，在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。和解密函數(shù)是互逆的。 為實(shí)現(xiàn)加密，需要公開為實(shí)現(xiàn)加密，需要公開(e, n)，為實(shí)現(xiàn)解密需要，為實(shí)現(xiàn)解密需要(d, n)。如何計(jì)算如何計(jì)算ab mod n？如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？如何找到足夠大的素?cái)?shù)如何找到足夠大的素?cái)?shù)p和和q ? 要點(diǎn)要點(diǎn)1：(a x b) mod n = (a mod n) x (b mo

18、d n) mod n 要點(diǎn)要點(diǎn)2：a16=aaaaaaaaaaaaaaaa =a2, a4,a8, a16更一般性的問(wèn)題：更一般性的問(wèn)題：amm的二進(jìn)制表示為的二進(jìn)制表示為bkbk-1b0, 則則 計(jì)算計(jì)算am mod nam mod n = a(2i) mod n = ( a(2i) mod n) mod nbi 0bi 0ikiibm20 Square_and_Multiply(a, m, n) y 1for i 0 to k if bi = 1 y ay mod n a aa mod n return yMiller_Rabin_Test(n, a)1. 求求m, k 使得使得 n-1

19、= m *2k2. T = am mod n3. If (T = 1 | T = n-1) return True4. for i 1 to k-15.T (T T) mod n6.if T = 1 return False7.if T = n-1 return True8. return FALSE 返回值：返回值：TRUE: n可能是素?cái)?shù)可能是素?cái)?shù)FALSE: n一定不是素?cái)?shù)一定不是素?cái)?shù)應(yīng)用：應(yīng)用：隨機(jī)選擇隨機(jī)選擇a n, 計(jì)算計(jì)算s次，次，如果每次都返回如果每次都返回True，則這時(shí)則這時(shí)n是素?cái)?shù)的概率為是素?cái)?shù)的概率為(1 - 1/4s)如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？如何判定一個(gè)給定的整

20、數(shù)是素?cái)?shù)？1. 隨機(jī)選一個(gè)奇數(shù)隨機(jī)選一個(gè)奇數(shù)n (偽隨機(jī)數(shù)發(fā)生器偽隨機(jī)數(shù)發(fā)生器)2. 隨機(jī)選擇一個(gè)整數(shù)隨機(jī)選擇一個(gè)整數(shù)a n3. 執(zhí)行概率素?cái)?shù)判定測(cè)試執(zhí)行概率素?cái)?shù)判定測(cè)試,如果如果n 未測(cè)試通過(guò)未測(cè)試通過(guò),則則 拒絕數(shù)值拒絕數(shù)值n, 轉(zhuǎn)向步驟轉(zhuǎn)向步驟14. 如果如果n已通過(guò)足夠的測(cè)試已通過(guò)足夠的測(cè)試, 則接受則接受n, 否則轉(zhuǎn)向步驟否則轉(zhuǎn)向步驟2;說(shuō)明：說(shuō)明： 隨機(jī)選取大約用隨機(jī)選取大約用 ln(N)/2的次數(shù)，如的次數(shù)，如ln(2200)/2=70 好在生成密鑰對(duì)時(shí)才用到，慢一點(diǎn)還可忍受。好在生成密鑰對(duì)時(shí)才用到，慢一點(diǎn)還可忍受。 確定素?cái)?shù)確定素?cái)?shù)p和和q以后，只需選取以后，只需選取e, 滿足

21、滿足gcd(e, (n)=1, 計(jì)算計(jì)算d = e-1 mod (n) （擴(kuò)展的歐拉算法）（擴(kuò)展的歐拉算法）如何找到足夠大的素?cái)?shù)如何找到足夠大的素?cái)?shù)p和和q ?p和和q在長(zhǎng)度上應(yīng)僅差幾個(gè)數(shù)位，即在長(zhǎng)度上應(yīng)僅差幾個(gè)數(shù)位，即p和和q應(yīng)是應(yīng)是1075 到到10100（p-1）和（）和（q-1）都應(yīng)包含一個(gè)較大的素?cái)?shù)因子）都應(yīng)包含一個(gè)較大的素?cái)?shù)因子gcd(p-1, q-1)應(yīng)比較小應(yīng)比較小如果如果en 且且 dn1/4,則則d可以很容易確定可以很容易確定算法的發(fā)明者建議算法的發(fā)明者建議數(shù)字簽名數(shù)字簽名方案：一個(gè)簽名方案是由簽署算法與驗(yàn)證算法方案：一個(gè)簽名方案是由簽署算法與驗(yàn)證算法兩部分構(gòu)成?？捎晌逶P(guān)

22、系組（兩部分構(gòu)成?？捎晌逶P(guān)系組（M,A,K,S,V）來(lái)描述：）來(lái)描述：(1)M是由一切可能是由一切可能消息消息所構(gòu)成的有限集合；所構(gòu)成的有限集合；(2)A是一切可能的簽名的有限集合；是一切可能的簽名的有限集合；(3)K為有限密鑰空間，是一些可能密鑰的有限集合；為有限密鑰空間，是一些可能密鑰的有限集合；(4)任意任意k K，有簽署算法，有簽署算法Sigk S且有對(duì)應(yīng)的驗(yàn)證算且有對(duì)應(yīng)的驗(yàn)證算法法VerkV,對(duì)每一個(gè)對(duì)每一個(gè)Sigk和和Verk滿足條件：任意一個(gè)滿足條件：任意一個(gè)簽名：簽名：Ver(x,y)= RSA的數(shù)字簽名應(yīng)用的數(shù)字簽名應(yīng)用真 若y=sig(x)假 若ySig(x)l選取整數(shù)選

23、取整數(shù)n=pq,M=A=Znl定義密鑰集合定義密鑰集合K=(n,e,p,q,d)|n=pq,d*e 1(mod (n)ln和和e為公鑰；為公鑰；p,q,d為保密的（私鑰）為保密的（私鑰）l對(duì)對(duì)xM, Bob要對(duì)要對(duì)x簽名，取簽名，取kK：lSigk(x) xd(mod n) y(mod n)l Verk(x,y)=真真 x ye(mod n)RSA的數(shù)字簽名方案的數(shù)字簽名方案假設(shè)假設(shè)Alice想把簽了名的消息加密送給想把簽了名的消息加密送給Bob：對(duì)明文：對(duì)明文x，Alice計(jì)計(jì)算對(duì)算對(duì)x的簽名的簽名y=SigAlice(x)，然后用，然后用Bob的公鑰加密函數(shù)的公鑰加密函數(shù)eBob,算出算出

24、z=eBob(x,y) ,Alice 將將z傳給傳給BobBob收到收到z后，先解密：后，先解密：dBob(z)=dBobeBob(x,y)=(x,y)后檢驗(yàn)：后檢驗(yàn)： VerAlice(x,y)= 真？真？問(wèn)題：?jiǎn)栴}：若若AliceAlice首先對(duì)消息首先對(duì)消息x x進(jìn)行加密進(jìn)行加密,z=e,z=eBobBob(x),(x),然后再簽名，然后再簽名， y=Sigy=SigAliceAlice(e(eBobBob(x),(x),結(jié)果如何呢？結(jié)果如何呢？Alice 將（將（z,y)傳給傳給Bob，Bob先將先將z解密，獲取解密，獲取x;然后用然后用VerAlice檢驗(yàn)關(guān)于檢驗(yàn)關(guān)于x的加密簽名的加

25、密簽名y一個(gè)潛在問(wèn)題一個(gè)潛在問(wèn)題：如果：如果Oscar獲得了這對(duì)（獲得了這對(duì)（z,y)，他能用自己，他能用自己的簽名來(lái)替代的簽名來(lái)替代Alice的簽名的簽名 y =SigOscar(eBob(x)簽名消息的加密傳遞問(wèn)題簽名消息的加密傳遞問(wèn)題 l橢圓曲線密碼體制以高效性著稱橢圓曲線密碼體制以高效性著稱l由由Neal Koblitz和和Victor Miller在在1985年年分別提出分別提出lECC的安全性基于橢圓曲線離散對(duì)數(shù)問(wèn)的安全性基于橢圓曲線離散對(duì)數(shù)問(wèn)題的難解性題的難解性l密鑰長(zhǎng)度大大地減少密鑰長(zhǎng)度大大地減少l是目前已知公鑰密碼體制中每位提供加是目前已知公鑰密碼體制中每位提供加密強(qiáng)度最高的

26、一種體制密強(qiáng)度最高的一種體制 定義：定義：橢圓曲線是一個(gè)具有兩個(gè)變?cè)獧E圓曲線是一個(gè)具有兩個(gè)變?cè)獂和和y的三的三次方程，它是滿足：次方程，它是滿足： Y2+aXY+bY=X3+cX2+dX+e 的所有點(diǎn)的所有點(diǎn)(X,Y)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn)點(diǎn)O （認(rèn)為其（認(rèn)為其y坐標(biāo)無(wú)窮大）坐標(biāo)無(wú)窮大）l實(shí)數(shù)域上的橢圓曲線是對(duì)于固定的實(shí)數(shù)域上的橢圓曲線是對(duì)于固定的a、b值，滿足形如方程：值，滿足形如方程：Y2=X3+aX+b 的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn)遠(yuǎn)點(diǎn)l其中其中a、b是實(shí)數(shù)，是實(shí)數(shù)，4*a2 + 27*b3 != 0, X和

27、和Y在實(shí)數(shù)域上取值在實(shí)數(shù)域上取值lGF(p)域上的橢圓曲線是對(duì)于固定的域上的橢圓曲線是對(duì)于固定的a、b值，滿足形如方程：值，滿足形如方程：Y2=X3+aX+b mod(p) 的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn)遠(yuǎn)點(diǎn)l其中其中a、b，X和和Y在在GF(p)域上取值域上取值 0, p-1， 且滿足且滿足4*a2 + 27*b3 != 0l如果如果E是定義在是定義在GF(p)域上的橢圓曲線，域上的橢圓曲線，N是是E上的點(diǎn)的個(gè)數(shù)，則：上的點(diǎn)的個(gè)數(shù)，則： ppN2) 1(l是對(duì)于固定的是對(duì)于固定的a、b值，滿足形如方程：值，滿足形如方程：Y2+XY=X3+aX2+b

28、的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn)遠(yuǎn)點(diǎn)l其中其中a、b，X和和Y在在GF(2m)域上取值域上取值lGF(2m)域上的元素是域上的元素是m位的二進(jìn)制串位的二進(jìn)制串 l由多項(xiàng)式定義的域由多項(xiàng)式定義的域GF（24）l生成元為生成元為g=(0010)，g的各冪分別是的各冪分別是 1)(4xxxfg0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(10

29、01)g15=(0001)l考慮橢圓曲線：考慮橢圓曲線：l點(diǎn)點(diǎn)(g5, g3)滿足該方程滿足該方程 l(g3)2 + g5 g3 = (g5) 3 + g4 (g5) 2 + 1 g6 + g8 = g15 +g14 + 1 (1100) + (0101) = (0001) + (1001) + (0001) (1001) = (1001) 12432xgxxyylAbel群群 ：l加法規(guī)則加法規(guī)則1：l加法規(guī)則加法規(guī)則2：l加法規(guī)則加法規(guī)則3：互逆點(diǎn)：互逆點(diǎn)l加法規(guī)則加法規(guī)則4：加法交換律：加法交換律l加法規(guī)則加法規(guī)則5：加法結(jié)合律：加法結(jié)合律 l加法規(guī)則加法規(guī)則6： l加法規(guī)則加法規(guī)則7

30、：0)(mod27423pbaOOOPOPOQPPQQPRQPRQP)()(332211,yxSyxQyxP2123xxx1313)(yxxy1212xxyy),(),(2),(,33111111yxQyxPyxPyxP1232xx1313)(yxxy12123yax lGF（2m)域域l加法規(guī)則加法規(guī)則3 ：如果，則如果，則l加法規(guī)則加法規(guī)則6 ：l加法規(guī)則加法規(guī)則7 ：332211,yxSyxQyxPaxxx212313313)(yxxxy1212xxyy),(),(2),(,33111111yxQyxPyxPyxP3213*) 1(xxyax231121xyx ,Px y,Px xyl標(biāo)

31、量乘標(biāo)量乘l階階P是橢圓曲線是橢圓曲線E上的一點(diǎn)，若存在最小的正上的一點(diǎn)，若存在最小的正整數(shù)整數(shù)n，使得，使得nP=O，則稱，則稱n是點(diǎn)是點(diǎn)P的階的階 mPPPmPlGF（23）上橢圓曲線）上橢圓曲線 ：l設(shè)：設(shè)：l求求P1P2和和2P1132xxy10, 31P7 , 92P112)23mod1()23(mod21391071212xxyy1723mod109931122123xxx2023mod14410)173(11)(1313yxxy6424423mod123mod2050223mod281021)3(3232121yax723mod3032)6(22123xx1223mod3410)

32、73(6)(1313yxxyl橢圓曲線離散對(duì)數(shù)問(wèn)題橢圓曲線離散對(duì)數(shù)問(wèn)題已知橢圓曲線已知橢圓曲線E和點(diǎn)和點(diǎn)P，隨機(jī)生成一個(gè)整數(shù)，隨機(jī)生成一個(gè)整數(shù)d，容易計(jì)算容易計(jì)算:Q=d*P，但給定，但給定Q和和P,計(jì)算計(jì)算d就相就相對(duì)困難對(duì)困難 l選取選取:一個(gè)基域一個(gè)基域GF(p)定義在該基域上的橢圓曲線定義在該基域上的橢圓曲線Ep(a,b)E上的一個(gè)擁有素?cái)?shù)階上的一個(gè)擁有素?cái)?shù)階n的點(diǎn)的點(diǎn)Pl其中有限域其中有限域GF(p) ，橢圓曲線參數(shù)，橢圓曲線參數(shù)a,b，點(diǎn)點(diǎn)P和階和階n都是公開信息都是公開信息l在區(qū)間在區(qū)間1,n-1中隨機(jī)選取一個(gè)整數(shù)中隨機(jī)選取一個(gè)整數(shù)dl計(jì)算計(jì)算:Q=d*Pl實(shí)體的實(shí)體的公開密鑰公

33、開密鑰:點(diǎn)點(diǎn)Q私鑰私鑰:整數(shù)整數(shù)d l待發(fā)送消息：待發(fā)送消息：AB：Ml查找查找B的公開密鑰：的公開密鑰：Ql將消息將消息M表示成一個(gè)域元素表示成一個(gè)域元素:ml在區(qū)間在區(qū)間1, n-1中隨機(jī)選取一個(gè)整數(shù)中隨機(jī)選取一個(gè)整數(shù)kl計(jì)算點(diǎn)計(jì)算點(diǎn):(x1,y1)=kPl計(jì)算點(diǎn)計(jì)算點(diǎn):(x2,y2)=kQ，如果，如果x2=0，則返回第，則返回第(3)步步l計(jì)算計(jì)算:c=mx21.傳送加密數(shù)據(jù)傳送加密數(shù)據(jù)(x1,y1,c)給給B l當(dāng)實(shí)體當(dāng)實(shí)體B解密從解密從A收到的密文收到的密文(x1,y1,c)時(shí)，時(shí)，執(zhí)行步驟：執(zhí)行步驟：使用私鑰使用私鑰d，計(jì)算點(diǎn)，計(jì)算點(diǎn):(x2,y2)=d (x1,y1)計(jì)算計(jì)算 ，

34、恢復(fù)出消息，恢復(fù)出消息m 12xcml任務(wù)：任務(wù)：BA：ml用戶用戶A選取隨機(jī)數(shù)（私鑰）選取隨機(jī)數(shù)（私鑰）dA，產(chǎn)生公開，產(chǎn)生公開密鑰密鑰:PA=dA*Gl用戶用戶B選取隨機(jī)數(shù)（私鑰）選取隨機(jī)數(shù)（私鑰）dB，并計(jì)算公，并計(jì)算公鑰：鑰：PB=dB*GlB計(jì)算并向計(jì)算并向A發(fā)送：發(fā)送：(PB，m+dB*PA)l用戶用戶A解密：解密：(m+dB*PA)dA*PBm l橢圓曲線橢圓曲線l設(shè)用戶設(shè)用戶A的私鑰為的私鑰為7，則公鑰為：，則公鑰為：1)設(shè)用戶設(shè)用戶B的消息的消息m編碼后為，且選取了編碼后為，且選取了隨機(jī)數(shù)隨機(jī)數(shù)2)用戶用戶B計(jì)算：，計(jì)算：，3）B向向A發(fā)送消息：發(fā)送消息：4)用戶用戶A計(jì)算：

35、計(jì)算：5)用戶用戶A計(jì)算：計(jì)算： 2213:22,133223xxyE5 ,10G21,177GPA1 ,11mP13Bd5 ,165 ,1013GdB18,2021,1713ABPd 19,1818,201 ,11ABmPdP 19,18,5 ,16 18,205 ,167 1 ,1181,2019,1818,2019,18l設(shè)設(shè)E是有限域是有限域GF(p)上的橢圓曲線，上的橢圓曲線，N為為橢圓曲線的階，橢圓曲線的階， 是明文空間到橢圓曲是明文空間到橢圓曲線群的嵌入線群的嵌入l用戶用戶A選取一個(gè)公鑰選取一個(gè)公鑰 ，私鑰，私鑰 ，滿，滿足，。足，。l對(duì)于消息對(duì)于消息m，用戶，用戶B加密消息為加密消息為 用戶用戶A解密過(guò)程為：解密過(guò)程為： mPm AeAdNdeAAmod1NeA1NdA1mAmPeCmmAAmAmPPdeCdP l橢圓曲線橢圓曲線 ，設(shè)消息，設(shè)消息m編編碼后的信息為碼后的信息為: ?？沈?yàn)證?？沈?yàn)證