basic-mod2 picoCTF 2022 Solution

Description

1. Step 1Reuse the parsing trick

   Observation

   message.txt uses the same space-separated integer format as basic-mod1, so the same sed pipeline converts it into a Python list with no changes.

   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 on a short message and is slow and error-prone on anything longer, where a single typo silently corrupts one character of the flag. The sed pipeline is faster and exact, so automate the parsing whenever the file holds more than a handful of numbers.

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

   basic-mod1 maps values to letters with n mod 37, while this one needs the modular inverse of n mod 41. Run the old script and you get garbage, because the operation is different in kind. 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 2Compute modular inverses

   Observation

   The title says mod2 and the problem asks for the modular inverse of each value modulo 41. So the decoding operation is pow(n, -1, 41), not a plain 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 3Build the string

   Observation

   After the inverse and a subtraction of 1, each index maps into the letters, digits, and underscore set. Assemble those characters in order inside the picoCTF{} wrapper.

   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.