慢雾：Ed25519 实现原理与可延展性问题

By: 阿为

Ed25519 是一个基于椭圆曲线的数字签名算法，它高效，安全且应用广泛。TLS 1.3, SSH, Tor, ZCash, WhatsApp 和 Signal 中都使用了它。本文主要讲解以下几点：

1. 介绍一点群论知识，目的是让大家对 Ed25519 和其可延展性问题的原理有一种直觉。若想深入理解，还需参考其他资料；

2. 针对 rust 库 ed25519-dalek 的 1.0.1 版本讲解 ed25519 的实现；

3. 针对该库的延展性问题做出解释。

数学要点回顾

群的定义与性质

群论是抽象代数研究的内容，但抽象代数的一些思想是程序员非常熟悉的。面向对象中的继承就是一个很好的例子，我们都知道子类继承了父类后，就能使用父类中定义的方法。可以将抽象代数理解为对一个抽象的数据结构定义了一些性质，由这些性质推导出来的定理对于所有的子类都成立。

沿用刚刚的比喻，来看看群（group）这个数据结构是如何定义的。

一个群由一个操作（任何的二元操作用 记）和一些元素构成，同时满足如下性质：

• CLOSURE: ，闭包性意味着群中的任何运算结果都在群里
• ASSOCIATIVITY: ，结合律代表运算符的顺序不影响结果
• NEUTRAL: ，这条性质也叫 Identity，意味着存在一个元素跟其他的元素结合，得到的结果总是其他元素
• INVERSE: ，可逆性代表元素总有一个逆

由此可以推出许多有意思的定理：

•  一定是唯一的，如果不是的话，假设存在两个 ，那么 且 ， 则 
• 也一定是唯一的

举几个例子： 

• 整数 ..., −2, −1, 0, 1, 2, ... 和加法是一个群，因为它们满足上面四个性质

• 整数和乘法不是群，因为它们不满足可逆性，，但是 并不属于整数

被一笔带过的群论术语

• order: 阶指的是群里面的元素个数，刚刚的例子中的群的阶都是 

• abelian group: 阿贝尔群就是在刚刚的 4 条性质基础上还多一条交换律

• cyclic group: 刚刚的例子都是元素无限多的群，但是我们较常遇到的其实是有限个数的群，比方说 : 0, 1, 2, 3, 4, 5, 6 这个群由这 7 个数和加法组成，加法做完后还要再模 7，所以 6 + 1 等于 0，不等于 7。这就是一个环群，很合理，很符合直觉的命名

• subgroup: 子群是某个群的一部分，而且它本身也是一个群。举例来说 : 0, 1, 2, 3, 4, 5, 6, 7, 8 中的 0, 3, 6 就能形成一个子群。偶数和加法是整数和加法的子群，但奇数不是，因为 ， 不是奇数

• generator: 生成元是一个具体的元素 ，但是这个元素自己和自己做运算最终能得到群里的所有元素 , , , ..., 其中 

拉格朗日定理

现在介绍一个非常有意思的定理，这个定理的推导在文末引用的视频中。

“群的阶能被子群的阶整除。”

为什么说这个定理有意思呢，不仅仅因为它的证明过程串起了刚刚介绍的许多知识，还因为下面的结论：

“如果一个群的阶是一个素数 ，那么根据拉格朗日定理，子群的阶一定是 或者 。除了 之外，群里的所有元素都是生成元。”

Ed25519 的实现

现在我们来讲 Ed25519，它是 EdDSA 算法的其中一种。EdDSA 有 11 个参数（https://datatracker.ietf.org/doc/html/rfc8032#autoid-3），这些参数的具体选择对于算法的安全和性能有很大的影响。Ed25519 的具体选择请参看链接（https://datatracker.ietf.org/doc/html/rfc8032#autoid-9）。

另外，值得一提的是这套算法用到了一个叫 Curve25519（https://datatracker.ietf.org/doc/html/rfc7748#autoid-5）的椭圆曲线。对于椭圆曲线，我们只需知道，它上边有很多很多点，这些点相加能得到新的点，新的点还是在曲线上。这些点和这个加法能形成一个群。注意这里的椭圆曲线加法（https://www.wikiwand.com/en/Elliptic_curve_point_multiplication）是有特殊定义的。

我们约定如下记法：

• 点 加点 记作 
• 标量 乘点 记作 

对于 Ed25519 这条曲线，我们一共有 个点，也就是说群的阶是 ，其中 是一个素数 + 27742317777372353535851937790883648493。

我们从刚刚那个阶为 的群中提取了一个阶为素数 的子群（https://en.wikipedia.org/wiki/Abelian_group#Classification）：，这里的 是一个特殊的点，也是群中的 ，设 为任意点，。 也是一个点，被称为基点。根据定义，我们有 。后面讨论的内容都是在说这个子群。

