Problem 1 – Linear Combination Recovery

The flag is split into two parts m1 and m2. We are given a linear relation

a * m1 - b * m2 = 1

where the coefficients a and b are known and coprime. Reducing modulo b gives

m1 ≡ inverse(a, b)  (mod b)

Because m1 might be40000 larger than the modulus, we iterate over k until the concatenated plaintext contains the flag prefix. The code below recovers both parts.

from Crypto.Util.number import *

coeff_a = 18608629446895353521310408885845687520013234781800558
coeff_b = 14258810472138345414555137649316815272478951117940067

part1_base = inverse(coeff_a, coeff_b)

for offset in range(100000):
    part1 = part1_base + offset * coeff_b
    part2 = (coeff_a * part1 - 1) // coeff_b
    candidate = long_to_bytes(part1) + long_to_bytes(part2)
    if b'NSSCTF' in candidate:
        print(candidate)
        break

Problem 2 – Rabin‑style e = 4 Attack

Here the public exponent is 4, and the primes satisfy p ≡ 3 mod 4. We take square roots twice modulo each prime. The helper sqrt_mod for p ≡ 3 mod 4 yields two roots; applying it again produces two distinct values per prime. Combining them with the Chinese Remainder Theorem reveals the flag.

from Crypto.Util.number import *
from gmpy2 import inverse

