Constructing the digital signature scheme based on the discrete logarithmic problem

Information technology & Applied mathematics 
L. V. Tuan, B. T. Truyen, L. D. Tan, “Constructing the digital ... logarithmic problem.” 44 
CONSTRUCTING THE DIGITAL SIGNATURE SCHEME 
BASED ON THE DISCRETE LOGARITHMIC PROBLEM 
Le Van Tuan1,*, Bui The Truyen2, Leu Duc Tan3 
Abstract: In this report, the DSA digital signature scheme has been introduced. 
Based on these digital signature scheme, a new digital signature scheme on the ring 
of Zn is developed. Its computing complexity is similar to the DSA and getting rid of 
some unwanted disadvantages of the DSA digital signature scheme and can be 
applied in practice. 
Keywords: Digital Signature Scheme, Discrete logarithmic problem, Hash Function. 
1. INTRODUCTION 
Nowadays, the digital signature plays an important role for authentication, 
integrity, information security. Therefore, it has been being applied in many 
organizations and countries over the world, such as the DSA digital signature 
scheme of US [7], the GOST digital signature scheme of Russia, or Okamoto’s key 
distribute system based on the identification information [8]... However, these 
schemes’ standards of parameters are often published and they are applied for 
commercial purpose, if they are used in defense security area, the information 
highly runs the risk of being unsafe. So, developing the digital signature schemes is 
a researching trend of many countries and the code scientists in the world. [1], [2], 
[8]. In this study, we have studied and developed the digital signature scheme 
based on the ring of Zn safe based on the complication of discrete logarithmic 
problem on ring Zn. This new digital signature scheme can be applied in practice. 
2. THE DEFINITION OF FUNCTIONS 
Definition 2.1. The Number function converts a binary string into an integer 
that does not exceed T bits, notated Number: ℕ {0, 1}H ℤ. 
Definition 2.2. Random function: The random function is a function that 
randomly takes an integer in [a, b], a random number (a, b). 
Definition 2.3. The bitlength (m) function returns the size of m as how many 
bits 
Definition 2.4. A||B is a connection between the string A with the string B. 
3. DSA DIGITAL SIGNATURE SCHEME 
3.1. DSA parameters 
p is a prime, its length is bit, bitlength(p)= L. 
q is a divisor prime of p 1, bitlength(q)= N. 
g is a primitive element of subgroup q on Zp, 0< g < p 
x is the private key that must be kept in secret; x is randomly chosen or 
pseudorandomly in [1, q–1]. 
y is the public key, where y = gx mod p. 
Research 
Journal of Military Science and Technology, Special Issue, No. 51A, 11 - 2017 45
k is a secret number for each message (another name is session key); k is 
randomly chosen or pseudorandomly in [1, q–1]. 
Set of (p, q, g, x) is also called private key and set of (p, q, g, y) is a public 
key of signer. 
3.2. Signature generation algorithm 
Algorithm 3.1[7][10]: 
Input: (p, q, g, x), k, M. 
Output: (r,s). 
1. z  Number(N, Hash(M)). 
2. k  Random(1, q). 
3. r  (gk mod p) mod q. 
4. w  (z + x.r) mod q. 
5. if (r = 0) or (w = 0), then go to 2. 
6. s  (k 1.(z + x.r)) mod q. 
7. return (r, s). 
3.3. Signature verification algorithm 
Algorithm 3.2 [7], [10] 
Input: (p, q, g, y), (r,s), M. 
Output: "accept" or "reject". 
1. w  s 1 mod q. 
2. z Number(N, Hash(M)). 
3. u1  (z.w) mod q. 
4. u2  (r.w) mod q. 
5. v  ((gu1.yu2) mod p) mod q. 
6. if (v = r) then return "accept" Else return "reject". 
3.4. Computing complexity 
The computing complexity of the algorithm 3.1 is focused on method gk mod 
p. According to [6, p176], if bitlength (p) = L, bitlength (q) = N, the computing 
complexity of gk mod p ≈ O(logk.L2). If ML is a computing complexity for a 
multiplication on the field Zp with bitlength (p)= L and MN the computing 
complexity for a multiplication on the field Zq with bitlength (p)= N. If bitlength(k) 
≈ N, the charge of the algorithm 3.1 is estimated as below: 
 CG N.(ML + MN) (3.1) 
