Функция хеширования, которая создает короткие хэши?

Question

Есть ли способ шифрования, который может взять строку любой длины и создать хэш длиной до 10 символов?Я хочу создавать достаточно уникальные идентификаторы, но на основе содержимого сообщения, а не случайным образом.

Я могу ограничить сообщения целочисленными значениями, если строки произвольной длины невозможны.Однако в этом случае хэш не должен быть одинаковым для двух последовательных целых чисел.

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

Вам нужно хешировать содержимое, чтобы составить дайджест.Доступно много хэшей, но 10 символов довольно мало для результирующего набора.В прошлом люди использовали CRC-32, который создает 33-битный хеш (в основном 4 символа плюс один бит).Существует также CRC-64, который создает 65-битный хэш.MD5, который создает 128-битный хеш (16 байтов / символов), считается неработающим для криптографических целей, поскольку можно найти два сообщения, которые имеют одинаковый хеш.Само собой разумеется, что каждый раз, когда вы создаете 16-байтовый дайджест из сообщения произвольной длины, вы получите дубликаты.Чем короче дайджест, тем больше риск коллизий.

Однако ваше беспокойство о том, что хеш-код не будет одинаковым для двух последовательных сообщений (целых или нет), должно быть истинным для всех хешей.Даже одно-битное изменение в исходном сообщении должно привести к совершенно другому результирующему дайджесту.

Таким образом, использование чего-то вроде CRC-64 (и результата base-64) должно привести к тому, что вы окажетесь поблизостиищу.

Answer 4

Вы можете использовать существующий алгоритм хеширования, который выдает что-то короткое, например, MD5 (128 бит) или SHA1 (160).Затем вы можете сократить это, используя XORing разделы дайджеста с другими разделами.Это увеличит вероятность коллизий, но не так плохо, как простое усечение дайджеста.

Кроме того, вы можете включить длину исходных данных как часть результата, чтобы сделать их более уникальными.Например, если XOR первой половины дайджеста MD5 со второй половиной, то получится 64 бита.Добавьте 32 бита для длины данных (или меньше, если вы знаете, что длина всегда будет соответствовать меньшему количеству бит).Это приведет к получению 96-битного (12-байтового) результата, который затем можно превратить в 24-символьную шестнадцатеричную строку.Кроме того, вы можете использовать кодировку base 64, чтобы сделать ее еще короче.

Answer 5

Просто суммирую ответ, который был мне полезен (обратите внимание на комментарий @ 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 6

Если вам нужно "sub-10-character hash", вы можете использовать алгоритм Fletcher-32 , который выдает 8-значный хэш (32 бита), CRC-32 или Adler-32 .

CRC-32 медленнее, чем Adler32, в 20% - 100% раз.

Fletcher-32 несколько надежнее, чем Adler-32.Он имеет меньшую вычислительную стоимость, чем контрольная сумма Адлера: Сравнение Флетчера и Адлера .

Пример программы с несколькими реализациями 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 7

Просто запустите это в терминале (в MacOS или Linux):

crc32 <(echo "some string")

8 символов.

Answer 8

Недавно мне понадобилось что-то вроде простой функции сокращения строк. По сути, код выглядел примерно так (код 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 заканчивается строкой ввода как есть (0 * 37 + значение = значение). Если вам нужно что-то «читаемое» в конце процесса, Normalize отрегулирует преобразованные байты за счет увеличения коллизий.

Источник:

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