Skip to content
返回搜索结果

椭圆曲线密码学

提出者
Neal Koblitz
年份
1985
类型
asymmetric encryption and key agreement
类别
Public-key cryptography

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线代数结构的公钥密码系统。ECC由Neal Koblitz和Victor Miller于1985年独立提出,在提供与RSA相当的安全性的同时,密钥尺寸却小得多。现代密码学日益青睐ECC,因为它效率高:一个256位的ECC密钥提供的安全性相当于一个2048位的RSA密钥,这使其成为资源受限环境和高性能系统的理想选择。

方法背后的直觉

ECC基于椭圆曲线离散对数问题:给定一个曲线方程和两个点,利用曲线的几何性质很容易计算它们的和,但反向操作——找出需要将一个点自加多少次才能得到另一个点——则极其困难。这种不对称性使得安全的密钥生成和交换成为可能。与RSA依赖于因子分解问题不同,ECC的难度来自于椭圆曲线群的结构。

历史学

ECC由Neal Koblitz和Victor Miller于1985-1987年独立发明。最初,由于专利问题和RSA的既有主导地位,采用缓慢。然而,从21世纪初开始,ECC作为更优越的替代方案逐渐获得重视,尤其是在美国国家安全局(NSA)推荐在保密信息中使用椭圆曲线之后。现代协议如TLS 1.3、Signal和区块链系统已在很大程度上标准化了Curve25519和P-256等ECC曲线。

何时使用

ECC非常适合需要强大安全性但资源有限的应用,例如移动设备、物联网系统和嵌入式系统。它是现代互联网协议(TLS 1.3使用ECDHE)、区块链系统(比特币和以太坊使用ECDSA)以及消息传递应用(Signal使用Curve25519)的标准。由于其卓越的性能和相当的安全性,新系统应优先选择ECC而非RSA。

局限与注意事项

  • 比RSA具有更复杂的数学基础,使得实现和分析更具挑战性
  • 需要仔细选择椭圆曲线参数;弱曲线(如嵌入度低的曲线)容易受到攻击
  • 安全性高度依赖于所使用的特定曲线;标准化曲线是首选,但其选择涉及一些争议

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 与RSA相比,同等安全级别下密钥尺寸小得多,减少了存储和传输开销
  • 与同等安全强度的RSA相比,密钥生成、加密和解密速度更快
  • 非常适合资源受限的设备,如手机、物联网设备和智能卡
  • 在现代密码库和协议中日益标准化和得到支持

应用

  • TLS/SSL加密,用于HTTPS和现代Web安全,使用ECDHE密钥交换
  • 区块链和加密货币系统(比特币在secp256k1上使用ECDSA,以太坊在secp256k1上使用ECDSA)
  • 消息传递和安全通信(Signal协议使用Curve25519和X25519)
  • 智能卡、硬件安全模块和政府凭证中的身份验证和数字签名
  • 计算资源有限的物联网和嵌入式系统安全
  • 后量子密码学研究,研究双曲曲线以实现抗量子算法

使用方式

使用方式

1

选择一个椭圆曲线方程(通常是有限域上的y^2 = x^3 + ax + b),曲线上一个生成元点G,以及阶n(曲线上点的数量)。私钥d是一个随机整数,公钥Q = d × G通过点乘法计算得出。

2

椭圆曲线上的点在几何加法运算下构成一个群。要将两个不同的点相加,画一条穿过它们的直线,找到它与曲线的交点,然后将结果沿x轴反射。点倍增则使用切线。

3

要为公钥Q加密消息,生成一个随机数k,并计算两个值:一个点(x, y) = k × G,以及一个将消息与k × Q的哈希值结合起来的密文。

4

接收者使用其私钥d计算d × (k × G) = k × (d × G) = k × Q,从而恢复共享密钥并解密消息。

常见陷阱

  • 在未进行侧信道攻击防护的情况下实现点乘法,可能通过时间或功耗分析泄露私钥
  • 使用弱的或非标准的椭圆曲线,这些曲线可能存在数学弱点,从而将安全性降低到不存在的水平
  • 在ECDSA签名中未能为临时密钥k使用密码学安全的随机数生成器,导致签名可被伪造

常见问题

为什么256位的ECC密钥与2048位的RSA密钥一样安全?

椭圆曲线上的离散对数问题比整数分解问题更难。即使使用量子计算机,解决ECDLP也需要指数时间(使用Shor算法),而整数分解在量子计算机上则变为多项式时间。

最常用的椭圆曲线有哪些?

NIST标准化曲线有P-256、P-384和P-521。Bernstein的Curve25519因其对实现攻击的鲁棒性而在现代系统中受到青睐。比特币使用secp256k1,以太坊也使用secp256k1进行账户和交易签名。

ECC是否容易受到量子计算机攻击?

是的,Shor算法可以在量子计算机上解决椭圆曲线离散对数问题,使得ECC和RSA都易受攻击。后量子密码学研究正在开发基于格、基于码和多元方程的替代方案。

ECDH和ECDSA之间有什么区别?

ECDH(椭圆曲线Diffie-Hellman)是一种在不安全信道上建立共享密钥的关键协议。ECDSA(椭圆曲线数字签名算法)用于创建和验证数字签名。

我可以使用相同的密钥进行ECDH和ECDSA吗?

技术上可行,但不推荐。为加密和签名操作使用单独的密钥遵循了密钥分离原则,并降低了细微漏洞的风险。

相关方法

参考文献

  1. Miller, V. S. (1985). Use of Elliptic Curves in Cryptography. In Proceedings of the Advances in Cryptology - CRYPTO 1985, LNCS 218, pp. 417-426.

    打开 DOI 文献
    已复制。
  2. Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177), 203-209.

    打开 DOI 文献
    已复制。