第九講離散對數(shù)

第九講離散對數(shù)第1頁，課件共43頁，創(chuàng)作于2023年2月在RSA密碼算法中，我們看到如何利用分解的困難性產(chǎn)生有用的密碼系統(tǒng)。另一個數(shù)論問題，稱為離散對數(shù)問題，也有相似的應(yīng)用。Diffie認(rèn)為離散對數(shù)問題來源于Gill的提示。離散對數(shù)問題是公鑰密碼學(xué)的又一個重要公開困難問題。第2頁，課件共43頁，創(chuàng)作于2023年2月本講提要離散對數(shù)計算離散對數(shù)ElGamal公鑰加密算法比特承諾第3頁，課件共43頁，創(chuàng)作于2023年2月1離散對數(shù)第4頁，課件共43頁，創(chuàng)作于2023年2月第5頁，課件共43頁，創(chuàng)作于2023年2月第6頁，課件共43頁，創(chuàng)作于2023年2月2計算離散對數(shù)2.1窮舉搜索第7頁，課件共43頁，創(chuàng)作于2023年2月2.2小步大步算法第8頁，課件共43頁，創(chuàng)作于2023年2月2.2小步大步算法(續(xù))第9頁，課件共43頁，創(chuàng)作于2023年2月2.2小步大步算法(續(xù))第10頁，課件共43頁，創(chuàng)作于2023年2月2.2小步大步算法(續(xù))第11頁，課件共43頁，創(chuàng)作于2023年2月2.3Pollard的Rho算法第12頁，課件共43頁，創(chuàng)作于2023年2月2.3Pollard的Rho算法(續(xù))第13頁，課件共43頁，創(chuàng)作于2023年2月2.3Pollard的Rho算法(續(xù))第14頁，課件共43頁，創(chuàng)作于2023年2月2.3Pollard的Rho算法(續(xù))第15頁，課件共43頁，創(chuàng)作于2023年2月2.3Pollard的Rho算法(續(xù))第16頁，課件共43頁，創(chuàng)作于2023年2月2.3Pollard的Rho算法(續(xù))第17頁，課件共43頁，創(chuàng)作于2023年2月2.4Pohlig-Hellman算法第18頁，課件共43頁，創(chuàng)作于2023年2月2.4Pohlig-Hellman算法(續(xù))第19頁，課件共43頁，創(chuàng)作于2023年2月2.4Pohlig-Hellman算法(續(xù))第20頁，課件共43頁，創(chuàng)作于2023年2月2.4Pohlig-Hellman算法(續(xù))第21頁，課件共43頁，創(chuàng)作于2023年2月2.4Pohlig-Hellman算法(續(xù))第22頁，課件共43頁，創(chuàng)作于2023年2月2.5指數(shù)積分算法

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