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, 03-04/12/2012 
Phát triển một số thuật toán mật mã khóa công khai 
Development of some public key cryptographic algorithms 
Lưu Hồng Dũng1, Trần Trung Dũng2, Vũ Tất Thắng3 
luuhongdung@gmail.com, ttdung@ictu.edu.vn, vtthang@ioit.ac.vn 
1
 Khoa Công nghệ Thông tin – Học viện Kỹ thuật Quân sự 
2
 Đại học CNTT và Truyền thông – Đại học Thái Nguyên 
3
 Viện Công nghệ Thông tin – Viện Khoa học và Công nghệ Việt nam 
Tóm tắt—Bài báo đề xuất một số thuật toán mật mã khóa công 
khai được phát triển từ hệ mật ElGamal. Ưu điểm của các thuật 
toán mới đề xuất là cho phép bảo mật và xác thực thông tin một 
cách đồng thời. Hơn nữa, mức độ an toàn của các thuật toán 
mới đề xuất không nhỏ hơn mức độ an toàn của thuật toán 
ElGamal. 
Từ khoáa: Public Key Cryptosystem, SignCryption 
Algorithm, Digital Signature, Hash Function. 
I. ĐẶT VẤN ĐỀ 
Thuật toán mật mã RSA [1] và ElGamal [2] là những 
thuật toán mật mã khóa công khai được biết đến và sử dụng 
phổ biến nhất trong thực tế. Nhược điểm cơ bản của các 
thuật toán này là không có cơ chế xác thực thông tin được 
bảo mật (nguồn gốc, tính toàn vẹn), vì thế nó không có khả 
năng chống lại một số dạng tấn công giả mạo trong thực tế. 
Đã có một số kết quả đạt được từ việc phát triển các thuật 
toán này nhằm khắc phục yếu điểm nói trên của nó. Trong 
[3] đề xuất một thuật toán cải tiển từ ElGamal bằng việc sử 
dụng chữ ký số để tạo cơ chế xác thực về nguồn gốc và tính 
toàn vẹn cho thông tin (bản tin, thông điệp dữ liệu, ...) được 
bảo mật. Đặc điểm của thuật toán này là chữ ký số được hình 
thành trực tiếp từ bản rõ nên chỉ phù hợp với các ứng dụng 
mà ở đó bản tin được truyền trực tiếp giữa 2 đối tượng 
gửi/mã hóa và nhận/giải mã. Do đặc điểm trên, nó bị hạn chế 
trong một số tình huống ứng dụng khi bản tin mật được 
truyền từ người gửi/mã hóa đến người nhận/giải mã phải 
chuyển tiếp qua một số khâu trung gian, mà ở đó nó cần phải 
được xác thực về nguồn gốc cũng như tính toàn vẹn trước 
khi gửi đến các khâu trung gian khác hay đến đối tượng 
nhận. Vấn đề là ở chỗ, các khâu trung gian không được phép 
biết nội dung bản tin, nhưng để xác thực được nguồn gốc và 
tính toàn vẹn của nó thì bản tin cần phải được giải mã, nghĩa 
là thông tin sẽ bị lộ ở các khâu trung gian mà lẽ ra là không 
được phép. Thuật toán thứ nhất được đề xuất ở đây cho phép 
khắc phục nhược điểm nói trên của thuật toán trong [3] nhờ 
việc hình thành chữ ký số từ bản mã chứ không phải từ bản 
rõ. Do đó, với thuật toán mới đề xuất việc giải mã bản tin 
được bảo mật là không cần thiết khi phải xác thực nguồn gốc 
và tính toàn vẹn của nó ở các khâu trung gian. Bốn thuật toán 
tiếp theo cũng được phát triển từ thuật toán ElGamal nhằm 
bảo đảm khả năng xác thực về nguồn gốc nhưng không xác 
thực về tính toàn vẹn của bản tin cũng được đề xuất ở đây. 
II. PHÁT TRIỂN MỘT SỐ THUẬT TOÁN MẬT MÃ 
KHÓA CÔNG KHAI 
A. Các thuật toán cơ sở 
Các thuật toán cơ sở ở đây bao gồm thuật toán mật mã 
khóa công khai El Gamal và thuật toán chữ ký số DSA. 
Thuật toán mật mã Elgama được đề xuất vào năm 1985, 
thuật toán này được xây dựng trên cơ sở bài toán logarith 
rời rạc và được sử dụng bởi Cơ quan An ninh Quốc gia Mỹ 
- NSA (National Security Agency). Thuật toán chữ ký số 
DSA (Digital Signature Algorithm) được phát triển từ thuật 
toán chữ ký số ElGamal. DSA được NSA đề xuất và NIST 
(National Institute of Standards and Technology) công nhận 
làm chuẩn chữ ký số của Mỹ từ năm 1994 [4]. Các thuật 
toán trên được sử dụng để phát triển một số thuật toán mật 
mã có khả năng bảo mật và xác thực thông tin một cách 
đồng thời. 
1) Thuật toán mật mã ElGamal 
Các thành viên trong hệ thống muốn trao đổi thông tin 
mật với nhau bằng thuật toán mật mã Elgamal thì trước tiên 
thực hiện quá trình hình thành khóa như sau: 
• Chọn số nguyên tố đủ lớn p sao cho bài toán logarit 
trong pZ là khó giải. 
• Chọn phần tử sinh g của nhóm ∗pZ . 
• Chọn khóa mật x là số nguyên thỏa mãn: 
( )11 −<< px . Tính khóa công khai y theo công 
thức: pgy x mod= . 
Giả sử người gửi/mã hóa là A, người nhận/giải mã là B. 
Người A có khóa bí mật là xA và khóa công khai là yA. Người 
B có khóa bí mật là xB và khóa công khai là yB. Khi đó, để 
gửi bản tin M cho B, với: pM <≤0 , người gửi A sẽ thực 
hiện các bước như sau: 
• Chọn số ngẫu nhiên k thỏa mãn: )1(1 −<< pk ; 
• Tính giá trị R theo công thức: 
pgR k mod= ; 
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, 03-04/12/2012 
• Sử dụng khóa công khai của B để tính: 
pyMC kB mod)(×= . 
• Gửi bản mã ( )RC, đến người nhận B. 
Để khôi phục bản tin ban đầu (M) từ bản mã ( )RC, 
nhận được, người nhận B thực hiện các bước như sau: 
• Tính giá trị Z theo công thức: 
pRZ mod1−= . 
• Khôi phục bản tin ban đầu (M): 
( ) pZCM Bx mod×= . 
2) Thuật toán chữ ký số DSA 
Thủ tục hình thành tham số và khóa bao gồm các bước 
thực hiện như sau: 
• Chọn cặp số nguyên tố p và q sao cho bài toán 
logarit trong pZ là khó giải và thỏa mãn: 
)1(| −pq ; 
• Chọn phg qp mod/)1( −= là phần tử sinh có bậc q 
của nhóm ∗pZ , nghĩa là: pg <<1 và: 
pg q mod1≡ . Ở đây: h là một số nguyên thỏa 
mãn: ph <<1 ; 
• Khóa bí mật x là một giá trị được chọn trong 
khoảng: qx <<1 . 
• Khóa công khai y được tính theo công thức: 
pgy x mod= . 
Thủ tục hình thành chữ ký lên bản tin M bao gồm các 
bước như sau: 
• Chọn một giá trị k thỏa mãn: qk <<1 . 
• Tính thành phần thứ nhất R của chữ ký theo công 
thức: 
 qpgR k mod)mod(= . 
• Thành phần thứ hai S của chữ ký được tính theo 
công thức: 
( ) qRxMHkS mod)(1 ×+×= − , 
 Với: |q| = 160 bit, hàm băm H(.) được chọn ở đây là 
SHA-1. 
Thủ tục kiểm tra tính hợp lệ của chữ ký bao gồm các bước 
như sau: 
• Tính giá trị: qSW mod1−= : 
• Tính giá trị: ( ) qMHWU mod.= 
• Tính giá trị: qRWV mod.= 
• Kiểm tra nếu ( ) qpygR VU modmod×= thì 
chữ ký (R,S) hợp lệ, do đó nguồn gốc và tính toàn 
vẹn của bản tin M được công nhận. 
B. Thuật toán mật mã khóa công khai phát triển dựa trên 
hệ mật ElGamal và DSA 
1) Thuật toán thứ nhất 
Thuật toán thứ nhất đề xuất ở đây được phát triển từ 
việc kết hợp thuật toán mật mã El Gamal và thuật toán chữ 
sô DSA nhằm bảo đảm các khả năng về bảo mật và xác thực 
thông tin. Ở đây thông tin được xác thực đồng thời về nguồn 
gốc cũng như tính toàn vẹn. 
a) Thủ tục hình thành tham số và khóa 
Thủ tục hình thành tham số và khóa ở đây hoàn toàn 
tương tự như ở thuật toán DSA, bao gồm các bước như sau: 
• Chọn cặp số nguyên tố p và q sao cho bài toán 
logarit trong pZ là khó giải và thỏa mãn: 
)1(| −pq ; 
• Chọn phg qp mod/)1( −= là phần tử sinh có bậc q 
của nhóm ∗pZ , với h là một số nguyên thỏa mãn: 
ph <<1 ; 
• Khóa bí mật x là một giá trị được chọn trong 
khoảng: qx <<1 . Khóa công khai y được tính 
theo công thức: pgy x mod= ; 
• Giữ bí mật: x; công khai: p, q, g, y. Khóa công khai 
y cần phải được chứng thực bởi một CA (Certificate 
Authority) đáng tin cậy. 
b) Thủ tục mã hóa 
Giả sử người gửi/mã hóa là A, người nhận/giải mã là B. 
Người gửi A có khóa bí mật là xA và khóa công khai là yA. 
Người nhận B có khóa bí mật là xB và khóa công khai là yB. 
Để gửi bản tin M cho B, với: pM <≤0 , A thực hiện các 
bước như sau: 
• Chọn giá trị kA thỏa mãn: qkA <<1 và không lặp 
lại. 
• Sử dụng khóa công khai của B để mã hóa M theo 
công thức: 
( ) pyMC AkB mod×= , 
• Tính thành phần R theo công thức: 
( ) qpgR Ak modmod= , 
• Tính thành phần S theo công thức: 
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, 03-04/12/2012 
( ) ( ) qRxCkS AA mod1 ×+×= − , 
• Gửi bản mã gồm ( )SRC ,, đến B. 
c) Thủ tục giải mã 
Từ bản mã ( )SRC ,, nhận được, B khôi phục và kiểm tra 
nguồn gốc cũng như tính toàn vẹn của bản tin ban đầu (M) 
như sau: 
• Tính giá trị nghịch đảo của S: 
 qSw mod1−= . 
