XEdDSA – Chữ ký số tương thích khóa Diffie–Hellman

EdDSA là thuật toán chữ ký số tiên tiến sử dụng các đường cong Edwards, được thiết kế nhằm cung cấp hiệu suất cao và tính bảo mật mạnh mẽ.

Giới thiệu

Bài viết này mô tả cách tạo và xác minh chữ ký tương thích với EdDSA bằng cách sử dụng định dạng khóa công khai và khóa riêng ban đầu được xác định cho các hàm Diffie–Hellman đường cong elliptic X25519 và X448. Signal gọi đây là sơ đồ chữ ký XEdDSA (hoặc XEd25519 hoặc XEd448 đối với các đường cong cụ thể).

Lý do tồn tại của XEdDSA xuất phát từ một vấn đề kỹ thuật thực tiễn: các phép tính Diffie–Hellman phổ biến trên đường cong elliptic – đặc biệt là X25519 và X448 – làm việc với định dạng khóa Montgomery, trong đó khóa công khai là một tọa độ u trên đường cong Montgomery. Trong khi đó, chữ ký EdDSA được định nghĩa trên các đường cong Edwards xoắn, nơi khóa công khai là một điểm nén gồm tọa độ y và một bit dấu. Hai định dạng này không trực tiếp tương thích, buộc các ứng dụng muốn dùng cả Diffie–Hellman lẫn chữ ký phải duy trì hai cặp khóa riêng biệt – một giải pháp cồng kềnh về mặt quản lý khóa và lưu trữ. XEdDSA giải quyết vấn đề này bằng cách định nghĩa một phép chuyển đổi giữa hai định dạng khóa, cho phép cùng một cặp khóa Montgomery được dùng cho cả Diffie–Hellman lẫn ký số.

So sánh với các thuật toán chữ ký truyền thống như RSA, EdDSA mang đến nhiều lợi thế đáng kể: tốc độ ký và xác minh nhanh hơn nhiều, kích thước chữ ký nhỏ gọn (64 byte với Curve25519), và khả năng chống lại các cuộc tấn công bên kênh (side-channel attacks) tốt hơn do cấu trúc toán học đặc biệt của đường cong Edwards. Ứng dụng của XEdDSA trải rộng từ nhắn tin bảo mật đến các hệ thống blockchain, giao thức xác thực và các môi trường yêu cầu chữ ký số hiệu suất cao với tài nguyên tính toán hạn chế.

Bài viết này cũng mô tả VXEdDSA, một phần mở rộng của XEdDSA giúp nó trở thành một hàm ngẫu nhiên có thể xác minh (verifiable random function – VRF). Việc xác minh thành công một chữ ký VXEdDSA sẽ trả về một đầu ra VRF được đảm bảo là duy nhất cho thông điệp và khóa công khai. Đầu ra VRF cho một thông điệp và khóa công khai nhất định không thể phân biệt được với một giá trị ngẫu nhiên đối với bất kỳ ai chưa từng thấy chữ ký VXEdDSA của thông điệp và khóa đó.

Kiến thức cơ bản

Phần này đặt nền tảng toán học và ký hiệu cho toàn bộ đặc tả XEdDSA và VXEdDSA. Hiểu rõ các quy ước ký hiệu, thông số đường cong, phép chuyển đổi và các hàm mật mã là điều kiện tiên quyết để theo dõi chính xác các thuật toán ký và xác minh trong các phần tiếp theo.

Ký hiệu

Phép nhân hai số nguyên a và b theo modulo số nguyên tố p được ký hiệu là ab (mod p), hoặc a b (mod p). Phép chia được ký hiệu là a/b (mod p) và được tính bằng công thức ab⁻¹ (mod p). Hàm inv(a) (mod p) được định nghĩa để trả về a⁻¹ (mod p) khi a khác 0, và trả về 0 khi a bằng 0. Điều này có thể được tính bằng công thức inv(a) = a^(p – 2) (mod p) theo định lý Fermat nhỏ – một kết quả toán học cổ điển đảm bảo tính đúng đắn của phép tính nghịch đảo trong trường số nguyên tố. Hàm ceil và floor lần lượt làm tròn lên hoặc làm tròn xuống đến số nguyên gần nhất.

Phép cộng và trừ giữa hai điểm A và B trên đường cong elliptic được ký hiệu là A + B và A – B. Phép nhân vô hướng (scalar multiplication) của một số nguyên a với một điểm đường cong elliptic B tạo ra điểm mới C = aB, là kết quả của việc cộng điểm B với chính nó a lần. Phép nhân vô hướng là phép toán cốt lõi của mật mã đường cong elliptic và độ khó tính toán của bài toán logarit rời rạc trên đường cong elliptic (tức là tìm a từ B và C = aB) là nền tảng bảo mật của toàn bộ lớp thuật toán này.

Các biến số nguyên được viết thường (x, y); các điểm và biến khác được viết hoa (P, Q); các hằng số nguyên được viết thường ngoại trừ hằng số A của đường cong Montgomery theo quy ước. Chuỗi byte được viết in đậm (x, P). Một số nguyên in đậm hoặc một điểm đường cong elliptic biểu thị một chuỗi byte có độ dài cố định mã hóa giá trị của nó. Một số nguyên được viết in đậm biểu thị một chuỗi byte dài b bit, mã hóa số nguyên theo dạng little-endian – byte có giá trị nhỏ nhất được đặt trước. Một điểm trên đường cong elliptic được viết in đậm mã hóa tọa độ P.y dưới dạng số nguyên little-endian với độ dài b – 1 bit, sau đó thêm một bit để lưu trữ giá trị P.s. Phép nối chuỗi byte x và P được ký hiệu là x || P. Việc kiểm tra hai số nguyên hoặc hai điểm có bằng nhau không được thực hiện bằng biểu thức a == b; việc kiểm tra hai chuỗi byte có bằng nhau không được thực hiện bằng bytes_equal(X, Y) – sự phân biệt này quan trọng vì phép so sánh chuỗi byte cần thực hiện theo thời gian cố định để tránh tấn công qua timing channel.

Thông số đường cong Elliptic

