Developing root problem aims to create a secure digital signature scheme in data transfer

In which:
 - p, t: System parameters/ Domain parameters. - M: message must be signed, with: M ∈{0, 1}∞
 ∗
 - q, x: Private keys. - H(.): hash function H : {0, 1} → Zn, with: q<n<p
 - y: Public key of signature object (U). - (R, S): signature of U on M.
 26
Algorithm 2 Signature Algorithm 4) On the validity of newly proposed scheme: The problem
 to prove here is: Let (p, q) are two prime numbers with
Input: (M, p, q, t, x, y) ∗
 q|(p − 1), H : {0, 1} → Zn, q<n<p, α ∈ (1,p), x =
Output: (R, S) (p−1)/q t t
 α mod p, y = x mod p, 1 <k<p, Z = k mod p,
 E = H(M)   −1 −1
 1: −(E−1·Z mod q) (E +1) mod q
 k :1<k<p− 1 E = H(M), S = k×x mod
 2: select −1 t ¯ t
 t p, u = S ×k mod p, R = u mod p. If: Z =(R×S )mod
 3: Z ← k mod p ¯
   −1 −1 E t Z
 −(E−1·Z mod q) (E +1) mod q p, A = R mod p, B = S × y mod p then: A = B.
 4: S ← k × x mod p
 −1 The validity of new proposed scheme is proved as:
 5: u ← S × k mod p
 t From (2), (3), (8), (11), (12), we have:
 6: R ← u mod p
 A = RE mod p = ut·E mod p
 7: if (R == 1) or (S == 1) then
  −1 −1 t·E
 8: go to 2 = SE × xE ·Z mod p
 9: end if −1 −1
 = SE ·t·E × xE ·Z·t·E mod p
 10: return (R, S)
 = St × xt·Z mod p
 = St × yZ mod p (15)
 3) Testing Algorithm: Testing algorithm of this scheme is Otherwise, from (2), (3), (5) (8), (11) and (12), we have:
assumed that:
 Z¯ = R × St mod p = ut × St mod p
 E t (R×St mod p)  t
 R ≡ S × y mod p = SE−1 × xE−1·Z × St mod p
 (E−1+1)·t t·E−1·Z
Here, E is a value representing for the message that need = S × x mod p
 −1 −1 −1
 E = H(M) M (R, S) −1 (E +1) ·(E +1)·t
to be verified: .If and the signature =(k × x−E ·Z )
satisfy the above equation then the signature is valid and
 t·E−1·Z
the message will be verified by originality also integrity. × x mod p
  t
Otherwise, the signature is invalid and the signature is denied = k × x−E−1·Z × xt·E−1·Z mod p
by the originality and integrity. Therefore, if the left side of
 t −t·E−1·Z t·E−1·Z
testing equation is calculated as: = k × x × x mod p
 = kt mod p (16)
 A = RE mod p (12)
 Instead (16) to (14), we have:
 ¯
and the right side of testing equation is calculated as: B = St × yZ mod p = St × yZ mod p (17)
 t Z¯ From (15) and (17), we have the proof: A = B.
 B = S × y mod p (13)
 5) Security level of the newly proposed algorithm: The
 safety level of the newly proposed algorithm can be assessed
in which:
 by its ability to resist some types of attacks such as:
 t - The secret key attack
 Z¯ =(R × S )modp (14)
 In the new proposed algorithm, the pair of parameters x and
 q are both used as private keys to create a signature. Therefore,
Then, the condition for valid signature is: A = B.
 the algorithm is only broken if both parameters are exposed,
 And after that, the testing algorithm of the new proposed
 in other words, the attacker must solve the root problem on
scheme is described in Algorithm 3 as:
 Zp and the problem of finding the order of x. Therefore, the
 safety level of the new proposed algorithm in terms of attack
Algorithm 3 Signature Testing Algorithm resistance to expose the private key is assessed by the difficulty
 p, t, y, M, R, S
Input: of solving the above problem. It should be noted that finding
 True/False
Output: the order of x is impossible, because x is a secret parameter.
 1: E = H(M)
 E + Forged signature attack
 2: A ← R mod p From the verifying algorithm (Algorithm 3) of the new
 ¯ t
 3: Z ← (R × S )modp proposed algorithm, a fake pair (R, S) will be recognized as
 t Z¯
 4: B ← S × y mod p a valid signature with an message M if the condition is met:
 5: if (A == B) then t
 RE ≡ St × y(R·S )modp mod p
 6: return True (18)
 7: else From (18), if R is selected before calculating S then the
 8: return False condition (18) will take the following form:
 9: end if t S
 S ≡ a mod p (19)
 27
 If S is selected before calculating R then the condition (18) and S is a number in (1,p):
