椭圆曲线密码学

椭圆曲线密码学（ECC）在有限域椭圆曲线上实现公钥密码。椭圆曲线群目前没有经典亚指数级离散对数算法，故 ECC 以远小于 RSA 的密钥达到同等安全强度（256 位 ECC ≈ 3072 位 RSA），是移动设备与区块链常用的公钥密码。它是有限域几何结构对离散对数问题的直接移植。

有限域上的椭圆曲线

设素数 $p>3$，曲线 $E:\ y^2=x^3+ax+b$（$4a^3+27b^2\not\equiv0\pmod p$）上的点连同无穷远点 $O$ 构成加法群：

• $O$ 为单位元；$(x,y)$ 的逆元为 $(x,-y)$
• 加法法则：过 $P,Q$ 的直线与曲线交于第三点，关于 $x$ 轴对称得 $P+Q$；$P=Q$ 时取切线
• 群阶 $N=\#E(\mathbb{F}_p)$ 满足 Hasse 界 $|N-(p+1)|\le2\sqrt p$；密码学使用其大素数阶循环子群

ECDLP 与协议

椭圆曲线离散对数问题（ECDLP）：给定 $P$ 与 $kP$ 求 $k$，目前无经典亚指数算法（见离散对数问题）。

• ECDH：Alice 发 $aP$、Bob 发 $bP$，共享密钥 $abP$（见Diffie-Hellman密钥交换）
• ECDSA：椭圆曲线版数字签名

示例

取 $E:\ y^2=x^3+2x+2$ 于 $\mathbb{F}_{17}$，$N=19$ 为素数，$P=(5,1)$ 生成整个群。Alice 选 $a=5$，Bob 选 $b=8$：

$$aP=5P=(9,16),\qquad bP=8P=(13,7)$$

共享密钥 $5(8P)=8(5P)=40P\equiv2P=(6,3)$。

安全与应用

• 密钥长度：256 位 ECC 提供约 128 位安全强度，与 3072 位 RSA 相当
• 须选用标准曲线（P-256、Curve25519 等），避免异常曲线攻击
• 椭圆曲线同时是数论研究对象：费马大定理证明中的弗赖曲线、以及 ECM 因子分解都用到它

应用

ECC 广泛用于 TLS、比特币/以太坊签名（secp256k1）与身份认证；与解析数论中的椭圆曲线从不同视角研究同一对象。