The computing complexity of algorithm 3.2 is centered on the statement of 
step 5 with two powers ((gu1.yu2) mod p) mod q. If bitlength (u1) ≈ N bitlength (u2) 
≈ N, total charge for algorithm 3.2 is estimated as below: 
Cv 2N(ML + MN) (3.2) 
3.5. The security of DSA digital signature scheme 
Information technology & Applied mathematics 
L. V. Tuan, B. T. Truyen, L. D. Tan, “Constructing the digital ... logarithmic problem.” 46 
The security of DSA digital signature scheme is displayed on the difficulty 
that generates the valid signature not for the owner of parameter x or that called 
“forging signature”. Indicatively, signature forging is generated when a discrete 
logarithm problem is solved on Zp or Hash function is collided, so FIPS_186-4 
standard [7] proposed the size of bit of the L and N parameter that would allow the 
DSA to be safe until 2030 as follows: (L, N) = (2048, 224), (L, N) = (2048, 256) 
and (L, N) = (3072, 256). However, when the primitive element g is published, that 
makes the DSA digital signature scheme unsafe in some of the situations as 
following: 
The first situation: While signing the message M, if the session key is 
revealed, the secret key x is calculated by the following formula: 
s = (k 1(z + r.x)) mod q 
The secret key x is computed easily using the following formula: 
x = ((s.k z).r 1) mod q 
This situation is illustrated as follows: The message m is considered, which 
is transformed by the Hash function SHA-512 and the output is M as follows: 
M=97975747105107409187956387180507750847513881963918549765479
880765663033851160001447900781761796849869035947103240517957798729
04918107245447649435608188242 
The value of the prime number p is: 
p=11242439595922330094500086844804966357759313431812385371494
511369847330693855087879539343469849551078435848382192561802575175
142455951043851140468418943323 
The value of prime q is as follows: 
q=1533291864970491990937935102336166269334618134678016648433 
The value of the primitive element g is: 
g=10078664070544453678464709258084804131491365192204951024927
548083774068483673108796539309434316671809670409438483987936673806
832475458540206862060143901544 
The secret key x is: x=74679656459306509739026621399 
The public key is calculated by the formula y = gx mod p, the value y is: 
y=25356434363194005296219381386234511997842772125732011576745
964039509236125101457653326120201899969767766769245813695835554616
78797023907419768950517837742 
Session key k=36914925716335327919902465072. 
The signature (r, s) is calculated as follows: 
r=182506323373540150306991765601851814823939026112244878180 
s=1364155657594448977789831809839374109626537375756543450808 
If the session key k is revealed, the secret key x is calculated as follows: 
x=((s.k z).r 1) mod q. The value z = Number(N, Hash(M)). 
Research 
Journal of Military Science and Technology, Special Issue, No. 51A, 11 - 2017 47
While 
z=1718579994752701761185453037319519709545839390727609025874 
s.k=5035770476561765474814810107577845641249213573792850649717
0831890443345548356570178176 
(s.k-z) mod q = 
524050766533797319315236385558804362401516138504649902691 
r 1 mod q= 
997958988071514117853806215293691244299223701750102569501 
x =74679656459306509739026621399. 
The second situation: two different messages are signed with the same 
session key k (using the same key). If the session key of the message M and M is k 
and the two signatures corresponding to M and M' are respectively (r, s) and (r, s'). 
The secret key x will be found by the attacker as follows: The first z and z’values 
are calculated from the formula z = Number (N, Hash (M)) và z' = Number (N, 
Hash (M')), then s and s' are calculated as follows: 
s= (k 1(z + r.x)) mod q k= s-1(z+r.x) mod q (*) 
s'= (k 1(z' + r.x)) mod q k= s’-1(z’+r.x) mod q (**) 
From (*) and (**) the equation is as following: 
s-1 (z+r.x)= s’-1 (z’+r.x) mod q s-1z- s’-1z’= (s’-1 s-1).r.x mod q, from this 
equation it is easy to calculate the secret key x as follows: x= r-1(s-1.z-s’ 1z’) (s’-1 
s-1)-1 mod q. 
This situation is illustrated as follows: when the message is m, which is 
transformed by the Hash function SHA-512 and the output is M as follows: 
M=97975747105107409187956387180507750847513881963918549765479
880765663033851160001447900781761796849869035947103240517957798729
04918107245447649435608188242 
z=1718579994752701761185453037319519709545839390727609025874 
p=11242439595922330094500086844804966357759313431812385371494
511369847330693855087879539343469849551078435848382192561802575175
142455951043851140468418943323 
q=1533291864970491990937935102336166269334618134678016648433 
g=10078664070544453678464709258084804131491365192204951024927
548083774068483673108796539309434316671809670409438483987936673806
832475458540206862060143901544 
x=74679656459306509739026621399 
y=25356434363194005296219381386234511997842772125732011576745
964039509236125101457653326120201899969767766769245813695835554616
78797023907419768950517837742 
k= 36914925716335327919902465072 
r= 182506323373540150306991765601851814823939026112244878180 
Information technology & Applied mathematics 
L. V. Tuan, B. T. Truyen, L. D. Tan, “Constructing the digital ... logarithmic problem.” 48 
s= 1364155657594448977789831809839374109626537375756543450808 
When the message is m’, which is transformed by the Hash function SHA-
512, its output is M’ as follows: 
M’=1555457977903788052707047276246170107839826966119437765908
551907661193845442947767748147758127032282855927340310116634922731
918069707272168480196212609551 
Z' is calculated by the formula as follow: z' = Number (N, Hash (M')) 
z’= 2686783626449795392261088445951789906711383394607353090575 
p=11242439595922330094500086844804966357759313431812385371494
511369847330693855087879539343469849551078435848382192561802575175
142455951043851140468418943323 
q=1533291864970491990937935102336166269334618134678016648433 
g=10078664070544453678464709258084804131491365192204951024927
548083774068483673108796539309434316671809670409438483987936673806
832475458540206862060143901544 
x=74679656459306509739026621399 
y=25356434363194005296219381386234511997842772125732011576745
964039509236125101457653326120201899969767766769245813695835554616
78797023907419768950517837742 
k=36914925716335327919902465072 
r=r’=182506323373540150306991765601851814823939026112244878180 
s’= 419930701966257575864048550021807565165401949643752549481 
In this situation, the secret key x is calculated by the formula as follow: 
x= r-1(s-1.z-s’ 1z’) (s’-1 s-1)-1 mod q. Where: 
s’ 1mod 
q=1104369623657571975932291813648449955114049489078722571641 
s’ 1z’mod 
q=606082038342155792558174208526507093346465357060780120714 
s-1 mod q 
=1451278297840009702777459600785951165698531270580902059174 
s-1.z mod q= 
1313713634264547240570981004522210825585496954765626822777 
(s-1.z-s’ 1z’) mod q= 
707631595922391448012806795995703732239031597704846702063 
r 1 mod q= 
997958988071514117853806215293691244299223701750102569501 
r-1(s-1.z-s’ 1z’) mod q, 
 where q=12536132561166344302362245931756388805698010284 
7137437 0307 
Research 
Journal of Military Science and Technology, Special Issue, No. 51A, 11 - 2017 49
(s’-1 s-1) mod q= 
1186383190788054264092767315198665058750136353175837160900 
(s’-1 s-1)-1 mod q= 
1004917863501878505091781121120933399705847132586335489436 
The secret x can be easily calculated as follows: 
x=74679656459306509739026621399. 
It’s noted that if a session key is used for both signatures, both signatures of 
the component r will be the equal value, but if the both signatures of value r are of 
the equal value, the session key for both signatures may not be of the equal value. 
4. CONSTRUCTION THE NEW SIGNATURE SCHEME 
4.1. Parameters domain 
n = p.q with p, q are primes and n-factorization is a difficult problem; m is 
private, m = p1.q1 where p1, q1 are primes and p1 | (p 1), q1 | (q 1), p1 ∤ (q 1), q1 
∤ (p 1); mbit= bitlength (m). 
g is a primitive element, 0 is cyclic subgroup on Zn. 
x is chosen randomly in (1, m 1) and x is private. 
y is public, where y = gx mod n. 
k is chosen randomly in (1, m 1), k is the unique private number for each 
message (also known as session key) 
the set of five values (n, m, g, x, m) are the secret key and set of four values 
(n, g, y, mbit) are the public key. 
4.2. Generation signature 
Algorithm 4.1. 
Input: (n, m, g, x, mbit), M.//mbit= bitlength (m) 
Output: (r,s). 
1. z0; tg0; 
2. While (z=0) or ((tg,m) 1) 
3. k Random(1,m-1) 
4. r  gk mod n. 
5. z  number (mbit,H(M||r))// The output is the value z, its size is not 
more than mbit 
6. tg(z + x) mod m 
End while // The loop stops when z + x exists the inverse value 
7. s  (k.(z + x) 1) mod m) 
8. return (r, s). 
4.3. Verifying signature 
Algorithm 4.2. 
Information technology & Applied mathematics 
L. V. Tuan, B. T. Truyen, L. D. Tan, “Constructing the digital ... logarithmic problem.” 50 
Input: M, (r, s), (n, g, y, mbit)// mbit= bitlength (m). 
Output: "True" hoặc "False". 
1. z  number(mbit,H(M||r))// value of z < a mbit number. 
2. u  (gs.z.ys) mod n. 
3. if (u = r) return "True" else return "False". 
4.4. Correctness of the algorithm 
It's easy to see that: 
 (gs.z.ys) mod n= mxzkmzxzk yg mod)(mod)( 11 mod n 
= 
 mxzkxmzxzk gg mod)(.mod)( 11 mod n = mxzxzkg mod))(( 1 mod n 
= gk mod n= r and the correctness of the digital signature scheme is proven. 
4.5. Example 
Algorithms 4.1 and 4.2 are illustrated by the following example: 
Parameter generation: 
If the set of parameters of the new digital signature scheme are as following: 
The value of the prime number p is: 
11242439595922330094500086844804966357759313431812385371494511
369847330693855087879539343469849551078435848382192561802575175142
455951043851140468418943323 
p1 is a prime divisor of p-1 and its value is as follows: 
1533291864970491990937935102336166269334618134678016648433 
The value of prime q is: 
13000056097250407151278816580424694762126189598035228608160655
285286101077083814637602139866821888168231129087200207881652034129
346833758707500099753756233 
q1 is a prime divisor of q-1 and its value is as follows: 
693542050471501789153827056172377247128936626662022537753 
n = p.q and its value is as follows: 
14615234541693949095609152061384787442361691672134939078054914
055679365597736560216223659339938656710844125398866980864339936146
676123711815535232083000016596755394644166264672320085434477785326
142760988239038546633490482735589595127349439001902078113883338170
6728100718302316964348020060060727207161984982259 
The value of the primitive element g is as follows: 
13842455697058353097307630854947301896596179241034192521246818
029097994496972611578658769231921323332422390782921780701310024839
006077658293470388919994031736897350400418010831205276117348900655
500094697320878687677035834861273949911065633867432044330673823599
1077062669737065186351843811074484096101625162002 
Research 
Journal of Military Science and Technology, Special Issue, No. 51A, 11 - 2017 51
m = p1.q1 and is the order of g. The value of m is as follow: 
10634023840029080625322721134200576728589515343869740251998541
32745719623145728624346706867226494922194398270791049 
The value of the private key x is as follows: 
38980919841877720028126597041593821048381262206683380473759156
9778957938885573951169495 
y= gx mod n and is the public key. Its value is as follows: 
18081314126463681707208105600531354803219444942937364226766655
862136409936345298373098164575398685336030305202707520919329530142
743066526126436645106579246757152798713274411382431562410098563222
366335577278553026548503978941730278481202144166631848019867446163
313952951531181009401297673693032623866599834593 
Note: The prime numbers are used in this example that will be generated by 
the algorithm in [3] [5]. With the set of the parameter above, the result of signature 
generation and signature verification is as follows: 
Signature generation (algorithm 4.1) 
Input: Message M 
Output: (r, s) is signature of M 
Step 1: If the size of the message T is 13.87 Mb. Hash function used in 
example is SHA-512, denoted H and M = H (T). M is represented by the Hex 
number as follows: 
BB118C3045EB6214275894575B6CD7036504379792BAB744E3B6EB6F
DF4213D0921E67819974A7654616CFF6214A056398C026848CD131C757907D
280EE88552. 
The decimal value of M is as follow: 
97975747105107409187956387180507750847513881963918549765479880
765663033851160001447900781761796849869035947103240517957798729049
18107245447649435608188242 
Step 2: Number k is randomly selected in (1, m-1), the result is as follows: 
k= 65559053911122334369117687706 
Step 3: The value of r is calculated by the formula below: 
r  gk mod n, the result is as follows: 
r=700075376919223825896662238446486887192303123740882929410199
049353139983819732156200176461364426777339235615578940280578869971
077324767508786541362979546740656434723749239588803228906749181225
476240293095750593205272535388486577819602972736032978332611470815
35121991155908427229286352961144505949844357743176 
Step 4: z= number (N, M||r), the result is follows: 
z=155478582251494173649984772551104614294175933861221891771125
74402314481921039872402872063159318107139103701961573714 
Information technology & Applied mathematics 
L. V. Tuan, B. T. Truyen, L. D. Tan, “Constructing the digital ... logarithmic problem.” 52 
Step 5: s is calculated by formula as follow: s= (k.(z + x) 1) mod m. If s does 
not exist (because there is no inverse of (z + x)) then goes to step 2), value of s is: 
s=577507141296403366601531541536948842155948696090904353917855
626403078896511057634111000995527913016381540600291993 
The result of signature verification (Algorithm 4.2): 
Input: 
Pair of (r, s) is computed in algorithm 4.1 
M=97975747105107409187956387180507750847513881963918549765479
880765663033851160001447900781761796849869035947103240517957798729
04918107245447649435608188242 
Step 1: computed z= number (mbit, M||r), the result is follows: 
Z=15547858225149417364998477255110461429417593386122189177112
574402314481921039872402872063159318107139103701961573714 
Step 2: u is computed by formula as follow: u  (gt.ys) mod n, where t=(s.z) 
mod m. Value of t is as follow: 
t=520438263576991435816449931563023825609689069787196582958685
56660326006851318852877557879289120311977248897224820. Then value of 
gt mod n is: 
13844681836188787050490416867068509771590285902016616400783650
957734311355486486435527647703334553405840029394487960028532497459
814389197572124605811554459426661757447249592896271588855957968225
033434748506994886694757244516753159045582211664278264328337982381
9411858385451221424397855113087868438435419833685. 
With value of s is: 
s=577507141296403366601531541536948842155948696090904353917855
626403078896511057634111000995527913016381540600291993. 
The value of ys mod n is as follow: 
12816170749087009435477966847753686635354362533420059134229242
260063485426448713694511362952689978278402176620915385550216450289
169708686105622979392488244289452879294305003689544189051410160007
820070589877996495733249044611900436776739808890379714645276294533
6041348138585462065519811954121693711426715412552 
Then value of u with u (gt.ys) mod n as follow: 
u=70007537691922382589666223844648688719230312374088292941019
904935313998381973215620017646136442677733923561557894028057886997
107732476750878654136297954674065643472374923958880322890674918122
547624029309575059320527253538848657781960297273603297833261147081
535121991155908427229286352961144505949844357743176 
Step 3: Check both values: u and r show that u = r, so the pair of (r, s) is the 
signature of the message M. 
4.6. Computing complexity 
Research 
Journal of Military Science and Technology, Special Issue, No. 51A, 11 - 2017 53
There is at least one loop in the algorithm 4.1. The computing complexity for 
each of these loops is the total of the computing complexity of gk mod n and the 
computing complexity of (x + z)-1 mod m. According to [6], the computing 
complexity of gk mod n is approximately O (logk.L2), where L= bitlength (n). 
Because of (x+z) 1 mod m = mod m, where (m) = (p1 1) (q1 1), so 
the computing complexity of (x + z)-1 mod m is approximately O(log φ(m).N2), in 
which N = bitlength (m). If ML denotes for the computing complexity of a 
multiplication on ring Zn, where bitlength (n) = L and MN denote for the computing 
complexity of a multiplication on Zm, where bitlength (m) = N, then the computing 
complexity for each of these loops is as follow: 
N(ML + MN) 
The loop will exit if gcd (z + x, m) = 1 or (z + x) must be have an inverse in 
Zm. Probability (z + x) exists its inverse element is as follow: 
Prob (gcd(z + x, m) = 1)= 
m
φ(m)
= 
m
qp )11)(11( 
If the m is a large enough number, then Prob (gcd (z + x, m) = 1) 1, so the 
computing complexity of the signature generation algorithm denoted by CG is as 
follows: 
 CG NML + NMN (4.1) 
 The complexity of algorithm 4.2 is mainly focused on the complexity of 
exponentiation gs.z.ys mod n, so gs.z.ys mod n= gs.z.gs.x mod n. If ML denotes for the 
computing complexity of a multiplication on ring Zn, where bitlength (n) = L and 
MN denotes for the computing complexity of a multiplication on Zm, where 
bitlength (m) = N, then the computing complexity of algorithm 4.2 is as follow: 
Cv 2NML. (4.2) 
4.7. Some comparisons of the new digital signature scheme and the DSA 
Comparison about the security: 
Scheme the new digital signature scheme is similar to scheme DSA, so the 
analysis of abilities to forge signatures can be displayed similarly to DSA. 
However, there is a basic difference between the DSA digital signature scheme and 
the new digital signature scheme as follow: the order of g is published on the DSA 
digital signature scheme, but on the new digital signature scheme, the order of g 
is not published. From this difference, when the new digital signature scheme is 
displayed there’s no revealing or coinciding session key as using DSA. Moreover, 
when key session of the new digital signature scheme is revealed, it’s difficult to 
forge the signatures. 
Charge of computing: 
Basing on formula 3.1 and formula 4.1, the charge of computing of DSA 
signature generation algorithm is similar to the new digital signature scheme. 
Similarly, the computing charge of signature verification algorithm on the new 
digital signature scheme is similar to the DSA scheme (based on formula 3.2 
and 4.2). 
Information technology & Applied mathematics 
L. V. Tuan, B. T. Truyen, L. D. Tan, “Constructing the digital ... logarithmic problem.” 54 
5. EXPERIMENT 
In this experiment, the length of keys on the scheme the new digital signature 
scheme and the DSA scheme gradually is 1024, 1280, 1536, 1792, 2048 (bits). The 
message’s size of the testing is 18.87 MB. The time of experiment for each set of 
parameter is 1000 times. The Hash function SHA 512 used in signing and confirms 
algorithm of DSA digital signing scheme and the new digital signature scheme 
digital signing scheme. The test program is written by C ++ programming 
language, compiled by QT Creater and installed on Laptop in which its processor 
is a Core2 Duo 2.2 GHz and its memory is 2GB. The experimental parameter of 
the DSA signature scheme and the new digital signature scheme are generated by 
the algorithm [5], results are listed in the following table: 
Table 1. Consulting table of signing generation and verification. 
Key size(bit) Generation 
time 
Verification 
time 
DSA New DSA New 
1024 1.416 1.539 6.836 5.527 
1280 1.814 1.953 10.765 8.931 
1536 2.89 3.182 14.813 13.3 
1792 3.5 4.916 19.18 17.13 
2048 5.138 5.929 22.59 26.398 
In order to compare the signing speed between the DSA scheme and the new 
signing scheme. The test results in table 1 is illustrated by the following graph. 
Figure 1. The signature generation graph of the DSA 
and the new digital signature scheme. 
Similarly, based on Table 1, the relationship between the wasting time and 
key size to verify the digital signature scheme DSA and the new digital signature 
scheme is depicted by graph as follow: 
Research 
Journal of Military Science and Technology, Special Issue, No. 51A, 11 - 2017 55
Figure 2. The signature verification graph of the DSA scheme 
and the new digital signature scheme. 
Figure 1 and Figure 2 shows that the computing complexity of the signature 
generation algorithm and the signature verification algorithm of the the new digital 
signature scheme and the DSA digital signature scheme is equivalent. The graphs 
(Figure 1 and Figure 2) show that the results of the test and the results of the 
mathematical analysis shown in formula (3.1), (3.2), (4.1) and (4.2) is similar. 
6. CONCLUSIONS 
The authors' research results are a new digital signature scheme, in which its 
security is based on discrete logarithm problem in the ring of Zn. This new digital 
signature scheme has overcome some of the defect of the DSA the digital signature 
scheme (shown in 3.5). Based on the mathematical theoretical analysis and the test 
results, the computing complexity of the new digital signature scheme and the 
computing complexity of the DSA digital signature scheme are equivalent. 
However, if this digital signature scheme can be applied in practice, it should be 
estimated the security and the computing complexity, these research problems will 
be introduced in the next article. 
REFERENCES 
[1]. Lưu Hồng Dũng “Phát triển một dạng lược đồ chữ ký số mới”, Hội thảo quốc 
gia lần thứ XVI, 13-14-11-2013. 
[2]. Lưu Hồng Dũng “Phát triển lược đồ chữ ký số tập thể”, Luận án tiến sỹ, Hà 
nội – 2014. 
[3]. Lều Đức Tân “Số nguyên tố và đa thức nguyên thủy”, Hà nội – 2002. 
[4]. Lê Văn Tuấn, Lưu Hồng Dũng, Nguyễn Tiền Giang, “Phát triển lược đồ chữ 
ký trên bài toán phân tích số,” Tạp chí Nghiên cứu KH& CNQS - Đặc san 
CNTT, 04 – 2014, ISSN 1859 – 1043. 
[5]. Lê Văn Tuấn, Bùi thế truyền “Xây dựng thuật toán sinh số nguyên tố tất 
định”, Tạp chí Nghiên cứu KH& CNQS, Số 42, 4- 2016. 
[6]. D.R Stinson, Cryptography: Theory and Practice, CRC Press 2003. 
Information technology & Applied mathematics 
L. V. Tuan, B. T. Truyen, L. D. Tan, “Constructing the digital ... logarithmic problem.” 56 
[7]. FIPS PUB 186-4,“Digital Signature Standard (DSS)”, 2013. 
[8]. OKAMOTO E, Key distribution systems based on identification information. 
Proc. Of Crypto -1987. 
[9]. Richard Crandall, Carl Pomerance. “Prime Numbers, A Computational 
Perspective”, Second Edition, Springer Science + Business Media, Inc, 2005. 
[10]. https://en.wikipedia.org/wiki/Digital_Signature_ Algorithm. 
TÓM TẮT 
XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ MỚI DỰA TRÊN 
BÀI TOÁN LOGARIT RỜI RẠC 
Bài viết này giới thiệu lược đồ chữ ký số DSA. Dựa trên lược đồ chữ ký số 
DSA, chúng tôi phát triển một lược đồ chữ ký số mới trên vành Zn có độ phức 
tạp tính toán tương đương với lược đồ chữ ký số DSA, khắc phục được một số 
nhược điểm của lược đồ chữ ký số DSA và có thể ứng dụng trên thực tế. 
Từ khóa: Lược đồ chữ ký số, Hàm băm. 
Received date, 13th Sep., 2017 
Revised manuscript, 10th Oct., 2017 
Published, 1st Nov., 2017 
Author affiliations: 
 1 Academy of Military Science ; 
 2 Military Technical Academy; 
 3 Academy of Cryptography Technique. 
 * Corresponding author: levantuan71@yahoo.com.