# RSA: Is possible get p and q from this d and n?

I have this algorithm and Im searching p and q:

$n=p^2 * q$

$l=(p-1)*(q-1) / \gcd (p-1,q-1)$

$d\equiv l^{-1} \pmod n$

And the values are:

For $n$:

1043247381320041410146374847683905608886067988802815759655490071506964811427733496668055364700822779908166748193534341903285387332658081562041534228961538451830025041762537639985150344917584064827615356535763872539925989984117068207555498700585376330731428359489791600319636079777025344217248475485835298689437926003958578141784379857951264973109214803916445702964047899447002191548965239884095802091798787988745415178578597206815122915438351636672681355517982410123569961242563194480399347961753678159210217993526738306796503660563163029287419732210247579793266891085178817047536758465239950861266592524206390869822972469137566045176690277813352563392838847417674529251627419479815097868890993153215515488877097760272399483111013602618554846096893805108827211344467797072352072430591318485091677011261912992157762106672216780766138057271434398274272110062768324672899209610001835423246735718435995420720133657793744810610657


for $d$:

105717877672224295784291675385546750129601472163379527375367128238003471793097341763391999503913659542087520808364287167645349555897774428176288829031477703594776341268160433668976237198330124904372546897953955241778475322074160469767162566234358907740412805211247598698481640207956827199048419949848619731050860757808082106844953602176503247786535423423104239566910713528691298692332149783689032722772009974404716783312200885555343877611094998117307970399241640213553820043460140493803404190774171912962651075100983834071259021038322886114660028788229094872545516054757700068264628024524394995795135464746570071201


How can I get $p$ and $q$?

Thanks!

• Are you sure you have things listed correctly? I would initially expect $d$ to be approximately the same size as $n$, but the $d$ you have listed is significantly smaller. It's possible that whoever created this instance did that deliberately; however I don't see the reason... – poncho Apr 30 '18 at 2:38
• Note: this is not RSA as defined by PKCS#1, which requires that prime factors of $n$ are distincts. – fgrieu Apr 30 '18 at 8:11

I'll assume that $p$ and $q$ are prime.

Here's one approach to recover them

• Step 1: recover $l = d^{-1} \bmod n$

• Step 2: select a random $x$ and compute $y = x^l \bmod n$

Here's why such a $y$ is interesting.

We have $y \equiv 1 \pmod q$ (because $l$ is a multiple of $q-1$); similarly, we have $y \equiv 1 \pmod p$. However, if we consider $y \bmod p^2$, the group order of $\mathbb{Z}^*_{p^2}$ is $p(p-1)$; $l$ is unlikely to be a multiple of that (and will never be if $p$ and $q$ are the same size), and so we have (with great likelihood) $y \not\equiv 1 \pmod{p^2}$

• Step 3: compute $z = \gcd(y-1, n)$

$y-1$ is a multiple of $pq$, but not a multiple of $p^2q$, hence $z$ will be $pq$.

Then, it's trivial, $p = n/z$ and $q = z/p$

Now, the above might not work if the prime values $p$ and $q$ were deliberately selected to have $y \equiv 1 \pmod n$ consistently. However, we have another method:

• Step 2': set $l_0, k$ such that $l_0 = l / 2^k$ is odd

• Step 3': select a random $x$ and compute $y_0 = x^{l_0} \bmod n$

• Step 4': for $i := 0 .. k-1$

Check if $x_i = 1$; if so, fail (and go back to step 3' and select a different x)

Check if $\gcd(x_i - 1, n) \neq 1$; if so, that gives you a nontrivial factor of $n$ (and return success; completing the factorization should be straight-forward)

Otherwise, compute $x_{i+1} = x_i^2 \bmod n$

Here's how the above works; we know that we'll have $x_k = x^l \bmod n = 1$, and so $x_i \bmod p$ and $x_i \bmod q$ will both become 1 at some point in the computation; however it is likely that they'll become 1 at different points in the process; that is, one of them will become 1 first (and if so, the gcd will catch it)

• Dear @poncho, I implemented your answer. Unfortunately, $z$ was $1$ for more that $2000$ random $x$. Can you present a numeric example for your answer please? I think that something is wrong. – Meysam Ghahramani Apr 30 '18 at 6:53
• @poncho: my bets are on $n=p^2q$ with $d=n^{-1}\bmod l$ as suggested by Joana Vieira. That's because $d=l^{-1}\bmod n$ does not explain the relatively small $d$, as you observed; and does not seem to make sense as the decryption exponent of some natural $e$. – fgrieu Apr 30 '18 at 13:51
• @MeysamGhahramani: if fgreiu is correct, and $d = n^{-1} \bmod l$, then if you compute $l' = nd - 1$, and then use my second procedure, that should work ($l'$ is likely not $l$, but it is a multiple, and that's all you need for the second procedure) – poncho Apr 30 '18 at 14:05
• @poncho: experiment confirms your method $p=n/\gcd((2^{(n\cdot d-1)}\bmod n),n)$ and $q=n/{p^2}$ yields a full factorization of $n$ as $p^2\cdot q$, with $d=n^{-1}\bmod\operatorname{lcm}(p-1,q-1)$. – fgrieu Apr 30 '18 at 15:46
• @poncho, Yes. now, it's OK. – Meysam Ghahramani Apr 30 '18 at 17:27

I don't know the solution to this problem, but I think that where you have $d\equiv l^{-1} \pmod n$ should be $d\equiv n^{-1} \pmod l$. This is Takagi's RSA variant, or multi-power RSA, where $n=p^2q$ and the public exponent is $e=n$.