L’ALGORITHME D’ECHANGE DES CLES DIFFIE-HELLMAN

UNIVERSITE DE DOUALA

ECOLE NORMALE SUPERIEURE

DE L’ENSEIGNEMENT TECHNIQUE

B. P. 1872 Douala Cameroun

Tél. (Fax) : (237) 33 40 42 91 - E-mail : [email protected]

COURS DE PROMOTION SOCIALE (CPS)

Filière : GENIE ELECTRIQUE

Option : RESEAUX ET TELECOMMUNICATIONS

MASTER 2

REDIGE PAR :

TCHONANG JOUONANG ELVIS

MATRICULE : 12GRT1049

ENSET

EXPOSE COURS SECURITE DES SYSTEMES D’INFORMATIONS

L’Algorithme d’échange des clés DIFFIE-HELLMAN

Ministère de l’Enseignement Supérieur

Paix – Travail – Patrie

République du Cameroun

Ministry of Higher Education

Peace – Work – fatherland

Republic of Cameroon

Année académique : 2013 / 2014

ENSEIGNANT : M. KOUM CLAUDE

L’ALGORITHME D’ECHANGE DES CLES DIFFIE-HELLMAN

Exposé Cours Sécurité des Systèmes d’Informations présenté par : TCHONANG JOUONANG ELVIS 1

SOMMAIRE

SOMMAIRE ............................................................................................ 1

INTRODUCTION ................................................................................... 2

I. Histoire : Les créateurs ...................................................................... 2

II. L’algorithme de Diffie-Hellman ....................................................... 3

II.1 Rôle de Diffie-Hellman ................................................................. 3

II.2 Principe de l’algorithme d’échange des clés Diffie-Hellman ....... 3

II.2.1 Quelques Outils Mathématiques .............................................. 3

II.2.2 Procédure d’échange des clés DIFFIE-HELLMAN ................ 4

II.2.3 Exemple de calcul de la clé Sécrète via l’algorithme DIFFIE-

HELLMAN ........................................................................................ 4

II.2.4 Exemples d'applications du protocole de DIFFIE-HELLMAN

............................................................................................................ 5

II.2.5 Faiblesse de l'algorithme : attaque de l'homme du milieu ...... 5

II.2.6 Exemples de protocoles intégrant l’échange de clé de Diffie-

Hellman .............................................................................................. 6

CONCLUSION ....................................................................................... 6

REFERENCES BIBLIOGRAPHIQUES ................................................ 6



INTRODUCTION

Depuis la nuit des temps des empires cherchent à cacher des informations à leurs ennemis.

Ils ont pour cela développé des méthodes pour encoder et décoder leurs données. Aujourd’hui

avec l’ère de l’informatique et la puissance de calcul qui en découle, la cryptologie est une

science primordiale pour les services secrets, mais également pour le secteur bancaire et plus

généralement les entreprises.

Dans ce document nous expliquerons les fondements théoriques de l’algorithme de Diffie-

Hellman. Pour cela, nous ferons d’abord une brève présentation des créateurs ensuite nous

évoqueront le principe de ce protocole, quelques outils mathématiques implémentés dans

l’échange des clés et donneront à la fin les limites de Diffie-Hellman et quelques domaines

d’application de ce dernier

I. Histoire : Les créateurs

L’algorithme Diffie-Hellman tient son nom de ses auteurs WHITFIELD DIFFIE et

MARTIN HELLMAN.

BAILEY WHITFIELD DIFFIE né le 5 juin 1944, est un cryptologue américain. Il est l’un

des pionniers de la cryptographie asymétrique (utilisation d’une paire de clés publiques et

privées) en collaboration avec MARTIN HELLMAN et RALPH MERKLE .

En 1965, il reçoit un Bachelor en mathématiques au MIT. En 1976 avec l’aide de MARTIN

HELLMAN , il publie New Directions in Cryptography. La méthode révolutionnaire décrite

dans cet article permet de résoudre un problème fondamental en cryptographie : la distribution

des clés. Cette méthode sera par la suite renommée en méthode d’échange de clés Diffie-

Hellman et c’est elle que nous allons présenter dans ce document

MARTIN HELLMAN quant à lui né le 2 octobre 1945, est aussi un cryptologue

américain. Il a lui aussi développé la cryptographie asymétrique (découverte faite en

Collaboration avec RALPH MERKLE et WHITFIELD DIFFIE ). Hellman est aussi a

