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

p12 1)
 *
 8: If ((S1=1) or (S2=1)) then goto 2 function Hash: 0,1 Zn , p21 n p , 1, p1 , 
 9: Return (S , S ) 1
 1 2 sk mod p
 pp12 1/ pk sk2 mod p
 Note: sk mod p1 , 1 , 
 (pp12 1)/
 - M: Message need to be signed, M 0,1 .  1, p1 , bp  mod 1 , 
 * 1
 - Hash(.): Hash function Hash: 0,1 Z , in which: Z b sk mod p2 mod p mod p , H Hash() M , 
  n 12 
 p n p . 1 1
 21 H . pk 1 mod p
 Z. H 1 mod p 2
 - (S , S ): Signature of S on M. s b sk2 mod p , 
 1 2 1
 11
 pk. H mod p22 Z . H mod p
 2. Signature verifying algorithm t s sk mod p1 , 
 1 1
 Verifying formula of this proposed algorithm is sk mod p2 sk mod p2
 S11 s mod p , S21 t mod p . 
assumed that: H
 H pk S1 S 2mod p 1 mod p 2 If Z S1 S 2mod p 1 mod p 2 , V1 S 2 mod p 1 , 
 S2  S 1 pk mod p 1 . 
 V Spk pk Z mod p then: VV . 
 In which, M is message that must be verified and H 2 1 1 12
 Published by: The Mattingley Publishing Co., Inc. 2256 
 May – June 2020 
 ISSN: 0193-4120 Page No. 2254 - 2260 
 Assessing the validity of the proposed algorithm can be ALGORITHMS BASED ON A NEW KEY SCHEME!” 
proved as follows: - Value of b: 
 From equation (4), (5), (6), (11), (14) and (16), we have: 30655439685289175206556654650011723625756359203036025192
 H sk 1. H 8672988983163690105996812382440620226246315110104898510423
 V1 S 2 mod p 1 t mod p 1 1329971309140451311716741537384783908816 
 1
 11 sk . H - Value of H: 
 pk.. H Z H 
 s sk mod p 959366385729338426893978751086189809256431807060 
 1 (18) 
 11 - Value of S1: 
 sk .. pk sk Z
 s sk mod p1 22224417867721672828605289864862372567737084389508235689
 pk Z 0066313659814030966535708518080199703161131181731590581990
 S11 pk mod p . 044984635886214810253038806305730734728 
 - Value of S2: 
 Moreover, from equation (5), (6), (11), (14) and (15), we 25454345586881197866342222364319811737860697721720666029
have: 0253453708613022868560005632096432067870564031253044814884
 1372636874155464233039700280473688846190 
 Z S1 S 2mod p 1 mod p 2 3. Signature Verification (Signature verifying algorithm - 
 sk 11 sk Algorithm 3): 
 s tmod p mod p
 12 
 Input: p1, p2, pk, (S1, S2), M. 
 1
 sk 1 1 sk Output: True/ False. 
 s b s mod p12 mod p (19) + Case No.1: 
 1 1 1 - The message M: 
 b sk s sk sk sk mod p mod p
 12 “THIS IS A NEW METHOD FOR CONSTRUCTING DIGITAL SIGNATURE 
 ALGORITHMS BASED ON A NEW KEY SCHEME!” 
 1
 sk - Value of S : 
 b mod p12 mod p Z . 1
 22224417867721672828605289864862372567737084389508235689
 0066313659814030966535708518080199703161131181731590581990
 044984635886214810253038806305730734728 
 From (19) and (16), we have: 
 - Value of S : 
 pk Z pk Z 2
 V2 S 1 pk mod p 1 S 1 pk mod p 1 . (20) 25454345586881197866342222364319811737860697721720666029
 0253453708613022868560005632096432067870564031253044814884
 From (18) and (20), we have the proof: V1=V2. 1372636874155464233039700280473688846190 
Thus, the above algorithm is correct. - Value of H: 
 959366385729338426893978751086189809256431807060 
 - Value of Z: 
 C. Example 31111753115994037294348164808399470227246290399418825644
 1003511245862817556543609369642413957442155639843155177694
 The correctness of the algorithm that is constructed 6990618274561926868642316931231824140445 
by the new proposed method has been proved above, 
 - Value of V1: 
the following example continues to be a confirmation 19615353026049564016672006361476411600832227693855875184
 2389057820267102587920589495523684620777363307724604946477
of the correctness of this algorithm. 3766205381683466674713694277774185790445 
 1. Parameter selection and Key generation (Algorithm 1): 
 - Value of V2: 
 - A prime number p1: 19615353026049564016672006361476411600832227693855875184
 76965278880226250427015195180432917871888582232106042926 2389057820267102587920589495523684620777363307724604946477
1914982675508964388096140028023718761744429257720073224694 3766205381683466674713694277774185790445 
8641191946554666178703515956898081270671 
 Output: (S1, S2) = True. 
 - A prime number p2: In this case, all message and signature were not 
 1373186123048912294173936536433730021934719339773 
 - Value of sk: modified during transmission, so, with the above 
 23006588671344209047565634014252443981559908181217053799 result, the message and its signature are consistent, 
