A new method for constructing digital signature algorithm based on a new key scheme

 May – June 2020 
ISSN: 0193-4120 Page No. 2254 - 2260 
2254 
Published by: The Mattingley Publishing Co., Inc. 
 A New Method for Constructing Digital Signature 
Algorithm based on a New Key Scheme 
[1] 
Van Luu Xuan, 
[2] 
Binh Nguyen Luong, 
[3] 
Dung Luu Hong 
 [1] People’s Security Academy, [2] Military Technology Academy, [3] Military Technology Academy 
[1] vanlx.hvan@gmail.com, [2] nluongbinh@yahoo.co.uk, [3] luuhongdung@gmail.com 
Article Info 
Volume 83 
Page Number: 2254 - 2260 
Publication Issue: 
May - June 2020 
Article History 
Article Received: 11August 2019 
Revised: 18November 2019 
Accepted: 23January 2020 
Publication: 10 May2020 
Abstract: 
E-governance is the latest trend in many countries in which the government is using the 
online system for delivering government services to citizensand the Digital Signature is 
used to validate contents and authorize users who are involving in the E-governance 
system. Although there are many digital signature schemes currently known as: RSA, 
Elgamal,... the approach of improving the safety level of digital signature schemes based 
on the hardness of solving simultaneous difficult assumptions has still remained 
underdeveloped and attracted rising attentions from researchers. In this research, with 
the target to improve safety level of digital signature algorithms, we present the proposed 
method for constructing digital signature algorithms which is based on a new key 
scheme. This new key format is constructed using a new difficulty problem without 
high-efficiency solution and it can be applied to construct digital signature algorithms. 
According to this research, a high-security digital signature class can be construct by the 
proposed method in some actual situation. 
Keywords: Digital Signature Algorithm, Public Key Cryptosystem, Discrete Logarithm 
Problem, Elgamal Cryptosystem. 
I. INTRODUCTION 
Nowadays, in the development of Industry 4.0, a lot 
of information exchange and control activities have 
been carried out over the network. Along with the 
convenience, information security is potentially risky, 
increasingly important and needs special attention. All 
online transactions need to ensure the integrity and 
identity of the sender of the message. Therefore, 
digital signatures will be widely used in the near 
future. In addition to applying classic digital signature 
algorithms such as RSA, Elgamal [12], ..., scientists 
have researched and developed other digital signature 
algorithms to meet in some specific cases, for example 
improving safety or improving the efficiency of the 
algorithm. As research improves the security of digital 
signature algorithms, a number of studies have 
investigated the development of difficult problems in 
number theory. By combining the solvability of these 
difficult problems, some new digital signature 
algorithms have been constructed and developed. 
In [1-11], several studies have combined hard 
problems of discrete logarithm and integer 
factorization to develop digital signature algorithms. 
In line with this research direction, we propose a 
method to build a new digital signature algorithm 
based on a new key scheme. The new key scheme was 
developed from a root problem and discrete logarithm 
problem, which is difficult to find an effective 
solution. Therefore, digital signature scheme based on 
this new key scheme is secure, and can be applied in 
many actual situations. 
II. CONSTRUCTING DIGITAL SIGNATURE 
ALGORITHM BASED ON A NEW KEY SCHEME 
A. Proposed key scheme 
Key scheme of Elgamal digital signature algorithms 
are built based on the discrete logarithm problem: 
modxy g p (1) 
Here, (x, y) are private key and public key of a sign, 
(g, p) are domain parameters, system parameters that 
were created by digital authentication service 
provider, in which, g is generator of the group pZ , p is 
 May – June 2020 
ISSN: 0193-4120 Page No. 2254 - 2260 
2255 
Published by: The Mattingley Publishing Co., Inc. 
a prime number. Finding private key x, from public 
parameters y, g and p, is a difficult problem if p is a 
large and strong prime number. 
From (1), it can be seen that if g is also a secret 
parameter then (1) will becomes the form: 
 21 mod
