Sugar_fan's blog

By Sugar_fan, 7 months ago, In English

Hello, Codeforces!

For the convenience of hacking codes that incorrectly use rolling hashes (i.e., using fixed modulos and bases), I wrote a tool in Rust, which runs entirely on the frontend and requires WebAssembly support.

Try it here and feel free to create issues.

Explanation of parameters:

  • length: the length of generated strings;
  • $$$\lambda$$$ (lambda):detail follows;
  • $$$\delta$$$ (delta) and $$$\eta$$$ (eta) : parameters of $$$L^2$$$ algorithm;
  • precision: floating-point precision in decimal.

Given the modulos $$$\lbrace p_i\rbrace_{i=0}^{n-1}$$$ and the bases $$$\lbrace q_i\rbrace_{i=0}^{n-1}$$$, define $$$h_i(a)=\Big(\sum\limits_{j=0}^{\text{length}-1} q_i^js_j\Big)\bmod p_i$$$, where $$$a$$$ is a string of $$$\text{length}$$$. We want to find two strings $$$a$$$ and $$$b$$$ of $$$\text{length}$$$ such that $$$h_i(a)=h_i(b)$$$ for every $$$i$$$.

If we find a integer array $$$d$$$ of $$$\text{length}$$$ satisfying that $$$h_i(d)=0$$$ for every $$$i$$$, $$$|d_j|<26$$$ for every $$$j$$$, and $$$d_j\ne 0$$$ for some $$$j$$$, we can easily construct $$$a$$$ and $$$b$$$ from $$$d$$$.

Construct a matrix $$$M$$$ of size $$$(n+\text{length})\times(n+\text{length})$$$:

$$$M=\begin{bmatrix} Q & I\\ P & 0 \end{bmatrix}.$$$

where

  • $$$Q$$$ is a matrix of size $$$\text{length} \times n $$$, where $$$Q_{ji}=q_i^j\bmod p_i$$$;
  • $$$I$$$ is an identity matrix of size $$$(\text{length} \times \text{length})$$$;
  • $$$P$$$ is a diagonal matrix of size $$$n\times n$$$, where $$$P_{ii}=p_i$$$,
  • $$$0$$$ is a zero matrix of size $$$n\times \text{length}$$$.

We can find that the matrix $$$M$$$ has the following properties:

  • For every row $$$R$$$ of $$$M$$$, that $$$h_i(R[n\cdots n+\text{length}])\equiv R[i] \pmod{p_i}$$$ holds for every $$$i$$$,
  • $$$M$$$ is full rank.

Define the following operation:

  • $$$R_i\leftarrow R_i-R_j\times k$$$, where $$$k\in \mathbb Z$$$.

We can find that this operation does not affect the properties of the matrix.

If after operations, there exists a row $$$R$$$ satisfying that $$$R[i]=0$$$ for every $$$i<n$$$ and $$$|R[i]|<26$$$ for every $$$i\ge n$$$, we can find a solution $$$d=R[n\cdots n+\text{length}]$$$.

Intuitively, we should find the "shortest" row $$$R^*$$$. To make it more likey that $$$R^*[i]=0$$$ for every $$$i<n$$$, multiply the first $$$n$$$ columns by a big integer $$$\lambda$$$, i.e.,

$$$M=\begin{bmatrix} \lambda Q & I\\ \lambda P & 0 \end{bmatrix}.$$$

This is well known as Shortest Vector Problem (SVP). Here, we use the $$$L^2$$$ algorithm to reduce $$$M$$$. More details about $$$L^2$$$ algorithm can be found in the paper mentioned below.

References:

  • Vote: I like it
  • +328
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Please delete this and never hack any hash solution again

»
7 months ago, # |
  Vote: I like it +180 Vote: I do not like it

New fear unlocked

»
7 months ago, # |
Rev. 2   Vote: I like it +43 Vote: I do not like it

Orz!

It seems that people use the rolling hash formula $$$\sum_{j = 0}^{n - 1} q^{n - 1 - j} s_j$$$ more frequently than $$$\sum_{j = 0}^{n - 1} q^{j} s_j$$$. Probably it would be better to have an "reverse the result" option.

»
7 months ago, # |
  Vote: I like it +79 Vote: I do not like it

Please no GOD no please. I won't play Genshin any more. Please don't hack my Hash.

»
7 months ago, # |
  Vote: I like it +38 Vote: I do not like it

the hero we do not deserve

»
7 months ago, # |
  Vote: I like it +46 Vote: I do not like it