Editorial for COCI '13 Contest 6 #5 Hash

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

This requires a "meet-in-the-middle" attack: it's a common idea in crypto, but is also useful in a number of exponential-time competition problems. For $N = 10$ ~N = 10~, we can't consider all $26^{10}$ ~26^{10}~ words separately. However, we can consider $26^5$ ~26^5~ five-letter prefixes and $26^5$ ~26^5~ five-letter suffixes, and then figure out how to match them up. For each prefix, we can compute its hash, and store a table for how frequently each such hash occurs. For each suffix, we can compute what the hash of the prefix would need to be for the final hash to be $K$ ~K~, and then use the table to find the number of prefixes that match this suffix. To compute what the hash would need to be, we work backwards: assume the final hash is $K$ ~K~, and then remove one letter at a time from the end.

Let us observe an iteration of the stated hash function with the assumption that the current value of the hash is $S$ ~S~ and the ordinal number of the next letter is $x$ ~x~.

$\displaystyle S' = ((S \times 33) \mathbin{xor} x) \mathbin\% MOD$

We will try to get the value of the previous state $S$ ~S~ when we know the current state $S'$ ~S'~ and the ordinal number of the letter which got us to the state $x$ ~x~.

Given the fact that we can look at the operation remainder when dividing with a power of two ( $2^M$ ~2^M~) as discarding any bits after the $M^\text{th}$ ~M^\text{th}~, it is easily noticed that the following holds:

$\displaystyle (A \mathbin{xor} B) \mathbin\% MOD = (A \mathbin\% MOD) \mathbin{xor} (B \mathbin\% MOD)$

Therefore,

$\displaystyle S' = ((S \times 33) \mathbin\% MOD) \mathbin{xor} (x \mathbin\% MOD)$

because the bitwise XOR is inverse to itself and $x$ ~x~ will always be smaller than $MOD$ ~MOD~, this is also true:

$\displaystyle S' \mathbin{xor} x = (S \times 33) \mathbin\% MOD$

The modular multiplicative inverse of $33$ ~33~ in the field of size $MOD$ ~MOD~ will exist if $33$ ~33~ and $MOD$ ~MOD~ are relatively prime. Since $MOD$ ~MOD~ is a power of two, this condition is true. The modular inverse can be obtained using extended Euclid's algorithm, fast exponentiation or with brute force because $M$ ~M~ is small enough.

Let us display the complete inverse relation of the hash function:

$\displaystyle (S' \mathbin{xor} x) \times inv(33, MOD) = S$

Having inverse relation in place, meet in the middle attack is done which gives us a time complexity of $\mathcal O(26^{N/2})$ ~\mathcal O(26^{N/2})~.

Comments

There are no comments at the moment.