Sequences picoCTF 2022 Solution

Description

1. Step 1Understand the recurrence relation
   The sequence is defined by a 4-term recurrence: f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4), with base cases f(0)..f(3). The challenge asks for f(n) mod p for a large n.
   Learn more

   A linear recurrence is a sequence where each term is a fixed linear combination of previous terms. The Fibonacci sequence (f(n) = f(n-1) + f(n-2)) is the most familiar 2-term example. This challenge uses a 4-term version.

   The naive recursive implementation has exponential time complexity: to compute f(n), it recomputes f(n-1) through f(n-4) independently, each of which recomputes further, leading to O(4^n) function calls. For n = 10^18 (a common CTF value), this is astronomically slow.

   Two efficient approaches exist:

   • Memoization: cache computed values with functools.lru_cache. O(n) time but O(n) space - still too slow for n = 10^18.
   • Matrix exponentiation: represent the recurrence as matrix multiplication and use fast exponentiation. O(k^3 * log n) time where k=4.
2. Step 2Apply matrix exponentiation
   Express the recurrence as a matrix equation: [f(n), f(n-1), f(n-2), f(n-3)] = M * [f(n-1), f(n-2), f(n-3), f(n-4)]. Raise M to the power n with fast exponentiation.
   python

   python3 -c "
   import numpy as np
   
   MOD = 0  # Fill in from sequences.py
   
   def mat_mul(A, B):
       n = len(A)
       C = [[0]*n for _ in range(n)]
       for i in range(n):
           for j in range(n):
               for k in range(n):
                   C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
       return C
   
   def mat_pow(M, p):
       n = len(M)
       result = [[1 if i==j else 0 for j in range(n)] for i in range(n)]  # identity
       while p:
           if p & 1:
               result = mat_mul(result, M)
           M = mat_mul(M, M)
           p >>= 1
       return result
   
   # Transition matrix for f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4)
   M = [
       [1, 1, 1, 1],
       [1, 0, 0, 0],
       [0, 1, 0, 0],
       [0, 0, 1, 0],
   ]
   
   n = 0  # Fill target n from sequences.py
   base = [0, 0, 0, 1]  # f(3),f(2),f(1),f(0) - fill from sequences.py
   
   result_mat = mat_pow(M, n)
   answer = sum(result_mat[0][i] * base[i] for i in range(4)) % MOD
   print('f(n) =', answer)
   "

   Copied!
   Learn more

   The key insight: the recurrence f(n) = f(n-1)+f(n-2)+f(n-3)+f(n-4) can be written as a matrix equation:

   [f(n), f(n-1), f(n-2), f(n-3)]^T = M * [f(n-1), f(n-2), f(n-3), f(n-4)]^T

   where M is the 4x4 companion matrix shown above. By induction, [f(n), ...]^T = M^n * [f(3), f(2), f(1), f(0)]^T. Matrix exponentiation via square-and-multiply computes M^n in O(4^3 * log n) = O(64 log n) multiplications - fast even for n = 10^18.

   All operations are done modulo MOD (a prime), which keeps the numbers small throughout. Without this, the numbers would have billions of digits.

3. Step 3Decrypt the flag using the computed sequence value
   The challenge uses the sequence value as part of the flag derivation - often as a key for XOR or as an AES key. Apply the provided encryption/decryption logic in reverse.
   Learn more

   Once you have f(n) mod p, examine sequences.py to see how the flag is encrypted. Common patterns include XOR with a cyclic key derived from the sequence value, or AES-ECB with the sequence value as the key (padded or hashed to 16/32 bytes).

   The challenge is essentially testing whether you know to apply matrix exponentiation for linear recurrences. The actual flag derivation is usually straightforward once you have the correct sequence value.

   Matrix exponentiation for linear recurrences is a fundamental algorithm in competitive programming and appears in many picoCTF challenges under various disguises (Fibonacci variants, tiling counts, path counting in graphs). Mastering it pays dividends across many problem categories.

Flag

This challenge was not solved during the competition. Implement matrix exponentiation for the 4-term recurrence to compute f(n) mod p in O(log n) time, then use it to decrypt the flag.