# Ooo-la-la

## Topics

- Fermat factorization

## Challenge

[prompt.txt](https://github.com/ret2basic/ret2basic.github.io/blob/master/challs/NahamCon_CTF_2020/Crypto/Ooo-la-la/prompt.txt)

## Analysis

When the two factors `p` and `q` of `n` is close (specifically, when `p - q` is less than the fourth root of `n`), we could use **Fermat factorization** to factor `n`. The detailed proof can be found in [this blog post](https://bitsdeep.com/posts/attacking-rsa-for-fun-and-ctf-points-part-2/) (highly recommand to read all four parts carefully).

This challenge can be easily solved using `factordb`, but let's build a script for learning purpose:

## Script

```python
#!/usr/bin/env python3
from Crypto.Util.number import inverse, long_to_bytes

#--------data--------#

N = 3349683240683303752040100187123245076775802838668125325785318315004398778586538866210198083573169673444543518654385038484177110828274648967185831623610409867689938609495858551308025785883804091
e = 65537
c = 87760575554266991015431110922576261532159376718765701749513766666239189012106797683148334771446801021047078003121816710825033894805743112580942399985961509685534309879621205633997976721084983

#--------helper functions--------#

def isqrt(n):
x = n
y = (x + n // x) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x

# fermat factorization
def fermat(n, verbose=False):
a = isqrt(n) # int(ceil(n**0.5))
b2 = a*a - n
b = isqrt(n) # int(b2**0.5)
count = 0
while b*b != b2:
if verbose:
print('Trying: a=%s b2=%s b=%s' % (a, b2, b))
a = a + 1
b2 = a*a - n
b = isqrt(b2) # int(b2**0.5)
count += 1
p=a+b
q=a-b
assert n == p * q
return p, q

#--------rsa--------#

p, q = fermat(N)
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)
flag = long_to_bytes(m).decode()

print(flag)
```

## Flag

```plaintext
flag{ooo_la_la_those_are_sexy_primes}
```