José M. Fernandez
M-3109340-4711 poste 5433
INF4420: Sécurité InformatiqueCryptographie III
INF4420Sécurité Informatique
INF4420Sécurité Informatique
2
Aperçu – Crypto IIIAperçu – Crypto III
� Cryptographie à clé publique (suite)� RSA (suite)� Problème du log discret� Chiffre de El-Gamal� Chiffrement à courbe elliptique
� Autres primitives cryptographiques� Hachage cryptographique � Signatures digitales� Stéganographie
� Principes d'utilisation de la crypto� Gestion de clés privés et publiques� Standards cryptographiques
� Risques résiduels liés à l'utilisation de la crypto� (récapitulation)
INF4420Sécurité Informatique
INF4420Sécurité Informatique
3
RSA – Problématique d’implantationRSA – Problématique d’implantation
� Génération de clés� Comment générer N = p*q
• Combien de premiers de taille n/2 existent-ils?
� (Théorème des nombres premiers) ~ O(2n/2 / (n/2)) = O(2n/2-1/n)
� P.ex. pour n = 1024, nombre de premiers = 21012 choix de clés
• Comment vérifier si un entier aléatoire est premier ?
� Algorithme temps polynomial (probabiliste et déterministe)
� Comment générer clé publique e t.q. pgcd(e, N) = 1• Algorithme d’Euclides (temps polynomial) permet de calculer e mod N, donc
de vérifier si pgcd(e, N) = 1
• Il existe ϕϕϕϕ(n) = (p-1)(q-1) = N – p – q = O(2n) entier moins que N valable (presque tous!)
� Comment trouver d t.q. e*d = 1 modϕ(N)• Algorithme d’Euclide étendu (aussi temps polynomial) permet de trouver
inverse multiplicatif, donc d, SEULEMENT SI ON CONNAÎT ϕϕϕϕ(n)
� Il est facile de générer autant de paire de clés qu’on veut efficacement
INF4420Sécurité Informatique
INF4420Sécurité Informatique
4
RSA – Problématique d’implantation (suite)RSA – Problématique d’implantation (suite)
� Comment coder ?� Alphabet de source ΣΣΣΣ, |ΣΣΣΣ| = M, log M = m� recoder les symboles de sources en bits
• P.ex. sans compression : chaque σ∈Σ � m bits
� construire des blocs de n bits• Si n > m, regrouper n/m symboles dans un seul mot de code• Si n < m, diviser en m/n blocs de n bits• � Mais attention à l’entropie
� Et si le mode code construit x est t.q. pgcd(x,N) ?� Alors on est « fait » :
• le chiffreur (Alice) a découvert un facteur de N, donc p ou q• Elle peut calculer la clé privée de Bob …
� Quelles en sont les probabilités ?• Prob = N-ϕ(N)/N = (p+q)/ N = (p+q)/pq ~ 1 sur 2 n/2 (négligeable)
INF4420Sécurité Informatique
INF4420Sécurité Informatique
5
RSA – Niveau de sécuritéRSA – Niveau de sécurité
� La seule méthode connue pour retrouver la clé privéd et
cassé RSA est de connaître ϕ(N)� On peut calculer ϕ(N) si on peut factoriser N
� Si on connaît ϕ(N) on peut calculer les facteurs
� Casser RSA par cette méthode est aussi difficile que factoriser
� Sécurité de RSA basée sur deux principes/hypothèses1. Il n’existe pas d’algorithme efficace pour factoriser
2. Il n’y pas moyen de casser RSA sans connaître ϕ(N)
INF4420Sécurité Informatique
INF4420Sécurité Informatique
6
Notion de groupeNotion de groupe
� Notion de groupe (G, ⊗⊗⊗⊗)� Un ensemble abstrait G sur lequel on a défini une opération abstraite " ⊗⊗⊗⊗
" avec certaines propriétés :• élément identité : ∃ 1∈ G, t.q. ∀a ∈ G, a⊗ 1 = a• Associativité : ∀a, b, c ∈ G, a ⊗ (b ⊗ c) = (a ⊗ b) ⊗ c, • Tout éléments à un inverse : ∀a ∈ G, ∃ a-1 t.q.a ⊗ a-1 = 1• (Commutativité): ∀a, b ∈ G, a ⊗ b = b ⊗ a
on dit alors que le groupe est "abélien" ou "commutatif"
� Exponentiation:• an = a ⊗ a ⊗ … ⊗ a, n fois
oùn est un entier et (G, ⊗) est un groupe abélien
� Note: On peut définir le problème de log discret sur n'importe quel groupe abélien !
� Exemples :� Corps fini (corps de Galois)� Courbe elliptique
INF4420Sécurité Informatique
INF4420Sécurité Informatique
7
Problème du log discretProblème du log discret
� Propriétés mathématiques de Zp
� Tous les éléments de Zp ont des inverses multiplicatifs, sauf 0• Donc, Zp
* = Zp - {0}
� Il existe des éléments g dit générateurou racine primitive tel que : <g> = {g0, g1, … , gp-1} = Zp
*
• Notes:
� Il est possible de vérifier en temps polynomial si un élémentg est un
générateur.
� Il existe un très grand nombre de générateurs dansZp*
� Définition : Le logarithme discret en base g de a ∈∈∈∈ Zp est l'entier xtel que a = gx mod p
� Hypothèse calculatoire: Il n'est pas possible de calculer le log discret en temps polynomial sans connaître la factorisation de p-1.
INF4420Sécurité Informatique
INF4420Sécurité Informatique
8
Chiffre de El-GamalChiffre de El-Gamal
� Génération de clé1. Trouver un grand entier premier p tel que p-1 a au moins un grand facteur premier (donc
difficile à trouver).2. Choisir au hasard un générateur g de Zp
* et un entier d3. Calculer la valeur e= gd mod p 4. Clé publique = (p, g, e), Clé privé = d
� Chiffrement/Déchiffrement : Pour un message x ∈∈∈∈ Zp*
� Choisir un entier k ∈∈∈∈ [0..p-1] au hasard� E(k,x) = (y1, y2) = (gk mod p, xek mod p)� D(y1, y2) = y2 / y1
d mod p
� Intuition: � Le message x est "masqué" dans y2 en le multipliant par ek par � La partie y1 fourni à qui connaît d, l'information nécessaire pour reconstruire x,
en "divisant" par y1d (en réalité, calculer son inverse et multiplier)
� Notes importantes� Il s'agit d'une méthode de chiffrement dite "probabiliste" car il n'existe pas de chiffrement
unique pour un même x.� Il n'est pas nécessaire de connaître k pour déchiffrer,
mais il est très important de choisir un k différent à chaque fois.
INF4420Sécurité Informatique
INF4420Sécurité Informatique
9
Variantes de El-GamalVariantes de El-Gamal
� Corps de Galois� GF(2n)
• Il s’agit d’un groupe avec 2n éléments
• Se base sur l'arithmétique modulaire avec des polynômes
• Toutes les coefficients des polynômes sont binaires, et donc toute
l'arithmétique est binaire
• Chiffrement et déchiffrement très efficaces
• Très utilisée sur des plateforme matériel
� GF(pk)• Il s’agit d’un groupe avec pk éléments
• Également basé sur l'arithmétique modulaire avec des polynômes
• Les coefficients sont modulo p, donc les opérations sont plus complexes
(moins utilisés)
INF4420Sécurité Informatique
INF4420Sécurité Informatique
10
Courbe elliptique - DéfinitionCourbe elliptique - Définition
� Courbe elliptique� Définition :
• Une courbe elliptique C est l’ensemble de points (x,y) dans un espace
vectoriel de dimension 2, obéissant une équation cubique sur ses
coordonnées.
� Exemple : • Dans ℜ2, l’ensemble C(a,b) des points P = (x,y) tel que
y2 = x3 + ax + b oùa, b ∈ ℜ sont fixes
• Dans Zp2, l’ensemble C(a,b) des points P = (x,y), x, y ∈ Zp tel
y2 = x3 + ax + b modp oùa, b ∈ ℜ sont fixes
INF4420Sécurité Informatique
INF4420Sécurité Informatique
11
Opérations sur une courbe elliptiqueOpérations sur une courbe elliptique
� Somme sur une courbe elliptique C� Interprétation géométrique
• Soit un point P, alors –P est le point sur la courbe à l’opposé de l’axe x• Soit deux points P et Q, P+Q = -R,
où R est le point sur la courbe à l’intersection de la ligne PQ• Doublage si P = Q, alors
P + Q = P + P = 2P = R, où R est l’intersection de la droite tangente à la courbe au point P
� Interprétation algébrique• Pour ℜ2 , on peut déduire des formules explicites en fonction des
coordonnées x et y des points de P et Q ainsi que des paramètres de la courbe C (c.à.d.a et b)
• Ces formules sont directement généralisables dans le cas Zp2
���� Dans les deux cas (C, +) forme un groupe, si a et b sont bien choisis
INF4420Sécurité Informatique
INF4420Sécurité Informatique
12
Exemples de courbes elliptiques sur ℜℜℜℜ2 Exemples de courbes elliptiques sur ℜℜℜℜ2
INF4420Sécurité Informatique
INF4420Sécurité Informatique
13
Cryptographie à courbe elliptique - ECCCryptographie à courbe elliptique - ECC
� Si on rebaptise la somme comme « produit » on peut alors
définir le problème de « log discret » sur C
� La cryptographie à courbe elliptique (ECC en anglais)
consiste tout simplement à utiliser l’algorithme de El-
Gamal sur le groupe (C,+) où C est une courbe elliptique
sur Zp ×××× Zp
INF4420Sécurité Informatique
INF4420Sécurité Informatique
14
Avantage des ECCAvantage des ECC
� Permet un niveau équivalent de sécurité avec des tailles de clés entre 6-10 fois plus petites
=> meilleur performance de chiffrement et déchiffrement
1.6x1028234
7.1x1018205
3.8x1010150
Cryptanalyse
(MIPS.année)
Taille de
clés (bits)
3x10202048
3x10161536
3x10141280
3x10111024
2x108768
3x104512
Cryptanalyse
(MIPS.année)
Taille de
clés (bits)
ECC RSA
INF4420Sécurité Informatique
INF4420Sécurité Informatique
15
Hachage cryptographiqueHachage cryptographique
� Objectif :� Intégrité
• S'assurer qu'un message n'a pas été modifier de façon non autorisé une fois qu'il a été terminé par son auteur légitime
� Fonctions de hachage cryptographique h� Une fonction h( ) est dite de hachage cryptographique si à partir d'un
message x elle produit un "hachage" h(x), 1. (absence de collision faible): il est très difficile de trouver un x' à partir de h(x)
tel que h(x) = h(x').2. (absence de collision forte): il est très difficile de trouver un deux message de
notre choix x et x', tel que h(x) = h(x')3. (à sens unique): il est très difficile de trouver x à partir de h(x) = h(x')
� Notes :• 2 implique 1 (trivial), 2 implique 3 (pas trivial)• En anglais, h(x) est appelé "hash", MAC (pour Message Authentication Digest),
"message digest" ou simplement "digest"• Ne pas confondre avec les fonctions de hachage "universelles", utilisées par
exemple dans la construction de compilateur, les structures de données et algorithmes aléatoires, etc.
INF4420Sécurité Informatique
INF4420Sécurité Informatique
16
Exemples de fonctions de hachage cryptographiqueExemples de fonctions de hachage cryptographique
� MD4� Conçu par Rivest (de RSA)
� Ressemble un peu à DES• Plusieurs rondes de coupage,
transposition, permutation, et
autre opérations binaires.
� Produit un hachage de
128 bits
� MD5� Version amélioré de MD4
� Produit également un
hachage de 128
� Usage très répandu
� Utilisé par le programme
linux md5sum
� SHA-1� Conçu par la NSA
� Produit un hachage de
160 bits
� Compatible avec le Digital
Signature Standard (DSS)
INF4420Sécurité Informatique
INF4420Sécurité Informatique
17
StéganographieStéganographie
INF4420Sécurité Informatique
INF4420Sécurité Informatique
18
Signature DigitaleSignature Digitale
� Objectifs� Authenticité :
• Pouvoir prouver qu'un document électronique a bel et bien composé et "signé" par
son prétendu auteur.
=> Il ne doit pas être possible pour personne de falsifier la signature d'autrui.
� Intégrité :• Pouvoir prouver que le document n'as pas été modifiédepuis qu'il a été signé par
son auteur légitime.
=> Il ne doit pas être possible pour une autre personne que l'auteur de changer le
document après sa signature sans violer la condition d'authenticité.
� (Non-répudiabilité)• Empêcher qu'un auteur légitime puisse a posteriori nier qu'il est l'auteur et
signataire d'un document qu'il a bel et bien signé
=> Il ne doit pas être possible de "répudier" une signature faite par soi-même
INF4420Sécurité Informatique
INF4420Sécurité Informatique
19
Signature digitale par chiffrement à clé publiqueSignature digitale par chiffrement à clé publique
� Signature� Pour signer un x :
1. Ajouter au message un préambule T, p.ex."Le document qui suit a été signé par José M. Fernandez, en date du …"
x' = T || x2. Utiliser la clé privéd pour produire la version signéy du document
en utilisant la clé privé et l'algorithme de déchiffrement:y = D(x',d) p.ex. y = (x')d modn avec RSA
� Vérification� Pour vérifier un document y :
1. Utiliser l'algorithme de chiffrementavec la clé publique e du présumé auteur pour obtenir x' = E(y,e)
2. Vérifier si x' est bel et bien un message "légitime" (bien formaté, a un préambule, qui a du sens, etc.). Si oui, accepter la signature.
� Notes� Pourquoi un préambule?
• Parce qu'il est possible pour un malfaiteur de falsifié une signature sur un message aléatoire ("garbage"), mais il ne lui est pas possible de le faire sur un message déterminé de son choix (p.ex. ayant un préambule raisonnable en français)
� Authenticité de la clé publique ?• Comment s'assurer que le vérificateur à la bonne clépublique e qui correspond vraiment à l'auteur ?
INF4420Sécurité Informatique
INF4420Sécurité Informatique
20
Signature digitale avec hachage cryptographiqueSignature digitale avec hachage cryptographique
� Signature� Pour signer un x :
1. Calculer le hachage h(x) du message avec une fonction de hachage cryptographique
2. Utiliser la clé privéd pour h(x) comme avant 3. Le document signé contient : (x, D(h(x),d) )
� Vérification� Pour vérifier un document (y, s)
1. Calculer le hachage h(y) de y2. Obtenir la valeur h' en chiffrant la signature savec la clé publique e,
h' = E(s,e)3. Accepter la signature si h' = h(y)
� Avantages� Plus rapide� La "signature" est indépendante du message lui-même
INF4420Sécurité Informatique
INF4420Sécurité Informatique
21
Principe de gestion de clésPrincipe de gestion de clés
� Générations de clés� Nécessité de source de bit parfaitement aléatoire� Méthode matériel vs. logiciel vs. "manuel"� "Souveraineté" et contrôle sur la génération des clés� Difficulté technique pour certains algorithmes
• RSA : p et q premier, etc.• El-Gamal : p t.q. p-1a un grand facteur, etc.
� Gestion des clés et réduction de risque� Possibilité de révocation
• Distribution au préalable• Contrôle positif (détection de perte ou vol)
� Mécanisme de protection• Contrôle d'accès• Chiffrement des clés par mot de passe ou phrase de passe
� Principe de segmentation• Clés de réseaux vs. clés point-à-point• Durée de vie limitée des clés
� Distribution de clés� Nécessite de canaux privés dédiés
• Distribution physique• Utilisation de KEK (key-encryption keys) ou équivalent
INF4420Sécurité Informatique
INF4420Sécurité Informatique
22
Échange de clés – Diffie-HellmanÉchange de clés – Diffie-Hellman
� Objectifs� Alice et Bob n'ayant pas échanger de clés auparavant désirent
établir un canal privé
� Conditions et préalable � Ils ont accès à un canal "public" (non sécurisé)� Ils peuvent s'authentifier mutuellement
� Protocole de Diffie-Hellman� Se base sur la difficulté du log discret� Permet à Alice et Bob de générer une clé dans [0..p-1]
connue de personne d'autre� Vulnérable aux attaques "man-in-the-middle" en l'absence
d'authentification
INF4420Sécurité Informatique
INF4420Sécurité Informatique
23
Gestion des clés publiques et ICPGestion des clés publiques et ICP
� Infrastructure à clé publique� Modèle décentralisé
• Web of trust
• Inventé par Phil Zimmerman, créateur de PGP
• Les réseaux sociaux
• Pas de politiques fermes d'authentification
� Modèle hiérarchique et certificats• Chaîne de confiance
• Utilise les certificats de clé publique
� Date d'expiration
� Politique d'utilisation
� Format standard X.509
• Concept d'autorité de certification
• Infrastructure matérielle et logicielle: LDAP et autres technologies
INF4420Sécurité Informatique
INF4420Sécurité Informatique
24
Standards cryptographiquesStandards cryptographiques
� PKICS (RSA)� X.509� …
INF4420Sécurité Informatique
INF4420Sécurité Informatique
25
Risques résiduels à l’utilisation de cryptographieRisques résiduels à l’utilisation de cryptographie
� Erreur de codage � Erreur d’implémentation� Erreur de design cryptographiques� Hypothèses calculatoires� Gestion de clés