2
$\begingroup$

The hash value of a string $s$ is given by

$$ h(s) = \sum^{|s|}_{i = 1} s_i \cdot p^{|s| - i} \mod m; \text{ $m$ is prime, $m < 10^{12}$}. $$

The string $s$, $p$, $m$ is given, $|s| \le 14$, alphabet size $= 62$ (letters and digits).

I need to find a string $s^{\prime}$:

$s^{\prime} \neq s$, but $h(s^{\prime}) = h(s)$

$s^{\prime}$ must meet the same requirements as $s$. The answer is always exist.

I know about Birthday-attack, but $m$ is too large and if I generate random strings, probability of collision is too small. Simple brute-force is also not suitable, because the string may be too long (14 characters).

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Running birthday attack should be faster than writing the question: sqrt(1e12) = 1e6

Also note that your question have nothing with rolling hashes, moreover, with rolling hash len(s) is fixed. So it may be that you missed some condtitions from the original question.

Improve this answer
$\endgroup$
0
$\begingroup$

Hint: Write out the condition for $h(s)=h(s')$, expressed in terms of the variables $s_1,\dots,s_{14},s'_1,\dots,s'_{14}$. Use linear algebra.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.