本文關(guān)鍵詞：關(guān)于區(qū)間上離散對(duì)數(shù)問題的改進(jìn)算法，由筆耕文化傳播整理發(fā)布。

【摘要】：在群G上區(qū)間大小為N的離散對(duì)數(shù)問題為:給定g,h∈G以及大整數(shù)N,找到整數(shù)n(0≤n≤N),使得h=g~n,人們對(duì)于該問題的求解主要是對(duì)Pollard's kangaroos method的改進(jìn),嘗試通過減少跳躍次數(shù)來優(yōu)化算法,目前解決這一問題的最優(yōu)低存儲(chǔ)算法是Van Oorschot和Wiener版本的Pollard's kangaroos method,其平均情況下的時(shí)間代價(jià)是(2+0(1))√N(yùn)次群運(yùn)算.文中對(duì)解決這一問題的經(jīng)典Pollard's kangaroos method進(jìn)行改進(jìn)得到新的求解算法.新算法是通過利用多次小整數(shù)乘法代替一次完整的大整數(shù)乘法來減少kangaroos每次跳躍的時(shí)間代價(jià)實(shí)現(xiàn)算法效率的提高.進(jìn)一步,文中通過增加kangaroos的數(shù)量使得算法在跳躍次數(shù)和每次跳躍的時(shí)間代價(jià)兩方面都得到改進(jìn),從而得到區(qū)間上離散對(duì)數(shù)問題的更有效的求解算法.
【作者單位】： 中國科學(xué)院信息工程研究所;中國科學(xué)院數(shù)據(jù)與通信保護(hù)研究教育中心;
【關(guān)鍵詞】： 離散對(duì)數(shù)(DLP) Pollard’s kangaroos method Pollard’s rho method 區(qū)間 時(shí)間代價(jià)
【基金】：國家自然科學(xué)基金項(xiàng)目(61272039)
【分類號(hào)】：TN918.1
【正文快照】： 1引言經(jīng)典離散對(duì)數(shù)問題(DLP)是指:給定群元素g,h,計(jì)算n使得.nh?g這一問題在現(xiàn)代密碼學(xué)和數(shù)論中都扮演著重要的角色,許多密碼系統(tǒng)和協(xié)議(如Diffie-Hellman密鑰交換協(xié)議、ELGamal加密系統(tǒng)、ELGamal數(shù)字簽名系統(tǒng)、DSA以及基于橢圓曲線的加密和簽名系統(tǒng))的安全性都是基于離散對(duì)數(shù)

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 張海波;王小非;夏學(xué)知;黃友澎;;一個(gè)改進(jìn)的離散對(duì)數(shù)問題攻擊算法[J];計(jì)算機(jī)應(yīng)用;2007年04期

2 湯鵬志;何濤;李彪;;離散對(duì)數(shù)問題攻擊算法的改進(jìn)#[J];計(jì)算機(jī)技術(shù)與發(fā)展;2013年05期

3 戴宗鐸;楊君輝;;求離散對(duì)數(shù)問題的新進(jìn)展[J];通信保密;1985年Z1期

4 王洋;;橢圓離散對(duì)數(shù)問題的攻擊算法分析[J];硅谷;2011年02期

5 Leonard Adleman;淮濱;;離散對(duì)數(shù)問題的次指數(shù)算法及其在密碼中的應(yīng)用(摘要)[J];通信保密;1984年01期

6 付向群;鮑皖蘇;史建紅;李發(fā)達(dá);;基于多離散對(duì)數(shù)問題的公鑰密碼[J];電子與信息學(xué)報(bào);2014年06期

7 歐海文,葉頂鋒,楊君輝,戴宗鐸;關(guān)于同時(shí)基于因子分解與離散對(duì)數(shù)問題的簽名體制[J];通信學(xué)報(bào);2004年10期

8 曹素珍;王彩芬;;基于離散對(duì)數(shù)問題的可截取簽名方案[J];計(jì)算機(jī)工程;2013年04期

9 王之倉;俞惠芳;;基于離散對(duì)數(shù)問題的自認(rèn)證簽密方案[J];計(jì)算機(jī)應(yīng)用與軟件;2010年10期

10 杜偉章,陳克非;基于離散對(duì)數(shù)問題構(gòu)造弱盲簽名方案[J];計(jì)算機(jī)工程與應(yīng)用;2003年16期

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前5條

1 何銳明;變形Diffie-Hellman問題的等價(jià)性[D];華南理工大學(xué);2014年

2 趙書讓;有限域上新的離散對(duì)數(shù)問題[D];山東大學(xué);2014年

3 張學(xué)橋;GF（p）上離散對(duì)數(shù)問題GNFS算法實(shí)現(xiàn)[D];山東大學(xué);2009年

4 鄒舒婷;DNA計(jì)算在基于離散對(duì)數(shù)問題的公鑰密碼分析學(xué)中的應(yīng)用研究[D];湖南大學(xué);2008年

5 �？兹�;基于橢圓曲線離散對(duì)數(shù)的安全的不經(jīng)意傳輸協(xié)議[D];云南大學(xué);2012年

  本文關(guān)鍵詞：關(guān)于區(qū)間上離散對(duì)數(shù)問題的改進(jìn)算法，，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：439238