will becomes: S = vx2 mod p (24)
 E R
 R ≡ b mod p (20) Assume that, the testing equation of scheme as:
 E y (R×S)modp
 With a, b are constant numbers, it is easy to see that (19) R ≡ S × y mod p (25)
and (20) are in the second form of expanded root problem in which: H(.) is a hash function, E = H(M), R × S mod
without an efficient solution. p = kx1·x2 mod p, and k = β(p−1)/q mod p, (β ∈ (1,p)).
 Let:
C. Constructing digital signature scheme based on the difficult
 kx1·x2 mod p = Z
of solving expanded root problem (26)
 1) Key generation algorithm: In a new proposed digital then, we can transform the testing equation as following form:
signature scheme, the first form of expanded root problem RE ≡ Sy × yZ mod p (27)
is used to generate private and public keys of the signature
 From (21), (22), (23) and (27), we have:
object. In which, p is system parameter (domain parameter)
 x1·E x2·y x1·x2·Z
that was created by service provider, here, p is a prime number u ≡ v × x1 mod p (28)
that must be chosen so that solving the RP is difficult. Let From (28) to:
(x1,x2) is private key and y is public key corresponding to −1 −1
 ux1 ≡ vx2·y·E × xx1·x2·Z·E mod p
the signature object in system. For creating private key x1, the 1 (29)
signature object has to generate a prime number - q satisfy: Otherwise, from (22),(23), (24), we have:
q|(p − 1) and α ∈ (1,p). Private key x1 is created by:
 ux1 × vx2 mod p ≡ kx1·x2
 p−1
 x1 = α q mod p (21) or:
 ux1 ≡ v−x2 × kx1·x2
 The private key x2 is randomly chosen in (1,q) (30)
 Then, the public key is calculated from (x1,x2) as: From (29) va` (30), we have:
 −1 −1
 (x1·x2)modq −x2 x1·x2 E ·x2·y x1·x2·E ·Z
 y = x1 mod p (22) v × k ≡ v × x1
 Note that the parameter q is also used with the role of a so:
 −1 −1
 (E ·y+1)·x2 x1·x2 −x1·x2·E ·Z
secret key similar to x1 and x2 in the signing algorithm. v × k × x1 mod p
 Parameters and Key generation algorithm can be described as:
as the following algorithm (Algorithm 4): −1 −1 x1·x2
 (E ·y+1)·x2 −E ·Z
 v ≡ (k × x1 ) mod p (31)
Algorithm 4 Parameters and Key Generation Algorithm From (31) to:
 −1
Input: lp, lq - length by bits of prime number p, q.  −1  −1
 v = k × x−E ·Z x1·(E ·y+1) mod p
Output: (p, q, x1,x2,y) 1 (32)
 1: generate p, q : len(p)=lp, len(q)=lq, q|(p − 1) From (32) and (30), we can calculate u as:
 α α ∈ (1,p) −1
 2: select : −x ·x2 x2
 (p−1)/q u = v 1 × k mod p
 3: select x2 ∈ (1,q),x1 ← α mod p
 4: if (x1 == 1) or (x2 == 1) then or:
  −1 x2
 5: go to 2 u = v−x1 × k mod p (33)
 6: end if
 (x ·x )modq u v R
 7: y ← x1 1 2 mod p From values of and , we can calculate of the signature
 by (22) and (33):
 8: return (p, q, x1,x2,y)
 R = ux1 mod p
 In which: or:
 - len(.) is a function that calculate the length by bits of a R = v−x2 × kx1·x2 mod p (34)
integer number.
 and calculate S by (23):
 - p: System parameters/ Domain parameters.
 S = vx2 mod p
 - q, x1,x2: Private keys.
 - y: Public key of signature object (U). So that, the signature algorithm is described on Algorithm
 2) Signature Algorithm: Suppose that (R, S) is the sig- 5.
 ∗
nature on the message M. R is calculated by u ∈ Zp as In which:
following: - M: message must be signed, with: M ∈{0, 1}∞.
 ∗
 - H(.): hash function H : {0, 1} → Zn, with: q<n<p.
 R = ux1 mod p
 (23) - (R, S): signature of U on M.
 28
Algorithm 5 Signature Algorithm 4) On the validity of newly proposed scheme: The problem
 (p, q)
 (M,p,q,x ,x ,y) to prove here is: Let are two prime number with
Input: 1 2 q|(p − 1) H : {0, 1}∗ → Z q<n<p α ∈ (1,p)
 (R, S) , n, , ,
Output: x = α(p−1)/q mod p x ∈ (1,q) y = xx1·x2 mod q mod p
 E = H(M) 1 , 2 , 1 ,
 1: (p−1)/q x1·x2 mod q
 (p−1)/q β ∈ (1,p), k ← β mod p, Z = k mod p,
 β : β ∈ (1,p),k ← β mod p  −1  −1 −1
 2: select (−E ·Z x1·(E ·y+1)
 x E = H(M) v = k × x mod p R =
 3: Z ← k 2 mod p , 1 ,
   −1 −1 −x2 x1·x2 x2 ¯
 −E−1·Z x1·(E ·y+1) v ×k mod p, S = v mod p. If: Z =(R×S)modp,
 4: v ← k × x1 mod p E y Z¯
 −x x ·x A = R mod p, B = S × y mod p then: A = B.
 5: R ← v 2 × k 1 2 mod p
 x The validity of new proposed scheme is proved as:
 6: S ← v 2 mod p
 From (21), (22), (23), (29), (32), (35), we have:
 7: if (R == 1) or (S == 1) then
 8: go to 2 A = RE mod p = ux1·E mod p
 9: end if  −1 −1 E
 = vx2·E ·y × x x1·x2·E ·Z mod p
 10: return (R, S) 1
 x2·y x1·x2·Z
 = v × x1 mod p
 = Sy × yZ mod p (38)
 3) Testing Algorithm: Testing algorithm of this scheme is
assumed that: Otherwise, from (22), (23), (25), (33) and (37), we have:
 ¯ x1 x2
 RE ≡ Sy × y(R×S mod p) mod p Z = R × S mod p = u × v mod p
  −1 x1·x2
 = v−x1 × k × vx2 mod p
Here, E is a value representing for the message that need
 = v−x2 × kx1·x2 × vx2 mod p
to be verified: E = H(M).IfM and the signature (R, S)
 x1·x2
satisfy the above equation then the signature is valid and = k mod p = Z (39)
the message will be verified by originality also integrity.
Otherwise, the signature is invalid and the signature is denied Instead (39) to (36), we have:
by the originality and integrity. Therefore, if the left side of y Z¯ y Z
 B = S × y mod p = S × y mod p (40)
testing equation is calculated as:
 From (39) and (40), we have the proof: A = B.
 A = RE mod p (35)
 5) Security level of the newly proposed algorithm: The
 safety level of the newly proposed algorithm can be assessed
and the right side of testing equation is calculated as:
 by its ability to resist some types of attacks such as:
 ¯
 B = Sy × yZ mod p (36) - The secret key attack
 In the new proposed algorithm, the pair of parameters
 x ,x q
in which: 1 2 and are used as private keys to create a signature.
 Therefore, the algorithm is only broken if three parameters are
 Z¯ = R × S mod p (37) exposed, in other words, the attacker must solve the expanded
 root problem on Zp and find the order of x1. Therefore, the
Then, the condition for valid signature is: A = B. safety level of the new proposed algorithm in terms of attack
 And after that, the testing algorithm of the new proposed resistance to expose the private key is assessed by the difficulty
scheme is described in Algorithm 6. of solving two above problem simultaneously.
 It should be noted that EFRP is a new kind of problem,
Algorithm 6 Signature Testing Algorithm even if there are polynomial time algorithms for resolve Root
 Problem (RP), it does not mean that this problem will be
Input: p, y, M, R, S
 solved. In addition, the parameter q is also used as a private
Output: True/False
 key in the signing algorithm. Thus, in order to break down
 1: E = H(M)
 E the security of the algorithm, the attacker must also solve the
 2: A ← R mod p
 ¯ problem of finding the order of x1. However, finding the order
 3: Z ← (R × S)modp
 y Z¯ of x1 is impossible, because x1 is a secret parameter.
 4: B ← S × y mod p
 + Forged signature attack
 5: if (A == B) then
 6: return True From the verifying algorithm (Algorithm 3) of the new
 (R, S)
 7: else proposed algorithm, a fake pair will be recognized as
 M
 8: return False a valid signature with an message if the condition is met:
 9: end if E y (R×S)modp
 R ≡ S × y mod p (41)
 29
 From (41), if R is selected before calculating S then the [13] T. Elgamal, “A public key cryptosystem and a signature scheme based on
 discrete logarithms”, IEEE Transactions on Information Theory. 1985,
condition (41) will take the following form: Vol. IT-31, No. 4. pp.469–472, 1985.
 Sy ≡ aS mod p (42)
 If S is selected before calculating R then the condition (41)
will becomes:
 RE ≡ bR mod p (43)
 With a, b are constant numbers, it is easy to see that (42)
and (43) are in the second form of expanded root problem
without an efficient solution.
 III. CONCLUSION
 This paper proposes two new digital signature scheme based
on the difficulty of solving root problem and expanded root
problems simultaneously on Zp. Therefore, the safety level of
the algorithms built by this method will be ensured by the
difficulty of solving expanded root problems. In mathematics,
this is a form of problem without solution before. Therefore,
the newly proposed method can be used to develop a secure
digital signature algorithm class for data transfer applications
that require a high security in practice.
 REFERENCES
 [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
 Posts and Telecommunications, vol. 24, pp. 61–65, January 2001.
 [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.
 30