8
$\begingroup$

In RSA and other crypto based on prime factors. If I would know the sum of $p+q$, would it reveal any more information than just knowing $p\cdot q$?

Edit: I do not know either $p$ or $q$. The question relates to the fact that if I know the sum and the multiplication, can I find the factors $p$ and $q$ faster compared to when I don't know the sum?

$\endgroup$
6
  • 2
    $\begingroup$ I'm not entirely sure, are you asking about the case where you just know $p+q$ (but not $p\cdot q$) or where you know $p+q$ and $p\cdot q$? $\endgroup$
    – SEJPM
    Jan 3, 2021 at 12:41
  • 3
    $\begingroup$ I guess you are asking the case where you knoe both $m=pq$ and $a=p+q$. In this case, you can find $p$ and $q$ by solving the quadratic equation $x^2-ax+m=0$. $\endgroup$
    – Hhan
    Jan 3, 2021 at 12:48
  • 2
    $\begingroup$ You can also directly compute $d = e^{-1} \pmod{n-(p+q)+1)}$. $\endgroup$
    – Fractalice
    Jan 3, 2021 at 12:53
  • $\begingroup$ yes I know p+q and p*q (but I don't know P or Q. Given that they are big int (>1024 bit) does knowing the sum make it easier to find P&Q? $\endgroup$
    – ovanwijk
    Jan 3, 2021 at 13:14
  • $\begingroup$ What is capital $P$ and $Q$? $\endgroup$
    – kelalaka
    Jan 3, 2021 at 13:14

1 Answer 1

10
$\begingroup$

Let $n = p \cdot q $ be product of distinct primes $p$ and $q$, of arbitrary size as in the RSA setup.

The RSA public key $(n,e)$ contains both the modulus and the public exponent, so we assume both are known.

Let $b = p +q$. If $b$ is also known, then we can form a quadratic equation as

$$ f(x) = x^2 - b x + n \label{1}\tag{1}$$ by using the following identity:

$$(x-p)(x-q) = x^2 - (p+q) x + (p\cdot q).$$

The solution of the quadratic equation (\ref{1}) is that $p$ and $q$ and can be found by the second-degree formulas using this equation:

$$p,q = \frac{ b \pm \Delta}{2}$$ where the discriminant $\Delta = \sqrt{b^2 - 4n}.$

It is also possible to directly find the private exponent too! Observe that:

$$\varphi(n) = (p-1)(q-1) = pq - p -q +1 = pq - (p +q) +1 = n - b + 1.$$

Since $e \cdot d \equiv 1 \bmod \varphi(n)$, you can solve for $d$ without computing $p$ and $q$, though those are also cheap to compute if you would still like to use them.


Example:

Let $m = 35$ and $b = 12$. We thus need to solve $x^2 - 12x + 35$, which gives us:

$$\Delta = \sqrt{12^2 - 4 \cdot 35} = \sqrt{144 - 140} = \sqrt{4} =2. $$

As a result:

$$p = \frac{12 + 2}{2} = 7 \text { and } q = \frac{12 - 2}{2} = 5.$$

$\endgroup$
5
  • $\begingroup$ Please see my edit but: does this mean, that revealing the sum will expose $p$ and $q$? $\endgroup$
    – ovanwijk
    Jan 3, 2021 at 13:51
  • $\begingroup$ That is exactly what you need, call their sum $b$ and multiple as $n$ the modulus then it works, $\endgroup$
    – kelalaka
    Jan 3, 2021 at 13:56
  • $\begingroup$ Sorry I might not understand how exactly. Given p=5 and q=7, m=35 and s=12. How do I find 5 & 7 from f(35, 12) (other than brute force)? $\endgroup$
    – ovanwijk
    Jan 3, 2021 at 14:06
  • $\begingroup$ Ok I got it! Thnx! $\endgroup$
    – ovanwijk
    Jan 3, 2021 at 14:11
  • $\begingroup$ @ovanwijk added the example. $\endgroup$
    – kelalaka
    Jan 3, 2021 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.