Let’s see what’s happening.

[+] Generating values...
afba99c04ee1f7b2b932e117942cda1c6066fbcc2e01ad8decbfe9c091a14f957fda0f6a4521b654a99515cd57f0f953237c14ef3a4723e250ffbcf665dbd531
We will encrypt the key three times, and you can even choose the value of e. Please put your distinct e values in increasing order.

Interesting, we can pick the values of $e$ here! We are given the server’s source code, let’s check it out.

from Crypto.Cipher import AES
from Crypto.Util.number import bytes_to_long, getPrime
from Crypto.Util.Padding import pad
import os


print("[+] Generating values...", flush=True)
flag = open("/app/flag.txt").read().encode()
key = os.urandom(160)
p, q, n, e = [], [], [], []
for i in range(3):
    p.append(getPrime(1024+512*i))
    q.append(getPrime(1024+512*i))
    n.append(p[i]*q[i])


cipher = AES.new(key[:16], AES.MODE_ECB)
print(cipher.encrypt(pad(flag, AES.block_size)).hex())
print("We will encrypt the key three times, and you can even choose the value of e. Please put your distinct e values in increasing order.")

try:
    e = list(map(int, input().split(" ")))
    assert e[0]>1
    assert e[1]>e[0]
    assert e[2]>e[1]
except Exception as e:
    print("sorry, invalid input")
    quit()

key = bytes_to_long(key)
for i in range(3):
    print(f"n{i}=",n[i], sep="")
    print(f"c{i}=", pow(key, e[i], n[i]), sep="")

These lines in particular stand out.

key = os.urandom(160)
p, q, n, e = [], [], [], []
for i in range(3):
    p.append(getPrime(1024+512*i))
    q.append(getPrime(1024+512*i))
    n.append(p[i]*q[i])

So the key used in the AES encryption is a random bytestream of length 160, which means the bit length is approximately 1280~ bits. The other part is that the primes $p$ and $q$ generated are first 1024 bits, then 1536 bits, then 2048 bits. This means that the moduli will be 2048 bits, 3072 bits, then 4096 bits.

Given we can choose values of $e$, and the server uses different keys, this seems like a perfect setup for a broadcast attack.

Broadcast AttacK: Quick Recap

Håstad’s broadcast attack is an attack which utilises the chinese remainder theorem, that says if you have an unknown that has been put through several pairwise coprime moduli, there exists a unique solution $X \pmod{\mathcal{N}}$, where $\mathcal N$ is the product of all the moduli. The pairwise coprime part is almost guaranteed in RSA, so no need to worry about that.

\[ m^e \equiv c_1 \pmod{n_1} \] \[ m^e \equiv c_2 \pmod{n_2} \] \[ \vdots \] \[ m^e \equiv c_k \pmod{n_k} \] …means that we can find a unique solution: \[ m^e \equiv X \pmod{\prod_{i=1}^{k}n_i} \]

So if you can gather enough moduli such that the product of all moduli is larger than $m^e$, then the original message can be recovered by directly taking the $e$th root of $X \pmod{\mathcal N}$. Now normally in such an attack, the value of $e$ is fixed, e.g. $e = 7$ for all moduli. However, here, the 3 values of $e$ we send to the server must be distinct and greater than 1. So how can we leverage this?

First, recall that, \[ (c)^r \equiv (m^{e})^r \equiv m^{er} \pmod{n} \] Keep this in your mind. It may seem obvious, but it is crucial for this attack to work. We need to find a value of $e$ such that $m^e$ is less than the product of all moduli. We know the bit length of the moduli, so we can make a few estimates for this part as such,

This means that the moduli will be 2048 bits, 3072 bits, then 4096 bits.

When two numbers are multiplied, the bit length of the result can be estimated by adding the bit lengths of the two numbers. This means if we add the bit lengths of the three moduli, we get a modulus $\mathcal N$ that is around 9216 bits! Now remember that the message being encrypted is 160 random bytes which means 1280 bits as an integer. Since exponentiation is just repeated multiplication, we just need a number such that when we do $m^e$, $e\cdot1280 < 9216$. This means we can have $e$ up to $7$.

