計算機安全%20%20公鑰密碼體系

1、編輯ppt 公鑰密碼體系計算機安全與保密編輯ppt對稱算法的不足n密鑰必須通過某一信道協(xié)商，對這個信道的安全性的要求比正常的傳送消息的信道的安全性要高編輯ppt公鑰密碼背景A用戶加密公鑰空間密碼分析解密私鑰空間用戶B明文M1(,)CE M k密文1k2k2( ,)MD C k公鑰密碼體制的特點：n加密密鑰與解密密鑰在本質(zhì)上是不同的，即已知一個密鑰并不能輕易地求出另一個密鑰。1.不需要增加分發(fā)密鑰的額外信道。編輯ppt公鑰密碼體制的要求：編輯pptn公鑰密碼的安全性依賴于從已知的公鑰，加密算法和密文中無法求出明文或秘鑰。nDiffie和Hellman提出了一種陷門單向函數(shù)概念，為建立公鑰密碼體制

2、找到了一種途徑。編輯ppt單向函數(shù)n函數(shù)f 若滿足下列條件n）對任意給定的x，容易計算f(X)=yn）對任意給定的y，求出x使得f(x)=y是困難的。編輯pptn求離散對數(shù)問題y=gx mod p若給出p,g,y求x稱為求離散對數(shù)問題n因子分解問題n=pq若給定n,求p,q稱為因子分解問題n背包問題給定一個有限個自然數(shù)序列集合B=(b1,b2,bn)及二進制數(shù)序列x=(x1,x2,xn)，S= x1 b1 + x2 b2 + + xn bn給定B，S，求x序列，稱為求背包問題編輯ppt單向陷門函數(shù)：單向陷門函數(shù)是滿足下列條件的函數(shù)f：n給定x，計算y=f(x)是容易的；n給定y, 計算x使x=

3、f-1(y)是不可行的；1.存在陷門t，已知t時，對給定的任何y，若相應(yīng)的原象x存在，則計算x是容易的。編輯ppt通過陷門單向函數(shù)建立公鑰密碼nf(x)是單向陷門函數(shù)，陷門為t。 那么設(shè)計公鑰密碼系統(tǒng)時f(x)作為公鑰，陷門t作為私鑰，任何人都可將明文m利用公鑰f(x)加密得到密文y=f(m)，而任何人不知道私鑰即陷門，由密文y都無法求出m，因為f(x)是單向的，但擁有私鑰，便可容易求出m編輯pptRSA公鑰密碼體制1 、1977年由Rivest、Shamir和 Adleman發(fā)明并于1978年公布。2 、明文和密文在0n-1之間,n是一個正整數(shù)3 、應(yīng)用最廣泛的公鑰密碼算法4 、只在美國申請

4、專利，且已于2000年9月到期編輯ppt歐拉函數(shù)( )n1, )nnnn在中，不大于 而且與 互素的正整數(shù)的個數(shù)，記作 (編輯ppt歐拉函數(shù)( )n11)12)(1)kkppppppp、 為素數(shù)， (、 為素數(shù), (1,kkpp計 數(shù) ：中 與互 素 的 數(shù) 的 個 數(shù)1111,1,kkkkkkkkppppppppppppp除去中 的倍數(shù)，剩下的都與互素,2是中所有 的倍數(shù)，共有個。所以與互素的數(shù)的個數(shù)有個1212123(,)1()() ()m mm mmm、若，則編輯ppt歐拉函數(shù)( )n11)12)(1)kkppppppp、 為素數(shù)， (、 為素數(shù), (1212123(,)1()() ()

5、m mm mmm、若，則1, ( )?nn編輯ppt歐拉函數(shù)11)12)(1)kkppppppp、 為素數(shù)， (、 為素數(shù), (1212123(,)1()() ()m mm mmm、若，則1212121212121211111221, ( )? ( )()() ()()(1)(1)(1)mmmmeeemeeeeeemmeeemmnnnp ppnp ppppppppppp編輯ppt歐拉函數(shù)(300)?練習(xí)：2222(300)(253)(2 ) (5 ) (3)2(21)5(51)(31)80,()?p qpq為素數(shù)，()( ) ( )(1)(1)pqpqpq編輯pptnRSA密碼體制的描述n密鑰

6、生成算法：每個用戶執(zhí)行以下操作n隨機生成兩個不同大素數(shù)p,q;n計算n=pq,(n)=(p-1)(q-1);n隨機選取整數(shù)e,1e2是一個素數(shù)，對于任意整數(shù)b0,如果(b,p)=1則p一定是b為基的強偽素數(shù)這個定理說明了Miller-Rabin算法如果輸入的n是素數(shù)，正確的輸出判定n是素數(shù)定理如果n為一奇合數(shù)，則在0,n中，至多有1/4個b 0,n滿足n是b為基的強偽素數(shù)這個定理說明了Miller-Rabin算法如果輸入的n是合數(shù)，但輸出判定n是素數(shù)的概率最多是總之，Miller-Rabin算法判定n是素數(shù)的正確概率至少為75%編輯pptMiller-Rabin素數(shù)判定算法Prime_test

7、(n)For i=0 to 50 b=rand(); if test(n,b)=false return false;/輸出n不是素數(shù) return true;/輸出n是素數(shù)編輯pptP-1分解法0,122mod3gcd(1, )4(1)jStepinputn BStepaStepBaanStepdanStepifdndnelsefor j=2 to 是 的一個因子分解失敗編輯ppt2 3 4 5 61333622mod1333,838(838 1,1333)3131 1333nBStepaa ，后，所以是的一個因子，1333=31 43編輯ppt!1|1(1)|!22 mod2 mod21mod(1)|!1mod|1| ,|(1, )(1, )1,(1, )BBppnq pqqBpBStepanpnp napppBapp ap