Harekaze mini CTF 2021 Writeup(Crypto)

はじめに

nyan( ；∀；) というソロチームで Harekaze mini CTF 2021 に参加しました．

本来は 18 時ちょうどに参戦するつもりでしたが，大渋滞に巻き込まれて 19 時半からの参戦になってしまいました 😢 それに加えて，体力も限界だったのですが，せめて Crypto は・・・と思い頑張りました！！（他は力尽きました）

first exam

問題ファイル

problem.py

import base64
import random

# flag.py から flag を読み込みます。flag.pyは非公開なので、手元でデバッグするときは自分でテスト用のファイルを生成してください。
# Load the flag from flag.py. Since flag.py is not public, you can generate your own test file for debugging at hand.
from flag import flag

# pycryptodomeから(https://pycryptodome.readthedocs.io/en/latest/) import します。使えない場合は `pip3 install pycryptodome` をしてください
# import from pycryptodome (https://pycryptodome.readthedocs.io/en/latest/). If you can't run this problem, do `pip3 install pycryptodome`
from Crypto.Util.number import long_to_bytes, bytes_to_long

flag = base64.b64encode(flag)
flag = bytes_to_long(flag)
key = random.randrange(flag)
flag = flag ^ key
print(f"{key = }")
print(f"{flag = }")

key = 407773567691797768945309646881381330143924911048532252374484400956007416406007936505301187512369384531883020224488253602523154102140950477859193
flag = 1392812161183976577227166142672085037819799462496681473937900208451109718213256601589927195482395914799893761610554140977947503369343069077952836

解法

flag には「base64 encode → bytes_to_long → key と XOR」という処理が行われているので，flag に「key と XOR → long_to_bytes → base64 decode」をすると元のフラグが得られます．配布ファイルのコメントが非常に優しいですね．

solve.py

from base64 import b64decode
from Crypto.Util.number import long_to_bytes


key = 407773567691797768945309646881381330143924911048532252374484400956007416406007936505301187512369384531883020224488253602523154102140950477859193
flag = 1392812161183976577227166142672085037819799462496681473937900208451109718213256601589927195482395914799893761610554140977947503369343069077952836

flag = flag ^ key
flag = long_to_bytes(flag)
flag = b64decode(flag)
print(flag)

$ python3 solve.py
b'HarekazeCTF{OK_you_can_join_wizardry_school}'

sage training

問題ファイル

problem.sage

# この問題ではsagemath(https://www.sagemath.org/)を利用します。
# インストールして、 `sage problem.sage` コマンドを実行することで実行することができます。
# this problem requires `sagemath(https://www.sagemath.org/)`.
# you can run `sage problem.sage` after install this tool.

# *sagemathに* pycryptodomeを入れる必要があります。
# `sage --sh` コマンドでshellに入った後、`pip install pycryptodome` で Python の module をインストールすることが可能です。
# to solve this problem, you have to install `pycryptodome`.
# After entering the shell with the command `sage --sh`, you can use `pip install pycryptodome` to install the Python module.
from Crypto.Util.number import *
from flag import flag

# bytes <- str
flag = flag.encode('utf-8')
# long <- bytes
flag = bytes_to_long(flag)

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 65537

# 計算するたびに mod n を取る 行列を生成します。
# generate matrix which calculate modulus n at every operation.
m = matrix(Zmod(n), [
    [p, 0],
    [0, flag]
])

# sagemathでは ^ は xor を表さずに、冪乗を表しています。
# in sagemath, ^ means exponentiation. not `xor`
m = m^e

# listで二次元配列に変換します。
# convert two-dimensional array by list() function
print("c =",list(m))
print("n =",n)
print("e =",e)

# hint 1
# c = [? 0] <= what's ?
#     [0 ?] <= what's ?
# hint 2
# JP: https://ja.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%B4%84%E6%95%B0
# EN: https://en.wikipedia.org/wiki/Greatest_common_divisor

