cryptoverse CTF 2022

Challenge Files

Warmup 1

Decode the following ciphertext: cGlwZ3N7cG5yZm5lXzY0X3Nnan0=.

This is just base64 and then rot13
https://gchq.github.io/CyberChef/#recipe=From_Base64('A-Za-z0-9%2B/%3D',true,false)ROT13(true,true,false,13)&input=Y0dsd1ozTjdjRzV5Wm01bFh6WTBYM05uYW4w

cvctf{caesar_64_ftw}

Warmup 2

First described by Giovan Battista Bellaso in 1553, this cipher is easy to understand and implement, but it resisted all attempts to break it until 1863, three centuries later.

Remember: The Key to success is determination.

fzvxw{hqtegmfr_lw_msf_scrslg_kvwlhyk_fpr_kxg?}

https://www.dcode.fr/vigenere-cipher

cvctf{vigenere_is_too_guessy_without_the_key?}

Warmup 3

You should recognize this instantly.

-.-. …- -.-. - ..-. – —– .-. ….. …– .. … -. —– - ….. —– ..-. ..- -.

Note: Add { and } around the flag. Flag is all lower case.

https://www.dcode.fr/morse-code

CVCTFM0R53ISN0T50FUN

cvctf{m0r53isn0t50fun}

Warmup 4

Last warmup. You should get it fast if you use any social media.

Ｉn sｃｉencｅ fіctіοｎ, ｍetａνerse ｉs ｉtｅrａtiｏｎоf the Iｎternｅｔ as a sⅰｎgｌe, universal and immersive virtual world that is facilitated by the use of virtual reality and augmented reality headsets.

Note: Wrap the message you decoded in cvctf{}.

Note 2: This challenge involves some steganography tool related to a social media.

https://holloway.nz/steg/

cvctf{secretsaretobeh1dd3n}

Substitution

Substitution is a cryptographic technique where a plaintext is replaced by a ciphertext. The ciphertext is a substitution of the plaintext.

Here is a very simple CTF-related substitution cipher. Find out the flag.

Hxpkdiz kcz Osxe ja x apzhjxs ljvr go jvogimxkjgv azhdijkf hgmpzkjkjgva. Kcziz xiz kcizz hgmmgv kfpza, Uzgpxirf, Xkkxhl Rzozvhz xvr mjyzr. Jo fgd cxwz ojedizr gdk kcz xqgwz mzaaxez, cziz ja fgdi osxe, pszxaz xrr hdisf qixhlzka qzogiz adqmjaajgv: hwhkoxwzifajmpszadqakjkdkjgv

http://quipqiup.com/

cvctf{averysimplesubstitution}

RSA 1

The n is so large that it’s not possible to factor it. Or is it?

n = 0x7c05a45d02649367ebf6f472663119777ce5f9b3f2283c7b03471e9feb1714a3ce9fa31460eebd9cd5aca7620ecdb52693a736e2fcc83d7909130c6038813fd16ef50c5ca6f491b4a8571289e6ef710536c4615604f8e7aeea606d4b5f59d7adbec935df23dc2bbc2adebbee07c05beb7fa68065805d8c8f0e86b5c3f654e651
e = 0x10001
ct = 0x35b63f7513dbb828800a6bcd708d87a6c9f33af634b8006d7a94b7e3ba62e6b9a1732a58dc35a8df9f7554e1168bfe3de1cb64792332fc8e5c9d5db1e49e86deb650ee0313aae53b227c75e40779a150ddb521f3c80f139e26b2a8880f0869f755965346cd28b7ddb132cf8d8dcc31c6b1befc83e21d8c452bcce8b9207ab76e

In this challenge the author simply uploaded the factors of n to http://factordb.com

n = 0x7c05a45d02649367ebf6f472663119777ce5f9b3f2283c7b03471e9feb1714a3ce9fa31460eebd9cd5aca7620ecdb52693a736e2fcc83d7909130c6038813fd16ef50c5ca6f491b4a8571289e6ef710536c4615604f8e7aeea606d4b5f59d7adbec935df23dc2bbc2adebbee07c05beb7fa68065805d8c8f0e86b5c3f654e651
e = 0x10001
ct = 0x35b63f7513dbb828800a6bcd708d87a6c9f33af634b8006d7a94b7e3ba62e6b9a1732a58dc35a8df9f7554e1168bfe3de1cb64792332fc8e5c9d5db1e49e86deb650ee0313aae53b227c75e40779a150ddb521f3c80f139e26b2a8880f0869f755965346cd28b7ddb132cf8d8dcc31c6b1befc83e21d8c452bcce8b9207ab76e
p = 8156072525389912369788197863285751656042515380911795404436333529629416084362735262281722179416240983448945672233749861517470671156357917601583268804973543
q = n//p
d = pow(e, -1, (p-1)*(q-1))
flag = long_to_bytes(pow(ct, d, n))
print(flag)
#b'cvctf{f4c70rDB_15_p0w3rfu1}'

