Anew construction method of digital signature algorithms

s x is enough to 
As well as methods that have been proposed in [1], [2], [3], authenticate is U. 
[4], an advantages of the newly proposed method here is Assuming that the secret key of the signer x is randomized 
that it can be used for the purpose of developing different in the range (1,p) and the corresponding public key y is 
digital signature schemes to choose suitably to the formed from x in accordance with: 
 x
requirements of applications in practice. y = g mod p (1.1) 
 Here, p is the chosen prime number so that solution of the 
 problem DLP(g,p) (y) is difficult, g is the birth particle 
2. Construction of digital signature algorithm of the group ℤp* has the degree of q, with q|(p-1). 
 Assume that (r,s) is the signature on the message M, u is 
2.1 Construction method one value in the range (1,q) and r is calculated from u by 
 the formula: 
This newly proposed sheme is built up based on difficulty 
 r = g u mod p
of the Discrete Logarithm Problem [5]. Discrete (1.2) 
logarithm problem – DLP(g,p) can be stated as follows: And s calculated from v by the formula: 
 v
Let p be prime number, r is the birth particle of the group s = g mod p (1.3) 
ℤp*. For each positive integer y∈ ℤp*, find x satisfying Here: v is also one value in the range (1,q). 
the equation: Also assume that the verifying equation of the scheme is 
 x = formed: 
 g mod p y 
 Manuscript received December 5, 2016 
 Manuscript revised December 20, 2016 
54 IJCSNS International Journal of Computer Science and Network Security, VOL.16 No.12, December 2016 
 Table 1. Algorithm for formation parameter and key 
 f (M , f (r,s)) f (M , f (r,s)) f (M , f (r,s)) 
 s 1 ≡ r 2 × y 3 mod p Input: p, q, x. 
 Output: g, y. 
With f (r, s) is the function of r and s. Consider the case: [1]. select h: 1<h<p 
 f (r,s) = r × s mod p ← ( p−1)/ q
 [2]. g h mod p 
 k
 = g mod p (1.4) [3]. if ( g = 1) then go to [1] 
Where k is a randomly chosen value in the range (1,q). ← x
 [4]. y g mod p 
Set: 
 k [5]. return {g,y} 
 g mod p = Z (1.5) Remarks: 
Then, the verifying equation can be taken to the form: (i) p,q: primes satisfying conditions: 
 ( ) ( ) f (M ,Z )
 f1 M ,Z f2 M ,Z 3 = × +
 s ≡ r × y mod p (1.6) p N q 1, N=1,2,3,. 
From (1.1), (1.2), (1.3) and (1.6) we have: (ii) x,y: secret, public keys of signing object U. 
 ( ) ( ) x. f (M ,Z )
 g v. f1 M ,Z ≡ g u. f2 M ,Z × g 3 mod p
 (1.7) Table 2. Algorithm for formation of signature 
From (1.7) infer: Input: p, q, g, x, M. 
 v× f1 (M ,Z) ≡ [u × f 2 (M ,Z) + Output: (r,s). 
 + x× f (M ,Z)]modq [1]. select k: 1<k<q 
 3 (1.8) 
 ← k
