ExerciceMaths expertes, chapitre 7 — PGCD · Approfondissements

Exercice 31 Cryptage RSA, tiré du BAC 2018

DémonstrationCalcul

Le but de cet exercice est d’envisager une méthode de cryptage à clé publique d’une information numérique, appelée système RSA, en l’honneur des mathématiciens Ronald Rivest, Adi Shamir et Leonard Adleman, qui ont inventé cette méthode de cryptage en $1977$ et l’ont publiée en $1978$ .

Les questions $1$ et $2$ sont des questions préparatoires, la question $3$ aborde le cryptage, la question $4$ le décryptage.

1. Cette question envisage de calculer le reste dans la division euclidienne par $55$ de certaines puissances de l’entier $8$ .

(a) Vérifier que $8^{7}\equiv 2 \; [55]$ . En déduire le reste de la division euclidienne par $55$ du nombre $8^{21}$ .

(b) Vérifier que $8^{2}\equiv 9 \; [55]$ puis en déduire à l'aide de la question $a)$ le reste de la division euclidienne par $55$ de $8^{23}$ .

2. Dans cette question, on considère l’équation $(E) \; : \; 23x-40y=1$ , dont les solutions sont des couples $(x,y)$ d’entiers relatifs.

(a) Justifier le fait que l’équation $(E)$ admet au moins un couple solution.

(b) Donner un couple, solution particulière de l’équation $(E)$ .

(c) Déterminer tous les couples d’entiers relatifs solutions de l’équation $(E)$ .

(d) En déduire qu’il existe un unique entier $d$ vérifiant les conditions $0\leqslant d<40$ et $23d\equiv 1 \; [40]$ .

3. Cryptage dans le système RSA.

Une personne $A$ choisit deux nombres premiers $p$ et $q$ , puis calcule les produits $N=p\times q$ et $n=(p-1)\times(q-1)$ . Elle choisit également un entier naturel $c$ premier avec $n$ . La personne publie le couple $(N;c)$ qui est une clé publique permettant à quiconque de lui envoyer un nombre crypté. Les messages sont numérotés et transformés en une suite d’entiers compris entre $0$ et $N-1$ . Pour crypter un entier $a$ de cette suite, on procède ainsi : on calcule le reste $b$ dans la division euclidienne par $N$ du nombre $a^{c}$ et le nombre crypté est l’entier $b$ . Dans la pratique, cette méthode est sûre si la personne $A$ choisit des nombres premiers $p$ et $q$ très grands, s’écrivant avec plusieurs dizaines de chiffres. On va l’envisager ici avec des nombres plus simples : $p=5$ et $q=11$ . La personne $A$ choisit également $c=23$ .

(a) Calculer les nombres $N$ et $n$ , puis justifier que $c$ vérifie la condition voulue.

(b) Un émetteur souhaite envoyer à la personne $A$ le nombre $a=8$ . Déterminer la valeur du nombre crypté $b$ .

4. Décryptage dans le système RSA.

La personne $A$ calcule dans un premier temps l’unique entier naturel $d$ vérifiant les conditions : $0\leqslant d<n$ et $cd\equiv 1 \; [n]$ . Elle garde secret le nombre $d$ qui lui permet, et à elle seule, de décrypter les nombres qui lui ont été envoyés cryptés avec la clé publique. Pour décrypter un nombre crypté $b$ , la personne $A$ calcule le reste de la division euclidienne par $N$ du nombre $b^{d}$ , et le nombre en clair (c’est-à-dire le nombre avant le cryptage) est le nombre $a$ . On admet l’existence et l’unicité de l’entier $d$ , et le fait que le décryptage fonctionne. Les nombres choisis par $A$ sont encore $p=5$ , $q=11$ et $c=23$ .

(a) Quelle est la valeur de $d$  ?

(b) En appliquant la règle de décryptage, retrouver le nombre en clair lorsque le nombre crypté est $b=17$ .

Corrigé

1. (a) On calcule les puissances de $8$ modulo $55$ de proche en proche : $8^{2}=64\equiv 9\;[55] \quad ; \quad 8^{4}\equiv 9^{2}=81\equiv 26\;[55]$

8^{6}\equiv 26\times 9=234=4\times 55+14\equiv 14\;[55]

8^{7}\equiv 14\times 8=112=2\times 55+2\equiv 2\;[55]

$\boxed{8^{7}\equiv 2\;[55]}$ On en déduit, en élevant au cube : $8^{21}=\left(8^{7}\right)^{3}\equiv 2^{3}=8\;[55]$

\boxed{\text{Le reste de la division euclidienne de } 8^{21} \text{ par } 55 \text{ est } 8}

(b) Le premier calcul ci-dessus donne $\boxed{8^{2}\equiv 9\;[55]}$ . On décompose alors : $8^{23}=8^{21}\times 8^{2}\equiv 8\times 9=72=55+17\equiv 17\;[55]$