7372593417479966646716362600165012729100205755365717558283 and so that, the recipient can trust the integrity and 
7273663124479073641172724995112153441509 
 - Value of pk: original of the message. 
 28419900856552571673682694246095151428677466512887295201 + Case No.2: The message M has been modified by 
5471885140560023408089823343170458331052176782028545103373
8234439317209690947612929624884251717220 an attacker. 
 2. Signature generation (Signing algorithm - Algorithm 2): - The message M (fake): 
 Input: p1, p2, sk, pk, M. “THIS IS A OLD METHOD FOR CONSTRUCTING DIGITAL SIGNATURE 
 ALGORITHMS BASED ON A NEW KEY SCHEME!” 
 Output: (S1, S2). 
 - Value of S : 
 - Message M: 1
 22224417867721672828605289864862372567737084389508235689
 “THIS IS A NEW METHOD FOR CONSTRUCTING DIGITAL SIGNATURE 0066313659814030966535708518080199703161131181731590581990
 Published by: The Mattingley Publishing Co., Inc. 2257 
 May – June 2020 
 ISSN: 0193-4120 Page No. 2254 - 2260 
044984635886214810253038806305730734728 and its signature are not consistent, and so that, the 
 - Value of S2: recipient should not trust the integrity and original of 
 25454345586881197866342222364319811737860697721720666029
0253453708613022868560005632096432067870564031253044814884 the message. Be careful! 
1372636874155464233039700280473688846190 
 + Case No.4: S2 of digital signature is not correct. 
 - Value of H: - The message M: 
 49789245265502077531030000076484782224926234320 
 “THIS IS A NEW METHOD FOR CONSTRUCTING DIGITAL SIGNATURE 
 - Value of Z: ALGORITHMS BASED ON A NEW KEY SCHEME!” 
 31111753115994037294348164808399470227246290399418825644
 - Value of S1: 
1003511245862817556543609369642413957442155639843155177694
 22224417867721672828605289864862372567737084389508235689
6990618274561926868642316931231824140445 
 0066313659814030966535708518080199703161131181731590581990
 - Value of V1: 044984635886214810253038806305730734728 
 31529231369497922565973057222139900761456055975419936895
 - Value of S2: 
5372764691045957675543283167562733312975854117709072269909
 25454345586881197866342222364319811737860697721720666029
784004189635353390700047656178816002322 
 0253453708613022868560005632096432067870564031253044814884
 - Value of V2: 1372636874155464233039700280473688846199 
 19615353026049564016672006361476411600832227693855875184 - Value of H: 
2389057820267102587920589495523684620777363307724604946477
 959366385729338426893978751086189809256431807060 
3766205381683466674713694277774185790445 
 - Value of Z: 
 Output: (V , V ) = False. 
 1 2 51113729196943542840092925686775605538209666349976237764
 In this case, the message (M) has been modified (the 2063193539695445426425747035914593690287173703401586701485
attacker replaces the word “NEW” with the word 7395479997537860160919666187983400752997 
 - Value of V1: 
“OLD”), with the above result, the message and its 66210739927154078294641748468352521836179912755373350341
signature are not consistent, and so that, the recipient 0407528302102956280862275055943227739622383094545353353562
should not trust the integrity and original of the 7133034288013314905653061978850859602873 
 - Value of V2: 
message. Be careful! 52591606785462721865947337220778622012533474619595288010
 1601806829704044762996841132346219113178457556852518358367
 3101212954715647992906348413748801089422 
 + Case No.3: S of digital signature is not correct. 
 1 Output: (S , S ) = False. 
 - The message M: 1 2
 “THIS IS A NEW METHOD FOR CONSTRUCTING DIGITAL SIGNATURE In above case, a component of signature (S2) has 
ALGORITHMS BASED ON A NEW KEY SCHEME!” 
 been modified (the last digit of S2 has been changed), 
 - Value of S1: according to the above result, the message and its 
 22224417867721672828605289864862372567737084389508235689
0066313659814030966535708518080199703161131181731590581990 signature are not consistent, and so that, the recipient 
044984635886214810253038806305730734720 should not trust the integrity and original of the 
 - Value of S2: message. 
 25454345586881197866342222364319811737860697721720666029
0253453708613022868560005632096432067870564031253044814884
1372636874155464233039700280473688846190 III. SECURITY LEVEL OF THE PROPOSED 
 - Value of H: AGORITHM BASED ON THE NEW KEY SCHEME 
 959366385729338426893978751086189809256431807060 
 The safety level of the proposed algorithm based on 
 - Value of Z: 
 58372825061623205644655971435139729940026455321971626190 the new key scheme can be assessed by its ability to 
4720829603485527772351984396942113699710931162979016332706 resist some types of attacks such as: 
1933099120982211540435262558136557182938 
 - Value of V1: 
 19615353026049564016672006361476411600832227693855875184 - Safety against attacks on the private key 
