5
$\begingroup$

Having known the values for $N$ a large number, $e = 65537$ and another large number $g = d \cdot (p-17)$, how can I use that info to find out $p$ and $q$?

I guess that have something to do with Fermat's little theorem and I noticed that $e$ is the largest prime number of the form $2^k+1$. Can you give me some hint? I am not very familiar with some other theorems that may help.

$\endgroup$
2
  • $\begingroup$ Actually the choice of e is very much standard and not unusual. $\endgroup$ – SEJPM Apr 28 '18 at 16:33
  • $\begingroup$ And the correct answer doesn't depend on the value of $e$; it does assume you know it $\endgroup$ – poncho Apr 28 '18 at 16:34
5
$\begingroup$

Fermat's little theorem is useful indeed.

For instance, for almost any integer $m$, you have that $m^{P-1}=1 \mod{P}$. Since then, you know that $A=m^{P-1}-1$ is a multiple of $P$. With that value, you can therefore compute $gcd(A,N)$ which should provide $P$ (knowing that $N=P \times Q$).

With the provided values, you may be able to build that special $A$. For instance, $(m^e)^g \mod{N}=m^{e \times g} \mod{N} = m^{P-17} \mod{N}$.

So $(m^e)^g \times m^{16} = m^{P-1} \mod{N}$ ! To conclude, you can finally compute the gcd between $N$ and $(m^e)^g \times m^{16}-1$.

As an example with small integers, let us define $P=11$, $Q=17$, $N=P \times Q = 187$, $\Phi(N)=(P-1) \times (Q-1) = 10 \times 16 = 160$, $e=3$, $d=107$, $g=d \times (P-17) = 158$ and $m=2$.

One gets $(m^e)^g \mod{N} = 38$ and thus $(m^e)^g \times m^{16} = 89$. One finds $P$ by computing $gcd(89-1,187)=11=P$ ;-)

$\endgroup$

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.