这是一个创建于 2251 天前的主题，其中的信息可能已经有所发展或是发生改变。
注意我是说这些教程和文章有缺陷，不是说 RSA 算法有缺陷。
我们知道，在 RSA 算法里面，需要选定两个足够大的质数 p 和 q 相乘得到 N，由于对 N 进行分解非常困难，所以能保证 RSA 算法的安全性。网上的文章也是这样说的。
但是，我在网上看了四十多篇 RSA 相关的文章，所有的文章对于如何选定 p 和 q，全都没有讲。都只是轻描淡写地说一句：
选定两个足够大的质数 p 和 q
我现在就问你，你给我找两个质数，每个质数要超过 100 位数。你能在短时间找出来吗？
所以我很好奇，现在的 RSA 库里面，他们是怎么选定这个 p 和 q 的呢？难道是现场 2,3,5,7,11,13...这样一个一个数直到找到足够大的为止？还是提前算好并存在了某个地方，要用的时候直接随机取出来用？
目前 python-rsa 库确实是一个一个数出来的：
 | 1 shintendo 2020 年 2 月 24 日 应该是生成足够位数的随机数，判定是不是质数，不是就再取一个 |
 | &nsp; 2 itskingname OP @shintendo 看了源代码才知道，找 p 和 q 的算法太简单粗暴了。运气不好的话，算一天都遇不上。 |
 | 3 Citrus 2020 年 2 月 24 日  6 1. 个人并不认为这是教程的缺陷，因为如何选大素数可以单独拎出来说一整篇文章，完全没必要在 RSA 的文章里详细说。就像我告诉你如何检测牛奶的成分，会告诉你取一杯牛奶，但是不会把《奶牛的产后护理》一并附上 2. 请看仔细，Python 并不是从 2 3 5 7 这样一个个的数到足够大。我不知道你是怎么把这段源码理解成这样的。。。这样数每次生成密钥还不到天荒地老。而且一个个数上去只要稍微会一点算法的人都知道是没必要的。因为素数都是各自独立的，找一个大素数完全没必要从 2 数上来 3. 关键函数：rsa.randnum.read_random_odd_int(nbits) |
| 4 Citrus 2020 年 2 月 24 日 @itskingname 一天都遇不到的结论是如何得出的？请给出你的计算。RSA 的素数获取是有数学论证的，请不要不给证据的直接猜想。 |
 | 5 coderluan 2020 年 2 月 24 日 @shintendo 我记得应该是从足够位数的最小数开始递增，直到找到一个质数。 PS：生成质数算是和正经问题，但是说这个是别人文章的缺陷就太扯了，我感觉看 RSA 文章的人，是有能力搜索解决这个问题的，写文章不可能所有东西都说清楚的。 |
| 6 shintendo 2020 年 2 月 24 日 |
| 7 itskingname OP @Citrus 2,3,5 是我还没有看源代码的时候猜的，发了这篇帖子我去看了一下源代码，然后截图贴过来。因为怕过了 6 分钟改不了了，所以贴了图又直接发。导致前面的文字没有修改 |
 | 8 est 2020 年 2 月 24 日 via Android 这就是为啥喊不要自己造加密库轮子的原因 |
| 9 OP @Citrus #4，因为它的 randomnum 这个模块里面，获取随机计数是没有去重的。运气不好的情况下，始终获取的都是非质数的奇数。而且会重复获得。 |
| 10 itskingname OP @shintendo 它不是递增计算的。它就是不停获取这么多位的随机奇数，然后反复验证是不是质数。 |
 | 11 swulling 2020 年 2 月 24 日 via iPhone @itskingname #2 一天都找不到？你可以自己跑下 benchmark 看看 |
 | 12 mxT52CRuqR6o5 2020 年 2 月 24 日 via Android 在数学上去验证一个数是不是素数确实是很慢的，所以你会想不通，但实际操作是现在有快速验证一个数是否是素数的方法，可以快速判断一个数是否是工程实践中可用的素数(验出来的数大概率是素数) |
| 13 itskingname OP @swulling 我都说了在运气不好的情况下。现实中不容易出现这样的极端情况。 |
 | 14 falsemask 2020 年 2 月 24 日 Miller-Rabin 素数检测，可以了解一下，java BigInteger 类用的是这个算法 |
 | 15 Mohanson 2020 年 2 月 24 日 3 素数除了产设随机数再判断是否素数, 没有其它方法了吧? 如果有的话, 等于"找到了素数通项公式"... |
| 16 itskingname OP @Mohanson 产生随机数再判断，在大多数情况下效果不错，但极端况下就很慢，因为 python-rsa 库里面没有做去重处理，可能运气不好多次产生同一个非质数奇数。 而从最小的 nbit 奇数开始逐渐增加 2，一个一个遍历，不会重复。效率平庸，但不容易出现极端情况。 |
 | 17 ETiV 2020 年 2 月 24 日 via iPhone #14 +1 but 那个算法并不能保证被检测的数 100%是质数 但是够快 |
