Cours : Cryptographie et Sécurité Informatique

Chapitre 5. Cryptographie asymétrique

I. Akharraz
Université Sidi Mohamed Ben Abdellah

[email protected]
1/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Sommaire

2/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Introduction

Systèmes cryptographique symétrique :

• Une même clé pour le chiffrement et le
déchiffrement.
• Problème de transmission de la clé : il faut une
clé par destinataire.

Systèmes cryptographique asymétriques (ou à clef

publique):
• Chaque personne possède 2 clés distinctes : une
privée et une publique.
• Impossibilité de déduire la clé privée à partir de
la clé publique.
• Possiblité de distribuer librement la clé publique.

3/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Introduction

• Le concept de clef publique date officiellement de

1976(Diffie et Hellman).
• La première implémentation a lieu en 1978 par
Rivest, Shamir et Adleman sous la forme de
l'algorithme RSA.
• Les codes asymétriques les plus utilisés:
• RSA basé sur la difficulté calculatoire de la
factorisation des grands entiers. 4/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Introduction

•El Gamal basé sur la difficulté calculatoire de

calculer le logarithme discret dans un corps fini.

•Menezes-Vanstonne basée sur le logarithme

associé au groupe des points d'une courbe elliptique
sur un corps fini.

• Il existe d'autres codes asymétriques peu utilisés :

•McEliece basé sur la théorie algébrique des

codes correcteurs d'erreurs. considéré comme sûr,
nécessite des clefs extrèmement longues 1019 bits.

•Chor-Rivest Basé sur une instance du problème du

sac-à-dos.
5/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Principe des codes à clef publique.

Fonctions à sens unique.

On cherche une fct f entre des ensembles P et C telle
que :
• Le calcul de f(x) pour x ∈ P se fait en temps
polynomial en fct de la taille des données.
• le calcul de f (−1) (y ) pour y ∈ C ne se fait pas
en temps polynomial en fct de la taille des données.
• Le plus souvent la fonction f possède une porte
dérobée (trapdoor) qui permet de calculer facilement
f −1 (y ) lorsqu'on a une information supplémentaire
comme la clef secrète.
• Autrement, on cherche des fct f : P −→ C
appartient à la classe des problèmes P et telle que la
réciproque f (−1) appartienne à la classe des problèmes
NP.
• La mise au point de telles fonctions a révolutionné
la cryptographie. 6/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

• Un des premiers proposés ( 1978).

• Repose sur le problème du sac-à-dos.

Le problème du sac-à-dos.
Le problème du sac-à-dos s'énonce de la manière
suivante:
• Soit a un ensemble d'entiers {a1 , a2 , ..., an ; s}.
• Existe-t-il un sous-ensemble de {a1 , a2 , ..., an }.
dont la somme soit s.
Remarque
on peut considérer que les ai représentent la taille de paquets que
l'on veut mettre dans un sac-à-dos de taille s, ou encore qu'ils
représentent des billets et des pièces monnaies destinées à payer un
objet dont le prix est s.
7/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

Théorème
(Karp 1972). Le problème du calcul de la solution, supposée
exister, du sac-à-dos est un problème génériquement NP-complet.
• Ce théorème signifie que génériquement trouver une
solution, que l'on sait exister, au problème du
sac-à-dos est difficile c'est à dire que la calcul de
la solution nécessite un temps exponentiel en fonction
de la taille des données.
• Le mot générique signifie qu'il existe au moins un
ensemble a ayant une solution tel que le calcul de la
solution ne se fasse pas en temps polynomial en
fonction de la taille des données.
• Le problème est de cacher une clef secrète, une
porte dérobée, ou trapdoor qui permette au
destinataire du message de le décoder.
8/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

• On choisit un entier M on dira que

a = {a1 , a2 , ... , an ; s} est un problème de sac-à-dos modulo
M s'il existe :
{ak , ... , akm } ⊂ {a1 , a2 , ... , an }
1

tel que
ak + ... + akm ≡ s mod M
1

Description du cryptosystème Merkle-Hellman.

• L'idée principale de Merkle et Hellman consiste à
choisir un sac-à-dos particulier dont la solution est
triviale et à cacher cette forme particulière du
sac-à-dos par une transformation secrète connue
seulement par destinataire du message.

