M1 Cryptographie

Mise à niveau en arithmétique

Exercices à résoudre sur papier, n'utiliser l'ordinateur que comme calculette

Exercice 1

$\def\ZZ{{\mathbb Z}}$

1. Calculer la table de multiplication de $\ZZ/9\ZZ$. On note $G_9$ le groupe de ses éléments inversibles.
2. Donner la liste des éléments de $G_9$ et la valeur de $\varphi(9)$. Comparer avec la formule du cours pour $\varphi(n)$.
3. Vérifier que 2 est d'ordre $\varphi(9)$. Quel est l'ordre de 4 ? Et celui de 8 ?
4. Pour chaque élément de $G_9$ indiquer son inverse.
5. Le groupe $G_9$ est-il cyclique ?

Exercice 2

Calculer le pgcd $d$ de $a=561$ et $b=476$ par l'algorithme d'Euclide étendu, et trouver $u$ et $v$ tels que $d=au+bv$.

Exercice 3

On va utiliser le système RSA avec $p=11$, $q=13$.

1. Calculer $n=pq$, et écrire $p,q,n$ en binaire.
2. En conclure qu'on peut utiliser ce système pour chiffrer les caractères ASCII (codes de 0 à 127)
3. Calculer $\varphi(n)$.
4. Peut-on utiliser l'exposant public $e=3$ ? Pourquoi ?
5. On choisit $e=17$. Calculer l'exposant privé $d$.
6. Si on prenait $e=11$, quel serait l'exposant privé ?

Exercice 4

Résoudre $$\left\{\begin{matrix}x\equiv 2\ [3]\\ x\equiv 3\ [5]\\ x\equiv 2 \ [7]\end{matrix}\right.$$

ensuite, regarder là.

Exercice 5

1. Calculer $42^{666}\mod 43$.
2. Sachant que $p=2^{107}-1$ est premier, calculer $2^{(2^{108})}\mod p$.
3. Prouver que $2^{70}+3^{70}$ est divisible par 13.