A Design Method of Digital Signature Scheme Based on Discrete Logarithm Problem
214
IJCSNS International Journal of Computer Science and Network Security, VOL.17 No.2, February 2017
A Design Method of Digital Signature Scheme Based on Discrete
Logarithm Problem
Thuy Nguyen Đuc †, Giang Nguyen Tien ††, Son Le Dinh†††, Dung Luu Hong †††
† Ho Chi Minh City Technical and Economic College, Vietnam
†† Information Technology Department, Department of Defense
††† Military Technical Academy, Vietnam
Abstract
DLP(g,p): For each positive integer y ∈ ℤp*, find x
This paper proposes a design method of digital signature scheme
based on the difficulty of the discrete logarithm problem. With
the proposed method, we can develop a lot of other digital
signature schemes to choose suitable for practical applications.
Key words:
satisfying the following equation:
g x mod p = y
(1.1)
The algorithm for the discrete logarithm problem with the
public parameters {p,g} written as an algorithm for
calculating DLP(g,p)(.) with the input variable y and the
value function is the root x of equation (1.1):
x = DLP( p,g) (y)
Digital signature; Digital signature algorithm; Discrete
logarithm problem.
1. Problem Posing
In an electronic trading system, digital authentication
application to authenticate the origin and integrity of
information for the data message, the problem DLP(g,p) is
difficult in the sense that it cannot be done in real time.
There, each member U of the system selects secret key x
at will satisfying: 1< x < (p-1), calculate and disclose
parameters:
In 1985, T. ElGamal [l] proposed the digital signature
scheme based on the discrete logarithm problem. Then, in
1989, C.P. Schnorr [2] proposed an efficient signature
scheme to shorten the length of the signature and to speed
up the signature generation/verification process, and in
1991, the NIST (National Institute of Standards and
Technology) proposed the Digital Signature Algorithm
(DSA) [3] for the digital signature standard based on
ElGamal and Schnorr signature schemes. Currently, the
digital signature has been widely applied in e-government,
e-commerce ... in the world and initially deployed in
Vietnam. Therefore, it is required to be set out the digital
signature scheme research - development to design -
manufacture new products, safe equipment and
information security in countries such as Vietnam. This
paper proposes a construction method of digital signature
scheme based on the difficulty of the discrete logarithm
problem by generalizing ElGamal and Schnorr’s method,
and some digital signature schemes have been developed
based on this method.
y = gx mod p
(1.2)
Note:
(i) DLP(g,p) is difficult in the sense that it cannot be
*
done in real time, but not difficult with ever y ∈ ℤp at
y = g x mod p
all, DLP(g,p), for example, the
with x is
not large enough, by browsing gradually x = 1, 2, ...
until finding root of (1.2) we will find the secret key x,
so the value of the secret key x must be selected so that
the calculation DLP(g,p)(y) is difficult.
(ii) Such choice of x means that no one other than U
knows the value of x, so knowing x is enough to verify
that it is U.
Currently, the problem is still considered to be difficult
since no polynomial time algorithm for it is found and
ElGamal cryptosystem [1] is an actual proof for the
difficult solution of the problem.
2. Construction of digital signature scheme
based on discrete logarithm problem.
2.1 Discrete logarithm problem
2.2 Construct generalized scheme
Generalized scheme is used to develop digital signature
scheme for practical applications. Generalized scheme
proposed here is constructed basing on difficult solution of
discrete logarithm problem and is designed as a signature
generation scheme with 2 components similar to DSA in
Let p be a prime number and g is a generating element of
ℤp* group. Then the discrete logarithm problem – DLP
(Discrete Logarithm Problem) on the ℤp*, also known as
the problem DLP(g,p) is stated as follow:
Manuscript received February 5, 2017
Manuscript revised February 20, 2017
IJCSNS International Journal of Computer Science and Network Security, VOL.17 No.2, February 2017
215
America Digital Signature Standard (DSS) [3] or
R34.10-94 GOST of Russian Federation [4], including
methods of forming parameters, methods of forming and
checking signature shown below.
Method of verifying signature
Input data: p, q, g, y, M, (e, s).
Results: Assert (e, s) is the valid signature ((e,s) = true) or
(e,s) is false and/or M is no longer intact ((e, s) = false).
Method of initialization-generating parameters and keys
Steps:
Input data: p, q, and x.
Results: g, y, H (.).
Steps:
1. Calculate the value u:
(
(
M ,e
)
. f3
(
M ,e
)
u = gs. f
) × y f
mod p
(
M ,e
2
2
, if s is
(2.7)
calculated according to (2.4)
*
1. Calculate generating elements of ℤp :
or:
g = h( p−1) / q mod p
, with:
1< h < p
) × ys. f
(
M ,e
M ,e
)
u = gs. f
2
3
, if s is
mod p
y = g±x mod p
2. Calculate public key:
(2.1)
with:
calculated according to (2.5)
(2.8)
, if
0,1 ∗
→ Zq
}
or:
3. Select hash function H:
,
{
−1. f3
(
M ,e
)
−1
× g f
mod p
(
M ,e
)
(
M ,e
)
u = ys. f
.
q < p
2
2
s
is
calculated
according
to
(2.6)
Remarks:
(2.9)
(i) p, q: 2 prime numbers satisfy q | (p-1).
(ii) x: secret key of signing object satisfy:
2. Calculate the value v:
v = f1(M ,u)modq
3. Check if: v = e, then:
.
1< x < q
(2.10)
(2.11)
Method of signing messages
Input data: p, q, g, x, M.
Results: (e, s).
(e,s) = true, otherwise: (e,s) = false.
The correctness of the generalized scheme
Steps:
That need proving here is: if parameters and key are
formed under (2.1), digital signature is formed according
to the formula from (2.2) to (2.6), while checking digital
signature shall be implemented from (2.7) to (2.10), the
condition indicated by (2.11) will be satisfied.
Proposition 1.1:
1. Select value k satisfying:
by the formula:
. Calculate value r
1 < k < q
(2.2)
2. The first component e of digital signature is selected
in one of two forms:
Let p and q be two prime numbers with q is a divisor of
(p-1),
h
is
a
positive integer less than
p
and
,
g = h( p−1) / q mod p
r = gk mod p
y = g−x mod p
(2.3)
,
.
If:
1 < x,k < q
3. The second component s of digital signature is formed by
,
,
,
e = f1 (M ,r)modq
one of following forms:
s = [k. f2 (M,e)−1 + x. f3 (M,e)]mod q
u = gs. f (M ,e) × y f (M ,e). f (M ,e) mod p
2
2
3
,
(2.4)
then:
.
v = e
v = f1(M ,u)modq
or:
or:
(2.5)
(2.6)
Proof:
Indeed, we have:
Remarks:
(i) M: data messages for signing.
(ii) (e, s): signature on M of the object holding {x, y}.
(iii) : as a function of M and e.
(2.12)
f1(M ,e), f2 (M ,e), f3 (M ,e)
216
IJCSNS International Journal of Computer Science and Network Security, VOL.17 No.2, February 2017
−1
u = ys. f
× g− f
(M ,e) mod p
(
M ,e
)
(M ,e)
−1. f3
2
From (2.2) and (2.12) we have: u = r.
Therefore:
2
) mod p
(
M ,e
)
−1.x−1
.
(
k. f2
(
M ,e
)+ f3
(
M ,e
(
f2 (M ,e) (M ,e)
−1. f3
= g x. f
)) × g.−
2
(
f2
(
M ,e
)
−1. f3
(
M ,e
)
)
.−
(
f2 (M ,e
) (M ,e)
−1. f3
= gk+
) mod p
(2.13)
= gk mod p
(2.16)
From (2.3) and (2.13) we infer: v = e.
Things are proved.
From (2.2) and (2.16) we have: u = r.
Therefore:
Proposition 1.2:
Let p and q be two prime numbers with q is a divisor of
(2.17)
(p-1),
h
is
a
positive integer less than
p
and
,
y = gx mod p
g = h( p−1/ q mod p
From (2.3) and (2.17) we infer: v = e.
Things are proved.
,
.
If:
1< x,k < q
r = gk mod p
s = k.[ f2 (M ,e) + x. f3 (M ,e)]−1 mod q
u = gs. f (M ,e) × ys. f
,
,
,
e = f1(M , r) mod q
2.3 Some digital signature schemes developed from
the generalized form
3 (M ,e)
2
,
then:
mod p v = f1(M,u)modq
.
v = e
2.3.1 The scheme LD 16.12 – 01
Proof:
Scheme LD 16.12 – 01 was developed from the
generalized scheme with (2.4) and (2.7), selections:
Indeed, we have:
f3 (M ,e) = H(M )
f1 (M, r) = r modq
f2 (M,e) = e
,
and
,
u = gs. f (M ,e) × ys. f (M ,e) mod p
2
3
where H (.) is a hash function and H (M) is the
representative value of the signed message M. The public
y = g−x mod p
(
M ,e
)
.k.
(
f2
(
M ,e
)
+x. f3
(
M ,e))−1
(
M ,e
)
.k.
(
f2
(
M ,e
)
+x. f3
(
M ,e))−1
= g f
× g x. f
mod p
2
3
(
f2
(
M ,e
)
+x. f3
(
M ,e))
.
(
f2
(
M ,e
)
+x. f3
(
M ,e))−1
= gk.
mod p
key is calculated by using the formula:
. The
proposed new signature scheme consists of two
algorithms: (a) signing messages, and (b) verifying
signature - are described in Table 1.1 and Table 1.2 below.
The algorithm initialization – generating parameters and
keys similar to Generalized scheme.
= gk mod p
(2.14)
(2.15)
From (2.2) and (2.14) we have: u = r.
Therefore:
a) Algorithm for signing messages
v = f1(M ,u)modq = f1(M,r)modq
From (2.3) and (2.15) we infer: v = e.
Table 1.1. Algorithm for signing messages
Input: p, q, g, x, M.
Output: (e, s).
Things are proved.
[1]. select k:
1< k < q
r ← gk mod p
e ← r modq
s ← [k ×e−1 + x× H(M )]modq
Proposition 1.3:
[2].
[3].
[4].
(3.1)
(3.2)
(3.3)
Let p and q be two prime numbers with q is a divisor of
(p-1), is positive integer less than and
h
a
p
1< x,k < q
y = gx mod p
g = h( p−1/ q mod p
r = gk mod p
[5]. return (e, s)
,
.
If:
,
,
,
Notes:
e = f1(M , r) mod q
,
s = x−1.[k. f2 (M,e) + f3 (M,e)]mod q
(i) U: signing object possesses the secret key x.
(ii) M: Message signed by the object U.
(iii) (e, s): the signature of U on M.
b) Algorithm for verifying signature
−1
× g− f
) mod p
v = f1(M,u)modq
(
M ,e
)
(M ,e) (M ,e
−1. f3
u = ys. f
2
2
,
then: v=e.
Proof:
Indeed, we have:
Table 1.2. Algorithm for verifying signature
Input: p, q, g, y, M, (e, s).
Output: (e, s) = true / false .
u ← gs.e × ye.H (M ) mod p
[1].
(3.4)
IJCSNS International Journal of Computer Science and Network Security, VOL.17 No.2, February 2017
217
[2].
[3]. if (
(3.5)
The algorithm initialization-generating parameters and
keys similar to Generalized scheme.
v ← u modq
) then {return true }
else {return false }
v = e
a) Algorithm for signing messages
Table 3.1. Algorithm for signing messages
Input: p, q, g, x, M.
Output: (e, s).
c) The correctness of the scheme LD 16.12 – 01
f3(M,e) = H(M )
f1 (M, r) = r modq
f2 (M ,e) = e
Set:
,
and
.
[1]. select k:
1< k < q
By (3.1), (3.2), (3.3), (3.4), (3.5v) a=ndePr.oposition 1.1, it is
r ← gk mod p
e ← H(M || r)modq
s ← x−1 ×
k + e mod q
[2].
[3].
[4].
(6.1)
(6.2)
(6.3)
easy to get things proved here:
2.3.2 The scheme LD 16.12 – 02
(
)
[5]. return (e, s)
Scheme LD 16.12 – 02 was developed from the
generalized scheme with (2.5) and (2.8), selections:
b) Algorithm for verifying signature
f3(M,e) = H(M )
f1 (M, r) = r modq
f2 (M ,e) = e
,
,
, the
Table 3.2. Algorithm for verifying signature
Input: p, q, g, y, M, (e, s).
Output: (e, s) = true / false .
public key is calculated by using the formula:
y = g x mod p
. The algorithms: (a) signing messages, and
u ← g−e × ys mod p
v ← H(M || u) mod q
[1].
(6.4)
(6.5)
(b) verifying signature are described in Table 2.1 and
Table 2.2 below. The algorithm initialization-generating
parameters and keys similar to Generalized scheme.
[2].
[3]. if ( v = e ) Then {return true }
else {return false }
a) Algorithm for signing messages
c) The correctness of the scheme LD 2.02
Table 2.1. Algorithm for signing messages
Input: p, q, g, x, M.
Output: (e, s) - the signature of U on M.
f2 (M ,e) =1
f1 (M ,r) = H(M || r)modq
f3 (M,e) = e
Set:
,
and
. By (6.1), (6.2), (6.3) (6.4), (6.5) and
Proposition 1.3, we have: v=e. Things are proved.
[1]. select k:
1< k < q
r ← gk mod p
[2].
(5.1)
(5.2)
(5.3)
2.4 The safety level of the proposed schemes
[3].
[4].
e ← r modq
s ← k ×[e + x× H(M )]−1 modq
The safety level of digital signature scheme is generally
assessed through following capabilities:
a) Prevent attacks which reveal the secret key
[5]. return (e, s)
b) Algorithm for verifying signature
In the proposed new schema, the public key of signer is
formed from the secret key corresponding to:
Table 2.2. Algorithm for verifying signature
Input: p, q, g, y, M, (e, s)
y = g±x mod p
Output: (e, s) = true / false .
. Thus, the ability of attack prevention of
this scheme depends on the difficulty solution of the
u ← ys.H (M ) × gs.e mod p
[1].
(5.4)
(5.5)
[2].
v ← u modq
discrete logarithm problem DLP(p,q)
.
[3]. if (
) Then {return true }
else {return false }
v = e
b) Anti – phishing signature
Verifying algorithm of the proposed new schema show
that a fake pair (e,s) will be recognized as valid digital
signature for a message M if it satisfies conditions shown
in Table 5 as follows:
c) The correctness of the scheme LD 16.12 – 02
f3 (M ,e) = H(M )
f1 (M, r) = r modq
f2 (M ,e) = e
Set:
,
,
. By
(5.1), (5.2), (5.3), (5.4), (5.5) and Proposition 1.2, we
have: v=e. Things are proved.
Table 5.
2.3.4 The scheme LD 16.12 – 03
Conditions for (e,s) to be the
valid signature for the message M
Scheme
Scheme LD 16.12 – 03 was developed from the
generalized scheme with (2.6) and (2.9), selections:
LD 16.12 – 01
LD 16.12 – 02
LD 16.12 – 03
e =
u =
gs.e × ye.H (M ) mod p
mod q
ys.H (M ) × gs.e mod p
mod q
f3 (M,e) = e
f1 (M ,r) = H(M || r)modq
f2 (M ,e) =1
,
and
, the
ys × g−e mod pmod q
x
e = H
M ||
public key is calculated by using the formula: y = g
The algorithms: (a) signing messages, and (b) verifying
signature are described in Table 3.1 and Table 3.2 below.
.
mod p
The nature of finding the (e,s) satisfying the conditions
shown in Table 5 is solving the discrete logarithm problem
DLP(p,q)
.
218
IJCSNS International Journal of Computer Science and Network Security, VOL.17 No.2, February 2017
Giang N.T graduated from Military
Technical Academy. He works at
Information Technology Department,
Department of Defense. His research is
information security.
3. Conclusion
This paper proposes the design method of digital signature
scheme based on the discrete logarithm problem by
developing a generalized schema, thereby developing
some schemes that can be applied in practice. The safety
level of the new proposed schema is evaluated by the
difficulty level of the discrete logarithm problem.
However, the schemes should be carefully evaluated in
terms of the safety level as well as effective
implementation to be applied in practice.
References
[1] T. ElGamal, “A public key cryptosystem and a signature scheme
based on discrete logarithms“, IEEE Transactions on Information
Theory, Vol. IT-31, No. 4, pp. 469 – 472, 1985.
[2] Schnorr, C.P., “Efficient identification and signatures for smart
cards”. Advances in cryptology - CRYFTO ’89, August 2&24,
1989, Santa Barbara, pp. 239-252, (Springer-Verlag)
[3] National Institute of Standards and Technology, NIST FIPS PUB
186-3. Digital Signature Standard, US Department of Commerce,
1994.
[4] GOST R 34.10-94. Standard Russian Federation. Information
Technology. Cryptographic Data Security. Produce and check
Procedures of Electronic Digital Signature based on Asymmetric
Cryptographic Algorithm. Government Committee of the Russia for
Standards, 1994 (in Russian).
Thuy N.D received the B.S from HUFLIT
University in 2005 and M.S degree from
Faculty of Information Technology,
Military Technical Academy in 2013. My
research interests include cryptography,
communication and network security.
Dung L.H is a lecture at the Military
Technical Academy (Ha Noi, Viet Nam).
He received the Electronics Engineer
degree (1989) and Ph.D (2013) from
Military Technical Academy.
Son L.D is a lecture at the Military
Technical Academy (Ha Noi, Viet Nam).
He received the Information Technology
engineer degree (2001) from Military
Technical Academy and Ph.D (2007) from
Saint
Petersburg
Electrotechnical
University "LETI", St. Petersburg, Russia.
5 trang
22520
Free
Bạn đang xem tài liệu "A Design Method of Digital Signature Scheme Based on Discrete Logarithm Problem", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- adesign_method_of_digital_signature_scheme_based_on_discrete.pdf