RSA 2

Part 1: p is given so I just solve mod p.

Part 2: p and q are close so use Fermat factorisation.

from Crypto.Util.number import long_to_bytes
from gmpy2 import isqrt, is_square


def part_1():
    p = 12288921312928905252066685441095433471598896337203035200127730574490649634697724898647492622180506530440487680891254318894425463123822054731206592479004443
    e = 65537
    ct = 477810761866191067447439010305549740987167655432530443522675033657369723786048842040442154581768138072922232065577919832660311749722811153131700616623491664129964460155641257628035443854025940214881843381516731886468952698960658032624539602708992596947417406064936755170646371843885836414699432839708624613424771775975205847206849618916244266841618040141811129621887797853986955912887940909492892452582572860341612662314834825669781647797309123819689482025845274220304090264258705352508079779481185568502456351966535816576336785374480232497981502094209095089630736220344636425703292835013643094434503207582627896342361399742142907352683789098893088197300169085876182759566238368607976127565393402067969228801828020040880864943530678429628691860709498984558508259930639978577326355937177663775355912658421617068727167293437739623405125007006701483686062823345676708079582959894137740287934681427537716868544192722130809973616745739204044297782671776628943651456537315348365219970412662895839161961678735840519665352845752401565067760259782075123983614541164569034238760232355335830834765695866518376808132147639516485086981529017855541096845234038238351348084096654297016020126411818954399154297310283491861804817107618193838806953155
    assert gcd(e, p-1) == 1
    m = mod(ct, p).nth_root(e)
    return long_to_bytes(int(m))


def fermat(n):
    a = isqrt(n)
    b = a**2 - n
    while not is_square(b):
        a += 1
        b = a**2 - n
    p = int(a + isqrt(b))
    return p, n//p


def part_2():
    n = 85205911394226026500275210536070696774019932212697333763455696542783046512381571530938238053084695855960959283864240454975283339087819608102879636911292604501949036560581582119299425314297903747045402522844383142899951990239300430074264857012937328120615676527671685158004985642485347181510738733455006987563
    e = 65537
    ct = 36094975186594521686754290222264536503273789013798395884104790217898195008843408149451748239377299652426931967019223980259457768048183972055991854928660562680316115848049030120068763050175827932483663365464482727317050056562889546636425655657765772098105202889353529152305437946280810771045676951442322243838
    p, q = fermat(n)
    d = pow(e, -1, (p-1)*(q-1))
    m = pow(ct, d, n)
    return long_to_bytes(int(m))


def main():
    p1 = part_1()
    p2 = part_2()
    print(p1 + p2)


if __name__ == "__main__":
    main()
    
#b'cvctf{Hensel_Takagi_Lifting,but_Fermat_is_better?}'

RSA 3

CRT attack but there is 1/10 chance we get a bad value, so collect more than you need
then zip the lists and use random.sample

from pwn import remote, process
from sympy.ntheory.modular import crt
from gmpy2 import iroot
from random import sample
from Crypto.Util.number import long_to_bytes

def get_values():
    n_list = []
    c_list = []
    while len(n_list) < 30:
        #io = process("./server.py")
        io = remote("137.184.215.151", 22629)
        n = int(io.readline().split()[-1])
        e = int(io.readline().split()[-1])
        c = int(io.readline().split()[-1])
        io.close()
        if e == 17:
            n_list.append(n)
            c_list.append(c)
            print(len(n_list))
    return n_list, c_list

def main():
    n_list, c_list = get_values()
    for _ in range(1000):
        x = list(zip(n_list, c_list))
        ns = []
        cs = []
        for a, b in sample(x, 17):
            ns.append(a)
            cs.append(b)
        flag = iroot(crt(ns, cs)[0], 17)[0]
        flag = long_to_bytes(flag)
        if b"ctf" in flag:
            print(flag)