根据论文（https://ed25519.cr.yp.to/ed25519-20110926.pdf）的描述，Ed25519 的算法是这样的，假设我们是 Prover，知道一个小秘密 ，其中 是基点， 是一个标量，也叫私钥， 是一个点，也叫公钥。我们要做的就是向知道我们公钥的 Verifier 证明我们知道公钥对应的私钥，但是我们不能直接将私钥告诉他：

1. Prover: 选择一个随机标量 

2. Prover —> Verifier: 发送 

3. Verifier —> Prover: 选择并发送一个随机标量 

4. Prover —> Verifier: 计算并发送 

5. Verifier: 验证 

这是个交互式的算法，但是没关系，有一个技巧叫做 the Fiat – Shamir heuristic（https://link.springer.com/chapter/10.1007%2F3-540-47721-7_12），它可以把任意的交互式算法转化成非交互式的算法。最终我们会用非交互式算法。

数字签名算法都会给我们如下 API：

•  —> 为私钥， 为公钥

•  —> 为消息， 为签名

•  —> 

 的实现

 输出一个私钥和一个公钥：

1. 随机生成一个 seed（https://github.com/dalek-cryptography/ed25519-dalek/blob/97c22f2d07b3c260726b90c55cd45f34ec34a037/src/secret.rs#L167-L176），这个 seed 有 32 个字节。我们使用了一个系统自带的密码学安全的随机数生成元。

where
    T: CryptoRng + RngCore,
{
    let mut sk: SecretKey = SecretKey([0u8; 32]);

    csprng.fill_bytes(&mut sk.0);

    sk
}

2. 把刚刚的 seed 扩展成 64 个字节（https://github.com/dalek-cryptography/ed25519-dalek/blob/97c22f2d07b3c260726b90c55cd45f34ec34a037/src/secret.rs#L265-L282），也就是图中的 xseed。xseed 的低 32 字节就是我们的私钥（aka a）。高 32 字节被称为 nonce，后面会被用在 中，其作用类似 domain sperator。

    pub(crate) key: Scalar,      // a
    pub(crate) nonce: [u8; 32],  // nonce
}

fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {
    let mut h: Sha512 = Sha512::default();
    let mut hash:  [u8; 64] = [0u8; 64];
    let mut lower: [u8; 32] = [0u8; 32];
    let mut upper: [u8; 32] = [0u8; 32];

    h.update(secret_key.as_bytes());
    hash.copy_from_slice(h.finalize().as_slice());

    lower.copy_from_slice(&hash[00..32]);
    upper.copy_from_slice(&hash[32..64]);


         // 这一步是 clamp
    lower[0]  &= 248;
    lower[31] &=  63;
    lower[31] |=  64;

    ExpandedSecretKey{ key: Scalar::from_bits(lower), nonce: upper, }
}

3. 用私钥生成公钥（https://github.com/dalek-cryptography/ed25519-dalek/blob/97c22f2d07b3c260726b90c55cd45f34ec34a037/src/public.rs#L54-L68）。公钥是椭圆曲线上的一个点。具体来说，我们利用椭圆曲线的基点 来做椭圆曲线乘法，就得到公钥。乘法中的标量则是通过对私钥 做一次哈希得到。

pub struct PublicKey(pub(crate) CompressedEdwardsY, pub(crate) EdwardsPoint);

impl<'a> From<&'a SecretKey> for PublicKey {
    /// Derive this public key from its corresponding `SecretKey`.
    fn from(secret_key: &SecretKey) -> PublicKey {
        let mut h: Sha512 = Sha512::new();
        let mut hash: [u8; 64] = [0u8; 64];
        let mut digest: [u8; 32] = [0u8; 32];

        h.update(secret_key.as_bytes());
        hash.copy_from_slice(h.finalize().as_slice());

        digest.copy_from_slice(&hash[..32])
        PublicKey::mangle_scalar_bits_and_multiply_by_basepoint_to_produce_public_key(&mut digest)
    }
}

fn mangle_scalar_bits_and_multiply_by_basepoint_to_produce_public_key(
    bits: &mut [u8; 32],
) -> PublicKey {
    bits[0] &= 248;
    bits[31] &= 127;
    bits[31] |= 64;

    let point = &Scalar::from_bits(*bits) * &constants::ED25519_BASEPOINT_TABLE;
    let compressed = point.compress();

    PublicKey(compressed, point)
}

 的实现

这里可以提一下之前说的 Fiat Shamir 技巧，其实只需要把所有 Verifier 提供的随机数替换成一个哈希函数的结果即可。具体请看代码注释。

