Exercice 17

1. On pose $p = 3$, $q = 11$ et $n = pq$. Combien vaut $\phi(n)$ ?
2. Donner (dans l'ordre croissant) la liste des éléments non inversibles modulo $33$.
3. Déterminez $\phi(n)$ en utilisant la question précédente, vérifiez si ce résultat concorde avec celui de la première question.
4. Calculez le $pgcd$ de $20$ et $8$ en utilisant l'algorithme d'Euclide.
5. Utilisez la question précédente pour dire si $8$ et $20$ sont-ils premiers entre eux ?
6. Est-il possible d'utiliser $(8, 33)$ comme clé de chiffrement ?
7. Est-il possible d'utiliser $(13, 33)$ comme clé de chiffrement ? Justifiez votre réponse.
8. On prend comme clé de chiffrement le couple $(13, 33)$. Chiffrer le message $4$.
9. Donner dans l'ordre croissant la liste des éléments non inversibles modulo $20$.
10. Donner la valeur de $\phi(20)$.
11. Que représente la valeur $a^{\phi(n) - 1}\ mod\ n$ par rapport à $a$ ?
12. Utiliser la question précédente pour déterminer l'inverse de $13$ modulo $20$.
13. Quelle est la clé de déchiffrement associée à la clé de chiffrement $(13, 33)$ ?
14. Utilisez l'algorithme d'Euclide étendu pour déterminer $u$ et $v$ tels que $13u + 20v = 1$.
15. Déduire de la question précédente la clé de déchiffrement associé à la clé de chiffrement $(13, 33)$. Est-ce que cela correspond à la clé que vous aviez trouvé ?
16. Calculez $31^{17}\ mod\ 33$
17. Déchiffrez le message $31$, vérifiez votre résultat.