def crt_test():
    m = 999999999999999999999999999999999999999
    e = 3
    from Crypto.Util.number import getPrime
    ns = [getPrime(100)*getPrime(100) for _ in range(e)]
    cs = [pow(m, e, n) for n in ns]
    print(m == iroot(crt(ns, cs)[0], e)[0])

if __name__ == "__main__":
    main()

#b'cvctf{Hastad_with_e=65537_might_be_slow}'

CyberMania

I got this piece of ciphertext from my friend who is a Cyber Mania. It must have hidden something…

NDAgNmIgNzEgNmEgNjkgM2EgMzIgM2QgNDIgM2YgM2QgNzUgMjcgNjIgNmEgM2QgNWQgNjUgMmQgNWMgM2MgNjMgMjggM2IgNzMgM2MgNDEgNDkgNWQgMzUgM2IgNDQgNTcgMzggNzAgM2IgMmYgNDMgMjYgNDIgM2EgMzAgMjggMmMgMmEgNDAgM2IgNTMgNGEgNTYgM2MgMjkgNmQgNTUgMzYgM2EgMmMgMmMgMzQgMmQgNDAgMzkgM2YgMjEgNDAgM2MgNWYgMmMgNzQgNjEgNDEgMzQgNGIgNWIgMjQgM2UgMjMgNjYgNGUgM2IgNDAgNmIgNzAgMjIgNzUgM2QgNWYgNjcgNjAgNTcgM2QgNjEgNDYgNTUgNGIgNDEgMzggNTEgMjEgNmUgM2IgNjUgNmYgNTEgMjkgM2QgMjUgNDcgNzIgMjggNDAgMzcgMzMgNTMgMjMgM2QgMjUgM2YgNzEgMjEgM2EgMmUgNGIgMzQgNTggNDEgMzggMzQgNTMgNDkgM2QgNWQgNDAgNmEgNjkgM2MgMjggNGIgNmUgNjYgM2EgMmUgNDkgMzAgM2QgMzkgNjkgNTkgNWYgM2YgM2MgNjAgNGYgMmEgNjAgM2MgMmEgMjkgNWIgNjMgNDEgMzggNGYgNjUgMzUgMzkgNjkgNTAgMmUgNWUgM2IgNjYgMmIgNGYgM2MgM2EgNDkgNjYgMzUgM2EgMzkgNmQgNTQgNjUgNmUgM2QgNWQgNTQgNGEgNzEgM2MgMjkgNjQgMjQgNjYgM2QgMjkgNGMgNTcgNGUgNDAgNmYgNzUgMzMgNDggM2QgNTkgNGYgNDEgNjcgNDAgM2MgNzQgNGYgNWMgM2EgMmUgMzcgNjAgMzAgM2IgNjYgMjMgNDcgNjYgM2QgMjUgMjQgNTAgNDUgM2QgNzQgNjkgNTEgNDQgM2MgMjggMzkgNjIgM2YgM2UgMjYgMzggMmUgMzUgM2MgNDMgNDMgMjIgNDcgM2IgNGEgNWQgMzYgNGMgM2UgMjIgM2EgNDcgNGMgM2IgNDggM2YgMzcgNjggM2IgMmYgNGEgNmMgNWEgM2IgNjUgNjYgNGIgNTkgM2EgNDkgNjQgNmMgNmEgM2QgMjcgMjUgNDMgNzUgM2IgNDYgNDYgMmQgMjMgM2MgNDUgNDMgNmUgNmIgM2MgNDUgMzQgMzUgNzMgM2QgMjYgNjEgMjEgM2QgM2IgNDggMzUgNTMgNjcgNDAgMzkgNDAgMjYgNWMgMzkgNjYgMjQgNjAgNWIgM2QgNWQgNTIgNzQgM2IgNDAgNmYgNmMgMzkgNDMgNDEgNGYgNGIgMjEgNTMgM2MgMmEgMzIgNjEgNWUgNDAgMzcgM2MgNjUgMjUgNDAgNTQgNDggNGUgMzEgM2EgMzIgNDYgNjAgNGIgM2UgMjMgNjUgMzAgNmUgM2MgMjggMjcgNGEgNzUgM2MgNWYgMmMgNTEgMjIgNDAgNzIgMjIgNTggNmUgM2IgMmQgMjUgNGMgMjYgMzkgNjkgNTAgNzEgMjggNDAgM2IgMzkgM2QgNTYgM2MgMjkgNjQgNWIgNGUgNDEgNGYgNGIgMzkgNjAgM2QgNWYgNzAgNTAgNWQgNDEgNTMgNmEgMmIgNTcgM2QgNzQgNzMgMzMgMjQgM2UgMjYgNGEgMmIgMzMgM2MgNjAgNjkgMmIgMzIgNDAgMzcgNGUgNjQgNDYgM2IgNDQgNDMgNTggM2QgM2IgMmYgNDMgMjMgNmYgM2IgNWYgNTYgMmEgNjMgM2MgNWUgNzAgMjggNDYgNDAgNmYgNWEgNDUgMmYgNDAgNTAgNWYgNzMgNTggNDAgNTQgNWEgNjIgNjUgM2QgMjkgMjkgNTAgNmMgNDEgMzggM2QgNjUgMjggNDEgMzYgM2MgNGQgMzMgNDAgMzcgNGYgNzMgNTQgNDEgNGYgNmYgNTEgNTAgNDEgMzkgNTUgMzEgMjI

