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

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

David PointchevalLe Chiffrement Asymétrique

et la Sécurité Prouvée

Habilitation à Diriger des Recherches

Université Paris VII -Denis Diderot

École normale supérieure

Le chiffrement asymétriqueet la sécurité prouvée -2David Pointcheval

SommaireSommaire

1.Le chiffrement asymétrique

2.Les hypothèses algorithmiques

3.Les preuves de sécurité

4.Un exemple : OAEP

5.La sécurité pratique

6.Conclusion

Le chiffrement asymétriqueet la sécurité prouvée -3David Pointcheval

1.Le chiffrement asymétrique

2.Les hypothèses algorithmiques

3.Les preuves de sécurité

4.Un exemple : OAEP

5.La sécurité pratique

6.Conclusion

SommaireSommaire

Le chiffrement asymétriqueet la sécurité prouvée -4David Pointcheval

Deux clés... Deux clés...

Cryptographieasymétrique

Diffie-Hellman1976

-une clé privée (de déchiffrement kd) qui lui permet de déchiffrer

AliceBobconfidentialité

authenticité

Chiffrement asymétrique :

Bob possède un couple de "clés»

-une clé publique (de chiffrement ke) qui permet à qui le souhaite de lui chiffrer un message

Þconnue de tous

(dont Alice)

Þconnue de Bob

uniquement Le chiffrement asymétriqueet la sécurité prouvée -5David Pointcheval Chiffrement / déchiffrementChiffrement / déchiffrementdécryptementdécryptement

Grâce à la clé publique de Bob,

Alice peut fermer un coffre,

avec le message à l"intérieur (chiffrer le message) sauf Bob, avecsa clé privée(il peut déchiffrer) Alice envoie à Bob ce coffreque nul ne peut ouvrir (impossible de décrypter) Le chiffrement asymétriqueet la sécurité prouvée -6David Pointcheval Un schéma de chiffrementUn schéma de chiffrement

3 algorithmes :

-génération des clés -chiffrement -déchiffrement Confidentialité = impossibilité de retrouver m

à partir de csans la clé privée k

d (ke,kd)w kdke rcmm Le chiffrement asymétriqueet la sécurité prouvée -7David Pointcheval Confidentialité Confidentialité calculatoirecalculatoire

Le chiffré est calculé par c= ke(m;r)

·la clé keest publique

un unique msatisfait cette relation (avec éventuellement plusieurs r) hypothèses algorithmiques

Au moins la recherche exhaustive sur met r

permet de retrouver m, peut-être mieux !

Þconfidentialitéinconditionnelle impossible

Le chiffrement asymétriqueet la sécurité prouvée -8David Pointcheval

1.Le chiffrement asymétrique

Les hypothèses algorithmiques

3.Les preuves de sécurité

4.Un exemple : OAEP

5.La sécurité pratique

6.Conclusion

SommaireSommaire

Le chiffrement asymétriqueet la sécurité prouvée -9David Pointcheval Factorisation entière et RSAFactorisation entière et RSA

·Multiplication/Factorisation :

-p, q ?n = p.qfacile (quadratique) -n = p.q ?p, qdifficile (super-polynomial)

Fonction

à sens-unique

·Fonction RSA, de ndans n(avec n=pq)

pour un exposant efixéRivest-Shamir-Adleman1978 -x ?xemodnfacile (cubique) -y=xemodn ?xdifficile (sans pni q) x = ydmodnoù d = e-1modj(n)trappe Le chiffrement asymétriqueet la sécurité prouvée -10David Pointcheval chiffrement Factorisation entière et RSAFactorisation entière et RSA

·Multiplication/Factorisation :

-p, q?n = p.qfacile (quadratique) -n = p.q ?p, qdifficile (super-polynomial)

Fonction

à sens-unique

trappe

·Fonction RSA, de ndans n(avec n=pq)

pour un exposant efixéRivest-Shamir-Adleman1978 -x ?xemodnfacile (cubique) -y=xemodn ?xdifficile (sans pni q) x = ydmodnoù d = e-1modj(n) Le chiffrement asymétriqueet la sécurité prouvée -11David Pointcheval chiffrement décryptement difficile Factorisation entière et RSAFactorisation entière et RSA

·Multiplication/Factorisation :

-p, q?n = p.qfacile (quadratique) -n = p.q ?p, qdifficile (super-polynomial)

Fonction

à sens-unique

trappe

·Fonction RSA, de ndans n(avec n=pq)

pour un exposant efixéRivest-Shamir-Adleman1978 -x ?xemodnfacile (cubique) -y=xemodn ?xdifficile (sans pni q) x = ydmodnoù d = e-1modj(n) Le chiffrement asymétriqueet la sécurité prouvée -12David Pointcheval chiffrement décryptement difficile Factorisation entière et RSAFactorisation entière et RSA

