1、密碼學(xué)韋寶典副教授中山大學(xué)電子系,第7講：公鑰密碼體制,一：公鑰密碼原理二：RSA密碼體制三：Rabin密碼體制四：離散對數(shù)五：ElGamal密碼體制六：Diffie-Hellman密鑰協(xié)商七：公鑰密碼總結(jié),一、公鑰密碼原理,雙(公)鑰密碼體制1976年W.Diffie和M.Hellman;R.Merkle1978可用于保密通信，也可用于數(shù)字簽字密碼學(xué)史上劃時(shí)代的事件為解決計(jì)算機(jī)信息網(wǎng)中的安全提供了新的理論和技術(shù)基礎(chǔ)加密變換(公鑰)公開解密變換(私鑰)保密,一、公鑰密碼原理,公鑰密碼方案RSAscheme(78):R.L.Rivest,A.Shamir,L.Adleman,“AMethodfo

2、rObtainingDigitalSignaturesandPublicKeyCryptosystems”,CACM,Vol.21,No.2,pp.120-126,Feb,1978McEliecescheme(78)Rabinscheme(79)Knapsackscheme(79-):Merkle-Hellman,Chor-RivestWilliamsscheme(80)ElGamalscheme(85)EllipticCurvebasedscheme(85):Koblitz,MillerHiddenFieldEquations(95):C*,PatarinLatticeCryptograph

3、y(97-):Ajtai(AD,DDH,NTRU)NonabeliangroupCryptography(2000):Braid,一、公鑰密碼原理,二、RSA密碼體制,1978年MIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.Adleman用數(shù)論構(gòu)造雙鑰密碼的方法，稱作MIT體制，后被廣泛稱為RSA體制它既可用于加密、又可用于數(shù)字簽名易懂且易于實(shí)現(xiàn)，是目前仍然安全并且逐步被廣泛應(yīng)用的一種體制國際上一些標(biāo)準(zhǔn)化組織ISO、ITU、及SWIFT等均已接受RSA體制作為標(biāo)準(zhǔn)Internet采用的PGP(PrettyGoodPrivacy)也將RSA作為傳送會(huì)話密鑰和數(shù)字簽名的標(biāo)準(zhǔn)算法R

4、SA算法的安全性基于數(shù)論中大整數(shù)分解的困難性,參數(shù)選擇：獨(dú)立地選取兩大素?cái)?shù)p1和p2(各512bit的數(shù))，計(jì)算n=p1p2其歐拉函數(shù)值(n)=(p11)(p21)隨機(jī)選一整數(shù)e，1e(n)，(n),e)=1(因而在模(n)下e有逆元)d=e-1mod(n)公鑰為n，e;私鑰為d(p1,p2不再需要，可以銷毀),二、RSA密碼體制,加密、解密：將明文分組，各組長1024比特明文集Az=x：1xn,(x,n)=1注意，(x,n)1是很危險(xiǎn)的xAz的概率：加密y=xemodn解密x=ydmodn證明：yd=(xe)d=xde，因?yàn)閐e1mod(n)即de=q(n)1由歐拉定理，(x,n)=1意味x

