資源描述：
《密碼學(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ù)增長(zhǎng)和因子分解算法的不斷完善，為保證RSA的安全性，在實(shí)際應(yīng)用中選取的素?cái)?shù)p和q越來越大，現(xiàn)在來看，n的長(zhǎng)度為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ù)的分
