Fichier PDF

Partagez, hébergez et archivez facilement vos documents au format PDF

Partager un fichier Mes fichiers Boite à outils PDF Recherche Aide Contact



rapport log .pdf



Nom original: rapport_log.pdf

Ce document au format PDF 1.4 a été généré par TeX / pdfTeX-1.40.10, et a été envoyé sur fichier-pdf.fr le 02/05/2016 à 20:32, depuis l'adresse IP 82.238.x.x. La présente page de téléchargement du fichier a été vue 351 fois.
Taille du document: 264 Ko (16 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Logarithme Discret
Jade Tourteaux & Christophe Boubel
9 avril 2014

Table des mati`
eres
1 Introduction

2

2 Baby Step Giant Step
2.1 L’algorithme . . . . . . . . . . . . . . . .
2.2 Baby Step - Pr´e-calcul . . . . . . . . . . .
2.3 Giant Step . . . . . . . . . . . . . . . . .
2.4 Complexit´e . . . . . . . . . . . . . . . . .
2.5 Avantages - Inconv´enients . . . . . . . . .
2.6 Exemple d’impl´ementation dans (Z/pZ)∗

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

3
3
3
3
4
4
5

3 Rho-Pollard
3.1 L’algorithme . . . . . . . . . . . . .
3.2 Un exemple . . . . . . . . . . . . . .
3.3 Le Li`evre et la Tortue . . . . . . . .
3.3.1 Pr´esentation de l’agorithme .
3.3.2 Complexit´e . . . . . . . . . .
3.4 Complexit´e de Rho Pollard . . . . .
3.4.1 Le paradoxe des anniversaires
3.5 Avantages - Inconv´enients . . . . . .
3.6 Impl´ementation . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

7
7
7
8
8
9
10
10
11
11

4 Pohlig-Hellman
4.1 L’algorithme .
4.2 Complexit´e . .
4.3 Exemple . . . .
4.4 Impl´ementation

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

13
13
15
15
15

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

5 Conclusion

.
.
.
.

.
.
.
.

.
.
.
.

16

1

1

Introduction

La cryptographie `
a cl´e publique ou cryptographie asym´etrique est une m´ethode
de chiffrement bas´ee sur l’´echange d’une cl´e publique (diffus´ee) et d’une cl´e
priv´ee (secr`ete), l’une permettant le chiffrement, l’autre le d´echiffrement. Elle
repose sur l’existence des fonctions `a sens unique. C’est `a dire la donn´ee d’une
fonction f de chiffrement qui soit rapide `a calculer mais telle que son inverse
f −1 soit difficile `
a trouver. Il faut donc que ´etant donn´e une image par f , il soit
difficile de lui trouver un ant´ec´edent.
Un exemple d’une telle fonction est l’exponentiation. En effet, grˆace `a l’algorithme d’exponentiation rapide, il est tr`es rapide de calculer de grandes puissances enti`eres d’un nombre, mais le calcul de la fonction inverse que l’on appelle
logarithme discret n’est pas si ais´e.
Concr`etement, on consid`ere un groupe cyclique G d’ordre n (dont la loi est
not´ee multiplicativement), un g´en´erateur g de G et un ´el´ement x ∈ G. Le logarithme discret de x en base g est le plus petit entier ` ∈ N tel que g ` = x.
Pour certains groupes (bien choisis), le calcul du logarithme discret s’av`ere
difficile. Il est notamment utilis´ee dans le protocole d’´echange de cl´es DiffieHellman ou le chiffrement El Gamal.
Na¨ıvement, on pourrait ´enum´erer toutes les puissances de g (puisque G est
cyclique) jusqu’`
a ce qu’on tombe sur le bon r´esultat. Cependant cette m´ethode
n’est pas viable pour de grands groupes G car mˆeme si sur le plan m´emoire cette
m´ethode est ´economique, sa complexit´e temporelle est en O(n) op´erations dans
G. Or pour les applications cryptographiques, le logarithme discret cherch´e est
au moins de l’ordre de 160 bits, c’est `a dire x ≥ 2160 . Ce qui nous am`enerait `a
faire au moins 2160 − 1 multiplications dans G.
Il existe des algorithmes pour calculer le logarithme discret plus efficaces que
la recherche exhaustive que nous allons ´etudier.
Dans toute la suite, on se donne comme hypoth`ese la donn´ee d’un groupe
cyclique G d’ordre n, d’un g´en´erateur g de G ainsi que d’un ´el´ement x ∈ G. Le
but est de trouver ` ∈ N, 0 ≤ ` < n tel que g ` = x.

