Problème Diffie-Hellman

Cryptographie à clé • Soit G un groupe cyclique: tous les éléments

s’écrivent de la forme gx pour x=0 à n-1
publique • Problème du logarithme discret (DLog): étant
donné y, trouver x tel que y=gx ?
Pierre-Alain Fouque • Meilleur algorithme: complexité O(n ) 1/2
• Problème Diffie-Hellman (DH): étant donné g x et
gy, calculer gxy ?
• Problèmes équivalents sur une courbe elliptique
vendredi 12 septembre 14 vendredi 12 septembre 14
Diffie-Hellman Rivest-Shamir-Adleman
• RSA: premier système de chiffrement à clé publique
• résout aussi le problème de la signature numérique
(RSA=fonction à sens unique est une permutation)
• Sécurité = un problème algorithmique difficile
• Papier historique «New Directions in Cryptography» • factorisation des nombres de la forme produit de
2 grands nombres premiers
• Opération difficile: inversion du chiffrement (fonction
à sens unique à trappe) • inverser la fonction f(x)=x e mod N
• Résolvent le problème de l’échange de clé
vendredi 12 septembre 14 vendredi 12 septembre 14
 Calcul modulaire Soustraction dans Z7
- 0 1 2 3 4 5 6
11 0 1 • 5-2=3
• «Groupe de l’horloge» 0 0 6 5 4 3 2 1
10 2
• 2-5=-3=(-3)+7=4 mod 7 1 1 0 6 5 4 3 2
• Z ={0,1,2,3,...,11}
12 9 3 2 2 1 0 6 5 4 3
8 4
• 2+5=7 7 65 3
4
3
4
2
3
1
2
0
1
6
0
5
6
4
5
• 9+5=14=12+2=2 mod 12 5 5 4 3 2 1 0 6
6 6 5 4 3 2 1 0
vendredi 12 septembre 14 vendredi 12 septembre 14
Addition dans Z7 Multiplication dans Z7
+ 0 1 2 3 4 5 6
• Z ={0,1,2,3,4,5,6}
7
0
1
0
1
1
2
2
3
3
4
4
5
5
6
6
0
• a×b=a+a+...+a=b+b+...+b
b fois a fois
• 2+3=5 2 2 3 4 5 6 0 1
• 4+5=9=7+2=2 mod 7
3 3 4 5 6 0 1 2 • 3×5=5+5+5=10+5=3+5=8=7+1=1 mod 7
4 4 5 6 0 1 2 3
5 5 6 0 1 2 3 4 • 3×5=15=(2×7)+1=1 mod 7
6 6 0 1 2 3 4 5 • 6×4=24=(3×7)+3=3 mod 7
vendredi 12 septembre 14 vendredi 12 septembre 14
 Multiplication dans Z7 Multiplication dans Z6
x 0 1 2 3 4 5 6 x 0 1 2 3 4 5 6
• 3×5=(2×7)+1=1 mod 7 0 0 0 0 0 0 0 0
x 0 1 2 3 4 5
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
• 6×4=(3×7)+3=3 mod 7 1 0 1 2 3 4 5 6 1 0 1 2 3 4 5 1 0 1 2 3 4 5 6
2 0 2 4 6 1 3 5 2 0 2 4 0 2 4 2 0 2 4 6 1 3 5
3 0 3 6 2 5 1 4 3 0 3 0 3 0 3 3 0 3 6 2 5 1 4
4 0 4 1 5 2 6 3 4 0 4 2 0 4 2 4 0 4 1 5 2 6 3
5 0 5 3 1 6 4 2 5 0 5 4 3 2 1 5 0 5 3 1 6 4 2
6 0 6 5 4 3 2 1 6 0 6 5 4 3 2 1
vendredi 12 septembre 14 vendredi 12 septembre 14
Multiplication dans Z6 Exponentiation modulaire
x 0 1 2 3 4 5 x 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 1 0 1 2 3 4 5 6 • ab=a×a×...×a
b fois
2 0 2 4 0 2 4 2 0 2 4 6 1 3 5
3
4
0
0
3
4
0
2
3
0
0
4
3
2
3
4
0
0
3
4
6
1
2
5
5
2
1
6
4
3
• 4 =4×4×4×4×4=16×16×4=2×2×4=2 mod 7
5
5 0 5 4 3 2 1 5 0 5 3 1 6 4 2 • 5 =5×5×5×5×5×5=4×4×4=16×4=2×4=8=1 mod 7
6
6 0 6 5 4 3 2 1
vendredi 12 septembre 14 vendredi 12 septembre 14
 Inverse modulaire Division modulaire
