# Anti Fermat - zer0pts CTF 2022
###### tags: `zer0pts CTF 2022`

Writeups: https://hackmd.io/@ptr-yudai/rJgjygUM9

## overview

It is a traditional RSA challenge. $p$ is 1024bit prime and $q = (p \oplus 2^{1024} - 1) + \alpha$.

## solution

We can approximate $q \simeq 2^{1024} - p - 1$. Then $p^2 - (2^{1024} - 1)p + n \simeq 0$ stands.

We can bruteforce small $\delta$ such that $p^2 - (2^{1024} - 1)p + n \pm \delta = 0$ and solve the quadratic to find $p$

## exploit

with open('./distfiles/output.txt', 'r') as f:
    exec(f.read())

beta = 2**1024 - 1
ep = int((beta - sqrt(beta**2 - 4*n)) / 2)

delta = 0
while n%(ep+delta) != 0 and n%(ep-delta) != 0:
    delta += 1

if n % (ep+delta) == 0:
    p, q = ep+delta, n//(ep+delta)
else:
    p, q = ep-delta, n//(ep-delta)

d = inverse_mod(65537, (p-1)*(q-1))
flag = int.to_bytes(int(power_mod(c, d, n)), 2048//8, 'big')

print(flag.strip(b'\0').decode())