sha-1 когда-либо производит коллизии для входных сигналов меньше чем 160 битов?

Кто-нибудь знает, ша-1 или альтернатива, гарантированно не произвести коллизии

Хеш-функции были разработаны так, чтобы не вызывать коллизий, но ничто не "гарантировано". Напротив, гарантировано, что столкновения будут, потому что пространство сообщений практически неограничено, а количество возможных хешей ограничено.

SHA-1, однако, оказался устойчивым к столкновениям , и это лучшее, на что можно надеяться.

Я не знаю, какие хэш-функции избегают коллизий, но, если вы не можете найти здесь ответ , хорошей отправной точкой может быть Perfect Hash Function в Википедии. На этой странице:

Идеальная хеш-функция для множества S - это хеш-функция, которая отображает различные элементы в S к различным целым числам, без наездов.

На этой странице есть несколько ссылок на дополнительную информацию, которые могут быть вам полезны.

Сказав это, можете ли вы сказать, зачем вам нужна идеальная функция has? Возможно, есть другие способы выполнить то, что вы хотите, без необходимости в этом свойстве, и кто-то из присутствующих может сделать предложение.

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

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

Если вы хотите вычислить секретную перестановку из 128 бит в 128 бит, одно простое решение - использовать 128-битный блочный шифр, такой как AES, с фиксированным, но секретным ключом. Вы, конечно, должны иметь возможность хранить ключ в секрете вечно, иначе у вас ничего не будет.

Хеширование "маловероятно" для создания каких-либо дубликатов, но нет никаких гарантий. На С другой стороны, любая симметричная схема шифрования будет выдавать 128 бит на 128 бит на входе, и гарантируем отсутствие дубликатов.

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

Для достаточно больших размеров битов, я думаю, дискретное возведение в степень - это функция 1: 1, но реверсирование невозможно с вычислительной точки зрения. Я не уверен, насколько требуется «большой». Код для необычно медленной (но концептуально понятной) реализации:

unsigned long spin_once(unsigned long dat)
{
  if (dat & 1)
    return (dat >> 1);
  return (dat >> 1) ^ SomeMagicNumber;
}

unsigned long hash(unsigned long dat)
{
  unsigned long i,ret;

  if (dat == 0xFFFFFFFF)
    return 0;
  ret = 1;
  for (i=0; i < dat; i++)
    ret = spin_once(ret);
}

Эта программа потребовала бы миллиардов шагов для вычисления хэша для многих значений dat, но с более сложным кодом работа может быть выполнена в разумные сроки. Конечно, 32-битный хэш криптографически бесполезен, но этот подход можно легко расширить до любого размера.

Криптографические хэши дают очень хорошее приближение случайного числа для заданного ввода. Так сколько же случайных хэшей вам нужно в комнате, чтобы получить те же 160 бит? Примерно квадратный корень (отказ от ответственности: я не статистик). Поэтому следует ожидать столкновений примерно в 80 битах.

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

Согласно этой статье http://www.debian-administration.org/users/dkg/weblog/48 ,

Правительственные федеральные агентства США были направлен на прекращение всякой зависимости от SHA-1 к концу 2010 г.

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

Ваш идентификатор уникален и 128 бит.

Ваши комментарии объясняют, что вы не можете использовать идентификатор как есть.

Вам нужно, чтобы он был уникальным, а не просто вероятно уникальным. Поэтому вы не можете использовать хэш.

Вы не можете иметь оба мира - вы не можете иметь отображение 1:1, которое не является обратимым. Это невозможно.

Шифрование - биективная операция, поэтому не будет никаких коллизий - идентификаторы с секретным ключом сделают реверсирование идентификатора для определения его исходного значения очень сложным.

AES имеет хорошую длину блока 128 бит, который будет генерировать 128 бит вывода из ваших 128 бит входов, быстрее, чем старые алгоритмы (!) и широко доступен для большинства платформ и языков. Я предлагаю вам использовать AES для вашей цели.