ECDSA - Chữ ký số trên đường cong elliptic

Nếu bạn chưa biết gì hoặc mới tìm hiểu về Elliptic Curve, bạn có thể đọc lại các bài trước của series này:

• Bài viết về: Đường cong elliptic trên trường số thực

• Bài viết về: Đường cong elliptic trên trường hữu hạn

Ở các bài viết trước, chúng ta đã biết rằng có thể tạo ra một nhóm con cyclic với phép cộng từ một điểm $G \ne O$ bất kỳ trên đường cong $E$. Đây là cơ sở để xây dựng lược đồ chữ ký số dựa trên đường cong elliptic (ECDSA - Ellipti Curve Digital Signature Algorithm)

Ưu điểm của hệ mật mã trên đường cong elliptic (ECC - Elliptic Curve Cryptography) là nó sử dụng khóa có độ dài nhỏ hơn RSA truyền thống. Hãy xem lại bảng thống kê dưới đây để thấy rõ điều đó:

Hiện nay tất cả các hệ mã hóa được sử dụng trong công nghệ blockchain đều dùng ECC cho mọi kỹ thuật: mã hóa, trao đổi khóa, chữ ký số, ZKP, … Trong bài này mình sẽ giới thiệu kỹ thuật chữ ký số trên ECC.

Elliptic Curve Digital Signature Algorithm

Chữ ký số cho phép:

• Xác thực người gửi

• Đảm bảo dữ liệu không bị thay đổi

• Không thể chối bỏ

ECDSA được sử dụng rộng rãi trong nhiều hệ thống:

• Bitcoin

• Ethereum

• Transport Layer Security

Nhờ sử dụng elliptic curve, ECDSA đạt mức bảo mật cao với kích thước khóa nhỏ hơn nhiều so với RSA.

Một hệ thống chữ ký số thường gồm 3 bước:

1. Key Generation – tạo khóa

2. Signing – ký dữ liệu

3. Verification – xác minh chữ ký

ECDSA thực hiện các bước này dựa trên toán học của elliptic curve.

Tạo khóa

• Cho điểm $G$ là điểm sinh của nhóm con bậc $n$ trên đường cong $E$.

• Chọn $d_A, 0 \lt d_A \lt n$ ngẫu nhiên làm secret key.

• Tính public key $Q_A = d_A \times G$

Sinh chữ ký cho message $M$

• Gọi $m = Hash(M)$ là giá trị hash của message $M$, tính $z = m \bmod n$.

  Chú ý: việc tính $z$ là để nhằm đảm bảo giá trị $z$ trong khoảng $[0, n-1]$

• Chọn giá trị ngẫu nhiên $k \in [1, n-1]$, tính điểm $K(x_K,y_K) = k \times G (*)$. Lưu ý rằng giá trị $k$ phải ngẫu nhiên và chỉ dùng 1 lần duy nhất vì nếu hai chữ ký sử dụng cùng một gia trị $k$, attacker có thể tính ngược lại được secret key. Lịch sử đã từng có nhiều sự cố bảo mật do lỗi này, ví dụ trong hệ thống của Sony khi triển khai chữ ký số cho PlayStation 3. Do đó trong thực tế người ta thường sử dụng chuẩn deterministic ECDSA (RFC 6979) để tạo $k$.

• Tính $r = x_K \bmod n$. Nếu $r=0$, chọn lại $k$ với giá trị khác.

• Tính $s = k^{-1} (z + rd_A) \bmod n$. Nếu $s=0$, chọn lại $k$ với giá trị khác.

• Chữ ký là cặp số $(r,s)$. Lưu ý là cặp số $(r,-s)$ cũng là một chữ ký hợp lệ.

Xác minh chữ ký $(r,s)$ cho $m$

Dùng public key $Q_A$:

• Tính $z = m \bmod n$

• Tính $u_1 = z \times s^{-1} \bmod n$, tính $u_1 \times G$

• Tính $u_2 = r \times s^{-1} \bmod n$, tính $u_2 \times G$

• Tính $S(x,y) = u_1 \times G+ u_2 \times Q_A$

• Chữ ký hợp lệ nếu $r=x$

Lý do tại sao thuật toán này hoạt động?

Xét điểm $S(x,y)$:

Như vậy ta có:

Mà $r = x_K \bmod n \implies r = x$, vì thế thuật toán chính xác!

Lý do tại sao giá trị $k$ không được sử dụng nhiều lần?

Trong quá trình ký, ta có:

trong đó:

• $d_A$ : private key

• $k$ : số ngẫu nhiên chỉ dùng một lần

• $z$ : hash của message

• $r,s$ : chữ ký

• $n$ : order của điểm sinh

Giả sử attacker biết được một giá trị $k$ dùng cho 2 message, ta có 2 chữ ký:

• Message $m1$: $s_1 = k^{-1}(z_1 + r d_A) \pmod n$

• Message $m_2$​: $s_2 = k^{-1}(z_2 + r d_A) \pmod n$

Mà:

• $r$ giống nhau vì $r = x(kG)$

• $k$ giống nhau vì bị reuse

Trừ hai phương trình ta có:

Suy ra:

Như vậy attacker tính được $k$. Và từ $k$ có thể tính ra private key bằng cách:

• Quay lại phương trình ban đầu $s=k^{-1}(z+rd_A)$

• Nhân 2 vế với $k$: $ks = z+rd_A$

• Suy ra: $\displaystyle d_A = \frac {ks-z} r \pmod n$

Mà attack đã biết tất cả giá trị $k,s,z,r$ nên chúng tính được private key $d_A$.

Demo

Các bước trong demo này:

• Chọn tham số đường cong, update

• Chọn một điểm trên đường cong để làm điểm sinh $G$

• Chọn khóa bí mật, chọn giá trị để ký, sinh chữ ký

• Verify chữ ký