Int. J. Comm unications, Networ k and System Science s, 2010, 3, 639-644
doi:10.4236/ijcns.2010.38086 Published Online August 2010 (htt p:/ / www.SciRP.org/journal/ijcns)
Potential Vulnera bility of Encrypted Messages:
Decomposability of Discrete Logarithm Problems
B oris S. Verkhovsky
Computer Science Department, Ne w J ersey Inst itute of Technology, Newark, USA
E-mai l:
Recei ved May 10, 2010; r evis ed June 15, 2010; accept ed Jul y 21, 2010
A bst ract
This paper provides a framework that reduces the computational complexity of the discrete logarithm prob-
lem. The paper describes how to decompose the initial DLP onto several DLPs of smaller dimensions. De-
com posability of the DLP is an indicator of potential vulnerability of encrypted messages transmitted via
op en cha nne ls of the Int ernet or wit hin cor porate net wor ks. S ever a l nu m er ica l examp l es il lus t r ate the fr a me -
work and s how its computationa l efficiency.
Keywords: Network Vulnerability, System Security, Discrete Logarithm, Integer Factorization, Multi-Level
Decomposition, Complexity Analysi s
1. Introduction and Problem Stat ement
The cryptoimmunity of numerous public key cryptogra-
phi c protocols is based on the computational complexity
of th e discrete logarithm pr oblems [1,2].
A DLP finds an integer x satisfying th e equation
mod
x
g ph=
. (1)
Here
21gp≤≤−
;
11hp≤≤−
(2)
and p is a large prime. In (1) g, p and h are inputs, and
the unknown integer x must be selected on the interval
[ ]
1, 1p−
.
Two trivial cases: if h = 1, t hen x = p – 1; If h = g, t hen
x = 1. If h is neither 1 nor g, then x must be selected on
the int e rval [2, p – 2].
If g is a gen erator, th en (1) always has a solution, oth-
erwise t he exi s tence of a sol ut ion is not guar anteed.
For instance, if p = 7 and g = 2, then the DLP
2 mod75
x
=
doe s not have a s olution.
Various a lgo rithms for solving the DLP were propose d
an d th eir computati ona l compl exi ti es wer e an alyzed over
the last forty years [3-15].
This paper provides the algorithmic framework that
reduc es the com puta ti onal complexi ty of the DLP.
The paper describes step-by-step procedure for deco-
mposition of the initial DLP onto several DLPs with
smaller dimensions. Several examples illustrate the dec-
omposition algorithm and highlight its computational
effi cienc y.
Let
111
:; :; :ggh hxx== =
;
1
:1qp= −
and
12
12p rr−=
. (3)
Her e it is a ssumed that integer fact or s
12
and rr
in (3)
are known or can be determined using existing algo-
rithms for integer factor ization [5,16,17].
Proposition: Let
( )
1: 1/Rp q= −
; (4)
if
( )
|1qp−
, then
1
R
is an intege r (4).
Let’s define
1
21
: mod
R
gg p=
; (5)
1
21
: mod
R
hh p=
; (6)
If an integer
2
x
is a solution of equation
2
22
mod
x
g ph=
, where
[ ]
2
0,xq∈
, (7)
then q divides
12
xx−
.
Proof: Let’s multiply both sides of the Equation (1) by
2
1
mod
x
gp
−
[18], and fin d
2
x
, such that
2
11
mod
x
hg p
−
(8)
has a root of power
q
.
By Euler ’s criterion [5] such a root exists if an d only if
( )
( )
2
1/
11
mod 1
pq
x
hg p
−
−
=
(9)
Using nota tions (4)-(6), rewr ite (8) as
2
22
mod 1
x
hg p
−
=
(10)
or as Equation (7). Q. E.D.

