← Retour à CryptoHack

CryptoHack | Real Eisenstein

•8 min•Très difficile

Real Eisenstein

Énoncé du challenge Real Eisenstein sur CryptoHack

Pour ce challenge à 150 points le programme transforme un flag en une somme de racines carrées de nombres premiers. Chaque caractère sert de coefficient. On reçoit ensuite une approximation très précise de cette somme sous forme d'entier.

Il faut retrouver les caractères à partir de cette seule valeur. Comme leurs codes sont petits et qu'une partie du flag est connue on peut ramener le problème à une recherche de vecteur court avec LLL.

Comprendre le calcul

Le fichier real_eisenstein.py contient ce code :

import math
from decimal import Decimal, getcontext

getcontext().prec = 100

FLAG = "crypto{???????????????}"

PRIMES = [
    2, 3, 5, 7, 11, 13, 17, 19, 23,
    29, 31, 37, 41, 43, 47, 53, 59, 61,
    67, 71, 73, 79, 83, 89, 97, 101, 103,
]

h = Decimal(0)

for i, c in enumerate(FLAG):
    h += ord(c) * Decimal(PRIMES[i]).sqrt()

ct = math.floor(h * 16**64)
print(f"ciphertext: {ct}")

ord(c) donne le code du caractère. Le programme le multiplie par la racine carrée du premier placé au même indice puis ajoute le résultat à h.

Pour les 23 caractères du flag on a donc :

h=∑i=022aipih = \sum_{i=0}^{22} a_i\sqrt{p_i}

a_i représente le code du caractère et p_i le nombre premier associé. La liste contient 27 premiers mais seuls les 23 premiers sont utilisés ici.

Le programme multiplie ensuite la somme par 16**64 et prend sa partie entière. Comme 16**64 = 2**256 on obtient :

ct=⌊2256h⌋ct = \left\lfloor 2^{256}h \right\rfloor

getcontext().prec = 100 fixe la précision des opérations Decimal à 100 chiffres significatifs. Le ciphertext conserve donc beaucoup d'informations sur la somme de départ.

Isoler les caractères inconnus

Le préfixe occupe les indices 0 à 6. Les caractères à retrouver sont aux indices 7 à 21 et l'accolade finale est à l'indice 22.

Il n'y a pas de clé secrète dans ce calcul. On connaît les nombres premiers et la manière dont ils sont combinés. Les seules inconnues sont les quinze coefficients qui correspondent au contenu du flag.

Tester toutes les chaînes possibles demanderait trop de calculs. En revanche ces coefficients sont petits puisqu'ils représentent des caractères ASCII. C'est cette contrainte qui va servir pour la réduction de réseau.

Passer des racines aux entiers

Pour construire le réseau je remplace chaque racine par une approximation entière à la même échelle que le ciphertext :

S=2256Ai=⌊Spi⌋S = 2^{256} \qquad A_i = \left\lfloor S\sqrt{p_i} \right\rfloor

On peut calculer ces valeurs sans utiliser de nombres flottants :

from math import isqrt

scale = 2**256
a = [isqrt(p * scale**2) for p in primes]

isqrt(n) renvoie la partie entière de la racine carrée de l'entier n. Comme S est positif la racine de p × S² vaut S × sqrt(p).

Les valeurs A_i sont donc calculées exactement avec de l'arithmétique entière. Un float Python n'aurait pas assez de précision pour conserver les informations nécessaires à cette échelle.

Je retire ensuite les contributions connues :

known = sum(ord(c) * a[i] for i, c in enumerate(prefix))
known += ord("}") * a[22]
target = ct - known

Il reste une relation approchée sur les quinze caractères :

T≈∑i=721aiAiT \approx \sum_{i=7}^{21} a_i A_i

Ce n'est pas une égalité exacte. Le programme arrondit la somme finale alors que les A_i sont arrondis séparément. Cette différence reste petite par rapport à la taille des entiers manipulés.

Centrer les coefficients

Je centre les codes autour de 79 :

xi=ai−79x_i = a_i - 79

Les nouveaux coefficients sont plus proches de zéro. Par exemple un caractère de code 97 donne un coefficient de 18.

Il faut retirer la même contribution de la cible :

T′=T−79∑i=721AiT' = T - 79\sum_{i=7}^{21} A_i

En Python :

center = 79
target -= center * sum(a[7:22])

On cherche maintenant de petits entiers x_i tels que :

∑i=721xiAi−T′≈0\sum_{i=7}^{21} x_i A_i - T' \approx 0

