Cryptographie à clef publique R.S.A.

DLP & Diffie-Hellman El Gamal

Chiffrement à clef publique ou asymétrique

Pierre-Louis Cayrel

Université de Limoges, XLIM-DMI,

123, Av. Albert Thomas
87060 Limoges Cedex France
[Link].10
[Link]@[Link]

Licence professionnelle Administrateur de Réseaux

et de Bases de Données
IUT Limoges

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Sommaire

Cryptographie à clef publique

R.S.A.

DLP & Diffie-Hellman

El Gamal

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Motivations

I Systèmes cryptographiques à clé secrètes

I pratiquement sûrs
I efficaces en termes de temps de calcul.
I Mais nouvelles interrogations :
IAvant d’utiliser un système de chiffrement à clé secrète, comment
convenir d’une clé ?
I Comment établir une communication sécurisée entre deux entités

sans échange préalable de clef ?

⇒ Solution apportée par Diffie et Hellman (1976)
I systèmes cryptographiques à clé publique

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Cryptographie à clef publique

Fig.: La cryptographie symétrique

Fig.: La cryptographie asymétrique

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Cryptographie asymétrique
——————————————————————–

——————————————————————–
Fig.: La cryptographie asymétrique : Première Étape

Alice génère deux clés. La clé publique (verte) qu’elle envoie à Bob et la
clé privée (rouge) qu’elle conserve précieusement sans la divulguer à
quiconque.
Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Cryptographie asymétrique
——————————————————————–

——————————————————————–
Fig.: La cryptographie asymétrique : Deuxième et Troisième Étape

Bob chiffre le message avec la clé publique d’Alice et envoie le texte

chiffré. Alice déchiffre le message grâce à sa clé privée.
Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Cryptographie asymétrique

Fondée sur l’existence de fonctions à sens unique.

Il est simple d’appliquer cette fonction à un message, mais extrêmement
difficile de retrouver ce message à partir du moment où on l’a transformé.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Déroulement

Bob souhaite pouvoir recevoir des messages chiffrés de n’importe qui.

I Il génère une valeur (clef publique) à partir d’une fonction à sens
unique.
I Il diffuse la clef publique, mais garde secrète l’information
permettant d’inverser cette fonction (clef secrète).

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

R.S.A.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Ronald Rivest, Adi Shamir et Leonard Adleman

Fig.: Ronald Rivest, Adi Shamir et Leonard Adleman, dans A Method for
Obtaining Digital Signatures and Public-key Cryptosystems ont eu l’idée
d’utiliser les anneaux Z/nZ et le petit théorème de Fermat pour obtenir des
fonctions trappes, ou fonctions à sens unique à brèche secrète.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

R.S.A.

I C’est à l’heure actuelle le système à clef publique le plus utilisé

(Netscape, la carte bancaire française, de nombreux sites web
commerciaux).
I RSA repose sur le calcul dans les groupes Z/nZ, plus précisément
sur l’exponentiation modulaire. Voici une description des principes
mathématiques sur lesquels repose l’algorithme RSA.
I Il est toutefois important de remarquer que le passage des principes
à la pratique requiert de nombreux détails techniques qui ne peuvent
pas être ignorés, sous peine de voir la sécurité du système anéantie.
Par exemple, il est recommandé d’encoder le message en suivant
l’OAEP.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

R.S.A.

Alice veut envoyer M à Bob.

I M un entier représentant un message.
I Bob choisit p et q deux nombres premiers et on note n leur produit.
I Bob choisit e un entier premier avec p − 1 et q − 1.
I On a ϕ(n) = (p − 1)(q − 1) donc e est premier avec ϕ(n) et on
obtient (via Bézout) qu’il est inversible modulo ϕ(n), i.e. il existe un
entier d tel que ed ≡ 1 (mod ϕ(n)).
I Le message chiffré sera alors représenté par :

C = Me (mod n)
I Pour déchiffrer C , on calcule d l’inverse de e mod ϕ(n), ensuite on
calcule C d mod n.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

R.S.A.
I On a alors,

Cd (mod n) ≡ (M e )d (mod n) ≡ M ed (mod n)

I Comme ed ≡ 1 (mod ϕ(n)) par définition de modulo, on a

ed = 1 + kϕ(n), avec k ∈ N.
I D’où,

M ed (mod n) ≡ M · M kϕ(n) (mod n) ≡ M · (M ϕ(n) )k (mod n)

I Or si x est premier avec n; on a x ϕ(n) ≡ 1 (mod n), d’après le
théorème d’Euler.
I Donc finalement, si le message M est premier avec n :

Cd ≡ M (mod n).
Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

R.S.A.

I Le cas où le message M n’est pas premier avec n est un peu plus
compliqué mais le résultat reste le même :

