1

I need to calculate the $d$ private key in RSA.

The data I know is $n$, $e$ and part of $q$. For calculating that d, I need to calculate $\phi = (p-1)(q-1)$, but, before I can calculate $\phi$ I need to know $q$ and $p$.

Knowing that $n = p\ \cdot q$ it should be easy to get $p$, but the problem is that $q$ isn't complete.

The solution I was thinking was to calculate the next prime number greater than $q$, then $p = \frac{n}{q}$.

The problem with that solution is that $n$ and $q$ are very large numbers and calculating the next prime number may take so long.

The values I have are:

$$q = 28715579796305758474667846518766873255492272737905466351525171318348391723088262 \\ 58249653585601622660761481080342866203785689093327148932226949505505837$$

$$n = 14634343605751036979940788054761314555865888648259143600014237897373212259787937\\988432044946495940379719810430822794442825272333645896273848057928426810706372\\6288619593719244281352195659364220185216358546968554006023167367419980981469627098 \\371458194077000595132435883250233193631515839672002808488444790391157 $$

$$e = 65537$$

My question is: How can I calculate $p$ with such a large numbers?

EDIT:

I solved my problem, maybe it's not the best solution, but it worked.

What I did was assume that the bytes from $q$ I already know must not change, so I added one new byte at the end and tried to divide $n$ by the new $q$, adding 1 to that new value if it could not divide. As the 16 possible options couldn't divide, I added one new byte and tried again.

Finally, with 4 bytes added at the end of my known $q$, I found a new one that divided $n$. After that, calculating $\phi$ was trivial.

Thanks to everyone who tried to help me.

DrChacal
  • 11
  • 1
    What do you mean with "q is not complete"? Is the part of $q$ that you present a part of the number (in base 10), or should some small number be added to that? Or is there a factor it should be multiplied with? – Jasper May 21 '16 at 15:19
  • I checked the 10 next biggest primes (this is easy using Wolfram Alpha or Mathematica) but none of them divide your given $n$. – Stefan Hante May 21 '16 at 15:25
  • @Jasper Hi, n and q are shown on a video, written on a paper in hex format, but the last bytes of q are covered by a paper, that's why I say it is not complete. – DrChacal May 21 '16 at 15:43
  • I checked the next 100 primes. None of them divide $n$. Are you sure you did not make any mistakes writing the hex numbers down and converting them? How many bytes were missing? – Stefan Hante May 21 '16 at 15:48
  • @Wauzl Part of the problem is that, I really don't know how many bytes are missing. Do you think that Wolfram can factorize n? This way I probably get both p and q, don't you think? – DrChacal May 21 '16 at 15:53
  • You have to use LLL, look up Coppersmith. – Henno Brandsma May 21 '16 at 16:39
  • E.g. see https://github.com/niklasb/BKP2015-Bowdoin as a puzzle where this was the exercise. – Henno Brandsma May 21 '16 at 16:55

1 Answers1

1

This can be done using Coppersmith's theorem and LLL reduction (see this paper and this follow-up paper). This assumes you have about half of the bits of one of the primes.

Implementable with LLL, via Sage, e.g, like in this blog post.

Henno Brandsma
  • 242,131