So: [2]. Z g mod p 
 −1
 v = (u × f1 (M ,Z) × f 2 (M ,Z) ←
 [3]. w1 f1(M , Z) 
 −1
 + x× f1 (M ,Z) × f3 (M ,Z)modq ←
 (1.9) [4]. w2 f 2 (M , Z) 
On the other hand, from (1.2), (1.3) and (1.4) we have: 
 w3 ← f 3 (M , Z)
 (v + u)mod q = k [5]. 
 (1.10) ← −1 ×
From (1.9) and (1.10) we have: [6]. w4 (w1 ) w2 mod q 
 [u × f (M , Z)−1 × f (M , Z) + w ← (w )−1 × w mod q
 1 2 [7]. 5 1 3 
 −1 −
 + x × f (M , Z) × f (M , Z) + u]mod q u ← (w +1) 1 × (k − x × w )mod q
 1 3 [8]. 4 5 
 = k r ← g u mod p
Or: [9]. 
 −1 v ← (u × w4 + x × w5 )mod q
 [u × ( f1 (M , Z) × f2 (M , Z) +1) [10]. 
 v
 −1 s ← g mod p
 + x × f1 (M , Z) × f3 (M , Z)]mod q [11]. 
 = k (1.11) [12]. return (r,s) 
From (1.11), infer: Remarks: 
 ∞
 −1 −1 ∈
 (i) M: the message to be signed, with: M {0,1} . 
 u = [( f1 (M , Z) × f2 (M , Z) +1) ×
 (ii) (r,s): signature of U on M. 
 −1
 (k − x × f1 (M , Z) × f3 (M , Z)]mod q
 (1.12) Table 3. Algorithm for verifying signature 
From (1.12), the first component of signature is calculated Input: p, q, g, y, {M,(r,s)}. 
by (1.2): Output: true / false. 
 u Z ← f (r, s)
 r = g mod p [1]. 
 ←
and the second component is calculated by (1.3): [2]. w1 f1 (M , Z) 
 s = g v mod p ←
 [3]. w2 f 2 (M , Z) 
with v calculated by (1.9): w ← f (M , Z)
 [4]. 3 3 
 −1
 ← w1
 v = [u × f1 (M , Z) × f2 (M , Z) + [5]. A s mod p 
 B ← r w2 × y w3 mod p
 + x × f (M , Z)−1 × f (M , Z)]mod q [6]. 
 1 3 [7]. if (A=B) then {return true} 
From here, a form of signature scheme corresponding to else {return false} 
 f (r, s) = r × s mod p = g k mod p Remarks: 
the case: is shown as (i) M, (r,s): the messages, signature need verifying. 
Table 1, Table 2 and Table 3 below. 
IJCSNS International Journal of Computer Science and Network Security, VOL.16 No.12, December 2016 55 
 (ii) If the return is true, the integrity and origin of M are 2.2 Several algorithms for signature built up under 
confirmed. Conversely, if the return is false, M is denied the proposed method 
the origin and integrity. 
It should be noted that the signature created here is not 2.2.1 The first scheme 
necessarily the pair of (r,s). From the Table 2 shows that 
the value v can be selected as the second component of the a) Structure and operation 
signature instead of s, thus reduce one calculation step in The first signature scheme proposed here - symbols LD 
the procedure for formation of signature. Indeed, if the 16.9–01, is built up under Table 1, 2 and 3 in section A 
hypothesis of the verifying equation of the scheme is = =
 with selections: f1 (M ,Z) H (M ) , f2 (M , Z) Z , 
formed: =
 ( ( )) ( ( )) f (M , f (r,v)) f3 (M ,Z) H (M )
 g v. f1 M , f r,v ≡ r f2 M , f r,v × y 3 mod p . Algorithms for formation of parameter 
 (1.13) and key, algorithm for signature and verifying signature of 
and: the scheme are described in the Table 6, Table 7 and Table 
 v k
f (r,v) = r × g mod p = g mod p (1.14) 8 below. 
Set: 
 g k mod p = Z Table 6. Algorithm for formation of parameter and key 
 Input: p, q, x. 
Then, from (1.1), (1.2) and (1.13) we also have: 
 ( ( )) Output: g, y, H(.). 
 v. f1 (M , f (r,v)) u. f2 (M , f (r,v)) x. f 3 M , f r,v
 g ≡ g × g mod p [1]. select h: 1<h<p 
 ( p−1)/ q
From here, algorithms for formation and verifying [2]. g ← h mod p 
signature of the form of the scheme corresponding to new [3]. if ( g = 1) then goto [1] 
assumptions given in Table 4 and Table 5 as follows: ← x
 [4] y g mod p . (2.1) 
 ∗
 Table 4. Algorithm for formation of signature H : {0,1} Z n q < n < p
 Input: p, q, g, x, M. [5]. select , 
 Output: (r,v). [6]. return {g,y,H(.)} 
 [1]. select k: 1<k<q Remarks: 
 ← k - H(.): Hash function (SHA, MD5, ...). 
 [2]. Z g mod p 
 ←
 [3]. w1 f1(M , Z) Table 7. Algorithm for signing messages 
 Input: p, q, g, H(.), x, M . 
 w ← f (M , Z)
 [4]. 2 2 Output: (r,s). 
 w ← f (M , Z)
 [5]. 3 3 [1]. E = H (M ) 
 −1 [2]. select k: 1<k<q 
 w4 ← (w1 ) × w2 mod q
 [6]. ← k
 −1 [3] Z g mod p (2.2) 
 w5 ← (w1 ) × w3 mod q
 [7]. − −1
 u ← (E 1 × Z +1) × (k − x)mod q
 u ← (w +1)−1 × (k − x × w )mod q [4]. 
 [8]. 4 5 r ← g u mod p
 u [5]. (2.3) 
 r ← g mod p −1
 [9]. [6]. v ← (u × E × Z + x)mod q (2.4) 
 ← × + ×
 v (u w4 x w5 )mod q ← v
 [10]. [7]. s g mod p (2.5) 
 [11]. return (r,v) [8]. return (r,s) 
 Table 5. Algorithm for verifying signature Table 8. Algorithm for verifying signature 
 Input: p, q, g, y, {M,(r,v)}. Input: p, q, g, H(.), y, M, (r,s). 
 Output: true / false. Output: true / false. 
 ←
 [1]. Z f (r, v) =
 [1]. E H (M ) 
 w ← f (M , Z)
 [2]. 1 1 ← E
 [2]. A s mod p (2.6) 
 w ← f (M , Z)
 [3]. 2 2 ← ×
 [3]. w r s mod p (2.7) 
 w3 ← f 3 (M , Z)
 [4]. B ← r w × y E mod p
 v.w [4]. (2.8) 
 A ← g 1 mod p
 [5]. [5]. if ( A = B ) then {return true } 
 ← w2 × w3
 [6]. B r y mod p else {return false } 
 b) 
 [7]. if ( A = B ) then {return true } Correctness of the scheme LD 16.9-01
 else {return false } The thing to be proved is: Let p, q are 2 primes with 
 H : {0,1}∗ Z
 q|(p-1), n , q < n < p , 1 < k, x < q , 
