1、密 碼 學（第九講）公開密鑰密碼（2）1目 錄1、密碼學的基本概念2、古典密碼3、數據加密標準（DES）4、高級數據加密標準（AES）5、中國商用密碼（SMS4）6、分組密碼的應用技術7、序列密碼8、習題課：復習對稱密碼9、公開密鑰密碼（1）2目 錄10、公開密鑰密碼（2）11、數字簽名（1）12、數字簽名（2）13、HASH函數14、認證15、密鑰管理16、PKI技術17、習題課：復習公鑰密碼18、總復習/檢查：綜合實驗3一、ELGamal公鑰密碼的基本情況1、基本情況：ELGamal密碼是除了RSA密碼之外最有代表性的公開密鑰密碼。RSA密碼建立在大合數分解的困難性之上。ELGamal密碼

2、建立在離散對數的困難性之上。4一、ELGamal公鑰密碼的基本情況2、離散對數問題：設p為素數，則模p的剩余構成有限域： Fp=0,1,2, ,p-1Fp 的非零元構成循環群Fp* Fp* =1,2, ,p-1 =，2，3，p-1，則稱為Fp*的生成元或模 p 的本原元。求的摸冪運算為:y =x mod p，1xp-1, 5一、ELGamal公鑰密碼的基本情況2、離散對數問題：求對數 X 的運算為 x=logy，1xp-1由于上述運算是定義在模p有限域上的，所以稱為離散對數運算。從x計算y是容易的。可是從y計算x就困難得多，利用目前最好的算法，對于小心選擇的p將至少需用O(p )次以上的運算，

3、只要p足夠大，求解離散對數問題是相當困難的。6二、 ELGamal公鑰密碼準備：隨機地選擇一個大素數p，且要求p-1有大素數因子。再選擇一個模p的本原元。將p和公開。 密鑰生成用戶隨機地選擇一個整數d作為自己的秘密的解密鑰，2dp-2 。計算y=d mod p，取y為自己的公開的加密鑰。由公開鑰y 計算秘密鑰d，必須求解離散對數，而這是極困難的。 7二、 ELGamal公鑰密碼 加密將明文消息M（0Mp-1)加密成密文的過程如下：隨機地選取一個整數k，2kp-2。計算： U y k mod p； C1k mod p； C2UM mod p；取 C（C1 ，C2）作為的密文。 8二、 ELGam

4、al公鑰密碼 解密將密文（C1 ，C2）解密的過程如下：計算VC1 d mod p；計算MC2 V -1 mod p。9二、 ELGamal公鑰密碼解密的可還原性可證明如下： C2 V-1 mod p (UM)V-1 mod p UM（C1 d）-1 mod p UM（k）d）-1 mod p UM（d）k）-1 mod p UM（y）k）-1 mod p UM（U）-1 mod p M mod p 10二、 ELGamal公鑰密碼 安全性由于ELGamal密碼的安全性建立在GF（p）離散對數的困難性之上，而目前尚無求解GF（p）離散對數的有效算法，所以在p足夠大時ELGamal密碼是安全的。

5、為了安全p應為150位以上的十進制數，而且p-1應有大素因子。為了安全加密和簽名所使用的k必須是一次性的。d和k都不能太小。11二、 ELGamal公鑰密碼 安全性如果 k不是一次性的，時間長了就可能被攻擊著獲得。又因y是公開密鑰，攻擊者自然知道。于是攻擊者就可以根據Uy k mod p計算出U，進而利用Euclid算法求出U1。又因為攻擊者可以獲得密文C2，于是可根據式C2UM mod p通過計算U1C2得到明文M。設用同一個k加密兩個不同的明文M和M，相應的密文為（C1 ，C2）和（C1，C2）。因為C2C2 MM，如果攻擊者知道M，則很容易求出M。 12二、 ELGamal公鑰密碼 EL

6、Gamal密碼的應用 由于ELGamal密碼的安全性得到世界公認，所以得到廣泛的應用。著名的美國數字簽名標準DSS，采用了ELGamal密碼的一種變形。為了適應不同的應用，人們在應用中總結出18種不同的ELGamal密碼的變形。13二、 ELGamal公鑰密碼 ELGamal密碼的應用 加解密速度快由于實際應用時ELGamal密碼運算的素數p比RSA要小，所以ELGamal密碼的加解密速度比RSA稍快。隨機數源由ELGamal密碼的解密鑰d和隨機數k都應是高質量的隨機數。因此，應用ELGamal密碼需要一個好的隨機數源，也就是說能夠快速地產生高質量的隨機數。大素數的選擇為了ELGamal密碼的

