如果我在密码学上没有错，则有2种基本的公共密钥密码学方案。 RSA加密的安全性基于解决大素数问题的分解的不可行性，而ElGamal加密的安全性与离散对数问题一样安全。问题是，是否在特定情况下必须使用ElGamal代替RSA，反之亦然。

总结一下，在相同的攻击模型下，解决因式分解问题或离散对数问题更困难吗？

#1 楼

实际上，对于大多数我们要使用非对称加密的应用程序，我们确实希望弱一点：密钥协议（也称为“密钥交换”）。当使用RSA或ElGamal时，一方选择一个随机字符串，并用另一方的公钥对其进行加密，然后该随机字符串用作经典对称加密的密钥。因此，我们必须将Diffie-Hellman添加到列表中。您可以想象Diffie-Hellman是一种非对称加密，您无需选择要加密的随机值：比ElGamal通用性差，但对于使用非对称加密的大多数协议而言，功能却足够强大。 SSL / TLS和S / MIME在实践中愉快地使用RSA和Diffie-Hellman。与ElGamal一样，Diffie-Hellman或多或少地依赖于打破离散对数的难度，并且在内部与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的位没有“一般”地处理ElGamal。

协议设计者应该做的是为算法敏捷性做些准备：协议应与各种算法一起使用，并带有指示实际使用哪种算法的字段。算法敏捷性在处理未来的密码分析方面的新进展以及满足法规要求方面有很大帮助。

评论

$ \ begingroup $
但是Diffie-Hellman不属于非对称密码学家族。就是这种情况，在共享密钥加密数据（DH），然后使用公共密钥密码术（RSA或ELGamal）加密此密钥的情况下，您很有可能将其与对称加密一起使用？
$ \ endgroup $
–好奇
2012年1月17日15:31
$ \ begingroup $
@curious：DH是完全不对称的密码；它不是非对称加密，但仍然是密码学，并且仍然是非对称的（“ asymmetric” =“并非所有参与方共享相同的密钥”）。数字签名也是非对称密码（我在这里不谈论它们）。另外，使用DH时，请勿对其使用非对称加密。您可能对Diffie-Hellman是什么有所了解。我建议您看一下Wikipedia页面（除非已关闭，否则他们似乎想将其涂黑一天，以抗议某种拟议的美国法律）。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2012年1月17日在16:12
$ \ begingroup $
进行密钥交换后，您会得到一个对称密钥。但是密钥交换本身仍然基于非对称加密。但是，当您使用RSA，DH甚至它们的组合来交换密钥时，这是正确的。不确定DH是否需要共享机密。
$ \ endgroup $
– CodesInChaos
2012年1月18日12:28


$ \ begingroup $
@curious：我认为您看错了99.9％的书-很可能这些书不清楚。对称密码就是您使用共享密钥（例如AES，HMAC ...）所做的。 DH是获取共享密钥的方式（将使用该密钥进行对称加密）。 DH是“非对称密码术”，例如RSA。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2012年1月18日在12:30
$ \ begingroup $
考虑到算法RSA于1978年发布并进行了全面描述，而该公司实际上是在RSA成立之前（1982年）的，因此您的主张是可疑的。这意味着不仅美国国家安全局向公司支付了修改算法的费用，而且还允许他们使用一些时差技术，以便他们可以回到1978年以实施所述修改。 （我想我否认了NSA的时空旅行能力。可耻的是我。）
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2014年12月6日13:08

#2 楼

硬度

关于求解因式分解的硬度，这个问题（以及答案和评论）提供了有趣的讨论。只要遵循建议的密钥大小，则任一加密系统都是足够安全的。

用例

我看到ElGamal被用于RSA的一个用例是当一个乘法同态时需要加密系统（注意ElGamal和RSA都是同态的）。首选ElGamal的原因是它在语义上是“开箱即用”的安全（即未经修改（此问题和我的回答可能会对我在说的内容有更多的了解）。

评论

$ \ begingroup $
为什么RSA在语义上不安全？
$ \ endgroup $
–好奇
2012年1月17日15:21
$ \ begingroup $
首先，请记住，我说的是“教科书RSA”或没有修改的RSA。添加良好的填充（OAEP）将使RSA在语义上安全，但是随后您将失去同构属性。语义安全性的一个简单定义就是能够区分$ m_0 $的加密和$ m_1 $的加密之间的机会要好于50％。因此，您拥有公共密钥并知道消息，质询者将给您$ c_b $，并且您必须说出$ b = 0 $或$ b = 1 $。使用RSA教科书，您只需对$ m_1 $和$ m_0 $进行加密，然后与$ c_b $进行比较即可得到答案（加密是确定性的）。
$ \ endgroup $
–mikeazo
2012年1月17日15:34
$ \ begingroup $
另一种情况是，您不想被NSA恐怖分子监视。
$ \ endgroup $
– Evi1M4chine
2014年12月6日在9:28
$ \ begingroup $
@ EviM4chine，您是否能证明它们通常可以破坏RSA，还是只是偏执？
$ \ endgroup $
–mikeazo
2014年12月6日上午10:55
$ \ begingroup $
@Ragnagord，是的，但是RSA中断并不意味着P = NP。换句话说，您可能会破坏RSA，但仍然不知道P = NP。您的第一条评论说，破坏RSA需要证明P = NP。那是不对的。
$ \ endgroup $
–mikeazo
15年5月22日在18:11