1、非對稱密碼體制第六章第六章 非對稱密碼體制非對稱密碼體制信息安全技術信息安全技術 非對稱密碼體制6.1 概述概述6.1.1 對稱密碼體制的缺陷對稱密碼體制的缺陷密鑰的安全傳遞比較困難密鑰的安全傳遞比較困難n個用戶多點通信所需密鑰數為個用戶多點通信所需密鑰數為n(n-1)/2個個難以提供對抗抵賴功能的支持難以提供對抗抵賴功能的支持6.1.2 公鑰（非對稱）密碼體制的基本思想公鑰（非對稱）密碼體制的基本思想 Whitfield Diffie和和Martin Hellman在在1976年年n首先提出：用公開的密鑰（公鑰）加密，用與之首先提出：用公開的密鑰（公鑰）加密，用與之對應的不公開的密鑰（私鑰）

2、解密。對應的不公開的密鑰（私鑰）解密。 公鑰密碼體制提出的標志性文獻公鑰密碼體制提出的標志性文獻密碼學密碼學的新方向：的新方向： 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、公鑰對應的私鑰（只有胡旦自胡旦用的與自己的公鑰對應的私鑰（只有胡旦自己知道）解密得到明文。俞敏祺企圖知道密信內己知道）解密得到明文。俞敏祺企圖知道密信內容，截獲到密文，雖然他也知道加密所用的公鑰，容，截獲到密文，雖然他也知道加密所用的公鑰，但他無法通過公鑰倒推出相應的私鑰，當然就不但他無法通過公鑰倒推出相應的私鑰，當然就不可能解密出明文。可能解密出明文。非對稱密碼體制6.1.2 對公鑰密碼體制的要求對公鑰密碼體制的要求（1）參與方）參與方B容易通過計算產生一對密鑰（公開密容易通過計算產生一對密鑰（公開密鑰鑰KUb和私有密鑰和私有密鑰KRb）。）。（2）在知道公鑰和待加密報文）在知道公鑰和待加密

