Найти строку столкновения с заданной хеш-функции

У меня есть строка anna, где значения символов в строке являются a = 1, n = 14 (You can compute the value of other chars like (char - 96) и хэш-функция, которая выглядит как:Найти строку столкновения с заданной хеш-функции

int hashCode(string s) // s = "anna"; 
{ 
    k = 0; 
    for (int i = 0; i < s.length(); i++) 
     k = (7 * k + 3 * s[i]) % 61; 
    return k; 
}

Как найти строку длины 3 где происходит столкновение (что-то умное)? Единственный способ, который приходит мне на ум, - вычислить k из anna, который равен 29, а затем как-то подумайте о другой строке длины 3, которая дает 29.

источник

2016-11-30 kvway

вам придется это сделать, я боюсь, да. –

Я вижу, что _61_ является простым, и вы его модулируете. Добро пожаловать в мир [Задача дискретного логарифма] (https://en.wikipedia.org/wiki/Discrete_logarithm). – SpencerD

@ Jean-FrançoisFabre: Я бы не был так уверен, есть причина, чтобы написать хорошую одностороннюю криптографическую хэш-функцию. Тем не менее, я не специалист по криптографии или математике, поэтому я не могу сказать, как бы вы отменили это правильно, но когда вы говорите о трех строках строчных букв, вам не нужно быть умным; поисковое пространство - это только '26 ** 3 == 17,576' тотальные строки, поэтому исчерпывать их все тривиально. – ShadowRanger

Почему бы вам просто не сгенерировать все строки длины 3 и вычислить их хэши (на самом деле вы можете остановиться, когда все 61 возможные значения хэш-функций могут быть достигнуты)? Количество опций не слишком велико.

Одна возможная оптимизация: если вам нужно ответить на несколько запросов (например, с учетом строки, найдите строку длины 3 с тем же значением хэш-функции), вы можете сгенерировать все строки длины 3 и вычислить их хэши один раз построить карту hash -> a string of length 3 with this hash. Когда у вас есть эта карта, поиск строки длины 3 с тем же хешем, что и данный, - это всего лишь один поиск карты.

источник

2016-11-30 18:39:09 kraskevich

Возможно, вы хотите сохранить 'hash -> две строки длиной 3 с этим хешем'. Знаете, в случае, если первая сохраненная строка является той, на которую вы пытаетесь найти столкновение. :-) – ShadowRanger

@ShadowRanger Да, приятно поймать. – kraskevich

Найти строку столкновения с заданной хеш-функции

ответ

Смежные вопросы