Ooo-la-la

Topics

• Fermat factorization

Challenge

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 (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

#!/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

flag{ooo_la_la_those_are_sexy_primes}