Constructing digital signature algorithms based on new key schemes

ructing digital signature algorithm based on 2-key scheme
 The method of constructing the digital signature algorithm based on the 2-key scheme
herein is also presented through several steps of constructing a digital signature scheme:
 2.3.1. Parameter and key generation algorithm:
 In this method of constructing digital signature algorithm, the 2-key scheme is used
to generate pairs of the private and public keys of signing objects. The key generation
algorithm is described in Table 4. Where, p and q are system parameters (domain
parameters) generated by the DASP, p here is a prime number that needs to be chosen
so that it is difficult to solve DLP and q|(p − 1).(x1, x2) pair is private keys and (y1, y2)
are corresponding public keys of each signing object in the system. To generate x1 key,
 ∗
each signing object requires a number α ∈ Zp , x1 key is generated according to:
 (p−2)/q
 x1 = α mod p
 x2 key is a randomly chosen value in the range of (1, q). Then public keys are generated
from (x1, x2) according to (21) as follows:
  x1
 y1 = (x1) mod p
 (x )−1×x modp (21)
 y2 = (x1) 1 2 mod p
 The parameter and key generation algorithm is likely to be described as shown in
Table 4:
 Table 4. Parameter and key generation algorithm
 Input: p – prime number, lq – length (in bits) of prime number q.
 Output: q, x1, x2, y1, y2.
 [1]. generate q: len(q) = lq, q|(p − 1)
 [2]. select α : 1 < α < p
 (p−1)/q
 [3]. x1 ← α mod p
 [4]. if (x1 = 1) then goto [2]
 [5]. select x2: 1 < x2 < q
 x1 (x )−1×x modq
 [6]. y1 ← (x1) mod p, y2 ← (x1) 1 2 mod p
 [7]. return {q, x1, x2, y1, y2}
 Note:
 - len(.): The function calculates the length (in bits) of an integer.
 - p, q: System parameters/domain parameters.
 - x1, x2: Private key.
 13
Section on Information and Communication Technology (ICT) - No. 16 (12-2020)
 - y1, y2: Public key of a signing object.
 2.3.2. Signing algorithm:
 Suppose that (R, S) is the signature on the message M, u is a value in the range of
(1, q) and R is calculated from u according to:
 u
 R = (x1) mod p (22)
and S is calculated from v according to:
 v
 U = (x1) mod p (23)
Here: v is also a value in the range (1, q).
 Also, suppose that the verification equation of the algorithm has a form:
 y y E (R×Smodp)modq
 S 1 ≡ R 2 ×(y1) ×(y2) mod p with E = H(M) and
 k
and R × S mod p = (x1) mod p (24)
 ∗
in which H(.) is the hash function, M is the message to sign and k ∈ Zq .
 k
 Set (x1) mod p =T (25)
 Then, the verification equation can be get into the form:
 y y E T modq
 S 1 ≡ R 2 × (y1) × (y2) mod p (26)
 From (21), (22), (23) and (26) we have:
 v×y u×y x ×E ((x )−1×x )×(T modq)
 (x1) 1 ≡ (x1) 2 ×(x1) 1 ×(x1) 1 2 mod p or:
or:
 v×y modq u×y modq x ×Emodq (x )−1×x ×T modq
 (x1) 1 ≡ (x1) 2 × (x1) 1 × (x1) 1 2 mod p (27)
 From (27) we deduce:
 −1
 v × y1 ≡ (u × y2 + x1 × E + (x1) × x2 × T ) mod q (28)
 Besides, from (22), (23) and (24) we have:
 (v + u) mod q = k
 Deduct:
 (k − v) mod q = u (29)
 From (28) and (29) we have:
 −1 −1
 v = (k × y2 + x1 × E + (x1) × x2 × T ) × (y1 + y2) mod q (30)
 From (29) and (30), the first component of the signature can be calculated according
to (22):
 k−v
 R = (x1) mod p and
and from (30) the second component can be calculated according to (23):
 v
 S = (x1) mod p
 From here, the signing algorithm is described in Table 5 as follows:
