frozen cake (crypto,warmup)
oh your cake is frozen. please warm it up and get the first cake.
author: theoremoon
Pythonスクリプトと出力文が配布される。
from Crypto.Util.number import getPrime
import os
flag = os.getenv("FLAG", "FakeCTF{warmup_a_frozen_cake}")
m = int(flag.encode().hex(), 16)
p = getPrime(512)
q = getPrime(512)
n = p*q
print("n =", n)
print("a =", pow(m, p, n))
print("b =", pow(m, q, n))
print("c =", pow(m, n, n))
素数p,qと、その積n=pq、メッセージmとして次のa,b,cの出力が与えられている。
\(a=m^{p}\mod n\)
\(b=m^{q}\mod n\)
\(c=m^{n}\mod n\)
RSA暗号っぽい処理をしているが、eにp,q,nを使っているのでRSAの要件を満たしていないだろう。
RSAにおけるオイラーの定理を利用する。
\(m^{(p-1)(q-1)}\mod n=1\)
これを変形する。
\(m^{(pq-p-q+1)}\mod n=(m^{pq}/m^{p}/m^{q}*m)\mod n=(ca^{-1}b^{-1}m)\mod n=1\)
a^-1とb^-1はaとbのモジュラ逆数を計算すれば得られる。
この式は適当な整数のkを使って以下のように書ける。
\(ca^{-1}b^{-1}m-kn=1\)
この関係を満たすmとkは拡張ユークリッドの互除法を使って計算できるため、メッセージmが入手できる。
次のソルバーを書いた。
from Crypto.Util.number import inverse,bytes_to_long, long_to_bytes
n = 101205131618457490641888226172378900782027938652382007193297646066245321085334424928920128567827889452079884571045344711457176257019858157287424646000972526730522884040459357134430948940886663606586037466289300864147185085616790054121654786459639161527509024925015109654917697542322418538800304501255357308131
a = 38686943509950033726712042913718602015746270494794620817845630744834821038141855935687477445507431250618882887343417719366326751444481151632966047740583539454488232216388308299503129892656814962238386222995387787074530151173515835774172341113153924268653274210010830431617266231895651198976989796620254642528
b = 83977895709438322981595417453453058400465353471362634652936475655371158094363869813512319678334779139681172477729044378942906546785697439730712057649619691929500952253818768414839548038664187232924265128952392200845425064991075296143440829148415481807496095010301335416711112897000382336725454278461965303477
c = 21459707600930866066419234194792759634183685313775248277484460333960658047171300820279668556014320938220170794027117386852057041210320434076253459389230704653466300429747719579911728990434338588576613885658479123772761552010662234507298817973164062457755456249314287213795660922615911433075228241429771610549
abc = (c * inverse(a,n) * inverse(b,n))%n
def extgcd(_a, _b):
if _b:
_d, _y, _x = extgcd(_b, _a % _b)
_y -= (_a // _b)*_x
return _d, _x, _y
return _a, 1, 0
d,x,y = extgcd(n,abc)
print(long_to_bytes(y))
CakeCTF{oh_you_got_a_tepid_cake_sorry}
CakeGEAR (web,warmup)
Can you crack the login portal of CakeGEAR router?
author: ptr-yudai
usernameとpasswordを入力してログインできる。username:guest, password:guestでログインできるので試してみる。
配布されるソースコードはログインを行うindex.phpと上記の画面を表示させるadmin.phpがある。
admin.php<?php
session_start();
if (empty($_SESSION['login']) || $_SESSION['login'] !== true) {
header("Location: /index.php");
exit;
}
if ($_SESSION['admin'] === true) {
$mode = 'admin';
$flag = file_get_contents("/flag.txt");
} else {
$mode = 'guest';
$flag = "***** Access Denied *****";
}
?>
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>control panel - CAKEGEAR</title>
<style>table, td { margin: auto; border: 1px solid #000; }</style>
</head>
<body style="text-align: center;">
<h1>Router Control Panel</h1>
<table><tbody>
<tr><td><b>Status</b></td><td>UP</td></tr>
<tr><td><b>Router IP</b></td><td>192.168.1.1</td></tr>
<tr><td><b>Your IP</b></td><td>192.168.1.7</td></tr>
<tr><td><b>Access Mode</b></td><td><?= $mode ?></td></tr>
<tr><td><b>FLAG</b></td><td><?= $flag ?></td></tr>
</tbody></table>
</body>
</html>
admin.phpはadminのセッションがtrueのときにflagを表示、それ以外はAccess Denied。付け入る隙間はなさそうだ。
index.php<?php
session_start();
$_SESSION = array();
define('ADMIN_PASSWORD', 'f365691b6e7d8bc4e043ff1b75dc660708c1040e');
/* Router login API */
$req = @json_decode(file_get_contents("php://input"));
if (isset($req->username) && isset($req->password)) {
if ($req->username === 'godmode'
&& !in_array($_SERVER['REMOTE_ADDR'], ['127.0.0.1', '::1'])) {
/* Debug mode is not allowed from outside the router */
$req->username = 'nobody';
}
switch ($req->username) {
case 'godmode':
/* No password is required in god mode */
$_SESSION['login'] = true;
$_SESSION['admin'] = true;
break;
case 'admin':
/* Secret password is required in admin mode */
if (sha1($req->password) === ADMIN_PASSWORD) {
$_SESSION['login'] = true;
$_SESSION['admin'] = true;
}
break;
case 'guest':
/* Guest mode (low privilege) */
if ($req->password === 'guest') {
$_SESSION['login'] = true;
$_SESSION['admin'] = false;
}
break;
}
/* Return response */
if (isset($_SESSION['login']) && $_SESSION['login'] === true) {
echo json_encode(array('status'=>'success'));
exit;
} else {
echo json_encode(array('status'=>'error'));
exit;
}
}
?>
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>login - CAKEGEAR</title>
<style>input { margin: 0.5em; }</style>
</head>
<body style="text-align: center;">
<h1>CakeWiFi Login</h1>
<div>
<label>Username</label>
<input type="text" id="username" required>
<br>
<label>Password</label>
<input type="text" id="password" required>
<br>
<button onclick="login()">Login</button>
<p style="color: red;" id="error-msg"></p>
</div>
<script>
function login() {
let error = document.getElementById('error-msg');
let username = document.getElementById('username').value;
let password = document.getElementById('password').value;
let xhr = new XMLHttpRequest();
xhr.addEventListener('load', function() {
let res = JSON.parse(this.response);
if (res.status === 'success') {
window.location.href = "/admin.php";
} else {
error.innerHTML = "Invalid credential";
}
}, false);
xhr.withCredentials = true;
xhr.open('post', '/');
xhr.send(JSON.stringify({ username, password }));
}
</script>
</body>
</html>
adminのpasswordのsha1ハッシュが与えられているので既知のhashを検索したが該当なし。
admin,guest以外にpasswordなしで入れるgodmodeが用意されており、IPアドレスが127.0.0.1であれば入れるというので、HTTPリクエストにX-Forwarded-For:127.0.0.1などを追加したが上手くいかない。
in_arrayの仕様を調べていると、このソースのように第3変数を省略すると == で比較されて暗黙の型変換による問題が起きるようだが、これも$_SERVER['REMOTE_ADDR']を変更できないため使用不能。しかし似たような脆弱性が別の部分にも存在する。
switch ($req->username) {
case 'godmode':
/* No password is required in god mode */
$_SESSION['login'] = true;
$_SESSION['admin'] = true;
break;
case 'admin':
/* Secret password is required in admin mode */
if (sha1($req->password) === ADMIN_PASSWORD) {
$_SESSION['login'] = true;
$_SESSION['admin'] = true;
}
break;
case 'guest':
/* Guest mode (low privilege) */
if ($req->password === 'guest') {
$_SESSION['login'] = true;
$_SESSION['admin'] = false;
}
break;
}
phpのswitch文は === ではなく緩い == で比較される。したがってusernameが文字列以外のときにはcaseの文字列を型変換して比較させることができる。
BurpSuiteでログイン時に送られるjsonのusernameを次のようにboolean値に書き換えた。
{"username":true,"password":"a"}
case 'godmode'にヒットしてgodmodeでログインできる。
CakeCTF{y0u_mu5t_c4st_2_STRING_b3f0r3_us1ng_sw1tch_1n_PHP}
brand new crypto (crypto)
One day, I came up with a brand-new idea.
author: theoremoon
競技中解けなかった問題。複雑な計算をしているように見えるが式を立て計算すれば簡単に解ける問題だったようだ。
from Crypto.Util.number import getPrime, getRandomRange, inverse, GCD
import os
flag = os.getenv("FLAG", "FakeCTF{sushi_no_ue_nimo_sunshine}").encode()
def keygen():
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p-1)*(q-1)
while True:
a = getRandomRange(0, phi)
b = phi + 1 - a
s = getRandomRange(0, phi)
t = -s*a * inverse(b, phi) % phi
if GCD(b, phi) == 1:
break
return (s, t, n), (a, b, n)
def enc(m, k):
s, t, n = k
r = getRandomRange(0, n)
c1, c2 = m * pow(r, s, n) % n, m * pow(r, t, n) % n
assert (c1 * inverse(m, n) % n) * inverse(c2 * inverse(m, n) % n, n) % n == pow(r, s - t, n)
assert pow(r, s -t ,n) == c1 * inverse(c2, n) % n
return m * pow(r, s, n) % n, m * pow(r, t, n) % n
def dec(c1, c2, k):
a, b, n = k
return pow(c1, a, n) * pow(c2, b, n) % n
pubkey, privkey = keygen()
c = []
for m in flag:
c1, c2 = enc(m, pubkey)
assert dec(c1, c2, privkey)
c.append((c1, c2))
print(pubkey)
print(c)
flagを1文字ずつRSAっぽい式で暗号化している。pubkeyとしてs,t,nが与えられ、flagを1文字ずつ暗号化した暗号文c1,c2の組が与えられている。flagの文字をmとする。
\(c_{1}=m*r^{s}\mod n\)
\(c_{2}=m*r^{t}\mod n\)
rが乱数なので、これを消去するように式を変形する。
\(r^{st}\mod n=(c_{1}m^{-1})^{t}\mod n=(c_{2}m^{-1})^{s}\mod n\)
s,t,nは与えられており、mはASCII文字なので、m=32～127で等式を満たすものをブルートフォースすればmを特定できる。
from Crypto.Util.number import inverse,bytes_to_long, long_to_bytes
pubkey = (44457996541109264543284111178082553410419033332933855029363322091957710753242917508747882680709132255025509848204006030686617307316137416397450494573423244830052462483843567537344210991076324207515569278270648840208766149246779012496534431346275624249119115743590926999300158062187114503770514228292645532889, 75622462740705359579857266531198198929612563464817955054875685655358744782391371293388270063132474250597500914288453906887121012643294580694372006205578418907575162795883743494713767823237535100775877335627557578951318120871174260688499833942391274431491217435762560130588830786154386756534628356395133427386, 91233708289497879320704164937114724540200575521246085087047537708894670866471897157920582191400650150220814107207066041052113610311730091821182442842666316994964015355215462897608933791331415549840187109084103453994140639503367448406813551512209985221908363575016455506188206133500417002509674392650575098359)
c = [(45407329054347031671462943733352990423405785239871852919766388653716380674478315503174214528590036701783624146580550794165374415239306839525663023158300526837557014080909086170028906592103649042424746066914113525159948460918940298801848524927126031315219782495938440479872531059016544239798079080583435425272, 53803936997086552930627817379668506302893396793752623708360134917132605596928214528571105049705120619752149234071083180369925875862051592731789425096964405472100251718476911662256938722325188400861316756367788140688700177508892203256571533937287519223938863342057635289100232219250241102383398900866693695652), (43655057390335874506424383722663749879268247658758301232763211203219034349589651957189919237836443955915188039020164771364408742547530334210779314381716283732476569324383808908588686811442984537157164133686423953400300793137466630580146269650901652256761231520608826151296619038805828021253934922305783052068, 22233195992702924578524207396162236484139847008812639391463164055567886910452393492091463760246536738125831803192662206571576172793920367252270085750654989763310242365985521455667232114869169344954690807107158884655752698402756382223555567145081598370775906153285079937174531239253543407433367582200836610175), (48173873193909006408632297373915173790664659725746939094589343816073423919263047699388435118407574844268716955427868555631969644087988395036364141902594843243379684314361966560751185147668489006481398858464098338093514824123877412587515749213491292900765729982214694907759173091312610985653757846721099693705, 76817816373615148654537532291761513097163971256744831379142858777846475358054723383285667408330406512928700971894048395942516839805953619252254847283301512970930741216713747079850697370802425515835725740876449005910904484351656611302288466232416535480093946267856758500867503009449274185328340037258592716371), (88181556564448552743470651647613170657265373286576775460516559200455566480309480705843230497653790999582490266271313892072511625577265833270079728068505993491356494530077152806136276226195967028046339189883006809964435844460698466928587302061692926433760535217381986144262861862566381194116070709037208999401, 63370723636020229642410979908187071508736381021595789419457496843573386844198640322444487840285946294022122763471233336770659096823580764650076994457887836246663976420521365592844871147648096148955435558684689798834090516872947869190607978012558695155976981949795502719139914429074964440672738004797662751885), (29139663737789913345103441763780807040514657935189851468405000837294805478670789331447639954020377820647986737668615350421616354471056827872331675736340460779795705242873854224453751149626796824129656577825274945589606806573528485093768168677458644538824156398404420448765270996254466680503974884590730687378, 21500379801479007023353668056676746223176565487836817834056195997514529407585222504949002514061494924818986877285056823370793801366131278299355198753204202241110732235726065633572048452121474192587926512893685587829196851792871282932391943427859886343407845632783583634735667917765301063973911920849180294098), (54809525172944218202784726054498706998986149532511307519365283214884333880759745646278235574064877808157006111870771237203269184164314286476070475185995594824309208502823107324283920052191671116525458147531253950071276884485238114103420679047825923884557258462480734282087906311641078470196896360487749892573, 81756574947979605476650028939295792851475444895060413278232268139381597769558451189134106037964480236110371112516333929656157296036583135264093244894292249727192183265430654608785016023574686377239496707149469240805172256538547119578612613881470987817240447366420531027722797626494948409537961295222642021444), (64581946911869470666097268473392661044475969923339229140927358267556528172213609787779696090622053952652668978524338470162911316697390949808783655611617876109211286694343109621020960295832172147438415561956308406799304243867943438522877262605902358753239812719829300922953429837677373207350383089531945242948, 4989202309903010953719840716160983131923824435926216390772665631159083535342650887896436920339410183623631783629147570511670117183321361647935232415882559823843152346725088400015157458185719803768183653956581039298618112278104252985108558324521969323520284557339380818947379242004241551972067129406796808935), (24050664789314886113720668704180550072993106310870346083253546267042756407484807570451813004260765063606584428605639572513424172325412403895838039105709376823365323159655659151408268823133835771975457499029638871482209996359202745481739217943688219653831455932633967649578897001344404083554900566236885627737, 5078862691592128263352852510666122840030285630831638766176300357522807318383846716106216568460142803289566847692345952651963412612962105101231388253318702295886925661843963084255196924883678429164955546747674338551155382989815950325295144708239558070428759268472145434251227219248376558739077877118530558188), (10981182755645110147840880990626281909200842864374510902944701655395084603646573786166543516890533214506391857428638845372253733737156456082844743708690266620584024715320183807311628767363209619331085192075820717082732277252596167259879519767012311096053281500843889124066588113231154849160559020474649842587, 48628013989694927962194395415798795873416288084308779260579310956002594515818120285022411082944390380970308604763496857968262138386211780401383400041921478603479196794980964506028622926717244340252781575614138892749112397650400500418854520548246410937778301968094406721694358172486175037101358211904305056188), (44360277072700564667964173299662488309584045678334750273307585678949472488131125933301169268398108693130870610851130563562090826740566901389184325759939555672952981057592887466739014581815332917890531875610787126374523236060844599081895057821080780548090658842826966188770983803744090187804553933028284254496, 48273434685515654186832795186583256450895711192312545965105109470933068272806936185591944079210941237041982601541620984754516345720659776503957564804487602583312942065077659473295380140474319873730351072144589623573969204984854137989929858207704633624005052516826707160016060208365297336358565522317813767464), (74277933307236164326757644922067920801480785119949118589560723492534913135703754520437407922955182889954305118758677121762622579641738595489644476162454299651705753977649890831175535558859659525822911912287630717322506427309948348019059409214267177709825073868587534379366078072632602447954405890179938497461, 66602388097201318405705296520564795735953321348327797787051884532396438924734024286046743628020460734981623607608174540900808784257988960564208045076250282711405581704384244359869398658420527457430106563782524831815546242794912450142390719447021885168566182186664874168746315737538628598891671251478646569617), (49120599997213639306440821727046825314993860762336395139600472507067816244512545746326501825105904276141522344200215109677387108328336551306880558925846585406040392548038673084306865894764819849040850107321143831794486395912595925305805216964539591635806444085598930586673451131584169589994976970980116536532, 89605574950696010170500382341449965286291373776728773984278459956617560551368218268682897979905299084006206665281133782058303029897527802677831995496318862776228671169484298444105000685342284902044064551058007429448992686320553051635977774855333332367078869021201194024528642186911178765073214845075915626179), (41611080343606305830333831923092927711590469283988442378503884159556024189514675436427506145898811044466140448358948186450665318639405341140042120267729049393750987970242498568755250433028344998764727169201091360941372506979616400222249776986452044815280977489214216970290556155565929065571349321400040283913, 21139101480491595249130131428878444537421820606030591689582012187092436765245740512682059135054538501020177284744367692064170753062316751646795161243281614703026407863201142981649528660337350889287055807832758516648170894331032036142036299561727043692745576731855213488764703066239572002910072596534446393839), (20490987020873393090008295620506280766213451771219628158341596111970095830892210293314699090243454110753696301316012556612494750985052684739657739104333864805614326073598419607021749253786050899495974576862156596449007947396263782649180518906154954849534631495476172516357072199237048119032955986061871862791, 52850861480093344347499519384438724817363494693124489593787028233020406143033254649296542300511931220384839505948481451981576902841577951349288618983278854982070953169642507493786846520358246749714992587127533832169910307963688683661599706837139677683369318080006636158263924710701720863830868341920715621682), (80853409152239099736735872194427808832980418988933693163305301375040630938093028681852130708526237031395461431892234731310784471397739336729179565396082711796484062998605410852241177946554055329289624332615396579952280692123661602733627502500253572150193893738215306126792702936942644834961376146152970407738, 80973097743756544665373698310048627537644987905720998071139881933189894486845349857678406443601125043131283549635099209537251523375887247430981981398224532015713216627147625029264837776848999772480406852744590074654410393950652962445457596572984039590092010512293665086904971617310470279237797895412618927277), (59319218621513273128759439143529671215875449536774356293431900286422749894438024740465572847569537475961532836056341881145173986346241368533905956600097412766460790940244451498575184259494816082619182998930076428238477191215660480755765456754809972023953106617826139962192056600709733605285365791427589896063, 24357887632691962970976985089558301595349861281510080484490644157364225341499870438287239961541145111386858884723584247791193028047045783102378922036816196942514480950800457281669365194862805186378709747930469075093267406790928074179402303136297305267690633892780347370398107941822532133246372257691166589137), (85217094645426637465323870559419505823708464072911745322845791142515396143425435811563642023523280324556875259780157674349099556725355218085572779434795588790477800050416896639675576381808694134873024789314835498701807262456973666346363213730337324857207545199143824378358338525580674936703029527863934630717, 12519809087939336216752652200157609404708023684768262633178814643142480959654963499884725352571999224051592636619664254250643563073654054356328411217280512411346187624501189423266941883486844640544641438300961204859007770951322441443967996040926551311322697698960566208311293321822613221572517752610945736721), (57288946944410943903214662819251894187325679110281167871413777309626588356659202019503729275710180126211456100317004343048505327374757520391179465155903349755948006110029367397809480290273245621828529738326508975488971533561543457157080391945152462726278188796142447512710090859975919606541174124792404163439, 22220712351333069567427557033262698652554044414331306784186320378525310196529786644069251717170491091975461914330553302471323642439967695857824172144862510297924161839180824921039392476239749209905961023229296126307918585113463538803539104363412162799858052198868138257236235018855763409241899887882981736173), (19835741197927725763399748301000918602288178863503542825868728476987269999258814871571775923113209674232400500879120632477519746567852214263869025007738377114685857958449533825299792377249175544164445678950341070121158546719612745591169898168884908959545231778812680867085358082303611071527415161205564845836, 19973222326945723408242843496602781956703549960674918557231158176287550473411113128599088863813547842956991616425799997338489003245285107346467937974857394623924044368870123099167824786346528109351675640263942071929065802641683227178884239625722201578691224998522346953657490728954250643776587537140572714205), (25554167339937618394562541331440243699596295966058060814266447870936244405151757140240692565052844806710069702863805265751880795277656508665531889816911791909901907311088532699704960033117566205664374760808670027185744249102732979464429381517071160543081035706218385900233427838370049446027835362206434314894, 10460575105394286237759519141616855215681418062638006251374699808676359893285222802652035401150684072263112025850103371598505554630968820395367459892333902788733965141740736003965094716675836288257806163369303867674203798850601462147738714424954764249099842558882052587505989161855896724365851599582320083878), (76177848157770995554126299097219136005305052869591323919776394353268855113668448401574787806986472922311408362977960044250384277658584897656648319717109157841717890205487034704796193287500391971452387990211710786779973681681249067924737843830540542383699593967515599366065768800959591924848070827108187677038, 46215456815446016335267206114919934650862972950250342038033156364633267171006631241992835931902390699214514408179128537784649609476026300451597941206872970370714837920767587886970200637691626864232711537713162628036756842418037810519178715245505978106233990651312201760477651376960741845640133156005889460316), (11269955952468438206955851954022014926484202386256826823886154452500212338886038898188721201620401061024335996109886736658009035339755667988846131141048272132722822635684725582177693861955752717084282730289676737964038247479485039795472547492379733367037244088054859338662949818649091943035956826076556245029, 65433665727853015848097740627681436799112076610316711683312555103838308687915816938955064441477704797424945098871481738559154443138532109555026129915101258462126126697966967810610052215792514651190200640484500281048963167521750002080463066891449024638705297266122017903593763805594124143092937066371087923895), (35416095072640273615139991580036629511136986196117789245602474636223514660234557491583069779459875766893399012004707240389838301250537022486354763271510837416178071811362701648669343192981137137248360635747954873589833490186622168968903884443338978446268943170357745021757343452875708216900752436145500050611, 74198210279202177497048622771243543325378352654865510737792920865966497575682474568611935597992838029014306039791404338602293378727904580803502242118388817678365086841674799963903665635455280397768184807595161532934929872572806137182454236958317255052971012347581841772471473480687992025887264641568421023573), (52271588561351867515196054498308231113748763360194435525781167443200385650999864949572633987104405248103420676433070012501618045056966961865458241021369414003548111255496814619027717975444266384925711499126319909395622419682795495526760984707336606251988758479565051723035640753454754302367308441170444811397, 16444883713624365851750068156426766563545673093987671965263826320232852536013662548110110380452441678149404515764945427189802575704944181544359984028658512002740548167226803255435840529894499459314255629463585687990207233378008765188475349935177125177609330643599660398310962024503541326271042730261146704654), (42821234468628925922499698480012095721977867526248078133782929564764399713761160280461971921285020761076172034966101269594805345437358037903565786855873514093673962340842716581898569510841678122603340965045893401564705146110936338224582167919921719329278378952856378441516972965654066654323902174906003000033, 27377479209413995816698490519167619990466277095035668746702445475259897984122114655125884884618944472068139049649061934750918516208397034412287316084735607245406699774784069545578344774542778581678647168519798548865507143806856822650079414653438568508869686219136150973497156053194562838177342993772488111456), (58062507824630699098436920212053195649218896789481183328020847490509112063306132695218080639122851511835046085028434265067694447433041929231094097085064292054615070252348709738602574771024737320319719950726743588561079850547931988475348762931856145934925478501955609190195539054130348208656268997983256260294, 240701597589678942567462606537262408517379321625639019616610094642470104136331371212274921877433194919860924517822357991168875346635862636675924235863363690426243173174951386412868896885371134350949980222922834977337505806007699679766656242941471317825749826384691780383233646920584182111481922165072882383), (4125708060865105810034805509930307557940082978071370751313203826359965822310262019150795104206289727495039598144906535821266535334482886208275533478794955539954388025135438406775217806772699844527794916247081118063961790094975760177446181160221497646568446570017643397423449487509240340320086907819889420663, 1836932230493423935444595413409225185810500755349362763840406820979916981342003381216731048384102641345612767094995028141589534874642358670555482441437259836099452565221930021137434738360827985826025963815377675805814928919685086296626376067237513427288172762353445116713716459393061073846340156263331186269), (65931713182668749542175624921968745524321223387852019959124572941503644226665941539336445826103051163475199371141274310660830281707450938072748016603701892392440880217148099992933316712562459434593392856931861328141117424081701015283680263547142090079870038157955781833996061436329676102522123064378500568108, 5440527496347321506994508711672573238933251703083149620918031771093931068622519457635760247201842011662654730667570064333980117020014786948941988041693219720785794828094785180992573895596442733116650832972187556379729236117021344611360799315557240919128004672839877681954508825352834590163995491746162449328), (1356944228036494354052115490423028025300823090360032662752421214773203791145547594362443303861634714763309825766676513349433093687323391141826224172914812024973586196211119852698426577437766311109737653448871758023686496783181761150494775440498238414290143290345016690420389019576910552329873700538338300539, 53647025961779606832847391790850869437595570215517969293674088318733317364276494740168499102137942708502599001177805749589148451272279632854210269432578175137622820986316262894596402763868063474902556123471455711109621458298180746327647163435838766196485517054947577827216501433595425623318294047201016959347), (36818634055835319932984480336134294202118180114169178278340029248632771412526001606501073071921476491068666947585444301902624121669560367233369392214453933850510490937295150923265557861164203437685491354728938094230921990408933786471266430095673823790308864488561137167464491863521930764623489771316094188679, 78243253311711446851687955119808361600692752383790904970462233046330896607484860563599954268004098636082195540350278465163869608284137609490420748250665474071758292700168482969481920660866283010537956996753569406310395290515467626696881945479350635726382997937817375515940679160678519648656866139988564319388), (76840120041164084290556006661381189107512959872512527877514920633961742522749499670880231032585080472851806944109188987242266446755152383005147945448851053420277198872024989789785259189587547636048850520263650841469908135841501877708766384198114528068103780707035363815433360722834986552182822645576328199015, 50074062846148509248344549604017873625536412277864756628420952242913390136198357561081457116697566296501551411670488204565709073751860962324292103597984714513043114923395676308578056967625728730287462445589954801551427722647685123676662471489873779250940702937440720501951774372278339410119792720005344098558), (50163461428489953576004053612907499265999803490005549559244420438902194707839286991574026422725057995822227837537043525859399565756467356066905283472910075618438714309391865932051246754702870448640518356212066064361705917590156375718618940364950837882254094001744528970874952696293137683097955003541836139257, 59416831451197153325400627969950618487412847588489831524681425247369014731366332318413100528312302406457430083784243145530812220078568460958148665584919203707291453922777259666790107421295283849024591088424471297880048525871963549477450230411394690860776792880532135063697486930540577835681762104363371989622), (76650785761954112630096878761400709592616226052105263087421756456891458994695778032788332981918087001556609615471790802410215094854463175632942570802427830352201130688831096001276671195670309226365859496031221274561958126680019380782574462697753506849739880291609930099751143877476835898387465615709136128399, 18163124475719965357998583638921492649077367745051057026376108188696491652851226275515200025115440688329849993540025587934815359688053424195678298769724820068123704988673437401070099713933516465493416742891546631560955429471883942471987997673330729102413645404328394635861466662054753133042324200080631453586), (5380539094648158144269731447069739831541546529159009232736491767614186283389523459270728168517923165609582059857792404933438676104881557075187157970035607798719928593815044194257316991660153446383026057537023237200172373334607696957414043605482240578355513539752352291933087855038649160500371952972642435518, 37272868681285311892320540335507188665933066274743126619307944625583989880844641309242994172264104275130536856240654702795794628245019325261796193527950164502257585430319910309056987912917720031119981455833930898071491366851697560046931942351194533399707804630258069997772038641702853818050354445826383712061), (49619601666042404929919230892231776198099192378743150666287963746413823407663760261510249035908181845358101724898367887197326614465900064959913415585357805262808888737357476995411160388983031520556857955221448114226657503555243291209732174372112955682752626778203304098712688866512730246908173876723073857582, 44840996889387328159172684354120922743910271777351527609935904388419446604192399230033674446767798727496577933060653336706838452512517818991608987955440414816161584687582489828491246147930682617091765610447626130637711482984612792630768779707575839877450237925908332440975399707860344946502346186776059948565), (22958781771732345187204316848076987975059971670488921431474378581890666325156051036244487445258701810957327476927055333872505448155790977268099260050092055693305945290381751279809883495653200273732061673934680669796499820254631148766585953011229318014006949037465368890812834003685076292396606766784226250169, 17099920031969606234234096691836134238969595641557560110099442393331752996575236468114210450291700024219315980818875745502988508765563496602701839788628476907982260930975252911816033475365459331324611173384318240490739799350982376628136015898958825309612348508000462302444825419853737224215324126815125432853), (30656717514078231590975866524172875733745333807410602534893419474697081425009104025841352062549736884948644989907083309036443738343520726970292297399935912835649102133564687634617790382463038628689920460402204565031424197226853138698386752466244612465622554780889142542635432703304552923635861900506143775559, 40411939854112773751662006874982763230208708108754076427955148550516215849098192289637362074290966502046676804977418190869153220508812448022958731224347361982211815853037715160032532678279968503337767753651613622207283842797787238062598771987554935540753841721822846867066266189363280254793170571538914780711), (34927721763388926767602424145820089007146556548751777041209966424535318837501594880896511453245790503266898485153279448538230058738122729148684342270663901343470406975505891302988672799134893728410201537809950290913459730953924879048199200943848633359325456243119257012096516819114325168592508363238140142736, 53615749474627064447599836316842885262307898519123375179072068969035321756587561417041120702820380537882713025654401116235720269697681865216800482492717789008461487872158923575373325063534869720775850496315429243060685436204431201426655310676074617382385128720309251393897046466243029901982261208809837795869), (26658271065213903276829412050255335866161778308305414643138982804683845629689762402754727571410504259116450598396835880131625743291742656122520066094899385999859668707305721850573152096342336269270754500129460390871085335525846167479466823811238311459018365750625589222883351053639847033610943885943991599649, 63367480038228629776574239235230111545901049202319091631188362352003396690591017347608155096880802828898932071416567549015994091510867537591686345776067606068928068605786963005009701749521472861797647776524649500419313923192547563008808602261806809917044755330974653082688338053308989166815535158991683276660), (4952439175075767251330727193762842236997720733433928601189846086068517067282486951609447942718281473873689518689479945605394409464654427408194024386299148307317024353792207291993174153732131984690664568392440864586138043586025454126074349461195808359204470782496620820683400440432165892188824861921952716496, 39506621564899707276621714932812940323192541772931609001749356244789259777505660780211019458647083034195839251410307268167170038735981658890093081153155350449156436601590917611340975743771353770947072832272282947694999923539012669284326179285910900498413716159611492944836692385252487719496563237429222864359), (353864615957248211456593548147288733436232946830782389022011150746590434381159921866658910189704763825441461517782043530397700799245454880046167616969889911781057708292916945560090386958746449099941160545174414847537391882328267649094245053436745820002827340146511344672380975787595368870462339657090754025, 21652037213978393616033255777606331114993726006373231091791321587680393957895130829759631974249988070479126519815038141804240640412421985460131703042014327575391771490402940753196320750789474882286696753664354806815481807224187709171188658952949971383365563332718716244105523249065157421111498014939122449668), (79169384697457164615264523833308539499979735407436650491360452270841526048713122405348279015429721418043061855398233353397168779743948311507366926092302395881817073139852341961737990430549062587090978216743806556108013068871638664031288673265115538296853290686213055780043883934589609228595174647897199340555, 62408327911241863895511354101403908384365193320276742609383798452946917679645451543513946120561363895216860423860435816254712655540309893892142965018878021494579085911806538824880180397954807628565654230569301110335345188441343069399738042207002537923185480545992609090708775016050438923329356289824368060528), (57585029704785710147539274752112440519580287542674657569968683089795300504397139946906135267906715856550334096881909933439053962717233562857148746789495707412477087370129784583080086526242999957218156775073876111995431994318581809555849108199307439491353909277119541246357971239317242617741054673246069214280, 27783094581614514281943099434364804016073415275807509022317808099388776590435421391884588932646261248401975923176641151156622813742964331714375790433992358143300561413055042425635958892899426849084813550453467707614338438866371515052386327897466646026270540921708343983720539751629019476689295235575153453917), (41077250740866790447100465985972835757982726462659500458904629308450991778147801788893308630744298905682441890370493963568928729814718837595173746804968050978611959808981498423375275551464950550673176619375174207915856618665663730207576153355694485377178216961289488954856674421843179435507819598054184939469, 26943346365507944910774328060510704860364161305003573314236904432218442142210667996605234424941372012704130955756634235542459941332726510089413093757752045374196979682932840844323672339067873233421048522391942009004620967841370138899433729724235359858651523417360570908135708893293166703477175648306908683545), (44918787366634518892106390083981948284260910673245794059352962820975492768657545424155419849313433112996850817556161312708292937974296297335131886678971264108245684738174711312026488902202248770315896208266176179956745037068311877655221175930797189094930825651385648855699846510627865487879029522543311005622, 78979601980305569617075034436907321801372187010122570286693698981250137203506219602621994142455907362221755887868701148905732841841259936959747788993129243051445773507138618771991249338599903885651897365071334835565645573905628503560375804343537905258782853227011815599291047972451442767677107438517640160312), (51666949658924342405733281842482325421179362110161773492542420992274074856840316829859206998128541971578319597831084099753340880688273994524443382911613379373659343748669340243306563407572597950821991792193171177254441460079357885357854109308948330977106915069427096509329950708474940868690977240995549258122, 52761412767823220983686386775820042512355646607332261081358000855107536021620748183437703468885124005260780120587683615619188942840795842025713917119747212781027818368479920356829928227176885980467349098084791784067775441955522606658415080587575594800507630920346758785182432805238692195786811034115547912095), (4588176755849559990874105143212886482880035541789043414137863503174998955303700677664939544294092635264330297338331332472025353697885374404868983266347812022745791486261484476841710308468074387935343293176699241090188652111061009201471278410084020655398474914261298850198927083794356654544582517083472666620, 85037581275048280715758647032757959383085610630899293576052724372440724737517365669971209337352103703167318867313191557640467337378589421291041535531495003509796817972929010027189989169755211790862677386366275992170524712466987548553039479802192929946472203762312347270701433684927840144783975632438418650864), (3611469832376257179006614519466729380346705051637855896476550833890325003288224466267785686496193515771491496483497841040776984006243310160476851954024096573048551125620111694220454335636944181902365044718076881258376330144709071041962521294655960719149552462080191870516037354425762003072654651923475417889, 16407221464213183635954007657263709233538452770187865019671477234874961690874533350646551261362718783372434890533479727701339083999685535471377235169395733060763617558566929717523100821784603354916473874919688995925169330872276438484723896884644215414317687969220990254303782316879515914610145923842361425869), (66294955175369445366051223626345473237935532901143675854858005103759816495782061087246322306776038271143013788759733906443735381065871244386188212319097075575210923933544825336444634222151849856488223023188672159173959370826601447382548185668903025621431463604434938736763455640441028242933588219902343355072, 52997681848706092949951286927541641930134498793535541839978127746460273584257425422628154997042960624404276108032593164982040824394546950557581558408382925557388338099341721349316865553858506599719185450132027746504451205479995111345835638840644077342472032701457683474996828181788207666687459371709901822084), (27911981556337013712930157335239281511765759685689650596325660565853535615228138851465775956483057766153574743199103570947029029073500908901801045364879500836762167827543229258162053359855722283291743265378056666812738510754948399787471865027282345697111137579197232877106526152372524571974306357178805491288, 23170831324418941374725150578818022337382143015626258017291899913538067790684515810732538658724883540277731332253444366276367380479308928538997832156335453210801209925556520553962147115469889445406266331497113184402553251888760053016373852466590775372230369912762092254342458069361123861419318643950013806890)]
s,t,n = pubkey
flag = b""
for cp in c:
c1,c2 = cp
for m in range(32,127,1):
mi = inverse(m,n)
if pow(c1*mi,t,n) == pow(c2*mi,s,n):
flag += long_to_bytes(m)
break
print(flag)
CakeCTF{s0_anyway_tak3_car3_0f_0n3_byt3_p1aint3xt}
