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

Hệ mật khóa cơng khai dựa trên tính khó của việc giải đồng thời
2 bài tốn phân tích số và logarit rời rạc/khai căn
A Public – Key Cryptosystem Based on Difficulty of Simultaneous Solving
Two Factorization and Discrete Logarithm/Root Problems
Lưu Hồng Dũng
Khoa CNTT
Học Viện KTQS
Hà Nội, Việt Nam
e-mail:

Abstract— Bài báo đề xuất một hệ mật khóa cơng khai
xây dựng dựa trên tính khó của việc giải đồng thời 2

bài tốn phân tích một số ngun lớn ra các thừa số
nguyên tố với bài toán logarit rời rạc trên Zp hoặc
bài tốn khai căn trên Zn. Vì thế, các thuật toán mật
mã và chữ ký của hệ mật mới đề xuất có thể đáp
ứng được các yêu cầu về độ an toàn cao của các ứng
dụng trong thực tế.
Keywords: Digital Signature Algorithm, Public – Key
Cryptography Algorithm, Key Exchange Protocol, Public
– Key CryptoSystem, Discrete Logarithm Problem,
Integer Factoring Problem.

I.

ĐẶT VẤN ĐỀ

Nâng cao độ an tồn cho các thuật tốn mật mã

khóa cơng khai và chữ ký số dựa trên tính khó của
việc giải đồng thời 2 bài tố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 [1–8]. Trong [9–22] nhóm tác giả đã đề
xuất một số thuật tốn mật mã khóa cơng khai và
chữ ký số xây dựng trên bài tốn phân tích số, khai
căn 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 thuật tốn trước
một số dạng tấn cơng trong thực tế, nhóm tác giả
tiếp tục đề xuất một hệ mật khóa cơng khai được
phát triển từ các kết quả trước đó [9–19] dựa trên
tính khó của việc giải đồng thời 2 bài tốn phân tích
một số nguyên lớn ra các thừa số nguyên tố (bài
tốn phân tích số) với bài tốn logarit rời rạc trên Zp
, với p là 1 số nguyên tố (bài toán logarit rời rạc trên
Zp) hoặc bài toán khai căn trên vành Zn, ở đây:
n = p × q , với p và q là 2 số nguyên tố (bài toán

Nguyễn Vĩnh Thái
Viện CNTT
Viện KH và CN QS
Hà Nội, Việt Nam
e-mail:

khai căn trên Zn). Hệ mật được đề xuất ở đây bao
gồm thuật tốn mật mã khóa cơng khai, thuật tốn
chữ ký số, thuật tốn mã hóa – xác thực và 1 giao
thức trao đổi khóa cho các hệ mật khóa đối xứng,
các thuật tốn của hệ mật này được thiết kế để các
thực thể cuối (người sử dụng) trong cùng một hệ

thống có thể sử dụng chung một bộ tham số (tham
số miền) do nhà cung cấp dịch vụ chứng thực số tạo
ra.
II.

XÂY DỰNG HỆ MẬT KHÓA CƠNG KHAI
DỰA TRÊN 2 BÀI TỐN KHĨ

A. Một số bài tốn khó ứng dụng trong mật mã
1) Bài tốn phân tích số
Bài tốn phân tích số được phát biểu như sau:
Cho số n ∈ N , hãy tìm biểu diễn:
e
e
n = p1e . p2e ... pi ... pk , với: ei ≥ 1 và pi là các số
nguyên tố.
1

2

i

k

Một trường hợp riêng của bài tốn phân tích số
được ứng dụng để xây dựng hệ mật RSA [23] mà ở
đó n là tích của hai số nguyên tố p và q. Khi đó, bài
tốn phân tích số hay cịn gọi là bài tốn phân tích
số hay cịn gọi là bài tốn IFP(n) được phát biểu như
sau:

Bài toán IFP(n): Với mỗi số nguyên dương n,
hãy tìm số nguyên tố p hoặc q thỏa mãn phương
trình sau: p × q = n
Giải thuật cho bài tốn IFP(n) có thể được viết
như một thuật tốn tính hàm IFP(.) với biến đầu vào
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

là n, còn giá trị hàm là p hoặc q của phương trình
sau: p = IFP(n ) hoặc: q = IFP (n )
Trong hệ mật RSA, bài toán phân tích số được
sử dụng trong việc hình thành cặp khóa cơng khai/bí
mật cho mỗi thực thể ký. Với việc giữ bí mật các
tham số (p, q) thì việc tính được khóa bí mật (d) từ
khóa cơng khai (e) và modulo n là một bài tốn khó
nếu p, q được chọn đủ lớn và mạnh. Hiện tại bài
toán trên vẫn được coi là bài tốn khó do chưa có
giải thuật thời gian đa thức hay đa thức xác suất cho
nó và hệ mật RSA là một minh chứng thực tế cho
tính khó giải của bài tốn này. Trong thực tế, các
tham số p, q có thể chọn theo FIPS 186 – 4 [24] của
Hoa Kỳ cho hệ mật RSA.
2) Bài toán khai căn trên Zn
Cho cặp số nguyên dương (n,e) với n là tích 2
số nguyên tố p và q sao cho bài tốn phân tích số là
khó giải trên Zn, còn e là một giá trị thỏa mãn:
và: gcd( e,ϕ ( n)) = 1 , ở đây:
1 < e < ϕ ( n)

ϕ ( n) = ( p − 1).(q − 1) . Khi đó, bài tốn khai căn trên
Zn hay còn gọi là RSAP(n,e) được phát biểu như sau:
Bài toán RSAP(n,e): Với mỗi số nguyên dương

