Hội thảo lần thứ III: Một số vấn đề chọn lọc về an tồ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 tốn khó mới
A construction method of digital signature algorithms based on a new hard
problem
Lưu Hồng Dũng
Khoa CNTT
Học Viện KTQS
Hà Nội, Việt Nam
e-mail:

Nguyễn Đức Thụy
Khoa CNTT
CĐ Kinh tế - Kỹ thuật
Tp.HCM, Việt Nam
e-mail:

Abstract— Bài báo đề xuất một phương pháp xây

đó, nếu có một giải thuật thời gian đa thức cho bài

dựng thuật toán chữ ký số dựa trên tính khó của

tốn này (DLP) thì tính an tồn của các thuật tốn sẽ

bài tốn logarit rời rạc kết hợp khai căn trên Zp.

bị phá vỡ hoàn toàn. Nâng cao độ an toàn cho các

Đây là một dạng bài tốn khó mới, lần đầu được

thuật tốn chữ ký số dựa trên tính khó của việc giải

đề xuất và ứng dụng để xây dựng các thuật toán

đồng thời 2 bài tốn khó là một hướng tiếp cận đang

chữ ký số. Từ phương pháp được đề xuất có thể

nhận được nhiều sự quan tâm của các nhà nghiên

xây dựng một lớp thuật tốn chữ ký số có độ an

cứu, trong [3 – 10] các tác giả đã đề xuất một số

toàn cao cho các ứng dụng trong thực tế.

thuật toán chữ ký xây dựng trên đồng thời hai bài

Keywords:

Digital

signature;

Digital

signature

algorithm;


Digital

Signature

Schema;

Discrete

tố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 tồn cho các
thuật tốn chữ ký số, nhóm tác giả tiếp tục phát triển

logarithm problem.

phương pháp đề xuất trong [1,2] trên cơ sở tính khó
I.

ĐẶT VẤN ĐỀ

của việc giải một bài tốn khó mới, ở đây được gọi

Trong [1,2] đề xuất một phương pháp xây dựng

là bài toán logarit rời rạc kết hợp khai căn trên Zp.

thuật toán chữ ký số dựa trên tính khó của việc giải

Đây là một dạng bài tốn khó lần đầu được đề xuất


bài tốn logarit rời rạc trên Zp. Ưu điểm của phương

và ứng dụng cho việc xây dựng thuật toán chữ ký số

pháp mới đề xuất là từ đó có thể triển khai một lớp

và có nhiều triển vọng tạo ra các thuật tốn có độ an

thuật tốn chữ ký số cho các ứng dụng khác nhau.

toàn cao cho các ứng dụng thực tế.

Tuy nhiên, độ an tồn của các thuật tố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 tố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 tồn an ninh thơng tin – Đà Nẵng, 07/12/2018

II.

BÀI TỐN KHĨ MỚI VÀ PHƯƠNG PHÁP
XÂY DỰNG THUẬT TỐN CHỮ KÝ SỐ

A. Một số bài tố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 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 tốn
có thể được phát biểu như sau: Cho p là số nguyên
tố, g là phần tử sinh của nhóm Zp*. Với mỗi 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:
Bài tốn DLRP: Với mỗi số nguyên dương
y ∈ Z *p , hãy tìm các số x1 và x2 thỏa mãn phương

trình sau:

(x1 )x

2

mod p = y

*

nguyên dương y ∈ Zp , hãy tìm x thỏa mãn phương
trình:

Trường hợp x1 là hằng số thì DLRP trở thành
DLP, còn nếu x2 là 1 số nguyên tố (hằng số) và thỏa

g x mod p = y
Giải thuật cho bài tốn DLP có thể được viết

như một thuật tố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 điều kiện theo [12]: p = N × ( x2 )S + 1 , với: N là
một số nguyên chẵn và S ≥ 2, thì DLRP sẽ trở thành
FRP. Dễ thấy rằng, việc giải được DLRP là khó hơn
cả DLP và FRP. Ngay cả khi có các giải thuật thời
gian đa thức cho DLP và FRP thì cũng khơng có

x = DLP( y )
Ở 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.
2) Bài toán khai căn trên Zp
Bài tốn khai căn (FRP) trên Zp có thể được phát
biểu như sau: Cho p là số nguyên tố, với mỗi số
nguyên dương y ∈ Zp*, hãy tìm x thỏa mãn phương
trình:

