La Cryptographie Asymétrique

et les Preuves de Sécurité

David Pointcheval
Chargé de recherche CNRS
Département d’informatique
École normale supérieure

Sommaire

1. Introduction
2. Les hypothèses algorithmiques
3. Le chiffrement asymétrique
4. Les preuves de sécurité
5. La signature
6. Conclusion

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 2

 Introduction

1. Introduction
2. Les hypothèses algorithmiques
3. Le chiffrement asymétrique
4. Les preuves de sécurité
5. La signature
6. Conclusion

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

Confidentialité

• Archiver sur un support

• Émettre
sur un canal

de façon qu’un tiers ne puisse en

prendre connaissance
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 4
 Authentification (1)

Prouver de façon interactive son identité

à un interlocuteur

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 5

Authentification (2)

• Attacher, à un message,
une preuve non-interactive de son origine
• Si cette preuve peut convaincre un tiers
⇒ signature

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

 Intégrité

Garantir qu’un message, un document,

un fichier, n’a pas subi de modification
(aussi bien accidentelle qu’intentionnelle)

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

Les 3 âges de la cryptologie

• L’âge artisanal : jusqu’en 1918

• L’âge technique : de 1919 à 1975
• L’âge paradoxal : de 1976 à nos jours

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 8

 Âge artisanal

Substitutions et permutations :
cadrans cylindres

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

Algorithmes secrets

Scytale Lacé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
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 10
 Chiffrement par décalage

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

subit un décalage constant K
CK(x) = x + K mod 26
DK(y) = y - K mod 26
Cryptanalyse : recherche exhaustive
elle consiste à essayer toutes les clés K possibles
(soit seulement 26)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 11

Chiffrement par substitution

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

est substituée par une autre
Cπ(x) = π(x)
Dπ(y) = π-1(y)
où π est une permutation de [0,25]
Cryptanalyse : recherche exhaustive ?
Sur un alphabet de 26 lettres : 26! Possibilités
Soit plus de 4. 1026, ou 288

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 12

 Cas particuliers

Chiffrement par décalage :

π(x) = x + K mod 26
Chiffrement affine :
π(x) = a x + b mod 26

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

Chiffrement par permutation

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

mais on change l’ordre (ex: scytale)
CK(x1,…,xn) = (xπ(1) , xπ(2), …, xπ(n))
DK(y1,…,yn) = (yπ-1(1) , yπ-1(2), …, yπ-1(n))
où π est une permutation de [1,n]
C’est un cas particulier de Hill :
matrice de permutation K : Y = KX

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 14

 Âge technique

Machines chiffrantes

Automatisation
des permutations
et substitutions

Enigma

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 15

Âge paradoxal

• Cryptographie à clé secrète

• Cryptographie à clé publique

Fonctions à sens-unique
(éventuellement à trappe)
⇒ Preuves de sécurité

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

 Principes de Kerckhoffs

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

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

Chiffrement symétrique

Algorithme de chiffrement, C
Algorithme de déchiffrement, D
k k

c
m C D m

Sécurité : impossible de retrouver m

à partir de c sans k
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 18
 Chiffrement de Vigenè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)
