# Build a hash function that returns a digest in $\mathbb{Z}_{N}^{\ast}$

I want to know if there is a way to build a Hash Function in a such way?

$\mathcal{H}:{\left\{ {0,1} \right\}^*} \to \mathbb{Z}_{N}^{\ast}$, $N=pq$ and where $p,q$ are primes.

• I'm pretty sure this is theoretically impossible without factoring $N$, because you need the factorization to find the multiplicative group. However if you don't mind that with a super-low chance the output will be not in the ring, then this is totally possible. – SEJPM Jun 26 '16 at 10:07
• @SEJPM: actually, if you use rejection sampling ("hash into a value between 0 and $N-1$, and if the result $r$ has a $\gcd(r, N) > 1$, rerun the hash function with a different input"), it most certainly can be done. – poncho Jun 26 '16 at 11:00
• @poncho, chances are, if you hit $\gcd(r,n)>1$ your cryptosystem is screwed anyways, if it relies on factoring being difficult and the chance of randomly hitting this is absolutely negligible in any practical implementation. – SEJPM Jun 26 '16 at 11:10
• does this question help you? – SEJPM Jun 26 '16 at 12:30
• @SEJPM: true, but it does show that it's not theoretically impossible to have such a hash function without factoring $N$ apriori... – poncho Jun 26 '16 at 16:57