BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2
ĐÀM CÔNG THẮNG

ĐÀM CÔNG THẮNG

KHOA HỌC MÁY TÍNH

CHỮ KÝ KHÔNG THỂ PHỦ NHẬN VÀ ỨNG DỤNG
TRONG CÁC GIAO DỊCH ĐẶT HÀNG QUA MẠNG

LUẬN VĂN THẠC SĨ MÁY TÍNH

KHÓA 17

HÀ NỘI, 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2

ĐÀM CÔNG THẮNG

CHỮ KÝ KHÔNG THỂ PHỦ NHẬN VÀ ỨNG DỤNG
TRONG CÁC GIAO DỊCH ĐẶT HÀNG QUA MẠNG

Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số:
60 48 01 01

LUẬN VĂN THẠC SĨ MÁY TÍNH

Người hướng dẫn khoa học: TS. Lê Văn Phùng

HÀ NỘI, 2015


LỜI CẢM ƠN

Bằng sự kính trọng và lòng biết ơn sâu sắc, em xin chân thành cảm ơn TS Lê
Văn Phùng, người đã tận tình hướng dẫn và giúp đỡ em trong suốt quá trình nghiên
cứu và hoàn thành luận văn này.
Em xin chân thành cám ơn các thầy cô trong khoa Công nghệ thông tin, phòng
Sau đại học Trường Đại học Sư Phạm Hà Nội 2, các thầy cô trực tiếp giảng dạy các
học phần trong toàn khóa học đã truyền thụ những kiến thức quý báu và tạo điều kiện
cho em trong suốt quá trình học tập và nghiên cứu tại trường.
Xin cảm ơn gia đình, bạn bè, đồng nghiệp đã quan tâm, giúp đỡ tôi trong suốt
thời gian nghiên cứu và hoàn thành luận văn.
Trong quá trình nghiên cứu, hoàn thiện luận văn khó tránh khỏi những thiếu sót.
Rất mong nhận được sự góp ý của quý thầy cô và bạn bè đồng nghiệp quan tâm đến
luân văn này.

Hà nội, tháng 12 năm 2015
Học viên

Đàm Công Thắng


LỜI CAM ĐOAN
Trong quá trình hoàn thành luận văn, tôi đã tìm hiểu, nghiên cứu, tổng hợp
nhiều nguồn tài liệu khác nhau, dưới sự chỉ dẫn, giúp đỡ của giáo viên hướng dẫn, kết

quả của đề tài là sản phẩm lao động của cá nhân tôi. Các nguồn tài liệu sử dụng được
trích dẫn rõ ràng, khoa học.
Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ hình
thức nào và cũng không sao chép từ bất kỳ công trình nghiên cứu nào.
Tôi xin cam đoan những điều trên hoàn toàn là đúng.

Hà nội, tháng 12 năm 2015
Học viên

Đàm Công Thắng


1

MỤC LỤC
TRANG BÌA PHỤ

LỜI CẢM ƠN
LỜI CAM ĐOAN
MỤC LỤC .................................................................................................................... 1
DANH MỤC CÁC BẢNG .......................................................................................... 3
DANH MỤC CÁC HÌNH VẼ..................................................................................... 4
Chƣơng 1 ...................................................................................................................... 5
Tổng quan về mã hóa dữ liệu và chữ ký số ............................................................... 5
1.1 Tổng quan về mã hóa dữ liệu ............................................................................. 5
1.1.1 Cơ sở toán học của lý thuyết mật mã ........................................................... 5
1.1.2 Những vấn đề chung nhất về mã hóa dữ liệu ............................................ 15
1.1.3 Giới thiệu một số hệ mã hóa cổ điển .......................................................... 17
1.1.4 Khái quát về các hệ mã hóa khóa hiện đại ................................................ 24
1.2. Tổng quan về chữ ký số ................................................................................... 29

1.2.1 Khái niệm về chữ ký số................................................................................ 29
1.2.2 Một số cách phân loại chữ ký số ................................................................. 34
1.2.3. Giới thiệu một số chữ ký số thông dụng ................................................... 35
1.2.4 Đại diện tài liệu và hàm băm ...................................................................... 40
1.2.5 Các ứng dụng của chữ ký số ....................................................................... 41
Kết luận ...................................................................................................................... 44
Chƣơng 2 .................................................................................................................... 45
Chữ ký số đặc biệt và chữ ký số không thể phủ nhận ........................................... 45
2.1. Sơ đồ thuật toán và ứng dụng của một số loại chữ ký đặc biệt ................... 45
2.1.1 Chữ ký “mù” RSA ....................................................................................... 45
2.1.2 Chữ ký mù nhóm ......................................................................................... 50
2.1.3 Chữ ký mù bội (Blind Multi Signature) .................................................... 53


2

