[PDF] La Cryptographie Asymétrique et les Preuves de Sécurité Sommaire

View - Download La Cryptographie Asymétrique et les Preuves de Sécurité Sommaire

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

facteurs premiers de 78 chiffres

èaeOenn)ln(ln)(ln3/23/192.1

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

Et la trappe ?Et la trappe ?

·Le produit/factorisation

est une fonction à sens-unique mais où est la trappe ?quotesdbs_dbs29.pdfusesText_35

[PDF] cryptographie exercices corrigés pdf

[PDF] les nombres en lettres pdf

[PDF] les nombres en lettres de 0 ? 1000

[PDF] ap seconde chiffres significatifs

[PDF] chiffres significatifs excel

[PDF] les chiffres significatifs cours

[PDF] chiffres significatifs sinus

[PDF] precision d une mesure et chiffres significatifs

[PDF] chiffres significatifs exacts

[PDF] chiffres significatifs exos

[PDF] exercices chiffres significatifs 2nde

[PDF] les nombres cardinaux en anglais pdf

[PDF] les nombres en anglais pdf

[PDF] les nombres et les chiffres en anglais pdf

[PDF] l'heure en anglais pdf