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ã C
k
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ủ đề 11, “xây dựng chương trình mô phỏng 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 11
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 1
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 log
a

1
= α
k
mod p
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 2
y
2
=x.β
k
mod p
*. Giải mã:
Với y
1
, y
2
Є Zp
*
ta xác định : d
k
(y
1
, y
2
)= y
2
(y
1
a
)
-1

= 2
79
mod 569
x a y=1
79 2 2
39 4 8
19 16 128
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 3
9 256 335
4 101 x
2 528 x
1 543 394
= > y
1
= 394
+. y
2
= x. β
k
mod p
= 257 .229
79
mod 569
• tính: 229
79
mod 569
x a y=1
79 229 229
39 93 244
19 114 504

• Tính 394
109
mod 569
x a y=1
109 394 394
54 468 x
27 528 347
13 543 82
6 107 x
3 69 537
1 209 140
Kq= 140
Tính (140)
-1
mod 569
x a b y
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 4
569 1 0
140 0 1 4
9 1 -4 15
5 -15 61 1
4 16 -65 1
1 -31 126
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

: (j, α
m.j
mod p ) theo α
m.j
mod p và lưu vào
danh sách L
1
Bước 3: tính β.α
-i
mod p với 0≤i≤m-1
Bước 4: Sắp xếp các cặp t
i
: (I, β.α
-i
mod p) theo β.α
-i
mod p và lưu vào
danh sách L
2
.
Bước 5: Tìm trong hai danh sách L
1
và L
2
xem có tồn tại cặp (j, α
m.j
mod p)
và (I, β.α
-i
mod p) nào mà α

9.j
mod 79 với 0≤ j≤8
j =0 => t=1; t
j
(0,1)
j=1=> 2
9
mod 79 =38; t
j
(1,38)
j=2=>2
18
mod 79=13; t
j
(2,22)
j=3=>2
27
mod 79=46; t
j
(3,46)
j=4=>2
36
mod 79;
x a d=1
36 2 x
18 4 x
9 16 16
4 19 x
2 45 x
1 50 10

j =7 => 2
63
mod 79
x a d=1
63 2 2
31 4 8
15 16 49
7 19 62
3 45 25
1 50 65
=> t
j
(7,65)
j =8 =>2
72
mod 79
x a d=1
72 2 x
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 7
36 4 x
18 16 x
9 19 19
4 45 x
2 50 x
1 51 21
=>t
j
(8,21)
B2: Sắp xếp các cặp t
j

mod 79=40(tính theo EuClic)
=> 55.(2
1
)
-1
mod 79 = 55.40 mod 79=67
= >t
i
(1,67)
i =2:2
2
mod 79 =4 => 4
-1
mod 79= 20
=>55.(2
2
)
-1
mod 79= 55.20 mod 79=73
= >t
i
(2,73)
i =3: 2
3
mod 79 =8 => 8
-1
mod 79 = 10
=> 55.(2
3
)

i
(5,74)
i =6:2
6
mod 79 =64 =>64
-1
mod 79= 21
= > 55.(2
6
)
-1
mod 79 = 55.21 mod 79=49
= >t
i
(6,49)
i =7:2
7
mod 79=49 => 49
-1
mod 79=50
= > 55.(2
7
)
-1
mod 79=55.50 mod 79= 64
= >t
i
(7,64)
i =8:2
8

(7,64) ; t
i
(1,67) ; t
i
(4,73) ; t
i
(5,74) ; t
i
(3,76)
B5: Tìm trong hai danh sách L
1
và L
2
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 t
j
(1,38) và cặp t
i
(4,38) có tọa độ thứ 2 bằng nhau cùng bằng 38 . và cặp t
j
(5,64)

3 45 9
1 50 55
= > β= 55 đúng theo bài ra )
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(p
1/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 = 2
n
.
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= m
0
+2m
1
+4m
2
+…. + 2
n-1

=
-1 nếu m
1
=1
Quá trình tính toán cứ thế tiếp diễn cho tới khi chúng ta tìm được m
i
. Độ phức tạp của
thuật toán là : n.(2[log
2
p]+2) ~O((log
2
p)
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
Z
p
* 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.

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)
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 12
Chứng minh(1): Xét bảng chân trị sau

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:

AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 13
a b a
XORb=c
C
XOR b
0 0 0 0
0 1 1 0
1 0 1 1
1 1 0 1
a b c a XOR b XOR
c
a XOR c XOR
b
0 0 0 0 0
0 0 1 1 1
0 1 0 1 1
0 1 1 0 0
1 0 0 1 1
1 0 1 0 0
1 1 0 0 0

(3’)
Rút r
2
ở biểu thức (2’) thay vào biểu thức (3’) ta được:
xy= (k+mz) + r
3
So sánh với biểu thức(1’) ta được:
(k + mz)x + r
3
= nz + r
1
Dễ dàng nhận thấy r
1
= r
3
.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]
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 14
Do B[i] = A[i] <<SV(bước 2 quá trinh mã hóa), mặt khác, là vectơ liên hiệp dịch của
SV, việc dịch vòng trái từng byte của khối B[i] thao [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 ( mod p) (*)
Mặt khác, ta lại có:
mod p = mod p

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
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 16
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.
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 17
S
Đ
S
Đ
II. PHẦN LẬP TRÌNH

2.1.2 Hàm xử lý Mã Hóa
public void xulyMahoa(int alpha, int beta, int p, int k, String banRo){
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; i<banRo.length(); i++){
int 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));
}
}
2.1.1 Hàm xử lý Giải Mã

public void xulyGiaima(int alpha, int p, int a, String banMa){
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<banMa.length(); i+=2){
//Bản rõ x=y2*y0
//Trong đó y2 là bản mã
//y0=(y
1

y
2
=(int)banma[i]
x= y
2
(y
1
a
)
-1
mod p
i+=1
Banro+=(char)x
i>=banma.lengt
h
hienthi(Banro)
2.3 Giao Diện Chương Trình
2.3.1 Home, Mã Hóa, Giải Mã
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 21
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] />ration.htm
AT8C – Nhóm 11 – Cơ Sở Lý Thuyết Mật Mã Page 22