选择两个不同的素数$ p $和$ q $。
计算$ n = pq $。
我可能有一些愚蠢的问题：
为什么$ p $和$ q $必须是质数？为什么它们不能是任何整数或奇数整数？还是破坏了整个算法？
因为与常规整数相比，质数很少，将算法限制为仅质数会降低安全性吗？如果攻击者知道私钥只会是一些质数，似乎更容易找到私钥？
#1 楼
为了生成RSA密钥对，您将找到一个公共指数$ e $和一个私有指数$ d $，这样，对于\ mathbb Z_n ^ * $中的所有$ m \，即$ m $相对于$ n $，$（m ^ e）^ d \ equiv m \ pmod n $。欧拉定理的结果是，如果$ e，d $满足方程$ ed \ equiv 1 \ pmod {\ phi（n）} $，它们就是这样一个有效的公共/私有指数对。算术的基本定理说，每个整数都有因式分解为素数的幂，这是整数所独有的，除了因子的顺序。
欧拉的$ \ phi $函数的定义是$ \ phi（n）$等于小于$ n $且相对于$ n $质数的整数。为了确定该数字，必须知道$ n $的因式分解。
因此，如果选择一个数字$ n = pq $，其中$ p，q $都是素数，则选择了一个您可以分解的数字，但是，如果这个数字足够大，则没人可以分解。这样做的原因是，对于任意整数使用已知的分解算法，此类算法的运行时间取决于输入的第二大质数因子的相对大小。这意味着仅给定公用指数$ e $，您就可以确定私有指数$ d $。（注意：执行RSA私钥操作$ m \ equiv c ^ d \ mod的难度仅给定公钥$ e的n $，如上所述，n $被称为RSA问题，尚未证明其与分解模数一样困难，但是最著名的方法是分解系数$ n $为了确定给定$ e $的$ d $。）
这也意味着，如果您选择$ p，q $作为奇数整数，则将很难找到$ \ phi（n）$，同时减小第二大质数的相对大小因素，从而使其他所有人更容易地考虑$ n $。实际上，将$ n $分解为其他人一样困难，因此您将完全松开方案的活板门部分（如果不完全不可能找到对$ e，d $ ）。关于第二个问题，对于大$ x $，小于$ x $的质数等于$ \ pi（x）\ approx \ frac x {log（x）} $。因此，对于大的$ n = pq $，素数的数量大约等于$ \ sqrt n $，足以使分解算法比暴力搜索更快。此外，根据上述算术定理，对手实际上只对素数感兴趣，因此问题是没有根据的。
评论
$ \ begingroup $
次要问题：$ e，d $必须满足（满足）方程$ ed \ equiv 1（\ bmod \ phi（n））$是不正确的。一个反例是$ n = 133 $，$ e = 5 $，$ d = 11 $。这具有$ ed \ equiv 55 \（\ bmod \ phi（n）= 108）$，但是对于所有$ m $，$ {（m ^ e）} ^ d \ equiv m \（\ bmod \ n）$。这是一个小问题，但是我们应该避免告诉初学者一些不正确的事情。
$ \ endgroup $
–雨披
2013年9月27日14:21
$ \ begingroup $
@poncho：好的，谢谢，含义是相反的。显然，$ d = 65 $满足$ 5d = 1 \ pmod {\ phi（133）} $。
$ \ endgroup $
–亨里克·赫尔斯特伦
2013年9月27日15:36
#2 楼
假定$ n $为21。如果您尝试查找可能的因子，则必须尝试直到找到3和7。这当然很容易，因为数字很小，但是对于大数字来说，没有有效的方法。 （并且RSA中使用的那些确实很大）现在假设$ n $是32。您可以将其拆分为2 * 2 * 2 * 2 *2。现在，您只需要乘以它们（bruteforce ），直到得到两个数字。
这里的可能组合是： >
现在当然会随着数量的增加而变得更加复杂，但仍然非常容易/快速。因此，基本上，如果这些数字不是质数，则可以尽可能多地分解$ n $，从那里您可以找到一种更简单的方法来找到$ p $和$ q $。如果两者都是素数，则必须尝试$ p $和$ q $的值，直到找到完全正确的值。
评论
$ \ begingroup $
这是一个完美的解释！谢谢！现在我又有一个愚蠢的人，即RSA令牌上显示的数字，是n的“块”还是整个素数？
$ \ endgroup $
–布鲁斯
16年11月17日在16:53
$ \ begingroup $
回答自己，好像不是，我只是检查了一下，现在显示的数字不是素数。那么RSA令牌上的数字来自哪里？
$ \ endgroup $
–布鲁斯
16年11月17日在16:55
评论
简而言之：因为要计算$ \ phi（n）$，您需要对其进行因子分解。如果存在一个或多个较小（且易于查找）的因素，则您可能之前就已将它们删除了（那么它们对安全性没有意义，只需增加数字即可）。质数是“稀有”的假设只是部分成立：存在更多的非质数，但是即使对于1000位长的数，平均每个$ ln（2 ^ {1000}）\约700. $个数仍然是。而且还很多。RSA通常基于恰好两个质数。如果您有三个质数（或更多），即n = pqr，则基本上会有多质数RSA（尝试对其进行谷歌搜索）。但是，如果仅使用随机数（p和q是随机数，因此通常是许多数字的合成），则可能不会给出良好的结果。
您的问题根本不是愚蠢的。它们是密码学中引入某人的合法问题。对第一个的（愚蠢）答案是：因为数学属性必须是有序的。第二个问题的（愚蠢的）答案是：我们选择非常大的数字，所以不会，这不会降低安全性，并且攻击者很难找到私钥。