y ∈ Z n∗ , hãy tìm x thỏa mãn phương trình sau:
x e mod n = y

Giải thuật cho bài tốn RSAP(n,e) có thể được
viết như một thuật tốn tính hàm RSAP(n,e)(.) với
biến đầu vào là y, còn giá trị hàm là x của phương
trình sau:

g x mod p = y

Giải thuật cho bài tốn DLP(p,g) có thể được viết
như một thuật tốn tính hàm DLP(p,g)(.) với biến đầu
vào là y, cịn giá trị hàm là x của phương trình sau:
x = DLP( p, g ) ( y )

Bài toán DLP(p,g) là cơ sở để xây dựng nên hệ
mật ElGamal [25]. Hiện tại chưa có giải thuật hiệu
quả (thời gian đa thức hay đa thức xác suất) cho
DLP(p,g) và độ an toàn của thuật toán DSA trong
chuẩn chữ ký số DSS của Hoa Kỳ [23] là một minh
chứng thực tế cho tính khó giải của bài tốn này.
B. Xây dựng hệ mật khóa cơng khai dựa trên tính
khó của việc giải 2 bài tốn phân tích số và
logarit rời rạc/khai căn
1) Thuật tốn hình thành tham số và khóa
Các tham số hệ thống hay tham số miền được

nhà cung cấp dịch vụ chứng thực số hình thành
bằng thuật tốn như sau:
Thuật tốn 1.1: Hình thành tham số hệ thống.
Input: lp, lq – độ dài (tính theo bit) của các
số nguyên tố p, q.
Output: p, q, g.
[1]. Chọn 1 cặp số p, q nguyên tố với:
len(p) = lp, len(q)= lq sao cho: q|(p – 1).
[2]. Chọn g là phần tử sinh của nhóm Zp*
theo:

x = RSAP( n ,e ) ( y )

Bài toán RSAP(n,e) cũng là một cơ sở quan trọng
để xây dựng nên hệ mật RSA. Ở hệ mật RSA nếu
giải được RSAP(n,e), kẻ thám mã có thể tìm được bản
rõ (M) từ bản mã (C) và các tham số công khai (n,e),
hoặc dễ dàng tạo được chữ ký giả mạo (S) cho một
bản tin bất kỳ (M) mà khơng cần biết khóa bí mật (d)
của đối tượng ký (bị mạo danh). Tuy nhiên, hiện tại
vẫn chưa có giải thuật thời gian đa thức cho bài tốn
này và do đó việc tấn cơng hệ mật RSA bằng việc
giải RSAP(n,e) là vẫn chưa khả thi.
3) Bài toán logarit rời rạc trên Zp
Cho cặp số nguyên dương (p,g) với p là số
nguyên tố, còn g là một phần tử của nhóm Zp*. Khi
đó, bài tốn logarit rời rạc trên Zp hay cịn gọi là bài
tốn DLP(p,g) được phát biểu như sau:
Bài toán DLP(p,g): Với mỗi số nguyên dương


y ∈ Z ∗p , hãy tìm x thỏa mãn phương trình sau:

g =α

p −1
q

mod p , với: α ∈ (1, p ) .

Chú thích:
+ len(.): hàm tính độ dài (theo bit) của một
số.
Mỗi thực thể cuối/người sử dụng trong hệ thống
hình thành khóa của mình bằng thuật tốn như sau:
Thuật tốn 1.2: Hình thành khóa.
Input: p, q , g, lp1 và lq1 - độ dài (tính theo
bit) của số các nguyên tố p1 và q1.
Output: x1, x2, φ(n), y.
[1]. Chọn 1 cặp số p1, q1 là các số nguyên tố
với: len(p1) = lp1, len(q1)= lq1
[2]. Tính: n = p1. q1 , nếu: n ≤ p thì thực hiện
lại từ bước [1].

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

[3]. Tính: φ(n) = (p1 – 1).( q1 – 1)


[1]. Người nhận sử dụng khóa bí mật thứ hai

để tính

[4]. Chọn khóa bí mật thứ nhất x1 trong khoảng
(1, q).

y=g

[2]. Người nhận sử dụng khóa bí mật thứ
nhất của mình để giải mã bản tin nhận
được:
x
(2.5)
m = C × (R ) 1B mod nB
[3]. Chuyển giá trị m thành bản tin M.

(1.1)

mod p

nếu:
hoặc:
y ≥ ϕ (n)
gcd( y, ϕ (n)) ≠ 1 thì thực hiện lại từ bước [4].
Kiểm

tra

[6]. Tính khóa bí mật thứ hai theo:

−1

b) Tính đúng đắn của thuật toán

(1.2)

x2 = y mod ϕ ( n )
∗

[7]. Chọn hash function H: {0,1} → Z h , với:

x1B được chọn ngẫu nhiên trong khoảng (1, q ) , còn
( x2 B , y B ) được tính theo (1.1) và (1.2) như sau:
−1

mod p, x2 B = ( y B ) mod ϕ (n B )

(2.1)

a) Thuật toán mã hóa và giải mã
Thuật tốn 2.1: Thuật tốn mã hóa.
Input: p, q , g, nB , yB, M.
Output: C,R.
[1]. Biểu diễn bản tin cần mã hóa M thành
một giá trị m tương ứng trong khoảng
[0, p – 1], chọn ngẫu nhiên một giá trị k
trong khoảng (1,q) rồi tính thành phần
thứ nhất của bản mã:
k
(2.2)

