Ed25519 公钥深度解析

我们从一段 Rust 代码说起：

pub struct PublicKey<H: Hasher512> {
    compressed: CompressedEdwardsY,
    point: EdwardsPoint,
    _phantom: PhantomData<H>,
}

三个字段，每一个都有其存在的理由。本文从数学基础开始，逐层解释为什么要这么设计。

一、Ed25519 是什么？

Ed25519 是一种基于 Edwards 曲线的椭圆曲线数字签名算法（EdDSA），由 Daniel J. Bernstein 等人于 2011 年提出。

相比传统的 ECDSA，它有几个关键优势：

  • 确定性签名：随机数由私钥 + 消息哈希确定性推导，彻底消除随机数复用漏洞（ECDSA 因随机数复用导致私钥泄露的事故屡见不鲜）
  • 抗侧信道：Edwards 曲线的点加法公式是”完整的”，对任意两点都成立，无需特判无穷远点，消除了基于分支的侧信道攻击
  • 高性能：扭曲 Edwards 曲线的点加法比 Weierstrass 曲线快约 2 倍
  • 小巧：公钥 32 字节，签名 64 字节，非常适合嵌入式和区块链场景

二、数学基础

有限素数域 𝔽_p

所有运算都在一个巨大的素数定义的有限域上进行：

p = 2²⁵⁵ − 19

选这个数的原因是 2²⁵⁵ ≡ 19 (mod p)，使得模运算可以用移位 + 小常数加法高效实现，无需大整数除法。

扭曲 Edwards 曲线方程

Ed25519 使用的曲线方程：

−x² + y² = 1 + d·x²·y²

其中 d = −121665/121666  (mod p)

扭曲因子 a = −1 使得加法公式更高效。

基点与离散对数

曲线上有一个公认的生成元（基点）B，标量乘法 n·B 是整个签名体系的单向函数：

已知 P = n·B，无法从 P 反推 n。公钥 = 私钥标量 × 基点，私钥不可逆推。这就是离散对数难题（ECDLP）。

点加法（完整公式）

Edwards 曲线的点加法对任意两点 P₁=(x₁,y₁)，P₂=(x₂,y₂)：

x₃ = (x₁y₂ + y₁x₂) / (1 + d·x₁x₂y₁y₂)
y₃ = (y₁y₂ − a·x₁x₂) / (1 − d·x₁x₂y₁y₂)

分母在扭曲 Edwards 曲线上永远非零，所以公式是”完整的”，无需对无穷远点做特殊处理——这正是抗侧信道的根源。

三、EdwardsPoint：扩展齐次坐标

EdwardsPoint 不是直接存储 (x, y)，而是用扩展齐次坐标表示一个点：

(X : Y : Z : T)  其中  x = X/Z,  y = Y/Z,  T = XY/Z

4 个域元素 = 4 × 32 = 128 字节。这样设计有两个原因：

原因一：消除模逆元

在 𝔽_p 上做除法需要计算模逆元（费马小定理或扩展欧几里得算法），代价约等于 250 次乘法。

仿射坐标 (x, y) 的点加法每步都需要做一次除法。齐次坐标把除法推迟到最终需要仿射坐标时才做一次，中间所有加法都只用乘法——这是巨大的性能提升。

原因二：T 分量加速 unified 加法

额外的 T = XY/Z 分量使得 unified 加法公式只需 8 次乘法，无需分支判断。

标量乘法流程：

result = identity (0,1,1,0)
for each bit of scalar s (high → low):
    result = point_double(result)     // ~4 次乘法
    if bit == 1:
        result = point_add(result, B) // ~8 次乘法
return result

约 255 次 double + 128 次 add，全部在扩展坐标做，最后一次仿射化（1 次模逆元）得到 (x, y)。

四、CompressedEdwardsY：32 字节公钥

CompressedEdwardsY 是一个 [u8; 32]，即 32 字节 = 256 bits，实际只使用 255 bits 存储信息。

核心思想：给定曲线方程，已知 y 坐标就能恢复 x（最多两个解 ±x），所以只需存 y，再用 1 bit 标记 x 的符号即可唯一确定点。

编码格式

bytes[0..31]     = y 坐标（小端序，255 bits）
bytes[31] bit 7  = x 坐标的最低位（符号位）

解压缩（Decompression）

