Phát triển thuật toán mật mã khóa công khai dựa trên bài toán logarit rời rạc

Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX “Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR'9)”; Cần Thơ, ngày 4-5/8/2016 
DOI: 10.15625/vap.2016.00072 
PHÁT TRIỂN THUẬT TOÁN MẬT MÃ KHÓA CÔNG KHAI DỰA TRÊN 
BÀI TOÁN LOGARIT RỜI RẠC 
Lƣu Hồng Dũng1, Nguyễn Đức Thụy 2, Nguyễn Lƣơng Bình 3, Tống Minh Đức 4 
1
 Khoa CNTT, Học viện Kỹ thuật Quân sự 
2 
Khoa CNTT, Cao đẳng Kinh tế - Kỹ thuật Tp. Hồ Chí Minh 
3
 Khoa CNTT, Học viện Kỹ thuật Quân sự 
4 Khoa CNTT, Học viện Kỹ thuật Quân sự 
luuhongdung@gmail.com, thuyphulam2013@gmail.com, nluongbinh@yahoo.co.uk, ductm08@gmail.com 
TÓM TẮT— Bài báo đề xuất xây dựng thuật toán mật mã khóa công khai dựa trên tính khó của bài toán logarit rời rạc trên trường 
hữu hạn. Ngoài khả năng bảo mật thông tin, thuật toán mới đề xuất còn có thể xác thực tính toàn vẹn và nguồn gốc của bản tin được 
bảo mật, từ đó có thể chống lại các dạng tấn công giả mạo đã biết trong thực tế. Ngoài ra, thuật toán còn được thiết kế để hỗ trợ khả 
năng tương tác giữa các đối tượng tham gia trao đổi thông tin mật phù hợp với các yêu cầu đặt ra trong các ứng dụng thực tế. 
Từ khóa— Mật mã khóa công khai, thuật toán mật mã khóa công khai, thuật toán chữ ký số, bài toán logarit rời rạc. 
I. ĐẶT VẤN ĐỀ 
Các thuật toán mật mã khóa công khai điển hình được sử dụng trong thực tế hiên nay như RSA [1] hay 
ElGamal [2] đều không có cơ chế xác thực nguồn gốc cũng như tính toàn vẹn của bản tin nhận được nên không có khả 
năng chống lại các tấn công giả mạo trong thực tế kiểu như tấn công “Man- in- the- Middle” [3]. Ngoài ra, các thuật 
toán kiểu này cũng không hỗ trợ khả năng tương tác giữa các bên tham gia trao đổi thông tin mà các ứng dụng trong 
thực tế thường yêu cầu. 
Trong bài báo này, nhóm tác giả đề xuất xây dựng thuật toán mật mã khóa công khai được tích hợp chữ ký số 
cho phép khả năng bảo mật và xác thực thông tin một cách đồng thời, có thể chống lại các dạng tấn công giả mạo một 
cách hiệu quả. Hơn nữa, thuật toán mới đề xuất còn được thiết kế dưới dạng một giao thức cho khả năng tương tác giữa 
các bên tham gia trao đổi thông tin nhằm phù hợp với yêu cầu của các ứng dụng trong thực tế. Đây là những vấn đề mà 
trên thực tế chưa có các kết quả nghiên cứu tương ứng được công bố. 
II. PHÁT TRIỂN THUẬT TOÁN MẬT MÃ KHÓA CÔNG KHAI 
A. Xây dựng thuật toán cơ sở 
Thuật toán cơ sở ở đây là một thuật toán chữ ký số được xây dựng dựa trên tính khó của bài toán logarit rời rạc 
trên trường hữu hạn theo phương pháp chỉ ra trong [4] và được sử dụng để xây dựng các thuật toán mật mã khóa công 
khai có khả năng bảo mật và xác thực thông tin ở phần sau. 
1. Bài toán logarit rời rạc 
Bài toán logarit rời rạc – DLP (Discrete Logarithm Problem) 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 ℤp
*
. Với mỗi số nguyên dương y ℤp
*
, hãy tìm x thỏa mãn phương trình: 
 ypg x mod 
