D31: Protocoles Cryptographiquesmeloni.univ-tln.fr/cours/pld.pdf · Protocole de Di e-Hellman Alice Bob Choisissent G =< g > G en ere a 2N G en ere b 2N Calcule h A =ga Calcule

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

hA

hB

Calcule g ab = haB Calcule g ab = hbA

Alice et Bob partage le secret g ab






hA

hB








hA

hB








hA

hB








hA

hB








hA

hB





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

mod p

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∏

i=1

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

x

y

Q

P

R = −(P + Q)

R = (P + Q)

Figure : Courbe y2 = x3 − x sur R


Loi de groupe sur R

x

y

Q

P

R = −(P + Q)

R = (P + Q)



Loi de groupe sur R

x

y

Q

P

R = −(P + Q)

R = (P + Q)



Loi de groupe sur R

x

y

Q

P

R = −(P + Q)

R = (P + Q)



Loi de groupe sur R

x

y

Q

P

R = −(P + Q)

R = (P + Q)



Loi de groupe sur R

x

y

Q

P

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

E (F11) = { (2, 4), (2, 7),(3, 5), (3, 6),(5, 2), (5, 9),(7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)}




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

E (F11) = { (2, 4), (2, 7),(3, 5), (3, 6),(5, 2), (5, 9),(7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)}




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

E (F11) = { (2, 4), (2, 7),(3, 5), (3, 6),(5, 2), (5, 9),(7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)}




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

E (F11) = { (2, 4), (2, 7),(3, 5), (3, 6),(5, 2), (5, 9),(7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)}




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

E (F11) = { (2, 4), (2, 7),(3, 5), (3, 6),(5, 2), (5, 9),(7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)}




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

E (F11) = { (2, 4), (2, 7),(3, 5), (3, 6),(5, 2), (5, 9),(7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)}




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

E (F11) = { (2, 4), (2, 7),(3, 5), (3, 6),(5, 2), (5, 9),(7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)}




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

E (F11) = { (2, 4), (2, 7),(3, 5), (3, 6),(5, 2), (5, 9),(7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)}


Addition de deux points sur E (F11)

Considerons les points P = (3, 6) et Q = (7, 9). Pour obtenirle point R = P + Q on calcule:

λ = (y1 − y2)(x1 − x2)−1 ≡ (−3)× (−4)−1 ≡ 9 mod 11

x3 = λ2 − x1 − x2 ≡ 92 − 3− 7 ≡ 5 mod 11

y3 = λ(x1 − x3)− y1 ≡ 9(3− 5)− 6 ≡ 9 mod 11

Ainsi P + Q = (5, 9).


Loi de groupe sur Fp

1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q

Figure : Courbe y2 = x3 + x + 6 sur F11



1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q




1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q




1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q




1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q




1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q




1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q




1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q




1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q




1 2 3 4 5 6 7 8 9 10 110

1

2

3

4

5

6

7

8

9

10

11

x

y

P

Q

R = −(P + Q)

R = P + Q



Le groupe E (F11)

En rajoutant le point a l’infini O on obtient 13 points surla courbe E

Le groupe est d’ordre premier et donc est engendre parn’importe quel element non nul

Par exemple prenons P = (2, 7) comme generateur on a

E (F11) = {[i ]P : i = 0 . . . 12} .

Notation

Le groupe (F∗p,×) est note multiplicativement (G = {αi})alors que le groupe des points d’une courbe elliptique est note,par convention, additivement.


Le groupe E (F11)

En rajoutant le point a l’infini O on obtient 13 points surla courbe E

Le groupe est d’ordre premier et donc est engendre parn’importe quel element non nul

Par exemple prenons P = (2, 7) comme generateur on a

E (F11) = {[i ]P : i = 0 . . . 12} .

Notation

Le groupe (F∗p,×) est note multiplicativement (G = {αi})alors que le groupe des points d’une courbe elliptique est note,par convention, additivement.


Nombre de points d’un courbe elliptique

Theoreme

Soit E une courbe elliptique definie sur un corps fini Fq.L’ordre du groupe E (Fq), note #E (Fq), verifie:

q + 1− 2√q ≤ #E (Fq) ≤ q + 1 + 2

√q.

Une courbe sur Fq possede, environ, q points

Il n’existe pas d’algorithme sous exponentiel pourresoudre le PLD sur une courbe bien choisie

C’est donc un objet particulierement interessant pour lacryptographie


Protocole de Diffie-Hellman avec ECC

Alice BobChoisissent Fp ,E et P ∈ E tel que

E(Fp) =< P >Genere a ∈ N Genere b ∈ N

Calcule QA = [a]P Calcule QB = [b]P

QA

QB

Calcule [ab]P = [a]QB Calcule [ab]P = [b]QA






QA

QB







QA

QB







QA

QB







QA

QB







QA

QB



El Gamal avec ECC

Le cryptosysteme

Soit E (Fp) une courbe elliptique d’ordre premier n. SoientP ,Q ∈ E (Fp) deux points tels que Q = [k]P . On definit:

P = E (Fp)

C = E (Fp)× E (Fp)

Kpub = (E (Fp),P ,Q)

Ksec = k



Chiffrement

So it M ∈ E (Fp),

E (Kpub,M) = (P1,P2)

ou P1 = [r ]P ,P2 = M + [r ]Q et r est un entier generealeatoirement.

Dechiffrement

Le chiffre est C = (P1,P2),

D(Ksec ,C ) = P2 − [k]P1.


Compression de point

Un chiffre contient deux points soit 4 coordonnees, onutilise l’equation de la courbe pour limiter la bandepassante

Compression

Compress(P = (x , y)) = (x , y mod 2)

Decompression

Decompress(x , i) :

z ← x3 + ax + b

y ←√z mod p

si y ≡ i mod p on retourne (x , y) et (x , p − y) sinon


ICIESElliptic Curve Integrated Encryption Scheme

Parametres

Message: m ∈ F∗pCle publique: E (Fp) d’ordre n, P ,Q ∈ E (Fp)

Cle privee: k tel que P = [k]Q


ICIESElliptic Curve Integrated Encryption Scheme

Chiffrement

r genere aleatoirement

E (Kpub,m) = (Compress([r ]P), xqm mod p)) ou[r ]Q = (xq, yq) et xq 6= 0

Dechiffrement

Chiffre C = (c1, c2)

D(Kpri ,C ) = c2(xq)−1 mod p ou(xq, yq) = [k]Decompress(c1)


Securite des primitives a cle publique

Complexite des meilleures attaques

AES-n: O(n)

ECC sur Fp: O(√p)

DLP sur F∗p: O(Lp[1/2, 1])

RSA-n: O(Ln[1/3, 1.92])

Niveau de securite

Securite (bits) AES ECC RSA F∗p80 80 160 1024 1024

128 128 256 3072 3072256 256 512 15360 15360


Documents

D31: Protocoles Cryptographiquesmeloni.univ-tln.fr/cours/pld.pdf · Protocole de Di e-Hellman Alice Bob Choisissent G =< g > G en ere a 2N G en ere b 2N Calcule h A =ga Calcule