x
y x p (2) 
Finding exactly one pair of values 
1 2( , )x x from 
public parameters (y, p) will be a difficult problem that 
has not been solved yet (except “brute fore attack”). 
Theoretically, if (2) is used as the key generation 
scheme for the digital signature algorithm, in which, 
1 2( , )x x are private keys and y is the signer's public key, 
the security of key will be higher than key of Elgamal 
signature algorithm. 
However, using (2) to create keys also has some 
certain weaknesses, for example, an attacker who use 
the pair (y, 1) can still create a valid digital signature 
without having to find the exact value of the private 
keys 
1 2( , )x x . The reason is that, according to (2), the 
values of 
1x and 2x can be chosen independently of 
each other, so, the attacker can choose 
2 1x and 
easily obtain 
1x y . 
To overcome such weaknesses of (2), we propose a 
new key scheme as following: With 
1 2( , )p p are prime 
numbers that being the domain parameters/system 
parameters that created by the sender of service 
provider, and they must satisfy the condition 
2 1| ( 1)p p , each object chooses a number 11, p . 
Let sk be private key, it is generated by equation (3): 
1 2( 1)/
1mod
p p
sk p (3) 
Then, the public key is generated, according to (4), 
as follows: 
1
2mod
1mod
sk p
pk sk p
 (4) 
The key scheme here can be described in algorithm 
1 as a key generation algorithm as follows: 
Algorithm 1. Key Generation Algorithm 
Input: l1, l2 - length by bits of 1 2,p p . 
Output: 1 2, , ,p p sk pk . 
1: Generate 1 2,p p : length( 1p ) = l1, length( 2p ) = l2, 
2 1| ( 1)p p 
 ... validity of the proposed algorithm can be 
proved as follows: 
From equation (4), (5), (6), (11), (14) and (16), we have: 
1
1
1 1
1 1
.
1 2 1 1
.
. .
1
. .
1
1 1
mod mod
mod
mod
mod .
H sk H
sk H
pk H Z H
sk pk sk Z
pk Z
V S p t p
s sk p
s sk p
S pk p
 (18) 
Moreover, from equation (5), (6), (11), (14) and (15), we 
have: 
1 1
1
1
1 1 1
1
1 2 1 2
1 2
1
1 2
1 2
1 2
mod mod
mod mod
mod mod
mod mod
mod mod .
sk sk
sk
sk
sk sk sk
sk
Z S S p p
s t p p
s b s p p
b s sk p p
b p p Z
 (19) 
From (19) and (16), we have: 
 2 1 1 1 1mod mod