2.1.4 Chữ ký không thể phủ nhận ....................................................................... 57
2.2 Sơ đồ chữ ký không thể phủ nhận ................................................................... 58
2.2.1 Sơ đồ chữ ký không thể phủ nhận Chaum – Van Antverpen.................. 58
2.2.2 Tính hợp thức của các giao thức ................................................................ 59
2.2.3 Ví dụ về các giao thức kiểm thử và chối bỏ ............................................... 62
2.2.4 Các ứng dụng chữ ký số không thể phủ nhận trong đời sống kinh tế -xã
hội................................................................................................................................ 65
Kết luận ...................................................................................................................... 66
Chƣơng 3 .................................................................................................................... 67
Xây dựng chƣơng trình ứng dụng chữ ký không thể phủ nhận trong việc xác thực
các giao dịch đặt hàng qua mạng ............................................................................. 67
3.1 Bài toán đặt ra và môi trƣờng thử nghiệm ..................................................... 67
3.1.1 Bài toán ......................................................................................................... 67
3.1.2 Môi trƣờng thử nghiệm ............................................................................... 67

3.2 Chức năng chính của chƣơng trình và thuật toán sử dụng .......................... 68
3.2.1 Chức năng ký trên đơn hàng và gửi đơn hàng kèm chữ ký .................... 68
3.2.2 Chức năng thực hiện giao thức kiểm thử .................................................. 68
3.2.3 Chức năng thực hiện giao thức chối bỏ ..................................................... 70
3.3 Một số giao diện quan trọng trong chƣơng trình .......................................... 71
3.3.1 Giao diện nhập thông số chung .................................................................. 71
3.3.2 Giao diện nhập đơn hàng và nhận đơn hàng ............................................ 72
3.3.3 Giao diện giao thức kiểm thử...................................................................... 73
3.3.4 Giao diện giao thức chối bỏ ......................................................................... 74
3.4. Kết quả thử nghiệm chƣơng trình và đánh giá ............................................. 76
KẾT LUẬN ................................................................................................................ 78
TÀI LIỆU THAM KHẢO ........................................................................................ 79


3

DANH MỤC CÁC BẢNG
Bảng 1.1 Mô tả quá trình tính toán của thuật toán Euclid ............................................... 6
Bảng 1.2 Mô tả quá trình tính toán của thuật toán Euclid mở rộng ................................. 8
Bảng 1.3 Tìm phần tử nghịch đảo của 3 trong Z7 .......................................................... 13
Bảng 1.4 Mô tả quá trình mã hóa của hệ mã hóa VIGENERE ...................................... 22


4

DANH MỤC CÁC HÌNH VẼ
Hình 1.1 Quá trình tạo chữ ký ........................................................................................ 31
Hình 1.2 Quá trình xác thực chữ ký số .......................................................................... 33
Hình 2.1 Lưu đồ thuật toán chữ ký mù RSA ................................................................. 47
Hình 3.1 Sơ đồ chức năng ký trên đơn hàng và gửi đơn hàng kèm chữ ký ................... 68

Hình 3.2 Sơ đồ chức năng thực hiện giao thức kiểm thử ............................................... 69
Hình 3.3 Sơ đồ chức năng thực hiện giao thức chống chối bỏ: ..................................... 71
Hình 3.4 giao diện nhập thông số chung ........................................................................ 71
Hình 3.5 Giao diện nhập đơn hàng ................................................................................ 72
Hình 3.6 Giao diện nhận đơn hàng ................................................................................ 72
Hình 3.7 Giao diện kiểm thử của N và G ....................................................................... 73
Hình 3.8 Thông báo xác nhận chữ ký ............................................................................ 74
Hình 3.9 Thông báo yêu cầu thực hiện giao thức chối bỏ ............................................. 74
Hình 3.10 Giao diện chương trình khi thực hiện với chữ ký giả mạo ........................... 74
Hình 3.11 Giao diện thực hiện giao thức chối bỏ .......................................................... 75
Hình 3.12 Thông báo chữ ký trong đơn hàng nhận được là giả mạo. ............................ 75
Hình 3.13 Thông báo yêu cầu thiết lập lại giao dịch. .................................................... 76


5

Chƣơng 1
Tổng quan về mã hóa dữ liệu và chữ ký số
1.1 Tổng quan về mã hóa dữ liệu
1.1.1 Cơ sở toán học của lý thuyết mật mã

1.1.1.1 Khái niệm
Ước số , bội số
Cho hai số nguyên a, b ( b  0 ). Nếu có một số nguyên q sao cho a=b*q, ta nói
rằng a chia hết cho b, kí hiệu b\a. Ta nói b là ước của a và a là bội của b.
Ước chung lớn nhất, bội chung nhỏ nhất
- Số nguyên d được gọi là ước chung của các số nguyên a1, a2,…,an, nếu nó là
ước của tất cả các số đó.
- Số nguyên m được gọi là bội chung của các số nguyên a1, a2,…,an, nếu nó là
bội của tất cả các số đó.

- Một ước chung d của tất cả các số nguyên a1, a2, …, an trong đó mọi ước chung
của a1, a2, …, an đều là ước của d, thì d được gọi là ước chung lớn nhất (gcd) của a1, a2,

