目前 RSA 算法相关的教程和文章都有一个根本性缺陷

[itskingname]

注意我是说这些教程和文章有缺陷，不是说 RSA 算法有缺陷。

我们知道，在 RSA 算法里面，需要选定两个足够大的质数 p 和 q 相乘得到 N，由于对 N 进行分解非常困难，所以能保证 RSA 算法的安全性。网上的文章也是这样说的。

但是，我在网上看了四十多篇 RSA 相关的文章，所有的文章对于如何选定 p 和 q，全都没有讲。都只是轻描淡写地说一句：

选定两个足够大的质数 p 和 q

我现在就问你，你给我找两个质数，每个质数要超过 100 位数。你能在短时间找出来吗？

所以我很好奇，现在的 RSA 库里面，他们是怎么选定这个 p 和 q 的呢？难道是现场 2,3,5,7,11,13...这样一个一个数直到找到足够大的为止？还是提前算好并存在了某个地方，要用的时候直接随机取出来用？

目前 python-rsa 库确实是一个一个数出来的：

[Mutoo]

费马小定理了解一下，一个快速确定一个数是否质数的方法。

[crab]

@geelaw

[swulling]

大概算了下，可能不太准确。2^128 位差不多是在 10^40 左右，1~10^41 中，素数密度大约是 1/41 （根据素数密度定律） [实际上选择的范围比这个小，密度会更低，但是也就是 1/4x 而已，不会有大的影响] 。

根据 benchmark，一次验证素数是 0.5ms 。那么 1000 次（ 0.5s ）内随机挑选的数都不是素数的概率 (40/41)^1000，大概是 10^-11 次方的概率，这个概率低到真的没有任何工程上的考虑价值。

[itskingname]

@mxT52CRuqR6o5 #19 你这样说确实有道理。不能挨着遍历。

[itskingname]

@swulling #23 用数字和概率说就很清楚了，23 楼可以说服我。但你前面楼层只提 benchmark 就没有什么说服力。

[BinRelay]

要是告诉你关于 rsa 的考试题目 一般 pq 都是计算 20 以内的质数你会不会认为考试不合理……

[richard1122]

可是维基百科这里清楚的写了怎么找啊

[kindjeff]

每次看到 RSA 的数学问题一定会回复这篇文章

http://www.matrix67.com/blog/archives/5100

[tzm41]

标题：“目前 RSA 算法相关的教程和文章都有一个根本性缺陷”。
正文：“我现在就问你，你给我找两个质数，每个质数要超过 100 位数。你能在短时间找出来吗？”
已知：《 Introduction to Modern Cryptography 》第 303 页，8.2.1 章为《 Generating Random Primes 》。详细讨论了和 python-rsa 库一样的算法，以及 Bertrand’s postulate 和 Miller–Rabin test。
结论：思而不学则怠。

[pangleon]

@swulling 有理有据 令人信服 这楼主也是没谁了 年轻真好

[nathanw]

你这“运气不好”表述还没有论文来的专业

[geelaw]

素数定理保证一个 n 位随机数是质数的概率是 Omega(1/n)，因此在 O(nk) 次尝试中仍然不出现一个质数的概率是 2^(-Omega(k))。

现实世界里可能会对质数的选择有其他要求，但通常也可以在 Otilde(n) 次内找到。

另外现实世界用的质数判断算法通常是 BPP 的（ Miller-Rabin ），虽然实际上存在着 P 的算法（ AKS ）。

在现代计算机上一天都找不到的概率大概比 1/宇宙里的原子数 还小。

[churchmice]

有个数字货币就是用来找素数的

[swulling]

@swulling 补充下#23

10^40 - 10^41 中素数出现的概率大约是(10^41/41 - 10^40/40) / 10^41，等于 0.9/41

也就是 1/46。那么 0.5s 内找不到素数的概率是 (45/46)^1000 = 3E-10，也很小，不过比 E-11 高了一个数量级。

[liaoliaojun]

实时计算生成所花费的时间太多，所以我认为是提前存储好的质数

[Citrus]

@itskingname #16 那你有没有想过，如果你的随机数生成算法，运气这么不好的多次重复生成了同一个数，还导致你一天都没有生成到有用的数，那这个算法是不是有什么问题呢？？？

[siyemiaokube]

@Mohanson 素数通项公式本来就能写出来，只是没有 O （ 1 ）公式

[siyemiaokube]

@swulling 有一些前人总结了某些范围内 miller robin 的 magic number 表，证明了完备性，wiki 上就有链接

[geelaw]

@liaoliaojun #35 提前存储素数是完全不安全的做法。只要 N 的一个质因数存在于预先存定的质数表里，就可以迅速分解 N。

[roland2015]

深入一点研究 RSA 算法，能找到不少问题的文章