Cd ≡ M (mod n).
I (n, e) est appelé clef publique
I (n, d) est appelé clef privée.
I pour chiffrer, il suffit de connaı̂tre e et n.
I pour déchiffrer, il faut d et n, autrement dit connaı̂tre la
décomposition de n en facteurs premiers.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Alice Bob

M
choisit p et q
e premier avec p − 1 et q − 1

calcule n = p × q
d tel que ed ≡ 1 (mod ϕ(n))

←− envoie (n, e) à Alice

calcule C = M e (mod n)
et l’envoie à Bob −→

calcule C d (mod n)
et en déduit M

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Le cryptosystème RSA : Exemple

Prenons p = 47 et q = 59.
I On calcule n = p.q = 47.59 = 2773
I On choisit e, premier par rapport à φ(n) . Ex : e = 17.
I On calcule alors, par l’algorithme d’Euclide étendu1 , d tel que
d.e = 1 mod (p − 1)(q − 1), soit d = 157.
Clef publique : (e, n) = (17, 2773)
Clef privé : d = 157.
I Chiffrement du message M = 01000010 = 66 :

C = Me mod n = 6617 mod 2773 = 872

I Déchiffrement de C :

Cd mod n = 872157 mod 2773 = 66

1 sous Maple : igcdex

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

RAPPEL : Exponentiation rapide modulaire

Exercice :
Calcul de 5144721 mod 17 (E )

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Exponentiation rapide modulaire

51447 = 3026 × 17 + 5 donc (E ) ≡ 521 mod 17

1. Décomposition de 21 en binaire : 21 = 24 + 22 + 20
i
2. Calcul de {52 mod 17}0≤i≤4
0
I i = 0 : 52 = 5 mod 17
1
I i = 1 : 52 = 52 = 25 = 8 mod 17
22
I i =2:5 = 82 = 64 = 13 = −4 mod 17
3
I i = 3 : 52 = (−4)2 = 16 = −1 mod 17
4
I i = 4 : 52 = (−1)2 = 1 mod 17
4 2 0
3. On en déduit : 521 = 52 × 52 × 52 = 1 × (−4) × 5 = −20 = 14
mod 17

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Le cryptosystème RSA : Exercice

Prenons p = 29, q = 31 et e = 13. Utilisé le protocole RSA pour chiffrer

et déchiffrer M = 123

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Le cryptosystème RSA : Exercice

I Les variables étant données, p = 29, q = 31, e = 13, m = 123;

I Nous calculons : n = p × q = 899
I (p − 1) × (q − 1) = 840
I d = 517 car e × d = 13 × 517 = 8 × (p − 1) × (q − 1) + 1
I Pour chiffrer,
c = 12313 mod 899 = 402
I Et pour déchiffrer,

m = 402517 mod 899 = 123

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Sécurité du cryptosystème RSA

I Le vrai but de l’attaquant : découvrir le texte en clair !