…, an.
Ký hiệu d = gcd(a1, a2,…, an) hay d= gcd(a1, a2,…, an).
- Nếu gcd(a1, a2, …, an) =1 thì các số a1, a2, …, an được gọi là nguyên tố cùng
nhau.
- Một bội chung m>0 của các số nguyên a1, a2, …, an, trong đó mọi bội chung
của a1, a2, …, an, đều là bội của m thì m được gọi là bội chung nhỏ nhất (BCNN) của

a1, a2, …, an.
Ký hiệu m = lcm(a1, a2, …, an) hay m=BCNN(a1, a2, …, an).
- Tập Zn và Zn*
+ Zn={ 0, 1, 2, …, n-1} là tập các nguyên tố không âm < n.


6

+ Zn* = { e  Zn , e là nguyên tố cùng nhau với n}. Tức e  0 .
Thuật toán Euclide tìm ước chung lớn nhất
Bài toán:
- Input: Cho hai số không âm a,b (a  b)
- Output: gcd(a,b)
Thuật toán mô phỏng bằng ngôn ngữ lập trình Pascals

Readln(a, b)
While b>0 do
Begin
r:=a mod b; a:= b; b:=r;
end;

writeln(a);
Ví dụ: a = 30, b = 18; gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6.

Bảng 1.1 Mô tả quá trình tính toán của thuật toán Euclid
a

b

r

a = b.q + r

30

18

12

30 = 18 * 1 + 12

18

12

6

18 = 12 * 1 + 6

12


6

0

12 = 6 * 2 + 0

6

0

Thuật toán Euclide mở rộng
Bài toán:
- Input: Cho hai số nguyên không âm a, b ( a  b)
- Output: d = gcd(a, b) và hai số x, y sao cho ax + by = d
- Thuật toán:
1. Nếu b = 0 thì đặt d  a, x  1, y  0 và cho ra (d, x, y).
2. Đặt x2 = 1, x1 = 0, y2 = 0, y1 = 1.


7

3. Trong khi còn b > 0 thực hiện:
3.1 q  a div b, r  a mod b, x  x2 – qx1, y  y2 – qy1.
3.2 a  b, b  r, x2  x1, x1  x, y2  y1 và y1  y.
4. Đặt d  a, x  x2, y  y2, và cho ra kết quả (d, x, y).
Ở đây d  a giống như trong ngôn ngữ tựa Pascal là d:=a (gán giá trị a vào biến d).
Mô phỏng thuật toán bằng ngôn ngữ Pascal :
Readln(a,b)
IF b = 0 THEN
Begin

d:=a; x:=1; y:= 0;
Writeln( d, x, y);
End
ELSE
Begin
x2:=1; x1:= 0; y2:=0; y1:=1;
While b>0 Do
Begin
q:= a div b; r:= a mod b;
x:= x2 –q*x1; y:=y2-q*y1;
a:= b; b:=r; x2:=x1; x1:= x; y2:=y1; y1:=y;
end;
d:=a; x:=x2; y:=y2;
writeln ( d, x1, x2);
end;
Ví dụ:


8

Dùng thuật toán Euclide mở rộng cho các số a = 4864 và b = 3458, lần lượt
được các giá trị sau đây cho các biến a, b, q, r, x, y, x1, x2, y1, y2 (sau mỗi chu trình
thực hiện hai lệnh 3.1 và 3.2).

Bảng 1.2 Mô tả quá trình tính toán của thuật toán Euclid mở rộng
a

b

q


r

x

4864

3458

3458

1406

1

1406

1

1406

646

2

646

646

114


2

114

76

76
38

y

x1

x2

y1

y2

0

1

1

0

-1


1

0

-1

1

-2

3

-2

1

3

-1

114

5

-7

5

-2


-7

3

5

76

-27

38

-27

5

38

-7

38

1

38

32

-45


32

-27

-45

38

0

2

0

-91

128

-91

32

128

-45

Dễ thử lại rằng sau mỗi lần thực hiện chu trình gồm hai lệnh 3.1 và 3.2 các giá
trị x, y, r thu được luôn thỏa mãn 4864. x + 3458.y = r, và do đó khi kết thúc các vòng
lặp (ứng với giá trị b = 0), thực hiện tiếp lệnh 4 ta được kết quả d = 38, x=32 và y = 45, cặp số (32, -45) thỏa mãn 4864.32 + 3458. (-45) = 38.
Thuật toán cho kết quả*: GCD(4864, 3458) = 38.


1.1.1.2 Quan hệ đồng dư
Khái niệm
Cho các số nguyên a, b, m (m>0). Ta nói rằng a và b đồng dư với nhau theo
modul m nếu chia a và b cho m, ta nhận được cùng một số dư.
Ký hiệu a  b ( mod m)
Ví dụ: 17  5 ( mod 3) vì chia 17 và 5 cho 3 được cùng số dư là 2
Nhận xét các mệnh đề sau đây là tương đương:

a  b ( mod m)
m\ ( a – b )
Tồn tại số nguyên t sao cho a = b + mt
Các tính chất của quan hệ đồng dư


9

1/ Quan hệ đồng dư là quan hệ tương đương Z
Với mọi số nguyên dương m ta có

