V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
fyyz
V2EX  ›  JavaScript

为什么密码必须要用到大素数

  •  
  •   fyyz · 2016-03-22 01:12:50 +08:00 via Android · 6059 次点击
    这是一个创建于 3153 天前的主题,其中的信息可能已经有所发展或是发生改变。
    这是看到最近的某帖子的疑问。
    经常看到素数与密码有关,但是不是很懂为什么素数与密码有这么深的关系,而且我也只知道现代的密码是通过分解大素数实现的,至于为什么要用大素数,也不是很懂。
    23 条回复    2016-03-24 10:09:58 +08:00
    ffffwh
        1
    ffffwh  
       2016-03-22 01:16:55 +08:00 via iPad
    RSA 的实现,阮一峰有篇拾人牙慧的,还不错
    UnisandK
        2
    UnisandK  
       2016-03-22 01:20:36 +08:00
    RSA 算法基于一个十分简单的数论事实:将两个大素数相乘十分容易·但是想分解它们的乘积却极端困难,因此可以将乘积公开作为加密密钥
    honeycomb
        3
    honeycomb  
       2016-03-22 01:51:49 +08:00   ❤️ 2
    vanxining
        4
    vanxining  
       2016-03-22 01:58:35 +08:00
    将所有不太大的素数都乘一遍不就行了?
    chrishine
        5
    chrishine  
       2016-03-22 02:23:26 +08:00 via Android   ❤️ 1
    一个问题的逆问题是难问题。
    大数可能的解空间会非常大,素数是因为素数本身的性质。
    fashioncj
        6
    fashioncj  
       2016-03-22 02:36:27 +08:00 via iPhone
    @vanxining n 方
    7timesonenight
        7
    7timesonenight  
       2016-03-22 03:59:20 +08:00
    简而言之:
    问:“你说你的加密算法安全, 凭什么?”, 答:“基于数学的 xxx 不可解问题”
    YUX
        8
    YUX  
       2016-03-22 04:31:50 +08:00 via Android
    因为对于大数的因数分解在目前是困难的
    这一现状可能会在数论有相关重大突破后改善
    SoloCompany
        9
    SoloCompany  
       2016-03-22 05:27:52 +08:00
    @vanxining 本来想类比一下的,还是直接丢一个 wiki 吧 https://zh.wikipedia.org/wiki/%E7%A7%80%E7%88%BE%E6%BC%94%E7%AE%97%E6%B3%95
    bombless
        10
    bombless  
       2016-03-22 06:06:11 +08:00 via Android   ❤️ 1
    其实很多密码系统用的不是数论而是代数。
    不过非对称性加密似乎确实都是数论。
    dndx
        11
    dndx  
       2016-03-22 07:00:56 +08:00
    也不一定,椭圆曲线加密就跟素数没啥关系。
    popil1987
        12
    popil1987  
       2016-03-22 08:55:15 +08:00
    答案在 @honeycomb 给出的链接的第二部分
    http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
    搜索“那么,有无可能在已知 n 和 e 的情况下,推导出 d ”
    crystom
        13
    crystom  
       2016-03-22 09:47:44 +08:00
    据说有数学协会给能破解 RSA 的人设了个 100 万美元的奖
    然而假如真能破解,可以赚的钱比 100 万不知道高到哪里去了
    shyling
        14
    shyling  
       2016-03-22 10:02:22 +08:00
    因为“ 2 个素数相乘容易,分解回 2 个素数不容易”
    amustart
        15
    amustart  
       2016-03-22 10:31:37 +08:00
    因为基于大素数分解是数学上的一个复杂问题,既然数学家都不能很好解决,那么正好就用在加密上呗
    jyhmijack
        16
    jyhmijack  
       2016-03-22 10:38:24 +08:00
    单向陷门函数
    zacard
        17
    zacard  
       2016-03-22 10:54:11 +08:00
    又学到了。。。
    msg7086
        18
    msg7086  
       2016-03-22 13:48:38 +08:00
    @SoloCompany 本来以为是什么科普知识还想读一下的,打开看了一眼还是决定关掉搬砖去了。
    Felldeadbird
        19
    Felldeadbird  
       2016-03-22 15:58:22 +08:00
    瞬间觉得自己遇到硬伤了。自己写的只不过过过家代码。
    Viztor
        20
    Viztor  
       2016-03-22 16:03:22 +08:00
    “将两个大素数相乘十分容易·但是想分解它们的乘积却极端困难”

    本质上是让解出密码的成本大于获取到的信息的价值。比如一个 RSA 可能数百年解开。到时候秘密也不是秘密了。
    iF2007
        21
    iF2007  
       2016-03-22 20:16:04 +08:00
    @dndx 曲线是定义在 Z_p 域上的,明显用了大素数
    kkzxak47
        22
    kkzxak47  
       2016-03-22 22:57:25 +08:00
    没别的就是特别难算,如果你找到别的类似的正向计算容易 /逆向困难的问题也可以拿来做加密的基础。
    dndx
        23
    dndx  
       2016-03-24 10:09:58 +08:00
    @iF2007 孤陋寡闻了,感谢指出
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5762 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 06:12 · PVG 14:12 · LAX 22:12 · JFK 01:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.