c = [(94705679004463284733541288053549635663983624426348082883911423652044420589882644740030824857964094373277293351421545117172457918484063609288563394969114856228940330220982203798491227942337707868513380987219942847139213839127934175216087451584996193094098370176337671205679032479708240220775365041028562298045, 0), (0, 14243811671300968907609174458855708829741032120754409000357686908873126315334915231420353855815283498571171729689334442024813021199910238276500626386134036150649025606319036019223959715867658461585221634071508142818645594816357236002650041503442624594820852244903155433016041077813314542285538820574629698950)]
n = 123658273021758657244926229590842169697216202161458868027271307824674005278002104678607018762498569110790554844101479136721968081586766904446085438475258864812618061595487772978115460674609635002737826341845366713797429237465562629770189347062332559337703309881797723858775511801114681134013841432780549606609
e = 65537

解法

行列 $m$ は次のような対角行列です．

$$m = \begin{bmatrix} p & 0 \\ 0 & \text{flag} \end{bmatrix}$$

各成分は $\mathbb{Z}/n\mathbb{Z}$ の元なので，計算するたびに $\text{mod} \,\,n$ が取られます．暗号化として $m^e$ をしますが，対角行列なので各成分が $e$ 乗されるだけです．

$$m^e = \begin{bmatrix} p^e & 0 \\ 0 & \text{flag}^e \end{bmatrix}$$

$p^e \bmod{n}$ は $p$ の倍数なので，p = gcd(c[0][0], n) となります．後は，$p$, $q$ から $d$ を計算し，c[1][1] を $d$ 乗して復号します．

solve.py

from Crypto.Util.number import long_to_bytes, GCD


c = [(94705679004463284733541288053549635663983624426348082883911423652044420589882644740030824857964094373277293351421545117172457918484063609288563394969114856228940330220982203798491227942337707868513380987219942847139213839127934175216087451584996193094098370176337671205679032479708240220775365041028562298045, 0),
     (0, 14243811671300968907609174458855708829741032120754409000357686908873126315334915231420353855815283498571171729689334442024813021199910238276500626386134036150649025606319036019223959715867658461585221634071508142818645594816357236002650041503442624594820852244903155433016041077813314542285538820574629698950)]
n = 123658273021758657244926229590842169697216202161458868027271307824674005278002104678607018762498569110790554844101479136721968081586766904446085438475258864812618061595487772978115460674609635002737826341845366713797429237465562629770189347062332559337703309881797723858775511801114681134013841432780549606609
e = 65537

p = GCD(n, c[0][0])
q = n // p
d = pow(e, -1, (p-1)*(q-1))
m = pow(c[1][1], d, n)
print(long_to_bytes(m))

$ python3 solve.py
b'HarekazeCTF{which_do_you_like_mage_or_sage?}'

mulmulmulti-prime rsa

問題ファイル

problem.py

from sympy.ntheory.modular import crt
from Crypto.Util.number import *
from Crypto.Random.random import *
from flag import flag

flag = bytes_to_long(flag)

N = 1
num = 2
while N < flag:
    if isPrime(num):
        N *= num
    num += 1

p = getStrongPrime(512)
q = getStrongPrime(512)
N = N * p * q
e = 65537
c = pow(flag, e, N)

print("bit_length =", flag.bit_length())
print("c =", c)
print("e =", e)
print("N =", N)

bit_length = 535
c = 6444384937952479446360543800306726693252997452825552613901755375099255166714791921303820142603050845604453415771813934605436773362180219243666255359716995456217503120584807127945079526447091871683834669804927783277541340212953733681665967741288390917442432418885663222080013261671274096066346531406665749671823431928515791704387207382571496076159703188939522942673142857854899106254676400171188528066441584894129954980506317784944539407501773216256651827692873203651175
e = 65537
N = 13105434584967797009222723925714056612973229654650200307281518067540513311350491750775580308761120670043385919352137451528084580772272083564644136982142743585238409901075466075590932718136237274538943262152033321299508243379729042658808185056276914453786554308920681089647171956781340126500826872053436182017911021212882822071757885385543985492728290224139575551494811781675324350095354476279621406379090030101147754502075514438702852559140941288066281245455568260855730

解法

便宜上，$N$ の初期値を $n$ とします．この $n$ は次のように生成されています．

N = 1
num = 2
while N < flag:
    if isPrime(num):
        N *= num
    num += 1

$n$ は明らかに合成数で，それなりに小さい素数の積になっていることが期待できます．実際に $10000$ 以下の素数で素因数分解をすると，以下のようになりました．

