Rsa
為什麼 ElGamal 被認為是非確定性的？
RSA 和 ElGamal 之間的一個區別是 ElGamal 不一定是確定性的（而 RSA 是）。
是什麼使它具有不確定性？這對安全有利嗎？此屬性如何影響 ElGamal 加密或 ElGamal 簽名方案？
在這種情況下，“非確定性”意味著生成密文（或簽名）的算法將隨機值作為其輸入之一，並且它可以根據隨機值生成許多可能的密文（或簽名）。ElGamal 是非確定性的，因為加密器選擇隨機指數作為加密方法的一部分。
對於公鑰加密，加密消息的這種隨機化很重要。如果公鑰加密算法不是非確定性的（即加密消息只依賴於明文消息和公鑰），那麼有人擁有加密消息 $ M $ 和公鑰 $ PK $ 和一個候選明文消息 $ P $ 可以測試是否解密 $ M $ 曾是 $ P $ （只需加密 $ P $ 使用公鑰 $ PK $ ，並檢查結果是否為 $ M $ ).
因此，公鑰加密幾乎總是不確定的。請注意，RSA 也不例外。雖然核心 RSA 算法是確定性的，但實際的 RSA 公鑰加密還包括填充方法，並且這種填充方法可以（並且通常確實）包括隨機性。
對於公鑰簽名，由於使用一些隨機輸入生成簽名的原始語義，沒有相應的要求；然而，一些密碼學證明技術確實假設簽名生成也是非確定性的。另一方面，在 ElGamal 簽名 ( DSA ) 的特定情況下，它實際上確實需要一個隨機輸入，而事實證明這個輸入確實需要是隨機的，並且是均勻分佈的。