Хеш-функция, которая производит короткие хеши?

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

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

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

Например, в Python:

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

Если вам не нужен алгоритм, устойчивый к преднамеренной модификации, я нашел алгоритм под названием adler32, который дает довольно короткие (~ 8 символов) результаты. Выберите его из раскрывающегося списка, чтобы попробовать:

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

Вам нужно хешировать содержимое, чтобы получить дайджест. Доступно много хешей, но 10 символов - это довольно мало для набора результатов. Раньше люди использовали CRC-32, который выдает 33-битный хеш (в основном 4 символа плюс один бит). Также существует 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 для других типов.

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

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

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

CRC-32 медленнее Adler32 в 20% - 100%.

Флетчер-32 чуть надежнее Адлера-32. У него более низкие вычислительные затраты, чем у контрольной суммы Адлера: сравнение Флетчера и Адлера .

Ниже приводится пример программы с несколькими реализациями Флетчера:

    #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")

Длина 8 символов.

Вы можете использовать библиотеку hashlib для Python. В shake_128 и shake_256 алгоритмы обеспечивают переменные хешей длины. Вот рабочий код (Python3):

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

Обратите внимание, что с параметром длины x (в примере 5) функция возвращает хеш-значение длины 2x .

Сейчас 2019 год, и есть варианты получше. А именно xxhash .

~ echo test | xxhsum                                                           
2d7f1808da1fa63c  stdin

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

Источник:

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