CryptoHack | Modular Binomials

Modular Binomials

Pour ce challenge à 80 points on reçoit un entier N et deux expressions qui dépendent de ses facteurs premiers. Il faut retrouver p et q sans les connaître au départ.

L'idée est de combiner les deux expressions pour obtenir un multiple de l'un des facteurs. Un PGCD avec N permet ensuite de le récupérer.

Comprendre les données

Le fichier data.txt contient cinq entiers : N, e1, e2, c1 et c2.

N est le produit des deux nombres premiers recherchés :

Les deux autres valeurs sont calculées avec des combinaisons de ces facteurs :

Les coefficients 2, 3, 5 et 7 sont publics. Les exposants le sont aussi. Ce sont ces relations qui vont permettre de factoriser N.

Travailler modulo p

Je commence par regarder ce que deviennent les équations modulo p. Un multiple de p vaut zéro dans ce calcul. Les termes 2p et 5p disparaissent donc :

Pour info : une égalité modulo N reste vraie modulo p car p divise N. On peut raisonner modulo ce facteur sans encore connaître sa valeur.

Les deux expressions ne dépendent plus que de q. Il reste à leur donner le même exposant pour pouvoir les combiner.

Mettre les puissances au même niveau

J'élève c1 à la puissance e2 et c2 à la puissance e1. Dans les deux cas l'exposant sur q devient le produit des deux exposants. Je note ce produit k :

On obtient alors :

Pour obtenir le même coefficient devant q^k je multiplie la première expression par 7^k et la seconde par 3^k :

Les deux membres de droite sont identiques. Leur différence vaut donc zéro modulo p :

Cela signifie que D est un multiple de p.

Retrouver les facteurs avec un PGCD

N et D sont tous les deux divisibles par p. Leur plus grand diviseur commun permet de retrouver ce facteur :

Il faut vérifier que le PGCD est strictement compris entre 1 et N. Si D était aussi divisible par q on obtiendrait N et la factorisation ne serait pas terminée. Sur les données du challenge le calcul donne bien un facteur non trivial.

Pour info : on peut réduire tous les calculs modulo N avant le PGCD car gcd(N, D) = gcd(N, D mod N).

Script de résolution

from math import gcd
from pathlib import Path
from sys import argv

input_file = Path(argv[1]) if len(argv) > 1 else Path(__file__).with_name("data.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"]
e1 = values["e1"]
e2 = values["e2"]
c1 = values["c1"]
c2 = values["c2"]

k = e1 * e2

a = pow(c1, e2, N) * pow(7, k, N) % N
b = pow(c2, e1, N) * pow(3, k, N) % N

p = gcd((a - b) % N, N)
assert 1 < p < N, "Le PGCD ne donne pas de facteur non trivial"
q = N // p

verification = (
    p * q == N
    and pow(2 * p + 3 * q, e1, N) == c1
    and pow(5 * p + 7 * q, e2, N) == c2
)
assert verification, "Les facteurs ne correspondent pas aux données"

print("p =", p)
print("q =", q)
print("verification =", verification)

Chaque ligne du fichier contient une affectation nom = entier. Je sépare les deux parties puis je convertis la valeur avec int.

pow(a, b, N) calcule directement une puissance modulo N. Le % N après chaque produit garde aussi les résultats intermédiaires inférieurs à N.

Vérifier le résultat

Le script retrouve les deux facteurs et affiche :

verification = True

Cela confirme que p et q correspondent aux coefficients utilisés dans l'énoncé et pas seulement à une factorisation de N.

Conclusion

Les deux expressions publiques permettent d'éliminer q en travaillant modulo p. En mettant les puissances au même exposant puis en ajustant leurs coefficients on obtient un multiple de p. Un PGCD avec N suffit alors à retrouver ce facteur.

Références

• Modular Binomials sur CryptoHack