TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ
TRUYỀN THÔNG
ĐẠI HỌC THÁI NGUYÊN
---------------O0O--------------

BÁO CÁO BÀI TẬP LỚN
MÔN: An toàn và bảo mật thông tin
CHỦ ĐỀ 5: Hệ mật mã Elgamal
GIẢNG VIÊN : Nguyễn Lan Oanh
Nhóm 8:
1.
2.
3.
4.
5.
6.

Hà Thị Lan (28/7/1990)
Nguyễn Thị Huyền
Đào Trung Sơn
Nguyễn Thị Thảo
Võ Văn Trường
Trần Thị Hồng Hạnh


Hệ mật mã Elgamal

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 2

Hệ mật mã Elgamal
LỜI NÓI ĐẦU

Ta biết rằng tin truyền trên mạng rất dễ bị lấy cắp. Để đảm bảo việc truyền tin an toàn người ta
thường mã hoá thông tin trước khi truyền đi. Việc mã hoá thường theo quy tắc nhất định gọi là hệ
mật mã.
Hiện nay có hai loại hệ mật mã: mật mã cổ điển và mật mã khoá công khai. Mật mã cổ điển dễ
hiểu, dễ thực thi nhưng độ an toàn không cao. Vì giới hạn tính toán chỉ thực hiện trong phạm vi
bảng chữ cái sử dụng văn bản cần mã hoá. Với các hệ mã cổ điển, nếu biết khoá lập mã hay thuật
toán lập mã, người ta có thể "dễ" tìm ra được bản rõ. Ngược lại các hệ mật mã khoá công khai cho
biết khoá lập mã K và hàm lập mã Ck thì cũng rất "khó" tìm được cách giải mã.
Hệ mã hóa với khoá công khai Elgamal được đề xuất năm 1985, dựa vào độ phức tạp của bài
toán lôgarit rời rạc. Với chủ đề 5, “cài đặt hệ mã Elgamal”, chúng ta sẽ có cái nhìn tổng quan về hệ
mã hóa công khai Elgamal.

Nhóm 8

MỤC LỤC
Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 3


Hệ mật mã Elgamal
Phần I : Lý thuyết
1.1.Cơ sở xây dựng hệ mã Elgamal
1.2. Hệ mã Elgamal
1.3. Ví dụ
1.4. Ưu nhược điểm của hệ mật mã Elgamal

1.5. Độ phức tạp của hệ mật mã Elgamal
1.6. Thám mã đối với hệ mật mã elgamal
1.6.1.Thuật toán Shank(cân bằng thời gian)
1.6.2.Thuật toán Pohlig-Hellman
1.7. Thuật toán mật mã khóa bất đối xứng tương lai(Advanced Elgamal)
1.7.1. Thuật toán
1.7.2 quá trình mã hóa
1.7.3. quá trình giải mã
1.7.4.Chứng minh thuật toán
1.7.5. Đánh giá độ phức tạp thuật toán
1.7.6. Kết luận
Phần II : Lập trình (code)

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 4


Hệ mật mã Elgamal
PHẦN I: LÝ THUYẾT
1.1.Cơ sở xây dựng hệ mã Elgamal
Hệ mật mã elgamal được xây dựng dựa trên bài toán logarithm rời rạc .
Bài toán logarithm được phát biểu như sau:
I={p,α,β}
Trong đó: p là số nguyên tố
α Є Zp là là phần tử nguyên thủy
β Є Zp*
Mục tiêu: Hãy tìm một số nguyên duy nhất a ,0 ≤ a ≤ p-2 : αa ≡ β(mod p)
Ta sẽ xác định số nguyên a bằng loga β
1.2. Hệ mã Elgamal