C = m × ( y B ) mod p
[2]. Tính thành phần thứ 2 của bản mã:
y
k
(2.3)
R = (g ) mod p mod n B
[3]. Gửi bản mã (C,R) cho B.

)

B

Thuật toán 2.2: Thuật toán giải mã.
Input: p, q , g, x1B , x2B, nB , yB, (C,R).
Output: M .

n> p,

1 < α < p , g = α ( p −1) / q mod p ,

−1
mod p , x2 B = ( y B ) mod ϕ ( nB ) ,

− x1 B

0 ≤ M ≤ p − 1 , C = M × ( y B )k mod p ,

R = (g k mod p ) mod n B .
yB


Thuật toán mật mã được đề xuất ở đây bao gồm
thuật tốn mã hóa (Thuật toán 2.1) và giải mã
(Thuật toán 2.2), với các tham số hệ thống được
hình thành theo Thuật tốn 1.1 và khóa hình thành
theo Thuật tốn 1.2. Giả thiết người gửi/mã hóa là
A, người nhận/giải mã là B và B có cặp khóa bí
mật/cơng khai tương ứng là ( x1B , x2 B , y B ) , trong đó:

(

n = p1 × q1 ,

1< k < q ,

2) Thuật tốn mật mã khóa cơng khai

y B = (g )

Điều cần chứng minh ở đây là: Cho p, q, p1, q1
là các số nguyên tố thỏa mãn:
q | ( p − 1) ,
1 < x1B < q , y B = g

| q |≤| h |< p .

− x1 B

(2.4)

x


R = (R ) 2 B mod n B

[5]. Tính khóa công khai theo:
− x1

R theo:

Nếu: R = (R )x mod nB , M = C × (R )x1 B mod p ,
thì: M = M .
2B

Chứng minh:
Thật vậy, từ (2.3) và (2.4) ta có:

(R )

x1 B

=

mod p =

( (R )

yB

mod n B

((


=  g k mod p


((

)
= (g mod p )
= g k mod p

)

x2 B

mod n B

mod n B

y B . x2 B

x1 B

k

yB

)

)


x2 B

mod n B

)

)

x1 B

mod p

mod n B 


x1 B

(2.6)

x1 B

mod p

mod p

mod p

= g k . x1 B mod p

Nên từ (2.1), (2.2), (2.5) và (2.6) ta có điều cần

chứng minh:
M = C × (R ) 1 B mod p
x

(

) (
k

)

= M × g − x1 B mod p × g k . x1B mod p mod p
=M ×g

− k . x1 B

×g

x1 B

mod p = M

c) Mức độ an tồn của thuật tốn
+ Tấn cơng khóa bí mật
Ở thuật tốn mới đề xuất, khóa bí mật là cặp
(x1,x2), tính an tồn của lược đồ sẽ bị phá vỡ khi cặp
khóa này có thể tính được bởi một hay các đối
tượng không mong muốn. Từ Thuật tốn 1.2 cho
thấy, để tìm được x2 cần phải tính được tham số
φ(n), nghĩa là phải giải được IFP(n), cịn để tính

được x1 cần phải giải được DLP(p,g). Như vậy, để
tìm được cặp khóa bí mật này kẻ tấn công cần phải
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

giải được bài tốn IFP(n) và DLP. Nói cách khác, độ
an tồn về khóa của thuật tốn được đảm bảo bằng
độ khó của việc giải đồng thời 2 bài tốn IFP(n) và
DLP(p,g).
+ Tấn cơng thám mã bản tin
Để giải mã bản tin có thể thực hiện tấn cơng
vào thuật tốn mã hóa hoặc giải mã như sau:
- Tấn cơng thuật tốn mã hóa
Từ (2.2) có thể giải mã bản tin nếu tính được k
như sau: m = C.( y B )− k mod p
Để tính được k từ (2.3) đầu tiên cần phải giải
được bài toán khai căn RSAP(n,e) để tìm:
X = RSAP( n , y ) (R ) hoặc giải bài tốn phân tích số để
B

a) Thuật tốn ký và kiểm tra chữ ký
Thuật toán 3.1: Sinh chữ ký.
Input: p, q, g, φ(n), x1, x2, M – bản tin cần
ký.
Output: (E,S) – chữ ký.
[1]. Chọn ngẫu nhiên giá trị k trong khoảng
(1, q)
(3.2)

[2]. Tính giá trị: R = g k mod p
[3]. Tính thành phần thứ nhất của chữ ký
theo: E = H (M || R) mod q
(3.3)
[4]. Tính thành phần thứ 2 của chữ ký theo:
S = x2 × ((k + x1 × E ) mod q ) mod φ (n) (3.4)
Chú thích:
+ Tốn tử “||” là phép nối 2 xâu bit.

B

tìm x2 B rồi tìm X: X = (R )x mod nB . Sau đó phải
giải tiếp bài tốn logarit rời rạc DLP(p,g) để tìm:
k = DLP( p, g ) ( X ) .
2B

Như vậy, để giải mã bản tin bằng cách tấn công
trực tiếp vào thuật tốn mã hóa, kẻ tấn cơng cần
phải giải được đồng thời hai bài toán RSAP(n,e) và
DLP(p,g) đã chỉ ra ở trên. Như vậy, độ an tồn của
thuật tốn trước dạng tấn cơng này được quyết định
bằng độ khó của việc giải đồng thời 2 bài toán: bài
toán khai căn trên Zn và bài toán logarit rời rạc trên
Zp, hoặc: bài tốn phân tích số và bài tốn logarit rời
rạc trên Zp.
- Tấn cơng thuật tốn giải mã
Để giải mã bản tin bằng cách tấn cơng vào thuật
tốn giải mã, kẻ tấn cơng cần phải tính được các
khóa bí mật của người nhận B, nghĩa là phải giải
được đồng thời hai bài tốn IFP(n) và DLP(p,g). Như