4、報文M的情況下，對于發的情況下，對于發送方送方A，很容易通過計算產生對應的密文：，很容易通過計算產生對應的密文：C=EKUb(M)（3）接收方）接收方B使用私鑰容易通過計算解密所收到的使用私鑰容易通過計算解密所收到的密文密文C以便恢復原來的明文：以便恢復原來的明文： M=DKRb(C)=DKRb (EKUb(M)（4）攻擊者即使知道公鑰）攻擊者即使知道公鑰KUb，要確定其對應的私，要確定其對應的私鑰鑰KRb在計算上是不可行的。在計算上是不可行的。（5）攻擊者即使知道公鑰）攻擊者即使知道公鑰KUb和密文和密文C，要想恢復，要想恢復原來的明文原來的明文M在計算上也是不可行的。在計算上也是不可行的。

5、（6）加密和解密函數可以以兩個次序中的任何一個）加密和解密函數可以以兩個次序中的任何一個來使用來使用:M=DKRb(EKUb(M) （機密性）（機密性） 或或M=EKUb(DKRb(M) （數字簽名）（數字簽名）非對稱密碼體制6.1.3 單向陷門函數單向陷門函數公鑰密碼體制必須設計一個滿足下列條件的函數公鑰密碼體制必須設計一個滿足下列條件的函數f：正向易算性正向易算性由消息由消息x和密鑰和密鑰pk 容易計算容易計算y=fpk(x)反向不可算性反向不可算性在不知道密鑰在不知道密鑰sk的情況下，由的情況下，由任意的任意的y倒過來計算倒過來計算x =f-1sk(y)都是不可行的都是不可行的陷門依賴性

6、陷門依賴性如果給定另一密鑰如果給定另一密鑰sk，則，則f-1(y)是是可以計算的，可以計算的， sk 與與pk配對，相當于陷門。配對，相當于陷門。 滿足滿足1、2的函數稱為單向函數的函數稱為單向函數 滿足滿足1、2、3的函數被稱為帶陷門的單向函數的函數被稱為帶陷門的單向函數非對稱密碼體制非對稱密碼體制 6.1.4 公鑰密碼體制的特點公鑰密碼體制的特點無需密鑰的安全傳遞無需密鑰的安全傳遞n個用戶僅需個用戶僅需n個個“公鑰公鑰-私鑰私鑰”對對支持數字簽名機制支持數字簽名機制安全性基于帶陷門的單向函數安全性基于帶陷門的單向函數加密、解密速度比加密、解密速度比DES、AES等分組密碼體制慢等分組密碼體

7、制慢可用于對稱密鑰的交換可用于對稱密鑰的交換非對稱密碼體制6.2 數論背景數論背景歐拉函數與歐拉定理歐拉函數與歐拉定理歐拉數歐拉數設正整數設正整數n，則歐拉數則歐拉數(n)定義為小于定義為小于n且與且與n互素的正整數的個數（特殊地，互素的正整數的個數（特殊地，(1)=1 ）。）。例如：例如：(6)=2(小于小于6且與且與6互素的是互素的是1和和5); (7)=6(1,2,3,4,5,6); (11)=10(110)素數的歐拉數素數的歐拉數對于素數對于素數p ，其歐拉數，其歐拉數(p)=p-1(1p-1)歐拉數的初等性質歐拉數的初等性質 當當p、q都是素數時，都是素數時， (pq)=(p)(q)

8、=(p-1) (q-1)例：例： (15)=(3)(5)=2*4=8(1,2,4,7,8,11,13,14)非對稱密碼體制當當e與與m互素，則存在正整數互素，則存在正整數d，使得使得 ed=1 (mod m) 稱稱d是是e關于模關于模m的乘法逆元（簡稱的乘法逆元（簡稱“模模乘逆元乘逆元”或或“模逆元模逆元”），記作），記作e-1 例如：設例如：設m=13， 則則5*8=40=3*13+1=1 (mod 13) 故故 5-1=8歐拉定理歐拉定理 假設假設m、n互素，則互素，則m(n)=1 (mod n) 例如：設例如：設m=13，n=7， 則則136=4826809=689544*7+1=1 (

9、mod 7)非對稱密碼體制費馬小定理費馬小定理歐拉定理的推論歐拉定理的推論 設設p與與m互素，且互素，且p是素數，則是素數，則 m p-1=1 (mod p)（因為（因為(p)=p-1）基礎定理基礎定理RSA的理論基礎的理論基礎 設設n是兩個不同的素數是兩個不同的素數p、q之積，之積，x是小于是小于n的非負整數，的非負整數，k是非負整數，是非負整數，則有：則有： x k(n) +1=x (mod n)非對稱密碼體制證明：若證明：若x不是素數不是素數p的倍數，則的倍數，則p與與x互素，由費馬小互素，由費馬小定理可得：定理可得： x p-1=1 (mod p) ，于是由前述各式可得：于是由前述各式

10、可得：x k(n) = x k(pq) = x k(p) (q) = x k(p-1)(q-1)=( xp-1) k(q-1) =1 (mod p) ，故故x k(n) +1=x (mod p)若若x是是p的倍數，則的倍數，則 x=0 (mod p) ，于是也有：于是也有： x k(n) +1=0=x (mod p)故存在非負整數故存在非負整數i，使得，使得x k(n) + 1=ip+x (mod p)，同理存在非負整數同理存在非負整數j ，使得，使得x k(n) +1=jq+x (mod q)，從而可得從而可得ip=jq又由于又由于p、q互素，故互素，故q i，設整商為設整商為t，即即i=t

11、q，于是：于是：x k(n) +1=ip+x= tqp+x=tn+x=x (mod n) 即最后證得：即最后證得：x k(n) +1=x (mod n)非對稱密碼體制6.3 RSA算法算法6.3.1 概述概述發明人發明人RSA(Ron Rivest, AdiShamir 和和 Leonard Adleman) 1977年在年在麻省理工學院開發麻省理工學院開發1978年發表年發表是最典型的公鑰密碼體制是最典型的公鑰密碼體制算法基于單向陷門函數的原理算法基于單向陷門函數的原理以模冪運算為基本運算以模冪運算為基本運算安全性基于大數因子分解的困難性安全性基于大數因子分解的困難性（將一個充分大的正整數分

12、解成兩個（將一個充分大的正整數分解成兩個素數之積幾乎是不可能的）素數之積幾乎是不可能的）1. 數學基礎是著名的歐拉數學基礎是著名的歐拉(Euler)數論數論非對稱密碼體制6.3.2 RSA密碼體制的創建密碼體制的創建選擇兩個充分大的不同的素數選擇兩個充分大的不同的素數p和和q計算積計算積n=pq及其歐拉數及其歐拉數(n)=(p-1)(q-1)選擇一個介于選擇一個介于1到到(n)之間且與之間且與(n)互素的正整互素的正整數數e 即即1e(n)且且GCD(e,(n)=1求出求出d=e-1 (mod (n) ) 即即e d=1 (mod (n) )1)對明文空間對明文空間0n-1中的數中的數x， 例

13、：例：P115【例例6-2】以以為公鑰加密：為公鑰加密： y=E(x)=xe (mod n)以以 為私鑰解密：為私鑰解密：x=D(y)=yd (mod n)非對稱密碼體制解密還原性的證明：解密還原性的證明：由于由于ed=1 (mod (n)，故存在非負整數故存在非負整數k，使得：使得：ed =k(n)+1，于是由基礎定理可得：于是由基礎定理可得：D(E(x)=(xe)d =xed =x k(n) +1 =x (mod n)注注1：p,q從理論上講也是私鑰的組成部從理論上講也是私鑰的組成部分，但因在解密過程中不用，故在確定分，但因在解密過程中不用，故在確定e,d之后應予以銷毀之后應予以銷毀注注2

14、: 加密前明文加密前明文M需表示為若干需表示為若干0n-1的代碼的代碼Mi非對稱密碼體制實例：對英文字母從實例：對英文字母從126編碼，空格為編碼，空格為0，對明文，對明文雙字母編碼，如雙字母編碼，如“its all greek to me ”編碼為：編碼為：0920、1900、0112、1200、0718、 0505、1100、2015、0013、0500設設p=47、q=59，則則n=2773， (2773)=46*58=2668因因17*157=2669=1 (mod 2668)，故取公鑰為故取公鑰為，私鑰為，私鑰為對明文組對明文組M=0920加密，加密，C=92017=24232212

15、2835000000=0948 (mod 2773)，190017=548000000000=2342 (mod 2773)，其余各組的密文為：，其余各組的密文為： 1084、1444、2663、2390、0778、0774、0219、1655非對稱密碼體制對密文組對密文組C=948解密，解密，M=948157 =2285119746776978676533928911676258194658943545577619796826858296111293376812426526485193665281965525847219764437926776848416542537626376718538

16、99712995186966528=920 (mod 2773) 詳見：詳見：RSA加密解密實例加密解密實例.doc非對稱密碼體制6.3.4 計算方法及其程序實現計算方法及其程序實現 如何計算模逆元如何計算模逆元要在已知要在已知e、m的情況下，求的情況下，求d，使得，使得 e*d=1(mod m)也即找整數也即找整數k，使得，使得e*d+mk=1這相當于求解這相當于求解d、k都是未知數的二元一都是未知數的二元一次不定方程次不定方程 e*d+mk=1的最小整數解的最小整數解非對稱密碼體制擴展擴展Euclid算法算法輸入：正整數輸入：正整數a、b輸出：輸出：GCD(a,b)及滿足及滿足ax+by=

17、GCD(a,b)的整的整數數x、y例如：設例如：設a=21、b=15，則則GCD(a,b)=3，x=-2、y=3算法步驟描述：算法步驟描述：置置x1=1，x2=0，y1=0，y2=1計算計算q=a / b，r=a % b若若r=0，則則GCD(a,b)=b，x=x2，y=y2，算法算法結束；否則做下步結束；否則做下步依次令依次令a=b，b=r，t=x2，x2=x1-qx2，x1=t， t=y2，y2=y1-qy2，y1=t，然后轉然后轉2) 附：附：擴展擴展Euclid算法算法.CPP非對稱密碼體制乘法逆元的計算乘法逆元的計算輸入：正整數輸入：正整數e、m輸出：輸出：GCD(e,m)及滿足及滿

18、足ed=GCD(e,m) (mod m)的整數的整數d當當GCD(e,m)=1 （即（即e、m互素）互素），則則d=e-1 (mod m)例如：設例如：設e=7、m=17，則則GCD(7,17)=1，d=5=7-1；因為因為7*5=35=17*2+1=1 (mod 17)算法：在擴展算法：在擴展Euclid算法中令算法中令a=e、b=m，則則ex+my= GCD(e,m) (mod m) ，即即 ex= GCD(e,m) (mod m)；若結果若結果GCD(e,m)=1，則則d=e-1=x；否則否則e沒有沒有逆元逆元附：附：求乘法逆元求乘法逆元.CPP非對稱密碼體制解密指數解密指數最小正逆元的

19、計算最小正逆元的計算附：附：求求最小正逆元最小正逆元.CPP設設d是是e的逆元，即的逆元，即ed=1 (mod m)，由于由于e(d+km)=ed+ekm=ed=1 (mod m)，故故d+km也是也是e的的逆元，可見乘法逆元不惟一。逆元，可見乘法逆元不惟一。在上述乘法逆元算法中得到的逆元最接近零，但有在上述乘法逆元算法中得到的逆元最接近零，但有可能為負?？赡転樨?。例如：設例如：設e=3、m=40，則則GCD(3,40)=1，但但d=13，顯然不能用作顯然不能用作RSA算法的解密指數。因此必須將這算法的解密指數。因此必須將這種負逆元調整為正逆元，才能得到解密指數。種負逆元調整為正逆元，才能得到

20、解密指數。改進后的算法如下：改進后的算法如下：輸入：正整數輸入：正整數e、m輸出：輸出：GCD(e,m)及滿足及滿足ed=GCD(a,m) (mod m)的的最小正整數最小正整數d;當當CD(e,m)=1，則則d=e-1 (mod m)就是就是所求解密指數所求解密指數非對稱密碼體制模冪的快速算法模冪的快速算法輸入：整數輸入：整數n、正整數正整數m、e輸出：輸出：C=ne (mod m) 算法：算法：將將e表示為二進制形式表示為二進制形式(bkbk-1 b1b0)C=1對于從對于從k到到0的的i做做C=C*C (mod m)，如果如果bi=1則再做則再做C=C*n (mod m)返回返回C附：附

21、：快速求模冪快速求模冪.CPP非對稱密碼體制素性檢測算法之一素性檢測算法之一Miller-Rabin算法算法對于充分大的正奇數對于充分大的正奇數n，設設n-1=2km（其中其中k是非負整數、是非負整數、m是正奇數），是正奇數），若若bm=1 (mod n)或或b2jm= 1（其中其中 0j i- 1） ，則稱則稱n通過以通過以b為基的為基的Miller-Rabin素性檢測素性檢測也即也即n以以(1-1/4b)的概率是素數的概率是素數非對稱密碼體制輸入：大奇數輸入：大奇數n、檢測次數檢測次數t輸出：確定輸出：確定n是合數或者以是合數或者以(1-1/4t)的概率是素數。的概率是素數。如：如：t=5

22、，則判定則判定n是素數的正確性約為：是素數的正確性約為：(1-1/45)=0.9990234375 算法：算法：將將n-1表示為二進制形式表示為二進制形式(bkbk-1 b1b0)隨機選取從隨機選取從1到到n-1的整數的整數ax=1對于從對于從k到到0的的i依次做依次做:x0=x、x=x2 (mod n)，如果如果x=1&x01&x0n-1則返回則返回“是是”，算，算法結束；如果法結束；如果bi=1則再做則再做x=x*a (mod n)如果如果x 1則返回則返回“是是” ，算法結束，算法結束1)轉轉2)直至算法結束或完成直至算法結束或完成t回測試，若完成回測試，若完成t回測試則

23、返回回測試則返回“不是不是”，即，即n是偽素數是偽素數附：附：用用M-R檢測素數檢測素數.CPP 求求65535以下的素數以下的素數.CPP非對稱密碼體制形如形如2p1（其中（其中P為素數）的素數稱為梅森素數為素數）的素數稱為梅森素數;它是以它是以17世紀法國數學家、法蘭西科學院奠基人世紀法國數學家、法蘭西科學院奠基人馬林馬林梅森的姓命名的。梅森的姓命名的。最近美國國家海洋和大氣局最近美國國家海洋和大氣局(NOAA)信息技術顧問、信息技術顧問、數學愛好者喬希數學愛好者喬希芬德利使用一臺裝有芬德利使用一臺裝有2.4GHz奔騰奔騰處理器的個人計算機，發現了目前世界上已知的處理器的個人計算機，發現了

24、目前世界上已知的最大素數。最大素數。該梅森素數為該梅森素數為21，它有它有7235733位數，位數，如果用普通字號將這個數字連續寫下來，它的長如果用普通字號將這個數字連續寫下來，它的長度可達度可達30公里！公里！6.3.5 梅森素數梅森素數非對稱密碼體制6.3.6 RSA方案的設計流程方案的設計流程用素性檢測法選兩個充分大的素數用素性檢測法選兩個充分大的素數p、q計算計算n=pq及及(n)=(p-1)(q-1)選擇一個介于選擇一個介于1到到(n)之間的正整數之間的正整數e用擴展用擴展Euclid算法計算算法計算GCD(e,(n)，若為若為1則則轉下步，否則轉轉下步，否則轉3)選出選出e的最小正

25、逆元的最小正逆元d=e-1 (mod (n)銷毀銷毀p、q，選選e、d中的較小的一個與中的較小的一個與n組成公組成公鑰并予以公布，另一個作為私鑰予以嚴格保密鑰并予以公布，另一個作為私鑰予以嚴格保密1)設計加密方案：以某種規則將明文消息表示為設計加密方案：以某種規則將明文消息表示為若干個小于若干個小于n的非負整數的非負整數非對稱密碼體制6.3.7 RSA算法的安全性算法的安全性7 對對RSA的攻擊等效于對模數的攻擊等效于對模數n的因數分解，的因數分解，屬于屬于NP-類計算問題（不確定性多項式時間類計算問題（不確定性多項式時間可解）可解）附：將輸入的充分大正整數分解為兩個素數之附：將輸入的充分大正

26、整數分解為兩個素數之積（可能的話）的算法積（可能的話）的算法整數分解為素數整數分解為素數之積之積.CPP7 p、q應盡量取符合下列要求的強素數：應盡量取符合下列要求的強素數：p-1有大的素因子有大的素因子rp+1有大的素因子有大的素因子r-1有大的素因子有大的素因子7 知道知道(n)則可求得則可求得p、q，故應予以保密或故應予以保密或銷毀銷毀7 泄漏解密指數泄漏解密指數d將有利于對將有利于對n的分解，因此的分解，因此不能光換不能光換d而必須選擇新的而必須選擇新的p、q非對稱密碼體制7 不同用戶不可共享不同用戶不可共享n 和和p、q7 在一對加密、解密指數中，盡可在一對加密、解密指數中，盡可能讓

27、能讓ed7 目前目前p、q在在1024位位(1.810308) 2048位位(3.210616)之內是安全的之內是安全的7 安全的安全的RSA方案速度較方案速度較DES、AES慢，一般用于對稱加密體制中的慢，一般用于對稱加密體制中的密鑰傳遞和交換密鑰傳遞和交換非對稱密碼體制6.3.9 安全安全RSA算法的實例算法的實例n=（1024位二進制、位二進制、256位十六進制）位十六進制）328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55

28、884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2BC511951公鑰公鑰e=10001H6.3.8 RSA算法的演示算法的演示RSA-TOOL非對稱密碼體制私鑰私鑰d=E760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C5D86B36E943080E49

29、19CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B1965設明文編碼設明文編碼M= =11111111111122222222222233333333333 非對稱密碼體制則加密后的密文則加密后的密文C=Me (mod n)=17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288

30、a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cC4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898 解密后還原成明文解密后還原成明文M= =Cd (mod n)=11111111111122222222222233333333333 非對稱密碼體制相對于對稱密碼體制，公鑰密碼體制有何優點？相對于對稱密碼體制

31、，公鑰密碼體制有何優點？請用生活中的例子簡述用于機密性的公鑰密碼請用生活中的例子簡述用于機密性的公鑰密碼體制的加密解密過程體制的加密解密過程最典型的公鑰密碼體制是哪一個？最典型的公鑰密碼體制是哪一個？RSA密碼體制的數學基礎是什么？密碼體制的數學基礎是什么？RSA密碼體制的安全性依賴于什么？密碼體制的安全性依賴于什么？請簡述一個具體的請簡述一個具體的RSA方案的設計過程方案的設計過程RSA密碼體制的主要缺點是什么？密碼體制的主要缺點是什么？p、q至少取十進制幾位才能使至少取十進制幾位才能使RSA方案具有安方案具有安全意義？全意義？什么是單向函數？什么是單向函數？能否用私鑰加密而用公鑰解密？有何

32、用途？能否用私鑰加密而用公鑰解密？有何用途？附：關于公鑰密碼體制與附：關于公鑰密碼體制與RSA的討論的討論非對稱密碼體制6.4 ElGamal（Taher ElGamal提出）密碼體制提出）密碼體制6.4.1 數論背景數論背景1. 離散對數離散對數在模意義下的對數在模意義下的對數設正整數設正整數、a和和p，若若 a= (mod p)，則稱則稱a是是的以的以為底在模為底在模p意義下的離散對數，意義下的離散對數，記作記作a = log (mod p)。例如：例如：因因54=625=9 (mod 11)，故故log59 (mod 11)=4非對稱密碼體制本原元和循環群本原元和循環群定義：設定義：設p

33、是素數，是素數，Zp=0,1,2,3,p-1，Zp* = 1,2,3,p-1，若對任一若對任一 Zp* ，總總存在正整數存在正整數a，使得使得a = (mod p)，也即：，也即： Zp中任意非中任意非0元素總存在離散對數元素總存在離散對數log (mod p)，則，則稱為稱為Zp*（或（或p）的本原元）的本原元（或生成元、基元、原根），也即（或生成元、基元、原根），也即Zp 對模對模p乘構成循環群乘構成循環群可以證明：對于素數可以證明：對于素數p，Zp* 共有共有(p-1)個本個本原元原元非對稱密碼體制例如：例如： Z19=0,1,2,3,18，(18)= 6(1,5,7,11,13,17)

34、,故故Z19*=1,2,3,18共有共有6個本個本原元：原元：2,3,10,13,14,15； 驗證驗證15是是Z19*的本原元：的本原元：151=15， 152=16， 153=12，154=9， 155=2， 156=11，157=13， 158=5， 159=18，1510=4， 1511=3， 1512=7，1513=10， 1514=17， 1515=8，1516=6， 1517=14， 1518=1附：附：求本原元求本原元.CPP非對稱密碼體制6.4.2 密碼體系設計步驟密碼體系設計步驟7 選擇合適的大素數選擇合適的大素數p，建立循環群建立循環群Zp =0,1,2,3,p-1，使得

35、在，使得在Zp中求離散對數是中求離散對數是困難的困難的7 選擇選擇Zp *的本原元的本原元 7 針對某用戶任選針對某用戶任選aZp ，計算計算=a (mod p)，以形成公鑰以形成公鑰(p,)和私鑰和私鑰a7 加密：對于明文加密：對于明文xZp ，隨機選取正整數隨機選取正整數r Zp* ，計算計算 y1 = r (mod p)和和 y2=xr(mod p) ，得到密文對得到密文對(y1, y2)7 解密：解密：x= y2 ( y1a)-1 (mod p) 非對稱密碼體制6.4.3 解密還原性的證明解密還原性的證明注意：注意： ( y1a)-1 (mod p)= ( y1a (mod p) )-

36、1 (mod p)因為：因為： y1=r (mod p)、 y2=xr(mod p)、 =a (mod p)所以：所以：y2 (y1a)-1 (mod p) =xr (r ) a)-1 (mod p)= x(a)r (r ) a)-1 (mod p) = xar (ra)-1 (mod p) =x (mod p)非對稱密碼體制6.4.4 安全性及算法說明安全性及算法說明7 由由、 a 求求=a (mod p)是容易的是容易的7 當當p充分大，由充分大，由、求離散對數求離散對數a= log (mod p)是極其困難的是極其困難的7 為抗擊已知的攻擊，為抗擊已知的攻擊，p至少是至少是150位十進制位十進制數，并且數，并且p-1有大的素因子有大的素因子7 p、可為所有用戶共享可為所有用戶共享7 a 、屬于某一個接收方屬于某一個接收方，其中其中是公鑰，是公鑰， a 是私鑰是私鑰7 r屬