- $$h(m) = g^m(\bmod p)$$ where $p$ is a prime number, how can I prove that this is a one way function and collision free?
- $$h(m) = g^m(\bmod n) $$ where $n=pq$ for two distinct primes $p,q$, how can I prove that it is a one way function and collision free?
- Neither function is is collision resistant, as $h(m+p-1)=h(m)$ if you don't restrict the input space for the first one, as we don't actually know $\varphi(n)$ as pointed out by poncho in his answer.
- I suppose one-way-ness depends on the techniques you have learned and will most likely make use of the precise formulation of the discrete logarithm problem (you know, that one that uses random sampling for $m$).
Actually, if all the following is true:
The factorization of $n$ is secret (as so SEJPM's counterexample doesn't apply, as you don't know the value $\varphi(n)$)
$p$ and $q$ are sufficiently large that the factorization problem is infeasible.
If the order of $g$, with respect to both $p$ and $q$, is large
Then, yes, the second instance is collision resistant. That is, if you do find a collision, that is, two distinct values $x, y$ such that $g^x \bmod n = g^y \bmod n$, then knowing the difference $x-y$ gives you enough information to efficiently factor $n$, which we assume is hard.