5、(n)1modn，故有yd=xde=xq(n)+1xxq(n)=x1=xmodn陷門函數(shù)：Z=(p1,p2,d),二、RSA密碼體制,例子：p1=47，p2=71，n=4771=3337，(n)=4670=3220e=79，d=e-1(mod3220)=1019公開n=3337和e=79保密私鑰d=1019銷毀p1,p2令x=6882326879666683，分組x1=688，x2=232，x3=687，x4=966，x5=668，x6=3x1的加密為(688)79(mod3337)=1570=C1，類似計(jì)算出其他各組密文，y=15702756209122762423158第一組密文解密為(1

6、570)1019mod3337=688=x類似解出其他各組密文,二、RSA密碼體制,RSA加密實(shí)質(zhì)上是一種Zn*Zn*上的單表代換！給定n=p1p2和合法明文xZn*，密文y=xemodnZn*對于xx，必有yyZn*中的元素是一個(gè)明文，也是與某個(gè)明文相對應(yīng)的一個(gè)密文因此，RSA是ZnZn的一種單表代換密碼關(guān)鍵在于：n極大時(shí)，若不知陷門信息，則極難確定這種對應(yīng)關(guān)系由于這種一一對應(yīng)性，RSA不僅可以用于加密也可用于數(shù)字簽名,二、RSA密碼體制,安全性:分解模數(shù)n理論上，RSA的安全性取決于模n分解的困難性，但數(shù)學(xué)上至今還未證明分解模就是攻擊RSA的最佳方法，也未證明分解大整數(shù)就是NP問題，可能有

7、尚未發(fā)現(xiàn)的多項(xiàng)式時(shí)間分解算法。人們完全可以設(shè)想有另外的途徑破譯RSA，如求出解密指數(shù)d或找到(p11)(p21)等。但這些途徑都不比分解n來得容易。甚至Alexi等1988曾揭示，從RSA加密的密文恢復(fù)某些比特的困難性也和恢復(fù)整組明文一樣困難。這一視在困難性問題是個(gè)NP問題，但還沒人證明它為NPC問題。,二、RSA密碼體制,采用廣義數(shù)域篩分解不同長度RSA公鑰模所需的計(jì)算機(jī)資源,二、RSA密碼體制,密鑰長(bit)所需的MIPS-年*1164001295,00051230,000768200,000,0001024300,000,000,0002048300,000,000,000,000,0

8、00,000*MIPS-年指以每秒執(zhí)行1,000,000條指令的計(jì)算機(jī)運(yùn)行一年,安全性:分解模數(shù)n,技術(shù)進(jìn)展使分解算法和計(jì)算能力在不斷提高，計(jì)算所需的硬件費(fèi)用在不斷下降RSA-129：110位十進(jìn)制數(shù)字早已能分解。Rivest等最初懸賞$100的RSA-129，已經(jīng)由包括五大洲43個(gè)國家600多人參加，用1600臺(tái)機(jī)子同時(shí)產(chǎn)生820條指令數(shù)據(jù)，通過Internet網(wǎng)，耗時(shí)8個(gè)月，于1994年4月2日利用二次篩法分解出為64位和65位的兩個(gè)因子，所給密文的譯文為“這些魔文是容易受驚的魚鷹”。這是有史以來最大規(guī)模的數(shù)學(xué)運(yùn)算。原來估計(jì)要用4億億年。RSA-130于1996年4月10日利用數(shù)域篩法分解

9、出來。RSA-140于1999年2月分解出來。RSA-154(512bit)于1999年8月分解出來。RSA-160,2003.01(http:/www.loria.fr/zimmerma/records/rsa160)RSA-174(576bit),2003.12,二、RSA密碼體制,安全性:分解模數(shù)n,從n若能求出(n)，則可求得p1,p2。n(n)1=p1p2(p11)(p21)1=p1p2(p1+p2)2-4n)1/2=p1-p2但已證明：求(n)等價(jià)于分解n的困難從n求d亦等價(jià)于分解n目前尚不知是否存在一種無需籍助于分解n的攻擊法也未能證明破譯RSA的任何方法都等價(jià)于大整數(shù)分解問題,

10、二、RSA密碼體制,安全性:其它途徑,Simmons和Norris提出迭代/循環(huán)攻擊法：給定一RSA的參數(shù)為(n,e,y)=(35,17,3)，由y0=y=3計(jì)算y1=317=33mod35再由y1計(jì)算y2=y117=3mod35從而得到明文x=y1=33mod35。一般對明文x加密多次，直到再現(xiàn)x為止。Rivest證明：當(dāng)p11和p21中含有大素?cái)?shù)因子，且n足夠大時(shí)，這種攻擊法成功的概率趨于0。,二、RSA密碼體制,安全性:迭代攻擊法,消息破譯0）收集用戶A以公鑰e加密的密文y=xemodn，目標(biāo)分析出消息x1）選隨機(jī)數(shù)rn，計(jì)算y1=remodn，這意味r=y1dmodn2）計(jì)算y2=y1

