This was an interesting challenge. Some of the other crypto challenges were copies of previous CTF tasks, not sure if this one was too, but I hadn't see it before.

crypto
- elgaml_rsa

elgaml_rsa

crypto

#!/usr/bin/env python
# coding=utf-8
from Crypto.Util.number import *
from gmpy2 import *
from binascii import *
from key import secret


size = 4096
next_state = getRandomInteger(size // 2)


def keygen(size):
    q = getPrime(size)
    k = 2
    while True:
        p = q * k + 1
        if isPrime(p):
        	break
        k += 1
    g = 2
    while True:
        if pow(g, q, p) == 1:
            break
        g += 1
    A = getRandomInteger(size) % q
    B = getRandomInteger(size) % q
    d = getRandomInteger(size) % q
    h = pow(g, d, p)
    return (g, h, A, B, p, q), (d,)


def rand(A, B, M):
    global next_state
    next_state, ret = (B * next_state + A) % M, next_state
    return ret


def enc(pubkey, m):
    g, h, A, B, p, q = pubkey
    assert 0 < m <= p
    r = rand(A, B, q)
    c1 = pow(g, r, p)
    c2 = (m * pow(h, r, p)) % p
    return (c1, c2)


pubkey, privkey = keygen(size)

c1, c2 = enc(pubkey, secret)
c11, c22 = enc(pubkey, secret)

print(pubkey)
print(c1, c2)
print(c11, c22)

with open('flag','rb') as f:
    flag = f.read().strip(b'gactf{').strip(b'}')

assert(len(flag)==36)
flag = bytes_to_long(flag)

e=0x1296
c = pow(flag,e,secret)
print(c)



'''
(64, 20780474293866131933862287255555455030374045530251095666369283432462810652525427691721304254462237017759426334882916049495889504594009770520464330762959016951546575145462307317894496460531556164410953148497518290028088712258668119908424719634615388291047264345913823034842970773368033086339559642636137744915369016200318607505245388543117271999254001335968170458213311497321117529280041082988824396151908188525489700796405858374530511663128135580173535828610757421885017756967359800260945101629391819567689637211651895850980281588310001703030835140810350079586117727295930982227960023008919855063362680952572131899713036162496210570179135414385493625653887326331804734492999669859178883625968923995256089541092732093557828711090165978111405804292224573421621191633338981450285157302862932940500093263243947199483627384074436212584903719549495723188986249991756615160063402163694830775734815955316835349073419639199758694671594404540029322234383581399522064379382021595719397223893607631901725607641744479242212920789603071407011348514876465946739422799404447033886982709934951857043468867599886808040297253407019293845393488573199993494540736979501538494818953066676387396633085444166742111351272947318154970048596923974504404380927416,381708384013002636433122354335926692336601617676926968898013795392655866091031994182231300776082068899737198812550890687137401508001940273120074129003646740029985994207331055782501249765461466584992023925230840665949906632198101999859500790212575156806509743006505701713970313218378023375414073482678391588622628187074299412433043817050683291933161425628794715547714403106509123476151979947917391393412645765122604354225100743870995206588381507456741290978603333889874930706693482317045587451791046190740066378574507676759649633128467597518860457862695484980816243465255252173136325137506270232696551053565764269904166529146681242149565805411556997705869017810058040591799368604689685951672647151912084757145775011455841321798009615242210532962596268560546312347194505828381287458597164561168495886248727096685588006006546480425238352362436971564880004651450568881978647634212713224047524921068489089978106015561713311517385843649234918915312918406300092887256427518081655040845694063162361305181653495296888548335581623440628369113672677762811628569895443681117805669311418808453448653593363449729346566117394039637974118545192223391804824330785203598209547944921552416944717704983567183156966157476160974179852872170934972858836781, 43505603305111680803563977459640944464105385282379422421980575558368972842607765670721003089672603097313103981235686237397257862849601241879471167930153646225844008471355704339980238211134686502225715019115869317427197390964362320090838527730898664248447107765413761830863605920486819969055546423684508389628123987801815335523239425432391765479775424040215970484578304273140784182204718527220185459004052198324217205275587873438839100176140844478555649819782992169483866083330097141949046245149094504794723574282964767779251414958958706784791732572996736294885028909774443354205765706938344147696599409331866916073619245974602504186911091638010576094381687164075770345437007237017511597686483438791354205795335973602676663054120116592544019595778273459615865899404356938805021081374452052068221554454819002242766042331745787877501397324349289129890310340865730592151597455837880210622067528365150318411999840330958344868422035016628605636595819056821789774656720527976088720077220560311329066034711257025398105457680968934892169828204426383391000448054370375803473806685234956611656904127231542272618726532676811311523606477787525194092155173656104677312540399404023913503117830278920886909662890420006539377593361467113937140744010, 45546439253566873046135178791096659917209492861617458211267719798885277887938347304820298843145674472870766332758636279557209016031713547700909688953215131457341421729182912313815167760908611069679571547056188204597788444236869052385801746036327394329618747230203387842029040907229766131476048451293016635093208306323063715706067371953108251630052089462662417303475933291290566336468462586635807978767551023772175046232601222877403596811965579296677734661047163959600195727625890255130528298615338776353196525781432396712546801275867984255488198557346322961570926619651871594687507639988384211396556450312496725130292814328927584109530411297121292814256252280901057553636074873996093840854880090055633725117055959590322998817024919326703993851904085347843055734589470195083739394356572346483715507513378038693666480211356659114879422949481825838585239350398353217171146754711645184363669060413784452297408480588454177322580570407385734077514306779834329286166444213819533159384145482066266175499414964502711323195573855494716545548783117249211738964334485427936770661680033789944683657229394946749668495670252890519005455449387321211576562318106342614124875224420621771672914794854566658369446093868181072056414942873885989261187792529, 948884151115976521794482891481180414941864434617030379401410829143443289332048902183756225898868218184807631932471589157441854500660698910435618519858648572027946286024644006537815995018929397284991073897003920929120592588268105258037536375756820715200390567295903913375605018900620127739084342735271179897775173048397160743876403582356421908959418530472133693822415276901886798676426303888245999557657312995253646796512525476612574933582616235347452805438482582491670744325539380315219339554486224507358260953779841598178058359913916338656004136611381728366060971242747324889323075833091337737428259381510348440214433631852658002281883568690026933630338589185438699034084893208251955017810001876159035939938665824798395808688019152639666538581335111413396994470613962397577904049095257218410739739862042472784718337736597064893321311447538038303859153133299025357732224056492608007576438758620509422862676678926128694220428550153869459948214724579881860128467587787906940820503030876380545322904478427139819233241121989473261365599648276025244561756968446415349388785000703957180909525612394723951426993130268552479280321862235858574511714960548804460934900508762953576519058226136805382696793622253772334508644643205958109608079011)
22453152428394606088943774662302202422153960447312197242455569997061450760047528966506441566524526853033293751967810594140854923226151650938525170137514600880805050554663943082815906368514404641025604294366860158614875990137728517294116316762556975898260341247898716976970617032432937955286668439404344848291545559658276642393602228734034612184252718870517184522197911024934717798077233461582581868193787894582258952888627951734023431879183670191669298358680498935709882003781077406338523907367346789138656618116933889244879390502610424899510803955442942977900239324993614041517202681723278532043123236878326249862092754098907790488065071040929376826057117979467292302080257950897426644056280125378364535680687786693270799850067554410612758531513629387059863596252391870417805469348504325636998643613777442875034648277326137337187208698790044216186340918785533348914782916443684223939292156374009910727628455699988827744627946732973050302225074511302818542457166115156873282388208050368257145196360795205915922021436321478999333704296935314435099278218817835181668673690398237608806925783268658459276024403522197373931280630406781239277149660631726005650281230352429449777583372994535668183455158366753076284188469366650872129189188954 43014070623103292976184689427105928199147965783937089428385491282216272444365283117905989848749181365267234218854446028762485581571306912831438529312945584194862759018753822869158358589009967858962779001877279323670583250081922847895176784620706892400531521013763514799201763745183044164104035196613753228089053191247345267210940633115873824974769014722055077799856934880737833185923456222178802890352524448603177600618056088876614578821438861413350348617677694184716464398433385655237392506169213931196012955755770139080945778856434397878091389138231179032165240858902248596578661346637175321979963481071276143651366658999282369341715121067180208904222607402081278785172060423774990737421479393799816962905617768730613118540383524977589624740822007170019678257890472150388700140797012249510238048211606905864478903986719042623036582247378794747826919609810170285750234710357000132728486804956251659199729624366338890451927509641664833932346738489065555140914795441664133418400958836523237094378780782603370403266584597230077617701944349882551595000276212025361451916984278427199657858078227972152325611502177407278626854076690433960994875505694991760829975244773421088756265358618620304273856739824192560105567929686528910876014823965
44608013650780329531109538179331822570135966195550223402070161598185644434770862399901412649297405576993241936895024146617797344461666950233511185666728221978895618296351596298775136672055923289389665757911807359016802923641460730946632818202168872788458468347348232090434225957209352582129271299425216944747679759179672053700778261669489727413942176315455298932909861450580984970798585428405552956293406458215448336032446056582649917889593692072954837453042473056600004374540260728744840291557410530843899434261407426178111249646964369037637633211541371271197280517635042592551789127833173333234479307397045400972018112295715569721800138429266922182854791647269058891183615748790947697069153882008589561211157334372972499729485252727694797282796590848738021218670314348696571534824112823542032680872158338607531482751162776081697861530593966973408267629391304447962348239015723944462941622104654613580650653767954875700171277625377411714660734830575428948037611098387735691682421457169239064406477687024462745934438832041378409566709345316139490973699111690159932212499398783638503401404235464154454535785113901174157533110165240552563496872266944710590644159214078372821774380931384935459500471791384494332187743455497646590556880486 1522687118053736861056969003430796399893176012103287854193029873658554858136827462259124651478772173757025568892302195402291455992394789178299309535616987072965579421593018021114875919558287237186455725647948113582053830294196737121722225985979525758513270467145143657376879463222508333678601013048368285045304095162002671773027175721352146624828522742775630450642598352531401961139587698492307980703004014415044157520489051036928610329089210652248586776563084702121754645966572787310495034532000331181441756647075157708515223727039422012212657926685677978199476498472278242756713492597894691133614639186351240949930682742853869969584053534079567976916119132941681011705563769739500572388748003030282448776889448778821320406706124477759144963675421171984971802471706213665007068221227826503520100160877838988068439450319825803900962680452544694163391017757486433728437439479064627991529036015041631361993854848621812502254104495342939127025063439806000291665982509626369261288950954463853496165866013918850578916279480441428849258614763017063059042143901251569352672219853411840562939930258505979216301725869416361119563043278577212326582324332541993877436871165282813371607548756276989941992463786598573454058633853167962827467271628
255310806360822158306697936064463902328816816156848194779397173946813224291656351345682266227949792774097276485816149202739762582969208376195999403112665514848825884325279574067341653685838880693150001066940379902609411551128810484902428845412055387955258568610350610226605230048821754213270699317153844590496606931431733319116866235538921198147193538906156906954406577796507390570080177313707462469835954564824944706687157852157673146976402325057144745208116022973614795377968986322754779469798013426261911408914756488145211933799442123449261969392169406969410065018032795960230701484816708147958190769470879211953704222809883281592308316942052671516609231501663363123562942
'''

Solution

Part 1: ElGamal and the Broken RNG

The script encrypts secret twice using the probabilistic ElGamal encryption. The random value r in the ElGamal encryption is generated from a LCG which is easily broken. Having two encryptions of the same message is enough for us to recover the message completely. This will be the first part of the challenge.

Let $r_1$ and $r_2$ be the random values used in the first and second ElGamal encryption. $r_1$ is some securely generated random value, and $r_2 \equiv Br_1 + A \pmod q$ is generated from the LCG. We are given $(c_1, c_2)$ and $(c_{11}, c_{22})$ where

\begin{aligned} c_1 &\equiv g^{r_1} \pmod p \\ c_2 &\equiv mh^{r_1} \pmod p \\ c_{11} &\equiv g^{r_2} \equiv g^{Br_1 + A \mod q} \pmod p \\ c_{22} &\equiv mh^{r_2} \equiv mh^{Br_1 + A \mod q} \pmod p \end{aligned}

Notice that

\begin{aligned} c_{22} &\equiv mh^{Br_1 + A} \\ &\equiv m(h^{r_1})^B h^A \\ &\equiv (mh^{r_1})(h^{r_1})^{B-1} h^A \\ &\equiv c_2 (h^{r_i})^{B-1} h^A \pmod p \end{aligned}

Therefore

h^{r_i} \equiv (c_{22} c_2^{-1} h^{-A})^{B'} \pmod p

where $B' \equiv (B-1)^{-1} \pmod {p-1}$ .

Then, we can recover $m$ by computing

m \equiv c_2 (h^{r_1})^{-1} \pmod p

This gives us the secret modulus:

N = 42044128297^6 * 232087313537^5 * 653551912583^15 * 28079229001363^14 * 104280142799213^6 * 802576647765917^7

Part 2: RSA and the Non-Coprime $e$ and $\varphi(N)$

We've now recovered the secret modulus, and luckily for us, it's easily factored! All that's left is to decrypt the (almost) textbook RSA...

Except there's a slight issue! e = 4758 is even, and in fact, e divides phi(N). One of the first things we learn when studying RSA is that e and phi(N) need to be coprime for decryption to be possible, so is the challenge broken?

Clearly not. In fact this particular line of code gives us a hint as to how to proceed:

assert(len(flag)==36)

For clarity, write the modulus as

N = p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}

Then

\begin{aligned} c &\equiv m^e \pmod N \\ &\equiv m^e \pmod {p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}} \end{aligned}