B. VERKHOVSKY
640
Therefore, the unknown
1
x
can be r epresent ed a s
12 3
xx qx= +
(11)
where the int ege r x3 must be on the interval
[ ] [ ]
33
0,(1) /0,xpq q∈−=
(12)
After
2
x
is determined, we need to find an integer
3
x
, for which the following equation holds
23
11
mod
x qx
g ph
+
=
. (13)
This equation can be rewritten as
( )
( )
32
1 11
mod
xx
q
g hgp
−
=
(14)
where in contrast with the BSGS algorithm, the value of
2
x
is already known.
Let
( )
3
1/
31
: mod
pq
gg p
−
=; (15)
and
2
3 11
: mod
x
h hgp
−
=
. (16)
2. Divide-and-Conquer Decomposition:
Illustrative Example-1
Let’s solve
1
2mod947 273
x
=
, (17)
i.e., here
11
2; 947;273gp h= ==
, and
[ ]
1
1,946x∈
.
Let
1
:1qp= −
.
Si nce
1 12
22 1143q rr= =××
, select
( )
201
minmax ,(1)/43
zp
qzp z
≤≤−
= −=
.
Then
1 12
: /22R qq= =
;
1
22
21
:mod2 mod947
R
gg p= =
41=
; and
1
22
21
:mod273 mod947283
R
hh p= ==
.
Ther efore we n eed to solve t he DLP(2):
2
41 mod947283
x
=
(7), (18)
where
[ ]
2
1, 42x∈
.
Remark1: Noti ce tha t the int er val of un cer ta int y [ 1, 42]
for
2
x
is much smaller than the corresponding interval
of uncert ainty [1, 946] for
1
x
.
Equation (18) can be solved using any algorithm for
the DLP [3,6,8-10,12].
In this example
2
x
= 39 a nd
2
43q=
.
Therefore
13
39 43xx= +
, where
( ) [ ]
32
0, 1/0,22x pq∈− = 

.
To fin d
3
x
solve th e DLP(3):
( )
( )
3
43 39
2273 2mod947
x−
= ×
,
wh ich is equivalent to
( )
3
367273111946 mod947
x=×=
. (19)
Therefore
3
11x=
.
Verification:
11
367 mod947946=
. (20)
Finally,
1
394311512x=+×=
.
3. Multi-Level Decomposition: Illus trative
Example-2
Initial DLP(1): Find an integer
1
x
, such that
1
30 mod9999145636
x=
, (21)
where
[ ]
11,99990x∈.
Because 99990=303*330, select
2
330q=
and
represent the unknown
1
x
as
12 3
330xx x= +
.
Si nce
( )
12
:1 /303Rp q=−=
;
then
303
21
:mod99991 151gg= =
;
and
303
21
:mod99991 64099hh==
.
Remark2: To better describe th e concept of decompo-
sition, a more suitable system of notations is considered
bel ow in th e fol lowi ng Table 1. These notati ons are us ed
to de scribe th e process of sol vi ng three D LPs .
DLP(2): S olve
2
22
mod99991
x
gh=
,
i.e.,
2
151 mod9999164099
x
=
,
where
[ ]
2
0,330x∈
. (22)
The so lut ion is
2
115x=
; inde ed
115
151mod99991 64099=
.
Therefore
3 1
115 330
3030mod99991 45636
x x+
= =
.
Consider the equation
( )
( )
3
330 115
303045636 mod99991
x−
= ×
.
Let
330
3: 30mod99991g= =
2593; and
( )
115
3
115
: 3045636
9665845636mod99991
49845
h
−
= ×
= ×
=
Ther efore, we need to solve
DLP(3):
3
2593 mod9999149845
x=
, where
[ ]
3
0,303x∈
. (23)
It is easy to ver ify that
3
47x=
. Finally,
12
xx=
23
115330 4715625qx+= + ×=
.
Decomposit ion of DLP(2): Solve
2
22
mod
x
g ph=
, (24)
where
[ ]
22
0,xq∈
= [0,330].