Một đường cong elliptic được sử dụng với XEdDSA hoặc VXEdDSA có các thông số sau: B là điểm cơ sở (base point); I là điểm đơn vị (identity point); p là số nguyên tố trường (field prime); q là bậc của điểm cơ sở (số nguyên tố; q < p; qB = I); c là hệ số (cofactor); d là hằng số đường cong Edwards xoắn (twisted Edwards curve constant); A là hằng số đường cong Montgomery; n là số nguyên không phải là bình phương theo modulo p. Các đại lượng |p| = ceil(log₂(p)) và |q| = ceil(log₂(q)) biểu thị số bit cần thiết để biểu diễn p và q tương ứng. Độ dài bit b = 8 × ceil((|p| + 1)/8) là độ dài bit chuẩn cho điểm hoặc số nguyên được mã hóa.

Một số nguyên theo modulo p được gọi là phần tử trường (field element). Một số nguyên theo modulo q được gọi là số vô hướng (scalar). Một đường cong elliptic là một tập hợp các cặp phần tử trường, mỗi cặp là một điểm với các thành phần là tọa độ, và tọa độ của mỗi điểm phải thỏa mãn một phương trình xác định đường cong. Hàm on_curve(P) trả về true nếu điểm P thỏa mãn phương trình đường cong. Đường cong elliptic còn định nghĩa một phép cộng giữa các điểm và một phép lấy đối điểm (negation). Cùng với điểm đơn vị, các phép toán này tạo thành một cấu trúc nhóm Abel trên các điểm của đường cong.

XEdDSA và VXEdDSA được định nghĩa trên các đường cong Edwards xoắn (twisted Edwards curves), trong đó các điểm được ký hiệu là (x, y). Một đường cong Edwards xoắn tương đương song hữu tỷ với một đường cong Montgomery, trong đó các điểm được ký hiệu là (u, v). Signal chủ yếu làm việc với đường cong Edwards xoắn, vì vậy khi đề cập đến điểm cơ sở B và điểm đơn vị I, Signal đang nói về các điểm trên đường cong Edwards xoắn. Hàm u_to_y áp dụng một phép biến đổi song hữu tỷ cụ thể cho đường cong để chuyển đổi tọa độ u của một điểm trên đường cong Montgomery thành tọa độ y của điểm tương đương trên đường cong Edwards xoắn. Mối quan hệ tương đương song hữu tỷ (birational equivalence) giữa hai dạng đường cong là nền tảng toán học cho phép XEdDSA dùng chung định dạng khóa giữa Diffie–Hellman (Montgomery) và chữ ký (Edwards).

Chuyển đổi đường cong Elliptic

Phép tính Diffie–Hellman trên đường cong elliptic thường được thực hiện bằng phương pháp Montgomery ladder – một thuật toán tính nhân vô hướng đặc biệt hiệu quả trên đường cong Montgomery. Cách tiếp cận này cung cấp phép tính đơn giản và hiệu quả, đồng thời có khả năng chống lại các kênh rò rỉ thời gian (timing side-channel) một cách tự nhiên vì số lượng phép tính không phụ thuộc vào giá trị cụ thể của số vô hướng. Montgomery ladder còn cho phép khóa công khai của mỗi bên là một tọa độ u duy nhất trên đường cong Montgomery thay vì toàn bộ điểm, giúp giảm kích thước khóa công khai mà không cần đến quá trình giải mã điểm phức tạp.

Tuy nhiên, chữ ký EdDSA được định nghĩa trên đường cong Edwards xoắn, nơi khóa công khai là một điểm nén gồm tọa độ y và bit dấu s (bằng 0 hoặc 1). Để giải quyết sự không tương thích giữa hai định dạng, hàm convert_mont thực hiện chuyển đổi từ tọa độ u Montgomery sang điểm trên đường cong Edwards. Hàm này trước tiên loại bỏ các bit cao dư thừa khỏi u (một thực hành tiêu chuẩn đối với khóa công khai Curve25519), sau đó áp dụng phép biến đổi song hữu tỷ để tính tọa độ y, cuối cùng ép bit dấu về 0.

convert_mont(u):
	umasked = u (mod 2|p|)
	P.y = u_to_y(umasked)
	P.s = 0
return P

Quyết định ép bit dấu về 0 xuất phát từ thực tế là convert_mont không có giá trị v của đường cong Montgomery nên không thể phân biệt được hai khả năng khác nhau của bit dấu – ý tưởng này từ Jivsov. Để làm cho khóa riêng tương thích với phép chuyển đổi này, Signal định nghĩa khóa riêng trên đường cong Edwards là một số vô hướng a sao cho khóa công khai Edwards tương ứng A = aB có bit dấu bằng 0. Hàm calculate_key_pair thực hiện chuyển đổi từ khóa riêng Montgomery sang cặp khóa Edwards:

calculate_key_pair(k):
	E = kB
	A.y = E.y
	A.s = 0
	if E.s == 1:
		a = – k (mod q)
	else:
		a = k (mod q)
	return A, a

Nếu nhân khóa riêng Montgomery k với điểm cơ sở Edwards B cho kết quả điểm E có bit dấu bằng 1, khóa riêng Edwards được điều chỉnh thành –k (mod q), đảm bảo khóa công khai tương ứng có bit dấu bằng 0. Tính nhất quán này là điều kiện để convert_mont và calculate_key_pair cho kết quả tương thích: cùng một khóa công khai Montgomery sẽ luôn cho ra cùng một điểm Edwards sau khi áp dụng cả hai hàm.

Hàm băm

XEdDSA và VXEdDSA yêu cầu một hàm băm mật mã. Hàm băm mặc định là SHA512 – lựa chọn cân bằng giữa độ bảo mật (256 bit bảo mật chống tấn công collision) và hiệu suất thực tiễn trên phần cứng hiện đại. Signal định nghĩa hash là một hàm áp dụng thuật toán băm mật mã lên một chuỗi byte đầu vào, và trả về một số nguyên là kết quả của hàm băm được phân tích dưới dạng little-endian.

Dựa vào hash và các hằng số đường cong p và b, Signal định nghĩa một họ các hàm băm được đánh số bởi các số nguyên không âm i, sao cho 2^(|p|) – 1 – i > p:

hashi(X):
	return hash(2b – 1 – i || X)

