第六章

非對(duì)稱密碼體制6.1概述6.1.1對(duì)稱密碼體制的缺陷密鑰的平安傳遞比較困難n個(gè)用戶多點(diǎn)通信所需密鑰數(shù)為n(n-1)/2個(gè)難以提供對(duì)抗抵賴功能的支持6.1.2公鑰〔非對(duì)稱〕密碼體制的根本思想WhitfieldDiffie和MartinHellman在1976年n首先提出：用公開的密鑰〔公鑰〕加密，用與之對(duì)應(yīng)的不公開的密鑰〔私鑰〕解密。公鑰密碼體制提出的標(biāo)志性文獻(xiàn)──密碼學(xué)的新方向：W.Diffieand,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654例：盧毅要傳送密信給胡旦，用胡旦的公鑰對(duì)明文進(jìn)行加密，然后通過公共信道將密文傳送給胡旦，胡旦用的與自己的公鑰對(duì)應(yīng)的私鑰〔只有胡旦自己知道〕解密得到明文。俞敏祺企圖知道密信內(nèi)容，截獲到密文，雖然他也知道加密所用的公鑰，但他無法通過公鑰倒推出相應(yīng)的私鑰，當(dāng)然就不可能解密出明文。6.1.3單向陷門函數(shù)公鑰密碼體制必須設(shè)計(jì)一個(gè)滿足以下條件的函數(shù)f：正向易算性──由消息x和密鑰pk容易計(jì)算y=fpk(x)反向不可算性──在不知道密鑰sk的情況下，由任意的y倒過來計(jì)算x=f-1sk(y)都是不可行的陷門依賴性──如果給定另一密鑰sk，那么f-1(y)是可以計(jì)算的，sk與pk配對(duì)，相當(dāng)于陷門。滿足1、2的函數(shù)稱為單向函數(shù)滿足1、2、3的函數(shù)被稱為帶陷門的單向函數(shù)6.1.4公鑰密碼體制的特點(diǎn)無需密鑰的平安傳遞n個(gè)用戶僅需n個(gè)“公鑰-私鑰〞對(duì)支持?jǐn)?shù)字簽名機(jī)制平安性基于帶陷門的單向函數(shù)加密、解密速度比DES、AES等分組密碼體制慢可用于對(duì)稱密鑰的交換6.2數(shù)論背景——?dú)W拉函數(shù)與歐拉定理歐拉數(shù)設(shè)正整數(shù)n，那么歐拉數(shù)φ(n)定義為小于n且與n互素的正整數(shù)的個(gè)數(shù)〔特殊地，φ(1)=1〕。例如：φ(6)=2(小于6且與6互素的是1和5);φ(7)=6(1,2,3,4,5,6);φ(11)=10(1~10)素?cái)?shù)的歐拉數(shù)對(duì)于素?cái)?shù)p，其歐拉數(shù)φ(p)=p-1(1~p-1)歐拉數(shù)的初等性質(zhì)當(dāng)p、q都是素?cái)?shù)時(shí)，φ(pq)=φ(p)φ(q)=(p-1)(q-1)例：φ(15)=φ(3)φ(5)=2*4=8(1,2,4,7,8,11,13,14)當(dāng)e與m互素，那么存在正整數(shù)d，使得ed=1(modm)稱d是e關(guān)于模m的乘法逆元〔簡稱“模乘逆元〞或“模逆元〞〕，記作e-1例如：設(shè)m=13，那么5*8=40=3*13+1=1(mod13)故5-1=8歐拉定理假設(shè)m、n互素，那么mφ(n)=1(modn)例如：設(shè)m=13，n=7，那么136=4826809=689544*7+1=1(mod7)費(fèi)馬小定理──歐拉定理的推論設(shè)p與m互素，且p是素?cái)?shù)，那么mp-1=1(modp)〔因?yàn)棣?p)=p-1〕根底定理──RSA的理論根底設(shè)n是兩個(gè)不同的素?cái)?shù)p、q之積，x是小于n的非負(fù)整數(shù)，k是非負(fù)整數(shù)，那么有：xkφ(n)+1=x(modn)證明：假設(shè)x不是素?cái)?shù)p的倍數(shù)，那么p與x互素，由費(fèi)馬小定理可得：xp-1=1(modp)，于是由前述各式可得：xkφ(n)=xkφ(pq)=xkφ(p)φ(q)=xk(p-1)(q-1)=(xp-1)k(q-1)=1(modp)，故xkφ(n)+1=x(modp)假設(shè)x是p的倍數(shù)，那么x=0(modp)，于是也有：xkφ(n)+1=0=x(modp)故存在非負(fù)整數(shù)i，使得xkφ(n)+1=ip+x(modp)，同理存在非負(fù)整數(shù)j，使得xkφ(n)+1=jq+x(modq)，從而可得ip=jq又由于p、q互素，故qi，設(shè)整商為t，即i=tq，于是：xkφ(n)+1=ip+x=tqp+x=tn+x=x(modn)即最后證得：xkφ(n)+1=x(modn)6.3RSA算法6.3.1概述創(chuàng)造人RSA(RonRivest,AdiShamir和

LeonardAdleman)1977年在麻省理工學(xué)院開發(fā)1978年發(fā)表是最典型的公鑰密碼體制算法基于單向陷門函數(shù)的原理以模冪運(yùn)算為根本運(yùn)算平安性基于大數(shù)因子分解的困難性〔將一個(gè)充分大的正整數(shù)分解成兩個(gè)素?cái)?shù)之積幾乎是不可能的〕數(shù)學(xué)根底是著名的歐拉(Euler)數(shù)論6.3.2RSA密碼體制的創(chuàng)立選擇兩個(gè)充分大的不同的素?cái)?shù)p和q計(jì)算積n=pq及其歐拉數(shù)φ(n)=(p-1)(q-1)選擇一個(gè)介于1到φ(n)之間且與φ(n)互素的正整數(shù)e即1<e<φ(n)且GCD(e,φ(n))=1求出d=e-1(modφ(n))即ed=1(modφ(n))對(duì)明文空間0～n-1中的數(shù)x，例：P115【例6-2】以<e,n>為公鑰加密：y=E(x)=xe(modn)以<d,n>為私鑰解密：x=D(y)=yd(modn)解密復(fù)原性的證明：由于ed=1(modφ(n))，故存在非負(fù)整數(shù)k，使得：ed=kφ(n)+1，于是由根底定理可得：D(E(x))=(xe)d=xed=xkφ(n)+1=x(modn)注1：p,q從理論上講也是私鑰的組成局部，但因在解密過程中不用，故在確定e,d之后應(yīng)予以銷毀注2:加密前明文M需表示為假設(shè)干0～n-1的代碼Mi實(shí)例：對(duì)英文字母從1~26編碼，空格為0，對(duì)明文雙字母編碼，如“itsallgreektome〞編碼為：0920、1900、0112、1200、0718、0505、1100、2021、0013、0500設(shè)p=47、q=59，那么n=2773，φ(2773)=46*58=2668因17*157=2669=1(mod2668)，故取公鑰為<17,2773>，私鑰為<157,2773>對(duì)明文組M=0920加密，C=92021=0948(mod2773)，190017=2342(mod2773)，其余各組的密文為：1084、1444、2663、2390、0778、0774、0219、1655對(duì)密文組C=948解密，M=948157=920(mod2773)詳見：RSA加密解密實(shí)例.doc6.3.4計(jì)算方法及其程序?qū)崿F(xiàn)如何計(jì)算模逆元要在e、m的情況下，求d，使得e*d=1(modm)也即找整數(shù)k，使得e*d+mk=1這相當(dāng)于求解d、k都是未知數(shù)的二元一次不定方程e*d+mk=1的最小整數(shù)解擴(kuò)展Euclid算法輸入：正整數(shù)a、b輸出：GCD(a,b)及滿足ax+by=GCD(a,b)的整數(shù)x、y例如：設(shè)a=21、b=15，那么GCD(a,b)=3，x=-2、y=3算法步驟描述：置x1=1，x2=0，y1=0，y2=1計(jì)算q=a/b，r=a%b假設(shè)r=0，那么GCD(a,b)=b，x=x2，y=y2，算法結(jié)束；否那么做下步依次令a=b，b=r，t=x2，x2=x1-qx2，x1=t，t=y2，y2=y1-qy2，y1=t，然后轉(zhuǎn)2)附：擴(kuò)展Euclid算法.CPP乘法逆元的計(jì)算輸入：正整數(shù)e、m輸出：GCD(e,m)及滿足ed=GCD(e,m)(modm)的整數(shù)d當(dāng)GCD(e,m)=1〔即e、m互素〕，那么d=e-1(modm)例如：設(shè)e=7、m=17，那么GCD(7,17)=1，d=5=7-1；因?yàn)?*5=35=17*2+1=1(mod17)算法：在擴(kuò)展Euclid算法中令a=e、b=m，那么ex+my=GCD(e,m)(modm)，即ex=GCD(e,m)(modm)；假設(shè)結(jié)果GCD(e,m)=1，那么d=e-1=x；否那么e沒有逆元附：求乘法逆元.CPP解密指數(shù)──最小正逆元的計(jì)算附：求最小正逆元.CPP設(shè)d是e的逆元，即ed=1(modm)，由于e(d+km)=ed+ekm=ed=1(modm)，故d+km也是e的逆元，可見乘法逆元不惟一。在上述乘法逆元算法中得到的逆元最接近零，但有可能為負(fù)。例如：設(shè)e=3、m=40，那么GCD(3,40)=1，但d=－13，顯然不能用作RSA算法的解密指數(shù)。因此必須將這種負(fù)逆元調(diào)整為正逆元，才能得到解密指數(shù)。改進(jìn)后的算法如下：輸入：正整數(shù)e、m輸出：GCD(e,m)及滿足ed=GCD(a,m)(modm)的最小正整數(shù)d;當(dāng)CD(e,m)=1，那么d=e-1(modm)就是所求解密指數(shù)模冪的快速算法輸入：整數(shù)n、正整數(shù)m、e輸出：C=ne(modm)算法：將e表示為二進(jìn)制形式(bkbk-1···b1b0)C=1對(duì)于從k到0的i做C=C*C(modm)，如果bi=1那么再做C=C*n(modm)返回C附：快速求模冪.CPP素性檢測算法之一──Miller-Rabin算法對(duì)于充分大的正奇數(shù)n，設(shè)n-1=2km〔其中k是非負(fù)整數(shù)、m是正奇數(shù)〕，假設(shè)bm=1(modn)或b2jm=–1〔其中0≤j≤i-1〕，那么稱n通過以b為基的Miller-Rabin素性檢測也即n以(1-1/4b)的概率是素?cái)?shù)輸入：大奇數(shù)n、檢測次數(shù)t輸出：確定n是合數(shù)或者以(1-1/4t)的概率是素?cái)?shù)。如：t=5，那么判定n是素?cái)?shù)的正確性約為：(1-1/45)=0.9990234375算法：將n-1表示為二進(jìn)制形式(bkbk-1···b1b0)隨機(jī)選取從1到n-1的整數(shù)ax=1對(duì)于從k到0的i依次做:x0=x、x=x2(modn)，如果x=1&x0≠1&x0≠n-1那么返回“是〞，算法結(jié)束；如果bi=1那么再做x=x*a(modn)如果x≠1那么返回“是〞，算法結(jié)束轉(zhuǎn)2)直至算法結(jié)束或完成t回測試，假設(shè)完成t回測試那么返回“不是〞，即n是偽素?cái)?shù)附：用M-R檢測素?cái)?shù).CPP求65535以下的素?cái)?shù).CPP6.3.5梅森素?cái)?shù)6.3.6RSA方案的設(shè)計(jì)流程用素性檢測法選兩個(gè)充分大的素?cái)?shù)p、q計(jì)算n=pq及φ(n)=(p-1)(q-1)選擇一個(gè)介于1到φ(n)之間的正整數(shù)e用擴(kuò)展Euclid算法計(jì)算GCD(e,φ(n))，假設(shè)為1那么轉(zhuǎn)下步，否那么轉(zhuǎn)3)選出e的最小正逆元d=e-1(modφ(n))銷毀p、q，選e、d中的較小的一個(gè)與n組成公鑰并予以公布，另一個(gè)作為私鑰予以嚴(yán)格保密設(shè)計(jì)加密方案：以某種規(guī)那么將明文消息表示為假設(shè)干個(gè)小于n的非負(fù)整數(shù)6.3.7RSA算法的平安性對(duì)RSA的攻擊等效于對(duì)模數(shù)n的因數(shù)分解，屬于NP-類計(jì)算問題〔不確定性多項(xiàng)式時(shí)間可解〕附：將輸入的充分大正整數(shù)分解為兩個(gè)素?cái)?shù)之積〔可能的話〕的算法──整數(shù)分解為素?cái)?shù)之積.CPPp、q應(yīng)盡量取符合以下要求的強(qiáng)素?cái)?shù)：①p-1有大的素因子r②p+1有大的素因子③r-1有大的素因子知道φ(n)那么可求得p、q，故應(yīng)予以保密或銷毀泄漏解密指數(shù)d將有利于對(duì)n的分解，因此不能光換d而必須選擇新的p、q不同用戶不可共享n和p、q在一對(duì)加密、解密指數(shù)中，盡可能讓e<d目前p、q在1024位(1.8×10308)～2048位(3.2×10616)之內(nèi)是平安的平安的RSA方案速度較DES、AES慢，一般用于對(duì)稱加密體制中的密鑰傳遞和交換6.3.9平安RSA算法的實(shí)例n=〔1024位二進(jìn)制、256位十六進(jìn)制〕328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2021433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2BC511951公鑰e=10001H6.3.8RSA算法的演示RSA-TOOL私鑰d=E760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B1965設(shè)明文編碼M=