• Inverse de a mod N x 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
(noté «1/a mod N» ou
«a-1 mod N») = b tel 1 0 1 2 3 4 5 6 • Diviser a par b revient à multiplier a par l’inverse de
que a×b=1 mod N 2 0 2 4 6 1 3 5 b: a/b=a×b-1 mod n
•3 -1=5 mod 7 3 0 3 6 2 5 1 4 • 2/3=2×3 =2×5=3 mod 7 (3×3=2 mod 7)
-1
•5 -1=3 mod 7
4
5
0
0
4
5
1
3
5
1
2
6
6
4
3
2
• 5 / 4 mod 6 n’est pas défini car 4 n’est pas inversible
•6 -1=6 mod 7 6 0 6 5 4 3 2 1
•2 -1=4 mod 7
vendredi 12 septembre 14 vendredi 12 septembre 14
Inverse modulaire En résumé
x 0 1 2 3 4 5 • Z ={0,1,2,...,N-1} (groupe d’horloge)
N
0 0 0 0 0 0 0 • Opérations d’addition, de soustraction, de
•5 -1=5 mod 6
1 0 1 2 3 4 5 multiplication
•2 -1=??? mod 6 => non
2 0 2 4 0 2 4
• Opération d’exponentiation
défini 3 0 3 0 3 0 3
• Parfois, opération d’inversion
• Seuls 1 et 5 sont 4 0 4 2 0 4 2
inversibles modulo 6 5 0 5 4 3 2 1 • cas particulier fondamental: si p est «premier»,
Zp*={1,2,...,p-1} est constitué d’éléments tous
inversibles
vendredi 12 septembre 14 vendredi 12 septembre 14
 Arithmétique modulaire Exponentiation binaire
• But: effectuer tous les calculs modulo un entier N
• Règle: «tout entier x est remplacé par le reste de la a=∑i=0k-1ai×2i, ai∈{0,1}
division entière de x par N»
• Définition de l’anneau Z : N
• éléments: entiers de 0 à N-1
• Opérations: addition, soustraction, multiplication,
exponentiation, et ... parfois, inversion
vendredi 12 septembre 14 vendredi 12 septembre 14
Exponentiation Exponentiation binaire
• But: calculer x =x.x.x...x (a fois)
a
• Algorithme élémentaire: a-1 multiplications
• ... mais on peut faire mieux x =(((x ) ) )
16 2 2 2 2
• soit 4 multiplications (carrés) au lieu de 15
vendredi 12 septembre 14 vendredi 12 septembre 14
 Exponentiation binaire Complexité du calcul xa
• But: calculer xa • Combien de fois peut-on «diviser a par 2 » ?
• y=1, P=x
• tant que a!=0 faire • si a=2 , k+1 fois (=log (a))
k
2
• si a est impair, y=y.P • en général, de l’ordre de log (a) 2
• a=a/2 (division entière)
• P=P2 • à chaque étape, on fait 1 ou 2 multiplications
• retourner y (1,5 en moyenne)
• La complexité du calcul est donc de l’ordre
de 1,5.log2(a) multiplications
vendredi 12 septembre 14 vendredi 12 septembre 14
Exponentiation binaire Exponentiation modulaire
• But: calculer xa • But: calculer x mod N a
• y=1, P=x
• tant que a!=0 faire • Ne surtout pas calculer x a puis réduire
modulo N !
• si a est impair, y=y.P
• a=a/2 (division entière) • Exemple: 171234567890= 1 mod 16 calcul
• P=P2 immédiat bien que 171234567890 soit
• retourner y impossible à calculer...
• Idée: effectuer les réductions modulaires dès
que possible
vendredi 12 septembre 14 vendredi 12 septembre 14
 Exponentiation binaire PGCD