Base64 -> hex -> base85 -> base64 -> base58 -> https://cryptoji.com

cvctf{3m0j1_c4n_L34K_7h1ng5}

Big Rabin

\[c \equiv m^2 \ (mod \ n)\]

We need to find the square root mod n.

I modified sympy’s sqrt_mod_iter function from https://github.com/sympy/sympy/blob/master/sympy/ntheory/residue_ntheory.py

from Crypto.Util.number import long_to_bytes
from sympy.ntheory.residue_ntheory import _sqrt_mod_prime_power, _product, _sqrt_mod1
from sympy.polys.galoistools import gf_crt1, gf_crt2
from sympy.polys.domains import ZZ


def sqrt_mod_iter(a, f):
    v = []
    pv = []
    for px, ex in f.items():
        if a % px == 0:
            rx = _sqrt_mod1(a, px, ex)
            if not rx:
                return
        else:
            rx = _sqrt_mod_prime_power(a, px, ex)
            if not rx:
                return
        v.append(rx)
        pv.append(px**ex)
    mm, e, s = gf_crt1(pv, ZZ)
    for vx in _product(*v):
        r = gf_crt2(vx, pv, mm, e, s, ZZ)
        yield r
    else:
        for vx in _product(*v):
            r = gf_crt2(vx, pv, mm, e, s, ZZ)
            yield r


