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

CONSTRUCTING A DIGITAL SIGNATURE
ALGORITHM BASED ON THE DIFFICULTY OF
SOME EXPANDED ROOT PROBLEMS
1st Luu Xuan Van
Faculty of Information Technology 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
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 algorithm,
Digital signature scheme, 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 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, e), with p and e are prime numbers. Root problem on Zp
(known as RP(p,e) problem - RP) is stated as:
Let a positive number y ∈ Z∗p , find x satisfy following
equation:
xe mod p = y
In [12], N.A. Moldovyan has proved that the above root
problem is difficult if p and e satisfy:
p = N × et + 1
In which: N is a integer number and t ≥ 2.
2) Expanded root problem on Zp: The proposed problem
is a form of root problem, the first form of this problem is
stated as:
Let a positive number y ∈ Z∗p , find x1 and x2 satisfy
following equation:
y = x1
x2 mod p
Formally, if x2 is constant number and x1 is a variable
then the above problem will be Root Problem on the Zp [12].
However, x1 and x2 are variables here, then, algorithms for
solving RP 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 y ∈ Z∗p , find x1 and x2 satisfy
following equation:
yx2 = x1
e mod p
Similarly the first form, if x2 is a constant number and x1
is a variable, then above problem will be a Root Problem on
Zp (RP) [12]. However, x2 is also a variable must be find as
x1, then, algorithms for solving RP can not be applied for this
second form of expanded root problem.
2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
978-1-7281-5163-2/19/$31.00 ©2019 IEEE 190
In addition, it is easy to show that, in both forms of the
above expanded root problem, if x1 is a constant and x2 is
an unknown variable, this is the Discrete Logarithm Problem
(DLP) - The base for building the ElGamal Encryption System
[13]. However, as shown in the above two cases, both x1
and x2 here are variables. So in both cases, algorithms for
DLP cannot apply to solving this problem either. Preliminary
analysis can show that the expanded root problem proposed
is more difficult to solve than RP and DLP problems. In the
details, the problem of the expanded root problem will be
presented by the authors in another research.
B. Constructing digital signature scheme based on the difficult
of newly proposed 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 a 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− 1). Private key x1 is created by:
x1 = α
p−1
q mod p
Private key x2 is chosen randomly in (1, q).
Then, public key is calculated from (x1, x2) as:
y = (x1)
x1·x2 mod q mod p (1)
Note that, the parameter q is also used as a private key,
similarly as x1 and x2 in signature algorithm.
Key generation algorithm can be described as the following
algorithm (Algorithm 1):
Algorithm 1 Key Generation Algorithm
Input: p - a prime number, lq - length by bits of q
Output: (q, x1, x2, y)
1: generate q : len(q) = lq, q|(p− 1)
2: select α: 1 < α < p
3: select x2 ∈ (1, q)
4: x1 ← α(p−1)/q mod p
5: if ((x1 == 1) or (x2 == 1)) then
6: go to 2
7: end if
8: y ← x1(x1·x2) mod q mod p
9: return (q, x1, x2, y)
In which:
- len(.) is a function that calculate the length by bits of a
integer number.
- p: System  ... x1)−x1·(y)−1·Z
)(y−1·E+1)−1
mod p (11)
From (11), we can calculate u by (8):
u = vy
−1·E × xx1·y
−1
1 ·Z
1 mod p
From values of u and v, we can calculate R of the signature
by (2):
R = ux2 mod p
and calculate S by (3):
S = vx2 mod p
So that, the signature algorithm is described on Algorithm
2 as:
In which:
- M : message must be signed, with: M ∈ {0, 1}∞
- H(.): hash function H : {0, 1}∗ 7→ Zn, with: q < n < p
- (R,S): signature of U on M .
2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
191
Algorithm 2 Signature Algorithm
Input: (p, q, x1, x2, y)
Output: (R,S)
1: E = H(M)
2: select k : 1 < k < p− 1
3: Z ← kx2 mod p
4: v ← (k × (x1)−x1·(y)−1·Z)(y−1·E+1)−1 mod p
5: u← vy−1·E × xx1·y
−1
1 ·Z
1 mod p
6: R← ux2 mod p
7: S ← vx2 mod p
8: if (R == 1) or (S == 1) then
9: go to 2
10: end if
11: return (R,S)
3) Testing Algorithm: Testing algorithm of this scheme is
assumed that:
Ry ≡ SE × 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 = Ry mod p (12)
and the right side of testing equation is calculated as:
B = SE × (y)Z mod p (13)
in which:
Z¯ = R× S 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, y,M,R, S
Output: True/False
1: E = H(M)
2: A← Ry mod p
3: Z¯ ← (R× S) mod p
4: B ← SE × 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}∗ 7→ Zn, q < n < p, 1 < α < p,
x1 = α
(p−1)/q mod p, x2 ∈ (1, q), y = (x1)(x1·x2) mod q mod
p, 1 < k < p, Z = x1k mod p, E = H(M), v =(
k × (x1)−x1·(y)−1·Z
)(y−1·E+1)−1
mod p, u = vy
−1·E ×
x
x1·y−11 ·Z
1 mod p, R = u
x2 mod p, S = vx2 mod p. If:
Z¯ = (R×S) mod p, A = Ry mod p, B = SE× (y)Z¯ mod p
then: A = B.
The validity of new proposed scheme is proved as:
From (1), (2), (3), (8), (11), (13), we have:
A = Ry mod p = ux2·y mod p
=
(
vy
−1·E × x1x1·y−1·Z
)x2·y
mod p
= vy
−1·E·x2·y × x1x1·y−1·Z·x2·y mod p
= vx2·E × x1x1·x2·Z mod p
= SE × yZ mod p (15)
Otherwise, from (2), (3), (8), (11) and (12), we have:
Z¯ = R× S mod p = ux2 × vx2 mod p
=
(
v(y)
−1·E × (x1)x1·y
−1·Z)x2 × vx2 mod p
= vy
−1·E·x2+x2 × x1x1·x2·y−1·Z mod p
= v(y
−1·E+1)·x2 × x1x1·x2·y−1·Z mod p
=
(
k × (x1)−x1·y
−1·Z)(y−1·E+1)−1·(y−1·E+1)·x2
× x1x1·x2·y−1·Z mod p
=
(
k × (x1)−x1·y
−1·Z)x2 × x1x1·x2·y−1·Z mod p
= kx2 × x1−x1·x2·y−1·Z × x1x1·x2·y2−1·Z mod p
= kx2 mod p = Z (16)
Instead (16) to (14), we have:
B = SE × yZ¯ mod p = SE × yZ mod p (17)
From (15) and (17), we have the proof: A = B.
5) Example: The validity of new proposed scheme is
described as the following example:
a) Parameter and key generation (Algorithm 1):
- Value of p:
891505711756810466801538581994639035723395
046984393012096518029175988878598532328716
007897388814756369043609524344142253015152
2256624968441471249159548721
- Value of q:
114169146889658081579965580080483177277395
1929057
- Value of x1:
787554019949566514178024987720721359923067
165874275462504405665757532105277496444801
718504313823545333439710356295680887406478
2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
192
1047383620292559004679777805
- Value of x2:
544679862739775176263996254185216317667127
684479100060093664136715997878178597128117
126805135609079604644585387615811144496262
8702531372228447519121344128
- Value of y:
441063086344010474906300383421442247158936
925505706949717244934963160362941072411938
445096088489139300691625194975575669586229
6845650459797968526942837435
b) Signature generation (Algorithm 2):
Input: p, y, x1, x2,M .
Output: (R,S).
- Message (M ):
THIS IS A NEW DIGITAL SIGNATURE ALGORITHM!
- Value of k:
224810619659488341208713525047815187805617
284189918974458223089880229903478611827454
354135800782245853186661590101057844721463
9010271583824330185230043744
- Value of E:
331093805086206888598876639555451737904126
266485
- Value of R:
423075212967381365570286154186075643013021
704004843447060655977130479044053204685193
253406059065865451717576656375347757790084
3159418457812119241879758646
- Value of S:
407323441104142607015539422158072296018149
427716534804130441636635576091312662258757
845096303882143614771060806488953511599782
9397260373114149558817750583
c) Signature Verification (Algorithm 3):
Input: p, y,R, S,M .
+ Case No.1:
- The message (M):
THIS IS A NEW DIGITAL SIGNATURE ALGORITHM!
- Value of R:
423075212967381365570286154186075643013021
704004843447060655977130479044053204685193
253406059065865451717576656375347757790084
3159418457812119241879758646
- Value of S:
407323441104142607015539422158072296018149
427716534804130441636635576091312662258757
845096303882143614771060806488953511599782
9397260373114149558817750583
- Value of E:
331093805086206888598876639555451737904126
266485
- Value of Z:
201595737909355043093039092014649024016097
253561429177074478824215862484918660296556
376258853319386641834258582058603343090017
8721513406175725285896970811
- Value of A:
107176181863688309366891233947822068387651
238133011104586640634308116068595547233030
975840620206832414013992565082088821981501
9076330319423513169298904522
- Value of B:
107176181863688309366891233947822068387651
238133011104586640634308116068595547233030
975840620206832414013992565082088821981501
9076330319423513169298904522
Output: (R,S) = True.
So that, both the signature and message are not modified,
then the result shows that, the signature is valid, and therefore,
the message is verified for its origin and integrity.
+ Case No.2: The message M is fake.
- The message (M):
THIS IS A OLD DIGITAL SIGNATURE ALGORITHM!
- Value of R:
423075212967381365570286154186075643013021
704004843447060655977130479044053204685193
253406059065865451717576656375347757790084
3159418457812119241879758646
- Value of S:
407323441104142607015539422158072296018149
427716534804130441636635576091312662258757
845096303882143614771060806488953511599782
9397260373114149558817750583
- Value of E:
552551286803389641937789869117923204883581
540722
- Value of Z:
201595737909355043093039092014649024016097
253561429177074478824215862484918660296556
376258853319386641834258582058603343090017
8721513406175725285896970811
2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
193
- Value of A:
107176181863688309366891233947822068387651
238133011104586640634308116068595547233030
975840620206832414013992565082088821981501
9076330319423513169298904522
- Value of B:
743269381442243470465432402145518013555831
219948708460132428193160698522139765735306
530244897336446577497693051749773673397689
7896799287519453093303007602
Output:(R,S) = False.
In this case, the message (M ) has been modified (“NEW”
was replaced by “OLD”), then the result is a disclaimer of the
validity of the signature and message.
+ Case No.3: R of digital signature is fake.
- The message M :
THIS IS A NEW DIGITAL SIGNATURE ALGORITHM!
- Value of R:
423075212967381365570286154186075643013021
704004843447060655977130479044053204685193
253406059065865451717576656375347757790084
3159418457812119241879758640
- Value of S:
407323441104142607015539422158072296018149
427716534804130441636635576091312662258757
845096303882143614771060806488953511599782
9397260373114149558817750583
- Value of E:
331093805086206888598876639555451737904126
266485
- Value of Z:
432172226554930801404418305050132355077385
828215399388581383091930372572838283730157
329373196470794060338722316157309032536776
9107826072815241680469113476
- Value of A:
405674532712334991638171236575064127019077
189874988519087379452713243002015605585476
352317030374040845456818844545940912658471
9887241515222904476971756719
- Value of B:
386201321854166300058775478375866915385968
158426050566371654570609931577616241878570
772130272650950131562836384276719470528642
8413431744203928752838444648
Output: (R,S) = False.
In this case, the signature has been modified (the last digit of
R has been modified), then the result shows that the signature
and message was denied for validity.
6) 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
and x2 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 expanded
root problem on Zp. 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 this 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:
Ry ≡ SE × y(R·S) mod p mod p (18)
From (18), if R is selected before calculating S then the
condition (18) will take the following form:
SE ≡ a× y(R·S) mod p mod p (19)
If S is selected before calculating R then the condition (18)
will becomes:
Ry ≡ b× y(R·S) mod p 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
with no efficient solution.
III. CONCLUSION
This paper proposes a new digital signature scheme based
on the difficulty of solving expanded root problems 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 digital signature algorithm class for
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.
2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
194
[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.
2019 6th NAFOSTED Conference on Information and Computer Science (NICS)
195