[PDF] [PDF] La Cryptographie Asymétrique et les Preuves de Sécurité - DI ENS

View - Download [PDF] La Cryptographie Asymétrique et les Preuves de Sécurité - DI ENS

Previous PDF

Next PDF

David Pointcheval

Chargé de recherche CNRS

Département d"informatique

École normale supérieureLa Cryptographie Asymétrique et les Preuves de Sécurité La cryptographie asymétriqueet les preuves de sécurité-2David Pointcheval

SommaireSommaire

1.Introduction

2.Les hypothèses algorithmiques

3.Le chiffrement asymétrique

4.Les preuves de sécurité

5.La signature

6.Conclusion

La cryptographie asymétriqueet les preuves de sécurité-3David Pointcheval

IntroductionIntroduction

1.Introduction

2.

Les hypothèses algorithmiques

3.Le chiffrement asymétrique

4.Les preuves de sécurité

5.La signature

6.Conclusion

La cryptographie asymétriqueet les preuves de sécurité-4David Pointcheval

ConfidentialitéConfidentialité

·Archiver sur un support

Émettre

sur un canal de façon qu"un tiers ne puisse en prendre connaissance La cryptographie asymétriqueet les preuves de sécurité-5David Pointcheval

Authentification (1)Authentification (1)

Prouver de façon interactiveson identité

à un interlocuteur

La cryptographie asymétriqueet les preuves de sécurité-6David Pointcheval

Authentification (2)Authentification (2)

·Attacher, à un message,

une preuve non-interactive de son origine

Si cette preuve peut convaincre un tiers

Þsignature

La cryptographie asymétriqueet les preuves de sécurité-7David Pointcheval

IntégritéIntégrité

Garantir qu"un message, un document,

un fichier, n"a pas subi de modification aussi bien accidentelle qu"intentionnelle) La cryptographie asymétriqueet les preuves de sécurité-8David Pointcheval Les 3 âges de la Les 3 âges de la cryptologiecryptologie

·L"âge artisanal : jusqu"en 1918

L"âge technique : de 1919 à 1975

L"âge paradoxal : de 1976 à nos jours

La cryptographie asymétriqueet les preuves de sécurité-9David Pointcheval

Âge artisanalÂge artisanal

Substitutions et permutations :

cadrans cylindres La cryptographie asymétriqueet les preuves de sécurité-10David Pointcheval

Algorithmes secretsAlgorithmes secrets

ScytaleLacédémonienne:

Enrouler un ruban autour d"un bâton,

écrire puis dérouler

Þpermutation des caractères

Chiffrement de César:

Décalage constant des lettres du

