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

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

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

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

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

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

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

 的实现

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

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}

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, }}

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)}

 的实现

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())        }    }}

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

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

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

按照标准（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 的实现存在可延展性问题，需要我们检查 的实现。

致谢

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

慢雾导航

慢雾科技官网

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