2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167 * 173 * 179 * 181 * 191 * 193 * 197 * 199 * 211 * 223 * 227 * 229 * 233 * 239 * 241 * 251 * 257 * 263 * 269 * 271 * 277 * 281 * 283 * 293 * 307 * 311 * 313 * 317 * 331 * 337 * 347 * 349 * 353 * 359 * 367 * 373 * 379 * 383 * 389 * 397 * 128848696926495916745553917814994928035029667296489523727671944087609501721531394472379521718952890260723614901637405679983979319365111309546235300061499134122849592480818043806940443007569844452975480160593277527943252379282745963124431928313227735923103593549373898154166412196617883605212184745219274212137

$n$ の作成方法的に flag と同じビット長なので，$p$, $q$ がわからなくても十分に復号できます．

solve.sage

from Crypto.Util.number import long_to_bytes


bit_length = 535
c = 6444384937952479446360543800306726693252997452825552613901755375099255166714791921303820142603050845604453415771813934605436773362180219243666255359716995456217503120584807127945079526447091871683834669804927783277541340212953733681665967741288390917442432418885663222080013261671274096066346531406665749671823431928515791704387207382571496076159703188939522942673142857854899106254676400171188528066441584894129954980506317784944539407501773216256651827692873203651175
e = 65537
N = 13105434584967797009222723925714056612973229654650200307281518067540513311350491750775580308761120670043385919352137451528084580772272083564644136982142743585238409901075466075590932718136237274538943262152033321299508243379729042658808185056276914453786554308920681089647171956781340126500826872053436182017911021212882822071757885385543985492728290224139575551494811781675324350095354476279621406379090030101147754502075514438702852559140941288066281245455568260855730

MAX = 10000
fs = factor(N, limit=MAX)
n = 1
phi = 1
for f in fs:
    if f[0] < MAX:
        n *= f[0]
        phi *= (f[0] - 1)

assert int(n).bit_length() >= bit_length

d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

$ sage solve.sage
b'HarekazeCTF{Small_prime_numbers_give_a_large_amount_of_information}'

lost key

問題ファイル

problem.py

from Crypto.Util.number import *
from flag import flag

assert flag.startswith('HarekazeCTF{')

p = getStrongPrime(512)
q = getStrongPrime(512)
e = 65537
n = p*q

print("e =", e)

out = []
for char in flag:
    out.append(pow(ord(char), e, n))

print("cs =", out)

