cryptography - Hash functions violating some pre image properties -

suppose h(xy) = h(x) * h(y) . preimage properties violated. how can find x, y such h(x) = h(y) mod (2^k)

2^k special modulus. can prove following strengthened version of euler's theorem:

suppose x postive integer. x^phi(2^k) (mod 2^k) equal either 0 or 1, 1 if , if x odd.

proof:

if x odd, gcd(x,2^k) = 1, hence x^phi(2^k) (mod 2^k) = 1 euler's theorem.

suppose x even. result trivially true if x = 0, suppose x > 0. write x = (2^s)*y y odd , s > 0. note

phi(2^k)` = 2^(k-1)

but then,

x^phi(2^k) = (2^s*y)^phi(2^k)            = (2^s)^phi(2^k) * y^phi(2^k)            = 2^(s*phi(2^k)) * y^phi(2^k)            = 2^(s*2^(k-1)) * y^phi(2^k)            = 0 * y^phi(2^k) = 0 (mod 2^k) 

the last line follows fact s*2^(k-1) >= k hence 2^(s*2^(k-1)) multiple of 2^k.

note if x have x^k = 0 (mod 2^k), raising x power phi(2^k) overkill smallest k.

given lemma, trivial see there exists distinct x,y either h(x) = h(y) = 0 or h(x) = h(y) = 1. since seems homework, i'll leave details you.