a  a ( mod m) với mọi a  Z ; ( Tính chất phản xạ)
a  b ( mod m) thì b  a ( mod m); ( Tính chất đối xứng)
a  b ( mod m) và b  c ( mod m) thì a  c ( mod m); ( Tính chất bắc cầu)
2/ Tổng hay hiệu các đồng dư
( a + b)( mod n)  [( a mod n) + ( b mod n) ] ( mod n)
( a - b) (mod n)  [(a mod n) – ( b mod n)] (mod n)
Tổng quát:
Có thể cộng hoặc trừ từng vế nhiều đồng dư thức theo cùng modulo m, ta được
một đồng dư thức theo cùng modulo m tức là:
k


k

i 1

i 1

Nếu ai  bi ( mod m), i = 1, …, k thì:  ti a i   ti bi (mod m) với ti  1

3/ Tích các đồng dư
( a*b)( mod n)  [( a mod n) * ( b mod n) ] (mod n)
Tổng quát:
Có thể nhân từng vế với đồng dư thức theo cùng một modulo m, ta được một
đồng dư thức theo cùng modulo m, tức là
k

k

i 1

i 1

Nếu ai  bi ( mod m) với i= 1, …k, thì ta có  ai   bi (mod m)
Hệ quả
+ Có thể cộng hoặc trừ cùng một số vào hai vế của một đồng dư thức.
+ Có thể chuyển vế các số hạng của đồng dư thức bằng cách đổi dấu các số hạng đó.
+ Có thể cộng vào một vế của đồng dư thức một bội của modulo

a  b ( mod m)  a + km  b ( mod m) với mọi k  Z
+ Có thể nhân hai vế của một đồng dư thức cùng với một số:


a  b ( mod m)  ac  bc ( mod m) với mọi c  Z


10

+ Có thể nâng lũy thừa bậc nguyên không âm cho 2 vế của một đồng dư thức

a  b ( mod m)  an  bn ( mod m) với mọi n  Z+
+ Có thể chia 2 vế đồng dư thức cho một ước chung nguyên tố với modulo

c\a, c\b, (c,m)=1, a  b ( mod m)  a/c  b/c ( mod m).
+ Có thể nhân 2 vế đồng dư thức và modulo cùng với một số nguyên dương:
Nếu a  b ( mod m), c>0  ac  bc ( mod mc)
+ Có thể chia 2 vế đồng dư thức và modulo cho cùng một số nguyên dương là ước
chung của chúng:
Nếu c/( a, b, m)  a/c  b/c ( mod m/c)
+ a  b ( mod m )  a  b ( mod k ) với k\ m
+ a  b ( mod m )  gcd(a, m) = gcd( b,m)
Các lớp thặng dư
- Quan hệ “đồng dư” theo modulo m trên tập Z ( tập các số nguyên) là một quan
hệ tương đương ( vì có tính chất phản xạ, đối xứng, bắc cầu), do đó nó tạo ra trên tập Z
một phần hoặc chỉ gồm các lớp tương đương khi và chỉ khi chúng có cùng một số dư
khi chia cho m.
- Mỗi lớp tương đương đại diện bởi một số duy nhất Zm = { 0, 1, 2, …, m-1} là
số dư khi chia các số trong lớp cho m, ký hiệu một lớp được đại diện bởi số a là [a]m.
Như vậy [a]m = [b]m  a  b (mod m)
Vì vậy ta có thể đồng nhất Zm với tập các lớp tương đương theo modulo m.
- Zm = {0, 1, 2,…,m-1} được gọi là tập các thặng dư đầy đủ theo modulo m.
Mọi số nguyên bất kỳ đều có thể tìm được trong Zm một số đồng dư với mình theo


modulo m.
1.1.1.3 Số nguyên tố
Khái niệm
Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước là 1 và chính nó.
Ví dụ: Các số 2, 3, 5, 7, 11, 13, 17, 19, 31, 37 ... là số nguyên tố.


11

Một số định lý về số nguyên tố
- Định lý về số nguyên dương lớn hơn 1: Mọi số nguyên dương n > 1 đều có thể
biểu diễn được duy nhất dưới dạng

n  P1n P2n ...Pknk trong đó: k, n là các số tự nhiên,
1

2

Pi ( i = 1, 2, 3, …, k) là các số nguyên tố, từng đôi một khác nhau.
- Định lý Mersence: Cho p= 2k – 1, nếu p là số nguyên tố thì k phải là số nguyên tố.
Hàm Euler
Cho số nguyên dương a, số lượng các số nguyên dương bé hơn n và nguyên tố
cùng nhau với n được ký hiệu ( p) và gọi là hàm Euler. [3]
Nhận xét: Nếu p là số nguyên tố, thì ( p)  p  1
Ví dụ:
Tập các số nguyên không âm nhỏ hơn 7 là Z7 = { 0, 1, 2, 3, 4, 5, 6}
Do 7 là số nguyên tố, nên tập các số nguyên dương nhỏ hơn 7 và nguyên tố
cùng nhau với 7 là Z7* ={ 1, 2, 3, 4, 5, 6}. Khi đó | Z| = ( p)  p  1 =7 – 1 = 6
Định lý về hàm Euler