\boxed{\text{Le reste de la division euclidienne de } 8^{23} \text{ par } 55 \text{ est } 17}

2. (a) $\mathrm{PGCD}(23,40)=1$ car $23$ est premier et ne divise pas $40$ . Comme $1$ divise $1$ , le corollaire de Bézout garantit : $\boxed{\text{L'équation } (E) \text{ admet au moins un couple solution}}$

(b) On cherche un couple par l'algorithme d'Euclide : $\begin{aligned} 40 &= 23\times 1+17 \qquad (L_{1}) \\ 23 &= 17\times 1+6 \qquad (L_{2}) \\ 17 &= 6\times 2+5 \qquad (L_{3}) \\ 6 &= 5\times 1+1 \qquad (L_{4}) \end{aligned}$ Remontée : $\begin{aligned} 1 &= 6-\textcolor{#9e0018}{5}\times 1 &&\text{or } (L_{3}) : \; 5=17-6\times 2 \\ &= 6-\textcolor{#9e0018}{(17-6\times 2)}=3\times\textcolor{#9e0018}{6}-17 &&\text{or } (L_{2}) : \; 6=23-17 \\ &= 3\times\textcolor{#9e0018}{(23-17)}-17=3\times 23-4\times\textcolor{#9e0018}{17} &&\text{or } (L_{1}) : \; 17=40-23 \\ &= 3\times 23-4\times\textcolor{#9e0018}{(40-23)}=7\times 23-4\times 40 && \end{aligned}$

\boxed{(x_{0}\,;y_{0})=(7\,;4) \quad \text{car} \quad 23\times 7-40\times 4=161-160=1}

(c) Soit $(x\,;y)$ une solution. En soustrayant terme à terme : $23(x-7)-40(y-4)=0 \qquad \text{soit} \qquad 23(x-7)=40(y-4)$ Comme $40$ divise $23(x-7)$ et que $\mathrm{PGCD}(23,40)=1$ , le théorème de Gauss donne $40\mid(x-7)$ : il existe $k\in\mathbb{Z}$ tel que $x=40k+7$ . En reportant, $23\times 40k=40(y-4)$ , d'où $y=23k+4$ . $\boxed{S=\left\{(40k+7\,;23k+4) \; ; \; k\in\mathbb{Z}\right\}}$ Vérification : $23(40k+7)-40(23k+4)=920k+161-920k-160=1$ .

(d) Dire que $23d\equiv 1\;[40]$ signifie que $40$ divise $23d-1$ , c'est-à-dire qu'il existe un entier $y$ tel que $23d-40y=1$ : le couple $(d\,;y)$ est solution de $(E)$ . D'après la question c), $d$ s'écrit $d=40k+7$ . La condition $0\leqslant d<40$ impose alors $k=0$ . $\boxed{d=7 \text{ est l'unique entier vérifiant les deux conditions}}$

3. (a) $N=p\times q=5\times 11=\boxed{55} \qquad ; \qquad n=(p-1)(q-1)=4\times 10=\boxed{40}$ Il reste à vérifier que $c=23$ est premier avec $n=40$ , ce qui a été établi à la question 2a : $\boxed{\mathrm{PGCD}(23,40)=1 : \text{la condition est bien remplie}}$

(b) Le nombre crypté $b$ est le reste de la division euclidienne de $a^{c}=8^{23}$ par $N=55$ . C'est exactement le calcul de la question 1b : $\boxed{b=17}$

4. (a) L'entier $d$ doit vérifier $0\leqslant d<n=40$ et $cd=23d\equiv 1\;[40]$ : c'est précisément la caractérisation de la question 2d. $\boxed{d=7}$

(b) On calcule le reste de $b^{d}=17^{7}$ modulo $55$ , de proche en proche : $17^{2}=289=5\times 55+14\equiv 14\;[55]$

17^{4}\equiv 14^{2}=196=3\times 55+31\equiv 31\;[55]

17^{6}\equiv 31\times 14=434=7\times 55+49\equiv 49\;[55]

17^{7}\equiv 49\times 17=833=15\times 55+8\equiv 8\;[55]

$\boxed{a=8}$ On retrouve bien le nombre initial de la question 3b : le décryptage fonctionne.

Toute la sécurité du procédé repose sur le fait que $d$ se calcule à partir de $n=(p-1)(q-1)$ , donc de la factorisation $N=p\times q$ . Avec $N=55$ , cette factorisation est immédiate ; avec un $N$ de plusieurs centaines de chiffres, elle est hors de portée des ordinateurs actuels.

Énoncé PDF, p. 6 Corrigé PDF, p. 23 Toute la feuille Le cours

Dans l'édifice

PGCD, théorème de Bézout, lemme de Gauss Les anneaux ℤ/nℤ Théorème fondamental de l'arithmétique

Thèmes

équations diophantiennes, congruences, nombres premiers, cryptographie, suites

Notions

entiers modulo n (anneau des), nombre premier