关于区间上离散对数问题的改进算法

发布时间：2017-06-10 17:09

  本文关键词：关于区间上离散对数问题的改进算法，由笔耕文化传播整理发布。

【摘要】：在群G上区间大小为N的离散对数问题为:给定g,h∈G以及大整数N,找到整数n(0≤n≤N),使得h=g~n,人们对于该问题的求解主要是对Pollard's kangaroos method的改进,尝试通过减少跳跃次数来优化算法,目前解决这一问题的最优低存储算法是Van Oorschot和Wiener版本的Pollard's kangaroos method,其平均情况下的时间代价是(2+0(1))√N次群运算.文中对解决这一问题的经典Pollard's kangaroos method进行改进得到新的求解算法.新算法是通过利用多次小整数乘法代替一次完整的大整数乘法来减少kangaroos每次跳跃的时间代价实现算法效率的提高.进一步,文中通过增加kangaroos的数量使得算法在跳跃次数和每次跳跃的时间代价两方面都得到改进,从而得到区间上离散对数问题的更有效的求解算法.
【作者单位】： 中国科学院信息工程研究所;中国科学院数据与通信保护研究教育中心;
【关键词】： 离散对数(DLP) Pollard’s kangaroos method Pollard’s rho method 区间 时间代价
【基金】：国家自然科学基金项目(61272039)
【分类号】：TN918.1
【正文快照】： 1引言经典离散对数问题(DLP)是指:给定群元素g,h,计算n使得.nh?g这一问题在现代密码学和数论中都扮演着重要的角色,许多密码系统和协议(如Diffie-Hellman密钥交换协议、ELGamal加密系统、ELGamal数字签名系统、DSA以及基于椭圆曲线的加密和签名系统)的安全性都是基于离散对数

【相似文献】

中国期刊全文数据库 前10条

1 张海波;王小非;夏学知;黄友澎;;一个改进的离散对数问题攻击算法[J];计算机应用;2007年04期

2 汤鹏志;何涛;李彪;;离散对数问题攻击算法的改进#[J];计算机技术与发展;2013年05期

3 戴宗铎;杨君辉;;求离散对数问题的新进展[J];通信保密;1985年Z1期

4 王洋;;椭圆离散对数问题的攻击算法分析[J];硅谷;2011年02期

5 Leonard Adleman;淮滨;;离散对数问题的次指数算法及其在密码中的应用(摘要)[J];通信保密;1984年01期

6 付向群;鲍皖苏;史建红;李发达;;基于多离散对数问题的公钥密码[J];电子与信息学报;2014年06期

7 欧海文,叶顶锋,杨君辉,戴宗铎;关于同时基于因子分解与离散对数问题的签名体制[J];通信学报;2004年10期

8 曹素珍;王彩芬;;基于离散对数问题的可截取签名方案[J];计算机工程;2013年04期

9 王之仓;俞惠芳;;基于离散对数问题的自认证签密方案[J];计算机应用与软件;2010年10期

10 杜伟章,陈克非;基于离散对数问题构造弱盲签名方案[J];计算机工程与应用;2003年16期

中国硕士学位论文全文数据库 前5条

1 何锐明;变形Diffie-Hellman问题的等价性[D];华南理工大学;2014年

2 赵书让;有限域上新的离散对数问题[D];山东大学;2014年

3 张学桥;GF（p）上离散对数问题GNFS算法实现[D];山东大学;2009年

4 邹舒婷;DNA计算在基于离散对数问题的公钥密码分析学中的应用研究[D];湖南大学;2008年

5 祝孔儒;基于椭圆曲线离散对数的安全的不经意传输协议[D];云南大学;2012年

  本文关键词：关于区间上离散对数问题的改进算法，，由笔耕文化传播整理发布。

本文编号：439238