Rsa
為什麼n=pq_n=pqn=pq和p=2p′+1p=2p′+1p=2p’+1和q=2q′+1q=2q′+1q=2q’+1而不僅僅是n=p′q′n=p′q′n=p’q’對於 RSA 加密？
對於 RSA 密碼學，我們知道模 $ n $ 是兩個大素數的乘積（比如說 $ p $ 和 $ q $ ）。但是，在某些文件中，我看到了 $ p=2p’+1 $ 和 $ q=2q’+1 $ 和 $ q’ $ 和 $ p’ $ 是巨大的素數。
為什麼必須有 $ n=pq $ 和 $ p=2p’+1 $ 和 $ q=2q’+1 $ 而不僅僅是 $ n=p’q’ $ 當我們知道 $ p’ $ 和 $ q’ $ 已經是素數了嗎？
如果有的話，您能否提供任何文件/資源？
在通常實踐的 RSA中（根據 PKCS#1 的加密或簽名，根據 X9.31、ISO/IEC 9796-2、FIPS 186 的簽名），沒有必要，甚至不常見，要求 $ n=p⋅q $ 和 $ p=2⋅p′+1 $ 和 $ q=2⋅q′+1 $ 和 $ p’ $ 和 $ q’ $ 巨大的素數，如問題中所述。如果這樣做了，它可以確保：
- 任何小奇數 $ e>2 $ （包括常見的 $ e=3 $ 和 $ e=65537 $ ) 是一個可用的公共指數（因為那時， $ e $ 不分 $ p-1 $ 或者 $ q-1 $ );
- 波拉德的 $ p−1 $ 因式分解算法將無效，因為它取決於整數 $ n $ 被分解 有一個因數 $ p $ 和 $ p-1 $ 一個光滑的整數。
在通常實踐的 RSA中，使用巨大的隨機素數通常就足夠了 $ p $ 和 $ q $ . 然而，對於相對較小的模量，通常要求 $ p-1 $ , $ q-1 $ , $ p+1 $ ， 和 $ q+1 $ 有一個很大的素數，以確保 Pollard 的 $ p−1 $ 和威廉的 $ p+1 $ 因式分解算法比ECM效率低；該預防措施是 ANSI X9.31 規定的，並且仍然適用於所有FIPS 186-4 $ 1024 $ 位模數和一些素數生成方法；我相信（反對許多人的建議）當一個人考慮敵手內容並在許多人中考慮一個公共模數時，它仍然很有用。
正如 DrLecter 所指出的，類似 RSA 的密碼系統或使用類似於 RSA 的密鑰的協議可能有額外的要求；看他的回答。