[MeepwnCTF 2018] Old School (Fermat's factorization attack)

조금 늦게 올리게되는 MeePwnCTF 2018 Qual에 나왔던 Old School이란 문제이다.

RSA에 익숙해졌다고 생각했는데, 당시 전혀 접근하지 못한 문제였는데; CTF가 끝나고 다른 팀의 Writeup을 보고 공부하였으나

결국 직접 소스코드를 짜보진 못하고 개념만 정리해서 블로그에 올렸었다.. (그것도 몇줄안되지만)

다시 한번 보자면, 이 문제는 Fermat's factorization attack에 관한 문제이다.

이 공격의 요점은 이렇다. 

N = p * q 인 N이 주어질때, p/q가 1에 근사하다면 Fermat's factorization으로 공격하여 p, q 값을 구할 수 있다.

from Crypto.Util.number import long_to_bytes
from gmpy2 import *
 
def xgcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return b, x0, y0
    
def mul_inv(b, n):
    g, x, _ = xgcd(b, n)
    if g == 1:
        return x % n
    
def fermat_factor(n):
    assert n % 2 != 0
    
    a = isqrt(n)
    b2 = square(a) - n
    
    while not is_square(b2):
        a += 1
        b2 = square(a) - n
    p = a + isqrt(b2)
    q = a - isqrt(b2)
    
    return int(p), int(q)
    
 
n = 12263815858436391339801252716055343215721551207190585812808883921492616938019767754888047221243921529199781329682187336097470283133260860905444173937906698593993435816362355791049334301256672146334457160396157422171213155186704409015520723701624704179794619860512757194475928285433621469983215042163268337482613981138412642113164161985610041212644438310461087934752877418645890869616237437302541973412868157911349542527624597832254480191497600938121405413426358837072839977429474448232347107365820912432960433009928432513624193587173708951345864949412064817411473475077328080824358689398099979260395549956349458200199
e = 65537
c = 10768566524581730417282966534533772232170128646105592645274840624344800039953305762328123247486367933169410426551021676301441508080687130308882531249672782247453418751384028303096785698132140306753136583313099836328879191020815311025909775009768461235238724055399564994913948731120265357427622567179898229336239135361607806956357971819975387160453721508112358768552880424521729959498368682405606641964356553284372394601190105374421489502575623037672340535664494377154727704978673190317341737416683547852588813171964475428949505648909852833637140722157843587170747890226852432960545241872169453977768278393240010335066
 
p, q = fermat_factor(n)
phi = (p-1)*(q-1)
 
d = mul_inv(e, phi)
plain = pow(c, d, n)
 
print("p :" + str(p))
print("q :" + str(q))
print("p/q :" +str(p/float(q)))
 
print("flag : " + long_to_bytes(plain))