B. VERKHOVSKY
641
Tabl e 1. Solu tions of DL P(1) via th e dec ompos ition of DLP (2) and DL P(3).
DLP(1):
1
11
mod
x
g ph=
Proble m A Problem B Problem C
Inputs
{ }
11
;;gph
{2; 9 47; 273} {2 ; 947; 641} {30; 99991; 45636}
1 12
:12... t qprr r= −=
2 11 43××
2 11 43××
2
2311 101×××
DLP(2):
( )
21
min max,/
z
qzq z=
2
q
= 43
2
q
= 43
2
q
= 330
( )
22
: 1/Rp q= −
2
R
= 22
2
R
= 22
2
R
= 303
2
21
: mod
R
gg p=
241g=
241g=
303
2
30 mod99991151g= =
2
21
: mod
R
hh p=
2283h=
2283h=
303
245636 mod99991h=
= 64099
2
22
mod
x
g ph=
,
[ ]
22
0,xq∈
[ ]
2
0,43x∈
;
239x=
[ ]
2
0,43x∈
;
223x=
[ ]
20,330x∈
;
2115x=
DLP(3):
1 23
q qq=
,
( )
33
: 1/Rp q= −
3
R
= 43
3
R
= 43
3
R
= 330
3
31
: mod
R
gg p=
3
367g=
3
367g=
330
330 mod999912593g= =
2
3 11
: mod
x
h hgp
−
=
3946h=
3643h=
1
30 mod96658fp
−
= =
,
2
3
96658 mod9381
x
hp==
3
33
mod
x
g ph=
,
[ ]
33
0,xq∈
[ ]
3
0,22x∈
;
3
11x=
[ ]
3
0,22x∈
;
314x=
[ ]
3
0,303x∈
;
347x=
Solution of DLP(1):
1 2 23
x x qx= +
1
3943 11 512 x= + ×=
1
2343 14 625 x=+×=
1
115 330 47 15625 x= +×=
Remark3: Notice that the interval of uncertainty in
DLP(2) is n ot [1, p – 1], but
[ ]
22
1,xq∈
, which is much
smaller than [1, p – 1].
In stead of solvin g (24) dir ectly usin g an existing DLP
algorithm, we can again apply the meth od of dec om posi-
tion described above. Consider a factor
4
q
of
2
q
that
i s c los e to the s quare root of
2
q
= 330:
( )
( )
2
42
0
minmax , /
minmax,330/30
zq
z
qzqz
zz
≤≤
=
= =
(25)
Let’s represent the unknown in (24) as
2445
xx qx= +
, (26)
[] []
[ ] [ ]
44
55 24
where 1,1,30
and 1,:/1,11
xq
xq qq
∈=
∈==
. (2 7)
Let us now investigate whether
2
h
has an integer
root of powe r 30 modulo p.
By Euler ’s criterion, such a root exists if and only if
( )
4
1/
2mod 1
pq
hp
−=
. (28)
However, if
( )
4
1/
2mod 1
pq
hp
−≠
, find an integer
4
x
,
which s atis fi es the equat ion
( )
( )
4
4
1/
22
mod 1
pq
x
hg p
−
−
=
. (29)
Let
( )
4
1/
42
: mod
pq
ggp
−
=; (30)
and
( )
4
1/
42
: mod
pq
hhp
−
=
. (31)
Now we need t o sol ve th e equat ion
4
44
mod
x
g ph=
, (32)
where
[ ]
40,30x∈
. An d aga i n, th e Equation (32) i tself is
also a DLP with a much smaller interval (27) for x4 than
the interval for
2
x
in (24), and so on.
4. Mu lti-Level Decomposition: Illustrative
Example-3
First level: Let’s s olve the equation 1
11
mod
x
g ph=, where
g = 2, p = 4,000,000,003,231; and h = 3,024,336,139,227.
Then p – 1 = 863*2310*2006491, where 863 and
2,006,491 ar e pr imes.
In this case the initial DLP(1)
1
11
mod
x
g ph=
; is de-
composable into two sub-problems: DLP(2) a nd DLP(3).
DLP(2): Compute
( )
2
1/
21
1993530
:
2mod4000000003231
pq
gg
−
=
=
=3278213345371;
and
( )
2
1/
21
:
pq
hh
−
=
=302433613922719 935 30 mod 4000000003231
=2084778340641.
Solve
2
22
mod4000000003231
x
gh=
, where
22
0xq≤≤
2006491=
;
It is easy to verify the solution
2
1853979 2006491x= ≤
.
DLP(3):Compute
( )
3
1/ 2006491
31
:2 mod4000000003231
pq
gg
−
= =
= 3767306619080;
and

