Chargement de l'audio en cours
Plus

Plus

Synthèse
P.162-163

Mode édition
Ajouter

Ajouter

Terminer

Terminer




Synthèse





78
SYSTÈME DE CRYPTOGRAPHIE RSA
[Calculer, Modéliser.]
D’après bac S, Centres étrangers, juin 2018

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. Les questions 1. et 2. sont des questions préparatoires, la question 3. aborde le cryptage et la question 4. le décryptage.

1. Cette question envisage de calculer le reste dans la division euclidienne par 5555 de certaines puissances de 88.
a. Vérifier que 872[55]8^{7} \equiv 2[55]. En déduire le reste dans la division euclidienne de 8218^{21} par 5555.


b. Vérifier que 829[55]8^{2} \equiv 9[55], puis déduire de la question a. le reste dans la division euclidienne par 5555 de 8238^{23}.


2. Dans cette question, on considère l’équation (E):23x40y=1(\mathrm{E}): 23 x-40 y=1, dont les solutions sont des couples (x;y)(x\,; y) d’entiers relatifs.
a. Justifier le fait que (E)(\mathrm{E}) admet au moins un couple solution.


b. Donner une solution particulière de (E)(\mathrm{E}).


c. Déterminer tous les couples d’entiers relatifs solutions de (E)(\mathrm{E}).


d. En déduire qu’il existe un unique entier dd vérifiant les conditions 0d<400 \leqslant d \lt 40 et 23d1[40]23 d \equiv 1[40].


