信息安全概論第講第1頁，共24頁，2023年，2月20日，星期日3.3公鑰密碼算法公鑰密碼算法又稱為非對(duì)稱密鑰密碼算法，其主要特征是加密密鑰可以公開，而不會(huì)影響到脫密密鑰的機(jī)密性。可用于保護(hù)數(shù)據(jù)的機(jī)密性、完整性、身份識(shí)別等。第2頁，共24頁，2023年，2月20日，星期日3.3.1RSA算法1.系統(tǒng)建立過程Bob選定兩個(gè)不同的素?cái)?shù)p和q，令n=pq，再選取一個(gè)整數(shù)e,使得。從而可以計(jì)算出Bob的公開密鑰———(e,n)Bob的私有密鑰———(d,n)表示n的歐拉函數(shù)，即表示不超過n且與n互素的整數(shù)個(gè)數(shù)。易證當(dāng)n=pq，p和q為不同的素?cái)?shù)時(shí)，當(dāng)把e看成中的元時(shí)對(duì)乘法是可逆的，從而可用歐幾里的算法求出其逆元第3頁，共24頁，2023年，2月20日，星期日3.3.1RSA算法2.加密過程RSA算法的明文空間與密文空間均為3.脫密過程第4頁，共24頁，2023年，2月20日，星期日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=<g>。第5頁，共24頁，2023年，2月20日，星期日1.Diffie-Hellman密鑰交換算法Alice和Bob選擇了一個(gè)有限域的乘法群G=<g>。Bob計(jì)算：結(jié)果，雙方共享了一個(gè)秘密參數(shù)值A(chǔ)lice計(jì)算：；Alice秘密選擇一個(gè)指數(shù)作為私鑰，計(jì)算作為公鑰；

Bob秘密選擇一個(gè)指數(shù)作為私鑰，計(jì)算作為公鑰；

Alice和Bob通過公共信道交換公鑰可作為雙方以后進(jìn)行密碼計(jì)算所需的秘密值，如作為密鑰使用！第6頁，共24頁，2023年，2月20日，星期日1.Diffie-Hellman密鑰交換算法容易看出，一個(gè)基本假設(shè)是敵手Oscar從給定的A計(jì)算a是困難的。也就是說給定底數(shù)g和冪A，求指數(shù)a是困難的，這就是所謂的離散對(duì)數(shù)問題是難解的。對(duì)有限域而言，最好的求解離散對(duì)數(shù)問題的方法叫做指標(biāo)計(jì)算法，它能在亞指數(shù)時(shí)間內(nèi)求解離散對(duì)數(shù)問題。就現(xiàn)在的計(jì)算能力來講，1024比特規(guī)模階的有限域是足夠了。另一方面，人們?cè)噲D在尋找一個(gè)群，使得其上的離散對(duì)數(shù)問題沒有亞指數(shù)算法。橢圓曲線中可以提供大量的這樣的群。我們稍后再回到這個(gè)問題上。第7頁，共24頁，2023年，2月20日，星期日2.ElGamal加密算法Alice和Bob選擇了一個(gè)有限域的乘法群G=<g>。Alice秘密選擇一個(gè)指數(shù)，計(jì)算Bob秘密選擇一個(gè)指數(shù)作為私鑰，計(jì)算作為公鑰；

Bob把公鑰傳給Alice或公開公鑰Alice要向Bob加密傳送消息m。和把消息發(fā)送給Bob。

Bob可脫密得到:第8頁，共24頁，2023年，2月20日，星期日3.橢圓曲線橢圓曲線是數(shù)論研究中的重要工具，有幾百年（？）的研究歷史。代數(shù)幾何描述：橢圓曲線虧格為1的光滑的代數(shù)曲線（而橢圓、拋物線、雙曲線是虧格為0的光滑代數(shù)曲線）。橢圓曲線可以化簡為平面曲線，并由下列的Weierstrass方程表示：第9頁，共24頁，2023年，2月20日，星期日R2上橢圓曲線點(diǎn)的圖像第10頁，共24頁，2023年，2月20日，星期日橢圓曲線上的點(diǎn)有一種自然的加法運(yùn)算，曲線上的點(diǎn)連同y軸方向上無窮遠(yuǎn)點(diǎn)O構(gòu)成一個(gè)加法群。圖像上點(diǎn)的加法規(guī)則表述為：O是單位元.曲線與任意一條直線如果有交點(diǎn)，則恰有三個(gè)交點(diǎn)，三點(diǎn)的和為O.由此可以同有限域乘法群類似地構(gòu)造密碼體制橢圓曲線群結(jié)構(gòu)第11頁，共24頁，2023年，2月20日，星期日EC的基本運(yùn)算計(jì)算兩個(gè)點(diǎn)的和。已知P(x1,y1),Q(x2,y2)，求R=P+Q的坐標(biāo)R(x3,y3)。令第12頁，共24頁，2023年，2月20日，星期日若Q=-P,則R=O若Q-P,則第13頁，共24頁，2023年，2月20日，星期日1985年Miller,Koblitz注意到有限域上的橢圓曲線加法群具有這樣的屬性。并發(fā)表了該想法，稱為ECC。經(jīng)過多年的研究人們發(fā)現(xiàn)，ECC有較高的安全—開銷比RSA小（一般認(rèn)為其密鑰長度開銷是RSA算法的1/4以下，而運(yùn)算時(shí)間開銷則會(huì)更?。亩艿綐I(yè)界的青睞。RSA不能公用密碼參數(shù)，ECC則可以。4.橢圓曲線密碼ECC第14頁，共24頁，2023年，2月20日，星期日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ì)算并公開一個(gè)點(diǎn)B=bG=(413,1808)作為自己的公鑰。第15頁，共24頁，2023年，2月20日，星期日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)算。第16頁，共24頁，2023年，2月20日，星期日ECC有兩類橢圓曲線上的離散對(duì)數(shù)問題沒有預(yù)期的那樣難解。一類稱為超奇異（supersingular）的曲線，其離散對(duì)數(shù)求解稍比其基域（有限域）上的困難一點(diǎn)。另一類稱為反常（anomalous）的曲線，其上的離散對(duì)數(shù)問題可以通過形式指數(shù)-形式對(duì)數(shù)映射為十分簡單的問題。用橢圓曲線構(gòu)造密碼系統(tǒng)時(shí)，絕對(duì)要避免反常曲線的情形。密碼研究原來對(duì)超奇異曲線也不感興趣，但是近年來人們又發(fā)現(xiàn)超奇異曲線有一些非常好的性質(zhì)。主要是通過weil配對(duì)，給出的E到基域乘法群上的雙線性映射，為人們提供了一種可以構(gòu)造基于身份的密碼系統(tǒng)的方法。而且這種密碼經(jīng)常是在較基本的假設(shè)下可以證明其安全性，從而成為近年來學(xué)術(shù)界追逐的對(duì)象之一。

