RSA 生成公私钥时质数是怎么选的？
谢邀… 这题真没想象的那么简单啊朋友们…事实上，下面三个问题的答案应该是完全不一样的： 前面几位前辈的答案基本围绕着“质数是怎么选的”这个问题回答的。实际上，RSA生成公钥、私钥时所用的质数生成方法以“质数是怎么选的”为基础，但是后面还有不少需要注意的事项。既然我最近一直在用Bouncy Castle开发密码学库（为了避免打广告的嫌疑，这个密码学库的链接和简单的介绍我就不放了，有兴趣的知友们可以在评论下面留言，如果确实需要我就在评论里面给链接），我就以Bouncy Castle里面RSA质数的选法为例，抛砖引玉地讲解一下RSA质数的生成方法。 ————————分割线———————— 0. 说明 ————————分割线———————— 1.  质数的个数 在我的知乎电子书《质数了不起》[1]中提到： 我们就用这个定理分析一下给定位数的质数个数到底有多少个。假定我们要求某个质数的位数要达到二进制的n位，那么这个数最大不会大于2^n，小于2^n质数的个数约为2^n / (n log e)。n位二进制数最小不会小于2^{n-1}，小于2^{n-1}的质数个数约为2^{n-1} / ((n - 1) log e)。因此，二进制位数恰好为n的质数个数总计为： \frac{2^n}{n \log e}-\frac{2^{n-1}}{(n-1) \log e}\approx\frac{(n-1)2^n-\frac{n}{2}2^n}{n(n-1) \log e}=\frac{n-2}{n(n-1) \log e}2^{n-1} 也就是说，二进制位数恰好为n的质数总个数与位数n的关系仍然是指数级的（只不过数量级小了O(n)）。因此，虽然二进制位数恰好为n的质数总个数和二进制位数恰好为n的所有整数个数相比少了一些，但是数量级是一样的。随着n的增大，质数个数也呈指数级增大，想遍历一定位数下质数的个数对当前计算机来说仍然是非常困难的。 ————————分割线———————— 2.  如何判断一个数是否为质数？ 还是引用我知乎电子书《质数了不起》[1]中的论述： 我们来看看在Java JDK 8中用的是什么算法： 从算法名就可以看出，Java JDK中使用的算法为Miller-Rabin质数判别法。至于判别法本身在此就不多做论述了，感兴趣的知友们可以参考《质数了不起》中的引用[33]了解算法的执行过程和算法复杂度。 ————————分割线———————— 3.  如何选择一个质数？ 这个过程有一点复杂，最简单的思路为：先随机选择一个给定位数的奇数，然后用质数判别法判断其是否为质数。如果不是，则重新选择。但是，根据“质数定理”，给定一个数x，小于x的质数个数约为x / ln x，也就是说，给定一个数，其为质数的概率约为1 / ln x。就算给定的数是个奇数，其概率也只能上升到2 / ln x。如果质数要求是2048位，那么随机取一个奇数，其能通过质数检验的概率约为 \frac{2}{2048 \log e} \approx 0.22\% （这里感谢 同学的指正，原始计算有误）。也就是说，差不断要选500次才能有一次通过质数判断。为了进一步提高效率，Java JDK实现了2个方法，一种方法适用于当给定位数比较小的情况，另一种方法适用于当给定位数比较大的情况。Java JDK规定，当给定位数小于95位时，用第一种方法；当给定位数大于等于95位时，用第二种方法： smallPrime函数的原理是：先用某种方法挑一个数，然后判断其是否能通过primeToCertainty函数的验证，如果不能通过则重新选取。smallPrime函数的源代码在BigInteger.java的第700行至第733行，其中第729行至第731行用到了质数判定函数： largePrime函数的原理是：先用某种方法挑一个数，用数筛法筛这个数，看是不是存在明显的合数，如果没有，再判断得到的指数是否能通过primeToCertainty函数的验证，返回通过primeToCertainty函数的验证的数（感谢 的指正，largePrime中所调用类BitSieve的第203行同样调用了primeToCertainty函数）： ————————分割线———————— 3.  如何选择一个满足RSA安全性的质数？ 这个问题回答起来也有点麻烦。RSA中涉及到2个质数：p和q，而且还涉及到公钥e和私钥d。只要p和q是质数就够了吗？答案是否定的。实际上，RSA中的质数还需要满足很多条件，简单列举如下： （1）RSA中的质数p和质数q不能离得太近 密码学家D. Coppersmith于1996年指出[2]：如果合数N的质因子p和质因子q离得很近，则存在快速算法将N分解。现在一般认为，如果合数N的位数为n，那么|p-q|要同时满足 \log |p-q|> n/2-100; \log |p-q| > n/3 （2）RSA中的e不能太小 同样是密码学家D. Coppersmith，其于1990年指出[3]：用于RSA的指数e不能太小，否则存在快速算法计算得到私钥d。这个定理要用到格密码学的著名算法LLL。再次就不多做展开了… 不过需要注意的是，由于加密算法要计算m^e，如果e太大的话加密过程可能会比较慢。现在一般认为令e=65537是比较合适的。 （3）RSA中的d不能太小 密码学家M. Wiener于1990年指出[4]：用于RSA的私钥d不能太小，否则存在快速算法得到私钥d。现在一般认为，如果合数N的位数为n，那么d的值要满足 d > 2^{n/2} （4）RSA中的合数N非相邻形式（Non-Adjacent Form，NAF）权重不能太小 密码学家O. Schirokauer于2010年指出[5]：如果N的NAF表述权重略小，则应用数筛法可能会快速对N进行质因数分解。现在一般要求N的NAF表述权重要大于N/4。 综合上述问题，我们才能得到RSA质数的选取方法，大致流程如下： ————————分割线———————— 4. 源代码参考 Bouncy Castle中的RSAKeyPairGenerator.java给出了RSA质数的完整选取方法，具体代码为第31行至第151行。我适当进行了中文标记。 以上，才是（至今为止）RSA质数的正确选法。未来，数学家们或者密码学家们若发现了其它漏洞，还可能进一步修改RSA质数的选择方法。 ————————分割线———————— 5. 参考文献 [1] 刘巍然. 质数了不起. 知乎出版社. 中国, 北京, 2016, . [2] Coppersmith D. Finding a small root of a bivariate integer equation; factoring with high bits known. EUROCRYPT 1996. pp. 178-189, ACM, 1996. [3] Coppersmith D., Small solutions to polynomial equations, and low exponent RSA vulnerabilities, Journal of Cryptology, 10: 233–260, 1997. [4] Wiener M. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information  Theory. 36: 553–558, 1990. [5] Schirokauer O. The number field sieve for integers of low weight. Mathematics of Computation, 79(269): 583-602, 2010.