*. Tạo khóa:
Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó giải. Cho α Є Zp *
là phần tử nguyên thủy. Giả sử P= Zp* , C= Zp* x Zp* .Ta định nghĩa :
K={(p,α,a,β): β ≡ αa (mod p) }
Khóa công khai là: (p, α , β)
Khóa bí mật là : a
*. Mã hóa:
Chọn 1 số ngẫu nhiên bí mật k Є Zp-1 ,(chú ý là sau khi mã hóa xong thì k sẽ bị hủy) ta xác
định : ek(x,k)=(y1 , y2 )
Trong đó:

y1= αk mod p
y2=x.βk mod p

*. Giải mã:
Với y1 , y2 Є Zp* ta xác định : dk(y1 , y2 )= y2(y1a )-1 mod p

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 5


Hệ mật mã Elgamal
1.3. Ví dụ
Cho p= 569 , α = 2 ,a = 109 ,x= 257 , chọn k= 79
β ≡ αa mod p

*, tạo khóa:

β ≡ 2109 mod 569

x
10

a
2

y=1
2

54
27
13
6
3
1

4
16
256
101
528
543

x
32
226
x
407
229


9

= > β= 229
Vậy:

Khóa công khai là : (p,α,β)=(569,2,229)
Khóa bí mật là a=109

*. Mã hóa
Chọn k ngẫu nhiên k=79
Khi người A gửi bản tin x=257 cho người B thì người A sẽ mã hóa như sau:
+. y1= αk mod p
= 279 mod 569
x
79
39
19
9
4
2
1

a
2
4
16
256
101
528
543


y=1
2
8
128
335
x
x
394

= > y1= 394
Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 6


Hệ mật mã Elgamal
+. y2 = x. βk mod p
= 257 .22979 mod 569
•
tính: 22979 mod 569
x
a
y=1
79
229
229
39
93
244

19
114
504
9
478
225
4
315
x
2
219
x
1
165
140
= > y2 =257.140 mod 569 = 133
Vậy người A sẽ gửi bản mã (y1,y2) =(394,140) cho người B
*. Giải mã:
Người B nhận được bản mã (y1,y2) sẽ tiến hành giải mã :
x= y2(y1a )-1 mod p = 140.(394109)-1 mod 569
•

Tính 394109 mod 569
x
109
54
27
13
6
3

1
Kq= 140

a
394
468
528
543
107
69
209

y=1
394
x
347
82
x
537
140

Tính (140)-1 mod 569
x
569
140
9
5
4
1


a
1
0
1
-15
16
-31

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

b
0
1
-4
61
-65
126

y
4
15
1
1

Page 7


Hệ mật mã Elgamal
Kq = 126
= > x =133.126 mod 569 = 257

Vậy người B sau khi giải mã sẽ nhận được bản rõ x= 257
1.4. Ưu nhược điểm của hệ mật mã Elgamal
•

Ưu điểm:

Do được xây dựng từ bài toán logarithm rời rạc nên hệ mã khó tìm được các loagarithm rời rạc
nếu p được chọn cẩn thận. Để khó tấn công p phải có ít nhất 150 chữ số và (p-1) phải có ít nhất 1
thừa số nguyên tố lớn.

•

Nhược điểm:
Dung lượng bộ nhớ dành cho việc lưu trữ các bản mã là lớn gấp đôi so với các hệ mã khác .
Do việc sử dụng các số nguyên tố nên việc sinh khóa và quản lý khóa cũng khó khăn hơn các
hệ mã khối.
1.5. Độ phức tạp của hệ mật mã Elgamal
Theo thời gian: O(p)
Theo không gian:O(1)
1.6. Thám mã đối với hệ mật mã elgamal
1.6.1.Thuật toán Shank(cân bằng thời gian)
Nếu chúng ta có đủ bộ nhớ thì có thể sử dụng bộ nhớ đó để làm giảm thời gian thực hiện
của bài toán xuống.



Input: số nguyên tố p , phần tử nguyên thủy α của Zp* , số nguyên β
Output : cần tìm a sao cho αa mod p = β




