# 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 python3from Crypto.Util.number import inverse, long_to_bytes
#--------data--------#
N = 3349683240683303752040100187123245076775802838668125325785318315004398778586538866210198083573169673444543518654385038484177110828274648967185831623610409867689938609495858551308025785883804091e = 65537c = 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 factorizationdef 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
```plaintextflag{ooo_la_la_those_are_sexy_primes}```