如何在不透露密文用於誰的情況下使用 RSA（或 ElGamal）進行加密？
想像一下，Alice 想要為 Bob 加密並公開發布此加密，這樣只有 Bob 可以解密，但除了 Alice 或 Bob 之外，沒有人可以告訴我們該消息是為 Bob 加密的。
天真的方法洩露了一些資訊。如果愛麗絲發帖 $ y = x^e \bmod{n} $ ，那麼觀察者可以斷定接收者有一個公鑰 $ n > y $ ，因此可以消除很多關於收件人是誰的猜測。根據更高級別的協議，這種優勢可能會被放大。
我的想法是愛麗絲可以隨機生成 $ r $ 大小的 $ 2^{\textrm{L}} $ ， 在哪裡 $ L $ 是允許的最大密鑰大小，並且發布 $ y + rn $ . 然後，Bob 可以考慮殘差 mod $ n $ 解密時。
同樣，在 ElGamal 中，Alice 可以隨機選擇 $ r_1 $ 和 $ r_2 $ ，然後發布 $ \langle c_1 + r_1 p, c_2 + r_2 p \rangle $ .
這些結構是否達到了它們的預期目標？
一個案例是 PGP 加密。假設 Alice 從外部數據包中剝離了密鑰 id，她能否發布 PGP 加密而不洩露有關其預期接收者的資訊？
你的目標是有一個數字 $ y’ = y + rn $ 在任何有效的密鑰模數上給出均勻分佈 $ n’ $ ，因此不能排除任何鍵。為此，您需要 $ y’ $ 以更大的數為模均勻分佈。問題有多大。
如果您有來自 $ [0, 2^l-1] $ ，根據這個（pdf，第20頁談論密鑰生成，但應該在這裡應用）它們是統一的（足夠）模 $ n < 2^k $ 如果 $ l = k + 64 $ . 因此，擁有你的 $ y’ $ 統一的鍵高達 $ L $ 你應該畫的位 $ y’ $ 從 $ [0, 2^{L+64}-1] $ .
你的方法給出了更大的數字（ $ 2^{L+lg(n)} > 2^{L-lg(n)+64} $ 用現實的 $ n $ )，因此該部分被覆蓋，但它可能會洩漏最小尺寸 $ n $ , 因為如果 $ r = 2^L $ , 沒有鍵 $ n’<n $ 可能導致如此高的數字 $ y’ $ .
你應該畫 $ r $ 從 $ [0, 2^{L-lg(n)+64}-1] $ ，將指數四捨五入，使得 $ y’ $ 可以到達 $ 2^{L+64}-1 $ ，然後扔掉那些 $ r $ 給你的價值觀 $ y’ > 2^{L+64}-1 $ .
（您可以為該隨機數生成找到更好的上限，但是生成不是模 2 的冪的統一隨機數本身就很棘手。最壞的情況是您將丟棄一半 $ r $ 值，所以這應該很容易。）
正如@DrLecter 評論的那樣，您所指的財產是由“關鍵隱私”擷取的。
基於 RSA 加密方案，還有更多棘手的方法可以實現密鑰隱私（針對選擇密文攻擊）。讓我們假設 $ 2^{k-1} < N < 2^{k} $ .
重複
重複生成密文 $ y $ 直到結果在公共域中，比如說， $ [0,2^{k-1}) $ . 請參閱Bellare、Boldyreva、Desai、Pointcheval：公鑰加密中的密鑰隱私 (ASIACRYPT 2001)。
擴大
這是你提到的。生成密文 $ y $ 並將其擴展為 $ y + rn $ 到共同領域，比如說 $ [0,2^{k+m}) $ . 環境 $ m = 160 $ 就足夠了（64 和 80 可能不行）。請參閱Desmedt：確保密文的可追溯性：邁向安全的軟體託管方案 (EUROCRYPT ‘95)。當與 RSA-OAEP 結合使用時，我們可以顯示其密鑰隱私。有關正式證明，請參見Hayashi, Tanaka：通用匿名公鑰加密 (ASIACRYPT 2005)。
兩次應用 RSA 函式
得到的密文在 $ [0,2^k) $ ， 在哪裡 $ k = |N| $ . 請參閱Hayashi、Okamoto、Tanaka：具有公共域的 RSA 系列陷阱門排列及其應用（PKC 2004）。
採樣兩次
生成兩個密文並應用“選擇和移位”算法。得到的密文按照均勻分佈分佈在 $ [0,2^{k}) $ . 請參閱Hayashi，Tanaka：基於 RSA 的匿名密碼系統的兩次採樣技術（PKC 2005）。