primes = [132226521510073241868478441993015354148527265070844601764638529221288504976410393924935295341036464167430758516679806086101355913069828507720078706111518764763860261405919471828890271375290465307125060869008747651304555905840414020300749769085263330846399185059492965396066022852144378645140305287757847727023, 166975174848900885230261330388360938761353252820281468924803320138144055905644086619356255132048410411366729267993937675260638228144755335215429145353099164053352619775669398053052968467143600192845905417256960156392197454820487653509257937973672298884564792967995269332679341948473655565516611128690668584197, 142872473239232009830855192451471368852668441691782565721008089294877340422457402592626252955869775729973997252931251666144198844354316321876779014522642204671232774572604583775513634884566978553917344483379779100930174962243024555704822801010773572545801848379806701640868474072068588187164478666117032536743, 130892261245352215748569386846911862074603359546553143534975947107064714450388455394151437883146319257061620436858323988107585895908396306525917087044899379090234252879747887675884686106229697448906503338648983178690152813231281939068998489985753607854487974314966395013411365168104897566924065151568253685389, 145551848922783998528416786343973572472474320126254044570241048099740111725992313257532536785462269965641550642274572312923944315477621869191221368417595336738285091021747216596626016115302578007940230744568897790622831057456985073420219248560391242735855176398817027832854071167392464605267378738681409692207, 109114236141132256858265781393324161877680502794260375634936389144130052076205935445884813005428724784271974614143303830651751053233628886067941762333164941597521613761267981323595507523576850094910118775698465333491285382926211396415210206640863838245229759501252816392805326580130465854590783194264915510107, 149012332254098169883676747964911319691822361308399858421962733809406243673749451302379098919202789878055459506619587309704672105656774201994079016346228841284249488225321663757366441960504330961474614423041525751882565821073188367282242863442968249947378755695090610366079747622976283329590239856372835372077, 89933039054622081733083753412036389257663070424046675225077590968264124467545748005665094466078872143690347802061705503577114736109829239359006199434519375691332381519569498638696542565602083683732367191126621738256117168725047465248935955872366458549695968621135516743160437309215563157049376939290044627313, 144740324082556719196755949987638484388687025029996662925584432266650207893213563830207448527247219434052744033623084777776494559920370369824340095295242250589124486762879342972124012161218261244077906297847144914260263449001263793071999861655844579640626513700692813426335252087586488036788977420619650395281, 177890920322792684381488228351207885958275622324411726844780096159974211995797980616696403624147387087872691406579164096185188544912293856215282348681231390887966279317515097280087518605104367297949995780275322107787760838983798771894346399852645638599662743887567463532610893557114956013160076360765011538011]
c = 22946885822002467171903084240416288222260709393342086666614067405740711654751859628586773085727309553476558484713992238684106955555407130896914013459177345438724868201174752650162646056513628813995822388584081951435555201995181471800953753065805537239004801790261801117451703491741695068405051052528468868702342710290967199025172882590726554624329641303992754921465060035494584473179143361525585375327174333664171595698051318950929679219084654514302582298457923944861686107213448365614170278678031637593258899000503650392461910041826689785746033611685952405642342168822481363285927108889621327497879411676118996705939126347323933488709432561266681241083588173377314801049718139453233426105928769665280701332464661007393707855685695381234000934601768404436981039966731154784057035002881385480733918721892505780861028743718627723983889337589245505471761609164355615583667187016246477658779583361278419641451588063893642706807003172297981383003084552004900791931139372946360714784486527322818344413194151333823878001862478897096198700081692897370151996011935154686270934438172865531978260775218635723194626200021562057411503822135701039014960850609050136539744310043850114618082256447659795677305772357979166562438839947373438799197847335503006808051165456399906449288192895712634565545914245083072956245576112332273453809567266070539909722697964638524279759280287013618910074497709507375042069373384981213251042198281
for r in sqrt_mod_iter(c, {p: 1 for p in primes}):
    flag = long_to_bytes(r)
    if b"ctf" in flag:
        print(flag)
# cvctf{r4b1n_Cryp70_K1nd4_c0mpL1C4t3d?}

ECC Quiz

Part 1:

Enter your choice: 1
Curve parameters:
p = 9293
a = 976
b = 2885
Point P: (8869, 3369)
Find the point Q = 6706P. The answer is in the form of (x,y):

p = 9293
a = 976
b = 2885
E = EllipticCurve(GF(p), [a, b])
P = E(8869, 3369)
Q = 6706*P
print(f"({Q.xy()[0]},{Q.xy()[1]})")

Part 2:

Enter your choice: 2
Curve parameters:
p = 51433739202998053371220980685899663686280260752622112821669119317780679706624105902737376950306118102714990107549978198586233629706211643268882352119938666900786950922694032708284072581149
Point M on the curve: (3773631355522095828049848024374040952359513528706052228416156111287866491030871899493905746868421630428498982265084580134266241917045228020118561297678525780040400661760202904826506385678,7941442579149750056586648318658051940950124351423297986426033291518044583061009359070890812298600321472668998381895956066265203298741742520944086107846957235469749682254431787795861830698)
Point N on the curve: (5516437461613914252116160545833589250643734791657183529805939601176853698861675342403778121445976378724749734519959117438109824680099280370201136021200586061141221629170090591334576068124,34696767797496710943159378541572468373258908718165744192776006781739846504005210477408644086113337788116690782947162982770155868753110592698978643291536099039367321089515333143959373751286)
Find the curve parameters a and b. The answer is in the form of (a,b):

\[(y_1)^2 = (x_1)^3+a(x_1)+b\] \[(y_2)^2 = (x_2)^3+a(x_2)+b\]

y1 = 7941442579149750056586648318658051940950124351423297986426033291518044583061009359070890812298600321472668998381895956066265203298741742520944086107846957235469749682254431787795861830698
y2 = 34696767797496710943159378541572468373258908718165744192776006781739846504005210477408644086113337788116690782947162982770155868753110592698978643291536099039367321089515333143959373751286
x1 = 3773631355522095828049848024374040952359513528706052228416156111287866491030871899493905746868421630428498982265084580134266241917045228020118561297678525780040400661760202904826506385678
x2 = 5516437461613914252116160545833589250643734791657183529805939601176853698861675342403778121445976378724749734519959117438109824680099280370201136021200586061141221629170090591334576068124
p = 51433739202998053371220980685899663686280260752622112821669119317780679706624105902737376950306118102714990107549978198586233629706211643268882352119938666900786950922694032708284072581149