But, setting $e$ to $7$ won’t help, because the chinese remainder theorem works when an unknown but constant variable has been put through several moduli. Note that, since we are not using decryption via $c^d \pmod{n}$, we don’t need to worry about $e$ being coprime to $\varphi (n)$ anymore. So $e$ can be any number we want, just not 1 and we can’t repeat $e$. This is important because it allows us to pick even values of $e$.

This is where that first idea comes back, because we can still perform operations on the ciphertext. So then, we can pick 3 values of $e$ such that… \[ (m^{e_1})^r \equiv m^{e_3} \pmod{n_1} \] \[ (m^{e_2})^s \equiv m^{e_3} \pmod{n_2} \]

For example, if we take the values of $e$ to be $[2, 3, 6]$, we can get,

\[ (m^{2})^3 \equiv m^6 \pmod{n_1} \] \[ (m^{3})^2 \equiv m^6 \pmod{n_2} \]

Which means we now have a constant variable $m^6$ under different moduli, and we can apply the CRT! Let’s write a script to do this.

from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from gmpy2 import iroot
from sympy.ntheory.modular import crt

HOST = "choose.chal.cyberjousting.com"
PORT = 1348

context.log_level = "debug"

server = remote(HOST, PORT)

server.recvuntil(b"[+] Generating values...\n")
ct = server.recvline()
server.recvuntil(b"We will encrypt the key three times, and you can even choose the value of e. Please put your distinct e values in increasing order.")
server.sendline(b"2 3 6")

N = []
C = []
# ignore the messy way of collecting n and c
server.recvuntil(b"n0=")
for _ in range(3):
    n = server.recvline()
    print(f"{n = }")
    if _ != 0:
        N.append(int(n[3:len(n)]))
    else:
        N.append(int(n))
    c = server.recvline()
    print(f"{c = }")
    C.append(int(c[3:len(c)]))

for i in range(3):
    print(f"{N[i] = }")
    print(f"{C[i] = }")

e = 6
# Cube the first ciphertext mod n0 to get m^6 mod n0
# Square the second ciphertext mod n1 to get m^6 mod n1
C[0] = pow(C[0], 3, N[0])
C[1] = pow(C[1], 2, N[1])

# Apply the CRT to the list of ciphertexts and take the 6th root 
m_exp_e, mod_product = crt(N, C)
m, exact = iroot(m_exp_e, e)

key = long_to_bytes(m)
cipher = AES.new(key[0:16], AES.MODE_ECB)
pt = unpad(cipher.decrypt(bytes.fromhex(ct.decode())), AES.block_size)

print(pt)
server.interactive()