7、安全，p應為150位（十進制數）以上的大素數，而且p-1應有大素因子。 14三、橢圓曲線密碼1、橢圓曲線密碼的一般情況受ELGamal密碼啟發，在其它離散對數問題難解的群中，同樣可以構成ELGamal密碼。于是人們開始尋找其它離散問題難解的群。研究發現，有限域GF（p）上的橢圓曲線的解點構成交換群，而且離散對數問題是難解的。于是可在此群上建立ELGamal密碼，并稱為橢圓曲線密碼。15三、橢圓曲線密碼1、橢圓曲線密碼的一般情況橢圓曲線密碼已成為除RSA密碼之外呼聲最高的公鑰密碼之一。它密鑰短、簽名短，軟件實現規模小、硬件實現電路省電。普遍認為，160位長的橢圓曲線密碼的安全性相當于1024位的

8、RSA密碼，而且運算速度也較快。16三、橢圓曲線密碼1、橢圓曲線密碼的一般情況一些國際標準化組織已把橢圓曲線密碼作為新的信息安全標準。如，IEEE P1363/D4，ANSI F9.62，ANSI F9.63等標準，分別規范了橢圓曲線密碼在Internet協議安全、電子商務、Web服務器、空間通信、移動通信、智能卡等方面的應用。17三、橢圓曲線密碼2、橢圓曲線設p是大于3的素數，且4a3+27b2 0 mod p ，稱 y2 =x3 +ax+b ，a,bGF(p) 為GF（p）上的橢圓曲線。由橢圓曲線可得到一個同余方程： y2 =x3 +ax+b mod p其解為一個二元組，x,yGF(p)，

9、將此二元組描畫到橢圓曲線上便為一個點，于是又稱其為解點。18三、橢圓曲線密碼2、橢圓曲線 為了利用解點構成交換群，需要引進一個O元素，并定義如下的加法運算：定義單位元 引進一個無窮點O（，），簡記為0，作為0元素。 O（，）O（，）000 。并定義對于所有的解點P（x ，y）， P（x ，y）+OO+ P（x ，y）P（x ，y）。 19三、橢圓曲線密碼2、橢圓曲線定義逆元素 設P（x1 ，y1）和Q（x2 ，y2）是解點，如果x1=x2 且y1=-y2 ，則 P（x1 ，y1）Q（x2 ，y2）0 。這說明任何解點R（x ，y）的逆就是 R（x ，-y）。注意：規定無窮遠點的逆就是其自己。

