09 - Cryptographie (3/3)

Auteur

Jérôme Soucy

Dernière mise à jour

05 février 2026 à 15:20

Question 1

Wilbrod utilise RSA pour communiquer avec sa douce Pauline. Il a choisi deux grands nombres premiers $p$ et $q$, qu’il garde secrets. Il a calculé $n$, le produit de $p$ et $q$, puis a rendu public ce nombre. Il a aussi choisi un nombre entier $e$ situé entre 1 et $\phi(n)$, copremier à $\phi(n)$, qu’il a également rendu public.

Pauline veut envoyer un message $m$, mais elle le chiffre deux fois à l’aide de la même clé publique $(n, e)$, obtenant ainsi un message chiffré $b$. La clé publique de Wilbrod satisfait $e^2\equiv 1\pmod{\phi(n)}$.

Expliquez pourquoi toute personne interceptant le message chiffré découvrira sans effort le message initial.

Solution. L’intercepteur verra directement le message de départ, car en chiffrant deux fois avec la clé publique, on revient au message initial $m$.

Si Wilbrod avait choisi $p = 3$ et $q = 11$, quelles valeurs de $e$ devait-il éviter pour que $e^2\equiv 1\pmod{\phi(n)}$ ne soit pas vrai ?

Solution. Les valeurs à éviter sont $1, 9, 11$, et $19$.

Question 2

Maria et Gontrand utilisent la méthode RSA pour communiquer. Ils utilisent le même module $n$, mais des exposants de chiffrement $e_M$ et $e_G$ différents, tels que $\text{pgcd}(e_M, e_G) = 1$. Dimitri intercepte les messages cryptés $c_M$ et $c_G$ et veut retrouver le message initial $m$.

Montrez que Dimitri peut retrouver le message initial $m$.

Solution. Dimitri peut utiliser la relation $c_M^{k_1}c_G^{k_2}\equiv m\pmod{n}$, où $k_1$ et $k_2$ sont tels que $k_1e_M + k_2e_G = 1$.

Si $e_M = 10$ et $e_G = 7$, trouvez deux entiers $x$ et $y$ tels que $e_Mx + e_Gy = 1$.

Solution. Une solution possible est $x = -2$ et $y = 3$.

Question 3

Énoncez le théorème d’Euler.

Solution. Soit $n$ un entier strictement positif, et soit $a \in \mathbb{Z}$ vérifiant $\text{pgcd}(a, n) = 1$. Alors : \[ a^{\phi(n)} \equiv 1 \pmod{n}, \] où $\phi(n)$ est la fonction indicatrice d’Euler.

Utilisez le théorème d’Euler pour trouver les deux derniers chiffres du nombre $7^{222}$.

Solution. Les deux derniers chiffres de $7^{222}$ sont $49$.

Soit $p$ un nombre premier. Montrez que : \[ 2^{p-1} + 3^{p-1} + \ldots + (p-1)^{p-1} \equiv -2 \pmod{p}. \]

Solution. En appliquant le petit théorème de Fermat à chaque terme, nous trouvons que la somme totale est équivalente à $(p - 2) \pmod{p}$, soit $-2 \pmod{p}$.

Question 4

Trouvez les trois derniers chiffres du nombre $43^{402}$ avec l’aide d’une calculatrice, mais pas d’un ordinateur.

Solution. Les trois derniers chiffres de $43^{402}$ sont $849$.

Montrez que pour tout entier $n$, $n(n^4 - 1)$ est divisible par $15$.

Solution. Pour tout $n$, $n(n^4 - 1)$ est un produit contenant les facteurs $n - 1$, $n$, et $n + 1$, qui sont trois entiers consécutifs. Un de ces nombres est divisible par 3 et un autre par 5. Ainsi, le produit est divisible par $15$.

Montrez que pour tout entier $n$, $n^2(n^4 - 1)$ est divisible par $60$.

Solution. Le raisonnement est similaire au précédent, mais en incluant $n^2$, qui garantit un facteur de 4 (puisque $n^2$ est pair). Par conséquent, le produit est divisible par $4 \times 15 = 60$.

Question 5

On choisit deux nombres premiers $p$ et $q$ congrus à $2$ modulo $3$. On pose $n = p \cdot q$, puis on chiffre un message $x$ par $y \equiv x^3 \pmod{n}$. Le déchiffrement se fait par $z \equiv y^d \pmod{n}$, où : \[ d = \frac{2(p - 1)(q - 1) + 1}{3}. \]

Montrez que $d$ est un entier.

Solution. Puisque $p$ et $q$ sont congrus à $2$ modulo $3$, il existe des entiers $a$ et $b$ tels que $p = 3a + 2$ et $q = 3b + 2$. Substituant dans l’expression de $d$, on montre que $d$ est un entier.

Montrez que $y$ et $z$ ne sont pas congrus à $0$ modulo $n$.

Solution. Si $y \equiv 0 \pmod{n}$, alors $x^3 \equiv 0 \pmod{n}$, ce qui impliquerait que $n \mid x^3$. Mais cela est impossible car $\text{pgcd}(x, n) = 1$. Un raisonnement similaire s’applique pour $z$.

Montrez que $z\equiv x\pmod{n}$, c’est-à-dire que le déchiffrement fonctionne.

Solution. En utilisant le théorème d’Euler et la relation $d = \frac{2(p-1)(q-1) + 1}{3}$, nous montrons que $z \equiv x \pmod{n}$.