Vì vậy, hash0 băm một chuỗi gồm b/8 byte có giá trị 0xFF trước chuỗi byte đầu vào X; hash1 thay đổi byte đầu tiên thành 0xFE; hash2 thay đổi byte đầu tiên thành 0xFD;… Các hàm hashi khác nhau được sử dụng cho các mục đích khác nhau nhằm cung cấp khả năng phân tách miền mật mã (domain separation). Kỹ thuật phân tách miền đảm bảo rằng cùng một đầu vào khi đưa qua các hàm hashi khác nhau sẽ cho ra các đầu ra độc lập nhau về mặt mật mã, ngăn chặn các cuộc tấn công chéo miền (cross-domain attack) trong đó kẻ tấn công cố gắng sử dụng đầu ra của hàm băm từ một ngữ cảnh để giả mạo trong một ngữ cảnh khác.

Cần lưu ý rằng hashi sẽ không bao giờ gọi hash với b bit đầu tiên mã hóa một số vô hướng hợp lệ hoặc một điểm trên đường cong elliptic, vì |p| bit đầu tiên mã hóa một số nguyên lớn hơn p – điều này loại bỏ khả năng nhầm lẫn giữa các tiền tố phân tách miền với các giá trị dữ liệu hợp lệ. Ngoài ra, hash0 được dành cho các đặc tả khác và không được sử dụng trong bài viết này, đảm bảo không có xung đột với các giao thức khác có thể tái sử dụng cùng cấu trúc phân tách miền.

Hàm băm thành điểm với Elligator 2

VXEdDSA yêu cầu ánh xạ một thông điệp đầu vào thành một điểm trên đường cong elliptic – thao tác được gọi là hash-to-curve (băm thành điểm). Đây là một bài toán không tầm thường: không thể đơn giản lấy một giá trị băm và giải thích nó là tọa độ của một điểm hợp lệ, vì không phải mọi giá trị đều tương ứng với một điểm trên đường cong. Phương pháp Elligator 2 giải quyết bài toán này bằng cách định nghĩa một ánh xạ xác định từ số nguyên sang điểm đường cong.

Phương trình đường cong Montgomery đối với các điểm (u, v) là v² = u(u² + Au + 1) (mod p), trong đó A là hằng số cụ thể của đường cong. Elligator 2 ánh xạ một số nguyên r thành giá trị u sao cho u(u² + Au + 1) có căn bậc hai v theo modulo p.

elligator2(r):
	u1 = – A inv(1 + nr²) (mod p)
	w1 = u1(u1² + Au1 + 1) (mod p)
	if w1^(p – 1)/2 == – 1 (mod p):
		u2 = – A – u1 (mod p)
		return u2
	return u1

Hàm hash_to_point kết hợp băm mật mã với Elligator 2 và phép biến đổi song hữu tỷ để ánh xạ một chuỗi byte tùy ý thành một điểm trên đường cong Edwards:

hash_to_point(X):
	h = hash2(X)
	r = h (mod 2|p|)
	s = floor((h mod 2b) / 2b – 1)
	u = elligator2(r)
	P.y = u_to_y(u)
	P.s = s
	return cP

Việc nhân điểm kết quả với hệ số c (cofactor) ở bước cuối đảm bảo điểm đầu ra thuộc về tập con bậc q được tạo ra bởi điểm cơ sở B – điều kiện cần thiết để các phép tính chữ ký và xác minh hoạt động chính xác. Nếu bỏ qua bước nhân với c, điểm có thể thuộc về một tập con nhỏ hơn của nhóm điểm, mở ra các cuộc tấn công dựa trên cấu trúc nhóm con nhỏ (small subgroup attack). Hàm hash2 được dùng ở đây nhằm mục đích phân tách miền, đảm bảo ánh xạ hash-to-curve này không bị nhầm lẫn với các hàm băm khác trong giao thức.

XEdDSA

XEdDSA là sơ đồ chữ ký cho phép ký và xác minh bằng định dạng khóa Montgomery, tương thích với EdDSA nhưng không yêu cầu duy trì cặp khóa riêng biệt cho mỗi mục đích. Đây là thành phần cốt lõi cho phép Signal Protocol dùng chung khóa cho cả trao đổi Diffie–Hellman và chữ ký số.

Thuật toán ký XEdDSA

Thuật toán ký XEdDSA yêu cầu ba đầu vào: khóa riêng Montgomery k (số nguyên theo modulo q), thông điệp cần ký M (chuỗi byte), và 64 byte dữ liệu ngẫu nhiên bảo mật Z (chuỗi byte). Đầu ra là một chữ ký (R || s), chuỗi byte có độ dài 2b bit, trong đó R mã hóa một điểm và s mã hóa một số nguyên theo modulo q.

xeddsa_sign(k, M, Z):
	A, a = calculate_key_pair(k)
	r = hash1(a || M || Z) (mod q)
	R = rB
	h = hash(R || A || M) (mod q)
	s = r + ha (mod q)
	return R || s

Cấu trúc của thuật toán bám sát sơ đồ chữ ký Schnorr: hàm băm hash1 tạo ra một số vô hướng ngẫu nhiên r từ khóa riêng Edwards a, thông điệp M và entropy bổ sung Z; điểm R = rB là phần đầu của chữ ký; giá trị thử thách h được tính bằng cách băm R, khóa công khai A và thông điệp M; cuối cùng s = r + ha (mod q) là phần số nguyên của chữ ký. Ý nghĩa bảo mật của cấu trúc này: nếu ai đó biết h, s và A, họ có thể xác minh rằng người ký biết a mà không cần tiết lộ a – đây là tính chất zero-knowledge của chữ ký Schnorr. Việc bổ sung entropy Z vào tính toán r ngăn chặn tấn công khi cùng một r được dùng hai lần với thông điệp khác nhau, một lỗi có thể dẫn đến lộ khóa riêng.

Việc gọi calculate_key_pair trong mỗi lần ký làm tăng chi phí tính toán một phép nhân vô hướng so với EdDSA thông thường, vì calculate_key_pair thực hiện phép tính E = kB. Để giảm chi phí này trong các ứng dụng ký nhiều lần, bên ký có thể lưu vào bộ nhớ đệm điểm E (không phải bí mật) để tránh tính toán lại, trong khi vẫn thực hiện bước điều chỉnh bit dấu và tính a từ đó. Tối ưu hóa này đặc biệt quan trọng trên thiết bị có tài nguyên tính toán hạn chế như điện thoại thông minh hay thiết bị IoT.

