密鑰管理及其他公鑰體制.ppt

2012年3月18日,計算機(jī)安全技術(shù)與實(shí)踐 密鑰管理和其他公鑰密碼體制,10.1 Diffie-Hellman密鑰交換,離散對數(shù)問題 ygx mod p，其中g(shù)是生成元 求x的困難性 目前沒有有效的方法 實(shí)際使用時常用Zp*和ECC上的點(diǎn)加法群 Pohlig-Hellman algorithm 如果p-1是小素數(shù)的乘積，則易求 因此，p-1應(yīng)含有大素因子,Diffie-Hellman密鑰交換協(xié)議,DH76，Diffie-Hellman 步驟 選取大素數(shù)q和它的一個生成元g，這些參數(shù)公開 A選擇隨機(jī)數(shù)Xa，B選擇隨機(jī)數(shù)Xb A計算YagXa mod q，B計算YbgXb mod q 交換Ya，Yb A計算KYbXa mod q，B計算KYaXb mod q 事實(shí)上，KK,證明、分析和例子,證明KK KYbXa mod q KYaXb mod q (gXb)Xa mod q (gXa)Xb mod q g(XbXa) mod q g(XaXb) mod q 舉例 q97，g5 A選Xa36，B選Xb58，則 Ya5369750，Yb5589744 交換50，44 A算K44369775，B算K50589775 分析（別人怎么計算K?） 別人看到了Ya和Yb，但需要計算Xa或Xb，即要算離散對數(shù) YagXa mod q，或YbgXb mod q,中間人攻擊,交換Y的過程中，Y有可能被替換假冒，而且不能發(fā)現(xiàn) 形式上，可以理解為一個中間人在跟雙方同時通信，當(dāng)然通信內(nèi)容在中間人那里是可見的 * 一個現(xiàn)實(shí)的例子就是：可以同時開兩盤QQx棋，一個后手，一個先手，,Man-in-the-middle,A E B Xa Xb Xa Xb Ya Yb Ya Yb K=YbXa K=YaXb,相關(guān)結(jié)論,maurer94towards Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms /maurer94towards.html 結(jié)論 破譯D-H密鑰協(xié)商協(xié)議等價于計算離散對數(shù) RSA算法的安全性是否等價于大數(shù)的因子分解？,10.1a PKCS#3,PKCS#3 Diffie-Hellman Key-Agreement Standard 進(jìn)一步參閱 pkcs#3,10.2 ElGamal密碼體制,準(zhǔn)備 素數(shù)p，Zp*中本原元g，公開參數(shù) 私鑰a，公鑰b=ga mod p 加密 對明文1=m=p-1，選隨機(jī)數(shù)k 密文(c1, c2) c1=gk mod p, c2=mbk mod p 解密 mc2 (c1a)-1mbk (gk)a)-1 m(ga)k (g-ka) m mod p,ElGamal etc,基于離散對數(shù)難題 缺點(diǎn) 需要隨機(jī)數(shù) 密文長度加倍 ElGamal可以遷移到ECDLP上 ElGamal簽名和DSS,10.3 橢圓曲線,背景 RSA中用到了因子分解的困難性，而為了增加困難得加大數(shù)的位數(shù)，從而導(dǎo)致計算速度變慢。 ECC可以用較小的密鑰長度達(dá)到較高的計算難度 Elliptic Curve y2axybyx3cx2dxe 其中a、b、c、d、e是滿足某個簡單條件的實(shí)數(shù) 另有O點(diǎn)被定義為無窮點(diǎn)/零點(diǎn) 點(diǎn)加法PQR定義為 過P、Q和橢圓曲線相交的第三點(diǎn)的X軸對稱點(diǎn)R,EC：PQR,素域上的EC,在有限域Zp上的簡化EC y2x3axb mod p 其中4a327b2 mod p 0 （這是一個離散點(diǎn)的集合） 舉例 y2x318x15 mod 23 y2x317x15 mod 23,EC (1),EC (2),EC上的離散對數(shù)問題（ECDLP）,QkP中的k計算也是極其困難的 kP表示k個P相加：P + P + + P 在DH密鑰交換中 使用了ygx mod p中x的計算困難性 同樣在ECC中 將使用QkP中計算k的困難性 有兩個應(yīng)用 密鑰交換 加密解密,10.4 橢圓曲線密碼學(xué)ECC,ECC利用EC上的離散對數(shù)難題(ECDLP)，這和利用Zp*上的離散對數(shù)難題(DLP)是一樣的方法。 在一般數(shù)域上的離散對數(shù)問題（以及大數(shù)分解問題）存在亞指數(shù)級時間復(fù)雜度求解算法，而ECDLP只有純指數(shù)算法。,使用EC的密鑰交換（D-H）,步驟 y2x3axb mod p 選擇素數(shù)p(得約160比特)和參數(shù)a、b 選擇一個生成點(diǎn)G(x1，y1) p、a、b和點(diǎn)G是公開的 A：選取秘密的數(shù)Na，計算PaNaG B：選取秘密的數(shù)Nb，計算PbNbG 交換Pa，Pb A：計算KNaPbNaNbG B：計算KNbPaNbNaG 分析 攻擊者得求Na和Nb，就是P?G中的?,用EC的加解密,準(zhǔn)備 曲線參數(shù)p、a、b、G，y2x3axb mod p A有自己的私鑰Na，并產(chǎn)生公鑰PaNaG B有自己的私鑰Nb，并產(chǎn)生公鑰PbNbG 加密 （A要給B發(fā)送消息） 對明文m的編碼點(diǎn)Pm，選擇隨機(jī)數(shù)k，密文 CC1，C2 kG，PmkPb 解密： 編碼點(diǎn)PmC2NbC1，因?yàn)?(PmkPb)NbkG PmkNbGNbkG Pm,用EC的加解密,原理 先是通過kPb掩蓋Pm (即m)，又通過kG掩蓋k 知道陷門Nb則可以輕松