Я использую ELF Hash для написания специально измененной версии хеш-карты. Желание произвести столкновения

Может ли кто-нибудь привести пример двух строк, состоящих только из буквенных символов, которые будут давать одно и то же значение хеш-функции с помощью ELFHash?

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

Ниже приведен хэш ELF, если он вам понадобится.

unsigned int ELFHash(const std::string& str)
{
   unsigned int hash = 0;
   unsigned int x    = 0;

   for(std::size_t i = 0; i < str.length(); i++)
   {
      hash = (hash << 4) + str[i];
      if((x = hash & 0xF0000000L) != 0)
      {
         hash ^= (x >> 24);
         hash &= ~x;
      }
   }

   return (hash & 0x7FFFFFFF);
}

hash hash-collision
person Haozhun    schedule 07.05.2011    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

Некоторые примеры столкновений (которые я получил таким образом):

hash = 23114:
-------------
UMz
SpJ

hash = 4543841:
---------------
AAAAQ
AAABA

hash = 5301994:
---------------
KYQYZ
KYQZJ
KYRIZ
KYRJJ
KZAYZ
person digEmAll    schedule 07.05.2011
comment
Ой. Я никогда не верил, что это может произойти в строках длиной меньше пяти. Большое вам спасибо за вашу помощь! - person Haozhun; 07.05.2011
comment
@Gene: Это всего лишь пара коллизий, но я уверяю вас, что их действительно много в строках ‹ 5 (к сожалению, я сделал код для генерации коллизий на C #, иначе я бы опубликовал его ...) Это заставляет меня думать, что, возможно, этот гашиш не такой сильный... - person digEmAll; 08.05.2011