Nếu cùng một bản rõ m được mã hóa dưới cùng modulus n nhưng với hai số mũ công khai e1, e2 thỏa gcd(e1, e2) = 1, kẻ tấn công khôi phục được m mà không cần phân tích n.
Dùng định lý Bézout tìm a, b sao cho a·e1 + b·e2 = 1, khi đó
c1^a · c2^b ≡ m^{a·e1 + b·e2} = m (mod n).
Số mũ âm xử lý bằng nghịch đảo modulo.
Input:
n e1 e2 c1 c2
Output:
m
Một dòng: n e1 e2 c1 c2.
gcd(e1, e2) = 1, gcd(c_i, n) = 1, n <= 10^12.
Bản rõ m.
Ví dụ:
Đầu vào:
99400891 3 5 5299668 88962689
Đầu ra:
12345
Giải thích:
Đang tải editor...