非對(duì)稱密碼體制課件VIP

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

2、解密。對(duì)應(yīng)的不公開的密鑰（私鑰）解密。 公鑰密碼體制提出的標(biāo)志性文獻(xiàn)公鑰密碼體制提出的標(biāo)志性文獻(xiàn)密碼學(xué)密碼學(xué)的新方向：的新方向： 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非對(duì)稱密碼體制例：盧毅要傳送密信給胡旦，用胡旦的公鑰對(duì)明文例：盧毅要傳送密信給胡旦，用胡旦的公鑰對(duì)明文進(jìn)行加密，然后通過公共信道將密文傳送給胡旦，進(jìn)行加密，然后通過公共信道將密文傳送給胡旦，胡旦用的與自己的

3、公鑰對(duì)應(yīng)的私鑰（只有胡旦自胡旦用的與自己的公鑰對(duì)應(yīng)的私鑰（只有胡旦自己知道）解密得到明文。俞敏祺企圖知道密信內(nèi)己知道）解密得到明文。俞敏祺企圖知道密信內(nèi)容，截獲到密文，雖然他也知道加密所用的公鑰，容，截獲到密文，雖然他也知道加密所用的公鑰，但他無法通過公鑰倒推出相應(yīng)的私鑰，當(dāng)然就不但他無法通過公鑰倒推出相應(yīng)的私鑰，當(dāng)然就不可能解密出明文?？赡芙饷艹雒魑?。非對(duì)稱密碼體制6.1.2 對(duì)公鑰密碼體制的要求對(duì)公鑰密碼體制的要求（1）參與方）參與方B容易通過計(jì)算產(chǎn)生一對(duì)密鑰（公開密容易通過計(jì)算產(chǎn)生一對(duì)密鑰（公開密鑰鑰KUb和私有密鑰和私有密鑰KRb）。）。（2）在知道公鑰和待加密報(bào)文）在知道公鑰和待加密

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

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

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

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

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

9、mod 7)非對(duì)稱密碼體制費(fèi)馬小定理費(fèi)馬小定理歐拉定理的推論歐拉定理的推論 設(shè)設(shè)p與與m互素，且互素，且p是素?cái)?shù)，則是素?cái)?shù)，則 m p-1=1 (mod p)（因?yàn)椋ㄒ驗(yàn)?p)=p-1）基礎(chǔ)定理基礎(chǔ)定理RSA的理論基礎(chǔ)的理論基礎(chǔ) 設(shè)設(shè)n是兩個(gè)不同的素?cái)?shù)是兩個(gè)不同的素?cái)?shù)p、q之積，之積，x是小于是小于n的非負(fù)整數(shù)，的非負(fù)整數(shù)，k是非負(fù)整數(shù)，是非負(fù)整數(shù)，則有：則有： x k(n) +1=x (mod n)非對(duì)稱密碼體制證明：若證明：若x不是素?cái)?shù)不是素?cái)?shù)p的倍數(shù)，則的倍數(shù)，則p與與x互素，由費(fèi)馬小互素，由費(fèi)馬小定理可得：定理可得： 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的倍數(shù)，則的倍數(shù)，則 x=0 (mod p) ，于是也有：于是也有： x k(n) +1=0=x (mod p)故存在非負(fù)整數(shù)故存在非負(fù)整數(shù)i，使得，使得x k(n) + 1=ip+x (mod p)，同理存在非負(fù)整數(shù)同理存在非負(fù)整數(shù)j ，使得，使得x k(n) +1=jq+x (mod q)，從而可得從而可得ip=jq又由于又由于p、q互素，故互素，故q i，設(shè)整商為設(shè)整商為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)非對(duì)稱密碼體制6.3 RSA算法算法6.3.1 概述概述發(fā)明人發(fā)明人RSA(Ron Rivest, AdiShamir 和和 Leonard Adleman) 1977年在年在麻省理工學(xué)院開發(fā)麻省理工學(xué)院開發(fā)1978年發(fā)表年發(fā)表是最典型的公鑰密碼體制是最典型的公鑰密碼體制算法基于單向陷門函數(shù)的原理算法基于單向陷門函數(shù)的原理以模冪運(yùn)算為基本運(yùn)算以模冪運(yùn)算為基本運(yùn)算安全性基于大數(shù)因子分解的困難性安全性基于大數(shù)因子分解的困難性（將一個(gè)充分大的正整數(shù)分

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31、，公鑰密碼體制有何優(yōu)點(diǎn)？請(qǐng)用生活中的例子簡述用于機(jī)密性的公鑰密碼請(qǐng)用生活中的例子簡述用于機(jī)密性的公鑰密碼體制的加密解密過程體制的加密解密過程最典型的公鑰密碼體制是哪一個(gè)？最典型的公鑰密碼體制是哪一個(gè)？RSA密碼體制的數(shù)學(xué)基礎(chǔ)是什么？密碼體制的數(shù)學(xué)基礎(chǔ)是什么？RSA密碼體制的安全性依賴于什么？密碼體制的安全性依賴于什么？請(qǐng)簡述一個(gè)具體的請(qǐng)簡述一個(gè)具體的RSA方案的設(shè)計(jì)過程方案的設(shè)計(jì)過程RSA密碼體制的主要缺點(diǎn)是什么？密碼體制的主要缺點(diǎn)是什么？p、q至少取十進(jìn)制幾位才能使至少取十進(jìn)制幾位才能使RSA方案具有安方案具有安全意義？全意義？什么是單向函數(shù)？什么是單向函數(shù)？能否用私鑰加密而用公鑰解密？有何

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

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

34、,故故Z19*=1,2,3,18共有共有6個(gè)本個(gè)本原元：原元：2,3,10,13,14,15； 驗(yàn)證驗(yàn)證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非對(duì)稱密碼體制6.4.2 密碼體系設(shè)計(jì)步驟密碼體系設(shè)計(jì)步驟7 選擇合適的大素?cái)?shù)選擇合適的大素?cái)?shù)p，建立循環(huán)群建立循環(huán)群Zp =0,1,2,3,p-1，使得

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

36、1 (mod p)因?yàn)椋阂驗(yàn)椋?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)非對(duì)稱密碼體制6.4.4 安全性及算法說明安全性及算法說明7 由由、 a 求求=a (mod p)是容易的是容易的7 當(dāng)當(dāng)p充分大，由充分大，由、求離散對(duì)數(shù)求離散對(duì)數(shù)a= log (mod p)是極其困難的是極其困難的7 為抗擊已知的攻擊，為抗擊已知的攻擊，p至少是至少是150位十進(jìn)制位十進(jìn)制數(shù)，并且數(shù)，并且p-1有大的素因子有大的素因子7 p、可為所有用戶共享可為所有用戶共享7 a 、屬于某一個(gè)接收方屬于某一個(gè)接收方，其中其中是公鑰，是公鑰， a 是私鑰是私鑰7 r屬