第4章公鑰密碼體制

第4章

公鑰密碼體制主要內(nèi)容

公鑰密碼體制的產(chǎn)生數(shù)論基礎(chǔ)公鑰密碼體制的基本原理

RSA公鑰密碼體制其它公鑰密碼算法傳統(tǒng)密碼體制在應(yīng)用中的缺陷密鑰管理的麻煩密鑰難以傳輸不能提供法律證據(jù)缺乏自動檢測密鑰泄密的能力整除定理：設(shè)整數(shù)a和b，如果存在整數(shù)k，使b=ak，則說b能被a整除，記作：a|b例：3|15，-15|60性質(zhì)：對所有整數(shù)a≠0，a|0、a|a成立對任意整數(shù)b，1|b成立素數(shù)(primenumber)定義：如果整數(shù)p(p>1)只能被1或者它本身整除，而不能被其他整數(shù)整除，則其為素數(shù)，否則為合數(shù)。素數(shù)定理：在各種應(yīng)用中，我們需要大的素數(shù),如100位的素數(shù)素數(shù)是構(gòu)成整數(shù)的因子，每一個整數(shù)都是由一個或幾個素數(shù)的不同次冪相乘得來的。最大公約數(shù)a和b的最大公約數(shù)是能夠同時整除a和b的最大正整數(shù)，記為gcd(a,b)。如果gcd(a,b)=1，則說a和b是互素的。定理：設(shè)a和b是兩個整數(shù)(至少一個非0)，d=gcd(a,b)，則存在整數(shù)x和y，使得ax+by=d特殊地，如果a和b互素，則有整數(shù)x和y，使得ax+by=1同余設(shè)整數(shù)a，b，n(n≠0)，如果a-b是n的整數(shù)倍，則a≡b(modn)，即a同余于b模n。也可理解為a/n的余數(shù)等于b/n的余數(shù)。(modn)運算將所有的整數(shù)(無論小于n還是大于n)，都映射到{0,1,…,n-1}組成的集合。模算術(shù)的性質(zhì)：(amodn)+(bmodn)=(a+b)modn(amodn)-(bmodn)=(a-b)modn(amodn)*(bmodn)=(a*b)modn性質(zhì)有整數(shù)a，b，c，n(n≠0)：如果a≡b(modn)，b≡c(modn)

那么a≡c(modn)如果a≡b(modn)，c≡d(modn)

那么a+c≡b+d，a-c≡b-d，ac≡bd(modn)計算117mod13計算21234mod789除法設(shè)整數(shù)a，b，c，n(n≠0)，且gcd(a,n)=1。如果ab≡ac(modn)，那么b≡c(modn)證明：∵gcd(a,n)=1，∴有x和y，使ax+ny=1兩邊同乘以(b-c):(b-c)(ax+ny)=b-c即:(ab-ac)x+n(b-c)y=b-c……①∵ab≡ac(modn),即ab=ac+k1n,∴ab-ac是n的倍數(shù)同時，n(b-c)y顯然也是n的倍數(shù)所以，:(ab-ac)x+n(b-c)y也是n的倍數(shù)，假設(shè)是k2倍則①式變?yōu)椋篵-c=k2n即b≡c(modn)歐幾里德算法(Euclid)用歐幾里德算法求最大公約數(shù)。求：gcd(482,1180)1180=2*482+216482=2*216+50216=4*50+1650=3*16+216=8*2+0所以gcd(482,1180)=2乘法逆元如果gcd(a,b)=1，那么：存在a-1，使a*a-1

≡1modb存在b-1，使b*b-1

≡1moda這里，把a-1稱為a模b的乘法逆元，b-1稱為b模a的乘法逆元用擴展的歐幾里德算法求乘法逆元gcd(11111,12345)12345=1*11111+123411111=9*1234+51234=246*5+45=1*4+14=4*1+01=5-1*4=5-1*(1234-246*5)=247*5-1*1234=247*(11111-9*1234)-1*1234=247*11111-2224*1234=247*11111-2224*(12345-1*11111)=2471*11111-2224*12345費爾馬小定理(Fermat)如果p是一個素數(shù),a不是p的倍數(shù)，則：ap-1≡1(modp)證明：設(shè)有一整數(shù)空間S={1,2,…,p-1}再設(shè)有一函數(shù)Ψ(x)=ax(modp)x∈S(1)對于任何x∈S，有Ψ(x)∈S(2)對于x和y(x≠y),有Ψ(x)≠Ψ(y)(3)根據(jù)乘法定理和除法定理

