Baccalauréat S Centres étrangers 11 juin 2018 - Correction Spécialité

Page 10 sur 10: Correction Spécialité

Correction de l'exercice de Spécialité 5 points

Candidats AYANT SUIVI l'enseignement de spécialité mathématiques

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$.
   1. Vérifier que $8^7 \equiv 2 \mod 55$. En déduire le reste dans la division euclidienne par $55$ du nombre $8^{21}$.
   $8^2=64 \equiv 9 $ mod $55$.
   Ainsi $8^6=\left(8^2\right)^3 \equiv 9^3 \equiv 729\equiv 14$ mod $55$.
   Par conséquent $8^7=8\times 8^6\equiv 8\times 14\equiv 112\equiv 2$ mod $55$.
   $\quad$
   $8^{21}=\left(8^7\right)^3 \equiv 2^3 \equiv 8$ mod $55$.
   $\quad$
    
   2. Vérifier que $8^2 \equiv 9 \mod 55$, puis déduire de la question a. le reste dans la division euclidienne par $55$ de $8^{23}$.
   $8^2=64 \equiv 9 $ mod $55$.
   $\quad$
   $8^{23}=8^{21}\times 8^2 \equiv 8\times 9 \equiv 72 \equiv 17$ mod $55$.
2. Dans cette question, on considère l'équation $(E)$ : $23 x - 40 y = 1$, dont les solutions sont des couples $(x~;~y)$ d'entiers relatifs.
   1. Justifier le fait que l'équation $(E)$ admet au moins un couple solution.
   $23$ et $40$ sont premiers entre eux. D’après le théorème de Bezout, l’équation $23x-40y=1$ possède un couple de solution $(x,y)$ avec $x$ et $y$ entiers relatifs.
   $\quad$
   b. Le couple $(7,4)$ est solution de l’équation $(E)$.
   En effet $7\times 23-4\times 40=161-160=1$.
   $\quad$
   
   2. Donner un couple, solution particulière de l'équation $(E)$.
   Le couple $(7,4)$ est solution de l’équation $(E)$.
   En effet $7\times 23-4\times 40=161-160=1$.
   $\quad$
   
   3. Déterminer tous les couples d'entiers relatifs solutions de l'équation $(E)$.
   Soit $(x,y)$ un couple solution.
   On a donc $7\times 23-4\times 40=1$ et $23x-40y=1$.
   Par différence, on obtient $23(7-x)-40(4-y)=0$.
   Soit $23(7-x)=40(4-y)$.
   Les nombres $23$ et $40$ sont premiers entre-eux.
   D’après le théorème de Gauss, il existe un entier relatif $k$ tel que $7-x=40k$ et $4-y=23k$.
   Soit $x=7-40k$ et $y=4-23k$.
   $\quad$
   Donc si $(x,y)$ est un couple solution alors $x=7-40k$ et $y=4-23k$.
   Réciproquement, soit $k$ un entier relatif. Vérifions que le couple $(7-40k,4-23k)$ est solution de l’équation $(E)$.
   $23(7-40k)-40(4-23k)=161-920k-160+920k=1$.
   Les solutions de l’équation $(E)$ sont donc les couples $(7-40k,4-23k)$ pour tout entier relatif $k$.
   $\quad$
   
   4. En déduire qu'il existe un unique entier $d$ vérifiant les conditions $0 \leqslant d < 40$ et $23 d \equiv 1 \mod 40$.
   $23x-40y=1 \iff 23x=1+40y$.
   D’après la question précédente les solutions de l’équation $23d \equiv 1$ mod $40$ sont de la forme $7-40k$ avec $k\in \mathbb Z$.
   On veut que $0 \leqslant 7-40k<40 \iff -7\leqslant -40k <33 \iff \dfrac{7}{40} \geqslant k >- \dfrac{33}{40}$ avec $k\in \mathbb Z$.
   La seule solution est donc pour $k=0$.
   Le seule entier $d$ vérifiant les conditions $0\leqslant d>40$ et $23d\equiv 1$ mod $40$ est donc $7$.
   $\quad$
3. Cryptage dans le système RSA Une personne A choisit deux nombres premiers $p$ et $q$, puis calcule les produits $N = p q$ et $n = (p - 1)(q - 1)$. Elle choisit également un entier naturel $c$ premier avec $n$. La personne A publie le couple $(N~;~c)$, qui est une clé publique permettant à quiconque de lui envoyer un nombre crypté. Les messages sont numérisé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$.
   1. Calculer les nombres $N$ et $n$, puis justifier que la valeur de $c$ vérifie la condition voulue.
   On a $N=pq=55$ et $n=(p-1)(q-1)=40$.
   On a $40=2^3\times 5$ et $23$ est un nombre premier.
   Par conséquent $40$ et $23$ sont premiers entre-eux.
   $\quad$
   
   2. Un émetteur souhaite envoyer à la personne A le nombre $a = 8$. Déterminer la valeur du nombre crypté $b$.
   $a^c=8^{23}\equiv 17$ mod $55$ d’après la question 1.b.
   Par conséquent $b=17$.
   $\quad$
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 \mod n$. Elle garde secret ce nombre $d$ qui lui permet, et à elle seule, de décrypter les nombres qui lui ont été envoyés cryptés avec sa clé publique. Pour décrypter un nombre crypté $b$, la personne A calcule le reste $a$ dans la division euclidienne par $N$ du nombre $bd$, et le nombre en clair , c'est-à-dire le nombre avant 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$.
   1. Quelle est la valeur de $d$ ?
   D’après la question 2.d. on a $d=7$.
   $\quad$
   
   2. En appliquant la règle de décryptage, retrouver le nombre en clair lorsque le nombre crypté est $b = 17$.
   $b^d=17^7=410~338~673=55\times 7~460~703+8$
   Donc $b^d \equiv 8$ mod $55$.
   On retrouve bien le nombre en clair de la question 3.
   $\quad$