vậy, độ an tồn của thuật tốn trước dạng tấn cơng
này được quyết định bằng độ khó của việc giải đồng
thời 2 bài tốn phân tích số và bài tốn logarit rời
rạc trên Zp.
3) Thuật toán chữ ký số
Thuật toán chữ ký số được đề xuất ở đây bao
gồm thuật toán ký (Thuật toán 3.1) và kiểm tra
(Thuật toán 3.2), với các tham số hệ thống được
hình thành theo Thuật tốn 1.1 và khóa hình thành
theo Thuật tốn 1.2. Giả thiết người ký ở đây có
cặp khóa khóa bí mật/cơng khai tương ứng là
( x1 , x2 , y) , trong đó: x1 được chọn ngẫu nhiên trong
khoảng (1, q ) , còn ( x2 , y ) được tính theo (1.1) và
(1.2) như sau:
−x
y = ( g ) mod p
−1
x2 = ( y ) mod ϕ (n)
1

(3.1)

Thuật toán 3.2: Kiểm tra chữ ký.
Input: p, q, g, y, n, M – bản tin cần thẩm tra.
Output: (E,S) = true/false.
[1]. Tính giá trị:
y
E
(3.5)
R = (g S ) mod n × ( y ) mod p

[2]. Tính giá trị:
(3.6)
E = H (M || R ) mod q

(

)

[3]. Nếu: E = E thì: (E,S) = true, ngược lại:
(E,S) = false
Chú thích:
+ (E,S) = true: chữ ký hợp lệ, bản tin M được
xác thực về nguồn gốc và tính tồn vẹn.
+ (E,S) = false: chữ ký hoặc/và bản tin bị giả
mạo.
b) Tính đúng đắn của thuật tốn
Điều cần chứng minh ở đây là: Cho p, q, p1, q1
là các số nguyên tố thỏa mãn: q | ( p − 1) , n = p1 × q1 ,
n > p , 1 < α < p , g = α ( p −1) / q mod p , 1 < x1 < q ,
−1
y = g − x mod p , x 2 = ( y ) mod ϕ (n) , 1 < k < q ,
1

với: | q |≤| h |<| p | ,
E = H ( M || S ) mod q , S = x2 × ((k + x1 × E ) mod q ) mod φ ( n) .
Nếu: R = (g S )y mod n × ( y )E mod p , E = H (M || R ) mod q
thì: E = E .
Chứng minh:
R = g mod p , H : {0,1} a Z h
∗


k

(

)

Thật vậy, từ (3.1), (3.2), (3.4) và (3.5) ta có:

((

R = gS

(
= (g (
= g
=g

)

y

E

x2 .( k + x1 . E )

×g

) (
mod n )× g

y

mod n × g − x1 mod p

k + x1 . E ). x2 . y

k + x1E

)

mod n × ( y ) mod p

− x1E

− x1 . E

)

E

mod p

(3.7)

mod p

mod p = g k mod p = R

Từ (3.3), (3.6) và (3.7) suy ra điều cần chứng
minh:

E = H ( M || R ) mod q = H ( M || R ) mod q = E

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

c) Mức độ an tồn của thuật tốn

[3]. Tính thành phần thứ 2 của bản mã:

+ Tấn cơng khóa bí mật
Ở thuật tốn chữ ký mới đề xuất, khóa bí mật
của một đối tượng ký ngồi cặp (x1,x2) tương tự như
ở thuật tốn mật mã (mục 2), cịn bao gồm tham số
φ(n). Như vậy, độ an tồn về khóa của thuật tốn
được đảm bảo bằng độ khó của việc giải đồng thời 2
bài tốn IFP(n) và DLP(p,g).
+ Tấn cơng giả mạo chữ ký
Từ điều kiện của Thuật toán 3.2, một cặp (E,S)
bất kỳ sẽ được coi là chữ ký hợp lệ của đối tượng sở
hữu các tham số công khai (n,y) lên bản tin M nếu
thỏa mãn:
y
E
(3.8)
E = H M || (g S ) mod n × ( y ) mod p
Từ (3.8) dễ thấy rằng, nếu H(.) được chọn là
hàm băm có tính kháng va chạm cao (SHA
256/512,...) thì việc tạo ngẫu nhiên được cặp (E,S)

thỏa mãn điều kiện của thuật tốn kiểm tra là khơng
khả thi trong các ứng dụng thực tế.
4) Thuật tốn mã hóa – xác thực

( ((

)

nhiên trong khoảng (1, q ) , còn ( x2 A , y A ) và ( x2 B , y B )
được tính theo (1.1) và (1.2) như sau:
−1

− x1 A

mod p, x2 A = ( y A ) mod ϕ (n A )

− x1 B

mod p, x2 B = ( y B ) mod ϕ (n B )

yB = (g )

(4.1)

−1

a) Thuật tốn mã hóa và giải mã

Thuật toán 4.2: Thuật toán giải mã.
Input: p,q,g,x1B,x2B,nA,yA,nB,yB,(C,E,S).

Output: M, (E,S) = true/false.
[1]. Người nhận sử dụng khóa bí mật thứ hai
để tính

Input: p,q, g,x1A,x2A,nB,yB,M.

((

)

B

)

yA

E

)

