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

ALGORITHMES DE CRYPTOGRAPHIE

Algorithmes de substitution ou chiffrement simple Algorithmes asymétriques ou à clef publique ... Exemples d'algorithmes de chiffrement simples.

Système El Gamal

de cryptographie asymétrique. Il est certes système de chiffrement à clé publique. ... Exemple: Un chiffrement El Gamal. On reprend la clé publique:.

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

Où trouver des candidats ? les mathématiques. Un premier exemple : la factorisation p q ? n = p.q facile k=

Cryptographie asymétrique - Lexemple de RSA

Cryptographie asymétrique. L'exemple de RSA Principe exemples

GUIDE DE SÉLECTION DALGORITHMES CRYPTOGRAPHIQUES

8 mars 2021 De même en cryptographie asymétrique

Le Chiffrement Asymétrique et la Sécurité Prouvée Sommaire

Dans le modèle de l'oracle aléatoire OAEP. • conduit à un schéma IND-CPA à partir de toute permutation à sens-unique à trappe. • et CCA ?

Primitives cryptographiques: Chiffrement Signature électronique et

Chiffrement asymétrique. Cryptosystème. Exemple. Le chiffrement de Caesar peut être représenté en utilisant les congruences sur les entiers.

Chiffrement et authentification

Chiffrement asymétrique ou “`a clef publique”. Exemple : Alice envoie un message confidentiel `a Bob. ? Alice chiffre son message avec la clef publique de

Module: Cryptographie

10 mars 2020 Système de chiffrement asymétrique. 42. 10/03/2020 09:56. Cours Cryptographie. Chapitre 5 : cryptographie asymétrique. Exemples – Rivest : ...

Reverse Engineering

Chiffrement et déchiffrement de données en se Par exemple disponible dans un ... Utilisées en cryptographie asymétrique et dans les.

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

David Pointcheval Sommaire 1 Introduction 2 Les hypothèses algorithmiques 3 Le chiffrement asymétrique 4 Les preuves de sécurité 5 La signature

[PDF] Le Chiffrement Asymétrique et la Sécurité Prouvée Sommaire - DI ENS

Le chiffrement asymétrique et la sécurité prouvée - 2 David Pointcheval Sommaire 4 Un exemple : OAEP 5 La sécurité pratique 6 Conclusion

[PDF] Cryptographie asymétrique - Zenk - Security

Principe exemples avantage / inconvénient ? Cryptographie asymétrique ? Principe illustration utilisation courante ? L'exemple de RSA

[PDF] Cours de Cryptographie - Irif

Introduction Quelques exemples de cubiques dans R2 Loi de groupe Usage cryptographique 9 Cryptographie symétrique Principe Les chiffrements à flot

[PDF] La cryptographie asymétrique avec RSA - Zeste de Savoir

12 août 2019 · Un système cryptographique est dit symétrique si toute la solidité du chiffrement repose sur un secret — on l'appelle généralement « clé » — qui

[PDF] Cryptographie à clé publique - Répertoire des cours

Problème cryptographie symétrique • Cryptographie asymétrique Par exemple disponible dans un Utilisées en cryptographie asymétrique et dans les

[PDF] Introduction au chiffrement symétrique et asymétrique - Librecours

15 mai 2020 · Exemple Le chiffrement RSA est l'un des algorithmes les plus connus lorsque l'on parle de chiffrement asymétrique

[PDF] Chap 3: Algorithmes à clé publique Hachage MAC Signature

La conception de la cryptographie asymétrique vient du besoin de résoudre deux grands problèmes : Exemple 1 : Chiffrer le message et son condensé par un

Cryptographie asymétrique - Linux Administration

RSA est par exemple 1000 fois plus lent que DES En pratique dans le cadre de la confidentialité on s'en sert pour chiffrer un nombre aléatoire qui sert

[PDF] La cryptographie - CORE

Les algorithmes asymétriques pour transmettre des clés de chiffrement et les algorithmes symétriques afin de chiffrer les données à protéger Ce travail de

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

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

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

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))

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)

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

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)

®yaisé, mais y ®xdifficile

·Fonctions àsens-unique àtrappe :

étant donnée une relation y = f(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

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] [PDF] La Cryptographie Asymétrique et les Preuves de Sécurité - DI ENS

David Pointcheval

Chargé de recherche CNRS

Département d"informatique

SommaireSommaire

1.Introduction

2.Les hypothèses algorithmiques

3.Le chiffrement asymétrique

4.Les preuves de sécurité

5.La signature

6.Conclusion

IntroductionIntroduction

1.Introduction

Les hypothèses algorithmiques

3.Le chiffrement asymétrique

4.Les preuves de sécurité

5.La signature

6.Conclusion

ConfidentialitéConfidentialité

·Archiver sur un support

Émettre

Authentification (1)Authentification (1)

Prouver de façon interactiveson identité

à un interlocuteur

Authentification (2)Authentification (2)

·Attacher, à un message,

Si cette preuve peut convaincre un tiers

Þsignature

IntégritéIntégrité

Garantir qu"un message, un document,

·L"âge artisanal : jusqu"en 1918

L"âge technique : de 1919 à 1975

L"âge paradoxal : de 1976 à nos jours

Âge artisanalÂge artisanal

Substitutions et permutations :

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 ééééPHVVDJH

Þsubstitution des caractères

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

CK(x) = x+ Kmod26

K(y) = y-Kmod26

Cryptanalyse: recherche exhaustive

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

Cp(x) = p(x)

Cryptanalyse: recherche exhaustive ?

Soit plus de 4. 1026, ou 288

Cas particuliersCas particuliers

Chiffrement par décalage:

Chiffrement affine:

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

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

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

C"est un cas particulier de Hill :

Âge techniqueÂge technique

Machines chiffrantes

Automatisation

Enigma

Âge paradoxalÂge paradoxal

·Cryptographie à clé secrète

Cryptographie à clé publique

Fonctions à sens-unique

Preuves de sécurité

Principes de Principes de KerckhoffsKerckhoffs

En 1883, Kerckhoffsénonce plusieurs

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

Algorithme de chiffrement, C

Algorithme de déchiffrement, D

Sécurité : impossible de retrouver m

à partir de csans k

Version poly-alphabétique

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

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

M E S S A G E

SécuritéSécurité