[CTF] WU - RSA101

Difficulty Level : Insane

Challenge Category : Crypto

Description :

During my work at the company I have collected 100 public keys and 100 encrypted texts. Can you help me decrypt them?

Solution Steps

Step 1: Understanding the Attack

RSA keys are defined by a modulus ( n = p \times q ), where ( p ) and ( q ) are prime numbers.
If two keys share a common prime factor ( p ), their moduli ( n_1 ) and ( n_2 ) are not coprime, i.e., ( \text{GCD}(n_1, n_2) = p ).
This shared prime can be used to:

1. Factorize ( n_1 ) and ( n_2 ).
2. Compute private keys for each RSA key.
3. Decrypt encrypted messages.

Step 2: Steps to Solve

1. Extract Public Keys:
   • Read the 100 public keys from the provided PEM files and extract ( n ) and ( e ).
2. Find Shared Factors:
   • Calculate the GCD for all pairs of ( n ) values to find shared prime factors.
3. Factorize ( n ):
   • For ( n_1 = p \times q ), where ( p ) is the shared factor, compute ( q = n_1 / p ).
4. Compute Private Key:
   • Use ( \phi = (p-1) \times (q-1) ) and ( e ) to compute ( d ) using the modular inverse ( d = e^{-1} \mod \phi ).
5. Decrypt Messages:
   • Use ( d ) and ( n ) to decrypt each ciphertext.

Step 3: Python Script

Key Functions:

1. Load Public Keys:

   from Crypto.PublicKey import RSA
   
   def load_public_key(file_path):
       with open(file_path, "rb") as f:
           return RSA.import_key(f.read())
   

2. Find Shared Factors:

   from Crypto.Util.number import GCD
   
   def find_shared_factor(n1, n2):
       return GCD(n1, n2)
   

3. Compute Private Key:

   from Crypto.Util.number import inverse
   
   def compute_private_key(n, e, p, q):
       phi = (p - 1) * (q - 1)
       return inverse(e, phi)
   

4. Decrypt Messages:

   def decrypt_rsa(ciphertext, n, d):
       return pow(ciphertext, d, n)
   

Full Script:

from Crypto.PublicKey import RSA
from Crypto.Util.number import inverse, long_to_bytes, GCD
import os

def load_public_key(file_path):
    with open(file_path, "rb") as f:
        pem_data = f.read()
        public_key = RSA.import_key(pem_data)
        return public_key

def load_public_keys_from_folder(folder_path):
    public_keys = []
    for i in range(100):  
        public_key = load_public_key(f"{folder_path}/public_key_{i}.pem")
        public_keys.append(public_key)
    return public_keys

def get_n_and_e(public_key):
    return public_key.n, public_key.e

def find_shared_factor(n1, n2):
    return GCD(n1, n2)

def compute_private_key(n, e, p, q):
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    return d

def decrypt_rsa(ciphertext, n, d):
    return pow(ciphertext, d, n)

public_keys = load_public_keys_from_folder("keys")

ns = [get_n_and_e(key)[0] for key in public_keys]
es = [get_n_and_e(key)[1] for key in public_keys]

shared_factors = []
for i in range(len(ns)):
    for j in range(i + 1, len(ns)):
        shared_factor = find_shared_factor(ns[i], ns[j])
        if shared_factor > 1:
            shared_factors.append(shared_factor)

private_keys = []
for shared_factor in shared_factors:
    for n in ns:
        if n % shared_factor == 0:
            p = shared_factor
            q = n // p
            for e in es:
                d = compute_private_key(n, e, p, q)
                private_keys.append({'n': n, 'd': d})

try:
    with open("encrypted_flags.txt", "r") as f:
        lines = f.readlines()
        print("Contenu du fichier encrypted_flags.txt :")
        for line in lines:
            print(line.strip())  

    if len(lines) < 2:
        raise ValueError("Le fichier ne contient pas assez de lignes. Assurez-vous qu'il y a une ligne d'en-tête et une ligne avec les valeurs chiffrées.")

    encrypted_flags_line = lines[1].strip()  
    
    encrypted_flags_line = encrypted_flags_line[1:-1]  
    encrypted_flags = encrypted_flags_line.split(", ")  
    encrypted_flags = [int(flag) for flag in encrypted_flags]  

except Exception as e:
    print(f"Erreur lors de la lecture ou du traitement du fichier: {e}")
    encrypted_flags = []

if encrypted_flags and private_keys:
    print("Messages chiffrés trouvés :", encrypted_flags)
    
    for encrypted_flag in encrypted_flags:
        for private_key in private_keys:
            n = private_key['n']
            d = private_key['d']
            decrypted_flag = decrypt_rsa(encrypted_flag, n, d)
            decrypted_flag_bytes = long_to_bytes(decrypted_flag)
            try:
                print(f"Decrypted flag with n = {n}: {decrypted_flag_bytes.decode(errors='ignore')}")
            except UnicodeDecodeError:
                print(f"Decrypted flag with n = {n} (bytes): {decrypted_flag_bytes}")
else:
    print("Aucun message chiffré trouvé ou problème avec le fichier.")