Thuật toán xác minh XEdDSA

Thuật toán xác minh XEdDSA yêu cầu ba đầu vào: khóa công khai Montgomery u (chuỗi byte độ dài b bit), thông điệp cần xác minh M (chuỗi byte), và chữ ký (R || s) (chuỗi byte độ dài 2b bit). Nếu xác minh thành công thuật toán trả về true; ngược lại trả về false.

xeddsa_verify(u, M, (R || s)):
	if u >= p or R.y >= 2|p| or s >= 2|q|:
		return false
	A = convert_mont(u)
	if not on_curve(A):
		return false
	h = hash(R || A || M) (mod q)
	Rcheck = sB – hA
	if bytes_equal(R, Rcheck):
		return true
	return false

Bước kiểm tra biên (boundary check) đầu tiên từ chối ngay các đầu vào có giá trị không hợp lệ: u phải nhỏ hơn p để là một phần tử trường hợp lệ; tọa độ y của R phải nhỏ hơn 2^|p|; s phải nhỏ hơn 2^|q| để không có bit dư thừa. Những kiểm tra này ngăn chặn các cuộc tấn công dựa trên các giá trị biên đặc biệt và đảm bảo tính xác định của quá trình xác minh. Sau khi chuyển đổi khóa công khai Montgomery u thành điểm Edwards A, thuật toán tính lại giá trị thử thách h và kiểm tra xem phương trình xác minh sB = R + hA có thỏa mãn không, hay tương đương Rcheck = sB – hA có bằng R không. Sự đúng đắn của thuật toán dựa trên tính tuyến tính của nhân điểm: nếu chữ ký hợp lệ thì s = r + ha nên sB = rB + haB = R + hA.

Đặc tính bảo mật của XEdDSA

Bảo mật của XEdDSA dựa trên giả định bài toán logarit rời rạc trên đường cong elliptic (ECDLP) là khó giải. Cụ thể hơn, không ai có thể tính được khóa riêng a từ khóa công khai A = aB trong thời gian đa thức. Trong mô hình oracle ngẫu nhiên (random oracle model) – khi hàm băm được mô hình hóa như một oracle ngẫu nhiên lý tưởng – XEdDSA là an toàn theo nghĩa EUF-CMA (existential unforgeability under chosen-message attacks): kẻ tấn công không thể tạo ra chữ ký hợp lệ cho bất kỳ thông điệp nào, ngay cả sau khi quan sát nhiều cặp (thông điệp, chữ ký) hợp lệ.

Một đặc tính bảo mật quan trọng của XEdDSA là tính ngẫu nhiên của chữ ký: hai lần ký cùng một thông điệp với cùng khóa riêng sẽ cho kết quả khác nhau vì Z là ngẫu nhiên mỗi lần. Điều này khác với các sơ đồ chữ ký xác định như EdDSA gốc (RFC 8032), nơi r được tính xác định từ khóa riêng và thông điệp. Cả hai cách tiếp cận đều có ưu và nhược điểm: chữ ký xác định tránh hoàn toàn rủi ro từ nguồn ngẫu nhiên yếu nhưng dễ bị tấn công nếu cùng r được dùng lại do lỗi triển khai; chữ ký ngẫu nhiên như XEdDSA cần nguồn ngẫu nhiên đủ mạnh nhưng bổ sung thêm lớp bảo vệ chống lại các tấn công yêu cầu ký nhiều lần. XEdDSA kết hợp cả hai bằng cách băm khóa riêng và thông điệp cùng với Z, thu được ưu điểm của cả hai cách tiếp cận.

VXEdDSA

VXEdDSA mở rộng XEdDSA để tạo thành một hàm ngẫu nhiên có thể xác minh (VRF – Verifiable Random Function). Đây là một primitive mật mã cho phép bên ký tạo ra một đầu ra ngẫu nhiên có thể chứng minh tính hợp lệ cho bất kỳ ai, trong khi không ai khác có thể dự đoán hay tính toán đầu ra đó mà không có khóa riêng.

Hàm ngẫu nhiên có thể xác minh

Một hàm ngẫu nhiên có thể xác minh (VRF) là một cặp hàm (sign, verify) thỏa mãn ba tính chất cốt lõi. Thứ nhất là tính duy nhất (uniqueness): với mọi khóa công khai và thông điệp nhất định, có duy nhất một đầu ra VRF hợp lệ. Điều này có nghĩa là không thể tạo ra hai bằng chứng khác nhau cho cùng một thông điệp và khóa mà đều được chấp nhận bởi hàm xác minh và cho ra đầu ra VRF khác nhau. Thứ hai là tính giả ngẫu nhiên (pseudorandomness): đầu ra VRF không thể phân biệt được với một giá trị ngẫu nhiên thực sự đối với bất kỳ ai không biết khóa riêng và chưa thấy bằng chứng xác minh. Thứ ba là tính có thể xác minh (verifiability): bất kỳ ai có khóa công khai đều có thể xác minh rằng đầu ra VRF được tính đúng từ thông điệp bằng khóa riêng tương ứng.

Ứng dụng quan trọng nhất của VRF trong bối cảnh Signal Protocol là tạo ra các giá trị ngẫu nhiên có thể kiểm chứng mà không cần bên tạo ra chúng phải tiết lộ nguồn gốc. Điều này đặc biệt hữu ích trong các giao thức nhóm và quản lý định danh, nơi cần đảm bảo tính nhất quán và không thể giả mạo của các giá trị ngẫu nhiên mà không tiết lộ thông tin bí mật. VXEdDSA cụ thể hóa VRF bằng cách tích hợp trực tiếp với cặp khóa Montgomery, cho phép cùng một khóa thực hiện ba chức năng: Diffie–Hellman, chữ ký (qua XEdDSA) và VRF (qua VXEdDSA).

Thuật toán ký và xác minh VXEdDSA

Thuật toán ký VXEdDSA có các đầu vào giống như XEdDSA. Đầu ra gồm hai phần: chữ ký (V || h || s) có độ dài 3b bit, trong đó V mã hóa một điểm và h cùng s mã hóa các số nguyên theo modulo q; và chuỗi byte đầu ra VRF v có độ dài b bit, được tính bằng cách nhân đầu ra V với hệ số c.

