- Trang Chủ
- An ninh - Bảo mật
- 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 toán phân tích số và logarit rời rạc/khai căn
Xem mẫu
- 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
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 toá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 Nguyễn Vĩnh Thái
Khoa CNTT Viện CNTT
Học Viện KTQS Viện KH và CN QS
Hà Nội, Việt Nam Hà Nội, Việt Nam
e-mail: luuhongdung@gmail.com e-mail: nguyenvinhthai@gmail.com
Abstract— Bài báo đề xuất một hệ mật khóa công khai khai căn trên Zn). Hệ mật được đề xuất ở đây bao
xây dựng dựa trên tính khó của việc giải đồng thời 2 gồm thuật toán mật mã khóa công khai, thuật toán
bài toán phân tích một số nguyên lớn ra các thừa số chữ ký số, thuật toán mã hóa – xác thực và 1 giao
nguyên tố với bài toán logarit rời rạc trên Zp hoặc thức trao đổi khóa cho các hệ mật khóa đối xứng,
bài toán khai căn trên Zn. Vì thế, các thuật toán mật các thuật toán của hệ mật này được thiết kế để các
mã và chữ ký của hệ mật mới đề xuất có thể đáp thực thể cuối (người sử dụng) trong cùng một hệ
ứng được các yêu cầu về độ an toàn cao của các ứng thống có thể sử dụng chung một bộ tham số (tham
dụng trong thực tế. số miền) do nhà cung cấp dịch vụ chứng thực số tạo
ra.
Keywords: Digital Signature Algorithm, Public – Key
Cryptography Algorithm, Key Exchange Protocol, Public
– Key CryptoSystem, Discrete Logarithm Problem, II. XÂY DỰNG HỆ MẬT KHÓA CÔNG KHAI
Integer Factoring Problem. DỰA TRÊN 2 BÀI TOÁN KHÓ
A. Một số bài toán khó ứng dụng trong mật mã
I. ĐẶT VẤN ĐỀ
1) Bài toán phân tích số
Nâng cao độ an toàn cho các thuật toán mật mã Bài toán phân tích số được phát biểu như sau:
khóa công khai và chữ ký số dựa trên tính khó của Cho số n ∈ N , hãy tìm biểu diễn:
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à n = p1e . p2e ... pi ... pk , với: ei ≥ 1 và pi là các số
1 2 e
i k e
nghiên cứu [1–8]. Trong [9–22] nhóm tác giả đã đề nguyên tố.
xuất một số thuật toán mật mã khóa công khai và
chữ ký số xây dựng trên bài toán phân tích số, khai Một trường hợp riêng của bài toán phân tích số
căn và logarit rời rạc. Trong bài báo này, cũng với được ứng dụng để xây dựng hệ mật RSA [23] mà ở
mục đích nâng cao độ an toàn cho thuật toán trước đó n là tích của hai số nguyên tố p và q. Khi đó, bài
một số dạng tấn công trong thực tế, nhóm tác giả toán phân tích số hay còn gọi là bài toán phân tích
tiếp tục đề xuất một hệ mật khóa công khai được số hay còn gọi là bài toán IFP(n) được phát biểu như
phát triển từ các kết quả trước đó [9–19] dựa trên sau:
tính khó của việc giải đồng thời 2 bài toán phân tích Bài toán IFP(n): Với mỗi số nguyên dương n,
một số nguyên lớn ra các thừa số nguyên tố (bài hãy tìm số nguyên tố p hoặc q thỏa mãn phương
toán phân tích số) với bài toán logarit rời rạc trên Zp trình sau: p × q = n
, 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: Giải thuật cho bài toán IFP(n) có thể được viết
n = p × q , với p và q là 2 số nguyên tố (bài toán như một thuật toá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 toà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 g x mod p = y
sau: p = IFP(n ) hoặc: q = IFP (n )
Giải thuật cho bài toán DLP(p,g) có thể được viết
Trong hệ mật RSA, bài toán phân tích số được như một thuật toán tính hàm DLP(p,g)(.) với biến đầu
sử dụng trong việc hình thành cặp khóa công khai/bí vào là y, còn giá trị hàm là x của phương trình sau:
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ừ x = DLP( p, g ) ( y )
khóa công khai (e) và modulo n là một bài toán khó Bài toán DLP(p,g) là cơ sở để xây dựng nên hệ
nếu p, q được chọn đủ lớn và mạnh. Hiện tại bài mật ElGamal [25]. Hiện tại chưa có giải thuật hiệu
toán trên vẫn được coi là bài toán khó do chưa có quả (thời gian đa thức hay đa thức xác suất) cho
giải thuật 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
nó và hệ mật RSA là một minh chứng thực tế cho chuẩn chữ ký số DSS của Hoa Kỳ [23] là một minh
tính khó giải của bài toán này. Trong thực tế, các chứng thực tế cho tính khó giải của bài toán này.
tham số p, q có thể chọn theo FIPS 186 – 4 [24] của
Hoa Kỳ cho hệ mật RSA. 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 toán phân tích số và
2) Bài toán khai căn trên Zn
logarit rời rạc/khai căn
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 toán phân tích số là 1) Thuật toán hình thành tham số và khóa
khó giải trên Zn, còn e là một giá trị thỏa mãn: Các tham số hệ thống hay tham số miền được
1 < e < ϕ ( n) và: gcd( e,ϕ ( n)) = 1 , ở đây: nhà cung cấp dịch vụ chứng thực số hình thành
ϕ ( n) = ( p − 1).(q − 1) . Khi đó, bài toán khai căn trên bằng thuật toán như sau:
Zn hay còn gọi là RSAP(n,e) được phát biểu như sau: Thuật toán 1.1: Hình thành tham số hệ thống.
Bài toán RSAP(n,e): Với mỗi số nguyên dương Input: lp, lq – độ dài (tính theo bit) của các
y ∈ Z n∗ , hãy tìm x thỏa mãn phương trình sau: số nguyên tố p, q.
x e mod n = y Output: p, q, g.
[1]. Chọn 1 cặp số p, q nguyên tố với:
Giải thuật cho bài toán RSAP(n,e) có thể được
viết như một thuật toán tính hàm RSAP(n,e)(.) với len(p) = lp, len(q)= lq sao cho: q|(p – 1).
biến đầu vào là y, còn giá trị hàm là x của phương
[2]. Chọn g là phần tử sinh của nhóm Zp*
trình sau:
theo:
x = RSAP( n ,e ) ( y ) p −1
Bài toán RSAP(n,e) cũng là một cơ sở quan trọng g =α q
mod p , với: α ∈ (1, p ) .
để xây dựng nên hệ mật RSA. Ở hệ mật RSA nếu
Chú thích:
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), + len(.): hàm tính độ dài (theo bit) của một
hoặc dễ dàng tạo được chữ ký giả mạo (S) cho một số.
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 Mỗi thực thể cuối/người sử dụng trong hệ thống
vẫn chưa có giải thuật thời gian đa thức cho bài toán hình thành khóa của mình bằng thuật toán như sau:
này và do đó việc tấn công hệ mật RSA bằng việc Thuật toán 1.2: Hình thành khóa.
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 Input: p, q , g, lp1 và lq1 - độ dài (tính theo
bit) của số các nguyên tố p1 và q1.
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 Output: x1, x2, φ(n), y.
đó, bài toán logarit rời rạc trên Zp hay còn gọi là bài [1]. Chọn 1 cặp số p1, q1 là các số nguyên tố
toán DLP(p,g) được phát biểu như sau: với: len(p1) = lp1, len(q1)= lq1
Bài toán DLP(p,g): Với mỗi số nguyên dương [2]. Tính: n = p1. q1 , nếu: n ≤ p thì thực hiện
y ∈ Z ∗p , hãy tìm x thỏa mãn phương trình sau: 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 toà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
[4]. Chọn khóa bí mật thứ nhất x1 trong khoảng để tính R theo:
(1, q). x
(2.4)
R = (R ) 2 B mod n B
[5]. Tính khóa công khai theo: [2]. Người nhận sử dụng khóa bí mật thứ
y=g − x1
mod p (1.1) nhất của mình để giải mã bản tin nhận
được:
Kiểm tra
nếu: y ≥ ϕ (n) hoặc: m = C × (R ) 1B mod nB
x
(2.5)
gcd( y, ϕ (n)) ≠ 1 thì thực hiện lại từ bước [4]. [3]. Chuyển giá trị m thành bản tin M.
[6]. Tính khóa bí mật thứ hai theo: b) Tính đúng đắn của thuật toán
−1
x2 = y mod ϕ ( n ) (1.2) Đ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) ,
∗
[7]. Chọn hash function H: {0,1} → Z h , với:
n = p1 × q1 , n> p, 1 < α < p , g = α ( p −1) / q mod p ,
1 < x1B < q , y B = g mod p , x2 B = ( y B ) mod ϕ ( nB ) ,
−1
| q |≤| h |< p . − x1 B
1< k < q , 0 ≤ M ≤ p − 1 , C = M × ( y B )k mod p ,
2) Thuật toán mật mã khóa công khai
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 toán mã hóa (Thuật toán 2.1) và giải mã Nếu: R = (R )x mod nB , M = C × (R )x1 B mod p ,
2B
(Thuật toán 2.2), với các tham số hệ thống được
thì: M = M .
hình thành theo Thuật toán 1.1 và khóa hình thành
theo Thuật toán 1.2. Giả thiết người gửi/mã hóa là Chứng minh:
A, người nhận/giải mã là B và B có cặp khóa bí
Thật vậy, từ (2.3) và (2.4) ta có:
mật/công khai tương ứng là ( x1B , x2 B , y B ) , trong đó:
(R ) x1 B
mod p =
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:
= ( (R ) yB
mod n B )
x2 B
mod n B )
x1 B
mod p
(2.6)
x1 B
− x1 B
y B = (g )
−1
mod p, x2 B = ( y B ) mod ϕ (n B ) (2.1)
((
= g k mod p ) yB
mod n B )x2 B
mod n B
mod p
a) Thuật toán mã hóa và giải mã ((
= g k mod p ) y B . x2 B
mod n B )
x1 B
mod p
= (g mod p )
x1 B
k
mod p
Thuật toán 2.1: Thuật toán mã hóa.
= g k . x1 B mod p
Input: p, q , g, nB , yB, M. Nên từ (2.1), (2.2), (2.5) và (2.6) ta có điều cần
Output: C,R. chứng minh:
M = C × (R ) 1 B mod p
x
[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 (
= M × g − x1 B mod p × g k . x1B mod p mod p ) (
k
)
[0, p – 1], chọn ngẫu nhiên một giá trị k − k . x1 B
trong khoảng (1,q) rồi tính thành phần =M ×g ×g x1 B
mod p = M
thứ nhất của bản mã:
k
(2.2) c) Mức độ an toàn của thuật toán
C = m × ( y B ) mod p
[2]. Tính thành phần thứ 2 của bản mã: + Tấn công khóa bí mật
k
( y
R = (g ) mod p mod n B ) B
(2.3) Ở thuật toán mới đề xuất, khóa bí mật là cặp
(x1,x2), tính an toàn của lược đồ sẽ bị phá vỡ khi cặp
[3]. Gửi bản mã (C,R) cho B.
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 toán 1.2 cho
Thuật toán 2.2: Thuật toán giải mã. thấy, để tìm được x2 cần phải tính được tham số
Input: p, q , g, x1B , x2B, nB , yB, (C,R). φ(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, để
Output: M . 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 toàn an ninh thông tin – Đà Nẵng, 07/12/2018
giải được bài toán IFP(n) và DLP. Nói cách khác, độ a) Thuật toán ký và kiểm tra chữ ký
an toàn về khóa của thuật toán được đảm bảo bằng
Thuật toán 3.1: Sinh chữ ký.
độ khó của việc giải đồng thời 2 bài toán IFP(n) và
Input: p, q, g, φ(n), x1, x2, M – bản tin cần
DLP(p,g).
ký.
+ Tấn công thám mã bản tin Output: (E,S) – chữ ký.
Để giải mã bản tin có thể thực hiện tấn công [1]. Chọn ngẫu nhiên giá trị k trong khoảng
vào thuật toán mã hóa hoặc giải mã như sau: (1, q)
[2]. Tính giá trị: R = g k mod p (3.2)
- Tấn công thuật toán mã hóa
[3]. Tính thành phần thứ nhất của chữ ký
Từ (2.2) có thể giải mã bản tin nếu tính được k theo: E = H (M || R) mod q (3.3)
như sau: m = C.( y B )− k mod p [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)
Để tính được k từ (2.3) đầu tiên cần phải giải
Chú thích:
được bài toán khai căn RSAP(n,e) để tìm:
+ Toán tử “||” là phép nối 2 xâu bit.
X = RSAP( n , y ) (R ) hoặc giải bài toán phân tích số để
B B
tìm x2 B rồi tìm X: X = (R )x mod nB . Sau đó phải
2B
Thuật toán 3.2: Kiểm tra chữ ký.
giải tiếp bài toán logarit rời rạc DLP(p,g) để tìm: Input: p, q, g, y, n, M – bản tin cần thẩm tra.
k = DLP( p, g ) ( X ) . Output: (E,S) = true/false.
[1]. Tính giá trị:
Như vậy, để giải mã bản tin bằng cách tấn công (
R = (g S ) mod n × ( y ) mod p
y E
(3.5) )
trực tiếp vào thuật toán mã hóa, kẻ tấn công cần [2]. Tính giá trị:
phải giải được đồng thời hai bài toán RSAP(n,e) và E = H (M || R ) mod q (3.6)
DLP(p,g) đã chỉ ra ở trên. Như vậy, độ an toàn của
thuật toán trước dạng tấn công này được quyết định [3]. Nếu: E = E thì: (E,S) = true, ngược lại:
bằng độ khó của việc giải đồng thời 2 bài toán: bài (E,S) = false
toán khai căn trên Zn và bài toán logarit rời rạc trên Chú thích:
Zp, hoặc: bài toán phân tích số và bài toán logarit rời + (E,S) = true: chữ ký hợp lệ, bản tin M được
rạc trên Zp. xác thực về nguồn gốc và tính toàn vẹn.
+ (E,S) = false: chữ ký hoặc/và bản tin bị giả
- Tấn công thuật toán giải mã mạo.
Để giải mã bản tin bằng cách tấn công vào thuật b) Tính đúng đắn của thuật toán
toán giải mã, kẻ tấn công cần phải tính được các Điều cần chứng minh ở đây là: Cho p, q, p1, q1
khóa bí mật của người nhận B, nghĩa là phải giải là các số nguyên tố thỏa mãn: q | ( p − 1) , n = p1 × q1 ,
được đồng thời hai bài toán IFP(n) và DLP(p,g). Như
n > p , 1 < α < p , g = α ( p −1) / q mod p , 1 < x1 < q ,
vậy, độ an toàn của thuật toán trước dạng tấn công
y = g − x mod p , x 2 = ( y ) mod ϕ (n) , 1 < k < q ,
−1
này được quyết định bằng độ khó của việc giải đồng 1
thời 2 bài toán phân tích số và bài toán logarit rời R = g mod p , H : {0,1} a Z h
k
với: | q |≤| h |
- 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
c) Mức độ an toàn của thuật toán [3]. Tính thành phần thứ 2 của bản mã:
E = H (M || R) mod q (4.4)
+ Tấn công khóa bí mật
Ở thuật toán chữ ký mới đề xuất, khóa bí mật [4]. Tính thành phần thứ 3 của bản mã:
của một đối tượng ký ngoài cặp (x1,x2) tương tự như S = x2 A × ((k + x1 A × E ) mod q ) mod φ ( n A ) (4.5)
ở thuật toán mật mã (mục 2), còn bao gồm tham số
[5]. Gửi bản mã (C,E,S) cho B.
φ(n). Như vậy, độ an toàn về khóa của thuật toán
được đảm bảo bằng độ khó của việc giải đồng thời 2
bài toán IFP(n) và DLP(p,g).
Thuật toán 4.2: Thuật toán giải mã.
+ 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) Input: p,q,g,x1B,x2B,nA,yA,nB,yB,(C,E,S).
bất kỳ sẽ được coi là chữ ký hợp lệ của đối tượng sở
Output: M, (E,S) = true/false.
hữu các tham số công khai (n,y) lên bản tin M nếu
thỏa mãn: [1]. Người nhận sử dụng khóa bí mật thứ hai
( ((
E = H M || (g S ) mod n × ( y ) mod p
y E
)
(3.8) )) để tính C theo: C = (C )x mod nB (4.6) 2B
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 [2]. Tính giá trị:
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 toán kiểm tra là không R = gS (( ) yA
mod n A × ( y A ) mod p
E
) (4.7)
khả thi trong các ứng dụng thực tế. [3]. Người nhận sử dụng khóa bí mật thứ
4) Thuật toán mã hóa – xác thực nhất của mình để giải mã bản tin nhận
Thuật toán mã hóa – xác thực được đề xuất ở được: m = C × (R )x1 B mod nB (4.8)
đây thực hiện đồng thời chức năng bảo mật thông [4]. Chuyển giá trị m thành bản tin M và
tin và xác thực nguồn gốc cũng như tính toàn vẹn
tính giá trị: E = H ( M || R ) mod q (4.9)
của bản tin được mã hóa, thuật toán được đề xuất
bao gồm thuật toán mã hóa (Thuật toán 4.1) và giải [5]. Nếu: E = E thì: M = M và khằng định
mã (Thuật toán 4.2), với các tham số hệ thống người gửi là A.
cũng được hình thành theo Thuật toán 1.1 và khóa
hình thành theo Thuật toán 1.2. Giả thiết người b) Tính đúng đắn của thuật toán
gửi/mã hóa là A, người nhận/giải mã là B có cặp Điều cần chứng minh ở đây là: Cho p, q, p1, q1
khóa bí mật/công khai tương ứng là ( x1 A , x2 A , y A ) và là các số nguyên tố thỏa mãn: q | ( p − 1) ,
( x1B , x2 B , y B ) , trong đó: ( x1 A , x1B ) được chọn ngẫu
n = p1 × q1 , n > p, 1 < α < p , g = α ( p −1) / q mod p ,
nhiên trong khoảng (1, q ) , còn ( x2 A , y A ) và ( x2 B , y B )
1 < x1 A , x1B < q , y A = g − x1 A mod p , y B = g − x mod p , 1B
được tính theo (1.1) và (1.2) như sau: −1
x2 A = ( y A ) mod ϕ ( n A ) , x2 B = ( y B ) mod ϕ ( nB ) ,
−1
− x1 A −1
y A = (g ) mod p, x2 A = ( y A ) mod ϕ (n A ) (4.1) 1 < k < q , 0 ≤ M ≤ p −1 , R = g k mod p ,
− x1 B −1
yB = (g ) mod p, x2 B = ( y B ) mod ϕ (n B )
(
C = M × ( y B ) mod p
k
)yB
mod nB , H : {0,1} a Z h với:
∗
a) Thuật toán mã hóa và giải mã | q |≤| h |
- 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
Từ (4.1), (4.5) và (4.7) ta lại có: Thuật toán 5.1: Thuật toán trao đổi khóa.
((
R = gS ) yA
mod n A × ( y A ) mod p
E
) Input: p,q, g,x1A,x2A, x1B,x2B,nA,yA, nB,yB.
(4.11)
(
= g x2 A .( k + x1 A .E ) mod n ) × (g
yA − x1 A
mod p )
E
mod p
Output: KAB, KBA.
= (g ( k + x1 A . E ). x2 A . y A
mod n )× g
− x1 A . E
mod p
= g k + x1 A . E × g − x1 A .E mod p = g k mod p
Bước 1:
+ A thực hiện:
Từ (4.8), (4.10) và (4.11) suy ra: 1 – Chọn ngẫu nhiên một giá trị kA thỏa
M = C × (R ) mod p
x 1B
mãn: 1 < k A < q , tính giá trị RA theo công
(4.12) thức: R A = (g k A mod p ) B mod nB (5.2)
y
= M × g − x1 B .k × g k mod p ( ) x1 B
mod p
= M × g − x1 B .k × g x1 B .k mod p = M 2 – Gửi RA cho B.
+ B thực hiện:
Từ (4.3), (4.4), (4.9), (4.11) và (4.12) suy ra
1 – Chọn ngẫu nhiên một giá trị kB thỏa
điều cần chứng minh:
mãn: 1 < kB < q , tính giá trị RB theo công
E = H ( M || R ) mod q = H ( M || R) mod q = E
thức: RB = (g k mod p ) mod n A (5.3)
yA
B
c) Mức độ an toàn của thuật toán 2 – Gửi RB cho A.
Thuật toán mã hóa – xác thực được đề xuất ở Bước 2:
đây thực chất là sự kết hợp giữa thuật toán mật mã ở + A thực hiện:
mục 2 với thuật toán chữ ký ở mục 3, nhằm cung 1 – Tính thành phần SA theo công thức:
cấp tính năng bảo mật nội dung của bản tin và xác
x
S A = ( y B ) mod p
1A
(5.4)
thực nguồn gốc cùng với tính toàn vẹn của bản tin 2 – Tính khóa bí mật chia sẻ với B theo:
được thực hiện một cách đồng thời. Có một điểm K AB = ((RB ) mod n A ) mod p
2A x A k
(5.5)
cần lưu ý là dạng tấn công giả mạo ở đây cần được 3 – Tính thành phần EA theo công thức:
hiểu theo nghĩa một kẻ thứ 3 (C) muốn mạo danh A (5.6)
E A = H ( K AB || S 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 4 – Gửi EA cho B.
toán ở mục 2 và 3 trên đây, đều cho thấy độ an toàn + B thực hiện:
của thuật toán được đảm bảo bởi độ khó của việc 1 – Tính thành phần SB theo công thức:
giải đồng thời 2 bài toán IFP(n) và DLP(p,g) hoặc
x
S B = ( y A ) mod p
1B
(5.7)
IFP(n) và RSAP(n,e). 2 – Tính khóa bí mật chia sẻ với A theo:
K BA = ((R A ) mod n B ) mod p (5.8)
x B k
2B
5) Giao thức trao đổi khóa
3 – Tính thành phần EB theo công thức:
Giả thiết rằng 2 đối tượng tham gia truyền
EB = H ( K BA || S B ) (5.9)
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 4 – Gửi EB cho A.
cần trao đổi với nhau, khi đó giao thức trao đổi khóa Bước 3:
đề xuất ở đây (Thuật toán 5.1) được sử dụng để + A thực hiện:
thiết lập một khóa bí mật chung/chia sẻ giữa A và Kiểm tra nếu: E A = E B thì khẳng định đối
B. Các tham số hệ thống cũng được hình thành theo tượng tham gia trao đổi khóa là B và B đã thiết lập
Thuật toán 1.1 và khóa hình thành theo Thuật được khóa bí mật chia sẻ với A, sau đó A có thể
toán 1.2. Giả thiết A và B có các cặp khóa bí dùng khóa này để trao đổi thông tin mật với B bằng
mật/công khai tương ứng là ( x1 A , x2 A , y A ) và 1 thuật toán mật mã khóa đối xứng. Ngược lại, tra
( x1B , x 2 B , y B ) , trong đó: ( x1 A , x1B ) được chọn ngẫu
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.
nhiên trong khoảng (1, q ) , còn ( x2 A , y A ) và ( x2 B , y B )
+ B thực hiện:
được tính theo (1.1) và (1.2) như sau: Kiểm tra nếu: E A = EB thì B khẳng định đối
−1
y A = ( g ) mod p, x 2 A = ( y A ) mod ϕ ( n A )
−x 1A
(5.1) tượng tham gia trao đổi khóa là A và A đã thiết lập
−1
yB = (g )
− x1 B
mod p, x 2 B = ( y B ) mod ϕ (n B ) được khóa bí mật chia sẻ với B. Ngược lại, nếu:
a) Thuật toán trao đổi khóa E A ≠ EB thì khẳng định đối tượng tham gia trao đổi
khóa là giả mạo.
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:
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
b) Tính đúng đắn của giao thức - Tính an toàn khóa đã biết (known – key
security): việc biết một hoặc một số khóa chia sẻ
Điều cần chứng minh ở đây là: Cho p, q, p1, q1
giữa A và B cũng không cho phép một đối tượng
là các số nguyên tố thỏa mãn: q | ( p − 1) , n = p1 × q1 , thứ 3 nào đó có thể tính được các khóa khác cũng
n > p, g = α ( p −1) / q mod p , α ∈ Z *p , H : {0,1}∗ a Z h với: được thiết lập bởi A và B.
- Tính bí mật về phía trước (forward secrecy):
| q |≤| h |
- 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
Hoàn toàn có thể khẳng định rằng không có bất kỳ [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 toán phân tích
kiểu tấn công nào vào hệ mật thành công được mà số”, Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu
không phải giải được đồng thời 2 bài toán khó nêu cơ bản và ứng dụng Công Nghệ thông tin (FAIR 2015); Hà
trên, do đó hệ mật mới đề xuất có thể phù hợp với Nội 09-10/07/2015. ISBN: 978-604-913-397-8.
các ứng dụng yêu cầu cao về độ an toàn trong thực [14] Luu Hong Dung, Le Dinh Son, Ho Nhat Quang and
tế. Nguyen Duc Thuy,” DEVELOPING DIGITAL
SIGNATURE SCHEMES BASED ON DISCRETE
LOGARITHM PROBLEM”, The 8th National Conference
TÀI LIỆU THAM KHẢO on Fundamental and Applied IT Research (FAIR 2015). Ha
[1] Q. X. WU, Y. X. Yang and Z. M. HU, "New signature Noi 09-10/07/2015 ISBN: 978-604-913-397-8.
schemes based on discrete logarithms and factoring", [15] Lưu Hồng Dũng, Nguyễn Đức Thụy, Nguyễn Lương Bình
Journal of Beijing University of Posts and và Tống Minh Đức, “Phát triển thuật toán mật mã khóa
Telecommunications, vol. 24, pp. 61-65, January 2001. công khai dựa trên bài toán logarit rời rạc”, Hội nghị khoa
[2] Z. Y. Shen and X. Y. Yu, "Digital signature scheme based học Quốc gia lần thứ IX về Nghiên cứu cơ bản và ứng dụng
on discrete logarithms and factoring", Information Công nghệ thông tin (FAIR 2016). ISBN: 978-604-913-
Technology, vol. 28,pp. 21-22, June 2004. 397-8. 2016.
[3] Shimin Wei, “Digital Signature Scheme Based on Two [16] Lưu Hồng Dũng, Nguyễn Đức Thụy, Lê Đình Sơn và
Hard Problems”, IJCSNS International Journal of Computer Nguyễn Thị Thanh Thủy, “ Một phương pháp xây dựng
Science and Network Security, VOL.7 No.12, December lược đồ chữ ký số dựa trên bài toán logarit rời rạc”, Hội
2007. nghị khoa học Quốc gia lần thứ IX về Nghiên cứu cơ bản
[4] Eddie Shahrie Ismail, Tahat N.M.F., Rokiah. R. Ahmad, “A và ứng dụng Công nghệ thông tin (FAIR 2016). ISBN: 978-
New Digital Signature Scheme Based on Factoring and 604-913-397-8. 2016.
Discrete Logarithms”, Journal of Mathematics and [17] Lưu Hồng Dũng, Nguyễn Đức Thụy, Nguyễn Văn Phúc và
Statistics, 04/2008; 12(3). DOI: Đỗ Anh Tuấn, “Một phương pháp xây dựng thuật toán chữ
10.3844/jmssp.2008.222.225 Source:DOAJ. ký số”, Hội thảo lần thứ I: Một số vấn đề chọn lọc về an
[5] Qin Yanlin , Wu Xiaoping,“ New Digital Signature Scheme toàn, an ninh thông tin (SoIS 2016), 11/2016.
Based on both ECDLP and IFP”, Computer Science and [18] Nguyen Duc Thuy and Luu Hong Dung, “A New
Information Technology, 2009. ICCSIT 2009. 2nd IEEE Construction Method of Digital Signature Algorithms”,
International Conference on, 8-11 Aug. 2009, E-ISBN : IJCSNS International Journal of Computer Science and
978-1-4244-4520-2, pp 348 - 351. Network Security. Vol. 16 No. 12 pp. 53-57, December
[6] Swati Verma1, Birendra Kumar Sharma, “A New Digital 2016. ISSN: 1738 - 7906.
Signature Scheme Based on Two Hard Problems”, [19] Nguyen Duc Thuy, Nguyen Tien Giang, Le Dinh Son and
International Journal of Pure and Applied Sciences and Luu Hong Dung, “ A Design Method of Digital Signature
Technology, ISSN 2229 – 6107, Int. J. Pure Appl. Sci. Scheme Based on Discrete Logarithm Problem”, IJCSNS
Technol., 5(2) (2011), pp. 55-59. International Journal of Computer Science and Network
[7] Sushila Vishnoi , Vishal Shrivastava, ”A new Digital Security. Vol. 17 No. 2 pp. 214-218, February 2017. ISSN:
Signature Algorithm based on Factorization and Discrete 1738 - 7906.
Logarithm problem”, International Journal of Computer [20] Lưu Hồng Dũng, Nguyễn Vĩnh Thái và Nguyễn Đức Thụy,
Trends and Technology, volume 3, Issue 4, 2012. “ Phát triển hệ mật khóa công khai từ hệ mã Pohlig -
[8] A.N. Berezin, N.A. Moldovyan, V.A. Shcherbacov, Hellman “, Hội thảo lần thứ II: Một số vấn đề chọn lọc về
"Cryptoschemes Based on Difficulty of Simultaneous an toàn, an ninh thông tin (SoIS 2017), Tp. HCM
Solving Two Different Difficult Problems", Computer 03/12/2017.
Science Journal of Moldova, vol.21, no.2(62), 2013. [21] Phạm Văn Hiệp, Nguyễn Hữu Mộng và Lưu Hồng
[9] Lưu Hồng Dũng, Trần Trung Dũng, Tống Minh Dũng,” MỘT THUẬT TOÁN CHỮ KÝ XÂY DỰNG
Đức, “Nghiên cứu xây dựng hệ tích hợp mật mã khóa công DỰA TRÊN TÍNH KHÓ CỦA VIỆC GIẢI ĐỒNG THỜI
khai - chữ ký số”, Tạp chí Khoa học và Kỹ thuật (Học viện HAI BÀI TOÁN PHÂN TÍCH SỐ VÀ LOGARIT RỜI
KTQS), số 149 (08-2012). ISSN: 1859 - 0209., 01/08/2012. RẠC “, TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI
[10] Lưu Hồng Dũng, “Phát triển thuật toán mật mã khóa công HỌC ĐÀ NẴNG, SỐ 7(128).2018. ISSN 1859-1531.
khai dựa trên hệ mật El Gamal”, Chuyên san Các công trình [22] Nguyễn Lương Bình, Lưu Hồng Dũng, Tống Minh
nghiên cứu, phát triển và ứng dụng CNTT và TT, Bộ TT và Đức, “Một phương pháp phát triển hệ mật khóa công khai”,
TT, tập V-1, số 8(28) (12-2012). ISSN: 1859 - 3526., pp. 8, Hội nghị Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng
01/12/2012. dụng CNTT (FAIR 2018). ISBN: 978-604-913-397-8. Hà
[11] Lưu Hồng Dũng, Ngô Đăng Tiến, Trần Trung Dũng, Vũ Nội 8/2018.
Tất Thắng, “Phát triển một số thuật toán mật mã khóa công [23] R. L. Rivest, A. Shamir, and L. M. Adleman, “A Method
khai”, Hội thảo quốc gia lần thứ XV: Một số vấn đề chọn for Obtaining Digital Signatures and Public Key
lọc của Công nghệ Thông tin và Truyền thông. Hà Nội 3- Cryptosystems”, Commun. of the ACM, Vol. 21, No. 2,
4/12/2012. ISBN: 978 - 604 - 67 - 0645 - 8., pp. 6, 1978, pp. 120-126.
04/12/2012. [24] National Institute of Standards and Technology, NIST FIPS
PUB 186-4. Digital Signature Standard, U.S. Department of
[12] Lưu Hồng Dũng, Hồ Ngọc Duy, Nguyễn Tiền Giang and
Commerce, 2013.
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 đề [25] T. ElGamal, “A public key cryptosystem and a signature
chọn lọc của Công nghệ Thông tin và Truyền thông, Đà scheme based on discrete logarithms”, IEEE Transactions
Nẵng - 11/2013. ISBN: 978 - 604 - 67 - 0645 - 8. 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 toà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 toàn an ninh thông tin – Đà Nẵng, 07/12/2018
10
nguon tai.lieu . vn
