LA CTF 2024
Below are writeups for all the cryptography challenges. Big shoutouts to PBR at UCLA for hosting this incredible event.
valentines-day
Starting off with the classical ciphers, we have a vigenere cipher encrypted with a very long key of known length.
Br olzy Jnyetbdrc'g xun, V avrkkr gb sssp km frja sbv kvflsffoi Jnuc Sathrg. Wkmk gytjzyakz mj jsqvcmtoh rc bkd. Canjc kns puadlctus!
L xyw fmoxztu va tai szt, dbiazb yiff mt Zzhbo 1178 gyfyjhuzw vhtkqfy sniu eih vbsel edih tpcvftz, xcie ysnecsmge hbucqtu qt wcorr crzhg-olhm srr gkh gdsjxqh gnxxl rtr guez jewr klkkgak dx uuka nnv hmvwbj gmv glz fvyh, jueg eww oq i wuqglh Z lrigjsss ynch xun esivmpwf: "oof hvrb frtbrq it Kcmlo?"
C ltzihfvxsq ghp abqs qrfzf glvx de HN bnty gocr gr:
Eiaj zek rvocf vnriiu ob Puiza. Xegjy webrvbvrj. Frat s vgxhidm kepldrv gbq phxgv.
Ehlb'w wuhu C ixyzchlr, ilc srez foq e wxzb sdz nrbrb. Eej W und siieesx nd pvvgb zvr pooi. B fox wc nrax v pedgei aex phvqe. Hqdru pc tvvtrv, C zyoxvxsq ghq wyvbg yzgmex KEKN=/ife/lgcyr/qg/ejl:$TNXC, eej hurn mlp qowtswvqn:
wrm ~cuamyh/umlofikjayrvplzcwm.gdg | pzwj
ropgf{qvjal_dfuxaxzbk_gbq_jeci_hdt_nr_hdr_eexij}
Yiqqeefl, cywfylnt zlrv finqvyq sqii sm oncw.
Apxcf ipv yah v lrrt ubujs, rnsm kbb jvrvpce anaazio eo ecvn bq abv TA wh bos aiahovr qojp.
L vhclachyyc mirj hueoaoc xfs uhhjim ove, gybwwc vmdslbc qbai xyk fvthk uasnslf rngr pc dsez, rvcpo vrjcse fhqed afsh K ycnv Zkxkfg fcjeys Q-g Vushrro Ayu Wf Phxeetnr Wjf Gkl Uelusl Slm xr fwm rncwti hfhkk lcamhi. D ary wa gozig wfcwe. Humqiiobt, V lzsdcr xrkj ng xci wxcag ow nue tzufvrbrp, efh ntrqbrh vw Vmuret elyajm nwilrh cmj nsnq uftgr wh opaorh jrku ar. "V wbpw akttp ybx," oy vvfcyl. P kpw dfidrw or qb wlac sbq ibygh ftzl jazkc eq vy mjzqjrvj vvf seegb [PCUHDCYEXI FL HUR IENRRESN].
V eorowiv jihk as fivx, aaacvns ofip gyxvpnp prcaqxl slubkbhv' ecwxw vru ydevnmmyr ua ble fwhcil ybx wbh dj Dfurm rbrs wal Kgmfg us Wxmvtqrf. Bab D gmifx hrrni knog Rgrikr kuv qhbfi jr de hnvl. Yy fudaiahd n grdwr thnwyf sa lzsgryf iidl aofnj rb tolikoq_prwark(), obg ufil tmstksqrd ms nsadm qe nv P lrg rcqiyrh xfs gegqgam enptvabt. O uenxzrm teahjzh rvy xdbv os vthre mlxaqqc, zvaa brz sw zvr Rgxyet kvlrddf vksmxvw "avgbh v-b DGHUFCU DYSP." W ntzcq skieobt ghw dmuf, pxu gx fljykkr ng mx: "Tpcmtawibq kyebcr." C ahws "vk -t xsba" olh utu qflc gnr qvxyyqv ouotymlu.
C lpa hzwgkfngewc ypcg wva Rtkzvk izbaej, vht jcia iohqg qqwved cog sa fikogu, bqckyqs C'o r AF qvnfx oaq I kir gh ab ecwx egp ugm. Fhdwiywy, T aew bql iw Xeuyza'g rpmbyw edb bszg apw zoyrjet. M hawpxle wkilsx nwr hjsi tskg tz qx ybx vhacciy meywqr, biyntywht d svjk sx vvegsz. Oyo xykb V gudnoh kmmgcd nvjyej oaq surcgasg.
"Xcppshi ku al bfymnp." Eroirg hjbfxb. "Mic'cs bebs cx fx tyv. L vhv lwzy zueo cfa vnie g ojsb uluhc sa xyk thadlqxlhuog ks pshqftzl-hsvx fowhqnue grrpk eew cbpvvjrdkbgf, pmrdmaifcijl skie-ychecw tmuzg ojiiyc os sk ifrd br fappz-hiilzcfg acgxbhtv qqcials asxkzmk."
A kuoztzvvj oaq bgkfib whnd glz gfxbre oq lbq cziwyr.
"Lsp qre pr joexrrzba urw lrx kgx yxps. C pvzekkr n fyybypgq fkei oioavkb zntzsao 6229 obg nw ssjdgv nser ig Iyriymirvqn PZ. B uohb fcj xm yhsj cvyx L pvv'l ziez lsp. M ngg zrrktt xcgncct cjy."
Z miyceo egb ziryaq vros yog rlej. "Lraczs?"
"Lhs..." Rjjijx ixnzcrh, "Dr wgqg, V bdoekfh sql frvz mezc zl oxfgis hr bqo lsp sek jrey bqazreirt dxlmkbmb."
"Qphh?" X wrinxrasb.
Ijzlzl dsntrh wetq wa uiy kcegf, mgxymik. "Pui fre, qsk rvy soog fiqiigz lraim V hrjy ohea exmdhzge ij n xzed ut uvgtli gydudcc vrymmorhnlk, olkg hkbr gnr vrkoqvcami qzrpqkn pbiyilcqozphn xffyegb tpsp isiuwg fapl vw LYQ nad ybjt rvyg. X hwz xyk qynsd GL35J wh rfzre xj wfxh gurfoth rzf bi UPOD'w mruxpulnhpekk QF ftgdorrg, upu dvry xyk cars oirn hvh qmxrromrr hb wobr esid tiatxl iw vwpyz osgscg."
"Nlnc'g... Rldm'z qehcfyvfgi..." Z yovq.
"Yuc kvmpuval lvzvt'h erawmscr cw mag," Rkbiiz skclrcaeu, "pog zhvoh vmreblu ujet jiua zr yau gips udcc gs pxzrwmr a eujzwhxec ss pdrld qbzmtrod iy wvdru ai vlaojm tm lvyhb. Hb hcs yqwlzkloaj jlvx knog zegvn?"
"Yf...." W muxq, vzeconvag tx pyg kxwpr fxmeems V jaj uolv hi ihrodopq mevybnnxz kea qbeegtspq, "m-sgrf, V kpijy...?"
Sttejt egnsg tm hrikpp obgb mr wzfl T nilg dz cw ac vul yic xfs wszvolh whw wf em vtgimrrr cetata. "Esgb gy, pah osxkhurr hi pgzf finir hjae zvr joifq."
sfilph: hgwsw://oan.kcrxvx.xsd/x/ipya/oowqcbnu/s2b4md/hc_vddreiwnak_kwwi_rlr_gn35p_wobny/Plugging the ciphertext into an online bruteforcing tool we find an approximation of the key
naverfonmagiceyouuphevergonnaletyoudownneverlonnaeunaroundanddezertyoynevergonrumakeyougryndvergomnasaygoocqyenevergonnatellalieandhurtyouihopeyouenjoyedthissongThat looks... familiar. Now using CyberChef with the full key and proper spelling, we get
Flag
lactf{known_plaintext_and_were_off_to_the_races}selamat pagi
Another classical cipher. This one I solved mostly by inspection by accumulating enough substitutions to guess the word, and then correcting any spelling mistakes using Google Translate.
Efe kqkbkx czwkf akfs kdkf qzfskf wzdcjtfk
Ieqku kqk akfs ikxj kck akfs wkak ukikukf :Q
Lzfqztk ukdj kqk qe wefe: bkvim{wzbkdki_ckse_kckukx_ukdj_wjuk_kfkbewew_mtzujzfwe}For example:
Since the flag format was
lactf{}, that gives us 5 letters for free.I guessed that the word for flag (
bendera) would be in the last line, and there was only one word with the matching number of characters.The end of the flag was beginning to look like the words "frequency analysis", which in Indonesian would be spelt
analisis frekuensi.A search through the 100 most common indonesian words for short palindromes gave us a few more letters.
Flag
lactf{selamat_pagi_apakah_kamu_suka_analisis_frekuensi}very-hot
We have a multiprime RSA problem,
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
# from flag import FLAG
# FLAG = bytes_to_long(FLAG.encode())
p = getPrime(384)
while not isPrime(p + 6) or not isPrime(p + 12):
p = getPrime(384)
q = p + 6
r = p + 12
n = p * q * r
e = 2**16 + 1
ct = pow(FLAG, e, n)
print(f"n: {n}")
print(f"e: {e}")
print(f"ct: {ct}")but the prime factors of n are related by a simple equation. In particular p is a root of the polynomial
which we can solve easily in Sage to reveal the factorisation of n.
#!/usr/bin/env sage
from Crypto.Util.number import *
# Solve polynomial p*(p+6)(p+12) to get p
n = 10565111742779621369865244442986012561396692673454910362609046015925986143478477636135123823568238799221073736640238782018226118947815621060733362956285282617024125831451239252829020159808921127494956720795643829784184023834660903398677823590748068165468077222708643934113813031996923649853965683973247210221430589980477793099978524923475037870799
solve(x * (x + 6) * (x + 12) - n, x)
p = 21942765653871439764422303472543530148312720769660663866142363370143863717044484440248869144329425486818687730842077
q = p + 6
r = p + 12
e = 65537
ct = 9953835612864168958493881125012168733523409382351354854632430461608351532481509658102591265243759698363517384998445400450605072899351246319609602750009384658165461577933077010367041079697256427873608015844538854795998933587082438951814536702595878846142644494615211280580559681850168231137824062612646010487818329823551577905707110039178482377985
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse_mod(e, phi)
print(long_to_bytes(pow(ct, d, n)))Flag
lactf{th4t_w45_n0t_so_53xY}hOlyT
We are provided with an RSA problem, and an oracle which, when provided with a quadratic residue \(x\) such that there exists \(x_1, x_2 \in \mathbb{Z}\) with
will return one of
where \(u, v\) are the Bezout coefficients of \(p\) and \(q\).
from Crypto.Util.number import getPrime, bytes_to_long
import random
def legendre(a, p):
return pow(a, (p - 1) // 2, p)
def tonelli(n, p):
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
if s == 1:
return pow(n, (p + 1) // 4, p)
for z in range(2, p):
if p - 1 == legendre(z, p):
break
c = pow(z, q, p)
r = pow(n, (q + 1) // 2, p)
t = pow(n, q, p)
m = s
t2 = 0
while (t - 1) % p != 0:
t2 = (t * t) % p
for i in range(1, m):
if (t2 - 1) % p == 0:
break
t2 = (t2 * t2) % p
b = pow(c, 1 << (m - i - 1), p)
r = (r * b) % p
c = (b * b) % p
t = (t * c) % p
m = i
return r
def xgcd(a, b):
if a == 0:
return 0, 1
x1, y1 = xgcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return x, y
def crt(a, b, m, n):
m1, n1 = xgcd(m, n)
return (b * m * m1 + a * n * n1) % (m * n)
def advice(x, p, q):
if legendre(x, p) != 1:
exit()
if legendre(x, q) != 1:
exit()
x1 = tonelli(x, p) * random.choice([1, -1])
x2 = tonelli(x, q) * random.choice([1, -1])
y = crt(x1, x2, p, q)
return y
def main():
p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 65537
m = bytes_to_long(b"lactf{redacted?}")
ct = pow(m, e, N)
print(f"ct = {ct}")
print(f"N = {N}")
print(f"e = {e}")
while 1:
x = int(input("What do you want to ask? > "))
ad = advice(x, p, q)
print(ad)
if __name__ == "__main__":
main()The observation here is that \(x = 1\) is a valid input, which reveals to us
Then since \(a + b = 2uq \pmod n\) shares a common factor with \(n\), we can recover \(q\) as \(\mathrm{gcd}(a + b, n)\).
Flag
lactf{1s_r4bin_g0d?}prove it!
Here we are working in the field \(\mathbb{F}_p\) for a 1024-bit prime \(p\). We are given the values
for \(g, s, \alpha \in \mathbb{F}_p\) unknown, as well as the coefficients of a polynomial \(t \in \mathbb{F}_p\left[x\right]\) of degree 7. To obtain the flag, we must find non-trivial elements \(f, h, f_\alpha \in \mathbb{F}_p\) such that \(f^\alpha = f_\alpha\) and \(f = h^{t(s)}\). We are allowed two attempts, and if we fail in the first attempt, then \(t(s)\) is given to us and a new polynomial \(t\) is chosen by the server.
#!/usr/local/bin/python
import random
from Crypto.Util.number import *
flag = "lactf{??????????}"
p = 171687271187362402858253153317226779412519708415758861260173615154794651529095285554559087769129718750696204276854381696836947720354758929262422945910586370154930700427498878225153794722572909742395687687136063410003254320613429926120729809300639276228416026933793038009939497928563523775713932771366072739767
if __name__ == "__main__":
s = random.getrandbits(128)
while GCD(s, p - 1) != 1:
s = random.getrandbits(128)
alpha = random.getrandbits(40)
g = redacted
ss = [pow(g, s**i, p) for i in range(1, 8)]
alphas = [pow(g, alpha * s**i, p) for i in range(1, 8)]
print(f"Use these values to evaluate your polynomials on s")
print(f"Powers of s: {ss}")
print(f"Powers of alpha*s: {alphas}")
tries = 0
while True:
if tries >= 2:
print("Fool me once shame on you, fool me twice shame on me")
break
print("Can you prove to me you know the polynomial f that im thinking of?")
target = []
for i in range(8):
target.append(random.randrange(p))
print(f"Coefficients of target polynomial: {target}")
ts = sum([(pow(s, 7 - i, p) * target[i]) % p for i in range(len(target))]) % p
f = int(input("give me your evaluation of f(s) > ")) % p
h = int(input("give me your evaluation of h(s) > ")) % p
fa = int(input("give me your evaluation of f(alpha * s) > ")) % p
if f <= 1 or h <= 1 or fa <= 1 or f == p - 1 or h == p - 1 or fa == p - 1:
print("nope")
exit()
if pow(f, alpha, p) != fa:
print("Failed f_alpha != fa")
if f != pow(h, ts, p):
print("Failed h_ts != f")
if pow(f, alpha, p) != fa or f != pow(h, ts, p):
print(f"failed! The target was {ts}")
tries += 1
continue
print(f"you made it! here you got {flag}")
breakTo avoid ambiguity, let \(t_1\) and \(t_2\) be the polynomials chosen by the server in the first and secound rounds respectively. Observe that after the first round, we know both the coefficients of \(t_1 \in \mathbb{F}_p\left[x\right]\) and the value of \(t_1(s)\). Hence \(s\) is a root of the polynomial \(t_1 - t_1(s)\). This allows us to recover the secret element \(s\) (if there are multiple roots, then choose the root closest in size to 128-bits as the most likely candidate). Then, since we know both \(s\) , \(g^s\) and \(\phi(p) = p - 1\), we can recover \(g\) by taking
where \(d = s^{-1} \pmod {p - 1}\). This reveals to us the redacted value \(g = 2\). Similarly by taking
we can determine the value of \(g^\alpha\).
We now have enough information to answer the server's challenge in the second round. Since \(s\) and \(t_2\) are known, then \(t_2(s)\) is known. Put
Then
as desired. Below is an implementation of the solution in SageMath.
#!/usr/bin/env python3
import itertools
from pwn import *
p = 171687271187362402858253153317226779412519708415758861260173615154794651529095285554559087769129718750696204276854381696836947720354758929262422945910586370154930700427498878225153794722572909742395687687136063410003254320613429926120729809300639276228416026933793038009939497928563523775713932771366072739767
def find_g(ss, alphas, coeff_1, ts_1):
K = GF(p)
x = PolynomialRing(K, "x").gen()
poly = sum([(x ^ (7 - i) * coeff_1[i]) for i in range(len(coeff_1))]) - K(ts_1)
root = poly.roots()
idx = min((abs(len(bin(s_)) - 130), i) for i, (s_, _) in enumerate(root))[1]
print(root)
s = root[idx][0]
print(f"Chose s = {s}")
d = inverse_mod(Integer(s), phi)
gs = ss[0]
g = pow(gs, d, p) # g = 2 fixed?
return g, s, d
def evalpoly(base, coeff):
# Assuming base is ordered lowest powers to highest powers
# coeff is ordered highest powers to lowest powers
return prod(pow(base[7 - i], coeff[i], p) for i in range(len(coeff))) % p
def evalpoly_additive(point, coeff):
return sum([(pow(point, 7 - i, p) * coeff[i]) % p for i in range(len(coeff))]) % p
# First round: Fail deliberately, but keep track of parameters and hints
conn = connect("chall.lac.tf", int(31179))
# conn = process(["python", "server.py"])
print(conn.readline())
ss = conn.readline()
ss = eval(ss[len(b"Powers of s: ") :].decode("ascii"))
alphas = conn.readline()
alphas = eval(alphas[len(b"Powers of alpha*s: ") :].decode("ascii"))
print(conn.readline())
coeff_1 = conn.readline()
coeff_1 = eval(coeff_1[len(b"Coefficients of target polynomial: ") :].decode("ascii"))
conn.sendafter("give me your evaluation of f(s) > ", "2\n")
conn.sendafter("give me your evaluation of h(s) > ", "2\n")
conn.sendafter("give me your evaluation of f(alpha * s) > ", "2\n")
ts_1 = conn.readline()
ts_1 = eval(ts_1[len(b"failed! The target was ") :].decode("ascii"))
# Round 2
# Gather data like in round 1
print(conn.readline())
coeff_2 = conn.readline()
coeff_2 = eval(coeff_2[len(b"Coefficients of target polynomial: ") :].decode("ascii"))
# First solve rsa problem for g
g, s, d = find_g(ss, alphas, coeff_1, ts_1)
g_alpha = pow(alphas[0], d, p)
ss_full = [g] + ss
alphas_full = [g_alpha] + alphas
# Want f = g^ts_2
ts_2 = evalpoly_additive(s, coeff_2)
f = pow(g, ts_2, p)
fa = pow(g_alpha, ts_2, p)
h = g
conn.sendafter("give me your evaluation of f(s) > ", str(f) + "\n")
conn.sendafter("give me your evaluation of h(s) > ", str(h) + "\n")
conn.sendafter("give me your evaluation of f(alpha * s) > ", str(fa) + "\n")
print(conn.recvall())Flag
lactf{2kp_1s_ov3rr4t3d}budget bag
Let \(n\) be the number of characters in the flag. In this challenge, we are given \(n\) points on an unknown elliptic curve \(E / \mathbb{F}_p\) of the form
where the \(P_i\) are random points of \(E(\mathbb{F}_p)\) and the \(f_i\) are the character codes of the flag after transformation by a simple invertible padding scheme. In addition to the \(n\) points, we are also given their sum in \(E(\mathbb{F}_p)\)
import random
from hidden import DollarStore
p = 95773813056613526295315889615423014145567365190638271416026411091272805051097
def legendre(a, p):
return pow(a, (p - 1) // 2, p)
def tonelli(n, p):
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
if s == 1:
return pow(n, (p + 1) // 4, p)
for z in range(2, p):
if p - 1 == legendre(z, p):
break
c = pow(z, q, p)
r = pow(n, (q + 1) // 2, p)
t = pow(n, q, p)
m = s
t2 = 0
while (t - 1) % p != 0:
t2 = (t * t) % p
for i in range(1, m):
if (t2 - 1) % p == 0:
break
t2 = (t2 * t2) % p
b = pow(c, 1 << (m - i - 1), p)
r = (r * b) % p
c = (b * b) % p
t = (t * c) % p
m = i
return r
class EllipticCurve:
def __init__ (self, a, b, p):
self.p = p
self.a = a
self.b = b
def getPoint(self, x):
ys = (x**3 + self.a*x + self.b) % p
if legendre(ys, self.p) != 1:
return None
y = tonelli( ys ,p)
return CurvePoint(x, y, self)
class CurvePoint:
def __init__(self,x,y, curve):
self.curve = curve
self.x = x % curve.p
self.y = y % curve.p
def __str__(self):
return f"({self.x},{self.y})"
def __eq__(self, other):
return str(self) == str(other)
__repr__ = __str__
def __add__(self, other):
x1,y1 = self.x, self.y
x2,y2 = other.x, other.y
if x2 == 0 and y2 == 1:
return self
if x1 == 0 and y1 == 1:
return other
if x1 == x2 and y2 == self.curve.p - y1:
return CurvePoint(0, 1, self.curve)
if x1 == x2 and y1 == y2:
lam = ((3*pow(x1, 2, self.curve.p) + self.curve.a) * pow(2* y1, -1, self.curve.p))% self.curve.p
else:
lam = ((y2 - y1) * pow(x2 - x1, -1, self.curve.p)) % self.curve.p
x = (lam**2 - x1 - x2) % self.curve.p
y = (lam*(x1 -x) - y1) % self.curve.p
return CurvePoint(x, y, self.curve)
def scalar_mult(x, n, ec) -> CurvePoint:
Q = x
R = CurvePoint(0,1 ,ec)
if n == 0: return R
if n == 1: return x
while n > 0:
if n % 2 == 1:
R = R + Q
Q = Q + Q
n = n // 2
return R
flag = "lactf{REDACTED}"
flag = flag.lstrip("lactf{").rstrip("}")
flagarray = [((random.randrange(2**10) >> 8) << 8) + ord(flag[i]) for i in range(len(flag))]
ec = DollarStore()
points = []
while len(points) < len(flagarray):
x = random.randrange(p)
point = ec.getPoint(x)
if point != None:
points.append(point)
s = scalar_mult(points[0], flagarray[0], ec)
for i in range(1,len(flagarray)):
s += (scalar_mult(points[i], flagarray[i], ec))
print(f"s= {s}")
print(f"points = {points}")Since the hidden elliptic curve \(E\) is defined by a Weierstrass equation with unknown coefficients \(a, b\), we can substitute in two of our given points into the equation
to recover the hidden values \(a\) and \(b\). This reveals to us that \(a = b = 0\), and so our elliptic curve is in fact the singular curve
The elliptic curve group for such curves has a particularly simple structure provided the gradient of the tangent line(s) at the singularity are in the field \(\mathbb{F}_p\): they are either isomorphic to the additive group \(\mathbb{F}_p^{+}\) or the multiplicative group \(\mathbb{F}_p^{\times}\) depending on whether the curve has a node or a cusp at the singularity. Silverman (Proposition III.2.5) provides details of a proof and an explicit formula for the isomorphism. In our case, our curve has a cusp at the origin and the gradient of the tangent line is zero. Hence the map
is an isomorphism. Applying \(\phi\) to each \(\left[f_i\right]P_i\) as well as \(s\), we obtain the following linear equation in \(\mathbb{F}_p\)
with \(n\) unknowns. The solution space forms a \(n - 1\) dimensional affine subspace of \(\mathbb{F}_p^n\). We can lift the solution to a lattice in \(\mathbb{Z}^{n}\) by appending arbitrary linear combinations of \(p\mathbf{e}_1,\ldots,p\mathbf{e}_n \in \mathbb{Z}^n\). Our solution will then be a lattice vector with all coordinates lying the range of the padded character codes. Such a vector can be found by a CVP solver provided we know a suitable estimate for the center of the range. For this, we assume the flag format consists of reasonable ASCII characters, and so each of the \(f_i\)'s should lie within the interval \(\left[65, 890\right] \subseteq \mathbb{Z}\).
#!/usr/bin/env python3
# Initial implementation in Sage to reduce apply the isomorphism and reduce the problem to F_p
s = (
4690331917760414380672348505790486524786128272326163170078478915876334878778,
77902523131087061897126273610460347147805642819184490444996378236375931739511,
)
p = 95773813056613526295315889615423014145567365190638271416026411091272805051097
points = [
# large challenge output elided #
]
def find_ec_params(p_1, p_2):
x_1, y_1 = p_1
x_2, y_2 = p_2
a = ((y_1**2 - y_2**2) - (x_1**3 - x_2**3)) * inverse_mod(x_1 - x_2, p)
a = a % p
b = (y_1**2 - x_1**3 - a * x_1) % p
return a, b # a = b = 0
K = GF(p)
def isomorphism(pt):
x, y = pt
return (x * inverse_mod(y, p)) % p
weights = list(map(isomorphism, points))
target = isomorphism(s)# Implemention of the CVP portion in Julia
using AbstractAlgebra
using LinearAlgebra
function solve()
p = 95773813056613526295315889615423014145567365190638271416026411091272805051097
K = GF(p)
weights = BigInt[
40934699560187760118076789839292640635422518557448839865404745220866778025546,
78310223071590492194236922321229075543476357564542955520452209526227950970041,
91705555999958172847918714712488726144644562704604773757857932534858806325518,
42501728239045823811266018530645187132678419583755394096925398410774167785495,
46119371924278215331040469610168125127482006988589418572015362580083398169762,
2330179126243704396521139915466741247281559783872381157453234051670693598729,
34253065139905257255915277994868632884775435324309315594946460625587903576019,
68623145750851611402492363714838439447614096997584503429073048348890609090063,
55215455687459981679753425402241794055048803159690691698625684881196534104984,
13160214960944791745737571666294687886179342741878106108153828171214300480356,
93632248451840935013313489637674048557270261830159812386104018347434531096708,
15750226451420001555465233524738870514754843878573661397197302153086698120116,
35034732986188570282752403373961714079465830549670098557342305666201533823308,
22731773695351497338883943431178589221370002456797684486999646027708779697151,
60817920765222559034343733934804760803601437813912852650747129379361411913898,
53493968718303524964250571104151904930212396250296291581259283032383539967004,
70883580398171358365333237193019023493492808520671476249469154781910452853710,
]
target =
big"23544990289611147830739672041010834898609229946569110903803362822865326025687"
A = matrix(K, transpose(weights))
b = matrix(K, reshape([target], 1, 1))
particular_sol = AbstractAlgebra.solve(A, b)
nullity, homogenous_sol = nullspace(A)
d = length(particular_sol)
# Solution is a subspace of Fp^n. Lift solution to ZZ by appending (e1, e2, ..., e_d) to the basis
particular_sol = lift.(Matrix(particular_sol))
homogenous_sol = [
lift.(Matrix(homogenous_sol)) p*diagm(ones(Int64, d))
]
reduced_basis = open(`fplll`; read = true, write = true) do fplll
write(fplll, to_fplll(transpose(homogenous_sol))) # tranpose becuase fplll expects row vectors
reduced_basis = read(fplll, String)
reduced_basis = "[" * join(split(reduced_basis, "\n")[end-17-1:end])
end
# What is our target vector?
lo = 65
hi = 122 + 768
for i = lo:hi
midpoint = fill(i, d)
target = to_fplll(reshape(midpoint - particular_sol, :))
closest_vector = open(`fplll -a cvp`; read = true, write = true) do cvp
write(cvp, reduced_basis * target)
closest = from_fplll(read(cvp, String))
end
solution = mod.(particular_sol + closest_vector, p)
@show String(UInt8.(decode(solution)))
end
end
function decode(v)
offsets = [0, 256, 512, 768]
out = []
for x in v
push!(out, x - offsets[searchsortedlast(offsets, x)])
end
out
end
function to_fplll(matrix::AbstractMatrix)
ret = "["
for row in eachrow(matrix)
ret *= "[" * join(string.(row), " ") * "]"
end
ret *= "]"
ret
end
function to_fplll(v::AbstractVector)
ret = "[" * join(string.(v), " ") * "]"
ret
end
function from_fplll(v::AbstractString)
reshape(permutedims(Meta.eval(Meta.parse(v))), :)
endFlag
lactf{im_w4y_t00_br0k3!}pprngc
In this challenge, we have an unknown invertible function \(f: \mathbb{F}_2^{16} \longrightarrow \mathbb{F}_2^{16}\) and a hidden 16-bit seed value \(s\). Our task is to recover the seed \(s\) given the value of \(f(s)\) and the following oracles.
prng-oracle
The prng-oracle chooses a public random 16-bit predicate \(p \in \mathbb{F}_2^{16}\) and produces the value \(f^{17}(s)\) together with 16 values \(S(p) = (s_1, s_2, \ldots, s_{16})\) given by
where \(\langle \cdot , \cdot \rangle\) denotes the dot product
We are allowed unlimited queries to the prng-oracle.
pprngc-oracle
The pprngc-oracle takes a 16-bit state \(s'\), a \(k\)-bit predicate \(p\) and a \(k\)-bit vector \((t_1, \ldots, t_k)\) such that
If valid inputs are provided, the oracle returns the value \(\langle f^{-(k +1)}(s'), p \rangle\). We are allowed to query this oracle at most 16 times.
f-oracle
The f-oracle takes a 16-bit value \(x\) and computes \(f(x)\). We are allowed up to 15 queries to this oracle.
#!/usr/local/bin/python3
import secrets
from super_secret_stuff import flag, f, f_inverse
seed = secrets.randbits(16)
function_uses = 0
oracle_uses = 0
done = False
def compute_output_bit(state, pred):
return bin((state & pred)).count("1") % 2
def prng(pred):
cur_state = seed
outputs = []
for i in range(16):
cur_state = f(cur_state)
outputs.append(compute_output_bit(cur_state, pred))
cur_state = f(cur_state)
cur_state_bits = format(cur_state, "b").zfill(16)
all_bits = ("".join([str(i) for i in outputs]) + cur_state_bits)[::-1]
return all_bits
def pprngc(pred, stream):
state = int("".join(stream[:16][::-1]), 2)
for i in range(16, len(stream)):
state = f_inverse(state)
if not compute_output_bit(state, pred) == int(stream[i]):
return None
state = f_inverse(state)
return compute_output_bit(state, pred)
print("All you need to know about f is that it's a function from 16 bits to 16 bits")
print("The output on today's secret seed is:", f(seed))
if __name__ == "__main__":
while not done:
choice = input("What can I do for you? 1. get random bits 2. use f 3. predict next bit 4. guess seed ").strip()
if choice == "1":
rand_pred = secrets.randbelow(2**16)
output = prng(rand_pred)
print(output)
print("Using predicate", rand_pred)
print("Ignore the fact that the first 16 bits are always the same (or don't, your choice)")
elif choice == "2":
if function_uses == 15:
print("Nah, you've had enough.")
continue
num = input("Gimme a number! ").strip()
try:
num = int(num)
if num < 0 or num >= 2**16:
print("Out of range!")
else:
print(f(num))
function_uses += 1
except:
print("Uh something went wrong.")
elif choice == "3":
if oracle_uses == 16:
print("Nah, you've had enough.")
continue
stream = input("Gimme the bitstream you want to predict! ").strip()
if len(stream) < 16:
print("Out of range!")
else:
pred = input("Oh, can you also give a predicate with that? ").strip()
try:
pred = int(pred)
if pred < 0 or pred >= 2**64:
print("Out of range!")
else:
output = pprngc(pred, stream)
if output is None:
print("Uh lemme get back to you on that...")
print("*liquidates assets, purchases fake identity, buys one way ticket to Brazil*")
done = True
else:
print(output)
oracle_uses += 1
except:
print("Uh something went wrong.")
elif choice == "4":
guess = input("Well, let's see it! ").strip()
if str(seed) == guess:
print(flag)
else:
print("Nope! Sorry!")
done = True
else:
print("Buh bye!")
done = TrueTo solve this challenge, we observe that the outputs of the prng-oracle are valid inputs to the pprngc-oracle. Hence, given a pair \((f^{17}(s), S(p))\) from the prng-oracle, we can pass \((f^{17}(s), p, S(p))\) into the pprngc-oracle to obtain the value \(\langle s, p \rangle\) which tells us some information about the parity of set bits in \(s\). Repeating the above process, we hope to obtain enough information about \(s\) within our allotted budget of 16 pprngc-oracle queries to restrict \(s\) to one of at most 16 possibilities. From there, we can use the f-oracle together with the known value of \(f(s)\) to identity \(s\) from amongst the 16 possibilities.
Depending on which predicates \(p\) are chosen by the prng-oracle, this approach may not always produce enough constraints to achieve the desired condition. In theory, one can query the prng-oracle a large number of times to gather a pool of \(n\) candidate predicates, and then select from those candidates the best set of 16 predicates to pass to the pprngc-oracle. Here, we define "best" to mean a set of predicates \(\{p_1, \ldots, p_{16} \}\) such that each \(p_i\) has low Hamming weight (so that locally the constraint returned by the pprngc-oracle admits a minimal number of solutions), whilst ensuring that the element wise product \(p_1 \cdot p_2 \cdot \ldots \cdot p_{16} = (1, \ldots, 1)\) as vectors in \(\mathbb{Z}^{16}\) (to ensure that globally we have enough information to determine all the bits of \(s\)). This can be modelled as an integer program
where \(p_i = (p_{i, 1}, \ldots, p_{i, 16})\) for \(1 \leq i \leq n\).
In practice, we can also just retry a couple of times until we get lucky 😛.
#!/usr/bin/env python3
from pwn import *
import claripy
import cvxpy as cp
import numpy as np
import time
def parse_conn(conn, prefix):
line = conn.readline()
print(line)
line = eval(line[len(prefix) :].decode("ascii"))
return line
MENU = b"What can I do for you? 1. get random bits 2. use f 3. predict next bit 4. guess seed "
def get_random_bits(conn):
conn.sendafter(MENU, b"1\n")
# pprng(rand_pred)
pprng_rand = conn.readline().strip()
pred = parse_conn(conn, "Using predicate")
print(conn.readline())
return pprng_rand, pred
def predict_next_bit(conn, stream, pred):
print(conn.sendafter(MENU, b"3\n"))
print(conn.sendafter("Gimme the bitstream you want to predict! ", stream + b"\n"))
print(conn.sendafter("Oh, can you also give a predicate with that? ", pred + "\n"))
mod = parse_conn(conn, "")
return mod
def use_f(conn, number):
print(conn.sendafter(MENU, b"2\n"))
print(conn.sendafter("Gimme a number! ", number + "\n"))
f_num = parse_conn(conn, "")
return f_num
def guess_seed(conn, seed):
print(conn.sendafter(MENU, b"4\n"))
print(conn.sendafter("Well, let's see it!", str(seed) + "\n"))
print(conn.recvall())
# https://stackoverflow.com/questions/15540798/count-number-of-ones-in-a-given-integer
def count_ones(n):
w = 0
while n:
w += 1
n &= n - 1
return w
def predict_bits(conn, pred, bitstream):
shortened_bitstream = bitstream # shorten bitstream by 1 bit to get one less f_inverse. nevermind i can't count
assert len(shortened_bitstream) == 32
pred_string = str(pred)
parity = predict_next_bit(conn, shortened_bitstream, pred_string)
return pred, parity
def collect_and_solve(conn):
# One variable for each bit
ZERO = claripy.BVV(int(0), int(32))
ONE = claripy.BVV(int(1), int(32))
TWO = claripy.BVV(int(2), int(32))
pred_parity_pairs = {}
s = claripy.Solver()
bv = [claripy.BVS(f"bit_{i}", 32) for i in range(16)]
# Binary constraint
for b in bv:
s.add(b >= ZERO)
s.add(b <= ONE)
while True:
bitstream, pred = get_random_bits(conn)
parity = predict_next_bit(conn, bitstream, str(pred))
pred_parity_pairs[pred] = parity
# Parity Constraint
binary_repr = format(pred, "b").zfill(16) # big endian. 16-bit padded
hamming_weight = sum(bv[i] for (i, b) in enumerate(binary_repr) if b == "1") # big endian
if parity == 1:
parity_bv = ONE
else:
parity_bv = ZERO
s.add(claripy.SMod(hamming_weight, TWO) == parity_bv)
if len(pred_parity_pairs) <= 8: # Don't try to solve yet. very low chance of success
continue
solutions = ["".join(str(bit) for bit in sol) for sol in s.batch_eval(bv, 100)]
if len(solutions) > 10:
print(f"Found {len(solutions)} solutions using {len(s.constraints)} constraints. More solutions than we can verify.")
else:
print(f"Found CSP solutions {solutions}")
return solutions
def query_f_oracle(conn, f_seed, solutions):
f_uses = 0
for solution in solutions:
sol_num = int(solution, 2) # TODO: Endianess?
if sol_num is None: # ???
print(f"None sol_num for {solution}")
if f_uses == 15: # 15 numbers before me were invalid, so this one must be the solution
print("15 numbers before me were invalid, so this one must be the solutione")
return sol_num
f_num = use_f(conn, str(sol_num))
f_uses += 1
if f_num == f_seed:
return sol_num
print("Reached bottom??")
# Initial contact
start = time.time()
first_connect = 0
try:
conn = connect("chall.lac.tf", int(31173))
print(conn.readline())
first_connect = time.time()
# f(seed)
f_seed = parse_conn(conn, "The output on today's secret seed is:")
# Do all together
solutions = collect_and_solve(conn)
# Query the f-oracle to find the correct solution
seed = query_f_oracle(conn, f_seed, solutions)
print(f"Found seed {seed}")
guess_seed(conn, seed)
except EOFError:
print("Terminated due to EOF")
end_time = time.time()
print(f"{end_time - start} elapsed from connect to end")
print(f"{first_connect - start} elapsed from first contact to end")Flag
lactf{we_love_blum-micali_generators_h1MNZuJSFjlAEwc1}shuffler
Fix \(L = 617\). In this challenge, we have a long secret message \(M\) of length \(L\) and a hidden permutation \(\sigma \in S_L\). We are provided the value of \(\sigma(M)\), and our goal is to invert the permutation so we can read the plaintext \(M\).
#!/usr/local/bin/python3
from secrets import randbits
import math
from base64 import b64encode
MESSAGE_LENGTH = 617
class LCG:
def __init__(self, a, c, m, seed):
self.a = a
self.c = c
self.m = m
self.state = seed
def next(self):
self.state = (self.a * self.state + self.c) % self.m
return self.state
def generate_random_quad():
return randbits(64), randbits(64), randbits(64), randbits(64)
initial_iters = randbits(16)
def encrypt_msg(msg, params):
global initial_iters
a, c, m, seed = params
L = LCG(a, c, m, seed)
for i in range(initial_iters):
L.next()
l = len(msg)
permutation = []
chosen_nums = set()
while len(permutation) < l:
pos = L.next() % l
if pos not in chosen_nums:
permutation.append(pos)
chosen_nums.add(pos)
output = "".join([msg[i] for i in permutation])
return output
# period is necessary
secret = b64encode(open("secret_message.txt", "rb").read().strip()).decode() + "."
length = len(secret)
assert length == MESSAGE_LENGTH
a, c, m, seed = params = generate_random_quad()
enc_secret = encrypt_msg(secret, params)
while True:
choice = input("What do you want to do?\n1: Shuffle a message.\n2: Get the encrypted secret.\n3: Quit.\n> ")
if choice == "1":
message = input("Ok. What do you have to say?\n")
if len(message) >= length:
print("I ain't reading allat.\n")
elif math.gcd(len(message), m) != 1:
print("Are you trying to hack me?\n")
else:
print(f"Here you go: {encrypt_msg(message,params)}\n")
elif choice == "2":
print(f"Here you go: {enc_secret}\n")
elif choice == "3":
print("bye bye")
exit(0)
else:
print("Bad choice.\n")The permutation in question is derived from the outputs of a linear congruential generator, and has the form
where the \(x_i\) are the remainders after division by \(L\) of a fixed element \(Z = (z_1, z_2, \ldots, z_L) \in (\mathbb{Z}/m\mathbb{Z})^L\) with \(z_i = az_{i-1}+c \pmod m\).
In addition to \(\sigma(M)\), we are also given to an oracle which effectively reveals to us the first \(n\) coordinates modulo \(n\) of the element \(Z\) for \(n <
L\) coprime to \(m\). This oracle can be accessed by passing a message consisting of \(n\) unique characters (e.g all UTF-8 codepoints from 0x47 to 0x47+n) to the server's encrypt_msg function.
If \(L = a_1 a_2 \cdots a_k\) was composite, then we could use the oracle to find the remainders of the LCG outputs modulo \(a_1,a_2, \ldots,a_k\) and lift these to relations modulo \(L\) using the Chinese remainder theorem. Unfortunately \(L\) is prime, so we need to modify the idea slightly.
Instead of attempting to lift to relations in \(L\), we will attempt to lift to relations modulo \(N\) for some \(N > m\) which will reveal to us a sample of raw outputs from the LCG. We can do this by glueing together oracle outputs for primes \(p_1, p_2, \ldots,p_k\) such that \(p_i < L\) and \(\prod p_i > m\). This reveals to us the first \(\mathrm{min}\{p_1, p_2, \ldots, p_k\}\) outputs of the LCG. We can then use these outputs to crack the LCG parameters via standard techniques, and from there determine all coordinates of the vector \(Z\).
using Primes
using Base64
const MENU = "What do you want to do?\n1: Shuffle a message.\n2: Get the encrypted secret.\n3: Quit.\n> "
function sendlineafter(conn, prefix, line)
print(readuntil(conn, prefix))
write(conn, string(line) * "\n")
end
function get_enc_msg(conn)
sendlineafter(conn, MENU, "2")
enc_msg = readline(conn)
enc_msg = only(match(r"Here you go: (.*)", enc_msg))
enc_msg
end
function chosen_pt(conn, msg)
sendlineafter(conn, MENU, "1")
sendlineafter(conn, "Ok. What do you have to say?", msg)
print(readline(conn))
s = readline(conn)
if occursin("Are you trying to", s)
return nothing
else
return only(match(r"Here you go: (.*)", s))
end
end
function unique_alphabet_string(len)
msg = collect('A':('A'+len-1))
return join(msg)
end
function get_sample(msg_len)
pt = unique_alphabet_string(msg_len)
ct = chosen_pt(conn, pt)
pt = collect(pt)
ct = collect(ct)
perm = sortperm(pt; lt = (a, b) -> findfirst(==(a), ct) < findfirst(==(b), ct))
@assert pt[perm] == ct
return perm
end
function crt(res1::BigInt, res2::BigInt, mod1::BigInt, mod2::BigInt)
d, u, v = gcdx(mod1, mod2)
@assert d == 1
@assert u * mod1 + v * mod2 == 1
x = res1 * v * mod2 + res2 * u * mod1
m = mod1 * mod2
@assert mod(x, mod1) == mod(res1, mod1)
@assert mod(x, mod2) == mod(res2, mod2)
return x, m
end
function reverse_lcg(outputs)
t = [outputs[i] - outputs[i-1] for i = 2:length(outputs)]
u = [t[i+2] * t[i] - t[i+1]^2 for i = 1:length(t)-2]
m = nothing
for i = 1:10
m = gcd(u[1:i]...)
@show m
if m < big(2)^64
break
end
end
# Now we know m, then a = mod(t*modinv(outputs[1] - outputs[2], m), m)
a = mod((outputs[3] - outputs[2]) * invmod(outputs[2] - outputs[1], m), m)
c = mod(outputs[2] - a * outputs[1], m)
return a, c, m
end
function decrypt_msg(enc_msg, a, c, m, initial)
enc_msg = collect(enc_msg)
perm = [mod(initial, length(enc_msg))]
state = initial
while length(perm) < length(enc_msg)
state = mod(a * state + c, m)
if !in(mod(state, length(enc_msg)), perm)
push!(perm, mod(state, length(enc_msg)))
end
end
perm = perm .+ 1 # switch to julia 1-index
@assert isperm(perm)
inv = invperm(perm)
pt = join(enc_msg[inv])
print(String(Base64.base64decode(pt)))
end
const MESSAGE_LENGTH = 617
function solve()
conn = connect("chall.lac.tf", 31172)
enc_msg = get_enc_msg(conn)
msg_len = modulus = big(613)
perm = get_sample(msg_len)
residues = big.(copy(perm))
moduli = fill(msg_len, msg_len)
msg_len -= big(1)
while modulus <= big(2)^64
if !isprime(msg_len)
msg_len -= big(1)
continue
end
perm = big.(get_sample(msg_len))
for (i, (res1, mod1, res2, mod2)) in
enumerate(zip(residues, moduli, perm, fill(msg_len, msg_len)))
residues[i], moduli[i] = crt(res1, res2, mod1, mod2)
end
modulus = lcm(modulus, msg_len)
@show modulus
msg_len -= 1
end
residues = mod.(residues, moduli)
residues = residues[moduli.==modulus]
a, c, m = reverse_lcg(residues)
decrypt_msg(enc_msg, a, c, m, residues[1])
endFlag
lactf{th3_h0us3_c0uld_n3v3r_l0se_r1ght}any%-ssg
This challenge takes place inside a graphical Java application which mimics Minecraft, so for brevity I will not reproduce the challenge code here, and instead dive straight into the mathematics.
Let \(m \in \mathbb{Z}\) and \(a, c \in \mathbb{Z}/m\mathbb{Z}\) be given. Let \(x_0 \in \mathbb{Z}/m\mathbb{Z}\) be fixed, and consider 16 consecutive outputs \(x_1, x_2, \ldots, x_{16}\) from the linear congruential generator
with initial value \(x = x_0\). Then we have the following relations in \(\mathbb{Z}/m\mathbb{Z}\),
or equivalently,
Let \(\mathbf{x} = (x_1, x_2, \ldots, x_{16})\), \(\mathbf{v} = (a, a^2, \ldots, a^{16})\) and \(\mathbf{p} = (p_1, \ldots, p_{16})\) where
Then we have \(\mathbf{x} = \mathbf{p} + x_0\mathbf{v}\). Fix an integer \(0 < L < m\). To obtain the flag for this challenge, we need to find a value of \(x_0\) for which each \(x_i\) is congruent modulo \(m\) to \(b_i\) for some \(b_i \in (L, m) \subseteq \mathbb{Z}\).
The solution proceeds much the same as the solution for budget-bag, albeit with vector spaces swapped out for modules since \(m\) is composite. The possible values of \(\mathbf{x}\) forms a 1-dimensional affine submodule of \((\mathbb{Z}/m\mathbb{Z})^{16}\). We can lift to a lattice in \(\mathbb{Z}^{16}\) by appending arbitrary linear combinations of \(m\mathbf{e}_1,\ldots,m\mathbf{e}_{16} \in \mathbb{Z}^{16}\). Under this lifting, the problem reduces to finding a lattice vector with all coordinates lying in the interval \((L, m)\), and this can solved using a CVP solver such as fplll.
using LinearAlgebra
function to_fplll(matrix::AbstractMatrix)
ret = "["
for row in eachrow(matrix)
ret *= "[" * join(string.(row), " ") * "]"
end
ret *= "]"
ret
end
function to_fplll(v::AbstractVector)
ret = "[" * join(string.(v), " ") * "]"
ret
end
function from_fplll(v::AbstractString)
reshape(permutedims(Meta.eval(Meta.parse(v))), :)
end
function invert_lcg(x, a, c, m)
mod((x - c) * invmod(a, m), m)
end
const m = big(1) << 52
const c = big(4164880461924199)
const a = big(2760624790958533)
const B = big(4053239664633446)
function solve()
# want an initial value x0 such that
# x_1 = a*x_0 + c mod m > B
# x_2 = a*x_1 + c mod m
# = a^2x_0 + a*c + c mod m > B
# x_3 = a^3x_0 + a^2*c + ac + c mod m > B
#
# and in general
# x_k = a^k x_0 + c*\sum_{i = 0}^{k - 1}a^i mod m
#
# Note: in rhs, the c*\sum_{i = 0}^{k - 1}a^i mod m term is constant
# and the lefthand side is x_0 * (a, a^2, a^3, a^4, .., a^n)
n = 16
particular_sol = [mod(c * sum(mod(a^i, m) for i = 0:(k-1)), m) for k = 1:n]
homogenous_sol = [mod(big(a)^i, m) for i = 1:n]
@assert length(particular_sol) == length(homogenous_sol)
# Lift to Z by appending combinations of (e_1, e_2, ... e_n)
homogenous_sol = [
homogenous_sol m*diagm(ones(BigInt, n))
]
# LLL-reduce lattice bassis
reduced_basis = open(`fplll`; read = true, write = true) do fplll
write(fplll, to_fplll(transpose(homogenous_sol))) # tranpose becuase fplll expects row vectors
reduced_basis = read(fplll, String)
reduced_basis = "[" * join(split(reduced_basis, "\n")[2:end]) # first row is all zeros, remove it
end
midpoint = fill(fld(B + m, 2), n)
target = to_fplll(reshape(midpoint - particular_sol, :))
closest_vector = open(`fplll -a cvp`; read = true, write = true) do cvp
write(cvp, reduced_basis * target)
closest = from_fplll(read(cvp, String))
end
solution = mod.(particular_sol + closest_vector, m)
@assert all(solution[i] == mod(a * solution[i-1] + c, m) for i = 2:length(solution))
x_1 = first(solution)
x_0 = invert_lcg(x_1, a, c, m)
for _ = 1:26
x_0 = invert_lcg(x_0, a, c, m)
end
rng_i = 3473400794307473
seed = xor(x_0, rng_i)
@show seed
seed
endFlag
lactf{c0ngr4ts_0n_th3_w0rld_r3c0rd}