Devoir maison n°6 – pour lundi 20 janvier 2025
Exercice 1 – Le système cryptographique R.S.A.
1. Introduction
Le chiffrement de Vigenère vu dans le précédent DM et les méthodes de plus
en plus sophistiquées qui lui succédèrent jusqu’à la fin des années 1970 ont
toutes posé un problème important : celui de l’échange des clés entre
l’émetteur et le destinataire du message, la clé utilisée étant la même pour le
chiffrement que pour le déchiffrement (on parle de clé « symétrique »).
En 1975, trois Américains (Diffie, Hellman et Merkle, ont l’idée d’utiliser une
clé « asymétrique » : la clé de chiffrement (clé publique) serait différent de la
clé de déchiffrement (clé privée).
Il restait à concrétiser cette idée en trouvant une fonction de chiffrement
adaptée. Trois autres Américains, Ron Rivest, Adi Shamir et Léonard
Adleman ont concrétisé les travaux de D.H.M. et ont donné naissance au
système R.S.A. en 1978.
Pour info Les nombres premiers de Mersenne
La fiabilité des clés du système R.S.A. nécessite l’utilisation de nombres premiers très
grands. Certains de ces nombres, trop célèbres, ne sont pas utilisés en cryptographie.
Les nombres de Mersenne sont les nombres premiers de la forme (2 1) où p est
p
premier. En 2012, on en connaissait 47 ; actuellement on en connaît 52. Le plus grand
en 2012 correspondait à p = 43 112 609 et s’écrivait avec presque 13 millions de
chiffres ! Actuellement, le plus grand nombre de Mersenne connu est 2 1.
136 279 841
2. Principe
Une personne donnée que l’on nomme Alice choisit deux nombres premiers p
et q distincts et supérieurs ou égaux à 3, et un entier e premier avec le produit
(p 1)(q 1) et tel que 0 e (p 1)(q 1) .
On note n le produit pq.
Le couple (n ;e) est la clé publique d’Alice (c'est-à-dire que tout le monde
peut se la procurer).
En revanche, les nombres p et q choisis par Alice sont grands de telle sorte que
la connaissance de n ne permet pas de les retrouver dans un temps raisonnable
avec des ordinateurs.
Tout le monde peut envoyer un message à Amice en utilisant sa clé publique
(n ;e) de la manière suivante : le message est numérisé en général avec le code
ASCII, puis découpé en tranches m1 , m2 ,…
Chaque nombre mi est ensuite remplacé par le reste ci de la division
euclidienne de mi e par n qui est transmis à Alice.
Le triplet (p ;q ;d) où d est l’unique entier tel que 1 d (p 1)(q 1) et
ed 1[(p 1)(q 1)] n’est connu que d’Alice : c’est sa clé privée.
Il permet à Alice de déchiffrer le message reçu, car en calculant le reste de ci d
dans la division euclidienne par n, Alice retrouve mi.
Tout le monde peut voir le message reçu par Alice, mais elle seule peut le
déchiffrer.
Pour info Le code ASCII
La fonction « code » d’un tableur renvoie le code ASCII des caractères ; c’est cette
fonction qui a été utilisée pour remplir la colonne mi du tableau de l’exemple ci-
dessous.
3. Exemple
Le but est de mettre le principe en application.
Contrairement à la réalité, on prend des nombres premiers
de taille modeste : p=13 et q=29.
(p 1)(q 1) 12 28 336 . On choisit un entier e premier
avec 336, compris entre 2 et 335. La décomposition de 336
en produit de puissances de facteurs premiers donne
336 24 3 7 , donc par exemple, e=5 convient.
a. Calculer n et d.
b. Bernard veut donner un lieu de rendez-vous secret à
Alice : CHARLIEU.
Que représentent les nombres 67 et 266 dans le
tableau ci-contre ?
c. Alice reçoit donc le message 266 193 364 36 189 242 101 258.
Quel calcul doit-elle faire avec le nombre 266 ?
Quel résultat va-t-elle obtenir ?
4. Justification
On note n’ le produit (p 1)(q 1) .
Partie A : existence du nombre d
a. Justifier que l’existence de e ne pose pas de problème.
b. Montrer qu’il existe un entier u vérifiant eu 1(n’).
c. En déduire qu’il existe un unique entier d tel que :
1 d n ' et ed 1(n ') .
Partie B : le déchiffrement
a. Montrer que c d m(n) med m(n) .
b. Justifier l’existence d’un entier t tel que ed 1 tn ' puis montrer que p
divise med m .
c. Justifier de même que q divise med m .
d. Conclure.
Coup de pouce
Distinguer les cas « p divise m » et « p ne divise pas m ». Dans le second cas, utiliser le
petit théorème de Fermat. (voir contrôle n°6).