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

1、第九講 離散對(duì)數(shù),在RSA密碼算法中，我們看到如何利用分解的困難性產(chǎn)生有用的密碼系統(tǒng)。另一個(gè)數(shù)論問(wèn)題，稱為離散對(duì)數(shù)問(wèn)題，也有相似的應(yīng)用。Diffie認(rèn)為離散對(duì)數(shù)問(wèn)題來(lái)源于Gill的提示。離散對(duì)數(shù)問(wèn)題是公鑰密碼學(xué)的又一個(gè)重要公開(kāi)困難問(wèn)題。,本講提要,離散對(duì)數(shù) 計(jì)算離散對(duì)數(shù) ElGamal公鑰加密算法 比特承諾,1 離散對(duì)數(shù),2 計(jì)算離散對(duì)數(shù),2.1 窮舉搜索,2.2 小步大步算法,2.2 小步大步算法(續(xù)),2.2 小步大步算法(續(xù)

2、),2.2 小步大步算法(續(xù)),2.3 Pollard的Rho算法,2.3 Pollard的Rho算法 (續(xù)),2.3 Pollard的Rho算法(續(xù)),2.3 Pollard的Rho算法(續(xù)),2.3 Pollard的Rho算法(續(xù)),2.3 Pollard的Rho算法(續(xù)),2.4 Pohlig-Hellman算法,2.4 Pohlig-Hellman算法(續(xù)),2.4 Pohlig-Hellman算法(續(xù)),2.4 Pohlig-

3、Hellman算法(續(xù)),2.4 Pohlig-Hellman算法(續(xù)),2.5 指數(shù)積分算法,2.5 指數(shù)積分算法(續(xù)),2.5 指數(shù)積分算法(續(xù)),2.5 指數(shù)積分算法(續(xù)),2.5 指數(shù)積分算法(續(xù)),2.5 指數(shù)積分算法(續(xù)),3 ElGamal公鑰加密算法,ElGamal公鑰加密方案依賴于離散對(duì)數(shù)問(wèn)題和Diffie-Hellman問(wèn)題的困難性?；镜腅lGamal公鑰加密方案是ElGamal于1985年提出。,3.1 算法描述

4、,3.1 算法描述(續(xù)),3.1 算法描述(續(xù)),3.2 例子,3.3 ElGamal加密算法效率,3.4 ElGamal加密算法安全,3.4 ElGamal加密算法安全(續(xù)),4 比特承諾,4.1 背景 Alice聲稱發(fā)現(xiàn)了一種方法可以成功預(yù)測(cè)球賽的結(jié)果。她想把這種方法買給Bob。Bob要求她把周末的球賽結(jié)果預(yù)測(cè)一下以證明方法有效。Alice說(shuō) “沒(méi)門，你可能利用我的預(yù)測(cè)結(jié)果去買彩票牟利，并且不與我分成。為什么不讓我給你預(yù)測(cè)上周

5、比賽的結(jié)果呢？”,4.2 比特承諾的要求 Alice能發(fā)送一個(gè)比特b給Bob，這個(gè)比特可以是0或1。并需要滿足 (1) Bob在沒(méi)有Alice的幫助下不能決定這一個(gè)比特的取值。 (2) Alice一旦發(fā)送了這個(gè)比特，就不能改變?nèi)≈登闆r。這樣，對(duì)每場(chǎng)球賽，Alice可以發(fā)送b=1，表示她預(yù)測(cè)的隊(duì)獲勝；發(fā)送 b=0，表示她預(yù)測(cè)的隊(duì)失敗。在比賽結(jié)束以后，Alice向Bob揭示這一比特的取值，證明自己的預(yù)測(cè)。,4.3 計(jì)算模