Message lointain

Description du challenge

• Nom du CTF : 404CTF 2025
• Catégorie : Crypto
• Difficulté : Intro
• Date : Mai 2025

On nous donne l'algorithme suivant :

from flag import FLAG

charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}-!"
n = len(charset)

def encrypt(message):
    encrypted = []
    for char in message:
        if char in charset:
            x = charset.index(char)
            y = pow(2, x, n+1)
            encrypted.append(charset[y])
    return ''.join(encrypted)

print("ENCRYPTED FLAG : ", encrypt(FLAG)) 

# ENCRYPTED FLAG : 828x6Yvx2sOnzMM4nI2sQ 

Analyse de l'algorithme

Pour chaque caractère du message :

1. On calcule son index dans charset
2. On élève 2 à la puissance de cet index modulo n+1 (où n est la longueur de charset).
3. Le caractère chiffré est ensuite le caractère à l'index obtenu dans charset.

Déchiffrage

Pour déchiffrer le message, nous devons inverser le processus.

Pour chaque caractère chiffré, nous devons :

1. Trouver sa position y dans le charset.
2. Tester toutes les valeurs possibles de x tel que pow(2, x, n+1) == y (exponantiation modulaire).
3. Pour chaque x trouvé, nous pouvons récupérer le caractère original à l'index x dans charset.

On a alors la fonction Python suivante pour déchiffrer le message :

def decrypt():
    encrypted_flag = "828x6Yvx2sOnzMM4nI2sQ"
    decrypted = []
    
    for char in encrypted_flag:
        if char in charset:
            y = charset.index(char)
            
            found = False
            for x in range(len(charset)):
                if pow(2, x, n+1) == y:
                    decrypted.append(charset[x])
                    found = True
                    break
            
            if not found:
                decrypted.append('?')
                
    return ''.join(decrypted)

print("DECRYPTED FLAG : ", decrypt())

FLAG

404CTF{C0nstEllAt!0n}