1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

Here is a proof in the direction you're asking about:

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jasnnabaty Aug 24 at 18:43
  • $\begingroup$ @Jasnnabaty I have edited in the parameters from the question. $\endgroup$ – SEJPM Aug 24 at 18:48
  • $\begingroup$ 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? $\endgroup$ – Jasnnabaty Aug 24 at 18:51
  • $\begingroup$ @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$. $\endgroup$ – SEJPM Aug 24 at 18:53
  • $\begingroup$ Just one thing Sir/Madam why do we do a^-1 mod n? $\endgroup$ – Jasnnabaty Aug 24 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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