• But: calculer xa mod N • Plus Grand Commun Diviseur
• y=1, P=x mod N
• tant que a!=0 faire • PGCD(30,42)=PGCD(5×6,6×7)=6
• si a est impair, y=y.P mod N • PGCD(11,17)=1
• a=a/2 (division entière)
• P=P2 mod N • PGCD(22,35)=PGCD(11×2,7×5)=1
• retourner y • Algorithme (récursif):
• Remarque: on ne manipule aucun entier >N2
• PGCD(a,0)=a pour tout a
• PGCD(a,b)=PGCD(b,a mod b)
vendredi 12 septembre 14 vendredi 12 septembre 14
Exponentiation binaire Algorithme d’Euclide
• Calcul de x mod N a
• Entrée: a et b
• |a|=1024 bits =>1536 multiplication modulaires • Sortie: d tel que d=PGCD(a,b)
• a=3=> 2 multiplications modulaires • x=a, y=b
• a=216+1=> 16 multiplications modulaires • Tant que y>0
• Complexité d’une multiplication mod N • r=x-qy (division euclidienne de x par y)
• => environ |N| opérations bit à bit
2
• x=y
• Exponentiation modulaire: environ |N| opérations
3
• y=r
(taille module x2 => temps de calcul x8)
• return x
vendredi 12 septembre 14 vendredi 12 septembre 14
 Inversion mod N Complexité (O(l3) O(l2))
• à tout instant: x =ax +bx et y =ay +by 1 2 3 1 2 3
• X est inversible modulo N ssi il existe Y tel • |y | décroît (y reste de la division de x par y )
1 1 1 1
que X.Y=1 mod N
• y =0 (donc le programme s’arrête)
1
• Exemple: 8.7=1 mod 55 • pgcd(x ,y )=pgcd(y ,x -qy )
1 1 1 1 1
• Seuls les entiers premiers avec N sont
• O(l ) division euclidienne et O(l) itérations
2
inversibles (Bézout)
• Calcul d’inverse: Euclide étendu appliqué à • (z ,z ,...,z ) valeurs prises par y (suite décroissante)
0 1 i 1
X et N: X.u+N.v=1 donc X.u=1 mod N • z <2 , z =0 et z =z -q z avec q =z /z
0
l
i j+1 j-1 j j j j-1 j
X-1=u mod N
• z +z ≤z car q >0 (sauf début) puis Fibonacci
j+1 j j-1 j
vendredi 12 septembre 14 vendredi 12 septembre 14
Algorithme d’Euclide étendu Calcul d’inverse modulaire
• Calculer a mod b: au+bv=1 au=1 mod b
-1
• Entrée: a et b d’au plus l-bit
• Sortie: d=pgcd(a,b),u,v tels que d=a.u+b.v • Inverse de 22 mod 3 (a=22, b=35)
itération x y q
• x=(a,1,0), y=(b,0,1) 0 (22,1,0) (35,0,1) 0
• Tant que y >0 faire 1
1
2
(35,0,1)
(22,1,0)
(22,1,0)
(13,-1,1)
1
1
• r=x-qy (q=quotient euclidienne x 1 par 3 (13,-1,1) (9,2,-1) 1
y1) 4 (9,2,-1) (4,-3,2) 2
• x=y puis y=r 5
6
(4,-3,2)
(1,8,-5)
(1,8,-5)
(0,-35,22)
4
Calcul du pgcd si on ne regarde que x1et y1
1=22x8-5x35
vendredi 12 septembre 14 vendredi 12 septembre 14
 ZN* Théorème d’Euler
• On note Z * l’ensemble des entiers de Z
N N
inversibles modulo N
• Si N est premier, Z *={1,2,...,N-1}
N
• Z * = entiers de 1 à N-1 premiers avec N
N
• Indicatrice d’Euler: Phi(N)=Card(ZN*) si
N=p1e1.p2e2....pkek,
Phi(N)=p1e1-1(p1-1)....pkek-1(pk-1)
ZN*
vendredi 12 septembre 14 vendredi 12 septembre 14
Calcul de Phi(N) Théorème d’Euler
• Z * entiers de 1 à N-1 premiers avec N
N
0 p 2p 3p 4p 5p 6p pq
q 2q 3q 4q
• Phi(p.q)=pq-(q-1)-(p-1)-1=(p-1).(q-1)
vendredi 12 septembre 14 vendredi 12 septembre 14
 Théorème d’Euler Anneau et corps
