信息安全概論第講

信息安全概論第講第一頁，共二十四頁，編輯于2023年，星期六3.3公鑰密碼算法公鑰密碼算法又稱為非對稱密鑰密碼算法，其主要特征是加密密鑰可以公開，而不會影響到脫密密鑰的機密性?？捎糜诒Ｗo數(shù)據(jù)的機密性、完整性、身份識別等。第二頁，共二十四頁，編輯于2023年，星期六3.3.1RSA算法1.系統(tǒng)建立過程Bob選定兩個不同的素數(shù)p和q，令n=pq，再選取一個整數(shù)e,使得。從而可以計算出Bob的公開密鑰———(e,n)Bob的私有密鑰———(d,n)表示n的歐拉函數(shù)，即表示不超過n且與n互素的整數(shù)個數(shù)。易證當n=pq，p和q為不同的素數(shù)時，當把e看成中的元時對乘法是可逆的，從而可用歐幾里的算法求出其逆元第三頁，共二十四頁，編輯于2023年，星期六3.3.1RSA算法2.加密過程RSA算法的明文空間與密文空間均為3.脫密過程第四頁，共二十四頁，編輯于2023年，星期六3.3.2有限域乘群密碼與橢圓曲線密碼用有限域構造有限群：按照抽象代數(shù)的有限域的構造理論，對于給定的任意一個素數(shù)p和一個正整數(shù)n，存在且僅存在一個pn階的有限域，記為GF(pn)。則G=GF(pn)×是一個s=pn-1階的循環(huán)群。若g是它的一個生成元，則可記為G=<g>。第五頁，共二十四頁，編輯于2023年，星期六1.Diffie-Hellman密鑰交換算法Alice和Bob選擇了一個有限域的乘法群G=<g>。Bob計算：結果，雙方共享了一個秘密參數(shù)值Alice計算：；Alice秘密選擇一個指數(shù)作為私鑰，計算作為公鑰；

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

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

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

Bob可脫密得到:第八頁，共二十四頁，編輯于2023年，星期六3.橢圓曲線橢圓曲線是數(shù)論研究中的重要工具，有幾百年（？）的研究歷史。代數(shù)幾何描述：橢圓曲線虧格為1的光滑的代數(shù)曲線（而橢圓、拋物線、雙曲線是虧格為0的光滑代數(shù)曲線）。橢圓曲線可以化簡為平面曲線，并由下列的Weierstrass方程表示：第九頁，共二十四頁，編輯于2023年，星期六R2上橢圓曲線點的圖像第十頁，共二十四頁，編輯于2023年，星期六橢圓曲線上的點有一種自然的加法運算，曲線上的點連同y軸方向上無窮遠點O構成一個加法群。圖像上點的加法規(guī)則表述為：O是單位元.曲線與任意一條直線如果有交點，則恰有三個交點，三點的和為O.由此可以同有限域乘法群類似地構造密碼體制橢圓曲線群結構第十一頁，共二十四頁，編輯于2023年，星期六EC的基本運算計算兩個點的和。已知P(x1,y1),Q(x2,y2)，求R=P+Q的坐標R(x3,y3)。令第十二頁，共二十四頁，編輯于2023年，星期六若Q=-P,則R=O若Q-P,則第十三頁，共二十四頁，編輯于2023年，星期六1985年Miller,Koblitz注意到有限域上的橢圓曲線加法群具有這樣的屬性。并發(fā)表了該想法，稱為ECC。經(jīng)過多年的研究人們發(fā)現(xiàn)，ECC有較高的安全—開銷比RSA?。ㄒ话阏J為其密鑰長度開銷是RSA算法的1/4以下，而運算時間開銷則會更小）。從而受到業(yè)界的青睞。RSA不能公用密碼參數(shù)，ECC則可以。4.橢圓曲線密碼ECC第十四頁，共二十四頁，編輯于2023年，星期六ECC舉例與在有限域上的乘法群一樣，在有限域上的橢圓曲線也可實現(xiàn)Diffie-Hellman密鑰交換算法和ElGamal加密算法。例.Alice想使用橢圓曲線版本的ElGamal加密算法給Bob傳送一個消息m。這時Bob選擇了一個大素數(shù)p=8831，并選擇了一個有限域GF(8831)上的橢圓曲線E:以及這條曲線上的一個點G=(4,11)。Bob還選擇了自己的私鑰b=3，計算并公開一個點B=bG=(413,1808)作為自己的公鑰。第十五頁，共二十四頁，編輯于2023年，星期六ECC舉例假設Alice想要發(fā)送的消息可以適當?shù)鼐幋a為E上的點這時她首先隨機選擇一個指數(shù)k=8，然后計算把這兩個數(shù)據(jù)一同傳送給Bob。Bob利用自己的私鑰b=3和收到的消息計算從而完成了脫密運算。第十六頁，共二十四頁，編輯于2023年，星期六ECC有兩類橢圓曲線上的離散對數(shù)問題沒有預期的那樣難解。一類稱為超奇異（supersingular）的曲線，其離散對數(shù)求解稍比其基域（有限域）上的困難一點。另一類稱為反常（anomalous）的曲線，其上的離散對數(shù)問題可以通過形式指數(shù)-形式對數(shù)映射為十分簡單的問題。用橢圓曲線構造密碼系統(tǒng)時，絕對要避免反常曲線的情形。密碼研究原來對超奇異曲線也不感興趣，但是近年來人們又發(fā)現(xiàn)超奇異曲線有一些非常好的性質(zhì)。主要是通過weil配對，給出的E到基域乘法群上的雙線性映射，為人們提供了一種可以構造基于身份的密碼系統(tǒng)的方法。而且這種密碼經(jīng)常是在較基本的假設下可以證明其安全性，從而成為近年來學術界追逐的對象之一。

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