pk Z pk Z
V S pk p S pk p . (20) 
From (18) and (20), we have the proof: V1=V2. 
Thus, the above algorithm is correct. 
C. Example 
The correctness of the algorithm that is constructed 
by the new proposed method has been proved above, 
the following example continues to be a confirmation 
of the correctness of this algorithm. 
1. Parameter selection and Key generation (Algorithm 1): 
- A prime number p1: 
76965278880226250427015195180432917871888582232106042926
1914982675508964388096140028023718761744429257720073224694
8641191946554666178703515956898081270671 
- A prime number p2: 
1373186123048912294173936536433730021934719339773 
- Value of sk: 
23006588671344209047565634014252443981559908181217053799
7372593417479966646716362600165012729100205755365717558283
7273663124479073641172724995112153441509 
- Value of pk: 
28419900856552571673682694246095151428677466512887295201
5471885140560023408089823343170458331052176782028545103373
8234439317209690947612929624884251717220 
2. Signature generation (Signing algorithm - Algorithm 2): 
Input: p1, p2, sk, pk, M. 
Output: (S1, S2). 
- Message M: 
“THIS IS A NEW METHOD FOR CONSTRUCTING DIGITAL SIGNATURE 
ALGORITHMS BASED ON A NEW KEY SCHEME!” 
- Value of b: 
30655439685289175206556654650011723625756359203036025192
8672988983163690105996812382440620226246315110104898510423
1329971309140451311716741537384783908816 
- Value of H: 
959366385729338426893978751086189809256431807060 
- Value of S1: 
22224417867721672828605289864862372567737084389508235689
0066313659814030966535708518080199703161131181731590581990
044984635886214810253038806305730734728 
- Value of S2: 
25454345586881197866342222364319811737860697721720666029
0253453708613022868560005632096432067870564031253044814884
1372636874155464233039700280473688846190 
3. Signature Verification (Signature verifying algorithm - 
Algorithm 3): 
Input: p1, p2, pk, (S1, S2), M. 
Output: True/ False. 
+ Case No.1: 
- The message M: 
“THIS IS A NEW METHOD FOR CONSTRUCTING DIGITAL SIGNATURE 
ALGORITHMS BASED ON A NEW KEY SCHEME!” 
- Value of S1: 
22224417867721672828605289864862372567737084389508235689
0066313659814030966535708518080199703161131181731590581990
044984635886214810253038806305730734728 
- Value of S2: 
25454345586881197866342222364319811737860697721720666029
0253453708613022868560005632096432067870564031253044814884
1372636874155464233039700280473688846190 
- Value of H: 
959366385729338426893978751086189809256431807060 
- Value of Z: 
31111753115994037294348164808399470227246290399418825644
1003511245862817556543609369642413957442155639843155177694
6990618274561926868642316931231824140445 
- Value of V1: 
19615353026049564016672006361476411600832227693855875184
2389057820267102587920589495523684620777363307724604946477
3766205381683466674713694277774185790445 
- Value of V2: 
19615353026049564016672006361476411600832227693855875184
2389057820267102587920589495523684620777363307724604946477
3766205381683466674713694277774185790445 
Output: (S1, S2) = True. 
In this case, all message and signature were not 
modified during transmission, so, with the above 
result, the message and its signature are consistent, 
and so that, the recipient can trust the integrity and 
original of the message. 
+ Case No.2: The message M has been modified by 
an attacker. 
- The message M (fake): 
“THIS IS A OLD METHOD FOR CONSTRUCTING DIGITAL SIGNATURE 
ALGORITHMS BASED ON A NEW KEY SCHEME!” 
- Value of S1: 
22224417867721672828605289864862372567737084389508235689
0066313659814030966535708518080199703161131181731590581990
 May – June 2020 
ISSN: 0193-4120 Page No. 2254 - 2260 
2258 
Published by: The Mattingley Publishing Co., Inc. 
044984635886214810253038806305730734728 
- Value of S2: 
25454345586881197866342222364319811737860697721720666029
0253453708613022868560005632096432067870564031253044814884
1372636874155464233039700280473688846190 
- Value of H: 
49789245265502077531030000076484782224926234320 
- Value of Z: 
31111753115994037294348164808399470227246290399418825644
1003511245862817556543609369642413957442155639843155177694
6990618274561926868642316931231824140445 
- Value of V1: 
31529231369497922565973057222139900761456055975419936895
5372764691045957675543283167562733312975854117709072269909
784004189635353390700047656178816002322 
- Value of V2: 
19615353026049564016672006361476411600832227693855875184
2389057820267102587920589495523684620777363307724604946477
3766205381683466674713694277774185790445 
Output: (V1, V2) = False. 
In this case, the message (M) has been modified (the 
attacker replaces the word “NEW” with the word 
“OLD”), with the above result, the message and its 
signature are not consistent, and so that, the recipient 
should not trust the integrity and original of the 
message. Be careful! 
+ Case No.3: S1 of digital signature is not correct. 
- The message M: 
“THIS IS A NEW METHOD FOR CONSTRUCTING DIGITAL SIGNATURE 
ALGORITHMS BASED ON A NEW KEY SCHEME!” 
- Value of S1: 
22224417867721672828605289864862372567737084389508235689
0066313659814030966535708518080199703161131181731590581990
044984635886214810253038806305730734720 
- Value of S2: 
25454345586881197866342222364319811737860697721720666029
0253453708613022868560005632096432067870564031253044814884
1372636874155464233039700280473688846190 
- Value of H: 
959366385729338426893978751086189809256431807060 
- Value of Z: 
58372825061623205644655971435139729940026455321971626190
4720829603485527772351984396942113699710931162979016332706
1933099120982211540435262558136557182938 
- Value of V1: 
19615353026049564016672006361476411600832227693855875184
2389057820267102587920589495523684620777363307724604946477
3766205381683466674713694277774185790445 
- Value of V2: 
97954225586140284955616793788545559257765081841750097270
4378472361292124832848476123404673668799481946932006186111
343478079418307938198873649409093046173 
Output: (S1, S2) = False. 
In this case, a component of the signature (S1) has 
been modified (some errors may occur during sending 
process), according to the above result, the message 
and its signature are not consistent, and so that, the 
recipient should not trust the integrity and original of 
the message. Be careful! 
 + Case No.4: S2 of digital signature is not correct. 