那么加密后的密文C=Me(modn)=17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cC4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898解密后復(fù)原成明文M=Cd(modn)=附：關(guān)于公鑰密碼體制與RSA的討論6.4ElGamal〔TaherElGamal提出〕密碼體制6.4.1數(shù)論背景離散對(duì)數(shù)──在模意義下的對(duì)數(shù)設(shè)正整數(shù)α、β、a和p，假設(shè)αa=β(modp)，那么稱a是β的以α為底在模p意義下的離散對(duì)數(shù)，記作a=logαβ(modp)。例如：因54=625=9(mod11)，故log59(mod11)=4本原元和循環(huán)群定義：設(shè)p是素?cái)?shù)，Zp={0,1,2,3,…,p-1}，Zp*={1,2,3,…,p-1}，假設(shè)對(duì)任一β∈Zp*，總存在正整數(shù)a，使得αa=β(modp)，也即：Zp中任意非0元素總存在離散對(duì)數(shù)logαβ(modp)，那么α稱為Zp*〔或p〕的本原元〔或生成元、基元、原根〕，也即Zp對(duì)模p乘構(gòu)成循環(huán)群可以證明：對(duì)于素?cái)?shù)p，Zp*共有φ(p-1)個(gè)本原元例如：Z19={0,1,2,3,…,18}，φ(18)=

