basic-mod2 picoCTF 2022 Solution

Description

1. Step 1

   Reuse the parsing trick

   Observation

   I noticed that message.txt contains the same space-separated integer format as basic-mod1, which suggested that the same sed pipeline for converting it into a Python list could be reused directly without any modification.

   The same sed pipeline from basic-mod1 turns the raw numbers into a Python-friendly array, letting you focus on the math instead of text processing.

   What didn't work first

   Tried: Manually copying numbers from message.txt and typing them as a Python list by hand.

   This works for a short message but is error-prone and slow for longer inputs. Any typo silently produces a wrong character in the flag. The sed pipeline is faster and exact, so automate the parsing step whenever the input file could have more than a handful of numbers.

   Tried: Trying to reuse the basic-mod1 script directly without changing the decoding logic.

   basic-mod1 computes n % 37 to map values to letters, but basic-mod2 requires the modular inverse of n modulo 41. Running the old script produces garbage output because the operation is fundamentally different - you must replace the modulo step with pow(n, -1, 41).

   Learn more

   Reusing tools and patterns across related challenges is a core CTF skill. Recognizing that the input format is identical to basic-mod1 means you can adapt your existing script rather than starting from scratch - you only need to swap the decoding logic, not the parsing.

   The sed pipeline that wraps space-separated numbers into a Python list is a general-purpose pattern that works any time you have whitespace-delimited integers on a single line. Keeping such one-liners in a personal "toolbox" or snippet library speeds up CTF solving considerably.

2. Step 2

   Compute modular inverses

   Observation

   I noticed the challenge title explicitly says 'mod2' and the problem statement asks for the modular inverse of each value modulo 41, which suggested that Python's pow(n, -1, 41) was the correct decoding operation rather than a simple modulo.

   pow(n, -1, 41) returns the multiplicative inverse of n modulo 41. The alphabet is 1-indexed in this challenge, so subtract 1 before indexing into ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_.

   What didn't work first

   Tried: Computing n % 41 instead of the modular inverse pow(n, -1, 41).

   The modulo operation and the modular inverse are opposite operations. Taking n mod 41 is what basic-mod1 style decoding does, but here you need to reverse the encoding by finding the x such that n * x is congruent to 1 mod 41. Using % produces a completely wrong character mapping and a garbled flag.

   Tried: Forgetting to subtract 1 before indexing into the alphabet string.

   The challenge maps 1 to A, 2 to B, and so on (1-indexed), but Python strings are 0-indexed. If you skip the minus 1, every character is shifted by one position - A becomes B, B becomes C - and the flag looks almost right but is subtly wrong throughout.

   Learn more

   The modular multiplicative inverse of a modulo m is the value x with a * x ≡ 1 (mod m). It exists only when a and m are coprime. 41 is prime, so every value from 1 to 40 has one - which is why 41 was picked.

   The inverse comes from the extended Euclidean algorithm: gcd(a, m) is written as a*x + m*y = 1, and reducing mod m drops the second term. Worked example for the inverse of 9 mod 41:

   Forward Euclidean (gcd):
     41 = 4*9 + 5
      9 = 1*5 + 4
      5 = 1*4 + 1
      4 = 4*1 + 0   -> gcd = 1
   
   Back-substitute (Bezout):
      1 = 5 - 1*4
        = 5 - 1*(9 - 1*5)     = 2*5 - 1*9
        = 2*(41 - 4*9) - 1*9  = 2*41 - 9*9
   
   So 9 * (-9) ≡ 1 (mod 41), and -9 mod 41 = 32.
   
   Full congruence verification:
     9 * 32 = 288
     7 * 41 = 287
     288 = 287 + 1 = 7*41 + 1
     Therefore 9 * 32 ≡ 1 (mod 41). Index = 32, character = alphabet[31] = '5'.

   Python 3.8+ supports pow(a, -1, m) as a one-liner that calls the same algorithm internally. The challenge prompt defines the alphabet as 1-indexed (A=1, B=2, ...) because it makes the math read more naturally - 0 has no inverse, so excluding it is convenient. Subtracting 1 aligns the result with Python's zero-based string indexing.

3. Step 3

   Build the string

   Observation

   I noticed that after computing the inverse and subtracting 1, each resulting index maps to a character in the alphabet/digit/underscore set, which suggested assembling those characters sequentially inside the picoCTF{} wrapper to form the final flag.

   Append each character to a string prefixed with picoCTF{ and close it with } once all characters are decoded.

Flag

Modular inverses are the foundation of RSA and Diffie-Hellman; Python's `pow(a, -1, m)` handles them in one call.