Quelque soit x∈ZN*, go=1 mod N, o=Card(ZN*) • Si n n’est pas premier, on note Zn
l’ensemble des entiers entre 0 et n-1, muni
Quelque soit k, ga+ko=ga mod N des opérations d’addition modulo n et de
multiplication mod n, c’est un anneau
Les exposants vivent
modulo phi(N)
• Autre anneau: Z
xa
• Si n=p premier, alors Zp est un corps: c’est-
à-dire que c’est un anneau et pour tout
Les éléments vivent élément non nul, il existe un inverse
modulo N modulaire
• Autres corps: Q, R, C
vendredi 12 septembre 14 vendredi 12 septembre 14
Cas p premier Théorème des restes chinois
• Petit théorème de Fermat: Si N=p premier,
on a xp-1=1 mod p pour tout x!=0 mod p • Th: Soit m,n deux entiers tels que pgcd(m,n)=1
• Zp*={1,2,...,p-1} et phi(p)=p-1 • f:(Zmn)→(Zm)x(Zn) f(x)=(x mod m, x mod n) est
un isomorphisme d’anneau
• Zp* est un groupe cyclique ={1,g,g2,...,gp-2}
avec phi(p-1) générateurs g • phi(mn)=phi(m)xphi(n)
• ord(x a mod p)=ord(x)/pgcd(a,p-1) • f (a,b)=an(n mod m) + bm(m
-1 -1 -1 mod n) mod mn
vendredi 12 septembre 14 vendredi 12 septembre 14
 Exemple Génération de
• Résoudre dans Z : x mod 5=3 et x mod 7=4
35
nombres premiers
• f (3,4)=(3x7x(7 mod 5)+4x5x(5 mod 7)) mod 35
-1 -1 -1
• 1=(-2)x7+3x5, donc 5 mod 7=3 et 7 mod 5=3
-1 -1
• Problème de primalité: savoir si un entier x est
• f (3,4)=(3x7x3+4x5x3) mod 35=123 mod 35=18
-1 un nombre premier ou non
• Application: calculer rapidement 2 mod 35 23 • Ce problème a été prouvé dans la classe de
complexité P en 2003 (Agrawal, Kayal, Saxena)
• 2 mod 5=2 23 3 mod 5=3
• 2 mod 7=2 23 5 mod 7=4
• Construire un test de primalité plus efficace
• f (3,4)=18
-1
vendredi 12 septembre 14 vendredi 12 septembre 14
Algorithme de division par
Résidus quadratiques essai (Trial division)
• Entrée: un entier n
• Déf: x est un résidu quadratique mod N est un carré • Sortie: listes des facteurs premiers de n
modulo N ssi il existe y tel que x=y2 mod N
• Soit p un nombre premier impair • Complexité: √n opérations arithmétiques
• x∈Zp* est un résidu quadratique ssi x =1 mod p p-1/2 • b=√n, x=n, i=2
• il y a (p-1)/2 résidus quadratiques dans Zp* • TQ (x>1 et i≤b) faire:
• si p=3 mod 4, tout résidu quadratique x a deux • TQ (i divise x) affiche i, x=x/i, b= √x
racines carrées x(p+1)/4 mod p et -x(p+1)/4 • i=i+1
• si x>1, affiche x
vendredi 12 septembre 14 vendredi 12 septembre 14
 Analyse Miller-Rabin
