Introduction la
cryptographie
- Introduction la cryptographie
Introduction
[email protected]
Pierre-Alain Fouque
Universit Rennes 1 et
Institut Universitaire de France (IUF)
vendredi 12 septembre 14
vendredi 12 septembre 14
Objectifs de la cryptographie
But : Assurer la scurit des communications transmises
sur un canal public en prsence dadversaires
Adversaire passif : coute les communications
Adversaire actif : capable dcrire, modifier et effacer des
informations passant sur le canal de communication
Canal public
- Introduction la cryptographie
Services de scurit
- Introduction la cryptographie
Non-rpudiation (signature) : le signataire ne peut pas
renier sa signature
Authentification : Garantir lidentit dune entit
(identification) ou lorigine dune communication ou dun
fichier (authentification de donnes)
Mcanismes cryptographiques : signature, MAC
Intgrit : Garantir que le contenu dune communication ou
dun fichier na pas t modifi
Mcanismes cryptographiques : signature, MAC
Confidentialit : Garantir que le contenu dune
communication ou dun fichier nest pas accessible aux
tiers (GSM,Internet)
Mcanismes cryptographiques : Chiffrement
vendredi 12 septembre 14
vendredi 12 septembre 14
Repres historiques
Age artisanal: ( 1900)
Csar : chaque lettre est remplace par celle situe
trois positions plus loin dans lalphabet
Systmes de substitutions et de permutations basiques
- Introduction la cryptographie
Age technique: (1900 1970)
Substitutions et permutations utilisant des machines
mcaniques ou lectro-mcaniques: Hagelin, Enigma
(2me guerre mondiale)
vendredi 12 septembre 14
Repres historiques (2)
- Introduction la cryptographie
Comment assurer un service dauthenticit bas
sur la possession dun secret sans rvler la
moindre information sur le secret ?
Age paradoxal (depuis 30 ans):
Nouveaux mcanismes rpondant des questions a
priori hors datteinte
Comment assurer un service de confidentialit sans
avoir tabli une convention secrte commune sur un
canal qui peut tre cout par un attaquant ?
vendredi 12 septembre 14
Cryptographie et Cryptanalyse
La cryptologie se partage en deux sous-disciplines:
la cryptographie propose des mthodes pour assurer les
services prcdents
la cryptanalyse recherche des failles dans les
mcanismes proposs
- Introduction la cryptographie
Cryptographie cl secrte
vs.
Cryptographie cl publique
Gnralits
- Introduction la cryptographie
Cryptologie: Science aujourdhui mi-chemin entre les
mathmatiques et linformatique
vendredi 12 septembre 14
vendredi 12 septembre 14
Principe du chiffrement
Algorithme de chiffrement, AC
Algorithme de dchiffrement, AD
m
AC
AD
Scurit (confidentialit): impossible de
retrouver le clair m partir du chiffr c seul
- Introduction la cryptographie
Principes de Kerckhoffs
Notion de cl
- Introduction la cryptographie
seule une donne de petite taille (cl) doit
assurer la scurit
En 1883, Kerckhoffs nonce plusieurs principes
dont:
la scurit dun systme ne doit pas tre fonde
sur son caractre secret
vendredi 12 septembre 14
vendredi 12 septembre 14
Chiffrement symtrique
k
AC
Algorithme de chiffrement, AC
Algorithme de dchiffrement, AD
AD
Scurit: impossible de retrouver m partir de c
sans k
Exemples de primitives: DES, AES
- Introduction la cryptographie
- Introduction la cryptographie
Transmission dune nouvelle cl oblige les deux
parties se rencontrer
Problme de lchange de cl
Ne pas utiliser la mme cl trop longtemps
Problme de la cryptographie cl
secrte
vendredi 12 septembre 14
vendredi 12 septembre 14
AD
sk
Chiffrement asymtrique
(Diffie-Hellman / 1976)
pk
AC
Algorithme de chiffrement, AC
Algorithme de dchiffrement, AD
Scurit: impossible de retrouver m partir de c
sans sk connaissant pk
Exemples de primitives: RSA, ElGamal
- Introduction la cryptographie
Temps de calcul
- Introduction la cryptographie
On estime que lon peut effectuer 264 oprations, mais que
280 et a fortiori 2128 oprations ne sont pas atteignables en
temps raisonnable (moins de 100 ans)
290=1027=4.1011 annes 1Ghz = nombre doprations
quaurait pu effectuer un ordinateur depuis le dbut de
lunivers
Un ordinateur cadenc 1Ghz peut effectuer en 1 seconde
230oprations lmentaires
Combien doprations peut effectuer un ou plusieurs
ordinateurs en un temps fini ?
vendredi 12 septembre 14
vendredi 12 septembre 14
Niveau de scurit
280 oprations reprsente aujourdhui un niveau fort de
scurit
Suivant les applications, on prfrera 2128
Une cl est une suite alatoire de bits (0 ou 1)
Cl symtrique: la taille des cls est aujourdhui de 128 bits
Cl asymtrique: la taille des cls est aujourdhui de 1536
bits (modules RSA)
- Introduction la cryptographie
Systmes cryptographiques
- Introduction la cryptographie
Problme pratique: Plus la taille des cls augmente, plus
les algorithmes sont lents surtout en cryptographie
asymtrique
vendredi 12 septembre 14
vendredi 12 septembre 14
Primitives de la cryptographie
(Briques de base pour concevoir des
systmes cryptographiques)
- Introduction la cryptographie
One-Time Pad
et chiffrement par flot
- Introduction la cryptographie
Inconvnients:
1) Cl aussi longue que le message
2) Changer de cl pour chaque message
En pratique, Chiffrement par flot pour gnrer k partir dune
petite cl.
Scurit Parfaite: mme si ladversaire a une puissance de
calcul infinie, il ne pourra obtenir aucune information sur le
message clair
Chiffrement: c = k+m avec + le ou-exclusif
Dchiffrement: m=c+k
vendredi 12 septembre 14
vendredi 12 septembre 14
Systmes de chiffrement
Cryptographie cl secrte (conventionnelle)
Systme de chiffrement par flot (stream cipher)
Systme de chiffrement par bloc (block cipher)
Cryptographie cl publique
Systme de chiffrement par bloc
Construction de schmas de chiffrement pour garantir
la confidentialit
- Introduction la cryptographie
- Introduction la cryptographie
3DES pour viter une partie de ces problmes...
Aujourdhui, longueur de cl trop petite car on peut
effectuer 256 chiffrement DES en 2 jours
En 1977, 256 reprsente un nombre de chiffrement
trs grand
Bloc de taille 64 bits
Cl de 56 bits (256 cls diffrentes)
Algorithme de chiffrement symtrique par bloc
Data Encryption Standard (DES)
vendredi 12 septembre 14
vendredi 12 septembre 14
Advanced Encryption Standard
(AES)
Algorithme de chiffrement symtrique par bloc
Cl de 128, 192 ou 256 bits (2128, 2192, 2256 cls
diffrentes)
Bloc de taille 128 bits
En 2000, 2128 reprsente un nombre de
chiffrement gigantesque et hors datteinte
- Introduction la cryptographie
- Introduction la cryptographie
A partir de c<N, calculer x t.q. c=xe mod N, est un
problme apparemment difficile sans la connaissance
de d (la trappe dans RSA)
xed = x mod N
Si N=pq, il existe e et d tels que pour tout x<N,
Bloc de taille 890 bits
Cl de 1024 bits (niveau de scurit en 280)
Algorithme de chiffrement asymtrique par bloc
Rivest, Shamir et Adleman (RSA)
vendredi 12 septembre 14
vendredi 12 septembre 14
Fonctions de hachage
Dfinition : Produisent une empreinte du message
(hach du message) de petite taille partir dun
message m arbitrairement grand
x2
y1
y2=y3
Collisions
invitables !!
- Introduction la cryptographie
x3
x1
Exemples : SHA-1 (160 bits) ou MD5 (128 bits)
vendredi 12 septembre 14
Scurit des
fonctions de hachage
Rsistance aux collisions :
Il est difficile de trouver x et x tq H(x) = H(x)
Rsistance un deuxime antcdent :
Connaissant H(x) et x trouver xx et H(x) = H(x)
Paradoxe des anniversaires : Si D est la taille de lensemble
darrive, on trouve des collisions avec pr > 1/2 en essayant
D valeurs alatoires
- Introduction la cryptographie
Niveau de scurit : 280 pour SHA-1
vendredi 12 septembre 14
- Introduction la cryptographie
Systme de chiffrement
Garantir la confidentialit
- Introduction la cryptographie
Mcanismes cryptographiques
vendredi 12 septembre 14
vendredi 12 septembre 14
Modes opratoires
Comment chiffrer de longs messages avec un
algorithme de chiffrement par bloc ?
- Introduction la cryptographie
M1
C2
M2
C3
M3
C4
M4
Cipher Block Chaining (CBC)
IV
C1
paralllisable
- Introduction la cryptographie
Avantage : Auto-synchronisant
Dsavantage : Non
Ci = Ek (Mi Ci-1)
Mi = Dk (Ci) Ci-1
C = (IV, C1, C2, C3, , Ci)
IV
vendredi 12 septembre 14
vendredi 12 septembre 14
Schma dencapsulation (padding) pour
RSA
- Introduction la cryptographie
Comment chiffrer efficacement et de manire
sre avec RSA ?
vendredi 12 septembre 14
Paddings de RSA
RSA est dterministe : le chiffrement dun mme
message produit le mme chiffr
Utilisation dala pour masquer linformation chiffre
Si les messages chiffrs sont trop petits, il est facile
dinverser la fonction RSA
Utilisation de bits de bourrage (padding) pour toujours
chiffrer des messages suffisamment longs
Certains paddings ont t casss (PKCS#1 dans SSL)
- Introduction la cryptographie
Le nouveau padding PKCS#1 v2 est prouv sr
vendredi 12 septembre 14
Schma hybride
- Introduction la cryptographie
Comment chiffrer efficacement de longs messages
sans avoir de cl en commun ?
vendredi 12 septembre 14
Avantage / inconvnient des
systmes symtriques et asymtriques
Cl symtrique:
Avantages:
Rapidit (soft qq 10Mo/s, hard
qq 100Mo/s)
Cls trs courtes
Peu gourmand en ressources
machines
Inconvnients:
Gestion des cls (n2)
change pralable toute
comm.
Pas de non-rpudiation
- Introduction la cryptographie
Inconvnients:
Lenteur (100 fois plus lent,
dpend de la taille de du
module)
Charge machine
importante
Cl asymtrique:
Avantages:
Gestion des cls (seule la
cl secrte doit le rester),
(n cls)
Non-rpudiation
vendredi 12 septembre 14
IDbob
ID || Public Key
Annuaire
Tirer avantage de la cryptographie
symtrique et asymtrique
Kpk-bob
(C0,C1)
Ks = DRSA(Ksk-bob,C0)
M = DAES(Ks,C1)
- Introduction la cryptographie
Gnrer alatoirement Ks
C0 = ERSA(Kpk-bob,Ks)
C1 = EAES(Ks,M)
-
vendredi 12 septembre 14
3 tapes en cryptographie:
Une science rigoureuse
1. Spcifier prcisment le modle de
scurit (menace)
2. Proposer une construction
3. Prouver que casser la construction dans le
modle de scurit se ramne rsoudre
un problme difficile (rduction)
vendredi 12 septembre 14
quelle est la lettre la plus frquente en
franais ?
Chiffrement de Csar (dcalage)
Chiffrement par Substitution
(tous casss ...)
Quelques exemples historiques
Vigenre
Pouvez-vous le dchiffrer ?
Key:
ABCDABCDABCDABCDABCDABCDABCD
Plaintext: CRYPTOISSHORTFORCRYPTOGRAPHY
Ciphertext: CSASTPKVSIQUTGQUCSASTPIUAQJB
Chiffrement polyalphabtique: viter de
toujours chiffrer avec la mme lettre
vendredi 12 septembre 14
vendredi 12 septembre 14
#keys AES: 2128
#keys DES=256
Today:
#keys enigma=1016253
Rotor machines (1870-1943)
X prend ses valeurs dans V et dfinit une
distribution sur V: Pr[X=b]=a:X(a)=b P(a)
A variable alatoire est une fonction X:UV
AU un vnement et Pr[A]=xA P(x)
Prob. distr. P sur U est une fonction
P:U[0,1] t.q. xU P(x)[0,1]
U: ensemble fini (e.g. U={0,1}n)
Probabilit Discrte
vendredi 12 septembre 14
vendredi 12 septembre 14
Indpendance de
variables alatoires
Pr[A et B]=Pr[A].Pr[B]
Def: A et B deux vnements sont indpendant si
Deux variables alatoires X,Y valeurs dans V sont
indpendante si a,bV, Pr[X=a et Y=b]=Pr[X=a].Pr[Y=b]
Exemple: U={0,1}2={00,01,10,11} et rRU, dfinissons X=lsb(r)
et Y=msb(r) Pr[X=0 and Y=0]= ?
Conclusion
- Introduction la cryptographie
lauthentification de document et de personne
lintgrit, et
la confidentialit,
Les services de scurit garantis sont :
Elle permet de rsoudre certains problmes d
la forme lectronique des documents
La cryptographie est la science du secret
vendredi 12 septembre 14
vendredi 12 septembre 14
Bibliographie
Livres:
La Guerre des Codes (David Kahn)
Histoire des Codes Secrets (Simon Singh)
La Science du Secret (Jacques Stern)
Cryptographie Applique (Bruce Schneier)
Cryptographie: Thorie et Pratique (Stinson)
- Introduction la cryptographie
Pointeurs internet
Handbook of Applied Cryptography
www.cacr.math.uwaterloo.ca/hac
vendredi 12 septembre 14
