Le code RSA

Cryptographie et exemple de chiffrement

Le chiffrement RSA est un algorithme de cryptographie, c’est-à-dire d’écriture secrète. Il est fréquemment employé aujourd’hui, d’autant qu’il est librement utilisable depuis 2000. Petite anecdote, il repose sur le petit théorème de Fermat découvert en 1640, dont on s'est très longtemps demandé à quoi il pouvait bien servir. Belle leçon de patience.

La cryptographie

Afin de rendre inintelligible un message ou un nombre, il faut une ou deux clés. Si l’émetteur et le récepteur utilisent la même pour chiffrer et pour déchiffrer, on parle de cryptographie symétrique. Sinon, le procédé est asymétrique.

RSA est un chiffrement asymétrique, avec une clé publique pour chiffrer et une clé privée pour déchiffrer. Ce type de cryptographie est plus sûr que le système symétrique.

Son principe vous apparaîtra à la faveur de ce sujet du bac S spé maths (centres étrangers, 11 juin 2018).

Sujet

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’on 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\;\bmod \;55\)
En déduire le reste dans la division euclidienne par 55 du nombre \({8^{21}}\)

b. Vérifier que \({8^2} \equiv 9\;\bmod \;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 \((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 40\) et \(23d \equiv 1\bmod 40\).

3. Cryptage dans le système RSA

Une personne A choisit deux nombres premiers \(p\) et \(q\), puis calcule les produits \(N = pq\) 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 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 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 n\) et \(cd \equiv 1\bmod 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 \(b^d\), 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\).

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. Cette question est traitée en page d’exercices sur la congruence. On retiendra que le reste de la division euclidienne de \(8^{23}\) par 55 est 17.

2. Cette question est traitée en page d’exercices sur équations diophantiennes. Retenons que 23 et 40 sont premiers entre eux et qu'il existe un unique entier \(d\) vérifiant les conditions \(0 \leqslant 40\) et \(23d \equiv 1\bmod 40\). Cet entier est 7.

3. Cryptage

a. Le calcul des nombres \(N\) et \(n\) ne pose aucune difficulté. \(N = 5 \times 11 = 55\) et \(n = 4 \times 10 = 40\). La condition voulue est que \(c\) soit premier avec \(n\), en l’occurrence que 23 soit premier avec 40. Or 23 et 40 sont bel et bien premiers entre eux (revoir la question 2).

b. \(b\) est le reste de la division de \(8^{23}\) par 55, c’est-à-dire 17. On se réfère cette fois à la question 1.

4. Décryptage

Nous allons vérifier ce que nous avons établi précédemment : si l’on envoie au destinataire le nombre 8, il apparaîtra 17 grâce au nombre secret \(d = 7\).

a. \(d\) est compris entre 0 et \(n\), soit \(0 \leqslant 40\).

\(cd \equiv 1\bmod n\), soit \(23d \equiv 1[40]\)

Nous avons vu en question 2.d. que pour satisfaire ces conditions, \(d\) doit être égal à 7.

b. Le nombre reçu est \(b = 17\). Comment retrouver \(a\) ?

\(a\) est le reste de la division de \(b^d\) par \(N\), soit le reste \(d\) la division de \(17^7\) par 55. Il s’agit d’un exercice sur la congruence un peu répétitif car le principe est le même qu’en question 1.

\(17^2 = 289\), soit \(5 \times 55 + 14\). Donc \(17^2 \equiv 14[55]\).
\(17^6 = (17^2)^3 \equiv 14^3[55]\). Or \(14^3 = 2744\) \(= 49 \times 55 + 49\) donc \(17^6 \equiv 49[55]\)
\(17^7 = 17^6 \times 17\) donc \(17^7 \equiv 49 \times 17[55]\). Or \(49 \times 17 = 833\) \(= 15 \times 55 + 8\)

Donc \(17^7 \equiv 8[55]\)

8 est le reste de la division de \(17^7\) par 55. Donc \(a = 8\).

Et un texte ?

Avec le système RSA, un texte n'est pas codé lettre par lettre mais par paquets. Exemple : si l'on code par paquets de trois lettres SITE WEB, cela devient la suite de nombres 190920 (S est la dix-neuvième lettre de l'alphabet, I la neuvième...) puis 052305... Ce sont ces nombres-ci qui sont codés.