Cryptography Reference
In-Depth Information
Using
l
e
one can reduce the DLP to subgroups of prime power order. To reduce the
problem to subgroups of prime order one can the following: suppose
g
0
has order
l
e
and
h
0
=
g
l
e
−
1
0
g
0
then we can write
a
a
e
−
1
l
e
−
1
=
a
0
+
a
1
l
+···
where 0
≤
a
i
<l
.Let
g
1
=
.
Raising to the power
l
e
−
1
gives
h
l
e
−
1
0
g
a
0
1
=
from which one can find
a
0
by trying all possibilities (or using baby-step-giant-step or
other methods).
To compute
a
1
we define
h
1
=
h
0
g
−
a
0
so that
0
g
a
1
l
+
a
2
l
2
+···
a
e
−
1
l
e
−
1
h
1
=
.
0
Then
a
1
is obtained by solving
h
l
e
−
2
1
g
a
1
.
=
h
1
g
−
la
1
0
To obtain the next value we set
h
2
=
and repeat. Continuing gives the full solution
modulo
l
e
. Once
a
is known modulo
l
e
i
i
for all
l
e
i
N
one computes
a
using the Chinese
remainder theorem. The full algorithm (in a slightly more efficient variant) is given in
Algorithm
12
.
Algorithm 12
Pohlig-Hellman algorithm
INPUT:
g,h
=
i
=
1
l
e
i
=
g
a
,
{
(
l
i
,e
i
):1
≤
i
≤
n
}
such that order of
g
is
N
i
OUTPUT:
a
1:
Compute
g
N/l
f
i
,h
N/l
f
i
i
:1
{
≤
i
≤
n,
1
≤
f
i
≤
e
i
}
2:
for
i
=
1to
n
do
a
i
=
0
3:
Reducing DLP of order
l
e
i
i
for
j
=
1to
e
i
do
to cyclic groups
4:
g
N/l
i
and
h
0
=
h
N/l
i
Let
g
0
=
These were already computed in line 1
5:
g
−
a
i
0
Compute
u
=
and
h
0
=
h
0
u
6:
if
h
0
=
1
then
7:
Let
g
0
=
g
N/l
i
,
b
=
=
1,
T
g
0
Already computed in line 1
8:
while
h
0
=
T
do
Exhaustive search
9:
b
=
b
+
1,
T
=
Tg
0
10:
end while
11:
bl
j
−
1
i
a
i
=
a
i
+
12:
13:
end if
14:
end for
15:
end for
16:
Use Chinese remainder theorem to compute
a
a
i
(mod
l
e
i
)for1
≡
≤
i
≤
n
17:
return
a
