Chapitre II

Les Cryptosystèmes RSA

1
Table des matières

II Les Cryptosystèmes RSA 1

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Le cryptosystème RSA(p, q) . . . . . . . . . . . . . . . . . . . . . . . 3
3 Sécurité du système RSA(p, q) . . . . . . . . . . . . . . . . . . . . . 5

1 Introduction
Dans un cryptosystème à clé publique, il y a deux sortes de clés : la clé
de chiffrement clé publique et la clé de déchiffrement clé privée. La clé de
chiffrement peut être largement diffusée tandis que la clé de déchiffrement est
tenue secrète par le destinataire.
C’est en général le destinataire du message choisit la fonction de déchiffre-
ment et diffuse à toutes les personnes susceptibles de communiquer avec lui
la fonction de chiffrement associée.
Donc, si Alice veut envoyer un message à Bob, elle doit s’assurer que la clé
de chiffrement qu’elle doit utiliser est bien celui donnée par Bob.
De plus, lorsque N veulent communiquer ensemble, il est seulement né-
cessaire d’avoir N couples de clés clé secrète, clé publique au lieu des N (N2−1)
clés dans un système classique : un couple par paire de personnes.
P.e. pour N = 100, il faut 100∙99
2
= 4950 clés pour un système classique tandis
qu’il ne faut que 100 paire de clés pour un système à clé publique.
Théoriquement, un tel système ne peut pas être inconditionnellement sûr
puisqu’un attaquant peut en principe décrypter un message c en chiffrant
tous les messages clairs possibles jusqu’à ce qu’il obtienne c.
Pour qu’un tel système fonctionne, le clé de déchiffrement doit être très
difficile, voire impossible à connaître, pour une personne qui ne connaît que
la clé de chiffrement.
La construction d’un tel système peut être basée sur les fonctions mathé-
matiques à sens unique ou fonctions à trappe. Ce sont des fonctions facile-
ment calculables mais leur réciproque est en pratique impossible à calculer

2
car trop coûteuse, en termes de complexité algorithmique, sauf pour des per-
sonnes qui connaissent une information supplémentaire.
Le destinataire choisit alors sa clé secrète et choisit une fonction à sens
unique pour calculer la clé publique qu’il diffuse. Les personnes qui ne connaissent
que la clé publique ne pourront pas calculer la clé privée.

2 Le cryptosystème RSA(p, q)
2.1 Définition. Soient p et q deux entiers naturels premiers. On pose N = pq.
Le système cryptographique RSA(p, q) est défini par :
(1) L’espace des textes clairs P = Z /26 Z,
(2) L’espace des textes chiffrés C = Z /N Z,
(3) L’ensemble des clés K = {e ∈ N | e > 2 et pgcd(e, (p − 1)(q − 1)) = 1},
(4) Pour e ∈ K, la fonction de chiffrement
Ee : Z /26 Z −→ Z /N Z
w 7−→ Ek (w) = we mod N ;

(5) et la fonction de déchiffrement

De : Z /N Z −→ Z /26 Z
z 7−→ De (z) = z d mod N

où d est l’inverse de e modulo (p − 1)(q − 1) :

ed = 1 mod (p − 1)(q − 1).

2.2 Remarque. L’espace des clés est donc l’ensemble des entiers inversibles
dans Z /ϕ(N ) Z, puisqu’ici, on a ϕ(N ) = (p − 1)(q − 1). Cette condition est nécés-
saire et suffisante pour pouvoir calculer la fonction de déchiffrement, qui est
l’inverse de la clé de chiffrement modulo ϕ(N ).

Pour montrer que RSA(p, q) est bien un système cryptographique, il nous

faut montrer que les fonctions Ee et De sont bien inverses l’une de l’autre,
pour tout e ∈ K. Or pour tout w ∈ C, on a

De ◦ Ee (w) = De (we mod N )

= ((we mod N )d )mod N
= wed mod N.

Or ed = 1 mod (p − 1)(q − 1), i.e. il existe k ∈ Z tel que

ed = 1 + k(p − 1)(q − 1).

3
Ainsi
wed = w1+k(p−1)(q−1) = w ∙ wk(p−1)(q−1) .
D’après le théorème d’Euler, on a

w(p−1)(q−1) = 1 mod N.

(Rappel : wϕ(N ) = 1 mod N ). Donc, finalement,

wed = w mod N,

i.e. De ◦ Ee (w) = w. De même, on a Ee ◦ De (z) = z pour tout z ∈ C. On a montré

que De ◦ Ee = IdP et Ee ◦ De = IdC . Donc, c’est bien un système cryptographique.

Paramètres utilisés par le système RSA(p, q) :

– N = (p − 1)(q − 1),
– la clé publique est e, un nombre premier avec (p − 1)(q − 1),
– la clé secrète est d, l’inverse de e modulo (p − 1)(q − 1),
– la fonction de chiffrement pour un message clair w est :

Ek (w) = we mod N,

– la fonction de déchiffrement pour un message chiffré c est :

Dk (c) = cd mod N.

En pratique, le fonctionnement du système se déroule comme suit : Alice

