# How to prove if a Hash Function is collision resistant

Say we have the following Hash Function, H(x) = 4x mod N where N is a number generated by multiplying two prime numbers and x={0,1,2,3,...,N-1}. So lets assume that N=15 where 15 is made from 3 and 5

How would we prove whether it is collision resistant or not? I tried manually doing it like below:

x=0; 4(0) mod 15 = 0
x=1; 4(1) mod 15 = 4
x=2; 4(2) mod 15 = 8
x=3; 4(3) mod 15 = 12
x=4; 4(4) mod 15 = 1
x=5; 4(5) mod 15 = 5
x=6; 4(6) mod 15 = 9
x=7; 4(7) mod 15 = 13
x=8; 4(8) mod 15 = 2
x=9; 4(9) mod 15 = 6
x=10; 4(10) mod 15 = 10
x=11; 4(11) mod 15 = 14
x=12; 4(12) mod 15 = 3
x=13; 4(13) mod 15 = 7
x=14; 4(14) mod 15 = 11


As you can see in the example, there are no collisions but how do you prove it Mathematically without providing numbers?

For the function $$F(x) = ax \bmod n$$, where the inputs are limited to the range $$[0, n)$$, this function will be a bijection (that is, no collisions) if and only if $$a$$ and $$n$$ are relatively prime.

Suppose there exists a collision, that is, we have a pair $$x, y$$ with $$0 \le x < y < n$$ where $$F(x) = F(y)$$. This implies that $$a(x-y) \equiv 0 \pmod n$$, that is, there exists an integer $$k$$ with $$a(x-y) = kn$$. $$x-y$$ is not a multiple of $$n$$ (it is not zero, as $$x < y$$, and we know that $$|x - y| < n$$, hence it is not a larger multiple of $$n$$), hence there exists a prime power $$p^k$$ where $$n$$ is a multiple of $$p^k$$, but $$x-y$$ is not.

We know that $$a(x-y)$$ must be a multiple of $$p^k$$, hence $$a$$ must be a multiple of $$p$$, and hence $$a$$ and $$n$$ are not relatively prime.

The other direction is easier; suppose $$a$$ and $$n$$ are not relatively prime, that is, there exists a prime $$p$$ for which both $$a$$ and $$n$$ are a multiple. Then, we have $$F(0) = F(n/p)$$, hence there exists a collision.

For this specific example, which doesn't make for a really useful hash function given that it isn't compressing, it's rather easy to prove the presence or absence of collisions.

So, assume $$H_{a,n}(x)=a\cdot x\bmod n$$ is the hash function we are looking it. Then if $$H_{a,n}(x)\cdot a^{-1}\bmod n$$ has a unique value, then there is exactly one input for each possible output value.

Luckily the ring of numbers $$\bmod n$$, also known as $$\mathbb Z_n$$ has been well-studied in mathematics, which allows us to know that the above value is unique if and only if $$\gcd(a,n)=1$$ holds.

As for the specific parameters in the question, we get $$a=4,n=15$$ and because $$\gcd(4,15)=1$$ no collisions occur if all inputs are in the range $$0\leq x<15$$.

• I don't suppose you could be kind enough to apply this to my context example please Sir/Madam. Also sorry but what is the a and n in this case? – Jasnnabaty Aug 24 '19 at 18:43
• @Jasnnabaty I have edited in the parameters from the question. – SEJPM Aug 24 '19 at 18:48
• thank you Sir/Madam I assume this could be used in any hash function predicament or scenario whereby one is asked whether the hash function is collision resistant or not? – Jasnnabaty Aug 24 '19 at 18:51
• @Jasnnabaty yes, this reasoning works whenever the hash function is of this specific form ($H(x)=a\cdot x \bmod n$) and the set of possible $x$ is restricted to be $0\leq x<n$. – SEJPM Aug 24 '19 at 18:53
• Just one thing Sir/Madam why do we do a^-1 mod n? – Jasnnabaty Aug 24 '19 at 18:54