nghĩa là sẽ giải được DLRP.
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ựng

Ở phương pháp xây dựng thuật toán chữ ký mới
đề xuất, DLRP được sử dụng để hình thành cặp khóa
bí mật và cơng khai của đối tượng ký. Trong đó, p là
tham số hệ thống (tham số miền) do nhà cung cấp

dịch vụ tạo ra, ở đây p là số nguyên tố cần phải

được chọn sao cho việc giải bài tốn DLP là khó.
k

(x )

mod p = y

Trong [12], tác giả N.A. Moldovyan đã chứng
minh bài tốn khai căn trên là khó nếu thỏa mãn:

p = N .k + 1
S

Ở đây: N là một số nguyên chẵn, k là một số

Cặp (x1, x2) là khóa bí mật và y là khóa cơng khai
tương ứng của mỗi đối tượng ký trong hệ thống. Để
tạo khóa x1 mỗi thực thể ký cần tạo trước số nguyên
tố q thỏa mãn: q|(p – 1) và một số α ∈ Z *p . Khóa x1

được tạo theo:

nguyên tố và S ≥ 2. Ngồ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.

x1 = α

p −1

q

mod p

2


Hội thảo lần thứ III: Một số vấn đề chọn lọc về an tồ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:

trong khoảng (1, q). Sau đó, các khóa cơng khai

v = (u × f1 ( M , Z , y1 , y2 ) −1 × f 2 ( M , Z , y1 , y 2 )

được tạo ra từ (x1, x2) theo:

+ x2 × f1 ( M , Z , y1 , y2 ) −1 × f 3 ( M , Z , y1 , y2 ) mod q

(1.9)

x
x
y1 = (x1 ) 2 mod p , y2 = (x2 ) 1 mod p (1.1)

Mặt khác, từ (1.2), (1.3) và (1.4) ta có:

Chú ý rằng tham số q cũng sẽ được sử dụng với


(1.10)

(v + u ) mod q = k

vai trị của một khóa bí mật tương tự như x1 và x2

Từ (1.9) và (1.10) ta có:

trong thuật tốn ký. Giả sử (r,s) là chữ ký lên bản
tin M, u là 1 giá trị trong khoảng (1,q) và r được

[u × f1 ( M , Z , y1 , y2 )−1 × f 2 ( M , Z ) +

tính từ u theo cơng thức:

+ x2 × f1 ( M , Z , y1 , y2 ) −1 × f 3 ( M , Z , y1 , y2 )
+ u] mod q = k

(1.2)

u

r = ( x1 ) mod p

Hay:

Và s được tính từ v theo cơng thức:

[u × ( f1 ( M , Z , y1 , y2 ) −1 × f 2 ( M , Z , y1 , y2 ) + 1)


(1.3)

v

s = ( x1 ) mod p

+ x2 × f1 ( M , Z , y1 , y2 )−1 × f 3 ( M , Z , y1 , y2 )

Ở đây: v cũng là 1 giá trị trong khoảng (1,q).

] mod q = k

Cũng giả thiết rằng phương trình kiểm tra của

(1.11)

lược đồ có dạng:
s f1 (M , f (r ,s ), y1, y2 ) ≡ r f 2 ( M , f (r ,s ), y1 , y2 ) × y1

f 3 ( M , f ( r ,s ), y1 , y2 )

Từ (1.11), suy ra:

mod p

−1

u = ( f1 ( M , Z , y1 , y2 ) −1 × f 2 ( M , Z , y1 , y2 ) + 1) ×


Với f (r , s) là hàm của r và s. Xét trường hợp:
f (r, s) = r × s mod p

× (k − x2 × f1 ( M , Z , y1 , y2 ) −1 × f 3 ( M , Z , y1 , y2 ) )
mod q

(1.4)

k

= ( x1 ) mod p

(1.12)

Trong đó k là một giá trị được chọn ngẫu nhiên
trong khoảng (1,q).

Từ (1.12), có thể tính thành phần thứ nhất của
chữ ký theo (1.2):

Đặt:

u

k

(x1 )

(1.5)


mod p = Z

r = ( x1 ) mod p

và thành phần thứ 2 được tính theo (1.3):

Khi đó có thể đưa phương trình kiểm tra về
dạng:

(s ) f (M , Z , y , y ) ≡ (r ) f (M , Z , y , y
f (M ,Z , y , y )
× ( y1 )
mod p
1

1

2

3

2

1

1

2

)


v

s = ( x1 ) mod p

với v được tính theo (1.9):
×

(1.6)

v = [u × f1 ( M , Z , y1 , y2 ) −1 × f 2 ( M , Z , y1 , y2 ) +

2

+ x2 × f1 ( M , Z , y1 , y2 ) −1 × f 3 ( M , Z , y1 , y2 )] mod q

Từ (1.1), (1.2), (1.3) và (1.6) ta có:
v . f1 ( M ,Z , y1 , y2 )

(x1 )
x .f
× ( x1 )
2

3

u . f 2 ( M ,Z , y1 , y2 )

≡ ( x1 )


( M ,Z , y1 , y2 )

×

Từ đây, phương pháp xây dựng một lớp thuật
(1.7)

mod p

toán chữ ký số tương ứng với một dạng cụ thể của
hàm f(r,s): f (r, s) = r × s mod p = ( x1 )k 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 , y 2 ) ≡ [u × f 2 ( M , Z , y1 , y 2 ) +
+ x 2 × f 3 ( M , Z , y1 , y 2 )] 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 tồn an ninh thơng tin – Đà Nẵng, 07/12/2018