2

2
2.1

Baby Step Giant Step
L’algorithme

Ce premier algorithme de r´esolution du probl`eme du logarithme discret,
d´evelopp´e par Daniel Shanks est bas´e sur l’existence de la division euclidienne
de tout nombre entier. √
Pour cela on pose m = d ne ∈ N.
Par division euclidienne de ` par m, il existe q ∈ N et r ∈ N tels que
` = qm + r avec 0 ≤ r < m
Transformons notre ´egalit´e x = g ` :
x = g ` = g qm+r
x = g qm+r
g r = x(g −m )q
L’algorithme se fait en deux temps, la premi`ere ´etape de pr´e-calcul (baby-step)
qui va calculer et garder en m´emoire tous les g r pour tous les r tels que
0 ≤ r < m. Puis les ”pas de g´eants”, qui vont calculer les x(g −m )q dans le but
de v´erifier l’´egalit´e ci-dessus.

2.2

Baby Step - Pr´
e-calcul

On stocke l’ensemble B d´efini par
B = {(g r , r) : 0 ≤ r < m}
dans une table de hachage id´ealement (pour nous, un tableau de taille n).
On est sˆ
ur qu’au moins une des valeurs stock´ees dans le tableau correspond au
v´eritable reste de la division euclidienne.

2.3

Giant Step

Maintenant que l’on a toutes les valeurs possibles pour le reste de la division,
cherchons le quotient.
Posons d = x,
n
,
Pour j allant de 0 `
a m
– On v´erifie si (d, j) ∈ B
– Si c’est le cas, on a trouv´e le logarithme. En effet, `a l’´etape j de la boucle,
d = x(g −m )j . Donc si d = g r , on retrouve l’´egalit´e g r = x(g −m )q . On a donc
l = jm + r
– Si ce n’est pas le cas, d = d ∗ g −m

3

2.4

Complexit´
e

L’´etape de pr´e-calcul constitue en une boucle de longeur m qui fait m multiplications dans G et stocke m nombres. Cette ´etape a donc une complexit´e
spatiale en O(m∗ taille d’un nombre de G) et une complexit´e temporelle de
O(m) op´erations dans G.
Pour les pas de g´eants, plusieurs impl´ementations sont possibles, elles influencent la complexit´e. Le probl`eme se situe au niveau de la v´erification d ∈ B.
Soit on effectue une recherche dans le tableau, ce qui risque d’augmenter la complexit´e de l’algorithme, soit on utilise une table de hachage pour avoir un acc`es
direct aux ´el´ements du tableau. Si on utilise une table de hachage, l’op´eration
n
fois cette v´erification,
”v´erifier si d ∈ B” est en O(1). Ainsi, comme on effectue m
n
les pas de g´eants sont en O( m ).
n
La complexit´e de l’algorithme est donc en√O(m + m
) op´erations dans G.
n,
on
obtient
une complexit´e en
Ainsi,
si
on
choisit
pour
valeur
de
m,
m
=

O( n). Ce qui est beaucoup mieux que la complexit´e en O(n) de la recherche
exhaustive.

2.5

Avantages - Inconv´
enients

