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:

• Đường cong elliptic trên trường số thực ở đây (basic)

• Đường cong elliptic trên trường hữu hạn ở đây

Ở bài 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ố … Trong bài này mình sẽ giới thiệu kỹ thuật chữ ký số trên ECC.

ECDSA

1. Thiết lập

• 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\)

2. Generate chữ ký cho message \(M\)

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

  Chú ý: tính \(z\) để 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 (*)\)

• 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ệ

3. Verify 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 Q_A\)

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

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

Verify thuật toán ECDSA

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

$$\begin{align*} S(x,y) &= u_1 \times G + u_2 \times Q_A\\ &= u_1 \times G + u_2d_A \times G \\ &= (u_1 + u_2d_A) \times G \\ &= (zs^{-1} + rd_As^{-1}) \times G \\ &= (z + rd_A)s^{-1}\times G \\ &= (z + rd_A)\left(k^{-1}(z + rd_A)\right)^{-1}\times G \\ &= (z + rd_A)(k^{-1})^{-1}(z+rd_A)^{-1} \times G \\ &= k \times G \end{align*}$$

Như vậy ta có:

$$S(x,y) = k \times G = K(x_K,y_K) (*)$$

Mà \(r = x_K \bmod n \implies r = x\). (Thuật toán chính xác)

Demo

Mình chưa có thời gian để làm trang demo nhúng thẳng vào blog này, các bạn xem tạm demo mình làm tại đây nhé! Các bạn chịu khó scroll xuống dưới, phần đầu là lược đồ chữ ký cho RSA, phần hai là ECDSA.