How to implement a hash function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$? I would like to implement a hash function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$ such that $p$ is a prime number and $\log_2(p) &gt; 256$. I am wondering if it is a good idea to use the hash function SHA-256.

Since $\log_2(p) &gt; 256$, can I just use the output of SHA-256 and apply the modulo $p$ on it?

I would also like to prevent the all-zero (0000…0000) output from SHA-256, is it correct for example to add the value $1$ to the output of SHA-256? Is there a better way?
A possible method is to build $k=1+\lceil\log_2(p)/256\rceil$ 256-bit hash functions $H_i(x)$ per the HMAC construction, by choosing $k$ arbitrary distinct 512-bit constants $c_i$, by defining
$$H_i(x)=\operatorname{SHA-256}\Bigl((c_i\oplus\mathsf{opad})\|\operatorname{SHA-256}\bigl((c_i\oplus\mathsf{ipad})\|x\bigr)\Bigr)$$
then build
$$H(x)=\Bigl(\bigl(H_0(x)\|H_1(x)\|\dots\|H_{k-1}(x)\bigr)\bmod(p-1)\Bigr)+1$$
where for computation of $\bmod$ the $256k$-bit bitstring $H_0(x)\|H_1(x)\|\dots\|H_{k-1}(x)$ is converted to integer per (say) big-endian convention.

$H(x)$ is slightly biased towards zero, but the advantage an adversary can get from that is negligible.



There would be two issues when directly using $H(x)=\operatorname{SHA-256}(x)$ as considered in the question (or $H(x)=\operatorname{SHA-256}(x)\bmod p$ which is equivalent if $\log_2(p)&gt;256$ ):


Except for $p$ just above $2^{256}$, it is easy to recognize such $H$ from a random function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$, because $H(x)&lt;2^{256}$.
It is quite possible that there exist $x$ with $\operatorname{SHA-256}(x)$ the all-zero 256-bit bitstring, so that $H(x)$ is not in $\mathbb Z_p^*$; however we know no computationally feasible way to exhibit such $x$, thus this might not be a practical issue.