Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.$$