(4.7)

mod n A × ( y A ) mod p

[3]. Người nhận sử dụng khóa bí mật thứ
nhất của mình để giải mã bản tin nhận
được: m = C × (R )x1 B mod nB
(4.8)
[4]. Chuyển giá trị m thành bản tin M và
tính giá trị: E = H ( M || R ) mod q (4.9)

[5]. Nếu: E = E thì: M = M và khằng định
người gửi là A.
b) Tính đúng đắn của thuật toán

Điều cần chứng minh ở đây là: Cho p, q, p1, q1
là các số nguyên tố thỏa mãn: q | ( p − 1) ,

n = p1 × q1 ,

n > p, 1 < α < p , g = α ( p −1) / q mod p ,
1 < x1 A , x1B < q , y A = g − x1 A mod p , y B = g − x mod p ,
−1
−1
x2 A = ( y A ) mod ϕ ( n A ) , x2 B = ( y B ) mod ϕ ( nB ) ,
1 < k < q , 0 ≤ M ≤ p −1 ,
R = g k mod p ,
1B

(

k

C = M × ( y B ) mod p

)

yB

∗
mod nB , H : {0,1} a Z h với:


,

,
E = H (M || R) mod q
.
Nếu:
S = x2 A × ((k + x1 A × E ) mod q ) mod φ ( n A )

x
C = (C ) 2 B mod n B ,

(

R = gS

)

)

E
mod n A × ( y A ) mod p ,

yA

mod p , E = H ( M || R ) mod q thì: E = E .

M = C × (R )

[1]. Biểu diễn bản tin cần mã hóa M thành một

giá trị m tương ứng trong khoảng [0,p–1],
chọn ngẫu nhiên một giá trị k trong khoảng
(1,q) rồi tính thành phần thứ nhất của bản
mã:
y
k
(4.2)
C = m × ( y B ) mod p mod nB
k
[2]. Tính giá trị: R = g mod p
(4.3)

2B

R = gS

x1 B

Output: C,E,S.

C theo: C = (C )x mod nB (4.6)

[2]. Tính giá trị:

| q |≤| h |<| p |

Thuật tốn 4.1: Thuật tốn mã hóa.

(


[5]. Gửi bản mã (C,E,S) cho B.

))

Thuật tốn mã hóa – xác thực được đề xuất ở
đây thực hiện đồng thời chức năng bảo mật thơng
tin và xác thực nguồn gốc cũng như tính tồn vẹn
của bản tin được mã hóa, thuật tốn được đề xuất
bao gồm thuật tốn mã hóa (Thuật tốn 4.1) và giải
mã (Thuật toán 4.2), với các tham số hệ thống
cũng được hình thành theo Thuật tốn 1.1 và khóa
hình thành theo Thuật tốn 1.2. Giả thiết người
gửi/mã hóa là A, người nhận/giải mã là B có cặp
khóa bí mật/cơng khai tương ứng là ( x1 A , x2 A , y A ) và
( x1B , x2 B , y B ) , trong đó: ( x1 A , x1B ) được chọn ngẫu

y A = (g )

(4.4)
E = H (M || R) mod q
[4]. Tính thành phần thứ 3 của bản mã:
S = x2 A × ((k + x1 A × E ) mod q ) mod φ ( n A ) (4.5)

Chứng minh:
Từ (4.2) và (4..6) ta có:
C = (C ) 2 B mod nB
x

(


= M × ( y B ) mod p

(

k

(

)

yB

)

k

mod n B

= M × g − x1B mod p mod p
=M ×g

− x1 B .k

)

)

x2 B

y B . x2 B


mod n B

(4.10)

mod nB

mod p

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

Từ (4.1), (4.5) và (4.7) ta lại có:

((

)

R = gS

(
= (g (

yA

Thuật tốn 5.1: Thuật tốn trao đổi khóa.

)


mod n A × ( y A ) mod p
E

) × (g
mod n )× g

= g x2 A .( k + x1 A .E ) mod n
k + x1 A . E ). x2 A . y A

yA

− x1 A

− x1 A . E

mod p

)

E

mod p

(4.11)

Output: KAB, KBA.

mod p


Bước 1:
+ A thực hiện:
1 – Chọn ngẫu nhiên một giá trị kA thỏa
mãn: 1 < k A < q , tính giá trị RA theo công

= g k + x1 A . E × g − x1 A .E mod p = g k mod p

Từ (4.8), (4.10) và (4.11) suy ra:
x
M = C × (R ) mod p
1B

(

= M × g − x1 B .k × g k mod p

)

x1 B

mod p

Input: p,q, g,x1A,x2A, x1B,x2B,nA,yA, nB,yB.

(4.12)

= M × g − x1 B .k × g x1 B .k mod p = M

Từ (4.3), (4.4), (4.9), (4.11) và (4.12) suy ra
điều cần chứng minh:

E = H ( M || R ) mod q = H ( M || R) mod q = E

thức: R A = (g k A mod p ) B mod nB (5.2)
2 – Gửi RA cho B.
+ B thực hiện:
1 – Chọn ngẫu nhiên một giá trị kB thỏa
mãn: 1 < kB < q , tính giá trị RB theo công
y