第17頁，共24頁，2023年，2月20日，星期日3.4哈希函數(shù)哈希函數(shù)是一類重要的函數(shù)，可用于計(jì)算數(shù)字簽名和消息鑒別碼。從而用于防抵賴、身份識(shí)別和消息鑒別等。第18頁，共24頁，2023年，2月20日，星期日3.4.1安全哈希函數(shù)的定義哈希函數(shù)是為了實(shí)現(xiàn)數(shù)字簽名或計(jì)算消息的鑒別碼而設(shè)計(jì)的。哈希函數(shù)以任意長度的消息作為輸入，輸出一個(gè)固定長度的二進(jìn)制值，稱為哈希值、雜湊值或消息摘要。從數(shù)學(xué)上看，哈希函數(shù)H是一個(gè)映射：這里第19頁，共24頁，2023年，2月20日，星期日安全哈希函數(shù)哈希函數(shù)是代表一個(gè)消息在計(jì)算意義下的特征數(shù)據(jù)。所謂計(jì)算特征數(shù)據(jù)表示在計(jì)算上無法找到兩個(gè)不同的消息和，使得他們有相同的函數(shù)值。這條性質(zhì)稱為哈希函數(shù)的強(qiáng)無碰撞性。滿足強(qiáng)無碰撞性的Hash函數(shù)叫做安全Hash函數(shù)。顯然安全Hash函數(shù)滿足：（1）弱無碰撞性：給定消息，計(jì)算上無法找到一個(gè)不同的，使得他們有相同的函數(shù)值。（2）單向性：對(duì)于任一給定的一個(gè)函數(shù)值，求源像，計(jì)算上是不可行的。實(shí)踐證明安全哈希函數(shù)的構(gòu)造是一件十分困難的事，已經(jīng)成為密碼學(xué)研究的一個(gè)熱點(diǎn)。第20頁，共24頁，2023年，2月20日，星期日哈希函數(shù)的構(gòu)造框架1.選擇一個(gè)適當(dāng)?shù)恼麛?shù)b，稱為分組長度，構(gòu)造一個(gè)映射h：2.選定一個(gè)初始向量。3.對(duì)任意給定的消息x，把它按照固定的規(guī)則擴(kuò)展成長度為b的整倍數(shù)的二進(jìn)制值：x→x1‖x2‖…‖xs4.令y0=IV，執(zhí)行下列迭代運(yùn)算：則H(x)=ys即為輸入x的雜湊值。第21頁，共24頁，2023年，2月20日，星期日哈希函數(shù)標(biāo)準(zhǔn)1.MD5和SHA-1。MD4由Rivest在1990年提出，其增強(qiáng)版于1991年提出。而SHA則是NSA與NIST1993年在MD4基礎(chǔ)上改進(jìn)的，并由美國國家標(biāo)準(zhǔn)技術(shù)局NIST公布作為安全Hash標(biāo)準(zhǔn)(FIPS180)。1995年,由于SHA存在一個(gè)未公開的安全性問題，NSA提出了SHA的一個(gè)改進(jìn)算法SHA-1作為安全Hash標(biāo)準(zhǔn)（SHS,FIPS180-1.）。2002年，在安全Hash標(biāo)準(zhǔn)FIPSPUB180-2中公開了SHA的三種固定輸出長度分別為256比特、384比特及512比特的變形算法SHA-256、SHA-384及SHA-512.。原SHA和SHA-1的固定輸出長度為160比特。但目前應(yīng)用較廣泛的還是SHA-1。MD4的另一個(gè)改進(jìn)版MD5，已經(jīng)被證明不滿足強(qiáng)無碰撞性，從而在一些需要強(qiáng)無碰撞性的場(chǎng)合使用MD5是不安全的。第22頁，共24頁，2023年，2月20日，星期日哈希函數(shù)標(biāo)準(zhǔn)2.MD5和SHA-1的安全性。1998年，兩位法國研究人員FlorentChabaud與AntoineJoux發(fā)現(xiàn)了攻擊SHA（也稱SHA-0）的一種差分碰撞算法。2004年美洲密碼年會(huì)Crypto’2004上，AntoineJoux利用BULLSA公司開發(fā)計(jì)算機(jī)系統(tǒng)TERANOVA發(fā)現(xiàn)了SHA算法的碰撞的實(shí)例。同一會(huì)議上，王小云指出可通過大約240次的計(jì)算，找出SHA-0的碰撞例子，她因?yàn)楣鬗D5、HAVAL-128、MD4和RIPEMD算法，并成功給出MD5碰撞的例子而受到關(guān)注。