B. VERKHOVSKY
642
2
3 11
1853979
30243361392272000000001616
mod 4000000003231
:
3024336139227 629308445687
mod4000000003231
2623468766941.
x
h hg
−
×
=
= ⋅
= ×⋅
=
Solve
( )
3
33
mod
x
gh p=
, where
( )
3 32
0146221 /1993530;xqp q≤=≤=− =
and
1 23
q qq=
.
Then
1223
=1,853,9792,006,49114,622
=29,340,765,381.
xx qx
∗
= +
+
It is easy to verify that the solution
3
14622 1993530x= ≤
.
Comparison of complexities: While the size of the
required memory/storage for DLP(1) equals
1
1 2000000Tp

= −=

;
the corresponding memory requirement for DLP(2) and
DLP(3) are res pe ctively
22
12006491 1416Tq
 
= −==
 
and
33
11993530 1411Tq
 
= −==
 
.
Ther efore the spe ed -up ratio
( ) ( )
1 23
/2000000 /14161411707.ST TT=+=+ =
Thus the decomposition algor ithm for solving DLP(1)
via DLP(2) and DLP(3) is 707 times faster than a direct
solution of t he original DLP(1).
5. Second-Level Decomposition: Solution of
DLP(3)
Remark4: The second problem, DLP(2), cannot be sol-
ved by decomposition since q2 = 2,006,491 is a prime
integer. However, the third problem, DLP(3), is decom-
posable, therefore the speed-up ratio S can be further
increas ed.
Inde ed, s elect
( )
3
63
0
:minmax/ ,
zq
qq zz
≤≤
=
= 2310.
Let’s repr es ent
3
x
as
36 67
xxqx= +
, where
66
0 2310xq<<=
and
77
0 863xq<<=
,
and solve DLP(3) by decomposition into DLP(6) and
DLP(7).
DLP(6): Compute
( )
6
1/
63
: mod
pq
gg p
−
=
;
and
( )
6
1/
63
: mod
pq
hh p
−
=;
where
67 3
1993530qqq= =
;
and solve
( )
6
66
mod 1993531
x
gh=
;
{
66
0 2310xq<<=
}.
DLP(7): Compute
( )
7
1/
73
: mod
pq
gg p
−
=
;
and
6
7 33
: mod
x
h hgp
−
=
;
and solve
( )
7
77
mod 1993531
x
gh=
;
{
77
0 863xq<<=
}.
Then
66
48Tq

= =

and
77
29Tq

= =

.
Therefore
( )
( )
1 267
/
=2000000/14164829
=2000000/1493
=,
ST TTT= ++
++
1339.6
wh ich implies that by decomposing th e original problem
DLP(1) into three sub-problems {DLP(2), DLP(6) and
DLP(7)}, we can solve the initial DLP(1) 1340 times
faster than if we directly solve it without employing de-
composition.
In general, the speed-up increases as the size of p in-
creas es .
6. Computational Considerations
It is quite re as ona ble to ask under what c onditions should
we stop t he de compositi on of a DLP(k) and tr y to solve it
direct ly. Here are th e major iss ue s that must be taken in to
the consideration:
1) Feasibility of factoring
2 21kkk
q qq+ =
in such a way
that
( )
2
1/
2
:mod 1
k
pq
kk
ggp
−
= ≠±
. (33)
For instance, if
( )
24
|2 1qq p−
, then
( )()( )
( )( )
( )
4
42
24
1/
1/ 1/
42 1
1 /2
2 1/
1
:
1mod
pq
pq pq
p
p qq
ww w
wp
−
−−
−
−

== 

== ±

