6
$\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 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 at 12:48
  • 2
    $\begingroup$ You can also directly compute $d = e^{-1} \pmod{n-(p+q)+1)}$. $\endgroup$ – Fractalice Jan 3 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 at 13:14
  • $\begingroup$ What is capital $P$ and $Q$? $\endgroup$ – kelalaka Jan 3 at 13:14
8
$\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 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 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 at 14:06
  • $\begingroup$ Ok I got it! Thnx! $\endgroup$ – ovanwijk Jan 3 at 14:11
  • $\begingroup$ @ovanwijk added the example. $\endgroup$ – kelalaka Jan 3 at 14:21

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.