Tests de primalités • Théorème: Soit N un entier, et considérons l’algo MR
avec comme paramètre N et k.
• Si N est premier, l’algorithme retourne «premier» ou
«pseudo-premier».
• Test de Fermat: pour tout b>0, b p-1=1 mod p
• Réciproquement, si N est composé, l’algorithme
• Problèmes: complexité grande et il existe des retourne «composé» avec proba sup. à 1-4-k.
nombres de Carmichael, non premier, qui • Si N est premier, bN-1=1 mod N pour tout b. Comme Zp
vérifie ce test est un corps, 1 a 2 racines carrées 1 et -1 mod N. Soit
bt=1 mod N, soit il existe 0≤i<s, tel que b2it=1 mod N.
• Test de Solovay-Strassen: pour tout b>0,
• Si N est composé, il a au mois 4 racines carrées, dont 2
bp-1/2=symbole Legendre de x par rapport à p révèlent la factorisation de N.
• Très bien, mais moins efficace que Miller-Rabin • 1=(1 mod p,1 mod q) et -1=(-1 mod p, -1 mod q)
• x=(1 mod p, -1 mod q) et -x=(-1 mod p, 1 mod q) sont
tq pgcd(x+1,N)=q
vendredi 12 septembre 14 vendredi 12 septembre 14
Test de Miller-Rabin Génération de
• Entrée: N entier de n bits et k un entier
• Sortie: pseudo-primalité de N nombres premiers
• Complexité: O(kn3)
• Théorème des Nombres Premiers: Soit
• Si N=2, return «premier» pi(N) le nombre de nombres premiers dans
• Si N pair, return «composé» {2,3,...,N}. p(N)≃N/ln N
• N=2st+1 avec t impair
• Le nombre de nombres premiers ≤2 n est
• Pendant k itérations, faire 2n/n, soit environ 1/n.
• Prendre aléa 0<b<n, x=bt mod N, i=0
• Au bout de k essais aléatoires, on a une
• Si x!=1, TQ x!=N-1, x=x2 mod N, i=i+1 probabilité petite de ne pas tomber sur un
• Si i=0 ou x=1, return «composé» FinPendant nombre premier ≤(1-1/n)k
• return «pseudo-premier»
vendredi 12 septembre 14 vendredi 12 septembre 14
 Algorithmes de factorisation RSA-CRT
• Problème de la factorisation: étant donné un entier • Génération des clés: publique (e,N), privée
(dp,dq,p,q)
N, trouver des facteurs non-triviaux (différents de 1
et N) de N • Générer 2 nombres premiers p et q
aléatoirement de 1024 bits
• Plusieurs algorithmes dont la complexité est
exponentielle en n (n=log(N)). • Calculer N=pq, puis phi(N)=(p-1)(q-1)
• Meilleur algorithme (NFS) a une complexité en • Prendre e tel que pgcd(e, phi(N))=1 et
c(N)=exp(O(log(N)1/3 loglog(N)2/3)) inverser e mod phi(N)=d
• Pour n=1024, c(n)=2 80
• dp=d mod (p-1)
• dq=d mod (q-1)
vendredi 12 septembre 14 vendredi 12 septembre 14
RSA RSA-CRT
• Génération des clés: publique (e,N), privée (d,N)
• Générer 2 nombres premiers p et q
• Chiffrement: f(x)=x mod N e
aléatoirement de 1024 bits
• Calculer N=pq, puis phi(N)=(p-1)(q-1) • Déchiffrement: f (y) clé privée (dp,dq,p,q)
-1
• Prendre e tel que pgcd(e, phi(N))=1 et inverser e • c =(y mod p)
1
dp mod p
mod phi(N)=d • c =(y mod q)
2
dq mod q
• Chiffrement: f(x)=x mod N e
• Combiner c1 et c2 avec le théorème des
restes chinois: facteur 4 en temps
• Déchiffrement: f (y)=y mod N
-1 d
vendredi 12 septembre 14 vendredi 12 septembre 14
 Sécurité de RSA Sécurité de RSA