, (34)
where w = {g, h}. In such a ca se Equation (32) ha s on ly
trivial solutions { 0 or 1} or no solution
if
44
1 and 1gh==−
.
2) Magnitude of the overhead computations required
to fin d
2 21
and
kk
gg
+
an d t h en t o s olve t h es e t wo DLP s,
provided that these intermediate computations do not

B. VERKHOVSKY
643
be come too “ c ostly”.
Re mark 4: Analogously, we can solve DLP(3) by de-
composing it into two DLPs with smaller intervals of
uncertainty for the corresponding unknown s.
7. Algorithmic Decomposition of DLP(k)
Suppose t hat we need to solve DLP(k)
mod
k
u
kk
g ph=
, (33)
where
[ ]
0,
kk
uq∈
.
If
k
q
is a prime or if factors of
k
q
are unknown,
then (33) can be solved by a n algori thm for DLP such as:
BSGS, Pollard’s rho-algorithm, Lenstra’s number field
algorithm etc. However, if
k
q cd=
, where both c and d
are integers, then the DLP(k) can be reduced to solving
two less complex DLPs: DLP(2k) and DLP(2k + 1).
Let
2 21kkk
q qq
+
=
;
DLP(2k): Solve
2
22
mod
k
ukk
g ph=
; (34)
where
2: k
qc=
and
[ ]
20, k
uc∈
; (35)
( )
: 1/
kk
Rpq= −
; (36)
2
: mod
k
R
kk
gg p=
; (37)
and
2
: mod
k
R
kk
hh p=
; (38)
DLP(2k+1): Solve
21
21 21
mod
k
ukk
g ph
+
++
=
; (39)
where
[ ]
21
0, /
kk
u qc
+
∈
, (40)
( )
21 21
: 1/
kk
R pq
++
= −
; (41)
21
21
: mod
k
R
kk
gg p
+
+
=
; (42)
and
2
21
: mod
k
u
k kk
h hgp
−
+
=
. (43)
8. Conclusions
Provi de d t hat we know how to fa c tor p – 1, we can reduce
the initial DLP(1) to two discrete logarithm problems:
DLP(2) and DLP(3), for solut i on of whi ch the bes t kn own
algorithms can be implemented. The decomposition can
be im plem ent ed r ecursi vel y for solution of th e DLP(k) by
reducing it to a pair of DLP(2k) and DLP (2k + 1).
9. Acknowledge ment s
I express my appreciation to R. Rubino and P. Fay for
their comments and suggestions that improved the style
of this paper.
10. R eferen c es
[1] W. Diffie and M. E. Hellman, “New Directions in Cry-
ptography,” IEEE Transactions on Information Theory,
Vol. 22, No. 6, 1976, pp. 644-654.
[2] T. ElGamal, “A Public Key Cryptosystem and a Digital
Signature Scheme Based on Discrete Logarithms,” IEEE
Transactions on Information Theory, Vol. 31, No. 4, 1985,
pp. 469-472.
[3] L. M. Adleman and J. DeMarrais, “A Sub-Exponential
Algorithm for Discrete Logarithms over all Finite Fields,”
Mathematics of Computation, Vol. 61, No. 203, 1993, pp.
1-15.
[4] E. Ba ch, “ Di scr ete Logar it hms and Fact oring, ” Technical
Repor t: CSD-84-186, University of California, Berkeley,
1984.
[5] R. Crandall and C. Pomerance, “Pri m e N umbers: A Com-
put ati onal Perspe ctive,” The Qua drat ic Sieve Fact ori z ation
Method, Springer, Berlin, 2001, pp . 227- 244.
[6] A. Enge and P. Gaudry, “A General Framework for Sub-
Exponential Discrete Logarithm Algorithms,” Research
Repor t LIX/RR/00/04, Luxembourg Internet eXchange
(LIX ), Luxembourg Kirchberg, Vol. 102 , June 2000, pp.
83-103.
[7] B. A. LaMacchia and A. M. Odlyzko, “Computation of
Discrete Logarithms in Prime Fields,” Designs, Codes
and Cry ptography, Vol. 19, No. 1, 1991, pp. 47-62.
[8] A. K. Lenstra and J. H. W. Lenstra, “T he Deve lopme nt of
the Number Field Sieve,” Lecture Notes in M athematics ,
Springer -Verlag, Berlin, Vol. 1554, 1993, pp. 95-102.
[9] V. Müller, A. Stein and C. Thiel, “Computing Discrete
Logarithms in Real Quadratic Congruence Function Fie-
lds of Large Genus,” Mathematics of Computation, Vol.
68, No. 226, 1999, pp. 807-822.
[10] O. Schi r oka uer, “Using Number Fields to Compute Log-
arithms in Finite Fields,” Mathematics of Computation,
Vol. 69 , No. 231, 2000, pp. 1267-1283.
[11] D. Shanks, “Class Number, a Theory of Factorization and
Genera,” Proceedings of Symposium in Pure Mathematics,
Vol. 20, American Mathematical Society, Providence,
1971, pp. 415-440.
[12] J. Silverman, “The xedni Calcul us a nd t he Elliptic Cur ve
Di scr ete Loga ri thm Pr oblem,” Designs, Codes and Cryp-
tography, Vol. 20, N o. 1, 2000, pp. 5-40.
[13] D. C. Terr, “A Modifi cat i on of Sha nks’ Ba by-Step Giant-
Step Algorithm,” Mathematics of Computation, Vol. 69,
No . 230, 2000, pp. 767-773.
[14] B. Ver khovsky, “Generalized Baby-Step Giant-Step Alg-
orithm for Discrete Logarithm Problem,” Advances in
Decision Technology and Intelligent Information Systems ,
International Institute for Advanced Studies in Systems
Research and Cybernetics, Baden-Baden, 2008, pp. 88-
89.
[15] R. Zucche rato, “The Equivalence between Elliptic Curve
and Quadratic Function Field Discrete Logarithms in
Characteristic 2,” Algorithmic Number Theory Seminar

