[PDF] Introduction à la cryptographie (cours 4): Chiffrement par bloc (AES)

View - Download Introduction à la cryptographie (cours 4): Chiffrement par bloc (AES)

Previous PDF

Next PDF

Introduction à la cryptographie (cours 4):

Chiffrement par bloc (AES)

Université Paris 13 Villetaneuse

01/02/2016

HoudaFERRADI

1 Rappel : chiffrement symétrique ou à clé secrète

AliceBob

E (Fonction de chiffrement) et D (Fonction de déchiffrement): Fonctions inversibles et efficaces

K: Clé secrète ou symétrique

C: Le message chiffré

m, k, et c sont de taille déterminée! EDmC KC Cm Eve 2

Rappel : chiffrement symétrique

Définition : Un algorithme de chiffrement symétrique transforme un message en clair M avec une clé secrète K. Le résultat est un chiffré C 3

Deux grandes catégories

Chiffrement par blocs

ƒM est traité par blocs de données

(ex: 64 bits ou 128 bits) ([HPSOH G·MOJRULPOPHV DES, AES,

HG($ 5F6 %I2J)H6+ "

Chiffrement par flots

ƒM est traité bit par bit (cours

précédent) ([HPSOH G·MOJRULPOPHV: RC4,

Bluetooth E0/1, GSM A5/1,

4

Introduction: Chiffrement par blocs

ƒDans un système de chiffrement par blocs, chaque texte clair est découpé en blocs de même longueuret chiffré bloc par bloc. ƒLa taille de bloc (n = 64 ou 128 bits)Les modes opératoires permettent ƒLa clésoit être suffisamment grande (k>128): Pour un bon algorithme, la meilleure attaque doit coûter -௞RSpUMPLRQV OM PHŃOQLTXH XPLOLVpH HVP O·MPPMTXH H[OMXVPLYHB

Exemple:

AES: n= 128 bits , k=128, 192, 256 bits

5

2 principes fondamentaux pour AES

C. Shannon avait montré que la combinaison de confusionet diffusion SHUPHPPMLP G·RNPHQLU XQH VpŃXULPp ŃRQYHQMNOH Confusion== Masquer toute relation linéaire entre le chiffréet le message en clair. Diffusion FMŃOHU OM UHGRQGMQŃH HQ UpSMUPLVVMQP O·LQIOXHQŃH G·XQ NLP GH ŃOp sur tout le chiffré. 6

Fonction aléatoire toujours notre objectif

Un bon algorithme à clé secrète doit transformer le message clair en un chiffré qui ressemble autant que possible à une suite aléatoire, pour limiter au PLQLPXP OHV ULVTXHV G·XQH MPPMTXH SMU analyse statistique du chiffré, de ses redondances. Exemple dans le chiffrement de flux : Le "masque jetable», clé tirée uniformémentG·XQ HVSMŃH GH ŃOpV .B 7

Construction: Fonction aléatoire

Nouvelle définition dans le chiffrement par blocs Fonction aléatoire

Permutation aléatoire

Telle que une fonction de chiffrement E(k,m) on a: ƒIl existe une façon efficaceG·pYMOXHU (k,m) ƒHO H[LVPH XQ MOJRULPOPH G·inversionefficace D(k,c) => E(k,m) doit être une fonction bijective 8 ([HPSOH G·XQH IRQŃPLRQ NLÓHŃPLYH E (m, k) est une fonction de chiffrement bijective

E (m,K)

9

AES (Advanced EncryptionStandard)

10 $SSHO G·RIIUH HQ 1EE7 ƒAvant 1997: DES (schéma de Feistel YXOQpUMNOH j O·MPPMTXH H[OMXVPLYHA

1997: NIST publie une demande de propositions.

1998: Quinze propositions des universités comme: RC6, IDEA

1999: NIST choisit 5 finalistes dont: RC6 (schéma de Feistelgénéralisé) et

IDEA (schéma de Lai-Massey)

2000: NIST choisit Rijndaelpour AES (conçu par Vincent Rijmenet Joan

Daemen).

11

GpVLJQMPLRQ G·$(6 HQ 2000

ƒAES est un algorithme de chiffrement itératif, mais contrairement à 9 autres ŃMQGLGMPV ŃH Q·HVP SMV XQ ŃOLIIUHPHQP GH Feistel(définit dans le cours précédent)

ƒTaille de bloc est de 128 bits

ƒChiffrement à 128, 128ou 256 bits de clés

ƒBasé sur la théorie de Galois

12

GLIIpUHQPHV ŃRXŃOHV G·$(6

A chaque tour, le chiffré Y(i)

produit par le tour précédent subit une substitutionnon-linéairequi assure la confusionpuis une permutation linéairequi assure la diffusion, puis la clé du tour est ajoutée bit à bit pour donner

Y(i+1). Le nombre de tours est 10

pour une clé de 128 bits et de 14 pour une clé de 256 bits.

Couche de permutation

Couche de substitution

Sortie du tour Y(i+1)

Entrée du tour Y(i)

Fonction

de tour 13

Plus de précisions

Mélange par colonne

Substitution par octet

Sortie du tour 128

bits

Décalage par ligne

Entrée du tour 128

bits 14

Structure générale

15

1ère étape

1ère étape: le stockage des données dans un " carré » de 4 x 4 = 16 cases

ensuite dans une matrice 4 x 4 appelée ܣ Chaque case contient 1 octet 8 [ 16 128 NLPV G·pPMP LQPHUQH 16

2e étape: AddRoundKey

2e étape: XOR la matrice avec la sous-clé

17

3eétape: SubBytes

Pour ͗ 1 ч i ч 16, Yi с S(yi)

S-Box: transformationnon-lineaire(confusion).

18

3eétape: SubBytes

S-Box est une fonction fixe et bijective de 8 bits vers 8 bits Définie comme un tableau à -଼= 256 entrées

Nécessite donc 256 octets de mémoire

‡ %MVpH VXU XQH RSpUMPLRQ MOJpNULTXH TXL V·pŃULP VRXV IRUPH

L et Cévitent les points fixes et particuliers

RZ O·LQYHUVH HVP SULV GMQV *)-଼)

19

S-Box pour AES

20

4eétape: ShiftRows

GpŃMOMJH ŃLUŃXOMLUH YHUV OM JMXŃOH GH L ŃMVHV SRXU OM OLJQH QXPpUR L 0 " L " 3

4eétape: Consiste à décaler les lignes en rotation: transformation

linéaire (diffusion). 21

5eétape: MixColumns

MixColumn() est appliquée à chaque colonne

5eétape: 0pOMQJHU OHV ŃRORQQHV VMXI OH GHUQLHU PRXU G·$(6 10eou 14e):

Permet la transformation linéaire (diffusion)

22

5eétape: MixColumns

MixColumm

Opérations linéaires dans GF(-଼)

Pour chaque colonne on applique une multiplication par une matrice circulante: 23

Rappel de Notions G·MOJqNUH

Groupes

Définition: un ensemble G muni G·XQHloiinterne, notée* par exemple, estappeléun groupessicette

loivérifieles trois axiomessuivants, pour tout x, y, z dansG: x*(y*z) = (x*y)*z Il existee telque x*e = e*x = x (e estun élémentneutre)

Pour tout x de G, ilexiste[· GH * telTXH [

[ H H[LVPHQŃH G·XQ élémentsymétrique[·B

Un telgroupeestnoté(G,*) ouG.

Un groupeG estditfinisicard(G) estfini. Le nombreG·pOpPHQPVG·XQ groupeestappeléordredu groupe.

Définition: un sous-HQVHPNOH + G·XQ groupeG estun sous-groupeV·LOestlui-mêmeun groupepour les

opérationsde G. Si H estun sous-groupestrictementinclusdansG, alorsH estditêtreun sous- groupepropre.

Théorèmede Lagrange : Si G estun groupefiniet H estun sous-groupede G, alorscard(H) divisecard(G).

Par conséquent, siaappartientà G, alorsord(a)divisecard(G).

Anneaux

Définition: un anneau(R,+,x) estun ensemble R munisde deuxopérationsbinairesnotées+ et * tellesque :

(R,+) estun groupeabélien(dontO·LGHQPLPpestnotée0)

La loi* estassociative sur R

Il existeun élémentde R, noté1, telque pour tout a dansR, a*1=1*a=a

La loi* estdistributive par rapport à la loi+ i.e. a*(b+c) = (a*b)+(a*c) et (b+c)*a = (b*a)+(c*a).

I·MQQHMXestcommutatifsila loiest* estcommutative sur R. Corps Définition: un corpsestun anneaudanslequeltousles élémentsnon-nulsontun inverse pour la multiplication.

Anneauxdes polynômes

Définition: siR estun anneaucommutatif, alorsun polynômeenx sur R estuneexpression de la forme:

Définition: siR estun anneaucommutatif, O·MQQHMXdes polynômesR[x] estO·MQQHMXformépar O·HQVHPNOH

des polynômesenx à coefficients dansR.

Définition: soitK un corps et soitf(x) un polynômedansK[x] de degréau moins1. f(x) estirréductible

dansK[x] V·LOne peutpas se décomposerenle produitde deuxpolynômesde K[x] dontles degréssont

supérieursouégauxà 1.

Définition: ܭ

estinférieurouégalà n=deg(f(x)). Les opérationsG·MGGLPLRQet de multiplication sonteffectuéesmodulo f(x).

Note : ܭ

Espacesvectoriels

Un espacevectorielE sur un corps K estun groupeabélien(E,+) munisG·XQHloi multiplicative noté. telleque a,bdansK et tout couple (u,v) dansEE, on a: Les élémentsde E sontappelésvecteurset les élémentsde K sontappelésscalaires. Définition: unecombinaisonlinéaireG·pOpPHQPVG·XQ VRXV-ensemble ܵ vectorielsur un corps K estuneexpression de la forme

I·espacenoté engendrépar S estO·HQVHPNOHde toutesles combinaisonslinéairesdes élémentsde S.

Les élémentsde S sontditsêtrelinéairementdépendantsV·LOexisteun ensemble de scalaires

telsque Dansle cascontraire les élémentsde S sontêtrelinéairementindépendants. Unefamillede vecteurslinéairementindépendantsengendrantun espaceV estditêtreunebase de V.

La dimensionG·XQ espacevectorielE, notédim E, estle nombrede vecteursque contientunebase de E.

Corps finis

Existence et unicité: siK estun corps fini, alorsK contientélémentsoùp estun nombre premier et n estun entierstrictementpositif. Pour tout nombrepremier p et tout entiern, ilexiste un unique corps fini(à isomorphismeprès) de cardinal . Ce corps estnoté.

GF(-଼): construction

Cet objet mathématique est utilisé pour définir la boîte S dans ShiftColumnset la matrice TX·RQ XPLOLVH SRXU PXOPLSOLHU ŃOMTXH ŃRORQQH GMQV O·pPMSH MixColumn():

Un corps est un anneau dans lequel tous les éléments non-nuls ont un inverse pour la multiplication.

Exemple:

Tous les polynômes de degré 1 sont irréductibles. Par conséquent il y a une infinité de polynômes irréductibles.

30

GF(-଼): construction

I·HQVHPNOH GH ŃHV SRO\Q{PHV VRQP GMQV GF(-଼) = ܨ GF(-଼) est un corps fini avec -ͷ͸éléments, aussi appelé corps de Galois dont les coefficients sont dans ܨ 31

GF(-଼) : représentation

32

Dernière étape : AddRoundKey

33

Synthèse

AES est 2,7 fois plus rapide que 3 DES ( gain de performance) Le nombre de tours dépends de la taille de blocs et de la clé La recherche exhaustive reste la meilleure attaque contre AES (impossible avec 128 bits)

NSA a annoncé que AES est le meilleur standard pour protéger des informations les plus sensibles avec des clés de 256 bits (14 tours)

AES a été conçu pour résister à la cryptanalyse linéaireet différentielle(cours suivant)

K= 128K= 192K=256

Bloc=128101214

Bloc=192121214

Bloc=256141414

34

En pratique

Algorithmes utilisés

DES dans les anciens produits

AES dans les nouveaux produits

Autres algorithmes utilisés ponctuellement

IDEA (PGP)

BlowFish

35

En pratique

Algorithmes utilisés

DES dans les anciens produits

AES dans les nouveaux produits

Autres algorithmes utilisés ponctuellement

IDEA (PGP)

BlowFish

36
quotesdbs_dbs23.pdfusesText_29