Bảng 1.1. Thuật tốn sinh khóa

[9]. v ← (u × w4 + x2 × w5 ) mod q


Input: p – số nguyên tố, lq – độ dài (tính theo
bit) của số nguyên tố q.

[11]. s ← (x1 )v mod p

Output: q, x1, x2, y1,y2.

[12]. return (r,s)

[1]. generate q: len(q) = lq, q|(p-1)

Chú thích:

[2]. select α: 1 < α < p
[3]. x1 ← α

( p −1) / q

[10]. r ← ( x1 )u mod p

(i) M: bản tin cần ký, với: M ∈ {0,1}∞ .

mod p

(ii) (r,s): chữ ký của U 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ý

[6]. y1 ← (x1 )x mod p , y2 ← (x2 )x mod p

Input: p, y1, y2, M, (r,s).

1

2

(2.1)
[7]. return {q, x1, x2, y1, y2}
Chú thích:
- len(.) là hàm tính độ dài (theo bit) của một

Output: true / false .
[1]. Z ← f (r , s )
[2]. w1 ← f1 ( M , Z , y1 , y2 )
[3]. w2 ← f 2 ( M , Z , y1 , y2 )

số nguyên.
- q, x1, x2: Khóa bí mật.

[4]. w3 ← f 3 ( M , Z , y1 , y2 )

- y1, y2: Khóa cơng khai của đối tượng ký.

[5]. A ← (s )w mod p

Bảng 1.2. Thuật toán ký

Input: p, q, x1, x2, y1, y2, M.

1

[6]. B ← (r )w2 × ( y1 )w3 mod p
[7]. if ( A = B ) then {return true }

else {return false }

Output: (r,s).
[1]. select k: 1 < k < q
[2]. Z ← ( x1 )k mod p

Chú thích:
- M, (r,s): bản tin, chữ ký cần thẩm tra.
- Nếu kết quả trả về là true thì tính tồn vẹn và

[3]. w1 ← f1 ( M , Z , y1 , y2 )

nguồn gốc của M được khẳng định. Ngược lại, nếu

[4]. w2 ← f 2 ( M , Z , y1 , y2 )

kết quả là false thì M bị phủ nhận về nguồn gốc và

[5]. w3 ← f 3 ( M , Z , y1 , y2 )
−1

[6]. w4 ← (w1 ) × w2 mod q


tính tồn vẹn.
2) Một số thuật toán chữ ký xây dựng theo
phương pháp mới đề xuất

[7]. w5 ← (w1 )−1 × w3 mod q

a) Thuật toán MTA 18.9 –01

[8]. u ← (w4 + 1)−1 × (k − x2 × w5 ) mod q

Thuật toán chữ ký thứ nhất đề xuất ở đây – ký
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 tồn an ninh thơng tin – Đà Nẵng, 07/12/2018

Bảng 1.1, 1.2 và 1.3 ở mục A với lựa chọn các hàm
như sau:

+ Tính đúng đắn của thuật toán được đề xuất

f1 ( M , Z , y1 , y2 ) = H ( M ) , f 2 ( M , Z , y1, y2 ) = y2 ,
f 3 ( M , Z , y1 , y 2 ) = Z .

