1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SEJPM Jun 26 '16 at 10:07
  • $\begingroup$ @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. $\endgroup$ – poncho Jun 26 '16 at 11:00
  • $\begingroup$ @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. $\endgroup$ – SEJPM Jun 26 '16 at 11:10
  • $\begingroup$ does this question help you? $\endgroup$ – SEJPM Jun 26 '16 at 12:30
  • 1
    $\begingroup$ @SEJPM: true, but it does show that it's not theoretically impossible to have such a hash function without factoring $N$ apriori... $\endgroup$ – poncho Jun 26 '16 at 16:57

Your Answer

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

Browse other questions tagged or ask your own question.