Diffie-Hellman在数学上是否与RSA相同？

#1 楼

RSA和Diffie-Hellman都使用模块化幂运算。但是它们的工作方式不同：

在RSA中，有两个指数互为倒数，即我们有$ e $和$ d $使得$（x ^ e）^ d \ equiv所有$ x $的x $。例如。如果$ \ square ^ e $是加密，则$ \ square ^ d $是相应的解密。要创建这对$ e $和$ d $（或从中得出一个），我们需要模数$ m $的素因式分解（因此应该是私有的）。

在Diffie中-Hellman，求幂的基数$ g $和模数$ m $是固定的。指数$ x $和$ y $是随机选择的私钥，我们使用以下事实：$（g ^ x）^ y \ equiv g ^ {x \ cdot y} \ equiv（g ^ y）^ x $，其中$ g ^ x $和$ g ^ y $是公开的，而$ x $和$ y $是（并保持）私有的，而$ g ^ {x·y} $是共享的机密。

要破解RSA，我们必须从$ x ^ d $，$ m $和$ d $中获得$ x $-这可以称为离散的$ d $根问题。 （执行此操作的最著名方法是将$ m $分解为$ e $ ...，如果您有$ e $，这也可用于分解$ m $）。

要打破Diffie-Hellman，我们必须从$ g ^ x $，$ g ^ y $，$ m $和$ g $中获得$ g ^ {x·y} $。进行此操作的最著名方法是从$ g ^ x $中获得$ x $或从$ g ^ y $中获得$ y $（以及$ m $和$ g $），即所谓的离散对数问题。 （通常，还没有证明这确实是最好的方法，即没有更快的方法可以做到这一点。）

#2 楼

Diffie-Hellman和RSA是不同的，并且不使用相同的“技巧”。

在Diffie-Hellman中使用可交换性：$（g ^ a）^ b =（g ^ b）^ a $。爱丽丝（Alice）和鲍勃（Bob）都做两个模幂运算（爱丽丝选择$ a $，计算$ g ^ a $并将其发送给Bob，从Bob接收$ g ^ b $，最后计算$（g ^ b）^ a $） 。安全性依赖于离散对数的难度：给定素数$ p $，整数$ g $和$ g ^ x \ mod p $，要找到$ x $是非常困难的。在RSA中，不涉及可交换性。爱丽丝和鲍勃各自只做一次模幂运算；计算不是对素数$ p $取模，而是对非素数$ n $取模。爱丽丝选择一个随机的$ m $，计算$ m ^ e \ mod n $并将其发送给Bob；鲍勃计算$（m ^ e）^ d \ mod n $等于$ m $，因为为此选择了$ d $和$ e $。 RSA依赖于提取第e个根的困难：给定$ n $，$ e $和$ m ^ e \ mod n $，要找到$ m $是非常困难的，除非您知道“魔术陷阱” “，即$ d $（或$ n $的因式分解）（如果$ n $是素数，则找到$ m $将很容易）。它们的工作方式，提供的内容以及所依赖的困难问题各不相同。注意区别：在离散对数中，您有$ g $和$ g ^ x $，并求$ x $；在$ e $根中，您有$ m ^ e $和$ e $，并寻求$ m $。

任何非对称加密算法（例如RSA）都可以用作密钥交换算法，以您描述的方式（为了“交换”密钥，Alice选择了一个随机Blob并使用Bob的公共密钥对其进行加密）。 SSL / TLS可以做到这一点。相反，事实并非如此：您不能将“单独的”密钥交换算法一般地转换为非对称加密算法（但是您可以将交换的密钥与AES等对称加密算法一起使用；在使用Diffie-Hellman时，SSL也会这样做） 。

#3 楼

DH和RSA背后的数学问题相似，但尚不直接相关。是否可以使用一个破坏DH的Oracle来构造另一个破坏RSA的Oracle（反之亦然）仍然是一个悬而未决的问题。人们普遍认为，这两个问题在聚合时间内是无法相互解决的。因此，DH和RSA建议的密钥大小都相同。

我应该补充一点，对于椭圆曲线DH，没有比普通算法更好的方法来解决DH问题，因此密钥长度要短得多。

#4 楼

DH和RSA绝对不同。 DH是一种密钥交换算法，RSA是一种加密/签名算法。它们确实可以用于类似目的。但是，该运算处理的是根本不同的数学问题。 DH使用DLP（离散对数），当g ^ x = H且g和H已知时，依靠发现x的难度。 RSA相信素数分解问题：知道n =（p-1）（q-1）时找到p（素数）和q（素数）的难度。

如果DL问题会解决方案，使得在合理的时间内计算x可行，DH和ElGamal都将被破坏。如果我没记错的话，RSA不会。解决素因数分解问题时，RSA将会受苦。

因此，您不能使用DH来证明RSA或反之。

#5 楼

不，它们是不一样的。

简短的答案是，Diffie-Hellman是在尚未共享的各方之间谈判一个秘密，而RSA使用现有密钥材料来保护数据。 br />
实际上有很大的不同。当然，两者都与“安全性”相关，但是DH是从头开始，而RSA使用的是已经存在的系统。

#6 楼

Diffie-Hellman假设离散日志（在底层组中）很难。尽管DH最初是在以质数为模的整数乘法组中指定的，但此后已被认为是假定离散对数很难的任何组中的相应算法。

RSA安全性依赖于假设“ RSA问题”很难解决。 RSA问题是找到仅给出$ n $，$ e $和密文的明文。很容易看到有效的分解算法可以破解RSA，但反之亦然：即，如果我们有一个可以有效破解RSA的预言机，我们可以有效分解$ n $吗？这些是不同的假设；尤其是破坏一个不会以任何明显的方式破坏另一个。

有趣的是，量子计算机通过类似的技术破坏了BOTH算法（假设DH在$ Z ^ * _ p $中）

#7 楼

在RSA中，给定e使得$ \ gcd（e，（p − 1）（q − 1））= 1 $和$ \ c $，找到$ \ m $使得$ \ m ^ {e} = c \（mod \ N）$

但是在Diffie-Hellman中，给定b和g使得$ \ b ^ {k} = g $，找到k