2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – poncho Apr 30 '18 at 2:38
  • $\begingroup$ Note: this is not RSA as defined by PKCS#1, which requires that prime factors of $n$ are distincts. $\endgroup$ – fgrieu Apr 30 '18 at 8:11
3
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Meysam Ghahramani Apr 30 '18 at 6:53
  • $\begingroup$ @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$. $\endgroup$ – fgrieu Apr 30 '18 at 13:51
  • 2
    $\begingroup$ @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) $\endgroup$ – poncho Apr 30 '18 at 14:05
  • 1
    $\begingroup$ @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)$. $\endgroup$ – fgrieu Apr 30 '18 at 15:46
  • $\begingroup$ @poncho, Yes. now, it's OK. $\endgroup$ – Meysam Ghahramani Apr 30 '18 at 17:27
3
$\begingroup$

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$.

$\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.