Adrien's Signs
Pour ce challenge à 80 points Adrien utilise des puissances aléatoires et un signe moins pour chiffrer chaque bit du flag. Il faut retrouver le message à partir des nombres obtenus.
Le challenge fournit un script Python et une liste d'entiers. Je commence par regarder comment cette liste est construite.
Lire le chiffrement
Le fichier source.py contient deux constantes publiques :
a = 288260533169915
p = 1007621497415251
Le programme convertit chaque octet du flag en huit bits :
plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
bin(i)[2:] récupère l'écriture binaire sans le préfixe 0b. Le zfill(8) ajoute les zéros nécessaires au début de chaque octet. On garde ainsi la bonne longueur pour reconstruire le message ensuite.
Pour chaque bit le script tire un exposant e puis calcule une puissance modulo p :
e = randint(1, p)
n = pow(a, e, p)
if b == '1':
ciphertext.append(n)
else:
ciphertext.append(-n % p)
Un bit à 1 donne donc a^e modulo p. Un bit à 0 donne son opposé. L'exposant change à chaque tour mais le choix du signe dépend directement du message.
Il faut trouver une propriété des puissances de a qui change avec ce signe.
Tester les constantes
Je vérifie le reste de p modulo 4 puis j'applique le critère d'Euler à a :
print("p modulo 4 :", p % 4)
print("Test d'Euler pour a :", pow(a, (p - 1) // 2, p))
p modulo 4 : 3
Test d'Euler pour a : 1
Le second résultat montre que a est un résidu quadratique modulo le premier p. Cela veut dire qu'il existe un entier x tel que a ≡ x² modulo p.
Toutes les puissances de a restent alors des carrés :
L'exposant aléatoire change la valeur obtenue mais pas cette propriété.
Comprendre le rôle du signe moins
Pour un premier impair le critère d'Euler distingue les résidus des non-résidus quadratiques. Sur un entier non nul n il donne :
p - 1 représente −1 modulo p.
Ici p % 4 == 3. L'exposant (p - 1) // 2 est donc impair. Appliqué à −1 le test donne −1. Le nombre −1 est ainsi un non-résidu quadratique.
Le produit d'un résidu par un non-résidu est un non-résidu. Le signe moins fait donc passer la puissance de a dans une classe différente que l'on peut reconnaître.
| Bit chiffré | Valeur envoyée | Test d'Euler |
|---|---|---|
1 | a^e mod p | 1 |
0 | -a^e mod p | p - 1 |
On peut lire chaque bit sans retrouver son exposant. Il n'y a pas de valeur nulle à traiter car a est non nul modulo p.
Reconstruire le message
Le fichier téléchargé s'appelle output_80fc6398d2fd9f272186d0af510323f9.txt. Il contient la liste des entiers à déchiffrer.
Depuis le dossier qui contient ce fichier je le renomme pour utiliser un nom plus court :
mv output_80fc6398d2fd9f272186d0af510323f9.txt output.txt
J'enregistre le script suivant dans solve.py. Il accepte le chemin du fichier en argument. Sans argument il cherche output.txt à côté de solve.py. literal_eval lit la liste sans exécuter son contenu comme le ferait eval.
from ast import literal_eval
from pathlib import Path
from sys import argv
a = 288260533169915
p = 1007621497415251
input_file = Path(argv[1]) if len(argv) > 1 else Path(__file__).with_name("output.txt")
ciphertext = literal_eval(input_file.read_text())
assert p % 4 == 3
assert pow(a, (p - 1) // 2, p) == 1
bits = []
for n in ciphertext:
test = pow(n, (p - 1) // 2, p)
assert test in (1, p - 1)
bits.append('1' if test == 1 else '0')
plaintext = ''.join(bits)
assert len(plaintext) % 8 == 0
flag = bytes(
int(plaintext[i:i + 8], 2)
for i in range(0, len(plaintext), 8)
)
print("Format du flag valide :", flag.startswith(b"crypto{") and flag.endswith(b"}"))
print(flag.decode())
pow(n, exposant, p) calcule directement la puissance modulaire. On évite de construire toute la puissance avant de prendre son reste.
La dernière conversion prend les bits par groupes de huit. int(..., 2) transforme chaque groupe en entier puis bytes reconstitue les octets du message.
Vérifier le résultat
Je lance le script depuis le dossier qui contient output.txt :
Format du flag valide : True
Le format seul ne prouve pas qu'un déchiffrement est correct. Ici il confirme que la conversion des bits produit bien le type de message attendu. La correspondance entre les bits et les deux résultats du critère d'Euler vient du calcul précédent.
Conclusion
Le critère d'Euler permet de retrouver chaque bit sans chercher les exposants aléatoires. Les puissances de a restent des résidus quadratiques alors que leur opposé est un non-résidu. Il suffit ensuite de regrouper les bits par huit pour reconstruire le message.