Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Phá khóa Diffie–Hellman với modulus nhỏ

    Diffie–Hellman chỉ an toàn khi số nguyên tố ppp đủ lớn, vì bài toán ngược — bài toán logarit rời rạc (Discrete Logarithm Problem) — mới khó về mặt tính toán. Với ppp nhỏ, kẻ tấn công có thể duyệt toàn bộ để tìm lại khóa bí mật.

    Cho số nguyên tố ppp, cơ số ggg (1≤g≤p−11 \le g \le p-11≤g≤p−1) và khóa công khai AAA (0≤A≤p−10 \le A \le p-10≤A≤p−1), hãy tìm số nguyên xxx nhỏ nhất thỏa 0≤x≤p−20 \le x \le p-20≤x≤p−2 sao cho:

    gx mod p=Ag^{x} \bmod p = Agxmodp=A

    Nếu không tồn tại xxx nào trong khoảng trên thỏa mãn (do ggg không sinh ra AAA), in ra −1-1−1.

    Ví dụ: p=23, g=5, A=8p=23,\ g=5,\ A=8p=23, g=5, A=8. Ta có 56 mod 23=85^{6} \bmod 23 = 856mod23=8 và không có x<6x<6x<6 nào thỏa, nên đáp án là 666.

    • Định dạng đầu vào:
      • Dòng đầu tiên chứa số nguyên TTT (1≤T≤501 \le T \le 501≤T≤50).
      • TTT dòng tiếp theo, mỗi dòng chứa ba số nguyên p g Ap\ g\ Ap g A, trong đó ppp là số nguyên tố (2≤p≤2×1052 \le p \le 2 \times 10^{5}2≤p≤2×105), 1≤g≤p−11 \le g \le p-11≤g≤p−1, 0≤A≤p−10 \le A \le p-10≤A≤p−1.
    • Định dạng đầu ra:

      In ra TTT dòng, dòng thứ iii là số nguyên xxx nhỏ nhất thỏa gx mod p=Ag^{x} \bmod p = Agxmodp=A (0≤x≤p−20 \le x \le p-20≤x≤p−2), hoặc −1-1−1 nếu không tồn tại.

    Ví dụ:

    Đầu vào:

    3
23 5 8
23 5 1
23 5 22

    Đầu ra:

    6
0
11

    Đầu vào:

    1
7 3 1

    Đầu ra:

    0

    Đang tải editor...