11、ymodn3）令t=r-1modn=y1-dmodn4）請A對消息y2進(jìn)行簽字(用私鑰，但不能用Hash函數(shù))得到s=y2dmodn5）攻擊者計(jì)算tsmodn=y1-dy2dmodn=y1-d(y1dyd)modn=ydmodn=x得到了明文。,二、RSA密碼體制,安全性:選擇明文攻擊,消息破譯y=xemodn，目標(biāo)分析出消息x=ydmodn=ydy1dy1-dmodn=(yy1)dy1-dmodn=(yre)d(re)-dmodn=y2dr-1modn=y2dtmodny1=remodny2=yy1=yremodnt=r-1modn,二、RSA密碼體制,安全性:選擇明文攻擊,多人共用同一模數(shù)

12、n，各自選擇不同e和d，實(shí)現(xiàn)簡單但不安全若消息以兩個(gè)互素(一般如此)的密鑰加密，在共用同一個(gè)模下，則可用任一密鑰恢復(fù)明文e1和e2是兩個(gè)互素的不同密鑰，共用模為n，對同一消息x加密得y1=xe1modn,y2=xe2modn分析者知道n,e1,e2,y1和y2因?yàn)?e1,e2,)=1，所以由Euclidean算法有re1+se2=1計(jì)算(y1-1)-ry2s=xmodn(假設(shè)r是負(fù)數(shù)),二、RSA密碼體制,安全性:公用模攻擊,小的e可加快加密和驗(yàn)證簽字速度，且所需的存儲(chǔ)密鑰空間小但若加密鑰e選擇得太小，則容易受到攻擊網(wǎng)中三用戶的加密鑰e均選3，分別模n1,n2,n3(互素，否則可求出公因子，而

13、降低安全性)一用戶將消息x傳給三個(gè)用戶的密文分別為y1=x3modn1xe(e+1)/2，采用低指數(shù)亦可有效攻擊為抗擊這種攻擊e必須選得足夠大e選為16位素?cái)?shù)，既可兼顧快速加密，又可防止這類攻擊,二、RSA密碼體制,安全性:低加密指數(shù)攻擊,在x后加時(shí)戳y1=(2tx+t1)3modn1y2=(2tx+t2)3modn2y3=(2tx+t3)3modn3t是t1,t2,t3的二元表示位數(shù)可防止這類攻擊對短的消息，可用隨機(jī)數(shù)字填充以防止低加密指數(shù)攻擊d小也不行：對en，dn1/4，也可以攻破這類RSA體制,二、RSA密碼體制,安全性:低加密指數(shù)攻擊,構(gòu)造y=xemodn，猜測d值，做ydmodn，

14、直到試湊出ydxmodnWiener給出對小d的系統(tǒng)攻擊法，證明了當(dāng)d長度小于n的1/4時(shí)，由連分式算法，可在多項(xiàng)式時(shí)間內(nèi)求出d值,利用測定RSA解密所進(jìn)行的模指數(shù)運(yùn)算的時(shí)間來估計(jì)解密指數(shù)d，而后再精確定出d的取值?？赏ㄟ^將解密運(yùn)算量與參數(shù)d無關(guān)化來挫敗此攻擊(R.Rivest)還可采用盲化技術(shù)：將數(shù)據(jù)盲化后再密，而后做去盲運(yùn)算這樣做雖然不能使解密運(yùn)算時(shí)間保持不變，但計(jì)算時(shí)間被隨機(jī)化而難于推測解密進(jìn)行的指數(shù)運(yùn)算的時(shí)間,二、RSA密碼體制,安全性:定時(shí)攻擊法(Timing:P.Kocher),對明文x，0 xn1，采用RSA體制加密，可能出現(xiàn)xe=xmodn，致使消息暴露這是明文在RSA加密下的