• RSADP (Decryption Problem):
• RSADP (Problème de déchiffrement)
• Entrée: (e,N) clé publique RSA et message chiffré y
• RSAKRP (Problème de retrouver clé secrète)
• Sortie: x tel que y=xe mod N
• RSAEMP (Problème multiple exposant)
• RSAKRP (Key Recovery Problem):
• RSAOP (Problème de trouver l’ordre)
• Entrée: (e,N) clé RSA
• RSAFP (Problème de la factorisation)
• Sortie: d tel que xed mod N=x pour tout x∈ZN*
RSAEMP RSAFP
• RSAEMP (Exponent Multiple Problem):
• Entrée: Module RSA N
RSADP RSAKRP RSAOP
• Sortie: entier k tel que xk mod N=1 pour tout x∈ZN*
vendredi 12 septembre 14 vendredi 12 septembre 14
Sécurité de RSA RSA PKCS#1 v1.5
• On peut montrer qu’il est difficile de trouver les
• RSAOP (Order Problem): bits de poids faible de x connaissant xe mod N
• Entrée: N module RSA
• Eviter attaque petit exposant
• Sortie: phi(N)
• RSAFP (Factorization Problem):
• Attaque par broadcast
• Entrée: N module RSA • Attaque même module
• Sortie: p et q tels que N=pq • Randomisation
• Attaque par canaux auxiliaires
• Sécurité sémantique sous le problème RSA
vendredi 12 septembre 14 vendredi 12 septembre 14
 Sécurité de RSA
Chiffrement El Gamal
• Problème broadcast
• Problème si le message est trop petit m<N 1/e, c’est
• Clé publique y=g et clé secrète x
x
facile à inverser
• Chiffrement: E(m;r)=(g ,m.y )=(A,B)
r r
• Chiffrement déterministe • Déchiffrement: D(A,B)=B/A =m.y /g
x r rx=m
• Attention: D(E(m))=m mod N • Sécurité:
• Solution: padding • Un élément au hasard gr apparaît comme
• PKCS #1 version 1.5: P(m)=00||01||random||m un élément random. La multiplication
opère comme le XOR dans le OTP
• PKCS #1 version 2: OAEP
vendredi 12 septembre 14 vendredi 12 septembre 14
RSA-OAEP
Signature
• Aujourd’hui, on sait comment utiliser RSA
• Réduction: si on sait attaquer RSA avec une
attaque IND-CPA, alors on sait casser plus
efficacement le problème RSA
vendredi 12 septembre 14 vendredi 12 septembre 14
 Signature RSA
• Signature: S(m)=f(m) mod N d
• Vérification: S(m) mod N = f(m) ?
e
• Problème: si on a une signature s1 pour le message
Signature m1 et s2 pour le message m2, alors s1xs2 mod N est
une signature pour le message m1xm2 mod N
• Signer le haché du message. Collision sur H ?
• f(m) est une fonction de padding:
• PKCS #1 v1.5 f(m)=00||02||FF...FFFF||H(m)
• PKCS #1 v2.0 RSA-PSS(m)
vendredi 12 septembre 14 vendredi 12 septembre 14
RSA-PSS
• Schéma de signature randomisé
• si on signe le même message 2 fois,
on n’aura pas la même signature
Signatures • Hash et MGF sont des fonctions de
hachage (concaténé pour la seconde)
• Paddings contient en info sur la fonction
de hachage
• salt contient le nombre d’octets de la
taille de la fonction de hachage
vendredi 12 septembre 14 vendredi 12 septembre 14
 Preuve Zero-Knowledge Schéma d’authentification de Schnorr
