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

花了两天时间终于看懂 rsa 证明过程,真滴是拍案叫绝

  •  
  •   simonlu9 · 2020-11-03 14:33:37 +08:00 · 9185 次点击
    这是一个创建于 1242 天前的主题,其中的信息可能已经有所发展或是发生改变。

    贴上阮大神的博客 https://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

    当中涉及了中国同余定理,欧拉函数,补了这些基础算勉强看懂。了解到数学定理多么重要,一环紧扣一环,我在想当时是怎么发明,知道这些定理之后在倒推回去

    m^e ≡ c (mod n)
    c^d ≡ m (mod n)
    
    34 条回复    2020-11-04 16:36:31 +08:00
    qwertyegg
        1
    qwertyegg  
       2020-11-03 15:08:40 +08:00
    不要脸推一下我自己写的 intro tutorial

    https://github.com/DogtorDoggo/rsa-guide

    本来打算写一下要注意的坑,但是一直拖延到现在都没写
    easonHHH
        2
    easonHHH  
       2020-11-03 15:16:24 +08:00
    没了解之前就特别好奇,算法过程都是公开的,不就很容易破解吗;了解原理就明白了,牛皮,椭圆曲线加密也是
    simonlu9
        3
    simonlu9  
    OP
       2020-11-03 16:11:26 +08:00
    @easonHHH 言之有理
    kuro1
        4
    kuro1  
       2020-11-03 16:19:04 +08:00
    大三计算机网络安全其中一章
    vision1900
        5
    vision1900  
       2020-11-03 16:22:29 +08:00   ❤️ 1
    量子计算机:Hold my beer
    user8341
        6
    user8341  
       2020-11-03 16:26:28 +08:00   ❤️ 1
    楼主牛 X 啊。

    数学定理证明只给出一个完美的推理过程。没告诉我们作者如何想到这个 idea 的思考过程。
    FutherAll
        7
    FutherAll  
       2020-11-03 16:29:07 +08:00
    FutherAll
        8
    FutherAll  
       2020-11-03 16:29:44 +08:00
    @FutherAll 周末刚好写了一篇,感觉欧拉定理的证明部分比较麻烦
    hatebugs
        9
    hatebugs  
       2020-11-03 17:47:11 +08:00
    当年密码学老师给我们证明了好几节课,说实话听的很爽很顺畅,感觉很奇妙。现在证明的细节忘的差不多了。
    abersheeran
        10
    abersheeran  
       2020-11-03 17:59:31 +08:00
    嘿,建议找任一大学的公开课看看。比这个还详细的。
    kindjeff
        11
    kindjeff  
       2020-11-03 18:09:34 +08:00
    xenme
        12
    xenme  
       2020-11-03 18:21:51 +08:00 via iPhone
    之前见过更神奇的加密
    homomorphic encryption
    上次看到说微软还是谁有实现
    BIAOXYZ
        13
    BIAOXYZ  
       2020-11-03 19:26:20 +08:00   ❤️ 2
    准确说只是欧拉定理和扩展欧几里得算法,不涉及中国剩余定理。
    itskingname
        14
    itskingname  
       2020-11-03 19:29:02 +08:00 via iPhone   ❤️ 1
    lvybupt
        15
    lvybupt  
       2020-11-03 19:46:01 +08:00
    公钥加密想法来源于 DH 在 1976 年发表了一篇具有开创性的论文《密码学的新方向》(New Directions in Cryptography)
    这两个人也因为 DH 协议获得了图灵奖
    dlsflh
        16
    dlsflh  
       2020-11-03 19:47:32 +08:00 via Android
    @xenme 我记得是 IBM
    qwertqwert12345
        17
    qwertqwert12345  
       2020-11-03 21:58:37 +08:00
    离散数学课必讲的。。。。。。
    tonyaiken
        18
    tonyaiken  
       2020-11-04 01:10:52 +08:00 via iPhone   ❤️ 1
    @easonHHH 不公开的反而容易破解,因为安全性没有被广泛验证
    zzw1998
        19
    zzw1998  
       2020-11-04 02:18:19 +08:00
    我记得这是离散数学的一节课的内容
    Perry
        20
    Perry  
       2020-11-04 02:19:37 +08:00 via iPhone   ❤️ 1
    大学里没学过吗 🐶
    aliceclark
        21
    aliceclark  
       2020-11-04 03:43:02 +08:00   ❤️ 2
    当初自己上课的时候手写一遍 RSA,AES 的简化版简直是收获颇多
    constexpr
        22
    constexpr  
       2020-11-04 07:44:51 +08:00 via Android
    打扰了,看到数论就头大
    watzds
        23
    watzds  
       2020-11-04 08:15:42 +08:00 via Android
    大一还要用 c 实现这个算法呢,先写好大数加减乘除,素性检测,最后只实现到寻找大素数
    littlewing
        24
    littlewing  
       2020-11-04 09:01:49 +08:00 via iPhone
    我选择放弃
    p1gd0g
        25
    p1gd0g  
       2020-11-04 09:07:03 +08:00
    密码学研究生路过~
    有意思的密码算法可多了,只不过这个圈子还是太小众了。
    lingxi27
        26
    lingxi27  
       2020-11-04 09:44:59 +08:00
    实用的 rsa 和教科书的 rsa 还是很不一样的
    gunpowderfans
        27
    gunpowderfans  
       2020-11-04 10:05:26 +08:00
    所以大学信息安全专业的数学课程是最多的
    bsmagic
        28
    bsmagic  
       2020-11-04 10:11:57 +08:00
    RSA 的下一代是什么
    simonlu9
        29
    simonlu9  
    OP
       2020-11-04 11:16:46 +08:00
    @bsmagic 搞定大素数分解就可以下一代啦,目前还算比较安全吧
    aliceclark
        30
    aliceclark  
       2020-11-04 13:16:11 +08:00
    @bsmagic 目前还是挺看好量子计算机的大素数分解的,真正实用了之后真是不敢想象,那么多 RSA 的应用都要凉。
    反倒是对称加密对量子计算机还挺 resisted 的,还有好多后量子时代的加密的候选,什么 lattice 啦,超奇艺椭圆曲线啥的
    bsmagic
        31
    bsmagic  
       2020-11-04 15:06:29 +08:00
    @aliceclark 感觉量子计算机就是个噱头,目前来看都是差强人意。
    shm7
        32
    shm7  
       2020-11-04 15:44:45 +08:00
    好久前 信息安全课上的问题,不过 rsa 应该几个小时就能破解了现在。
    xenme
        33
    xenme  
       2020-11-04 15:47:35 +08:00
    @shm7 你这哪里来的结论?
    现在证书主流还是 RSA,几个小时,那不是到处都是劫持了。
    joydee
        34
    joydee  
       2020-11-04 16:36:31 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2733 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 12:43 · PVG 20:43 · LAX 05:43 · JFK 08:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.