2389057820267102587920589495523684620777363307724604946477 From (4), finding sk by algorithms for Discrete 
3766205381683466674713694277774185790445 
 Logarithm Problem on Zp such as Pollard Rho, Baby 
 - Value of V2: 
 97954225586140284955616793788545559257765081841750097270 Step - Giant Step, Index Calculus, ... is impossible. 
4378472361292124832848476123404673668799481946932006186111 Nowaday, the “brute force attack” is the only 
343478079418307938198873649409093046173 algorithm that can be applied to solve (4). However, 
 Output: (S , S ) = False. 
 1 2 “brute force attack" is not a polynomial time algorithm 
 that can be applied in practical applications. 
 In this case, a component of the signature (S1) has 
been modified (some errors may occur during sending - Safety against attack on signing algorithm 
process), according to the above result, the message An attacker could perform an attack on the signing 
 Published by: The Mattingley Publishing Co., Inc. 2258 
 May – June 2020 
 ISSN: 0193-4120 Page No. 2254 - 2260 
algorithm to find sk. Finding sk from solving IV. CONCLUSION 
equations: The paper proposes a new method to build a digital 
 1
 sk mod p2 signature algorithm based on a new key scheme. By 
 S11 s mod p . 
 using this new key scheme, we can develop some 
 or: 
 1 digital signature algorithms. These algorithms are high 
 S t sk mod p2 mod p
 21 . secure and can be applied in some actual situation. 
 or: 
 sk 1 mod p 
 Z b 2 mod p mod p . 
 12 REFERENCES 
 [1] Wei-Hua He, “Digital signature scheme based on 
 (In which: Z S1 S 2mod p 1 mod p 2 ) factoring and discrete logarithms”, in Electronics 
 Including to solve equation (4), this is a hard Letters, volume 37, no. 4, pp. 220-222, 15 Feb 2001. 
problem. It shows that attacking signing algorithm to DOI: 10.1049/el:20010149 
find sk is a completely impossible. [2] Shiang-Feng Tzeng, Cheng-Ying Yang and 
 + Safety against attack on signature verifying Min-Shiang Hwang, “A new digital signature scheme 
 based on factoring and discrete logarithms”, in 
algorithm International Journal of Computer Mathematics, 
 From the Signature verifying Algorithm (Algorithm volume 28, issue 1, pp. 9-14, 2004. DOI: 
3) of the proposed algorithm, if attacker want to forge 10.1080/00207160310001614954. 
a signature, he must create a fake signature (S1, S2) [3] Li-Hua Li, Shiang-Feng Tzeng and Min-Shiang 
will be recognized as a valid signature of a message M, Hwang, “Improvement of signature scheme based on 
in other word, it must satisfies the following factoring and discrete logarithms”, in Applied 
conditions: Mathematics and Computation, volume 161, pp. 
 49-54, 2005. DOI: 10.1016/j.amc.2003.12.008. 
 SE S pk pk S1 S 2mod p 1 mod p 2 mod p . (21) 
 2 1 1 [4] Shimin Wei, “Digital Signature Scheme Based on Two 
 Hard Problems”, in International Journal of Computer 
 From (21), if S1 is preselected and then S2 will be Science and Network Security, volume 7, no. 12, pp. 
calculated, the condition (21) will become the 207-209, 2007. 
following form: [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. 
 HS2
 S21  X mod p . (22) 163-182, 2008. 
 [6] Eddie Shahrie Ismail, Nedal Tahat and Rokiah Rozita 
 If S2 is preselected and then S1 will be calculated, the Ahmad, “A New Digital Signature Scheme Based on 
condition (21) will become the following form: Factoring and Discrete Logarithms”, in Journal of 
 Mathematics and Statistics, volume 4, issue 4, pp. 
 Spk Y S1 mod p . (23) 
 11 222-225, 2008. DOI: 10.3844/jmssp.2008.222.225. 
 [7] Al-Fayoumi Mustafa, Aboud Sattar and Al-Fayoumi 
 With X and Y being constants, it is easy to see that Mohammad, “A New Digital Signature Scheme Based 
(22) and (23) are hard problems that currently do not on Integer Factoring and Discrete Logarithm 
have a solution. It is easy to see that if the left side of Problem”, in International Journal Computer 
(22) and (23) is a constant number then this is a Applications, volume 17, no. 2, pp. 108-115, 2010. 
 [8] Nedal Tahat, Zead Mustafa and A. K. Alomari, “New 
Discrete Logarithm Problem, and if the right side is a ID-Based Digital Signature Scheme on Factoring and 
constant number then this is the Root Problem. Discrete Logarithms”, in Applied Mathematical 
However, in (22) and (23), both sides contain Sciences, volume 6, no. 28, 1363-1369, 2012. 
variables to be searched, so, algorithms for Discrete [9] Andrey N. Berezin, Nikolay A. Moldovyan and Victor 
Logarithm Problem and Root Problem on Zp are not A. Shcherbacov, “Cryptoschemes Based on Difficulty 
applicable to solve (22) and (23). 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 
 Published by: The Mattingley Publishing Co., Inc. 2259 
 May – June 2020 
 ISSN: 0193-4120 Page No. 2254 - 2260 
 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. 
 Published by: The Mattingley Publishing Co., Inc. 2260