souhaite envoyer un message à Bob. Pour ce faire, Bob doit créer les clés pour
que Alice puisse chiffrer le message à partir de la clé publiée par Bob.
Bob choisit deux nombres premiers p et q et calcule

N = pq et ϕ(N ) = (p − 1)(q − 1).

Puis il choisit un nombre e > 2 premier avec ϕ(N ), qui sera la clé de chiffre-
ment. Ensuite, il calcule l’inverse de e modulo ϕ(N ), en utilisant l’AEE, qui
sera la clé de déchiffrement d. Enfin Bob publie le couple (e, N ) et garde secret
les nombres p, q, d et ϕ(N ). Alice pourra alors chiffrer les messages en utilisant
Ee et Bob pourra les déchiffrer en utilisant De .

2.3 Exemple. Bob choisit les nombres premiers p = 733, q = 193. Soit le
cryptosystème(733, 193). On a

N = 141469 et ϕ(N ) = 140544,

P = Z /26 Z, C = Z /141469 Z,
K = {e ∈ N | e > 2 et pgcd(e, 140544) = 1},

4
Bob peut factoriser ϕ(N ) = 140544 en produit de facteurs premiers pour trouver
un clé e :
140544 = 28 ∙ 32 ∙ 61
Un nombre est alors premier avec 140544 si sa décomposition en facteurs pre-
miers ne contient pas les nombres premiers 2, 3 ou 61. Le nombre e = 515 =
5.103 est donc une clé. La fonction de chiffrement est définie par

E515 : Z /26 Z −→ Z /141469 Z

w 7−→ Ek (w) = w515 mod N ;

Pour calculer l’inverse de 515 modulo 140544 afin de trouver D515 , Bob peut
appliquer l’AEE. Il trouve d = 27563. La fonction de déchiffrement est alors
définie par

D515 : Z /141469 Z −→ Z /26 Z

z 7−→ D515 (z) = z 27563 mod N.

Nous allons chiffrer le mot OUI =15, 21, 9 en utilisant E515 :

E
→ 15515
15 7−515 mod 141469 = 48945,
E
→ 21515
21 7−515 mod 141469 = 2836,
E
→ 9515
9 7−515 mod 141469 = 37785.

Donc OUI est chiffré en 48945, 2836, 37785.

2.4 Remarque. On ne peut plus écrire le chiffrement à l’aide des lettres de

l’alphabet usuel car on obtient des nombres très grands, donc > 26.

Pour déchiffrer le texte chiffré, on utilise D515 :

D
515
48945 7−→ 1527563 mod 141469 = 15,
D
515
2836 7−→ 2127563 mod 141469 = 21,
D
515
37785 7−→ 927563 mod 141469 = 9.

En revenant à l’alphabet usuel, on obtient le mot OUI.

3 Sécurité du système RSA(p, q)

En pratique, on doit choisir les nombres p et q de telle sorte que leur produit
N = pq soit un grand nombre. Aujourd’hui, on peut prendre pour p et q des
nombre premiers de plus de 200 chiffres décimaux pour favoriser la sécurité
d’un message.

5
 L’application qui, à une clé e ∈ K associe l’inverse d de e modulo ϕ(N ) est un
exemple de fonction à sens unique (ou à trappe). Bob peut facilement calculer
d puisqu’il connaît la factorisation N = pq, mais un attaquant éventuel, c-à-d
une personne, autre que Bob (ne connaissant que N et e), qui veut regarder
ou même modifier un message chiffré z , ne pourra pas calculer d, donc ne
pourra pas déchiffrer le message, comme le montre les résultats suivants :

3.5 Lemme. La connaissance de ϕ(N ) est équivalente à la factorisation de N .

Preuve. Si la factorisation de N est N = pq, alors ϕ(N ) = (p − 1)(q − 1) est facile

à calculer.
Réciproquement, supposons que ϕ(N ) soit connu. Alors, en substituant q
par Np dans l’équation
ϕ(N ) = (p − 1)(q − 1),
on obtient l’équation du second degré

p2 − (N + 1 − ϕ(N ))p + N = 0,

qu’il est alors facile de résoudre en p. On en déduit q = N

p
. Donc N = pq est la
factorisation de N .

D’après ce lemme, l’attaquant qui ne connaît ni ϕ(N ), et ni p ni q sera

confronté au problème de la factorisation, s’il veut calculer la clé de déchiffre-
ment d.
Or, la factorisation d’un grand nombre N est un problème très coûteux,
donc être impossible en pratique. Ainsi, l’attaquant ne pourra pas calculer la
clé de dechiffrement en utilisant e et N uniquement, il lui faut ϕ(N ) ou p et q,
qu’il ne connaît pas.
Par exemple, pour l’algorithme par les divisions successives, le coût est
exponentiel en n2 où n est le nombre de chiffres de N . P.e., si n = 100, le coût
est de l’ordre de e50 = 5, 18 ∙ 1021 divisions.
Effectuons cette factorisation sur un ordinateur avec un processeur de
3GHz, c’est-à-dire qui effectue 3 milliards d’opérations par seconde. Il faudrait
pour cela environ 54802 années ! Par conséquent, il est pratiquement impos-
sible d’effectuer cette factorisation !