Avantages :
Cet algorithme est d´eterministe, c’est `a dire que quelque soit les valeurs
donn´ees, l’algorithme est certain de trouver le logarithme discret.
Inconv´
enients :
D’un autre cˆ
ot´e, il n´ecessite de stocker des valeurs, c’est `a dire d’utiliser un
certain espace m´emoire puis de rechercher de mani`ere efficace parmi les valeurs
pour pour effectuer des tests. En pratique l’id´eal est d’utiliser une table de
hachage qui est tr`es pratique pour acc´eder `a des valeurs stock´ees rapidement.

4

2.6

Exemple d’impl´
ementation dans (Z/pZ)∗

Fonction qui retourne l’inverse d’un ´
el´
ement dans G = (Z/pZ)∗ (pour
−m
calculer g
qui est ´
egal `
a l’inverse de g m )
i n t i n v e r s e ( i n t a , i n t b){
i n t r 1 = a , r 2 = b , u1 = 1 , u2 = 0 ;
i n t q , r s , us ;
w h i l e ( r 2 != 0 ) {
q = r1 / r2 ;
r s = r 1 ; us = u1 ;
r 1 = r 2 ; u1 = u2 ;
r 2 = r s −q∗ r 2 ;
u2 = us−q∗u2 ;
}
r e t u r n u1 ;
}
Fonction qui calcule les pas de b´
eb´
e et les stocke
v o i d b a b y s t e p ( i n t g , i n t m, i n t B [ ] , i n t n ) {
i n t cmp = 1 ;
int r ;
f o r ( r = 1 ; r < m; r++){
cmp ∗= g ;
cmp = cmp%n ;
B [ cmp ] = r ;
}
Calcule les pas de g´
eant et retourne le log discret trouv´
e
i n t g i a n t s t e p ( i n t g , i n t m, i n t x , i n t B [ ] , i n t n ) {
mpz t bmpz , gmpz , nmpz ;
m p z i n i t ( bmpz ) ;
m p z i n i t s e t u i ( gmpz , g ) ;
m p z i n i t s e t u i ( nmpz , n ) ;
mpz powm ui ( bmpz , gmpz , m, nmpz ) ;
int b =
i n t inv
inv = n
int y =
int q ;
for (q =

( i n t ) m p z g e t u i ( bmpz ) ;
= inverse (b , n ) ;
+ inv ;
x;
0 ; q < ( n/m) ; q++){
i f (B [ y ] != −1) r e t u r n B [ y ] + m∗q ;
y ∗= i n v ;
y = y%n ;

}
5

r e t u r n −1;
}
Calcule le log `
a l’aide de baby step, giant step et retourne le log
discret
i n t BSGS( i n t n , i n t g , i n t x ) {
i n t m;
int log ;
int i ;
m = ( int ) c e i l ( sqrt (n ) ) ;
i n t B[ n ] ;
f o r ( i = 0 ; i < n ; i ++)
B [ i ] = −1;
b a b y s t e p ( g ,m, B, n ) ;
l o g = g i a n t s t e p ( g ,m, x , B, n ) ;
r e t u r n l o g %(n −1);
}

6

3

Rho-Pollard

3.1

L’algorithme

L’algorithme de Rho-Pollard est une approche probabiliste
√ du calcul du logarithme discret, dont la complexit´e temporelle reste en O( n) mais n’utilise
presque pas d’espace m´emoire.
On cherche ` tel que x = g ` , pour cela, on va poser a, b, a0 et b0 tels que
0
0
0
0
0
x g = xa g b , c’est-`
a-dire xa−a = g b −b d’o`
u on d´eduit ` = a−a
b0 −b (mod n)
Il faut donc trouver a, b, a0 et b0 .
a b

L’id´ee est d’utiliser un fonction f : G → G v´erifiant ces propri´et´es :
1. f doit ˆetre simple `
a calculer
0
0
2. pour a, b ∈ G on doit pouvoir trouver a0 , b0 ∈ G tels que f (g a xb ) = g a xb
3. f doit avoir un comportement al´eatoire (ou presque)
On choisit u0 al´eatoirement dans {1, ..., n}, et on pose v0 = 0
On calcule la suite (βi )i∈N d´efinie par β0 = g u0 xv0 et βi+1 = f (βi )
D’apr`es 2. on sait que que chaque βi = g ui xvi
Comme G est fini, il existe un k > 0 tel que βi = βi+k
g ui xvi = g ui+k xvi+k
g ui −ui+k = xvi+k −vi
Soit ` le logarithme discret de x en base g, il v´erifie la congruence
`(vi+k − vi ) ≡ ui − ui+k

(mod 1)

La solution de cette congruence est unique si vi+k −vi est premier avec u−1,
dans ce cas on en d´eduit `.
Sinon on peut recommencer l’algorithme avec un autre u0

3.2

Un exemple

Des exemples de fonctions simples v´erifiant les propri´et´es 1. et 2. sont les
fonctions du type β → β k , k petit, ou β → gβ, β → xβ.
Pour obtenir le comportement al´eatoire on va combiner ces fonctions. On
pose G1 , G2 , G3 disjoints, tels que G1 ∪ G2 ∪ G3 = G
On d´efinit la fonction f : G → G telle que :

 gβ si β ∈ G1
β 2 si β ∈ G2
f (β) =
(1)

xβ si β ∈ G3
7

On en d´eduit que les suites (ui )i et (vi )i sont d´efines par :

 ui + 1 mod [n − 1] si β ∈ G1
2ui mod [n − 1]
si β ∈ G2
ui+1 =

ui
si β ∈ G3

vi+1 =




vi
si
2vi mod [n − 1]
si

vi + 1 mod [n − 1] si

β ∈ G1
β ∈ G2
β ∈ G3

(2)

(3)

Le probl`eme qui se pose est : comment trouver rapidement un cycle ? Na¨ıvement, il faudrait donc stocker tous les triplet (βi , ui , vi ) afin de trouver une
collision. Cependant l’algorithme de recherche des cycles de Floyd nous permet
d’effectuer l’algorithme de rho Pollard (presque) sans m´emoire.

3.3
3.3.1

Le Li`
evre et la Tortue
Pr´
esentation de l’agorithme

Soit f une fonction, et X un ensemble fini de cardinal n. On consid`ere la
suite (τ )i d´efinie par τ0 ∈ X et τi+1 = f (τi ). La suite (τ )i aura le rˆole de
la tortue et on pose le li`evre, (λi ) tel que ∀i, λi = τ2i . L’algorithme calcule
les termes successifs des suites (τ )i et (λ)i jusqu’`a trouver un i tel que τi = λi .

8

3.3.2

Complexit´
e

La complexit´e spatiale est en O(1) puisque sont stock´es uniquement deux
termes `
a la fois.
Pour la complexit´e temporelle, posont k le plus petit indice tel qu’il y ai une
collision en τk (τk est donc le terme qui fait rentrer la suite dans le cyle).
Et posont aussi ` la longueur du cycle.
Si on prouve que l’algorithme termine `a l’indice i pour lequel τi = λi avec
k ≤ i ≤ k + ` alors la complexit´e temporelle de l’algorithme sera en k + ` comparaisons dans le pire des cas.
Montrons qu’il existe i, k ≤ i ≤ k + ` tel que τi = λi , c’est-`a-dire τi = τ2i
Sachant que X est un ensemble fini, il existe forc´ement un j tel que τj = τ2j .
Comme k est le plus petit indice tel que τk = τk+` on en d´eduit k ≤ j.
Soit j ≤ k + ` donc j = i, soit j ≥ k + `.
Si j ≥ k + ` on pose j 0 avec k ≤ j 0 ≤ k + ` tel que j = q`j 0 .
Or τj = τ2j , donc τqlj 0 = τ2qlj 0 ⇒ τj 0 = τ2j 0 , donc j 0 = i

9

3.4

Complexit´
e de Rho Pollard

D’apr`es l’´etude de la complexit´e de l’algorithme de recherche des cycles de
Floyd, la complexit´e spatiale de Rho Pollard est en O(1). Etudions la complexit´e
temporelle.
En admettant que la fonction f soit uniform´ement al´eatoire, on se retrouve avec
une suite de (βi ) al´eatoire, uniform´ement distribu´ee dans G, jusqu’`a la premi`ere
collision. On peut donc comparer l’´etude de la complexit´e temporelle de Rho
Pollard avec le paradoxe des anniversaires.
3.4.1

Le paradoxe des anniversaires

Posons p(a) la probabilit´e que parmi a ´el´ements tir´es al´eatoirement de G,
deux soient identiques.
p¯(a) =

n−a+1
n n−1

∗ ... ∗
n
n
n
p(a) = 1 − p¯(a)
p¯(a) = 1 − p(a)

0
1
a−1
)(1 − )...(1 −
)
n
n
n
Cherchons une approximation de p(a). le d´eveloppement limit´e de ex ´etant
x
e = 1 + x + o(x) pour x au voisinage de 0. On en d´eduit :
p¯(a) = (1 −

p¯(a) ≈

a−1
Y

i

e− n

i=0

p¯(a) ≈ e−
Or

Pa−1
i=0

i=

Pa−1
i
i=0
n

a(a−1)
2

p¯(a) ≈ e−

a(a−1)
2−n

p(a) ≈ 1 − e−

a(a−1)
2−n

L’approximation de p(a) permet d’obtenir simplement une approximation
du nombre d’´el´ements n´ecessaire pour avoir une probabilit´e donn´ee p d’avoir au
moins deux ´el´ements identiques. On obtient ainsi :
r
1
a(p) ≈ 2n ln(
)
1−p

On en d´eduit que la complexit´e temporelle de Rho Pollard est en O( n)
op´erations dans G.
10

3.5

Avantages - Inconv´
enients

Avantages :
Cet algorithme n´ecessite
un temps d’ex´ecution similaire `a celui de Baby-Step

d’espace m´emoire. L`a
Giant-Step, i.e en O( n), cependant il prend beaucoup

o`
u celui de Shanks a un stockage de l’ordre de O( n), Rho Pollard n´ecessite un
stockage `
a peu pr`es constant.
Inconv´
enients :
Par contre, cet algorithme est probabiliste, ce qui signifie que l’on est pas

ur de trouver le logarithme discret `a tous les coups.

3.6

Impl´
ementation

Fonction qui retourne l’inverse d’un ´
element dans Z/pZ grˆ
ace `
a
l’algorithme d’Euclide ´
etendu
i n t i n v e r s e ( i n t a , i n t b){
i n t r 1 = a , r 2 = b , u1 = 1 , u2 = 0 ;
i n t q , r s , us ;
w h i l e ( r 2 != 0 ) {
q = r1 / r2 ;
r s = r 1 ; us = u1 ;
r 1 = r 2 ; u1 = u2 ;
r 2 = r s −q∗ r 2 ;
u2 = us−q∗u2 ;
}
r e t u r n u1 ;
}
Prends en arguments βi , ui , vi et calcule βi+1 , ui+1 , vi+1
v o i d maj beta n m ( i n t N, i n t g , i n t x ,
i n t ∗ beta , i n t ∗n , i n t ∗m ) {
switch ( ∗ beta % 3 ) {
case 0:
∗ b e t a = g ∗ ∗ b e t a % N;
∗n
= ∗n + 1
% (N−1);
break ;
case 1:
∗ b e t a = ∗ b e t a ∗ ∗ b e t a % N;
∗n = 2 ∗ ∗n
% (N−1);
∗m = 2 ∗ ∗m
% (N−1);
case 2:
∗ b e t a = x ∗ ∗ b e t a % N;
∗m = ∗m + 1
% (N−1);
11

}
}
Recherche de la colision grˆ
ace `
a l’algorithme de Floyd et r´
esolution
du logarithme discret
i n t main ( i n t argc , c h a r ∗∗ argv ) {
i n t r , inv , l o g ;
i n t N = a t o i ( argv [ 1 ] ) ; // T a i l l e du groupe Z/NZ
i n t g = a t o i ( argv [ 2 ] ) ; // g e n e r a t e u r
i n t x = a t o i ( argv [ 3 ] ) ; // un e l e m e n t du groupe
i n t beta = 1 , n = 1 , m = 0 ;
i n t b e t a 2 = beta , n2 = n , m2 = m;
int i ;
f o r ( i = 0 ; i < N; ++i ) {
maj beta n m ( N, g , x , &beta , &n , &m ) ;
maj beta n m ( N, g , x , &beta2 , &n2 , &m2 ) ;
maj beta n m ( N, g , x , &beta2 , &n2 , &m2 ) ;
p r i n t f ( ”%d : (%d,%d,%d ) (%d,%d,%d ) \ n ” ,
i , beta , n , m, beta2 , n2 , m2 ) ;
i f ( b e t a == b e t a 2 ) {
r = m2 − m % N;
i f ( r == 0 ) r e t u r n 0 ;
i n v = i n v e r s e ( r , N−1);
l o g = i n v ∗ ( n − n2 ) % N ;
p r i n t f ( ” Le l o g d i s c r e t en b a s e %d de %d
dans l e groupe ( Z/%dZ ) ∗ e s t : %d\n ” ,
g , x , N, l o g ) ;
break ;
}
}
return 0;
}

12

4

Pohlig-Hellman

4.1

L’algorithme

L’algorithme de Pohlig-Hellman est un algorithme qui permet de ramener
le calcul du logarithme discret dans un groupe G d’ordre n (non premier) `a un
calcul de logarithmes discrets dans des sous-groupes d’ordre premier.
En effet cet algorithme consiste `a utiliser la d´ecomposition de l’ordre du
groupe en produit de facteurs premiers (qui existe et est unique).
On a :
n = pu1 1 ∗ pu2 2 ∗ ... ∗ puk k
Que l’on notera pour simplifier :
n = n1 ∗ n2 ∗ ... ∗ nk
O`
u:
ni = pui i
Comme G est un groupe cyclique, on a : G ' Z/nZ.
Grˆ
ace au Th´eor`eme Chinois on a :
Z/nZ ' Z/n1 Z × Z/n2 Z × ... × Z/nk Z
Les Z/ni Z sont des sous-groupes cycliques de G.
Posons Z/ni Z = Gi , xi = xn/ni et gi = g n/ni .
Les Gi sont d’ordre ni et
Gi =< gi >
(gi )ni = g n = 1
On a :
(g ` )n/ni = xi
(gi )` = xi
Ce qui signifie que ` est le logarithme discret de xi dans Gi .
Donc on cherche les `i dans chaque Gi , solution modulo ni de gi`i = xi . On peut
les trouver grˆ
ace `
a Baby-Step Giant-Step.
Lorsque l’on a obtenu chaque `i , on utilise le th´eor`eme des restes chinois
pour trouver ` ∈ Z/nZ tel que :
` ≡ `i

(mod ni ), ∀i ∈ {1, 2, ..., k}

Ce ` est la solution de g ` = x.

13

Malgr´e cela, le calcul du logarithme discret dans chaque Gi peut encore ˆetre
fastidieux si la d´ecomposition de n est ”in´egale”.
6
Par exemple : si n = 210 ∗ 3, on va ˆetre amen´e `a calculer `a l’aide de BSGS
(baby-step giant-step) le logarithme discret dans un groupe d’ordre 3 et dans un
6
groupe d’ordre 210 , ce qui est encore ´enorme quant au temps de calcul pratique.
On peut faire mieux que cela.
Posons pour la suite, afin de simplifier les notations : Gi = G =< g >.
On sait donc que |G| = pk et 0 ≤ ` < pk .
En fait, {1, p, ..., pk−1 } est une base de Z/pk Z en tant que Z/pZ-espace vectoriel.
On peut donc ´ecrire ` en base p :
` = `0 + `1 ∗ p + `2 ∗ p2 + ... + `k−1 ∗ pk−1
On a :
x = g ` = g `0 +`1 ∗p+...+`k−1 ∗p
x = g `0 +p(`1 +...+`k−1 ∗p
k−1

xp
x

= (g `0 +p(`1 +...+`k−1 ∗p

pk−1

=g

k−1

k−1

)

k−1

) pk−1

)