(p-1)!ap-1≡(p-1)!modp歐拉函數(shù)Ф(n)：小于n且與n互素的正整數(shù)的個數(shù)顯然，對于素數(shù)p，有Ф(p)=p-1設(shè)有兩個素數(shù)p和q，p≠q，那么對于n=pq，有：Ф(n)=Ф(pq)=Ф(p)*Ф(q)=(p-1)*(q-1)歐拉定理(Euler)對于任意互素的a和n，有aФ(n)

≡1modn證明：對于整數(shù)n，與n互素的數(shù)有Ф(n)個：令這些數(shù)為：R={x1,x2,…,xФ(n)

}用a與R中的每個元素相乘模n，得到集合S：

S={ax1modn,x2modn,…,xФ(n)modn

}其實S就是R：(ax1modn)RS中的元素是唯一的那么：R中各元素相乘就等于S中各元素相乘：∈離散對數(shù)由Euler定理可知，互素的a和n，有aФ(n)

≡1modn也就是說，至少存在一個整數(shù)m，使am

≡1modn成立使得成立am

≡1modn的最小正冪m，稱為a的階、a所屬的模n的指數(shù)，或a所產(chǎn)生的周期長。本原根：如果使得am

≡1modn成立的最小正冪m：

m=Ф(n)，則稱a是n的本原根。指標某素數(shù)p，有本原根a，且：X1=a1modp，X2=a2modp，…，Xp-1=ap-1modp，則：x1≠x2≠…≠xp-1令：S={x1,x2,…,xp-1}，T={1,2,…,p-1}則：S=P對于任意整數(shù)b，有b≡rmodp(0≤r≤p-1)所以，對于b和素數(shù)p的本原根a，有唯一的冪i，使得：b≡aimodp，0≤i≤p-1指數(shù)i稱為a模p的b的指標，記為inda,p(b)指標的性質(zhì)inda,p(1)=?inda,p(a)=?乘法性質(zhì)冪性質(zhì)離散對數(shù)的計算對于方程y=gxmodp給定g,x,p,計算y比較容易。但給定y,g,p,求x非常困難。X=indg,p(y)其難度與RSA中因子分解素數(shù)之積的難度有相同的數(shù)量級。公鑰密碼體制(Publickeysystem)公鑰密碼學(xué)與其他密碼學(xué)完全不同：公鑰算法基于數(shù)學(xué)函數(shù)而不是基于替換和置換使用兩個獨立的密鑰公鑰密碼學(xué)的提出是為了解決兩個問題：密鑰的分配數(shù)字簽名1976年Diffie和Hellman首次公開提出了公鑰密碼學(xué)的概念，被認為是一個驚人的成就。公鑰密碼體制的原理公鑰體制(Publickeysystem)(Diffie和Hellman,1976)

每個用戶都有一對選定的密鑰(公鑰k1；私鑰k2)，公開的密鑰k1可以像電話號碼一樣進行注冊公布。主要特點：加密和解密能力分開多個用戶加密的消息只能由一個用戶解讀，（用于公共網(wǎng)絡(luò)中實現(xiàn)保密通信）只能由一個用戶加密消息而使多個用戶可以解讀（可用于認證系統(tǒng)中對消息進行數(shù)字簽字）。無需事先分配密鑰。公鑰密碼體制有4個組成部分明文：算法的輸入，它們是可讀信息或數(shù)據(jù)，用M表示；密文：算法的輸出。依賴于明文和密鑰，對給定的消息，不同的密鑰產(chǎn)生密文不同。用E表示；公鑰和私鑰：算法的輸入。這對密鑰中一個用于加密，為Ke，此密鑰公開；一個用于解密，為Kd，此密鑰保密。加密算法執(zhí)行的變換依賴于密鑰；加密、解密算法公鑰密碼體制下的秘密通信公鑰加密體制的特點加密和解密能力分開多個用戶加密的消息只能由一個用戶解讀，可用于公共網(wǎng)絡(luò)中實現(xiàn)保密通信用私鑰加密的消息可以用對應(yīng)的公鑰解密，所以由一個用戶加密消息而使多個用戶可以解讀，可用于認證系統(tǒng)中對消息進行數(shù)字簽字無需事先分配密鑰密鑰持有量大大減少提供了對稱密碼技術(shù)無法或很難提供的服務(wù)：如與哈希函數(shù)聯(lián)合運用可生成數(shù)字簽名，可證明的安全偽隨機數(shù)發(fā)生器的構(gòu)造，零知識證明等保證機密性

MEKbeE(M,Kbe)DKbdMKbe：Bob的公鑰Kbd

：Bob的私鑰保證真實性

Kad：Alice的私鑰Kae

：Alice的公鑰MEKadE(M,Kad)DKaeM既保證機密性又保證真實性

Kad：Alice的私鑰Kae

