> Bài viết này sẽ giới thiệu nguyên tắc triển khai và khả năng mở rộng của thuật toán chữ ký số dựa trên đường cong elip Ed25519.

Được viết bởi: A Wei

Ed25519 là một thuật toán chữ ký điện tử dựa trên đường cong elip, hiệu quả, an toàn và được sử dụng rộng rãi. Nó được sử dụng trong TLS 1.3, SSH, Tor, ZCash, WhatsApp và Signal. Bài viết này chủ yếu giải thích các điểm sau:

1. Giới thiệu một chút kiến thức về lý thuyết nhóm, mục đích là để mọi người có trực giác về nguyên tắc của Ed25519 và vấn đề khả năng mở rộng của nó. Để hiểu sâu hơn, bạn cần tham khảo thêm các tài liệu khác;
2. Giải thích việc triển khai ed25519 cho phiên bản 1.0.1 của thư viện gỉ ed25519-dalek;
3. Giải thích khả năng mở rộng của thư viện.

Ôn tập Khái quát về Toán

Định nghĩa và tính chất của nhóm

Lý thuyết nhóm là nội dung nghiên cứu về đại số trừu tượng, nhưng một số ý tưởng về đại số trừu tượng lại rất quen thuộc với người lập trình. Tính kế thừa trong hướng đối tượng là một ví dụ điển hình, chúng ta đều biết rằng sau khi các lớp con kế thừa lớp cha, chúng có thể sử dụng các phương thức được định nghĩa trong lớp cha. Đại số trừu tượng có thể được hiểu là định nghĩa một số thuộc tính cho cấu trúc dữ liệu trừu tượng và các định lý rút ra từ các thuộc tính này đúng với tất cả các lớp con.

Sử dụng phép ẩn dụ vừa rồi, hãy xem cấu trúc dữ liệu của nhóm được xác định như thế nào.

Một nhóm bao gồm một phép toán (được biểu thị bằng bất kỳ phép toán nhị phân nào) và một số phần tử, thỏa mãn các thuộc tính sau:

Nhiều định lý thú vị có thể được suy ra từ đây:

Để đưa ra một vài ví dụ:

• Các số nguyên ..., −2, −1, 0, 1, 2, ... và cộng là một nhóm vì chúng thỏa mãn 4 tính chất trên
• Số nguyên và phép nhân không phải là nhóm vì không thỏa mãn tính khả nghịch, 4 x 1/4 = 1, nhưng 1/4 không phải là số nguyên

Thuật ngữ lý thuyết nhóm bị cắt bỏ

Định lý Lagrange

Bây giờ xin giới thiệu một định lý rất thú vị, nguồn gốc của định lý này nằm trong video được trích dẫn ở cuối bài viết.

** "Thứ tự của nhóm chia hết cho thứ tự của nhóm con."**

Tại sao định lý này thú vị, không chỉ vì quá trình chứng minh của nó kết nối rất nhiều kiến thức vừa được giới thiệu, mà còn vì những kết luận sau:

**“Nếu bậc của một nhóm là một số nguyên tố thì theo định lý Lagrange, bậc của nhóm con phải là hoặc. Các phần tử trong nhóm đều là sinh trừ

Triển khai Ed25519

