Есть ли способ шифрования, который может взять строку любой длины и создать хэш длиной до 10 символов? Я хочу создать достаточно уникальный идентификатор, но на основе содержимого сообщения, а не случайным образом.
Однако я могу ограничить сообщения целочисленными значениями, если строки произвольной длины невозможны. Однако в этом случае хэш не должен быть одинаковым для двух последовательных целых чисел.
Вы можете использовать любой общедоступный алгоритм хеширования (например, 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 result), вы должны найти вас по соседству, который вы ищете.
Просто суммирую ответ, который был мне полезен (отметив комментарий @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). Затем вы можете сократить это далее секциями XORing дайджестов другими разделами. Это увеличит вероятность столкновений, но не так плохо, как просто усечение дайджеста.
Кроме того, вы можете включить длину исходных данных как часть результата, чтобы сделать его более уникальным. Например, XORing первой половины дайджест 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. Он имеет меньшую вычислительную стоимость, чем контрольная сумма Адлера: сравнение Флетчера и Адлера.
Пример программы с несколькими реализациями 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 недостаточно сложен, чтобы конкурировать с сопоставимыми контрольными суммами.
Вы можете использовать библиотеку hashids, которая имеет реализации для PHP, Javascript, Python и т.д. Подробнее см. эту ссылку
Просто запустите это в терминале (в MacOS или Linux):
crc32 <(echo "some string")
длиной 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 + value = значение). Если вам нужно что-то "читаемое" в конце процесса, Normalize отрегулирует преобразованные байты за счет увеличения коллизий.
Источник:
https://github.com/cubiclesoft/cross-platform-cpp/blob/master/sync/sync_util.cpp