I play VolgaCTF last weekend, could not solve any challenge because quite busy last weekend

But here is my writeup for Recurrent

# Attachment

Let’s look at the source code, it generate a random prime number and some random numbers:

p = random_prime(2 ** 512 - 1, False, 2 ** 511)
F = GF(p)

a = IntegerMod(F, randint(1, p))
b = IntegerMod(F, randint(1, p))
s0 = IntegerMod(F, randint(1, p))

n_a = IntegerMod(F, randint(1, p))
n_b = IntegerMod(F, randint(1, p))


Then pass into the recurrent function

A = recurrent(s0, a, b, n_a)
B = recurrent(s0, a, b, n_b)


Then it uses the master_secret to encrypt the flag using AES CBC mode:

master_secret = int(recurrent(A, a, b, n_b))

key = sha256(master_secret.to_bytes(64, 'big')).digest()[:16]
iv = sha256(key).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv=iv)



As you can see, we need to find out the value of master_secret in order to decrypt the flag

All values are given in the params file except n_a and n_b

p = 11402052825540369388503481527295817481121560256343494229999703486843211603849210440171418919250976071577012333493508412960698029285144211123336209953546781
a = 2817802771147678250767821085169703611490909101765946538363694715392828746232646298983204110458876307183328568276931317661434830232022114467877231852642060
b = 9490450238579366303161630595850378445035492689429789647605534026537099144306960890264012619313399265591312506737704378948826242942974381162153121492302043
s0 = 8599613106490622815088840657327923452887480903614107996301188278431030143342810757070939643143362386195629333762665379031911566602662441910306436944668091
A = 986962953549041204542742968905526856564460530774514387254820641350803588102370143051893651800079411337299897527695463495894799510402443635863507908895240
B = 7400642646495721122069695917309138984119691728390992710126139372576214409335954108817954691349087032495947562990375228286533082455228820477398400954673663
Encrypted: b'\xd8\x95H\x97\x8b*\x06\x0fOs\xe5\xf0M\x96Z\xba\xed$\xa0[T\xc2D\x8b\xf4\xae\xb1\xd9\xc4\x19\xdb{o\xf7\x81-U\x1f\xce\xd6GF\xac\xb4\xb8\xe6\x01\xf8=\xed\x94:\xd0\xa1\x14(\xa1\x0fo\x1f\xa0\x88\x17\xf3'  # Math Let’s look at the function recurrent def recurrent(s0, a, b, n): s = s0 for i in range(1, n + 1): s = s + a * i + b return s  Basically it just add the seed value s0 n times with a*i and b, if written in math expression it looks like this: $s = s_0 + \sum_{i=1}^{n}ai + bn$ The flag only needed $$n_b$$ to decrypt so we only using $$B$$ and $$n_b$$, we can rewrite the math equation: $B = s_0 + \sum_{i=1}^{n_b}ai + bn_b$ We know all the values except for $$n_b$$, so how we calculate $$n_b$$ by using this equation? # Find $$n_b$$ The summation part we can use the sum of arithmetic sequence formula where we learned in high school add maths $S_n = \frac{n}{2}[2a + (n–1)d]$ Substitute the $$d$$ with $$a$$ (The difference is $$a$$) $S_n = \frac{n}{2}[2a + (n–1)a]$ Then simplify the equation $=\frac{n}{2}(2a+an-a)$ $=\frac{2an+an^2-an}{2}$ $=\frac{an+an^2}{2}$ We can back to the recurrent equation and substitute it: $B = s_0 + \frac{an_b+a(n_b)^2}{2} + bn_b$ Reconstruct the equation to form of $$ax^2+bx+c$$ so we can find the roots: $2B = 2s_0 + an_b+a(n_b)^2 + 2bn_b$ $2s_0 + an_b+a(n_b)^2 + 2bn_b - 2B =0$ $a(n_b)^2 + 2bn_b + an_b + 2s_0 - 2B =0$ $a(n_b)^2 + (2b+a)n_b + (2s_0 - 2B) =0$ As you can see, we have $$a=a$$, $$b=2b+a$$ and $$c=2s_0-2B$$ we can now find the roots of the quadratic equation to calculate $$n_b$$! The number are too large so we have to use SageMath to help us calculate this! Also don’t forget the modular p p = 11402052825540369388503481527295817481121560256343494229999703486843211603849210440171418919250976071577012333493508412960698029285144211123336209953546781 a = 2817802771147678250767821085169703611490909101765946538363694715392828746232646298983204110458876307183328568276931317661434830232022114467877231852642060 b = 9490450238579366303161630595850378445035492689429789647605534026537099144306960890264012619313399265591312506737704378948826242942974381162153121492302043 s = 8599613106490622815088840657327923452887480903614107996301188278431030143342810757070939643143362386195629333762665379031911566602662441910306436944668091 A = 986962953549041204542742968905526856564460530774514387254820641350803588102370143051893651800079411337299897527695463495894799510402443635863507908895240 B = 7400642646495721122069695917309138984119691728390992710126139372576214409335954108817954691349087032495947562990375228286533082455228820477398400954673663 n = var('n') # Declare symbol n print(solve_mod([a*n^2 + (a+2*b)*n + 2*s -2*B == 0],p)) # solve in modular p  Unfortunately it show this error: /usr/lib/python3/dist-packages/apport/report.py:13: DeprecationWarning: the imp module is deprecated in favour of importlib; see the module's documentation for alternative uses import fnmatch, glob, traceback, errno, sys, atexit, locale, imp, stat Traceback (most recent call last): File "solve.sage.py", line 14, in <module> print(solve_mod([a*n**_sage_const_2 + (a+_sage_const_2 *b)*n + _sage_const_2 *s -_sage_const_2 *B == _sage_const_0 ],p)) File "/usr/lib/python3/dist-packages/sage/symbolic/relation.py", line 1506, in solve_mod solution =_solve_mod_prime_power(eqns, p, i, vars) File "/usr/lib/python3/dist-packages/sage/symbolic/relation.py", line 1609, in _solve_mod_prime_power possibles = cartesian_product_iterator([range(len(R)) for _ in range(len(vars))]) File "/usr/lib/python3/dist-packages/sage/symbolic/relation.py", line 1609, in <listcomp> possibles = cartesian_product_iterator([range(len(R)) for _ in range(len(vars))]) File "sage/rings/ring.pyx", line 236, in sage.rings.ring.Ring.__len__ (build/cythonized/sage/rings/ring.c:3217) OverflowError: Python int too large to convert to C ssize_t  Not sure why it complaining the value too large? Then I struggle until the competition ends… Then I saw someone post the solution on telegram, I saw the solution script I realise need to use PolynomialRing to find the roots… p = 11402052825540369388503481527295817481121560256343494229999703486843211603849210440171418919250976071577012333493508412960698029285144211123336209953546781 a = 2817802771147678250767821085169703611490909101765946538363694715392828746232646298983204110458876307183328568276931317661434830232022114467877231852642060 b = 9490450238579366303161630595850378445035492689429789647605534026537099144306960890264012619313399265591312506737704378948826242942974381162153121492302043 s = 8599613106490622815088840657327923452887480903614107996301188278431030143342810757070939643143362386195629333762665379031911566602662441910306436944668091 A = 986962953549041204542742968905526856564460530774514387254820641350803588102370143051893651800079411337299897527695463495894799510402443635863507908895240 B = 7400642646495721122069695917309138984119691728390992710126139372576214409335954108817954691349087032495947562990375228286533082455228820477398400954673663 b = (a+2*b) % p c = (2*s-2*B) % p F = GF(p) R.<x> = PolynomialRing(F) quad_poly = a * x^2 + b * x + c roots = quad_poly.roots() print(roots) # [(9843820933844649036327547942406712352816347215384538217313810946594825095037363480375700165926228786958138234308107215538911557037358884579012142374529722, 1), (1994023652190016323861372658827484904528548480921553267078233601451075663946468145138879986275822079751273076865795300424230748235691951213719042182521596, 1)]  Then using AES to decrypt it using master_secret as the key: from hashlib import sha256 from Crypto.Cipher import AES p = 11402052825540369388503481527295817481121560256343494229999703486843211603849210440171418919250976071577012333493508412960698029285144211123336209953546781 a = 2817802771147678250767821085169703611490909101765946538363694715392828746232646298983204110458876307183328568276931317661434830232022114467877231852642060 b = 9490450238579366303161630595850378445035492689429789647605534026537099144306960890264012619313399265591312506737704378948826242942974381162153121492302043 A = 986962953549041204542742968905526856564460530774514387254820641350803588102370143051893651800079411337299897527695463495894799510402443635863507908895240 # Recoding recurrent to def recurrent(s0, a, b, n): return (s0 + (a*n + a*(n**2))//2 + b*n)%p n_b = 9843820933844649036327547942406712352816347215384538217313810946594825095037363480375700165926228786958138234308107215538911557037358884579012142374529722 master_secret = int(recurrent(A, a, b, n_b)) key = sha256(master_secret.to_bytes(64, 'big')).digest()[:16] iv = sha256(key).digest()[:16] cipher = AES.new(key, AES.MODE_CBC, iv=iv) enc = b'\xd8\x95H\x97\x8b*\x06\x0fOs\xe5\xf0M\x96Z\xba\xed$\xa0[T\xc2D\x8b\xf4\xae\xb1\xd9\xc4\x19\xdb{o\xf7\x81-U\x1f\xce\xd6GF\xac\xb4\xb8\xe6\x01\xf8=\xed\x94:\xd0\xa1\x14(\xa1\x0fo\x1f\xa0\x88\x17\xf3'
print(cipher.decrypt(enc[16:]))
# b'VolgaCTF{y0u_r3_s0_g00d_1_s33_n0w}\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'


# Flag

VolgaCTF{y0u_r3_s0_g00d_1_s33_n0w}


Great math challenge!