Nếu n là tích của hai số nguyên tố p, q thì (n)  ( p).(q)  ( p  1)(q  1)
Định lý Ferma
Nếu p là số nguyên tố, a là số nguyên thì ap  a( mod p ).
Nếu p nguyên tố, p không chia hết cho a thì a p1  1(mod p)
Ví dụ: 47  4( mod 7); 47-1  1 ( mod 7)
Định lý Euler
Nếu gcd( a, m) = 1 thì

a ( m)  1(mod m)

Trường hợp m là số nguyên tố, ta có định lý Ferma.
Ví dụ : m = 10,  (m)=  (2).  (5)=1*4=4.

Ta có 74  1( mod 10), 94  1( mod 10), 214  1( mod 10)
Hệ quả 1
Nếu gcd (c, m)=1 và a  b ( mod  (m)) với a,b là các số tự nhiên thì


12

ca = cb(mod m) và suy ra

ca  ca mod (m) (mod m).

Nhận xét : Hệ quả trên giúp giảm nhẹ việc tính toán đồng dư của lũy thừa bậc
cao.
Ví dụ : Ta thấy  (15) =  (5).  (3) = 4*2 =8 và 1004  4 (mod 8)
Do đó 21004 ( mod 15) = 24(mod 15) = 16 ( mod 15) = 1.
Hệ quả 2
Nếu các số nguyên e, d thỏa mãn e.d  1 ( mod  (m)), thì với mọi số c nguyên

tố cùng nhau với m, ta có (ce)d  c ( mod m)
Hệ quả này đóng vai trò then chốt trong việc thiết lập các hệ mã mũ sau này ví
dụ: RSA

1.1.1.4 Phần tử nghịch đảo đối với phép nhân trong Zn theo mod n
Định nghĩa:
Cho a  Zn, nếu tồn tại b  Zn sao cho a.b  1(mod n) , ta nói b là phần tử
nghịch đảo của a trong Zn và ký hiệu a-1.

Một phần tử có phần tử nghịch đảo được gọi là phần tử khả nghịch.
Định lý:

gcd(a, n) = 1  phần tử a  Zn có phần tử nghịch đảo.
Chứng minh:
Nếu a. a-1  1 ( mod n) thì a. a-1= 1+ kn  a. a-1 – kn = 1  ( a, n) = 1.
Nếu ( a, n) = 1, ta có a. a-1 + kn = 1  a. a-1 = 1 + kn do đó a. a-1  1( mod n).
Thuật toán Euclid mở rộng tìm phần tử nghịch đảo:
Input: n, a Zn
Output: phần tử nghịch đảo của a
Mô phỏng thuật toán bằng ngôn ngữ lập trình Pascal:
Procedure Invert(a,n);
Begin


13

g0:=n; g1:=a; u0:=1; u1:=0; v0:=0; v1:=1;
i:=1;
While gi ≠ 0 do
Begin

y:= gi-1 div gi; gi+1 := gi-1 – y.gi;
ui+1:= ui-1 – y.ui ; vi+1:= vi-1 – y.vi;
i:=i+1;
End;
t:= vi+1;
if t>0 then a-1:=t else a-1:=t+n;
End;
Ví dụ: Tìm phần tử nghịch đảo của 3 trong Z7
Tức là phải giải phương trình 3.x  1 ( mod 7), x sẽ là phần tử nghịch đảo của 3.

Bảng 1.3 Tìm phần tử nghịch đảo của 3 trong Z7
I

gi

ui

vi

0

7

1

0

1

3


0

1

2

2

1

1

-2

3

3

0

Vì t = v2= -2 <0 do đó x = a-1 := t+n = -2 + 7 = 5
Vậy 5 là phần tử nghịch đảo của 3 trong Z7
Định lý Euler tổng quát

Nếu ( a, n) = 1 thì

a  ( n) mod n = 1

Hệ quả : Nếu p là số nguyên tố và ( a, p) = 1 thì ap-1(mod p) = 1


1.1.1.5 Nhóm Cyclic
Ký hiệu: Zn = {0, 1, 2, 3, …, n-1}.
Zn * = { x  Zn , x là nguyên tố cùng nhau với n }.

y


14

Khái niệm Nhóm Cyclic:
Nhóm (G, *) được gọi là Nhóm Cyclic nếu nó được sinh ra bởi một phần tử g
 G. Tức là với mỗi a  G, đều tồn tại số n  N để g n = g * … * g = a. Khi đó
g được gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm G. [3]
Trong lý thuyết số, người ta đã chứng minh được các tính chất sau đây của các phần
tử nguyên thuỷ:
1/. Với mọi số nguyên tố p, Zp* là nhóm Cyclic, và có (p-1) phần tử nguyên thuỷ.
a1

a1

as

2/. Nếu p - 1 = p1 . p2 ... ps là khai triển chính tắc của p - 1, và nếu
a

p-1
p1

 1 (mod p), …., a


p-1
ps

 1 (mod p)

