Cryptography Reference
In-Depth Information
Let
g
be a generator modulo
p
, and suppose we wish to solve
g
x
b
(mod
p
)
for
x
. To do this, we will first determine each residue
x
i
such that
x
x
i
(mod
p
i
e
i
)
∀
i
.
To compute each of these residues, we will compute the digits of each
x
i
in terms of its
p
i
-ary representation; that is, we will construct each
x
i
as a base
p
i
number:
x
i
=
d
ei
1
p
i
ei
1
+
d
ei
2
p
i
ei
2
+ . . . +
d
2
p
i
2
+
d
1
p
i
+
d
0
. (
*
)
Once we have determined each
x
i
, we have a system
x
x
1
(mod
p
1
e
1)
x
x
2
(mod
p
2
e
2)
···
x
x
n
(mod
p
n
e
n
)
which we can then solve for
x
= log
g
b
using the Chinese Remainder Theorem (notice the
moduli are pairwise relatively prime). The trick, of course, is to obtain the representation
given by (
*
); this is described in the following algorithm.
Suppose
p
,
g
, and the prime factorization of
p
1 are as described previously. We wish
to find
x
= log
g
,
p
b
:
1.
For
i
= 1 to
n
do:
(a) Let
q
=
p
i
,
e
=
e
i
,
c
= 1, and
d
1
= 0.
(b) Compute
g
*
=
g
(
p
1)/
q
.
(c) For
k
= 0 to
e
1 do:
I. Set
c
=
cg
d
k
1
qk
1
II. Set
b
*
= (
bc
)
n
/(
qk
1)
(where
c
is an inverse of
c
modulo
p
)
III. Compute
d
k
= log
g
*
b
*
(d) Let
x
i
=
d
e
1
q
e
1
+
d
e
2
q
e
2
+ . . . +
d
2
q
2
+
d
1
q
+
d
0
2.
Use CRT to compute a simultaneous solution
x
to the system
x
x
1
(mod
p
1
e
1
)
x
x
2
(mod
p
2
e
2
)
···
x
x
n
(mod
p
n
e
n
)
Search WWH ::
Custom Search