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

David Pointcheval Le chiffrement asymétrique et la sécurité prouvée -15 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 Sommaire David Pointcheval Le chiffrement asymétrique et la sécurité prouvée -16 Hypothèse algorithmique

Algorithmes de chiffrement symétrique par bloc (DES et AES)

Chiffrement par bloc • Une des primitives (« briques ») les plus largement utilisées en cryptographie – Chiffrement symétrique – Protection de l’intégrité – Construction de fonctions de hachage, de générateur pseudo-aléatoire, etc

Cryptographie asymétrique - Zenk

Un exemple de chiffrement à clé publique: le codage

Un tel système, appelé aussi chiffrement asymétrique, a été imaginé à la fin des années soixante dix ; le plus connu est le système RSA utilisé aujourd'hui dans une multitude d'applications, notamment les transactions sécurisées via internet L'objectif de cette activité est la mise en œuvre d'un chiffrement à clé publique

Cryptographie à clé publique - uliegebe

Chiffrement asymétrique - 22 Exemple Le destinataire légitime connaît le havresac simple S et les valeurs de w et de n Il peut donc déterminer w-1 Exemple avec w = 15 et n = 17, w-1 est 8: 15 * 8 = 120 = 7 * 17 + 1 Exemple 13 * 8 mod 17 = 104 mod 17 = 2 = [1, 2, 4, 9] * [0100] 40 * 8 mod 17 = 320 mod 17 = 14 = [1, 2, 4, 9] * [1011]

Cryptographie symétrique : introduction

cryptologie asymétrique : – RSA – Diffie-Hellman – Ce sont des algorithmes plus coûteux en temps machine que les algorithmes symétriques utilisés pour le chiffrement C'est un domaine récent, initié par Diffie et Hellman en 1976

Chapitre II Principes généraux de la cryptographie

Sinon, on parle de chiffrement asymétrique (Figure 2) ou de chiffrement à clé publique Dans ce cas, chaque utilisateur possède une paire de clés privée/publique, telle que la clé privée est connue uniquement par son propriétaire tandis que la clé publique peut être publiquement connue La clé publique est dérivée de la clé

Cours 4MMCSR - Codage et sécurité des réseaux

• chiffrement symétrique et Chiffrement asymétrique; (ECDLP/El Gamal) Fonctions de hachage et générateurs aléatoires • Application aux attaques par corrélation Exemple: Siegenthaler sur GSM • Partie 2 : Sécurité applicative et attaques [F Duchene, K Hossen] – 1 Sécurité des applications Web et des réseaux

1 Le chiffrement de César - Exo7

Encore une fois, k appartient à Z=26Z, car par exemple les fonctions C29 et C3 sont identiques Le décalage k s’appelle la clé de chiffrement, c’est l’information nécessaire pour crypter le message Il y a donc 26 clés différentes et l’espace des clés est Z=26Z Il est clair que ce chiffrement de César est d’une sécurité

Travaux pratiques de Crypto avec OpenSSL - coins-laborg

exemple 3DES) Cet algorithme va chiffrer et protéger la clé privée grâce à une clé de chiffrement symétrique générée par le mot de passe (pass-phrase) que vous allez choisir et confirmer OpenSSL> genrsa -des3 -out key -rand rand txt 1024 Ici, vos clé privée/publique sont générées Elles sont stockées sur votre disque

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

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

David PointchevalLe Chiffrement Asymétrique

Habilitation à Diriger des Recherches

Université Paris VII -Denis Diderot

École normale supérieure

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

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

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

Cryptographieasymétrique

Diffie-Hellman1976

AliceBobconfidentialité

Chiffrement asymétrique :

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

Þconnue de tous

Þconnue de Bob

Grâce à la clé publique de Bob,

Alice peut fermer un coffre,

3 algorithmes :

à partir de csans la clé privée k

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

·la clé keest publique

Au moins la recherche exhaustive sur met r

Þconfidentialitéinconditionnelle impossible

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

·Multiplication/Factorisation :

Fonction

à sens-unique

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

·Multiplication/Factorisation :

Fonction

à sens-unique

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

·Multiplication/Factorisation :

Fonction

à sens-unique

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

·Multiplication/Factorisation :

Fonction

à sens-unique

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

·RSA

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

Diffie-Hellman

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

Record

Août 1999

20115681921491044096111662048

80351024

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

Convenables pour RSA

Bornes inférieures pour LD dans*

Repère

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

·n=pq: module public

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

Chiffrement RSA