Реверс хэш-функции

Question

Есть функция хэшировния строки c символами A-Za-z0-9_. Как её обратить, чтобы можно было перебирать строки с одинаковым хэшем? Иными словами, нужно написать что-то наподобие генератора строк (до 15000) с одинаковым хэшем.

const int p = 31;
size_t operator()(const string& s) const {
    size_t hash = 0, p_pow = 1;
    for (size_t i = 0; i < s.size(); ++i) {
        hash += (s[i] - 'a' + 1) * p_pow;
        p_pow *= p;
    }
    return hash;
}

Answer 1

Ваш «хэш» это просто полином вида S = a_n×31ⁿ + … + a₁×31 + a₀.

Где все a_k имеют значения из списка -48…-39 (0-9), -31…-6 (A-Z), -1 (_) и 1…26 (a-z).

Для примера возьмём S = 20. Посчитаем остаток от деления на 31. S % 31 = 20. (Ну да, немножко тривиально). Очевидно что a_k при k >= 1 никак не влияют на этот остаток. Смотрим какие значения a₀ могут дать такой остаток. Это значения 20, -11 и -42. Т.е. первый символ нашей строки это t, U или 6.

не дописал…

Answer 2

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

void recursiveSearch( size_t hash, std::string s ){
    if( hash == 0 ){
        // Строка найдена
        // ...
        return;
    }
    if( s.size() < 12 ) // Ограничить размер строки, иначе некая бесконечная строка может иметь ненулевой хэш
        for( auto q : ab ) // Для каждого символа алфавита
        {
            if( ( hash - q ) % 31 == 0 ) // Если символ подходящий
                // Искать подпоследовательность(-и)
                recursiveSearch( ( hash - q ) / 31, s + std::string( 1, static_cast<char>( q + 'a' - 1 ) ) );
        }
}

Группа вывода:

OPHRBCBBBBBBBBa OPHRBCBBBBBBBa OPHRBCBBBBBBa OPHRBCBBBBBa OPHRBCBBBBa OPHRBCBBBa OPHRBCBBa OPHRBCBa OPHRBCa OPHRBb

БЛОГ НА HUSL

Реверс хэш-функции

Ответы (2 шт):