Phát triển thuật toán mật mã khóa công khai dựa trên hệ mật ElGamal

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 8 (28), tháng 12/2012 
22 
Abstract: This paper proposed a new public key 
cryptographic algorithm based on the ElGamal 
cryptosystem. This algorithm has the capacity of 
information security and anthentication information. 
The paper also offers analysis on the safety of the 
proposed schemes, has shown the ability to apply it in 
practice. 
I. ĐẶT VẤN ĐỀ 
Trong thực tế, nhiều ứng dụng đòi hỏi việc bảo 
mật thông tin cần phải được thực hiện đồng thời 
với việc xác thực về nguồn gốc và tính toàn vẹn 
của thông tin. Nội dung bài báo đề xuất một 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 [1] cho phép giải quyết tốt 
các yêu cầu nêu trên. 
II. PHÁT TRIỂN THUẬT TOÁN MẬT MÃ 
KHÓA CÔNG KHAI DỰA TRÊN HỆ 
MẬT ELGAMAL 
1. Hệ mật Elgamal 
Hệ mật Elgama được đề xuất vào năm 1984 trên 
cơ sở bài toán logarith rời rạc. Sau đó, các chuẩn 
chữ ký số DSS [2] của Mỹ và GOST R34.10-94 
[3] của Liên bang Nga đã được phát triển trên cơ 
sở thuật toán chữ ký số của hệ mật này. 
1.1 Thuật toán hình thành tham số và khóa 
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ã 
Elgamma thì trước tiên thực hiện quá trình hình 
thành khóa như sau: 
1- Chọn số nguyên tố đủ lớn p sao cho bài toán 
logarit trong pZ là khó giải. 
2- Chọn *pZg ∈ là phần tử nguyên thủy. 
3- Chọn khóa mật x là số ngẫu nhiên sao cho: 
px <<1 . Tính khóa công khai y theo công 
thức: pgy x mod= . 
1.2 Thuật toán 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 , người gửi A sẽ thực hiện các bước 
như sau: 
1- Chọn số ngẫu nhiên k thỏa mãn: 
pk <<1 . Tính giá trị R theo công thức: 
 pgR k mod= . 
