V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
andybest
V2EX  ›  问与答

怎样写一个hash算法其结果为8位包含大/小写字母和数字?

  •  
  •   andybest · 2013-06-18 19:09:06 +08:00 · 9031 次点击
    这是一个创建于 4175 天前的主题,其中的信息可能已经有所发展或是发生改变。
    鉴于目前安全事故频发,我打算简单写一个hash算法,输入例如“v2ex”然后算出一个8位包含大小写字母的密码

    怎样写这个hash算法?想听听各位的意见 :)
    35 条回复    2018-05-04 15:15:49 +08:00
    jkeylu
        1
    jkeylu  
       2013-06-18 19:12:26 +08:00 via Android
    放弃这个念头吧骚年
    binux
        2
    binux  
       2013-06-18 19:12:48 +08:00
    随便一个hash,base58取8位,over
    Sunyanzi
        3
    Sunyanzi  
       2013-06-18 19:15:12 +08:00
    @binux 说来这个 base58 是咋回事 ... hash 又不需要去除相似字符 ...

    不应该用 base62 么 ..?
    binux
        4
    binux  
       2013-06-18 19:16:46 +08:00
    @Sunyanzi 好吧,我数错了。。
    kuphrer
        5
    kuphrer  
       2013-06-18 19:25:17 +08:00 via iPad
    现有算法(sha-256之类的),加一个自定义密钥头。严格保管密钥头则密码坚不可摧。
    ejin
        6
    ejin  
       2013-06-18 20:23:52 +08:00
    加个盐值就可以了嘛。
    andybest
        7
    andybest  
    OP
       2013-06-18 22:04:58 +08:00
    @binux @Sunyanzi

    谢谢,但是使用base58/62 其中取出8位,理论上是可能不包含数字的吧?
    怎样确保取出的8个字符必然包含数字/大小写字母?
    Sunyanzi
        8
    Sunyanzi  
       2013-06-18 22:08:57 +08:00   ❤️ 1
    @andybest 把其他 hash 的结果分成三段 ... 一段 base10 一段 base36 ...

    然后用第三段的结果把上两个结果拼在一起 ...
    Sunyanzi
        9
    Sunyanzi  
       2013-06-18 22:09:50 +08:00   ❤️ 1
    我也手滑了 orz ... 一段 base10 一段 base52 ... 然后依据第三段的结果拼在一起 ...
    andybest
        10
    andybest  
    OP
       2013-06-18 22:13:55 +08:00
    @Sunyanzi 感谢,的确可以这样,但这样生成出的密码格式全部相同是不是显得有点搓?

    最好能完全随机,无规律性可言的情况下同时包含了大小写与数字
    (例如第1个字符可能是数字/大小写,不要第1个字符总是数字这样固定格式)
    andybest
        11
    andybest  
    OP
       2013-06-18 22:17:04 +08:00
    @Sunyanzi “一段 base10 一段 base52 ... 然后依据第三段的结果拼在一起”


    “第三段”是什么怎么生成?
    根据什么逻辑将base10与base52的两个hash结果拼在一起?结果的密码会是什么样子的?
    binux
        12
    binux  
       2013-06-18 22:19:53 +08:00   ❤️ 1
    @andybest 不满足再hash一次
    Sunyanzi
        13
    Sunyanzi  
       2013-06-18 22:22:02 +08:00   ❤️ 1
    @andybest 为什么会完全相同 ..?

    第三段会决定字母和数字的个数以及被拼接到什么位置 ... 这个完全取决于你如何处理呀~
    andybest
        14
    andybest  
    OP
       2013-06-18 22:37:19 +08:00
    @Sunyanzi 是。。关键是怎么组合,这个组合逻辑岂不是相当的复杂了?

    能否比 @binux 的循环hash取得满足条件的结果更加高效呢?
    Sunyanzi
        15
    Sunyanzi  
       2013-06-18 22:46:23 +08:00   ❤️ 1
    @andybest 循环 hash 从算法的角度讲不是 保证 肯定会有结果的 ...

    虽然概率微乎其微但是依然不是 0 概率不会引发死循环这样 ...

    那是个粗暴的办法 ... 组合的逻辑会更精巧复杂一些 ...

    效率其实不好说 ... 但我觉得多数情况下是用逻辑拼接来的要快些 ...
    andybest
        16
    andybest  
    OP
       2013-06-18 22:59:33 +08:00
    @Sunyanzi 恩,你说的对

    能否给个怎么用第三段拼接前两段的思路?
    breeswish
        17
    breeswish  
       2013-06-19 07:57:58 +08:00 via Android
    先纯数学任意方法hash,然后base52一下将二进制转换为大小写数字
    rrfeng
        18
    rrfeng  
       2013-06-19 08:58:40 +08:00
    8位很容易发生碰撞吧?
    andybest
        19
    andybest  
    OP
       2013-06-19 11:18:54 +08:00
    @breeswish baseXX理论人上是有可能是不包含数字或者不包含大/小写字母

    除了重新hash还有什么好办法解决?
    andybest
        20
    andybest  
    OP
       2013-06-19 11:19:44 +08:00
    @rrfeng 即使8位碰撞机率也基本可以忽略了...
    lichao
        21
    lichao  
       2013-06-19 11:22:21 +08:00
    一般来说 SHA256 + 随机盐 就可以应付了
    andybest
        22
    andybest  
    OP
       2013-06-19 11:28:21 +08:00
    @lichao sha不区分大小写,并且截取8位可能不满足包含数字/字母
    lichao
        23
    lichao  
       2013-06-19 11:32:29 +08:00
    @andybest 我觉得既然有现成的 hash 算法了,没必要自己再去实现一个 hash 算法了吧。
    而且你不觉得 8 位的 hash 很容易撞车吗?
    andybest
        24
    andybest  
    OP
       2013-06-19 11:41:13 +08:00
    @lichao 撞车无所谓阿

    实际上就是需求一个: 必然包含大/小写字母和数字 hash算法的思路

    想听听大家的想法
    zoho
        25
    zoho  
       2013-06-19 11:41:15 +08:00   ❤️ 1
    (1)根据已知 hash 算法生成一个较长的 X 值,分为 7 段;X1 到 X7;

    (2)用 X1,X2,X3 分别确定大写字母,小写字母,数字三部分的各自长度;

    (3)分别用 base26,base26,base10 从 X4,X5,X6 中截取前面三部分的字符;

    (4)利用 X7 值打乱字符串的顺序。
    andybest
        26
    andybest  
    OP
       2013-06-19 11:45:04 +08:00
    @zoho 感谢,好想法

    请问:(4)利用 X7 值打乱字符串的顺序。

    这个是使用X7安排 三部分字符 组合逻辑吗?
    这一部分怎么实现可以给个例子吗?

    比如X7是xxx, 在base26/26/10分别为xxx的时候如何组合。
    就是怎样利用X7组合这三个段?
    Sunyanzi
        27
    Sunyanzi  
       2013-06-19 11:54:26 +08:00   ❤️ 1
    @andybest 这个其实交由你自己来决定 ... 我可以提供一个参考思路 ...

    假设第三段是个 20 位的 hexstring ... 先取前四位 ... 模 8 取得一个值 ...

    如果这个值等于 0 的话继续往下取一位也就是取前五位模 8 ... 直到取得非零值为止 ...

    如果十二位都走完了模依然为零 ... 说明这个 hexstring 由 1 0 和 8 组成 ...

    我们为这种特殊情况手动定义一个值 ... 比如 3 ... 这个值代表结果中的数字个数 ...

    现在假设我们用前五位取到了非零值 ... 以 5 为例吧 ...

    后面还剩下十五位 ... 把第三段的开头一位补进来凑够十六位 ... 然后两位一分组 ...

    现在我们得到了八个两位的 hexstring ...

    前五个 hexstring 模 10 得到五个数字 ... 后三个 hexstring 模 26 得到三个字母 ...

    继续处理这八个 hexstring ... 每个 hexstring 取第一位 ... 这代表结果的排序 ...

    按照这个排序把我们得到的字母与数字放入对应的位置 ...

    假如对应的位置已经有值的话就往后推一位 ... 直到可以放入为止 ...

    八位都填入之后 ... 去除没有内容的空位 ...

    我们就最终得到了一个肯定包含字母与数字的八位 hash ...

    写的比较着急可能有点乱 ... 但大体意思是这样 ... 能看懂么 ..?
    Sunyanzi
        28
    Sunyanzi  
       2013-06-19 11:57:54 +08:00   ❤️ 1
    @Sunyanzi 修正错误 ... 行 4 ... 十二位 改为 二十位 ...
    zoho
        29
    zoho  
       2013-06-19 11:59:25 +08:00   ❤️ 1
    @andybest 模运算啊,将 X7 再分为 7 个数,第一个数模 8 得到该选取 8 个字符中第几个字符,第二个数模 7 得到该选取剩下 7 个字符中的第几个字符,一直下去。。。
    andybest
        30
    andybest  
    OP
       2013-06-19 12:05:22 +08:00
    @Sunyanzi 完全明白,感谢!这个方法很好,我打算就这么做
    andybest
        31
    andybest  
    OP
       2013-06-19 12:07:51 +08:00
    @zoho 感谢,你的方法结合 @Sunyanzi 的解决方案我就很明白了

    这应该是最优的解决方案了吧!
    notedit
        32
    notedit  
       2013-06-19 12:09:12 +08:00   ❤️ 1
    从base62中截取6位 其他两位根据一定的算法一个是数字一个是字母
    Sunyanzi
        33
    Sunyanzi  
       2013-06-19 12:19:14 +08:00   ❤️ 1
    @andybest 取模是相对最容易想到的解决方案 ... 对应一般情况也够用 ...

    如果考虑到海量样本数量下平衡所有字符的出现率什么的问题 ... 还可以做的更复杂 ...

    基本上说到底这就是一个数字到字符的转化 ... 怎么实现还是看个人创意的 ...
    andybest
        34
    andybest  
    OP
       2013-06-19 13:07:00 +08:00
    @Sunyanzi 非常感谢! :)
    wlwood
        35
    wlwood  
       2018-05-04 15:15:49 +08:00
    8 位太短了吧?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2676 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 12:16 · PVG 20:16 · LAX 04:16 · JFK 07:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.