Thuật toán:
Gọi m=[(p-1)1/2] (lấy phần nguyên)
Bước 1: tính αm.j mod p với 0≤ j≤ m-1
Bước 2: Sắp xếp các cặp tj: (j, αm.j mod p ) theo αm.j mod p và lưu vào danh
sách L1
Bước 3: tính β.α-i mod p với 0≤i≤m-1

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 8


Hệ mật mã Elgamal
Bước 4: Sắp xếp các cặp ti: (I, β.α-i mod p) theo β.α-i mod p và lưu vào danh
sách L2.
Bước 5: Tìm trong hai danh sách L1và L2 xem có tồn tại cặp (j, αm.j mod p) và
(I, β.α-i mod p) nào mà αm,j mod p= β.α-i mod p (tọa độ thứ 2 của hai cặp bằng
nhau).
Bước 6: a=(m.j+i) mod (p-1)
Kết quả này có thể kiểm chứng từ công thức αm.j mod p=β.α-i mod p
= > am.j+i mod p = β mod p
= > a=(m.j+i) mod (p-1)

Độ phức tạp thuật toán:
Phụ thuộc vào m=[(p-1)1/2], với giá trị của m, chúng ta cần tính các phần tử thuộc 2 danh sách
L1 và L2 , đều là các phép toán lũy thừa phụ thuộc vào j và i ; mà j và I lại phụ thuộc vào m nên có
thể nhận thấy là thuật toán này chỉ có thể áp dụng trong những trường hợp p nhỏ

Ví dụ minh họa :

Cho p=79, α=2, β=55 .Tìm a theo thuật toán Shank
Bài giải
1/2
Tính m=[(p-1) ] = 9
B1: Tính t= αm.j mod p với 0≤ j≤ m-1 : 29.j mod 79 với 0≤ j≤8
j =0 => t=1;
tj (0,1)
9
j=1=> 2 mod 79 =38; tj (1,38)
j=2=>218 mod 79=13; tj (2,22)
j=3=>227mod 79=46; tj(3,46)
j=4=>236mod 79;
x
36
18
9
4
2
1
=>

a
2
4
16
19
45
50

d=1

x
x
16
x
x
10

tj(4,10)
j=5=>245mod 79
x
45
22

a
2
4

d=1
2
x

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 9


Hệ mật mã Elgamal
11
5
2

1

16
19
45
50

32
55
x
64

a
2
4
16
19
45
50

d=1
x
4
64
x
36
62

a
2

4
16
19
45
50

d=1
2
8
49
62
25
65

a
2
4
16
19
45
50
51

d=1
x
x
x
19
x
x

21

=> tj(5,64)
J=6 => 254mod 79
x
54
27
13
6
3
1
=>tj(6,62)
j =7 => 263mod 79
x
63
31
15
7
3
1
=> tj(7,65)

j =8 =>272 mod 79
x
72
36
18
9
4
2

1
=>tj(8,21)
Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 10


Hệ mật mã Elgamal
B2: Sắp xếp các cặp tj theo hướng tăng dần của αm.j mod p
(0,1);(4,10);(2,13);(8,21);( 1,38);(3,46);(6,62); (5,64);(7,65)
B3: tính β.α-i mod p với 0≤i≤m-1 : 55.(2-i) mod 79 với 0≤i≤8
Hay tính 55.(2i)-1 mod 79
i =0: 20 mod 79 = 1 => 1-1 mod 79=1 => 55.(20)-1 mod 79 =55
= >ti(0,55)
i =1:21 mod 79=2 => 2-1mod 79=40(tính theo EuClic)
=> 55.(21)-1 mod 79 = 55.40 mod 79=67
= >ti(1,67)
i =2:22 mod 79 =4 => 4-1 mod 79= 20
=>55.(22)-1 mod 79= 55.20 mod 79=73
= >ti(2,73)
i =3: 23 mod 79 =8 => 8-1 mod 79 = 10
=> 55.(23)-1 mod 79=55.10 mod 79=76
= >ti(3,76)
i =4:24 mod 79=16 => 16-1 mod 79 = 5
=> 55.(24)-1 mod 79 = 55.5 mod 79=38
= >ti(4,38)
i =5:25mod 79=32=>32-1mod 79=42
= > 55.(25)-1 mod 79=55.42 mod 79= 74
= >ti(5,74)
i =6:26 mod 79 =64 =>64-1mod 79= 21