·Multiplication/Factorisation :

-p, q?n = p.qfacile (quadratique) -n = p.q ?p, qdifficile (super-polynomial)

Fonction

à sens-unique

déchiffrement trappe

·Fonction RSA, de ndans n(avec n=pq)

pour un exposant efixéRivest-Shamir-Adleman1978 -x ?xemodnfacile (cubique) -y=xemodn ?xdifficile (sans pni q) x = ydmodnoù d = e-1modj(n) clé Le chiffrement asymétriqueet la sécurité prouvée -13David Pointcheval Variantes et autres problèmesVariantes et autres problèmes

·RSA

-Flexible : (y, n) ?(x, e), y = xemodn -Relié : (Dependent-RSA)(P EC-1999) pour net efixés,y=xemodn ?(x+1)emodn

·Logarithme discret : g, y=gxlogg(y) = x

Diffie-Hellman

-Calcul : (A=ga,B=gb)?DH(A,B)=gab ?-Décision : (A=ga,B=gb,C=gc) ?C=DH(A,B) -Gap : Gap-Problems (OP PKC-2001)

Résoudre C-DH à l"aide d"un oracle D-DH

Le chiffrement asymétriqueet la sécurité prouvée -14David Pointcheval

Record

Août 1999

20115681921491044096111662048

80351024

5813512Opérations(en log2)Mips-Year(en log2)Module(en bits)

Estimations de complexitéEstimations de complexité Estimations pour la factorisation Lenstra-Verheul2000

Convenables pour RSA

Bornes inférieures pour LD dans*

Repère

Le chiffrement asymétriqueet la sécurité prouvée -15David Pointcheval

1.Le chiffrement asymétrique

2.Les hypothèses algorithmiques

Les preuves de sécurité

4.Un exemple : OAEP

5.La sécurité pratique

6.Conclusion

SommaireSommaire

Le chiffrement asymétriqueet la sécurité prouvée -16David Pointcheval Hypothèse algorithmiqueHypothèse algorithmiquenécessairenécessaire

·n=pq: module public

e: exposant public

·d=e-1modj(n): privé

Chiffrement RSA

(m)= memodn (c)= cdmodn

Si le problème RSA est facile,

clairement, la confidentialité n"est pas garantie : n"importe qui peut retrouver mà partir de c Le chiffrement asymétriqueet la sécurité prouvée -17David Pointcheval Hypothèse algorithmiqueHypothèse algorithmiquesuffisante ?suffisante ?

Les preuves de sécurité garantissent

que l"hypothèse est suffisante pour la confidentialité : si un adversaire parvient

à violer la confidentialité

on peut mettre en défaut l"hypothèse

Þpreuveparréduction

Le chiffrement asymétriqueet la sécurité prouvée -18David Pointcheval

Preuve par réductionPreuve par réduction

Réduction d"un problème à une attaqueAtk:

Soit un attaquant

qui parvient à son but

Instance

de insolubleÞschéma incassable

Solution

de alorspeut être utilisé pour résoudre Le chiffrement asymétriqueet la sécurité prouvée -19David Pointcheval Protocole prouvé sûrProtocole prouvé sûr

Pour prouver la sécurité d"un protocole

cryptographique, on doit préciser les hypothèses algorithmiques préciser les notions de sécurité à garantir présenterune réduction : un attaquant permet de contredire les hypothèses Le chiffrement asymétriqueet la sécurité prouvée -20David Pointcheval Notions de sécuritéNotions de sécurité

En fonction des besoins, on définit

les objectifs de l"adversaire les moyens, soit les informations mises

à sa disposition.

Le chiffrement asymétriqueet la sécurité prouvée -21David Pointcheval Confidentialité élémentaireConfidentialité élémentaire

·Non-inversibilité(OW -One-Wayness) :

