Lets say hypothetically all one knew was a value of $e$ and a value of $p$.

As an example, lets assume that $e = 13$ and $p = 67$.

Would it be possible to find the value of $q$ from this equation?

$\gcd(13, (66)(q-1)) = 1$

If so, how would I begin solving this?

  • 1
    $\begingroup$ Note that this is equivalent to $\gcd(13,q-1)=1$ in terms of constraints (not in value!) $\endgroup$ – SEJPM Dec 4 '18 at 20:36
  • $\begingroup$ is this a homework or CTF? $\endgroup$ – kelalaka Dec 4 '18 at 20:43
  • $\begingroup$ Might you actually intend to ask "how do I find $d$ such that $e \cdot d = 1 \pmod p$"? $\endgroup$ – poncho Dec 4 '18 at 21:06
  • 1
    $\begingroup$ Well obviously you need $n$. $\endgroup$ – forest Dec 5 '18 at 2:27
  • 1
    $\begingroup$ Possible duplicate of RSA limiting down the possible values for $n,q$, and $d$? given only $e$ and $p$ $\endgroup$ – forest Dec 5 '18 at 9:08

The question is a bit strange.

Do you mean $n$ is unknown? Then there are infinitely many $q$ which will work. Since 13 and 66 are relatively prime, by @SEJPM's comment, all $q$ which are of the form $$ q_k \neq 13k+1, $$ are possible solutions. Depending on what $n$ you want you can take $k$ large enough. But in the RSA context $n$ must be public.


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.