Điều cần chứng minh ở đây là: Cho p, q là 2 số
∗
nguyên tố với q|(p-1), H : {0,1} a Z n , q < n < p ,


Khi đó, các thuật tốn ký và kiểm tra chữ ký
của thuật tốn được mơ tả trong các Bảng 2.1 và
Bảng 2.2 dưới đây:

1<α < p ,

,

x1 = α ( p −1)/ q mod p

x
y1 = (x1 ) 2 mod p ,

1 < k , x2 < q ,

x
y2 = ( x2 ) 1 mod p ,

E = H (M ) ,

,

k

Z = (x1 ) mod p

Bảng 2.1. Thuật toán ký

−1


Input: p, q, x1, x2, y2, M .

u = ( y 2 × E −1 + 1) × (k − x 2 × Z × E −1 ) mod q

Output: (r,s).

v = E −1 × (u × y 2 + x 2 × Z ) mod q

(2.2)

k

Z ← ( x1 ) mod p

[4]. u ← (y 2 × E + 1) × (k − x 2 × Z × E )mod q (2.3)
−1

E
A = (s ) mod p ,

y
Z
B = (r ) 2 × ( y1 ) mod p thì: A = B .

[2]. select k: 1 < k < p − 1

−1

,


u

r = ( x1 ) mod p

v
s = ( x1 ) mod p . Nếu: Z = r × s mod p ,

[1]. E ← H (M )

[3].

,

,

−1

[5]. v ← E −1 × (u × y 2 + x 2 × Z ) mod q

Tính đúng đắn của thuật toán mới đề xuất

được chứng minh như sau:
Từ (2.2), (2.3), (2.4) và (2.6) ta có:
v. E

E

A = (s ) mod p = ( x1 )

(2.4)


(u. y 2 + x 2 . Z ).( E )

[6]. r ← ( x1 ) mod p

(2.5)

[7].

(2.6)

u

v

s ← ( x1 ) mod p

= ( x1 )

u. y 2 + x2 . Z

= ( x1 )

−1

.E

mod p =

(2.9)


mod p

mod p

Với:
−1

u = ( y 2 × E −1 + 1) × (k − x 2 × Z × E −1 ) mod q

[8]. return (r,s)

Từ (2.3), (2.4), (2.5) và (2.6) ta có:
u

u+v

= ( x1 )

Input: p, y1, y2, M, (r,s).

−1

2

−1

2

−1


−1

2

−1

2

1

× ( x1 )

[1]. E ← H (M )

E −1 .  y2 . E −1 +1


(

(

= ( x1 )

(2.7)

(

× ( x1 )


E −1 . y2 . E −1

× ( x1 )

E −1 . x2 . Z

)E

1

−1

−1

. (u . y 2 + x 2 . Z )

mod p

)×

−1

) .(k − x . Z . E ). y + x . Z 
−1

2

2

−1


2

−1

2

mod p
−1

−1

−1

2

−1

2

2

(2.10)

−1

−1

. x2 . Z . E −1 . y 2


1

(

k

(

k . y2 . E −1 +1

mod p = ( x1 )

− x2 . Z . E −1 . y2 . E −1 +1

× ( x1 )

(2.8)

) × (x

) × (x )− x . Z . E . ( y . E +1)
1
+1) . k . y
− E .( y . E +1)
× (x )

k . y2 . E −1 +1

[2]. A ← (s )E mod p


[4]. B ← (r ) y 2 × ( y1 )Z mod p

mod p

( y . E +1) . (k − x . Z . E
= ( x1 )
( y . E . +1) . (k − x . Z . E
= (x )

Output: true / false .

[3]. Z ← r × s mod p

v

Z = r × s mod p = ( x1 ) × ( x1 ) mod p

Bảng 2.2. Thuật toán kiểm tra

= ( x1 ) × ( x1 )

−1

) .(y . E

− x2 . Z . E −1

2

−1


+1

× ( x1 )

)

−1

) .(y . E
2

× ( x1 )

E −1 . x 2 . Z

−1

+1

E −1 . x2 . Z

)

mod p

mod p

k


[5]. if ( A = B ) then {return true }

else {return false }

= ( x1 ) mod p = Z

Thay (2.1), (2.3), (2.5), (2.7) và (2.10) vào (2.8)
ta lại có:

5


Hội thảo lần thứ III: Một số vấn đề chọn lọc về an tồn an ninh thơng tin – Đà Nẵng, 07/12/2018

y

Z

w1 = (r ) 2 × ( y1 ) mod p =
u . y2

= ( x1 )

× ( x1 )

u . y 2 + x2 . Z

= ( x1 )

x2 . Z


(2.11)

mod p

đượ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:

mod p

(s )E ≡ (r )y × ( y1 )( r.s ) mod p mod p
2

Với:

(2.12)

Từ (2.12), nếu chọn trước r rồi tính s thì khi đó
−1

u = ( y 2 × E + 1) × (k − x 2 × Z × E
−1

−1

)mod q

điều kiện (2.12) sẽ có dạng:

Từ (2.9) và (2.11) suy ra điều cần chứng minh:


A=B
+ Mức độ an tồn của thuật tốn được đề xuất

(s )E ≡ a (s.r ) mod p mod p

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 lược đồ mới đề xuất có thể
đánh giá qua khả năng như:
- Chống tấn cơng khóa bí mật
Ở thuật tố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
chữ ký. Vì thế, thuật tốn chỉ bị phá vỡ nếu cả 2
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 tồn của thuật tố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

(2.13)

(r )y

2

( r . s ) mod p

≡ (b )


mod p

(2.14)

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.
b) Thuật tốn MTA 18.9 – 02
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
phương pháp tương tự MTA 18.9 – 01 với một số
thay đổi như sau:
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:
y

việc giải được DLRP. Cần chú ý, DLRP là một
dạng bài tố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

y = ( y1 ) 2 mod p

(3.1)

Và đẳng thức kiểm tra được giả thiết là:

(s )E ≡ (r )y × ( y )Z mod p

có nghĩa là sẽ giải được bài tốn này. Ngồi ra,


Khi đó, các thuật tốn ký và kiểm tra chữ ký

tham số q cũng được sử dụng với vai trò khóa bí

của thuật tốn được mơ tả trong các Bảng 3.1 và

mật trong thuật toán ký. Như vậy, để phá vỡ tính an

Bảng 3.2 dưới đây:

tồn của thuật tốn, kẻ tấn cơng cịn phải giải được
bài tố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.
- Chống giả mạo chữ ký
Từ thuật tố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ẽ

Bảng 3.1. Thuật toán ký
Input: p, q, x1, x2, y2, y, M .
Output: (r,s).
[1]. E ← H (M )
[2]. select k: 1 < k < p − 1
[3]. Z ← (x1 )k mod p

(3.2)

[4]. u ← (y × E −1 + 1)−1 × (k − x 2 × y 2 × Z × E −1 )mod q
6



Hội thảo lần thứ III: Một số vấn đề chọn lọc về an tồn an ninh thơng tin – Đà Nẵng, 07/12/2018

(3.3)

,

v = E −1 × (u × y + x 2 × y 2 × Z ) mod q

[5]. v ← E −1 × (u × y + x 2 × y 2 × Z ) mod q

(3.4)

v
s = ( x1 ) mod p . Nếu: Z = r × s mod p ,

[6]. r ← ( x1 )u mod p

(3.5)

y
Z
B = (r ) × ( y ) mod p thì: A = B .

[7].

(3.6)

v


s ← ( x1 ) mod p

,

u

r = ( x1 ) mod p

E
A = (s ) mod p ,

Tính đúng đắn của thuật tốn mới đề xuất

được chứng minh như sau:

[8]. return (r,s)

Từ (3.2), (3.3), (3.4) và (3.6) ta có:
v. E

E

A = (s ) mod p = (x1 )

Bảng 3.2. Thuật toán kiểm tra

−1

(u . y + x2 . y2 . Z ).( E )


= (x1 )

u . y + x2 . y2 . Z

= (x1 )

Input: p, y, M, (r,s).

.E

mod p =

(3.9)

mod p

mod p

Với:

Output: true / false .

−1

u = ( y × E −1 + 1) × (k − x 2 × y 2 × Z × E −1 ) mod q

[1]. E ← H (M )

Từ (3.3), (3.4), (3.5) và (3.6) ta có:


[2]. A ← (s )E mod p

u

[3]. Z ← r × s mod p

u +v

(3.7)

[4]. B ← (r )y × ( y )Z mod p

