椭圆曲线离散对数问题的研究进展  

On the Progress of Elliptic Curve Discrete Logarithm Problem

作　　者：田松[1,2] 李宝[1,2] 王鲲鹏[1,2] 

机构地区：[1]中国科学院信息工程研究所信息安全国家重点实验室,北京100093 [2]中国科学院数据与通信保护研究教育中心,北京100093

出　　处：《密码学报》2015年第2期177-188,共12页Journal of Cryptologic Research

基　　金：国家自然科学基金项目(61272040;61379137);国家重点基础研究发展项目(973计划)(2013CB338001)

摘　　要：自从1985年椭圆曲线密码被提出后,其理论和应用研究都受到了广泛关注.椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题的困难性.由于计算一般椭圆曲线中离散对数的算法都是指数时间的,椭圆曲线密码体制能够以更小的密钥尺寸来满足与其他公钥密码体制相同的安全性要求,从而特别适用于计算和存储能力受限的领域,许多标准化组织也相继提出了椭圆曲线上的公钥加密、密钥协商、数字签名协议的标准.利用Schoof's算法或复乘方法,人们可以很容易构造出密码学所需的椭圆曲线.通常推荐使用的椭圆曲线都定义在特征为2的有限域或素域上.为了加速有限域的运算,部分学者提议使用非素域有限域.然而对于非素域有限域上椭圆曲线中离散对数,基于求和多项式的指标计算法和Weil下降方法有可能比Pollard's Rho等一般性算法快.因此研究这些算法对椭圆曲线离散对数问题困难性的削弱程度以及相应的弱曲线特点对椭圆曲线密码学的安全应用有重大意义.本文将对解椭圆曲线离散对数问题的方法和研究进展做简单综述.Since 1985 when elliptic curve cryptography was proposed, its theory and applications have attracted a wide spread attention. The hardness of the discrete logarithm problem in elliptic curves is crucial for the security of elliptic curve cryptosystems. Since the fastest algorithms for the discrete problem in generic elliptic curves are exponential, smaller key sizes can provide the same level of security as other public-key cryptosystems.This advantage is attractive for applications where the computational power and storage space are limited, and numerous standards organizations have standardized elliptic curve cryptographic approach for public-key encryption, key agreement and digital signature. Additionally, it is easy to construct elliptic curves which are suitable for cryptographic applications by using Schoof's algorithm and complex multiplication algorithm. Normally elliptic curves considered for cryptographic application are defined over binary or prime fields. For potential performance advantages, various forms of extension fields have been proposed for usage. However, some elliptic curves over finite non-prime fields can be attacked with index calculus based on summation polynomials and Weil descent attack, which are faster than the generic algorithms. Consequently, for cryptographic purposes, it is necessary to study the security reduction these algorithms lead to and find features weak curves share. This survey describes the state-of-the-art in algorithms for solving the elliptic curve discrete logarithm problem.

关 键 词：椭圆曲线 离散对数问题 指标计算法 求和多项式 Weil下降 

分 类 号：TN918.1[电子电信—通信与信息系统]