D31: Protocoles Cryptographiquesmeloni.univ-tln.fr/cours/pld.pdf · Protocole de Di e-Hellman Alice...

D31: Protocoles CryptographiquesCryptosystemes bases sur le probleme du logarithme discret

Nicolas Meloni

Master 2: 1er semestre(2014/2015)

Nicolas Meloni — D31: Protocoles Cryptographiques 1/29

Introduction

Introduit des 1976 par Diffie et Hellman comme basepour leur protocole d’echange de cle

Utilise par ElGamal en 1984 pour construire un schema dechiffrement a cle publique ainsi qu’un protocole designature

Probleme difficile sur lequel repose la cryptographie baseesur les courbes elliptiques

Introduction

Definition

Soit G un groupe cyclique d’ordre n. G = {g i : 0 ≤ i ≤ n− 1}pour un certain g ∈ G . Pour tout h ∈ G , il existe un uniqueentier k ∈ {0, . . . , n − 1} tel que h = g k que l’on appellelogarithme discret de h (en base g). Resoudre le probleme dulogarithme discret (PLD) c’est resoudre l’equation en k :

k ∈ {0, . . . , n − 1}, h = g k .

Remarque

La fonction f : g 7→ g k est une fonction a sens unique maispas une fonction a trappe!

Protocole de Diffie-Hellman

Alice BobChoisissent G =< g >

Genere a ∈ N Genere b ∈ N

Calcule hA = g a Calcule hB = gb

Calcule g ab = haB Calcule g ab = hbA

Alice et Bob partage le secret g ab

Securite du protocole

Un adversaire voit passer sur le reseau g , hA, hB

Il doit calculer g ab a partir de g , g a, gb, c’est ce qu’onappelle le probleme de Diffie-Hellman calculatoire(PDHC).

Un sous probeme est egalement considerer parfois, leprobleme de Diffie-Hellman decisionel (PDHD): a partirde g , g a, gb et h ∈ G a-t’on h = g ab?

Si un adersaire peut resoure le PLD sur G il peutsimplement resoudre le PDHC

De meme, s’il peut resoudre le PDHC il peut resoudre lePDHD

Il existe cependant des groupes pour lesquels le PDHDest facile alors que le PDHC reste dur

Le PLD et le PDHC ne sont pas prouves equivalents, lasecurite des systemes a base de logarithme discret reposeen general sur la difficulte du PDHC et non directementdu PLD

Le cryptosysteme El Gamal

Le cryptosysteme

Soit p un nombre premier, on note Fp = Z/pZ le corps a pelements. Soit α un element primitif de F∗p. Soient enfin k unentier et β = αk . On definit:

P = F∗pC = F∗p × F∗p

Kpub = (p, α, β)

Ksec = k

Chiffrement

Soit m ∈ P ,E (Kpub,m) = (y1, y2)

ou y1 = αr mod p, y2 = mβr mod p et r est un entiergenere aleatoirement.

Dechiffrement

Le chiffre est c = (y1, y2),

D(Ksec , c) = y2(y k1 )−1 mod p.

Securite du systeme El Gamal

Le niveau de securite est directement lie au probleme deDiffie-Hellman:

la fonction de chiffrement est bien a sens unique si lePDHC est difficile,

le systeme est semantiquement sur si le PDHD est diffcile,

le systeme doit etre modifie pour devenir resistant auxattaques a chiffres choisis.

Resolution du PLD

G =< g > est un groupe d’ordre p − 1, on cherche acalculer l’entier k tel que h = g k pour un certain h ∈ Gdonne.

Algorithme naıf

Il ”suffit” donc d’enumerer les puissances de g jusqu’a obtenirh.Complexite: O(p)

Resolution du PLD

Algorithme de Shanks (pas de bebe, pas de geant)

Il consiste a choisir un entier m < k et a ecrire k sous la formek = qm + r ou q et r sont, respectivement, le quotient et lereste de la division de k par m.

On calcule les gmj

On calcule les hg i

lorsqu’on obtient une collision on a bien

gmj = hg i ⇔ gmj+i = h.

La complexite est optimale en choisissant m = d√pe. On alorsun algorithme en O(

√p).

Resolution du PLD

Algorithme Rho de Pollard

Repose sur le paradoxe des anniversaires.

Genere aleatoirement des elements de la forme g aihbi

lorsqu’on obtient une collision on a:

g aihbi = g ajhbj ⇒ k ≡ ai − ajbj − bi

En moyenne, il faut√p etapes pour obtenir une collision. On

a donc un algorithme en O(√p) en moyenne.

Resolution du DLP

Algorithme de Pohlig-Hellman

Permet d’accelerer le calcul lorsque l’ordre du groupe n(n = p − 1 dans le cas d’ElGamal)peut etre factorise, i.e.

n =r∏

pcii ,

grace au theoreme des restes chinois.Complexite: O(c

√q) ou qc est la plus grande puissance

premiere divisant n.

Courbes elliptiques (ECC)

Courbe elliptique sur un corps K (car(K ) >3)

Soient a, b ∈ K deux tels que 4a3 + 27b3 6= 0. Une courbeelliptique est l’ensemble des solutions (x , y) ∈ K×K del’equation

E : y 2 = x3 + ax + b,

plus un point a l’infini note O. On note generalement E (K)cet ensemble de points.

Loi de groupe d’un courbe elliptique

Propriete

Une courbe elliptique peut etre munie d’un structure degroupe commutatif. La somme R = (x3, y3) de deux pointsP = (x1, y1),Q = (x2, y2) s’obtient comme suit:

−P = (x1,−y1)

x3 = λ2 − x1 − x2, y3 = λ(x1 − x3)− y1 ou

{y2−y1

x2−x1si P 6= ±Q

3x21 +a

2y1siP = Q

R = O si P = −QP +O = O + P = P

Loi de groupe sur R

R = −(P + Q)

R = (P + Q)

Figure : Courbe y2 = x3 − x sur R

Loi de groupe sur R

R = −(P + Q)

R = (P + Q)

Loi de groupe sur R

R = −(P + Q)

R = (P + Q)

Loi de groupe sur R

R = −(P + Q)

R = (P + Q)

Loi de groupe sur R

R = −(P + Q)

R = (P + Q)

Loi de groupe sur R

R = −(P + Q)

R = (P + Q)

Loi de groupe sur R

Les courbes sur R ne sont pas utilisees dans la pratique:

impossible de representer les reels en machine,

le PLD est ”facile” a resoudre sur Q.

C’est pour cela qu’on utilise des courbes definies sur un corpsfini, en general Fp ou F2n .

Un exemple de courbe sur F11

Considerons la courbe E : y 2 = x3 + x + 6 definie sur le corpsF11.

x 0 1 2 3 4 5 6 7 8 9 10y 0 1 2 3 4 5 6 7 8 9 10

x3 + x + 6 6 8 5 3 8 4 8 4 9 7 4y 2 0 1 4 9 5 3 3 5 9 4 1