vxeddsa_sign(k, M, Z):
	A, a = calculate_key_pair(k)
	Bv = hash_to_point(A || M)
	V = aBv
	r = hash3(a || V || Z) (mod q)
	R = rB
	Rv = rBv
	h = hash4(A || V || R || Rv || M) (mod q)
	s = r + ha (mod q)
	v = hash5(cV) (mod 2b)
	return (V || h || s), v

Điểm mấu chốt trong cấu trúc VXEdDSA là điểm Bv = hash_to_point(A || M) – một điểm đường cong được tính xác định từ khóa công khai và thông điệp. Điểm V = aBv là kết quả nhân điểm này với khóa riêng a, và đây chính là cơ sở của đầu ra VRF: vì Bv được tính công khai từ khóa công khai và thông điệp, bất kỳ ai cũng có thể tính Bv; nhưng chỉ người biết a mới có thể tính V = aBv. Đầu ra VRF v = hash5(cV) là duy nhất cho mỗi cặp (khóa, thông điệp) vì tính duy nhất của V – và không thể dự đoán được vì hàm băm hash5 làm mờ cấu trúc điểm.

vxeddsa_verify(u, M, (V || h || s)):
	if u >= p or V.y >= 2|p| or h >= 2|q| or s >= 2|q|:
		return false
	A = convert_mont(u)
	Bv = hash_to_point(A || M)
	if not on_curve(A) or not on_curve(V):
		return false
	if cA == I or cV == I or Bv == I:
		return false
	R = sB – hA
	Rv = sBv – hV
	hcheck = hash4(A || V || R || Rv || M) (mod q)
	if bytes_equal(h, hcheck):
		v = hash5(cV) (mod 2b)
		return v
	return false

Tính chất đầu ra VRF

Tính duy nhất của đầu ra VRF trong VXEdDSA xuất phát từ ECDLP: nếu tồn tại hai giá trị V và V’ đều vượt qua xác minh cho cùng một (thông điệp, khóa), thì từ V = aBv và V’ = a’Bv ta suy ra a = a’ (mod q) – điều này mâu thuẫn với giả định ECDLP nếu a ≠ a’. Tính giả ngẫu nhiên của đầu ra bảo đảm rằng v = hash5(cV) không thể phân biệt được với giá trị ngẫu nhiên bởi bất kỳ kẻ tấn công nào không biết a, vì điều đó đồng nghĩa với việc kẻ tấn công có thể tính V từ khóa công khai và Bv – lại mâu thuẫn với ECDLP.

Kiểm tra cA == I, cV == I, Bv == I trong xác minh loại bỏ các trường hợp điểm đặc biệt có thể bị khai thác. Nếu cA = I (điểm đơn vị nhân với hệ số), thì A thuộc về tập con nhỏ của nhóm điểm, có thể cho phép tấn công dựa trên nhóm con nhỏ (small subgroup attack). Tương tự, cV = I hay Bv = I chỉ ra các trường hợp suy biến không nên xuất hiện trong hoạt động bình thường và có thể là dấu hiệu của đầu vào được chế tạo đặc biệt để tấn công. Các kiểm tra này đảm bảo xác minh chỉ thành công cho các đầu vào thực sự hợp lệ trong bối cảnh sử dụng đúng đắn.

Curve25519

Đường cong elliptic Curve25519 là lựa chọn mặc định và phổ biến nhất cho XEdDSA và VXEdDSA, tạo thành XEd25519 và VXEd25519. Đây là đường cong được thiết kế bởi Daniel Bernstein (1971–) với mục tiêu tối ưu hóa đồng thời cho hiệu suất phần mềm, an toàn triển khai và bảo mật mật mã.

Tham số và phương trình đường cong

Curve25519 xác định các tham số sau cho XEdDSA: điểm cơ sở B = convert_mont(9); điểm đơn vị I = (x=0, y=1); số nguyên tố trường p = 2²⁵⁵ – 19 (một số Mersenne gần, được chọn vì cho phép tối ưu hóa đặc biệt trong phép nhân modulo); bậc điểm cơ sở q = 2²⁵² + 27742317777372353535851937790883648493; hệ số c = 8; hằng số Edwards xoắn d = –121665 / 121666 (mod p); hằng số Montgomery A = 486662; tham số Elligator n = 2; độ dài bit |p| = 255, |q| = 253, b = 256.

Phương trình đường cong Edwards xoắn tương ứng là:

– x² + y² = 1 + dx²y²

Hàm u_to_y thực hiện phép biến đổi song hữu tỷ từ tọa độ Montgomery sang Edwards bằng cách tính:

y = (u – 1) * inv(u + 1) (mod p)

Đây là phép biến đổi Möbius (phân tuyến) cổ điển giữa hai dạng đường cong. Giá trị p = 2²⁵⁵ – 19 được chọn đặc biệt vì phép giảm modulo có thể thực hiện hiệu quả bằng cách khai thác cấu trúc số Mersenne gần: thay vì thực hiện phép chia thực sự, phần mềm có thể dùng các phép dịch bit và cộng, cho phép Curve25519 đạt được hiệu suất ký và trao đổi khóa rất cao ngay cả trên phần cứng không có phần mở rộng mật mã đặc biệt.

Quan hệ với Ed25519

Chữ ký XEd25519 là chữ ký Ed25519 hợp lệ và ngược lại, với điều kiện khóa công khai được chuyển đổi bằng phép biến đổi song hữu tỷ. Cụ thể: nếu lấy khóa riêng Montgomery k và tạo cặp khóa Edwards (A, a) bằng calculate_key_pair, sau đó ký thông điệp M bằng xeddsa_sign, chữ ký thu được là chữ ký Ed25519 hợp lệ cho khóa công khai A và thông điệp M. Ngược lại, mọi chữ ký Ed25519 hợp lệ cũng là chữ ký XEd25519 hợp lệ, miễn là khóa công khai Edwards tương ứng có bit dấu bằng 0.

Điều này có ý nghĩa quan trọng về khả năng tương tác: các thư viện triển khai Ed25519 theo tiêu chuẩn có thể xác minh chữ ký XEd25519 mà không cần sửa đổi, chỉ cần thực hiện bước chuyển đổi khóa công khai từ Montgomery sang Edwards trước. Tính tương thích ngược này giảm đáng kể công sức tích hợp cho các ứng dụng đã có cơ sở hạ tầng Ed25519.