--- title: "09 - Cryptographie (3/3)" author: "Jérôme Soucy" --- ## Question 1 Wilbrod utilise RSA pour communiquer avec sa douce Pauline. Il a choisi deux grands nombres premiers $p$ et $q$, qu'il garde secrets. Il a calculé $n$, le produit de $p$ et $q$, puis a rendu public ce nombre. Il a aussi choisi un nombre entier $e$ situé entre 1 et $\phi(n)$, copremier à $\phi(n)$, qu'il a également rendu public. Pauline veut envoyer un message $m$, mais elle le chiffre deux fois à l'aide de la même clé publique $(n, e)$, obtenant ainsi un message chiffré $b$. La clé publique de Wilbrod satisfait $e^2\equiv 1\pmod{\phi(n)}$. 1. Expliquez pourquoi toute personne interceptant le message chiffré découvrira sans effort le message initial. ::: solution L'intercepteur verra directement le message de départ, car en chiffrant deux fois avec la clé publique, on revient au message initial $m$. ::: 2. Si Wilbrod avait choisi $p = 3$ et $q = 11$, quelles valeurs de $e$ devait-il éviter pour que $e^2\equiv 1\pmod{\phi(n)}$ ne soit pas vrai ? ::: solution Les valeurs à éviter sont $1, 9, 11$, et $19$. ::: --- ## Question 2 Maria et Gontrand utilisent la méthode RSA pour communiquer. Ils utilisent le même module $n$, mais des exposants de chiffrement $e_M$ et $e_G$ différents, tels que $\text{pgcd}(e_M, e_G) = 1$. Dimitri intercepte les messages cryptés $c_M$ et $c_G$ et veut retrouver le message initial $m$. 1. Montrez que Dimitri peut retrouver le message initial $m$. ::: solution Dimitri peut utiliser la relation $c_M^{k_1}c_G^{k_2}\equiv m\pmod{n}$, où $k_1$ et $k_2$ sont tels que $k_1e_M + k_2e_G = 1$. ::: 2. Si $e_M = 10$ et $e_G = 7$, trouvez deux entiers $x$ et $y$ tels que $e_Mx + e_Gy = 1$. ::: solution Une solution possible est $x = -2$ et $y = 3$. ::: --- ## Question 3 1. Énoncez le théorème d'Euler. ::: solution Soit $n$ un entier strictement positif, et soit $a \in \mathbb{Z}$ vérifiant $\text{pgcd}(a, n) = 1$. Alors : $$ a^{\phi(n)} \equiv 1 \pmod{n}, $$ où $\phi(n)$ est la fonction indicatrice d'Euler. ::: 2. Utilisez le théorème d'Euler pour trouver les deux derniers chiffres du nombre $7^{222}$. ::: solution Les deux derniers chiffres de $7^{222}$ sont $49$. ::: 3. Soit $p$ un nombre premier. Montrez que : $$ 2^{p-1} + 3^{p-1} + \ldots + (p-1)^{p-1} \equiv -2 \pmod{p}. $$ ::: solution En appliquant le petit théorème de Fermat à chaque terme, nous trouvons que la somme totale est équivalente à $(p - 2) \pmod{p}$, soit $-2 \pmod{p}$. ::: --- ## Question 4 1. Trouvez les trois derniers chiffres du nombre $43^{402}$ avec l'aide d'une calculatrice, mais pas d'un ordinateur. ::: solution Les trois derniers chiffres de $43^{402}$ sont $849$. ::: 2. Montrez que pour tout entier $n$, $n(n^4 - 1)$ est divisible par $15$. ::: solution Pour tout $n$, $n(n^4 - 1)$ est un produit contenant les facteurs $n - 1$, $n$, et $n + 1$, qui sont trois entiers consécutifs. Un de ces nombres est divisible par 3 et un autre par 5. Ainsi, le produit est divisible par $15$. ::: 3. Montrez que pour tout entier $n$, $n^2(n^4 - 1)$ est divisible par $60$. ::: solution Le raisonnement est similaire au précédent, mais en incluant $n^2$, qui garantit un facteur de 4 (puisque $n^2$ est pair). Par conséquent, le produit est divisible par $4 \times 15 = 60$. ::: --- ## Question 5 On choisit deux nombres premiers $p$ et $q$ congrus à $2$ modulo $3$. On pose $n = p \cdot q$, puis on chiffre un message $x$ par $y \equiv x^3 \pmod{n}$. Le déchiffrement se fait par $z \equiv y^d \pmod{n}$, où : $$ d = \frac{2(p - 1)(q - 1) + 1}{3}. $$ 1. Montrez que $d$ est un entier. ::: solution Puisque $p$ et $q$ sont congrus à $2$ modulo $3$, il existe des entiers $a$ et $b$ tels que $p = 3a + 2$ et $q = 3b + 2$. Substituant dans l'expression de $d$, on montre que $d$ est un entier. ::: 2. Montrez que $y$ et $z$ ne sont pas congrus à $0$ modulo $n$. ::: solution Si $y \equiv 0 \pmod{n}$, alors $x^3 \equiv 0 \pmod{n}$, ce qui impliquerait que $n \mid x^3$. Mais cela est impossible car $\text{pgcd}(x, n) = 1$. Un raisonnement similaire s'applique pour $z$. ::: 3. Montrez que $z\equiv x\pmod{n}$, c'est-à-dire que le déchiffrement fonctionne. ::: solution En utilisant le théorème d'Euler et la relation $d = \frac{2(p-1)(q-1) + 1}{3}$, nous montrons que $z \equiv x \pmod{n}$. :::