56 IJCSNS International Journal of Computer Science and Network Security, VOL.16 No.12, December 2016 
 x k
y = g mod p , E = H (M ) , Z = g mod p , 2.2.1 The second scheme 
 −1 −1 u
u = (E × Z +1) × (k − x)mod q , r = g mod p , a) Structure and operation 
 −1 E
s = (u × E × Z + x)modq . If: w = r × s mod p , A = s mod p , The second signature scheme - symbols LD 16.9–02, is 
 w E built up under the method stated in Table 4 and 5 in 
B = r × y mod p =
 then: A B . section A with selections: f1(M,Z) = Z, f2(M,Z) = H(M), 
Correctness of the newly proposed scheme is proved as f3(M,Z) = H(M). The algorithm for formation of 
follows: parameter and key is similar to that in the scheme LD 
From (2.4), (2.5) and (2.6) we have: 16.9–01 (Table 6), algorithms for signature and 
 E
 A = s mod p verifying signature of the scheme are described in Table 8 
 = g v.E mod p and Table 10 below. 
 (u.E−1.Z +x).E
 = g mod p Table 9. Algorithm for signing messages 
 = g u.Z +x.E mod p Input: p, q, g, H(.), x, M . 
 (2.9) Output: (r,v). 
From (2.1), (2.3), (2.7) and (2.8) we also have: [1]. select k: 1<k<q 
 w E
 B = r × y mod p Z ← g k mod p
 u.(r.s mod p) x.E [2]. (3.1) 
 = g × g mod p E = H (M )
 u.Z x.E [3]. (3.2) 
 = g × g mod p −1
 w1 = Z × E mod q
 u.Z +x.E [4]. (3.3) 
 = −1
 g (2.10) ← + × − ×
 [5]. u (w1 1) (k x w1 )mod q (3.4) 
From (2.9) and (2.10) infer the thing to be proved: 
 r ← g u mod p
A = B [6]. (3.5) 
 ← × ( + )
Safety level of the scheme LD 16.9-01 [7]. v w1 u x mod q (3.6) 
In form of the newly proposed scheme, the public key is [8]. return (r,v) 
formed from the secret key based on difficulty of the 
discrete logarithm problem DLP(g,p). Therefore, if the Table 10. Algorithm for verifying signature 
parameters {p,q,g} is selected for the problem DLP(g,p) to Input: p, q, g, H(.), y, M, (r,v). 
be difficult, the safety level of the newly proposed scheme Output: true / false. 
in terms of resistance to attacks disclosing secret key will [1]. E = H(M) 
 ← × v
be assessed by the level of difficulty of the problem [2]. w2 r g mod p (3.7) 
DLP(g,p). It should be noted that, in order for DLP(g,p) to ← v.w2
 [2]. A g mod p (3.8) 
be difficult, the parameters {p,q,g,n} can be selected 
 B ← (r × y)E mod p
similarly to DSA [6] or GOST R34.10-94 [7], with: [3]. (3.9) 
| p |≥ 512bit | q |≥ 160bit | n |≥ 160bit [4]. if ( A = B ) then {return true } 
 , , . else {return false } 
The Algorithm for verifying signature (Table 8) of the 
scheme LD 16.9-01 shows, any pair of (r,s) will be 
recognized as a valid signature of U on a message M if it b) Correctness of the scheme LD 16.9-02 
meets the condition: The thing to be proved is: Let p, q are 2 primes with 
 ∗
 E (s.r mod p) E
 H : {0,1} Z n < < < <
 s ≡ r × y mod p (2.11) q|(p-1), , q n p , 1 k, x q , 
 = x = k = ( ) = −1 ×
Here: U is signing object owning a public key y and y g mod p , Z g mod p , E H M , w1 Z E modq , 
 = −1