• Tính giá trị u theo công thức: 
( ) qwCu mod×= , 
• Tính giá trị v theo công thức: 
( ) qwRv mod×= , 
• Tính giá trị R theo công thức: 
( ) ( ) pygR vAu mod×= , 
• Tính giá trị M theo công thức: 
( ) pRCM Bx mod×= , 
• Tính giá trị R theo công thức: 
( ) qRR mod= , 
• So sánh R với R , nếu RR = thì MM = và 
bản tin nhận được (C,R,S) có nguồn gốc từ đối 
tượng gửi A. 
d) Tính đúng đắn của thuật toán mới đề xuất 
Điều cần chứng minh ở đây là: Cho: p, q là 2 số nguyên tố 
phân biệt thỏa mãn: 
)1(| −pq , ph <<1 , 
phg qp mod/)1( −= , qxx BA << ,1 , 
pgy AxA mod= , pgy B
x
B mod= , qkA <<1 , 
( ) pyMC AkB mod×= , ( ) qpgR Ak modmod= , 
( ) ( ) qRxCkS AA mod1 ×+×= − . Νếu: 
qSw mod1−= , 
( ) qwCu mod×= , qwRv mod)( ×= ,
( ) ( ) pygR vAu mod×= , ( ) pRCM Bx mod−×= , 
( ) qRR mod= . Thì : MM = và RR = . 
Chứng minh: 
Thật vậy, ta có: 
( )( )
( ) ( )( )
( ) ( )( ) pyg
pyg
pygR
SR
A
SC
wR
A
wC
v
A
u
mod
mod
mod)(
11 −− ××
××
×=
×=
×=
Mặt khác, từ: 
( ) ( ) qRxCkS AA mod1 ×+×= − , 
Suy ra: 
( ) qRxCSk AA mod1 ×+×= − . 
Nên: 
( ) ( )
( ) ( )
( ) ( )
( ) pyg
ppgpg
pgg
pgpg
SR
A
SC
SRxSC
SRxSC
RxCSk
A
A
AA
mod
modmodmod
mod
modmod
11
11
11
1
−
−
−
−
−−
−
××
××
×××
×+×
×=




×=
×=
=
Từ đây suy ra: 
 pgR Ak mod= . 
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, 03-04/12/2012 
Do đó: 
( ) ( )( )
( )( )( )
( )( )
( )( ) ( )( )
( ) ( )
( ) MpggM
ppgpgM
ppgpgM
pppg
ppyM
ppRpC
pRCM
ABAB
ABAB
BAAB
BA
A
B
B
kxkx
kxkx
xkkx
xk
k
B
x
x
=××=
××=
××=
×
××=
×=
×=
××−
××−
−
mod
modmodmod
modmodmod
modmodmod
modmod
modmodmod
mod)(
Và: 
 ( ) ( ) RqpgqRR Ak === modmodmod . 
Đây là điều cần chứng minh. 
e) Mức độ an toàn của thuật toán mới đề xuất 
Mức độ an toàn của thuật toán mới đề xuất có thể đánh 
giá qua các khả năng: 
• Chống tấn công làm lộ khóa mật. 
• Chống thám mã. 
• Chống giả mạo nguồn gốc và nội dung bản tin . 
Có thể thấy rằng, thủ tục hình thành khóa ở thuật toán 
được đề xuất và ở các thuật toán El Gamal, DSA thực chất 
là một. Vì vậy, có thể kết luận khả năng chống tấn công làm 
lộ khóa mật của thuật toán mới đề xuất là tương đương với 
khả năng chống tấn công làm lộ khóa mật của các thuật toán 
El Gamal và DSA. 
Về khả năng chống thám mã, xét trong các trường hợp tấn 
công trực tiếp vào thuật toán mã hóa: 
( ) pyMC AkB mod×= và thuật toán giải mã: 
( ) pRCM Bx mod×= , cho thấy rằng mức độ an toàn 
của thuật toán được đề xuất và của thuật toán El Gamal là 
tương đương nhau. 
Ở thuật toán mới đề xuất, cơ chế xác thực về nguồn gốc 
và tính toàn vẹn của bản tin được thiết lập trên cơ sở các thủ 
tục hình thành và xác minh chữ ký số của thuật toán DSA. 
Vì vậy, mức độ an toàn của thuật toán mới đề xuất xét theo 
khả năng chống giả mạo nguồn gốc và nội dung bản tin là 
tương đương khả năng chống giả mạo chữ ký của thuật toán 
DSA. 
2) Thuật toán thứ 2 
Thuật toán thứ 2 đề xuất ở đây cũng được phát triển từ 
thuật toán mật mã El Gamal. Điểm khác biệt cơ bản với 
thuật toán El Gamal là ở chỗ thuật toán mới đề xuất có cơ 
chế xác thực nguồn gốc thông tin 2 chiều được thiết lập dựa 
trên việc sử dụng khóa công khai của người nhận (yB) trong 
thủ tục mã hóa và khóa công khai của người gửi (yA) trong 
thủ tục giải mã. 
a) Thủ tục hình thành tham số và khóa 
• Chọn số nguyên tố lớn p sao cho bài toán logarit 
trong pZ là khó giải. 
• Chọn g là phần tử sinh của ∗pZ . 
• Chọn khóa mật x là số nguyên thỏa mãn: 
( )11 −<< px . 
• Tính khóa công khai y theo công thức: 
pgy x mod= . 
• Giữ bí mật: x; công khai: p, q, g, y. Khóa công khai 
y cần phải được chứng thực bởi một CA (Certificate 
Authority) đáng tin cậy. 
b) Thủ tục mã hóa 
Giả sử người gửi là A, người nhận là B. Người gửi A có 
khóa bí mật là xA và khóa công khai là yA. Người nhận B có 
khóa bí mật là xB và khóa công khai là yB. Khi đó, để gửi bản 
tin M cho B, với: pM <≤0 , A sẽ thực hiện các bước như 
sau: 
• Chọn số ngẫu nhiên kA thỏa mãn: 
)1(1 −<< pk A . Tính giá trị R theo công thức: 
pgR Ak mod= . 
• Sử dụng khóa công khai của B để tính: 
pyMC AA xkB mod)( +×= . 
• Gửi bản mã gồm ( )RC, đến người nhận B. 
c) Thủ tục giải mã 
Để khôi phục bản tin ban đầu (M) từ bản mã ( )RC, 
nhận được, người nhận B thực hiện các bước như sau: 
• Tính giá trị Z theo công thức: 
( ) pyRZ A mod1−×= . 
• Khôi phục bản tin ban đầu (M): 
( ) pZCM Bx mod×= . 
d) Tính đúng đắn của thuật toán mới đề xuất 
Điều cần chứng minh ở đây là: cho p là số nguyên tố, g là 
phần tử sinh của ∗pZ , ( )1,1 −<< pxx BA , 
pgy AxA mod= , pgy B
x
B mod= , ( )11 −<< pkA , 
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, 03-04/12/2012 
( ) pyMC AA xkB mod+×= , ( ) pgR Ak mod= . Nếu: 
( ) pyRZ A mod1−×= , ( ) pZCM Bx mod×= thì: 
MM = . 
Chứng minh: 
Thật vậy, ta có: 
( )
( )( )
( )( )
( )( )
( ) ( )( )
( )( ) ( )( )
( ) ( ) MpggM
ppgpgM
pppgpg
ppgM
ppyR
pyM
pZCM
BAABAA
BAABAA
B
AA
AAB
B
AA
B
xxkxxk
xxkxxk
x
xk
xkx
x
A
xk
B
x
=××=
××=
=××
××=
=××
××=
=×=
+−+
+−+
−
+
−
+
mod
modmodmod
modmodmodmod
modmod
modmod
mod
mod
..
..
1
1
e) Mức độ an toàn của thuật toán mới đề xuất 
Ở thuật toán mới đề xuất, việc tấn công trực tiếp vào 
thủ tục mã hóa là khó khăn hơn thuật toán El Gamal, vì ở 
thuật toán này cả 2 khóa bí mật ngắn hạn (kA) và dài hạn 
(xA) của người gửi cùng được sử dụng để mã hóa bản tin. 
Do đó, việc thám mã và giả mạo, xét trong trường hợp này, 
chỉ có thể thực hiện thành công khi cả 2 khóa bí mật đồng 
thời bị lộ. Từ đây có thể thấy rằng, mức độ an toàn của 
thuật toán mới đề xuất xét theo khả năng chống thám mã và 
chống tấn công làm lộ khóa mật là không nhỏ hơn mức độ 
an toàn của thuật toán El Gamal trong khi mức độ chống giả 
mạo nguồn gốc bản tin được bảo mật lại cao hơn thuật toán 
El Gamal. 
3) Thuật toán thứ 3 
Thuật toán thứ 3 được đề xuất ở đây có cơ chế xác thực 
tương tự như thuật toán thứ hai, nhưng có cách thức thực 
hiện dưới dạng một giao thức (protocol). Ngoài ra, bản mã 
được tạo ra bởi thuật toán này chỉ có một thành phần duy 
nhất. 
a) Thủ tục hình thành tham số và khóa 
• Chọn số nguyên tố lớn p sao cho bài toán logarit 
trong pZ là khó giải. 
• Chọn g là phần tử sinh của ∗pZ . 
• Chọn khóa mật x là số nguyên thỏa mãn: 
( )11 −<< px . 
• Tính khóa công khai y theo công thức: 
pgy x mod= . 
• Giữ bí mật: x; công khai: p, q, g, y. Khóa công khai 
y cần phải được chứng thực bởi một CA (Certificate 
Authority) đáng tin cậy. 
b) Thủ tục mã hóa 
Giả sử người gửi là A, người nhận là B. Người gửi A có 
khóa bí mật là xA và khóa công khai là yA. Người nhận B có 
khóa bí mật là xB và khóa công khai là yB. Khi đó, thủ tục để 
A gửi bản tin M cho B, với: pM <≤0 , bao gồm các 
bước như sau: 
Bước 1: Đối tượng B thực hiện: 
• Chọn giá trị kB thỏa mãn: )1(1 −<< pkB . 
• Tính giá trị RB theo công thức: 
pgR BkB mod= . 
• Gửi giá trị RB cho đối tượng A. 
Bước 2: Đối tượng A thực hiện: 
• Mã hóa bản tin M theo công thức: 
( ) pyRMC AxBB mod××= . 
• Gửi bản mã C đến đối tượng nhận B. 
c) Thủ tục giải mã 
Để khôi phục bản tin ban đầu (M) từ bản mã nhận được 
(C), người nhận B thực hiện các bước như sau: 
• Tính giá trị Z theo công thức: 
( ) pyZ A mod1−= . 
• Khôi phục bản tin ban đầu (M): 
( ) pZCM BB xk mod+×= . 
d) Tính đúng đắn của thuật toán mới đề xuất 
Điều cần chứng minh ở đây là: cho p là số nguyên tố, g là 
phần tử sinh của ∗pZ , ( )1,1 −<< pxx BA , 
pgy AxA mod= , pgy B
x
B mod= , 
( )11 −<< pkB , ( ) pgR BkB mod=
( ) pyRMC AxBB mod××= . Nếu: 
( ) pyZ A mod1−= , ( ) pZCM BB xk mod+×= thì: 
MM = . 
Chứng minh: 
Thật vậy, ta có: 
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, 03-04/12/2012 
( )
( )( )
( )( )
( ) ( )( )( )
( )( )
( )( ) ( )( )
( ) ( ) MpggM
ppgpgM
pppg
ppgpgM
ppy
pyRM
pZCM
ABBABB
ABBABB
BB
A
ABB
BB
A
BB
xxkxxk
xxkxxk
xk
x
xxk
xk
A
x
BB
xk
=××=
××=
=×
×××=
=×
×××=
=×=
+−+
+−+
+
−
+
−
+
mod
modmodmod
modmodmod
modmodmod
modmod
mod
mod
..
..
1
1
e) Mức độ an toàn của thuật toán mới đề xuất 
Ở thuật toán mới đề xuất, khả năng chống thám mã xét 
trong trường hợp tấn công trực tiếp vào thủ tục mã hóa là 
tương đương với thuật toán El Gamal, nhưng thủ tục giải mã 
của thuật toán được đề xuất có khả năng chống thám mã cao 
hơn so với thuật toán El Gamal do việc sử dụng kết hợp 
đồng thời cả 2 khóa bí mật ngắn hạn (kB) và dài hạn (xB) của 
người nhận (B). 
4) Thuật toán 4 
Thuật toán thứ 4 được đề xuất ở đây cũng có cơ chế xác 
thực và cách thức thực hiện tương tự như thuật toán thứ ba, 
nhưng có mức độ an toàn xét theo khả năng chống thám mã 
và giả mạo cao hơn do thủ tục mã hóa sử dụng đồng thời 2 
khóa bí mật ngắn hạn và dài hạn của người gửi, còn thủ tục 
giải mã lại sử dụng đồng thời 2 khóa bí mật ngắn hạn và dài 
hạn của người nhận. Ở thuật toán thứ tư này, việc thám mã 
và giả mạo chỉ có thể thực hiện thành công khi bị lộ đồng 
thời cả 2 khóa bí mật ngắn hạn và dài hạn. 
a) Thủ tục hình thành tham số và khóa 
• Chọn số nguyên tố lớn p sao cho bài toán logarit 
trong pZ là khó giải. 
• Chọn g là phần tử sinh của ∗pZ . 
• Chọn khóa mật x là số nguyên thỏa mãn: 
( )11 −<< px . 
• Tính khóa công khai y theo công thức: 
pgy x mod= . 
• Giữ bí mật: x; công khai: p, q, g, y. Khóa công khai 
y cần phải được chứng thực bởi một CA (Certificate 
Authority) đáng tin cậy. 
b) Thủ tục mã hóa 
Giả sử người gửi là A, người nhận là B. Người gửi A có 
khóa bí mật là xA và khóa công khai là yA. Người nhận B có 
khóa bí mật là xB và khóa công khai là yB. Khi đó, thủ tục để 
A gửi bản tin M cho B, với: pM <≤0 , bao gồm các 
bước như sau: 
Bước 1: Đối tượng B thực hiện: 
• Chọn giá trị kB thỏa mãn: )1(1 −<< pkB . 
• Tính giá trị RB theo công thức: 
pgR BkB mod= . 
• Gửi giá trị RB cho đối tượng A. 
Bước 2: Đối tượng A thực hiện: 
• Chọn giá trị kA thỏa mãn: )1(1 −<< pk A . 
• Hình thành phần thứ nhất của bản mã theo công 
thức: 
( ) pyRMC AA xkBB mod+××= . 
• Hình thành phần thứ hai của bản mã: 
 pgR Ak mod= 
• Gửi bản mã (C,R) đến đối tượng nhận B. 
c) Thủ tục giải mã 
Để khôi phục bản tin ban đầu (M) từ bản mã nhận được 
(C,R), người nhận B thực hiện các bước như sau: 
• Tính giá trị Z theo công thức: 
( ) pyRZ A mod1−×= . 
• Khôi phục bản tin ban đầu (M): 
( ) pZCM BB xk mod+×= . 
d) Tính đúng đắn của thuật toán mới đề xuất 
Điều cần chứng minh ở đây là: cho p là số nguyên tố, g là 
phần tử sinh của ∗pZ , ( )1,1 −<< pxx BA , 
pgy AxA mod= , pgy B
x
B mod= , 
( )1,1 −<< pkk BA , ( ) pgR BkB mod=
( ) pyRMC AA xkBB mod+××= ,. ( ) pgR Ak mod= 
Nếu: ( ) pyRZ A mod1−×= , 
( ) pZCM BB xk mod+×= thì: MM = . 
Chứng minh: 
Thật vậy, ta có: 
( )
( )( )
( )( )
( ) ( )( )( )
( ) ( )( )
( ) ( )( )
( ) ( )( )
( ) ( ) ( ) ( ) MpggM
ppg
pgM
pppgpg
ppgpgM
ppyR
pyRM
pZCM
AABBAABB
AABB
AABB
BB
AA
AABB
BB
AA
BB
xkxkxkxk
xkxk
xkxk
xk
xk
xkxk
xk
A
xk
BB
xk
=××=
×
××=
××
×××=
=××
×××=
=×=
++−++
++−
++
+
−
+
+
−
+
+
mod
modmod
mod
modmodmodmod
modmodmod
modmod
mod
mod
..
.
.
1
1
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, 03-04/12/2012 
e) Mức độ an toàn của thuật toán mới đề xuất 
Ở thuật toán mới đề xuất, cả 2 khóa bí mật ngắn hạn 
(kA) và dài hạn (xA) của người gửi (A) cũng như khóa bí mật 
ngắn hạn (kB) và dài hạn (xB) của người nhận (B) đều được 
sử dụng kết hợp trong các thủ tục mã hóa và giải mã. Vì 
vậy, mức độ an toàn của thuật toán mới đề xuất xét theo khả 
năng chống thám mã trong cả 2 trường hợp tấn công trực 
tiếp vào thủ tục mã hóa và giải mã đều cao hơn thuật toán El 
Gamal. 
5) Thuật toán thứ 5 
Thuật toán thứ 5 đề xuất ở đây được xây dựng theo 
nguyên tắc tương tự như thuật toán thứ 4. 
a) Thủ tục hình thành tham số và khóa 
• Chọn số nguyên tố lớn p sao cho bài toán logarit 
trong pZ là khó giải. 
• Chọn g là phần tử sinh của ∗pZ . 
• Chọn khóa mật x là số nguyên thỏa mãn: 
( )11 −<< px . 
• Tính khóa công khai y theo công thức: 
pgy x mod−= . 
• Giữ bí mật: x; công khai: p, q, g, y. Khóa công khai 
y cần phải được chứng thực bởi một CA (Certificate 
Authority) đáng tin cậy. 
b) Thủ tục mã hóa 
Giả sử người gửi là A, người nhận là B. Người gửi A có 
khóa bí mật là xA và khóa công khai là yA. Người nhận B có 
khóa bí mật là xB và khóa công khai là yB. Khi đó, thủ tục để 
A gửi bản tin M cho B, với: pM <≤0 , bao gồm các 
bước như sau: 
Bước 1: Đối tượng B thực hiện: 
• Chọn giá trị kB thỏa mãn: )1(1 −<< pkB . 
• Tính giá trị RB theo công thức: 
pgR BkB mod= . 
• Gửi giá trị RB cho đối tượng A. 
Bước 2: Đối tượng A thực hiện: 
• Chọn giá trị kA thỏa mãn: )1(1 −<< pk A . 
• Hình thành phần thứ nhất của bản mã theo công 
thức: 
( ) ( ) pyRMC AA kBxB mod××= . 
• Hình thành phần thứ hai của bản mã: 
 pgR Ak mod= 
• Gửi bản mã (C,R) đến đối tượng nhận B. 
c) Thủ tục giải mã 
Từ bản mã nhận được (C,R), người nhận B khôi phục lại 
bản tin ban đầu theo công thức: 
( ) ( ) pyRCM BB kAx mod××= . 
d) Tính đúng đắn của thuật toán mới đề xuất 
Điều cần chứng minh ở đây là: cho p là số nguyên tố, g là 
phần tử sinh của ∗pZ , ( )1,1 −<< pxx BA , 
pgy AxA mod
−
= , pgy BxB mod
−
= , 
( )1,1 −<< pkk BA , ( ) pgR BkB mod=
( ) ( ) pyRMC AA kBxB mod××= ,. ( ) pgR Ak mod= 
Nếu: ( ) ( ) pyRCM BB kAx mod××= thì: MM = . 
Chứng minh: 
Thật vậy, ta có: 
( ) ( )
( ) ( )( )
( ) ( )
( ) ( )
( ) ( )
M
pggggM
ppgpg
pgpgM
pyR
pyRM
pyRCM
ABBABAAB
BABA
ABAB
BB
AA
BB
xkxkxkxk
kxxk
kxxk
k
A
x
k
B
x
B
k
A
x
=
××××=
=××
×××=
=××
×××=
=××=
−−
−
−
mod
modmodmod
modmod
mod
mod
mod
....
e) Mức độ an toàn của thuật toán mới đề xuất 
Phân tích tương tự như với thuật toán thứ 4, có thể thấy 
rằng mức độ an toàn của 2 thuật toán này là như nhau. 
III. KẾT LUẬN 
Bài báo đề xuất 5 thuật toán mật mã khóa công khai được 
phát triển dựa trên hệ mật ElGamal, các thuật toán này có 
thể bảo đảm đồng thời 2 khả năng bảo mật và xác thực 
nguồn gốc thông tin. Hơn nữa, mức độ an toàn của các thuật 
toán được đề xuất ở đây không nhỏ hơn mức độ an toàn của 
thuật toán El Gamal xét theo khả năng chống thám mã khi 
tấn công trực tiếp vào các thủ tục mã hóa và giải mã. 
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] Lưu Hồng Dũng, Nghiên cứu phát triển thuật toán mật 
mã khóa công khai dựa trên hệ mật ElGamal, Chuyên 
san CNTT và TT, Bộ Thông tin và Truyền thông, số 
8(28), 12-2012. 
[4] National Institute of Standards and Technology, NIST 
FIPS PUB 186-3. Digital Signature Standard, U.S. 
Department of Commerce,1994.