15、不動(dòng)點(diǎn)總有一些不動(dòng)點(diǎn)，如x=0，1和n1一般有1+gcd(e1,p1)1+gcd(e1,q1)個(gè)不動(dòng)點(diǎn)由于e1，p1和q1都是偶數(shù)所以不動(dòng)點(diǎn)至少為9個(gè)一般來說，不動(dòng)點(diǎn)個(gè)數(shù)相當(dāng)少而可忽略,二、RSA密碼體制,安全性:消息隱匿問題,D.Boneh.TwentyYearsofAttacksontheRSACryptosystem.NoticesoftheAmericanMathematicalSociety,46(2):203-213,1999./dabo/abstracts/RSAattack-survey.html,二、RSA密碼體制,安全性,(

16、1)n=pq的確定：p與q必須為強(qiáng)素?cái)?shù)強(qiáng)素?cái)?shù)p的條件：(a)存在兩個(gè)大素?cái)?shù)p1和p2，p1|(p1)，p2|(p1)(b)存在4個(gè)大素?cái)?shù)r1,s1,r2及s2，使r1|(p11),r2|(p21),s1|(p11),s2|(p21)。p1和p2為二級素?cái)?shù)；r1,r2,s1和s2為三級素?cái)?shù),二、RSA密碼體制,RSA參數(shù)的選擇,采用強(qiáng)素?cái)?shù)的理由如下：若，pi為素?cái)?shù)，ai為正整數(shù)分解式中piB，B為已知一個(gè)小整數(shù)則存在一種p1的分解法，使我們易于分解n令n=pq，且p1滿足上述條件，piB令aai，i=1,2,t可構(gòu)造顯然(p1)R，由費(fèi)爾馬定理2R1modp令2R=xmodn，若x=1則選3代2

17、，直到出現(xiàn)x1此時(shí)，kR=1modp有解的充要條件是kR=xmodn(p,n)=p|x-1由GCD(x1,n)=p，就得到n的分解因子p和q,二、RSA密碼體制,RSA參數(shù)的選擇,p與q之差要大若p與q之差很小，則可由n=pq估計(jì)(pq)/2=n1/2，由(pq)/2)2n=(pq)/2)2，等式右邊為小的平方數(shù)，可以試驗(yàn)給出p,q的值例：n=164009，估計(jì)(pq)/2405，由4052n=16=42，可得(pq)/2=405，(pq)/2=4，p=409，q=401,二、RSA密碼體制,RSA參數(shù)的選擇,p1與q1的最大公因子要小惟密文攻擊下，設(shè)破譯者截獲密文y=xemodn破譯者做下述

18、遞推計(jì)算：xi=xi-1emodn=(xe)imodn若ei=1mod(n)，則有xi=xmodn，且ei+1=emod(n)，即xi+1=x若i小，則由此攻擊法易得明文x。由Euler定理知，i=(p1)(q1)，若p1和q1的最大公因子小，則i值大，如i=(p1)(q1)/2，此攻擊法難于奏效。,二、RSA密碼體制,RSA參數(shù)的選擇,p，q要足夠大，以使n分解在計(jì)算上不可行,二、RSA密碼體制,RSA參數(shù)的選擇,e的選取原則(e,(n)=1條件易于滿足，因?yàn)閮蓚€(gè)隨機(jī)數(shù)互素的概率約為3/5e不可過小：若e小，x小，y=xemodn，當(dāng)xen，則未取模，由y直接開e次方可求x，易遭低指數(shù)攻擊e

