椭圆曲线密码学

维基百科,自由的百科全书
跳转至: 导航搜索

椭圆曲线密码学Elliptic curve cryptography,缩写为ECC)是基于椭圆曲线数学的一种公钥密码的方法。椭圆曲线在密码学中的使用是在1985年由Neal KoblitzVictor Miller分别独立提出的。

ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA加密算法——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射,基于Weil对或是Tate对;双线性映射已经在密码学中发现了大量的应用,例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。

密钥交换[编辑]

椭圆曲线密码学的许多形式有稍微的不同,所有的都依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上,对应有限域椭圆曲线的群。

伽罗瓦域[编辑]

对椭圆曲线来说最流行的有限域是以素数为模的整数域(参见 模运算GF(p),或是特征为2的伽罗瓦域GF(2m)。后者在专门的硬件实现上计算更为有效,而前者通常在通用处理器上更为有效。专利的问题也是相关的。一些其他素数的伽罗瓦域的大小和能力也已经提出了,但被密码专家认为有一点问题。

给定一条椭圆曲线E以及一个域GF(q),我们考虑具有(x, y)形式有理数点E(q)阿贝尔群,其中x和y都在GF(q)中并且定义在这条曲线上的群运算"+"(运算"+"在文章椭圆曲线中描述)。我们然后定义第二个运算"*" | Z×E(q)->E(q):如果P是E(q)上的某个点,那么我们定义2*P=P+P, 3*P=2*P+P=P+P+P等等。注意给定整数 j和k,j*(k*P)=(j*k)*P=k*(j*P)。椭圆曲线离散对数问题(ECDLP)就是给定点P和Q,确定整数k使k*P=Q。 -- 一般认为在一个有限域乘法群上的离散对数问题(DLP)和椭圆曲线上的离散对数问题(ECDLP)並不等价;ECDLP比DLP要困难的多。

在密码的使用上,曲线E(q)和其中一个特定的基点G一起被选择和公布。一个私钥k被作为随机整数来选择;值P=k*G被作为公钥来公布(注意假设的ECDLP困难性意味着k很难从P中确定)。如果Alice和Bob有私钥kAkB,公钥是PAPB,那么Alice能计算kA*PB=(kA*kB)*G;Bob能计算同样的值kB*PA=(kB*kA)*G

这允许一个“秘密”值的建立,这样Alice和Bob能很容易地计算出,但任何的第三方却很难得到。另外,Bob在处理期间不会获得任何关于kA的新知识,因此Alice的私钥仍然是私有的。

加密[编辑]

基于这个秘密值,用来对Alice和Bob之间的报文进行加密的实际方法是适应以前的,最初是在其他组中描述使用的离散对数密码系统。这些系统包括:

对于ECC系统来说,完成运行系统所必须的群操作比同样大小的因数分解系统或模整数离散对数系统要慢。不过,ECC系统的拥护者相信ECDLP问题比DLP或因数分解问题要难的多,并且因此使用ECC能用小的多的密钥长度来提供同等的安全,在这方面来说它确实比例如RSA之类的更快。到目前为止已经公布的结果趋于支持这个结论,不过一些专家表示怀疑。

ECC被广泛认为是在给定密钥长度的情况下,最强大的非对称算法,因此在对带宽要求十分紧的连接中会十分有用。

建议[编辑]

美國國家標準與技術局ANSI X9已经设定了最小密钥长度的要求,RSA和DSA是1024位,ECC是160位,相应的对称分组密码的密钥长度是80位。NIST已经公布了一列推荐的椭圆曲线用来保护5个不同的对称密钥大小(80, 112, 128, 192, 256)。一般而言,二进制域上的ECC需要的非对称密钥的大小是相应的对称密钥大小的两倍。

Certicom是ECC的主要商业支持者,拥有超过130项专利,并且已经以2千5百万美元的交易获得了国家安全机构(NSA)的技术许可。他们也已经发起了许多对ECC算法的挑战。已经被解决的最复杂的是109位的密钥,是在2003年初由一个研究团队破解的。破解密钥的这个团队使用了基于生日攻击的大块并行攻击,用超过10,000台奔腾级的PC机连续运行了540天以上。对于ECC推荐的最小密钥长度163位来说,当前估计需要的计算资源是109位问题的108倍。

在2005年2月16日,NSA宣布决定采用椭圆曲线密码的战略作为美国政府标准的一部分,用来保护敏感但不保密的信息。NSA推荐了一组被称为Suit B的算法,包括用来密钥交换的Menezes-Qu-Vanstone椭圆曲线和Diffie-Hellman椭圆曲线,用来数字签名的椭圆曲线数字签名算法。这一组中也包括AESSHA

另见[编辑]

参考文献[编辑]

  • Neal Koblitz, "Elliptic curve cryptosystems", Mathematics of Computation 48, 1987, pp203–209
  • V. Miller, "Use of elliptic curves in cryptography", CRYPTO 85, 1985.
  • Blake, Seroussi, Smart, "Elliptic Curves in Cryptography", Cambridge University Press, 1999
  • Hankerson, Menezes, Vanstone, "Guide to Elliptic Curve Cryptography", Springer-Verlag, 2004
  • L. Washington, "Elliptic Curves: Number Theory and Cryptography", Chapman & Hall/CRC, 2003

外部链接[编辑]