ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
-----------------------------
NGUYỄN QUÝ HÀO
NGHIÊN CỨU PHỐI HỢP HAI PHƯƠNG PHÁP NÉN
và MÃ HOÁ THÔNG TIN
Ngành:
Công nghệ thông tin
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số:
60 48 15
LUẬN VĂN THẠC SĨ NGÀNH CNTT
Giảng viên hướng dẫn: PGS. TS TRỊNH NHẬT TIẾN
HÀ NỘI, 11-2012
2
MỤC LỤC
MỤC LỤC
........................................................................................................................................... 2
DANH MỤC CÁC BẢNG......................................................................................................................... 4
DANH MỤC CÁC HÌNH VẼ.................................................................................................................... 5
LỜI MỞ ĐẦU 6
Chương 1:
MỘT SỐ KHÁI NIỆM CƠ BẢN ................................................................................... 8
1.1
CÁC ĐỊNH LÝ QUAN TRỌNG ................................................................................... 8
1.1.1
Định lý Euler ..................................................................................................................... 8
1.1.2
Định lý Fermat (hệ quả của định lý Euler) ....................................................................... 8
1.1.3
Định lý đồng dƣ Trung Quốc ........................................................................................... 8
1.1.4
Định lý Bezout .................................................................................................................. 9
1.2
MỘT SỐ THUẬT TOÁN ............................................................................................... 9
1.2.1
Thuật toán Euclidean ........................................................................................................ 9
1.2.2
Thuật toán Euclidean mở rộng ....................................................................................... 10
1.2.3
Thuật toán bình phƣơng và nhân.................................................................................... 11
1.2.4
Thuật toán xác suất kiểm tra số nguyên tố ..................................................................... 12
1/.
Thuật toán Miller – Rabin............................................................................................... 12
1.3
KHÁI NIỆM ENTROPY .............................................................................................. 13
1.3.1
Định nghĩa Entropy......................................................................................................... 13
1.3.2
Tính chất của Entropy..................................................................................................... 14
Chương 2:
PHƢƠNG PHÁP MÃ HOÁ ......................................................................................... 15
2.1
CÁC KHÁI NIỆM CƠ BẢN ........................................................................................ 15
2.1.1
Hệ mã hoá khoá đối xứng............................................................................................... 16
2.1.2
Hệ mã hoá khoá phi đối xứng......................................................................................... 16
2.1.3
Hệ mã hoá RSA .............................................................................................................. 17
2.1.3.1
Lịch sử hình thành hệ mã hoá RSA ................................................................................ 17
2.1.3.2
Hệ mã hoá RSA đầu tiên................................................................................................. 17
2.1.3.3
Định nghĩa hệ mã hoá RSA ............................................................................................ 18
2.2
CÁC CHUẨN KỸ THUẬT TRONG PKCS............................................................... 19
2.2.1
Tổng quan về PKCS và PKCS#1 v2.1 .......................................................................... 19
2.2.1.1
PKCS ............................................................................................................................... 19
2.2.1.2
PKCS#1 v2.1 ................................................................................................................... 19
2.2.2
Các ký hiệu trong PKCS#1 v2.1 .................................................................................... 20
2.2.3
Các kiểu khóa.................................................................................................................. 21
2.2.3.1
Khóa công khai RSA ....................................................................................................... 22
2.2.3.2
Khóa bí mật RSA............................................................................................................. 22
2.2.4
Cơ sở chuyển đổi dữ liệu I2OSP và OS2IP ................................................................... 23
2.2.4.1
Chuyển đổi dữ liệu I2OSP .............................................................................................. 24
2.2.4.2
Chuyển đổi dữ liệu OS2IP .............................................................................................. 24
2.2.5
Cơ sở của hệ mật mã....................................................................................................... 25
2.2.5.1
Cơ sở hệ mã hóa RSAEP................................................................................................ 25
2.2.5.2
Cơ sở hệ mã hóa – RSADP ............................................................................................ 26
2.2.6
Lƣợc đô mã hóa .............................................................................................................. 28
2.2.6.1
Tổng quan về lược đồ mã hóa ........................................................................................ 28
2.2.6.2
Các kỹ thuật hỗ trợ.......................................................................................................... 28
2.2.6.3
Lược đồ RSAES – OAEP............................................................................................... 29
2.2.7
Ý nghĩa của việc áp dụng EME - OAEP trƣớc khi mã hóa RSA ................................. 34
2.2.8
Vấn đề sinh khóa RSA ................................................................................................... 35
2.3
CHUẨN MÃ HÓA DỮ LIỆU TIÊN TIẾN – AES ..................................................... 37
3
2.3.1
Mục đích nghiên cứu chuẩn AES .................................................................................. 37
2.3.2
Tổng quan........................................................................................................................ 38
2.3.3
Các khái niệm cơ sở ........................................................................................................ 38
2.3.3.1
Input, Output, Key ........................................................................................................... 38
2.3.3.2
Byte .................................................................................................................................. 38
2.3.3.3
Ma trận trạng thái (State Matrix). .................................................................................. 39
2.3.3.4
Hộp thay thế S – Box và InvS – Box ............................................................................... 40
2.3.4
Đặc tả thuật toán.............................................................................................................. 41
2.3.4.1
Sinh khóa con .................................................................................................................. 41
2.3.4.2
Hoạt động mã hóa .......................................................................................................... 42
2.3.4.3
Hoạt động giải mã .......................................................................................................... 43
Chương 3:
PHƢƠNG PHÁP NÉN DỮ LIỆU................................................................................ 44
3.1
TỔNG QUAN VỀ NÉN DỮ LIỆU.............................................................................. 44
3.1.1
Mã nén dữ liệu ................................................................................................................ 44
3.1.1.1
Nén dữ liệu, bít trung bình .............................................................................................. 44
3.1.1.2
Mã tổng và mã phân tách................................................................................................ 46
3.1.2
Định lý Shannon ............................................................................................................. 47
3.2
MÔ HÌNH THỐNG KÊ ................................................................................................ 51
3.2.1
Mô hình thống kê tĩnh..................................................................................................... 51
3.2.2
Mô hình thống kê động................................................................................................... 51
3.2.3
Một số mã nén cơ bản..................................................................................................... 52
3.2.3.2
Mã Huffman .................................................................................................................... 57
3.2.3.3
Lưu đồ giải mã Fanon, Shannon, Huffman ................................................................... 60
3.3
MÔ HÌNH TỪ ĐIỂN ..................................................................................................... 62
3.3.1
Giới thiệu ......................................................................................................................... 62
3.3.2
Kỹ thuật từ điển............................................................................................................... 62
3.3.2.1
Nguyên lý LZ ................................................................................................................... 62
3.3.2.2
Các thuật toán nén LZ .................................................................................................... 66
Chương 4:
PHỐI HỢP HAI PHƢƠNG PHÁP NÉN VÀ MÃ HOÁ THÔNG TIN .................... 80
4.1
MÔ HÌNH PHỐI HỢP HAI PHƢƠNG PHÁP NÉN VÀ MÃ HOÁ THÔNG TIN 80
4.1.1
Về không gian lƣu trữ ..................................................................................................... 80
4.1.2
Vấn đề an ninh ................................................................................................................ 81
4.1.3
Vấn đề thời gian xử lý dữ liệu ........................................................................................ 82
4.2
Mô hình phối hợp hai phƣơng pháp nén và mã hoá dữ liệu.......................................... 82
4.3
CHƢƠNG TRÌNH THỬ NGHIỆM ............................................................................ 86
4.3.1
Mô tả chung .................................................................................................................... 86
4.3.2
Ý tƣởng cài đặt ................................................................................................................ 86
4.3.2.1
Ngôn ngữ lập trình .......................................................................................................... 86
4.3.2.2
Cấu trúc chƣơng trình ..................................................................................................... 87
4.3.3
Thực hiện......................................................................................................................... 92
4.3.4
Đánh giá .......................................................................................................................... 94
KẾT LUẬN
......................................................................................................................................... 98
TÀI LIỆU THAM KHẢO ........................................................................................................................ 99
4
DANH MỤC CÁC BẢNG
STT
Tên bảng
Trang
1.
Bảng 2.1: Thay thế dãy 4 bit sang cơ số 16
40
2.
Bảng 2.2: Ma trận trạng thái khởi đầu
40
3.
Bảng 3.1: Ví dụ về mã nén Shannon
57
4.
Bảng 3.2: Mã hoá các kí tự trong xâu “go go gophers” theo mã
Huffman
60
5.
Bảng 3.3: Giải mã bản mã “00111010000” theo lƣu đồ giải mã Hình
3.8
62
6.
Bảng 3.4: Quá trình nén xâu “bcabbcbccbababc” theo thuật toán LZ77
68
7.
Bảng 3.5: Quá trình giải nén theo thuật toán LZ77bản mã
bca[3,1,b][4,1,b][2,1,c][3,1a][2,2,b][5,1,””]
68
8.
Bảng 3.6:
Quá trình nén xâu “ aaabbabaabaaabab” bằng thuật toán LZ78
72
9.
Bảng 3.7: Quá trình nén bằng thuật toán LZ78 bản mã
“(0,a)(1,a)(0,b)(3,a)(4,a)(5,a)(4,b)”
73
10.
Bảng 3.8: Quá trình nén xâu “aabababaaababb” bằng thuật toán LZW
79
11.
Bảng 3.9: Quá trình giải nén bản mã “001352411” theo thuật toán
LZW
80
12.
Bảng 4.2: Bảng kết quả thử nghiệm đánh giá về mặt hiệu quả nén
96
13.
Bảng 4.2: Bảng kết quả thử nghiệm đánh giá về mặt thời gian
97
5
STT
1.
DANH MỤC CÁC HÌNH VẼ
Tên bảng
Hình 2.1: Nguy cơ bị tấn công khi truyền thông tin trên mạng máy tính
Trang
16
17
4.
5.
Hình 2.2: Mô hình truyền thông sử dụng hệ mã hoá khoá đối xứng [12]
Hình 2.3: Mô hình truyền thông sử dụng hệ mã hoá khoá công khai
[12]
Hình 2.4: Sơ đồ mã hoá EME – OAEP [13]
Hình 2.5: Tóm lƣợc quy trình xử lý RSAES – OAEP - ENCRYPT
6.
7.
8.
9.
10.
Hình 2.6: Tóm lƣợc quy trình xử lý RSAES – OAEP – DECRYPT
Hình 2.7: Sơ đồ kết hợp RSA và AES
Hình 2.8: Hộp S –Box sử dụng trong quá trình mã hoá AES [14]
Hình 2.9: Hộp InvS –Box sử dụng trong quá trình mã hoá AES [14]
Hình 3.1: Quá trình nén dữ liệu
35
11.
12.
Hình 3.2: Văn bản tổng
Hình 3.3: Mã tổng
47
13.
Hình 3.4: Mã hoá theo mô hình thống kê động
47
52
14.
Hình 3.5: Giải mã hoá theo mô hình thống kê động
53
15.
Hình 3.6: Quá trình tạo mã Fanno
5
16.
Hình 3.7: Xây dựng mã Huffman
59
17.
Hình 3.8: Lƣu đồ giải mã Fanon, Shanon, Huffman
61
18.
Hình 3.9: Lƣợng tin
64
19.
Hình 3.10: Quá trình thực hiện nén bằn mã LZ
66
20.
Hình 3.11: Sơ đồ nén LZ78
70
21.
Hình 3.12: Sơ đồ giải nén thuật toán LZ78
71
22.
Hình 3.13: Sơ đồ nén dữ liệu thuật toán LZW
75
23.
Hình 3.14: Sơ đồ giải nén dữ liệu thuật toán LZW
78
24.
Hình 4.1: Luồng xử lý nén và mã hoá
82
25.
Hình 4.2: Mô hình phối hợp hai phƣơng pháp nén và mã hoá thông tin
83
26.
Hình 4.3: Nội dung tệp bản rõ
84
27.
Hình 4.4: Nén tệp bằng phƣơng pháp LZW
84
28.
Hình 4.5: Mã hoá tệp đã nén bằng LZW
85
29.
Hình 4.6: Mã hoá tệp bản rõ bằng AES
85
2.
3.
30.
HHình 4.7: Nén tệp tin sau khi mã hoá bằng AES
18
32
33
38
41
41
45
86
6
LỜI MỞ ĐẦU
Quá trình lƣu trữ và truyền tải thông tin luôn luôn có 2 yếu tổ đƣợc quan tâm
hàng đầu là: tính an toàn bảo mật và kích thƣớc của tệp tin.
Đã có rất nhiều các phần mềm, các chƣơng trình đƣợc viết để giải quyết hai vấn
đề đƣợc đặt ra. Tuy nhiên các phần mềm phần lớn chỉ quan tâm tới một trong hai yếu
tố chỉ nén dữ liệu Winzar, Winzip, 7Zip… hoặc
chỉ mã hoá nhƣ: Enterprise,
TrueCrypt… tuy nhiên nếu chỉ nén dữ liệu kích thƣớc tệp tin đƣợc giảm nhƣng lại
không bảo đảm tính an toàn thông tin. Ngƣợc lại nếu chỉ mã hoá chỉ đảm bảo tính an
toàn nhƣng không giải quyết đƣợc vấn đề giảm dung lƣợng lƣu trữ hơn thế mã hoá tệp
tin lớn tốn nhiều thời gian và băng thông để truyền tải cũng tăng theo.
Trong khi đó nếu phối hợp cả hai quá trình trên sẽ đem lại rất nhiều lợi ích:
giảm dung lƣợng lƣu trữ, giảm băng thông truyền tải, giảm thời gian mã hoá, tăng tính
bảo mật cho tệp tin so với tệp tin chỉ mã hoá đơn thuần.
Từ ý nghĩa thực tiễn quan trọng nêu trên là động lực để tôi nghiên cứu đề tài:
“Nghiên cứu phối hợp hai phƣơng pháp nén và mã hoá thông tin”.
Trong luận văn sẽ đề xuất mô hình và giải pháp phối hợp hai phƣơng pháp nén
và mã hoá thông tin: sử dụng các thuật toán nén để nén dữ liệu sau đó dùng phƣơng
pháp mã hoá đối xứng để mã hoá tệp tin sau, cuối cùng là dùng mã khoá khoá bất đối
xứng RSA để mã hoá khoá chung của AES.
Luận văn đƣợc trình bày theo cấu trúc sau:
-
-
Chƣơng 1: trình bày cơ sở toán học đƣợc sử dụng trong quá trình nén và mã
hoá thông tin gồm: các khái niệm, các định lý, định nghĩa và một số thuật
toán cơ bản
Chƣơng 2: trình bày về các thuật toán mã hoá: AES, RSA và các kỹ thuật
có liên quan đƣợc sử dụng trong quá trình mã hoá.
Chƣơng 3: trình bày về các phƣơng pháp nén: Fanno, Shanon, Huffman,
Lzw…
Chƣơng 4: trình bày về hƣớng nghiên cứu phối hợp các phƣơng pháp nén và
mã hoá thông tin. Giải pháp thực hiện và đánh giá mô hình nghiên cứu.
Ngoài ra còn trình bày về quá trình cài đặt chƣơng trình thử nghiệm mô hình
phối hợp bằng ngôn ngữ lập trình C#.Net.
Học viên: Nguyễn Quý Hào
7
LỜI CẢM ƠN
Tôi xin chân thành cảm ơn PGS.TS Trịnh Nhật Tiến, thầy đã trực tiếp hƣớng
dẫn, giúp đỡ tôi từ lúc nhận đề tài đến lúc hoàn thành luận văn tốt nghiệp này.
Tôi xin chân thành cảm ơn tất cả các thầy cô giáo trong khoa Công nghệ thông
tin - Trƣờng ĐH Công Nghệ - ĐH Quốc Gia Hà Nội, những ngƣời đã nhiệt tình giảng
dạy, truyền đạt những kiến thức trong suốt thời gian tôi học tập tại trƣờng cũng nhƣ
đóng góp những ý kiến quý báu, những định hƣớng chuẩn mực giúp tôi hoàn thành
luận văn này.
Cuối cùng tôi xin cảm ơn tất cả các bạn trong lớp đã góp ý, trao đổi hỗ trợ cho
tôi trong suốt thời gian vừa qua.
Tôi xin chân thành cảm ơn!
Học viên: Nguyễn Quý Hào
8
Chương 1: MỘT SỐ KHÁI NIỆM CƠ BẢN
1.1
CÁC ĐỊNH LÝ QUAN TRỌNG
1.1.1 Định lý Euler
Định lý:
Cho a
Z, m
N, m > 1. Nếu UCLN (a, m) = 1 thì a
(m)
1 (mod m)
1.1.2 Định lý Fermat (hệ quả của định lý Euler)
Định lý:
Cho a
Z và k là một số nguyên tố khi đó ak
Nếu UCLN(a, k) = 1 thì ak-1
a (mod k)
1 (mod k)
1.1.3 Định lý đồng dƣ Trung Quốc
Định lý:
Cho m1, m2, …, mr là các số nguyên tố cùng nhau từng đôi một nghĩa là
UCLN(m1, m2) = 1
i, j = 1, 2, …, r ;
i ≠ j. Giả sử a1, a2, … ar
Z khi đó hệ
phƣơng trình đồng dƣ
x
a1 (modm1 )
x
a 2 (modm 2 )
....
x
a r (modm r )
Có nghiệm duy nhất theo modulo M = m1m2, … mr là x =
r
ai M i y i trong đó
i 1
Mi =
M
và yi = Mi-1 mod mi
mi
Ví dụ: Tìm nghiệm đồng dƣ của hệ phƣơng trình đồng dƣ:
x
3(mod 2)
x
6(mod 3)
x
8(mod 7)
Giải:
M = 2 x 3 x 7 = 42 M1 =3 x 7 = 21; M2 = 2 x 7 = 14;
M3 = 2 x 3 = 6
y1 = 21-1 mod 2 = 1; y2 = 14-1 mod 3 = 2; y3 = 6-1 mod 7 = 6
x = 3 x 21 x 1 + 6 x 14 x 2 + 8 x 6 x 6 =519 mod 42 = 15
9
1.1.4 Định lý Bezout
Định lý:
Cho a, b
N, a > b
+ Tồn tại x, y
1; ta có:
Z sao cho ax + by = UCLN(a, b)
+ Nếu a, b nguyên tố cùng nhau thì tồn tại x,y
Z | ax + by = 1
+ a, b nguyên tố cùng nhau khi và chi khi tồn tại x, y
1.2
MỘT SỐ THUẬT TOÁN
1.2.1 Thuật toán Euclidean
Cơ sở số học của thuật toán:
Cho a, b, d
Z, d ≠ 0 nếu a d và b d thì a mod b d
Nội dung thuật toán:
INPUT: r0, r1
N, r0 > r1
0
OUPUT: d = UCLN(r0, r1)
Thuật toán:
Bƣớc 1: Nếu r1 = 0 trả về d := r0, kết thúc thuật toán
Nếu r1 ≠ chuyển sang bƣớc 2
Bƣớc 2: r := r0 mod r1; r0 := r1; r1 = r; quay lại bƣớc 1
Z | ax + by = 1
10
1.2.2 Thuật toán Euclidean mở rộng
Cơ sở số học của thuật toán: trong thuật toán Euclidean tìm UCNL của hai số
0, ta thấy thuật toán là quá trình thực hiện chuỗi phép chia lấy phần dƣ
nguyên r0 > r1
dễ dàng ta thấy
UCLN(r0, r1) = UCLN(r1, r2) = UCLN(r2, r3) = … = UCLN(rm-1, rm)
Với r2 = r0 mod r1 r3 = r1 mod r2 ….
Dựa trên thuật toán Euclidean ngƣời ta mở rộng thuật toán trên để tính đƣợc
số nghịch đảo theo modulo m trong vành Zm
Xét dãy tuần tự các số nguyên t0, t1, … tm nhƣ sau:
t0 = 0
t1 = 1
tj = (tj-2 – qj-1tj-1) mod r0, với j
2
Ta có kết quả quan trọng sau:
Định lý:
Với mọi j, 0
j
2 ta có rj
tjr1 (mod r0)
Nội dung thuật toán:
INPUT: n, b
N (n> b
0)
OUTPUT: t = b-1 mod n
Giả mã thuật toán:
1. n0 = n
2. b0 = b
3. t0 = 0
4. t = 1
5. q = n0 div b0
6. r = n0 – qb0
7. while r > 0 do
7.1 temp = t0 – qt
7.2 if temp
0 then temp = temp mod n
11
7.3 if temp < 0 then temp = n – ((-temp) mod n)
7.4 t0 = t
7.5 t = temp
7.6 n0 = b0
7.7 b0 = r
q = n0 div b0
r = n0 – qb0
8. if b0 ≠ 1 then b không khả nghịch theo modulo n
9. else b-1 = t mod n
1.2.3 Thuật toán bình phƣơng và nhân
Giả sử có các số nguyên x, b và n. Ta phải tính xb mod n. Thuật toán: “Bình
phƣơng và nhân” sau đây sẽ giúp ta tính lũy thừa này khá đơn giản. Đây là một thuật
toán quan trọng đƣợc sử dụng trong qui trình mã hóa cũng nhƣ giải mã của hệ mã hoá
RSA
Nội dung thuật toán:
INPUT:
x
Zn , b
Z, 0 < b < n,
b: viết dƣới dạng nhị phân với k chữ số nhị phân b = b1b2…bk; bi = {0, 1}
OUTPUT: số a = xb mod n
Giả mã thuật toán:
1.
2.
3.
4.
5.
6.
z=1
for i = 1 to k do
z = z. z mod n
if bi = 1 then z = z.x mod n
a=z
return a
12
1.2.4 Thuật toán xác suất kiểm tra số nguyên tố
INPUT: một số nguyên dƣơng n
OUPUT: n là hợp số
Sau đây ta sẽ đi xem thuật toán Miller - Rabin giải quyết bài toán này
1/. Thuật toán Miller – Rabin
Kiểm tra Miller:
Giả sử n là một số nguyên dƣơng lẻ, khi đó ta biểu diễn đƣợc n – 1 = 2st với s là
một số nguyên không âm, t là một số nguyên dƣơng lẻ. Ta nói n vƣợt qua đƣợc kiểm
tra Miller cơ sở a (a
0
Z, a > 0) nếu at
1 (mod n) hoặc a 2
k
t
-1 (mod n) với k nào đó
k < s.
Mệnh đề:
Nếu n là một số nguyên tố thì n vƣợt qua kiểm tra Miller cơ sở
a, 0 < a < n
Định nghĩa:
Nếu n vƣợt qua Miller cơ sở a thì n đƣợc gọi là số nguyên tố giả cơ sở a
Số nguyên dƣơng n > 1 đƣợc gọi là số giả nguyên tố mạnh cơ sở a nếu nó là
hợp số và vƣợt qua đƣợc kiểm tra Miller cơ sở a
Thuật toán Miller – Rabin
INPUT:
OUTPUT:
n N, lẻ, N > 1
“n là nguyên tố” hoặc “n là hợp số”
Nội dung thuật toán:
Miller – Rabin – Test(n)
1.
2.
3.
4.
5.
6.
7.
8.
Viết n – 1 = 2km (m lẻ)
Chọn một số ngẫu nhiên a, 1 a n – 1
b: = am mod n
if b = 1 then return “n là số nguyên tố rồi” và kết thúc
for i = 0 to k – 1 do
if b = n – 1 then return “n là số nguyên tố” và thoát
b = b2 mod n
Tra lời “n” là hợp số
Mệnh đề:
Thuật toán Miller – Rabin cho bài toán hợp số là thuật toán Monter – Carlo
định hƣớng có. Nghĩa là câu trả lời “b là hợp số” luôn đúng. Câu trả lời “n là số
nguyên tố” có xác suất sai không quá 1/4
13
Miller – Rabin – Test(n)
Thuật toán Miller – Rabin với t lần thực hiện kiểm tra Miller:
N, lẻ, n > 1, t
N, số lần kiểm tra
INPUT:
n
OUTPUT:
“n là nguyên tố” hoặc “n là hợp số”
1. Viết n – 1 = 2km (m lẻ)
2. for i := 1 to t do
2.1 Chọn một số ngẫu nhiên a, 1
a
n–1
2.2 test:= false
2.3 b: = am mod n
2.4 if b = 1 then test: = true
else
for i = 0 to k – 1 do
if b = n – 1 then test:= true
else b = b2 mod n
2.5 if test = false then return “n là hợp số” và thoát
3. return “n là số nguyên tố”
Xác suất sai khi trả lời n là số nguyên tố không vƣợt quá (1/4) t
1.3
KHÁI NIỆM ENTROPY
1.3.1 Định nghĩa Entropy
Định nghĩa. Độ bất định :
Xét không gian mẫu
= {w1, w2, w3, ..., wm} với xác suất của các sự kiện ngẫu
nhiên cơ bản tƣơng ứng là p1, p2, p3, ..., pm. Entropy của không gian mẫu Ω sinh ra do
phép thử ngẫu nhiên mà kết quả là một trong số các sự kiện của không gian mẫu Ω hay
độ bất định của việc đoán nhận sự kiện ngẫu nhiên cơ bản xảy ra đƣợc ký hiệu H(Ω) là
một số tính theo công thức sau:
H(Ω) =
m
pi . log( pi )
i 1
Định lý:
Có một số δ > 1 mà H( ) =
m
pi . log ( pi )
i 1
Giả sử chúng ta lấy việc đoán nhận sự kiện nào trong 2 sự kiện đồng xác suất
làm đơn vị đo độ bất định thì khi đó H(2) = 1 vì thế log (2) = 1. Suy ra, = 2. Chúng
ta có công thức H(k) = log2(k).
14
Độ bất định xác định không phụ thuộc vào việc chọn đơn vị để đo. Nếu chọn
độ bất định của việc đánh số đề tức là đoán nhận 1 trƣờng hợp trong số 100 trƣờng hợp
đồng khả năng làm đơn vị đo và nếu có một việc có độ bất định là 3, tức là H(k) =
log100(k) = 3. Khi dùng đơn vị đo là việc đoán nhận một trƣờng hợp trong số 10 khả
năng làm đơn vị thì chỉ số đo sẽ là 6, vì H(k) = log10(k) = 2.log100(k) = 6. Chính vì vậy
mà chúng ta có thể chọn đơn vị đo bất kỳ, ví dụ δ = 2.
m
Sau này, chúng ta sẽ dùng công thức
pi log 2 ( pi ) để tính độ bất định
i 1
(entropy) cho một không gian mẫu Ω với xác suất các phần tử là p1, p2, p3, ..., pm. Lƣu
ý, H( ) càng lớn thì việc đoán nhận sự kiện ngẫu nhiên cơ bản nào sẽ xảy ra càng khó
(càng bất định).
1.3.2 Tính chất của Entropy
Tính chất:
a) Entropy là một đại lƣợng luôn luôn dƣơng hoặc bằng không H(Ω)≥ 0.
b) Entropy bằng 0 khi có một sự kiện ngẫu nhiên cơ bản có xác suất bằng 1 và
xác suất của tất cả các sự kiện ngẫu nhiên cơ bản còn lại bằng 0. Nghĩa là có
một sự kiện ngẫu cơ bản luôn luôn xảy ra. Nhƣ vậy thì việc đoán nhận một
kết quả xảy ra khi thực hiện một phép thử là không có ý nghĩa gì nữa.
c) Entropy đạt giá trị cực đại khi xác suất của các sự kiện ngẫu nhiên cơ bản của
không gian mẫu bằng nhau. Lúc đó độ bất định của việc đoán nhận một sự
kiện ngẫu nhiên cơ bản nào đó xảy ra là lớn nhất.
Định lý:
Nếu Ω, Φ là hai không gian mẫu cùng có m phần tử và nếu Φ là đồng xác suất
thì H(Ω) ≤ H(Φ).
Dấu bằng xẩy ra khi và chỉ khi với mỗi sự kiện ngẫu nhiên cơ bản trong Ω có
xác suất pi thì trong Ф cũng có một sự kiện ngẫu nhiên cơ bản có xác suất pi, tức là Ω
cũng là không gian đồng xác suất.
Nhƣ vậy, định lý khẳng định rằng entropy của không gian đồng xác suất là lớn
nhất trong số các không gian mẫu có cùng số các sự kiện ngẫu nhiên cơ bản.
Ví dụ:
Ví dụ đơn giản để minh hoạ nhƣ sau: giả sử chúng ta tung con xúc sắc mà ở
mặt 1 chúng ta gắn chì vào. Do khối lƣợng chì nặng nên đa số trƣờng hợp mặt 6 xuất
hiện (mặt 6 đối diện với mặt 1). Vì thế việc đoán xem mặt nào xuất hiện trở nên dễ
hơn.
15
Chương 2: PHƢƠNG PHÁP MÃ HOÁ
2.1
CÁC KHÁI NIỆM CƠ BẢN
Trong một phạm vi hẹp, có thể hiểu nhiệm vụ cơ bản của mật mã học là
nghiên cứu những phƣơng pháp cho phép hai ngƣời có thể truyền thông với nhau trên
một kênh thông tin không an toàn, sao cho ngƣời thứ ba dù có thể lấy cắp đƣợc thông
tin cũng không thể hiểu đƣợc nội dung những thông tin truyền đi đó.
Thông điệp mà Alice muốn gửi tới Bob đƣợc gọi là bản rõ (plaintext), kí hiệu
là x. Để bảo vệ thông tin Alice cần sử dụng một cơ chế để truyền bản rõ x sang một
dạng biểu diễn khác – bản mã (ciphertext), đƣợc kí hiệu là y và gửi bản y. Bob sau khi
nhận đƣợc bản mã y anh sử dụng một cơ chế để chuyển đổi bản mã y về bản rõ x.
Công việc của Alice chuyển từ bản rõ x sang bản mã y đƣợc gọi là mã hóa
(encryption), công việc ngƣợc lại của Bob chuyển đổi từ bản mã y sang bản rõ x đƣợc
gọi là giải mã (decryption.
Yêu cầu cơ bản nhất với mỗi hệ mã hoá là bảo đảm qui tắc mã hóa và giải mã
phải có khả năng tính toán hiệu quả, đồng thời đối phƣơng khi có bản mã y, khả năng
tìm ra bản rõ x hoặc khóa K là khó (rất khó thực hiện trong thời gian cho phép). Sau
đây là định nghĩa một hệ mã hoá dƣới hình thức toán học:
Định nghĩa:
Một hệ mật mã là một bộ 5 (P, C, K, E, D) trong đó:
1.
2.
3.
4.
P là một tập hợp hữu bạn các bản rõ có thể
C là một tập hợp hữu hạn các bản mã có thể
K, không gian khóa, là một tập hữu hạn các khóa có thể
Với mỗi khóa k K, tồn tại một qui tắc mã hóa ek E và một qui tắc giải
mã tƣơng ứng dk D, trong đó et: P
C và dk : C
P là các ánh xạ thỏa
mãn dk(ek(x)) = x x P
Hình 2.1 Nguy cơ bị tấn công khi truyền thông tin trên mạng máy tính
16
2.1.1 Hệ mã hoá khoá đối xứng
Theo mô hình chung của các hệ mã hoá khoá đối xứng, Alice và Bob bí mật
chọn khóa K, sau đó K đƣợc sử dụng cho quy tắc mã hóa cũng nhƣ giải mã. Theo
phƣơng pháp mã hóa này thì khóa để mã hóa chính là khóa để giải mã hoặc trong một
số hệ mật thì khóa để mã hóa và khóa để giải mã tuy khác nhau nhƣng dễ dàng tính
đƣợc thành phần này khi đã biết thành phần kia. Từ đó mà các hệ mã hoá khoá đối
xứng còn đƣợc gọi với tên khác là hệ mã hoá khóa bị mật, hay hệ mã hoá khóa đối
xứng. Dƣới đây là mô hình truyền thông sử dụng hệ mã hoá khoá đối xứng
Hình 2.2: Mô hình truyền thông sử dụng hệ mã hoá khoá đối xứng [12]
2.1.2 Hệ mã hoá khoá phi đối xứng
Một hạn chế của một hệ mã hoá khoá đối xứng là nó yêu cầu việc truyền đi khóa
K giữa Alice và Bob trên một kênh an toàn trƣớc khi bất kì thông điệp mã hóa nào đƣợc
truyenf đi. Trên thực tế điều này rất khó thực hiện khi mà hai ngƣời ở xa nhau
Từ mặt hạn chế của các hệ mã hoá khoá đối xứng đã phân tích ở trên, ngƣời ta
nghiên cứu và đề xuất các hệ mã hoá công khai (hệ mã hoá bất đối xứng). Tƣ tƣởng chung
của các hệ mã hoá khoá phi đối xứng là mỗi khóa K trong hệ mã hoá bao gồm hai thành
phần: thành phần thứ nhất dành cho quá trình mã hóa, đƣợc gọi là khóa công khai và
thành phần thứ hai dành cho quá trình giải mã, đƣợc gọi là khó bí mật (khóa riêng). Có thể
hình dung Bob là ngƣời sẽ nhận các thông điệp bí mật từ những ngƣời khác, anh tìm một
qui tắc mã hóa eK và một quy tắc giải mã tƣơng ứng dK. Bob công bố công khai khoá e K
và giữ bí mật khoá dK. Sau đó Alice và những ngƣời khác có thể sử dụng eK để mã hoá các
thông điệp trƣớc khi gửi tới Bob. Về mặt lý thuyết, Bob phải đảm bảo ngƣời khác không
thể tìm ra dK tƣơng ứng từ eK trong thời gian thực. Ý tƣởng về hệ mã hoá công khai đƣợc
Diffie và Hellman đề xuất vào năm 1976. Và sự hiện thực hoá đầu tiên của ý tƣởng này
vào năm 1977 là công của Rivest, Shamir và Adleman họ là những ngƣời phát minh ra hệ
mã hoá RSA
17
Hình 2.3: Mô hình truyền thông sử dụng hệ mã hoá khoá công khai [12]
2.1.3 Hệ mã hoá RSA
2.1.3.1 Lịch sử hình thành hệ mã hoá RSA
RSA (Ron Rivers, Adi Shamir và Len Adleman) là một hệ mã hoá khoá phi
đối xứng. Nó là thuật toán đầu tiên phù hợp với việc tạo ra chữ kí điện tử và đánh dấu
một sự tiến bộ vƣợt bậc trong mật mã học. RSA đang đƣợc ứng dụng phổ biến trong
giao dịch điện tử, đảm bảo an toàn với điều kiện độ dài đủ lớn. Thuật toán đƣợc mô tả
lần đầu tiên vào năm 1977 tại Học viện công nghệ Massachusettes (MIT).
Trƣớc đó, vào năm 1973, Clifford Cocks, một nhà toán học ngƣời Anh đã mô
tả thuật toán tƣơng tự. Với khả năng tính toán tại thời điểm đó thì thuật toán này không
khả thi và chƣa bao giờ đƣợc cài đặt thực nghiệm. Phát minh này chỉ đƣợc công bố
năm 1977 vì đƣợc xếp vào loại tuyệt mật
2.1.3.2 Hệ mã hoá RSA đầu tiên
1/. Bài toán phân tích một số tự nhiên ra thừa số nguyên tố
Các thuật toán mã hóa công khai hiện đại đƣợc nghiên cứu và đề xuất dựa trên
việc nghiên cứu lý thuyết độ phức tạp của thuật toán và tính khó của các bài toán mà
thuật toán tốt nhất đƣợc tìm ra là để giải quyết bài toán đó cũng không chấp nhận đƣợc
trong thời gian thực với các máy tính hiện đại
Thuật toán RSA là thuật toán mã hóa dựa trên tính khó của bài toán phân tích
một số nguyên tố tự nhiên (đủ lớn) ra thừa số nguyên tố. Giả sử có n là một số tự nhiện
n = p.q trong đó p, q là các số nguyên tố. Với n là số tự nhiên đủ lớn, có độ dài trên
100 chữ số thập phân, thì bài toán phân tích n ra thừa số nguyên tố (tức tìm p, q) chƣa
18
có thuật toán trong thời gian đa thức. Với các máy tính hiện đại thì chƣa thể giải quyết
bài toán này trong thời gian thực
2/. Bộ số RSA
Cho p, q là hai số nguyên tố khác nhau và n = p.q khi đó (n) = (p-1)(q-1).
Lấy a thuộc Z
(n)
sao cho a khả nghịch. Giả sử b = a-1 mod (n)
a/ Định nghĩa:
Bộ các số (n, p, q, a, b) trong đó n, p, q, a, b đƣợc đề cập ở trên đƣợc gọi là bộ
số RSA.
Ta có tính chất quan trọng sau đây của bộ số RSA.
b/ Định lý:
Nếu (n, p, q, a, b) là các bộ số RSA thì
x
Zn ta có: xab mod n = x
c/ Ứng dụng:
Cho bộ số RSA (n, p, q, a, b), x
Zn. Đặt y = xb mod n. Khi đó ta có cách tìm
x từ y bởi công thức: x = ya mod n. Từ đó đƣa ra định nghĩa hệ mã hoá RSA.
2.1.3.3 Định nghĩa hệ mã hoá RSA
Định nghĩa:
Cho bộ số RSA (n, p, q, a, b) trong đó p, q là những số nguyên tố cỡ 512 bit
hoặc lớn hơn. Hệ mã hoá RSA với khóa K = (n, p, q, a, b) là hệ mã hoá với P = C = Zn,
qui tắc mã hóa và giải mã nhƣ sau:
Qui tắc mã hóa: với mỗi x
ek : Z n
x
P = Zn
Zn
y = xb mod n
Qui tắc giải mã:
dk: Zn
y
Trong đó:
Zn
x = ya mod n
(n, b) là thành phần khóa công khai
(p, q, a) là thành phần khóa bí mật
19
2.2
CÁC CHUẨN KỸ THUẬT TRONG PKCS
2.2.1 Tổng quan về PKCS và PKCS#1 v2.1
2.2.1.1 PKCS
PKCS là viết tắt của Publick – Key Cryptography Standards, là một tập hợp
các chuẩn trong mã hoá hóa công khai, đƣợc đánh thứ tự PKCS#1 tới PKCS #15.
PKCS đƣợc phát triển bởi phòng thí nghiệm RSA (RSA Laboratories) – một bộ phận
của Tổ chức an toàn dữ liệu RSA (RSA Data Security Inc), cùng sự hợp tác rộng rãi
với các nhà phát triển các hệ thống an ninh, nhằm đẩy nhanh tốc độ triển khai các ứng
dụng các hệ mã hoá khoá phi đối xứng.
2.2.1.2 PKCS#1 v2.1
Chuẩn PKCS#1 v2.1 đƣợc phòng thí nghiệm RSA công bố trong tài liệu
PKCS#1 v2.1: RSA Cryptopraphy Standard, ngày 14/6/2002. Mục đích là đƣa ra các
khuyến nghị trong việc cài hệ mã hoá công khai dựa trên cơ sở của thuật toán RSA.
Chuẩn PKCS#1 v2.1 đề cập tới các vấn đề cơ bản sau:
+ Các cơ sở của hệ mã hoá
+ Lƣợc đồ mã hóa
+ Lƣợc đồ chữ ký số
+ Cú pháp ASN.1 để biểu diễn khóa và nhận dạng lƣợc đồ
Điểm mới trong PKCS#1 v2.1 so với các phiên bản trƣớc ở sự dựa vào thuật
toán RSA – đa nguyên tố (Multi prime RSA) và lƣợc đồ chữ ký RSASSA – PSS.
Trong RSA – đa nguyên tố thể hiện ở modulo RSA n là tích của nhiều hơn hai số
nguyên tố (trong các phiên bản trƣớc đó n tích của hai số nguyên tố n = p.q)
20
2.2.2 Các ký hiệu trong PKCS#1 v2.1
Biểu diễn bản mã dạng số nguyên, 0
c
c
n – 1 (là đầu ra của cơ sở mã hóa
RSAEP và là đầu vào của cơ sở giải mã RSADP)
bản mã, là một chuỗi octet (là đầu ra của
C
mã hóa RSAES – OAEP –
DECRYPT).
d
số mũ RSA bí mật, sử dụng cho quá trình giải mã
di
số mũ CRT của ri, là một số nguyên dƣơng thỏa mã:
e.di
1 (mod ( ri - 1)), di < ri – 1, i = 3, . . u.
số mũ CRT của p, là một số nguyên dƣơng thỏa mãn:
dP
e.dP
dQ
số mũ CRT của q, là một số nguyên dƣơng thỏa mã:
e.dQ
e
1 (mod (p – 1)); dP< p – 1
1 (mod (q – 1)); dQ < q – 1
số mũ RSA công khai, sử dụng trong quá trình mã hóa
EM thông điệp đã mã hóa, là một chuỗi octet (kết quả của quá trình áp dụng phƣơng
thức độn EME – OAEP trên thông điệp M)
emBit chiều dài tính theo số bit của một thông điệp đã đƣợc mã hóa EM
emLen
chiều dài tính theo số octet của một thông điệp đã đƣợc mã hóa EM
GCD(. , .)
WCLN của hai số nguyên không âm
Hash hàm băm bảo mật
hLen chiều dài đầu ra, tính theo octet của hàm băm Hash
k
chiều dài tính theo số octet của modulo RSA n
K
khóa bí mật RSA
L
nhãn sử dụng trong RSAES – OAEP, một chuỗi octet
LCM (. , … , .)
bội chung nhỏ nhất của các số nguyên không âm
M
biểu diễn thông điệp (bản rõ) dạng số nguyên, 0 m
sở mã hóa RSAEP, và là đầu ra của cơ sở giải mã RSADP)
n – 1 (là đầu vào của cơ
M
thông điệp, là một chuỗi octet (là đầu vào của hoạt động mã hóa RSAES –
OAEP – ENCRYPT, và là đầu ra của hoạt động giải mã RSAES – OAEP –
DECRYPT)
- Xem thêm -
.PDF 
99 
231 
86 
