Énoncé:
Le cryptage RSA est basé sur la procédure suivante :
Générer deux nombres premiers distincts $p$ et $q$.
Calculer $n=pq$ et $\phi=(p-1)(q-1)$.
Trouver un entier $e$, $1<e<\phi$, tel que $gcd(e,\phi)=1$.
Un message dans ce système est un nombre dans l'intervalle $[0,n-1]$.
Un texte à crypter est alors en quelque sorte converti en messages (nombres dans l'intervalle $[0,n-1]$).
Pour chiffrer le texte, pour chaque message, $m$, on calcule $c=m^e \mod n$.
Pour décrypter le texte, la procédure suivante est nécessaire: calculer $d$ tel que $ed=1 \mod \phi$, puis pour chaque message crypté, $c$, calculer $m=c^d \mod n$.
Il existe des valeurs de $e$ et de $m$ telles que $m^e \mod n=m$.
Nous appelons les messages $m$ pour lesquels $m^e \mod n=m$ des messages non dissimulés.
Un problème lors du choix de $e$ est qu'il ne doit pas y avoir trop de messages non dissimulés.
Par exemple, supposons que $p=19$ et $q=37$.
Alors $n=19 \times 37=703$ et $\phi=18 \times 36=648$.
Si nous choisissons $e=181$, alors, bien que $gcd(181,648)=1$ il s'avère que tous les messages possibles $m$ ($0 \le m \le n-1$) sont non dissimulés lors du calcul de $m^e \mod n$.
Pour tout choix valide de $e$, il existe des messages non dissimulés.
Il est important que le nombre de messages non dissimulés soit au minimum.
Choisissons $p=1009$ et $q=3643$.
Trouvez la somme de toutes les valeurs de $e$, $1<e<\phi(1009,3643)$ et $pgcd(e,\phi)=1$, pour que le nombre de messages non dissimulés pour cette valeur de $e$ soit minimal.
Lien du problème originel