Objectif
Dans ce challenge, il nous est demandé de retrouver le déchiffré du message $c$.
Pour ce faire on nous donne la clé publique qui a servi à obtenir $c$.
Réalisation
Nous voulons tout d’abord récupérer la clé privée associéé à la clé publique fournit pour pouvoir déchiffrer le message.
Cela se réalise en 3 étapes :
- retrouver $p$ et $q$, les deux nombres premiers tel que : $p\times q = n$ ;
- retrouver $d$, exposant de la clé privée tel que : $e \times d \equiv 1 \pmod{\varphi(n)}$, où $\varphi(n)$ est la valeur de l’indicatrice d’euler en $n$ ;
- déchiffrer $c$ en utilisant la clé privée.
Étape 1
On veux $p$ et $q$, les deux nombres premiers tel que : $$p\times q = n$$
Pour ce faire, on peut soit réaliser un algorithme de factorisation, soit utiliser le site factorDB qui est une base de données répertoriant des factorisations de grands nombres.
Ici notre $n$ est répertorié dans la base. Nous obtenons donc directement $p$ et $q$ :
$$p = 650655447295098801102272374367,$$ $$q = 972033825117160941379425504503.$$
Étape 2
On veux $d$, exposant de la clé privée tel que : $$e * d \equiv 1\mod(\varphi(n))$$ ou $\varphi(n)$ est la valeur de l’indicatrice d’euler en $n$.
On cherche alors l’inverse modulaire de $e$ modulo $\varphi(n)$.
Pour se faire on utilise l’algorithme d’Euclide étendu.
Le code python suivant présente l’algorithme d’Euclide étendu ainsi que son utilisation pour trouver l’inverse modulaire en python.
def extended_euclidean(a, b):
if a == 0: return (b, 0, 1)
else:
g, y, x = extended_euclidean(b % a, a)
return (g, x - (b // a) * y, y)
def modular_inv(a, m):
g, x, y = extended_euclidean(a, m)
return x % m
Pour trouver $d$ il faut donc remplacer $a$ par $e$ et $m$ par $\varphi(n)$ dans les paramètres de la fonction $modular_inv()$.
Ici, par le thm de Euler-Fermat, on a : $$\varphi(n) = (p - 1) \times (q - 1).$$
Donc :
d = modular_inv(e, (p-1) \times (q-1))
Dans le langage Python, à partir de la version 3.8, on peut aussi trouver l’inverse modulaire en faisant :
d = pow(e, -1, (p-1) * (q-1))
au lieu de refaire l’algorithme présenté ci-dessus.
Étape 3
Maintenant que nous avons la clé privée, on suit l’algorithme RSA pour le déchiffrement qui nous dit que : $$m \equiv c^d\mod(n).$$
On a alors :
m = pow(c, d, n)
Il nous suffit alors d’afficher $m$ pour obtenir le flag recherché : FCSC{563694726501963824567957403529535003815080102246078401707923}.