19、小時(shí)，加密速度快，Knuth和Shamir曾建議采用e=3但e太小存在一些問題選e在mod(n)中的階數(shù)i(ei1mod(n)達(dá)到(p1)(q1)/2,二、RSA密碼體制,RSA參數(shù)的選擇,p，q要足夠大，以使n分解在計(jì)算上不可行,d的選擇e選定后可用Euclidean算法在多項(xiàng)式時(shí)間內(nèi)求出dd小，簽字和解密快，在IC卡中尤為重要(復(fù)雜的加密和驗(yàn)證簽字可由主機(jī)來做)d要大于n1/4：類似于加密下的情況，d不能太小否則由已知明文攻擊，構(gòu)造y=xemodn，猜測d的值：做ydmodn，直到試湊出ydxmodnWiener給出對小d的系統(tǒng)攻擊法，證明了當(dāng)d長度小于n的1/4時(shí)，由連分式算法，可在多項(xiàng)

20、式時(shí)間內(nèi)求出d值,二、RSA密碼體制,RSA參數(shù)的選擇,不可用公共模由一密鑰產(chǎn)生中心(KGC)采用一公共模，分發(fā)多對密鑰，公布相應(yīng)公鑰ei這當(dāng)然使密鑰管理簡化，存儲(chǔ)空間小，且無重新分組問題但如前所述，它在安全上會(huì)帶來問題。明文熵要盡可能地大明文熵要盡可能地大，以使在已知密文下，要猜測明文無異于完全隨機(jī)等概情況。用于簽字時(shí)，要采用Hash函數(shù),二、RSA密碼體制,RSA體制實(shí)用中的其它問題,Set-upoftheRabinSystem,Choosetwodistinctprimesp,qs.t.andputn=pq.Encryptionfunction,三、Rabin密碼體制,Encryptio

21、nalgorithm:,Decryptionalgorithm:step1:Finda,bs.t.ap+bq=1usingtheEuclideanalgorithm.step2:putstep3:Compute,三、Rabin密碼體制,Claim:,arefourrootsof,andmisoneofthesefour.Choseonewhichmakessense!,Theorem.Letn=pqbetheproductoftwodistinctoddprimesp,q.If,thenhasnosolutionsorexactlyfoursolutions(ii)Letr,sbeasolut

22、ionof,respectively,thenthefoursolutionsofare(aps+bqr);-(aps+bqr);(aps-bqr);-(aps-bqr),wherea,bsatisfyap+bq=1.(iii)If,thenisasolutionof,三、Rabin密碼體制,c=x2modpcp-1=1modpc(p-1)/2=xp-1=1modpc=x2modnc=x2modqcq-1=1modqc(q-1)/2=xq-1=1modqc(p-1)/2c=x2modpx=c(p+1)/4modpCRT:c(q-1)/2c=x2modqx=c(q+1)/4modqx=c(p+1

23、)/4bqc(q+1)/4apmodn,Theorem:Solvingforallisequivalenttofactoringn.,Cryptanalysis,三、Rabin密碼體制,四、離散對數(shù),Thediscretelogarithmproblemappliestomathematicalstructurescalledgroups.GivenanelementginafinitegroupGandanotherelementhinG,findanintegerxsuchthatgx=h.Likethefactoringproblem,thediscretelogarithmproble

24、misbelievedtobedifficultandalsotobetheharddirectionofaone-wayfunction.Forthisreason,ithasbeenthebasisofseveralpublic-keycryptosystems,includingtheElGamalsystemandDSS.ThediscretelogarithmproblembearsthesamerelationtothesesystemsasfactoringdoestotheRSAsystem:thesecurityofthesesystemsrestsontheassumpti

25、onthatdiscretelogarithmsaredifficulttocompute.,Thediscretelogarithmproblemhasreceivedmuchattentioninrecentyears;descriptionsofsomeofthemostefficientalgorithmsfordiscretelogarithmsoverfinitefieldscanbefound.Thebestdiscretelogarithmalgorithmshaveexpectedrunningtimessimilartothoseofthebestfactoringalgo

26、rithms.Rivesthasanalyzedtheexpectedtimetosolvethediscretelogarithmproblembothintermsofcomputingpowerandcost.Ingeneral,thediscretelogarithminanarbitrarygroupofsizencanbecomputedinrunningtimeO(n1/2),thoughinmanygroupsitcanbedonefaster.,四、離散對數(shù),四、離散對數(shù),ElGamal1984,1985提出、基于離散對數(shù)問題的雙鑰密碼體制既可用于加密，又可用于簽字方案：Zp

27、是一個(gè)有p個(gè)元素的有限域，p是一個(gè)素?cái)?shù)，g是Zp的一個(gè)生成元明文集M為Zp，密文集C為ZpZp。公鑰：ygxmodp秘密鑰：xp(2)加密：選擇隨機(jī)數(shù)kZp-1，且(k,p1)=1，對明文組M計(jì)算：c1=gkmodp(隨機(jī)數(shù)k被加密)c2=Mykmodp(明文被隨機(jī)數(shù)k和公鑰加密)密文由y1、y2級連構(gòu)成，即密文C=c1|c2。(3)解密：收到密文組C后，計(jì)算c2=Myk=M(gx)k=M(gk)x=M(c1)xM=c2/c1x=Myk/gkx=Mgxk/gkmodp,五、ElGamal密碼體制,c1=gkc2=Myk=M(gx)k=M(gk)x=M(c1)xM=c2/c1x=Myk/gkx=

