basic-mod2 picoCTF 2022 Solution

Description

1. Step 1Reuse the parsing trick
   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.
   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
   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_.
   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
   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.