2- Sử dụng khóa công khai của B để tính: 
 pyMC kB mod)(×= 
3- Gửi bản mã gồm ( )RC, đến người nhận B. 
1.3 Thuật toán 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: 
 1- Tính giá trị Z theo công thức: 
 pgpRZ BB xkx modmod .== 
 2- Tính gía trị nghịch đảo của Z: 
 ( ) pgpgZ BB xkxk modmod .1.1 −−− == 
 3- Khôi phục bản tin ban đầu (M): 
 pZCM mod1−×= 
 1.4 Tính đúng đắn của thuật toán mật mã 
Elgamal 
Giả sử bản tin nhận được sau quá trình giải mã 
( )RC, là M , thế thì: 
PHÁT TRIỂN THUẬT TOÁN MẬT MÃ KHÓA CÔNG KHAI DỰA TRÊN HỆ MẬT 
ELGAMAL 
DEVELOPMENT OF PUBLIC KEY CRYPTOGRAPHIC ALGORITHM BASED ON 
ELGAMAL CRYPTOSYSTEM 
Lưu Hồng Dũng 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 8 (28), tháng 12/2012 
 23 
M
pggM
ppgpyM
pZCM
BB
B
xkxk
xkk
B
=
××=
××=
=×=
−
−
−
mod
mod)]mod()mod)([(
mod
..
.
1
 Như vậy, bản tin nhận được sau giải mã 
( M ) chính là bản tin ban đầu (M). 
1.5 Mức độ an toàn của hệ mật ElGamal 
Hệ mật ElGamal sẽ bị phá vỡ nếu khóa mật x 
hoặc k có thể tính được. Để tính được x hoặc k, cần 
phải giải một trong hai bài toán logarit rời rạc, 
chẳng hạn: pgy x mod= hay: pgR k mod= . 
Tuy nhiên, việc giải bài toán logarit rời rạc này 
là việc khó [4]. 
Một điểm yếu có thể bị tấn công trong hệ mã 
ElGamal là khi giá trị k bị sử dụng lại. Thực vậy, 
giả sử cùng một giá trị k được sử dụng để mã hóa 
hai bản tin M và *M được các bản mã tương ứng 
là ( )RC, và ( )** , RC . Khi ấy ta sẽ có: 
pgMgM
CC
kxkx mod))(()(
)(
1*
1*
−
−
×××≡
≡×
Suy ra: 
 pMCCM mod)( 1** ≡×× − 
Nghĩa là, chỉ cần biết nội dung của một trong hai 
bản tin M hoặc *M thì sẽ dễ dàng biết được nội 
dung của bản tin kia. 
Một vấn đề được đặt ra không chỉ với hệ 
ElGamal nói riêng mà với các hệ mật khóa công 
khai nói chung là: Giả sử một người gửi A mã hóa 
bản tin M được bản mã C và gửi C cho người nhận 
B. Sẽ có các tình huống xảy ra như sau: 
- Người nhận B không thể biết chắc chắn rằng bản 
tin nhận được (M) có nguồn gốc từ người gửi A. 
- Giả sử bản mã C đã bị thay đổi thành *C và 
người nhận giải mã được bản tin M*. Trường 
hợp này, người nhận không thể khẳng định nội 
dung bản tin nhận được (M*) đã bị thay đổi hay 
không. 
Thuật toán mật mã được đề xuất trong bài báo 
này được phát triển trên cơ sở hệ mật ElGamal sẽ 
là giải pháp cho các vấn đề nêu trên. 
2. Thuật toán mật mã khóa công khai dựa trên 
hệ mật Elgamal 
2.1. Thuật toán hình thành tham số và khóa 
1- Phát sinh cặp số nguyên tố p và q đủ lớn và: 
)1(| −pq sao cho bài toán logarit trong 
pZ là khó giải. 
2- Chọn pg 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: α là một số nguyên 
thỏa mãn: )1(1 −<< pα . 
3- Khóa bí mật x là một giá trị được chọn ngẫu 
nhiên trong khoảng: qx <<1 . Khóa công 
khai y được tính theo công thức: 
 pgy x mod−= 
4- Lựa chọn hàm băm (hash) H:{ } qZa*1,0 
(Ví dụ: SHA-1, MD5). 
2.2 Thuật toán 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.. Để gửi bản tin M cho B, A thực hiện 
các bước như sau: 
1- Chọn số ngẫu nhiên k thỏa mãn: qk <<1 . 
2- Tính giá trị R theo công thức: 
 pgR k mod= (1) 
3- Tính thành phần E theo công thức: 
 qMRHE mod)||(= (2) 
24Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 8 (28), tháng 12/2012 
22 4
4- Tính thành phần S theo công thức: 
 qExkS A mod][ ×+= (3) 
5- Sử dụng khóa công khai của B để tính thành 
phần C theo công thức: 
 pyMC kB mod)(×= (4) 
6- Gửi bản mã gồm ( )SEC ,, đến B. 
Tương tự thuật toán Elgamal, thuật toán mật mã 
mới đề xuất có thể bị tấn công khi sử dụng lại giá 
trị của k. Có thể khắc phục yếu điểm trên nếu sử 
dụng giá trị )||( MxH thay cho k, với H(.) là hàm 
băm kháng va chạm (chẳng hạn SHA-1, MD5,...) 
và “||” là toán tử nối/xáo trộn xâu. Khi đó thuật 
toán mã hóa sẽ được mô tả lại như sau: 
1- Tính giá trị R theo công thức: 
 pgR MxH A mod)||(= 
2- Tính thành phần E theo công thức: 
 qMRHE mod)||(= 
3- Tính thành phần S theo công thức: 
 qExMxHS AA mod])||([ ×+= 
4- Sử dụng khóa công khai yb của người nhận để 
tính thành phần C theo công thức: 
 pyMC MxHB A mod)( )||(×= 
5- Gửi bản mã gồm ( )SEC ,, đến người nhận B. 
2.3 Thuật toán giải mã 
Từ bản mã ( )SEC ,, 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: 
1- Tính giá trị R theo công thức: 
 pygR EA
S mod)(×= (5) 
2- Khôi phục bản tin ban đầu theo công thức: 
 pRCM Bx mod)(×= (6) 
3- Tính thành phần E theo công thức: 
 qMRHE mod)||(= (7) 
4- Kiểm tra nếu EE = thì MM = và M có 
nguồn gốc từ người gửi A. 
Chú ý: 
Trường hợp sử dụng giá trị )||( MxH thay cho 
k, thuật toán giải mã vẫn được giữ nguyên. 
2.4 Tính đúng đắn của thuật toán mới đề xuất 
Tính đúng đắn của hệ mật mới đề xuất là sự phù 
hợp giữa thuật toán giải mã với thuật toán mã hóa. 
Điều cần chứng minh ở đây là: 
 Cho: p, q là 2 số nguyên tố độc lập, 
pg qp mod/)1( −= α , pg qp mod/)1( −= α , 
*
pZ∈α , ]1,1[, −∈ qxx BA , pgy AxA mod−= , 
pgy BxA mod
−
= , { } pZH a*1,0: , 
pgR MxH A mod)||(= , qMRHE mod)||(= , 
qExMxHS AA mod])||([ ×+= , 
pyMC MxHB A mod)( )||(×= . Nếu: 
pygR EA
S mod)()( ×= , 
pRCM Bx mod)(×= , qMRHE mod)||(= 
thì: MM = và EE = . 
Chứng minh: 
Thật vậy, thay (3) vào (5) ta có: 
pg
pggg
pgg
pygR
k
ExExk
ExExk
E
A
S
AA
AA
mod
mod
mod)(
mod)(
.
=
××=
×=
×=
−×
−×+
 (8) 
Từ (8) suy ra: 
 pgR k mod= (9) 
Thay (4) và (9) vào (6) ta có: 
Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 8 (28), tháng 12/2012 
 25 
M
pggM
ppg
pyM
pRCM
BB
B
B
xkxk
xk
k
B
x
=
××=
×
××=
×=
− mod
mod}mod)(
mod)({
mod)(
..
 (10) 
Từ (8) cũng suy ra: 
 RR = (11) 
Thay (10) và (11) vào (7) ta được: 
E
qMRH
qMRHE
=
=
=
mod)||(
mod)||(
Đây là điều cần chứng minh. 
2.5 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 
đánh giá bằng: 
1) Khả năng chống thám mã. 
2) Khả năng chống giả mạo về nguồn gốc và nội 
dung của bản tin. 
Về khả năng chống thám mã, có thể thấy rằng 
mức độ an toàn của thuật toán mật mã mới đề xuất 
là hoàn toàn tương đương với thuật toán Elgamal. 
Hệ mật chỉ bị phá vỡ nếu khóa mật x có thể tính 
được từ việc giải bài toán logarit rời rạc: 
 pgy x mod−= 
hay từ: 
 qExMxHS mod])||([ ×+= 
Khả năng chống giả mạo về nguồn gốc và nội 
dung bản tin của thuật toán mật mã mới đề xuất 
phụ thuộc vào mức độ khó của việc tạo ra các cặp ( )*** ,, SEC giả mạo thỏa mãn được điều kiện 
kiểm tra của thuật toán giải mã: EE = . Xét một 
số trường hợp như sau: 
- Trường hợp thứ nhất: Giả mạo cả về nội dung 
và nguồn gốc bản tin, khi đó bản tin nhận được 
( )*** ,, SEC sẽ có cả 3 thành phần đều là giả mạo. 
Rõ ràng là, để được công nhận hợp lệ thì cặp ( )*** ,, SEC giả mạo này cần phải thỏa mãn: 
 qMpygHE EA
S mod)||)mod)((( *** ∗×= 
với: 
 ppygCM BxEA
S mod])mod)(([ ∗∗ ××= ∗∗ 
- Trường hợp thứ hai: Giả mạo về nguồn gốc 
nhưng không giả mạo về nội dung, trường hợp 
này bản mã nhận được ( )**,, SEC có cặp 
( )**, SE là giả mạo, khi đó việc giả mạo sẽ 
thành công nếu ( )**,, SEC thỏa mãn: 
 qMpygHE EA
S mod)||)mod)((( *** ×= 
với: 
 ppygCM BxEA
S mod])mod)(([ ∗∗ ××= 
- Trường hợp thứ ba: Giả mạo về nội dung 
nhưng không giả mạo về nguồn gốc, ở trường 
hợp này bản mã nhận được ( )SEC ,,∗ chỉ có 
thành phần ∗C là giả mạo, việc giả mạo sẽ được 
chấp nhận nếu điều kiện sau thỏa mãn: 
 qMpygHE EA
S mod)||)mod)((( ∗×= 
với: 
 ppygCM BxEA
S mod])mod)(([ ××= ∗∗ 
Cần chú ý là ở 3 trường hợp trên, trong biểu thức 
tính M và M* thì xB là khóa bí mật của người nhận 
mà kẻ giả mạo không biết được. Mặt khác, với việc 
sử dụng H(.) là hàm băm có tính kháng va chạm thì 
việc tìm được các cặp ( )*** ,, SEC giả mạo là rất 
khó thực hiện. 
III. KẾT LUẬN 
Bài báo đề xuất một 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ó khả năng đồng thời: 
1) Bảo mật thông tin. 
2) Xác thực về nguồn gốc thông tin. 
26Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 8 (28), tháng 12/2012 
22 6
3) Xác thực về tính toàn vẹn của thông tin. 
Hơn nữa, mặc dù bản mã được tạo ra bởi thuật 
toán mới đề xuất bao gồm 3 thành phần (C,E,S) 
nhưng độ dài của nó không lớn hơn độ dài bản mã 
2 thành phần (C,R) mà thuật toán ElGamal tạo ra. 
Giả sử |p| = 512 bit, |q| = 160 bit khi đó độ dài bản 
mã do thuật toán ElGamal tạo ra là: |C| + |R| = 512 
bit + 512 bit = 1024 bit. Trong khi đó, bản mã với 
khả năng xác thực được nguồn gốc và tính toàn 
vẹn của nội dung bản tin do thuật toán mới đề xuất 
tạo ra chỉ có độ dài: |C| + |E| + |S| = 512 bit + 160 
bit + 160 bit = 832 bit. 
Những phân tích về mức độ an toàn cho thấy khả 
năng ứng dụng thuật toán mới đề xuất là hoàn toàn 
thực tế. 
TÀI LIỆU THAM KHẢO. 
[1] 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. 
[2] National Institute of Standards and Technology, 
NIST FIPS PUB 186-3. Digital Signature Standard, U.S. 
Department of Commerce,1994. 
____________________________________________ 
SƠ LƯỢC VỀ TÁC GIẢ 
LƯU HỒNG DŨNG. 
Sinh năm 1966 tại Hưng Yên. 
Tốt nghiệp đại học ngành Vô tuyến Điện tử tại 
Học viện Kỹ thuật Quân sự năm 1989. 
Hiện đang công tác tại khoa CNTT- Học viện 
KTQS. 
Hướng nghiên cứu: An toàn và bảo mật thông tin. 
Email: luuhongdung@gmail.com. 
[3] 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). 
[4] D.R Stinson, Cryptography: Theory and Practice, 
CRC Press 1995.