DK(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
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 19

Sécurité

Recherche exhaustive :
si la clé est de longueur n,
il y a 26n possibilités

n = 5 ⇒ 2 23 n = 10 ⇒ 2 47 n = 15 ⇒ 2 70

→ Recherche exhaustive
vite hors de portée

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 20

 Analyses 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 !
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 21

Sécurité parfaite ?

Chiffrement de Vernam :
Combiner le message à chiffrer
avec une suite de bits aléatoires
c = m⊕k m = c⊕k

Sécurité inconditionnelle
à condition que la « clé » k soit aussi
longue que le message m (Shannon)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 22

 En pratique …?

• César/Vigenère/… pas sûrs

• Vernam pas 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

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 23

Chiffrement symétrique

• clé unique k
– chiffrement
– déchiffrement
• conception heuristique :
– permutations (diffusion)
– substitutions (confusion)
• orienté implémentation matérielle
→ débit rapide

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 24

 Chiffrement symétrique

Par blocs (block cipher) :

décompose le message en blocs
– DES (IBM-NBS)
s normal - clé de 56 bits, blocs de 64 bits
s renforcé (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

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 25

Chiffrement symétrique

Par flot (stream cipher) :

chiffre un flux de données
– Vernam (générateur pseudo-aléatoire) :
G(k) = k1k 2 m = m1m2
c = c1c2 ci = mi ⊕ ki

– RC4 (Rivest)
chiffre octet par octet

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 26

 Chiffrement asymétrique

Algorithme de chiffrement, C
Algorithme de déchiffrement, D
kc kd

c
m C D m

Sécurité : impossible de retrouver m

à partir de c sans kd
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 27

Chiffrement asymétrique
• Lois de Kerckhoffs poussé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
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 28
 Chiffrement asymétrique

– RSA (Rivest-Shamir-Adleman 1978)

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
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 29

Authentification

• Algorithme d’authentification, A
• Algorithme de vérification, V
ka kv

σ
m A
m V 0/1

Sécurité: impossible de produire

un σ valide sans ka
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 30
 Authentification « artisanale »

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
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 31

Signature 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

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

 Signature numérique

– RSA (Rivest-Shamir-Adleman 1978)

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 (Pointcheval 1995)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 33

Identification : contrôle d’accès

• Authentification interactive :
Alice (client) veut prouver
à Bob (serveur) son identité
Je m’appelle
Alice

Prouve-le moi !

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 34

 Preuves Zero-Knowledge

Protocoles « zero-knowledge » :
– preuve de connaissance d’un secret
– sans transfert d’information sur ce secret,
seule la conviction de connaissance

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

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

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 36

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

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 37

Exemples
• 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
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 38
Les 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

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 39

Chiffrement asymétrique

Algorithme de chiffrement, C
m → c : transformation aisée

c
m C D m

Algorithme de déchiffrement, D
c → m : transformation difficile
à moins de connaître une trappe
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 40
 Outils nécessaires

• Fonctions à sens-unique :
étant donnée une relation y = f(x)
x → y aisé, mais y → x difficile
• Fonctions à sens-unique à trappe :
étant donnée une relation y = f(x)
x → y aisé,
y → x difficile
y → x aisé avec z (« trappe »)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 41

Où trouver des candidats ?

les mathématiques

Un premier exemple : la factorisation

p, q → n = p.q facile k=|n|=log2(n)
en O(k2) opérations élémentaires
en revanche
n = p.q → p, q difficile
en  1 . 92 (ln n ) (ln ln n ) 
1/3 2/3

Οe 
 
Record actuel : nombre n produit de deux
facteurs premiers de 78 chiffres
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 42
 Et la trappe ?

• Le produit/factorisation
est une fonction à sens-unique
mais où est la trappe ?
• Certains calculs dans /n sont
– faciles si on connaît les facteurs de n
– difficiles sans les facteurs de n

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

Théorie des nombres

L’anneau quotient :
n = /n = {0,1,… , n-1}

Théorème de Bezout
Soient a et b deux entiers
(∃u,v)(au+bv=1)⇔pgcd(a,b)=1

n ⇔n
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 44
 Algorithme d’Euclide
• Trouver l’inverse d’un élément x modulo n
revient à trouver u et v tels que
ux + vn = 1
• L’algorithme d’Euclide calcule
le PGCD de deux entiers
• Une version « étendue » calcule
les coefficients u et v.
Ces deux algorithmes ont une complexité
linéaire en la taille des arguments.
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 45

Théorème des restes chinois

Quand n=pq est composé ?

f: n → p × q g: p × q → n

x ( x mod p, x mod q ) ( a, b) auq + bvp

f isomorphisme u = q −1 mod p v = p −1 mod q

d’anneaux

n ≅ p× q
*
n ≅ *
p × *
q

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 46

 Fonction d’Euler

(∀n) ϕ (n) = card( *

n )

p est premier :
ϕ ( p ) = card( *
p ) = p −1

n=pq est composé :

ϕ (n) = card( *
n ) = card( *
p × *
q )
= ϕ ( p )ϕ (q ) = ( p − 1)(q − 1)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 47

Fonction d’Euler

 1
n = ∏ pi ⇒ ϕ (n) = n × ∏ 1 − 
vi

 pi 

connaissance
(d’un multiple) de ϕ(n)

connaissance de
la factorisation de n
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 48
 Théorème d’Euler

Pour tout groupe G,

(∀x ∈ G)( x = 1) c
de cardinal c :
En particulier, pour tout entier n
(∀x ∈ *n )( xϕ ( n ) = 1 mod n)

Petit théorème de Fermat :

pour tout entier premier p
(∀x< p)(x p−1=1 mod p)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 49

La fonction RSA

• Soit un module n=pq

• Soit un exposant e premier avec ϕ(n)
• Soit d=e-1 mod ϕ(n)
e d + u ϕ(n) = 1

∗ ∗ ∗ ∗
f: n → n g: n → n
m me mod n c cd mod n

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 50

 Hypothèse RSA

multiple de ϕ(n) ⇔ factorisation de n

• calculer des racines e-ièmes :

ϕ(n) suffisant
• nécessaire ?
– En pratique : oui (calcul de d)
– En théorie : non RSA(n,e) ≤ FACT(n)
• Hypothèse RSA :
RSA(n,e) ≈ FACT(n)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 51

Estimations de complexité

Record de factorisation : 512 bits (155 dig.)

coût estimé : 213 Mips-Years (258 op.)

Module Mips-Year Opérations En 2015

512 13 58 48
1024 35 80 70
2048 66 111 101
4096 104 149 139
8192 156 201 191

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 52

 Le logarithme discret

• ( ,×) groupe d’ordre q

• g∈ et y∈<g>
Logg(y) = min{x > 0 | y = gx}
• Pour ⊆ *p , le calcul du logarithme
discret est en
 1 . 92 (ln p ) (ln ln p ) 
1/3 2 /3

Οe 
 

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 53

Le théorème de Lagrange

• ( ,×) groupe d’ordre q

• pour tout sous-groupe ⊆
Card | Card
• Pour ⊆ *p,
q = Card <g> | p-1

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 54

 Le problème Diffie-Hellman

⊆ *
p groupe cyclique d’ordre q
g générateur : = <g>

• Étant donnés A=ga et B=gb

• Calculer DH(A,B) = C=gab

Clairement DH ≤ LD
(a = LoggA et C=Ba)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 55

Et les trappes ?

• Le problème du logarithme discret est

difficile, mais pas moyen de le rendre facile !
• Et le problème Diffie-Hellman ?
Étant donnés A=ga et B=gb
Calculer DH(A,B) = C=gab
Difficile, mais si on connaît a : C=Ba

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 56

 La fonction Diffie-Hellman

• Soit un groupe cyclique = <g>

• Soit un exposant x (privé)
• Soit y = gx (public)

f: → f: →
gr yr R Rx

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 57

Hypothèse Diffie-Hellman

• Évaluation de f :
r ou x suffisent
• nécessaire ?
– En pratique : oui
– En théorie : non
• Hypothèse Diffie-Hellman :

DH(g) ≈ LD(g)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 58

 Estimations de complexité

Records de logarithme discret

• sur les courbes elliptiques : GF(2109)
• dans p : 120 chiffres
*

plus difficile que la factorisation

⇒ estimations pour la factorisation donnent
une borne inférieure

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 59

Le chiffrement asymétrique

1. Introduction
2. Les hypothèses algorithmiques
3. Le chiffrement asymétrique
4. Les preuves de sécurité
5. La signature
6. Conclusion

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 60

 Le Chiffrement Asymétrique

Algorithme de chiffrement, C
kc : clé de chiffrement (publique)
kc kd

c
m C D m

Algorithme de déchiffrement, D
kd : clé de déchiffrement (privée)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 61

Chiffrement RSA (1978)

• n=pq : module public

• e : exposant public
• d=e-1 mod ϕ(n) : exposant secret

C(m) = me mod n → c
( ) d
D(c) = cd = me = m mod n

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 62

 Propriétés de RSA

n, e publics, puis d secret

Efficacité
C(m) = m e mod n 3|e|/2 mult mod n
D(c) = c d mod n = g ( f (c) d ) 3|n|/8 mult mod n
Sécurité : Le calcul de racines e-ièmes
semble nécessiter d
⇒ e d – 1 est un multiple de ϕ(n)
⇒ factorisation de n
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 63

Chiffrement de Rabin (1978)

• n=pq : module public

• B : élément public
• p,q : clé privée

public C( m) = m(m + B ) mod n → c

 B2 B 
secret D(c) ∈  c + − mod n 
 4 2 
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 64
 Propriétés de Rabin

n, B publics, puis p, q secrets

Efficacité
• Chiffrement : 1 mult mod n
• Déchiffrement : 3|n|/8 mult mod n

Sécurité : Le calcul de racines carrées

⇒ factorisation de n

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 65

Échange de clé
Diffie-Hellman (1976)

q | p-1 et g : éléments communs

Alice choisit x et publie X=gx

Bob choisit y et publie Y=gy

Secret commun K = X y = Y x = g xy

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 66

 Chiffrement El Gamal (1985)

• g : générateur commun
• x : clé privée
• y=gx : clé publique

public C( m) = ( g a , y a m) → (c, d )

secret D(c, d ) = d / c x

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 67

Inversion de El Gamal

g : générateur commun
x : clé privée y=gx : clé publique

Soit un algorithme qui inverse le

chiffrement El Gamal : (y,c,d) → m
Soient A=ga et B=gb puis d aléatoire
(A,B,d) → m alors DH(A,B)=d/m

Inversion EG = DH
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 68
 Les preuves de sécurité

1. Introduction
2. Les hypothèses algorithmiques
3. Le chiffrement asymétrique
4. Les preuves de sécurité
5. La signature
6. Conclusion

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 69

Protocole prouvé sûr

Pour prouver la sécurité d’un protocole

cryptographique, on doit
• préciser les notions de sécurité à garantir
• préciser les hypothèses calculatoires
• décrire un protocole
• présenter une réduction :
un attaquant permet de contredire
les hypothèses
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 70
 Notions de sécurité

En fonction des besoins, on définit

• les objectifs de l’adversaire
• les moyens,
soit les informations mises
à sa disposition.

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 71

Hypothèses calculatoires

Les hypothèses sont

• Une fonction est à sens-unique
• Une fonction est à sens-unique à trappe
• Tel problème est insoluble
en un temps t donné

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 72

 Protocole cryptographique
On décrit un protocole
ex. basé sur l’hypothèse RSA
Il est impossible d’extraire des racines modulaires,
pour des modules de 1024 bits,
en moins de 280 opérations
• n = pq, e exposant premier avec ϕ(n)
• (n, e) : clé publique
• d = e-1 mod ϕ(n) : clé privée
(m) = m e mod n (c) = c d mod n
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 73

Sécurité par réductions

Réduction d’un problème difficile
à une attaque Atk :
• Si l’attaquant A parvient à son but
alors A peut être utilisé pour résoudre
insoluble ⇒ schéma incassable
Efficacité de la réduction :
• Théorie de la complexité : polynomiale
⇒ sécurité asymptotique
• Sécurité exacte : réduction précise
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 74
 Sécurité pratique

Soit un attaquant A qui parvient à son but

en temps t, et une réduction qui permet
de résoudre , avec A, en temps t’=f(t)
• Théorie de la complexité : f polynomiale
• Sécurité exacte : f explicite
• Sécurité pratique : f petite (linéaire)
Ex: t’ = 2t ⇒ schéma incassable
en moins de 279 opérations
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 75

Divers modèles de sécurité

Les réductions efficaces sont rares

⇒ on fait des hypothèses idéales :
– Fonctions de hachage aléatoires
random oracle model
– Chiffrement par blocs parfait
ideal cipher model
– Attaque indépendante du groupe
generic model

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 76

 Chiffrement

• Sécurité parfaite :
le chiffré et les données publiques
ne révèlent aucune information
sur le message clair,
sauf éventuellement la taille
Au sens de la théorie de l’information
⇒ impossible

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 77

Buts de l’adversaire

• Non-inversibilité (OW - One-Wayness)

Sans la clé privée, il est calculatoirement
impossible de retrouver le message clair
• Sécurité sémantique
(IND - Indistinguishability):
Aucun adversaire polynomial ne peut
apprendre d’information sur le message clair à
partir du chiffré et des données publiques
(sauf éventuellement la taille)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 78
 Attaques possibles
• à 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
• à chiffrés choisis
(CCA - Chosen-Ciphertext Attacks)
L’adversaire à accès à un oracle de déchiffrement,
qui déchiffre tout chiffré de son choix
(sauf le challenge)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 79

Notions de sécurité

• OW-CPA: (sécurité minimale)

• CC Attaques
parfois faciles à mettre en œuvre
⇒ les rendre inutiles
• Espace des messages clairs
souvent limité : oui/non -- achat/vente
⇒ IND nécessaire
IND-CCA niveau de sécurité souhaitable
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 80
Principaux niveaux de sécurité

• OW-CPA: (le plus faible)

Pr [ (c) = m c = (m;r )] = Succ négligeable
m,r

• IND-CCA: (le plus fort - BDPR C ’98)

 (m0 , m1 , s ) ← 1 (k e )
2 Pr  2 (m0 , m1 , c, s ) = b
c ← (mb , r )  −1
r ,b  
= Adv négligeable
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 81

Ex. I : Chiffrement RSA

• n = pq, produit de deux grands premiers

• e, exposant premier avec ϕ(n) = (p-1)(q-1)
• n, e : clé publique
• d = e-1 mod ϕ(n) : clé privée

(m) = m e mod n (c) = c d mod n

OW-CPA = problème RSA

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 82

 Ex. II : Chiffrement El Gamal

• = (<g>, ×) groupe d’ordre q

• x : clé privée
• y=gx : clé publique

( m ) = ( g a , y a m ) → (c, d ) ( c, d ) = d / c x

OW-CPA = problème DH

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 83

El Gamal : OW-CPA
( m ) = ( g a , y a m ) → (c, d ) ( c, d ) = d / c x

= (<g>, ×) et (A,B)
en entrée de B ε = mPr, a[ (c' ) = m c' = (m;a) ]
• y ← A et c ← B
• Valeur aléatoire d : A(c,d) → m
• Retourne d/m
Si m est correct, DH(A,B)=d/m
SuccDH (B) = SuccOW-CPA(A) = ε
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 84
 El Gamal : IND-CPA
 (m0, m1, s) ← 1 (ke) 
c' ← (mb, a)  −1
ε = 2 Pr (m ,
 2 0 1 m , c' , s ) = b
a, b 

= (<g>, ×) et (A, B, C) en entrée de B

• y ← A et c ← B: A1(y) → (m0, m1)
• b ∈{0,1} et d ← C mb: A2(c,d) → b’
• retourne (b=b’)
Supposons que m0, m1 ∈
– Si C=DH(A,B), Pr[b=b’] = Succ(A) = (ε+1)/2
– Si C≠DH(A,B), Pr[b=b’] = 1/2
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 85

Les problèmes Diffie-Hellman

⊆ *
p groupe cyclique d’ordre q
g générateur : = <g>
Calculatoire :
• Étant donnés A=ga et B=gb
• Calculer DH(A,B) = C=gab

Décisionnel :
• Étant donnés A=ga, B=gb et C=gc
• Décider si DH(A,B) = C (ou c=ab mod q)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 86
 Attaques à chiffrés choisis

Pour résister aux attaques à chiffrés

choisis, l’oracle de déchiffrement ne doit
apporter aucune information utile à
l’adversaire
– preuve non-interactive zero-knowledge
de la connaissance du clair
– plaintext-awareness
(dans le model de l’oracle aléatoire)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 87

Schémas IND-CCA
• Rackoff-Simon (1991),
définition de la notion CCA
+ exemple (pas pratique)
• Cramer-Shoup (1998),
premier exemple pratique :
IND-CCA = DDH
Mais pas très efficace
⇒ modèle de l’oracle aléatoire
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 88
 Conversions génériques
• Toute fonction injective à sens-unique à
trappe = chiffrement OW-CPA
• Mais OW-CPA insuffisant
• Comment atteindre IND-CCA ?
⇒ conversions génériques
de OW-CPA en IND-CCA
( , ) est supposé un chiffrement faible et on
fabrique un chiffrement fort ( , )
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 89

OAEP (Bellare-Rogaway EC ‘94)

M a
M = m||0…0 G et H
G H fonctions aléatoires
r aléa
r b

(m): Calculer a,b puis retourner (a||b)

(c): Calculer a||b = (c)
inverser OAEP, et retourner m
(si la redondance est satisfaite)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 90
 OAEP (suite)

Il fournit une conversion « optimale »

de toute permutation à sens-unique
sur un domaine partiel, à trappe
en un chiffrement IND-CCA
Efficacité : optimale (+ 2 hachés)
Taille : optimale
Application : RSA (la seule permutation !)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 91

RSA-OAEP sécurité (FOPS ‘01)

(M) = (a = M⊕ G(r) || b = r ⊕ H(a) ) mod n → c

e

Deviner 1 bit de M ⇔ deviner r ⇔ deviner a

⇔ deviner (a,b) ⇔ inverser RSA
(c) = cd mod n → (a, b)
r = H(a) ⊕ b M = a ⊕ G(r)
si M = m||0…0 alors m = x sinon « refus »
Chiffré valide ⇔ H(a) et G(r) ⇔ clair connu
Plaintext-awareness
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 92
 RSA-OAEP - norme
OAEP : premier padding
avec « preuve » de sécurité
• Mais preuve originale de BR ‘94 incomplète
• Preuve complète récente FOPS ‘01
Heureusement car retenu par
RSA PKCS, SET, IETF, IEEE, ISO, …
Cependant, mauvaise réduction : quadratique
⇒ sécurité avec 1024 bits en 240 !
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 93

Autres conversions

OAEP ne convient que pour des

permutations : peu de candidats !
– Fujisaki-Okamoto (PKC ‘99):
IND-CPA → IND-CCA
– Fujisaki-Okamoto (Crypto ‘99)
– Pointcheval (PKC ‘00):
OW-CPA → IND-CCA
mais déchiffrement non-optimal
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 94
 Nouvelle conversion: REACT
(Okamoto-Pointcheval RSA ‘01)

(m ; r||s)= a = (r ; s) avec r∈ s∈
b = k ⊕ m où k = G(r)
c = H(m,r,a,b)
(a,b,c): Calculer r = (a) et k = G(r)
extraire m = k ⊕ b
si c = H(m,r,a,b) et r∈
alors retourner m sinon « refus »
Conversion de tout chiffrement OW-PCA
en chiffrement IND-CCA
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 95

Nouvelle attaque : PCA

Plaintext Checking Attack : l’adversaire

– peut obtenir le chiffré de tout message de son
choix (en le chiffrant lui-même)
– a de plus accès à un PC-oracle qui,
sur la paire (m,c) répond si c chiffre m, ou non
Remarque: IND-PCA impossible
⇒ mais seul OW-PCA nous intéresse

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 96

 Résultat de sécurité
→ {0,1} H : {0,1} → {0 ,1} H
∗
 

G: G

Si un adversaire A contre IND-CCA

obtient un avantage AdvA
après qG, qH et q questions
à G, H et resp.
alors on peut casser la OW-PCA
de ( , ) avec probabilité
Adv − q


2 2H
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 97

Preuve : IND-CPA

Soit (a,b,c) tel que a = (r ; s),

k = G(r), b = k ⊕ md, c = H(md,r,a,b)
Pour deviner le bit d, un adversaire doit avoir
demandé
– r à G pour obtenir k (et vérifier b)
– (m0,r,a,b) ou (m1,r,a,b) à H (et vérifier c)
à cause du caractère imprédictible de G et H

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 98

 Preuve IND-CPA (suite)

Probabilité pour que r (= (a)) ait été

demandé à G ou H supérieure à AdvA/2

On trouve le bon, grâce au PC-oracle,

dans la liste des questions posées à G et H
⇒ qG + qH questions au PC-oracle

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 99

Plaintext-awareness

(a,b,c) chiffré valide ⇒ on a

• demandé H(m,r,a,b) pour obtenir un c valide
• deviné c, mais avec probabilité 1/2 H

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 100

 Plaintext-extractor
Lors d’une question (a,b,c) posée par
l’attaquant à l’oracle de déchiffrement,
on regarde dans la liste des questions
(m,r,a,b) posées à H telles que
H(m,r,a,b) = c
puis on vérifie si
– r = (a) (grâce au PC-oracle)
– b = k ⊕ m pour k = G(r)
Extraction correcte, sauf avec
probabilité 1 - 1/2 H
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 101

IND-CCA
Après q questions à l’oracle de
déchiffrement
• toutes les simulations de déchiffrement ont
réussi, avec probabilité
(1 - 1/2 H )q ≥ 1 - q /2 H
• r a été demandé à G ou à H
(et extrait grâce au PC-oracle)
avec probabilité


Adv q
supérieure à − H

2 2
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 102
 Les problèmes Diffie-Hellman
• Calculatoire
✦ Étant donnés A=ga et B=gb
✦ Calculer DH(A,B) = C=gab

• Décisionnel
✦ Étant donnés A, B et C
✦ Décider si C = DH(A,B)
• Gap Résoudre le problème calculatoire,
avec un accès à un oracle de
décision
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 103

Le Gap-Diffie-Hellman
(Okamoto-Pointcheval PKC ‘01)

Le CDH est considéré difficile

(hypothèse Diffie-Hellman)
GDH facile ⇒ DDH = CDH
DDH facile ⇒ GDH = CDH
CDH est considéré
beaucoup plus difficile que DDH
⇒ GDH difficile

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 104

 REACT – El Gamal
• un groupe, et g d’ordre q
• G et H : fonctions de hachage
• E, D: chiffrement symétrique
E(m): a ←R q, R ←R x : clé privée
A ← ga , A’ ← R ya y=gx : clé publique
k ← G(R), B ← Ek(m), (A , A’, B, C)
C ← H(R, m, A, A’, B)
D(A, A’, B, C): R ← A’/Ax,
k ← G(R), m ← Dk(B),
vérifier C = H(R, m, A, A’, B)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 105

Sécurité pratique

Soit A un attaquant en temps t,

qui pose qG, qH et q questions à G, H
et l’oracle de déchiffrement
Alors
AdvA(t) ≤ 2 SuccGDH(t’) + 2 AdvE(t’) + 2 q /2 H
avec
t’ ≤ t + (qG + qH) TDDH

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 106

 La signature

1. Introduction
2. Les hypothèses algorithmiques
3. Le chiffrement asymétrique
4. Les preuves de sécurité
5. La signature
6. Conclusion

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 107

Authentification

Deux scénarios classiques

nécessitent de l’authentification :
• interactif : on prouve son identité
à un interlocuteur
• non-interactif : on attache,
à un message, une preuve de
son origine

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 108

 Signature

Si cette preuve peut convaincre un tiers :

non-répudiation
⇒ signature

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 109

Schéma de signature
• Algorithme de signature :
(A,ka) : secret
• Algorithme de vérification :
(V,kv) : public
ka kv

σ
m A
m V 0/1

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 110

 Sécurité
• Une signature produite avec ka est toujours
valide (acceptée) :
∀m, σ = ( , m)

(σ , m, ) =1

• Falsification universelle :
être capable d’authentifier
tout message sans ka
• Falsification existentielle :
être capable d’authentifier
un message sans ka
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 111

Attaques

Attaque sans message :

l’attaquant ne connaît que la clé publique
(même pas de signatures
⇒ très faible)
Attaque à messages connus :
l’attaquant connaît de plus
des couples message-signature
Attaque à messages choisis adaptative :
l’attaquant a accès à un oracle de signature
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 112
 Signature sûre
Un schéma de signature est dit SÛR
s’il garantit l’impossibilité de
falsifications existentielles
même selon des attaques
à messages choisis adaptatives
Une telle signature garantit :
– l’identité de l’expéditeur
– la non-répudiation:
l’expéditeur ne pourra pas renier
avoir émis cette signature
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 113

Permutations
à sens-unique à trappe

Soient C une permutation à sens-unique

et D son inverse (avec trappe)
ex : C(x) = xe mod n et D(y)=yd mod n
• C public et D secret
D(C(x)) = C(D(x)) = x
• Soit m un message :
A(m) = σ = D(m) secret
V(σ,m) = (C(σ) = m) public
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 114
 Signature RSA

• n=pq : module public

• e : exposant public
• d=e-1 mod ϕ(n) : exposant secret

(m,d)=md modn→σ

(σ,m,e)= m=σ emodn 

 ?

 
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 115

Sécurité

C public et D secret
D(C(x)) = C(D(x)) = x
• Calculer σ pour tout m :
calcul de D(m) pour tout m
⇒ falsification universelle = D
• Falsification existentielle :
Soit σ quelconque et m = C(σ)
V(σ,m) = (C(σ) = m) = 1
(m,σ) paire valide sans D !
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 116
 Full-Domain Hash

C public et D secret
D(C(x)) = C(D(x)) = x
h : fonction de hachage « aléatoire »
{0,1}*→Im(C)

(m)=D(h(m))→σ

(σ,m)= h(m)=C(σ) 
 ?

 
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 117

Intérêt de FDH-RSA
• Efficacité : même si le message à signer
est long,
– un seul bloc à signer
– |σ| = |n| = 1024 bits : overhead fixe
• Sécurité : si h aléatoire,
une falsification existentielle
est équivalente au problème RSA
il est aisé de trouver (h(m),σ),
mais ensuite il faut remonter à m :
inverser h
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 118
 Hypothèses de complexité

• Chiffrement asymétrique :
besoin de fonctions à sens-unique
avec une trappe
peu de candidats : RSA, Diffie-Hellman
• Signature numérique :
une fonction à sens-unique suffit
pas besoin de trappe
⇒ tout problème difficile :
problèmes NP-complets, RSA, LD
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 119

Signature El Gamal (1985)

p et g : éléments communs
x : clé privée y=gx : clé publique
Signature de m :
choisir k∈ p-1 inversible
calculer r=gk mod p
et s=(m-xr)×k-1 mod p-1 σ = (r,s)

Vérification de (m,σ) :
( gxr gk(m-xr)k-1 = ) yr rs = gm mod p
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 120
 Falsification existentielle

Équation de vérification :
yr rs = gm mod p
Posons r = yagb mod p
Alors yr rs = yr yas gbs = gm mod p
r+as = 0 mod p-1
bs = m mod p-1
Soit s = -r/a mod p-1 et m = bs mod p-1

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 121

Signature Schnorr (1989)

q | p-1 et g : éléments communs

x : clé privée y=gx : clé publique
Signature de m :
choisir k∈ q et calculer r=gk mod p
ainsi que e=h(m,r)
et s = k-xe mod q σ = (e,s)

Vérification de (m,σ) :
u = gs ye (= gk-xe gxe mod p) tester e=h(m,u) ?
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 122
 Preuve de sécurité (PS ‘96)

Falsification existentielle
selon une attaque à messages
choisis adaptative
dans le modèle de l’oracle aléatoire
= résolution du logarithme discret
(extraction de la clé privée)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 123

Lemme de bifurcation
h aléatoire
e=h(m,r)
(m,e,s) prob. ε
y aléatoire

y aléatoire
h(m,r)
h
aléatoire
e
(m,e,s) prob. ε
h e’
aléatoire
(m,e’,s’) prob. ε/qh
Après 2 exécutions, avec probabilité ε2/qh :
gs ye = r = gs’ ye’ ⇒ gs-s’ = ye’-e
Posons α = (s-s’)/(e’-e) mod q ⇒ y=gα
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 124
 Digital Signature Algorithm
Norme américaine (1994)
Variante de Schnorr : (p,q,g) et (x,y)
Signature de m :
choisir k∈ q inversible σ = (r,s)
et calculer r=(gk mod p) mod q
ainsi que e=SHA(m) et s = (e+xr)× k-1 mod q

Vérification de (m,σ) :
u = SHA(m) s-1 mod q et v = r s-1 mod q
tester si r = (gu yv mod p) mod q ?

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 125

Comparaison

• El Gamal : Pas sûr et coûteux

• Schnorr :
Avantages
– efficace : réduction modulo q
suppression de l’inversion
– signature courte : 240 bits
– sûr : e = h(m,r)
Inconvénients
– breveté … par Schnorr
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 126
 Comparaison

• DSA :
Avantages
– pas breveté (norme)
Inconvénients
– efficace : rajout d’inversions
– sûr : e=h(m) (et non h(m,r) qui suffirait)
• ECDSA : DSA sur courbes elliptiques
– preuve de sécurité (sous hypothèse forte)

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 127

Sans théorie des nombres

Suppressions des calculs coûteux :

• PKP : Permuted Kernel Problem
(Shamir -1989)
• SD : Syndrome Decoding
(Stern - 1993)
• CLE : Constraint Linear Equations
(Stern - 1994)
• PPP : Permuted Perceptrons Problem
(Pointcheval - 1995)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 128
 PKP (Shamir 1989)

Problème des Noyaux Permutés :

• Soit p un petit premier (p = 251)
Soit A une matrice m × n dans p
Soit V un vecteur de taille n dans p
• Existe-t-il une permutation π sur les
coordonnées de V qui mette Vπ dans le
noyau de A ?
(∃ ? π)(Vπ ∈ Ker A)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 129

PKP : complexité

• PKP est un problème NP-complet

• Difficile à résoudre en pratique :
p = 251, m = 16 et n = 32
suffisent à le rendre insoluble
• Shamir a proposé une preuve de
connaissance de π, Zero-Knowledge
– 3 passes : 2 chances sur 3 de frauder
– 5 passes : ~1 chance sur 2 de frauder

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 130

 Signature
Toute preuve interactive « Zero-Knowledge »
(vérifieur honnête) peut être transformée
en schéma de signature sûr
(Heuristique : Fiat-Shamir 1986)
(Preuve : Pointcheval-Stern 1996)
Preuve interactive Signature de m


→r r
e = H(m,r)
←
e
s → (r, s)

→s
V(r , e, s )
V(r,e,s)
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 131

Non-répudiation

• Un schéma de signature est dit sûr

si aucun attaquant ne peut produire de
falsification existentielle.
⇒ tout couple (m,σ) valide a
nécessairement été produit
par l’utilisateur possédant
la clé publique
Nul ne peut renier un message signé
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 132
 Conclusion

1. Introduction
2. Les hypothèses algorithmiques
3. Le chiffrement asymétrique
4. Les preuves de sécurité
5. La signature
6. Conclusion

David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 133

Conclusion
La sécurité prouvée se fait en 3 étapes
1. notions formelles de sécurité
2. hypothèses algorithmiques précises
3. réduction
d’une mise en défaut d’une hypothèse
en le cassage d’une notion de sécurité
Plus la réduction est efficace, plus la
sécurité du système est proche de
l’hypothèse algorithmique
⇒ Sécurité pratique
David Pointcheval La cryptographie asymétrique et les preuves de sécurité- 134