e = 65537
cs = [107466974184702145841553115319664339451930120354255273379558301545144507867522177692766159895259859624597019715005555797296886281889980929155335051650180549267089493842162874438089885015009176408334472291993521164651083717243958338826627907485117225058962936487939446771769736790338807986944156168183749925840, 22170132985413848490531783256781545736605099405646311268035819648933711512452780485867743670267230573816424442101847710685057703148406327241405695594207932241067458449670531595183417759103156231396266753674309067947713122567002400734977976535077517990037756703231259947021113899161279426849577708990870731796, 53663607942106145324856505634900952366446957335671164130522298044915630458145599229549689140621749659760530223576029477516300914481873420175142570078712350791717712867102285434801786722800007966464203566632283618002607953903231805867079414136989142782468226938194605757261613478374151072690376532757078133321, 78365694503332388406635946375239888121420777373504294295865419461438621745194084475076351926821762908738314158329198338224524128225720604464503818477193486444917215723917379663727939853085907074473084404201033606252087766780407179445044519351567149421025751850087276632425870891542111663028730543465980924674, 39567326944456595185852131549239713048406760014375723185889668137264862184400625209347132385346771952845648844528249396652730647892825213067744420896877172327145941557401152582745524351689936262218846212578493068131068289265309178184007416700486534305431585962239171245639859026914854729185183441536829994448, 22170132985413848490531783256781545736605099405646311268035819648933711512452780485867743670267230573816424442101847710685057703148406327241405695594207932241067458449670531595183417759103156231396266753674309067947713122567002400734977976535077517990037756703231259947021113899161279426849577708990870731796, 19813692100529537153354196993326523976562641892144201032611152108085873052606047939028690660226848756109920448101177116200738248725456016292678619972016171389890378572323158782910627138681771345476065407747135093852592146230620163204742268175127348379246545806302445392839995057465044154985661763415511576915, 78365694503332388406635946375239888121420777373504294295865419461438621745194084475076351926821762908738314158329198338224524128225720604464503818477193486444917215723917379663727939853085907074473084404201033606252087766780407179445044519351567149421025751850087276632425870891542111663028730543465980924674, 86174815022656632820771815979848030991675449543858855538627033941173753463367127894912055591372276897893437851783103074453592833551980654440535422481459741992278375567239249797317101408951009372022666702935853551917516924695550542803023670435217018079474513312282507406283149149570227529130055453440693914269, 34251875649975900624684998660114519673055590184671553260809017427144567326208069656921748383189000068962382701183513219524420099538429211695861509218173285646800610926279186899385309575260233174554207858518171018524467259932783939780914383666363299484495396394572719367986255792364572940917973921563505448745, 131565416119678741014839407584223561029046554798152094981545060972297005833560091291352270034957409105706026993588528015469925505101518215167306761508868265349503115829224214417137323529658877240406238182480876219586238117250727275734913776571115032892387800565095870548323872910437611015057874077022397854569, 33815480616631994870971836193748318863481967291437195733184731238113087224536068722813183061889623448743955589560683228444185059481907449357122797432162322060345888743401660268629471753828654003871502320494829264202176494512254265921462146874076028450917313182158956935690037364855755650554334685083895867068, 86174815022656632820771815979848030991675449543858855538627033941173753463367127894912055591372276897893437851783103074453592833551980654440535422481459741992278375567239249797317101408951009372022666702935853551917516924695550542803023670435217018079474513312282507406283149149570227529130055453440693914269, 22170132985413848490531783256781545736605099405646311268035819648933711512452780485867743670267230573816424442101847710685057703148406327241405695594207932241067458449670531595183417759103156231396266753674309067947713122567002400734977976535077517990037756703231259947021113899161279426849577708990870731796, 95099633707955315716043240047400293694963134315000154040199470050231601405242009961859755101495775900057639022200903957701742294339381243957985339026218101877491848982588498409542234475170365427534871365999205545899955987813295825723156661870032606446201831406566509782752822453980726176243545245206321306611, 61737408873612311772259012945956027132119115853001428319314314241907109256087958061546894753960238529596491497895380913312688665343145849089453317670932134264932588320215145124014649556912773725283429180364888438085909811849894942273496160144562117923210401864041673502617134476745582453861241094401041426371, 37485766595063329601220010426289654518957990907265744685366993530789457867618132860365922990882718428604529600228984964032099232874374222460511687639517298884151530863424383708182801530978733652489831846323498206754579884274193819080226605792517323786300061084936119993024406419351880798350828583190079546746, 59091690178918932344514115276463450512958932813218218982632215803645007725632433228335302191336528516004719934113340911282619669674183859556622253453438037922671421657556268489672698428628687182827799202195089425797921832876631069571596552627010811297580734592673896904169615512613359321830332981475621145567, 32964168544968959353510698558874273000919323952493281946099962533506939498208181688742588300431696600292065238290546021981276177298765942076660797531804323237105854415918460873117281806730392017410543607418493227646928072616545409798293188005310381977095538544131859435136369660686059342461896512437530856807, 61737408873612311772259012945956027132119115853001428319314314241907109256087958061546894753960238529596491497895380913312688665343145849089453317670932134264932588320215145124014649556912773725283429180364888438085909811849894942273496160144562117923210401864041673502617134476745582453861241094401041426371, 122241563213741464979968719064140698493039933777834740175915217094995940174961699629250317112942306596094029381030668383544628596970576878357003221534342655655846033783236204331593159741855823643227766075516440483252852793627722169633097234643306786225936030578609417530459491093717173598465178880769316178044, 78365694503332388406635946375239888121420777373504294295865419461438621745194084475076351926821762908738314158329198338224524128225720604464503818477193486444917215723917379663727939853085907074473084404201033606252087766780407179445044519351567149421025751850087276632425870891542111663028730543465980924674, 7591190426273359761941616407328929144928770113517275241093950141596156063756282617198447983218357512532106065008192311376773134252922140464779836357119244223237739097375626981010120297527408789567509829201223532075894871619418707161080401002015173531204361217534542306210196443834027818745071731611178116102, 59091690178918932344514115276463450512958932813218218982632215803645007725632433228335302191336528516004719934113340911282619669674183859556622253453438037922671421657556268489672698428628687182827799202195089425797921832876631069571596552627010811297580734592673896904169615512613359321830332981475621145567, 22664583763981843374303022518005994035657097278137383178209854110549233704242068066967000507844722717498970431366228359404935646715495523018056691695416834096458747223276018066714685309994835448613781345301588650015402046268973716286992844357802566430554011962162835995086846984162192044523380375361802448218, 78365694503332388406635946375239888121420777373504294295865419461438621745194084475076351926821762908738314158329198338224524128225720604464503818477193486444917215723917379663727939853085907074473084404201033606252087766780407179445044519351567149421025751850087276632425870891542111663028730543465980924674, 53663607942106145324856505634900952366446957335671164130522298044915630458145599229549689140621749659760530223576029477516300914481873420175142570078712350791717712867102285434801786722800007966464203566632283618002607953903231805867079414136989142782468226938194605757261613478374151072690376532757078133321, 61737408873612311772259012945956027132119115853001428319314314241907109256087958061546894753960238529596491497895380913312688665343145849089453317670932134264932588320215145124014649556912773725283429180364888438085909811849894942273496160144562117923210401864041673502617134476745582453861241094401041426371, 70480713168757924539311929940667780467970587842818445025524418743197460964600164745651995347296980394486922827896626755652508161710436441737113055312895245602294855426377720530563018422908207244199085965533115922382801317795420570385448911898023773378170687812737983373672258357899304606026326252164454917380, 26047568072817115878494867894312437678288420198021118255975389413872187727029430115159427279201003925435414525092202995249992275528836448324452587202712175796867393292136562948141422497412486302036882434258287763076036896726821940579522223779143091983761347952513295578107694805378100425301153924104306062998, 91787381900269188260278447720373303310489148968304685923635762638358985393364143392777737095065187700401801078356045890609652133551386013705471578679563002092971756426764956920204023299288270929657689101848397216780612154256911542955444439856286288474258681128430625157922381056568239575747179508619880090383, 19776578673353144927275864184783861309264188793640244818775000749693721784434736580334695236818666332736203761370924654937786145968319601425120102369903413307379455581007799093158364222412674609843713510282895193311987501448419353965575002099029023833110758779437479839173501503297218293482700872628654297986, 125326845192544440509276282506481573283240724338574897067845504723648638309772954799371511105917309088905368831611594229377570680550345769210665683357475682304404835864851287315570998264956738569042205063390711870398463147536649068917477705868473769928436248823742587056194359108616016055142099517087868052076, 32964168544968959353510698558874273000919323952493281946099962533506939498208181688742588300431696600292065238290546021981276177298765942076660797531804323237105854415918460873117281806730392017410543607418493227646928072616545409798293188005310381977095538544131859435136369660686059342461896512437530856807, 91787381900269188260278447720373303310489148968304685923635762638358985393364143392777737095065187700401801078356045890609652133551386013705471578679563002092971756426764956920204023299288270929657689101848397216780612154256911542955444439856286288474258681128430625157922381056568239575747179508619880090383, 61737408873612311772259012945956027132119115853001428319314314241907109256087958061546894753960238529596491497895380913312688665343145849089453317670932134264932588320215145124014649556912773725283429180364888438085909811849894942273496160144562117923210401864041673502617134476745582453861241094401041426371, 91787381900269188260278447720373303310489148968304685923635762638358985393364143392777737095065187700401801078356045890609652133551386013705471578679563002092971756426764956920204023299288270929657689101848397216780612154256911542955444439856286288474258681128430625157922381056568239575747179508619880090383, 19776578673353144927275864184783861309264188793640244818775000749693721784434736580334695236818666332736203761370924654937786145968319601425120102369903413307379455581007799093158364222412674609843713510282895193311987501448419353965575002099029023833110758779437479839173501503297218293482700872628654297986, 78365694503332388406635946375239888121420777373504294295865419461438621745194084475076351926821762908738314158329198338224524128225720604464503818477193486444917215723917379663727939853085907074473084404201033606252087766780407179445044519351567149421025751850087276632425870891542111663028730543465980924674, 61737408873612311772259012945956027132119115853001428319314314241907109256087958061546894753960238529596491497895380913312688665343145849089453317670932134264932588320215145124014649556912773725283429180364888438085909811849894942273496160144562117923210401864041673502617134476745582453861241094401041426371, 131040946974245026675658058355729944120000121321870000188404709281435584116278394991809905119413703272844512311536278017673800410331882203288245095027071614357027112724940054197254425819803021685988771514425910034927629090391726496207856325205247386443488436597264105916073735204891428125878570620071016241142, 32964168544968959353510698558874273000919323952493281946099962533506939498208181688742588300431696600292065238290546021981276177298765942076660797531804323237105854415918460873117281806730392017410543607418493227646928072616545409798293188005310381977095538544131859435136369660686059342461896512437530856807, 51881903993917641483997323850869811987536038225111627485870643872052008803086447178754190907042703266291567337065800056687478280445329593338406909415012963680420370144400172847215701319544343476968467495864151008758153702721097854774586711217305181423901628447556759613107726842767091009348289250122189785036, 119068023942915123834453890801615386465501339394239797127627292458405364408652779944528299230385822484839542992300412357529700493946856868435526246881940439551516659994051777777890838403084888735602598147329910405072187829956484467108868728797474058963491292723955648893332590334862441379387587421054617352375, 26047568072817115878494867894312437678288420198021118255975389413872187727029430115159427279201003925435414525092202995249992275528836448324452587202712175796867393292136562948141422497412486302036882434258287763076036896726821940579522223779143091983761347952513295578107694805378100425301153924104306062998, 7591190426273359761941616407328929144928770113517275241093950141596156063756282617198447983218357512532106065008192311376773134252922140464779836357119244223237739097375626981010120297527408789567509829201223532075894871619418707161080401002015173531204361217534542306210196443834027818745071731611178116102, 61737408873612311772259012945956027132119115853001428319314314241907109256087958061546894753960238529596491497895380913312688665343145849089453317670932134264932588320215145124014649556912773725283429180364888438085909811849894942273496160144562117923210401864041673502617134476745582453861241094401041426371, 108623843147477631119786732455662776965429219466020757714020187646998446057803775748746530453769487275081577395650842333746842202866631361612598186542004712441099158759758755509018326899678450576264260147179759845904840404687049322108190291649207031114338018219438814789866476631689164384325667004478217180777, 95099633707955315716043240047400293694963134315000154040199470050231601405242009961859755101495775900057639022200903957701742294339381243957985339026218101877491848982588498409542234475170365427534871365999205545899955987813295825723156661870032606446201831406566509782752822453980726176243545245206321306611, 133351192310202563419426901323994384713440205208151868715643142935400012258411897257974968750050191281830595418066271226357824322914122125910498597975000929812150922805102417484457821873962051137397158246187719558420161623509563016907599978340865914055121915450412988237550455073879054425886488125963620347686, 61737408873612311772259012945956027132119115853001428319314314241907109256087958061546894753960238529596491497895380913312688665343145849089453317670932134264932588320215145124014649556912773725283429180364888438085909811849894942273496160144562117923210401864041673502617134476745582453861241094401041426371, 131040946974245026675658058355729944120000121321870000188404709281435584116278394991809905119413703272844512311536278017673800410331882203288245095027071614357027112724940054197254425819803021685988771514425910034927629090391726496207856325205247386443488436597264105916073735204891428125878570620071016241142, 53663607942106145324856505634900952366446957335671164130522298044915630458145599229549689140621749659760530223576029477516300914481873420175142570078712350791717712867102285434801786722800007966464203566632283618002607953903231805867079414136989142782468226938194605757261613478374151072690376532757078133321, 105556932542245217837514115055775462864903512903809995567283778630584585678106941149852343294250017922855045081349459579094317034729691863434432162931660961638290043282138627957649917234937135249663297808688852822695562463651780284273851153820189241714031472163530769144140864209408438325377119537941221960531, 22664583763981843374303022518005994035657097278137383178209854110549233704242068066967000507844722717498970431366228359404935646715495523018056691695416834096458747223276018066714685309994835448613781345301588650015402046268973716286992844357802566430554011962162835995086846984162192044523380375361802448218, 22170132985413848490531783256781545736605099405646311268035819648933711512452780485867743670267230573816424442101847710685057703148406327241405695594207932241067458449670531595183417759103156231396266753674309067947713122567002400734977976535077517990037756703231259947021113899161279426849577708990870731796, 91787381900269188260278447720373303310489148968304685923635762638358985393364143392777737095065187700401801078356045890609652133551386013705471578679563002092971756426764956920204023299288270929657689101848397216780612154256911542955444439856286288474258681128430625157922381056568239575747179508619880090383, 78365694503332388406635946375239888121420777373504294295865419461438621745194084475076351926821762908738314158329198338224524128225720604464503818477193486444917215723917379663727939853085907074473084404201033606252087766780407179445044519351567149421025751850087276632425870891542111663028730543465980924674, 61737408873612311772259012945956027132119115853001428319314314241907109256087958061546894753960238529596491497895380913312688665343145849089453317670932134264932588320215145124014649556912773725283429180364888438085909811849894942273496160144562117923210401864041673502617134476745582453861241094401041426371, 39567326944456595185852131549239713048406760014375723185889668137264862184400625209347132385346771952845648844528249396652730647892825213067744420896877172327145941557401152582745524351689936262218846212578493068131068289265309178184007416700486534305431585962239171245639859026914854729185183441536829994448, 78365694503332388406635946375239888121420777373504294295865419461438621745194084475076351926821762908738314158329198338224524128225720604464503818477193486444917215723917379663727939853085907074473084404201033606252087766780407179445044519351567149421025751850087276632425870891542111663028730543465980924674, 37485766595063329601220010426289654518957990907265744685366993530789457867618132860365922990882718428604529600228984964032099232874374222460511687639517298884151530863424383708182801530978733652489831846323498206754579884274193819080226605792517323786300061084936119993024406419351880798350828583190079546746, 54654851876914080966669294072266680316237257314112763522717957624090555990759711312831465420820115888060496319530663148955963721935388528488503095888463911956642207510234857634578445323935685115331866533375908740782162677968051666308084412334476185841082309379065946002682963601103366953276426988653294184985, 42482427773147130194812689536913368638500081237478535489659215264193263428770540828147841848358274276495344365420108498381423756998877818209503381681969582766793835586739511090517781184229755174548633034965819780902871349417908442111735773596392436160814727974903411429784536931401566107378581772146035766032, 35930567221176949983032393471537465956255142659604274746127055228630351918767533995190245953000208387959040650822605531305590422970245280265227270608180544226270924727120053380823893678184112932417170980296052271050084089289663890989780614126562039368255291578422422201128945232924297966192833485833017989673, 23143986891216249914663826063115820607206746945143883358014118079713956430178113457314904759546411358799835088875030074243573599227417981305876359711490612127320931332708264875195350899805210021457591886105523051676279929638131079316059284303837762361507811984602430228290510398571565718816739452416463824733]