• La forme retenue par Merkle et Hellman est le

sac-à-dos super-croissant (super-increasing knapsack).
9/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

Dénition
Une suite d'entier {b1 , b2 , ... , bn , bn+1 } est dite super-croissante si
l'on a:
X1
j=i−
bi > bj , pour 1 ≤ i ≤ n + 1
j=1

Théorème
(1) Si {b1 , b2 , ... , bn , bn+1 } est super-croissante et si M = bn+1
alors tout problème de sac-à-dos {b1 , b2 , ... , bn , ; s} modulo M est
équivalent au problème de sac-à-dos {b1 , b2 , ... , bn , ; s} sur les
entiers naturels.
(2) bn est dans le sous-ensemble de la solution si et seulement si
bn ≤ s et on peut alors ramener le problème initial au problème de
sac-à-dos {b1 , b2 , ..., bn−1 ; s } avec s = s − bn ou s .
0 0

10/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

Remarque
La transformation secrète destinée à cacher le fait que l'on a un
sac-à-dos super-croissant est simplement la multiplication par un
nombre secret M.
Le crypto-système de Merkle et Hellman :
1. Paramètre public n.
2. Fabrication de la clef:
• Choisir un suite super croissante
{b1 , b2 , ... , bn , bn+1 = M}
• Choisir un nombre W ∈ ZZ /MZZ et une
permutation π de {1, ... , n}.
• Calculer ai = Wbπ(i) (mod M) pour 1 ≤ i ≤ n.
3. Clef Publique : Kp = (a1 , a2 , ..., an )
4. Clé secrète : Ks = (b1 , b2 , ... , bn , M, W , π)
5. Message : une suite de zéros et de uns de
longueur n, m = m1 m2 ... mn . 11/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

6. Codage :
n
X
c= mi ai
i=1
7. Décodage :
• calculer cW−1 (modM),
• résoudre le problème de sac- à-dos
super-croissant x1 b1 + ... + xn bn = cW −1 (modM),
• Alors mi = xπ(i) .

• Le crypto-système Merkle-Hellman revient à trouver

un vecteur de sélection V = (x1 , ..., xn ) satisfaisant la
relation : x1 b1 + ... + xn bn = cW −1 (mod M) : xi = 1 si
l'objet est présent dans la suite super croissante et
xi = 0 si non.

12/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

Exemple

(1) Calcul de la clé publique :

• Soit S, une séquence super-croissante de n entiers :
par exemple S = {1, 2, 4, 9,17}.
• Choisissons un multiplicateur W et un module M :
soit W = 15 et M = 17
• 1 * 15 mod 17 −→ 15
• 2 * 15 mod 17 −→ 13
• 4 * 15 mod 17 −→ 9
• 9 * 15 mod 17 −→ 16
• Kp = {15, 13, 9, 16}, la clé publique.
Chiffrement :
• Un message P est traité comme une séquence de bits :
P = (p1 , p2 , p3 , ..., pk ).
13/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

• On le divise en blocs de n bits : P0 = (p1 , p2 , p3 ,

..., ph ), P1 = (pn+1 , pn+2 , pn+3 , ..., p2n ),...
On utilise chaque bloc comme vecteur V du problème de
havresac.
Soit P = (0100101110100101) =⇒ 0100 1011 1010 0101 :
• (0, 1, 0, 0) *(15, 13, 9, 16) =⇒ 13
• (1, 0, 1, 1]) * (15, 13, 9, 16) =⇒ 40
• (1, 0, 1, 0) * (15, 13, 9, 16) =⇒ 24
• (0, 1, 0, 1)*(15, 13, 9, 16) =⇒ 29
Le message chiffré est donc {13, 40, 24, 29} en
utilisant le havresac public (la clef publique)
Kp = {15, 13, 9, 16}.

14/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

Déchiffrement : le destinataire légitime connaît le