I Calculer d à partir de (n, e) ≡ factoriser n.
⇐ : trivial (cf génération des clefs)
⇒ : Soit s = max{t ∈ N : 2t |ed − 1}. On pose k = ed−1
2s
. Alors, soit
a ∈ Z est premier avec n.
I l’ordre de ak dans Zn ∈ {2i ; 0 ≤ i ≤ s}(aφ(n) = 1 mod n)
I si l’ordre de ak mod p 6= l’ordre de ak mod q, alors
t
∃t ∈ [0, s[/1 < pgcd(a2 k
− 1, n) < n
On a ainsi trouvé un facteur non trivial de n.
I (Résultat récent) : Casser RSA est équivalent à la factorisation de n
[Coron2004].

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Sécurité du cryptosystème RSA

I Limites actuelles de factorisation : ≈ 200 chiffres

I Record actuel2 : RSA200 (200 chiffres décimaux)
Bahr, Boehm, Franke and Kleinjung - 9 mai 2005.
1
I Si la clef secrète d est petite (de l’ordre de n 4 ) :
I attaque utilisant l’algorithme des fractions continues (algorithme
LLL)
I permet de calculer d à partir de n et e.

2 [Link]

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

DLP & Diffie-Hellman

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Merkle-Hellman-Diffie

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

DLP & Diffie-Hellman

Autre problème difficile : Discret Logarithme Problem

I Definition (Logarithme discret)
Soit G =< g >= {g i }0≤i<n un groupe monogène fini d’ordre n.
Soit h ∈ G . Alors le logarithme discret de h en base g , noté logg h,
est l’unique entier x tel que h = g x (0 ≤ x < n).
I DLP consiste alors à résoudre le problème suivant :
Etant donné G , g , h, trouver x = logg h.
I Exemple : p = 97 et G = Z/97Z = 1, 2, ..., 96 = {5i }0≤i<96 ;
532 = 35 mod 97 ⇒ log5 35 = 32 dans Z/97Z.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Protocole d’échange de clefs de Diffie-Hellman

Alice et Bob veulent partager une clef secrète K . On suppose que les
données G , n = |G | et g sont publiques.
I Alice choisit un entier 1 ≤ a ≤ n − 1 au hasard.
I Alice calcule A = g a et l’envoie à Bob.
I Bob choisit un entier 1 ≤ b ≤ n − 1 au hasard.
I Bob calcule B = g b et l’envoie à Alice.
I Alice est en mesure de calculer B a et Bob de calculer Ab . La clef
commune est donc
K = g ab = Ab = B a .

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Protocole d’échange de clé de Diffie-Hellman

Alice Bob

génère a génère b
A = g a mod p B = g b mod p
A −→
←− B
(dispose de [a, A, B, p]) (dispose de[b, A, B, p]
Clé secrète : K = B a mod p Clé secrète : K = Ab mod p

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Protocole d’échange de clé de Diffie-Hellman

Fig.: [Link]/2004/talks/fairbrother/

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Protocole d’échange de clé de Diffie-Hellman (exemple)

1. Alice et Bob choisissent un nombre premier p et une base g . Dans

notre exemple, p = 23 et g = 3
2. Alice choisit un nombre secret a = 6
3. Elle envoie à Bob la valeur g a mod p = 36 mod 23 = 16
4. Bob choisit à son tour un nombre secret b = 15
5. Bob envoie à Alice la valeur g b mod p = 315 mod 23 = 12
6. Alice peut maintenant calculer la clé secrète :

(g b mod p)a mod p = 126 mod 23 = 9

7. Bob fait de même et obtient la même clé qu’Alice :

(g a mod p)b mod p = 1615 mod 23 = 9

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Protocole d’échange de clé de Diffie-Hellman (exercice)

1. Supposons qu’Alice et Bob partagent p = 233 et g = 45 :

2. si Alice choisit a = 11 et Bob b = 20, alors :
3. Quelle est leur clef secrète commune ?

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Protocole d’échange de clé de Diffie-Hellman (corrigé)

g a = 4511 mod 233 = 147, g b = 4520 mod 233 = 195,

I (g b )a mod p = 19511 mod 233 = 169 et (g a )b mod p = 14720
mod 233 = 169.
I Alice et Bob disposent d’une clé privée commune : k = 169.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Sécurité de DH

I Problème de DH :
I connaissant G , g , A = g a et B = g b , calculer K = g ab .
I A l’heure actuelle, résoudre DLP est la seule méthode générale
connue pour résoudre DH.
I MAIS : pas de preuve que résoudre DLP ≡ résoudre DH.
I Choix du groupe G : G = F∗p , G = E (Fp ), etc.
I Attention au bon choix des paramètres.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Le cryptosystème de El Gamal

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

El Gamal

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Le cryptosystème de El Gamal

Données publiques pré-requise :

I (G , .) =< g > un groupe cyclique d’ordre n

Génération des clefs

I Bob choisit a ∈ [1, n − 1] et calcule A = g a dans G .
I Clef publique : (G , g , n, A).
I Clef secrète : a.

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Le cryptosystème de El Gamal (2)

Chiffrement : Alice souhaite envoyer le message M ∈ G à Bob

I Alice récupère la clef publique (G , g , n, A) de Bob.
I Alice choisit au hasard k ∈ [1, n − 1]
I Le message chiffré qu’Alice envoit à Bob est C = (y1 , y2 ) avec

y1 = g k et y2 = [Link]

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Le cryptosystème de El Gamal (3)

Déchiffrement
I Bob recoit le message chiffré C = (y1 , y2 )
I Il lui suffit alors de calculer

M = y2 .(y1a )−1 = y2 .y1n−a

En effet :
y2 .y1n−a = [Link] .(g k )n−a
= M.g a.k .g k.n .g −ka
= M.g a.k .(g n )k .g −ka
= M.g a.k .g −ka = M

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Le protocole d’El Gamal

Fig.: [Link]/2004/talks/fairbrother/

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique
Cryptographie à clef publique R.S.A. DLP & Diffie-Hellman El Gamal

Sécurité du cryptosystème de El Gamal

I Résoudre DLP dans G ⇒ Casser El Gamal dans G

I l’attaquant peut alors calculer a à partir de A (public).
I La réciproque n’est pas encore prouvée !
Cas particulier de G = F∗p :
I utiliser un nombre premier p de 1024 bits choisis uniformément
I permet de résister aux méthodes actuelles de résolution de DLP sur
F∗p

Pierre-Louis Cayrel Université de Limoges, XLIM-DMI, 123, Av. Albert Thomas 87060 Limoges Cedex France [Link].10 [Link]@[Link]
Chiffrement à clef publique ou asymétrique