Fermat’s factorization method

This method works very fast with $p$ and $q$ are close (the difference between 2 numbers is small), slow when those 2 numbers are far apart.

We can rewrite $N$ as:

$$ N=(A+B)(A-B) $$

where:

$$ A:\ the\ average\ of\ 2\ primes\\ B:\ the\ distances\ between\ A\ and \ 2\ primes $$

If the primes are close, $A$ is close to $\sqrt{N}$. We can simply guess the value of $A$ by starting at $\sqrt{N}$, increasing by 1 each round. For each round, we check if the result of $B^2=A^2-N$ is a square of an integer or not. In theory, such $A$ and $B$ should always be found by using Fermat’s method, but since there’s no such computers can

int fermat(int n) {
    int a = ceil(sqrt(n));
    int b2 = a*a - n;
    int b = round(sqrt(b2));
    while (b * b != b2) {
        a = a + 1;
        b2 = a*a - n;
        b = round(sqrt(b2));
    }
    return a - b; // this returns p, then q = N/p
}
// I haven't test what will happen if b2 is a negative number at the start.
// In the example below, I have to check if b2 is larger than 0 or not first.

This is the idea to solve the next challenge from UDCTF 2023

# UDCTF 2023
from Crypto.Util.number import *
import sympy.ntheory as nt
import random
from gmpy import *

p=getPrime(1024)
q=nt.nextprime(p)
for _ in tqdm(range(random.randint(500,10000))):
    q=nt.nextprime(q)
N=p*q
msg="UDCTF{REDACTED}"
pt=bytes_to_long(msg)
e=65537
ct=pow(pt,e,N)
print(N)
print(e)
print(ct)

In this example, $q$ is generated as a random-number-next-prime of $p$ using module sympy . We can already notice that although the difference between 2 numbers is random, it is still in the brute-force-able range. By using Fermat’s method, $N$will easily be factorized.

Solution:

from Crypto.Util.number import *
from gmpy2 import isqrt
N = 17740803753336460891508014077951088945415214329359164945595622460861617151883658129377771074141448545977293824812472806768754107334272113784618671425945265453677763300584120796664192793654787317526905676618168560287204392207536711238413377822113265783504873957094131330620182217422910507867161033695120195691266283498385072573721376398480018719760538723050237163598524153522595496137288270407836138586188296538117138982579560625325815068701431157466298638302885600982291990551448117534677697122276691651611734934147801954625280213769902451417946572231015611006746186167211313556716518863585799128114202130873384852581
e = 65537
ct = 7617664236008252568996899627946125782926068188323112773389474654757630578865481085502759186904920518615173703165984894164411436709177950136929724052191922739861682189280802963747906815275683543148623167088950096943169566195634558711652670745197446307315888349532981492405588457559228674864147994684328968321710022127803384848143475788457274558988285904875669797926919759123645348144531804252200718312650929926931919262408975771593313266992606751663814830129337536342634243623652919127335934704778878412649409415730419077839365246227059700689395639431013008985996793686430486195007712091309878718060405038405039494286

def fermat(N):
    a = isqrt(N)
    counter =0
    while True:
        counter+=1 
        if (a*a)-N >=0:
            b = isqrt((a*a)-N)
            while b*b != (a*a)-N:
                a+=1
                b=isqrt((a*a)-N)
            return a-b
        else:
            a+=1
            b=isqrt((a*a)-N)
		print(counter) # just for fun :d

p = fermat(N)
q = N//p
d = inverse(e,(p-1)*(q-1)) # or pow(e,-1,(p-1)*(q-1))
m = pow(ct,d,N)
print(long_to_bytes(m))

# UDCTF{F3rma7_c4n_sur3_fac70r!}