def resultant(f1, f2, var):
    from sage.matrix.matrix2 import Matrix
    return Matrix.determinant(f1.sylvester_matrix(f2, var))

R.<a, b> = PolynomialRing(GF(p))
f = x1^3 + a*x1 + b - y1^2
g = x2^3 + a*x2 + b - y2^2
_a = resultant(f, g, b).univariate_polynomial().roots()[0][0]
_b = resultant(f, g, a).univariate_polynomial().roots()[0][0]

print(f"({_a},{_b})")

Part 3:

Enter your choice: 3
Curve parameters:
p = 990797363000349360431762242217
a = 433943439817203561550709271692
b = 590324040643133056390189897982
P = (929180207154324494894848490687, 457008628012031640052195736567)
Q = uP = (380095452486555009157692387257, 371989668605415913052456359025)
Find the scalar u. The answer is a single integer:

p = 990797363000349360431762242217
a = 433943439817203561550709271692
b = 590324040643133056390189897982
E = EllipticCurve(GF(p), [a,b])
P = E(929180207154324494894848490687, 457008628012031640052195736567)
Q = E(380095452486555009157692387257, 371989668605415913052456359025)

u = P.discrete_log(Q)
print(u)

cvctf{ECC_is_411_y0u_n33d_t0_kn0w...And_CryptoHack_15_4w3s0m3!}

1337

Systems of equations can be solved with Groebner basis

from Crypto.Util.number import long_to_bytes

p = 231609284865232306744388160907453774453
PR.<w,x,y,z> = PolynomialRing(Zmod(p), 4)

f1 = x^1+y^3+z^3+w^7 - 213929627434382339098735177055751649916
f2 = y^1+z^3+w^3+x^7 - 19199104003461693263250446715340616788
f3 = z^1+w^3+x^3+y^7 - 81305572597778258494448971196865605263
f4 = w^1+x^3+y^3+z^7 - 204055349607012377951682156574173649079
f5 = x+y+z+w - 2268211308285612387872477045295901103

ww, xx, yy, zz = Ideal([f1, f2, f3, f4, f5]).groebner_basis()

w = p - (ww - w)
x = p - (xx - x)
y = p - (yy - y)
z = p - (zz - z)

flag = b""
for i in (x, y, z, w):
    flag += long_to_bytes(int(i))
print(flag)
#cvctf{this chall is for another CTF but it was cancelled :(}

Weird dlog

\[\text{We have } n = p^2 \cdot q \text{ and } c \equiv g^m \ (mod \ n)\]

Note the challenge uses the variable ‘m’ for the ciphertext
but I will use m for flag and c for ciphertext.

First we should factor n, because p and q are close together.

\[\text{Let } ap = n^\frac{1}{3}\] \[\text{Let } p = ap + x\]

Then use Coppersmith’s method:

from gmpy2 import iroot

n = 10941888529432710302272044808172366177817083267353728387778251966266072287607755644721338043351870432706497693313492403987246128369454049222700884094312120262698229189208223218732275272981771624419914106314134685967783268356547329406040929859316975902966386276320517786973713050654580905181729305020144204934138012268416005803949005810888621349553556279807338189673928133725107444318753299258813428869755492871371365509253274275507785302703028229706104025231495516828413453372697736689315270600144033367988185883751955533145131820299821036099425033741978037404521469840343451728996005273312522454265432166678945758946508086710070492821787815923425038513533610548985733666276895713644320042830406173577168099532687994444950160159745610177551080984478286003952657902953582221120083238221655231826293209922243103643973158229947410799996443039134812980230923730059957532891088920291921544489491437892953022797147371056895427933338596342279801238281297736043937512612367418666450917035364442328787819461040287010570790023067874699031894369374666073884261229547448186848837461040401572755725068306333093138881471721393682218994576974011413807781411295540237225784367274045480384276599164320452991405168935726178669
ap = int(iroot(n, 3)[0])
PR.<x> = PolynomialRing(Zmod(n))
f = ap + x
x = f.small_roots(beta=0.2)[0]
p = int(f(x))
assert is_prime(p)
print(f"p = {p}")
# p = 2220056847922888806692961201204181494180468404265144656979415727846610609650612145504228170996668036830178564363339729040733053444504290404813978909079947107025031382736413106168755521395169078323433549912352350586785691382035545583930303726697079796565769117602611817953388750640643945286203371871152311393277382213336946213995315438785489971755082168989679975255419041436378409691325787848675432435671

