3
$\begingroup$

I know that an equation $$a^x \equiv b \pmod{p}$$ can be solved for $x$ in $O(\sqrt{p} \ log(p) )$ time using meet-in-the-middle technique, which relies on fact that we can rewrite the equation as follows: $$a^{nk} \equiv ba^{h} \pmod{p},$$ where $nk - h = x$.

I want to know whether one can solve the following equation (relatively) effectively: $$(a^x \bmod p) \equiv b \pmod{q} $$ where $p, q$ are primes and $p > q$. I don't see how one can rewrite this one to apply meet-in-the-middle.

Problem source: I've been reading about Digital Signature Algorithm and I want to write a program that finds signature $(r, s)$ using public key only (for toy numbers), which can be done by solving for $r, s$ the following equation $$(r^s \bmod p) \bmod q = (g^{H(m)}y^{r} \bmod p) \bmod q$$

$\endgroup$
6
$\begingroup$

As far as we know there is no efficient way to do that. Such a way would constitute a break of the DSA scheme, and no break of the DSA is known. In particular, DSA is believed to be secure, so it is believed that no efficient algorithm for this exists.

If you only want to do it for small numbers, you can just use brute force and try all possible values of $x$. Or, you can solve

$$a^x \equiv b \pmod p.$$

Then any solution to that equation will be a solution to your equation as well. More generally, you can pick any constant $c$ of your choice such that $0 \le c < (p-b)/q$ and solve

$$a^x \equiv b + cq \pmod p;$$

if you can't find a solution for a particular value of $c$, try another one until you can. This won't be efficient once $p,q$ get large.

$\endgroup$
  • $\begingroup$ Is there any mathematical evidence to suggest this problem is "harder" than others, or do we just base our confidence in its difficulty on our past history of inability to solve it? $\endgroup$ – Alexander Feb 12 '18 at 20:28
  • 2
    $\begingroup$ @Alexander, that's probably better asked as a separate question (and probably on Crypto.SE, frankly), but the short answer is: I'm not aware of any strong evidence of that form for the security of DSA. If you believe that the discrete log problem is hard, then there is some weak evidence: Pointcheval & Vaudenay ("On Provable Security for Digital Signature Algorithms"), Brickell & Pointcheval & Vaudenay & Yung ("Design Validations for Discrete Logarithm Based Signature Schemes"). However those results make heuristic assumptions that aren't very reasonable/realistic. $\endgroup$ – D.W. Feb 12 '18 at 20:34
  • $\begingroup$ On the other hand, there is arguably somewhat better evidence for the hardness of the ordinary discrete log problem -- but still no proof (and any proof would immediately imply P != NP, so we don't expect an unconditional proof any time soon). $\endgroup$ – D.W. Feb 12 '18 at 20:35

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.