Le problème présente un code python implémentant un chiffrement El Gamal basé sur une courbe elliptique ainsi qu’un fichier texte contenant le flag une fois chiffré.
Le chiffrement El Gamal fonctionne de la manière suivante. On part d’une courbe elliptique $E$ sur un corps fini $F_p$ avec $p$ un (grand) nombre premier. Un point $g$ est choisi sur cette courbe, dont l’ordre $order$ est également un nombre premier, également grand mais plus petit que $p$. Enfin, un nombre $sk$ entre $0$ et $order-1$ est choisi au hasard et permet de calculer $pk = sk\cdot g$. Les informations auxquelles on a accès sont $p$, $E$, $g$, $pk$ mais $sk$ est gardé secret.
Pour chiffrer un message $m$, on le transforme en point $t=encode(m)\in E$ puis on choisit un entier $r\in [0,order-1]$ au hasard et on renvoie le couple $(u,v)=(r\cdot g,t+r\cdot pk)$. Le déchiffrement est possible connaissant $sk$ en calculant $$v-sk\cdot u = t+r\cdot pk - sk\cdot r\cdot g = t+r\cdot sk\cdot g - sk\cdot r\cdot g = t = encode(m)$$ à partir duquel on retrouve $m$.
La faille réside ici dans le fait que les caractères du flag sont chiffrés un par un, autrement dit octet par octet, ce qui ne laisse que $256$ possibilités à chaque fois. Etant donné une paire chiffrée $(u,v)$, si $c$ est le caractère correspondant, $v-encode(c)=r\cdot pk=r\cdot sk\cdot g$ donc $v-encode(c)\in G = {n\cdot g, n\in[0,order-1]}$. Les éléments $x=n\cdot g$ de $G$ vérifient $order\cdot x = order\cdot n\cdot g = n\cdot order\cdot g=O$. Ainsi, l’octet correspondant à la paire $(u,v)$ vérifie $$order\cdot(v-encode(c)) = O$$ On peut donc tester toutes les valeurs d’octet possibles jusqu’à trouver celui qui vérifie cette condition.
Empiriquement, on constate qu’il n’y a à chaque fois qu’une seule valeur qui vérifie la condition, et il y a de bonnes raisons pour cela. Un calcul avec SageMath montre que $|E|=p+1$, $p$ est premier, $order$ est premier, $order$ divise $p+1$ et $order^2$ ne divise pas $p+1$. Cela a pour conséquence (théorème de structure des groupes abéliens) que $G$ est l’unique sous-groupe de $E$ de d’ordre $order$ et ses éléments sont caractérisés exactement par la relation $order\cdot x=0$.
De plus, il est extrêmement improbable que la condition $v-encode(c)\in G$ soit vérifiée pour deux caractères différents $c1$ et $c2$ car on aurait alors $encode(c1)-encode(c2)\in G$ mais $|G|=order$ est très petit devant $|E| = p+1$ et $encode(c)$ ne prend que $256$ valeurs différentes.