This implies $c \equiv m^e \pmod {p_i^{k_i}}$ . This is quite easy to show (sketch):

Suppose $a \equiv b \pmod {pq}$ , then $a - b = kpq = (kp)q$ , so $a \equiv b \pmod q$ .

Since the flag is 36 bytes, we can solve for $m$ modulo some factor(s) of $N$ such that their product is greater than $2^{36\times 8}$ .

653551912583^15 works well here. Actually gcd(4758, phi(653551912583^15)) = 2, but it turns out that this doesn't cause much troubles for us because m^2 < 653551912583^15 (we'll see why this is soon enough).

So let $N = 653551912583^{15}$ . Then $\varphi(N) = 653551912583^{15} - 653551912583^{14}$ .

Let $g = \gcd(e, \varphi(N)) = 2$ and let $d \equiv (\frac{e}{g})^{-1} \pmod {\varphi(N)}$ .

$d$ exists since $\gcd(\frac{e}{g}, \varphi(N)) = 1$ . It follows that $d = \frac{g}{e} + k\varphi(N)$ for some integer $k$ .

Then

\begin{aligned} c^d &\equiv (m^e)^d \\ &\equiv (m^e)^{\frac{g}{e} + k\varphi(N)} \\ &\equiv m^g m ^{k\varphi(N)} \\ &\equiv m^g \pmod N \end{aligned}

