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

Question

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.

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