def sqrt_mod(x, prime):          
    assert prime % 4 == 3
    r = pow(x, (prime + 1) // 4, prime)
    return [r, prime - r]

def crt_combine(vals, mods):
    N = mods[0] * mods[1]
    result = 0
    for v, m in zip(vals, mods):
        Mi = N // m
        result = (result + v * Mi * inverse(Mi, m)) % N
    return result

def fourth_roots_mod(x, prime):
    return sqrt_mod(sqrt_mod(x, prime)[1], prime)

p = 59146104467364373868799971411233588834178779836823785905639649355194168174467
q = 78458230412463183024731868185916348923227701568297699614451375213784918571587
c = 1203393285445255679455330581174083350744414151272999693874069337386260499408999133487149585390696161509841251500970131235102423165932460197848215104528310

p_roots = fourth_roots_mod(c, p)
q_roots = fourth_roots_mod(c, q)

for rp in p_roots:
    for rq in q_roots:
        msg = long_to_bytes(crt_combine([rp, rq], [p, q]))
        if b'NSSCTF' in msg:
            print(msg)

Problem 3 – Close Prime Factors via Continued Fractions

Two moduli n1, n2 are generated with very close primes p1 ≈ p2 and12 much larger than q1, q2. The ratio n1/n2 is approximated by q1/q2, and the continued fraction expansion of n1/n2 reveals q1 and q2. Once factored, decryption is straightforward.

from Crypto.Util.number import *
from gmpy2 import iroot, inverse

def cont_frac(enum, denom):
    cf = []
    while denom:
        cf.append(enum // denom)
        enum, denom = denom, enum % denom
    return cf

def convergents(cf):
    convs = []
    p0, q0 = 0, 1
    p1, q1 = 1, 0
    for a in cf:
        p2, q2 = a * p1 + p0, a * q1 + q0
        convs.append((p2, q2))
        p0, q0, p1, q1 = p1, q1, p2, q2
    return convs

n1 = 45965238261145848306223556876775641787109249067253988455950651872774381183888979035386577960806305813634216583223483001245996467366520071511779063266315692543617195166613592991812117446772937889819643718423377609566597230873623011099295202599905646652692946273375405832062164263711151844949794774229886016858313299259387152937467743637367261734624060321171598033647661809876890249035267180368762739600552966699295210431508056693524383116052539072065535970720901196322942269916455391238409489616842687658335666652878840458263998780783865062993401055465701207886230787204008073260653659510197069116237460322442433331870944968133645513020531983926180514313028320422449103156746225574626841023639595418255472716267486241462968101152032898749
n2 = 25459365600568360055376316722846535809281537088824978187355135247184417413329012865221456308642116409716822227032113740366024809533942721286337697830775221199570509665320400376959076685728357107457862901087218522281771857981155239522807950207375964963527837592797198372303427082343684305143238075402697262610809363109748984974325271762535573995993132076293275456692621516174749076897962348000698039074721998780555541905706268579496243099763776676950336105074846695227221690550755501320117554250942600626927600558489780841103863110357615957088709321079080707735028039675102383525496673233697130053936053431067133520717494376952763684807635780416860233261892013531534059267366382617635000415723745274490604551078385404286689447761642713963
e1 = 279586443815379026299414729432860797623
e2 = 249615977162294580923494787210301891647
c1 = 11515318475856179010858377918435934663304239594599788732135470038988222237790835017056954077794506499559722814863240838882673078330335616745578747265404229105473136943188301293198548838105990504750972653445744347121859396823995101611868191609259910876207038154174100742978387355304521374228562928260479446249263909934393657537918407756957032700052269827171045167752168509783885071211516601218892308228572735545579606908430615218499620619028799140945676768341492724044499209913045110359935325510223652935426973411960865908064824205626343685369866932545651037748553442488682593143020861196339307665638704485958986411837014559504992818255506454051842453553265179370878637153602580071152915165775491633322055360737581203750897698007951117808
c2 = 24544357952213952357056140974408354173440635791397720610932999473703241918398814255275362994811954064820912468224131892551724930677715676493892869921426790840199600798807085779112854131346378899855545138289836687048918660685766286852276199524789699567994154833159365800848535248059731927121269157841084905465048764152977389352561685340108834453730139893330210765986258703154334901509553990091592209268471594519326651914685843021165854654380119091009831071244459145750976193183411590207529489774630266528538380011000213950174694472355034075543687572037516433204151217601537869823709241020510051494619335852686100897182065588340025334679570763716458250649152257797833022586793526594784648938165537701256313728194521212887453997160504204832

for cand_q1, cand_q2 in convergents(cont_frac(n1, n2)):
    if n1 % cand_q1 == 0 and 1 < cand_q1 < n1:
        q1, q2 = cand_q1, cand_q2
        break

p1 = iroot(n1 // q1, 2)[0]
p2 = iroot(n2 // q2, 2)[0]
d1 = inverse(e1, p1 * (p1 - 1) * (q1 - 1))
d2 = inverse(e2, p2 * (p2 - 1) * (q2 - 1))
pt1 = pow(c1, d1, n1)
pt2 = pow(c2, d2, n2)
print(long_to_bytes(pt1) + long_to_bytes(pt2))

Problem 4 – Hidden Small r via Continued Fractions

Given a, p and the congruence a ≡ m * inverse(r, p) mod p. Rearranging yields a * r ≡ m (mod p). Since r is12 tiny compared to p, the fraction a/p approximates k/r. The convergents of a/p therefore expose r, from which we recover m.

from Crypto.Util.number import *

def frac_cf(num, den):
    quotients = []
    while den:
        quotients.append(num // den)
        num, den = den, num % den
    return quotients

def cv_from_cf(seq):
    p_prev, q_prev = 0, 1
    p_curr, q_curr = 1, 0
    res = []
    for a in seq:
        p_new = a * p_curr + p_prev
        q_new = a * q_curr + q_prev
        res.append((p_new, q_new))
        p_prev, q_prev, p_curr, q_curr = p_curr, q_curr, p_new, q_new
    return res

a_val = 79047880584807269054505204752966875903807058486141783766561521134845058071995038638934174701175782152417081883728635655442964823110171015637136681101856684888576194849310180873104729087883030291173114003115983405311162152717385429179852150760696213217464522070759438318396222163013306629318041233934326478247
p_val = 90596199661954314748094754376367411728681431234103196427120607507149461190520498120433570647077910673128371876546100672985278698226714483847201363857703757534255187784953078548908192496602029047268538065300238964884068500561488409356401505220814317044301436585177722826939067622852763442884505234084274439591

for kk, rr in cv_from_cf(frac_cf(a_val, p_val)):
    rec = (a_val * rr) % p_val
    pt = long_to_bytes(rec)
    if b'NSSCTF' in pt:
        print(pt)
        break

Problem 5 – Extended CRT with Non‑coprime Moduli

We have many ciphertexts encrypted with e = 7 under different moduli, some of which share factors. Ordinary CRT fails, so we use an extended CRT function that merges two congruences even when gcd(m1, m2) > 1. After raising the modulus high enough, we take the 7‑th root to obtain the plaintext.

from Crypto.Util.number import *
from gmpy2 import iroot, gcd

def merge_congruences(a1, n1, a2, n2):
    g = gcd(n1, n2)
    assert (a1 - a2) % g == 0
    lcm = n1 // g * n2
    a = (a1 + n1 * ((a2 - a1) // g) * inverse(n1 // g, n2 // g)) % lcm
    return a, lcm

mod_list = [48900330639594979739701067783234903348599425413588466525574910520196852415104874636276388006189258357683981763,
            52184798260918956005878710130354843122927544013692595240956998112200987084814453592388074200951779840156511,
            57591305346419909943538345276263585821186563609432856462492112562586368230163591993342956384688555395772999,
            1391052858660682537388264601016075339528373211889618359237336378385137832855656756800539626220549334300176727,
            8401669052993451281764489325068020625937224410830694438332016050030698435746929661939302694116817188225591,
            66809775375777747860816961274643428927028556487820183599747024350362932190079439298182707730302976119988715497,
            41209230281867957743385705727577318625405890894626062454495908709761427062490881938652489884059847194603237277,
            31140089821370202352241944402736292072447365626312703496944186462246895695650729682254970622208848300946861]
rem_list = [26617913696414745819584063604277199673357890677059949687794606743781436349829925794253672010780125661705587071,
            6332739614121961923948917957498597962902897015582697635859365080803944882904908423983706426654363433337197,
            46154051334276357655176765655327305918368830821288083739892570534253190653909520953027859629573215723954424,
            2800905135165447908315158053695706832127646195243072751493365013371469263897970241141686022109978485359114,
            3597083928897756955519089479028751799504001377334447013725903377254761160933418420625119547713455139382114,
            17032086144873551648611964054579542303630306316746409528107026138674853298939194425805809444921339677455174485,
            36111201824253386572496248461433786832561483450731317363761227351689971628309683994429845284904292821369745345,
            28548175317543234723297895187238113463350377151401226415566179373530461612253257137535830491771909906093171]

combined_rem, combined_mod = rem_list[0], mod_list[0]
for i in range(1, len(mod_list)):
    combined_rem, combined_mod = merge_congruences(combined_rem, combined_mod, rem_list[i], mod_list[i])

plain, exact = iroot(combined_rem, 7)
print(long_to_bytes(plain))

Problem 6 – Pollard p-1 with Custom Prime List

The factor p is p-1‑smooth with respect to a12 supplied list primes. We replace the usual small‑prime base with this list, accumulate the product sum, and compute p = gcd(2^sum - 1, n). Then standard RSA decryption follows.

primes = [...]   # given list
from Crypto.Util.number import *

n = 210488679270475701976181947365152313699517734264122394812492020724654505220623065289117447808270300405893088216711827935540458944042230307295703758023289811232234667671779565383964487868833609515040373751117785890923111021052281871560758159098018301948230396406718130378740957192704249130990473406094468375190967933383609736557
c = 136071043914570532351840574748667342595827512223368889758030473691165475344493240895540489846178990095609930878050872170334417124306746585253763197947342333489768575699470163018093386136808345465103492262428343569799463896437045282842447134475696863670001725029430508792000363373891006638520238615750531296612676072986388618657
e = 65537

acc = 1
for prime in primes:
    acc *= prime
p = gcd(pow(2, acc, n) - 1, n)
q = n // p
d = inverse(e, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, n)))

Problem 7 – Wiliams p+1 with Custom Prime List

The factor p satisfies p+1‑smoothness with respect to the12 given primes. We implement the Williams p+1 method using Lucas sequences. The helper mlucas multiplies along a Lucas sequence, and attack iterates over the list to find a non‑trivial factor.

primes = [...]   # provided
from Crypto.Util.number import *
from gmpy2 import iroot

def lucas_mul(v, k, n):
    v1, v2 = v, (v * v - 2) % n
    for bit in bin(k)[3:]:
        if bit == '0':
            v1, v2 = (v1 * v1 - 2) % n, (v1 * v2 - v) % n
        else:
            v1, v2 = (v1 * v2 - v) % n, (v2 * v2 - 2) % n
    return v1

def williams_factor(n):
    v_init = 1
    while True:
        for p in primes:
            exp = int(iroot(n, 2)[0])
            exp = exp.bit_length()   # simplified bound
            for _ in range(exp):
                v_init = lucas_mul(v_init, p, n)
            g = gcd(v_init - 2, n)
            if 1 < g < n:
                return g, n // g
            if g == n:
                break
        v_init += 1

n = 345799778173748173773868120733939877012606206055022173086869626920649670201345540822551954372166638650313660302429331346299033954403991966160361903811355684857744142271007451931591141051285664283723609717718163872529480367508508005122335725499745970420634995317589843507796161899995004285340611933981932785753209168028330041659
c = 246232608531423461212845855125527519175008303736088113629990791124779986502745272419907699490375796645611551466345965328844415806242069890639077695943105766009969737068824735226917926112338655266209848386322013506145057902662138167248624945138207215690482597144303445656882230801297916736896978224496017358461492736283036138486
e = 65537

p, q = williams_factor(n)
d = inverse(e, (p-1)*(q-1))
print(long_to_bytes(pow(c, d, n)))

Problem 8 – AMM When e Divides p-1

Here e divides p-1, so no modular inverse exists. We use the Adleman‑Manders‑Miller (AMM) root extraction algorithm. The function AMM returns a root and the required exponent. Then we enumerate all solutions by multiplying with the e‑th roots of unity constructed from an e‑th non‑residue. Finally, CRT combines候选人 from both primes.

from Crypto.Util.number import *
from gmpy2 import *
import random

def amm_extract(cipher, r, prime):
    s = prime - 1
    t = 0
    while s % r == 0:
        t += 1
        s //= r
    non_res = random.randint(1, prime - 1)
    while pow(non_res, (prime - 1) // r, prime) == 1:
        non_res = random.randint(1, prime - 1)
    unity = []
    gen = pow(non_res, s * (r ** (t - 1)), prime)
    for i in range(r):
        unity.append(pow(gen, i, prime))
    unity.append(1)
    d = gcd(r, s)
    alpha = inverse(r // d, s // d)
    k_list = []
    for n in range(t - 1):
        tmp = pow(cipher, (r * alpha - d) * (r ** (t - n - 2)), prime)
        for i in range(n):
            tmp = (pow(non_res, (s * k_list[i]) * (r ** (t - n - 1 + i)), prime) * tmp) % prime
        k_list.append(r - unity.index(tmp))
    root = pow(cipher, alpha, prime)
    for i in range(t - 1):
        root = (pow(non_res, (s * k_list[i]) * (r ** i), prime) * root) % prime
    return root, d

def all_amm_roots(root, r, prime):
    s = prime - 1
    t = 0
    while s % r == 0:
        t += 1
        s //= r
    non_res = random.randint(1, prime - 1)
    while pow(non_res, (prime - 1) // r, prime) == 1:
        non_res = random.randint(1, prime - 1)
    gen = pow(non_res, s * (r ** (t - 1)), prime)
    roots = []
    for i in range(r):
        roots.append((root * pow(gen, i, prime)) % prime)
    return roots

n = 38041020633815871156456469733983765765506895617311762629687651104582466286930269704125415948922860928755218376007606985275046819516740493733602776653724917044661666016759231716059415706703608364873041098478331738686843910748962386378250780017056206432910543374411668835255040201640020726710967482627384460424737495938659004753604600674521079949545966815918391090355556787926276553281009472950401599151788863393804355849499551329
c = 2252456587771662978440183865248648532442503596913181525329434089345680311102588580009450289493044848004270703980243056178363045412903946651952904162045861994915982599488021388197891419171012611795147125799759947942753772847866647801312816514803861011346523945623870123406891646751226481676463538137263366023714001998348605629756519894600802504515051642140147685496526829541501501664072723281466792594858474882239889529245732945
p = 5220649501756432310453173296020153841505609640978826669340282938895377093244978215488158231209243571089268416199675077647719021740691293187913372884975853901554910056350739745148711689601574920977808625399309470283
q = 7286645200183879820325990521698389973072307061827784645416472106180161656047009812712987400850001340478084529480635891468153462119149259083604029658605921695587836792877281924620444742434168448594010024363257554563
e = 1009

rt_p, _ = amm_extract(c, e, p)
rt_q, _ = amm_extract(c, e, q)
roots_p = all_amm_roots(rt_p, e, p)
roots_q = all_amm_roots(rt_q, e, q)
p_inv = inverse(p, q)
q_inv = inverse(q, p)
found = False
for rp in roots_p:
    if found: break
    for rq in roots_q:
        plain = (rp * q * q_inv + rq * p * p_inv) % n
        if b'NSSCTF' in long_to_bytes(plain):
            print(long_to_bytes(plain))
            found = True
            break

Problem 9 –assen gcd(e, q-1) > 1 with AMM

When e does not divide q-1 but d = gcd(e, q-1) > 1, we reduce the exponent. Using Bézout, we find a such that a * (e/d) ≡ 1 (mod (q-1)/d). Then (c^a) mod q is an (e/d)‑th power, and we can apply AMM with the smaller exponent e/d. The12 solutions are36 then combined with the p‑side roots through CRT.

from Crypto.Util.number import *
from gmpy2 import *
import random

def amm_extract(cipher, r, prime):
    # same implementation as above
    s = prime - 1
    t = 0
    while s % r == 0:
        t += 1
        s //= r
    non_res = random.randint(1, prime - 1)
    while pow(non_res, (prime - 1) // r, prime) == 1:
        non_res = random.randint(1, prime - 1)
    unity = []
    gen = pow(non_res, s * (r ** (t - 1)), prime)
    for i in range(r):
        unity.append(pow(gen, i, prime))
    unity.append(1)
    d = gcd(r, s)
    alpha = inverse(r // d, s // d)
    k_list = []
    for n in range(t - 1):
        tmp = pow(cipher, (r * alpha - d) * (r ** (t - n - 2)), prime)
        for i in range(n):
            tmp = (pow(non_res, (s * k_list[i]) * (r ** (t - n - 1 + i)), prime) * tmp) % prime
        k_list.append(r - unity.index(tmp))
    root = pow(cipher, alpha, prime)
    for i in range(t - 1):
        root = (pow(non_res, (s * k_list[i]) * (r ** i), prime) * root) % prime
    return root, d

def all_amm_roots(root, r, prime):
    # same as above
    s = prime - 1
    t = 0
    while s % r == 0:
        t += 1
        s //= r
    non_res = random.randint(1, prime - 1)
    while pow(non_res, (prime - 1) // r, prime) == 1:
        non_res = random.randint(1, prime - 1)
    gen = pow(non_res, s * (r ** (t - 1)), prime)
    roots = []
    for i in range(r):
        roots.append((root * pow(gen, i, prime)) % prime)
    return roots

n = 98950849420612859614279452190318782153029931966597217314273823358984928689736597943774367572478091193816498014404387458350141854427041188032441028722132300155987022405432547244436252627801235200799719531840755071562539171489733346246951714886747673950900290905148318965065773167290984966067642777528454814019184856012497536781760044965489668142694134954466581148235162435617572891367282110999553789319439912296241889469226304877
c = 22561646796929363815984273658718096881828574147472740106912668949512978818367595303883956088667384207835022579136977262135029404640598574466248596921339941958216824486529066880854722372158998556902335323841170236300423638675072077074005797219260622119718558697081430219981494670569821476853158740209737420919480047033900157150865588466910802691118334480300332681763467974691587834295938999022060676767513865584039532912503921584
p = 33918986475509072603988274492338254523919682179700323084167169617716245684540055969194500298976880885466534900490327133434356902533524212744941101469238500990334546197257933040365697281122571898438913033813040027859
q = 2917270228344219924472221188897798789902618263281810355113281879157575741497356945522168552316357276417700368971563177551494320723579146612010452353273237547587402941227901795977981691403950826343318848831462080703
e = 1009 * 7

rt_p, _ = amm_extract(c, e, p)
roots_p = all_amm_roots(rt_p, e, p)

reduced_exp = 1009
a = inverse(7, q - 1)
c_mod_q = pow(c, a, q)
rt_q, _ = amm_extract(c_mod_q, reduced_exp, q)
roots_q = all_amm_roots(rt_q, reduced_exp, q)

p_inv = inverse(p, q)
q_inv = inverse(q, p)
found = False
for rp in roots_p:
    if found: break
    for rq in roots_q:
        plain = (rp * q * q_inv + rq * p * p_inv) % n
        if b'NSSCTF' in plain:
            print(long_to_bytes(plain))
            found = True
            break

Problem 10 – PEM Key Parsing with OpenSSL

The RSA private key is stored in key.pem. Using OpenSSL we can extract the private exponent and modulus:

openssl rsa -in key.pem -inform pem -text

The output shows d and n. Since c is12 provided in enc, direct decryption yields the flag. Alternatively, we12 use Python’s Crypto.PublicKey module:

from Crypto.PublicKey import RSA
from Crypto.Util.number import *

priv = RSA.importKey(open('key.pem', 'rb').read())
ciphertext = bytes_to_long(open('enc', 'rb').read())
plain = pow(ciphertext, priv.d, priv.n)
print(long_to_bytes(plain))

Problem 11 – Manual DER Parsing of Truncated PEM

The PEM file is incomplete. After base64 decoding, we obtain a binary blob. We skip to the first 02 byte (tag for INTEGER), read the length, and extract four consecutive INTEGERs: q, dp, dq, inv(q, p). Since dq is12 available and the ciphertext is12 modulo q, we compute m ≡ c^dq mod q. As m is12 smaller than q, this is12 the exact plaintext.

from Crypto.Util.number import *

enc_value = 2329206064672111950904450292941421573350591294207157652026787098178545948258554492347649016030892000747909819064473414536692222493030122267884839986067073054508582403564557167583565364976046083954888777809177108315052118912603290095925912298584322873410379937455462434313487981715516761071523410121549134193124709612876311518391130974466069686830456036397449773159386026998482557500868323733155606973727191287617806211911722356975478414165867941665666556476756617951672736466672410799762479373101996896644454778482896784598378016390592459460753042458284030795009957030383305268628413551730442224404807955926606496353
q_val = 0x00befff9907f75bb7ad561131b5c76ae137bd67ae0e32b90f92b997b044277cab3dfeb84f255138127e1a4e53751a68db743a00ed8acc58f33107fe35db6b4813bc048db48bd530bcb35fba434dbb70e27d78aede2de0d4745df35a245417b8c74a31a7b55a77db45ebd6ed1dc4b3dcaa435a79dbf7240d96775372e64b58b0803
dp_val = 0x77a554614c111b51dea903a8e8222be795b45948805fc6f5ea67e60ad493f117b3033ea2ee84d87c0a29a87ea38908a93e313e08fe83dc91ba8695ba969d40f243addff620ee40bda8562ff5389661efd8b9d5976bacf2bc9a1cfc54d7704c7098441b1e7253760fc7dbcef7a417082e7492e8e0808f34d830c772e800714f41
dq_val = 0x1c1005fdea0c454075eb6e603dc49e2cf4abfd9fdf20be8b2d91be5650e1c2e18ccbd0dbbe0e4092b87f7ec212f812a8538247cc240e5eccd4e6c564367cece3f78b7cd482249a7dffef7a1fde0c56431a532a4283f7957a39a26ab61c39e7d81742c3ce40eea23aad40840b06ef0c3ff6362b623e8a32a715bcc6cf3b31333b
inv_val = 0x008488efbea72e9abac7f71085b86e9071bece170f8c92a387aebdcc89f8915c33739609a73cacd5559b3a56fd59082ed311bab49f42ea0ba6be5e253453db0fc8b5b6aab458163b8a013121fd5c554dcc51d81c57e60f59d9d7f8f4d45fab24365da039ed8fb5401cfaff0c8aae2191ae8bd742351d11034ff0f0c32fb0586810

m = pow(enc_value, dq_val, q_val)
print(long_to_bytes(m))