Ở đây, 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. Dễ thấy rằng, nếu x là khóa bí mật thì việc tính khóa công 
khai y từ x và các tham số hệ thống {p,g} là một việc hoàn toàn dễ dàng. Nhưng điều ngược lại thì rất khó thực hiện, 
nghĩa là từ y và {p,g} thì việc tính được khóa bí mật x là không khả thi trong các ứng dụng thực tế. Cần chú ý rằng, 
theo [5] và [6] để bài toán logarit rời rạc là khó thì p cần phải được chọn đủ lớn với: |p| ≥512 bit. 
2. Lược đồ cơ sở 
Lược đồ cơ sở ở đây - ký hiệu MTA 16.5 – 01 là một lược đồ chữ ký số bao gồm các thủ tục hình thành tham số 
và khóa, thủ tục hình thành chữ ký và thủ tục xác minh chữ ký như sau: 
a) Thủ tục hình thành tham số hệ thống và khóa 
Thủ tục bao gồm các bước như sau: 
1. Sinh 2 số nguyên tố lớn và mạnh: p và q, sao cho: )1(| pq hay: 1 qNp , với N là một số nguyên 
dương. 
2. Chọn pg qp mod/)1( , là phần tử sinh có bậc q của nhóm 
*
pZ , ở đây: 
*
pZ . 
3. Khóa riêng x được hình thành bằng cách chọn số nguyên thỏa mãn: qx 1 . 
584 PHÁT TRIỂN THUẬT TOÁN MẬT MÃ KHÓA CÔNG KHAI DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC 
4. Khóa công khai được tính theo công thức: 
 pgy x mod (1.1) 
5. Lựa chọn hàm băm:  nZH 
1,0: với: pnq 
6. Công khai các giá trị: p, g, y. Giữ bí mật: x. 
b) Thủ tục hình thành chữ ký 
Dữ liệu đầu vào bao gồm khóa bí mật x của người ký và bản tin cần ký M. Thủ tục bao gồm các bước như sau: 
1. Chọn ngẫu nhiên một giá trị k thỏa mãn: qk 1 , tính giá trị R theo công thức: 
 pgR k mod (1.2) 