= > 55.(26)-1 mod 79 = 55.21 mod 79=49
= >ti(6,49)
i =7:27 mod 79=49 => 49-1 mod 79=50
Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 11


Hệ mật mã Elgamal
= > 55.(27)-1 mod 79=55.50 mod 79= 64
= >ti(7,64)
i =8:28 mod 79=19 => 19-1 mod 79 =25
= > 55.(28)-1 mod 79= 55.25 mod 79 = 32
= >ti(8,32)

B4: Sắp xếp các cặp ti: (I, β.α-i mod p) theo thứ tự tăng của β.α-i mod p và lưu vào danh sách L2 :
ti(8,32) ; ti(4,38) ; ti(6,49) ; ti(0,55) ; ti(7,64) ; ti(1,67) ; ti(4,73) ; ti(5,74) ; ti(3,76)
B5: Tìm trong hai danh sách L1và L2 xem có tồn tại cặp (j, αm.j mod p) và (I, β.α-i mod p) nào
mà αm,j mod p= β.α-i mod p (tọa độ thứ 2 của hai cặp bằng nhau).
Ta thấy cặp tj(1,38) và cặp ti(4,38) có tọa độ thứ 2 bằng nhau cùng bằng 38 . và cặp tj(5,64) với
cặp ti(7,64) có tọa độ thứ 2 bằng 64
= > chon : bộ 1: j=1 ;i=4 ; bộ 2: j=5;i=7
B6:
Với bộ 1: a=(m.j+i) mod (p-1)
a =(9.1+4) mod (p-1) =13
với bộ 2: a=(9.5+7)mod 78 =52

( Kiểm tra: ta có β≡αa mod p theo trên tính a=13
= > β≡ 213 mod 79
x

a
d=1
13
2
2
6
4
x
3
16
32
1
19
55
= > β=55 đúng theo bài ra β =55
Tính theo a=52
= > β≡ 252 mod 79
x
a
d=1
52
2
x
26
4
x
13
16
16
6

19
x
3
45
9
Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 12


Hệ mật mã Elgamal
1
50
= > β= 55 đúng theo bài ra )

55

1.6.2.Thuật toán Pohlig-Hellman
Có những trường hợp đặc biệt mà bài toán Logarithm rời rạc có thể giải quyết với độ phức tạp
nhỏ hơn O(p1/2), chẳng hạn như khi (p-1) chỉ có các ước nguyên tố nhỏ. Một thuật toán làm việc
với các trường hợp như vậy đã được Pohlig và Hellman đưa ra vào năm 1978.
Giả sử, p-1 = 2n.
Gọi α là phần tử nguyên thủy của Z*p, p là một số lẻ và α(p-1)/2 mod p= -1. Gọi m là số nguyên
thuộc
[0,p-2] mà chúng ta cần tìm để β= α m mod p. giả sử, m được biểu diễn thành dạng nhị phân
m= m0+2m1 +4m2+…. + 2n-1mn-1. Khi đó,

1 nếu m0=0
=
-1 nếu m0= 1

Việc tính β(p-1)/2 mất nhiều nhất 2[log2p] bước và sẻ cho ta m0. Khi xác định được β1=β.α-m0, ta
lặp lại thao tác tương tự để tính m1:

1 nếu m1=0
Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 13


Hệ mật mã Elgamal
=
-1 nếu m1=1

Quá trình tính toán cứ thế tiếp diễn cho tới khi chúng ta tìm được mi. Độ phức tạp của thuật
toán là : n.(2[log2p]+2) ~O((log2p)2).

