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

fffmCQ.jpg

密码学算法的实现和使用都有非常多要注意的地方。

作者:阿为

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

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

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

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

数学要点回顾

群的定义与性质

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

沿用刚刚的比喻,来看看群(group)这个数据结构是如何定义的。

一个群由一个操作(任何的二元操作用 o 记)和一些元素构成,同时满足如下性质:

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

拉格朗日定理

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

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

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

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

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 实现原理与可延展性问题
慢雾:Ed25519 实现原理与可延展性问题

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

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

慢雾:Ed25519 实现原理与可延展性问题
慢雾:Ed25519 实现原理与可延展性问题
图片

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

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

pub fn generate<T>(csprng: &mut T) -> SecretKeywhere    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 struct ExpandedSecretKey { // xseed    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)}
慢雾:Ed25519 实现原理与可延展性问题
图片

这里可以提一下之前说的 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()}
慢雾:Ed25519 实现原理与可延展性问题
慢雾:Ed25519 实现原理与可延展性问题
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 是绝对安全的。在原始的论文中也提到,可延展性问题是可以接受的,且原始的算法就有这个问题。

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

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

慢雾:Ed25519 实现原理与可延展性问题
慢雾: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

声明:该文观点仅代表作者本人,与炒币网无关。炒币网系信息发布平台,仅提供信息存储空间服务。对所包含内容的准确性、可靠性或者完整性不提供任何明示或暗示的保证,并不对文章观点负责。 提示:投资有风险,入市须谨慎。本资讯仅供参阅,不作为投资理财建议。

发表评论

登录后才能评论