A New Construction Method of Digital Signature Algorithms
IJCSNS International Journal of Computer Science and Network Security, VOL.16 No.12, December 2016
53
A New Construction Method of Digital Signature Algorithms
Thuy Nguyen Đuc† and Dung Luu Hong††
† Faculty of Information Technology, Ho Chi Minh City Technical and Economic College
†† Faculty of Information Technology, Military Technical Academy
Here, the discrete logarithm problem is used as a one-way
function in formation of the key of entities in the same
system with the common parameter set {p,g}. It is easy to
see that, if x is a secret parameter, calculation of the public
parameter y from x and systematic parameters {p,g} is
absolutely easy. However, the opposite is very difficult to
implement, ie from y and {p,g}, the calculation of the
secret parameter x is unfeasible in practical applications. It
should be noted that, according to [6] and [7] in order for
discrete logarithm problem to be difficult, p selected must
Summary
The article presents a new construction method of digital
signature algorithms based on difficulty of the discrete logarithm
problem. From the proposed method, the different signature
schemes can be deployed to choose suitably for applications in
practice.
Key words:
Digital signature; Digital signature algorithm; Discrete
logarithm problem.
be large enough with:
|p| ≥512 bit.
1. Problem
Algorithm for the problem DLP(g,p) can be written as a
function calculating algorithm DLP(g,p)(.) with the input
variable y and function value is the root x of the equation:
Currently, the digital signature has been widely applied to
the fields of e-Government, e-Commerce, ... in the world
and has been initially deployed applications in Vietnam to
meet the authentication requirements for the origin and the
integrity of information in electronic transactions.
However, the initiative research - development of new
digital signature schemes to meet the requirements for
product, safety equipment design - manufacture and
information security in the country has always been
essential problem arising. In the country, a number of
research results in this field have been published [1], [2],
[3], [4] and implemented in practical applications.
In this article, the authors propose a new construction
method of signature schemes based on difficulty of the
discrete logarithm problem in the field of finite elements.
As well as methods that have been proposed in [1], [2], [3],
[4], an advantages of the newly proposed method here is
that it can be used for the purpose of developing different
digital signature schemes to choose suitably to the
requirements of applications in practice.
x = DLP(g, p) (y)
This signature scheme built up based on the newly
proposed method allows entities signing in the same
system to share the parameter set {g,p}, where each
member U of the system chooses oneself the secret key x
1< x < ( p −1)
satisfying:
parameter:
, calculate and disclosure the
y = g x mod p
It also should be noted that the secret parameter x must be
chosen so that the calculation of DLP(g,p) (y) is difficult.
With the above stated choice, only the signer U knows the
value of x, so the person who knows x is enough to
authenticate is U.
Assuming that the secret key of the signer x is randomized
in the range (1,p) and the corresponding public key y is
formed from x in accordance with:
y = g x mod p
(1.1)
Here, p is the chosen prime number so that solution of the
problem DLP(g,p) (y) is difficult, g is the birth particle
of the group ℤp* has the degree of q, with q|(p-1).
Assume that (r,s) is the signature on the message M, u is
one value in the range (1,q) and r is calculated from u by
the formula:
2. Construction of digital signature algorithm
2.1 Construction method
This newly proposed sheme is built up based on difficulty
r = gu mod p
(1.2)
of the Discrete Logarithm Problem [5].
Discrete
And s calculated from v by the formula:
logarithm problem – DLP(g,p) can be stated as follows:
Let p be prime number, r is the birth particle of the group
ℤp*. For each positive integer y∈ ℤp*, find x satisfying
the equation:
s = gv mod p
(1.3)
Here: v is also one value in the range (1,q).
Also assume that the verifying equation of the scheme is
formed:
g x mod p = y
Manuscript received December 5, 2016
Manuscript revised December 20, 2016
54
IJCSNS International Journal of Computer Science and Network Security, VOL.16 No.12, December 2016
Table 1. Algorithm for formation parameter and key
s f
≡ r f
)) × y
)) mod p
f 3
(
M , f r,s
(
(
M , f
(
r,s))
(
M , f r,s
(
1
2
Input: p, q, x.
Output: g, y.
f (r, s)
[1]. select h: 1<h<p
With
is the function of r and s. Consider the case:
g ← h( / q mod p
p−1
)
f (r,s) = r × smod p
= gk mod p
[2].
[3]. if ( g = 1) then go to [1]
(1.4)
y ← gx mod p
Where k is a randomly chosen value in the range (1,q).
Set:
[4].
[5]. return {g,y}
gk mod p = Z
(1.5)
Remarks:
Then, the verifying equation can be taken to the form:
(i) p,q: primes satisfying conditions:
f3 M ,Z
(
s f
≡ r f
) × y
) mod p
(
M ,Z
)
(
M ,Z
2
1
p = N × q +1
, N=1,2,3,….
(1.6)
(ii) x,y: secret, public keys of signing object U.
From (1.1), (1.2), (1.3) and (1.6) we have:
) mod p
x. f3 (M ,Z
) × g
(
M ,Z
)
(M ,Z
2
gv. f
≡ gu. f
1
(1.7)
Table 2. Algorithm for formation of signature
Input: p, q, g, x, M.
Output: (r,s).
From (1.7) infer:
v× f1 (M,Z) ≡ [u × f2 (M,Z) +
+ x× f3 (M ,Z)]modq
[1]. select k: 1<k<q
(1.8)
(1.9)
Z ← gk mod p
So:
[2].
v = (u× f1(M ,Z)−1 × f2 (M ,Z)
w ← f1(M, Z)
1
[3].
+ x× f1(M ,Z)−1 × f3 (M,Z)modq
w2 ← f2 (M , Z)
[4].
On the other hand, from (1.2), (1.3) and (1.4) we have:
w3 ← f3 (M , Z)
[5].
(
v + u mod q = k
)
(1.10)
w4 ←
w5 ←
w1
)
)
−1 × w2 modq
−1 × w3 modq
From (1.9) and (1.10) we have:
[6].
[u × f1(M, Z)−1 × f2 (M, Z) +
(
w1
[7].
[8].
+ x × f1(M, Z)−1 × f3 (M, Z) + u]mod q
u ←
(
w4 +1 −1
×
(
k − x× w5 mod q
)
r ← gu mod p
v ← u × w4 + x× w5
s ← gv mod p
= k
[9].
Or:
(
)
modq
[u × ( f1(M, Z)−1 × f2 (M, Z) +1)
+ x × f1(M, Z)−1 × f3 (M, Z)]mod q
[10].
[11].
[12]. return (r,s)
Remarks:
= k
From (1.11), infer:
(1.11)
M ∈{0,1}∞
u = [( f1(M, Z)−1 × f2 (M, Z) +1)−1 ×
(k − x × f1(M, Z)−1 × f3 (M, Z)]mod q
(i) M: the message to be signed, with:
(ii) (r,s): signature of U on M.
.
(1.12)
Table 3. Algorithm for verifying signature
Input: p, q, g, y, {M,(r,s)}.
Output: true / false.
From (1.12), the first component of signature is calculated
by (1.2):
r = gu mod p
Z ← f (r, s)
[1].
w1 ← f1 (M , Z)
and the second component is calculated by (1.3):
[2].
s = gv mod p
w2 ← f2 (M , Z)
[3].
with v calculated by (1.9):
w3 ← f3 (M , Z)
[4].
v = [u × f1(M, Z)−1 × f2 (M, Z) +
+ x × f1(M, Z)−1 × f3 (M, Z)]mod q
A ← sw mod p
1
[5].
w3
B ← rw × y mod p
2
[6].
[7]. if (A=B) then {return true}
else {return false}
Remarks:
(i) M, (r,s): the messages, signature need verifying.
From here, a form of signature scheme corresponding to
f (r, s) = r × s mod p = gk mod p
the case:
is shown as
Table 1, Table 2 and Table 3 below.
IJCSNS International Journal of Computer Science and Network Security, VOL.16 No.12, December 2016
55
(ii) If the return is true, the integrity and origin of M are
confirmed. Conversely, if the return is false, M is denied
the origin and integrity.
2.2 Several algorithms for signature built up under
the proposed method
It should be noted that the signature created here is not
necessarily the pair of (r,s). From the Table 2 shows that
the value v can be selected as the second component of the
signature instead of s, thus reduce one calculation step in
the procedure for formation of signature. Indeed, if the
hypothesis of the verifying equation of the scheme is
formed:
2.2.1 The first scheme
a) Structure and operation
The first signature scheme proposed here - symbols LD
16.9–01, is built up under Table 1, 2 and 3 in section A
f1(M ,Z) = H(M )
f2 (M, Z) = Z
with selections:
,
,
f3 (M,Z) = H(M )
f 3 M , f r,v
( (
)) mod p
(
M , f
(
r,v))
(
M , f
(
r,v
. Algorithms for formation of parameter
gv. f
≡ r f
)) × y
1
2
(1.13)
and key, algorithm for signature and verifying signature of
the scheme are described in the Table 6, Table 7 and Table
8 below.
and:
f (r,v) = r × gv mod p = gk mod p
(1.14)
Set:
gk mod p = Z
Table 6. Algorithm for formation of parameter and key
Input: p, q, x.
Output: g, y, H(.).
Then, from (1.1), (1.2) and (1.13) we also have:
x. f3 (M , f (r,v
gv. f
≡ gu. f
)) × g
)) mod p
(
M , f
(
r,v))
(M , f (r,v
1
2
[1]. select h: 1<h<p
p−1
)
From here, algorithms for formation and verifying
signature of the form of the scheme corresponding to new
assumptions given in Table 4 and Table 5 as follows:
g ← h( / q mod p
[2].
[3]. if ( g = 1) then goto [1]
y ← gx mod p
[4]
.
(2.1)
H :
{
0,1 ∗
Zn
}
Table 4. Algorithm for formation of signature
Input: p, q, g, x, M.
Output: (r,v).
q < n < p
[5]. select
,
[6]. return {g,y,H(.)}
Remarks:
[1]. select k: 1<k<q
Z ← gk mod p
- H(.): Hash function (SHA, MD5, ...).
[2].
w ← f1(M, Z)
Table 7. Algorithm for signing messages
Input: p, q, g, H(.), x, M .
Output: (r,s).
1
[3].
w2 ← f2 (M , Z)
[4].
w3 ← f3 (M , Z)
E = H(M )
[5].
[1].
[2]. select k: 1<k<q
w4 ←
(
(
w1
w1
w4 +1 −1
r ← gu mod p
)
)
−1 × w2 modq
−1 × w3 modq
k − x× w5
[6].
[7].
Z ← gk mod p
[3]
(2.2)
w5 ←
u ←
r ← gu mod p
E−1 × Z +1 −1
×
(
k − x modq
)
[4].
[5].
[6].
u ←
(
)
×
(
)
mod q
[8].
(2.3)
(2.4)
u × E−1 × Z + x
modq
[9].
v ←
s ← gv mod p
v ←
(
u × w4 + x× w5 modq
)
[10].
[7].
(2.5)
[11]. return (r,v)
[8]. return (r,s)
Table 5. Algorithm for verifying signature
Input: p, q, g, y, {M,(r,v)}.
Output: true / false.
Table 8. Algorithm for verifying signature
Input: p, q, g, H(.), y, M, (r,s).
Output: true / false.
Z ← f (r,v)
[1].
E = H(M )
A ← sE mod p
[1].
w1 ← f1 (M , Z)
[2].
[2].
[3].
(2.6)
(2.7)
w2 ← f2 (M , Z)
[3].
w ← r × s mod p
B ← rw × yE mod p
w3 ← f3 (M , Z)
[4].
[4].
(2.8)
A ← gv.w mod p
1
[5].
A = B
[5]. if (
)
then {return true }
w3
B ← rw × y mod p
2
else {return false }
[6].
b) Correctness of the scheme LD 16.9-01
if ( A = B )
[7].
then {return true }
else {return false }
The thing to be proved is: Let p, q are 2 primes with
H :
{
0,1 ∗
Zn
}
q < n < p
1< k, x < q
,
q|(p-1),
,
,
56
IJCSNS International Journal of Computer Science and Network Security, VOL.16 No.12, December 2016
2.2.1 The second scheme
y = g x mod p
Z = gk mod p
r = gu mod p
E = H
modq
. If:
(
M
)
,
,
,
u =
s =
E−1 × Z +1 −1
u × E−1 × Z + x
×
(
k − x
)
,
,
,
a) Structure and operation
modq
A = sE mod p
The second signature scheme - symbols LD 16.9–02, is
built up under the method stated in Table 4 and 5 in
section A with selections: f1(M,Z) = Z, f2(M,Z) = H(M),
f3(M,Z) = H(M). The algorithm for formation of
parameter and key is similar to that in the scheme LD
w = r × s mod p
,
B = rw × yE mod p
A = B
then:
.
Correctness of the newly proposed scheme is proved as
follows:
From (2.4), (2.5) and (2.6) we have:
16.9–01 (Table 6),
verifying signature of the scheme are described in Table 8
and Table 10 below.
algorithms for signature and
A = sE mod p
= gv.E mod p
−1.Z+x
)
.E
= g(u.E
mod p
Table 9. Algorithm for signing messages
Input: p, q, g, H(.), x, M .
Output: (r,v).
= gu.Z+x.E mod p
(2.9)
From (2.1), (2.3), (2.7) and (2.8) we also have:
[1]. select k: 1<k<q
B = rw × yE mod p
Z ← gk mod p
[2].
[3].
[4].
(3.1)
(3.2)
(3.3)
= gu.
) × g x.E mod p
= gu.Z × g x.E mod p
= gu.Z+x.E
(
r.s mod p
E = H(M )
w1 = Z −1 × E mod q
(2.10)
u ←
r ← gu mod p
w1 +1 −1
×
k − x× w1 modq
[5].
(3.4)
From (2.9) and (2.10) infer the thing to be proved:
[6].
[7].
(3.5)
(3.6)
A = B
v ← w1 ×
(
u + x modq
)
Safety level of the scheme LD 16.9-01
[8]. return (r,v)
In form of the newly proposed scheme, the public key is
formed from the secret key based on difficulty of the
discrete logarithm problem DLP(g,p). Therefore, if the
parameters {p,q,g} is selected for the problem DLP(g,p) to
be difficult, the safety level of the newly proposed scheme
in terms of resistance to attacks disclosing secret key will
be assessed by the level of difficulty of the problem
DLP(g,p). It should be noted that, in order for DLP(g,p) to
be difficult, the parameters {p,q,g,n} can be selected
similarly to DSA [6] or GOST R34.10-94 [7], with:
Table 10. Algorithm for verifying signature
Input: p, q, g, H(.), y, M, (r,v).
Output: true / false.
[1]. E = H(M)
w2 ← r × gv mod p
A ← gv.w mod p
[2].
[2].
(3.7)
(3.8)
(3.9)
2
B ←
(
r × y
)
E mod p
[3].
A = B
[4]. if (
)
then {return true }
| n |≥160bit
| p |≥ 512bit | q |≥160bit
,
,
.
else {return false }
The Algorithm for verifying signature (Table 8) of the
scheme LD 16.9-01 shows, any pair of (r,s) will be
recognized as a valid signature of U on a message M if it
b) Correctness of the scheme LD 16.9-02
The thing to be proved is: Let p, q are 2 primes with
meets the condition:
0,1 ∗
Zn
}
sE ≡ r(
) × yE mod p
s.r mod p
H :
{
q < n < p
1< k, x < q
w1 = Z −1 × E modq
r = gu mod p
q|(p-1),
,
,
,
,
,
,
(2.11)
y = g x mod p Z = gk mod p
E = H
M
Here: U is signing object owning a public key y and
,
,
,
E = H(M )
w1 +1 −1
u + x
E mod p
)
×
(
k − x× w1
)
modq
are representative value of the message M to
u =
v = w1 ×
B = r × y
(
,
be verified.
A ← gv.w mod p
modq
w2 = r × gv mod p
2
(
)
. If:
To find (r,s) from (2.11), the first way is to select a value
for r in advance, then calculate s. Then (2.11) will be
formed:
(
)
A = B
then:
.
Correctness of the newly proposed scheme is proved as
follows:
as ≡ sb mod p
(2.12)
From (3.7) and (3.8) we have:
Or in the second way is select s in advance then calculate r.
Then (2.11) will be formed:
A = gv.w mod p
2
r.gv mod p
rr mod p = b
= gv.
) mod p
(
(2.13)
= gv.Z mod p
In both two cases, a and b constants. It is easy to see that
solutions of (2.12) and (2.13) to find s and r is more
difficult than solution of the discrete logarithm problem
DLP(g,p).
−1.E.
(u+x).Z
= g Z
= g(
mod p
mod p
u+x).E
(3.10)
IJCSNS International Journal of Computer Science and Network Security, VOL.16 No.12, December 2016
57
Produce and check procedures of Electronic Digital
Signature based on Asymmetric Cryptographic Algorithm.
Government Committee of the Russia for Standards (in
Russian).
From (2.1), (3.5) and (3.9) we also have:
B = r × y
E mod p
= g( .E mod p
From (3.10) and (3.11) infer the thing to be proved:
A = B
(
)
u+x
)
(3.11)
Thuy N.D received the B.S from
HUFLIT University in 2005 and M.S
degree from Faculty of Information
.
c) Safety level of the scheme LD 16.9-02
From the Algorithm for verifying signature (Table 10) of
the scheme LD 16.9–02 shows that, any pair of (r,v) will
be recognized as a valid signature if the scheme generated
from a message M if it meets the condition:
Technology,
Military
Technical
Academy in 2013. My research interests
include cryptography, communication
and network security.
(
r.gv mod p
)
gv.
≡
(
r × y
E mod p
)
(3.12)
Similarly, (2.11), to find r and v from solution of (3.12) is
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 the
Military Technical Academy.
more difficult than solution of the problem DLP(g,p)
.
3. Conclusion
The article proposes a method of digital signature scheme
design based on difficulty discrete logarithm problem. An
advantages of the newly proposed method is that it can be
used for developing different digital signature schemes to
choose suitably for applications in practice. Signature
schemes of LD 16.9–01 and LD 16.9–02 presented here
has somewhat showed the feasibility of the newly
proposed method.
References
[1] Luu Hong Dung, Le Dinh Son, Ho Nhat Quang, Nguyen
Duc Thuy,“DEVELOPING DIGITAL SIGNATURE
SCHEMES BASED ON DISCRETE LOGARITHM
PROBLEM”, the Eighth National Scientific Meeting of
Basic Research and Information Technology Applications
(FAIR 2015), ISBN: 978-604-913-397-8.
[2] Luu Hong Dung, Hoang Thi Mai, Nguyen Huu Mong “A
form of signature scheme built up based on the digital
analysis problem”, the Eighth National Scientific Meeting
of Basic Research and Information Technology
Applications (FAIR 2015), ISBN: 978-604-913-397-8.
[3] Luu Hong Dung, Ho Ngoc Duy, Nguyen Tien Giang,
Nguyen Thi Thu Thuy, “Development of a new form of
digital signature scheme”, the Proceedings of the Sixteenth
National Seminar: Some Selected Issues of Information
Technology and Communication - Da Nang.
[4] Hoang Thi Mai, Luu Hong Dung, “A form of signature
scheme built up based on the digital analysis problem and
the square root problem”, Journal of Science and
Engineering - Military Technical Academy No. 172
(Journal of IT and Communication, No.7 - 10/2015), page:
32 – 41. ISSN: 1859 – 0209.
[5] 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.
[6] National Institute of Standards and Technology. NIST FIPS
PUB 186-3(2013). Digital Signature Standard, U.S.
Department of Commerce.
[7] GOST
R
34.10-94. Russian Federation Standard.
Information Technology. Cryptographic data Security.
5 trang
23480
Free
Bạn đang xem tài liệu "A New Construction Method of Digital Signature Algorithms", để 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:
- a_new_construction_method_of_digital_signature_algorithms.pdf
