[CTF GEMA] Affine

Niveau de Difficulté : Very-Easy

Catégorie du Challenge : Crypto

Description :
Un message a été chiffré à l'aide d'un chiffrement affine.
Pour déchiffrer un tel message, il faudrait normalement connaître les valeurs de a et b. Cependant, dans ce challenge, ces valeurs ne sont pas fournies, et vous devrez les déterminer par cryptanalyse.

VIYGBAFVKCVI RI NROS FIR QKI DGBBIV IB DIAYVCLFCGB OPIY: O_T_YXCNNVIWIBF_ONNCBI

Format du flag: FLAG{...}

Solutions Steps

Le script de chiffrement nous est fourni, nous pouvons de ce fait comprendre comment celui-ci est construit :

import string
import argparse
from math import gcd

def affine_encrypt(message, a, b):
    if gcd(a, 26) != 1:
        raise ValueError("'a' doit être copremier avec 26.")

    alphabet = string.ascii_uppercase
    n = len(alphabet)

    encrypted_message = ""
    for char in message:
        if char.isalpha() and char.isupper():
            P = alphabet.index(char)  
            C = (a * P + b) % n       
            encrypted_message += alphabet[C]
        else:
            encrypted_message += char

    return encrypted_message

if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="Chiffrement affine d'un message.")
    parser.add_argument("message", type=str, help="Le message à chiffrer (en majuscules).")
    parser.add_argument("a", type=int, help="Coefficient multiplicatif (doit être copremier avec 26).")
    parser.add_argument("b", type=int, help="Décalage additionnel.")

    args = parser.parse_args()

    plaintext = args.message
    a = args.a
    b = args.b

    try:
        ciphertext = affine_encrypt(plaintext, a, b)
        print(f"Texte clair : {plaintext}")
        print(f"Texte chiffré : {ciphertext}")
    except ValueError as e:
        print(e)

À l'aide de ce script et des ressources sur internet liée au chiffrement affine, nous pouvons établir le script qui permettra de le déchiffré par force brute.

import string
import sys
from math import gcd

def mod_inverse(a, m):
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

def affine_decrypt(ciphertext, a, b):
    a_inv = mod_inverse(a, 26)
    if a_inv is None:
        raise ValueError(f"L'inverse de {a} modulo 26 n'existe pas.")
    
    plaintext = []
    for char in ciphertext:
        if char.isalpha():  
            x = ord(char.lower()) - ord('a')
            decrypted_char = (a_inv * (x - b)) % 26
            plaintext.append(chr(decrypted_char + ord('a')))
        else:
            plaintext.append(char)
    
    return ''.join(plaintext)

def brute_force_affine_decrypt(ciphertext):
    alphabet = string.ascii_lowercase
    for a in range(1, 26):  
        if gcd(a, 26) == 1:  
            for b in range(26):  
                try:
                    plaintext = affine_decrypt(ciphertext, a, b)
                    print(f"Essai avec a={a} et b={b} : {plaintext}")
                except ValueError:
                    continue

if len(sys.argv) != 2:
    print("Usage: python affine_decrypt.py <ciphertext>")
    sys.exit(1)

ciphertext = sys.argv[1]

brute_force_affine_decrypt(ciphertext)