L’origine d’une attaque avec compromis temps/mémoire notamment utilisée pour trouver des

mots de passe.



II. L’algorithme de Diffie-Hellman

II.1 Rôle de Diffie-Hellman

La cryptologie est une science qui englobe d’une part la cryptographie c’est à dire

l’écriture secrète des données, et la cryptanalyse qui est l’analyse de cette dernière.

En règle générale les méthodes de cryptage font appellent à des clés de cryptage. Une clé de

cryptage est un ensemble de valeurs qui permet d’encoder et de décoder des données.

Des algorithmes tels que le RSA utilisent plusieurs nombres premiers qui doivent être tenus

secrets. Or la difficulté est de pouvoir communiquer la clé de cryptage d’un émetteur A à un

destinataire B sans qu’une tiers personne E ne puisse l’intercepter. C’est la que ‘algorithme

Diffie-Hellman intervient. Il propose à A et B de pouvoir définir une clé secrète même si E

écoute leur communication.

II.2 Principe de l’algorithme d’échange des clés Diffie-Hellman

En cryptographie, l'échange de clés Diffie-Hellman du nom de ses auteurs WHITFIELD

DIFFIE et MARTIN HELLMAN , est une méthode par laquelle deux personnes nommées

conventionnellement Alice et Bob peuvent se mettre d'accord sur un nombre (qu'ils peuvent

utiliser comme clé pour chiffrer la conversation suivante) sans qu'une troisième personne

appelée Ève puisse découvrir le nombre, même en ayant écouté tous leurs échanges. Le but de

l’algorithme est donc de créer un secret commun aux personnes qui veulent communiquer et

d’utiliser ce secret pour chiffrer les données échangées.

II.2.1 Quelques Outils Mathématiques

Théorème (Petit théorème de FERMAT )

Soient p un nombre premier et k €Z. Si p et k sont premiers entre eux alors

kp-1 ≡ 1 mod p. De plus pour tout k €Z on a : kp ≡ k mod p.

Racine Primitive

Soit W € F*p On appelle W une racine primitive si les deux conditions suivantes sont

satisfaites : W i ≠ 1; pour 1 ≤ i < p -1 et W i = 1; pour i = p -1.



II.2.2 Procédure d’échange des clés DIFFIE-HELLMAN

Nous allons vous présenter la procédure étape par étape. Elle permet d’échanger des clés

de manière sécurisée.

Considérons deux individus, A et B, qui souhaitent s’envoyer un message crypté.

Les données et les échanges sont les suivants :

Tout d’abord A et B se mettent d’accord sur un nombre premier p. Puis ils conviennent

d’une racine primitive g.

A choisi un nombre au secret a tel que : 0 <a<p-1.

A envoie la valeur ga mod p à B.

B choisi un nombre secret b tel que 0< b<p-1.

B envoie la valeur gb mod p à A.

A peut désormais calculer la clé secrète : key = (gb mod p) a mod p.

B procède de manière analogue et obtient la clé que A : key = (ga mod p) b mod p.

A et B sont alors en possession chacun de la même clé secrète (key) et peuvent ainsi utiliser un

simple algorithme de clé privée.

Nous pouvons dire que cette méthode est sécurisée car, supposons qu’une troisième

personne, disons E, écoute les transmissions de A et B. Dans ce cas E n’a accès qu’à p, g, ga

mod p et gb mod p.

Dans ce cas, on peut se demander pourquoi il n’est pas possible à E de calculer a ou b afin

d’obtenir la clé secrète. Il peut, en apparence, paraitre simple de calculer a = logg(ga) ou b =

logg(gb). Mais ce n’est pas le cas car on travaille ici en mod p. Ce qui implique de calculer un

logarithme discret. Or d’après la littérature, il n’existe pas à ce jour de solution rapide pour le

calculer. E est donc dans l’impossibilité de déterminer (ga mod p) b mod p.

Notons tout de même qu’il faut que p soit suffisamment grand pour éviter que E tente une

recherche exhaustive. Actuellement, en utilisant un nombre premier p de l’ordre de 500 à 1024

chiffres et a et b de l’ordre de 100 chiffres, il est impossible de déterminer la clé secrète, même

avec les meilleurs algorithmes de résolution de logarithme discret.

II.2.3 Exemple de calcul de la clé Sécrète via l’algorithme DIFFIE-HELLMAN

1. Alice et Bob choisissent un nombre premier p et une base g. Dans notre exemple, p=23

et g=3

