Constructing a digital signature algorithm based on the difficulty of some expanded root problems

d as a private key, From (8) va` (9), we have:
 −1 −1
similarly as x and x in signature algorithm. (y) ·E x1·(y) ·Z
 1 2 v × v × x1 mod p = k
 Key generation algorithm can be described as the following
algorithm (Algorithm 1): as:
 −1 −1
 (y) ·E+1 x1·(y) ·Z
 v × x1 mod p = k (10)
Algorithm 1 Key Generation Algorithm
Input: p - a prime number, lq - length by bits of q From (10) to:
 −1 (y−1·E+1)−1
Output: (q, x1, x2, y)  −x1·(y) ·Z 

 v = k × (x1) mod p (11)
 1: generate q : len(q) = lq, q|(p − 1)
 2: select α: 1 < α < p From (11), we can calculate u by (8):
 3: −1 −1
 select x2 ∈ (1, q) y ·E x1·y1 ·Z
 (p−1)/q u = v × x1 mod p
 4: x1 ← α mod p
 5: if ((x1 == 1) or (x2 == 1)) then From values of u and v, we can calculate R of the signature
 6: go to 2 by (2):
 7: end if R = ux2 mod p
 8: y ← x (x1·x2) mod q mod p
 1 and calculate S by (3):
 9: return (q, x1, x2, y)
 S = vx2 mod p
 In which: So that, the signature algorithm is described on Algorithm
 - len(.) is a function that calculate the length by bits of a 2 as:
integer number. In which:
 - p: System parameter/ Domain parameter. - M: message must be signed, with: M ∈ {0, 1}∞
 ∗
 - q, x1, x2: Private keys. - H(.): hash function H : {0, 1} 7→ Zn, with: q < n < p
 - y: Public key of signature object (U). - (R, S): signature of U on M.
 191
 2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
Algorithm 2 Signature Algorithm 4) On the validity of newly proposed scheme: The problem
Input: (p, q, x1, x2, y) to prove here is: Let (p, q) are two prime number with
 ∗
Output: (R, S) q|(p − 1), H : {0, 1} 7→ Zn, q < n < p, 1 < α < p,
 (p−1)/q (x1·x2) mod q
 1: E = H(M) x1 = α mod p, x2 ∈ (1, q), y = (x1) mod
 k
 2: select k : 1 < k < p − 1 p, 1 < k < p, Z = x1 mod p, E = H(M), v =
 −1 −1
 x2 −1 (y ·E+1) −1
 3: Z ← k mod p k × (x )−x1·(y) ·Z 
 mod p, u = vy ·E ×
 −1 (y−1·E+1)−1 1
  −x1·(y) ·Z 
 −1
 4: v ← k × (x ) mod p x1·y ·Z
 1 x 1 mod p, R = ux2 mod p, S = vx2 mod p. If:
 −1 x ·y−1·Z 1
 y ·E 1 1 y E Z¯
 5: u ← v × x1 mod p Z¯ = (R × S) mod p, A = R mod p, B = S × (y) mod p
 6: R ← ux2 mod p then: A = B.
 7: S ← vx2 mod p The validity of new proposed scheme is proved as:
 8: if (R == 1) or (S == 1) then From (1), (2), (3), (8), (11), (13), we have:
 9: go to 2
 y x2·y
10: end if A = R mod p = u mod p
 −1 −1 x ·y
  y ·E x1·y ·Z 
 2
11: return (R, S) = v × x1 mod p
 −1 −1
 y ·E·x2·y x1·y ·Z·x2·y
 = v × x1 mod p
 = vx2·E × x x1·x2·Z mod p
 3) Testing Algorithm: Testing algorithm of this scheme is 1
 E Z
assumed that: = S × y mod p (15)
 Ry ≡ SE × y(R×S mod p) mod p Otherwise, from (2), (3), (8), (11) and (12), we have:
 Z¯ = R × S mod p = ux2 × vx2 mod p
 E
Here, is a value representing for the message that need −1 −1 x2
  (y) ·E x1·y ·Z 
 x2
to be verified: E = H(M). If M and the signature (R, S) = v × (x1) × v mod p
 −1 −1
satisfy the above equation then the signature is valid and y ·E·x2+x2 x1·x2·y ·Z
 = v × x1 mod p
the message will be verified by originality also integrity. −1 −1
 (y ·E+1)·x2 x1·x2·y ·Z
Otherwise, the signature is invalid and the signature is denied = v × x1 mod p
 −1 −1 −1
by the originality and integrity. Therefore, if the left side of −1 (y ·E+1) ·(y ·E+1)·x2
  −x1·y ·Z 

testing equation is calculated as: = k × (x1)
 −1
 x1·x2·y ·Z
 × x1 mod p
 y
 A = R mod p (12) −1 x2 −1
  −x1·y ·Z 
 x1·x2·y ·Z
 = k × (x1) × x1 mod p
 −1 −1
and the right side of testing equation is calculated as: x2 −x1·x2·y ·Z x1·x2·y2 ·Z
 = k × x1 × x1 mod p
 x
 B = SE × (y)Z mod p (13) = k 2 mod p = Z (16)
 Instead (16) to (14), we have:
in which:
 ¯
 B = SE × yZ mod p = SE × yZ mod p (17)
 Z¯ = R × S mod p (14)
 From (15) and (17), we have the proof: A = B.
Then, the condition for valid signature is: A = B. 5) Example: The validity of new proposed scheme is
 And after that, the testing algorithm of the new proposed described as the following example:
scheme is described in Algorithm 3 as: a) Parameter and key generation (Algorithm 1):
 - Value of p:
Algorithm 3 Signature Testing Algorithm 891505711756810466801538581994639035723395
Input: p, y, M, R, S 046984393012096518029175988878598532328716
Output: T rue/F alse 007897388814756369043609524344142253015152
 1: E = H(M) 2256624968441471249159548721
 2: A ← Ry mod p
 3: Z¯ ← (R × S) mod p - Value of q:
 E Z¯
 4: B ← S × y mod p 114169146889658081579965580080483177277395
 5: if (A == B) then 1929057
 6: return T rue
 7: else - Value of x1:
 8: return F alse 787554019949566514178024987720721359923067
 9: end if 165874275462504405665757532105277496444801
 718504313823545333439710356295680887406478
 192
 2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
1047383620292559004679777805 427716534804130441636635576091312662258757
 845096303882143614771060806488953511599782
 - Value of x :
 2 9397260373114149558817750583
544679862739775176263996254185216317667127
 - Value of E:
684479100060093664136715997878178597128117
126805135609079604644585387615811144496262 331093805086206888598876639555451737904126
8702531372228447519121344128 266485
 - Value of y: - Value of Z:
441063086344010474906300383421442247158936 201595737909355043093039092014649024016097
925505706949717244934963160362941072411938 253561429177074478824215862484918660296556
445096088489139300691625194975575669586229 376258853319386641834258582058603343090017
6845650459797968526942837435 8721513406175725285896970811
 b) Signature generation (Algorithm 2): - Value of A:
 Input: p, y, x1, x2,M.
 Output: (R, S). 107176181863688309366891233947822068387651
 - Message (M): 238133011104586640634308116068595547233030
 975840620206832414013992565082088821981501
THIS IS A NEW DIGITAL SIGNATURE ALGORITHM! 9076330319423513169298904522
 - Value of k: - Value of B:
224810619659488341208713525047815187805617 107176181863688309366891233947822068387651
284189918974458223089880229903478611827454 238133011104586640634308116068595547233030
354135800782245853186661590101057844721463 975840620206832414013992565082088821981501
9010271583824330185230043744 9076330319423513169298904522
 - Value of E: Output: (R, S) = T rue.
331093805086206888598876639555451737904126 So that, both the signature and message are not modified,
266485 then the result shows that, the signature is valid, and therefore,
 the message is verified for its origin and integrity.
 - Value of R:
 + Case No.2: The message M is fake.
423075212967381365570286154186075643013021 - The message (M):
704004843447060655977130479044053204685193
253406059065865451717576656375347757790084 THIS IS A OLD DIGITAL SIGNATURE ALGORITHM!
3159418457812119241879758646 - Value of R:
 - Value of S: 423075212967381365570286154186075643013021
407323441104142607015539422158072296018149 704004843447060655977130479044053204685193
427716534804130441636635576091312662258757 253406059065865451717576656375347757790084
845096303882143614771060806488953511599782 3159418457812119241879758646
9397260373114149558817750583 - Value of S:
 c) Signature Verification (Algorithm 3): 407323441104142607015539422158072296018149
 Input: p, y, R, S, M. 427716534804130441636635576091312662258757
 + Case No.1: 845096303882143614771060806488953511599782
 - The message (M): 9397260373114149558817750583
THIS IS A NEW DIGITAL SIGNATURE ALGORITHM!
 - Value of E:
 - Value of R: 552551286803389641937789869117923204883581
423075212967381365570286154186075643013021 540722
704004843447060655977130479044053204685193
 - Value of Z:
253406059065865451717576656375347757790084
3159418457812119241879758646 201595737909355043093039092014649024016097
 253561429177074478824215862484918660296556
 - Value of S:
 376258853319386641834258582058603343090017
407323441104142607015539422158072296018149 8721513406175725285896970811
 193
 2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
 - Value of A: In this case, the signature has been modified (the last digit of
 R has been modified), then the result shows that the signature
107176181863688309366891233947822068387651
 and message was denied for validity.
238133011104586640634308116068595547233030
 6) Security level of the newly proposed algorithm: The
975840620206832414013992565082088821981501
 safety level of the newly proposed algorithm can be assessed
9076330319423513169298904522
 by its ability to resist some types of attacks such as:
 - Value of B: - The secret key attack
 In the new proposed algorithm, the pair of parameters x
743269381442243470465432402145518013555831 1
 and x are both used as private keys to create a signature.
219948708460132428193160698522139765735306 2
 Therefore, the algorithm is only broken if both parameters are
530244897336446577497693051749773673397689
 exposed, in other words, the attacker must solve the expanded
7896799287519453093303007602
 root problem on Zp. Therefore, the safety level of the new
 Output:(R, S) = F alse. proposed algorithm in terms of attack resistance to expose the
 In this case, the message (M) has been modified (“NEW” private key is assessed by the difficulty of solving the above
was replaced by “OLD”), then the result is a disclaimer of the problem.
validity of the signature and message. It should be noted that this is a new kind of problem, even if
 + Case No.3: R of digital signature is fake. there are polynomial time algorithms for resolve Root Problem
 - The message M: (RP), it does not mean that this problem will be solved. In
 addition, the parameter q is also used as a private key in the
THIS IS A NEW DIGITAL SIGNATURE ALGORITHM! signing algorithm. Thus, in order to break down the security
 - Value of R: of the algorithm, the attacker must also solve the problem of
 finding the order of x1. However, finding the order of x1 is
423075212967381365570286154186075643013021 impossible, because x1 is a secret parameter.
704004843447060655977130479044053204685193 + Forged signature attack
253406059065865451717576656375347757790084 From the verifying algorithm (Algorithm 3) of the new
3159418457812119241879758640 proposed algorithm, a fake pair (R, S) will be recognized as
 - Value of S: a valid signature with an message M if the condition is met:
 y E (R·S) mod p
407323441104142607015539422158072296018149 R ≡ S × y mod p (18)
427716534804130441636635576091312662258757
 From (18), if R is selected before calculating S then the
845096303882143614771060806488953511599782
 condition (18) will take the following form:
9397260373114149558817750583
 SE ≡ a × y(R·S) mod p mod p (19)
 - Value of E:
331093805086206888598876639555451737904126 If S is selected before calculating R then the condition (18)
266485 will becomes:
 y (R·S) mod p
 - Value of Z: R ≡ b × y mod p (20)
432172226554930801404418305050132355077385 With a, b are constant numbers, it is easy to see that (19)
828215399388581383091930372572838283730157 and (20) are in the second form of expanded root problem
329373196470794060338722316157309032536776 with no efficient solution.
9107826072815241680469113476
 III. CONCLUSION
 - Value of A:
 This paper proposes a new digital signature scheme based
405674532712334991638171236575064127019077 on the difficulty of solving expanded root problems on Zp.
189874988519087379452713243002015605585476 Therefore, the safety level of the algorithms built by this
352317030374040845456818844545940912658471 method will be ensured by the difficulty of solving expanded
9887241515222904476971756719 root problems. In mathematics, this is a form of problem
 without solution before. Therefore, the newly proposed method
 - Value of B:
 can be used to develop a digital signature algorithm class for
386201321854166300058775478375866915385968 applications that require a high security in practice.
158426050566371654570609931577616241878570
772130272650950131562836384276719470528642 REFERENCES
8413431744203928752838444648 [1] Q. X. WU, Y. X. Yang and Z. M. HU, “New signature schemes based
 on discrete logarithms and factoring”, Journal of Beijing University of
 Output: (R, S) = F alse. Posts and Telecommunications, vol. 24, pp. 61–65, January 2001.
 194
 2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
 [2] Z. Y. Shen and X. Y. Yu, “Digital signature scheme based on discrete
 logarithms and factoring”, Information Technology, vol. 28. pp.21–22,
 June 2004.
 [3] Shimin Wei, “Digital Signature Scheme Based on Two Hard Problems”,
 International Journal of Computer Science and Network Security, vol.
 7, No 12, pp. 207–209, December 2007.
 [4] Eddie Shahrie Ismail, Tahat N.M.F., Rokiah. R. Ahmad, “A New Digital
 Signature Scheme Based on Factoring and Discrete Logarithms”, Journal
 of Mathematics and Statistics, April 2008.
 [5] Qin Yanlin, Wu Xiaoping, “New Digital Signature Scheme Based on
 both ECDLP and IFP”, 2nd IEEE International Conference on Computer
 Science and Information Technology, 8-11 August 2009, E-ISBN: 978-
 1-4244-4520-2, pp.348–351.
 [6] Swati Verma1, Birendra Kumar Sharma, “A New Digital Signature
 Scheme Based on Two Hard Problems”, International Journal of Pure
 and Applied Sciences and Technology, ISSN: 2229-6107, 5(2) (2011),
 pp.55–59.
 [7] Sushila Vishnoi, Vishal Shrivastava, “A new Digital Signature Algorithm
 based on Factorization and Discrete Logarithm problem”, International
 Journal of Computer Trends and Technology, vol. 3, Issue 4, 2012.
 [8] A.N. Berezin, N.A. Moldovyan, V.A. Shcherbacov, “Cryptoschemes
 Based on Difficulty of Simultaneous Solving Two Different Difficult
 Problems”, Computer Science Journal of Moldova, vol.21, no.2(62),
 2013.
 [9] Pham Van Hiep, Nguyen Huu Mong, Luu Hong Dung, “Constructing
 a digital signature algorithm based on the difficult of co-resolve two
 hard problems: integer factorization and discrete logarithm”, Journal of
 Science and Technology of Danang University, ISSN: 1859–1531, no.
 7(128), 2018.
[10] Nguyen Vinh Thai, Luu Hong Dung, “A public key cryptosystem based
 on the difficult of co-resolved two hard problems: discrete logarithm and
 root finding”, Journal on Information and Communications, Ministry of
 Information and Communications, ISSN: 1859–3550, December 2018.
[11] Luu Hong Dung, Tong Minh Duc, Luu Xuan Van, “A new method for
 constructing digital signature schemes base on difficulty of the integer
 factorization and discrete logarithm root problems the Zn”, Fundamental
 and Applied IT Research Conference, pp.1–9, August 2018.
[12] N.A. Moldovyan, “Digital Signature Scheme Based on a New Hard
 Problem”, Computer Science Journal of Moldova, vol.16, no.2(47),
 2008.
[13] T. Elgamal, “A public key cryptosystem and a signature scheme based on
 discrete logarithms”, IEEE Transactions on Information Theory. 1985,
 Vol. IT-31, No. 4. pp.469–472, 1985.
 195