Quadratic Leak

3 minutes to read

We are given the Python source code to encrypt the flag:

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes, bytes_to_long  

flag = b'ptm{REDACTED}'
flag = bytes_to_long(flag)

key = RSA.generate(2048)
n = key.n
e = key.e
p, q = key.p, key.q

leak = (p**2 + q**2 - p - q)%key.n

ciph = pow(flag, key.e, key.n)
ciph = long_to_bytes(ciph)

print(f'{n = }')
print(f'{e = }')
print(f'{ciph = }')
print(f'{leak = }')

And we have the output of the script in output.txt:

n = 18981841105895636526675685852772632158842968216380018810386298633786155635996081803989776444322885832862508871280454015266715098097212762303823817669399277859053310692838636039765017523835850272300243126797277954387477501506925762258179024160726332434715115654485883242651742714579029928789693932848304595300833348009779987606253681750351002940239431890559231554840489325837351081804589516122959648786979395257143753954514874848903523580352634665455711644772319481340052722305319056316013353993453687301538982087215697860640865435677605005049256026879380517059221652220476972139202570771113865372482940490650024591211
e = 65537
ciph = b'/>\xf0a\xe4\x95a\xb8!h\x11[\xa01\xa2\x08\xd2\xa0\xd7G\xb0CU`\x97\xc7\xa2\xe9\x94\x10=\xf7\xd6y{\x01u\xcbl\xe1\x7f\x8d\xa0\xd8_\xba\x8a\xd9\x85\xc1\xcc\rK\xc7\xb6\xfb.(\x99%\x1f\x0b\xeci\nR\x8b\xcc>\x86\x18\xe1ie\x19\x9dI\xda\x9bNh8N\xe5\xf2\xf3kP\xeb\x02d\xdei\xadd\xa0\x17WKs~3ohp\xeb\x83\x17>[\x87K\xd1\x0e>\xf6\xeeR\x08\xc4y\x9c\xc7\xbf\xdaq\x9a\xff\x99EQSg\x04"H\xc0=\xfc\x1b\xdcA\x95\xb9\x15m\xe6\x04N\x81%\xda\xa5\xb2P\x02\xbb\xb9\x83\xbf\xcfR\xffe\x0fT\xd9=f\xc1\xab\xd3:\xfb\xf8k\xc0\xd1]V\xc6pK\x86T\xfe\xd5\xadb\x7f\x1b\xb1\x9d9\xe51\xb8\'BY\xcb\x934\x1e\xfb\xc8\x96V4\x0f\xb3\xe4\xd9\x92e;v\x88\x8e\x16\x14?\xe9ew\x95\x8c\xa2\xfc\xc3\xf7,\xd50\xc3@\x11|\x8a\xe0\xee\xf3u\xa0\x8a_?A2[\xad\x8e\x81\x99\xf0\r'  
leak = 110277838449088002585424592968018361142419851286027284241723700708406129526007148628583636124051067276081936889565484783806534793568491888186904160969266846545579940493300734427497600123059580090561311191997050900418560468769108541786093143743441372956591688646550593311523980201035231511541259853198512190703006995530566933548862787123808685889850952840156903871573965022335639190635103252052979042642912530238710466180279568731038056810280199578414064760950459385877300845399348928704648108281000674478903445454838155321984920936780746021819652974978142789457099370813760033995294668404782700700352547809925049256

Source code analysis

The code is straight-forward. It implements a text-book RSA with 1024-bit primes $p$ and $q$. It encrypts the flag and shows the public parameters $n$ and $e = 65537$, and also the ciphertext $c$.

In addition, we are given a leak, which is the value of

$$ p^2 + q^2 - p - q \mod{n} $$

We must use the value of leak to find the primes $p$ and $q$.

Solution

Notice that $n = p \cdot q$ is a 2048-bit integer, since it is the product of two 1024-bit integers. As a result, $p^2 + q^2 - p - q$ is also a 2048-bit integer. Therefore,

$$ p^2 + q^2 - p - q = (p^2 + q^2 - p - q \mod{n}) + k \cdot n $$

For some small $k$. Assuming we know the exact value of $p^2 + q^2 - p - q$ (let’s denote it by $h$), we can solve a system of equations on variables $x$ and $y$:

$$ \begin{cases} x \cdot y = n \\ x^2 + y^2 - x - y = h \end{cases} $$

For instance, we can isolate $y = n / x$ on the first equation and come up with the following quartic polynomial:

$$ x^4 - x^3 - h \cdot x^2 - n \cdot x + n^2 = 0 $$

We know that $x = q$ is indeed an integer solution to the above polynomial equation (also $x = p$ due to the symmetry of the equations).

As a result, we can test several $k$ values (i.e. $k = 0, 1, 2, \dots$) and try to solve the polynomial equation. Once we find a solution, we will know both $p$ and $q$ and we will be able to decrypt RSA to get the flag.

Implementation

We can use SageMath in a REPL directly:

$ sage -q
sage: with open('output.txt') as f:
....:     exec(f.read())
....: 
sage: P.<x> = PolynomialRing(ZZ)
sage: k = 0
sage: 
sage: while True:
....:     h = leak + k * n
....:     if (roots := (x ** 4 - x ** 3 - h * x ** 2 - n * x + n ** 2).roots()):  
....:         (p, _), (q, _) = roots
....:         break
....:     k += 1
....: 
sage: k
2
sage: n == p * q and 1 < p < n and 1 < q < n
True

Flag

At this point, we can decrypt RSA the usual way to get the flag:

sage: phi_n = (p - 1) * (q - 1)
sage: d = pow(e, -1, phi_n)
sage: c = int(ciph.hex(), 16)
sage: m = pow(c, d, n)
sage: bytes.fromhex(hex(m)[2:])
b'ptm{Nonlinear_Algebra_Preserved_Over_Large_Integers}'