椭圆曲线密码学
- 提出者
- 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)
- 智能卡、硬件安全模块和政府凭证中的身份验证和数字签名
- 计算资源有限的物联网和嵌入式系统安全
- 后量子密码学研究,研究双曲曲线以实现抗量子算法
使用方式
使用方式
选择一个椭圆曲线方程(通常是有限域上的y^2 = x^3 + ax + b),曲线上一个生成元点G,以及阶n(曲线上点的数量)。私钥d是一个随机整数,公钥Q = d × G通过点乘法计算得出。
椭圆曲线上的点在几何加法运算下构成一个群。要将两个不同的点相加,画一条穿过它们的直线,找到它与曲线的交点,然后将结果沿x轴反射。点倍增则使用切线。
要为公钥Q加密消息,生成一个随机数k,并计算两个值:一个点(x, y) = k × G,以及一个将消息与k × Q的哈希值结合起来的密文。
接收者使用其私钥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吗?
技术上可行,但不推荐。为加密和签名操作使用单独的密钥遵循了密钥分离原则,并降低了细微漏洞的风险。