計(jì)算機(jī)安全%20%20公鑰密碼體系

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

2、找到了一種途徑。編輯ppt單向函數(shù)n函數(shù)f 若滿足下列條件n）對任意給定的x，容易計(jì)算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背包問題給定一個(gè)有限個(gè)自然數(shù)序列集合B=(b1,b2,bn)及二進(jìn)制數(shù)序列x=(x1,x2,xn)，S= x1 b1 + x2 b2 + + xn bn給定B，S，求x序列，稱為求背包問題編輯ppt單向陷門函數(shù)：單向陷門函數(shù)是滿足下列條件的函數(shù)f：n給定x，計(jì)算y=f(x)是容易的；n給定y, 計(jì)算x使x=

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

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

5、m mm mmm、若，則1, ( )?nn編輯ppt歐拉函數(shù)11)12)(1)kkppppppp、 為素?cái)?shù)， (、 為素?cái)?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為素?cái)?shù)，()( ) ( )(1)(1)pqpqpq編輯pptnRSA密碼體制的描述n密鑰

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

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