3. Cryptage dans le système RSA
Une personne A choisit deux nombres premiers pp et qq, puis calcule les produits N=pq\mathrm{N} = pq et n=(p1)(q1)n=(p-1)(q-1).
Elle choisit également un entier naturel cc premier avec nn. La personne A publie le couple (N;c)(\mathrm{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 00 et N1\mathrm{N} - 1.
Pour crypter un entier aa, on calcule le reste bb dans la division euclidienne par N\mathrm{N} du nombre aca^c. Le nombre crypté est alors l’entier bb.
Dans la pratique, cette méthode est sûre si la personne A choisit des nombres premiers pp et qq très grands, s’écrivant avec plusieurs dizaines de chiffres. On va l’envisager ici avec des nombres plus simples : p=5p=5 et q=11q=11. La personne A choisit aussi c=23c=23.

a. Calculer les nombres N\mathrm{N} et nn, puis justifier que la valeur de cc vérifie la condition voulue.


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


4. Décryptage dans le système RSA
La personne A calcule dans un premier temps l’unique entier naturel dd vérifiant les conditions 0d<n0 \leqslant d \lt n et cd1[n]c d \equiv 1[n]. Elle garde secret ce nombre dd qui lui permet, à 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é bb, la personne A calcule le reste aa dans la division euclidienne par N\mathrm{N} du nombre bdb^d, et le nombre en clair – c’est‑à‑dire le nombre avant cryptage – est le nombre aa. Pour cette question, les nombres choisis par A sont encore p=5p=5, q=11q=11 et c=23c=23.

a. Quelle est la valeur de dd ?


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


Remarque

On pourra aussi consulter le TP 2 p. 155.
Voir les réponses

79
[Calculer, Chercher.]
On définit la fonction d’Euler de la manière suivante : φ:{NNnφ(n)\varphi:\left\{\begin{aligned} \mathbb{N}^{*} & \rightarrow \mathbb{N}^{*} \\ n & \mapsto \varphi(n) \end{aligned}\right., où φ(n)\varphi(n) désigne le nombre d’entiers naturels inférieurs ou égaux à nn et premiers avec nn.

1. Déterminer φ(5)\varphi(5), φ(7)\varphi(7), φ(8)\varphi(8), φ(9)\varphi(9) et φ(10)\varphi(10).


2. Si pp est un nombre premier, exprimer φ(p)\varphi(p) en fonction de pp.


3. Si pp est un nombre premier et si kk est un entier naturel non nul, montrer que φ(pk)=pkpk1\varphi\left(p^{k}\right)=p^{k}-p^{k-1}.


4. On admet que si aa et bb sont deux entiers premiers entre eux, alors φ(ab)=φ(a)×φ(b)\varphi(a b)=\varphi(a) \times \varphi(b).
On considère un nombre entier nn qui se décompose en produit de facteurs premiers de la façon suivante : n=p1α1×p2α2××prαrn=p_{1}^{\alpha_{1}} \times p_{2}^{\alpha_{2}} \times \ldots \times p_{r}^{\alpha_{r}}.
Montrer alors que 
φ(n)=n×(11p1)×(11p2)××(11pr)\varphi(n)=n \times\left(1-\dfrac{1}{p_{1}}\right) \times\left(1-\dfrac{1}{p_{2}}\right) \times \ldots \times\left(1-\dfrac{1}{p_{r}}\right).


5. Déterminer le nombre d’entiers compris entre 11 et 945945 et premiers avec 945945.
Voir les réponses

80
PETIT THÉORÈME DE FERMAT
[Raisonner.]
[DÉMO]

Le but de l’exercice est de démontrer la propriété suivante du cours : « Si pp est un nombre premier, alors, pour tout nombre entier aa, apa[p]a^{p} \equiv a[p]. »
Dans tout l’exercice, pp désigne un nombre premier fixé.

1. Montrer que, pour tout entier kk compris entre 11 et p1p-1, pp divise k!(pk)k !\left(\begin{array}{l}p \\ k\end{array}\right) puis en déduire que pp divise (pk)\left(\begin{array}{l}p \\ k\end{array}\right).


2. On va démontrer par récurrence que la propriété P(a)\mathcal{P}(a) : « apa[p]a^{p} \equiv a[p] » est vraie, pour tout entier aa compris entre 00 et p1p-1.
a. Vérifier que P(0)\mathcal{P}(0) est vraie.


b. On suppose que P(b)\mathcal{P}(b) est vraie pour un certain bb tel que 0bp10 \leqslant b \leqslant p-1. Montrer en utilisant le résultat de la question préliminaire que P(b+1)\mathcal{P}(b+1) est vraie.


3. Déduire des questions précédentes que, pour tout entier naturel aa, apa[p]a^{p} \equiv a[p].
Voir les réponses

81
[Calculer, Modéliser.]
D’après bac S, Pondichéry, mai 2018

À toute lettre de l’alphabet, on associe un nombre entier entre 00 et 2525 : 00 à A\mathrm{A}, 11 à B\mathrm{B}, … et 2525 à Z\mathrm{Z}.
Alice veut communiquer de manière sécurisée. Elle choisit deux nombres premiers pp et qq et un entier naturel B\mathrm{B} tel que 1B<pq1 \leqslant \mathrm{B} \lt pq. Elle publie les nombres n=p×qn=p \times q et B\mathrm{B} et garde secrets les nombres pp et qq.
Si Bob veut envoyer un message secret à Alice, il le code lettre par lettre.
Le codage d’une lettre représentée par l’entier xx est le nombre yy tel que yx(x+B)[n]y \equiv x(x+\mathrm{B})[n] et 0y<n0 \leqslant y \lt n.
Dans tout l’exercice, on prend p=3p=3, q=11q=11 et B=13\mathrm{B}=13.

1. Bob veut envoyer la lettre N\mathrm{N} à Alice. Quel nombre crypté doit‑il lui transmettre ?


2. Alice a reçu un message crypté qui commence par le nombre 33. Elle doit donc déterminer l’entier xx compris entre 00 et 2525 tel que x(x+13)3[33]x(x+13) \equiv 3[33].
a. Montrer que cette équation équivaut à :
(x+23)24[33](x+23)^{2} \equiv 4[33].


b. En déduire que x(x+13)3[33]x(x+13) \equiv 3[33] si, et seulement si, {(x+23)21[3](x+23)24[11]\left\{\begin{array}{l}(x+23)^{2} \equiv 1[3] \\ (x+23)^{2} \equiv 4[11]\end{array}\right..


c. Déterminer les entiers aa tels que :
0a<30 \leqslant a \lt 3 et a21[3]a^{2} \equiv 1[3].


d. Déterminer les entiers bb tels que :
0b<110 \leqslant b \lt 11 et b24[11]b^{2} \equiv 4[11].


e. En déduire que l’entier xx recherché est congru à 00 ou 22 modulo 33 et qu’il est congru à 88 ou 11 modulo 1111.


3. En énumérant les différentes possibilités, Alice peut-elle connaître la première lettre du message envoyé par Bob ? Cette méthode de chiffrement est‑elle utilisable pour décoder un message lettre par lettre ? Justifier.
Voir les réponses

82
APPROFONDISSEMENT
[Chercher, Communiquer.]
Nombres de Fermat

On considère un entier n1n \geqslant 1 et on définit l’entier Fn=22n+1\mathrm{F}_{n}=2^{2^{n}}+1 appelé nn‑ième nombre de Fermat.

1. En utilisant la calculatrice, montrer que F1\mathrm{F}_1, F2\mathrm{F}_2, F3\mathrm{F}_3 et F4\mathrm{F}_4 sont des nombres premiers.


2. Soit pp un nombre premier impair. On note k0k_0 le plus petit entier kk non nul tel que 2k1[p]2^{k} \equiv 1[p]. Justifier que k0k_0 existe, puis montrer que, pour tout entier \ell non nul tel que 21[p]2^{\ell} \equiv 1[p], k0k_0 divise \ell.


3. Dans cette question, on suppose n5n \geqslant 5. Soit pp un diviseur premier de Fn\mathrm{F}_n.
L’objectif est de montrer que p1[2n+1]p \equiv 1\left[2^{n+1}\right].
a. Justifier que pp est impair, puis montrer que 22n1[p]2^{2^{n}} \equiv-1[p] et que 22n+11[p]2^{2^{n+1}} \equiv 1[p].


b. En utilisant le résultat de la question 2., en déduire que 2n+12^{n+1} est le plus petit entier kk tel que 2k1[p]2^{k} \equiv 1[p].


c. Justifier que 2p11[p]2^{p-1} \equiv 1[p].


d. En utilisant de nouveau le résultat de la question 2., déduire des questions précédentes que p1[2n+1]p \equiv 1\left[2^{n+1}\right].


4. En utilisant le résultat de la question précédente, déterminer un diviseur premier de F5\mathrm{F}_5 inférieur à 1 0001 000.
Voir les réponses

Le Grand Oral

Entraînez-vous au Grand Oral et enregistrez-vous sur LLS.fr/GrandOralMaths


Comme le suggère le programme, les problèmes abordés en maths expertes peuvent servir d’appui à des questions de Grand Oral.
Voici un exemple, basé sur l’enseignement de spécialité, utilisant des notions de ce chapitre.

Plusieurs points du chapitre peuvent être utilisés pour illustrer des notions rencontrées au cours de l’enseignement de spécialité. En voici quelques exemples.

1. La décomposition d’un entier naturel supérieur ou égal à 22 en produit de facteurs premiers est l’occasion d’illustrer une méthode du chapitre Combinatoire et dénombrement pour déterminer le nombre de diviseurs positifs de cet entier naturel.

2. On dispose d’un résultat donnant une approximation du nombre de nombres premiers inférieurs ou égaux à un entier nn : ce nombre vaut environ nln(n)\dfrac{n}{\ln (n)}. Ce résultat est connu sous le nom du théorème des nombres premiers (voir exercice 53 page 159) et expose une application surprenante de la fonction logarithme népérien étudiée au cours de l’enseignement de spécialité.

3. La fonction logarithme peut également être utilisée pour déterminer le nombre de chiffres d’un nombre entier strictement positif écrit en base 1010. Expliquer comment puis appliquer ce résultat à la détermination du nombre de chiffres de 8328^{32}.

Méthodologie
Consulter les fiches méthode de ce manuel pour le Grand Oral p. 244
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.