- The message M: 
“THIS IS A NEW METHOD FOR CONSTRUCTING DIGITAL SIGNATURE 
ALGORITHMS BASED ON A NEW KEY SCHEME!” 
- Value of S1: 
22224417867721672828605289864862372567737084389508235689
0066313659814030966535708518080199703161131181731590581990
044984635886214810253038806305730734728 
- Value of S2: 
25454345586881197866342222364319811737860697721720666029
0253453708613022868560005632096432067870564031253044814884
1372636874155464233039700280473688846199 
- Value of H: 
959366385729338426893978751086189809256431807060 
- Value of Z: 
51113729196943542840092925686775605538209666349976237764
2063193539695445426425747035914593690287173703401586701485
7395479997537860160919666187983400752997 
- Value of V1: 
66210739927154078294641748468352521836179912755373350341
0407528302102956280862275055943227739622383094545353353562
7133034288013314905653061978850859602873 
- Value of V2: 
52591606785462721865947337220778622012533474619595288010
1601806829704044762996841132346219113178457556852518358367
3101212954715647992906348413748801089422 
Output: (S1, S2) = False. 
In above case, a component of signature (S2) has 
been modified (the last digit of S2 has been changed), 
according to the above result, the message and its 
signature are not consistent, and so that, the recipient 
should not trust the integrity and original of the 
message. 
III. SECURITY LEVEL OF THE PROPOSED 
AGORITHM BASED ON THE NEW KEY SCHEME 
The safety level of the proposed algorithm based on 
the new key scheme can be assessed by its ability to 
resist some types of attacks such as: 
- Safety against attacks on the private key 
From (4), finding sk by algorithms for Discrete 
Logarithm Problem on Zp such as Pollard Rho, Baby 
Step - Giant Step, Index Calculus, ... is impossible. 
Nowaday, the “brute force attack” is the only 
algorithm that can be applied to solve (4). However, 
“brute force attack" is not a polynomial time algorithm 
that can be applied in practical applications. 
- Safety against attack on signing algorithm 
An attacker could perform an attack on the signing 
 May – June 2020 
ISSN: 0193-4120 Page No. 2254 - 2260 
2259 
Published by: The Mattingley Publishing Co., Inc. 
algorithm to find sk. Finding sk from solving 
equations: 
1
2mod
1 1mod
sk p
S s p
 . 
or: 
1
2mod
2 1mod
sk p
S t p
 . 
or: 
1
2mod
1 2mod mod
sk p
Z b p p
 . 
(In which: 1 2 1 2mod modZ S S p p ) 
Including to solve equation (4), this is a hard 
problem. It shows that attacking signing algorithm to 
find sk is a completely impossible. 
+ Safety against attack on signature verifying 
algorithm 
From the Signature verifying Algorithm (Algorithm 
3) of the proposed algorithm, if attacker want to forge 
a signature, he must create a fake signature (S1, S2) 
will be recognized as a valid signature of a message M, 
in other word, it must satisfies the following 
conditions: 
 1 2 1 2mod mod
2 1 1mod
E pk S S p p
S S pk p
 . (21) 
From (21), if S1 is preselected and then S2 will be 
calculated, the condition (21) will become the 
following form: 
 22 1mod
H S
S X p . (22) 
If S2 is preselected and then S1 will be calculated, the 
condition (21) will become the following form: 
 11 1mod
