V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
itskingname
V2EX  ›  分享发现

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

  •  
  •   itskingname · 2020-02-24 09:43:46 +08:00 · 3941 次点击
    这是一个创建于 1495 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

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

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

    42 条回复    2020-02-26 10:41:39 +08:00
    shintendo
        1
    shintendo  
       2020-02-24 09:55:34 +08:00
    应该是生成足够位数的随机数,判定是不是质数,不是就再取一个
    itskingname
        2
    itskingname  
    OP
       2020-02-24 09:59:21 +08:00
    @shintendo 看了源代码才知道,找 p 和 q 的算法太简单粗暴了。运气不好的话,算一天都遇不上。
    Citrus
        3
    Citrus  
       2020-02-24 10:00:06 +08:00   ❤️ 6
    1. 个人并不认为这是教程的缺陷,因为如何选大素数可以单独拎出来说一整篇文章,完全没必要在 RSA 的文章里详细说。就像我告诉你如何检测牛奶的成分,会告诉你取一杯牛奶,但是不会把《奶牛的产后护理》一并附上
    2. 请看仔细,Python 并不是从 2 3 5 7 这样一个个的数到足够大。我不知道你是怎么把这段源码理解成这样的。。。这样数每次生成密钥还不到天荒地老。而且一个个数上去只要稍微会一点算法的人都知道是没必要的。因为素数都是各自独立的,找一个大素数完全没必要从 2 数上来
    3. 关键函数:rsa.randnum.read_random_odd_int(nbits)
    Citrus
        4
    Citrus  
       2020-02-24 10:01:30 +08:00
    @itskingname 一天都遇不到的结论是如何得出的?请给出你的计算。RSA 的素数获取是有数学论证的,请不要不给证据的直接猜想。
    coderluan
        5
    coderluan  
       2020-02-24 10:02:52 +08:00
    @shintendo 我记得应该是从足够位数的最小数开始递增,直到找到一个质数。

    PS:生成质数算是和正经问题,但是说这个是别人文章的缺陷就太扯了,我感觉看 RSA 文章的人,是有能力搜索解决这个问题的,写文章不可能所有东西都说清楚的。
    shintendo
        6
    shintendo  
       2020-02-24 10:07:34 +08:00
    @coderluan 印象中第一个数是随机取的,往后开始递增
    @itskingname 不会遇不到,素数的密度有数学论证的
    itskingname
        7
    itskingname  
    OP
       2020-02-24 10:09:08 +08:00
    @Citrus 2,3,5 是我还没有看源代码的时候猜的,发了这篇帖子我去看了一下源代码,然后截图贴过来。因为怕过了 6 分钟改不了了,所以贴了图又直接发。导致前面的文字没有修改
    est
        8
    est  
       2020-02-24 10:11:08 +08:00 via Android
    这就是为啥喊不要自己造加密库轮子的原因
    itskingname
        9
    itskingname  
    OP
       2020-02-24 10:11:25 +08:00
    @Citrus #4,因为它的 randomnum 这个模块里面,获取随机计数是没有去重的。运气不好的情况下,始终获取的都是非质数的奇数。而且会重复获得。
    itskingname
        10
    itskingname  
    OP
       2020-02-24 10:13:04 +08:00
    @shintendo 它不是递增计算的。它就是不停获取这么多位的随机奇数,然后反复验证是不是质数。
    swulling
        11
    swulling  
       2020-02-24 10:14:01 +08:00 via iPhone
    @itskingname #2 一天都找不到?你可以自己跑下 benchmark 看看
    mxT52CRuqR6o5
        12
    mxT52CRuqR6o5  
       2020-02-24 10:18:24 +08:00 via Android
    在数学上去验证一个数是不是素数确实是很慢的,所以你会想不通,但实际操作是现在有快速验证一个数是否是素数的方法,可以快速判断一个数是否是工程实践中可用的素数(验出来的数大概率是素数)
    itskingname
        13
    itskingname  
    OP
       2020-02-24 10:24:12 +08:00
    @swulling 我都说了在运气不好的情况下。现实中不容易出现这样的极端情况。
    falsemask
        14
    falsemask  
       2020-02-24 10:31:03 +08:00
    Miller-Rabin 素数检测,可以了解一下,java BigInteger 类用的是这个算法
    Mohanson
        15
    Mohanson  
       2020-02-24 10:36:32 +08:00   ❤️ 3
    素数除了产设随机数再判断是否素数, 没有其它方法了吧?

    如果有的话, 等于"找到了素数通项公式"...
    itskingname
        16
    itskingname  
    OP
       2020-02-24 10:44:21 +08:00
    @Mohanson 产生随机数再判断,在大多数情况下效果不错,但极端情况下就很慢,因为 python-rsa 库里面没有做去重处理,可能运气不好多次产生同一个非质数奇数。

    而从最小的 nbit 奇数开始逐渐增加 2,一个一个遍历,不会重复。效率平庸,但不容易出现极端情况。
    ETiV
        17
    ETiV  
       2020-02-24 10:49:21 +08:00 via iPhone
    #14 +1

    but 那个算法并不能保证被检测的数 100%是质数
    但是够快
    swulling
        18
    swulling  
       2020-02-24 10:50:36 +08:00   ❤️ 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,那么基本上对统计学没有实际的逻辑概念
    mxT52CRuqR6o5
        19
    mxT52CRuqR6o5  
       2020-02-24 10:52:53 +08:00 via Android
    @itskingname 你这样就不够安全了,生成素数是一次性操作,慢一点也没关系,安全才是第一目的,慢不慢什么的无所谓的,不要本末倒置了
    swulling
        20
    swulling  
       2020-02-24 11:04:02 +08:00
    @itskingname #16

    1. 如果顺序遍历,那么你的 p 和 q 不是都被人知道了么?这个还有什么安全性可言?

    2. #17 我记得 Miller Rabin 通过一些方法可以在特定的范围内,比如 2 的 32 次方内,确定 100%是否为素数。不太懂,有懂的可以补充

    3. 其实工程上并不需要 100%的准确,因为验证素数足够快,所以随机选了极大次,都不是素数的概率应该非常的低。具体多少我算不出来,但是应该有人能够算出来。如果这个概率低到了和宇宙射线把你的 bit 反转的概率都还要低,真的要从工程上讨论它么?
    Mutoo
        21
    Mutoo  
       2020-02-24 11:13:01 +08:00
    费马小定理了解一下,一个快速确定一个数是否质数的方法。
    crab
        22
    crab  
       2020-02-24 11:17:10 +08:00
    swulling
        23
    swulling  
       2020-02-24 11:22:23 +08:00   ❤️ 2
    大概算了下,可能不太准确。2^128 位差不多是在 10^40 左右,1~10^41 中,素数密度大约是 1/41 (根据素数密度定律) [实际上选择的范围比这个小,密度会更低,但是也就是 1/4x 而已,不会有大的影响] 。

    根据 benchmark,一次验证素数是 0.5ms 。那么 1000 次( 0.5s )内随机挑选的数都不是素数的概率 (40/41)^1000,大概是 10^-11 次方的概率,这个概率低到真的没有任何工程上的考虑价值。
    itskingname
        24
    itskingname  
    OP
       2020-02-24 11:28:49 +08:00
    @mxT52CRuqR6o5 #19 你这样说确实有道理。不能挨着遍历。
    itskingname
        25
    itskingname  
    OP
       2020-02-24 11:32:30 +08:00
    @swulling #23 用数字和概率说就很清楚了,23 楼可以说服我。但你前面楼层只提 benchmark 就没有什么说服力。
    BinRelay
        26
    BinRelay  
       2020-02-24 11:45:29 +08:00
    要是告诉你关于 rsa 的考试题目 一般 pq 都是计算 20 以内的质数你会不会认为考试不合理……
    richard1122
        27
    richard1122  
       2020-02-24 11:56:03 +08:00


    可是维基百科这里清楚的写了怎么找啊
    kindjeff
        28
    kindjeff  
       2020-02-24 12:05:37 +08:00
    每次看到 RSA 的数学问题一定会回复这篇文章

    http://www.matrix67.com/blog/archives/5100
    tzm41
        29
    tzm41  
       2020-02-24 12:11:54 +08:00
    标题:“目前 RSA 算法相关的教程和文章都有一个根本性缺陷”。
    正文:“我现在就问你,你给我找两个质数,每个质数要超过 100 位数。你能在短时间找出来吗?”
    已知:《 Introduction to Modern Cryptography 》第 303 页,8.2.1 章为《 Generating Random Primes 》。详细讨论了和 python-rsa 库一样的算法,以及 Bertrand’s postulate 和 Miller–Rabin test。
    结论:思而不学则怠。
    pangleon
        30
    pangleon  
       2020-02-24 12:17:04 +08:00
    @swulling 有理有据 令人信服 这楼主也是没谁了 年轻真好
    nathanw
        31
    nathanw  
       2020-02-24 12:35:12 +08:00 via iPhone
    你这“运气不好”表述还没有论文来的专业
    geelaw
        32
    geelaw  
       2020-02-24 13:11:06 +08:00 via iPhone   ❤️ 2
    素数定理保证一个 n 位随机数是质数的概率是 Omega(1/n),因此在 O(nk) 次尝试中仍然不出现一个质数的概率是 2^(-Omega(k))。

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

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

    在现代计算机上一天都找不到的概率大概比 1/宇宙里的原子数 还小。
    churchmice
        33
    churchmice  
       2020-02-24 14:45:17 +08:00 via Android
    有个数字货币就是用来找素数的
    swulling
        34
    swulling  
       2020-02-24 15:02:48 +08:00
    @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
        35
    liaoliaojun  
       2020-02-24 15:07:03 +08:00
    实时计算生成所花费的时间太多,所以我认为是提前存储好的质数
    Citrus
        36
    Citrus  
       2020-02-24 15:14:01 +08:00
    @itskingname #16 那你有没有想过,如果你的随机数生成算法,运气这么不好的多次重复生成了同一个数,还导致你一天都没有生成到有用的数,那这个算法是不是有什么问题呢???
    siyemiaokube
        37
    siyemiaokube  
       2020-02-25 00:25:37 +08:00 via iPhone
    @Mohanson 素数通项公式本来就能写出来,只是没有 O ( 1 )公式
    siyemiaokube
        38
    siyemiaokube  
       2020-02-25 00:28:14 +08:00 via iPhone
    @swulling 有一些前人总结了某些范围内 miller robin 的 magic number 表,证明了完备性,wiki 上就有链接
    geelaw
        39
    geelaw  
       2020-02-25 05:28:27 +08:00 via iPhone
    @liaoliaojun #35 提前存储素数是完全不安全的做法。只要 N 的一个质因数存在于预先存定的质数表里,就可以迅速分解 N。
    roland2015
        40
    roland2015  
       2020-02-25 10:09:50 +08:00
    深入一点研究 RSA 算法,能找到不少问题的文章
    fbi007130
        41
    fbi007130  
       2020-02-25 13:52:57 +08:00
    因为面向的人不同
    大学时候密码学课上把 RSA 分析得很透切,关于楼主提到的问题,也详尽分析过。
    同时当时。。。针对 1024bit rsa 也已经有一些破解的办法 /手段了
    no1xsyzy
        42
    no1xsyzy  
       2020-02-26 10:41:39 +08:00
    @liaoliaojun 你大约需要 (10^41/41-10^40/40)*128/8/1024/1024/1024/1024 = 31107907577789752039967513.66592 PB 来存储这些素数。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2606 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 15:36 · PVG 23:36 · LAX 08:36 · JFK 11:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.