Hệ thống mật mã Rabin: Tấn công bản mã được chọn

Tôi đã đọc trong tài liệu rằng Hệ thống mật mã Rabin có thể bị phá vỡ bằng cách sử dụng cuộc tấn công bằng bản mã được chọn. Người ta mô tả rằng sau khi bản mã đã chọn được giải mã, kẻ tấn công có thể tạo ra khóa công khai $n$ bằng cách sử dụng căn bậc hai với xác suất $1/2$. Nhưng bài báo không mô tả quá trình phân tích thừa số này được thực hiện như thế nào.

Nếu ai đó có thể đưa ra một số ví dụ, tôi sẽ biết ơn.

Tôi sẽ cho rằng đây không phải là bài tập về nhà.

Nó thực sự khá đơn giản:

• Chọn một giá trị ngẫu nhiên $r$

• tính toán $s = r^2 \bmod n$, và gửi $s$ đến bộ giải mã Rabin

• Từ $s$ là Dư lượng bậc hai, bộ giải mã Rabin sẽ trả về một số giá trị $t = \sqrt{s} \bmod n$.

• Hiện nay, $s$ có bốn căn bậc hai (giả sử $n$ có hai thừa số nguyên tố và bạn đã không tình cờ chọn một $r$ đó không phải là tương đối chính để $n$); nếu bạn có $t = r$ hoặc $t = n-r$, nó không hoạt động. Nếu đó là một trong hai giá trị có thể khác, thì chúng ta có $r^2 = t^2 \bmod n$, đó là, $(r+t)(r-t) = kn$, đối với một số nguyên $k$; tuy nhiên cũng không $r+t$ cũng không $r-t$ là bội số của $n$, vì thế $\gcd(r+t, n)$ là một yếu tố không tầm thường của $n$ (và $\gcd(r-t, n)$ là một yếu tố không cần thiết khác).

Bởi vì chúng tôi đã chọn $r$ một cách ngẫu nhiên, Rabin không có cách nào biết chúng tôi đã chọn khả năng nào trong bốn khả năng; nó trả về một trong số chúng, và do đó, xác suất để nó tình cờ trả về một cái mang lại cho chúng ta hệ số hóa là $2/4 = 0.5$