导读:本文包含了椭圆曲线离散对数论文开题报告文献综述、选题提纲参考文献及外文文献翻译,主要关键词:对数,椭圆,曲线,算法,亏格,同态,多项式。
椭圆曲线离散对数论文文献综述
朱玉清,庄金成,于伟,林东岱[1](2018)在《特征p椭圆曲线上p-群的离散对数问题》一文中研究指出设E是定义在有限域F_q上的一条椭圆曲线.当曲线的Frobenius迹为1时,即#E(F_q)=q,我们称其为异常曲线.为了设计安全的椭圆曲线密码方案,我们通常要求曲线的群阶含有一个大素因子.而素域上的异常曲线恰好满足这个要求,其群阶为素数,等于有限域的大小.然而研究学者发现这样看似安全的椭圆曲线其实并不安全.Satoh-Araki,Semaev和Smart分别提出了求解异常曲线上离散对数问题的有效算法.其中Satoh-Araki和Smart提出的算法本质相同,均为提升法.该方法通过把素域F_p上的椭圆曲线提升到p-adic域Q_p上,然后利用易于计算的形式对数映射求出离散对数.然而Satoh-Araki和Smart只给出了素域上椭圆曲线的提升法,并没有提及当基域是非素域时的情形.本文将推广该方法,使其可以求解特征p有限域上椭圆曲线p-群的离散对数问题.该方法和Semaev的方法具有相同的复杂度,并且具有简洁和直观的优势.进一步,我们将讨论Q_p及其代数扩域上椭圆曲线离散对数问题,并给出它们与有限域上椭圆曲线离散对数问题的关系.(本文来源于《密码学报》期刊2018年04期)
翁江,扈瑜龙,马传贵[2](2018)在《F_(q~k)上阶为q~k-1的椭圆曲线离散对数问题研究》一文中研究指出基于椭圆曲线离散对数问题(elliptic curve discrete logarithm problem,ECDLP)求解的困难性,提出基于最优对(optimal-pairing)将椭圆曲线E(F_(p~l))上的离散对数问题(discrete logarithm problem,DLP)规约到扩域乘法群F*_(p~(kl))上的离散对数问题,新算法与MOV和FR规约算法相比速度更快,并且针对具有大扩张次数有限域的乘法群,改进Pollard-ρ算法迭代函数的选取,通过构造迭代压缩函数使其象集小于原象集,使新算法比原始的迭代函数更快地找到碰撞。在有限域Fpkl的乘法群上,新算法在原始算法的基础上速度提高了大约3p-3/5p-3~(2kl)~(1/2)倍。(本文来源于《信息工程大学学报》期刊2018年01期)
颜世骏[3](2015)在《Koblitz椭圆曲线离散对数问题的计算》一文中研究指出椭圆曲线密码体制(Elliptic Curve Cryptosystem,简称ECC)是当前最流行实用的公钥密码体制之一,由于其构造的独特性,达到一定安全需求所需的密钥长度很短,并且实现效率很高。椭圆曲线离散对数问题(ECDLP)是ECC的安全核心,求解ECDLP问题最快的算法是指数时间的,这意味着由此设计的加密与签名方案更加的安全。主要有两类计算ECDLP问题的算法:一是与所选椭圆曲线及其有限域无关的通用算法,二是特定椭圆曲线或有限域的特定算法。Pollard rho及其并行算法为计算ECDLP的一种非常有效的通用算法。1997年,加拿大公司Certicom为了鼓励对ECC的研究以及评估其安全性,开展了Certicom ECC挑战项目。对计算ECDLP问题的研究,一方面能够让人们更好地理解其工业标准及ECDLP问题的困难性,另一方面鼓励着人们对于ECC的安全性进行更深入的研究。Koblitz曲线是定义在2上形如2+=3+1或2+=3+2+1的一种特殊的椭圆曲线。在Koblitz曲线上,存在一种特殊的映射叫做Frobenius自同态。由于在Koblitz曲线上可以进行快速的群运算,同时快速的Frobenius自同态和半分运算可以对标量乘运算的速度有着很大的提高,因此Koblitz曲线受到了欢迎并在实际的工业标准中有着广泛的应用。例如,在NIST推荐使用的椭圆曲线中就有5条Koblitz曲线。本文研究的是这种特殊的椭圆曲线Koblitz曲线的安全问题,即用Pollard rho算法在Koblitz曲线上求解ECDLP问题。本文利用Frobenius自同态和半分运算,在Koblitz曲线上分别用多项式基和正规基进行了软件上的仿真实现,成功求解出了41和83比特上的ECDLP问题。本文首次在Koblitz曲线上对多项式基和正规基软件上的实现进行了理论和实践上的比较,并得出了结论。虽然正规基多用于硬件实现,但在Koblitz曲线上与Frobenius自同态和半分运算相结合的前提下,正规基在软件上的实现效率仍高于多项式基。(本文来源于《中山大学》期刊2015-05-21)
王旻南[4](2015)在《椭圆曲线离散对数问题的相关算法分析》一文中研究指出本文主要分析了椭圆曲线离散对数问题的相关算法。首先在第一章,我介绍了相关问题的研究背景和现状。在第二章则研究了常用的3种求解算法:大步小步法、Pollard方法和指标计算方法。在第叁章,则专门对GHS方法进行了分析,这种方法主要用于特征为2的有限域上椭圆曲线离散对数问题,它是把椭圆曲线上的离散对数问题转化到子域上高亏格的超椭圆曲线上的离散对数问题。Gaudry,Hass和Smart等人给出了一个判断椭圆曲线是否可用GHS算法的条件。在本文中,我证明了如何将此条件改进为充要条件,并计算了满足新条件却不满足原有条件的椭圆曲线数量,扩充了GHS算法适用范围。(本文来源于《南京大学》期刊2015-05-01)
田松,李宝,王鲲鹏[5](2015)在《椭圆曲线离散对数问题的研究进展》一文中研究指出自从1985年椭圆曲线密码被提出后,其理论和应用研究都受到了广泛关注.椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题的困难性.由于计算一般椭圆曲线中离散对数的算法都是指数时间的,椭圆曲线密码体制能够以更小的密钥尺寸来满足与其他公钥密码体制相同的安全性要求,从而特别适用于计算和存储能力受限的领域,许多标准化组织也相继提出了椭圆曲线上的公钥加密、密钥协商、数字签名协议的标准.利用Schoof's算法或复乘方法,人们可以很容易构造出密码学所需的椭圆曲线.通常推荐使用的椭圆曲线都定义在特征为2的有限域或素域上.为了加速有限域的运算,部分学者提议使用非素域有限域.然而对于非素域有限域上椭圆曲线中离散对数,基于求和多项式的指标计算法和Weil下降方法有可能比Pollard's Rho等一般性算法快.因此研究这些算法对椭圆曲线离散对数问题困难性的削弱程度以及相应的弱曲线特点对椭圆曲线密码学的安全应用有重大意义.本文将对解椭圆曲线离散对数问题的方法和研究进展做简单综述.(本文来源于《密码学报》期刊2015年02期)
杜育松,张方国[6](2014)在《椭圆曲线离散对数的不动点》一文中研究指出椭圆曲线离散对数问题在密码领域有着重要的应用.本文中我们将模素数p的离散对数的不动点问题推广到有限域上椭圆曲线离散对数的不动点问题.对于有限域p?上的任意椭圆曲线()pE?,证明了当p足够大时,以大概率存在一点(,)()pQ?x y?E?使得logPQ?x,即Q?x?P,其中logP被看成是以点()pP?E?为底的离散对数,且点P满足ord(P)?n,而x被看成是在区间[0,n?1][0,p?1]?上的整数.(本文来源于《密码学报》期刊2014年01期)
邵飞,孟博[7](2014)在《一种基于椭圆曲线离散对数问题的非交互式可否认认证协议》一文中研究指出可否认认证协议作为一种安全协议,被用在如电子选举等许多特殊领域中,由于交互式可否认认证协议的多次交互带来的安全隐患,非交互式可否认认证协议引起了更多的重视,提出一种基于椭圆曲线离散对数问题的非交互式可否认认证协议,椭圆曲线离散对数问题的难解性提高了密钥的保密性,保证了非交互式协议的安全,构建的非交互式可否认协议可以抵抗重放攻击、伪造攻击、冒充攻击和已知会话密钥攻击,基于形式化方法对该协议的可否认性进行了证明,最后通过与其他协议的比较,说明了该协议的安全性和高效.(本文来源于《小型微型计算机系统》期刊2014年01期)
曹媛[8](2013)在《加速椭圆曲线上离散对数问题的Pollard's Rho算法》一文中研究指出椭圆曲线密码学的许多形式有稍微的不同,但所有的形式都依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上,对应有限域上椭圆曲线的群。研究表明,椭圆曲线密码是目前唯一无法用亚指数算法破解的公钥密码。离散对数公钥加密算法是目前最为热门的公钥加密算法,其安全性要远远高于基于大数分解的RSA算法。通过几代密码学家几十年来的不懈努力,在求解椭圆曲线离散对数问题上取得了不少成绩,诞生了许多经典的求解算法,如Shanks的小步大步算法(BSGS)[1]、Pollard'sρ算法[2]、Pohlig-Hellman算法、Index Calculus算法等,以及针对特殊类型椭圆曲线的MOV算法[3]、SSAS算法等。本文将着重对Pollard's ρ算法进行分析。Pollard's ρ算法基于生日悖论,实为BSGS算法的一种变形。具体实施起来即在群元素中寻找匹配或者碰撞,并希望能从这种碰撞中恢复出关于起始点的一些信息。其运算时间与BSGS算法相同,但不需要存储空间。后来的密码学家在此基础上提出了各种对ρ算法的改进和优化的方法。其中韩国密码学家Jung Hee Cheon,Jin Homg和Minkyu Kim[4]提出了对求解有限域上的离散对数的ρ算法进行改进的方法。对G=<9>中的元素仍如原始ρ算法中一样运用迭代函数生成随机序列,并保证它们是指数可追踪的。事先选定某一性质作为对点进行筛选的条件,将满足这一性质的点定义为特征点。Jung Hee Cheon等人结合指标函数s:G→{0,1},其将G中1/r的元素映到0,其余映到1,选取一个小的正整数δ,将满足下式s(gi-δ+1)=…=s(gi-1)=s(gi)=0中的最后一点gi定义为他们所选取的特征点。由于照此方法定义的特征点有聚集出现的趋势,因此对连续的特征点组,只选取一点存储即可。通过计算,可求得连续的特征点组之间的平均距离(即平均迭代次数)为r/(r-1)(rδ-1),也就是平均作r/(r-1)(rδ-1)次迭代运算可以求得一个特征点。特征点定义好后,开始引入标记追踪法进行迭代运算。在迭代开始前,假定我们已有指标函数s:G→S={0,1….,r-1}和一个预计算表Ml,其中M={mi}i∈s。在迭代过程中,不需要如之前一样计算每一次gi+1=gimsi的值,通过引入一个辅助的指标函数s:G×Ml→S,便可很方便的求得gi+1。之后再结合特征点的定义,选取迭代过程中产生的特征点并存储,直至找到碰撞为止。由于相对于迭代计算过程,预计算表Ml的计算时间可以忽略,此方法比原始的ρ算法在求解时间上要快一些。下面我们所作的是,将上述ρ算法的改进方法应用到求解椭圆曲线离散对数问题上。椭圆曲线上离散对数的ρ算法与有限域上的ρ算法类似,但ECDLP比DLP要困难的多。结合前人的思想,我们可以考虑,将椭圆曲线上的离散对数问题转化到有限域上,再运用Jung Hee Cheon等人的改进方法来进行求解。本文所选取的方法是由Menezes、Okamoto和、anstone于1993年提出的MOV算法,定义双线性对Weil对利用双线性对的性质来完成MOV算法的转化。其核心思想便是将ECDLP转化为某个有限域的乘法群上的DLP,实质便是将Fq映到其扩域Fqk。而n|qk-1是利用MOV算法将DLP转化到Fqk上的必要条件。该方法在实际应用时,并不是对所有的椭圆曲线均有效,而是受有限域的扩张次数k的限制。若所取的k值太大时,并没有降低离散对数问题求解的困难度,该算法是无法有效进行运算的。因此我们要选取小一些的k值。目前通过运算已知k≤6时,MOV算法对一类特殊的椭圆曲线离散对数求解是十分有效的,即超奇异椭圆曲线,这个过程是亚指数时间算法的。应用MOV算法将ECDLP转化为DLP,就可以利用上述的ρ算法的改进方法来进行离散对数的求解。(本文来源于《山东大学》期刊2013-05-01)
严爽[9](2013)在《有限域上超椭圆曲线离散对数问题的错误攻击问题》一文中研究指出椭圆曲线Weierstrass方程存在一个系数与椭圆曲线上有理点群的标量乘法无关[4],从而出现了一系列相应的攻击方法。Biehl等在[4]中提出了对于椭圆曲线密码体制的错误攻击法。Ciet和Joye[7]基于此在确定错误植入位置的情况下给出了一种恢复密钥的方法。Karabina和Ustaoglu[8]说明了如果公钥选择不恰当,那么此类无效曲线攻击可以应用在基于亏格为2的超越椭圆曲线的协议上。因为椭圆曲线的标量乘法与坐标y无关,Domiinguze-Oviedo等[9]给出了一种错误攻击算法可以应用到基于二元域上的曲线的Montgomery ladder算法。近期,通过在输入除子上植入1-比特错误,王明强,薛海洋和展涛[29][30]给出了一种基于有限域上亏格为2的超越椭圆曲线上Jacobian群中除子的不同表示方法的有效的攻击算法。在他们的攻击模型中,攻击者是知道错误发生的位置的,然而在实际过程中攻击者可以植入错误却很难去知道错误发生的具体位置。在本文中,我们假设攻击者不知道错误发生位置,给出了对输入除子植入1-比特错误情况下,有限域上亏格为2的超椭圆曲线上离散对数问题的无效曲线攻击,并且根据除子的不同表示给出两种攻击算法。基于超椭圆曲线上的标量乘法(HECSM)的算法F2a[20]与曲线方程中系数a0,a1无关,我们可以根据植入1-比特错误的除子对应的输出除子来构造与原曲线相差系数a0,a1的无效曲线,并且若此无效曲线上Jacobian群的阶是光滑整数,从而被植入错误的除子在新的无效曲线上的Jacobian群中的阶n的素因子均不大,可用Silver-Pohlig-Hellmans算法[25]来恢复部分密钥к1nod n,甚至к。我们估算了得到一个ω-有效错误的概率为ρ(log n/log ω)。同时,实验结果表明文中的攻击算法是有效的。(本文来源于《山东大学》期刊2013-05-01)
王明强,薛海洋,展涛[10](2012)在《有限域上超椭圆曲线离散对数问题的错误攻击(英文)》一文中研究指出In this paper, we present two explicit invalid-curve attacks on the genus 2 hyperelliptic curve over a finite field. First, we propose two explicit attack models by injecting a one-bit fault in a given divisor. Then, we discuss the construction of an invalid curve based on the faulted divisor. Our attacks are based on the fact that the Hyperelliptic Curve Scalar Multiplication (HECSM) algorithm does not utilize the curve parameters and We consider three hyperelliptic curves as the attack targets. For curve with security level 186 (in bits), our attack method can get the weakest invalid curve with security level 42 (in bits); there are 93 invalid curves with security level less than 50. We also estimate the theoretical probability of getting a weak hyperelliptic curve whose cardinality is a smooth integer. Finally, we show that the complexity of the fault attack is subexponential if the attacker can freely inject a fault in the input divisor. Cryptosystems based on the genus 2 hyperelliptic curves cannot work against our attack algorithm in practice.(本文来源于《中国通信》期刊2012年11期)
椭圆曲线离散对数论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
基于椭圆曲线离散对数问题(elliptic curve discrete logarithm problem,ECDLP)求解的困难性,提出基于最优对(optimal-pairing)将椭圆曲线E(F_(p~l))上的离散对数问题(discrete logarithm problem,DLP)规约到扩域乘法群F*_(p~(kl))上的离散对数问题,新算法与MOV和FR规约算法相比速度更快,并且针对具有大扩张次数有限域的乘法群,改进Pollard-ρ算法迭代函数的选取,通过构造迭代压缩函数使其象集小于原象集,使新算法比原始的迭代函数更快地找到碰撞。在有限域Fpkl的乘法群上,新算法在原始算法的基础上速度提高了大约3p-3/5p-3~(2kl)~(1/2)倍。
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
椭圆曲线离散对数论文参考文献
[1].朱玉清,庄金成,于伟,林东岱.特征p椭圆曲线上p-群的离散对数问题[J].密码学报.2018
[2].翁江,扈瑜龙,马传贵.F_(q~k)上阶为q~k-1的椭圆曲线离散对数问题研究[J].信息工程大学学报.2018
[3].颜世骏.Koblitz椭圆曲线离散对数问题的计算[D].中山大学.2015
[4].王旻南.椭圆曲线离散对数问题的相关算法分析[D].南京大学.2015
[5].田松,李宝,王鲲鹏.椭圆曲线离散对数问题的研究进展[J].密码学报.2015
[6].杜育松,张方国.椭圆曲线离散对数的不动点[J].密码学报.2014
[7].邵飞,孟博.一种基于椭圆曲线离散对数问题的非交互式可否认认证协议[J].小型微型计算机系统.2014
[8].曹媛.加速椭圆曲线上离散对数问题的Pollard'sRho算法[D].山东大学.2013
[9].严爽.有限域上超椭圆曲线离散对数问题的错误攻击问题[D].山东大学.2013
[10].王明强,薛海洋,展涛.有限域上超椭圆曲线离散对数问题的错误攻击(英文)[J].中国通信.2012