28、Mgxk/gkxmodp特點(diǎn)：密文由明文和所選隨機(jī)數(shù)k來定，因而是非確定性加密，一般稱之為隨機(jī)化加密，對同一明文不同時(shí)刻的隨機(jī)數(shù)k不同會(huì)給出不同的密文代價(jià)是數(shù)據(jù)擴(kuò)展一倍例p=2579，g=2，x=765，y=g765mod2579=949明文為M=1299，選隨機(jī)數(shù)k=853c12853mod2579=435c21299949853mod2579=2396密文C=(435,2396)解密：C算出消息組M2396/(435)765mod2579=1299。安全性：本體制基于Zp中有限群上的離散對數(shù)的困難性。,五、ElGamal密碼體制,算法雙方選擇素?cái)?shù)p以及p的一個(gè)本原根g用戶A選擇一個(gè)隨機(jī)數(shù)X

29、ap，計(jì)算Ya=gXamodp用戶B選擇一個(gè)隨機(jī)數(shù)Xbp，計(jì)算Yb=gXbmodp每一方保密X值，而將Y值交換給對方用戶A計(jì)算出K=YbXamodp用戶B計(jì)算出K=YgXbmodp雙方獲得一個(gè)共享密鑰(gXaXbmodp)素?cái)?shù)p以及p的本原根g可由一方選擇后發(fā)給對方,六、Diffie-Hellman密鑰交換,GeneraterandomXapCalculateYa=gXamodp,GeneraterandomXbpCalculateYb=gXbmodp,UserA,UserB,Ya,Yb,CalculateK=(Yb)Xamodp,CalculateK=(Ya)Xbmodp,Diffie-He