pub fn sign(&self, message: &[u8], public_key: &PublicKey) -> ed25519::Signature {
    let mut h: Sha512 = Sha512::new();
    let R: CompressedEdwardsY;
    let r: Scalar;
    let s: Scalar;
    let k: Scalar;

    h.update(&self.nonce);
    h.update(&message);

    r = Scalar::from_hash(h); // r在我们交互式算法中是一个随机数，但是这里我们用了哈希。
    R = (&r * &constants::ED25519_BASEPOINT_TABLE).compress(); // R = [r]B

    h = Sha512::new();
    h.update(R.as_bytes());
    h.update(public_key.as_bytes());
    h.update(&message);

    k = Scalar::from_hash(h);   // h = Sha512(R || A || M)
    s = &(&k * &self.key) + &r; // s = r + h * a，h原本是随机数

    InternalSignature { R, s }.into()
}

 的实现

impl Verifier<ed25519::Signature> for PublicKey {
    #[allow(non_snake_case)]
    fn verify(
        &self,
        message: &[u8],
        signature: &ed25519::Signature
    ) -> Result<(), SignatureError>
    {
        let signature = InternalSignature::try_from(signature)?;

        let mut h: Sha512 = Sha512::new();
        let R: EdwardsPoint;
        let k: Scalar;
        let minus_A: EdwardsPoint = -self.1;

        h.update(signature.R.as_bytes());
        h.update(self.as_bytes());
        h.update(&message);

        k = Scalar::from_hash(h); // h的计算和sign中一样，h=Sha512(R||A||M)
        R = EdwardsPoint::vartime_double_scalar_mul_basepoint(&k, &(minus_A), &signature.s); // R’ = [s]B - [h]A

        if R.compress() == signature.R { // 如果R’==R，那么验证结果为真。
            Ok(())
        } else {
            Err(InternalError::VerifyError.into())
        }
    }
}

代码地址（https://github.com/dalek-cryptography/ed25519-dalek/blob/97c22f2d07b3c260726b90c55cd45f34ec34a037/src/public.rs#L322-L355）

可延展性问题

密码学算法的实现和使用都有非常多要注意的地方。当我们说一个数字签名算法是安全的，一般指的是即使在攻击者能够获得任意消息的签名（Chosen Message Attack）的情况下，攻击者仍然不能伪造签名。Ed25519 满足这个性质，但不代表 Ed25519 是绝对安全的。在原始的论文中也提到，可延展性问题是可以接受的，且原始的算法就有这个问题。

可延展性（Malleability）说的是，如果我们知道了一个对应着消息 和公钥 的签名 ，就能改变这个签名，改完后的签名 满足 。 

上一节提到，签名由 和 组成。我们只需要给 加上 就能构造新的签名。

还记得 是我们群的阶吗，所以 ，下面等式成立：

这样，新构造的签名和旧的签名就都能被验证成功了。延展性问题告诉我们签名并不是相对 message 和公钥确定，当签名算法存在延展性问题且代码中假设签名是确定的情况下，就很有可能存在漏洞。

按照标准（https://datatracker.ietf.org/doc/html/rfc8032#autoid-37），Ed25519 其实是没有可延展性问题的。因为在验证的过程中，我们会检查 是否小于 ，如果检查结果不为真，验证失败。但是标准（https://datatracker.ietf.org/doc/html/rfc8032）的出现晚于论文（https://ed25519.cr.yp.to/ed25519-20110926.pdf），因此在实际环境中，仍有 Ed25519 的实现存在可延展性问题，需要我们检查 的实现。

总结

文章首先介绍了一些群论概念，如群的定义和性质、阿贝尔群、环群、子群、生成器和拉格朗日定理。接着解释了基于 rust 库 ed25519-dalek 的 Ed25519 实现； 生成私钥和公钥； 生成签名 (R,s) 及  验证签名是否对消息和公钥有效。最后，指出 Ed25519 的可延展性问题及可以向 添加 （群的阶）生成同一消息和公钥的新有效签名 。

致谢

感谢领先的⼀站式数字资产⾃托管服务商 Safeheron 提供的专业技术建议。

References

[1]. https://ed25519.cr.yp.to/ed25519-20110926.pdf 

[2]. https://datatracker.ietf.org/doc/html/rfc8032 

[3]. https://github.com/dalek-cryptography/curve25519-dalek 

[4]. https://github.com/dalek-cryptography/ed25519-dalek 

[5]. Researchers Use Group Theory to Speed Up Algorithms — Introduction to Groups

往期回顾

慢雾导航

慢雾科技官网

https://www.slowmist.com/

慢雾区官网

https://slowmist.io/

慢雾 GitHub

https://github.com/slowmist

Telegram

https://t.me/slowmistteam

Twitter

https://twitter.com/@slowmist_team

Medium

https://medium.com/@slowmist

知识星球

https://t.zsxq.com/Q3zNvvF