• Preuve de connaissance d’un secret
• Paramètres généraux: (p,q,g) tels que g engendre un
• Après un échange de message, le Vérifieur est certain que le sous-groupe de taille q dans le groupe Zp*
Prouveur connaît un secret avec probabilité 1-280
• Mais le Vérifieur n’a aucune information sur le secret détenu • Clé publique/secrète d’un utilisateur: (g x mod p,x)
par le prouveur
• Preuve Zero-Knowledge:
• Problème d’isomorphisme de graphes est conjecturé difficile
k aléa t=gk mod p
mod q
Prou c ∈ [0,230[ Vérifi
veur eur
z
z=k+cx [q] t=?gz/yc [q]
Prouveur attrapé avec proba 1-230
vendredi 12 septembre 14 vendredi 12 septembre 14
Preuve Zero-Knowledge Signature DSA/ECDSA
• Le prouveur et le vérifieur connaissent les graphes G0 et G1
• Le prouveur connaît un isomorphisme p entre ces graphes • Adaptation de la signature de Schnorr breveté
• Le vérifieur avec proba 1/2 attrape le prouveur s’il ment • Paramètres généraux: (p,q,g) tels que g engendre un
• Le prouveur qui connaît le secret répond toujours correctement sous-groupe de taille q dans le groupe Zp*
p: isomorphisme
entre G0 et G1 H • générer q de 160 bits, puis p=2qR+1 avec R random
H=h(G1)
de 1024-160 bits
c
• g aléatoire et calculer g mod p≠1
c au hasard {0,1}
(p-1)/2R
Prouv Vérifie
f
si c=0, f=poh
si c=1, f=h
eur ur
f(Gc)=H • Clé publique/secrète d’un utilisateur: (p,q,g,y=g x
mod p) et x<q
Vérifieur n’apprend aucune information sur p !
vendredi 12 septembre 14 vendredi 12 septembre 14
 Signature DSA
• Vérification Signature
• Génération Signature • 0<s1,s2<q
• s1=(gk mod p) mod q • w=s2-1 mod q Echange de clés
• s2=(H(m)+s1*x)/k mod q • u1=H(m)*w mod q
• S(m)=(s1,s2) • u2=s1*w mod q
• v=(gu1*yu2 mod p) mod q =? s1
vendredi 12 septembre 14 vendredi 12 septembre 14
Faux échange de clé
pk
Alice Epk(r) Bob
aléa r
• Clé commune r • utilisé dans SSHv1 et SSL
• Bob a le contrôle de la clé
• Avantage: si Alice prouve sa
connaissance de sa clé, elle
s’authentifie
vendredi 12 septembre 14 vendredi 12 septembre 14
 Diffie-Hellman key Echange de clé: attaque active
exchange Man-in-the-middle Attacks
gx
• Alice: ga
• Bob:
gx’
• génère a au hasard
• génère b au hasard Alice Eve gy Bob
• calcule ga
• calcule gb gy’
• réception de gb, gb • réception de ga,
calcule K=(gb)a=gab
calcule K=(ga)b=gab
gxy’ gx’y
Forward-secure: pas de clé long-terme
vendredi 12 septembre 14 vendredi 12 septembre 14
Clés éphémères et forward-secrecy Diffie-Hellman signé v1
• Forward-secure: les clés de session ne sont pas
A, gx, signA(gx)
mises en danger par la fuite des clés long-terme aléa x aléa y
Alice B, gy, signB(gy) Bob
• Moyen d’y parvenir: utiliser des clés publiques Vérifie Vérifie
éphémères pour protéger la clé de session
• éventuellement en combinaison avec des clés
• Evite les attaques par le milieu: impossible pour
long-terme
un attaquant de fournir signA(gx’)
• Les clés privées éphémères sont effacées • Rejeu possible: si (gx,signA(gx)) est capturé, il
sitôt l’échange terminé
peut être utilisé pour s’authentifier comme A,
• ex: «server key» de SSH v1 mais on ne peut pas calculer la clé
correspondante
vendredi 12 septembre 14 vendredi 12 septembre 14
 Station-To-Station Protocol
Usurpation d’identité
aléa x A, gx
aléa y
Alice B, gy, signB(gy,gx) Bob
Vérifie
A, signA(gx,gy)
Vérifie
• Bob est une banque
• Alice et Eve des clients
• Le meilleur des deux mondes: • Alice crédite sont compte avec de la
• évite les attaques par le milieu: impossible monnaie électronique
pour un attaquant de fournir signB(gx’,gy)
• la banque crédite le compte d’Eve
• évite le rejeu: la valeur DH est aussi signée
• Mais...
vendredi 12 septembre 14 vendredi 12 septembre 14
Usurpation d’identité Diffie-Hellman signé v3
A,gx aléa x A, gx
E,gx aléa y
Alice B, gy, signB(B,gy,gx,A) Bob
B,gy,signB(gx,gy) A, signA(A,gx,gy,B)
Alice Bob
B,gy,signB(gx,gy) Eve Vérifie Vérifie
A,signA(gy,gx)
E,signE(gy,gx)
• Tous les messages envoyés par Alice sont
vus par Bob comme venant d’Eve
• Eve ne connaît pas la clé g xy
vendredi 12 septembre 14 vendredi 12 septembre 14
vendredi 12 septembre 14 vendredi 12 septembre 14
Gestion des clés
vendredi 12 septembre 14 vendredi 12 septembre 14
vendredi 12 septembre 14
vendredi 12 septembre 14