Phương pháp xây dựng thuật toán chữ ký số dựa trên một dạng bài toán khó mới
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018
Phương pháp xây dựng thuật toán chữ ký số dựa trên một dạng
bài toán khó mới
A construction method of digital signature algorithms based on a new hard
problem
Lưu Hồng Dũng
Nguyễn Đức Thụy
Khoa CNTT
Học Viện KTQS
Khoa CNTT
CĐ Kinh tế - Kỹ thuật
Hà Nội, Việt Nam
Tp.HCM, Việt Nam
e-mail: luuhongdung@gmail.com
e-mail: thuyphulam2013@gmail.com
Abstract— Bài báo đề xuất một phương pháp xây
dựng thuật toán chữ ký số dựa trên tính khó của
bài toán logarit rời rạc kết hợp khai căn trên Zp.
Đây là một dạng bài toán khó mới, lần đầu được
đề xuất và ứng dụng để xây dựng các thuật toán
chữ ký số. Từ phương pháp được đề xuất có thể
xây dựng một lớp thuật toán chữ ký số có độ an
toàn cao cho các ứng dụng trong thực tế.
đó, nếu có một giải thuật thời gian đa thức cho bài
toán này (DLP) thì tính an toàn của các thuật toán sẽ
bị phá vỡ hoàn toàn. Nâng cao độ an toàn cho các
thuật toán chữ ký số dựa trên tính khó của việc giải
đồng thời 2 bài toán khó là một hướng tiếp cận đang
nhận được nhiều sự quan tâm của các nhà nghiên
cứu, trong [3 – 10] các tác giả đã đề xuất một số
thuật toán chữ ký xây dựng trên đồng thời hai bài
toán phân tích số và logarit rời rạc. Trong bài báo
này, cũng với mục đích nâng cao độ an toàn cho các
thuật toán chữ ký số, nhóm tác giả tiếp tục phát triển
phương pháp đề xuất trong [1,2] trên cơ sở tính khó
của việc giải một bài toán khó mới, ở đây được gọi
là bài toán logarit rời rạc kết hợp khai căn trên Zp.
Đây là một dạng bài toán khó lần đầu được đề xuất
và ứng dụng cho việc xây dựng thuật toán chữ ký số
và có nhiều triển vọng tạo ra các thuật toán có độ an
toàn cao cho các ứng dụng thực tế.
Keywords: Digital signature; Digital signature
algorithm; Digital Signature Schema; Discrete
logarithm problem.
I.
ĐẶT VẤN ĐỀ
Trong [1,2] đề xuất một phương pháp xây dựng
thuật toán chữ ký số dựa trên tính khó của việc giải
bài toán logarit rời rạc trên Zp. Ưu điểm của phương
pháp mới đề xuất là từ đó có thể triển khai một lớp
thuật toán chữ ký số cho các ứng dụng khác nhau.
Tuy nhiên, độ an toàn của các thuật toán chữ ký
được xây dựng theo phương pháp này chỉ được đảm
bảo bởi độ khó của việc giải bài toán logarit rời rạc
- DLP (Discrete Logarithm Problem) trên Zp. Do
1
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018
II. BÀI TOÁN KHÓ MỚI VÀ PHƯƠNG PHÁP
XÂY DỰNG THUẬT TOÁN CHỮ KÝ SỐ
3) Bài toán logarit rời rạc kết hợp khai căn trên
trường Zp
Bài toán logarit rời rạc kết hợp khai căn trên
trường Zp (Bài toán DLRP) được đề xuất ở đây có
thể phát biểu như sau:
A. Một số bài toán khó ứng dụng trong mật mã và
bài toán logarit rời rạc kết hợp khai căn trên Zp
1) Bài toán logarit rời rạc trên Zp
Bài toán DLRP: Với mỗi số nguyên dương
Bài toán logarit rời rạc trên Zp là cơ sở xây
dựng hệ mật khóa công khai ElGamal [11]. Bài toán
có thể được phát biểu như sau: Cho p là số nguyên
y ∈ Z*p
, hãy tìm các số x1 và x2 thỏa mãn phương
trình sau:
*
x2
tố, g là phần tử sinh của nhóm Zp . Với mỗi số
(
x1
)
mod p = y
p x1 là h
*
nguyên dương y ∈ Zp , hãy tìm x thỏa mãn phương
Trường h
DLP, còn n u x2 là 1 s
mãn u ki n theo [12]:
t s nguyên ch
FRP. D th y r ng, vi
DLP và FRP. Ngay c
gian a th c cho DLP và FRP thì c
ngh a là s gi được DLRP.
ợ
ằ
ng s
nguyên t
p = N ×
ố
thì DLRP tr
ở
thành
) và th
, v i: N là
thành
được DLRP là khó h
khi có các gi i thu t th
ng không có
trình:
ế
ố
ố
(hằ
ng s
ố
ỏa
g x mod p = y
S
)
đ
i
ề
ệ
ớ
(
x2
+1
Giải thuật cho bài toán DLP có thể được viết
như một thuật toán tính hàm DLP(.) với biến đầu
vào là y còn giá trị hàm là nghiệm x của phương
trình:
m
ộ
ố
ẵ
n và S
≥
2, thì DLRP s
ẽ
tr
ở
ễ
ấ
ằ
ệc gi
ả
i
ơn
c
ả
ả
ả
ậ
ời
đ
ứ
ũ
x = DLP(y)
ĩ
ẽ
ải
Ở hệ mật ElGamal, bài toán logarit rời rạc được
sử dụng với vai trò hàm một chiều trong việc hình
thành khóa của các thực thể trong cùng hệ thống với
bộ tham số {p,g} dùng chung.
B. Xây d
ựng lược đồ chữ ký dựa trên tính khó của
bài toán DLRP
1) Phương pháp xây d
phương pháp xây d
t, DLRP được s
t và công khai c
tham s th ng (tham s
ch v o ra, ở đây p là s
được ch n sao cho vi c gi i bài toán DLP là khó.
p (x1, x2) là khóa bí m t và y là khóa công khai
đối tượng ký trong h th ng. Để
c th ký c n t o trước s nguyên
t s
* . Khóa x1
ự
ng
ng thu
ng để hình thành c
đối tượng ký. Trong
mi n) do nhà cung c
nguyên t n ph
Ở
ự
ậ
t toán ch
ữ
ký m
p khóa
ó, p là
ớ
i
2) Bài toán khai căn trên Zp
đề xu
ấ
ử
d
ụ
ặ
Bài toán khai căn (FRP) trên Zp có thể được phát
bí m
ậ
ủa
đ
biểu như sau: Cho p là số nguyên tố, với mỗi số
ố
h
ệ
ố
ố
ề
ấp
*
nguyên dương y ∈ Zp , hãy tìm x thỏa mãn phương
d
ị
ụ
tạ
ố
ố
c
ầ
ải
trình:
ọ
ệ
ả
k
x mod p = y
( )
C
ặ
ậ
Trong [12], tác giả N.A. Moldovyan đã chứng
minh bài toán khai căn trên là khó nếu thỏa mãn:
t
t
t
ương
ứ
ng c
ủa m
ỗ
i
ệ
ố
ạ
o khóa x1 m
ỗ
i thự
ể
ầ
ạ
ố
p = N.kS +1
ố
q th
ỏ
a mãn: q|(p – 1) và m
ộ ố
α
∈ Zp
Ở đây: N là một số nguyên chẵn, k là một số
nguyên tố và S ≥ 2. Ngoài ra, p và k còn phải có kích
thước thỏa mãn: |p| ≥ 1024 bit và: |k| ≥ 160 bit.
được t
ạo theo:
p−1
q
x1 =
α
mod p
2
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018
Khóa x2 là m
ộ
t giá trị được ch
ọ
n ng
ẫ
u nhiên
Nên:
v = (u × f1(M ,Z, y1, y2 )−1 × f2 (M ,Z, y1, y2 )
trong kho ng (1, q). Sau
ả
đ
ó, các khóa công khai
+ x2 × f1(M ,Z, y1, y2 )−1 × f3(M ,Z, y1, y2 )mod q
được t
ạ
o ra từ (x1, x2) theo:
x2
x1
(1.9)
,
(1.1)
y1 =
(
x1
)
mod p y2 =
ng tham s q c
a m t khóa bí m
t toán ký. Gi
tin M, u là 1 giá tr trong kho
tính t u theo công th c:
r = x1
u mod p
Và s được tính t v theo công th
s = x1
v mod p
ng là 1 giá tr
(
x2
)
mod p
M
ặ
t khác, t
ừ (1.2), (1.3) và (1.4) ta có:
Chú ý r
vai trò c
trong thu
ằ
ố
ũ
ng sẽ được s
t tương t nh
(r,s) là ch ký lên b
ử
d
ụ
ng v
ới
(1.10)
(
v + u mod q = k
)
ủ
ộ
ậ
ự
ư x1 và x2
T
ừ
(1.9) và (1.10) ta có:
ậ
ả
s
ử
ữ
ả
n
[u × f1(M,Z, y1, y2 )−1 × f2 (M,Z) +
ị
ả
ng (1,q) và r được
+ x2 × f1(M,Z, y1, y2 )−1 × f3(M,Z, y1, y2 )
ừ
ứ
+ u]modq = k
(1.2)
(
)
Hay:
ừ
ức:
[u ×
f1(M,Z, y1, y2 )−1 × f2 (M,Z, y1, y2 ) +1
+ x2 × f1(M,Z, y1, y2 )−1 × f3(M,Z, y1, y2 )
(1.3)
(
)
Ở đây: v c
ng gi
đồ có d
ũ
ị
trong kho
ả
ng (1,q).
]modq = k
C
ũ
ả
thi
ế
t r
ằ
ng phương trình ki
ể
m tra c
ủa
(1.11)
l
ượ
c
ạ
ng:
T
ừ
(1.11), suy ra:
u =
f1(M,Z, y1, y2 )−1 × f2 (M,Z, y1, y2 ) +1 −1
k − x2 × f1(M,Z, y1, y2 )−1 × f3(M,Z, y1, y2 )
modq
f3 (M, f (r,s),y1,y2
) mod p
a r và s. Xét trường h p:
f (r,s) = r ×smod p
x1
k mod p
ó k là m
ng (1,q).
(
M , f
(
r,s
),y1,y2
(M , f (r,s),y1,y2
s f
) ≡ r f
) × y1
1
2
×
V
ớ
i
là hàm c
ủ
ợ
f (r,s)
×
(
)
(1.4)
=
( )
(1.12)
nh t c
Trong
đ
ột giá trị được chọn ngẫu nhiên
T
ừ
(1.12), có th
ký theo (1.2):
r = x1
u mod p
n th được tính theo (1.3):
v mod p
i v được tính theo (1.9):
v = [u × f1(M,Z, y1, y2 )−1 × f2 (M,Z, y1, y2 ) +
+ x2 × f1(M,Z, y1, y2 )−1 × f3(M, Z, y1, y2 )]modq
ừ đây, phương pháp xây d ng m t l p thu
toán ch ký s ương ng v i m t d ng c th
hàm f(r,s):
ể
tính thành ph
ầ
n th
ứ
ấ
ủa
trong kho
ả
ch
ữ
Đặt:
(
)
(x1 )
k mod p = Z
(1.5)
và thành ph
s = x1
ầ
ứ 2
Khi
ng:
đ
ó có thể đưa phương trình ki
ể
m tra về
(
)
d
ạ
vớ
f1
(
M ,Z , y1 , y2
)
f2 (M ,Z , y1 , y2 )
(
s
)
≡
(
r
)
×
(1.6)
f 3 (M ,Z , y1 , y2
×
(
y1
)
) mod p
T
ừ (1.1), (1.2), (1.3) và (1.6) ta có:
T
ự
ộ
ớ
ậ
t
v. f1
)
(
M ,Z ,y1,y2
)
u. f2 (M ,Z ,y1,y2 )
(
x1
≡
(
x1
)
×
ữ
ố
t
ứ
ớ
ộ
ạ
ụ
ể
c
ủa
(1.7)
x2 . f3 (M ,Z,y1,y2
f (r, s) = r × s mod p = x1
k mod p
(
)
×
(
x1
)
) mod p
đượ
c
Từ (1.7) suy ra:
ch
ỉ
ra trong các B ng 1.1, B ng 1.2 và B ng 1.3 nh
ả
ả
ả
ư
v × f1(M , Z, y1, y2 ) ≡ [u × f2 (M , Z, y1, y2 ) +
+ x2 × f3(M , Z, y1, y2 )]mod q
sau:
(1.8)
3
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018
Bảng 1.1. Thu
ậ
t toán sinh khóa
nguyên t , lq – độ dài (tính theo
a s nguyên t q.
[9].
v ← (u × w4 + x2 × w5 )mod q
Input: p – s
ố
ố
r ←
s ←
(
x1
x1
)
u mod p
v mod p
[10].
bit) c
ủ
ố
ố
[11].
(
)
Output: q, x1, x2, y1,y2.
[1]. generate q: len(q) = lq, q|(p-1)
[12]. return (r,s)
Chú thích:
(i) M: b n tin c
(ii) (r,s): ch ký của U
[2]. select α
:
1<
α < p
M ∈{0,1}∞
.
ả
ầ
n ký, v
ớ
i:
x1 ← α (
mod p
p−1)/ q
[3].
ữ
lên M.
[4]. if (x1 = 1) then goto [2]
[5]. select x2:
1< x2 < q
Bảng 1.3
.
Thuậ
t toán ki
ể
m tra chữ ký
x1
)
x2
)
[6].
,
y1 ←
(
x
mod p y2 ←
(
x2
mod p
Input: p, y1, y2, M, (r,s).
1
(2.1)
Output
[1].
:
true
/
.
false
[7]. return {q, x1, x2, y1, y2}
Chú thích:
- len(.) là hàm tính độ dài (theo bit) c
nguyên.
- q, x1, x2: Khóa bí m
- y1, y2: Khóa công khai c
Z ← f (r, s)
[2].
w1 ← f1(M,Z, y1, y2 )
w2 ← f2 (M, Z, y1, y2 )
ủ
a một
[3].
[4].
s
ố
ậ
t.
w3 ← f3(M,Z, y1, y2 )
w1
ủa
đối tượng ký.
[5].
[6].
A ←
B ←
(
s
)
mod p
w2
)
w3
(
r
×
(
y1
)
mod p
Bảng 1.2. Thuật toán ký
[7]. if
(
A = B
)
then
{
return
}
true
Input: p, q, x1, x2, y1, y2, M.
Output: (r,s).
else
{
return
}
false
[1]. select k:
Chú thích:
- M, (r,s): b
- N u k
n g c c
t qu là false thì M b
tính toàn v n.
2) t s
phương pháp m
a) Thu t toán MTA 18.9 –01
1 < k < q
ả
n tin, ch
tr là true thì tính toàn v
a M được kh ng định. Ngược l i, n
ph nh n v ngu n g c và
ữ ký cần thẩm tra.
Z ← x1
( )
k mod p
[2].
ế
ế
t qu
ả
ả
v
ề
ẹn và
[3].
w1 ← f1(M, Z, y1, y2 )
ngu
ồ
ố
ủ
ẳ
ạ
ếu
kế
ả
ị
ủ
ậ
ề
ồ
ố
[4].
[5].
w2 ← f2 (M,Z, y1, y2 )
ẹ
w3 ← f3 (M,Z, y1, y2 )
M
ộ
ố
thu
ật toán chữ ký xây dựng theo
−
w4 ←
w5 ←
(
w1
w1
w4 +1 −1
)
1 × w2 mod q
[6].
[7].
ớ
i
đề xu
ấ
t
−1 × w3 mod q
ậ
(
)
Thuậ
t toán ch
ữ
ký th
ứ
nh
ất đề xuất ở đây – ký
[8].
u ←
(
)
×
(
k − x2 × w5
)
modq
hi
ệ
u: MTA 18.9 – 01
,
được xây d
ự
ng theo các
4
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018
B
ả
ng 1.1, 1.2 và 1.3
sau:
f1(M,Z, y1, y2 ) = H(M )
ở mục A với lựa chọn các hàm
nh
ư
+ Tính
u c
nguyên t
đ
úng đắn c
n ch ng minh ở đây là: Cho p, q là 2 s
0,1 ∗
ủa thuật toán được đề xuất
,
,
f2(M,Z, y1, y2 ) = y2
Đ
i
ề
ầ
ứ
ố
,
.
f3(M ,Z, y1, y2 ) = Z
Khi ó, các thu
a thu t toán được mô t
ng 2.2 dướ ây:
Bảng 2.1. Thu
H :
{ } a Zn
,
ố
vớ
i q|(p-1),
q < n < p
đ
ật toán ký và kiểm tra chữ ký
p−1)/
x1 = α ( q mod p
,
,
,
1<
α
< p
1< k, x2 < q
c
ủ
ậ
ả
trong các B
ả
ng 2.1 và
x1
)
x2
,
,
,
(
x1
)
mod p
y2 =
(
x2
mod p
E = H M
(
)
y1 =
Z =
B
ả
i đ
k mod p
,
(
x1
)
ậ
t toán ký
,
,
,
u =
y2 × E−1 +1 −1
×
k − x2 × Z × E−1
mod q
u mod p
Input: p, q, x1, x2, y2, M .
Output: (r,s).
v = E−1
× (u × y2 + x2 × Z )
mod q
,
Z = r ×smod p
r = x1
( )
,
E
)
v
)
. N
ế
u:
s =
(
x1
mod p
A =
(
s
mod p
[1].
E ← H(M )
y2
Z
thì:
.
A = B
a thu t toán m
sau:
(2.2), (2.3), (2.4) và (2.6) ta có:
B =
(
r
)
×
(
y1
)
mod p
úng đắn c
ng minh nh
[2]. select k:
1< k < p −1
Tính
được ch
đ
ủ
ậ
ớ
i
đề xuất
[3].
[4].
[5].
[6].
[7].
(2.2)
(2.3)
Z ←
( )
k mod p
x1
y2 × E−1 +1 −1
v ← E−1
u × y2 + x2 × Z )
ứ
ư
u ←
×
k − x2 × Z × E−1
mod q
T
ừ
A =
(
s
)
E mod p =
(
−1
x1
)
v.E mod p =
.E mod p
.Z mod p
(2.4)
(2.5)
(2.6)
×
(
mod q
(2.9)
(
u. y2 + x2 .Z . E
) ( )
=
=
(
(
x1
x1
)
u
r ←
s ←
(x1 ) mod p
u. y2 + x2
)
(
x1
)
v mod p
Với:
[8]. return (r,s)
u =
(
y2 × E−1 +1 −1
)
×
(
k − x2 × Z × E−1
)mod q
T
ừ
(2.3), (2.4), (2.5) và (2.6) ta có:
u
)
Z = r × s mod p =
(
x1
×
(
x1
)
v mod p
Bảng 2.2. Thu
ậ
t toán ki
ể
m tra
=
(
(
(
x1
x1
x1
)
u+v mod p
Input: p, y1, y2, M, (r,s).
(
y2.E−1+1 −1
)
.
(
k−x2 .Z.E−1
)
E−1
.(u. y2 +x2.Z
=
=
×
=
×
×
)
×
(
x1
)
) mod p
y2.E.−1+1 −1 k−x2 .Z.E−1
) .( )
(2.10)
(
)
×
Output
[1].
:
true
/
.
false
E−1
.
(
y2 .E−1+1 −1
)
.
(
k−x2 .Z.E−1
)
. y2 +x2 .Z
(
x1
)
mod p
k.
)
(
y2 .E−1+1 −1
)
−x2.Z.E−1
.
(
y2 .E−1+1 −1
y2.E−1+1 −1.x2.Z.E−1.y2
y2.E−1+1 −1 y2 .E−1+1
−1.x2.Z
)
E ← H(M)
(
x1
x1
x1
x1
×
(
x1
)
E−1
.
(
y2.E−1+1
)
−1.k.y2
−E−1
.
(
)
A ← s
( )
E mod p
×
x1
[2].
(
(
(
)
)
)
(
)
E
−1.x2 .Z
k.
(
)
.
(
)
mod p = (x1 )
[3].
(2.7)
(2.8)
Z ← r × s mod p
−x2.Z.E−1
.
(
y2 .E−1+1 −1
)
.
(
y2.E−1+1
)
E
×
=
=
×
(
x1
)
mod p
k
)
−x2.Z.E−1
E
−1.x2 .Z
y2
Z
)
[4].
(
x1
x1
×
(
x1
)
×
(
x1
)
mod p
B ←
(
r
)
×
(
y1
then
return
mod p
k
(
)
mod p = Z
[5]. if
(
)
{return true }
A = B
Thay (2.1), (2.3), (2.5), (2.7) và (2.10) vào (2.8)
ta lại có:
else
{
}
false
5
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018
y2
Z
)
được công nhận là chữ ký hợp lệ với một bản tin M
nếu thỏa mãn điều kiện:
w1 =
(
r
)
×
(
y1
mod p =
(2.11)
u. y2
x2
=
=
(
(
x1
x1
)
× x1
( )
.Z mod p
u. y2 +x2
E
y2
s ≡ r × y1
( ) ( ) ( )
(r.s) mod p mod p
)
.Z mod p
(2.12)
Với:
u =
Từ (2.12), nếu chọn trước r rồi tính s thì khi đó
điều kiện (2.12) sẽ có dạng:
y2 × E−1 +1 −1
×
k − x2 × Z × E−1
mod q
E
)
)
≡ a(s.r mod p mod p
Từ (2.9) và (2.11) suy ra điều cần chứng minh:
A = B
(2.13)
(
s
Còn nếu chọn trước s rồi tính r thì khi đó điều
kiện (2.12) sẽ trở thành:
+ Mức độ an toàn của thuật toán được đề xuất
y2
(r.s)
mod p mod p
Mức độ an toàn của lược đồ mới đề xuất có thể
đánh giá qua khả năng như:
(2.14)
(r
)
≡
(b
)
Với a, b là hằng số, dễ thấy rằng việc giải
(2.13) và (2.14) là khó tương đương với DLRP.
- Chống tấn công khóa bí mật
b) Thuật toán MTA 18.9 – 02
Ở thuật toán mới đề xuất, cặp tham số x1, x2
cùng được sử dụng làm khóa bí mật để hình thành
Thuật toán chữ ký thứ hai đề xuất ở đây – ký
hiệu: MTA 18.9 – 02, cũng được xây dựng theo
chữ ký. Vì thế, thuật toán chỉ bị phá vỡ nếu cả 2
phương pháp tương tự MTA 18.9 – 01
thay đổi như sau:
với một số
tham số này cùng bị lộ, nói cách khác là kẻ tấn công
phải giải được bài toán logarit rời rạc kết hợp khai
căn trên Zp. Do đó, mức độ an toàn của thuật toán
mới đề xuất xét theo khả năng chống tấn công làm
lộ khóa mật được đánh giá bằng mức độ khó của
việc giải được DLRP. Cần chú ý, DLRP là một
dạng bài toán khó mới, mà ngay cả khi có các giải
thuật thời gian đa thức cho FRP và DLP cũng không
có nghĩa là sẽ giải được bài toán này. Ngoài ra,
tham số q cũng được sử dụng với vai trò khóa bí
mật trong thuật toán ký. Như vậy, để phá vỡ tính an
toàn của thuật toán, kẻ tấn công còn phải giải được
bài toán tìm bậc của x1. Tuy nhiên, việc tìm bậc của
x1 là không thể thực hiện được, vì x1 ở đây là 1 tham
số bí mật.
Các giá trị: x1, x2, y2 được sử dụng làm khóa bí
mật của đối tượng ký, khóa công khai được tính
theo:
y2
(3.1)
y =
(
y1
)
mod p
Và đẳng thức kiểm tra được giả thiết là:
E
y
Z
s ≡ r × y mod p
( ) ( ) ( )
Khi đó, các thuật toán ký và kiểm tra chữ ký
của thuật toán được mô tả trong các Bảng 3.1 và
Bảng 3.2 dưới đây:
Bảng 3.1. Thuật toán ký
Input: p, q, x1, x2, y2, y, M .
Output: (r,s).
[1].
E ← H(M )
- Chống giả mạo chữ ký
[2]. select k:
1< k < p −1
k mod p
y × E−1 +1 −1
Từ thuật toán kiểm tra (Bảng 2.2) của thuật
toán mới đề xuất cho thấy, một cặp (r,s) giả mạo sẽ
[3].
(3.2)
Z ← (x1 )
u ←
×
k − x2 × y2 × Z × E−1
mod q
[4].
6
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018
v = E−1
×
(
u × y + x2 × y2 × Z
)
mod q
,
Z = r ×smod p
(3.3)
(3.4)
,
,
,
r =
(
x1
A =
)
u mod p
E mod
v
−1
[5].
[6].
[7].
. N
ế
u:
v ← E
r ←
s ←
×
(
u × y + x2 × y2 × Z
)
mod q
s =
(
x1
)
mod p
(
s
)
p
y
Z
)
u
)
thì:
.
A = B
a thu t toán m
sau:
(3.2), (3.3), (3.4) và (3.6) ta có:
A = x1
E mod p = v.E mod p =
.E mod p
u. y+x . y .Z mod p
(3.5)
(3.6)
B =
(
r
)
×
(
y
mod p
(
x1
mod p
Tính
được ch
đ
úng đắn c
ủ
ậ
ới đề xuất
x1
( )
v mod p
ứ
ng minh như
[8]. return (r,s)
T
ừ
(s
)
( )
−1
(3.9)
(
u. y+x2 . y2 .Z . E
) ( )
Bảng 3.2. Thuật toán kiểm tra
Input: p, y, M, (r,s).
=
=
(
(
x1
x1
)
2
2
)
V
ớ
i:
u =
Output: true
/
.
false
y × E−1 +1 −1
×
k − x2 × y2 × Z × E−1
mod q
[1].
[2].
[3].
[4].
E ← H(M)
E mod p
T
ừ
(3.3), (3.4), (3.5) và (3.6) ta có:
A ←
(
s
)
u
Z = r × s mod p =
(
x1
)
×
(
x1
)
v mod p
=
(
(
x1
x1
)
u+v mod p
) .( )
y.E−1+1 −1 k−x2. y2 .Z.E−1
(3.7)
(3.8)
Z ← r × s mod p
(
=
×
=
)
×
y
Z
E−1
.(u. y+x2. y2.Z
B ← r × y mod p
( ) ( )
(
x1
)
) mod p
(
y.E.−1+1 −1 k−x2. y2.Z.E−1
) .( )
(
x1
)
×
[5]. if
(
)
then
{
return true
}
A = B
E−1
.
(
y.E−1+1 −1
)
.
(
k−x2. y2.Z.E−1
)
. y+x2. y2.Z
×
=
×
×
(
x1
)
mod p
else
{
return
}
false
k.
)
(
y.E−1+1 −1
)
−x2 . y2.Z.E−1
.
(
y.E−1+1 −1
y.E−1+1 −1.x2. y2.Z.E−1. y
y.E−1+1 −1 y.E−1+1
)
(
x1
x1
x1
x1
×
(
x1
)
E−1
.
(
y.E−1+1
)
−1.k. y
−E−1
.
(
)
(
(
(
)
)
)
× x1
( )
E
−1.x2. y2.Z
k.
( )
x1
(
)
.
(
)
mod p =
Nh
ậ
n xét:
−x2. y2.Z.E−1
.
(
y.E−1+1 −1
)
.
(
y.E−1+1
)
E
−1.x2. y2 .Z
×
=
=
×
(
x1
)
mod p
T
ừ
vi
và MTA 18.9 – 02 cho th
ở đây có th o ra các thu
khóa bí m t và 1 ho c 2 khóa công khai là hoàn toàn
c vào ý định thi t k
úng đắn c a thu t toán đượ
ệ
c xây d
ự
ng các thu
y phương pháp m
t toán ch ký v
ậ
t toán MTA 18.9 – 01
đề xu
i nhi
k
)
−x2 .y2 .Z.E−1
E
−1.x2 . y2.Z
(
x1
x1
×
(
x1
)
×
(
x1
)
mod p
ấ
ớ
i
ất
k
(3.10)
(
) mod p = Z
ể
t
ạ
ậ
ữ
ớ
ều
Thay (3.1), (3.3), (3.5), (3.7) và (3.10) vào (3.8)
ta lại có:
ậ
ặ
tùy thu
ộ
ế
ế.
y
Z
w1 = r × y mod p =
( ) ( )
+ Tính
đ
ủ
ậ
c
đề xu
ất
(3.11)
u. y
x2. y2.Z
=
(
(
x1
x1
)
×
(
x1
)
mod p
mod p
u. y+x2 . y2.Z
Đ
i
ề
u c
ầ
n chứ
ng minh ở đây là: Cho p, q là 2 s
ố
,
=
)
H :
{
0,1 ∗
}
a Zn
,
q < n < p
nguyên t
ố
vớ
i q|(p-1),
Với:
u =
1<
α < p
1< k, x2 < q
y × E−1 +1 −1
×
k − x2 × y2 × Z × E−1
mod q
p−1
)
x1 = α ( / q mod p
,
,
,
x1
x2
y2
Từ (3.9) và (3.11) suy ra điều cần chứng minh:
A = B
,
mod p
,
,
y2 =
(
x2
)
mod p
( )
y1 =
E = H
u =
(
x1
)
y = y1 mod p
,
,
)
Z =
(
x1
)
k mod p
(
M
+ Mức độ an toàn của thuật toán được đề xuất
Mức độ an toàn của lược đồ mới đề xuất có thể
,
(
y × E−1 +1 −1
)
×
(
k − x2 × y2 × Z × E−1
)
mod q
7
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018
đánh giá qua khả năng như:
TÀI LIỆU THAM KHẢO
- Chống tấn công khóa bí mật
[1] Lưu Hồng Dũng, Nguyễn Đức Thụy, Nguyễn Văn Phúc và
Đỗ Anh Tuấn, “Một phương pháp xây dựng thuật toán chữ
ký số”, Hội thảo lần thứ I: Một số vấn đề chọn lọc về an
toàn, an ninh thông tin (SoIS 2016), 11/2016.
Tương tự MTA 18.9 – 01, mức độ an toàn của
thuật toán mới đề xuất xét theo khả năng chống tấn
công làm lộ khóa mật cũng được đánh giá bằng mức
độ khó của việc giải được bài toán DLRP.
[2] Nguyen Duc Thuy and Luu Hong Dung, “A New
Construction Method of Digital Signature Algorithms”,
IJCSNS International Journal of Computer Science and
Network Security. Vol. 16 No. 12 pp. 53-57, December
2016. ISSN: 1738 - 7906.
[3] 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.
- Chống giả mạo chữ ký
Từ thuật toán kiểm tra (Bảng 3.2) của thuật
toán mới đề xuất cho thấy, một cặp (r,s) giả mạo sẽ
được công nhận là chữ ký hợp lệ với một bản tin M
nếu thỏa mãn điều kiện:
[4] 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.
[5] Shimin Wei, “Digital Signature Scheme Based on Two
Hard Problems”, IJCSNS International Journal of
Computer Science and Network Security, VOL.7 No.12,
December 2007.
E
y
s ≡ r × y
( ) ( ) ( )
(r.s) mod p mod p
(3.12)
[6] 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
Từ (3.12), nếu chọn trước r rồi tính s thì khi đó
điều kiện (3.12) sẽ có dạng:
Statistics,
04/2008;
12(3).
DOI:
10.3844/jmssp.2008.222.225 Source:DOAJ.
E
)
)
(3.13)
(
s
≡ a(s.r mod p mod p
[7] Qin Yanlin , Wu Xiaoping,“ New Digital Signature Scheme
Based on both ECDLP and IFP”, Computer Science and
Information Technology, 2009. ICCSIT 2009. 2nd IEEE
International Conference on, 8-11 Aug. 2009, E-ISBN :
978-1-4244-4520-2, pp 348 - 351.
Còn nếu chọn trước s rồi tính r thì khi đó điều
kiện (3.12) sẽ trở thành:
[8] 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, Int. J. Pure Appl. Sci.
Technol., 5(2) (2011), pp. 55-59.
y
(r.s)
mod p mod p
(3.14)
(r
)
≡
(b
)
Với a, b là hằng số, cũng dễ thấy rằng việc giải
(3.13) và (3.14) là khó tương đương với bài toán
DLRP.
[9] Sushila Vishnoi , Vishal Shrivastava, ”A new Digital
Signature Algorithm based on Factorization and Discrete
Logarithm problem”, International Journal of Computer
Trends and Technology, volume 3, Issue 4, 2012.
III. KẾT LUẬN
[10] 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.
Bài báo đề xuất một phương pháp xây dựng thuật
toán chữ ký số mới dựa trên bài toán logarit rời rạc
kết hợp khai căn trên Zp. Mức độ an toàn của các
thuật toán xây dựng theo phương pháp này sẽ được
đảm bảo bằng mức độ khó của việc giải bài toán
trên. Ở đây, bài toán logarit rời rạc kết hợp khai căn
trên trường Zp là một dạng bài toán khó mới, lần đầu
được đề xuất và ứng dụng trong việc xây dựng thuật
toán chữ ký số. Từ phương pháp mới đề xuất có thể
xây dựng một lớp thuật toán chữ ký số có độ an toàn
cao cho các ứng dụng trong thực tế.
[11] 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.
[12] N.A. Moldovyan, "Digital Signature Scheme Based on a
New Hard Problem", Computer Science Journal of
Moldova, vol.16, no.2(47), 2008.
8
Hội thảo lần thứ III: Một số vấn đề chọn lọc về an toàn an ninh thông tin – Đà Nẵng, 07/12/2018
9
9 trang
10/05/2022
6120
Bạn đang xem tài liệu "Phương pháp xây dựng thuật toán chữ ký số dựa trên một dạng bài toán khó mới", để 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:
- phuong_phap_xay_dung_thuat_toan_chu_ky_so_dua_tren_mot_dang.pdf