Những điểm khác biệt trong xác minh

Ed25519 cho phép các triển khai có một số linh hoạt trong việc chấp nhận hoặc từ chối một số chữ ký không hợp lệ nhất định: chữ ký với s chưa được giảm hoàn toàn theo modulo q, hoặc kiểm tra phương trình xác minh có hoặc không nhân hệ số c. Sự linh hoạt này dẫn đến tình trạng các triển khai Ed25519 khác nhau có thể không nhất quán trong việc chấp nhận hay từ chối cùng một chữ ký.

XEdDSA quy định chính xác quy trình xác minh để đảm bảo tính xác định: từ chối s nếu nó có các bit dư thừa nhưng không yêu cầu nó phải được giảm hoàn toàn; kiểm tra phương trình xác minh mà không cần nhân hệ số c. Những lựa chọn này được thiết kế để phù hợp với đa số các triển khai Ed25519 hiện có trong thực tế – đặc biệt là các triển khai dựa trên thư viện libsodium và SUPERCOP – đồng thời tránh các trường hợp biên có thể dẫn đến hành vi không nhất quán giữa các triển khai khác nhau. Điều này quan trọng đặc biệt trong các hệ thống nhắn tin phân tán nơi hai phía có thể dùng các triển khai khác nhau nhưng vẫn cần có kết quả xác minh nhất quán.

Curve448

Đường cong elliptic Curve448 là lựa chọn thứ hai cho XEdDSA và VXEdDSA, tạo thành XEd448 và VXEd448. Curve448 cung cấp mức độ bảo mật cao hơn đáng kể so với Curve25519 – khoảng 224 bit bảo mật so với khoảng 128 bit – đổi lại là chữ ký và khóa công khai có kích thước lớn hơn, và tốc độ thực hiện chậm hơn. Curve448 được thiết kế bởi Mike Hamburg và đã được NIST lựa chọn cùng với Curve25519 như các đường cong được khuyến nghị trong FIPS 186-5.

Tham số và phương trình đường cong

Curve448 xác định các tham số sau: điểm cơ sở B = convert_mont(5); điểm đơn vị I = (x=0, y=1); số nguyên tố trường p = 2⁴⁴⁸ – 2²²⁴ – 1 (còn gọi là số nguyên tố Goldilocks vì có cấu trúc đặc biệt thuận tiện cho tính toán phần cứng); bậc điểm cơ sở q = 2⁴⁴⁶ – 13818066809895115352007386748515426880336692474882178609894547503885; hệ số c = 4; hằng số Edwards xoắn d = 39082 / 39081 (mod p); hằng số Montgomery A = 156326; tham số Elligator n = –1; độ dài bit |p| = 448, |q| = 446, b = 456.

Phương trình đường cong Edwards xoắn là:

x² + y² = 1 + dx²y²

Hàm u_to_y thực hiện phép biến đổi song hữu tỷ bằng cách tính:

y = (1 + u) * inv(1 – u) (mod p)

Lưu ý rằng phương trình đường cong Edwards cho Curve448 khác với Curve25519 ở dấu của số hạng x²: Curve25519 dùng –x² (đường cong Edwards xoắn) trong khi Curve448 dùng +x² (đường cong Edwards không xoắn). Sự khác biệt này phản ánh hai dạng chuẩn hóa khác nhau của phương trình Edwards và không ảnh hưởng đến các tính chất bảo mật cốt lõi.

So sánh với Curve25519

Mức bảo mật 224 bit của Curve448 so với 128 bit của Curve25519 có ý nghĩa thực tiễn trong bối cảnh điện toán lượng tử: thuật toán Grover giảm mức bảo mật của các bài toán khó về bình phương, đưa 128 bit bảo mật cổ điển xuống còn khoảng 64 bit bảo mật lượng tử, trong khi 224 bit cổ điển vẫn cho 112 bit lượng tử. Đối với các ứng dụng yêu cầu bảo vệ thông tin trong thời gian rất dài (hàng thập kỷ) hoặc trước các đối thủ có tài nguyên tính toán lượng tử, Curve448 cung cấp biên an toàn lớn hơn đáng kể.

Đổi lại, Curve448 tạo ra chữ ký lớn hơn (114 byte thay vì 64 byte với XEd25519), khóa công khai lớn hơn (57 byte thay vì 32 byte), và tốc độ ký và xác minh chậm hơn khoảng 4–5 lần trên phần mềm thông thường. Đối với hầu hết các ứng dụng nhắn tin thời gian thực, mức bảo mật của Curve25519 là hoàn toàn đủ trong thời gian tới. Curve448 phù hợp hơn cho các ứng dụng cần bảo vệ dữ liệu rất dài hạn, các hệ thống chính phủ với yêu cầu bảo mật đặc biệt cao, hay các môi trường lo ngại sớm về mối đe dọa lượng tử.

Sự khác biệt với các đề xuất EdDSA khác

XEd448 khác với một số phương án triển khai EdDSA trên Curve448 được đề xuất trong các tài liệu khác ở hai điểm quan trọng. Thứ nhất là lựa chọn hàm băm: XEd448 sử dụng SHA512, trong khi một số đề xuất khác khuyến nghị sử dụng hàm băm có độ dài 912 bit (tức 2b) như SHAKE256 hay các biến thể Keccak. Nếu hàm băm thực sự là bảo mật, các đầu ra có độ dài lớn hơn 512 bit không làm tăng mức độ bảo mật với Curve448 – vì mức bảo mật của thuật toán chữ ký bị giới hạn bởi ECDLP, không phải bởi kích thước đầu ra hàm băm. Do đó, XEd448 chọn SHA512 như phương pháp đơn giản hơn mà không hi sinh bảo mật.

Thứ hai là lựa chọn đường cong: một số đề xuất EdDSA trên Curve448 sử dụng đường cong 4-isogenous từ Goldilocks thay vì đường cong song hữu tỷ tương đương (birationally equivalent) mà XEdDSA sử dụng. Việc ánh xạ từ dạng Montgomery của Curve448 sang đường cong 4-isogenous phức tạp hơn đáng kể và yêu cầu triển khai cẩn thận hơn để tránh lỗi. XEd448 chọn dạng song hữu tỷ vì tính đơn giản của phép biến đổi, dù hai cách tiếp cận về cơ bản tương đương về bảo mật.

