Хэш-функция, которая производит короткие хэши?
существует ли одностороннее шифрование, которое может принимать строку любой длины и создавать хэш из 10 символов? Я хочу создать достаточно уникальные идентификаторы, но на основе содержимого сообщения, а не случайно.
Я могу жить с ограничением сообщений целочисленными значениями, хотя, если строки произвольной длины невозможны. Однако в этом случае хэш не должен быть одинаковым для двух последовательных целых чисел.
8 ответов:
вы можете использовать любой общедоступный алгоритм хэширования (например. SHA-1), что даст вам немного более длительный результат, чем то, что вам нужно. Просто обрезать результат до нужной длины, что может быть достаточно хорошим.
например, в Python:
>>> import hashlib >>> hash = hashlib.sha1("my message".encode("UTF-8")).hexdigest() >>> hash '104ab42f1193c336aa2cf08a2c946d5c6fd0fcdb' >>> hash[:10] '104ab42f11'
Если вам не нужен алгоритм, который силен против преднамеренной модификации, я нашел алгоритм под названием adler32 это дает довольно короткие (~8 символов) результаты. Выберите его из выпадающего списка здесь, чтобы попробовать его:
вам нужно хэшировать содержимое, чтобы придумать дайджест. Есть много доступных хэшей, но 10 символов довольно мало для результирующего набора. В прошлом люди использовали CRC-32, который производит 33-битный хэш (в основном 4 символа плюс один бит). Существует также CRC-64, который производит 65-битный хэш. MD5, который производит 128-битный хэш (16 байт / символов), считается сломанным для криптографических целей, потому что можно найти два сообщения, которые имеют один и тот же хэш. Это должно пойти, не говоря, что каждый раз, когда вы создаете 16-байтовый дайджест из сообщения произвольной длины, вы получите дубликаты. Чем короче дайджест, тем больше риск столкновений.
однако ваше беспокойство о том, что хэш не будет похож для двух последовательных сообщений (будь то целые числа или нет), должно быть истинным со всеми хэшами. Даже одно битовое изменение в исходном сообщении должно привести к совершенно другому результату дайджеста.
Итак, используя что-то вроде CRC-64 (и base-64'ing результате) следует получить вас в районе, который вы ищете.
вы можете использовать существующий хэш-алгоритм, который производит что-то короткое, например MD5 (128 бит) или SHA1 (160). Затем вы можете сократить это еще больше, закрепив разделы дайджеста с другими разделами. Это увеличит вероятность столкновений, но не так плохо, как просто усечение дайджеста.
кроме того, вы можете включить длину исходных данных в качестве части результата, чтобы сделать его более уникальным. Например, XORing первая половина дайджеста MD5 со второй половиной будет результат в 64 бит. Добавьте 32 бита для длины данных (или ниже, если вы знаете, что длина всегда будет вписываться в меньшее количество битов). Это привело бы к 96-битному (12-байтовому) результату, который затем можно было бы превратить в 24-символьную шестнадцатеричную строку. Кроме того, вы можете использовать кодировку base 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='The
resultздесь используется больше, чем просто шестнадцатеричные символы (что вы получите, если вы использовалиhash.hexdigest()) Так что это менее вероятно, чтобы иметь столкновение (то есть, должно быть безопаснее усечь, чем шестнадцатеричный дайджест).Примечание: с помощью UUID4 (random). Смотрите http://en.wikipedia.org/wiki/Universally_unique_identifier для других типов.
вы можете использовать библиотеку hashids, которая имеет реализации для PHP, Javascript, Python и т. д. Для получения более подробной информации проверьте этой ссылке
Если вам нужно
"sub-10-character hash"вы могли бы использовать Флетчер-32 алгоритм, который производит хэш 8 символов (32 бита),CRC-32 или Адлер-32.CRC-32 медленнее, чем Adler32 в 20% - 100%.
Fletcher-32 немного надежнее, чем Adler-32. Он имеет более низкую вычислительную стоимость, чем контрольная сумма Адлера:Флетчер против Adler сравнения.
пример программы с несколькими Флетчер реализации приведены ниже:
#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; // '' 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 недостаточно сложен, чтобы конкурировать с сопоставимыми контрольными суммами.
Мне недавно понадобилось что-то вроде простой функции сокращения строк. В принципе, код выглядел примерно так (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