1.7. Thuật toán mật mã khóa bất đối xúng tương lai(Advanced Elgamal)
1.7.1. Thuật toán
Thuật toán Elgamal còn nhược điểm khá lớn là tạo ra các văn bản mã giống nhau nếu cùng khối
văn bản gốc. Điều này là một yếu điểm chung của phương pháp mật mã khóa bất đối xứng, làm
giảm tính an toàn của thuật toán vì có thế sự dụng phương pháp thám mã theo xác suất[1,2]. Mặt
khác, các khối dữ liệu sau mã hóa đi trên mạng, do chủ quan hay khách quan, một vài khối có thế
bị mất đi hoặc thêm vào hoặc bị thay đổi nội dung. Nơi nhận hoàn toàn không phát hiện được.
Thuật toán sau giải quyết vấn đề này.
Cho p là số nguyên tố lớn có chiều dài n byte sao cho việc giải bài toán trong miền Zp* là
đủ khó. Có thể chọn bằng 8, 16, 32, 64 hoặc 128 byte.
-Khoá công khai K pu = (p,α,β), trong đó: p: một số nguyên tố lớn bất kì; α: số
nguyên bất phần tử sinh; β =
mod p, với a nguyên bất kì thỏa mãn 1 ≤ a ≤ p-2.
-Khóa bí mật Kpr = a.

1.7.2 quá trình mã hóa
Chia dữ liệu cần mã hóa thành các khối X[i] có kích thước n byte. Khối cuối cùng có kích
thước nhỏ hơn n byte sẽ không đưuọc mã hóa.
Bước 1: Tính A[i] = ( mod p) XOR X[i]
K là số nguyên bất kì thỏa 1 ≤ a ≤ p-2.
Bước 2: Thực hiện dịch vòng trái LCS(Left Circular Shift) từng byte của A[i] theo vectơ dịch
SV(Shift Vectơ) thu đưoojwc B[i]
B[i][j]=A[i][j]<<SV là ma trận hàng gồm n phần tử, mỗi phần tử thỏa điều kiện:
0≤ SV[i] ≤ 7.
Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 14


Hệ mật mã Elgamal
Bước 3: Thu được văn bản sau mã hóa bằng cách:
C[i]=B[i] XOR C[i-1]
Trong đó C[i-1] là văn bản liền trước. Sử dụng vectơ khởi tạo IV(Initial Vectơ) cho lần đầu tiên

1.7.3. quá trình giải mã
Nhận được C[i], C[i-1] và biết trước khóa bí mật Kpr = a.
Bước 1: Tìm B[i] = C[i] XOR C[i-1], sử dụng vectơ khởi tạo IV(Inital Vectơ)cho lần đầu tiên.
Bước 2: Sử dụng vectơ liên hiệp dịch

dịch vòng trái LCS từng byte B[i] để thu A[i]. Vectơ

liên hiệp dịch là ma trận được suy ra từ vectơ SV, với

[i]=(8-SV[i]) XOR 8

A[i][j]=B[i][j]<<< SV .
Bước 3: Ta thu được X[i] = A[i] XOR (

mod p)

1.7.4.Chứng minh thuật toán
Trước tiên ta cần chứng minh:
Nếu a XOR b = c thì c XOR b = a

(1)

a XOR b XOR c = a XOR c XOR b

(2)

xy mod z = [x(y mod z)] mod z

(3)

Chứng minh(1): Xét bảng chân trị sau
a

b

0

a
XORb=c
0

0

0

1

1

0

1

0

1

1

1

1

0

1

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

C
XOR b

0

Page 15


Hệ mật mã Elgamal

So sánh cột 1 và 4, ta thấy (1) đúng với số 1 bit. Vì phép XOR thực hiện trên từng bit, nên (1)
cũng dúng trong trường hợp a và b là số nhiều bit. Vậy (1) đã được chứng minh

Chứng minh(2): Tương tự, xét bảng chân trị sau:
a

b

c

a XOR b XOR
c

0
0
0
0
1
1
1
1

