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

ao 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: 1 k q , tính giá trị R theo công thức: 
 R g k mod p (1.2) 
 2. Tính thành phần E theo công thức: 
 E H(M || R)mod q (1.3) 
 3. Tính thành phần S theo công thức: 
 S x 1 k E mod q (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: 
 U g E (y)S mod p (1.5) 
 2. Tính giá trị V theo công thức: 
 V H(M || U) mod q (1.6) 
 3. Kiểm tra nếu V E 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 q | (p 1) , g ( p 1) / q mod p với: 
 x k
1 p , H : 0,1 Zn với: q n p, 1 x,k q, y g mod p , R g mod p , , 
S x 1 (k E)modq . Nếu: U g E yS mod p và V H(M || U) mod q thì: V E . 
 III. THẬT VẬY, TỪ (1.1), (1.3), (1.4) VÀ (1.5) TA CÓ: 
 E S E x.x 1.(k E)
 U g y mod p g g mod p (1.7) 
 g E k E mod p g k mod p
 Từ (1.2) và (1.7), suy ra: U R (1.8) 
 Thay (1.8) vào (1.6) ta được: 
 V H M || U mod q H(M || R)mod q (1.9) 
 Từ (1.3) và (1.9), suy ra: 
 Đâ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: | p | 512bit , | q | 160bit . 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: 
 E H((g E y S mod p) || M)modq (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: 
 x
 A , xB (2.1) 
 yA g mod p yB g mod p
 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: M B {IDB ,RQ,T1,...} 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:1 kB q , tính giá trị RB theo công thức: 
 kB
 RB g mod p (2.2) 
 3. Tính thành phần EB theo công thức: 
 EB H(M B || RB )modq (2.3) 
 4. Tính thành phần SB theo công thức: 
 1
 SB xB kB EB modq (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ị RB theo công thức: 
 .EB SB
 RB g yB mod p (2.5) 
 2. Tính giá trị EB theo công thức: 
 EB H(M B || RB )modq (2.6) 
 3. Kiểm tra nếu EB EB 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:1 kA q , tính giá trị RA theo công thức: 
 kA
 RA g mod p (2.7) 
 5. Tính thành phần thứ nhất của chữ ký: 
 EA H(M || RA )modq (2.8) 
 6. Tính thành phần thứ 2 của chữ ký: 
 1
 S A xA k A EA modq (2.9) 
 7. Tính bản mã C: 
 kA (2.10) 
 C M RB mod p
 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ị theo công thức: 
 RA
 EA SA
 RA g yA mod p (2.11) 
 2. Giải mã bản tin nhận được: 
 kB (2.12) 
 M C RA mod p
 3. Tính giá trị theo công thức: 
 E A
 (2.13) 
 EA H(M || RA )mod q
 4. Kiểm tra nếu thì khẳng định (E ,S ) là chữ ký hợp lệ của A và : . 
 EA EA A A M M
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: q | (p 1) , 1 p , g ( p 1)/ q mod p , 
 x
H : 0,1 Z với: q n p , , A , xB , , , 
  n 1 xA, xB q yA g mod p yB g mod p 1 k A ,kB q 0 M p 1
 , kB , , , , 1 , 
M B {IDB , RQ,T1,...} RB g mod p EB H(M B || RB )modq SB xB kB EB modq
 , . Nếu: , thì: , và nếu: 
 kB
 , M C RA mod p , thì: và . 
 Chứng minh: 
 V. THẬT VẬY, từ (2.1), (2.3), (2.4) và (2.5) ta có: 
 1
 EB SB EB xB . xB . kB EB 
 RB g yB mod p g g mod p (2.14) 
 g EB kB EB mod p g kB mod p
 Từ (2.2) và (2.14), suy ra: RB RB (2.15) 
 Thay (2.15) vào (2.6) ta được: 
 EB H M B || RB modq H(M B || RB )modq (2.16) 
 Từ (2.8) và (2.16), suy ra điều cần chứng minh: . 
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ó: 
 S 1
 EA A EA xA. xA . kA EA EA kA EA kA (2.17) 
 RA g yA mod p g g mod p g mod p g mod p
 Thay (2.10), (2.14) và (2.17) vào (2.12) ta có điều cần chứng minh: 
 k k k
 B A kA B
 M C RA mod p M RB mod p g mod p mod p (2.18) 
 M g kA.kB g kA.kB mod p M
 Mặt khác, từ (2.2) và (2.17) suy ra: (2.19) 
 RA RA
 Thay (2.18) và (2.19) vào (2.13) ta được: 
 (2.20) 
 EA H(M || RA)modq H(M || RA)mod q
 Từ (2.8) và (2.20) suy ra điều cần chứng minh: . 
 EA EA
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ị: g kA .kB mod p . Những gì mà C có được ở đây là: 
g k A mod p và g kB mod p . Về lý thuyết , có thể có cách sử dụng tri thức về và để tính . 
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:1 kA q , tính giá trị RA theo công thức: 
 kA
 RA g mod p (3.1) 
 2. Tính thành phần thứ nhất của chữ ký: 
 EA H(M || RA )modq (3.2) 
 3. Tính thành phần thứ 2 của chữ ký: 
 1
 S A xA k A EA modq (3.3) 
 4. Tính bản mã C: 
 kA
 C M yB mod p (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ị theo công thức: 
 RA
 EA SA
 RA g yA mod p (3.5) 
 2. Giải mã bản tin nhận được: 
 xB
 M C RA mod p (3.6) 
 3. Tính giá trị theo công thức: 
 E A
 EA H(M || RA )mod q (3.7) 
 4. Kiểm tra nếu thì khẳng định (EA,SA) là chữ ký hợp lệ của A và : M M . B tạo thông báo xác nhận: 
 M B IDB , ACK,T2 ,..., 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:1 kB q , tính giá trị RB theo công thức: 
 kB
 RB g mod p (3.8) 
 6. Tính thành phần EB theo công thức: 
 EB H(M || M B || RB )modq (3.9) 
 7. Tính thành phần SB theo công thức: 
 1
 SB xB kB EB modq (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ị RB theo công thức: 
 .EB SB
 RB g yB mod p (3.11) 
 2. Tính giá trị EB theo công thức: 
 EB H(M || M B || RB )modq (3.12) 
 3. Kiểm tra nếu EB EB 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: q | (p 1) , 1 p , g ( p 1)/ q mod p , 
 x k
H : 0,1 Z với: q n p , , A , xB , , , A , 
  n 1 xA, xB q yA g mod p yB g mod p 1 k A ,kB q 0 M p 1 RA g mod p
 1 kA
EA H(M || RA )mod q , S A xA k A EA modq , C M yB mod p , M B IDB , ACK,T2 ,..., , 
 S xB
 , . Nếu: EA A , , 
EB H(M B || RB )modq RA g yA mod p M C RA mod p
 thì: và , và nếu: , thì: . 
EA H(M || RA )modq EA EA M M EB H(M B || RB )modq
 Chứng minh: 
 Từ (2.1 ) và (3.3 ), ta có: 
 S 1
 EA A EA xA. xA . kA EA EA kA EA kA (3.13) 
 RA g yA mod p g g mod p g mod p g mod p
 Thay (2.1), (3.4) và (3.13) vào (3.6) ta có điều cần chứng minh: 
 x x
 B kA kA B
 M C RA mod p M yB mod p g mod p mod p (3.14) 
 M g kA.xB g kA.xB mod p M
 Mặt khác, từ (3.1) và (3.13) suy ra: RA RA (3.15) 
 Thay (3.14) và (3.15) vào (3.7) ta được: 
 EA H(M || RA)modq H(M || RA)mod q (3.16) 
 Từ (3.2) và (3.16) suy ra điều cần chứng minh: 
 VII. TỪ (2.1) VÀ (3.10), TA CÓ: 
 1
 EB SB EB xB . xB . kB EB 
 RB g yB mod p g g mod p (3.17) 
 g EB kB EB mod p g kB mod p
 Từ (3.8) và (3.17), suy ra: RB RB (3.18) 
 Thay (3.18) vào (3.12) ta được: 
 EB H M B || RB modq H(M B || RB )modq (3.19) 
 Từ (3.9) và (3.19), suy ra điều cần chứng minh: . 
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 
 k .x
nếu tính được: g A B mod p từ : g k A mod p và g xB mod p . Như vậy, C cũng không có cách nào để tính 
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.