2. Alice choisit un nombre secret a=6



3. Elle envoie à Bob la valeur A = ga mod p = 36 [23]= 16

4. Bob choisit à son tour un nombre secret b=15

5. Bob envoie à Alice la valeur B = gb mod p = 315[23] = 12

6. Alice peut maintenant calculer la clé secrète : (B) a [mod p] = 126 [23] = 9

7. Bob fait de même et obtient la même clé qu'Alice : (A) b [mod p] = 1615 [23] = 9

II.2.4 Exemples d'applications du protocole de DIFFIE-HELLMAN

Le protocole DIFFIE-HELLMAN est principalement appliqué dans les domaines

suivants : Sécurité Internet, sécurité bancaire, applications gouvernementales (militaires,

services secrets, . .).

II.2.5 Faiblesse de l'algorithme : attaque de l'homme du milieu

Ce protocole est vulnérable à « l'attaque de l'homme du milieu », ce qui implique un

attaquant capable de lire et de modifier tous les messages échangés entre A et B.

Cette attaque repose sur l'interception de ga et gb, ce qui est facile puisqu'ils sont échangés en

clair ; l'élément g étant supposé connu par tous les attaquants. Pour retrouver les nombres a et b

et ainsi casser complètement l'échange, il faudrait calculer le logarithme discret de ga et gb, ce

qui est impossible en pratique. Mais un attaquant peut se placer entre A et B, intercepter la clé

ga envoyée par A et envoyer à B une autre clé ga', se faisant passer pour A.

De même, il peut remplacer la clé gb envoyée par B à A par une clé gb', se faisant

passer pour B. L'attaquant communique ainsi avec A en utilisant la clé partagée ga b'et

communique avec B en utilisant la clé partagée ga'b, A et B croient communiquer directement.

C'est ce que l'on appelle « attaque de l'homme du milieu : A et B croient ainsi avoir échangé

une clé secrète alors qu'en réalité ils ont chacun échangé une clé secrète avec l'attaquant,

l'homme du milieu

Solution :

La parade classique à cette attaque consiste à signer les échanges de valeurs à l'aide d'une

paire de clés asymétriques certifiées par une tierce partie fiable, ou dont les moitiés publiques

ont été échangées auparavant par les deux participants. A peut ainsi être assurée que la clé

qu'elle reçoit provient effectivement de B, et réciproquement pour B.



II.2.6 Exemples de protocoles intégrant l’échange de clé de Diffie-Hellman

• Station to station protocol: Le protocole Station to Station (STS) consiste à combiner

l’échange de clé de Diffie-Hellman avec de la signature à clé publique, assurant ainsi

l’authentification mutuelle des deux interlocuteurs de manière à éviter l’attaque de

l’homme au milieu.

• Secure Shell (SSH)

• Le protocole de gestion de clés automatisé pour IPSec ISAKMP/Oakley : le

Protocole d’Oakley est un protocole de détermination de clés basé sur l’algorithme de

Diffie-Helman avec une sécurité ajoutée. ISAKMP est un protocole fournissant un

cadre pour la gestion des clés, et des formats pour la négociation des attributs de

sécurité.

CONCLUSION

Le système Diffie-Hellman peut être appliqué au chiffrage à clef publique. Ainsi, le

système Diffie-Hellman est aussi une méthode de chiffrage à clef publique. Il n'a pas connu le

succès, pour des raisons tant commerciales qu'historiques. Un concurrent sérieux est arrivé

avec l'invention du système RSA. Ce dernier avait un atout décisif : il permet l'authentification

des messages ce que Diffie-Hellman ne sait pas faire. DIFFIE-HELLMAN est souvent associé

à DSS (Digital Signature Standard, un autre algorithme, DSS permet de signer des

documents. On voit souvent le sigle DH associé à DSS : DH/DSS qui est l’algorithme par

défaut de Gnu Privacy Guard (GPG). Néanmoins, l'évolution de la technologie à permis de

mettre sur pieds DIFFIE-HELLMAN signé V3 selon la norme ISO/IEC 9798-3.

REFERENCES BIBLIOGRAPHIQUES

[1] : http://fr.wikipedia.org/w/index.php?oldid=97164547

[2] : http://www.bibmath.net/crypto/index.php

[3] : José R. Beuret, Gwenol Grandperrin , Le protocole DIFFIE-HELLMAN, 18 avril 2008

Documents

L’ALGORITHME D’ECHANGE DES CLES DIFFIE-HELLMAN