
_START_ARTICLE_
椭圆曲线密码学
_START_PARAGRAPH_
椭圆曲线密码学（英语：Elliptic Curve Cryptography，缩写：ECC）是一种基于椭圆曲线数学的公开密钥加密算法。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。_NEWLINE_ECC的主要优势是在某些情况下它比其他的算法（比如RSA加密算法）使用更小的密钥并提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。
_START_SECTION_
密钥交换
_START_PARAGRAPH_
椭圆曲线密码学的许多形式有稍微的不同，所有的都依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上，对应有限域上椭圆曲线的群。
_START_SECTION_
伽罗瓦域
_START_PARAGRAPH_
对椭圆曲线来说最流行的有限域是以素数为模的整数域（参见模运算)，或是特征为2的伽罗瓦域 GF（2ᵐ）。后者在专门的硬件实现上计算更为有效，而前者通常在通用处理器上更为有效。专利的问题也是相关的。一些其他素数的伽罗瓦域的大小和能力也已经提出了，但被密码专家认为有一点问题。_NEWLINE_给定一条椭圆曲线E以及一个域，我们考虑具有形式有理数点的阿贝尔群，其中x和y都在中并且定义在这条曲线上的群运算"+"（运算"+"在文章椭圆曲线中描述）。我们然后定义第二个运算"*" | Z×：如果P是上的某个点，那么我们定义等等。注意给定整数j和k，。椭圆曲线离散对数问题（ECDLP）就是给定点P和Q，确定整数k使。_NEWLINE_--_NEWLINE_一般认为在一个有限域乘法群上的离散对数问题（DLP）和椭圆曲线上的离散对数问题（ECDLP）并不等价；ECDLP比DLP要困难的多。_NEWLINE_在密码的使用上，曲线和其中一个特定的基点G一起被选择和公布。一个私钥k被作为随机整数来选择；值被作为公钥来公布（注意假设的ECDLP困难性意味着k很难从P中确定）。如果Alice和Bob有私钥kA和kB，公钥是PA和PB，那么Alice能计算kA*PB=(kA*kB)*G；Bob能计算同样的值kB*PA=(kB*kA)*G。_NEWLINE_这允许一个“秘密”值的建立，这样Alice和Bob能很容易地计算出，但任何的第三方却很难得到。另外，Bob在处理期间不会获得任何关于kA的新知识，因此Alice的私钥仍然是私有的。
_START_SECTION_
建议
_START_PARAGRAPH_
美国国家标准与技术局和ANSI X9已经设定了最小密钥长度的要求，RSA和DSA是1024位，ECC是160位，相应的对称分组密码的密钥长度是80位。NIST已经公布了一列推荐的椭圆曲线用来保护5个不同的对称密钥大小（80, 112, 128, 192, 256）。一般而言，二进制域上的ECC需要的非对称密钥的大小是相应的对称密钥大小的两倍。_NEWLINE_Certicom是ECC的主要商业支持者，拥有超过130项专利，并且已经以2千5百万美元的交易获得了美国国家安全局（NSA）的技术许可。他们也已经发起了许多对ECC算法的挑战。已经被解决的最复杂的是109位的密钥，是在2003年初由一个研究团队破解的。破解密钥的这个团队使用了基于生日攻击的大块并行攻击，用超过10,000台奔腾级的PC机连续运行了540天以上。对于ECC推荐的最小密钥长度163位来说，当前估计需要的计算资源是109位问题的10⁸倍。_NEWLINE_在2005年2月16日，NSA宣布决定采用椭圆曲线密码的战略作为美国政府标准的一部分，用来保护敏感但不保密的信息。NSA推荐了一组被称为Suit B的算法，包括用来密钥交换的Menezes-Qu-Vanstone椭圆曲线和Diffie-Hellman椭圆曲线，用来数字签名的椭圆曲线数字签名算法。这一组中也包括AES和SHA。
_START_SECTION_
安全性
_START_PARAGRAPH_
如果攻击者拥有大型量子计算机，那么他可以使用秀尔算法解决离散对数问题，从而破解私钥和共享秘密。目前的估算认为：破解256位素数域上的椭圆曲线，需要2330个量子比特与1260亿个托佛利门。相比之下，使用秀尔算法破解2048位的RSA则需要4098个量子比特与5.2万亿个托佛利门。因此，椭圆曲线会更先遭到量子计算机的破解。目前还不存在建造如此大型量子计算机的科学技术，因此椭圆曲线密码学至少在未来十年（或更久）依然是安全的。但是密码学家已经积极展开了后量子密码学的研究。其中，超奇异椭圆曲线同源密钥交换（SIDH）有望取代当前的常规椭圆曲线密钥交换（ECDH）。