E H (M ) are representative value of the message M to = ( + ) × ( − × ) = u
 u w1 1 k x w1 mod q , r g mod p , 
be verified. v.w
 v = w × (u + x)modq w = r × g v mod p A ← g 2 mod p
To find (r,s) from (2.11), the first way is to select a value 1 . If: 2 , 
 E
for r in advance, then calculate s. Then (2.11) will be B = (r × y) mod p then: A = B . 
formed: Correctness of the newly proposed scheme is proved as 
 s b
 a ≡ s mod p (2.12) follows: 
Or in the second way is select s in advance then calculate r. From (3.7) and (3.8) we have: 
Then (2.11) will be formed: A = g v.w2 mod p
 r v.(r.g v mod p)
 r mod p = b (2.13) = g mod p
In both two cases, a and b constants. It is easy to see that = g v.Z mod p
 −1
solutions of (2.12) and (2.13) to find s and r is more = g Z .E.(u+x).Z mod p
difficult than solution of the discrete logarithm problem = g (u+x).E mod p
DLP(g,p). (3.10) 
IJCSNS International Journal of Computer Science and Network Security, VOL.16 No.12, December 2016 57 
From (2.1), (3.5) and (3.9) we also have: Produce and check procedures of Electronic Digital 
 B = (r × y)E mod p Signature based on Asymmetric Cryptographic Algorithm. 
 (u+x).E Government Committee of the Russia for Standards (in 
 = g mod p (3.11) Russian). 
From (3.10) and (3.11) infer the thing to be proved: 
 A = B . Thuy N.D received the B.S from 
 HUFLIT University in 2005 and M.S 
 c) Safety level of the scheme LD 16.9-02 degree from Faculty of Information 
From the Algorithm for verifying signature (Table 10) of Technology, Military Technical 
the scheme LD 16.9–02 shows that, any pair of (r,v) will Academy in 2013. My research interests 
be recognized as a valid signature if the scheme generated include cryptography, communication 
from a message M if it meets the condition: and network security. 
 v.(r.g v mod p) E
 g ≡ (r × y) mod p 
 (3.12) 
Similarly, (2.11), to find r and v from solution of (3.12) is Dung L.H is a lecture at the Military 
more difficult than solution of the problem DLP(g,p). Technical Academy (Ha Noi, Viet Nam). 
 He received the Electronics Engineer 
 degree (1989) and Ph.D (2013) from the 
3. Conclusion Military Technical Academy. 
The article proposes a method of digital signature scheme 
design based on difficulty discrete logarithm problem. An 
advantages of the newly proposed method is that it can be 
used for developing different digital signature schemes to 
choose suitably for applications in practice. Signature 
schemes of LD 16.9–01 and LD 16.9–02 presented here 
has somewhat showed the feasibility of the newly 
proposed method. 
References 
[1] Luu Hong Dung, Le Dinh Son, Ho Nhat Quang, Nguyen 
 Duc Thuy,“DEVELOPING DIGITAL SIGNATURE 
 SCHEMES BASED ON DISCRETE LOGARITHM 
 PROBLEM”, the Eighth National Scientific Meeting of 
 Basic Research and Information Technology Applications 
 (FAIR 2015), ISBN: 978-604-913-397-8. 
[2] Luu Hong Dung, Hoang Thi Mai, Nguyen Huu Mong “A 
 form of signature scheme built up based on the digital 
 analysis problem”, the Eighth National Scientific Meeting 
 of Basic Research and Information Technology 
 Applications (FAIR 2015), ISBN: 978-604-913-397-8. 
[3] Luu Hong Dung, Ho Ngoc Duy, Nguyen Tien Giang, 
 Nguyen Thi Thu Thuy, “Development of a new form of 
 digital signature scheme”, the Proceedings of the Sixteenth 
 National Seminar: Some Selected Issues of Information 
 Technology and Communication - Da Nang. 
[4] Hoang Thi Mai, Luu Hong Dung, “A form of signature 
 scheme built up based on the digital analysis problem and 
 the square root problem”, Journal of Science and 
 Engineering - Military Technical Academy No. 172 
 (Journal of IT and Communication, No.7 - 10/2015), page: 
 32 – 41. ISSN: 1859 – 0209. 
[5] T. ElGamal, “A public key cryptosystem and a signature 
 scheme based on discrete logarithms”, IEEE Transactions 
 on Information Theory, Vol. IT-31, No. 4. pp.469–472. 
[6] National Institute of Standards and Technology. NIST FIPS 
 PUB 186-3(2013). Digital Signature Standard, U.S. 
 Department of Commerce. 
[7] GOST R 34.10-94. Russian Federation Standard. 
 Information Technology. Cryptographic data Security.