[Crypto] hello - COMPFEST CTF 2026

주어진 문제 파일이다.

def generate_pq(size):
    mu = randint(100, 1000)
    p = random_prime(1 << (size - 1), 1 << size)
    while True:
        q = random_prime(1 << (size - 1), 1 << size)

        if p < q:
            p, q = q, p
            if q < p < mu*q:
                 break
    return p, q, mu


def generate_instance(nbits, prec=1024):
    n = 10  # parameter n such that phi = (p^n - 1)(q^n - 1)
    RF = RealField(prec)
    p, q, mu = generate_pq(nbits//2)
    N = p*q
    phi = (p^n - 1) * (q^n - 1)
    N_1 = RF(N^(n//2))
    N_2 = RF(N^n)
    a = (2*mu^2*N_2 - (mu^2+1)^2*N_1 + 2*mu^2)
    b = (4*mu^2*(mu^2+1)*N + 2*(3*mu^4+4*mu^2+1)*N_1)
    threshold = a / b
    found = False

    while not found:
        d = randint(1, round(sqrt(threshold)) - 1)
        if gcd(d, phi) == 1:
            found = True
    
    e = inverse_mod(phi-d, phi)
    return N, e


flag = b'COMPFEST{fake_flag}'
pad_len = 10 - (len(flag) % 10)
padded_flag = flag + bytes([pad_len] * pad_len)
chunk_size = len(padded_flag) // 10
chunks = [padded_flag[i:i+chunk_size] for i in range(0, len(padded_flag), chunk_size)]
temp = [int.from_bytes(c, 'big') for c in chunks]
n = len(temp)
N, e = generate_instance(2048)
r = 2
R.<x> = PolynomialRing(Zmod(N))
A.<t> = R.quotient(x^n - r)
temp_poly = A(temp)
c = temp_poly^e

print("Hello! Can you recover the hidden message?")
print(f"N = {N}")
print(f"e = {e}")
print(f"c = {c}")

# N = 3590180681722560683285381088996291614949702075688185647918792706184505414324401442654396063905528374421166636132591883232283675686794121618361514309810575475497708015570684325043164062168342018690965605738829716583121802110732652751494344375613474180116478321254470888834882493684817629933472357454107597361915280884347919052516959593289441607701790805689119782282944114931097090549121962434401987286278602656816172835798217563337780021988798946265630216881661865140769559634848884406861049560448000050946929599932539934143042301615561179378712730986531394491313183517094283419918831936212685494603993640302240674913
# e = 213671286769939700603776286166008365457597952750756106926319147149071819475723520172510617427509206532461335299150009682584683735722267427340224387918170184862320602882320230539874715308748460678269838311466452070860903511270378108127998693129784141180511351365489793088436590483427057969224482274769426195875620830808767601105020665321181138970742046247348945820001415687537535727526130399383060912273226138092800877337835956914016102985401482872500778551169473342081100764587048607502935429078096652762360719763053907153291484274938642009816048852156185274268465918822677206746513821803452663896304330511700803421433968232332917803111450863829321016650474915308937190741922157857104333701087795261564776204885698011963537577216818187755384821615762850873369192901424811617579294986561337611278214222801937913847219818414038613408574152553856612598370056902164618692125160827104994162877134767707490698858531855569749443289659273063124816216175525000958543097307886216509942046569473317014921629690795623578834695870006933816339108779469533427029944972812972729126676929357038126553669947679011943384534094084051182661918781401586453151588048520013739213315714780599176013112511985077396867714776030994634571677119400568662499553934338791483936908730853008525630678726321536197352353371277445432890601199745017830983759922932029050317056946943644430498035475102535944413562371754290728631281777394751004296164764405830360035439037380232910861684879208236695582444503201429462401630449629661486010463367647388024921691459541789115101511503390824061882534824033286797162477279066505690162048557532225557669366466349624411886168462978602433520595141581890290667757410779564125268674765883572670852935465708951882126774446137240205243696090381684263787948103521435132028819697214550136967618761895649182419796975526060874865413187796785974682827632402039278281567246377529172083639199668498656006872658580594827085823649958313314108188873091690774946554525318882172312529974397191568004211702990754680455823515414021318192634083091142329592821673360268003240346891689389852511863962880774619196386752717100213402590414459496903799499392856064423472194820537804429562636142267753014443732596779601218875391866668766307191711377901741735268603151279467068990559661339649597141453603549922400933732027408739746003582038954501282868287954643371342736654149235509834711601132939801143532816824086903431314158366763118776567800264313828200714394821545343201414076026716929870936385621791814830702383899804078297934144771956096429539751370289179182275980356053602901609021952309220077287641291359549802352616308158479507768588100427651321545293245962222276973648945051680013473828032774718688411363022719483895105511073082820498187984838940326830202214344815291390403914585600529087737387313503244043429260027559427030799628880600328555931285171988383498491264304585794692064275495315853584714840263611488804435921955542912302372790965454374852790993394480818111850185854537565177632965162285862968701033928374551574827214227664150869687196470722168279131588453032741144812288369056230299066739320712974998071469248115785434079088451908527923280146373877217938043392884324734841894548678927941293394081081793988211054911563983151177484614035105071063835363905117423012353078707119771504877450188455788018964020874801384469887653243009666747998870389541548981363488226917909445475136552146687253943150921083455192971950779314786935298125422738879020301907857558481220542850388247223128088963442415092598584586726892587240226105567385507078118214760227667582246419770090288735166996158034229324065687114493845608827299713422662269939645792658196647871550781208668719051646748693618079093634633363919543508088303258590486813412052775571241177207495690328314997999918375723311872859003289490489903781350783133240131102708127547274788614693061694224207737640553282669525827077349374443418588234504278535332522873454545612154121282095373529064051066154633090269366894878290362120243587757534873282819429797512524775312144436087305526236217902581490714729425825015197765706343271234630623285047019791586028938765705566025065454875338068526180588387883245173011045958530500513715887185951793126878608688558729672676636795391497941645639041332288350198694557834092427060233901145963388764322488674764755125405226855647332164096851365912635045366739309512052713680589850836676764247490651661859555720315852950158191146071132461367424057120098041236438816838430256163948831017919784570648810686474609511945159733793058053561734160340533585212403125223487164216958550450629429573738345559663472063928601121051535793193541751167963541919274722336966579982256708279446351406507288810639805353668084424580761046436882281016528446315249050571586322705549985321314232523049355438964443309370770877613425960216416596258875058295494422254923673478993572391971798993967765489319019332199155783169810770302032612089698584490721876171965027246473865172189464024221254945693462008717649070491755295690394300322792005101683376695843298142211344739013809714301155556281536528463232522846576316755109958765049553040642048622541249392804124116345221120216332232775588431265525953871155088642572544127739821784761418151726993886393828445313217951374907272140685891350508421734068564810860905763441341360729817817721408951088721714274566022877693035914153705005097043530864921136539563136876617548546595001332633464687373288476825629514182054204291633320655821590098042724580525200045341045989324243997428837352344325122255107150705565315396784939945116557398623855130550255725250564006388194338798511901135564923189281326226743340835805463931752168363287362727746765498573349127760471885526113096533842830666078422083268574869588348931377154444711038306682946127369597758357974390274050020989692350928823111984112384847914215163255666418451351200393247411278273979531955776855104125967569390842064257920964956487189031778367352934784049187402560281400251851498733336543680903778036128979874169142855847867976043117453616566015996224834580671974165026780245878448538770013639067979440723633288652404318746082056352281411312995698708593924539312813454630753100660502681444916560234118394503985941
# c = 178331979262384284468738995619104514296042169820116427182170464832977629531625151226736187673708082856156938068081204324568620409092475856634425801669558914807901025107644949699600189374585580836464304262763140871847888668666598492270796914477108109252597282450694252508905078217561481993843102380416511796025586976497897539859241445744634486951035539747686369552337152241755987674912534444275404790642364530406449335830121894400557746770326358280510845394257586087355905307829397492221151557285079193193231318426596871946201907610500644458761127965936358407769998215574662838297163099040116285149125218059508083885*t^9 + 3525903127560742302140041793921466007458089521695178731376626156631320796485306459380575335125229130928595203224555135623878910439478931273639229933928955973828985430881581782334318562168557119153997107134508974576085506856429357281573339559183245307990231781904615229041403505356468969676087275383163752745814811628112004574456861033083689061201644144642119388869147622001444098103820172568864929737871377586134503846059878105451945799225722544256265923186331362747016093921507022488643401516236911152542116728309985451834540010310454303306281999889712829949097629101986974126606919630528593791928458039137963061112*t^8 + 2074150218813792209619026736986681081243449768184493839973160916189780737439111491330927882832756516016840147214653983477551814093271226884113895874875529047441299750680321072312669582611226656965572059931053310761063029843360834385202124304672454202341547508642377285062241764641524224560186589468842233411662998661041944000869170000171530152177763465287151344661710253300607080783047303502804545134272718825359069684904537247041013255388054098547236498789500845148129821853787046044141351798981875639583319108797115961548489494572196574960730741024085633877313389849989680791317109858617484117907122563958604653189*t^7 + 636136047977385835362285167630385683681293197163297763433080082581393717377407394385239487376486978769395041719790149907471120275984212338694681844240771541970142179966977853968266558494633698277961763518212926461355580686095489405733452915611390567813988702227926960287748056246537915834577272682169997226241017797669812345187693262878880146703386249386255257564980064063494090095968070854098048008613407896087971265933488653071555464422741658357556013439563209724041536369423557228257945770477255266203342746318807469217780268713458460392002152619088813904950447159085850975944050910435245329520510209357092327401*t^6 + 485616417459072866079676326310195847159298049600949388959786114089521155346424961427654743397284857210584278087954229467078937661864125051543629854116610179450076873257027748718380642305965966672250445300949304807184014780671745778212812959618518688875968296030898240330831583551531871619681984113532618772316281939526824522213553959582519127043537711126955413584642953484118281364284537376596304044359704438452661931971111582235223654888376680682881701672499980424766376512846155675360499404725151293531027245992036968626648186288401656174990675456740057372143414325211043166200139413367044499984248882223258876365*t^5 + 1073941836190575989534672716322654560548343335869947486356077271861957936401521783924126156345129456476644275597385843267467686720624098827650860147530847186463678925152878105218027079627300538168263844030162555260462877301273894621588730306942080224084696402609149785474862183069577151669225744541040925594649964491903979954108791775702008203521663128246610684060908159141281130771592717119938316572355361801911528094471576622534088531232100108732880496996925208115903210561364452400558451564790029817758128893742431331424852598457431349366924274644056482327784351695073334849290026423471728004978562717051340443824*t^4 + 2858288042143711110394662914039481948588327039990845613477097985873004871926610623023795950365389124949454223111655961508974258698607274173639029022240520818533405829277402282172868110324596320652874649265095295612807310386049349811384413875450220152092945444348627338773505578798340034334528157020118912493260437583444930692336858621212340176043047011907679172006008660890338829196040715979148278492452425138352837599708918227420800824437504064069562131472928786630381066310273766250874773262999176536865924191533099660767334206634896171916946361547935474732238369065021113512726810413641774384600303982769633070960*t^3 + 3073794636959775995174536486151616793197747790441831456178146203349597251702397814633547103708289639929751997047630307277200757021420935109329810536273540609586567873147249151413205873766520483178768429722950500024870267364872735493280955010148993985610216355886757433151432637936248974993608016166166820030230738441705234789517896750091898801398612589872245487315930759555711481507626120321385393417719255369719495338669152999479185904992518532326166665710813978584162182591804125493874122645710332714330597245195371291047618665766564590715260340422604199461490896565320865707557455367313036949644720886956262563554*t^2 + 2223125131528669750954856404481299944090238138633065307947285274376849213463978581506425464925138934679966266197400849179316438898716997621820210703659579927813736532273290582765391443528592696777728799053883221386039430775335606024940576179788669489352043439953820238592596809914704622465877576311854820622947301379079329345646639785916481549346045125867941673710015887955535503338575523393546969531802980142618962221970580592887470270376012487470649472024252237471530802627810579120400343907596632163416655793405578327404789548920809844006724595573314521603351177955093231621180626538341235651027099923607533902788*t + 2701940806806238382284407398956345047042363487246015295288049346404872156979832080944379573324450724362846584334954443814106104334484387256778450468934364892689584371639566898724972972555718167198608369631977146695744387961311922731905351502558133779527484802313505661390045262980349535591644792647799220530652713218925543154301106958673734029314580724824361253692954032206555923371878424768208198580732683279182585100179102231464055767222549941081055699712830396034865024118402302817335364994201242400177647426867914442079648682539745051839027002787678980442379852598626760163771733815796103555962787143602682202976

generate_instance()에서 공개키와 비밀키를 생성하는데, 일반적인 방법이 아니다.

$\phi(N) = (p^{10} - 1)(q^{10} - 1)$에 대해 $e(\phi(N) - d) \equiv 1 \pmod{\phi(N)}$이다.

$\phi(N)$을 소거할 수 있으므로 $ed + 1 \equiv 0 \pmod{\phi(N)}$이다.

어떤 정수 $k$에 대해 $ed + 1 = k\phi(N) \approx ed$이다.

$\phi(N) \approx N^{10}$이므로 위 등식을 아래의 근사식으로 근사할 수 있다.

$ed \approx kN^{10}$

$\frac{e}{N^{10}} \approx \frac{k}{d}$

$\frac{e}{N^{10}}$를 연분수 전개해 얻은 수렴분수들이 $\frac{k}{d}$에 근사되므로 $d$를 구할 수 있다.

이는 Wiener's Attack을 구현한 문제이다.

 

각 수렴분수에 대해 다음 조건을 확인해야한다.

위 식에서 $\phi(N) = \frac{ed + 1}{k}$이다.

$p^{10} + q^{10} = N^{10} - \phi(N) + 1$이고, 완전제곱식을 이용해 $p^{10} - q^{10}$을 구할 수 있다.

합과 차로 $p^{10},\ q^{10}$을 구하고, 10제곱근을 구해 $p,\ q$를 구할 수 있다.

$p \times q = N$이라면 개인키로 $\phi(N) - d$를 이용할 수 있다.

이후 문제와 동일한 몫환에서 RSA 복호화를 수행하면 플래그를 얻을 수 있다.

 

from pwn import *
from sage.all import *
from Crypto.Util.number import long_to_bytes as l2b
import sys

sys.set_int_max_str_digits(10000)

io = remote('34.2.147.230', 3000)
io.recvuntil(b'?\n')

N = ZZ(io.recvline(False).decode().split(' = ')[1])
e = ZZ(io.recvline(False).decode().split(' = ')[1])
c = io.recvline(False).decode().split(' = ')[1]
c = c.replace('^', '**')

R = PolynomialRing(Zmod(N), 'x')
x = R.gen()
A = R.quotient(x**10 - 2, 't')
t = A.gen()
ct = eval(c, {'t': t})


def euclidean(num, den):
    assert den != 0
    a, r = num // den, num % den
    yield a

    while r:
        num, den = den, r
        a, r = num // den, num % den
        yield a

def convergent(num, den):
    p_prev, p_curr = 0, 1
    q_prev, q_curr = 1, 0

    for a in euclidean(num, den):
        p = a * p_curr + p_prev
        q = a * q_curr + q_prev
        yield a, p, q

        p_prev, p_curr = p_curr, p
        q_prev, q_curr = q_curr, q

for a, k, d in convergent(e, N**10):
    if k == 0:
        continue

    if (e * d + 1) % k != 0:
        continue

    phi_i = (e * d + 1) // k
    s = N**10 - phi_i + 1 # p^10 + q^10
    delta = s * s - 4 * N**10
    if delta < 0 or not ZZ(delta).is_square():
        continue

    r = ZZ(delta).isqrt() # p^10 - q^10

    p10 = (s + r) // 2
    q10 = (s - r) // 2

    p = ZZ(p10).nth_root(10)
    q = ZZ(q10).nth_root(10)
    if p * q == N:
        print('found')
        d = phi_i - d
        pt = ct**d

        flag = b''
        for coef in pt.list():
            flag += l2b(int(coef))

        print(flag.decode())
        break

# COMPFEST18{c0ngr4tzzz_h3ngk3rrrr_g3n3r4l1Zed_w13n3R_4ttacK}