2. Tính thành phần E theo công thức: 
 qRMHE mod)||( (1.3) 
3. Tính thành phần S theo công thức: 
 qEkxS mod1 (1.4) 
Chú ý: 
- Chữ ký do lược đồ tạo ra với bản tin M ở đây là cặp (E,S). 
- Toán tử “||” sử dụng trong (1.3) là phép ghép nối 2 xâu ký tự/bit. 
c) Thủ tục xác minh tính hợp lệ của chữ ký 
Dữ liệu đầu vào bao gồm khóa công khai y của người ký và bản tin cần thẩm tra M. Thủ tục bao gồm các bước 
như sau: 
1. Tính giá trị U theo công thức: 
 pygU SE mod)( (1.5) 
2. Tính giá trị V theo công thức: 
 qUMHV mod)||( (1.6) 
3. Kiểm tra nếu EV thì chữ ký (E, S) hợp lệ và bản tin M được công nhận về nguồn gốc và tính toàn vẹn. 
d) Tính đúng đắn của lược đồ MTA 16.5 – 01 
Điều cần chứng minh ở đây là: cho p, q là 2 số nguyên tố thỏa mãn điều kiện )1(| pq , pg qp mod/)1( với: 
p 1 ,  nZH 
1,0: với: pnq , qkx ,1 , pgy x mod , pgR k mod , qRMHE mod)||( , 
qEkxS mod)(1 . Nếu: pygU
SE mod và qUMHV mod)||( thì: EV . 
III. THẬT VẬY, TỪ (1.1), (1.3), (1.4) VÀ (1.5) TA CÓ: 
pgpg
pggpygU
kEkE
EkxxESE
modmod
modmod ).(.
1
 (1.7) 
Từ (1.2) và (1.7), suy ra: RU (1.8) 
Thay (1.8) vào (1.6) ta được: 
 qRMHqUMHV mod)||(mod|| (1.9) 
Từ (1.3) và (1.9), suy ra: EV 
Đây là điều cần chứng minh. 
a) Mức độ an toàn của lược đồ MTA 16.5 – 01 
Mức độ an toàn của một lược đồ chữ ký số nói chung được đánh giá qua các khả năng: 
- Chống tấn công làm lộ khóa mật. 
- Chống tấn công giả mạo chữ ký. 
Về khả năng chống tấn công làm lộ khóa mật: Từ (1.1) cho thấy mức độ an toàn xét theo khả năng chống tấn 
công làm lộ khóa mật của thuật toán cơ sở phụ thuộc vào mức độ khó giải của bài toán logarit rời rạc. Cần chú ý rằng, 
Lưu Hồng Dũng, Nguyễn Đức Thụy, Nguyễn Lương Bình, Tống Minh Đức 585 
để bài toán DLP là khó thì các tham số {p,q,g} có thể được lựa chọn tương tự như DSA [5] hay GOST R34.10-94 [6], 
với: bitp 512|| , bitq 160|| . Ngoài ra, giá trị k cũng không được phép sử dụng lại ở các lần ký khác nhau nhằm 
ngăn chặn khả năng tấn công khóa mật từ (1.4) trong thủ tục hình thành chữ ký của lược đồ. 
Về khả năng chống tấn công giả mạo chữ ký: Từ (1.3), (1.5) và (1.6) của thuật toán cơ sở cho thấy, một cặp 
(E,S) bất kỳ sẽ được công nhận là chữ ký hợp lệ của đối tượng sở hữu khóa công khai y lên bản tin M nếu thỏa mãn 
điều kiện: 
qMpygHE SE mod)||)mod(( (1.10) 
 Có thể thấy rằng việc tìm được một cặp (E,S) giả mạo thỏa mãn (1.10) là một dạng bài toán khó chưa có lời giải 
nếu các tham số {p,q,n} được chọn đủ lớn để phương pháp “vét cạn” (Brute force) là không khả thi trong các ứng dụng 
thực tế. 
B. Xây dựng thuật toán mật mã khóa công khai 
Mục này đề xuất xây dựng 2 dạng thuật toán khác nhau. Để phù hợp với các ứng dụng thực tế, dạng thứ nhất 
được thiết kế với giả thiết rằng 2 đối tượng A và B tham gia quá trình trao đổi thông tin bí mật theo các bước như sau: 
- B yêu cầu A gửi cho mình một bản tin M. 
- A kiểm tra yêu cầu nhận được, nếu đúng là B yêu cầu, A sẽ tạo dấu xác nhận của mình lên M và mã 
hóa bản tin M rồi gửi cho B. 
- B giải mã bản tin nhận được, kiểm tra tính hợp lệ của dấu xác nhận do A tạo với bản tin nhận được, 
nếu dấu xác nhận hợp lệ thì khẳng định bản tin nhận được chính là bản tin M mà B yêu cầu từ A. 
Dạng thứ nhất có thể sử dụng phù hợp trong những trường hợp mà ở đó vai trò của A và B là ngang nhau, bên 
gửi chỉ đáp ứng khi bên nhận yêu cầu trước. Cũng có thể coi yêu cầu của B là sự cho phép bên gửi (A) mã hóa bản tin 
trong những trường hợp B có mức độ ưu tiên cao hơn. 
Ở dạng thứ hai, quá trình trao đổi thông tin giữa 2 đối tượng A và B được giả thiết như sau: 
- A mã hóa bản tin M, đồng thời tạo dấu xác nhận bản tin M rồi gửi cho B. 
- B giải mã bản tin nhận được và kiểm tra tính hợp lệ của dấu xác nhận mà A tạo ra với bản tin nhận 
được, nếu dấu xác nhận của A hợp lệ B sẽ tạo và gửi một thông báo xác nhận của mình tới A. 
- A kiểm tra thông báo xác nhận của B để biết bản tin M đã được gửi an toàn đến B. 
Dạng thứ hai có thể được sử dụng trong những trường hợp vai trò của bên gửi cao hơn, A có thể gửi bản tin bất 
cứ khi nào cần và B phải có trách nhiệm phản hồi thông báo xác nhận để A biết quá trình trao đổi thông tin đã hoàn tất. 
Trong cả 2 dạng thuật toán này, lược đồ chữ ký cơ sở MTA 16.5 – 01 được sử dụng để tạo và kiểm tra dấu xác 
nhận của A cũng như thông báo xác nhận của B. 
1. Thuật toán MTA 16.5 – 02 
Thuật toán thứ nhất – ký hiệu MTA 16.5 – 02, được đề xuất ở đây bao gồm thủ tục hình thành tham số hệ thống 
tương tự như lược đồ cơ sở MTA 16.5 – 01, trong đó khóa bí mật của A và B là xA và xB, các khóa công khai tương 
ứng yA và yB được tính theo: 
 pgy AxA mod , pgy
Bx
B mod (2.1) 
IV. VÀ CÁC THỦ TỤC YÊU CẦU, THỦ TỤC MÃ HÓA VÀ GIẢI MÃ NHƢ SAU: 
a) Thủ tục yêu cầu: Được thực hiện bởi đối tượng B, bao gồm các bước như sau: 
1. Tạo bản tin yêu cầu A: ,...},,{ 1TRQIDM BB trong đó: IDB là định danh của B, RQ là yêu cầu về bản tin M 
và T1 là nhãn thời gian,... 
2. Chọn ngẫu nhiên một giá trị kB thỏa mãn: qkB 1 , tính giá trị RB theo công thức: 
 pgR BkB mod (2.2) 
3. Tính thành phần EB theo công thức: 
 qRMHE BBB mod)||( (2.3) 
4. Tính thành phần SB theo công thức: 
 qEkxS BBBB mod
1
 (2.4) 
5. Gửi (MB,EB,SB) cho đối tượng A. 
586 PHÁT TRIỂN THUẬT TOÁN MẬT MÃ KHÓA CÔNG KHAI DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC 
b) Thủ tục mã hóa: Được thực hiện bởi A, bao gồm các bước như sau: 
1. Tính giá trị 
BR theo công thức: 
 pygR BB SB
