# How to find collisions in a hash function knowing its coefficent?

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.

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$.

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