3
$\begingroup$

My question is in $\mathbb{Z}_p^{*}$ context, where $p=q\cdot k+1$ for two primes $p,q$ and $k \in \mathbb{Z}$; $g$ is the generator of the subgroup $G_q$ of $\mathbb{Z}_p^{*}$, of order $q$.

Let's consider a small $H$ (e.g. $H=1024$) and a specific $h \in \mathbb{Z}_p$, with $0 < h < H$, and we randomly choose $g \in \mathbb{Z}_q$: is it true (I hope it is) that it is easy to find a $x$ such that $h \equiv (g^x \bmod p) \bmod H$?

My concern is: is it possible to create a mapping from a randomly chosen $g^x \bmod p$ that can be mapped to a target (desired) value $h$ in a small range, such that we can find it easily, e.g., in $\mathcal{O}(H)$?

$\endgroup$
2
$\begingroup$

Just sample a random $x$, and $[(g^x \bmod p) \bmod H]$ will equal your target value $h$ with probability $1/H$. After trying $O(H)$ candidates you will find a preimage.

Fine print: Technically speaking, the probability isn't exactly $1/H$. Each $h \in \mathbb{Z}_H$ has either $\lfloor \frac{p-1}{H} \rfloor$ or $\lceil \frac{p-1}{H} \rceil$ preimages under the mapping $a \in \mathbb{Z}^*_p \mapsto (a \bmod H)$. So the probability of hitting your target $h$, when you choose a random $a \in \mathbb{Z}_p^*$, is $\lfloor \frac{p-1}{H} \rfloor/(p-1)$ for some $h$'s and $\lceil \frac{p-1}{H} \rceil/(p-1)$ for others. But if $p$ is exponentially large (as I suspect it is here since you're talking about discrete logs), then this probability is negligibly close to $1/H$.

$\endgroup$
3
  • $\begingroup$ Mikero, I've just started learning crypto by myself. I have to say that I didn't ask it, but the "Fine print" part was my real doubt! Please, which of 'Number Theory' I have to read to really understand the ceiling and floor bounds? $\endgroup$ – Paollo May 20 '20 at 13:02
  • 1
    $\begingroup$ It is not really number theory, but simple counting. There are $p-1$ elements in $\mathbb{Z}^*_p$, and when you iterate over them in order, they map to $\mathbb{Z}_H$ in a regular repeating pattern. 1 out of every $H$ of them maps to your target $h$. But $(p-1)/H$ is probably not an integer, hence the ceiling/floor. $\endgroup$ – Mikero May 20 '20 at 18:38
  • 1
    $\begingroup$ Just visualize $p=31$, $H=7$. $\mathbb{Z}_{31}^* = \{1,2,\ldots,30\}$, and reducing them mod 7 gives $1, 2, \ldots, 6, 0, 1, 2, \ldots, 1,2$. So 1 & 2 have 5 preimages and the other numbers have 4 preimages. $\endgroup$ – Mikero May 20 '20 at 18:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.