E
B mod
. (2.5) 
2. Tính giá trị 
BE theo công thức: 
 qRMHE BBB mod)||( (2.6) 
3. Kiểm tra nếu 
BB EE thì (EB,SB) là hợp lệ và MB là do B tạo ra để yêu cầu A gửi bản tin M. Khi đó A sẽ 
ký lên và mã hóa bản tin M rồi gửi cho B theo các bước sau: 
4. Chọn ngẫu nhiên một giá trị kA thỏa mãn: qkA 1 , tính giá trị RA theo công thức: 
 pgR AkA mod (2.7) 
5. Tính thành phần thứ nhất của chữ ký: 
 qRMHE AA mod)||( (2.8) 
6. Tính thành phần thứ 2 của chữ ký: 
 qEkxS AAAA mod
1
 (2.9) 
7. Tính bản mã C: 
 pRMC AkB mod (2.10) 
8. Gửi (C,EA,SA) cho B. 
c) Thủ tục giải mã: Được thực hiện bởi B, bao gồm các bước như sau: 
1. Tính giá trị 
AR theo công thức: 
 pygR AA SA
E
A mod 
 (2.11) 
2. Giải mã bản tin nhận được: 
 pRCM BkA mod
 (2.12) 
3. Tính giá trị 
AE theo công thức: 
 qRMHE AA mod)||( (2.13) 
4. Kiểm tra nếu 
AA EE thì khẳng định (EA,SA) là chữ ký hợp lệ của A và : MM . 
d) Tính đúng đắn của MTA 16.5 – 02 
Điều cần chứng minh ở đây là: Cho: p, q là 2 số nguyên tố thỏa mãn: )1(| pq , p 1 , pg qp mod/)1( , 
  nZH 
1,0: với: pnq , qxx BA ,1 , pgy A
x
A mod , pgy
Bx
B mod , qkk BA ,1 , 10 pM , 
,...},,{ 1TRQIDM BB , pgR B
k
B mod 
, pgR AkA mod , qRMHE BBB mod)||( , qRMHE AA mod)||( , qEkxS BBBB mod
1
 , 
 qEkxS AAAA mod
1
 , pRMC AkB mod . Nếu: pygR BB
S
B
E
B mod
. , qRMHE BBB mod)||( thì: BB EE , và nếu: 
 pygR AA SA
E
A mod 
 , pRCM BkA mod
 , qRMHE AA mod)||( thì: AA EE và MM . 
Chứng minh: 
V. THẬT VẬY, từ (2.1), (2.3), (2.4) và (2.5) ta có: 
pgpg
pggpygR
BBBB
BBBBBBB
kEkE
EkxxES
B
E
B
modmod
modmod
..
1
 (2.14) 
Từ (2.2) và (2.14), suy ra: 
BB RR (2.15) 
Thay (2.15) vào (2.6) ta được: 
 qRMHqRMHE BBBBB mod)||(mod|| (2.16) 
Từ (2.8) và (2.16), suy ra điều cần chứng minh: 
BB EE . 
Lưu Hồng Dũng, Nguyễn Đức Thụy, Nguyễn Lương Bình, Tống Minh Đức 587 
Từ (2.1 ) và (2.9 ), ta có: 
 pgpgpggpygR AAAAAAAAAAA kEkEEkxxESA
E
A modmodmodmod
..
1
 (2.17) 
Thay (2.10), (2.14) và (2.17) vào (2.12) ta có điều cần chứng minh: 
MpggM
ppgpRMpRCM
BABA
B
AAB
kkkk
kkk
B
k
A
mod
modmodmodmod
..
 (2.18) 
Mặt khác, từ (2.2) và (2.17) suy ra: 
AA RR (2.19) 
Thay (2.18) và (2.19) vào (2.13) ta được: 
 qRMHqRMHE AAA mod)||(mod)||( (2.20) 
Từ (2.8) và (2.20) suy ra điều cần chứng minh: 
AA EE . 
a) Mức độ an toàn của MTA 16.5 – 02 
Độ an toàn về khả năng bảo mật thông tin được mã hóa: Từ (2.10) và (2.12) cho thấy một kẻ thứ 3 không mong 
muốn nào đó (C) có thể giải mã được bản tin nếu tính được giá trị: pg BA kk mod. . Những gì mà C có được ở đây là: 
pg A
k
mod và pg Bk mod . Về lý thuyết , có thể có cách sử dụng tri thức về pg Ak mod và pg Bk mod để tính pg BA
kk
mod
. . 
Nhưng hiện tại, chưa có cách nào để tính mà không phải giải bài toán DLP. 
Độ an toàn về khả năng chống tấn công giả mạo: Thuật toán được thiết kế dưới dạng một giao thức, các thủ tục 
mã hóa và giải mã chỉ được thực hiện khi danh tính của A, B và yêu cầu về việc trao đổi thông tin giữa 2 đối tượng 
được xác thực. Việc xác thực được thực hiện bằng lược đồ chữ ký MTA 16.5 – 01, như vậy độ an toàn của thuật toán 
xét theo khả năng chống tấn công giả mạo được quyết định bởi mức độ an toàn của lược đồ cơ sở MTA 16.5 – 01. 
2. Thuật toán MTA 16.5 – 03 
VI. THUẬT TOÁN THỨ HAI – KÝ HIỆU MTA 16.5 – 03, THỦ TỤC HÌNH THÀNH THAM SỐ HỆ THỐNG 
VÀ KHÓA TƢƠNG TỰ NHƢ MTA 16.5 – 02, THUẬT TOÁN BAO GỒM CÁC THỦ TỤC MÃ HÓA, 
GIẢI MÃ VÀ THỦ TỤC KIỂM TRA THÔNG BÁO XÁC NHẬN NHƢ SAU: 
a) Thủ tục mã hóa: được thực hiện bởi A, bao gồm các bước sau: 
1. Chọn ngẫu nhiên một giá trị kA thỏa mãn: qkA 1 , tính giá trị RA theo công thức: 
 pgR AkA mod (3.1) 