thức: RB = (g k mod p ) mod n A (5.3)
2 – Gửi RB cho A.
Bước 2:
+ A thực hiện:
1 – Tính thành phần SA theo cơng thức:
x
(5.4)
S A = ( y B ) mod p
2 – Tính khóa bí mật chia sẻ với B theo:
k
x
(5.5)
K AB = ((RB ) mod n A ) mod p
3 – Tính thành phần EA theo cơng thức:
(5.6)
E A = H ( K AB || S A )
4 – Gửi EA cho B.
+ B thực hiện:
1 – Tính thành phần SB theo công thức:
x
(5.7)

S B = ( y A ) mod p
2 – Tính khóa bí mật chia sẻ với A theo:
k
x
(5.8)
K BA = ((R A ) mod n B ) mod p
3 – Tính thành phần EB theo cơng thức:
(5.9)
EB = H ( K BA || S B )
4 – Gửi EB cho A.
Bước 3:
+ A thực hiện:
Kiểm tra nếu: E A = E B thì khẳng định đối
tượng tham gia trao đổi khóa là B và B đã thiết lập
được khóa bí mật chia sẻ với A, sau đó A có thể
dùng khóa này để trao đổi thơng tin mật với B bằng
1 thuật tốn mật mã khóa đối xứng. Ngược lại, tra
nếu: E A ≠ EB thì khẳng định đối tượng tham gia
trao đổi khóa là giả mạo và hủy khóa đã được tạo ra.
+ B thực hiện:
Kiểm tra nếu: E A = EB thì B khẳng định đối
tượng tham gia trao đổi khóa là A và A đã thiết lập
được khóa bí mật chia sẻ với B. Ngược lại, nếu:
E A ≠ EB thì khẳng định đối tượng tham gia trao đổi
khóa là giả mạo.
yA

B

c) Mức độ an tồn của thuật tốn

Thuật tốn mã hóa – xác thực được đề xuất ở
đây thực chất là sự kết hợp giữa thuật toán mật mã ở
mục 2 với thuật tốn chữ ký ở mục 3, nhằm cung
cấp tính năng bảo mật nội dung của bản tin và xác
thực nguồn gốc cùng với tính tồn vẹn của bản tin
được thực hiện một cách đồng thời. Có một điểm
cần lưu ý là dạng tấn công giả mạo ở đây cần được
hiểu theo nghĩa một kẻ thứ 3 (C) muốn mạo danh A
để gửi cho B bản tin M. Tuy nhiên, phân tích từng
dạng tấn cơng cụ thể tương tự như với các thuật
toán ở mục 2 và 3 trên đây, đều cho thấy độ an tồn
của thuật tốn được đảm bảo bởi độ khó của việc
giải đồng thời 2 bài tốn IFP(n) và DLP(p,g) hoặc
IFP(n) và RSAP(n,e).
5) Giao thức trao đổi khóa
Giả thiết rằng 2 đối tượng tham gia truyền
thơng ở đây là A và B sử dụng một thuật toán mật
mã khóa đối xứng (DES, AES,...) để mã hóa dữ liệu
cần trao đổi với nhau, khi đó giao thức trao đổi khóa
đề xuất ở đây (Thuật tốn 5.1) được sử dụng để
thiết lập một khóa bí mật chung/chia sẻ giữa A và
B. Các tham số hệ thống cũng được hình thành theo
Thuật tốn 1.1 và khóa hình thành theo Thuật
tốn 1.2. Giả thiết A và B có các cặp khóa bí
mật/cơng khai tương ứng là ( x1 A , x2 A , y A ) và
( x1B , x 2 B , y B ) , trong đó: ( x1 A , x1B ) được chọn ngẫu
nhiên trong khoảng (1, q ) , còn ( x2 A , y A ) và ( x2 B , y B )
được tính theo (1.1) và (1.2) như sau:
−x
−1

y A = ( g ) mod p, x 2 A = ( y A ) mod ϕ ( n A )
(5.1)
1A

yB = (g )

− x1 B

−1

mod p, x 2 B = ( y B ) mod ϕ (n B )

a) Thuật toán trao đổi khóa
Việc thiết lập khóa chung giữa A và B được thực
hiện theo các bước của Thuật toán 5.1 như sau:

1A

2A

A

2B

B

1B

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

b) Tính đúng đắn của giao thức

Điều cần chứng minh ở đây là: Cho p, q, p1, q1
là các số nguyên tố thỏa mãn: q | ( p − 1) , n = p1 × q1 ,
n > p, g = α ( p −1) / q mod p , α ∈ Z *p , H : {0,1}∗ a Z h với:
| q |≤| h |<| p | ,
yB = g

1 < x1 A , x1B < q , y A = g x mod p ,
1A

,

mod p

x1 B

−1

x2 A = ( y A ) mod ϕ ( n A )

,

−1

x2 B = ( yB ) mod ϕ ( nB )


(

RA = g mod p
kA

Nếu:

)

1 < k A , kB < q

,
,

y
mod nB , RB = (g k mod p ) mod n A .

yB

B

A

S A = ( y B ) mod p , S B = ( y A )x mod p ,
xA

(
= ((R

K AB = (RB )


x2 A

mod n A

)
)

kA

B

mod p ,

E A = H ( K AB || S A ) ,

mod nB mod p , E B = H ( K BA || S B ) thì:
và
K AB = K BA
E A = EB .
Chứng minh:
Thật vậy, từ (5.3) và (5.3) ta có:

K BA

A

)

kB


x2 B

(

)

kA

x

K AB = (R B ) 2 A mod n A

((

)
= (g mod p )
= g k B mod p

y B . x2 B

kA

kB

mod p

mod n A

mod p = g


)

kA

mod p

k A .k B

(5.10)

