What Does “mod 41” Mean?#

Taking a number mod 41 means:

Divide the number by 41 and keep the remainder

Examples:

• 104 mod 41 = 22
• 372 mod 41 = 3
• 110 mod 41 = 28

This reduces all large numbers into a small range between 0 and 40.

What is Modular Inverse?#

The modular inverse of a number answers this question:

“What number do I multiply by this value to get 1 (mod 41)?"

Mathematically, it is written as:

This means:

• Multiply a by x
• Take the result mod 41
• If the answer is 1, then x is the modular inverse of a

You can think of a modular inverse as the undo button for multiplication (when working modulo 41).

Example#

The modular inverse of 3 mod 11 is 4, because:

Why inverses always exist here

• 41 is a prime number
• This means every number from 1 to 40 has a modular inverse modulo 41
• So we are guaranteed that an inverse exists (except when the value is 0)

Character Mapping#

After finding the modular inverse, we convert it into a character using this mapping:

• 1-26: A-Z (alphabet)
• 27-36: 0-9 (digits)
• 37: _ (underscore)

Implementing the decryption#

Here’s the Python solution:

1
def decrypt_basic_mod2(ciphertext):
2
    # Character mapping
3
    # 1-26: a-z, 27-36: 0-9, 37: _
4
    char_map = {
5
        1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f', 7: 'g', 8: 'h', 9: 'i', 10: 'j',
6
        11: 'k', 12: 'l', 13: 'm', 14: 'n', 15: 'o', 16: 'p', 17: 'q', 18: 'r', 19: 's', 20: 't',
7
        21: 'u', 22: 'v', 23: 'w', 24: 'x', 25: 'y', 26: 'z',
8
        27: '0', 28: '1', 29: '2', 30: '3', 31: '4', 32: '5', 33: '6', 34: '7', 35: '8', 36: '9',
9
        37: '_'
10
    }
11

12
    plaintext = []
13

14
    for num in ciphertext:
15
        # Step 1: Take mod 41
16
        mod_result = num % 41
17

18
        # we use Python 3.8+ built-in: pow(a, -1, 41)
19
        if mod_result == 0:
20
            # Edge case: if mod_result is 0, there's no inverse
21
            continue
22

23
        inverse = pow(mod_result, -1, 41)
24

25
        # Step 3: Map to character
26
        if inverse in char_map:
27
            plaintext.append(char_map[inverse])
28

29
    return ''.join(plaintext)
30

31
# Parse the ciphertext
32
ciphertext = [104, 372, 110, 436, 262, 173, 354, 393, 351, 297, 241, 86, 262, 359, 256, 441, 124, 154, 165, 165, 219, 288, 42]
33

34
# Decrypt
35
message = decrypt_basic_mod2(ciphertext)
36
print(f"Decrypted message: {message}")
37
print(f"Flag: picoCTF{{{message}}}")

Running the solution#

The decrypted message is:

1
1nv3r53ly_h4rd_dadaacaa

⚡ Raikiri

🎉 Flag pwned!

1
$ python solve.py
2
Decrypted message: 1nv3r53ly_h4rd_dadaacaa
3
Flag: picoCTF{1nv3r53ly_h4rd_dadaacaa}

Flag: picoCTF{br1nv3r53ly_h4rd_dadaacaa}

💡 TL;DR / Lesson Learned

1. Modular inverse: Understanding that the modular multiplicative inverse is the key operation for decryption. Since 41 is prime, every non-zero number has an inverse.

2. Character mapping: The custom alphabet (1-26 = a-z, 27-36 = 0-9, 37 = _) is crucial for converting the numeric result back to characters.

3. Modular arithmetic: Taking mod 41 first reduces large numbers to a manageable range (0-40), making the inverse operation efficient.

4. Python’s pow() function: The three-argument pow(a, -1, m) efficiently computes modular inverses (available in Python 3.8+), making the solution elegant and fast.