$ python pwner.py
[+] Generating values...
afba99c04ee1f7b2b932e117942cda1c6066fbcc2e01ad8decbfe9c091a14f957fda0f6a4521b654a99515cd57f0f953237c14ef3a4723e250ffbcf665dbd531
We will encrypt the key three times, and you can even choose the value of e. Please put your distinct e values in increasing order.
2 3 6
n0=16053780180419405872728253065855953345138801691450431752671270462799329927186257613822811034570966514566371297913679659571988117146282361346111799139061497826178078919988204293800281700987503515319159415365966448198610328945112201215915148698132902827328009833613573246444025137901571047803479594756281436882319288269630476040862677022402246952199548776974688785302035792576916819985754333173763723087684310117992087132679439261784464808280283024417672591663819281213327609250980427239951298315584799843854531926772253856734384856368597671100809224054080090332524230003831785123370845544892628950184701169828862596609
c0=6636461499939556936491616166931981849929130927669893173709764272600880027695186593568243935581516972919867922391074848887943944808241359034726065159297329441467331969379040888759011164538695809980060706962516838180623982556084810135486914872780058759879686832777079733432944976153317955051902170696096105854783901522108699692345922406370621241657446067429128948861697755315420035304637805215575097392879509271351322169089619567380727046485040456904651340395039200139195797981782444711484595940061519793726566743385275327886992711063572972272193039686169831113292364134352208375851740641507668120579971744890975015944
n1=2988743317016368901176496252875145697755799092897753364462456947146274168482616195204757058872219851618835370958463203303996415034125346809237018110530523995443299290035365271021675643272991908611950163009112922180281398351318956427198105480264144612294134965091295856030413467547514616927917155309865605741681002441635908113577687450376008658104561108157824964433656860284302662646964415822260562106716799891575265841884860051054003999383322637450682269088517318502234197849438790192709992350215287234309188350950815866161948645668036086253873939610059991289999621052431210748838157795623817256576746572418145553354466427133074030936045200973759045012228158481153215177771931110078481667122015336812243078251607151716317080970096696876776628513237877361576276809642137487785104878925258965206418521792802082502035808649004403423318075485951013474927255428153320984846078203571370117677714357123871425033005655377237797316737
c1=1122200338066657596744960292076687145436895903161418899266667794471009173719197396996372419520337391570875744388393788336737365156752807545915102925825803940759164505452461696957681535236546209778548548687195440979550954666769114621199462113273084464134862228763295803879983281975406073962335057830812158398916598726232339555245644327774862456794147163853737579482368939062092789263476555267660764801011474572137164685006714757575005465944722675883598826420554939292223295515624282828189354386430668048524364053935194550766556522241609086825979425588285564476349509883035729239596131102211145650176476983346829857163657576891963893816764105655527359465901806041161522725347477975284968519331321645476201929790636273839143993886102214441824671438338481676615151957101257108079403469829745918561467598555021268857233241279835956162300315662835989144780331578229508864599617006939151793300041520911438279789902989046275585669018
n2=410690902888668881500669405551596225411160111083216664969155095694591589118798728413929423544561113303863893501826973600953174134763361263432681072643893928457081197744010262737740703972183818387581849537813194624564899862925477144164870760878185585410780410006112644599625317266449094087270590565530571308121445699584158136730922128605426142810586536779204728365302203680751445533672913017613259934224916316200344806174688837688511936629516369305932245061660938886950212746743000315200829999198687786057226333702640771547038793307233860879473410452243083686340091869735789700901818754089020455261769975732379578084388821441210240523788161828991858310205902407304290543916194069625392061648596486030004717060083432356121420205805413242775999873175590769024662765925747738634392295197824212622367886553137223891703332945850790323103616810064887076875527502188643825681312249778455325836910245116232201596770522057860175541484565432672122848682593710646734580790985268320798735234051685073474003695187408853244461275153172671133298924753108549431768449579350235874577760528883740299326610542187466291455178976349510713504077046707470781867616786471375404156864133004128983653822443146534084128870448944326790587280398692944232464134573
c2=22878957615362192677557434255084742993171984894187683995769900300990765231289615791788860959587576648468352260642078563244433654067428455092142540727614201257829468565714936384025031091685240619789334187083071396144922997171427613718877658208106135103646315089538359925074402989994752350968537972617184837307800025507805554580268491040219035602521660340868913902067564558661830208485036436081310500613631734205076930292301901677718839540523012878729394648746918753439181772682566428326085130271751976130590482847015330315963172133592519975244583894349559780179304124733694725706657510151960552885987701997286979336215683005438101198955481454014403550008857925316139802717602521580981541358051392848900328400047826689509724208033284456091204097591612945891045440541922756218489586739601661925856812843605158586893590372501685531976696233284489827182787137096961011463926873252428146539006157473376094511219890852432673129505207953100065009208299590657646549314359953699005442098103785033496088687977792700920670213683267645105138375841376174772423842688335338763718665539099017478869306959328643983510977086785611616468542248657447638606098348636219992127562278639693092107258355695481895840037602764474473540696556289
byuctf{Chin3s3_rema1nd3r_th30r3m_is_Sup3r_H3lpful}

Flag: byuctf{Chin3s3_rema1nd3r_th30r3m_is_Sup3r_H3lpful}