Le choix de 79 sert à centrer la recherche. Il ne correspond pas à une information secrète sur le flag.

Construire le réseau

Un réseau est l'ensemble des combinaisons entières des vecteurs de sa base. Ici je construis une matrice de 16 lignes et 16 colonnes :

B=(10⋯0A701⋯0A8⋮⋮⋱⋮⋮00⋯1A2100⋯0−T′)B = \begin{pmatrix} 1 & 0 & \cdots & 0 & A_7 \\ 0 & 1 & \cdots & 0 & A_8 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & A_{21} \\ 0 & 0 & \cdots & 0 & -T' \end{pmatrix}

Les quinze premières colonnes gardent les coefficients de la combinaison. La dernière contient la somme construite avec les A_i et la cible.

Avec les bons coefficients et une fois la dernière ligne ajoutée on obtient un vecteur de la forme :

(x7,…,x21,∑i=721xiAi−T′)\left(x_7,\ldots,x_{21},\sum_{i=7}^{21}x_i A_i - T'\right)

Ses premières coordonnées sont petites grâce au centrage. Sa dernière coordonnée est également petite car les contributions correspondent presque au ciphertext.

C'est donc un vecteur court dans ce réseau.

Réduire la base avec LLL

LLL signifie Lenstra-Lenstra-Lovász. L'algorithme transforme une base de réseau en une autre base du même réseau avec des vecteurs relativement courts.

LLL cherche des vecteurs courts sans forcément trouver le plus court. Ici l'un des vecteurs obtenus contient les coefficients qu'on cherche.

SageMath fournit la méthode LLL() pour réduire la base :

basis = Matrix(ZZ, rows)
reduced = basis.LLL()

ZZ indique que la matrice contient des entiers. Je parcours ensuite les lignes obtenues et je teste les deux signes. Un vecteur et son opposé appartiennent au même réseau.

Pour chaque ligne je remets le centre 79 puis je conserve les candidats dont les codes sont compris entre 32 et 126. Cela correspond aux caractères ASCII imprimables.

Une chaîne lisible n'est pas forcément la bonne. Je recalcule donc le ciphertext avec Decimal pour vérifier chaque résultat.

Script de résolution

Le script regroupe le calcul des racines, le retrait des caractères connus et la réduction de la matrice avec SageMath.

from decimal import Decimal, getcontext
from math import floor, isqrt
from sage.all import Matrix, ZZ

getcontext().prec = 100

primes = [
    2, 3, 5, 7, 11, 13, 17, 19, 23,
    29, 31, 37, 41, 43, 47, 53, 59, 61,
    67, 71, 73, 79, 83, 89, 97, 101, 103,
]

ct = 1350995397927355657956786955603012410260017344805998076702828160316695004588429433

prefix = "crypto{"
suffix = "}"
scale = 2**256
center = 79
unknown_count = 15

a = [isqrt(p * scale**2) for p in primes]

known = sum(ord(c) * a[i] for i, c in enumerate(prefix))
known += ord(suffix) * a[22]
target = ct - known - center * sum(a[7:22])

rows = []

for i in range(unknown_count):
    row = [0] * (unknown_count + 1)
    row[i] = 1
    row[-1] = a[i + len(prefix)]
    rows.append(row)

rows.append([0] * unknown_count + [-target])
reduced = Matrix(ZZ, rows).LLL()

for row in reduced.rows():
    for sign in (1, -1):
        values = [center + sign * int(x) for x in row[:unknown_count]]

        if not all(32 <= value <= 126 for value in values):
            continue

        flag = prefix + "".join(map(chr, values)) + suffix

        h = Decimal(0)
        for i, c in enumerate(flag):
            h += ord(c) * Decimal(primes[i]).sqrt()

        if floor(h * 16**64) == ct:
            print("flag:", flag)
            raise SystemExit

print("Flag non trouvé")

Le dernier test reprend le calcul du challenge avec la même précision de 100 chiffres. On garde uniquement la chaîne qui redonne exactement ct.

Vérifier le résultat

Le calcul redonne exactement le ciphertext fourni. On retrouve donc le flag attendu.

Résultat du script de résolution de Real Eisenstein

Conclusion

Le ciphertext conserve une approximation très précise d'une somme dont les coefficients sont petits. Le format connu du flag permet de retirer une partie des termes et de limiter la recherche à quinze caractères.

En centrant ces coefficients on peut représenter la solution par un vecteur court dans un réseau. La réduction LLL fournit alors un candidat que l'on vérifie avec le programme original.

Références

Voir aussi d'autres catégories...

Ces thèmes pourraient aussi t'intéresser.