# Sum of primes

## Introduction

We have :

• n : modulus
• e : public exponent
• c : ciphertext

Additionally, we have a special variable :

• x : sum of p and q

The goal is to find the cleartext.

## Maths

We know that :

$$n = p * q$$ $$x = p + q$$

Let's try to do something with it :

$$p = x - q$$

$$n = (x - q) * q$$

$$n = -q^2 + x \times q$$

$$-q^2 + x \times q - n = 0$$

We have a second degree equation, let's solve it :

$$delta = x^2 - 4 \times (-1) \times (-n)$$

$$p = \frac{- x + \sqrt{delta}}{2 * -1}$$ $$q = \frac{- x - \sqrt{delta}}{2 * -1}$$

## Example

Write-up for the challenge Sum-O-Primes from picoCTF 2022.

Source code :

from gmpy2 import isqrt
from Crypto.Util.number import long_to_bytes

x = 0x198e800b4f9e29e69889bc7a42b92dbd764cb22dbeb5fb81b1d9778bfe8c4b85d08a7f990019d537b6856aa1ff7355d0bef66c0a5c954bb4b7e58ac094c42ac1c23d23f8f763e41bbebdfa985505ab3571f8355290d2ca66ac333c4e30f1b7354c37d67db2c13c7e07ca3b6d98283f5042a55e23796ca227f428e0d3a83057510
e = 65537

delta = x ** 2 - 4 * (-1) * (-n)
d_sqrt = isqrt(delta)

p = (- x + d_sqrt) // -2
q = (- x - d_sqrt) // -2

phi_n = (p - 1) * (q - 1)
d = pow(e, -1, phi_n)
print("d =", d)

m = pow(c, d, n)
print("m =", long_to_bytes(m))

Output :

d = 1127439399893923133912707628369838645619413486081153868194322549263430464271487628166920090846284414060674923759835122712920275782145638815730909265745188866694498218417163612150327863917168285069522800442880578146452984443358315535368229409369978855340777181509567431540796668618072436317237316896508417951624330920268227424920546346184610507679335002930594105592638984054398797689679876059800971426371265461357943025665418837577601422699946107705988452212001703843148158300307727551909739089351035197873956373620030322437138163639780814925877499529967026959027228892716485664996757386343014299196168286140987346985
m = b'picoCTF{ee326097}'