havresac simple S et les valeurs de W et de M. Il peut
donc déterminer W−1 .
Pour W = 15 et M = 17, on a : W−1 = 8 car 15 *8 = 120
= 7* 17 + 1.
Alors :
• 13 * 8 mod 17 = 104 mod 17 = 2 = (1, 2, 4, 9) *
(0100).
• 40 *8 mod 17 = 320 mod 17 = 14 = (1, 2, 4, 9) *
(1011).
• 24 * 8 mod 17 = 192 mod 17 = 5 = (1, 2, 4, 9) *
(1010]).
• 29 * 8 mod 17 = 232 mod 17 = 11 = (1, 2, 4, 9) *
(0101).
Le texte en clair est : 0100 1011 1010 0101 =⇒
0100101110100101.
15/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème Merkle-Hellman.

Sécurité

• Plusieurs failles ont été découvertes, qui ont rendu

l'algorithme obsolète.

16/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

• Le système RSA est nommé d'après le nom de ses

inventeurs: Rivest, Shamir, Adleman.

• Il est basé sur la fonction à sens unique produit de

deux entiers :

• Sa fonction réciproque étant la décomposition d'un

nombre entier en un produit de deux facteurs non
triviaux ( différents de 1 et du nombre lui même).
• Celà revient à la décomposition en facteurs premiers
d'un entier.
17/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

Description du cryptosystème RSA. Soit un ensemble

(Ai )i ∈ I de correspondants (personnes physiques ou
ordinateurs).
Le principe du cryptosystème RSA est le suivant :
• Chacun des correspondants Ai choisit deux nombres
premiers pi et qi distincts. On note ni = pi qi , le
module du cryptosystème de Ai et ϕ(ni ) = (pi − 1)(qi − 1),
l'indicatrice d'Euler de ni .

• Ai choisit ensuite un nombre ei l'exposant de la clé

publique premier avec ϕ(ni ) (ce que l'on note
ei ∧ ϕ(ni ) = 1).

18/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

• D'après le petit théorème de Fermat, on peut

imposer:
• 1 ≤ ei ≤ ϕ(ni ) − 1, ce que l'on fait toujours en
pratique.
• Puis Ai calcule l'inverse di de ei modulo ϕ(ni ),
di est appelé l'exposant de la clé secrète. C'est à
dire, d'après la définition de l'inverse modulo ni ,
qu'on cherche di ∈ IN tel qu'il existe ki ∈ IN avec
di ∗ ei = 1 + ki ϕ(ni ) et 1 ≤ di ≤ ϕ(ni ) − 1 (Le calcul se
fait par l'algorithme d'Euclide étendu)

• Chacun des correspondants Aj publie dans un annuaire

public les nombres nj et ej qui forment sa clé publique
de chiffrement et garde secret pj , qj et dj qui forment
sa clé secrète de déchiffrement.
19/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

Remarque
En pratique on choisit les nombres premiers pi et qi de taille
comparable de telle sorte que leur produit ni = pi qi soit un nombre
d'au moins 300 chires en base 10 ou 500 pour une protection
longue.
Protocole d'envoi d'un message en RSA.
Ali veut envoyer un message M à Brahim. La clef
publique d'Ali (resp Brahim) est (na , ea ), (resp.
(nb , eb )), sa clef secrète est (pa , qa , da ) (resp.
(pb , qb , db )).
Ali suit le protocole suivant :
1. Ali commence par transformer le message en une
suite de chiffres, par exemple en remplaçant les
lettres et les différents symboles utilisés par des
chiffres (de 0 à 255 dans le cas du code ASCII).
20/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

2. Ali regarde dans l'annuaire public la clé de

chiffrement nb , eb de Brahim. Elle découpe le message
M en blocs M de taille nb .
3. Ali calcule fb (M) = M 0 ≡ M eb mod nb et envoie
M 0 = fb (M) à Brahim.
4. Pour récupérer le texte en clair Brahim calcule
fb−1 (M 0 ) = (M 0 )db = fb (M)db ≡ M eb db = M 1+kb ϕ(nb ) mod nb
D'après le théorème d'Euler on a : M ϕ(nb ) ≡ 1 mod nb
et par conséquent fb−1 (M 0 ) ≡ M mod nb .
Remarque
Si la taille de M est adaptée à celle de nb , Brahim récupère donc
bien le message d'Ali.

21/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

