Tôi sẽ cho rằng Paillier điển hình đã thiết lập điều đó $n=pq$ với $p$ và $q$ số nguyên tố $(p-1)\not\!| q$ và ngược lại.
Sự phục hồi của logarit rời rạc $x$ của một yếu tố chung $a$ đối với một trình tạo tương đương với việc khôi phục ba giá trị:
$$x\equiv\cases{x_\lambda\pmod{\lambda(n)}\ x_p\pmod p\ x_q\pmod q}.$$
Nếu biết các giá trị của $p$ và $q$ sau đó $x_p$ và $x_q$ dễ dàng phục hồi bằng cách sử dụng thương số Fermat hoặc $p$phiên bản -adic của chuỗi Taylor logarit. Các phương pháp được biết đến tốt nhất để phục hồi $x_\lambda$ dựa vào sàng trường số và cho kích thước mật mã* $p$ và $q$, điều này sẽ không khả thi. Nếu một người chọn một trình tạo sao cho thứ tự của trình tạo chia $n$, điều này có nghĩa rằng $x_\lambda$ có thể được bỏ qua và logarit rời rạc đối với trình tạo này có thể dễ dàng được tính toán bởi bất kỳ ai biết $p$ và $q$.
Trong trường hợp đầu tiên của bạn, nơi $n$ chia thứ tự của $g$, điều này chỉ cho chúng ta biết rằng $x_p$ và $x_q$ không thể bỏ qua. Nó không đảm bảo rằng $x_\lambda$ có thể bị bỏ qua và do đó vấn đề của chúng ta vẫn có thể khó giải quyết.
Trong trường hợp thứ hai của bạn, nơi $n$ không phân chia thứ tự của $r$ điều này cho chúng ta biết rằng một trong hai $x_p$ có thể bỏ qua hoặc $x_q$ có thể bỏ qua (có thể bỏ qua cả hai). Nó không đảm bảo rằng $x_\lambda$ có thể bị bỏ qua và vấn đề của chúng tôi vẫn có thể khó giải quyết.
Nói chung:
- nếu $p$ không phân chia thứ tự của trình tạo, sau đó $x_p$ có thể bỏ qua,
- nếu $q$ không phân chia thứ tự của trình tạo, sau đó $x_q$ có thể bỏ qua,
- nếu $\lambda(n)$ không phân chia thứ tự của trình tạo, sau đó $x_\lambda$ có thể được bỏ qua.
Cũng lưu ý rằng nếu chúng ta tình cờ biết được một giới hạn về kích thước của $x$, thì có thể không cần khôi phục cả ba thành phần này. ví dụ. nếu chúng ta biết điều đó $x<pq$ sau đó phục hồi của $x_p$ và $x_q$ cho phép chúng tôi phục hồi duy nhất $x$ từ định lý phần dư Trung Hoa.
*- Lưu ý rằng $p$ và $q$ phải có mô đun lớn hơn mức có thể bị tấn công bằng sàng trường số thay vì chỉ đơn giản là $n$ là một mô-đun lớn hơn mức có thể bị tấn công bằng sàng trường số.