10、O（，）-O（，）20三、橢圓曲線密碼2、橢圓曲線定義加法設P(x1，y1)Q(x2，y2)，且P和Q不互逆 ，則 P（x1 ，y1）Q（x2 ，y2）R（x3 ，y3） 。其中 x3 = 2 - x1 -x2 ， y3 = (x1 x3)- y1 ， =（y2 -y1 ）/(x2 - x1 ）。21三、橢圓曲線密碼2、橢圓曲線定義加法當P （x1 ，y1） = Q(x2，y2)時 P（x1 ，y1） Q(x2，y2) 2 P（x1 ，y1） R（x3 ，y3）。 其中 x3 = 2 - 2x1 ， y3 =(x1 x3)- y1 ， =（3x12 + a）/（2 y1）。 22三、橢圓曲線密

11、碼2、橢圓曲線作集合E=全體解點，無窮點O 。可以驗證，如上定義的集合E和加法運算構成加法交換群。復習：群的定義 G是一個非空集，定義了一種運算，且運算是自封閉的； 運算滿足結合律； G中有單位元； G中的元素都有逆元；23三、橢圓曲線密碼3、橢圓曲線解點加法運算的幾何意義： 設P（x1 ，y1）和Q（x2 ，y2）是橢圓曲線的兩個點，則連接P（x1 ，y1）和Q（x2 ，y2）的直線與橢圓曲線的另一交點關于橫軸的對稱點即為P（x1 ，y1）+Q（x2 ，y2）點。24三、橢圓曲線密碼3、橢圓曲線解點加法運算的幾何意義： xy0PQP+Q25三、橢圓曲線密碼4、舉例：取p=11，橢圓曲線y2=

12、x3 +x+6 。由于p較小，使GF(p)也較小，故可以利用窮舉的方法根據y2=x3 +x+6 mod 11求出所有解點。 復習：平方剩余 設p為素數，如果存在一個正整數x，使得 x2=a mod p,則稱 a是模p的平方剩余。26三、橢圓曲線密碼 x x3+x+6 mod 11 是否模11平方剩余 y 0 6 No 1 8 No 2 5 Yes 4,7 3 3 Yes 5,6 4 8 No 5 4 Yes 2,9 6 8 No 7 4 Yes 2,9 8 9 Yes 3,8 9 7 No 10 4 Yes 2,927三、橢圓曲線密碼根據表可知全部解點集為：(2，4),(2，7),(3，5),

13、(3，6),(5，2),(5，9),(7，2),(7，9),(8，3),(8，8),(10，2),(10，9)。再加上無窮遠點O，共13的點構成一個加法交換群。由于群的元素個數為13，而13為素數，所以此群是循環群，而且任何一個非O元素都是生成元。28三、橢圓曲線密碼由于是加法群，n個元素G相加，G+G+.+G nG 。我們取G （2，7）為生成元，具體計算加法表如下： 2G=（2，7）+（2，7）=（5，2）因為=（322+1）（27）-1 mod 11 =23-1 mod 11=24 mod 11=8 。于是，x3 =82-22 mod 11=5 ，y3 =8（2-5）-7 mod 11=

14、2。29三、橢圓曲線密碼 G （2，7）， 2G （5，2）， 3G （8，3）， 4G （10，2）， 5G （3，6）， 6G （7，9）， 7G （7，2）， 8G （3，5）， 9G （10，9），10G （8，8）， 11G （5，9）， 12G （2，4）， 13G O（ ， ）。30三、橢圓曲線密碼除了GF(p)上的橢圓曲線，外還有定義在GF(2m)上的橢圓曲線。這兩種橢圓曲線都可以構成安全的橢圓曲線密碼。在上例中，由于p較小，使GF(p)也較小，故可以利用窮舉的方法求出所有解點。但是，對于一般情況要確切計算橢圓曲線解點數N的準確值比較困難。N滿足以下不等式 P+1-2P 1/2

15、NP+1+2P 1/2 。31三、橢圓曲線密碼5、橢圓曲線密碼 ELGamal密碼建立在有限域GF（p）的乘法群的離散對數問題的困難性之上。而橢圓曲線密碼建立在橢圓曲線群的離散對數問題的困難性之上。兩者的主要區別是其離散對數問題所依賴的群不同。因此兩者有許多相似之處。32三、橢圓曲線密碼5、橢圓曲線密碼 橢圓曲線群上的離散對數問題 在上例中橢圓曲線上的解點所構成的交換群恰好是循環群，但是一般并不一定。于是我們希望從中找出一個循環子群E1 。可以證明當循環子群E1 的階n是足夠大的素數時，這個循環子群中的離散對數問題是困難的。33三、橢圓曲線密碼5、橢圓曲線密碼 橢圓曲線群上的離散對數問題 設P

16、和Q是橢圓曲線上的兩個解點，t 為一正整數，且1tn。對于給定的P和t，計算tPQ是容易的。但若已知P和Q點，要計算出t則是極困難的。這便是橢圓曲線群上的離散對數問題，簡記為ECDLP(Elliptic Curve Discrete Logarithm Problem)。34三、橢圓曲線密碼5、橢圓曲線密碼 橢圓曲線群上的離散對數問題 除了幾類特殊的橢圓曲線外，對于一般ECDLP目前尚沒有找到有效的求解方法。于是可以在這個循環子群E1中建立任何基于離散對數困難性的密碼，并稱這個密碼為橢圓曲線密碼。35三、橢圓曲線密碼橢圓曲線密碼 T=p為大于3素數，p確定了有限域GF（p）；元素a,bGF(p

17、),a和b確定了橢圓曲線；G為循環子群E1的生成元點，n為素數且為生成元G的階，G和n確定了循環子群E1；h=|E|/n，并稱為余因子，h將交換群E和循環子群聯系起來。36三、橢圓曲線密碼橢圓曲線密碼 密鑰：用戶的私鑰定義為一個隨機數d， d1,2,n-1。用戶的公開鑰定義為Q點， Q=dG 。37三、橢圓曲線密碼橢圓曲線密碼設d為用戶私鑰，Q為公鑰，將Q存入PKDB。設要加密的明文數據為M，將M劃分為一些較小的數據塊，M=m1 ，m2 ， ，mt，其中0mi n 。38三、橢圓曲線密碼橢圓曲線密碼 加密過程：A把M加密發給BA查PKDB，查到B的公開密鑰QB 。A選擇一個隨機數k，且k1,2

18、,n-1。A計算點X1（x1 ，y1）=kG 。A計算點X2（x2 ，y2）=kQB ，如果分量x2=O，則轉。A計算密文 C = mi x2 mod n 。A發送加密數據（X1，C）給B。39三、橢圓曲線密碼橢圓曲線密碼解密過程：用戶B用自己的私鑰dB 求出點X2 ： dBX1 = dB（kG） = k(dB G) = k QB = X2（x2 ，y2）對C解密，得到明文mi =C x2 1 mod n 。40三、橢圓曲線密碼橢圓曲線密碼橢圓曲線密碼的實現由于橢圓曲線密碼所依據的數學基礎比較復雜，從而使得其具體實現也比較困難。難點：安全橢圓曲線的產生；倍點運算。41四、公鑰密碼的理論模型1、單向函數 設函數 y=f(x)，如果滿足以下兩個條件，則稱為單向函數：如果對于給定的 x，要計算出 y很容易；而對于給定的 y，要計算出 x