我知道一个常见的选择是让$ e = 3 $（这需要一个好的填充方案）或$ e = 65537 $，这比较慢但更安全。
我也知道对于两个素数$ p，q $，我们有$ \ phi（pq）=（p-1）（q-1）$
现在，让我给一个（简单）示例：
假设我选择$ e = 3 $，并选择两个随机质数$ p = 5 $和$ q = 13 $。
我现在可以计算$ \ gcd（3，\ phi（5 \ cdot 13））= 3 $。
这表明$ 3 $和$ \ phi（n）$不是互质的。我认为对于$ p $和$ q $的较大值也可能发生这种情况，对于另一个$ e $同样如此。因此，我假设RSA算法必须检查$ \ gcd（e，\ phi（pq））= 1 $。但是，让我们假设它不是。
如果$ \ gcd（e，\ phi（pq））\ neq 1 $，RSA如何变得易受攻击？
#1 楼
它不会变得脆弱；相反，变得不可能唯一解密。让我们以您给出的示例为例：$ N = 65 $和$ e = 3 $。
然后，如果我们加密明文$ 2 $，我们将获得$ 2 ^ 3 \ bmod 65 = 8 $。
但是，如果我们加密明文$ 57 $，我们将获得$ 57 ^ 3 \ bmod 65 = 8 $
因此，如果我们得到密文$ 8 $，就无法确定它是否对应于明文$ 2 $或$ 57 $（就此而言为$ 32 $）；这三个纯文本都将转换为一个密文值。
确保$ e $和$ \ phi（N）$是相对质数的，确保不会发生这种情况。
顺便说一句：生成RSA密钥时，当今的常见做法是先选择$ e $，然后选择素数$ p $，$ q $时，确保$ p-1，q-1 $相对$ e $的素数；这等效于确保$ e $和$ \ phi（N）$是相对质数。
评论
$ \ begingroup $
如果您选择安全质数$ p，q $，s.t. $ p = 2a + 1 $，$ q = 2b + 1 $，$ a，b $质数，则可以选择任何奇数$ e $（对$ a $和$ b $进行互素），因为$ \ phi（pq ）= 4ab $。
$ \ endgroup $
– tylo
2013年12月11日13:52
#2 楼
RSA加密和解密基于欧拉定理，该定理说$ a ^ {\ phi（n）} \ equiv 1 \ pmod n $，并且由于$ p $和$ q $是质数，因此$ \ phi（pq）=（ p-1）（q-1）$。如果我们有消息$ M $，模数$ n $，私有指数$ d $和公共指数$ e $，RSA加密的工作方式如下：
加密：$ C =（M ^ e \ bmod n）$
解密：$ M'=（C ^ d \ bmod n）$，必须与$相同M $表示解密正确。
现在，结合上面的内容，我们得到$$ M'\ equiv C ^ d \ equiv（M ^ e）^ d = M ^ {ed} \ pmod n。$$因为$ ed \ equiv 1 \ mod {\ phi（n）} $，我们可以写$ k \ cdot \ phi（n）= ed-1 $来计算整数$ k $并将其重新排列为$ ed = k \ cdot \ phi（n）+ 1 $。
因此$$ M'\ equiv M ^ {ed} = M ^ {k \ phi（n）+ 1} = M \ cdot M ^ {k \ phi（n）} \ pmod n，$$，因为$$ M ^ {k \ phi（n）} =（M ^ {\ phi（n）}）^ k \ equiv 1 ^ k = 1 \ pmod n，$$解密结果$ M'\ equiv M \ cdot M ^ {k \ phi（n）} \ equiv M \ cdot 1 = M \ pmod n $等于原始消息。
这一切都主要取决于$ ed = 1 \ mod {\ phi（n）} $的事实，因此，如果没有它，我们解密时就不会取回$ M $。
评论
$ \ begingroup $
为什么这个答案不好？
$ \ endgroup $
–toogley
16年7月9日在13:40
$ \ begingroup $
除非访问该页面的人，否则我们不知道。很有可能是因为“雨披”的答案被认为相距太远，因此“我们将无法获得M”和“所有三个纯文本都将转换为一个密文值”。答案在语义上是不同的，因此只有两个是正确的。 @poncho你可以看看这个吗？
$ \ endgroup $
–马腾·博德威斯♦
16/12/24在1:34
$ \ begingroup $
@MaartenBodewes我认为这个答案不能回答问题，而雨披的答案却可以。问题的答案是，通过选择与$ \ phi（n）$不互质的$ e $，就不可能唯一地解密。不过，无论如何，我认为这个答案还是不错的，因为它为我清除了为什么您找到$ ed \ equiv 1 \ mod \ phi（n）$（$ ed = k \ phi（n）+ 1 $部分是我所缺少的）。
$ \ endgroup $
– desowin
17-09-25在16:51
$ \ begingroup $
好吧，我想我经过8次投票后，现在的投票结果才是学术性的。并且除非进行投票的人解释了自己，否则我们将认为这是继Poncho投票结果更好的第二个不错的答案。在没有任何人证明这两个错误之一之前，让我们尽可能保持科学:)
$ \ endgroup $
–马腾·博德威斯♦
17/09/25在18:42
$ \ begingroup $
为了使$（M ^ {\ phi（n）}）^ k \ equiv 1 ^ k \ pmod n $为真，由于欧拉定理，要求$ M $和$ n $必须互质。 。考虑到$ M $由每个消息的明文确定，我想知道如何确保这一点。谢谢！
$ \ endgroup $
–David Chen
19 Mar 20 '19在15:36
评论
Rabin密码系统与RSA类似，但使用e = 2，将$ \ phi（n）$进行小数划分。它需要做额外的工作，因为这会使解密变得模棱两可。$ e = 65537 $也需要一个好的填充方案。它使针对填充不良的RSA的某些攻击变得更加困难，但并非全部。