产生短散列的散列函数？

有没有一种加密方法可以接受任意长度的字符串并产生一个小于10个字符的散列？我希望根据消息内容生成合理的惟一 ID，而不是随机生成。

但是，如果不能使用任意长度的字符串，我可以将消息限制为整数值。但是，在这种情况下，两个连续整数的哈希值不能相似。

216133 次浏览
小开
最佳答案

您可以使用任何常用的哈希算法(例如。SHA-1) ，这将给你一个比你需要的稍长的结果。只需将结果截断到所需的长度，这可能已经足够好了。

例如，在 Python 中:

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

你需要对内容进行处理，才能得出摘要。有许多哈希表可用，但是10个字符对于结果集来说非常小。很久以前，人们使用 CRC-32，它产生一个33位散列(基本上是4个字符加1位)。还有 CRC-64，它产生一个65位的散列。MD5生成128位散列(16字节/字符) ，因为可以找到具有相同散列的两条消息，所以为了加密的目的将其视为中断。不用说，每次从任意长度的消息创建一个16字节的摘要时，都会得到重复的消息。消化时间越短，碰撞的风险就越大。

但是，如果您担心两个连续消息(无论是否为整数)的哈希值不相似，那么对于所有哈希值都应该为真。即使是原始消息中的一个比特变化，也会产生截然不同的结果摘要。

因此，使用类似 CRC-64(和以64为基数的结果)应该可以让你找到你要找的邻居。

小开

只是总结了一个对我有帮助的答案(注意@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。

小开

我最近需要一个简单的字符串缩减函数。基本上，代码看起来像这样(前面是 C/C + + 代码) :

size_t ReduceString(char *Dest, size_t DestSize, const char *Src, size_t SrcSize, bool Normalize)
{
size_t x, x2 = 0, z = 0;


memset(Dest, 0, DestSize);


for (x = 0; x < SrcSize; x++)
{
Dest[x2] = (char)(((unsigned int)(unsigned char)Dest[x2]) * 37 + ((unsigned int)(unsigned char)Src[x]));
x2++;


if (x2 == DestSize - 1)
{
x2 = 0;
z++;
}
}


// Normalize the alphabet if it looped.
if (z && Normalize)
{
unsigned char TempChr;
y = (z > 1 ? DestSize - 1 : x2);
for (x = 1; x < y; x++)
{
TempChr = ((unsigned char)Dest[x]) & 0x3F;


if (TempChr < 10)  TempChr += '0';
else if (TempChr < 36)  TempChr = TempChr - 10 + 'A';
else if (TempChr < 62)  TempChr = TempChr - 36 + 'a';
else if (TempChr == 62)  TempChr = '_';
else  TempChr = '-';


Dest[x] = (char)TempChr;
}
}


return (SrcSize < DestSize ? SrcSize : DestSize);
}

它可能有比预期更多的碰撞，但它并不是用来作为密码杂凑函数的。如果碰撞太多，你可以尝试不同的乘法器(比如把37改成另一个素数)。这个代码片段的一个有趣特性是，当 Src 比 Dest 短时，Dest 最终得到的输入字符串是-is (0 * 37 + value = value)。如果您想在进程结束时获得“可读”的内容，Normalize 将以增加冲突为代价来调整转换后的字节。

来源:

Https://github.com/cubiclesoft/cross-platform-cpp/blob/master/sync/sync_util.cpp

小开

如果你不需要一个强大的算法来对抗有意的修改，我已经找到了一个称为 Adler32的算法，它可以产生非常短(约8个字符)的结果。从下拉列表中选择它来尝试一下:

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

小开

您可以使用现有的散列算法来生成简短的代码，比如 MD5(128位)或 SHA1(160)。然后可以通过将摘要的部分与其他部分 XORing 来进一步缩短这个时间。这将增加发生冲突的几率，但不会像简单地截断摘要那样糟糕。

此外，还可以将原始数据的长度作为结果的一部分，使其更加独特。例如，将 MD5摘要的前半部分与后半部分 XORing 会产生64位。为数据的长度增加32位(或者更低，如果你知道长度总是适合更少的位)。这将导致一个96位(12字节)的结果，然后您可以将其转换为一个24个字符的十六进制字符串。或者，您可以使用基64编码使其更短。

小开

如果你需要 "sub-10-character hash" 你可以使用 Fletcher-32算法，它产生8个字符哈希(32位) ，CRC-32或 阿德勒 -32。

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

Fletcher-32比 Adler-32稍微可靠一些，它的计算成本比 Adler 校验和 Fletcher 和 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算法不够复杂，无法与可比较的校验和竞争。

小开

只需在终端(在 MacOS 或 Linux 上)运行该程序:

crc32 <(echo "some string")

八个字长。

小开

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

~ echo test | xxhsum
2d7f1808da1fa63c  stdin
小开

您可以将 Hashlib库用于 Python。摇摆 _ 128和 摇摆 _ 256算法提供可变长度的散列。下面是一些工作代码(Python 3) :

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

注意，对于长度参数 X(例如5) ，该函数返回长度为 2倍的散列值。


提交答案