pk S
S Y p . (23) 
With X and Y being constants, it is easy to see that 
(22) and (23) are hard problems that currently do not 
have a solution. It is easy to see that if the left side of 
(22) and (23) is a constant number then this is a 
Discrete Logarithm Problem, and if the right side is a 
constant number then this is the Root Problem. 
However, in (22) and (23), both sides contain 
variables to be searched, so, algorithms for Discrete 
Logarithm Problem and Root Problem on Zp are not 
applicable to solve (22) and (23). 
IV. CONCLUSION 
The paper proposes a new method to build a digital 
signature algorithm based on a new key scheme. By 
using this new key scheme, we can develop some 
digital signature algorithms. These algorithms are high 
secure and can be applied in some actual situation. 
 REFERENCES 
[1] Wei-Hua He, “Digital signature scheme based on 
factoring and discrete logarithms”, in Electronics 
Letters, volume 37, no. 4, pp. 220-222, 15 Feb 2001. 
DOI: 10.1049/el:20010149 
[2] Shiang-Feng Tzeng, Cheng-Ying Yang and 
Min-Shiang Hwang, “A new digital signature scheme 
based on factoring and discrete logarithms”, in 
International Journal of Computer Mathematics, 
volume 28, issue 1, pp. 9-14, 2004. DOI: 
10.1080/00207160310001614954. 
[3] Li-Hua Li, Shiang-Feng Tzeng and Min-Shiang 
Hwang, “Improvement of signature scheme based on 
factoring and discrete logarithms”, in Applied 
Mathematics and Computation, volume 161, pp. 
49-54, 2005. DOI: 10.1016/j.amc.2003.12.008. 
[4] Shimin Wei, “Digital Signature Scheme Based on Two 
Hard Problems”, in International Journal of Computer 
Science and Network Security, volume 7, no. 12, pp. 
207-209, 2007. 
[5] Nikolay A. Moldovyan, “Digital Signature Scheme 
Based on a New Hard Problem”, in Computer Science 
Journal of Moldova, volume 16, no. 2(47), pp. 
163-182, 2008. 
[6] Eddie Shahrie Ismail, Nedal Tahat and Rokiah Rozita 
Ahmad, “A New Digital Signature Scheme Based on 
Factoring and Discrete Logarithms”, in Journal of 
Mathematics and Statistics, volume 4, issue 4, pp. 
222-225, 2008. DOI: 10.3844/jmssp.2008.222.225. 
[7] Al-Fayoumi Mustafa, Aboud Sattar and Al-Fayoumi 
Mohammad, “A New Digital Signature Scheme Based 
on Integer Factoring and Discrete Logarithm 
Problem”, in International Journal Computer 
Applications, volume 17, no. 2, pp. 108-115, 2010. 
[8] Nedal Tahat, Zead Mustafa and A. K. Alomari, “New 
ID-Based Digital Signature Scheme on Factoring and 
Discrete Logarithms”, in Applied Mathematical 
Sciences, volume 6, no. 28, 1363-1369, 2012. 
[9] Andrey N. Berezin, Nikolay A. Moldovyan and Victor 
A. Shcherbacov, “Cryptoschemes Based on Difficulty 
of Simultaneous Solving Two Different Difficult 
Problems”, in The Computer Science Journal of 
Moldova, volume 21, no. 2 (62), 2013. 
[10] Dimitrios Poulakis, “A public key encryption scheme 
based on factoring and discrete logarithm”, in Journal 
 May – June 2020 
ISSN: 0193-4120 Page No. 2254 - 2260 
2260 
Published by: The Mattingley Publishing Co., Inc. 
of Discrete Mathematical Sciences and Cryptography, 
volume 12, no. 6, pp. 745-752, 2013. DOI: 
10.1080/09720529.2009.10698270. 
[11] Shin-Yan Chiou, “Novel Digital Signature Schemes 
based on Factoring and Discrete Logarithms”, in 
International Journal of Security and Its Applications, 
volume 10, no. 3, pp. 295-310, 2016. DOI: 
10.14257/ijsia.2016.10.3.26. 
[12] T. Elgamal, “A public key cryptosystem and a 
signature scheme based on discrete logarithms”, in 
IEEE Transactions on Information Theory, volume 31, 
no. 4, pp. 469-472, 1985. DOI: 
10.1109/TIT.1985.1057074.