Các yếu tố ảnh hưởng đến hiệu suất

Phần này trình bày phân tích các yếu tố ảnh hưởng đến hiệu suất của XEdDSA và VXEdDSA – không phải danh sách đầy đủ mà là các điểm quan trọng nhất cần xem xét khi thiết kế và tối ưu hóa triển khai trong môi trường thực tế.

Chi phí tính toán khi ký

Chi phí tính toán khi ký XEdDSA cao hơn EdDSA thông thường do bước calculate_key_pair thực hiện thêm một phép nhân vô hướng E = kB. Phép nhân vô hướng với điểm cơ sở là thao tác tốn kém nhất trong mật mã đường cong elliptic: trên phần mềm hiện đại, một phép nhân X25519 mất khoảng 100–200 microsecond trên CPU thông thường và lâu hơn nhiều trên vi điều khiển hay thiết bị di động cũ. Việc thêm một phép nhân vô hướng trong calculate_key_pair làm tăng thời gian ký lên khoảng 40–60% so với Ed25519.

Chiến lược giảm thiểu đơn giản nhất là lưu bộ nhớ đệm điểm E sau lần tính đầu tiên. Vì E = kB chỉ phụ thuộc vào khóa riêng k (không phải thông điệp hay dữ liệu ngẫu nhiên), giá trị này có thể được tính một lần khi tải khóa vào bộ nhớ và tái sử dụng cho tất cả các lần ký tiếp theo. Điểm E không phải là bí mật (nó tương đương với khóa công khai) nên việc lưu trữ trong bộ nhớ thông thường là an toàn. Tối ưu hóa này loại bỏ hoàn toàn overhead của calculate_key_pair trong trường hợp ký nhiều lần với cùng một khóa, đưa hiệu suất về ngang bằng Ed25519.

Ký VXEdDSA tốn kém hơn đáng kể vì cần tính thêm Bv = hash_to_point(A || M) và V = aBv – hai thao tác phụ thuộc vào thông điệp và không thể lưu bộ nhớ đệm. Hàm hash_to_point đòi hỏi một phép băm mật mã và một phép tính Elligator 2 (chứa phép tính lũy thừa modulo để kiểm tra căn bậc hai). Phép nhân V = aBv là một phép nhân vô hướng đầy đủ với điểm không cố định (không phải điểm cơ sở), thường chậm hơn đáng kể so với nhân với điểm cơ sở vì không thể dùng các bảng tra cứu được tối ưu hóa sẵn.

Vấn đề tiền băm

Ngoại trừ xác minh XEdDSA, các thuật toán ký và xác minh của VXEdDSA đều băm thông điệp đầu vào hai lần trong các ngữ cảnh khác nhau. Đối với các thông điệp lớn, điều này có thể tốn kém cả về thời gian lẫn yêu cầu bộ nhớ: nếu thông điệp không thể nạp toàn bộ vào bộ nhớ, cần có cơ chế xử lý luồng (streaming) hoặc chia nhỏ, điều này làm phức tạp API của hàm ký.

Các nhà thiết kế giao thức có thể quy định tiền băm (prehashing) các trường thông điệp lớn để phù hợp với giới hạn kích thước này: thay vì ký toàn bộ nội dung thư, ứng dụng có thể tiền băm các tệp đính kèm lớn và chỉ ký cấu trúc thông điệp (gồm tiêu đề, siêu dữ liệu và các tham chiếu đến tệp đính kèm đã được tiền băm). Tiền băm có chọn lọc giúp hạn chế tác động tiềm tàng từ các cuộc tấn công va chạm hàm băm (hash collision attacks): nếu tệp đính kèm được tiền băm nhưng nội dung chính và tiêu đề không được tiền băm, kẻ tấn công không thể giả mạo thông điệp toàn phần chỉ bằng cách tạo va chạm trên phần tệp đính kèm đã được tiền băm. Quy ước này cần được thống nhất rõ ràng ở cấp độ giao thức để tránh không tương thích giữa các bên.

Tối ưu hóa triển khai

Hiệu suất của XEdDSA phụ thuộc mạnh vào chất lượng của thư viện mật mã đường cong elliptic nền. Các thư viện được tối ưu hóa tốt như libsodium (sử dụng hợp ngữ x86-64 với các lệnh SIMD như AVX2), HACL* (được xác minh hình thức với tối ưu hóa cho nhiều kiến trúc) hay các triển khai dành riêng cho vi điều khiển ARM Cortex-M có thể nhanh hơn vài lần so với triển khai thuần C hay Python. Lựa chọn thư viện nền là quyết định có tác động lớn nhất đến hiệu suất thực tế, vượt trội so với hầu hết các tối ưu hóa ở tầng giao thức.

Đối với xác minh, hiệu suất có thể được cải thiện bằng kỹ thuật xác minh đồng thời (batch verification): thay vì xác minh từng chữ ký độc lập, có thể kiểm tra đồng thời nhiều chữ ký bằng một phép tính tuyến tính hóa ngẫu nhiên, giảm số lượng phép nhân vô hướng cần thiết. Với n chữ ký, xác minh đồng thời cần khoảng n+1 phép nhân vô hướng thay vì 2n phép như xác minh tuần tự, cho phép tăng tốc lên gần 2 lần khi n lớn. Tuy nhiên, tối ưu hóa này áp dụng cho bên nhận tin nhắn đang cần xác minh nhiều chữ ký cùng lúc – không liên quan đến bên ký thường chỉ ký một thông điệp trong một lần.

Các yếu tố ảnh hưởng đến bảo mật

Phần này trình bày các vấn đề bảo mật tinh tế quan trọng cần xem xét khi triển khai XEdDSA và VXEdDSA trong thực tế. Các vấn đề này không phải là điểm yếu của thuật toán mà là những lưu ý triển khai mà nếu bỏ qua có thể dẫn đến lỗ hổng bảo mật nghiêm trọng.

Đầu vào ngẫu nhiên và chữ ký xác định