(

x

(

)
= (g mod p )
= g k A mod p

y B . x2 A

kB

kA

)

kB


mod p

mod n B

)

kB

mod p

(5.11)

mod p = g k A .k B mod p

x

S A = ( y B ) A mod p

(

)

xA

(5.12)

mod p = g x A . xB mod p

Từ (5.1) và (5.7) ta lại có:

x

S B = ( y A ) B mod p

(

= g x A mod p

)

xB

cần phải giải được IFP(n) , cịn để tính k A từ (5.2)
trước tiên cần phải giải được bài toán phân tich số
IFP(n) rồi tính: X = (RB )x mod n A hoặc phải giải
được bài tốn khai căn RSAP(n,e) để tìm:
X = RSAP( n , y ) (RB ) . Sau đó phải giải tiếp bài toán
A

mod p

Từ (5.10) và (5.11) suy ra điều cần chứng minh
thứ nhất: K AB = K BA
Từ (5.1) và (5.4) ta có:
= g xB mod p

Để tính được khóa KAB, từ (5.5) cho thấy kẻ tấn
cơng cần phải tính được x2 A và k A . Để tính x2 A

2A


Mặt khác, từ (5.2) và (5.8) ta lại có:
K BA = (R A ) 2 B mod n B

- Tính an tồn khóa đã biết (known – key
security): việc biết một hoặc một số khóa chia sẻ
giữa A và B cũng không cho phép một đối tượng
thứ 3 nào đó có thể tính được các khóa khác cũng
được thiết lập bởi A và B.
- Tính bí mật về phía trước (forward secrecy):
việc tính các khóa bí mật chia sẻ đã được thiết lập
trước đó bởi A và B là khơng thể thực hiện được, dù
các khóa bí mật của A và B ( x1 A , x2 A , x1B , x2 B ) bị
lộ .
Các tính chất an tồn nói trên thực chất được
đảm bảo bởi mức độ an tồn của thuật tốn trước
các dạng tấn cơng:
+ Tấn cơng khóa bí mật chia sẻ:

(5.13)

mod p = g x A . xB mod p

(5.14)
Từ (5.12) và (5.13) suy ra: S A = S B
Từ (5.6), (5.9) và (5.14) suy ra điều cần chứng
minh thứ hai: E A = H ( K AB || S A ) = H ( K BA || S B ) = EB
c) Độ an toàn của giao thức
Giao thức được đề xuất bảo đảm các tính chất
của một giao thức trao đổi khóa an toàn:

- Xác thực thực thể (entity authentication): ở
giao thức này việc kiểm tra điều kiện E A = E B cho
phép các đối tượng tham gia trao đổi khóa hồn tồn
có thể xác thực được danh tính của nhau.
- Xác thực khóa hiện (explicit key
authentication): Cũng chỉ bằng việc kiểm tra điều
kiện E A = E B , A hồn tồn có thể khẳng định B đã
tạo được khóa bí mật chia sẻ với mình và B cũng có
thể khẳng định được điều tương tự như thế với A.

A

logarit rời rạc DLP(p,g) để tìm

kA :

k A = DLP( p , g ) (RA ) .

Việc tính KBA cũng phải được thực hiện các bước
tương tự như vậy. Như vậy, độ an tồn của thuật
tốn trước dạng tấn cơng khóa bí mật chia sẻ được
đảm bảo bằng tính khó của việc giải đồng thời 2 bài
toán: IFP(n) và DLP(p,g).
+ Tấn công giả mạo:
Một kẻ giả mạo C muốn mạo danh A để tạo
khóa bí mật chia sẻ với B hoặc mạo danh B để chia
sẻ khóa bí mật với A thì cần phải tính được EA hoặc
EB. Tuy nhiên, từ (5.6) và (5.9) cho thấy thực hiện
được việc đó thì kẻ tấn cơng tối thiểu phải tính được
KAB hoặc KBA. Do đó, độ an tồn của thuật tốn

trước dạng tấn cơng giả mạo cũng sẽ được đảm bảo
bằng tính khó của việc giải đồng thời 2 bài toán:
IFP(n) và DLP(p,g).
III. KẾT LUẬN
Bài báo đề xuất xây dựng một hệ mật khóa cơng
khai bao gồm các thuật tốn mã hóa, chữ ký số và
giao thức trao đổi khóa an tồn cho các hệ mật khóa
đối xứng. Qua phân tích đánh giá cho thấy các thuật
toán của hệ mật mới đề xuất có độ an tồn được đảm
bảo bằng mức độ khó của việc giải đồng thời 2 bài
toán: bài toán phân tích một số nguyên lớn ra các
thừa số nguyên tố và bài toán logarit rời rạc trên Zp,
hoặc: bài toán phân tích một số nguyên lớn ra các
thừa số nguyên tố và bài toán khai căn trên vành Zn.
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

