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

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

  •  
  •   simonlu9 · 354 天前 · 8216 次点击
    这是一个创建于 354 天前的主题,其中的信息可能已经有所发展或是发生改变。

    贴上阮大神的博客 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   354 天前
    不要脸推一下我自己写的 intro tutorial

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

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

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