thì a là phần tử nguyên thuỷ theo mod p (tức của Zp*).
3/. Nếu g là phần tử nguyên thuỷ theo mod p, thì   gi mod p với mọi i mà
gcd(i, p -1) = 1, cũng là phần tử nguyên thuỷ theo mod p.
Định lý 1:
Nếu p là số nguyên tố thì Zp* là nhóm Cyclic. Nếu bZn* thì bφ(n)≡1(mod n).
Nếu p-số nguyên tố thì φ(p) = p-1. Do đó với bZp*, tức b nguyên tố với p, thì
bφ(p)≡1(mod n) hay bp-1≡1(mod n).
Định lý 2:
Cho p là một số nguyên tố, và g  Zp*. Khi đó, g là phần tử sinh  g

p-1
q

1

(mod p) đối với mọi ước số nguyên tố q của p - 1.
Ví dụ:
Cho p = 19. Khi đó p - 1 = 18 = 2.32. Bây giờ giả sử lấy g = 2 ϵ Z19*, xét 2 có phải là
phần tử nguyên thủy hay không?
Ta có (p-1)/2 =9 và (p-1)/3 = 6 và thấy ngay rằng hệ đồng dư thức sau là đúng:
26 ≠ 1 mod (19) và 29≠ 1 mod(19).
Do đó, 2 là một phần tử nguyên thủy trong Z*19.



15

Định lý 3:
Xét tập hợp Z*p, trong đó p là số nguyên tố. Giả sử g là một phần tử nguyên thủy
trong Z*p. Khi đó, mỗi một phần tử bất kỳ a  Z*n, đều tồn tại một j nguyên (j ≥ 1) sao
cho a = gj ; số a là phần tử nguyên thủy nếu và chỉ nếu gcd(j, p-1)=1. Như vây, có bao
nhiêu số j mà nguyên tố với p-1 thì sẽ có bấy nhiêu phần tử nguyên thủy trong Z*p.
Ví dụ:
Xét Z*467, theo lý luận trên thì 2 là một phần tử nguyên thủy trong Z *467, do đó ta
sẽ tìm tất cả các phần tử nguyên thủy dạng 2j với j thỏa mãn điều kiện
gcd(j, p-1)=1, tức là gcd(j, 467-1) = gcd(j,466) = 1
Vì 466 = 2.233, nên mọi j không phải là số chẵn và thỏa mãn điều kiện 1 ≤ j < 233 thì
2j đều là phần tử nguyên thủy.
Cấp (Bậc) của Nhóm Cyclic:
Cho (G, *) là Nhóm Cyclic với phần tử sinh g và phần tử trung lập e.
Nếu tồn tại số tự nhiên nhỏ nhất n mà g n = e, thì G sẽ chỉ gồm có n phần tử
khác nhau: e, g, g2 , g3 , . . . , g n – 1 . Khi đó G được gọi là nhóm Cyclic hữu hạn cấp

n. Nếu không tồn tại số tự nhiên n để g n = e, thì G có cấp .
Ví dụ: (Z +, +) gồm các số nguyên dương là nhóm Cyclic với phần tử sinh g =

1, e = 0. Đó là Nhóm Cyclic vô hạn, vì không tồn tại số tự nhiên n để g n = e.
Cấp (Bậc) của một phần tử trong Nhóm Cyclic:
Phần tử   G được gọi là có cấp d, nếu d là số nguyên dương nhỏ nhất sao
cho  d = e, trong đó e là phần tử trung lập của G.
1.1.2 Những vấn đề chung nhất về mã hóa dữ liệu

1.1.2.1 Giới thiệu về mã hóa
Để đảm bảo An toàn thông tin lưu trữ trong máy tính (giữ gìn thông tin cố định) hay
đảm bảo An toàn thông tin trên đường truyền tin (trên mạng máy tính), người ta phải

“Che giấu” các thông tin này.


16

“ Che ” thông tin (dữ liệu) hay “ Mã hóa” thông tin là thay đổi hình dạng thông
tin gốc, và người khác khó nhận ra.
Hệ mã hóa được định nghĩa là một bộ năm (P, C, K, E, D), trong đó:
- P là một tập hữu hạn các bản rõ có thể.
- C là một tập hữu hạn các bản mã có thể.
- K là tập hữu hạn các khóa có thể.
- E là tập các hàm lập mã.
- D là tập các hàm giải mã.
Với khóa lập mã ke  K có hàm lập mã eke  E, eke : P  C
Với khóa giải mã kd  K có hàm giải mã dkd  E, dkd : P  C sao cho:

dkd (eke( x))  x, x  P .
Ở đây x được gọi là bản rõ, eke( x) được gọi là bản mã.[6]
Mã hoá nhằm đảm bảo các tính chất sau của thông tin:
Tính bí mật (Confidentiality): thông tin chỉ được tiết lộ cho những ai được phép.
Tính toàn vẹn (Integrity): thông tin không thể bị thay đổi mà không bị phát hiện.
Tính xác thực (Authentication): người gửi (hoặc người nhận) có thể chứng minh
đúng họ.
Tính không chối bỏ (Non-repudiation): người gửi hoặc nhận sau này không thể
chối bỏ việc đã gửi hoặc nhận thông tin. [5]