解法

このスクリプトは，フラグを一文字ずつ暗号化しています．このことを利用して，$n$ と各文字の対応を求めます．

フラグは HarekazeCTF{ から始まります．m0 = ord("H"), m1 = ord("a") なので，これらに対応する暗号文を c1, c2 とします．このとき，$m_i$ と $c_i$ の関係は次のようになります．

$$\begin{align*} &c_i \equiv m_i ^e \pmod{n} \\ &m_i ^e - c_i \equiv 0\pmod{n} \\ \end{align*}$$

このことから，$n = \gcd(m_0 ^e - c_0, m_1 ^e - c_1)$ と計算できます．そして，RSA 暗号の性質から，平文と暗号文は一対一になっているはずなので，一文字ずつ暗号化し比較することでフラグが求まります．

使用文字はルールの欄を見ると string.printable です．

solve.sage

import string


with open("output.txt", "r") as f:
    e = eval(f.readline().split("=")[1])
    cs = eval(f.readline().split("=")[1])

m0 = ord("H")
m1 = ord("a")

n = gcd(m0 ^ e - cs[0], m1 ^ e - cs[1])
table = [pow(ord(s), e, n) for s in string.printable]

flag = ""
for c in cs:
    flag += string.printable[table.index(c)]
print(flag)

$ sage solve.sage
HarekazeCTF{Can_you_Recover_with0ut_the_public_4nd_pr1vate_keys!?}