solution

Lược đồ chữ ký số ElGamal hoạt động trên nhóm nhân $\mathbb{Z}_p^*$ với $p$ nguyên tố. Khóa công khai gồm $(p, g, y)$ với $y = g^x \bmod p$ ($x$ là khóa bí mật, $1 \le x \le p-2$). Với giá trị băm thông điệp $h$ (số nguyên, $0 \le h < p-1$), người ký chọn ngẫu nhiên $k$ nguyên tố cùng nhau với $p-1$ và tính chữ ký $(r,s)$:

$r = g^k \bmod p, \qquad s = (h - x r) k^{-1} \bmod (p-1)$

Người xác thực (chỉ biết khóa công khai) kiểm tra chữ ký $(r,s)$ có hợp lệ với thông điệp có giá trị băm $h$ hay không bằng cách kiểm tra đồng thời hai điều kiện:

1. $0 < r < p$
2. $g^h \bmod p = \big(y^r \bmod p \cdot r^s \bmod p\big) \bmod p$

Cho $p, g, y, h, r, s$, hãy xác định chữ ký có hợp lệ hay không.

Ví dụ: $p=467,\ g=2,\ y=132,\ h=100,\ r=29,\ s=51$. Ta có $g^{100} \bmod 467 = 189$ và $(132^{29} \bmod 467) \cdot (29^{51} \bmod 467) \bmod 467 = 189$, hai vế bằng nhau và $0 < 29 < 467$ nên kết quả là VALID.