第九講離散對(duì)數(shù)

第九講離散對(duì)數(shù)第一頁，共四十三頁，編輯于2023年，星期四在RSA密碼算法中，我們看到如何利用分解的困難性產(chǎn)生有用的密碼系統(tǒng)。另一個(gè)數(shù)論問題，稱為離散對(duì)數(shù)問題，也有相似的應(yīng)用。Diffie認(rèn)為離散對(duì)數(shù)問題來源于Gill的提示。離散對(duì)數(shù)問題是公鑰密碼學(xué)的又一個(gè)重要公開困難問題。第二頁，共四十三頁，編輯于2023年，星期四本講提要離散對(duì)數(shù)計(jì)算離散對(duì)數(shù)ElGamal公鑰加密算法比特承諾第三頁，共四十三頁，編輯于2023年，星期四1離散對(duì)數(shù)第四頁，共四十三頁，編輯于2023年，星期四第五頁，共四十三頁，編輯于2023年，星期四第六頁，共四十三頁，編輯于2023年，星期四2計(jì)算離散對(duì)數(shù)2.1窮舉搜索第七頁，共四十三頁，編輯于2023年，星期四2.2小步大步算法第八頁，共四十三頁，編輯于2023年，星期四2.2小步大步算法(續(xù))第九頁，共四十三頁，編輯于2023年，星期四2.2小步大步算法(續(xù))第十頁，共四十三頁，編輯于2023年，星期四2.2小步大步算法(續(xù))第十一頁，共四十三頁，編輯于2023年，星期四2.3Pollard的Rho算法第十二頁，共四十三頁，編輯于2023年，星期四2.3Pollard的Rho算法(續(xù))第十三頁，共四十三頁，編輯于2023年，星期四2.3Pollard的Rho算法(續(xù))第十四頁，共四十三頁，編輯于2023年，星期四2.3Pollard的Rho算法(續(xù))第十五頁，共四十三頁，編輯于2023年，星期四2.3Pollard的Rho算法(續(xù))第十六頁，共四十三頁，編輯于2023年，星期四2.3Pollard的Rho算法(續(xù))第十七頁，共四十三頁，編輯于2023年，星期四2.4Pohlig-Hellman算法第十八頁，共四十三頁，編輯于2023年，星期四2.4Pohlig-Hellman算法(續(xù))第十九頁，共四十三頁，編輯于2023年，星期四2.4Pohlig-Hellman算法(續(xù))第二十頁，共四十三頁，編輯于2023年，星期四2.4Pohlig-Hellman算法(續(xù))第二十一頁，共四十三頁，編輯于2023年，星期四2.4Pohlig-Hellman算法(續(xù))第二十二頁，共四十三頁，編輯于2023年，星期四2.5指數(shù)積分算法

第二十三頁，共四十三頁，編輯于2023年，星期四2.5指數(shù)積分算法(續(xù))第二十四頁，共四十三頁，編輯于2023年，星期四2.5指數(shù)積分算法(續(xù))第二十五頁，共四十三頁，編輯于2023年，星期四2.5指數(shù)積分算法(續(xù))第二十六頁，共四十三頁，編輯于2023年，星期四2.5指數(shù)積分算法(續(xù))第二十七頁，共四十三頁，編輯于2023年，星期四2.5指數(shù)積分算法(續(xù))第二十八頁，共四十三頁，編輯于2023年，星期四3ElGamal公鑰加密算法ElGamal公鑰加密方案依賴于離散對(duì)數(shù)問題和Diffie-Hellman問題的困難性?；镜腅lGamal公鑰加密方案是ElGamal于1985年提出。第二十九頁，共四十三頁，編輯于2023年，星期四3.1算法描述第三十頁，共四十三頁，編輯于2023年，星期四3.1算法描述(續(xù))第三十一頁，共四十三頁，編輯于2023年，星期四3.1算法描述(續(xù))第三十二頁，共四十三頁，編輯于2023年，星期四3.2例子第三十三頁，共四十三頁，編輯于2023年，星期四3.3ElGamal加密算法效率第三十四頁，共四十三頁，編輯于2023年，星期四3.4ElGamal加密算法安全第三十五頁，共四十三頁，編輯于2023年，星期四3.4ElGamal加密算法安全(續(xù))第三十六頁，共四十三頁，編輯于2023年，星期四4比特承諾4.1背景(1)Alice聲稱發(fā)現(xiàn)了一種方法可以成功預(yù)測球賽的結(jié)果。她想把這種方法買給Bob。Bob要求她把周末的球賽結(jié)果預(yù)測一下以證明方法有效。Alice說“沒門，你可能利用我的預(yù)測結(jié)果去買彩票牟利，并且不與我分成。為什么不讓我給你預(yù)測上周比賽的結(jié)果呢？”第三十七頁，共四十三頁，編輯于2023年，星期四4.2比特承諾的要求Alice能發(fā)送一個(gè)比特b給Bob，這個(gè)比特可以是0或1。并需要滿足(1)Bob在沒有Alice的幫助下不能決定這一個(gè)比特的取值。(2)Alice一旦發(fā)送了這個(gè)比特，就不能改變?nèi)≈登闆r。這樣，對(duì)每場球賽，Alice可以發(fā)送b=1，表示她預(yù)測的隊(duì)獲勝；發(fā)送b=0，表示她預(yù)測的隊(duì)失敗。在比賽結(jié)束以后，Alice向Bob揭示這一比特的取值，證明自己的預(yù)測。第三十八頁，共四十三頁，編輯于2023年，星期四4.3計(jì)算模4的離散對(duì)數(shù)第三十九頁，共四十三頁，編輯于2023年，星期四4.3計(jì)算模4的離散對(duì)數(shù)(續(xù))第四十頁，共四十三頁，編輯于2023年，