2. Tính thành phần thứ nhất của chữ ký: 
 qRMHE AA mod)||( (3.2) 
3. Tính thành phần thứ 2 của chữ ký: 
 qEkxS AAAA mod
1
 (3.3) 
4. Tính bản mã C: 
 pyMC AkB mod (3.4) 
5. Gửi (C,EA,SA) cho B. 
b) Thủ tục giải mã: được thực hiện bởi B, bao gồm các bước sau: 
1. Tính giá trị 
AR theo công thức: 
 pygR AA SA
E
A mod 
 (3.5) 
2. Giải mã bản tin nhận được: 
 pRCM BxA mod
 (3.6) 
3. Tính giá trị 
AE theo công thức: 
 qRMHE AA mod)||( (3.7) 
4. Kiểm tra nếu 
AA EE thì khẳng định (EA,SA) là chữ ký hợp lệ của A và : MM . B tạo thông báo xác nhận: 
 ,...,, 2TACKIDM BB , trong đó: IDB là định danh của B, ACK là nội dung xác nhận về bản tin M và T2 là 
nhãn thời gian,... Sau đó B ký lên thông báo xác nhận này rồi gửi cho A theo các bước sau: 
588 PHÁT TRIỂN THUẬT TOÁN MẬT MÃ KHÓA CÔNG KHAI DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC 
5. Chọn ngẫu nhiên một giá trị kB thỏa mãn: qkB 1 , tính giá trị RB theo công thức: 
 pgR BkB mod (3.8) 
6. Tính thành phần EB theo công thức: 
 qRMMHE BBB mod)||||( (3.9) 
7. Tính thành phần SB theo công thức: 
 qEkxS BBBB mod
1
 (3.10) 
8. Gửi (MB,EB,SB) cho đối tượng A. 
c) Thủ tục kiểm tra thông báo xác nhận của B: được thực hiện bởi A, bao gồm các bước sau: 
1. Tính giá trị 
BR theo công thức: 
 pygR BB SB
