Given haphazard large integers $a$ and $b$ (like few thousand bits), can we efficiently find (and how) some integer triplet $(p,x,k)$ with

  • $p$ a large prime (like a thousand bits)
  • $a^x\equiv b\pmod p$
  • $k$ sizable (say of 10 bits or more if possible) and dividing $p-1$
  • $a^{(p-1)/k}\equiv 1\pmod p$

These conditions match the title, since $x_j\gets j\,(p-1)/k+(x\bmod((p-1)/k))$ gives $k$ distinct $x_j\in[1,p)$ with $a^{x_j}\equiv b\pmod p$.

Late addition: in a variant with reduced applicability, one of $a$ or $b$ would be an output instead of a given, with the constraint that it should be unremarkable modulo $p$ (at least not among $0$, $1$, $p-1$) when the other is haphazard.

  • $\begingroup$ Are there restrictions on how large $x$ has to be? I would at least say that $x>0$, correct? $\endgroup$ – AleksanderRas May 6 at 11:35
  • 1
    $\begingroup$ @AleksanderRas: I clarified how we count $x$ in the title. While $x$ remains unrestricted in the body of the question, what really matters is $x\bmod((p-1)/k)$ which is the smallest positive solution, and determines the $k-1$ others. $\endgroup$ – fgrieu May 6 at 11:55
  • 2
    $\begingroup$ I have a method that works for circa one in a million $(a, b)$ pairs. While this is obviously not a practical solution for this problem, it is enough to show that the problem can't be used as the 'hard problem' for a cryptographical system... $\endgroup$ – poncho May 6 at 13:23
  • $\begingroup$ @poncho: I'm thinking about an attack on an out-of-my-head security property of signatures, that usual RSA signatures do not pretend to have, but EdDSA has: I call it misappropriation resistance, and tried to discuss it there. Applied to OpenPGP signatures, what I ask in the present question would markedly reduce the complexity of most of $2^{64}$ steps required for the attack, or $2^{33}$ steps required for a passable mockup of an attack. $\endgroup$ – fgrieu May 6 at 13:53

You asked for my one-in-a-million attack; here is what it looks like:

  • Step 1: find a large prime factor of $b^i - 1$, for some small $i$. This can be done by iterating through the various small values of $i$ (starting with $i=1$ naturally), use the known factorizations (e.g. $b^2 - 1 = (b+1)(b-1)$), and then for the various subfactors, scrap off the easy small factors and hope what's remaining is a prime (e.g. $b+1 = hp$, for some small $h$ and prime $p$.

If this step succeeds, then we have $a^{0} \equiv b^i \pmod p$; check to see if this yields an $x$ (i.e.. if $a^{n(p-1)/i} \equiv b \pmod p$ for some $n \in \{0, …, i-1\}$).

An initial estimate is that we will manage for find just an appropriate $p$ (and $x$) about 1 in 1000 arbitrary $b$ values in the "thousand bit" range.

  • Step 2: find $k$. To do this, find the small factors of $p-1$, and for various small (not necessarily prime) factors $k$ in the appropriate range, check if $a^{(p-1)/k} \equiv 1 \pmod p$. If $a$ is random, this happens for a particular $k$ with probability $1/k$ (actually, perhaps a bit less if $i > 1$ in the previous step...)

Again, a very rough guess would be that this may succeed about 1 every 1000 times (that we have a factor $k$ of the appropriate magnitude, and that $a$ happens to be in that subgroup).

If both steps succeed, you have $p, x, k$ as requested (although, looking back at it, perhaps a probability of "one in a million" is a tad optimistic; "one in ten million" might be closer...

| improve this answer | |
  • 1
    $\begingroup$ Thanks! I'd have one of $a$ or $b$ (my choice) constrained to be nearly twice the width of $p$ and randomized by a hash, and the other 1) in a "real" attack, a random given nearly twice the width of $p$; 2) in a "mockup" attack, almost unconstrained. It seems that your idea would help with the mockup. $\endgroup$ – fgrieu May 6 at 15:13

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.