(3.8)

= ( x1 )

mod p

(y. E
= ( x1 )

−1

× ( x1 )

+1

−1


) . (k − x . y . Z . E ) ×
2

mod p

−1

( y . E . +1) . (k − x . y . Z . E ) ×
= ( x1 )


( )E . (y. E +1) .(k − x . y . Z . E ). y+ x . y . Z 

[5]. if ( A = B ) then {return true }

−1

2

−1

−1

(

−1

k . y . E +1

= ( x1 )


2

Nhận xét:
Từ việc xây dựng các thuật toán MTA 18.9 – 01
và MTA 18.9 – 02 cho thấy phương pháp mới đề xuất

ở đây có thể tạo ra các thuật tốn chữ ký với nhiều
khóa bí mật và 1 hoặc 2 khóa cơng khai là hoàn toàn
tùy thuộc vào ý định thiết kế.

−1

)

(

∗

nguyên tố với q|(p-1), H : {0,1} a Z n , q < n < p ,

1 < k , x2 < q ,

x
x
y
y1 = (x1 ) 2 mod p , y2 = ( x2 ) 1 mod p , y = ( y1 ) 2 mod p ,

Z = (x1 ) mod p


,

u = ( y × E −1 + 1) × (k − x 2 × y 2 × Z × E −1 )mod q

,

−1

k

−1

× ( x1 )
−1

× ( x1 )

E −1 . y . E −1 +1

)

× ( x1 )

E −1 . x2 . y2 . Z

mod p = ( x1 )

−1

(


.k . y

(

−1

) .(y. E

−1

−1

= ( x1 ) × ( x1 )

− x2 . y2 . Z . E

−1

−1

−1

)

(

)

k . y . E −1 +1


(

) .(y. E

) × (x

−1

+1

1

k

mod p

2

− E −1 . y . E −1 +1

× ( x1 )

− x2 . y2 . Z . E . y . E +1

× ( x1 )

× ( x1 )

−1


. x2 . y2 . Z . E −1 . y

−1

)E

E . x 2 . y2 . Z

k

= ( x1 ) mod p = Z

−1

+1

)

. x2 . y2 . Z

mod p

mod p

(3.10)

Thay (3.1), (3.3), (3.5), (3.7) và (3.10) vào (3.8)
ta lại có:
u. y


Điều cần chứng minh ở đây là: Cho p, q là 2 số

,

2

− x2 . y2 . Z . E . y . E −1 +1

y

E = H (M )

−1

2

Z

w1 = (r ) × ( y ) mod p =

+ Tính đúng đắn của thuật tốn được đề xuất

,

−1

2

× x1


else {return false }

x1 = α ( p −1)/ q mod p

−1

2

E −1 . (u . y + x2 . y2 . Z )
−1

1<α < p ,

v

Z = r × s mod p = ( x1 ) × ( x1 ) mod p

= ( x1 )

u . y + x2 . y2 . Z

= ( x1 )

x . y2 . Z

× ( x1 ) 2

mod p


(3.11)

mod p

Với:
−1

u = ( y × E −1 + 1) × (k − x2 × y 2 × Z × E −1 )mod q

Từ (3.9) và (3.11) suy ra điều cần chứng minh:

A=B
+ Mức độ an tồn của thuật tốn được đề xuất
Mức độ an tồn của lược đồ mới đề xuất có thể
7


Hội thảo lần thứ III: Một số vấn đề chọn lọc về an tồ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

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.
[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.
[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.
[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
Statistics,
04/2008;
12(3).
DOI:
10.3844/jmssp.2008.222.225 Source:DOAJ.
[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.
[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.
[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.
[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.
[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.
[1]

Tương tự MTA 18.9 – 01, mức độ an tồn của
thuật tố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.
- 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:

(s )E ≡ (r )y × ( y )( r.s ) mod p mod p


(3.12)

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:

(s )E ≡ a (s.r ) mod p mod p

(3.13)

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:

(r )y ≡ (b )(r. s ) mod p mod p

(3.14)

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 tốn
DLRP.
III. KẾT LUẬN
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 tố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 tố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 tốn chữ ký số có độ an tồn

cao cho các ứng dụng trong thực tế.

8


Hội thảo lần thứ III: Một số vấn đề chọn lọc về an tồn an ninh thơng tin – Đà Nẵng, 07/12/2018

9