| 18 swulling 2020 年 2 月 24 日 1 @itskingname 1. 统计学就是避免运气的影响，根据素数密度分布能够得到 getprime 耗时的数学期望 2. 验证是否为素数非常快，参考 https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test 3. 性能多做 benchmark，随手做一个 1000 loop 的 128 位素数 In [4]: timeit.timeit("rsa.prime.getprime(128)", setup="import rsa", number=1000) Out[4]: 4.098196368999993 如果仅仅说，运气不好就 XXX，那么基本上对统计学没有实际的逻辑概念 |
| 19 mxT52CRuqR6o5 2020 年 2 月 24 日 via Android @itskingname 你这样就不够安全了，生成素数是一次性操作，慢一点也没关系，安全才是第一目的，慢不慢什么的无所谓的，不要本末倒置了 |
| 20 swulling 2020 年 2 月 24 日 @itskingname #16 1. 如果顺序遍历，那么你的 p 和 q 不是都被人知道了么？这个还有什么安全性可言？ 2. #17 我记得 Miller Rabin 通过一些方法可以在特定的范围内，比如 2 的 32 次方内，确定 100%是否为素数。不太懂，有懂的可以补充 3. 其实工程上并不需要 100%的准确，因为验证素数足够快，所以随机选了极大次，都不是素数的概率应该非常的低。具体多少我算不出来，但是应该有人能够算出来。如果这个概率低到了和宇宙射线把你的 bit 反转的概率都还要低，真的要从工程上讨论它么？ |
 | 21 Mutoo 2020 年 2 月 24 日 费马小定理了解一下，一个快速确定一个数是否质数的方法。 |
| 23 swulling 2020 年 2 月 2 日 2 大概算了下，可能不太准确。2^128 位差不多是在 10^40 左右，1~10^41 中，素数密度大约是 1/41 （根据素数密度定律） [实际上选择的范围比这个小，密度会更低，但是也就是 1/4x 而已，不会有大的影响] 。 根据 benchmark，一次验证素数是 0.5ms 。那么 1000 次（ 0.5s ）内随机挑选的数都不是素数的概率 (40/41)^1000，大概是 10^-11 次方的概率，这个概率低到真的没有任何工程上的考虑价值。 |
| 24 itskingname OP @mxT52CRuqR6o5 #19 你这样说确实有道理。不能挨着遍历。 |
| 25 itskingname OP @swulling #23 用数字和概率说就很清楚了，23 楼可以说服我。但你前面楼层只提 benchmark 就没有什么说服力。 |
 | 26 BinRelay 2020 年 2 月 24 日 要是告诉你关于 rsa 的考试题目 一般 pq 都是计算 20 以内的质数你会不会认为考试不合理…… |
 | 27 richard1122 2020 年 2 月 24 日  可是维基百科这里清楚的写了怎么找啊 |
 | 28 kindjeff 2020 年 2 月 24 日 |
 | 29 tzm41 2020 年 2 月 24 日 标题：“目前 RSA 算法相关的教程和文章都有一个根本性缺陷”。 正文：“我现在就问你，你给我找两个质数，每个质数要超过 100 位数。你能在短时间找出来吗？” 已知：《 Introduction to Modern Cryptography 》第 303 页，8.2.1 章为《 Generating Random Primes 》。详细讨论了和 python-rsa 库一样的算法，以及 Bertrand’s postulate 和 MillerRabin test。 结论：思而不学则怠。 |
 | 31 nathanw 2020 年 2 月 24 日 via iPhone 你这“运气不好”表述还没有论文来的专业 |
 | 32 geelaw 2020 年 2 月 24 日 via iPhone 2 素数定理保证一个 n 位随机数是质数的概率是 Omega(1/n)，因此在 O(nk) 次尝试中仍然不出现一个质数的概率是 2^(-Omega(k))。 现实世界里可能会对质数的选择有其他要求，但通常也可以在 Otilde(n) 次内找到。 另外现实世界用的质数判断算法通常是 BPP 的（ Miller-Rabin ），虽然实际上存在着 P 的算法（ AKS ）。 在现代计算机上一天都找不到的概率大概比 1/宇宙里的原子数 还小。 |
 | 33 churchmice 2020 年 2 月 24 日 via Android 有个数字货币就是用来找素数的 |
| 34 swulling 2020 年 2 月 24 日 @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 高了一个数量级。 |
 | 35 liaoliaojun 2020 年 2 月 24 日 实时计算生成所花费的时间太多，所以我认为是提前存储好的质数 |
| 36 Citrus 2020 年 2 月 24 日 @itskingname #16 那你有没有想过，如果你的随机数生成算法，运气这么不好的多次重复生成了同一个数，还导致你一天都没有生成到有用的数，那这个算法是不是有什么问题呢？？？ |
 | 37 siyemiaokube 2020 年 2 月 25 日 via iPhone @Mohanson 素数通项公式本来就能写出来，只是没有 O （ 1 ）公式 |
| 38 siyemiaokube 2020 年 2 月 25 日 via iPhone @swulling 有一些前人总结了某些范围内 miller robin 的 magic number 表，证明了完备性，wiki 上就有链接 |
| 39 geelaw 2020 年 2 月 25 日 via iPhone @liaoliaojun #35 提前存储素数是完全不安全的做法。只要 N 的一个质因数存在于预先存定的质数表里，就可以迅速分解 N。 |
 | 40 roland2015 2020 年 2 月 25 日 深入一点研究 RSA 算法，能找到不少问题的文章 |
 | 41 fbi007130 2020 年 2 月 25 日 因为面向的人不同 大学时候密码学课上把 RSA 分析得很透切，关于楼主提到的问题，也详尽分析过。 同时当时。。。针对 1024bit rsa 也已经有一些破解的办法 /手段了 |
 | 42 no1xsyzy 2020 年 2 月 26 日 @liaoliaojun 你大约需要 (10^41/41-10^40/40)*128/8/1024/1024/1024/1024 = 31107907577789752039967513.66592 PB 来存储这些素数。 |
Select Language