6(1,5,7,11,13,17),故Z19*={1,2,3,…,18}共有6個(gè)本原元：2,3,10,13,14,15；驗(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附：求本原元.CPP6.4.2密碼體系設(shè)計(jì)步驟選擇適宜的大素?cái)?shù)p，建立循環(huán)群Zp={0,1,2,3,…,p-1}，使得在Zp中求離散對(duì)數(shù)是困難的選擇Zp*的本原元α針對(duì)某用戶任選a∈Zp，計(jì)算β=αa(modp)，以形成公鑰(p,α,β)和私鑰a加密：對(duì)于明文x∈Zp，隨機(jī)選取正整數(shù)r∈Zp*，計(jì)算y1=αr(modp)和y2=xβr(modp)，得到密文對(duì)(y1,y2)解密：x=y2(y1a)-1(modp)6.4.3解密復(fù)原性的證明注意：(

y1a)-1(modp)=(

y1a(modp))-1(modp)因?yàn)椋簓1=αr(modp)、

y2=xβr(modp)、β=αa(modp)所以：y2(y1a)-1(modp)

=xβr((αr)

a)-1(modp)=x(αa)r((αr

)

a)-1(modp)

=xαar(αra)-1(modp)

=x(modp)6.4.4平安性及算法說明由α、a求β=αa(modp)是容易的當(dāng)p充分大，由α、β求離散對(duì)數(shù)a=logαβ(modp)是極其困難的為抗擊的攻擊，p至少是150位十進(jìn)制數(shù)，并且p-1有大的素因子p、α可為所有用戶共享a、β屬于某一個(gè)接收方，其中β是公鑰，a是私鑰r屬于每次加密過程，由發(fā)送方選取，需保密，但在解密時(shí)不用，故可在加密后銷毀6.5Diffie-Hellman密鑰交換算法概述簡稱D-H密鑰交換算法用于通信雙方交換密鑰所要交換的密鑰用于加密明文，一般是對(duì)稱密鑰平安性依賴于計(jì)算離散對(duì)數(shù)的困難性算法步驟A、B方預(yù)先確定兩個(gè)公開的整數(shù)：q和a