`0 pk−1 +pk (`1 +...+`k−1 pk−1 )

xp

k−1

x
xp

k−1

= g `0 p

pk−1

k−1

=g

∗1

`0 pk−1

= (g p

k−1

)`0

Donc `0 est un logarithme discret dans un groupe d’ordre p que l’on peut
k−1
alors d´eterminer par la m´ethode de Shanks car g p
est d’ordre p. En effet
k−1
k
(g p )p = g p = 1.
On a ensuite :
x ∗ g −`0 = g `1 p+...+`k−1 p
(x ∗ g −`0 )p

k−2

(x ∗ g −`0 )p

= g `1 p

k−2

k−1

= (g p

k−1

+pk (...)

k−1

)`1

Donc `1 est un logarithme discret toujours dans un groupe d’ordre p.
Par r´ecurrence, on montre que que chaque `i est un logarithme discret dans
un groupe d’ordre p. Ce qui signifie qu’au lieu de calculer 1 logarithme discret
dans un groupe d’ordre pk , on calcule k logarithmes discrets dans un groupe
d’ordre p.
Cette r´eduction de calcul est donc valable pour chaque Gi du probl`eme
initial.
Si l’on reprend l’exemple que nous avons utilis´e pr´ec´edemment, avec n =
6
a calculer un logarithme discret dans un groupe d’ordre 3
210 ∗ 3, cela revient `
puis 106 logarithmes discrets dans un groupe d’ordre 2.
14

