Tôi không cảm thấy rằng đây là nơi để hướng dẫn về lý thuyết số cơ bản, vì vậy tôi sẽ chỉ đề cập đến các khía cạnh liên quan ngay đến câu hỏi của bạn.
Khi chúng ta lấy số nguyên tố $p$ và một giá trị $g$ (không phải là bội số của $p$), sau đó nếu chúng ta xem xét chuỗi các giá trị $g^0 \bmod p, g^1 \bmod p, g^2 \bmod p, ...$, sau đó chúng tôi thấy rằng tại một thời điểm nào đó, chuỗi sẽ trở về 1 và sau đó, bắt đầu lại. Ta gọi thứ tự của $g$ số lượng giá trị mà chúng ta trải qua trước khi đạt đến 1, nghĩa là, $g^q \bmod p = 1$, và đó là giá trị nhỏ nhất của $q > 0$ thỏa mãn điều này.
Vì vậy, khi Smart nói rằng $g$ và $h$ có cùng thứ tự nguyên tố, anh ấy đang nói rằng $g^q \bmod p = 1$, $h^q \bmod p = 1$ và $q$ là số nguyên tố (và trong cả hai trường hợp, không có giá trị nào nhỏ hơn của $q$).
Làm thế nào để bạn tìm thấy một $g, h, q$? Trên thực tế, hóa ra nó không khó lắm; $q$ sẽ luôn chia $p-1$ như nhau; chúng ta có thể chọn một số nguyên tố $p$ để thực hiện việc tìm kiếm một giá trị nguyên tố như vậy $q$ dễ dàng. Ngoài ra, nếu $q$ là một số nguyên tố như vậy thì với mọi giá trị $u$ không có $p$ như một yếu tố, giá trị $j = u^{(p-1)/q} \bmod p$ sẽ là 1 hoặc có thứ tự $q$; vậy việc tìm các giá trị $g, h$ dễ.
Bạn hỏi một ví dụ, tôi sẽ đưa cho bạn một món đồ chơi - chúng ta sẽ chọn $p=23$ và $q=11$ (lưu ý rằng $11$ phân chia $23-1$ đồng đều) và $g=4$ và $h=9$ (thật dễ dàng để xác minh rằng cả hai đều có thứ tự 11). Chúng tôi cũng chọn một giá trị bí mật $x$ (chúng tôi sẽ chọn 6) và xuất bản $y_1 = g^x \bmod p = 4^6 \bmod 23 = 2$ và $y_2 = h^x \bmod p = 9^6 \bmod 23 = 3$
Sau đó, người tục ngữ chọn một cách ngẫu nhiên $k$, ta sẽ tùy ý chọn $k=7$
Người tục ngữ sau đó tính toán $r_1 = g^k \bmod p = 4^7 \bmod 23 = 8$ và $r_2 = h^k \bmod p = 9^7 \bmod 23 = 4$, và truyền chúng. Lưu ý rằng chúng tôi đã thực hiện các phép tính này theo modulo $p$ - điều đó đã được ẩn trong giao thức (các hoạt động mô đun như vậy thường được hiểu).
Bây giờ, người thách thức chọn một giá trị $c$; chúng tôi sẽ chọn $4$; và gửi nó.
Người tục ngữ sau đó tính toán $s = (k - c \cdot x) \bmod q = (7 - 4 * 6) \bmod 11 = 5$ (lưu ý: trong toán học, $x \bmod q$ hoạt động luôn trả về giá trị giữa $0$ và $q-1$ để có thể $x - (x \bmod q)$ là bội số của $q$ - nhiều ngôn ngữ máy tính không tuân theo điều đó - những ngôn ngữ đó sai) và gửi nó.
Người xác minh sau đó kiểm tra xem $r_1 = 8$ giống như $g^s \cdot y_1^c \bmod p = 4^5 \cdot 2^4 \bmod 23 = 8$ và $r_2 = 4$ giống như $h^s \cdot y_2^c \bmod p = 9^5 \cdot 3^4 \bmod 23 = 4$; cả hai kiểm tra, và vì vậy điều này vượt qua.
Bạn cũng làm tương tự, chỉ với các giá trị có độ dài hàng trăm chữ số, không phải ví dụ về đồ chơi mà tôi đã đưa ra.