Now that we have p, this writeup was helpful for decrypting:

https://jsur.in/posts/2020-08-09-poseidonctf-2020-writeups#discrete-log

from Crypto.Util.number import long_to_bytes

g = 4217104162231108571881486363264502722577265670533700464292447122725884060865278499273749984084307890296655750169737247120115556105852793495207776085190125693574834744150776071626953537124287733539294768576947214664831668249537361880607900415980188224790377848428124695064324868240382228326860781143717838988468681317873292597463247890454032395659378742623078198171614526987958808613568346779857292295096270767472963769637419908101399359189794634298434235861743414985078720538901239212554829307311050121532457033249775247040962157091404814597818322567791804549931512078619168741053536240553838132062889112375399237994189289540471931223835109201969517169907064471393467949637030171468739827679615037096191102556235525038398343624846458755117043899170432849676184565935742212246568515988089821245576219250167380483425498097448081250808144546318744227429556017907249040862683999049166654695785359522913386597444234975046933660020802696704230400762773828356573597488744036818115263470798266879540313464252075039418721353291327500707724679404373330401143441889215673146351039551079579127929035980199349135110483207097742313251638620757710743549095431313120163844541459241899262156308740654917968060844284412082299
n = 10941888529432710302272044808172366177817083267353728387778251966266072287607755644721338043351870432706497693313492403987246128369454049222700884094312120262698229189208223218732275272981771624419914106314134685967783268356547329406040929859316975902966386276320517786973713050654580905181729305020144204934138012268416005803949005810888621349553556279807338189673928133725107444318753299258813428869755492871371365509253274275507785302703028229706104025231495516828413453372697736689315270600144033367988185883751955533145131820299821036099425033741978037404521469840343451728996005273312522454265432166678945758946508086710070492821787815923425038513533610548985733666276895713644320042830406173577168099532687994444950160159745610177551080984478286003952657902953582221120083238221655231826293209922243103643973158229947410799996443039134812980230923730059957532891088920291921544489491437892953022797147371056895427933338596342279801238281297736043937512612367418666450917035364442328787819461040287010570790023067874699031894369374666073884261229547448186848837461040401572755725068306333093138881471721393682218994576974011413807781411295540237225784367274045480384276599164320452991405168935726178669
c = 4576653037171661542042510858542458890428902270240861216961609304805830644888835861552943484827465024255946333173438385318547946480432546672274379127945737050221711664915718037389483818788255371177342813451318183796063859501483853616124820170927827054719451326957465962519367227753007179628370407849940782754428678471956932743015842138996456351682565775528904950367274203264025982858945560085867807654673726775851728189907590054081432299552285929407918297497972515287529506153936873120705301250301755547851988767682706931104344998515759782906834209711055747621306735557847407025512085632112612715677993856157667539100717815505576125450494688023610882544096421409195218600313621491935755995519193153556491442386466162185336840903547990417011020008723119132837593921370224096091218428827263318876330392141114596260431968349229888104149062981625468823935145842920387345948673405002062554960084883553497321014737635984993337888457310522533554029754162393609118195463217899952617045335297738291366080224287861881668432617054485772999546446076931624127877484962146375663168327918511556849268478695380248447621861402820926977211453653005530269636900365390125831754366239971553991824331582315041274983141065725144997
p = 2220056847922888806692961201204181494180468404265144656979415727846610609650612145504228170996668036830178564363339729040733053444504290404813978909079947107025031382736413106168755521395169078323433549912352350586785691382035545583930303726697079796565769117602611817953388750640643945286203371871152311393277382213336946213995315438785489971755082168989679975255419041436378409691325787848675432435671

a = (pow(c, p-1, p**2) - 1)//p
b = (pow(g, p-1, p**2) - 1)//p
b_ = pow(b, -1, p)
m = a*b_ % p
print(long_to_bytes(m))
#b'cvctf{Tatsuaki_Shigenori_uncommon_cryptosystem}'

A Tale of Two Systems

I couldn’t solve it, check out https://kevinliu.me/posts/cryptoverse