4.2

Complexit´
e

erant la factorisation de n en produit de nombres premiers : n =
Qk En uconsid´
i
,
on
r´esout pour chaque i ∈ {1, 2, ..., n}, ui logarithmes discrets dans
p
i
i=1
Z/pi Z. Si on consid`ere que l’on utilise la m´ethode de Shanks pour r´esoudre

chacun de ses logarithmes discrets, c’est `a dire qu’on met O( pi ) pour chacun
d’eux, on a la complexit´e de Pohlig-Hellman ´egale `a :
k
X

k
X


ui ∗ O( pi ) = O(
ui ∗ pi )

i=1

4.3

i=1

Exemple

Soit le groupe multiplicatif G = (Z/19Z)∗ , g = 2 un g´en´erateur et x = 9 un
´el´ement dont on cherche le logarithme discret `. L’ordre du groupe est n = 18,
qui peut s’´ecrire n = 32 ∗ 2. On calcule modulo 19.
Alors on calcule :
2

g1 = g n/3 = g 2 = 22 = 4
x1 = x2 = 81 = 5
g2 = g n/2 = g 9 = 29 = 512 = 18
x2 = x9 = 99 = 1
Maintenant, on r´esout ces deux sous-probl`emes du logarithme discret :
1. g1`1 = x1
n/3 a0
n/3
(g1 ) = x1

