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] Tấn công log rời rạc bằng Baby-step Giant-step

    Giải log rời rạc tìm khóa bí mật

    Kẻ tấn công biết p, g, A = g^a mod p và muốn tìm khóa bí mật a. Đây là bài toán log rời rạc. Với p nhỏ ta dùng Baby-step Giant-step chạy trong O(√p).

    Hãy tìm số mũ a nhỏ nhất trong [0, p-2] sao cho g^a ≡ A (mod p). Đảm bảo luôn tồn tại nghiệm.

    Ví dụ

    p=23, g=5, A=8: 5^6 mod 23 = 8 → a = 6.

    • Định dạng đầu vào:

      Ba số nguyên p g A.

    • Ràng buộc đầu vào:

      p nguyên tố, 2 ≤ p ≤ 10^9, 1 ≤ g,A < p, g là căn nguyên thủy.

    • Định dạng đầu ra:

      Số mũ a nhỏ nhất sao cho g^a ≡ A (mod p).

    Ví dụ:

    Đầu vào:

    23 5 8

    Đầu ra:

    6

    Giải thích:

    5^6 mod 23 = 8 nên log rời rạc a = 6.

    Đang tải editor...