顛覆 RSA 公鑰密碼學中的密鑰生成步驟
我對 RSA 密鑰生成實現可以或不能被破壞的方式感興趣，以便破壞者俱有優勢，但是密鑰的所有者以及與所有者互動的人都沒有意識到正在發生的事情。我假設密鑰的所有者沒有能力檢測密鑰生成實現中的細微錯誤，但密鑰將用於在顛覆者控制之外的標準實現中進行加密和解密。
- 我的第一個想法是顛覆素數測試可能會接受而不是拒絕形式為 P 1 *P 2的數字，其中 P 1是只有顛覆者知道的固定素數，而 P 2是隨機素數。密鑰的所有者最終會得到一個 P 1 *P 2 *Q 形式的模數，世界其他地方不一定能夠將其與半素數區分開來。但是，根據這個答案，密鑰的擁有者可能會發現自己無法破解自己的公鑰，即無法讀取發給他們的消息。我理解連結的答案意味著模數的主要分解是讀取加密消息所必需的，實際上，密鑰的所有者不會進行這種分解。密鑰的擁有者一方面只有 P 1 *P 2，另一方面只有 Q 。
- 另一個想法是，質數生成實現可能會被顛覆，使得存在一百萬個質數 P 1，P 2，…，P 1000000，實現比其他實現更可能生成（例如，每個質數的機率為 1 /2000000 每次生成）。實際上，這相當於私人探勘你的 Ps 和你的 Qs攻擊（*），保留給顛覆者（他們會知道 P 1，…，P 1000000的值）但是，只要被顛覆的實現仍然存在適度使用，不太可能被其他任何人（密鑰的所有者和世界其他地方）檢測到。
(*) 在寫完這樣一個問題後，我突然想到，如果被顛覆的實現永遠不會將列表 P 1，P 2，…，P 1000000中的素數與列表中的另一個素數配對，那麼顛覆者可以保持其遊戲保護更加私密。這並不能阻止他們使用原始的“探勘你的 Ps 和你的 Qs”攻擊一一被發現，但至少它們不會同時解開。
我的問題是： 1. 是否可以使用某種偽素數而不是合數來惡意接受為素數？2. 在實踐中可能不起作用有什麼原因嗎？
這是兩個問題，但它們是相關的，因為它們與相同的目的相關
我認為想法 1 根本無法工作。要點是，為了生成正確的秘密解密密鑰，密鑰生成器必須知道 $ \mathbb Z^_n $ ，即模數的總和 $ n $ . 生成器知道 $ n=p \cdot q $ , 它認為 $ p $ 和 $ q $ 是素數，所以它相信總論是 $ (p-1)(q-1) $ . 但實際上，如果 $ p $ 不是素數，實際的總數必須*更小，因為 $ p $ 嚴格小於 $ p-1 $ （同樣對於 $ q $ ）。所以生成器不會使用正確的totient，也無法計算出正確的密鑰。（從技術上講，所有這些都假設 $ p $ 和 $ q $ 實際上是互質的，生成器可以自行檢查。）
至於想法 2，它基本上已經在實踐中實現，因為具有該缺陷的幾個密鑰生成算法被部署和使用多年而沒有懷疑。最簡單的解釋是這些是偶然的而非惡意的缺陷，但同樣的缺陷也可能被惡意部署。
更新：類型 2 顛覆的“問題”是公眾可以發現許多密鑰共享一個共同的素數，從而了解顛覆。這是另一種不存在共享素數問題的顛覆，但確實允許顛覆者分解生成的模數。顛覆者設計生成算法以選擇與應用於（例如）電子郵件地址和/或時間的 PRF 的輸出接近的素數——一些（準）公共資訊將與密鑰相關聯，每次執行生成器時都是唯一的。所以選擇的素數可能永遠不會相同，但顛覆者可以使用 PRF 的密鑰輕鬆找到它們。唯一的問題是 PRF 密鑰也必須隱藏在生成器算法中。