0

0
1
1
0
0
1
1

0
1
0
1
0
1
0
1

a XOR c XOR
b

0
1
1
0
1
0
0
1

0

1
1
0
1
0
0
1

So sánh cột 4 và 5, ta thấy (2) đã được chứng minh
Chứng minh(3): xy mod z = [x(y mod z)] mod z
Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 16


Hệ mật mã Elgamal
Đặt :

xy mod z = r1v
với 0 ≤ r1< z,
y mod z = r2vvới 0 ≤ r2< z,
x(y mod z)] mod z = xr2mod z = r3v
Dễ thấy: xy= nz+ r1 (1’)

với 0 ≤ r3< z.

y=mz + r2 với m, n,k là các số nguyên không âm (2’)
x r2=kz + r3

(3’)

Rút r2 ở biểu thức (2’) thay vào biểu thức (3’) ta được:
xy= (k+mz) + r3
So sánh với biểu thức(1’) ta được:
(k + mz)x + r3 = nz + r1
Dễ dàng nhận thấy r1 = r3 .Hay xy mod z = [x(y mod z)] mod z (đpcm)

Chứng minh thuật toán giải mã:
Theo bước 3 của quá trình mã hóa, ta có:
C[i] = B[i] XOR C[i-1]
Dựa vào (1) suy ra B[i] = C[i] XOR C[i-1]
Do B[i] = A[i] <việc dịch vòng trái từng byte của khối B[i] thao

là vectơ liên hiệp dịch của SV,

[i] bit chính là trả về trị ban đầu A[i]. Nghĩa là:

A[i] = B[i] <<
Ta chỉ cần chứng minh X[i] = A[i] XOR (

mod p) . Thay A[i] ở bước 1 của quá trình mã

hóa vào ta có:
VP = (
=[

mod p) XOR X[i] XOR (

mod p)

mod p] XOR X[i] XOR (

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

mod p) (*)
Page 17


Hệ mật mã Elgamal
Mặt khác, ta lại có:
mod p =

mod p
=[

mod p) mod p] (theo 3)

=

mod p)

=

mod p)

=[

mod p)

=

mod p
mod p
mod p)] mod p (theo (3))
mod p

.....
=

mod p

Thay vào (*) ta thu được
VP = [
=[

mod p] XOR X[i] XOR
mod p] XOR

mod p]
mod p] XOR X[i]

= X[i]
=VP(đpcm)
1.7.5 Đánh giá độ phức tạp thuật toán
Thuật toán phát triển dựa trên độ khó của bài toàn logarit trong Elgama nên vẫn giữ được ưu
điểm khó thám mã tương đương với RSA và Elgamal.
Để thám mã thành công thuật toán Elgamanl độ dài 64 byte, với máy tính đơn có bộ vi xử
lý PIV 2.6 GHz, cần thời gian 300000 giờ(khoảng 34 năm). Thế nhưng nếu sử dụng mạng gồm
100000 máy thì thời gian thám mã chỉ còn hơn 3 giờ(theo tài liệu tính toán của RSA Inc)

Thuật toán Elgamal giải quyết tốt vấn đề bảo mạt, nhờ sử dụng vectơ dịch SV theo ma trận
hàng. Một số tính năng ưu việt nổi bật của thuật toán này như sau:
Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 18


Hệ mật mã Elgamal
Độ bảo mật được tăng cường rất lớn so với các thuật toán khóa mã công khai hiện tại. Với
cùng kích thước bài toán 64byte nhu trên, vectơ dịch SV là ma traanj1x64, mỗi phân của SV có giá
trị 0 ddeens7. Đế thám mã thành công thuật toán Elgamal, ngoài việc vượt qua độ khó của bài toán
logarit như trên, cần phải tìm được chính xác SV. Tập không gian SV là
vectơ. Theo trung tâm ứng dụng siêu quốc gia MỸ,(12/2003),
một hệ thống siêu mạnh với 1500 máy chủ có thể thực hiện được 20 nghìn tỉ(2.

), phép tính

