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 căn bậc ba RSA (e = 3, không đệm)

    Một hệ thống dùng RSA với số mũ công khai nhỏ e=3e = 3e=3 để mã hóa bản rõ mmm mà không áp dụng đệm (no padding): c=m3 mod nc = m^3 \bmod nc=m3modn.

    Nếu bản rõ đủ nhỏ sao cho m3<nm^3 < nm3<n thì phép lấy modulo không thực sự "cuộn" (không có phép rút gọn nào xảy ra), tức là ccc chính là giá trị m3m^3m3 theo số học thông thường (không phải chỉ đồng dư). Khi đó kẻ tấn công chỉ cần biết ccc là đã có thể khôi phục mmm bằng cách lấy căn bậc ba nguyên của ccc, không cần biết khóa bí mật.

    Cho hai số nguyên nnn và ccc (đảm bảo tồn tại số nguyên không âm mmm sao cho m3=cm^3 = cm3=c đúng theo số học thông thường, và m3<nm^3 < nm3<n), hãy khôi phục mmm.

    Ví dụ: với c=1000c = 1000c=1000, ta có m=10m = 10m=10 vì 103=100010^3 = 1000103=1000.

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

      Một dòng gồm 2 số nguyên n,cn, cn,c cách nhau bởi khoảng trắng (1≤n<101001 \le n < 10^{100}1≤n<10100, 0≤c<n0 \le c < n0≤c<n, ccc là lập phương đúng của một số nguyên không âm).

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

      In ra duy nhất số nguyên mmm thỏa m3=cm^3 = cm3=c.

    Ví dụ:

    Đầu vào:

    3233 0

    Đầu ra:

    0

    Đầu vào:

    3233 1

    Đầu ra:

    1

    Đang tải editor...