1.1.2.2 Phân loại hệ mã hóa
1/ Hệ mã hóa khóa đối xứng
Mã hóa khóa đối xứng là Hệ mã hóa mà biết được khóa lập mã thì có thể “dễ”
tính được khóa giải mã và ngược lại. Đặc biệt một số Hệ mã hóa có khóa lập mã (ke)

và khóa giải mã trùng nhau (kd), như Hệ mã hóa “dịch chuyển” hay DES.

2/ Hệ mã hóa khóa công khai


17

- Hệ mã hóa khóa công khai hay Hệ mã hóa phi đối xứng do Diffie và Hellman
phát minh vào những năm 1970.
- Hệ mã hóa khóa phi đối xứng là Hệ mã hóa có khóa lập mã và khóa giải mã
khác nhau (ke  kd), biết được khóa này cũng “khó” tính được khóa kia.
- Khóa lập mã cho công khai, gọi là khóa công khai (Public key).
- Khóa giải mã giữ bí mật, còn gọi là khóa riêng (Private key) hay khóa bí mật.
Sơ đồ: ( Pivest, Shamir, Adleman đề xuất năm 1977)
- Tạo cặp khóa bí mật và khóa công khai (a, b):
Chọn bí mật số nguyên tố lớn p, q, tính n=p*q, công khai n đặt P= C= Zn
- Tính bí mật (n)  ( p  1) * (q  1) . Chọn khóa công khai b  (n) , nguyên tố
cùng nhau (n) .
- Khóa bí mật a là phần tử nghịch đảo của b theo (n) : a * b  1(mod (n))
- Tập cặp khóa ( bí mật, công khai)

K   a , b  / a , b  Zn , a * b  1(mod (n))
Với bản rõ x  P và bản mã y  C , định nghĩa:
- Hàm mã hóa: y  ek ( x)  xb mod n
- Hàm giải mã: x  dk ( y)  ya mod n .
1.1.3 Giới thiệu một số hệ mã hóa cổ điển
Hệ mã hóa đối xứng đã được dùng từ rất sớm, nên còn gọi là Hệ mã hóa đối xứng – cổ
điển ( gọi ngắn gọn là Hệ mã hóa đối xứng cổ điển). Trong hệ mã hóa đối xứng cổ điển
bản mã hay bản rõ là dãy các ký tự Latin.
Lập mã: thực hiện theo các bước sau:

1/. Nhập bản rõ ký tự: RÕ_CHỮ.

2/. Chuyển RÕ_CHỮ  RÕ _SỐ

3/. Chuyển RÕ_SỐ  MÃ_SỐ.

4/. Chuyển MÃ_SỐ  MÃ_CHỮ.

Giải mã: thực hiện theo các bước sau:


18

1/. Nhập bản mã ký tự: MÃ_CHỮ.

2/. Chuyển MÃ_CHỮ  MÃ_SỐ.

3/. Chuyển MÃ_SỐ  RÕ_SỐ.

4/. Chuyển RÕ_SỐ  RÕ_CHỮ.

Để chuyển từ CHỮ sang SỐ hay ngược lại từ SỐ trở về CHỮ, người ta theo một
quy ước nào đó, ví dụ chữ cái thay bằng số theo modulo 26 như sau:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 1 1 1

1 1 1 1 1 1 1 2 2 2

2 2 2


0 1 2

3 4 5 6 7 8 9 0 1 2

3 4 5

Để thực hiện mã hóa hay giải mã với các “số”, người ta dùng các phép toán số học
theo modulo 26.
Mã hóa cổ điển gồm nhiều hệ, ví dụ:
Hệ mã hóa dịch chuyển: Khóa có 1 “chìa”. (Thể hiện bằng 1 giá trị).
Hệ mã Affine:

Khóa có 2 “chìa”. (Thể hiện bằng 2 giá trị).

Hệ mã hóa thay thế:

Khóa có 26 “chìa”. (Thể hiện bằng 26 giá trị).

Hệ mã hóa VIGENERE: Khóa có m “chìa”. (Thể hiện bằng m giá trị).
Hệ mã hóa HILL:

Khóa có ma trận “chìa”. (chùm chìa khóa).

1.1.3.1. Hệ mã khóa dịch chuyển
Sơ đồ:
Đặt P = C = K = Z26 . Bản mã y và bản rõ x
Với khóa k

Z26 .


K, ta định nghĩa:

Hàm Mã hóa: y = ek (x) = (x +k) mod 26
Hàm Giải mã: x = dk (y) = (y – k) mod 26
Ví dụ:
Bản rõ chữ: T O I
Chọn khóa k = 3.

N A Y

T H A

V I R U S


19

Bản rõ số:
19 14 8 26 13

0 24

26

19

7 0 26

21 8 17


20 18

Với phép mã hóa y = ek (x) = (x +k) mod 26 = (x + 3) mod 26, ta nhận được:
Bản mã số:
22 17 11 3 16

