> 本文將介紹基於橢圓曲線的數字簽名算法Ed25519 的實現原理與可延展性問題。

撰文：阿為

Ed25519 是一個基於橢圓曲線的數字簽名算法，它高效，安全且應用廣泛。 TLS 1.3, SSH, Tor, ZCash, WhatsApp 和Signal 中都使用了它。本文主要講解以下幾點：

1. 介紹一點群論知識，目的是讓大家對Ed25519 和其可延展性問題的原理有一種直覺。若想深入理解，還需參考其他資料；
2. 針對rust 庫ed25519-dalek 的1.0.1 版本講解ed25519 的實現；
3. 針對該庫的延展性問題做出解釋。

數學要點回顧

群的定義與性質

群論是抽象代數研究的內容，但抽象代數的一些思想是程序員非常熟悉的。面向對像中的繼承就是一個很好的例子，我們都知道子類繼承了父類後，就能使用父類中定義的方法。可以將抽象代數理解為對一個抽象的數據結構定義了一些性質，由這些性質推導出來的定理對於所有的子類都成立。

沿用剛剛的比喻，來看看群（group）這個數據結構是如何定義的。

一個群由一個操作（任何的二元操作用記）和一些元素構成，同時滿足如下性質：

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

舉幾個例子：

• 整數..., −2, −1, 0, 1, 2, ... 和加法是一個群，因為它們滿足上面四個性質
• 整數和乘法不是群，因為它們不滿足可逆性，4 x 1/4 = 1，但是1/4 並不屬於整數

被一筆帶過的群論術語

拉格朗日定理

現在介紹一個非常有意思的定理，這個定理的推導在文末引用的視頻中。

「群的階能被子群的階整除。」

為什麼說這個定理有意思呢，不僅僅因為它的證明過程串起了剛剛介紹的許多知識，還因為下面的結論：

「如果一個群的階是一個素數，那麼根據拉格朗日定理，子群的階一定是或者。除了之外，群裡的所有元素都是生成元。」

Ed25519 的實現

現在我們來講Ed25519，它是EdDSA 算法的其中一種。 EdDSA 有11 個參數（這些參數的具體選擇對於算法的安全和性能有很大的影響。Ed25519 的具體選擇請參看鏈接（

另外，值得一提的是這套算法用到了一個叫Curve25519（的橢圓曲線。對於橢圓曲線，我們只需知道，它上邊有很多很多點，這些點相加能得到新的點，新的點還是在曲線上。這些點和這個加法能形成一個群。注意這裡的橢圓曲線加法（是有特殊定義的。

我們約定如下記法：

這是個交互式的算法，但是沒關係，有一個技巧叫做the Fiat – Shamir heuristic（它可以把任意的交互式算法轉化成非交互式的算法。最終我們會用非交互式算法。

數字簽名算法都會給我們如下API：

KeyGen 的實現

輸出一個私鑰和一個公鑰：

1. 隨機生成一個seed（這個seed 有32 個字節。我們使用了一個系統自帶的密碼學安全的隨機數生成元。

pub fn 生成(csprng: &mut T) -> SecretKeywhere

T: CryptoRng + RngCore,

{

讓 mut sk: SecretKey = SecretKey([0u8; 32]);

csprng.fill_bytes(&mut sk.0);

斯克

}

2. 把剛剛的seed 擴展成64 個字節（也就是圖中的xseed。xseed 的低32 字節就是我們的私鑰（aka a）。高32 字節被稱為nonce，後面會被用在中，其作用類似domain sperator。

pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a

pub(crate) nonce: [u8; 32], // 隨機數

}

fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {

讓 mut h: Sha512 = Sha512::default();

讓 mut 散列：[u8; 64] = [0u8; 64]；

讓 mut 降低：[u8; 32] = [0u8; 32]；

讓 mut 上層：[u8; 32] = [0u8; 32]；

h.update(秘密_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

降低 [0] &= 248;

降低 [31] &= 63;

降低 [31] |= 64;

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

}

3. 用私鑰生成公鑰（公鑰是橢圓曲線上的一個點。具體來說，我們利用橢圓曲線的基點來做橢圓曲線乘法，就得到公鑰。乘法中的標量則是通過對私鑰做一次哈希得到。

pub struct ExpandedSecretKey { // xseed pub(crate) key: Scalar, // a

pub(crate) nonce: [u8; 32], // 隨機數

}

fn from(secret_key: &'a SecretKey) -> ExpandedSecretKey {

讓 mut h: Sha512 = Sha512::default();

讓 mut 散列：[u8; 64] = [0u8; 64]；

讓 mut 降低：[u8; 32] = [0u8; 32]；

讓 mut 上層：[u8; 32] = [0u8; 32]；

h.update(秘密_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

降低 [0] &= 248;

降低 [31] &= 63;

降低 [31] |= 64;

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

}

Sign 的實現

這裡可以提一下之前說的Fiat Shamir 技巧，其實只需要把所有Verifier 提供的隨機數替換成一個哈希函數的結果即可。具體請看代碼註釋。

pub fn sign(&self, message: & [u8] , public_key: &PublicKey) -> ed25519::Signature {

讓 mut h: Sha512 = Sha512::new();

讓 R：壓縮愛德華茲；

讓 r：標量；

let s：標量；

讓k：標量；

h.update(&self.nonce);

h.update(&消息);

r = Scalar::from_hash(h); // r 在我們交互式算法中是一個隨機數，但是這裡我們用了哈希。

R = (&r * &constants::ED25519_BASEPOINT_TABLE).compress(); // R = [r] 乙

h = Sha512::new();

h.update(R.as_bytes());

h.update(public_key.as_bytes());

h.update(&消息);

k = Scalar::from_hash(h); // h = Sha512(R || A || M)

s = &(&k * &self.key) + &r; // s = r + h * a，h 原本是隨機數

InternalSignature { R, s }.into()

}

Verify 的實現

impl驗證者對於公鑰 {

#[允許（非_snake_case）]

fn 驗證(

＆自己，

信息： ＆ [u8] ,

簽名：&ed25519::簽名

) -> 結果<(), SignatureError>

{

讓 signature = InternalSignature::try_from(signature)?;

讓 mut h: Sha512 = Sha512::new();

讓 R: EdwardsPoint;

讓k：標量；

減去_A: EdwardsPoint = -self.1;

h.update(signature.R.as_bytes());

h.update(self.as_bytes());

h.update(&消息);

k = Scalar::from_hash(h); // h 的計算和sign 中一樣，h=Sha512(R||A||M)

R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(minus_A), &signature.s); // R' = [s] 乙 - [h] A

if R.compress() == signature.R { // 如果R'==R，那麼驗證結果為真。

好的（（））

} 別的 {

錯誤（內部錯誤：：VerifyError.into（））

}

}

}

代碼地址（

可延展性問題

密碼學算法的實現和使用都有非常多要注意的地方。當我們說一個數字簽名算法是安全的，一般指的是即使在攻擊者能夠獲得任意消息的簽名（Chosen Message Attack）的情況下，攻擊者仍然不能偽造簽名。 Ed25519 滿足這個性質，但不代表Ed25519 是絕對安全的。在原始的論文中也提到，可延展性問題是可以接受的，且原始的算法就有這個問題。

這樣，新構造的簽名和舊的簽名就都能被驗證成功了。延展性問題告訴我們簽名並不是相對message 和公鑰確定，當簽名算法存在延展性問題且代碼中假設簽名是確定的情況下，就很有可能存在漏洞。

按照標準（ 其實是沒有可延展性問題的。因為在驗證的過程中，我們會檢查是否小於，如果檢查結果不為真，驗證失敗。但是標準（的出現晚於論文（因此在實際環境中，仍有Ed25519 的實現存在可延展性問題，需要我們檢查的實現。

總結

致謝

*感謝領先的⼀站式數字資產⾃託管服務商Safeheron 提供的專業技術建議。 *

> 參考資料

> [1] .

> [2] .

> [3] .

> [4] .

> [5] .研究人員使用群論來加速算法——群簡介