Say I have a simple hash function where $x$ is a sequence of integers:

$$h(x)=(a_1\cdot x_1+...+ a_n\cdot x_n) \bmod N=\sum_i a_i\cdot x_i \bmod N$$

where $a_1,a_2,a_3,...,a_n$ is the coefficient known to the attacker, size of $x$ can be anything smaller than $N$.

How to find 2 different inputs that hashes to the same value, i.e $0$?

I feel like this has something to do with linear combination / euclid algorithm but I'm not sure how to proceed.


1 Answer 1


We can easily find collisions for this system.

Let $x=(x_1,...,x_n) $ be a sequence such that $h(x)=k$. For finding collision we can do this:

Select $x'=(x_1',...,x_{n-1}')$ and then compute:

$$x_n'=({a_n}^{-1}\cdot(k-\sum_{i=1}^{n-1}a_ix_i')) \bmod N$$

Now we have $h(x)=h(x')=k$.

  • $\begingroup$ Just curious, is there any way to make the last bit xn' to be within an arbitrary range? say between 0-100. $\endgroup$ Commented May 8, 2016 at 22:33
  • 2
    $\begingroup$ @LoveProgramming, Yes, first choose $x_n$ in your range, and then compute $x_{n-1}$ using my method. $\endgroup$ Commented May 9, 2016 at 9:36
  • $\begingroup$ Can I make every Xi to be within arbitrary range? $\endgroup$ Commented May 9, 2016 at 22:47
  • $\begingroup$ @LoveProgramming, This is evident that at most one $x_i$ can not be within arbitrary range. $\endgroup$ Commented May 10, 2016 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.