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

DEVELOPING ROOT PROBLEM AIMS TO
CREATE A SECURE DIGITAL SIGNATURE
SCHEME IN DATA TRANSFER
1st Luu Xuan Van
Faculty of Info.Tech and Security
People’s Security Academy
Hanoi, Vietnam
vanlx.hvan@gmail.com
2nd Luu Hong Dung
Faculty of Information Technology
Military Technical Academy
Hanoi, Vietnam
luuhongdung@gmail.com
3rd Doan Van Hoa
Military Institute of
Science and Technology
Hanoi, Vietnam
doanvanhoa@gmail.com
Abstract—This paper presents the proposed method of building
a digital signature algorithm which is based on the difficulty of
solving root problem and some expanded root problems on Zp.
The expanded root problem is a new form of difficult problem
without the solution, also originally proposed and applied to
build digital signature algorithms. This proposed method enable
to build a high-security digital signature platform for practical
applications.
Index Terms—Digital signature, Digital signature scheme, Root
problem, Expanded root problem.
I. INTRODUCTION
Digital signatures are now widely used in the world as
well as in Vietnam in various fields such as e-government, e-
commerce,... or in telecommunication systems and computer
networks. However, the research and development of new
digital signature schemes improving the performance and
safety of the algorithm for the purpose of designing protective
products, devices as well as guaranteeing domestic information
security has always been a necessary issue. Recently, the
research improving the security of digital signature algorithms
based on the difficulty of solving two simultaneously difficult
problems is an approach receiving a lot of attention from
researchers.
In [1]–[10], authors have proposed some signature algo-
rithms built on simultaneously two problems of numerical
factorization and discrete logarithm. In this paper, with the
aim of improving the safety of digital signature algorithms,
we continue to develop the proposed method in [11] on the
basis of the difficulty of solving root problem and expanded
root problem on Zp. This is a new difficult type of problem
that was first proposed and applied for the construction of
a digital signature algorithm, and it has many prospects that
allow the construction of algorithms suitable for high security
requirement in practice.
II. CONSTRUCTING DIGITAL SIGNATURE SCHEME BASED
ON THE DIFFICULT OF SOLVING ROOT PROBLEM AND
EXPANDED ROOT PROBLEM ON Zp
A. Root problem and expanded root problem on Zp
1) Root problem on Zp: Given a pair of positive integers
(p, t), with p and t are prime numbers. Root problem on Zp
(known as RP problem) is stated as:
Let a positive number y ∈ Z∗p , find x satisfy following
equation:
xt mod p = y
In [12], N.A. Moldovyan has proved that the above root
problem is difficult if p and t satisfy:
p = N × te + 1
In which: N is a integer number and e ≥ 2.
2) Some expanded root problem on Zp: The proposed
problem is a form of root problem, it is Expanded Finding
Root Problem (EFRP), the first form of this problem is stated
as:
Let p, q are prime numbers satisfy: q|(p − 1), for each
positive number y ∈ Z∗p , find x1 and x2 satisfy following
equation:
y = x1
x1·x2 mod q mod p
Formally, if q, x2 are constant numbers and x1 is a variable
then the above problem will be Root Problem on the Zp [12],
if q, x1 are constant and x2 is a variable, this is the Discrete
Logarithm Problem (DLP) - The base for building the ElGamal
Encryption System [13]. However, q, x1 and x2 are variables
here, then, algorithms for solving RP and DLP can not be
applied for this first form of expanded root problem.
The second form of expanded root problem is stated as:
Let a positive number p ∈ Z∗p , for each pair of numbers
a, b ∈ Z∗p , find x satisfy following equation:
ax = xb mod p
Similarly the first form of EFRP, if the left side of above
equation is a constant number, then above problem will be a
25
2020 International Conference on Green and Human Information Technology (ICGHIT)
978-1-7281-6295-9/20/$31.00 ©2020 IEEE
DOI 10.1109/ICGHIT49656.2020.00013
Root Problem on Zp (RP), if the right side of above equation
is a constant number, then above problem will be a Discrete
Logarithm Problem.
However, two sides of that equation are not constant num-
bers, then, algorithms for solving RP and DLP can not be
applied for this second form of EFRP. This shows that the
new proposed problem here is more difficult than DLP and
RP.
B. Constructing digital signature scheme based on the difficult
of root problem
1) Key generation algorithm: In a new proposed digital
signature scheme, the root problem is used to generate private
and public keys of the signature object. In which, p and t are
system parameters (domain parameters) that was created by
service provider, here, p is a prime number that must be chosen
so that solving the RP is difficult. Let x is private key and y
is public key corresponding to the signature object in system.
For creating private key x, the signature object has to generate
a prime number - q satisfy: q|(p−1) and α ∈ (1, p−1). Private
key x is created by:
x = α
p−1
q mod p (1)
The public key is calculated from x as:
y = xt mod p (2)
Note that, parameters p, e must be satisfied: p = N × te + 1,
in which: N is a integer number and e ≥ 2 must be chosen
so that solving the RP is difficult.
Parameters and Key generation algorithm can be described
as the following algorithm (Algorithm 1):
Algorithm 1 Parameters and Key Generation Algorithm
Input: lp, lq - length by bits of prime numbers p, q.
Output: (p, q, t, x, y).
1: generate p : len(p) = lp
2: select t: te|(p− 1), e ≥ 2
3: generate q, α: q|(p− 1), 1 < α < p− 1
4: x ← α(p−1)/q mod p
5: if (x == 1) then
6: go to 2
7: end if
8: y ← xt mod p
9: return (p, q, t, x, y)
In which:
- len(.) is a function that calculate the length by bits of a
integer number.
- p, t: System parameters/ Domain parameters.
- q, x: Private  ... s a value representing for the message that need
to be verified: E = H(M). If M and the signature (R,S)
satisfy the above equation then the signature is valid and
the message will be verified by originality also integrity.
Otherwise, the signature is invalid and the signature is denied
by the originality and integrity. Therefore, if the left side of
testing equation is calculated as:
A = RE mod p (12)
and the right side of testing equation is calculated as:
B = St × yZ¯ mod p (13)
in which:
Z¯ = (R× St) mod p (14)
Then, the condition for valid signature is: A = B.
And after that, the testing algorithm of the new proposed
scheme is described in Algorithm 3 as:
Algorithm 3 Signature Testing Algorithm
Input: p, t, y,M,R, S
Output: True/False
1: E = H(M)
2: A ← RE mod p
3: Z¯ ← (R× St) mod p
4: B ← St × yZ¯ mod p
5: if (A == B) then
6: return True
7: else
8: return False
9: end if
4) On the validity of newly proposed scheme: The problem
to prove here is: Let (p, q) are two prime numbers with
q|(p − 1), H : {0, 1}∗ → Zn, q < n < p, α ∈ (1, p), x =
α(p−1)/q mod p, y = xt mod p, 1 < k < p, Z = kt mod p,
E = H(M), S =
(
k×x−(E−1·Z mod q))(E
−1+1)−1 mod q
mod
p, u = S−1×k mod p, R = ut mod p. If: Z¯ = (R×St) mod
p, A = RE mod p, B = St × yZ¯ mod p then: A = B.
The validity of new proposed scheme is proved as:
From (2), (3), (8), (11), (12), we have:
A = RE mod p = ut·E mod p
=
(
SE
−1 × xE−1·Z)t·E mod p
= SE
−1·t·E × xE−1·Z·t·E mod p
= St × xt·Z mod p
= St × yZ mod p (15)
Otherwise, from (2), (3), (5) (8), (11) and (12), we have:
Z¯ = R× St mod p = ut × St mod p
=
(
SE
−1 × xE−1·Z)t × St mod p
= S(E
−1+1)·t × xt·E−1·Z mod p
= (k × x−E−1·Z)(E
−1+1)−1·(E−1+1)·t
× xt·E−1·Z mod p
=
(
k × x−E−1·Z)t × xt·E−1·Z mod p
= kt × x−t·E−1·Z × xt·E−1·Z mod p
= kt mod p (16)
Instead (16) to (14), we have:
B = St × yZ¯ mod p = St × yZ mod p (17)
From (15) and (17), we have the proof: A = B.
5) Security level of the newly proposed algorithm: The
safety level of the newly proposed algorithm can be assessed
by its ability to resist some types of attacks such as:
- The secret key attack
In the new proposed algorithm, the pair of parameters x and
q are both used as private keys to create a signature. Therefore,
the algorithm is only broken if both parameters are exposed,
in other words, the attacker must solve the root problem on
Zp and the problem of finding the order of x. Therefore, the
safety level of the new proposed algorithm in terms of attack
resistance to expose the private key is assessed by the difficulty
of solving the above problem. It should be noted that finding
the order of x is impossible, because x is a secret parameter.
+ Forged signature attack
From the verifying algorithm (Algorithm 3) of the new
proposed algorithm, a fake pair (R,S) will be recognized as
a valid signature with an message M if the condition is met:
RE ≡ St × y(R·St) mod p mod p (18)
From (18), if R is selected before calculating S then the
condition (18) will take the following form:
St ≡ aS mod p (19)
27
If S is selected before calculating R then the condition (18)
will becomes:
RE ≡ bR mod p (20)
With a, b are constant numbers, it is easy to see that (19)
and (20) are in the second form of expanded root problem
without an efficient solution.
C. Constructing digital signature scheme based on the difficult
of solving expanded root problem
1) Key generation algorithm: In a new proposed digital
signature scheme, the first form of expanded root problem
is used to generate private and public keys of the signature
object. In which, p is system parameter (domain parameter)
that was created by service provider, here, p is a prime number
that must be chosen so that solving the RP is difficult. Let
(x1, x2) is private key and y is public key corresponding to
the signature object in system. For creating private key x1, the
signature object has to generate a prime number - q satisfy:
q|(p− 1) and α ∈ (1, p). Private key x1 is created by:
x1 = α
p−1
q mod p (21)
The private key x2 is randomly chosen in (1, q)
Then, the public key is calculated from (x1, x2) as:
y = x1
(x1·x2) mod q mod p (22)
Note that the parameter q is also used with the role of a
secret key similar to x1 and x2 in the signing algorithm.
Parameters and Key generation algorithm can be described
as the following algorithm (Algorithm 4):
Algorithm 4 Parameters and Key Generation Algorithm
Input: lp, lq - length by bits of prime number p, q.
Output: (p, q, x1, x2, y)
1: generate p, q : len(p) = lp, len(q) = lq, q|(p− 1)
2: select α: α ∈ (1, p)
3: select x2 ∈ (1, q), x1 ← α(p−1)/q mod p
4: if (x1 == 1) or (x2 == 1) then
5: go to 2
6: end if
7: y ← x1(x1·x2) mod q mod p
8: return (p, q, x1, x2, y)
In which:
- len(.) is a function that calculate the length by bits of a
integer number.
- p: System parameters/ Domain parameters.
- q, x1, x2: Private keys.
- y: Public key of signature object (U).
2) Signature Algorithm: Suppose that (R,S) is the sig-
nature on the message M . R is calculated by u ∈ Z∗p as
following:
R = ux1 mod p (23)
and S is a number in (1, p):
S = vx2 mod p (24)
Assume that, the testing equation of scheme as:
RE ≡ Sy × y(R×S) mod p mod p (25)
in which: H(.) is a hash function, E = H(M), R × S mod
p = kx1·x2 mod p, and k = β(p−1)/q mod p, (β ∈ (1, p)).
Let:
kx1·x2 mod p = Z (26)
then, we can transform the testing equation as following form:
RE ≡ Sy × yZ mod p (27)
From (21), (22), (23) and (27), we have:
ux1·E ≡ vx2·y × x1x1·x2·Z mod p (28)
From (28) to:
ux1 ≡ vx2·y·E−1 × xx1·x2·Z·E−11 mod p (29)
Otherwise, from (22),(23), (24), we have:
ux1 × vx2 mod p ≡ kx1·x2
or:
ux1 ≡ v−x2 × kx1·x2 (30)
From (29) va` (30), we have:
v−x2 × kx1·x2 ≡ vE−1·x2·y × x1x1·x2·E−1·Z
so:
v(E
−1·y+1)·x2 × kx1·x2 × x−x1·x2·E−1·Z1 mod p
as:
v(E
−1·y+1)·x2 ≡ (k × x−E−1·Z1 )
x1·x2
mod p (31)
From (31) to:
v =
(
k × x−E−1·Z1
)x1·(E−1·y+1)−1
mod p (32)
From (32) and (30), we can calculate u as:
u = v−x
−1
1 ·x2 × kx2 mod p
or:
u =
(
v−x1
−1 × k)x2 mod p (33)
From values of u and v, we can calculate R of the signature
by (22) and (33):
R = ux1 mod p
or:
R = v−x2 × kx1·x2 mod p (34)
and calculate S by (23):
S = vx2 mod p
So that, the signature algorithm is described on Algorithm
5.
In which:
- M : message must be signed, with: M ∈ {0, 1}∞.
- H(.): hash function H : {0, 1}∗ → Zn, with: q < n < p.
- (R,S): signature of U on M .
28
Algorithm 5 Signature Algorithm
Input: (M,p, q, x1, x2, y)
Output: (R,S)
1: E = H(M)
2: select β : β ∈ (1, p), k ← β(p−1)/q mod p
3: Z ← kx2 mod p
4: v ← (k × x−E−1·Z1
)x1·(E−1·y+1)−1
mod p
5: R ← v−x2 × kx1·x2 mod p
6: S ← vx2 mod p
7: if (R == 1) or (S == 1) then
8: go to 2
9: end if
10: return (R,S)
3) Testing Algorithm: Testing algorithm of this scheme is
assumed that:
RE ≡ Sy × y(R×S mod p) mod p
Here, E is a value representing for the message that need
to be verified: E = H(M). If M and the signature (R,S)
satisfy the above equation then the signature is valid and
the message will be verified by originality also integrity.
Otherwise, the signature is invalid and the signature is denied
by the originality and integrity. Therefore, if the left side of
testing equation is calculated as:
A = RE mod p (35)
and the right side of testing equation is calculated as:
B = Sy × yZ¯ mod p (36)
in which:
Z¯ = R× S mod p (37)
Then, the condition for valid signature is: A = B.
And after that, the testing algorithm of the new proposed
scheme is described in Algorithm 6.
Algorithm 6 Signature Testing Algorithm
Input: p, y,M,R, S
Output: True/False
1: E = H(M)
2: A ← RE mod p
3: Z¯ ← (R× S) mod p
4: B ← Sy × yZ¯ mod p
5: if (A == B) then
6: return True
7: else
8: return False
9: end if
4) On the validity of newly proposed scheme: The problem
to prove here is: Let (p, q) are two prime number with
q|(p − 1), H : {0, 1}∗ → Zn, q < n < p, α ∈ (1, p),
x1 = α
(p−1)/q mod p, x2 ∈ (1, q), y = xx1·x2 mod q1 mod p,
β ∈ (1, p), k ← β(p−1)/q mod p, Z = kx1·x2 mod q mod p,
E = H(M), v =
(
k× x(−E−1·Z1
)x1·(E−1·y+1)−1
mod p, R =
v−x2×kx1·x2 mod p, S = vx2 mod p. If: Z¯ = (R×S) mod p,
A = RE mod p, B = Sy × yZ¯ mod p then: A = B.
The validity of new proposed scheme is proved as:
From (21), (22), (23), (29), (32), (35), we have:
A = RE mod p = ux1·E mod p
=
(
vx2·E
−1·y × x1x1·x2·E−1·Z
)E
mod p
= vx2·y × x1x1·x2·Z mod p
= Sy × yZ mod p (38)
Otherwise, from (22), (23), (25), (33) and (37), we have:
Z¯ = R× S mod p = ux1 × vx2 mod p
=
(
v−x1
−1 × k)x1·x2 × vx2 mod p
= v−x2 × kx1·x2 × vx2 mod p
= kx1·x2 mod p = Z (39)
Instead (39) to (36), we have:
B = Sy × yZ¯ mod p = Sy × yZ mod p (40)
From (39) and (40), we have the proof: A = B.
5) Security level of the newly proposed algorithm: The
safety level of the newly proposed algorithm can be assessed
by its ability to resist some types of attacks such as:
- The secret key attack
In the new proposed algorithm, the pair of parameters
x1, x2 and q are used as private keys to create a signature.
Therefore, the algorithm is only broken if three parameters are
exposed, in other words, the attacker must solve the expanded
root problem on Zp and find the order of x1. Therefore, the
safety level of the new proposed algorithm in terms of attack
resistance to expose the private key is assessed by the difficulty
of solving two above problem simultaneously.
It should be noted that EFRP is a new kind of problem,
even if there are polynomial time algorithms for resolve Root
Problem (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 signing algorithm. Thus, in order to break down
the security of the algorithm, the attacker must also solve the
problem of finding the order of x1. However, finding the order
of x1 is impossible, because x1 is a secret parameter.
+ Forged signature attack
From the verifying algorithm (Algorithm 3) of the new
proposed algorithm, a fake pair (R,S) will be recognized as
a valid signature with an message M if the condition is met:
RE ≡ Sy × y(R×S) mod p mod p (41)
29
From (41), if R is selected before calculating S then the
condition (41) will take the following form:
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.
[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.
30