Hồn tồn có thể khẳng định rằng khơng có bất kỳ
kiểu tấn công nào vào hệ mật thành công được mà
khơng phải giải được đồng thời 2 bài tốn khó nêu
trên, do đó hệ mật mới đề xuất có thể phù hợp với
các ứng dụng yêu cầu cao về độ an toàn trong thực
tế.
TÀI LIỆU THAM KHẢO
[1]

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.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] Lưu Hồng Dũng, Trần Trung Dũng, Tống Minh
Đức, “Nghiên cứu xây dựng hệ tích hợp mật mã khóa cơng
khai - chữ ký số”, Tạp chí Khoa học và Kỹ thuật (Học viện
KTQS), số 149 (08-2012). ISSN: 1859 - 0209., 01/08/2012.
[10] Lưu Hồng Dũng, “Phát triển thuật tốn mật mã khóa cơng
khai dựa trên hệ mật El Gamal”, Chun san Các cơng trình
nghiên cứu, phát triển và ứng dụng CNTT và TT, Bộ TT và
TT, tập V-1, số 8(28) (12-2012). ISSN: 1859 - 3526., pp. 8,
01/12/2012.
[11] Lưu Hồng Dũng, Ngô Đăng Tiến, Trần Trung Dũng, Vũ
Tất Thắng, “Phát triển một số thuật toán mật mã khóa cơng
khai”, Hội thảo quốc gia lần thứ XV: Một số vấn đề chọn
lọc của Công nghệ Thông tin và Truyền thông. Hà Nội 34/12/2012. ISBN: 978 - 604 - 67 - 0645 - 8., pp. 6,
04/12/2012.
[12] Lưu Hồng Dũng, Hồ Ngọc Duy, Nguyễn Tiền Giang and
Nguyễn Thị Thu Thủy, “ Phát triển một dạng lược đồ chữ
ký số mới”, Hội thảo quốc gia lần thứ XVI: Một số vấn đề
chọn lọc của Công nghệ Thông tin và Truyền thông, Đà
Nẵng - 11/2013. ISBN: 978 - 604 - 67 - 0645 - 8.

[13] Lưu Hồng Dũng, Hoàng Thị Mai, Nguyễn Hữu Mộng,
” Một dạng lược đồ chữ ký xây dựng trên bài tốn phân tích
số”, Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu
cơ bản và ứng dụng Công Nghệ thông tin (FAIR 2015); Hà
Nội 09-10/07/2015. ISBN: 978-604-913-397-8.

[14] Luu Hong Dung, Le Dinh Son, Ho Nhat Quang and
Nguyen
Duc
Thuy,” DEVELOPING
DIGITAL
SIGNATURE SCHEMES BASED ON DISCRETE
LOGARITHM PROBLEM”, The 8th National Conference
on Fundamental and Applied IT Research (FAIR 2015). Ha
Noi 09-10/07/2015 ISBN: 978-604-913-397-8.
[15] Lưu Hồng Dũng, Nguyễn Đức Thụy, Nguyễn Lương Bình
và Tống Minh Đức, “Phát triển thuật tốn mật mã khóa
cơng khai dựa trên bài tốn logarit rời rạc”, Hội nghị khoa
học Quốc gia lần thứ IX về Nghiên cứu cơ bản và ứng dụng
Công nghệ thông tin (FAIR 2016). ISBN: 978-604-913397-8. 2016.
[16] Lưu Hồng Dũng, Nguyễn Đức Thụy, Lê Đình Sơn và
Nguyễn Thị Thanh Thủy, “ Một phương pháp xây dựng
lược đồ chữ ký số dựa trên bài toán logarit rời rạc”, Hội
nghị khoa học Quốc gia lần thứ IX về Nghiên cứu cơ bản
và ứng dụng Công nghệ thông tin (FAIR 2016). ISBN: 978604-913-397-8. 2016.
[17] 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
tồn, an ninh thơng tin (SoIS 2016), 11/2016.
[18] 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.
[19] Nguyen Duc Thuy, Nguyen Tien Giang, Le Dinh Son and
Luu Hong Dung, “ A Design Method of Digital Signature

Scheme Based on Discrete Logarithm Problem”, IJCSNS
International Journal of Computer Science and Network
Security. Vol. 17 No. 2 pp. 214-218, February 2017. ISSN:
1738 - 7906.
[20] Lưu Hồng Dũng, Nguyễn Vĩnh Thái và Nguyễn Đức Thụy,
“ Phát triển hệ mật khóa cơng khai từ hệ mã Pohlig Hellman “, Hội thảo lần thứ II: Một số vấn đề chọn lọc về
an toàn, an ninh thông tin (SoIS 2017), Tp. HCM
03/12/2017.
[21] Phạm Văn Hiệp, Nguyễn Hữu Mộng và Lưu Hồng
Dũng,” MỘT THUẬT TOÁN CHỮ KÝ XÂY DỰNG
DỰA TRÊN TÍNH KHĨ CỦA VIỆC GIẢI ĐỒNG THỜI
HAI BÀI TỐN PHÂN TÍCH SỐ VÀ LOGARIT RỜI
RẠC “, TẠP CHÍ KHOA HỌC VÀ CƠNG NGHỆ ĐẠI
HỌC ĐÀ NẴNG, SỐ 7(128).2018. ISSN 1859-1531.
[22] Nguyễn Lương Bình, Lưu Hồng Dũng, Tống Minh
Đức, “Một phương pháp phát triển hệ mật khóa cơng khai”,
Hội nghị Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng
dụng CNTT (FAIR 2018). ISBN: 978-604-913-397-8. Hà
Nội 8/2018.
[23] R. L. Rivest, A. Shamir, and L. M. Adleman, “A Method
for Obtaining Digital Signatures and Public Key
Cryptosystems”, Commun. of the ACM, Vol. 21, No. 2,
1978, pp. 120-126.
[24] National Institute of Standards and Technology, NIST FIPS
PUB 186-4. Digital Signature Standard, U.S. Department of
Commerce, 2013.
[25] T. ElGamal, “A public key cryptosystem and a signature
scheme based on discrete logarithms”, IEEE Transactions
on Information Theory. 1985, Vol. IT-31, No. 4. pp.469–
472.


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


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

10