資源描述:
《密碼學(xué)公鑰密碼1》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、5.1公鑰密碼的理論基礎(chǔ)5.2RSA公鑰密碼5.2.2RSA公鑰密碼體制5.2.3RSA的安全性討論5.2.4模n求逆的方法5.2.5模n的大數(shù)冪乘的快速算法5.2.6因子分解5.3大素?cái)?shù)生成第五章公鑰密碼1976年,W.Diffie和M.E.Hellman首先提出了公鑰密碼學(xué)。在公鑰密碼體制中,加密密鑰(Public-key)和解密密鑰(private-key)是不一樣的,由兩者任何一個(gè)不能推出另一個(gè),本章介紹RSA公鑰密碼體制,ElGamal公鑰密碼體制,Menezes-Vanstone公鑰密碼體制以
2、及一些相關(guān)知識(shí)。公鑰密碼的理論基礎(chǔ)是單向函數(shù)。5.1公鑰密碼的理論基礎(chǔ)定義5.1設(shè)f是一個(gè)函數(shù)。如果對(duì)任意給定的x,計(jì)算y使得y=f(x)是容易的,但對(duì)任意給定的y,計(jì)算x使y=f(x)是難解的,即求f的逆函數(shù)是難解的,則稱y=f(x)是一個(gè)單向函數(shù)(one-wayfunction)。定義5.2設(shè)f是一個(gè)函數(shù),t是與f有關(guān)的一個(gè)參數(shù),對(duì)任意給定的x,計(jì)算y使得y=f(x)是容易的,如果當(dāng)不知參數(shù)t時(shí),計(jì)算f的逆函數(shù)是難解的,但當(dāng)知道參數(shù)t時(shí),計(jì)算f的逆函數(shù)是容易的,則稱f是一個(gè)陷門單向函數(shù)(trapdoo
3、rone-wayfunction),參數(shù)t稱為陷門。在公鑰密碼中,加密變換是一個(gè)陷門單向函數(shù)。5.2RSA公鑰密碼5.2.1基本的數(shù)論知識(shí)定義5.3設(shè)a,b,n都是整數(shù)。如果n
4、(a-b)則稱a和b模n同余,記為,n稱為這個(gè)同余式的模。同余的性質(zhì):定理5.1(中國剩余定理)設(shè)是兩兩互素的正整數(shù),設(shè)是整數(shù)。則同余方程組模有唯一解:證明:對(duì)任意,考慮下面我們來證明式(5.2)是同余方程組(5.1)的模唯一解,假設(shè)和是同余方程組(5.1)的兩個(gè)解,即因此,式(5.2)是同余方程組(5.1)的模唯一解。則即故例1
5、(孫子算經(jīng)中物不知數(shù))今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何?解:例2(韓信點(diǎn)兵)有兵一對(duì),若列5行縱隊(duì),則末行1人,成6行縱隊(duì),則末行5人,成7行縱隊(duì),則末行4人,成11行縱隊(duì),末行10人.求兵數(shù)?解:5.2.2Euler函數(shù)定義5.4設(shè)n是一個(gè)正整數(shù)。稱為Euler函數(shù)。Euler函數(shù)是定義在正整數(shù)集合上的函數(shù)。由定義可以立即得出,如果p是一個(gè)素?cái)?shù),則定理5.2如果證明:定理5.3如果證明:首先證明對(duì)于任意素?cái)?shù)和任意正整數(shù)有根據(jù)定理5.2,我們有定理5.5(Euler定理)
6、5.2.3Euler定理和Fermat小定理推論5.1(Fermat小定理)定理5.5(Fermat小定理)證明:因?yàn)閜是素?cái)?shù),所以x或者與p互素或者是p的倍數(shù),如果x與p互素,則由推論5.1知結(jié)論顯然成立。如果x是p的倍數(shù),則也是p的倍數(shù),因此,結(jié)論也成立。設(shè)x和p都是正整數(shù),則5.2.4RSA公鑰密碼體制RonRivest、AdiShamir以及LeonardAdleman于1978年提出了RSA公鑰密碼體制。RSA公鑰密碼體制描述如下:RSA合理性證明練習(xí)例:取p=13,q=17,則n=13*17=
7、221,∮(n)=12*16=192,隨機(jī)取e=71,要求e與∮(n)互素,將后者分解即可。這里選取e有很多原則,加上∮(n)較大的時(shí)候,e的選取也較麻煩.d=e-1mod∮(n)=119.(該過程需用輾轉(zhuǎn)相除法和歐幾里德擴(kuò)展定理)這里RSA公鑰密碼系統(tǒng)建立,其中公鑰為(e,n)公開;私鑰(d,n)僅解密者知道。加密消息m=5,則密文c=m^emodn=112(該過程用的其他定理)解密的時(shí)候,對(duì)密文c=112,進(jìn)行d次方m=c^dmodn=112^119modn=5.5.2.5RSA的安全性討論RSA公鑰
8、密碼體制的安全性是基于大整數(shù)的素分解問題的難解性。隨著計(jì)算能力的持續(xù)增長和因子分解算法的不斷完善,為保證RSA的安全性,在實(shí)際應(yīng)用中選取的素?cái)?shù)p和q越來越大,現(xiàn)在來看,n的長度為1024位至2048位是比較合理的。注意以下事實(shí):除了指定n的大小之外,p和q的選取應(yīng)做如下限制:5.2.6模n求逆的方法求兩個(gè)正整數(shù)的最大公因子gcd(n,u)的Euclid算法如下:擴(kuò)展的Euclid算法存在正整數(shù)a和b,使得擴(kuò)展的Euclid算法如下:定理5.6設(shè)是一個(gè)正整數(shù),證明必要性。顯然,對(duì)任意存在整數(shù)使得充分性.假設(shè)
9、則存在整數(shù)使得模n求逆的算法求模n求逆的算法如下:故5.2.7模n的大數(shù)冪乘的快速算法模n的大數(shù)冪乘的快速算法如下:例5.3計(jì)算5.2.8因子分解J.M.Pollard(1974):p-1因子分解法:警告!!由P-1因子分解算法可以看出,在RSA公鑰密碼體制中,大素?cái)?shù)p和q的選取應(yīng)滿足p-1和q-1都至少有一個(gè)大的素因子。否則n可被分解,RSA被破譯。5.3大素?cái)?shù)的生成本節(jié)介紹快速生成大素?cái)?shù)的一些常用基本方法5.3.1素?cái)?shù)的分