Le chiffrement RSA : Cours et exercice

Le chiffrement RSA est un algorithme de chiffrement symétrique utilisé pour sécuriser les communications sur Internet et protéger les données sensibles. Il a été développé en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman, d’où son nom RSA.

Il est largement utilisé dans la sécurité informatique pour assurer l’intégrité et la confidentialité de l’information transmise sur internet.

Prérequis

• Nombres premiers
• Théorème de Bézout
• Algorithme d’Euclide
• L’indicatrice d’Euler

Principe du chiffrement RSA

Le principe de base du chiffrement RSA est de chiffrer un message en utilisant une clé publique et de le déchiffrer avec une clé privée. La clé publique est rendue publique et peut être utilisée par n’importe qui pour chiffrer un message destiné à l’utilisateur possédant la clé privée correspondante. Seul l’utilisateur possédant la clé privée peut déchiffrer le message et le lire.

Pour utiliser RSA, l’utilisateur génère d’abord une paire de clés, une clé publique et une clé privée. La clé publique est composée de deux nombres premiers très larges, nommés p et q, et d’un exposant, e. La clé privée est composée de l’exposant e et de l’inverse de e modulo (p-1)(q-1).

Voici le procédé pour calculer la clé publique et la clé privée :

• Prendre p et q deux nombres premiers distincts. En pratique p et q sont très grands pour rajouter de la complexité dans le chiffrement
• Calculer n = pq
• Calculer \varphi(n) = (p-1)(q-1) , l’indicatrice d’Euler
• Choisir un entier e premier avec \varphi(n) et strictement inférieur à \varphi(n) .
• Calculer d l’inverse de e modulo \varphi(n) . L’algorithme d’Euclide permet de faire cela.
• La clé publique sera le couple (n,e), la clé privée sera le couple (n,d)

Pour chiffrer un message, on utilise la clé publique. Soit m un message à chiffrer. On calcule le message chiffré en utilisant l’expression suivante : m^e \equiv c[n].

Pour déchiffrer le message, on utilise la clé privée. On détermine à partir d’un message chiffré c le message en clair. On calcule le message en clair en utilisant l’expression suivante : c^d \equiv = m[n], où c est le message chiffré, d est l’exposant de la clé privée, n est le produit de p et q, et m est le message en clair.

Le théorème d’Euler nous assure que M^{\varphi(n)}\equiv 1 [n]. Ainsi, M^{cd} = M^{1+ k \varphi(n)}= M \times \left(M^{\varphi(n)}\right)^k \equiv M [n].

Sécurité du chiffrement RSA

Le chiffrement RSA est très sécurisé car il est très difficile de trouver les nombres premiers p et q à partir de n connu. Dans la clé publique on ne donne pas p et q, on donne seulement n. Cependant, il est relativement lent par rapport à d’autres algorithmes de chiffrement, ce qui peut le rendre inadapté pour chiffrer de grandes quantités de données en temps réel.

Exemple

• On peut prendre p = 5 et q = 11.
• On a alors n = 5 \times 11 = 55 .
• Puis, on calcule aussi \varphi(n) = (5-1)(11-1) = 4 \times 10 = 40 .
• Ensuite, on choisit d premier avec 4. d = 3 convient par exemple.
• On cherche l’inverse de 3 modulo 40. On a 3 \times 27 = 40 \times 2 + 1. Donc 27 est l’inverse de 3 modulo 40.
• La clé publique est donc (40,3). La clé privée est (40,27).

Par exemple, si on veut chiffrer 7, alors on calculer 7^3 modulo 40. Si on veut déchiffrer 30, on calcule 30^{27} modulo 40.

Exercice

Ce sujet est tombé en 2018 – Centres étrangers pour l’exercice d’enseignement de spécialité. Le voici :

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 \mod 55 .En déduire le reste dans la division euclidienne par 5555 du nombre 8^{21}8​21​​.
   • b) 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}​​.
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.
   • 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 \leq d < 40 et 23 d \equiv 1 \mod 40.
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 cc 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.
   • 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 \leq d < n et cd \equiv 1 [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 aa 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 = 11q 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.