Bây giờ hãy nói về Ed25519, một trong những thuật toán EdDSA. EdDSA có 11 tham số (việc lựa chọn cụ thể các tham số này có ảnh hưởng lớn đến tính bảo mật và hiệu suất của thuật toán. Để biết lựa chọn cụ thể của Ed25519, vui lòng tham khảo liên kết (

Ngoài ra, điều đáng nói là thuật toán này sử dụng một đường cong elip có tên là Curve25519 (. Đối với đường cong elip, chúng ta chỉ cần biết rằng có rất nhiều điểm trên đó và việc thêm các điểm này vào có thể nhận được các điểm mới. điểm mới vẫn còn Trên đường cong. Những điểm này và phần bổ sung này có thể tạo thành một nhóm. Lưu ý rằng phần bổ sung đường cong elip (được xác định đặc biệt.

Chúng tôi thống nhất về ký hiệu sau:

Đây là một thuật toán tương tác, nhưng không sao cả, có một thủ thuật gọi là Fiat - Shamir heuristic (Nó có thể chuyển bất kỳ thuật toán tương tác nào thành thuật toán không tương tác. Cuối cùng chúng ta sẽ sử dụng thuật toán không tương tác).

Thuật toán chữ ký điện tử sẽ cung cấp cho chúng ta API sau:

Triển khai KeyGen

Xuất khóa riêng và khóa chung:

1. Tạo ngẫu nhiên một hạt giống (hạt giống này có 32 byte. Chúng tôi sử dụng một bộ tạo số ngẫu nhiên an toàn bằng mật mã đi kèm với hệ thống.

pub fn tạo (csprng: &mut T) -> SecretKeywhere

T: CryptoRng + RngCore,

{

cho phép thay đổi: SecretKey = SecretKey([0u8; 32]);

csprng.fill_bytes(&mut sk.0);

sk

}

2. Mở rộng hạt giống vừa rồi thành 64 byte (nghĩa là xseed trong hình. 32 byte thấp của xseed là khóa riêng của chúng tôi (hay còn gọi là a). 32 byte cao được gọi là nonce, sẽ được sử dụng sau. Trong đó, chức năng của nó tương tự như domain sperator.

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

quán rượu(crate) nonce: [u8; 32], // nonce

}

fn từ (bí mật_key: &'a SecretKey) -> ExpandedSecretKey {

hãy biến h: Sha512 = Sha512::default();

hãy để hàm băm: [u8; 64] = [0u8; 64];

để mut thấp hơn: [u8; 32] = [0u8; 32];

hãy để mut trên: [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]);

// Bước này là kẹp

thấp hơn [0] &= 248;

thấp hơn [31] &= 63;

thấp hơn [31] |= 64;

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

}

3. Sử dụng khóa riêng để tạo khóa chung (khóa chung là một điểm trên đường elip. Cụ thể, chúng ta sử dụng điểm gốc của đường elip để thực hiện phép nhân đường elip để lấy khóa chung. Vô hướng trong phép nhân có được bằng cách ghép nối khóa riêng Thực hiện một hàm băm để lấy nó.

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

quán rượu(crate) nonce: [u8; 32], // nonce

}

fn từ (bí mật_key: &'a SecretKey) -> ExpandedSecretKey {

hãy biến h: Sha512 = Sha512::default();

hãy để hàm băm: [u8; 64] = [0u8; 64];

để mut thấp hơn: [u8; 32] = [0u8; 32];

hãy để mut trên: [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]);

// Bước này là kẹp

thấp hơn [0] &= 248;

thấp hơn [31] &= 63;

thấp hơn [31] |= 64;

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

}

Thực hiện Dấu hiệu

Ở đây bạn có thể đề cập đến kỹ thuật Fiat Shamir đã đề cập trước đó, thực tế bạn chỉ cần thay thế tất cả các số ngẫu nhiên do Trình xác minh cung cấp bằng kết quả của hàm băm. Xem nhận xét mã để biết chi tiết.

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

hãy biến h: Sha512 = Sha512::new();

để R: NénEdwardsY;

để r: Vô hướng;

hãy s: Vô hướng;

cho k: Vô hướng;

h.update(&self.nonce);

h.update(&tin nhắn);

r = Scalar::from_hash(h); // r là một số ngẫu nhiên trong thuật toán tương tác của chúng tôi, nhưng ở đây chúng tôi sử dụng hàm băm.

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(&tin nhắn);

k = Vô hướng::từ_hash(h); // h = Sha512(R || A || M)

s = &(&k * &self.key) + &r; // s = r + h * a, h ban đầu là một số ngẫu nhiên

Chữ ký nội bộ { R, s }.into()

}

Thực hiện Xác minh

trình xác minh hàm ý cho Khóa công khai {

#[allow(non_snake_case)]

fn xác minh (

&bản thân,

tin nhắn: & [u8] ,

chữ ký: &ed25519::Chữ ký

) -> Kết quả<(), Chữ kýError>

{

để chữ ký = InternalSignature::try_from(chữ ký)?;

hãy biến h: Sha512 = Sha512::new();

để R: EdwardsPoint;

cho k: Vô hướng;

để trừ_A: EdwardsPoint = -self.1;

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

h.update(self.as_bytes());

h.update(&tin nhắn);

k = Scalar::from_hash(h); // Cách tính h giống như trong dấu hiệu, h=Sha512(R||A||M)

R = EdwardsPoint::time_double_scalar_mul_basepoint(&k, &(minus_A), &signature.s); // R' = [s] B - [h] MỘT

if R.compress() == signature.R {// Nếu R'==R, thì kết quả xác minh là đúng.

Được rồi(())

} khác {

Err(InternalError::VerifyError.into())

}

}

}

mã địa chỉ (

Các vấn đề về khả năng mở rộng

Có nhiều điểm cần chú ý trong việc triển khai và sử dụng các thuật toán mật mã. Khi chúng ta nói rằng thuật toán chữ ký điện tử là an toàn, điều đó thường có nghĩa là ngay cả khi kẻ tấn công có thể lấy được chữ ký của bất kỳ thư nào (Tấn công thư được chọn), thì kẻ tấn công vẫn không thể giả mạo chữ ký. Ed25519 thỏa mãn tính chất này nhưng không có nghĩa là Ed25519 an toàn tuyệt đối. Nó cũng được đề cập trong bài báo gốc rằng vấn đề về khả năng mở rộng có thể chấp nhận được và thuật toán ban đầu có vấn đề này.

Bằng cách này, cả chữ ký mới và chữ ký cũ đều có thể được xác minh thành công. Vấn đề về tính linh hoạt cho chúng ta biết rằng chữ ký không mang tính xác định so với thông điệp và khóa công khai.

Theo tiêu chuẩn (thực tế là không có vấn đề về khả năng mở rộng. Bởi vì trong quá trình xác minh, chúng tôi sẽ kiểm tra xem nó có nhỏ hơn không, nếu kết quả kiểm tra không đúng thì xác minh không thành công. Nhưng tiêu chuẩn (xuất hiện muộn hơn giấy (vì vậy trong môi trường thực tế, vẫn có những triển khai Ed25519 có vấn đề về khả năng mở rộng và yêu cầu triển khai mà chúng tôi kiểm tra.

Tóm tắt

Cảm ơn

*Cảm ơn Safeheron, nhà cung cấp dịch vụ tự quản tài sản kỹ thuật số một cửa hàng đầu, đã cung cấp lời khuyên kỹ thuật chuyên nghiệp. *

> Tham khảo

> [1] .

> [2] .

> [3] .

> [4] .

> [5] . Các nhà nghiên cứu sử dụng lý thuyết nhóm để tăng tốc thuật toán — Giới thiệu về nhóm