30、llmanKeyExchange,六、Diffie-Hellman密鑰交換,Diffie-Hellman密鑰交換的攻擊,replay攻擊,中間人攻擊圖示,六、Diffie-Hellman密鑰交換,中間人攻擊1雙方選擇素?cái)?shù)p以及p的一個(gè)原根g(假定O知道)2A選擇Xap,計(jì)算Ya=gXamodp,AB:Ya3O截獲Ya,選Xo,計(jì)算Yo=gXomodp,冒充AB:Yo4B選擇Xbp,計(jì)算Yb=gXbmodp,BA:Yb5O截獲Yb,冒充BA:Yo6A計(jì)算:(Yo)Xa(gXo)XagXoXamodp7B計(jì)算:(Yo)Xb(gXo)XbgXoXbmodp8O計(jì)算:(Ya)XogXaXomodp,(

31、Yb)XogXbXomodpO無法計(jì)算出gXaXbmodp雖然不需要計(jì)算出這個(gè)數(shù)，但O必須實(shí)時(shí)截獲每一數(shù)值，并冒充轉(zhuǎn)發(fā),否則會(huì)被發(fā)現(xiàn),Diffie-Hellman密鑰交換的攻擊,六、Diffie-Hellman密鑰交換,雙鑰體制的加密變換是公開的，任何人都可以采用選擇明文來攻擊雙鑰體制，明文空間必須足夠大才能防止窮盡搜索明文空間攻擊。這在雙鑰體制應(yīng)用中特別重要(如用雙鑰體制加密會(huì)話密鑰時(shí)，會(huì)話密鑰要足夠長)。一種更強(qiáng)有力的攻擊法是選擇密文攻擊：攻擊者選擇密文，而后通過某種途徑得到相應(yīng)的明文。多數(shù)雙鑰體制對于選擇密文攻擊特別敏感。通常采用兩類選擇密文攻擊：(1)冷漠(Indifferent)選擇

32、明文攻擊。在接收到待攻擊的密文之前，可以向攻擊者提供他們所選擇的密文的解密結(jié)果。(2)自適應(yīng)選擇密文攻擊，攻擊者可能利用(或接入)被攻擊者的解密機(jī)(但不知其秘密鑰)，而可以對他所選擇的、與密文有關(guān)的待攻擊的密文，以及以前詢問得到的密文進(jìn)行解密。,七、公鑰密碼總結(jié),雙鑰密碼體制的設(shè)計(jì)雙鑰密鑰保密、認(rèn)證系統(tǒng)的的安全性主要取決于構(gòu)造雙鑰算法所依賴的數(shù)學(xué)問題。要求加密函數(shù)具有單向性，即求逆的困難性。因此，設(shè)計(jì)雙鑰體制的關(guān)鍵是先要尋求一個(gè)合適的單向函數(shù)。,七、公鑰密碼總結(jié),單向函數(shù)令函數(shù)f是集A到集B的映射，以f：AB表示。若對任意x1x2，x1,x2A，有f(x1)f(x2)，則稱f為單射，或11映射

33、，或可逆的函數(shù)。f為可逆的充要條件是，存在函數(shù)g：BA，使對所有xA有g(shù)f(x)=x。一個(gè)可逆函數(shù)f：AB，若它滿足：1、對所有xA，易于計(jì)算f(x)。2、對“幾乎所有xA”由f(x)求x“極為困難”，以至于實(shí)際上不可能做到則稱f為一單向(One-way)函數(shù)?！皹O為困難”是對現(xiàn)有的計(jì)算資源和算法而言。Massey稱此為視在困難性(apparentdifficulty)，相應(yīng)函數(shù)稱之為視在單向函數(shù)。以此來和本質(zhì)上(Essentially)的困難性相區(qū)分Massey1985。,七、公鑰密碼總結(jié),例令f是在有限域GF(p)中的指數(shù)函數(shù)，其中p是大素?cái)?shù)，即y=f(x)=x,式中，xGF(p)，x為滿

