Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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$ ;-)