: on ´ecrit `1 = a0 + a1 3 et on trouve a0 , la solution du DL
⇔ 11a0 = 7 ⇒ a0 = 2.
Et on trouve a1 en r´esolvant le DL suivant :
n/32

g1

n/32

= x1

−a0 ∗n/32

∗ g1

⇔ (42 )a1 = 52 ∗ (4)−2∗2 = 52 ∗ 54 = 7 ⇔ 8a1 = 7

qui donne a1 = 2.
Alors `1 = a0 + a1 3 = 2 + 6 = 8.
2. g2`2 = x2 : en r´esolvant ce DL, on trouve `2 = 2.
Ainsi, on utilise le th´eor`eme des restes chinois pour calculer ` tel que ` ≡ 8
(mod 32 ) et ` ≡ 2 (mod 2), d’o`
u vient ` = 26.
On peut v´erifier que :
g 26 = 226 = (25 )5 ∗ 2 = 135 ∗ 2 = 14 ∗ 2 = 28 = 9 = x

4.4

Impl´
ementation
15

5

Conclusion

Le logarithme discret est un probl`eme important en cryptographie a` clef
publique, il permet de s´ecuriser et de fiabiliser de nombreux syst`emes et est
toujours fortement utilis´e.
La recherche le concernant est importante et pourrait aboutir `a de nouveaux
algorithmes permettant de r´eduire le temps de calcul, ce qui pourrait remettre
en cause les syst`emes bas´es dessus. Au d´ebut, il ´etait surtout utilis´e avec les
groupes cycliques (Z/pZ)∗ mais depuis quelques temps, on l’utilise notamment
avec les sous-groupes cycliques du groupe associ´e `a une courbe elliptique sur un
corps fini.
Il n’existe pas `
a l’heure actuelle d’algorithme de calcul du logarithme discret
en temps polynomial.

16


Documents similaires


Fichier PDF rapport log
Fichier PDF pre requis de maths
Fichier PDF triselection
Fichier PDF analysec00
Fichier PDF cours most sis
Fichier PDF 1 analyse et mesure des performances


Sur le même sujet..