當 q 或 p 除以 r 時的 Paillier 加密問題
我遇到了Wikipedia 上描述的 Paillier 加密問題。它說選擇 $ 0 < r < n $ ， 在哪裡 $ n=pq $ 對於大的，同樣大小的素數 $ p $ 和 $ q $ . 但是，我一直在用小密鑰大小進行測試，設置 p=11、q=13 並加密 m=1。當我嘗試 r 的所有合法值時，我發現解密失敗 $ p | r $ 或者 $ q | r $ .
（要清楚，我正在做 gcd 檢查並尋找一個小於 $ n^2 $ ，雖然我也嘗試過，但沒有在 Wiki 頁面上使用“更簡單的變體”，但沒有成功。）
我在 Python 中看到了一個特定的 Paillier 實現，其中的隨機值 $ r $ 被選為素數，也許是為了避免這個問題（我在這個執行緒中問過這個問題），但我在維基百科頁面或原始Paillier 論文中沒有看到對這個隨機常數的限制的這種規範。
我究竟做錯了什麼？如果在這個論壇上發布大約 40 行 Python 程式碼是合適的，我會 - 請在評論中指出。我不想搞砸飼料。
如果這是一個理論問題，那麼在不向進行加密的一方透露 p 或 q 的知識（gcd 與 n 為 1）或它只是基於大數定律，發送者在實踐中永遠不會落在這樣的 r 上？
謝謝你。
在 Paillier 加密中，密文是 $ c=g^n \cdot r^n \bmod n^2 $ ，並解密，你計算 $ m=L(c^\lambda \bmod n^2)\cdot \mu \bmod n $ .
為了解密正確， $ r $ 必須是組的成員 $ \Bbb Z_{n^2}^* $ ， 以便 $ r^{n\lambda} \equiv 1 \bmod n^2 $ 和 $ r $ 可以在解密過程中取消。如果 $ p $ 或者 $ q $ 劃分 $ r $ ， 然後 $ r $ 不在 $ \Bbb Z_{n^2}^* $ 因此無法取消，您的解密將不正確。
當你使用小 $ p,q $ ，很可能您可以輕鬆選擇 $ r $ 那不在 $ \Bbb Z_{n^2}^* $ . 然而，當 $ p,q $ 很大，隨機的機率 $ 0<r<n $ 不在 $ \Bbb Z_{n^2}^* $ 可以忽略不計（否則可以解決 RSA 問題）。所以我們通常可以只使用 $ 0<r<n $ ，沒有任何更多的約束（需要 $ r $ 對我來說是素數是沒有必要的）。