sans la clé privée, il est calculatoirement impossible de retrouver le message clair [])()(Pr)(Succ,m;rcmcrmow=== Insuffisant si on a déjà de l"information sur m: "Message au sujet de XXXXX» "Ma réponse est XXX» Le chiffrement asymétriqueet la sécurité prouvée -22David Pointcheval

Confidentialité forteConfidentialité forte

·Sécurité sémantique (IND -Indistinguishability) :

GM1984

le chiffré ne révèle aucune autreinformation sur le message clair à un adversaire polynomial

1Pr2),()(),,(),,,(

110
102

¬¬=rmcsmmbscmm

bbr ek =)(Advind Le chiffrement asymétriqueet la sécurité prouvée -23David Pointcheval ·Non-malléabilité(NM -Non-Malleability) :

DDN 1991

Aucun adversaire polynomialne peut dériver

de c= (m;r)un deuxième chiffré c"=(m";r"), de façon à ce que les clairs met m"soient reliés non-malléabilité

ßsécuritésémantique

non-inversibilité Le chiffrement asymétriqueet la sécurité prouvée -24David Pointcheval

Attaques de baseAttaques de base

·Attaques à clairs choisis

(CPA -Chosen-Plaintext Attacks)

Dans l"environnement à clé publique,

l"adversaire peut chiffrer tout message de son choix, grâce à la clé publique attaque de base ·Autres informations : accès à des oracles -attaque par réaction : cvalide ? ?-attaque par vérification : (m,c) m = (c) Le chiffrement asymétriqueet la sécurité prouvée -25David Pointcheval Attaques à chiffrés choisisAttaques à chiffrés choisis

·Attaques à chiffrés choisis

(CCA -Chosen-Ciphertext Attacks) L"adversaire a accès à l"oracle de déchiffrement soit le clair de tout chiffré de son choix (sauf le challenge) non-adaptatives (CCA1)NY 1990 accès avant de recevoir le challenge adaptatives (CCA2)RS 1991 accès illimité Le chiffrement asymétriqueet la sécurité prouvée -26David Pointcheval

RelationsRelationsBDPR CBDPR C--19981998

Implications et séparations

NM-CPAÜNM-CCA1ÜNM-CCA2

IND-CPAÜIND-CCA1ÜIND-CCA2

sécurité forte : CCA sécurité minimale sécurité faible

OW-CPA

Le chiffrement asymétriqueet la sécurité prouvée -27David Pointcheval

·Le chiffrement asymétrique

·Les hypothèses algorithmiques

·Les preuves de sécurité

Un exemple : OAEP

·La sécurité pratique

·Conclusion

SommaireSommaire

Le chiffrement asymétriqueet la sécurité prouvée -28David Pointcheval Une permutation à trappeUne permutation à trappe

Une permutation à sens-unique à trappe

conduit à un schéma OW-CPA

Ex : RSA

f (m) = memodn g(c) = cdmodn

Mais niveau de sécurité insuffisant !

On veut la sécurité forte : IND-CCA2

Le chiffrement asymétriqueet la sécurité prouvée -29David Pointcheval M ra b

GHM = m||0...0

raléaG etH fonctions aléatoires (m) : Calculera,bpuis retournerc=f (a||b) (c): Calculera||b = g(c) inverser OAEP, et retournerm (si la redondance est satisfaite) Le chiffrement asymétriqueet la sécurité prouvée -30David Pointcheval

Oracle aléatoireOracle aléatoire

de preuvede sécuritéfortepar réduction

Aucun schéma inefficacen"ad"intérêt

pratique(sécurité transparente) hypothèse supplémentaire

Ex : modèle de l"oracle aléatoire (ROM)

Bellare-Rogaway 1993

certaines fonctions (Get H) sont considérées parfaitement aléatoires Le chiffrement asymétriqueet la sécurité prouvée -31David Pointcheval

OAEP (suite)OAEP (suite)

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 ?

-admis jusqu"àtrès récemment

RSA-OAEP retenu par

RSA PKCS, SET, IETF, IEEE, ISO, ...

-finalement fauxShoup2000 Le chiffrement asymétriqueet la sécurité prouvée -32David Pointcheval

RSARSA--OAEP OAEP FOPS CFOPS C--20012001

·OAEP conduit au niveau CCA àpartir

d"une permutation àsens-unique sur un domaine partiel, àtrappe -(a,b)?f (a || b)àsens-unique, àtrappe -f (a|| b) ?aégalement difficile

·RSA-Partiel ÛRSA

avec un (t, e)-oracle qui extrait ade (a|| b)emodn, RSA(n,e)résolu avec probabilitée2en temps 2t

·IND-CCA2 de RSA-OAEP ÛRSA

Heureusement pour les applications industrielles ! Le chiffrement asymétriqueet la sécurité prouvée -33David Pointcheval

Intérêt pratiqueIntérêt pratique

RSA 1024 bits impose t"> 280donc t> 240

Þsécuritéprouvée en 240 !

(ou 274, ...mais avec 4096 bits :pas pratique)

·RSA-OAEP : construction efficace,

prouvéeIND-CCA2 sousRSA (ROM)

Maislaréduction est

quadratique

Attaquant contre

IND-CCA2 en tAlgorithme

contre RSA en t" »t2 Le chiffrement asymétriqueet la sécurité prouvée -34David Pointcheval

·Le chiffrement asymétrique

·Les hypothèses algorithmiques

·Les preuves de sécurité

·Un exemple : OAEP

La sécurité pratique

quotesdbs_dbs30.pdfusesText_36