E
B mod
. (3.11) 
2. Tính giá trị 
BE theo công thức: 
 qRMMHE BBB mod)||||( (3.12) 
3. Kiểm tra nếu 
BB EE thì thì (EB,SB) là hợp lệ và B đã nhận đúng bản tin M. 
d) Tính đúng đắn của MTA 16.5 – 03 
Điều cần chứng minh ở đây là: Cho: p, q là 2 số nguyên tố thỏa mãn: )1(| pq , p 1 , pg qp mod/)1( , 
  nZH 
1,0: với: pnq , qxx BA ,1 , pgy A
x
A mod , pgy
Bx
B mod , qkk BA ,1 , 10 pM , pgR
Ak
A mod , 
qRMHE AA mod)||( , qEkxS AAAA mod
1
 , pyMC AkB mod , ,...,, 2TACKIDM BB , pgR B
k
B mod , 
qRMHE BBB mod)||( , qEkxS BBBB mod
1
 . Nếu: pygR AA SA
E
A mod 
 , pRCM BxA mod
 , 
qRMHE AA mod)||( thì: AA EE và MM , và nếu: pygR
BB
S
B
E
B mod
. , qRMHE BBB mod)||( thì: BB EE . 
Chứng minh: 
Từ (2.1 ) và (3.3 ), ta có: 
 pgpgpggpygR AAAAAAAAAAA kEkEEkxxESA
E
A modmodmodmod
..
1
 (3.13) 
Thay (2.1), (3.4) và (3.13) vào (3.6) ta có điều cần chứng minh: 
MpggM
ppgpyMpRCM
BABA
B
AAB
xkxk
xkk
B
x
A
mod
modmodmodmod
..
 (3.14) 
Mặt khác, từ (3.1) và (3.13) suy ra: 
AA RR (3.15) 
Thay (3.14) và (3.15) vào (3.7) ta được: 
 qRMHqRMHE AAA mod)||(mod)||( (3.16) 
 Từ (3.2) và (3.16) suy ra điều cần chứng minh: 
AA EE 
VII. TỪ (2.1) VÀ (3.10), TA CÓ: 
pgpg
pggpygR
BBBB
BBBBBBB
kEkE
EkxxES
B
E
B
modmod
modmod
..
1
 (3.17) 
Từ (3.8) và (3.17), suy ra: 
BB RR (3.18) 
Thay (3.18) vào (3.12) ta được: 
 qRMHqRMHE BBBBB mod)||(mod|| (3.19) 
Từ (3.9) và (3.19), suy ra điều cần chứng minh: 
BB EE . 
e) Mức độ an toàn của MTA 16.5 – 03 
Độ an toàn về khả năng bảo mật thông tin được mã hóa: Từ (3.4) và (3.6) cho thấy C chỉ giải mã được bản tin 
nếu tính được: pg BA
xk
mod
. từ : pg Ak mod và pg Bx mod . Như vậy, C cũng không có cách nào để tính pg BA
xk
mod
. 
ngoài việc giải bài toán DLP. 
Lưu Hồng Dũng, Nguyễn Đức Thụy, Nguyễn Lương Bình, Tống Minh Đức 589 
Độ an toàn về khả năng chống tấn công giả mạo: Tương tự như thuật toán MTA 16.5 – 02, độ an toàn của thuật 
toán đề xuất ở đây xét theo khả năng chống tấn công giả mạo cũng được quyết định bởi mức độ an toàn của lược đồ cơ 
sở MTA 16.5 – 01. 
VIII. KẾT LUẬN 
Bài báo đề xuất xây dựng 2 thuật toán mật mã khóa công khai dựa trên tính khó của bài toán logarit rời rạc. Các 
thuật toán đề xuất ở đây được thiết kế dưới dạng giao thức để phù hợp với các ứng dụng trong thực tế. Hơn nữa, các 
thuật toán này còn có cơ chế xác thực nguồn gốc và tính toàn vẹn của bản tin được mã hóa vì thế có thể chống lại các 
dạng tấn công giả mạo đã được biết đến trong thực tế. 
TÀI LIỆU THAM KHẢO 
[1] 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. 
[2] 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. 
[3] Mark Stamp, Richard M. Low, “Applicd cryptanalysis: Breaking Ciphers in the Real World”, John Wiley & Sons, Inc., ISBN 
978-0-470-1. 
[4] Luu Hong Dung, Le Dinh Son, Ho Nhat Quang, Nguyen Duc Thuy, “Developing digital signature schemes based on discrete 
logarithm problem”, Hội nghị khoa học 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). ISBN: 978-604-913-397-8, 2015. 
[5] National Institute of Standards and Technology, NIST FIPS PUB 186-3. Digital Signature Standard, U.S. Department of 
Commerce, 1994. 
[6] GOST R 34.10-94. Russian Federation Standard. Information Technology. Cryptographic data Security. Produce and check 
procedures of Electronic Digital Signature based on Asymmetric Cryptographic Algorithm. Government Committee of the 
Russia for Standards, 1994 (in Russian). 
DEVELOPING SOME PUBLIC-KEY CRYPTOGRAPHIC ALGORITHMS 
BASED ON DISCRETE LOGARITHM PROBLEM 
Luu Hong Dung, Nguyen Duc Thuy, Nguyen Luong Binh, Tong Minh Duc 
ABSTRACT— This paper proposes some public-key cryptographic algorithms based on the difficulty of the discrete logarithm 
problem. In addition to information security capabilities, the new proposed algorithm has the ability to validate the integrity and 
origin of the message is confidential. 
Keywords— Public-key cryptography, public-key cryptographic algorithm, digital signature algorithm, discrete logarithm problem.