78

Système de cryptographie de 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 55 de certaines puissances de 8.
a. Vérifier que 8^{7} \equiv 2[55]. En déduire le reste dans la division euclidienne de 8^{21} par 55.

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

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

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

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

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

3. Cryptage dans le système RSA
Une personne A choisit deux nombres premiers p et q, puis calcule les produits \mathrm{N} = pq et n=(p-1)(q-1).
Elle choisit également un entier naturel c premier avec n. La personne A publie le couple (\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 0 et \mathrm{N} - 1.
Pour crypter un entier a, on calcule le reste b dans la division euclidienne par \mathrm{N} du nombre a^c. Le nombre crypté est alors 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 aussi c=23.

a. Calculer les nombres \mathrm{N} et n, puis justifier que la valeur de 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 \lt n et c d \equiv 1[n]. Elle garde secret ce nombre d 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é b, la personne A calcule le reste a dans la division euclidienne par \mathrm{N} du nombre b^d, et le nombre en clair – c'est‑à‑dire le nombre avant cryptage – est le nombre a. Pour cette question, 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.

79

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

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

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

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

4. On admet que si a et b sont deux entiers premiers entre eux, alors \varphi(a b)=\varphi(a) \times \varphi(b).
On considère un nombre entier n qui se décompose en produit de facteurs premiers de la façon suivante : n=p_{1}^{\alpha_{1}} \times p_{2}^{\alpha_{2}} \times \ldots \times p_{r}^{\alpha_{r}}.
Montrer alors que 

\varphi(n)=n \times\left(1-\frac{1}{p_{1}}\right) \times\left(1-\frac{1}{p_{2}}\right) \times \ldots \times\left(1-\frac{1}{p_{r}}\right).

5. Déterminer le nombre d'entiers compris entre 1 et 945 et premiers avec 945.

80

Petit théorème de Fermat

Démo

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

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

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

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

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

81

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

À toute lettre de l'alphabet, on associe un nombre entier entre 0 et 25 : 0 à \mathrm{A}, 1 à \mathrm{B}, … et 25 à \mathrm{Z}.
Alice veut communiquer de manière sécurisée. Elle choisit deux nombres premiers p et q et un entier naturel \mathrm{B} tel que 1 \leqslant \mathrm{B} \lt pq. Elle publie les nombres n=p \times q et \mathrm{B} et garde secrets les nombres p et q.
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 x est le nombre y tel que y \equiv x(x+\mathrm{B})[n] et 0 \leqslant y \lt n.
Dans tout l'exercice, on prend p=3, q=11 et \mathrm{B}=13.

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

2. Alice a reçu un message crypté qui commence par le nombre 3. Elle doit donc déterminer l'entier x compris entre 0 et 25 tel que x(x+13) \equiv 3[33].
a. Montrer que cette équation équivaut à :

(x+23)^{2} \equiv 4[33].

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

c. Déterminer les entiers a tels que :

0 \leqslant a \lt 3 et a^{2} \equiv 1[3].

d. Déterminer les entiers b tels que :

0 \leqslant b \lt 11 et b^{2} \equiv 4[11].

e. En déduire que l'entier x recherché est congru à 0 ou 2 modulo 3 et qu'il est congru à 8 ou 1 modulo 11.

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.

82

Approfondissement

[Chercher, Communiquer.]
Nombres de Fermat

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

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

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

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

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

c. Justifier que 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 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 \mathrm{F}_5 inférieur à 1 000.

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 à 2 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 n : ce nombre vaut environ \frac{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 10. Expliquer comment puis appliquer ce résultat à la détermination du nombre de chiffres de 8^{32}.