14
 Journal of Science and Technique - Le Quy Don Technical University - No. 213 (12-2020)
 Table 5. Signing algorithm
 Input: p, q, x1, x2, y1, y2,M.
 Output: (R,S).
 [1]. E ← H(M)
 [2]. select k : 1 < k < q
 k
 [3]. T ← (x1) mod p
 −1 −1
 [4]. v ← (k × y2 + x1 × E + (x1) × x2 × T ) × (y1 + y2) mod q
 [5]. u ← (k − v) mod q
 u
 [6]. R ← (x1) mod p
 v
 [7]. S ← (x1) mod p
 [8]. return (R,S)
Note: M: message to sign, with: M ∈ {0, 1}∞;(R, S); signature of U on M.
 2.3.3. Verification algorithm:
 The verification algorithm of the new digital signature algorithm is supposed to be:
 y y E (R×Smodp)modq
 S 1 ≡ R 2 × (y1) × (y2) mod p
 Here, E is the representative value of the message to be validated: E = H(M). If M
and signature (R, S) satisfy the above equation, the signature is considered valid and
the message will be validated to its origin and integrity. Otherwise, the signature is
consider forged and the message is denied its origin and integrity. Therefore, if the left
side of the verification equation is calculated according to:
 A = Sy1 mod p (31)
and the right side of the verification equation is calculated according to:
 y E T¯
 B = R 2 × (y1) × (y2) mod p (32)
whereas T¯ = (R × S mod p) mod q (33)
 The condition for a valid signature is: A = B.
 Then, the verification algorithm of the new digital signature algorithm is described
in Table 6 as follows:
 Table 6. Verification algorithm
 Input: p, y1, y2, M,(R, S).
 Output: true / false.
 [1]. E ← H(M)
 [2]. A ← Sy1 mod p
 [3]. T¯ ← (R × S) mod p) mod q
 y2 E T¯
 [4]. B ← R × y1 × (y2) mod p
 [5]. if A = B then {return true}
 else {return false}
 15
Section on Information and Communication Technology (ICT) - No. 16 (12-2020)
 Note:
 - M,(R, S): message, signature to validate.
 - If the result is true, the integrity and origin of M are confirmed. Otherwise, if the