trên giây. Với hệ thống siêu mạng này, theo ước tính của tác giả, thời gian để tìm ra chính xác SV
bằng phương pháp vét cạn để thám mã là

/(2.

) =5.

(giây)

1.6.

(năm). Rõ ràng

độ bảo mật tăng lên vô cùng lớn.
Kích thước dữ liệu sau mã hóa không thay đổi. So với thuật toán Elgamal, ứng với mỗi dữ
liệu x sẽ cho ra văn bản mã c gồm

và

. Riêng thuật toán Elgamal, chỉ sinh ra văn bản mã C[i]

có kích thước bằng với kích thước văn bản gốc X[i].
Chống thám mã theo xác suất xuất hiện. Các phương pháp mã hóa theo mô hình khóa đối
xứng đều có cùng nhược điểm là tạo ra các khối văn bản mã giống nhau với cùng văn bản gốc.
Nhờ phép XOR với văn bản mã liền trước, Advanced Elgamal sẽ tạo ra các văn bản mã khác nhau
cho dù văn bản gốc đầu đều giống nhau. Điều nayloại bỏ hoàn toàn thám mã theo xác suất.
Nhận ra sự thay đổi dữ liệu trên đường truyền. Một ai đó cố tình phá hoại hệ thống bảo mật
bằng cách tạo ra các khối giống với khối văn bản mã, hay cố tình sủa đối nội dung văn bản mã trên
đường truyền. Theo thuật toán Elgamal và RSA, nơi nhận không phát hiện điều này. Kĩ thuật XOR
các văn bản mã với nhau trong thuật toán Advanced Elgamal giúp giải quyết triệt để vấn đề này.
Tốc độ thực thi cao nhờ sử dụng các phép gần với ngôn ngữ máy(phép dịch vòng, phép
XOR)
Hiệu quả trong thiết kế phần cứng: Sử dụng chung khoanrg2/3 kiến trúc phần cứng cho quá
trình mã hóa và giải mã.
1.7.6. Kết luận
Tuy tốc độ mã hóa và giải mã được cải thiện rõ nét, nhưng không ngoại lệ, thuật toán
Advanced Elgamal cũng giống như các thuật toán thuộc hệ mã công khai, vẫn còn cồng kềnh so
với thuật toán hệ bí mật. Vì vậy, thuật rất thích hợp cho các ứng dụng có kích thước nhỏ, đòi hỏi
độ bảo mật cao, không cần định danh trước đối tác sử dụng khóa. Do đó, khả năng ứng dụng trong
thương mại, giao dịch điện tử, thu tín điện tử là rất lớn.

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 19


Hệ mật mã Elgamal

II. PHẦN LẬP TRÌNH (CODE)

//------ CODE CHÍNH ------//Mã hóa và giải mã Elgamal:
//Xử lý mã hóa:
public void xulyMahoa(int alpha, int beta, int p, int k, String banRo){
System.out.print("Mã hóa:\n");
int y1=mod.tinhMod(alpha, k, p);
//y1=alpha^k mod p (Theo Bình phương và nhân)
tBanMa.setText(""+(char)y1);
for (int i=0; iint x2[] = new int[2];
x2 = doi.tachSo((int)banRo.charAt(i));
//Vì giá trị của x2 (bản rõ) có thể lớn hơn P nên cần chia nhỏ x2 ra để xử lý
//Bản mã (y1,y2=x2.beta^k mod p) (Theo Bình phương và nhân)
tBanMa.append(""+(char)((x2[0] * mod.tinhMod(beta, k, p)) % p));
tBanMa.append(""+(char)((x2[1] * mod.tinhMod(beta, k, p)) % p));
}
}

