Broken RSA
Pour ce challenge à 100 points on reçoit un message chiffré avec RSA. Le modulo est premier et l'exposant public vaut 16. Ces paramètres empêchent de déchiffrer avec la méthode habituelle mais permettent de chercher le message avec des racines carrées modulaires.
L'énoncé donne aussi un indice : si le résultat semble illisible il faut vérifier toutes les solutions possibles.
Comprendre les données
Le fichier broken_rsa.txt fournit trois entiers : n, e et ct.
n est le modulo. e est l'exposant public et ct contient le résultat du chiffrement. Le message converti en entier est noté m :
Dans un RSA classique le modulo est le produit de deux nombres premiers. Ici n est lui-même premier. On peut le vérifier avec isprime de SymPy puis calculer le PGCD de e et n - 1 :
from math import gcd
from sympy import isprime
print("n premier :", isprime(n))
print("PGCD de e et n - 1 :", gcd(e, n - 1))
Avec les valeurs du fichier on obtient :
n premier : True
PGCD de e et n - 1 : 8
Pourquoi le déchiffrement habituel bloque
Pour déchiffrer RSA on cherche normalement un exposant privé d qui inverse e modulo la fonction indicatrice d'Euler :
Comme n est premier on connaît directement cette valeur :
Mais un inverse modulaire existe seulement si les deux entiers sont premiers entre eux. Ici le PGCD vaut 8. On ne peut donc pas calculer d de cette façon.
Pour info : connaître
φ(n)ne suffit pas à déchiffrer avec une clé privée si l'exposant choisi n'est pas inversible. Plusieurs messages peuvent alors donner le même ciphertext.
Remonter les puissances de deux
L'exposant 16 est une puissance de deux :
Le chiffrement revient donc à élever quatre fois le message au carré modulo n. Pour remonter dans l'autre sens il faut calculer quatre racines carrées successives :
On cherche des racines modulaires. Prendre une racine carrée ordinaire de l'entier ct ne permet pas d'annuler les réductions modulo n.
Garder toutes les racines
Pour un premier impair une valeur non nulle qui possède une racine carrée en possède deux. Si r est une racine alors n - r en est une aussi :
Choisir une seule racine à chaque étape risque d'écarter le message recherché. Je garde donc toutes les solutions avec sqrt_mod(x, n, all_roots=True).
Cette fonction renvoie les deux racines lorsqu'elles existent. Si une valeur n'est pas un résidu quadratique elle renvoie une liste vide. Cette branche disparaît au tour suivant.
Un ensemble Python set permet de conserver les candidats sans doublons. Pour les données du challenge le nombre de candidats évolue ainsi :
Étape 1 : 2 candidats
Étape 2 : 4 candidats
Étape 3 : 8 candidats
Étape 4 : 8 candidats
On ne double donc pas forcément le nombre de candidats à chaque tour. Au dernier tour certaines branches ne possèdent pas de racine.
Script de résolution
Le script utilise SymPy pour calculer les racines modulaires :
from pathlib import Path
from sys import argv
from sympy.ntheory.residue_ntheory import sqrt_mod
input_file = Path(argv[1]) if len(argv) > 1 else Path(__file__).with_name("broken_rsa.txt")
values = {}
for line in input_file.read_text().splitlines():
if not line.strip():
continue
name, value = line.split("=", 1)
values[name.strip()] = int(value.strip())
n = values["n"]
e = values["e"]
ct = values["ct"]
assert e == 16
roots = {ct}
for step in range(1, 5):
roots = {
int(r)
for x in roots
for r in sqrt_mod(x, n, all_roots=True)
}
print(f"Étape {step} : {len(roots)} candidats")
for m in sorted(roots):
assert pow(m, e, n) == ct
data = m.to_bytes((m.bit_length() + 7) // 8, "big")
if b"crypto{" in data:
print(data.decode())
Le fichier ne contient que des affectations nom = entier. Une séparation sur = et une conversion avec int suffisent pour charger les valeurs sans utiliser exec.
Chaque tour remplace les candidats par leurs racines carrées. Après les quatre tours je vérifie que chaque entier retrouvé redonne bien ct lorsqu'on le rechiffre avec l'exposant 16.
Retrouver le message lisible
to_bytes reconstruit le message à partir de son entier. Le nombre d'octets est calculé avec bit_length puis arrondi au supérieur. L'ordre big place les octets de poids fort en premier.
Les huit candidats satisfont l'équation du chiffrement. Pour repérer le texte attendu je cherche le marqueur crypto{ dans les octets obtenus. Le test utilise in car le flag se trouve dans un message plus long.
Conclusion
L'exposant 16 n'a pas d'inverse modulo n - 1. Le chiffrement ne permet donc pas de retrouver un message unique avec une clé privée. Comme le modulo est premier on peut calculer les racines carrées modulaires et remonter les quatre élévations au carré.