Public-Key
何時使用 RSA 以及何時使用 ElGamal 非對稱加密
如果我在密碼學方面沒有錯，那麼公鑰密碼學有兩種基本的密碼方案。RSA加密的安全性基於解決大素數分解問題的不可行性和與離散對數問題一樣安全的ElGamal加密。問題是是否存在必須使用 ElGamal 而不是 RSA 的特定情況，反之亦然。各自的弱點和強項是什麼？
綜上所述，在相同的攻擊模型下，是因式分解問題還是離散對數問題更難解決？
實際上，對於我們想要使用非對稱加密的大多數應用程序，我們確實想要一些更弱的東西：密鑰協商（也稱為“密鑰交換”）。當為此使用 RSA 或 ElGamal 時，一方選擇一個隨機字元串，用另一方的公鑰對其進行加密，並將隨機字元串用作經典對稱加密的密鑰。因此，我們必須將Diffie-Hellman添加到列表中。您可以將 Diffie-Hellman 想像為一種非對稱加密，在其中您無法選擇要加密的隨機值：不如 ElGamal 通用，但對於大多數使用非對稱加密的協議來說足夠強大。SSL/TLS和S/MIME在實踐中愉快地使用 RSA 和 Diffie-Hellman。Diffie-Hellman 和 ElGamal 一樣，（或多或少）依賴於打破離散對數的難度，並且在內部與 ElGamal 比較相似。
在 RSA、DH 和 ElGamal 之間的差異中，可以發現：
- DH 和 ElGamal 接受橢圓曲線變體。它們依賴於橢圓曲線上離散對數的硬度，這與模大素數的離散對數不同。橢圓曲線變體可以使用更小的欄位，因此雖然數學有點複雜，但性能更好。
- RSA加密（使用公鑰）比使用 ElGamal 的相應操作快，或者是 Diffie-Hellman 的一半。另一方面，RSA解密（使用私鑰）比 ElGamal 解密或 Diffie-Hellman 的另一半（尤其是橢圓曲線變體）要慢一些。
- RSA 加密的消息大於 ElGamal 加密的消息或 Diffie-Hellman 的一半，前提是後者使用橢圓曲線。
- 從歷史上看，RSA 在美國獲得了專利，而 ElGamal 沒有——這就是OpenPGP指定使用 ElGamal 的原因，而GnuPG傾向於支持它而不是 RSA（RSA 專利在十年前就到期了，所以這不再是一個問題）。
- RSA 由一個明確的標準來描述，該標準是免費的（如“免費啤酒”），並且準確地說明了每個字節應該去哪裡。這對實施者來說非常好：它減少了可能發生的事故。另一方面，Diffie-Hellman 標準（或橢圓曲線變體的標準）不是免費的，而且根據我的經驗，不太清楚。ElGamal 根本沒有既定的標準，除了 OpenPGP 中關於它的部分，它“一般”不處理 ElGamal。
協議設計者應該做的是為算法敏捷性做出一些規定：協議應該與各種算法一起工作，並帶有指示實際使用哪種算法的欄位。算法敏捷性在處理未來的密碼分析進步和監管要求方面有很大幫助。