But we know that $m^g = m^2 < N$ , so the congruence is actually an equality. Therefore, we can just take the integer square root to recover $m$ completely.

And we're done!

Solve Script

pubkey = (64, 20780474293866131933862287255555455030374045530251095666369283432462810652525427691721304254462237017759426334882916049495889504594009770520464330762959016951546575145462307317894496460531556164410953148497518290028088712258668119908424719634615388291047264345913823034842970773368033086339559642636137744915369016200318607505245388543117271999254001335968170458213311497321117529280041082988824396151908188525489700796405858374530511663128135580173535828610757421885017756967359800260945101629391819567689637211651895850980281588310001703030835140810350079586117727295930982227960023008919855063362680952572131899713036162496210570179135414385493625653887326331804734492999669859178883625968923995256089541092732093557828711090165978111405804292224573421621191633338981450285157302862932940500093263243947199483627384074436212584903719549495723188986249991756615160063402163694830775734815955316835349073419639199758694671594404540029322234383581399522064379382021595719397223893607631901725607641744479242212920789603071407011348514876465946739422799404447033886982709934951857043468867599886808040297253407019293845393488573199993494540736979501538494818953066676387396633085444166742111351272947318154970048596923974504404380927416,381708384013002636433122354335926692336601617676926968898013795392655866091031994182231300776082068899737198812550890687137401508001940273120074129003646740029985994207331055782501249765461466584992023925230840665949906632198101999859500790212575156806509743006505701713970313218378023375414073482678391588622628187074299412433043817050683291933161425628794715547714403106509123476151979947917391393412645765122604354225100743870995206588381507456741290978603333889874930706693482317045587451791046190740066378574507676759649633128467597518860457862695484980816243465255252173136325137506270232696551053565764269904166529146681242149565805411556997705869017810058040591799368604689685951672647151912084757145775011455841321798009615242210532962596268560546312347194505828381287458597164561168495886248727096685588006006546480425238352362436971564880004651450568881978647634212713224047524921068489089978106015561713311517385843649234918915312918406300092887256427518081655040845694063162361305181653495296888548335581623440628369113672677762811628569895443681117805669311418808453448653593363449729346566117394039637974118545192223391804824330785203598209547944921552416944717704983567183156966157476160974179852872170934972858836781, 43505603305111680803563977459640944464105385282379422421980575558368972842607765670721003089672603097313103981235686237397257862849601241879471167930153646225844008471355704339980238211134686502225715019115869317427197390964362320090838527730898664248447107765413761830863605920486819969055546423684508389628123987801815335523239425432391765479775424040215970484578304273140784182204718527220185459004052198324217205275587873438839100176140844478555649819782992169483866083330097141949046245149094504794723574282964767779251414958958706784791732572996736294885028909774443354205765706938344147696599409331866916073619245974602504186911091638010576094381687164075770345437007237017511597686483438791354205795335973602676663054120116592544019595778273459615865899404356938805021081374452052068221554454819002242766042331745787877501397324349289129890310340865730592151597455837880210622067528365150318411999840330958344868422035016628605636595819056821789774656720527976088720077220560311329066034711257025398105457680968934892169828204426383391000448054370375803473806685234956611656904127231542272618726532676811311523606477787525194092155173656104677312540399404023913503117830278920886909662890420006539377593361467113937140744010, 45546439253566873046135178791096659917209492861617458211267719798885277887938347304820298843145674472870766332758636279557209016031713547700909688953215131457341421729182912313815167760908611069679571547056188204597788444236869052385801746036327394329618747230203387842029040907229766131476048451293016635093208306323063715706067371953108251630052089462662417303475933291290566336468462586635807978767551023772175046232601222877403596811965579296677734661047163959600195727625890255130528298615338776353196525781432396712546801275867984255488198557346322961570926619651871594687507639988384211396556450312496725130292814328927584109530411297121292814256252280901057553636074873996093840854880090055633725117055959590322998817024919326703993851904085347843055734589470195083739394356572346483715507513378038693666480211356659114879422949481825838585239350398353217171146754711645184363669060413784452297408480588454177322580570407385734077514306779834329286166444213819533159384145482066266175499414964502711323195573855494716545548783117249211738964334485427936770661680033789944683657229394946749668495670252890519005455449387321211576562318106342614124875224420621771672914794854566658369446093868181072056414942873885989261187792529, 948884151115976521794482891481180414941864434617030379401410829143443289332048902183756225898868218184807631932471589157441854500660698910435618519858648572027946286024644006537815995018929397284991073897003920929120592588268105258037536375756820715200390567295903913375605018900620127739084342735271179897775173048397160743876403582356421908959418530472133693822415276901886798676426303888245999557657312995253646796512525476612574933582616235347452805438482582491670744325539380315219339554486224507358260953779841598178058359913916338656004136611381728366060971242747324889323075833091337737428259381510348440214433631852658002281883568690026933630338589185438699034084893208251955017810001876159035939938665824798395808688019152639666538581335111413396994470613962397577904049095257218410739739862042472784718337736597064893321311447538038303859153133299025357732224056492608007576438758620509422862676678926128694220428550153869459948214724579881860128467587787906940820503030876380545322904478427139819233241121989473261365599648276025244561756968446415349388785000703957180909525612394723951426993130268552479280321862235858574511714960548804460934900508762953576519058226136805382696793622253772334508644643205958109608079011)
c1, c2 = 22453152428394606088943774662302202422153960447312197242455569997061450760047528966506441566524526853033293751967810594140854923226151650938525170137514600880805050554663943082815906368514404641025604294366860158614875990137728517294116316762556975898260341247898716976970617032432937955286668439404344848291545559658276642393602228734034612184252718870517184522197911024934717798077233461582581868193787894582258952888627951734023431879183670191669298358680498935709882003781077406338523907367346789138656618116933889244879390502610424899510803955442942977900239324993614041517202681723278532043123236878326249862092754098907790488065071040929376826057117979467292302080257950897426644056280125378364535680687786693270799850067554410612758531513629387059863596252391870417805469348504325636998643613777442875034648277326137337187208698790044216186340918785533348914782916443684223939292156374009910727628455699988827744627946732973050302225074511302818542457166115156873282388208050368257145196360795205915922021436321478999333704296935314435099278218817835181668673690398237608806925783268658459276024403522197373931280630406781239277149660631726005650281230352429449777583372994535668183455158366753076284188469366650872129189188954, 43014070623103292976184689427105928199147965783937089428385491282216272444365283117905989848749181365267234218854446028762485581571306912831438529312945584194862759018753822869158358589009967858962779001877279323670583250081922847895176784620706892400531521013763514799201763745183044164104035196613753228089053191247345267210940633115873824974769014722055077799856934880737833185923456222178802890352524448603177600618056088876614578821438861413350348617677694184716464398433385655237392506169213931196012955755770139080945778856434397878091389138231179032165240858902248596578661346637175321979963481071276143651366658999282369341715121067180208904222607402081278785172060423774990737421479393799816962905617768730613118540383524977589624740822007170019678257890472150388700140797012249510238048211606905864478903986719042623036582247378794747826919609810170285750234710357000132728486804956251659199729624366338890451927509641664833932346738489065555140914795441664133418400958836523237094378780782603370403266584597230077617701944349882551595000276212025361451916984278427199657858078227972152325611502177407278626854076690433960994875505694991760829975244773421088756265358618620304273856739824192560105567929686528910876014823965
c11, c22 = 44608013650780329531109538179331822570135966195550223402070161598185644434770862399901412649297405576993241936895024146617797344461666950233511185666728221978895618296351596298775136672055923289389665757911807359016802923641460730946632818202168872788458468347348232090434225957209352582129271299425216944747679759179672053700778261669489727413942176315455298932909861450580984970798585428405552956293406458215448336032446056582649917889593692072954837453042473056600004374540260728744840291557410530843899434261407426178111249646964369037637633211541371271197280517635042592551789127833173333234479307397045400972018112295715569721800138429266922182854791647269058891183615748790947697069153882008589561211157334372972499729485252727694797282796590848738021218670314348696571534824112823542032680872158338607531482751162776081697861530593966973408267629391304447962348239015723944462941622104654613580650653767954875700171277625377411714660734830575428948037611098387735691682421457169239064406477687024462745934438832041378409566709345316139490973699111690159932212499398783638503401404235464154454535785113901174157533110165240552563496872266944710590644159214078372821774380931384935459500471791384494332187743455497646590556880486, 1522687118053736861056969003430796399893176012103287854193029873658554858136827462259124651478772173757025568892302195402291455992394789178299309535616987072965579421593018021114875919558287237186455725647948113582053830294196737121722225985979525758513270467145143657376879463222508333678601013048368285045304095162002671773027175721352146624828522742775630450642598352531401961139587698492307980703004014415044157520489051036928610329089210652248586776563084702121754645966572787310495034532000331181441756647075157708515223727039422012212657926685677978199476498472278242756713492597894691133614639186351240949930682742853869969584053534079567976916119132941681011705563769739500572388748003030282448776889448778821320406706124477759144963675421171984971802471706213665007068221227826503520100160877838988068439450319825803900962680452544694163391017757486433728437439479064627991529036015041631361993854848621812502254104495342939127025063439806000291665982509626369261288950954463853496165866013918850578916279480441428849258614763017063059042143901251569352672219853411840562939930258505979216301725869416361119563043278577212326582324332541993877436871165282813371607548756276989941992463786598573454058633853167962827467271628
c = 255310806360822158306697936064463902328816816156848194779397173946813224291656351345682266227949792774097276485816149202739762582969208376195999403112665514848825884325279574067341653685838880693150001066940379902609411551128810484902428845412055387955258568610350610226605230048821754213270699317153844590496606931431733319116866235538921198147193538906156906954406577796507390570080177313707462469835954564824944706687157852157673146976402325057144745208116022973614795377968986322754779469798013426261911408914756488145211933799442123449261969392169406969410065018032795960230701484816708147958190769470879211953704222809883281592308316942052671516609231501663363123562942
e = 0x1296

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

g, h, A, B, p, q = pubkey

hr1 = pow(c22 * invert(c2, p) * pow(h,-A, p), invert(B-1, p-1), p)
N = c2*invert(int(hr1), int(p)) % p

# fac = factor(N)
# print(fac)
fac = [(42044128297, 6), (232087313537, 5), (653551912583, 15), (28079229001363, 14), (104280142799213, 6), (802576647765917, 7)]
f,k = fac[2]
phi = f^k - f^(k-1)
g = gcd(e, phi)
d = inverse_mod(e//g, phi)
M = pow(c, d, f^k)
flag = iroot(int(M), g)[0]

print('gactf{' + long_to_bytes(flag).decode() + '}')