Alice and Bob use Diffie-Hellman Key Exchange to share a key with a common prime p=22 and a primitive root a=10. If Alice has a public key Y_A=10, what is her private key X_A

Đáp án đúng: "7". Trong Diffie-Hellman, khoá công khai Y_A = a^X_A mod p, nên ta kiểm 10^X_A mod 22 có bằng 10 không. Tính lần lượt: 10^1 = 10, 10^2 = 100 mod 22 = 100 − 88 = 12, 10^3 = 12 × 10 = 120 mod 22 = 120 − 110 = 10, tức dãy lặp chu kỳ 2: số mũ lẻ cho 10, số mũ chẵn cho 12. Vậy 10^7 mod 22 = 10, khớp Y_A, nên "7" thoả. Nhưng cần nói thẳng: đề chọn p = 22 = 2 × 11 không phải số nguyên tố và 10 không phải phần tử nguyên thuỷ (chỉ sinh được hai giá trị 10 và 12), nên "3", "5" và "11" cũng là số mũ lẻ và đều cho Y_A = 10; lôgarit rời rạc ở đây không có nghiệm duy nhất, và "7" là giá trị được chốt cho câu này. Phương án "8" là phương án duy nhất sai về số học, vì số mũ chẵn cho 10^8 mod 22 = 12 ≠ 10. Đây cũng là lý do Diffie-Hellman đòi p nguyên tố lớn và a là phần tử nguyên thuỷ để a^X phủ đủ các giá trị từ 1 tới p − 1.