//Xử lý giải mã:
public void xulyGiaima(int alpha, int p, int a, String banMa){
System.out.print("Giải mã:\n");
tBetaGiai.setText(""+mod.tinhMod(alpha,a,p));
// Tự sinh beta=alpha^a mod p (Theo Bình phương và nhân)
int y1=(int)banMa.charAt(0);

tBanRo.setText("");
for (int i=1; i//Bản rõ x=y2*y0
//Trong đó y2 là bản mã
//y0=(y1^a)^(-1) mod p (theo Euclid + Bình phương và nhân)
int y0=dao.Calculate(mod.tinhMod(y1, a, p), p);
int ix[] = new int[2];
ix[0]=((int)banMa.charAt(i) * y0) % p;
ix[1]=((int)banMa.charAt(i+1) * y0) % p;
int x=doi.ghepSo(ix); //Ghép cặp sô trên thu được bản rõ ban đầu
tBanRo.append(""+(char)x);
}
}

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 20


Hệ mật mã Elgamal
//Chữ ký số:

//Ký tên cho văn bản:
public void Kyten(int alpha, int a, int p, int k, String vanbanVao){
int beta = mod.tinhMod(alpha, a, p);
//beta=alpha^a mod p (Theo Bình phương và nhân)
int gama = mod.tinhMod(alpha, k, p);
//gama=alpha^k mod p (Theo Bình phương và nhân)
tChuky1.setText(""+(char)beta+""+(char)gama);
int kDao = dao.Calculate(k, (p-1)); //kĐảo = k^(-1) mod p (theo Euclid)

for (int i=0; iint x[] = new int[2];
x = doi.tachSo((int)vanbanVao.charAt(i));
//Tách số tương tự Mã hóa và giải mã Elgamal
tChuky1.append(""+(char)((p-1)-(Math.abs(x[0]-a*gama)*kDao%(p-1))));
tChuky1.append(""+(char)((p-1)-(Math.abs(x[1]-a*gama)*kDao%(p-1))));
//chữ ký xichma=(bảnRõ x - a*gama)*kĐảo mod (p-1)
}
}

//Kiểm tra chữ ký:
public int kiemTraChuky(int alpha, int p, String vanbanVao, String chuky){
int demLoi=-1;
if (chuky.length()%2==0 && vanbanVao.length()==(chuky.length()/2)-1){
demLoi=0;
int gama = (int)chuky.charAt(1);
int a = mod.tinhMod((int)chuky.charAt(0),gama,p);
//ký hiệu a=beta^gama mod p (Theo Bình phương và nhân)
for (int i=0; iint y[] = new int[2];
//ký hiệu y = a* gama^xichma mod p (Theo Bình phương và nhân)
y[0]=(a * mod.tinhMod(gama,(int)chuky.charAt((i+1)*2),p)) % p;
y[1]=(a * mod.tinhMod(gama,(int)chuky.charAt((i+1)*2+1),p)) % p;
int x[] = new int[2];
//Ký hiệu x=gama^chữKý mod p (Theo Bình phương và nhân)
x = doi.tachSo((int)vanbanVao.charAt(i));
int x1 = mod.tinhMod(alpha, x[0], p) % p;
int x2 = mod.tinhMod(alpha, x[1], p) % p;
if (y[0]!=x1 || y[1]!=x2) demLoi++;
//So sánh y với x nếu khác nhau thì văn bản hoặc chữ ký bị lỗi

}
}else
JOptionPane.showMessageDialog(null, "Chữ ký hoặc văn bản bị lỗi. Kiểm tra lại");
}

return demLoi;

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 21


Hệ mật mã Elgamal

TÀI LIỆU THAM KHẢO

[1] Nguyễn Văn Tảo, Hà Thị Thanh, Nguyễn Lan Oanh, bài giảng an toàn và bảo mật thông tin,
2011.
[2] Đại học Hàng Hải, giáo trình an toàn và bảo mật thông tin,2008.
[3] Tạp chí khoa học và công nghệ, tập 44,số 2, 2006.
[4] google.com.

Chủ đề 5 – Nhóm 8 N03 – An toàn bảo mật thông tin

Page 22