result is false M is denied for its origin and integrity.
 2.3.4. Correctness of the new algorithm:
 What to solve here is: Let p, q are two prime numbers with:
 ∗ (p−1)/q
 q|(p − 1),H : {0, 1} 7→ Zn, |q| ≤ |n| < |p|, 1 < α < p, x1 = α mod p,
 −1
 x1 (x1) ×x2modq
 1 < x2 < q, y1 = x1 mod p, y2 = (x1) mod p, E = H(M),
 k −1 −1
 1 < k < p, T = x1 mod p, v = (k × y2 + x1 × E + x1 × x2 × T ) × (y1 + y2) mod q,
 u v
 u = (k − v) mod q, R = x1 mod p, S = x1 mod p.
 ¯
 ¯ y1 y2 E T
 If T = (R × S mod p) mod q, A = S mod p, B = R × y1 × y2 mod p then A = B.
 The correctness of the new algorithm is proven as follows:
 From (23), (30) and (31) we have:
 y v×y v×y modq
 A = S 1 mod p = (x1) 1 mod p = (x1) 1 mod p
 (k×y +x ×E+(x )−1×x ×T )×(y +y )−1×y modq
 = (x1) 2 1 1 2 1 2 1 mod p (34)
 From (22), (23), (25) and (33) we have:
 u v
 T¯ = (R × S mod p) mod q = ((x1) × (x1) mod p) mod q
 (u+v)modq k
 = ((x1) mod p) mod q = ((x1) mod p)modq = T mod q (35)
 Replace (21), (22), (30) and (35) into (32) we have:
 y E T¯
 B = R 2 × (y1) × (y2) mod p
 u×y x ×E (x )−1×x ×(T modq)
 = (x1) 2 × (x1) 1 × (x1) 1 2 mod p
 u×y modq x ×Emodq (x )−1×x ×T modq
 = (x1) 2 × (x1) 1 × (x1) 1 2 mod p
 ((k−v)×y +x ×E+(x )−1×x ×T )modq
 = (x1) 2 1 1 2 mod p
 (k×y −v×y +x ×E+(x )−1×x ×T )modq
 = (x1) 2 2 1 1 2 mod p
 (k×y +x ×E+(x )−1×x ×T −y ×(k×y +x ×E+(x )−1×x ×T )×(y +y )−1)modq
 = (x1) 2 1 1 2 2 2 1 1 2 1 2 mod p
 (k×y +x ×E+(x )−1×x ×T )×(1−y ×(y +y )−1)modq
 = (x1) 2 1 1 2 2 1 2 mod p
 (k×y +x ×E+(x )−1×x ×T )×((y +y2)×(y +y )−1−y ×(y +y )−1modq
 = (x1) 2 1 1 2 1 1 2 2 1 2 mod p
 (k×y +x ×E+(x )−1×x ×T )×(y +y )−1×y modq
 = (x1) 2 1 1 2 1 2 1 mod p (36)
 From (34) and (36) deduce: A = B
 2.3.5. Security level of the new algorithm:
 The security level of the new algorithm can be evaluated through its ability to defend
16
 Journal of Science and Technique - Le Quy Don Technical University - No. 213 (12-2020)
against several types of attack such as:
 - Private key attack:
 There are two types of private key attacks: Attack on the key generation algorithm
and attack on the signing algorithm, perform a similar analysis to the 1-key scheme, it
shows that the private key attack against schemes constructed by this method is always
challenged with a difficult problem without solution currently.
 - Attack on the forged signature:
 The verification algorithm (Table 6) of the new algorithm algorithm shows a forged
signature (R, S) will be recognized as a valid signature of an M message if it met the
following condition:
 y y E (R×Smodp)modq
 (S) 1 ≡ (R) 2 × (y1) × (y2) mod p (37)
 From (37), if we choose R in advance and then calculate S, condition (37) will be:
 (S)y1 ≡ as mod p (38)
 Adversely, if we choose S in advance and then calculate R, condition (37) will be:
 (R)y2 ≡ bR mod p (39)
with a and b are constant, we can easily see that (38) and (39) are also difficult problems
without any solution currently [1], [3], [4], [5].
2.4. Some evaluation of the application efficiency of signature schemes constructed
based on the new method
 The effectiveness of the digital signature algorithm can be evaluated through the
cost of executing the signing algorithm, verification algorithm, and signature size that
the schema generates. In this section, the effectiveness of the new algorithm will be
evaluated and compared with the results in
 2.4.1. Signature size:
 It can be seen that with the same parameter set (p, q), the size of signatures generated
by the 2 schemes herein and those in [1], [3], [4], [5] are equivalent.
 2.4.2. Executing cost:
 Executing cost or computation cost of the signing and verification algorithms can be
evaluated by the number of computations to be performed or total computation time of
the signing and verification algorithms, the convention of the use of symbols as bellows:
 Texp: The execution time of the modular exponentiation.
 Th: The execution time of the hash function.
 Tmul: The execution time of the modulo multiplication.
 Tinv: The execution time of the modular inverse.
 17
Section on Information and Communication Technology (ICT) - No. 16 (12-2020)
 Attention:
 The key and parameter generation algorithm only needs to be executed once for all
signing objects. Therefore, the computation cost for the key and parameter generation
algorithm can be ignored when calculating the cost of performing the digital signature
algorithm.
 The executing cost for the signing algorithm (1) and verification algorithm (2) of
algorithms in [1], [3], [4], [5] and the 2 new algorithms are shown in Table 7 as
follows:
 Table 7. Executing cost for digital signature algorithms
 Texp Tmul Tinv Th
 (1) (2) (1) (2) (1) (2) (1) (2)
 Algorithm [1] 8 3 7 2 3 0 1 1
 Algorithm [2] 7 3 6 2 4 0 1 1
 Algorithm [3] 6 3 5 2 5 0 1 1
 Algorithm [4] 6 3 4 2 4 0 1 1
 Algorithm with 1-key scheme 3 3 3 2 1 0 1 1
 Algorithm with 2-key scheme 3 4 5 3 2 0 1 1
 Note:
 - The Algorithms [1], [3], [4] are signature algorithms proposed in [1], [3] and [4].
 - The Algorithm [2] is a signature algorithm proposed in "C. Constructing digital
signature schema based on the difficulty of solving expanded root problem" in [2].
 - The Algorithm with 1-key and 2-key scheme is 2 signature algorithms constructed
based on the newly proposed method here.
 Remark:
 Results in Table 3.1 shows that amount/duration to perform the calculations of the
two algorithms constructed according to the new method is lower than those on the
algorithms in [1], [3], [4], [5], thereby showing that the application efficiency of these
algorithms is higher than those on the earlier proposed algorithms.
3. Conclusion
 In this paper, the authors proposed a method to construct digital signature algorithms
based on new key schemes to improve the security of the algorithms. The security of
the algorithms constructed in this method is always guaranteed by difficult problems
without a solution currently. Besides, the issue of improving efficiency for signature
algorithms constructed by the proposed method in [1], [3], [4], [5] is also solved to
meet the requirements of application algorithms in practice.
18
 Journal of Science and Technique - Le Quy Don Technical University - No. 213 (12-2020)
References
[1] Luu Hong Dung, Tong Minh Duc, and 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. In Fundamental and
 Applied IT Research Conference, pages 1–9, 2018.
[2] Dung Luu Hong et al. A new construction method of digital signature algorithms. International Journal of
 Computer Science and Network Security (IJCSNS), 16(12):53, 2016.
[3] Dung Luu Hong et al. A new digital signature scheme based on the hardness of some expanded root problems.
 Procedia Computer Science, 171:541–550, 2020.
[4] Luu Xuan Van and Luu Hong Dung. Constructing a digital signature algorithm based on the difficulty of some
 expanded root problems. In 2019 6th NAFOSTED Conference on Information and Computer Science (NICS),
 pages 190–195. IEEE, 2019.
[5] Luu Xuan Van, Luu Hong Dung, and Doan Van Hoa. Developing root problem aims to create a secure digital
 signature scheme in data transfer. In 2020 International Conference on Green and Human Information Technology
 (ICGHIT), pages 25–30. IEEE, 2020.
 Manuscript received: 15-07-2020; Accepted: 30-10-2020
 
 Nguyen Duc Thuy Graduated in Information Technology University of Foreign Languages;
 Informatics University of Ho Chi Minh City in 2005, Master degree from Academy of Eco-
 nomics and Business in 2013; Currently working in the Faculty of Information Technology -
 Ho Chi Minh City Technical and Economic College; Research field: information security.
 Bui The Truyen graduated from Le Quy Don Technical University in 2000. He received a
 doctor’s degree in analysis and information processing at Moscow Aviation Institute, Russia
 in 2008. Currently a lecturer at the Le Quy Don Technical University. His research interests
 are virtual reality simulation and information security. E-mail: truyenbuithe@lqdtu.edu.vn
 Tong Minh Duc graduated from Le Quy Don Technical University in 2000. Received a
 doctorate from University of Electrical Engineering - Russia in 2007. Currently a lecturer at the
 Faculty of Information Technology - Le Quy Don Technical University. Research field: Image
 processing, object identification, information security safety. E-mail: ducmta@gmail.com
 19
Section on Information and Communication Technology (ICT) - No. 16 (12-2020)
 Luu Hong Dung graduated in Electronics and Communications from Le Quy Don Technical
 University in 1989, PhD at Le Quy Don Technical University in 2013; Currently working in
 the IT department - Le Quy Don Technical University; Research direction: Cryptography and
 information security. E-mail: luuhongdung@gmail.com
 XÂY DỰNG THUẬT TOÁN KÝ SỐ DỰA TRÊN
 CÁC SƠ ĐỒ KHÓA MỚI
 Tóm tắt
 Bài báo đề xuất một phương pháp xây dựng các thuật toán chữ ký số dựa trên các sơ
 đồ khóa mới. Các sơ đồ khóa mới được sử dụng ở đây thực chất là một dạng bài toán khó
 mà hiện tại còn chưa có cách giải. Phương pháp xây dựng thuật toán với các sơ đồ tạo khóa
 mới như thế được đề xuất nhằm mục đích nâng cao mức độ an toàn cho các thuật toán chữ
 ký số. Phương pháp mới đề xuất ở đây được trình bày thông qua việc xây dựng 2 thuật toán
 chữ ký số cụ thể, song hoàn toàn có thể tạo ra một lớp thuật toán chữ ký có độ an toàn cao
 cũng bằng chính phương pháp này.
20