Chữ ký XEdDSA và VXEdDSA là chữ ký ngẫu nhiên: người gọi phải cung cấp một giá trị bí mật ngẫu nhiên 64 byte mới Z mỗi khi gọi hàm ký. Yêu cầu này không phải là tùy chọn. Lý do xuất phát từ cấu trúc của thuật toán: giá trị r được tính từ a, M và Z. Nếu cùng một r được dùng để ký hai thông điệp khác nhau M₁ và M₂, kẻ tấn công quan sát được hai chữ ký (R || s₁) và (R || s₂) có thể tính: s₁ – s₂ = (r + h₁a) – (r + h₂a) = (h₁ – h₂)a, suy ra a = (s₁ – s₂) / (h₁ – h₂) (mod q) – tức là khóa riêng bị lộ hoàn toàn từ hai chữ ký.

XEdDSA và VXEdDSA duy trì ý tưởng tính r bằng cách băm một bí mật dài hạn (khóa riêng a) và thông điệp M, nhưng bổ sung thêm giá trị ngẫu nhiên Z để tăng độ bền vững. Cách tiếp cận này kết hợp ưu điểm của chữ ký xác định (không bao giờ tái sử dụng r với cùng thông điệp ngay cả khi Z bị đoán được một phần) và chữ ký ngẫu nhiên (chống lại các cuộc tấn công yêu cầu ký nhiều lần để thu thập thông tin về r). Ứng dụng phải đảm bảo sử dụng nguồn ngẫu nhiên mật mã mạnh để tạo Z – trên hầu hết hệ điều hành hiện đại, điều này có nghĩa là dùng /dev/urandom trên Unix hay CryptGenRandom trên Windows, không dùng các hàm ngẫu nhiên thông thường của ngôn ngữ lập trình vì chúng không đủ chất lượng cho mục đích mật mã.

Thời gian thực thi cố định

Các thuật toán ký không được thực hiện các truy cập bộ nhớ khác nhau hoặc mất thời gian khác nhau tùy thuộc vào thông tin bí mật. Yêu cầu này – thường được gọi là triển khai thời gian cố định (constant-time implementation) – là điều kiện thiết yếu để chống lại tấn công qua kênh thời gian (timing side-channel attack), trong đó kẻ tấn công đo thời gian thực thi của nhiều lần ký và suy ra thông tin về khóa riêng từ các biến động thời gian.

Cần đặc biệt chú ý đến hàm calculate_key_pair do việc sử dụng câu lệnh rẽ nhánh có điều kiện (if E.s == 1: a = –k ...). Câu lệnh này tạo ra một điểm phân kỳ trong luồng thực thi phụ thuộc vào giá trị của E.s – giá trị này phụ thuộc vào khóa riêng k. Nếu hai nhánh mất thời gian khác nhau, kẻ tấn công có thể thống kê học suy ra bit dấu của E và từ đó thu thập thông tin về k sau nhiều lần đo. Thực tiễn triển khai an toàn sử dụng phép chọn thời gian cố định (constant-time select, còn gọi là cmov – conditional move) thay vì câu lệnh if thông thường.

Hàm hash_to_point cũng sử dụng rẽ nhánh có điều kiện trong elligator2 để kiểm tra căn bậc hai, và nên được thực hiện theo thời gian thực thi cố định, mặc dù nó chỉ xử lý thông điệp không liên quan đến khóa bí mật. Lý do là kẻ tấn công quan sát được thời gian thực thi của hash_to_point có thể suy ra thông tin về thông điệp đang được ký – thông tin này có thể nhạy cảm ngay cả khi không trực tiếp giúp khôi phục khóa riêng.

Tái sử dụng khóa và các lưu ý khác

Việc sử dụng cùng một cặp khóa để tạo chữ ký XEdDSA và VXEdDSA là an toàn – không có cuộc tấn công đã biết nào khai thác sự kết hợp này để khôi phục khóa riêng hay giả mạo chữ ký. Tính an toàn xuất phát từ thực tế là cả hai sơ đồ đều dựa trên cùng giả định ECDLP và sử dụng hàm băm để phân tách miền đủ mạnh.

Về lý thuyết, trong một số trường hợp nhất định, có thể sử dụng một cặp khóa vừa để tạo chữ ký XEdDSA vừa để sử dụng trong các giao thức dựa trên Diffie–Hellman (đây chính là mục đích thiết kế của XEdDSA). Tuy nhiên, trên thực tế, việc tái sử dụng khóa giữa các giao thức là một chủ đề phức tạp đòi hỏi phân tích cẩn thận cho từng trường hợp cụ thể. Nguyên tắc an toàn chung là chỉ tái sử dụng khóa khi có bằng chứng rõ ràng từ phân tích hình thức rằng sự kết hợp cụ thể đó là an toàn – và Signal Protocol đã thực hiện phân tích này cho trường hợp kết hợp giữa X3DH (dùng khóa để trao đổi Diffie–Hellman) và XEdDSA (dùng cùng khóa để ký khóa tiền), xác nhận rằng sự kết hợp này an toàn trong bối cảnh giao thức được xác định.

Kết luận

XEdDSA và VXEdDSA giải quyết một bài toán thiết kế tưởng chừng nhỏ nhưng có hệ quả quan trọng: cho phép dùng chung một cặp khóa Montgomery cho cả trao đổi Diffie–Hellman lẫn ký số, loại bỏ nhu cầu duy trì hai cặp khóa riêng biệt với hai giao thức quản lý khác nhau. Thiết kế dựa trên phép chuyển đổi song hữu tỷ giữa dạng Montgomery và Edwards xoắn đảm bảo tính bảo mật được bảo toàn hoàn toàn qua phép chuyển đổi: không có thông tin khóa riêng nào bị tiết lộ thêm và không có điểm yếu đại số nào được tạo ra.

VXEdDSA mở rộng thêm một bước với hàm ngẫu nhiên có thể xác minh, cho phép tạo giá trị ngẫu nhiên có thể chứng minh công khai là đầu ra của hàm xác định từ khóa riêng và thông điệp – nền tảng cho các ứng dụng giao thức đòi hỏi ngẫu nhiên có thể kiểm chứng. Hiểu XEdDSA là hiểu tại sao Signal Protocol có thể xây dựng toàn bộ hệ thống xác thực – từ ký khóa sơ bộ trong X3DH đến ký khóa KEM hậu lượng tử trong PQXDH – trên một loại khóa duy nhất, đơn giản hóa đáng kể việc quản lý khóa mà không đánh đổi tính bảo mật.