3 1 3 22 10 3 3 24

W R

D B D W

11 20 23 21

Bản mã chữ:
L

D Q

K

D D Y

L

U

X

V


Với phép giải mã x = dk (y) = (y – k) mod 26 = (y – 3) mod 26, ta nhận lại được bản rõ
số, sau đó là bản rõ chữ.
Độ an toàn: Độ an toàn của mã dịch chuyển: Rất thấp.
Tập khóa K chỉ có 26 khóa, nên việc phá khóa (thám khóa) có thể thực hiện dễ dàng
bằng cách thử kiểm tra từng khóa: k = 1, 2, 3, …, 26.

1.1.3.2. Hệ mã hóa thay thế ( Hoán vị toàn cục)
Sơ đồ
Đặt P = C = Z26 . Bản mã y và bản rõ x

Z26 .

Tập khóa K là tập mọi hoán vị trên Z26 .
Với khóa k =

K, tức là 1 hoán vị trên Z26 , ta định nghĩa:

Mã hóa: y

(x) =

Giải mã: x

(y) =

(x)
(y)

Ví dụ:

Bản rõ chữ: T O I
Chọn khóa k =

N A Y

T H A

V I R U S

là hoán vị:

A B C D E F G H I

J

K L

M N O P Q R S T U V X Y

Y X V U T S R Q P O N M L
Mã hóa theo công thức: y

(x) =

(x):

K J

I


H G F E D C B A Z


20

Bản mã chữ:
E J

P

Z K

Y V Z E

Giải mã theo công thức x

Q

Y Z C

P

G

D

F

(y), ta nhận lại được bản rõ chữ.


(y) =

Độ an toàn: Độ an toàn của mã thay thế: Thuộc loại cao.
Tập khóa K có 26! khóa ( > 4.1026), nên việc phá khóa ( thám mã) có thể thực
hiện bằng cách duyệt tuần tự 26! hoán vị của 26 chữ cái.
Để kiểm tra tất cả 26! khóa, tốn rất nhiều thời gian !
Hiện nay với hệ mã này, người ta có phương pháp thám mã khác nhanh hơn.

1.1.3.3. Hệ mã hóa AFFINE
Sơ đồ:
Đặt P = C = Z26 . Bản mã y và bản rõ x
Tập khóa K = {(a, b), với a, b
Với khóa k = (a, b)

Z26 .

Z26 , gcd(a,26) = 1}

K, ta định nghĩa:

Phép Mã hóa: y

(x) = (a x + b)

Phép Giải mã: x

(y) =

mod 26


(y - b) mod 26

Ví dụ:
Bản rõ chữ:

CHIEUNAYOVUONHOA

Chọn khóa k = (a, b) = (3, 6).
Bản rõ số: x =
2 7 8
Mã hóa theo công thức: y

4 20 13 0 24 14 21 20 14 13 7
(x) = (a x + b) mod 26 = (3x + 6) mod 26

Bản mã số:y =
12 1 4 18 14 19 6 0
Bản mã chữ:

22 17

MBESOTGAWROWTBWG

14 22 19 1 22 6

14 0


21


Giải mã theo công thức x

(y) =

(y - b) mod 26

= 3-1 (y – 6) mod 26 = 9 * (y – 6) mod 26.
Độ an toàn: Độ an toàn của Hệ mã hóa Affine: Rất thấp.
+ Điều kiện gcd(a, 26) = 1 để bảo đảm a có phần tử nghịch đảo a-1 mod 26, tức là thuật
toán giải mã dK luôn thực hiện được.
+ Số lượng a

Z26 nguyên tố với 26 là

(26) = 12, đó là:

1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25
Các số nghịch đảo theo (mod 26) tương ứng: 1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25
+ Số lượng b

Z26 là 26.

+ Số các khóa (a, b) có thể là 12 * 26 = 312. Rất ít !
Như vậy việc dò tìm khóa mật khá dễ dàng.

1.1.3.4. Hệ mã hóa VIGENERE
Sơ đồ:
Đặt P = C = (Z26)m, m là số nguyên dương, các phép toán thực hiện trong Z26 .

Bản mã Y và bản rõ X


(Z26)m. Khóa k = (k1, k2, …, km), gồm m phần tử.

Mã hóa: Y = (y1, y2,…, ym)
Giải mã: X = (x1, x2, …, xm)

(x1, x2, …, xm)=(x1 + k1, x2 + k2, …, xm + km) mod 26
(y1, y2, …, ym)= (y1 - k1, y2 - k2, …, ym - km) mod 26

Ví dụ:
Bản rõ chữ:

THISISACRYPTOSYSTEM

Chọn khóa k = “KWORD” = {10, 22, 14, 17, 3} với độ dài m = 5.
Bản rõ số: SX = 19 7 8 18 8 0 2 17 24 15 19 14 18 24 18 19 4 12
Mã hóa:
Chia bản rõ SX thành các đoạn, mỗi đoạn gồm m = 5 số.
Với mỗi đoạn, áp dụng công thức mã hóa, ta nhận được bản mã số.