B. VERKHOVSKY
644
ANTS-III, Lecture Notes in Computer Science, Springe r,
Berlin, Vol. 1423,1998, pp . 621-638.
[16] J. P. Pollard, “A Mont e Carlo Method for F act ori zation,”
BIT Numerical Mathematics, Vol. 15, No. 3, 1975, pp.
331-334.
[17] C. Pomerance, J. W. Smith and R. Tuler, “A Pipeline
Architecture for Factoring Large Integers with the Qua-
dratic Sieve Algorithm,” S IAM Journal on Computing,
Vol. 17, No. 2, 1988, pp. 387-403.
[18] B. Verkhovsk y, “Multiplicative Inverse Algorithm and its
Complexity,” Proceedings of International Conference
on System Research, Informatics & Cyber netics , Baden-
Baden , 28-30 July 1999, pp. 62-67.
APPENDIX
Numeric example as an exercise
Let p = 5,000 ,491 ; t he n
1990 5051p−= ×
Let
11
2 and 1020305gh= =
.
In this ca se DLP(1) is
( )
1
21020305mod5000491
x
=
,
where the unknown
[ ]
1
1, 1xp∈−
.
The DLP(1) is decomposable into two sub-problems:
DLP(2):
( )
2
22
mod
x
ghp
= {see ( 4)-(6)}, wher e
[] []
22
1, 1,5051xq∈=
;
and DLP(3):
( )
3
33
mod
x
gh p=
{see (15) and (16)},
where
[ ] [ ]
33
1,1,990xq∈=
.
Therefore
12 23
xx qx= +
.
Remark5: The r eader n ow has an opportunity to solve
this problem himself since values required for the de-
composition are purposely omitted.
From DLP(2) and DLP(3) we find that
2
1947 5051x= <
;
and
3
470 990x= <
.
Finally,
1
194750514702375917.x=+×=
Overall complexity: the storage requirement for DLP
(2) and DLP(3) equal to 71 and 31 respectively, yet the
size of required storage for the DLP(1) is 2236, i.e. al-
most 32 times larger .