solution

Thuật toán chữ ký số ECDSA trên đường cong elliptic $E: y^2\equiv x^3+ax+b\pmod p$ với điểm cơ sở $G=(G_x,G_y)$ có bậc (order) $n$ (nghĩa là $nG=O$) hoạt động như sau. Cho khóa bí mật $d$ ($1\le d<n$), giá trị băm thông điệp đã được rút gọn thành số nguyên $e$ ($0\le e<n$, để đơn giản đề bài cho sẵn $e$ thay vì tính từ hàm băm thật), và một số ngẫu nhiên (nonce) $k$ ($1\le k<n$, đảm bảo $\gcd(k,n)=1$):

1. Tính điểm $R=kG=(x_R,y_R)$ bằng thuật toán Double-and-Add.
2. $r=x_R\bmod n$ (đề bài đảm bảo $r\neq 0$).
3. $s=k^{-1}(e+rd)\bmod n$, với $k^{-1}$ là nghịch đảo modulo $n$ của $k$ (đề bài đảm bảo $s\neq 0$).

Chữ ký là cặp $(r,s)$. Cho $T$ bộ dữ liệu, hãy tính chữ ký $(r,s)$ cho mỗi bộ.

Ví dụ: $p=97,a=2,b=3,G=(0,10),n=50,d=7,e=3,k=13 \Rightarrow (r,s)=(37,24)$.