AdveRSArial Crypto (Baby)

Énoncé

J’ai perfectionné mes connaissances sur RSA, mais je ne suis pas sûr que ma manière creuse de générer les nombres soit intelligente. Vous confirmez ?

Source et ressources : hackropole.fr

Analyse

L'énigme suggère une génération "creuse" des nombres. En analysant n, on observe une quantité inhabituelle de zéros dans ses représentations en bases 2 et 16.

Cette observation nous amène à calculer le poids de Hamming de n en base 2, révélant que n peut être approximé par un polynôme de faible degré (49 bits à un sur 1025 bits).

Quelques rappels sur le RSA

Le chiffrement RSA est un algorithme de cryptographie asymétrique, s'appuyant sur la difficulté de la factorisation des grands nombres entiers. L'algorithme utilise une paire de clés : une clé publique pour le chiffrement et une clé privée pour le déchiffrement. Pour générer ces clés, on choisit deux grands nombres premiers, p et q, puis on calcule leur produit n = p * q, qui fait partie de la clé publique. L'autre partie de la clé publique est un exposant e, choisi de telle sorte qu'il soit premier avec (p-1)*(q-1). La clé privée, d, est le multiplicateur inverse de e modulo (p-1)*(q-1).

Pour chiffrer un message m, on utilise la formule:

c = m^{e} \mod n

Et pour déchiffrer le message, on applique:

m = c^{d} \mod n

Ces opérations assurent que seul le détenteur de la clé privée peut lire le message original, même si la clé publique et le message chiffré sont connus de tous.

Dans notre cas l'idée n'est pas de factoriser un nombre mais un polynome.

Factorisation de polynômes vs. Factorisation d'un nombre

La factorisation de polynômes est généralement plus efficace que la factorisation d'un grand nombre entier, principalement en raison de la structure et des propriétés des polynômes qui offrent plus de leviers pour l'optimisation des algorithmes. La complexité de la factorisation d'un entier croît exponentiellement avec la taille de l'entier, rendant la factorisation impraticable pour de très grands nombres. En revanche, plusieurs méthodes efficaces existent pour la factorisation des polynômes, comme l'algorithme de Berlekamp ou celui de Cantor-Zassenhaus, qui exploitent les propriétés algébriques des polynômes pour diviser le problème en sous-problèmes plus simples.

Par exemple, la factorisation sur des corps finis permet de réduire le problème initial en plusieurs instances de taille plus petite, pour lesquelles la factorisation peut être réalisée plus rapidement. De plus, les polynômes peuvent être manipulés de manière à exploiter des symétries ou des structures particulières (comme la parcimonie des coefficients) qui ne sont pas directement accessibles lors de la factorisation d'entiers.

Ces différences fondamentales font que, pour une taille de problème comparable, factoriser un polynôme peut être significativement moins coûteux en termes de ressources computationnelles que de factoriser un grand nombre entier.

Solution à notre problème

Sachant qu'on peut obtenir un polynome avec un nombre de termes "faible", correspond à la distance de hamming en base y. Il suffit de trouver une base y dont la distance de hamming est le plus faible possible. Pour ce challenge, les bases 2 et 16 marchent très bien, on prendra par la suite un polynome en base 2.

Méthode de résolution

Pour extraire p et q de n, on peut suivre cette approche :

Identifier le polynôme de degré k représentant n en base y.
Factoriser ce polynôme. Si n = p * q, la factorisation devrait révéler deux polynômes.
Obtenir p et q en substituant la base du polynôme polynome(x) par x = y.
Calculer phi et ensuite d en utilisant p et q.
Décrypter c avec la clé trouvée.

Script de résolution

Pré-requis :

Sagemath (installation)
Pycryptodome (sage --pip install pycryptodome)

Le script suivant permet de retrouver le flag :

python

#!/usr/bin/env sage

from sage.all import *
from Crypto.Util.number import inverse, long_to_bytes

def from_assignation_texte(texte, base=10):
    '''Retourne le nombre associé à une opération d'assignation dans une ligne texte. Exemple : retourne 456 si le texte entrant est 'variable = 465' '''
    return Integer(int(texte.split("=")[1].strip(), base))

# Récupération des données de l'énoncé (output.txt)
with open("fichiers/output.txt", "r") as f:
    n = from_assignation_texte(f.readline())
    e = from_assignation_texte(f.readline())
    c = from_assignation_texte(f.readline(), 16)

# Construction du polynôme représentant n en base 2
poly = sum(e * x^i for i, e in enumerate(n.digits(2)))

# Factorisation du polynôme
factors = poly.factor_list()
(p_poly, _), (q_poly, _) = factors[0], factors[1]
p, q = p_poly(x=2), q_poly(x=2)

# Calcul de la clé privée RSA
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

# Décryptage du message chiffré
m = int(pow(c, d, n))

# Conversion du message en octets et affichage
flag = long_to_bytes(m)
print(flag)

#!/usr/bin/env sage

from sage.all import *
from Crypto.Util.number import inverse, long_to_bytes

def from_assignation_texte(texte, base=10):
    '''Retourne le nombre associé à une opération d'assignation dans une ligne texte. Exemple : retourne 456 si le texte entrant est 'variable = 465' '''
    return Integer(int(texte.split("=")[1].strip(), base))

# Récupération des données de l'énoncé (output.txt)
with open("fichiers/output.txt", "r") as f:
    n = from_assignation_texte(f.readline())
    e = from_assignation_texte(f.readline())
    c = from_assignation_texte(f.readline(), 16)

# Construction du polynôme représentant n en base 2
poly = sum(e * x^i for i, e in enumerate(n.digits(2)))

# Factorisation du polynôme
factors = poly.factor_list()
(p_poly, _), (q_poly, _) = factors[0], factors[1]
p, q = p_poly(x=2), q_poly(x=2)

# Calcul de la clé privée RSA
phi = (p - 1) * (q - 1)
d = inverse(e, phi)

# Décryptage du message chiffré
m = int(pow(c, d, n))

# Conversion du message en octets et affichage
flag = long_to_bytes(m)
print(flag)

AdveRSArial Crypto (Baby) ​

Énoncé ​

Analyse ​

Quelques rappels sur le RSA ​

Factorisation de polynômes vs. Factorisation d'un nombre ​

Solution à notre problème ​

Script de résolution ​