34、足0 xp1的整數(shù)，其逆運(yùn)算是GF(p)中定義的對數(shù)運(yùn)算，即x=logx0 xp1顯然，由x求y是容易的，即使當(dāng)p很大，例如p2100時(shí)也不難實(shí)現(xiàn)。為方便計(jì)算以下令=2。所需的計(jì)算量為ln2p次乘法，存儲(chǔ)量為(ln2p)2比特例如p=2100時(shí)，需作100次乘法。利用計(jì)算機(jī)由x計(jì)算x可在0.1毫秒內(nèi)完成。但是，相對于當(dāng)前計(jì)算GF(p)中對數(shù)最好的算法，要從x計(jì)算x所需存儲(chǔ)量大約為(2/3)*(p)1/2*logp比特、運(yùn)算量大約為(1/2)*(p)1/2*logp例如p=2100時(shí)，所需的計(jì)算量為(1/2)*250*100次，以計(jì)算指數(shù)一樣快的計(jì)算機(jī)進(jìn)行計(jì)算需時(shí)約1010.7秒(1年=107.

35、5秒，約為1600年！其中假定存儲(chǔ)量的要求能夠滿足)?？梢?，當(dāng)p很大時(shí)，GF(p)中的f(x)=x，xp1是個(gè)單向函數(shù)。,七、公鑰密碼總結(jié),Pohlig和Hellman對(p1)無大素因子時(shí)給出一種快速求對數(shù)的算法Pohlig等1978。特別是，當(dāng)p=2n1時(shí)，從x求x的計(jì)算量僅需(logp)2次乘法。對于p=2160，在高速計(jì)算機(jī)上大約僅需時(shí)10毫秒。因此，在這種情況下，f(x)=x就不能被認(rèn)為是單向函數(shù)。當(dāng)對素?cái)?shù)p，且p1有大的素因子時(shí)，GF(p)上的函數(shù)f(x)=x是一個(gè)視在單向函數(shù)。尋求在GF(p)上求對數(shù)的一般快速算法是當(dāng)前密碼學(xué)研究中的一個(gè)重要課題。,七、公鑰密碼總結(jié),陷門單向函數(shù)

36、單向函數(shù)是求逆困難的函數(shù)，而單向陷門函數(shù)(Trapdoorone-wayfunction)是在不知陷門信息下求逆困難的函數(shù)，當(dāng)知道陷門信息后求逆是易于實(shí)現(xiàn)的。Diffie和Hellmam1976引入的有用概念。例：號碼鎖、太平門。但如何給陷門單向函數(shù)下定義則很棘手，因?yàn)?1)陷門函數(shù)其實(shí)不是單向函數(shù)，因?yàn)閱蜗蚝瘮?shù)在任何條件下求逆都是困難的；(2)陷門可能不止一個(gè)，通過試驗(yàn),一個(gè)個(gè)陷門就可容易地找到逆。如果陷門信息的保密性不強(qiáng)，求逆也就不難。,七、公鑰密碼總結(jié),公鑰系統(tǒng)一個(gè)公鑰系統(tǒng)中，所有用戶共同選定一個(gè)陷門單向函數(shù)、加密運(yùn)算E及可用消息集鑒別函數(shù)F。用戶i從陷門集中選定zi，并公開Ezi和Fz

37、i。任一要向用戶i送機(jī)密消息者，可用Fzi檢驗(yàn)消息x是否在許用明文之中，而后送y=Ezi(x)給用戶x即可。在僅知y，Ezi和Fzi下，任一用戶不能得到x。但用戶i利用陷門信息zi，易于得到Dzi(y)=x。定義對zZ和任意xX，F(xiàn)i(x)yY=X。若Fj(Fi(x)=Fi(Fj(x)成立，則稱F為可換單向函數(shù)?？蓳Q單向函數(shù)在密碼學(xué)中更有用。,七、公鑰密碼總結(jié),用于構(gòu)造雙鑰密碼的單向函數(shù)1976年Diffie和Hellman發(fā)表的文章中雖未給出陷門單向函數(shù)，但大大推動(dòng)了這方面的研究工作。雙鑰密碼體制的研究在于給出這種函數(shù)的構(gòu)造方法以及它們的安全性。陷門單向函數(shù)的定義并沒有給出這類函數(shù)是否存在。目前多數(shù)雙鑰體制所用的單向函數(shù)的例子多項(xiàng)式求根離散對數(shù)大整數(shù)分解/RSA問題背包問題Diffie-Hellman問題(DHP)二次剩余問題模