椭圆曲线密码学

椭圆曲线密码学（ECC）在椭圆曲线上的点群上实现了公钥方案，以小得多的密钥实现了与RSA或有限域Diffie-Hellman相同的安全性。

Definition

椭圆曲线密码学是一种公钥密码学，其底层群是有限域上椭圆曲线上的点集，其安全性基于椭圆曲线离散对数问题的难度。

Scope

本主题涵盖有限域上的椭圆曲线群定律、椭圆曲线离散对数问题，以及基于它们构建的方案：椭圆曲线Diffie-Hellman（ECDH）、ECDSA和EdDSA签名方案，以及Curve25519等现代曲线。它解释了为什么椭圆曲线离散对数比有限域离散对数更难（没有亚指数指标演算），以及ECDSA中随机数重用等实现问题。它不包括在姊妹主题中涵盖的RSA和有限域离散对数方案。

Core questions

• 椭圆曲线上点的几何加法如何形成一个密码群？
• 为什么椭圆曲线离散对数比其有限域模拟更难，从而允许使用更小的密钥？
• Diffie-Hellman和数字签名如何在椭圆曲线上实例化？
• 与旧的NIST曲线相比，Curve25519等现代曲线为何更安全？
• 为什么ECDSA中每个签名的随机数唯一性至关重要？

Key concepts

• 椭圆曲线群定律
• 标量乘法
• 椭圆曲线离散对数问题
• ECDH
• ECDSA
• EdDSA和Ed25519
• Curve25519
• 随机数重用漏洞
• 密钥大小与RSA

Key theories

椭圆曲线离散对数问题

给定曲线上的点P和Q = kP，恢复标量k被认为需要对精心选择的曲线进行完全指数级的努力，因为削弱有限域离散对数的指标演算攻击不适用。

相同安全性下更小的密钥

由于椭圆曲线离散对数的最佳攻击是通用平方根算法，因此256位椭圆曲线提供大约128位安全性——与3072位RSA相当——从而实现更快的操作和更小的密钥和签名。

Mechanisms

有限域上椭圆曲线上的点在几何加法定律下形成一个阿贝尔群；将基点P重复加到自身k次（标量乘法，kP）是高效的，但从kP恢复k是一个难题。ECDH通过交换基点的标量倍数来执行Diffie-Hellman；ECDSA和EdDSA从每个消息的标量（一个随机数）生成签名——如果重复或可预测，则会泄露私钥，正如几次真实泄露所表明的。

Clinical relevance

ECC是新系统默认的公钥选择：ECDHE在TLS 1.3中提供前向保密密钥交换，Ed25519签署SSH密钥、软件更新和证书，Curve25519保护Signal、WireGuard和现代消息传递。其小密钥和快速操作使其非常适合移动设备、智能卡和受限的物联网硬件。

Evidence & guidelines

ECDSA在FIPS 186中标准化，ECDH在NIST SP 800-56A中标准化，EdDSA/Ed25519在RFC 8032中标准化；Curve25519/X25519在RFC 7748中标准化。现代实践倾向于Edwards曲线和X25519，因为它们能抵抗实现陷阱。ECDSA在随机数重用时失效（特别是2010年索尼PlayStation 3密钥提取事件）是一个警示性的标准案例。

History

Neal Koblitz和Victor Miller在1985-1987年独立提出了将椭圆曲线用于密码学。由于专利和信任问题以及NIST曲线的复杂性，最初的采用速度缓慢，但随着密钥大小效率变得更加重要，以及Bernstein的Curve25519（2006年）和Ed25519提供了快速、抗滥用的设计，ECC在2010年代占据了主导地位，并被广泛部署。

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

为什么256位椭圆曲线密钥与3072位RSA密钥匹配？

椭圆曲线离散对数的最佳已知攻击是通用的，所需时间大约是群大小的平方根，而因式分解和有限域离散对数有更快的亚指数算法。因此，椭圆曲线在相同安全级别下需要少得多的比特数。

NIST椭圆曲线值得信赖吗？

标准的NIST P曲线被广泛使用，并且没有已知被破解，但其未解释的常数选择和实现难度导致许多人更喜欢Curve25519和Ed25519，它们具有透明的设计原理，并且更容易以恒定时间安全地实现。