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 440 fois.
Taille du document: 264 Ko (16 pages).
Confidentialité: fichier public


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




Télécharger le fichier (PDF)

rapport_log.pdf (PDF, 264 Ko)

Télécharger
Formats alternatifs: ZIP







Documents similaires


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

Sur le même sujet..