产生短哈希的哈希函数？

Question

是否有单向加密,可以采用任意长度的字符串并产生一个10字符以下的哈希？我想生成合理的唯一ID,但是基于消息内容,而不是随机的.

但是,如果不能使用任意长度的字符串,我可以将消息约束为整数值.但是,在这种情况下,对于两个连续的整数,散列必须不相似.

Answer 1

您可以使用任何常用的哈希算法(例如SHA-1),这会给您一个比您需要的结果略长的结果.只需将结果截断为所需的长度,这可能足够好.

例如,在Python中:

>>> import hashlib
>>> hash = hashlib.sha1("my message".encode("UTF-8")).hexdigest()
>>> hash
'104ab42f1193c336aa2cf08a2c946d5c6fd0fcdb'
>>> hash[:10]
'104ab42f11'

Answer 2

如果你不需要一个强烈反对故意修改的算法,我发现了一个名为adler32的算法,它可以产生相当短的(~8个字符)结果.从下拉列表中选择它以试用它:

http://www.sha1-online.com/

Answer 3

您可以使用Python的hashlib库。的shake_128和shake_256算法提供可变长度的散列。这是一些工作代码（Python3）：

import hashlib
>>> my_string = 'hello shake'
>>> hashlib.shake_256(my_string.encode()).hexdigest(5)
'34177f6a0a'

请注意，使用长度参数x（示例中为 5），该函数返回长度为2x的哈希值。

Answer 4

如果您需要，"sub-10-character hash" 您可以使用Fletcher-32算法，该算法产生 8 个字符哈希（32 位）、 CRC-32或Adler-32。

CRC-32 比 Adler32 慢 20% - 100%。

Fletcher-32 比 Adler-32 稍微可靠一些。它的计算成本低于 Adler 校验和：Fletcher vs Adler 比较。

下面给出了一个带有一些 Fletcher 实现的示例程序：

    #include <stdio.h>
    #include <string.h>
    #include <stdint.h> // for uint32_t

    uint32_t fletcher32_1(const uint16_t *data, size_t len)
    {
            uint32_t c0, c1;
            unsigned int i;

            for (c0 = c1 = 0; len >= 360; len -= 360) {
                    for (i = 0; i < 360; ++i) {
                            c0 = c0 + *data++;
                            c1 = c1 + c0;
                    }
                    c0 = c0 % 65535;
                    c1 = c1 % 65535;
            }
            for (i = 0; i < len; ++i) {
                    c0 = c0 + *data++;
                    c1 = c1 + c0;
            }
            c0 = c0 % 65535;
            c1 = c1 % 65535;
            return (c1 << 16 | c0);
    }

    uint32_t fletcher32_2(const uint16_t *data, size_t l)
    {
        uint32_t sum1 = 0xffff, sum2 = 0xffff;

        while (l) {
            unsigned tlen = l > 359 ? 359 : l;
            l -= tlen;
            do {
                sum2 += sum1 += *data++;
            } while (--tlen);
            sum1 = (sum1 & 0xffff) + (sum1 >> 16);
            sum2 = (sum2 & 0xffff) + (sum2 >> 16);
        }
        /* Second reduction step to reduce sums to 16 bits */
        sum1 = (sum1 & 0xffff) + (sum1 >> 16);
        sum2 = (sum2 & 0xffff) + (sum2 >> 16);
        return (sum2 << 16) | sum1;
    }

    int main()
    {
        char *str1 = "abcde";  
        char *str2 = "abcdef";

        size_t len1 = (strlen(str1)+1) / 2; //  '\0' will be used for padding 
        size_t len2 = (strlen(str2)+1) / 2; // 

        uint32_t f1 = fletcher32_1(str1,  len1);
        uint32_t f2 = fletcher32_2(str1,  len1);

        printf("%u %X \n",    f1,f1);
        printf("%u %X \n\n",  f2,f2);

        f1 = fletcher32_1(str2,  len2);
        f2 = fletcher32_2(str2,  len2);

        printf("%u %X \n",f1,f1);
        printf("%u %X \n",f2,f2);

        return 0;
    }

输出：

4031760169 F04FC729                                                                                                                                                                                                                              
4031760169 F04FC729                                                                                                                                                                                                                              

1448095018 56502D2A                                                                                                                                                                                                                              
1448095018 56502D2A                                                                                                                                                                                                                              

同意测试向量：

"abcde"  -> 4031760169 (0xF04FC729)
"abcdef" -> 1448095018 (0x56502D2A)

Adler-32 对几百字节的短消息有一个弱点，因为这些消息的校验和对 32 个可用位的覆盖很差。检查这个：

Adler32 算法不够复杂，无法与可比较的校验和竞争。

Answer 5

您需要散列内容以提供摘要.有许多哈希可用,但结果集中10个字符非常小.回过头来,人们使用CRC-32,它产生33位散列(基本上是4个字符加1位).还有CRC-64产生65位散列.产生128位散列(16字节/字符)的MD5因加密目的而被视为已损坏,因为可以找到具有相同散列的两条消息.不用说,任何时候你从任意长度的消息中创建一个16字节的摘要,你最终会得到重复.摘要越短,碰撞的风险就越大.

但是,对于两个连续消息(无论是否为整数),散列不相似的问题应该适用于所有散列.即使原始消息中的单个位改变也应该产生截然不同的结果摘要.

因此,使用像CRC-64(以及结果的基础64)这样的东西可以让你进入你正在寻找的邻居.

Answer 6

只是总结一个对我有用的答案（注意@erasmospunk有关使用base-64编码的评论）。我的目标是要有一个短串，这串串大都是独特的...

我不是专家，因此，如果有任何明显的错误，请更正此错误（在Python中再次像接受的答案一样）：

import base64
import hashlib
import uuid

unique_id = uuid.uuid4()
# unique_id = UUID('8da617a7-0bd6-4cce-ae49-5d31f2a5a35f')

hash = hashlib.sha1(str(unique_id).encode("UTF-8"))
# hash.hexdigest() = '882efb0f24a03938e5898aa6b69df2038a2c3f0e'

result = base64.b64encode(hash.digest())
# result = b'iC77DySgOTjliYqmtp3yA4osPw4='

在result这里使用不止十六进制字符（如果你使用你会得到什么hash.hexdigest()），所以它不太可能有冲突（即，应该是较安全十六进制消化截断）。

注意：使用UUID4（随机）。有关其他类型，请参见http://en.wikipedia.org/wiki/Universally_unique_identifier。

Answer 7

只需在终端（在 MacOS 或 Linux 上）运行它：

crc32 <(echo "some string")

8 个字符长。

Answer 8

您可以使用现有的哈希算法来生成短的内容,例如MD5(128位)或SHA1(160).然后,您可以通过将摘要的部分与其他部分进行异或来进一步缩短.这将增加碰撞的机会,但不会像简单地截断摘要那样糟糕.

此外,您可以将原始数据的长度作为结果的一部分,以使其更加独特.例如,使用后半部分对MD5摘要的前半部分进行异或将导致64位.为数据长度添加32位(如果知道长度总是适合更少的位,则更低).这将导致96位(12字节)结果,然后您可以将其转换为24个字符的十六进制字符串.或者,您可以使用base 64编码使其更短.

Answer 9

现在是 2019 年，有更好的选择。即，xxhash。

~ echo test | xxhsum                                                           
2d7f1808da1fa63c  stdin