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

But here is my writeup for Recurrent

Description

image

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))

flag = open("flag.txt", "rb").read()
key = sha256(master_secret.to_bytes(64, 'big')).digest()[:16]
iv = sha256(key).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv=iv)

print("Encrypted:", iv + cipher.encrypt(pad(flag, 16)))

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!