已知 y，从曲线方程 −x² + y² = 1 + d·x²·y² 解出 x：

x² = (y² − 1) / (d·y² + 1)   (mod p)
x  = √(x²)                    (mod p，约 255 次乘法)
如果 x 的奇偶性与符号位不符，取 x = p − x

注意：模平方根需要约 255 次域乘法，代价相当高。这正是 PublicKey 同时缓存 EdwardsPoint 的根本原因。

为什么是 y 而不是 x？

在 Edwards 曲线方程里，y 出现在线性项，从 y 解 x 只需一次平方根。另外 RFC 8032 标准规定使用 y + 符号位，所有实现保持一致。

五、为什么同时持有两种表示？

PublicKey 同时存了 CompressedEdwardsY（32 字节）和 EdwardsPoint（128 字节），看起来像是冗余——但这是深思熟虑的设计权衡。

CompressedEdwardsYEdwardsPoint
大小32 字节~128 字节
用途序列化、存储、展示签名验证、点运算
缺点无法直接参与运算无法直接序列化

如果不缓存 EdwardsPoint：每次验签都要重新解压缩（约 255 次乘法），高频验签的服务器代价极高。

如果不缓存 CompressedEdwardsY：每次序列化都要仿射化（1 次模逆元）再重新压缩，也不便宜。

两者都缓存：内存多用 128 字节，解压和序列化都是 O(1)，高频场景性能最优。

这种”冗余存储”在密码学库中叫做预计算缓存（precomputed form），RSA 的 CRT 参数、BLS 曲线的 G2 预计算点都是同样的思路：牺牲少量内存，换取不必重复推导。

六、PhantomData<H: Hasher512>

结构体里有个神秘的字段 _phantom: PhantomData<H>，它在运行时占零字节，但在类型系统中起关键作用。

Ed25519 签名中哈希在哪里？

// 1. 生成随机数 r（确定性）
r = Hash(privkey_hash[32..64] || message)

// 2. 计算 Schnorr 挑战 k
k = Hash(R || pubkey || message)

// 3. 计算签名的 s
s = r + k * privkey_scalar  (mod l)

Hash 默认是 SHA-512（RFC 8032 标准），但某些场景需要替换：Ed25519-Zebra 用 SHAKE-256，TEE 环境用硬件 hash。

为什么把哈希器参数化到 PublicKey 类型上？

SHA-512 私钥生成的签名，用 SHAKE-256 公钥去验证会静默失败。把 H 编码进类型，让编译器直接拒绝这种混用：

let sk: SecretKey<Sha512>    = SecretKey::new(...);
let pk: PublicKey<Sha512>    = sk.public_key();
let pk2: PublicKey<Shake256> = ...;

verify::<Sha512>(pk, sig, msg);    // OK ✓
verify::<Sha512>(pk2, sig, msg);   // 编译错误 ✗

为什么不是真实字段？

H 只是类型参数，不需要真正存一个 Hasher 对象（哈希器是无状态的，调用时现场创建）。但 Rust 规定未使用的类型参数会报 E0392 错误，PhantomData<H> 就是”假装”使用了 H，让编译器启用正确的 Drop、variance、Send/Sync 检查。

七、总结

把所有零件拼回来：

pub struct PublicKey<H: Hasher512> {
    compressed: CompressedEdwardsY,  // 32 字节，给人看
    point: EdwardsPoint,             // ~128 字节，给机器算
    _phantom: PhantomData<H>,        // 0 字节，给编译器看
}

设计链条：

  1. 选椭圆曲线：Curve25519（p = 2²⁵⁵−19）+ 扭曲 Edwards 方程，兼顾安全性与性能
  2. 点的运算表示：扩展齐次坐标 (X,Y,Z,T) → EdwardsPoint，避免模逆元瓶颈
  3. 点的压缩存储：只存 y + 1-bit 符号 → CompressedEdwardsY，公钥仅 32 字节
  4. 双缓存：PublicKey 同时持有两种表示，解压一次缓存复用，存取都高效
  5. 泛型哈希器：PhantomData<H> 把哈希策略编码进类型，编译期阻止混用错误

Ed25519 的 PublicKey 是一个”双态”结构：32 字节给人看，128 字节给机器算，通过 Rust 类型系统把哈希策略焊死在类型签名里，做到零运行时开销的安全保障。