信息安全概論,第8講,3.3公鑰密碼算法,公鑰密碼算法又稱(chēng)為非對(duì)稱(chēng)密鑰密碼算法，其主要特征是加密密鑰可以公開(kāi)，而不會(huì)影響到脫密密鑰的機(jī)密性。可用于保護(hù)數(shù)據(jù)的機(jī)密性、完整性、身份識(shí)別等。,3.3.1RSA算法,1.系統(tǒng)建立過(guò)程,Bob選定兩個(gè)不同的素?cái)?shù)p和q，令n=pq，再選取一個(gè)整數(shù)e,使得,。從而可以計(jì)算出,Bob的公開(kāi)密鑰(e,n)Bob的私有密鑰(d,n),表示n的歐拉函數(shù)，即表示不超過(guò)n且與n互素的整數(shù)個(gè)數(shù)。易證當(dāng)n=pq，p和q為不同的素?cái)?shù)時(shí)，,當(dāng)把e看成,中的元時(shí)對(duì)乘法是可逆的，從而可用歐幾里的算法求出其逆元,3.3.1RSA算法,2.加密過(guò)程,RSA算法的明文空間與密文空間均為,3.脫密過(guò)程,3.3.2有限域乘群密碼與橢圓曲線密碼,用有限域構(gòu)造有限群：按照抽象代數(shù)的有限域的構(gòu)造理論，對(duì)于給定的任意一個(gè)素?cái)?shù)p和一個(gè)正整數(shù)n，存在且僅存在一個(gè)pn階的有限域，記為GF(pn)。則G=GF(pn)是一個(gè)s=pn-1階的循環(huán)群。若g是它的一個(gè)生成元，則可記為G=。,1.Diffie-Hellman密鑰交換算法,Alice和Bob選擇了一個(gè)有限域的乘法群G=。,Bob計(jì)算：,結(jié)果，雙方共享了一個(gè)秘密參數(shù)值,Alice計(jì)算：；,Alice秘密選擇一個(gè)指數(shù),作為私鑰，計(jì)算,作為公鑰；,Bob秘密選擇一個(gè)指數(shù),作為私鑰，計(jì)算,作為公鑰；,Alice和Bob通過(guò)公共信道交換公鑰,可作為雙方以后進(jìn)行密碼計(jì)算所需的秘密值，如作為密鑰使用！,1.Diffie-Hellman密鑰交換算法,容易看出，一個(gè)基本假設(shè)是敵手Oscar從給定的A計(jì)算a是困難的。也就是說(shuō)給定底數(shù)g和冪A，求指數(shù)a是困難的，這就是所謂的離散對(duì)數(shù)問(wèn)題是難解的。對(duì)有限域而言，最好的求解離散對(duì)數(shù)問(wèn)題的方法叫做指標(biāo)計(jì)算法，它能在亞指數(shù)時(shí)間內(nèi)求解離散對(duì)數(shù)問(wèn)題。就現(xiàn)在的計(jì)算能力來(lái)講，1024比特規(guī)模階的有限域是足夠了。另一方面，人們?cè)噲D在尋找一個(gè)群，使得其上的離散對(duì)數(shù)問(wèn)題沒(méi)有亞指數(shù)算法。橢圓曲線中可以提供大量的這樣的群。我們稍后再回到這個(gè)問(wèn)題上。,2.ElGamal加密算法,Alice和Bob選擇了一個(gè)有限域的乘法群G=。,Alice秘密選擇一個(gè)指數(shù),，計(jì)算,Bob秘密選擇一個(gè)指數(shù),作為私鑰，計(jì)算,作為公鑰；,Bob把公鑰傳給Alice或公開(kāi)公鑰,Alice要向Bob加密傳送消息m。,和,把消息,發(fā)送給Bob。,Bob可脫密得到:,3.橢圓曲線,橢圓曲線是數(shù)論研究中的重要工具，有幾百年（？）的研究歷史。代數(shù)幾何描述：橢圓曲線虧格為1的光滑的代數(shù)曲線（而橢圓、拋物線、雙曲線是虧格為0的光滑代數(shù)曲線）。橢圓曲線可以化簡(jiǎn)為平面曲線，并由下列的Weierstrass方程表示：,R2上橢圓曲線點(diǎn)的圖像,橢圓曲線上的點(diǎn)有一種自然的加法運(yùn)算，曲線上的點(diǎn)連同y軸方向上無(wú)窮遠(yuǎn)點(diǎn)O構(gòu)成一個(gè)加法群。圖像上點(diǎn)的加法規(guī)則表述為：O是單位元.曲線與任意一條直線如果有交點(diǎn)，則恰有三個(gè)交點(diǎn)，三點(diǎn)的和為O.由此可以同有限域乘法群類(lèi)似地構(gòu)造密碼體制,橢圓曲線群結(jié)構(gòu),EC的基本運(yùn)算,計(jì)算兩個(gè)點(diǎn)的和。已知P(x1,y1),Q(x2,y2)，求R=P+Q的坐標(biāo)R(x3,y3)。令,若Q=-P,則R=O若Q-P,則,1985年Miller,Koblitz注意到有限域上的橢圓曲線加法群具有這樣的屬性。并發(fā)表了該想法，稱(chēng)為ECC。經(jīng)過(guò)多年的研究人們發(fā)現(xiàn)，ECC有較高的安全開(kāi)銷(xiāo)比RSA小（一般認(rèn)為其密鑰長(zhǎng)度開(kāi)銷(xiāo)是RSA算法的1/4以下，而運(yùn)算時(shí)間開(kāi)銷(xiāo)則會(huì)更小）。從而受到業(yè)界的青睞。RSA不能公用密碼參數(shù)，ECC則可以。,4.橢圓曲線密碼ECC,ECC舉例,與在有限域上的乘法群一樣，在有限域上的橢圓曲線也可實(shí)現(xiàn)Diffie-Hellman密鑰交換算法和ElGamal加密算法。,例.Alice想使用橢圓曲線版本的ElGamal加密算法給Bob傳送一個(gè)消息m。這時(shí)Bob選擇了一個(gè)大素?cái)?shù)p=8831，并選擇了一個(gè)有限域GF(8831)上的橢圓曲線E:,以及這條曲線上的一個(gè)點(diǎn)G=(4,11)。Bob還選擇了自己的私鑰b=3，計(jì)算并公開(kāi)一個(gè)點(diǎn)B=bG=(413,1808)作為自己的公鑰。,ECC舉例,假設(shè)Alice想要發(fā)送的消息可以適當(dāng)?shù)鼐幋a為E上的點(diǎn),這時(shí)她首先隨機(jī)選擇一個(gè)指數(shù)k=8，然后計(jì)算,把這兩個(gè)數(shù)據(jù)一同傳送給Bob。Bob利用自己的私鑰b=3和收到的消息計(jì)算,從而完成了脫密運(yùn)算。,ECC,有兩類(lèi)橢圓曲線上的離散對(duì)數(shù)問(wèn)題沒(méi)有預(yù)期的那樣難解。一類(lèi)稱(chēng)為超奇異（supersingular）的曲線，其離散對(duì)數(shù)求解稍比其基域（有限域）上的困難一點(diǎn)。另一類(lèi)稱(chēng)為反常（anomalous）的曲線，其上的離散對(duì)數(shù)問(wèn)題可以通過(guò)形式指數(shù)-形式對(duì)數(shù)映射為十分簡(jiǎn)單的問(wèn)題。用橢圓曲線構(gòu)造密碼系統(tǒng)時(shí)，絕對(duì)要避免反常曲線的情形。密碼研究原來(lái)對(duì)超奇異曲線也不感興趣，但是近年來(lái)人們又發(fā)現(xiàn)超奇異曲線有一些非常好的性質(zhì)。主要是通過(guò)weil配對(duì)，給出的E到基域乘法群上的雙線性映射，為人們提供了一種可以構(gòu)造基于身份的密碼系統(tǒng)的方法。而且這種密碼經(jīng)常是在較基本的假設(shè)下可以證明其安全性，從而成為近年來(lái)學(xué)術(shù)界追逐的對(duì)象之一。,3.4哈希函數(shù),哈希函數(shù)是一類(lèi)重要的函數(shù)，可用于計(jì)算數(shù)字簽名和消息鑒別碼。從而用于防抵賴(lài)、身份識(shí)別和消息鑒別等。,3.4.1安全哈希函數(shù)的定義,哈希函數(shù)是為了實(shí)現(xiàn)數(shù)字簽名或計(jì)算消息的鑒別碼而設(shè)計(jì)的。哈希函數(shù)以任意長(zhǎng)度的消息作為輸入，輸出一個(gè)固定長(zhǎng)度的二進(jìn)制值，稱(chēng)為哈希值、雜湊值或消息摘要。從數(shù)學(xué)上看，哈希函數(shù)H是一個(gè)映射：,這里,安全哈希函數(shù),哈希函數(shù)是代表一個(gè)消息在計(jì)算意義下的特征數(shù)據(jù)。所謂計(jì)算特征數(shù)據(jù)表示在計(jì)算上無(wú)法找到兩個(gè)不同的消息和，使得他們有相同的函數(shù)值。這條性質(zhì)稱(chēng)為哈希函數(shù)的強(qiáng)無(wú)碰撞性。滿(mǎn)足強(qiáng)無(wú)碰撞性的Hash函數(shù)叫做安全Hash函數(shù)。顯然安全Hash函數(shù)滿(mǎn)足：,（1）弱無(wú)碰撞性：給定消息,，計(jì)算上無(wú)法找到一個(gè)不同的,，使得他們有相同的函數(shù)值。,（2）單向性：對(duì)于任一給定的一個(gè)函數(shù)值，求源像，計(jì)算上是不可行的。實(shí)踐證明安全哈希函數(shù)的構(gòu)造是一件十分困難的事，已經(jīng)成為密碼學(xué)研究的一個(gè)熱點(diǎn)。,哈希函數(shù)的構(gòu)造框架,1.選擇一個(gè)適當(dāng)?shù)恼麛?shù)b，稱(chēng)為分組長(zhǎng)度，構(gòu)造一個(gè)映射h：,2.選定一個(gè)初始向量,。,3.對(duì)任意給定的消息x，把它按照固定的規(guī)則擴(kuò)展成長(zhǎng)度為b的整倍數(shù)的二進(jìn)制值：xx1x2xs,4.令y0=IV，執(zhí)行下列迭代運(yùn)算：,則H(x)=ys即為輸入x的雜湊值。,哈希函數(shù)標(biāo)準(zhǔn),1.MD5和SHA-1,。,MD4由Rivest在1990年提出，其增強(qiáng)版于1991年提出。而SHA則是NSA與NIST1993年在MD4基礎(chǔ)上改進(jìn)的，并由美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)局NIST公布作為安全Hash標(biāo)準(zhǔn)(FIPS180)。1995年,由于SHA存在一個(gè)未公開(kāi)的安全性問(wèn)題，NSA提出了SHA的一個(gè)改進(jìn)算法SHA-1作為安全Hash標(biāo)準(zhǔn)（SHS,FIPS180-1.）。2002年，在安全Hash標(biāo)準(zhǔn)FIPSPUB180-2中公開(kāi)了SHA的三種固定輸出長(zhǎng)度分別為256比特、384比特及512比特的變形算法SHA-256、SHA-384及SHA-512.。原SHA和SHA-1的固定輸出長(zhǎng)度為160比特。但目前應(yīng)用較廣泛的還是SHA-1。MD4的另一個(gè)改進(jìn)版MD5，已經(jīng)被證明不滿(mǎn)足強(qiáng)無(wú)碰撞性，從而在一些需要強(qiáng)無(wú)碰撞性的場(chǎng)合使用MD5是不安全的。,哈希函數(shù)標(biāo)準(zhǔn),2.MD5和SHA-1的安全性,。,1998年，兩位法國(guó)研究人員FlorentChabaud與AntoineJoux發(fā)現(xiàn)了攻擊SHA（也稱(chēng)SHA-0）的一種差分碰撞算法。2004年美洲密碼年會(huì)Crypto2004上，AntoineJoux利用BULLSA公司開(kāi)發(fā)計(jì)算機(jī)系統(tǒng)TERANOVA發(fā)現(xiàn)了SHA算法的碰撞的實(shí)例。同一會(huì)議上，王小云指出可通過(guò)大約240次的計(jì)算，找出SHA-0的碰撞例子，她因?yàn)楣鬗D5、HAVAL-128、MD4和RIP