message (à l"origine +3)

MESSAGE ééééPHVVDJH

Þsubstitution des caractères

La cryptographie asymétriqueet les preuves de sécurité-11David Pointcheval Chiffrement par décalageChiffrement par décalage

Chaque lettre (codée dans [0,25])

subit un décalage constant K

CK(x) = x+ Kmod26

D

K(y) = y-Kmod26

Cryptanalyse: recherche exhaustive

elle consiste à essayer toutes les clés Kpossibles (soit seulement 26) La cryptographie asymétriqueet les preuves de sécurité-12David Pointcheval Chiffrement par substitutionChiffrement par substitution

Chaque lettre (codée dans [0,25])

est substituée par une autre

Cp(x) = p(x)

D p(y) = p-1(y) où pest une permutation de [0,25]

Cryptanalyse: recherche exhaustive ?

Sur un alphabet de 26 lettres : 26! Possibilités

Soit plus de 4. 1026, ou 288

La cryptographie asymétriqueet les preuves de sécurité-13David Pointcheval

Cas particuliersCas particuliers

Chiffrement par décalage:

p (x) = x+ Kmod26

Chiffrement affine:

p (x) = a x+ bmod26 La cryptographie asymétriqueet les preuves de sécurité-14David Pointcheval Chiffrement par permutationChiffrement par permutation

Cette fois-ci on garde les mêmes lettres,

mais on change l"ordre (ex: scytale)

CK(x1,...,xn) = (xp(1) , xp(2), ..., xp(n))

D

K(y1,...,yn) = (yp-1(1) , yp-1(2), ..., yp-1(n))

où pest une permutation de [1,n]

C"est un cas particulier de Hill :

matrice de permutation K: Y = KX La cryptographie asymétriqueet les preuves de sécurité-15David Pointcheval

Âge techniqueÂge technique

Machines chiffrantes

Automatisation

des permutations et substitutions

Enigma

La cryptographie asymétriqueet les preuves de sécurité-16David Pointcheval

Âge paradoxalÂge paradoxal

·Cryptographie à clé secrète

Cryptographie à clé publique

Fonctions à sens-unique

(éventuellement à trappe)

Preuves de sécurité

La cryptographie asymétriqueet les preuves de sécurité-17David Pointcheval

Principes de Principes de KerckhoffsKerckhoffs

En 1883, Kerckhoffsénonce plusieurs

principes dont : "la sécurité d"un système ne doit pas être fondée sur son caractère secret»

En effet, un jour ou l"autre il y a des fuites au

sujet du système, ainsi "seule une donnée de petite taille (clé) doit assurer la sécurité» La cryptographie asymétriqueet les preuves de sécurité-18David Pointcheval Chiffrement symétriqueChiffrement symétrique kk CDmcm

Algorithme de chiffrement, C

Algorithme de déchiffrement, D

Sécurité : impossible de retrouver m

à partir de csans k

La cryptographie asymétriqueet les preuves de sécurité-19David Pointcheval Chiffrement de Chiffrement de VigenèreVigenère

Version poly-alphabétique

du chiffrement par décalage : décalage des lettres en fonction de leur position

CK(x1,...,xn) = (x1+ K1, ..., xn+ Kn)

D

K(y1,...,yn) = (y1-K1, ..., yn-Kn)

où K= (K1, ..., Kn)

M E S S A G E

+C L E C L E C = O P W U L K G La cryptographie asymétriqueet les preuves de sécurité-20David Pointcheval

SécuritéSécurité

®Recherche exhaustive

vite hors de portéeRecherche exhaustive : si la clé est de longueur n, il y a 26 npossibilités

70472321521025Þ=Þ=Þ=nnn

La cryptographie asymétriqueet les preuves de sécurité-21David Pointcheval

Analyses statistiquesAnalyses statistiques

Probabilité d"occurrence de chaque

lettre/digramme/trigramme on casse aisément un chiffrement par substitution

Entropie : conservée par substitution

ou permutation on retrouve la longueur de la clé

Attaque de Kasiski :

elle casse Vigenère en temps linéaire ! La cryptographie asymétriqueet les preuves de sécurité-22David Pointcheval Sécurité parfaite ?Sécurité parfaite ?

Chiffrement de Vernam:

Combiner le message à chiffrer

avec une suite de bits aléatoires kmcÅ=

Sécurité inconditionnelle

à condition que la "clé» ksoit aussi

longue que le message m(Shannon) kcmÅ= La cryptographie asymétriqueet les preuves de sécurité-23David Pointcheval

En pratique ...?En pratique ...?

·César/Vigenère/... pas sûrs

Vernampas pratique

Sécurité inconditionnelle pas pratique :

mais Shannon a aussi montré que la combinaison de substitutions et de permutations apportait une sécurité convenable systèmes produits La cryptographie asymétriqueet les preuves de sécurité-24David Pointcheval Chiffrement symétriqueChiffrement symétrique

·clé unique k

-chiffrement -déchiffrement

·conception heuristique :

-permutations (diffusion) -substitutions (confusion)

·orienté implémentation matérielle

débit rapide La cryptographie asymétriqueet les preuves de sécurité-25David Pointcheval Chiffrement symétriqueChiffrement symétrique

Par blocs (block cipher):

décompose le message en blocs -DES(IBM-NBS) snormal -clé de 56 bits, blocs de 64 bits srenforcé (triple-DES) -clé de 112/168 bits

IDEA(Massey-Lai)

clé de 128 bits, blocs de 64 bits

AES(RIJNDAEL : Daemen-Rijmen)

clés de 128, 196 ou 256 bits, blocs de 128 bits La cryptographie asymétriqueet les preuves de sécurité-26David Pointcheval Chiffrement symétriqueChiffrement symétrique

Par flot (stream cipher):

chiffre un flux de données -Vernam(générateur pseudo-aléatoire) :

RC4(Rivest)

chiffre octet par octet iiikmc cc cmmmkkG(k) ??212121 La cryptographie asymétriqueet les preuves de sécurité-27David Pointcheval Chiffrement asymétriqueChiffrement asymétrique kdkc CDmcm

Algorithme de chiffrement, C

Algorithme de déchiffrement, D

Sécurité : impossible de retrouver m

à partir de csans k

d La cryptographie asymétriqueet les preuves de sécurité-28David Pointcheval Chiffrement asymétriqueChiffrement asymétrique

·Lois de Kerckhoffspoussées à bout

Deux clés :

-chiffrement kc®publique -déchiffrement kd®privée

·Fondements mathématiques :

-fonctions à sens-uniques -fonctions à trappe

·Analyse de sécurité

sécuritécalculatoire La cryptographie asymétriqueet les preuves de sécurité-29David Pointcheval Chiffrement asymétriqueChiffrement asymétrique -RSA(Rivest-Shamir-Adleman1978) racines modulaires (factorisation) -Merkle-Hellman(1978) problème du "sac à dos» (tous cassés...) -Mc Eliece(1978) codes correcteurs d"erreurs -El Gamal(1985) logarithme discret -HFE (Patarin 1996) polynômes multivariables La cryptographie asymétriqueet les preuves de sécurité-30David Pointcheval

AuthentificationAuthentification

·Algorithme d"authentification, A

Algorithme de vérification, V

kvka AV ms 0/1m

Sécurité: impossible de produire

un svalide sans k a La cryptographie asymétriqueet les preuves de sécurité-31David Pointcheval Authentification "Authentification "artisanaleartisanale»»

En raison du caractère secret des

procédés de chiffrement -clé secrète commune -voire algorithme secret commun

®Identité de l"expéditeur garantie

Mais l"expéditeur et le destinataire

connaissent la convention secrète

Pas de non-répudiation

La cryptographie asymétriqueet les preuves de sécurité-32David Pointcheval

Signature numériqueSignature numérique

·Deux clés :

-signature ka®privée -vérification kv®publique

·Fondements mathématiques :

-fonctions à sens-uniques

·Analyse de sécurité

sécuritécalculatoire La cryptographie asymétriqueet les preuves de sécurité-33David Pointcheval

Signature numériqueSignature numérique

-RSA(Rivest-Shamir-Adleman1978)

Extraction de Racines Modulaires

-El Gamal(1985)

Logarithme Discret

Variantes : Schnorr(1989), DSA (1994)

-Combinatoires (Problèmes NP-complets) :

PKP (Shamir 1989), SD (Stern 1993),

CLE (Stern 1994), PPP (Pointcheval1995)

La cryptographie asymétriqueet les preuves de sécurité-34David Pointcheval Identification : contrôle d"accèsIdentification : contrôle d"accès

·Authentification interactive :

Alice (client) veut prouver

à Bob (serveur) son identité

Je m"appelle

Alice

Prouve-le moi !

La cryptographie asymétriqueet les preuves de sécurité-35David Pointcheval

Preuves Preuves ZeroZero--KnowledgeKnowledge

Protocoles "zero-knowledge» :

-preuve de connaissance d"un secret sans transfert d"information sur ce secret, seule la conviction de connaissance La cryptographie asymétriqueet les preuves de sécurité-36David Pointcheval

IntégritéIntégrité

La signature numérique garantit l"intégrité du message reçu

N"y aurait-il pas plus simple

pour garantir l"intégrité de son propre disque dur ? -Conserver une copie en lieu sûr !... -Conserver un "condensé» en lieu sûr fonctions de hachage cryptographiques La cryptographie asymétriqueet les preuves de sécurité-37David Pointcheval

Fonctions de hachageFonctions de hachage

Créer une empreinte/un condensé h = H(x)

de petite taille (moins de 256 bits ?) garantissant qu"une altération -accidentelle, mais également intentionnelle -de la part d"un tiers, ou même du créateur du disque modifiera la valeur du condensé en résultant (détection de la différence) La cryptographie asymétriqueet les preuves de sécurité-38David Pointcheval

ExemplesExemples

·MD-2, MD-4 (Rivest, 1990, 128 bits)

MD-5 (Rivest, 1991, 128 bits) :

très utilisée dans le monde UNIX

SHA (NIST, 1992, 160 bits) :

"Standard Américain» en 1993

Remplacé, "pour faiblesse technique»

SHA-1 (NIST, 1994, 160 bits)

SHA-256/384/512 (NIST, 2000)

condensés sur 256, 384 ou 512 bits La cryptographie asymétriqueet les preuves de sécurité-39David Pointcheval Les hypothèses algorithmiquesLes hypothèses algorithmiques

1.Introduction

2.Les hypothèses algorithmiques

3.

Le chiffrement asymétrique

4.Les preuves de sécurité

5.La signature

6.Conclusion

La cryptographie asymétriqueet les preuves de sécurité-40David Pointcheval Chiffrement asymétriqueChiffrement asymétrique CDmcm

Algorithme de chiffrement, C

m ®c: transformation aisée

Algorithme de déchiffrement, D

c ®m : transformation difficile

à moins de connaître une trappe

La cryptographie asymétriqueet les preuves de sécurité-41David Pointcheval

Outils nécessairesOutils nécessaires

·Fonctions à sens-unique :

étant donnée une relation y = f(x)

x

®yaisé, mais y ®xdifficile

·Fonctions àsens-unique àtrappe :

étant donnée une relation y = f(x)

x

®yaisé,

y ®xdifficile y

®xaiséavec z ("trappe»)

La cryptographie asymétriqueet les preuves de sécurité-42David Pointcheval Où trouver des candidats ?Où trouver des candidats ? les mathématiquesles mathématiques

Un premier exemple : la factorisation

p, q

®n = p.qfacilek=|n|=log2(n)

en O(k2)opérations élémentaires en revanche n = p.q

®p, qdifficile

en

Record actuel : nombre nproduit de deux

quotesdbs_dbs32.pdfusesText_38

[PDF] carte badgeo etudiant

[PDF] ejemplos del verbo ser

[PDF] ejercicios ser estar español para extranjeros

[PDF] ejercicios verbo ser y estar para imprimir

[PDF] arts plastiques 3ème cube

[PDF] vecteur dans l espace terminale s

[PDF] sujets bac géométrie dans l espace

[PDF] géométrie dans lespace 3ème exercices corrigés pdf

[PDF] structure cubique centrée

[PDF] compacité cubique simple

[PDF] section rhénanes alcools

[PDF] cubisme def

[PDF] cubisme caractéristiques pdf

[PDF] menu de la renaissance

[PDF] costumes paysans 17ème siècle