Exemple
Ali publie sa clé publique (nA , eA ) = (65, 5), sa clef
secrète est dA .
Brahim publie sa clé publique (nB , eB ) = (77, 7), sa clef
secrète est dB .
Pour trouver les clefs secrètes on décompose en un
produit de facteurs premiers nA et nB : nA = 13 ∗ 5 et
nB = 7 ∗ 11. On calcule ensuite les indicatrices
d'Euler correspondantes ϕ(nA ) = 12 ∗ 4 = 48 et
ϕ(nB ) = 6 ∗ 10 = 60.
En utilisant l'algorithme de PGCD on calcule dA et dB :
5 ∗ 29 = 145 = 1 + 3 × 48 =⇒ dA = 29
7 43 = 301 = 5 60 + 1 =⇒ dB = 43
Ali veut transmettre le message 3 à Brahim. Il
calcule donc 37 ∼ = 31mod 77 = 7 ∗ 11 et elle envoi 31 à
Brahim. Brahim décode en calculant
3143 ∼
= 311+2+8+32 ∼= 31 ∗ 37 ∗ 58 ∗ 37 ∗ 31 ∼
= 3mod 77 22/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

Résumé
• Génération de 2 nombres premiers p et q
• Calcul de n = p*q
• Déterminer e tel que 3 < e < ϕ(n) et (e, ϕ(n)) = 1
• Calculer d tel que e*d ≡ 1 mod ϕ(n)
• Clé publique : (e,n)
• Clé privée : (d,n)
• p et q doivent rester secrets, voire supprimés
• C = Me mod n et M = C d mod n
Remarques
Il n'est pas très astucieux de choisir d'aussi petites
valeurs car on peut retrouver d très facilement.

23/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

Attaques sur RSA

Il existe trois approches pour attaquer le RSA :
(1) Recherche par force brute de la clé (impossible
étant donné la taille des données),
(2) Attaques mathématiques (basées sur la difficulté
de calculer ϕ(n), la factorisation du module n) :
• Factoriser n = p ∗ q et par conséquent trouver
ϕ(n) et puis d,

• Déterminer ϕ(n) directement et trouver d,

• Trouver d directement.

• Attaques de synchronisation (sur

le fonctionnement du déchiffrement).
24/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

• A l'heure actuelle, la factorisation connait de

lentes améliorations au cours des années.
• La meilleure amélioration possible reste
l'optimisation des algorithmes.
• Excepté un changement dramatique, le RSA- 1024
restera sûr pour les prochaines années.
• D'après les projections, une clé de 2048 bits est
sensée tenir jusque 2079 si on tient compte de la loi
de Moore.
• Mais ces valeurs sont correctes uniquement si on
respecte les propriétés de e, d, p et q.

25/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

Attaque de synchronisation (timing attack)

• Développé dans le milieu des années 90, il s'agit

d'exploiter les variations de temps pris pour
effectuer certaines opérations (par exemple la
multiplication par un petit ou un grand nombre).
• Plusieurs contre-mesures existent telles que
l'emploi de temps constants d'élévation à une
puissance, l'ajout de délais aléatoires, ou le fait de
rendre non visibles les valeurs utilisées dans les
calculs.

26/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

La menace quantique

Les valeurs précitées sont valables si on pratique la

factorisation. A coté de cela, la physique pourrait
faire pencher la balance, par l'utilisation d'un
ordinateur quantique. Celui-ci existe d'un point de
vue théorique depuis 1994 (algorithme de Shor), et son
prototype depuis 1996. Si son évolution se poursuit,
il permettrait de réaliser la factorisation d'un
nombre en un temps polynomial. Le principe est que
les 0 et 1 représentés par les portes logiques des
transistors sont remplacés par l'orientation du champ
magnétique émit par les atomes (que l'on nomme des
q-bits).
27/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique

Le cryptosystème RSA.

Conseils d'utilisation du RSA

Pour garantir une bonne sécurité, il faut respecter

certains règles telles que :
• Ne jamais utiliser de valeur n trop petite,

• N'utiliser que des clés fortes (p-1 et q-1 ont un

grand facteur premier),
• Ne pas chiffrer de blocs trop courts,

• Ne pas utiliser de n communs à plusieurs clés,

• Si (d,n) est compromise ne plus utiliser n.

28/28

I. Akharraz Université Sidi Mohamed Ben Abdellah Chapitre 5. Cryptographie asymétrique