：Alice的公鑰MEKbeE(C1,Kbe)DKbdMEKadC1=E(M,Kad)C1DKaeKbe：Bob的公鑰Kbd

：Bob的私鑰公鑰密碼應(yīng)滿足的要求接收方B產(chǎn)生密鑰對在計算上是容易的發(fā)送方A用收方的公開鑰對消息m加密以產(chǎn)生密文c在計算上是容易的。收方B用自己的秘密鑰對密文c解密在計算上是容易的。敵手由密文c和B的公開密鑰恢復(fù)明文在計算上是不可行的。敵手由密文c和B的公開密鑰恢復(fù)秘密密鑰在計算上是不可行的加解密次序可換，即EPKB[DSKB(m)]=DSKB[EPKB(m)],不是對任何算法都做此要求。對公鑰密碼體制的攻擊和單鑰密碼體制一樣，如果密鑰太短，公鑰密碼體制也易受到窮搜索攻擊。因此密鑰必須足夠長才能抗擊窮搜索攻擊。然而又由于公鑰密碼體制所使用的可逆函數(shù)的計算復(fù)雜性與密鑰長度常常不是呈線性關(guān)系，而是增大得更快。所以密鑰長度太大又會使得加解密運算太慢而不實用。因此公鑰密碼體制目前主要用于密鑰管理和數(shù)字簽字。對公鑰密碼算法的第2種攻擊法是尋找從公開鑰計算秘密鑰的方法。目前為止，對常用公鑰算法還都未能夠證明這種攻擊是不可行的。RSA算法

RSAAlgorithm概況MIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.Adleman[Rivest等1978,1979]發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰的方法，稱作MIT體制，后來被廣泛稱之為RSA體制。它既可用于加密、又可用于數(shù)字簽字。RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性。迄今為止理論上最為成熟完善的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。算法原理RSA算法使用了乘方運算。要求：明文M經(jīng)過加密得到密文C：C=Memodn

密文C經(jīng)過解密得到明文M：

Cd

modn=(Memodn)dmodn=Medmodn=M即：必須存在e，d，n，使Medmodn=M成立如何確定e,d,n確定n：獨立地選取兩大素數(shù)p和q(各100～200位十進制數(shù)字)計算n=p×q，其歐拉函數(shù)值(n)=(p－1)(q－1)確定e：隨機選一整數(shù)e，1e<(n)，gcd((n),e)=1確定d：根據(jù)ed≡

1

mod(n)在模(n)下，計算d這樣確定的e,d,n是否能使Medmodn=M成立呢？因為ed≡1

mod(n)即ed=k(n)+1

所以：Med=Mk(n)+1如果M和n互素，即gcd(M,n)=1那么，根據(jù)歐拉定理(如果gcd(a,n)=1，則

aФ(n)

≡1modn)：有：M(n)≡1modn所以：Med≡Mk(n)+1≡M[M(n)]kmodn

≡M[1]kmodn

≡Mmodn如果M和n不互素，即gcd(M,n)≠1，即M和n有大于1的公約數(shù)。因為n=pq，而p、q都是素數(shù)，不可再分解，所以M一定包含了p或q為因子。又因為M<n，所以M不可能既是p的倍數(shù)又是q的倍數(shù)。不妨設(shè)M是p的倍數(shù)，M=cp。由于M不是q的倍數(shù)，所以gcd(M,q)=1，則M(q)≡1modq，所以：[M(q)](p)≡1modq即M(n)≡1modq，進而有Mk(n)≡1modqMk(n)≡1modq所以：Mk(n)=1+bq（b為整數(shù)）兩邊同乘以M：Mk(n)+1=M+Mbq因為M=cp所以Mk(n)+1=M+cpbq=M+cbn因為cb為整數(shù)，令cb=K，即：

Mk(n)+1=M+Kn因為ed=k(n)+1所以Med=M+Kn即Med≡Mmodn密鑰以n，e為公鑰。秘密鑰為d。(p,q不再需要，可以銷毀。)RSA算法在計算上的可行性加密和解密無論是加密還是解密都需要計算某個整數(shù)的模n整數(shù)次冪，即C=Memodn、M=Cdmodn。但不需要先求出整數(shù)的冪再對n取模，而可利用模運算的性質(zhì)：

(amodn)*(bmodn)=(a*b)modn對于Memodn，可先求出M1modn，M2modn，M4modn……，再求MemodnRSA算法在計算上的可行性產(chǎn)生密鑰由于n是公開的，為了避免攻擊者用窮舉法求出p和q（根據(jù)n=pq），應(yīng)該從足夠大的集合中選取p和q，即p和q必須是大素數(shù)。目前還沒有有效的方法可以產(chǎn)生任意大素數(shù)，通常使用的方法是：隨機挑選一個期望大小的奇數(shù)，然后測試它是否是素數(shù)，若不是，則挑選下一個隨機數(shù)直至檢測到素數(shù)為止。素性檢驗引理：如果p為大于2的素數(shù)，則方程x2≡1modp的解只有x≡1modp和x≡-1modp證明:

x2≡1modpx2-1≡0modp(x+1)(x-1)≡0modp

所以,p|(x+1)或p|(x-1)

或p|(x+1)且p|(x-1)存在k,j，x+1=kp,x-1=jp2=(k-j)p,這是不可能的。或者這樣說p為大于2的素數(shù)，如果有x使得

x2≡1modp成立，那么：

xmodp=1或者xmodp=p-1素數(shù)的性質(zhì)1Letpbeaprimenumbergreaterthan2.Wecanthenwritep-1=2kq,withk>0,qodd.Letabeanyintegerintherange1<a<p-1.Thenoneofthetwofollowingconditionsistrue:aqmodp=1,orequivalently,aq≡1modp.Oneofthenumbersaq,a2q,a4q,...,iscongruentto-1modulop.素數(shù)的性質(zhì)2Proof根據(jù)Fermat‘stheorem，如果p是一個素數(shù),a不是p的倍數(shù)，則：ap-1≡1(modp)又因為p-1=2kq，所以：考察下列數(shù)列：

要么所有數(shù)均為1，要么其中必有一個數(shù)為p-1TEST(n)Findintegersk,q,withk>0,qodd,sothat(n-1=2kq);Selectarandomintegera,1<a<n-1;ifaqmodn=1thenreturn("inconclusive");forj=0tok1doifmodn=n-1thenreturn("inconclusive");return("composite");RepeatedUseoftheMiller-RabinAlgorithm算法對s個不同的a，重復(fù)調(diào)用，如果每次都返回inconclusive

，則n是素數(shù)的概率大于等于1-2-sMiller-Rabin算法可以確定一個整數(shù)是合數(shù)，但不能確定其一定是素數(shù)。要找到一個2200左右的素數(shù)，在找到素數(shù)之前大約要進行l(wèi)n(2200)/2=70次嘗試在N附近平均每隔lnN個整數(shù)就會有一個素數(shù)。RSA算法在計算上的可行性確定d和e有了p和q，可計算出(n)=(p－1)(q－1)根據(jù)gcd((n),e)=1來選擇e，這一步計算量也不大，因為兩個隨機數(shù)互素的概率約為0.6有了e，再計算d=e-1mod(n)，這里用的是擴展的Euclid算法。①選兩個保密的大素數(shù)p和q。②計算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。③選一整數(shù)e，滿足1<e<φ(n)，且gcd(φ(n),e)=1。④計算d，滿足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e與φ(n)互素，由模運算可知，它的乘法逆元一定存在。⑤以{e,n}為公開鑰,{d,n}為秘密鑰。算法描述選p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，滿足1<e<φ(n)，且gcd(φ(n),e)=1。確定滿足d·e=1mod96且小于96的d，因為77×5=385=4×96+1，所以d為77。因此公開鑰為{5，119}，秘密鑰為{77，119}。設(shè)明文m=19，則由加密過程得密文為C=195mod119≡2476099mod119=66解密為6677mod119=19RSA的安全性RSA的安全性是基于分解大整數(shù)的困難性假定如果分解n=p×q，則立即獲得(n)=(p－1)(q－1)，從而能夠確定e的模(n)乘法逆dRSA-129歷時8個月(曾經(jīng)預(yù)言需要4*1016年)被于1994年4月被成功分解，RSA－130于1996年4月被成功分解密鑰長度應(yīng)該介于1024bit到2048bit之間由n直接求(n)等價于分解nRSA-129的故事

鶚鳥（ossifrage），又名髭兀鷹（lammergeier），是阿爾卑斯山上一種稀有的肉食禿鷹。它的翅膀展開將近十米寬。鳥名的字面含義是“碎骨”。顧名思義，其習(xí)性令人毛骨悚然。MirtinGardner在1977年“ScientificAmerican”的專欄文章中介紹了RSA碼。為了顯示這一技術(shù)的威力，RSA公司的研究人員用一個129位的數(shù)N和一個4位數(shù)e對這個關(guān)于禿鷹的消息作了編碼。Gardner刊登了那個密文，同時給出了N和e。RSA公司還懸賞100美元，獎給第一個破譯這密碼的人。96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154一批松散組成的因子分解迷，大約有六百多人，分布在二十幾個國家。他們經(jīng)過八個月的努力最后于1994年4月為RSA-129