Surface (Cryptanalyse) - FCSC2022

Principe:
Résoudre une équation sur les nombres congruents pour trouver une clef de chiffrement AES

Infos (cf menu latéral):
🚩 Flaggué! +477 points gagnés — 💾 Téléchargez les fichiers du challenge
FCSC{67084c2bc8acfbf5e8a0d5e2809e230d092ab56630713dbe33ca42b8430a992b}

Le challenge

On doit résoudre une équation pour retrouver une clef AES et déchiffrer le flag

Un problème de "surface"

On cherche A et B, fractions, telles que A2+B2 soit une fraction de deux carrés parfaits et A*B = 20478
En voulant faire une résolution analytique, je suis tombé sur sqrt(3) qui n'est pas rationnel…

J'ai donc cru, pendant un moment, que le challenge ne portait pas sur la résolution de l'équation (qui n'en aurait aucune), mais sur la présence d'une faille d'implémentation. Or, non, l'implémentation est juste, il faut seulement résoudre l'équation

D'autant que WolframAlpha n'a pas trouvé de solution non plus
Dans le doute, j'ai vérifié si A et B pouvaient être irrationnels (et que ce soit donc une faille d'implémentation) mais non, pas de faille

Sage

En cherchant, on trouve que Sage peut résoudre ce genre d'équation (non modulaire cette fois)
En continuant de creuser, il s'avère qu'il n'existe pas de solution générale à cette équation
On continue les recherche, et on croise la route du théorème de Tunnell…
…et la conjecture de Birch et Swinnerton-Dyer
Tout cela tourne autour du "problème des nombres congruents"

Des tables de solutions?

Ayant maintenant le nom des nombres correspondant à ce type d'équation, j'ai cherché s'il existait des tables de solutions: celle-ci s'arrête à 126

En cherchant d'autres tables, je suis tombé sur ce repo git et la table de solutions mais elle se limite à 10000, et non 20478

Un résolveur Sage

Dans ce repo Git, j'ai trouvé un résolveur Python et je l'ai lancé pour la valeur 10239

Pourquoi 10239 alors que le problème parle de 20478? Simplement parce que le problème des nombre congruents concerne l'aire du triangle rectangle A B alors que A*B représente l'aire du rectangle A B.
On prend donc la moitié de 20478 (soit 10239) pour nos calculs

alpha= 56016137442517383387573828442896545524 / 703489048873239645599627668340196935 beta= 7203024371413100731294587696135276417465 / 28008068721258691693786914221448272762
Le résolveur Python, basé sur Sage, trouve alors une solution Alpha Beta (qui correspond à notre A B)

Livraison

Cette fois, c'est simple: on copie/colle les valeurs trouvées ci-dessus et poof, ça marche!

Flag: FCSC{67084c2bc8acfbf5e8a0d5e2809e230d092ab56630713dbe33ca42b8430a992b}