-i-
..
§¹i häc th¸i nguyªn
Tr-êng ®¹i häc c«ng nghÖ th«ng tin vµ truyÒn th«ng
Hoµng V¨n QuyÕn
ỨNG DỤNG HỆ MẬT MÃ KHÓA CÔNG KHAI
TRONG QUẢN LÝ ĐỀ THI
LuËn v¨n th¹c sü khoa häc
Thái Nguyên - 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-ii-
MỤC LỤC
MỞ ĐẦU ..............................................................................................................1
Chương 1 TỔNG QUAN HỆ MẬT MÃ KHÓA CÔNG KHAI .........................4
1.1. Khái niệm về hệ mật mã...............................................................................4
1.1.1. Khái niệm chung về mật mã và hệ mật mã ...........................................4
1.1.2. Phân loại các hệ mật mã .......................................................................6
1.2. Lý thuyết độ phức tạp .................................................................................10
1.2.1. Khái niệm độ phức tạp của thuật toán ................................................10
1.2.2. Các bài toán khó tính toán và ứng dụng trong mật mã học ................12
1.3. Hệ mật mã khóa công khai ..........................................................................13
1.3.1. Các quan điểm cơ bản của hệ mật mã khoá công khai ........................13
1.3.3. Hoạt động của hệ mật mã khóa công khai ...........................................14
1.3.4. Các yêu cầu của hệ mật mã khóa công khai ........................................14
1.4. Độ an toàn của hệ mật mã ...........................................................................15
1.2. Chữ ký số ....................................................................................................16
1.2.1. Giới thiệu về chữ ký số ........................................................................16
1.2.2. Quá trình ký và xác thực chữ ký ..........................................................17
Chương 2 MỘT SỐ THUẬT TOÁN PHÂN PHỐI VÀ QUẢN LÝ KHÓA
CÔNG KHAI .....................................................................................................22
2.1. Hệ mật mã khóa công khai RSA .................................................................22
2.1.1. Cơ sở toán học của hệ mật mã RSA ....................................................22
2.1.2. Mô tả hệ mật mã RSA .........................................................................24
2.1.3. Quá trình tạo khoá, mã hoá và giải mã ................................................24
2.1.4. Tính đúng của quá trình giải mã ..........................................................26
2.1.5. Chi phí thực hiện trong quá trình mã hóa và giải mã ..........................28
2.1.6. Đánh giá độ mật của hệ mật mã khóa công khai RSA ......................28
2.1.7. Phân tích cơ chế hoạt động của hệ mã RSA ........................................29
2.1.8. Khả năng bị bẻ khóa của hệ mã công khai RSA .................................30
2.2. Hệ mật mã khóa công khai ElGamal ..........................................................33
2.2.1. Bài toán logarit rời rạc .........................................................................34
2.2.2.Mô tả hệ mật mã ElGamal ....................................................................34
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-iii-
2.2.3. Tính đúng của quá trình giải mã ..........................................................36
2.2.4. Đánh giá độ an toàn và khả năng ứng dụng của hệ mật mã khóa công
khai ElGamal. ................................................................................................36
2.3. Hệ mật mã khóa công khai Rabin ...............................................................37
2.3.1. Sơ đồ hệ mã khóa Rabin ......................................................................37
2.3.2. Tính an toàn của hệ mã hoá Rabin.......................................................40
2.3.3. Sử dụng dư thừa dữ liệu.......................................................................41
2.3.4. Tính hiệu quả .......................................................................................42
2.4. Hệ mã hóa AES ...........................................................................................43
2.4.1. Quá trình phát triển ..............................................................................43
2.4.2. Mô tả thuật toán ...................................................................................44
2.4.3. Mô tả mức cao của thuật toán ..............................................................45
2.4.4. Tối ưu hóa ............................................................................................47
2.4.5. An toàn .................................................................................................47
2.4.5. Tấn công kênh bên (Side channel attacks) ..........................................48
Chương 3 XÂY DỰNG ỨNG DỤNG THỬ NGHIỆM ...................................50
3.1. Bài toán quản lý đề thi trong hệ thống các trường phổ thông .....................50
3.2. Áp dụng hệ mật mã khóa công khai cho quản lý đề thi trong các trường phổ
thông ...................................................................................................................52
3.2.1. Mô tả hệ thống. ....................................................................................52
3.2.2. Chức năng và giao diện chính của chương trình .................................54
3.2.3. Các bước thực hiện chương trình ........................................................56
3.2.5. Mã chương trình ..................................................................................64
Đánh giá kết quả thử nghiệm chương 3 .........................................................64
KẾT LUẬN ........................................................................................................65
TÀI LIỆU THAM KHẢO ..................................................................................66
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-iv-
LỜI CẢM ƠN
Tôi xin gửi lời cảm ơn tới trường Đại học CNTT & TT, Viện CNTT Việt Nam,
nơi các thầy cô đã tận tình truyền đạt các kiến thức quý báu cho tôi trong suốt quá
trình học tập. Xin cảm ơn Ban Giám Hiệu nhà trường và các cán bộ đã tạo điều kiện
tốt nhất cho chúng tôi học tập và hoàn thành đề tài tốt nghiệp của mình. Đặc biệt,
tôi xin gửi tới TS Bùi Văn Thanh, thầy đã tận tình chỉ bảo tôi trong suốt quá trình
thực hiện đề tài lời cảm ơn và biết ơn sâu sắc nhất. Bên cạnh những kiến thức khoa
học, thầy đã giúp tôi nhận ra những bài học về phong cách học tập, làm việc và
những kinh nghiệm sống quý báu. Tôi xin bày tỏ lòng biết ơn tới gia đình, bạn bè,
đồng nghiệp và những người thân đã động viên khích lệ tinh thần và giúp đỡ để tôi
hoàn thành luận văn này.
Thái Nguyên, ngày 10 tháng 10 năm 2012
Hoàng Văn Quyến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-v-
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
STT
Ký hiệu/ Chữ viết tắt
Viết đầy đủ
1
RSA
Rivest - Shamir - Adleman
2
DES
Data Encryption Standard
3
AES
Advanced Encryption Standard
4
NIST
National Institute of Standards and Technology
5
FIPF
Farm Innovation and Promotion Fund
6
NSA
National Security Agency
7
THPT
Trung học phổ thông
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-vi-
LỜI CAM ĐOAN
Tôi xin cam đoan, toàn bộ nội dung liên quan tới đề tài được trình bày trong
luận văn là bản thân tôi tự tìm hiểu và nghiên cứu, dưới sự hướng dẫn khoa học của
TS Bùi Văn Thanh.
Các tài liệu, số liệu tham khảo được trích dẫn đầy đủ nguồn gốc. Tôi xin chịu
trách nhiệm trước pháp luật lời cam đoan của mình.
Học viên thực hiện
Hoàng Văn Quyến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-vii-
DANH MỤC CÁC BẢNG
Trang
Bảng 1.1: Bảng chi phí thời gian phân tích số nguyên n ra thừa số nguyên tố….12
Bảng 2.1: Tóm tắt các bước tạo khoá, mã hoá, giải mã của Hệ RSA…………....20
Bảng 2.2: Bảng chi phí thời gian cần thiết để phân tích các số nguyên N……....24
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-viii-
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Trang
Hình 1.1: Sơ đồ hoạt động chung của hệ mật mã .................................................. 5
Hình 1.2: Sơ đồ hoạt động của mã hóa khóa đối xứng .......................................... 6
Hình 1.3. Sơ đồ hoạt động của mã hóa khóa không đối xứng ............................... 9
Hình 1.4 Lược đồ ký ........................................................................................... 18
Hình 1.5. Lược đồ xác thực ................................................................................. 20
Hình 2.1: Đồ thị so sánh chi phí tấn công khóa bí mật và khóa công khai. ........ 33
Hình 2.4: Bước SubBytes, một trong 4 bước của 1 chu trình .............................. 43
Hình 2.5: Mô tả thuật toán AES........................................................................... 44
Hình 2.6: Bước SubBytes .................................................................................... 44
Hình 2.7: Bước ShiftRows ................................................................................... 45
Hình.3.9: Sơ đồ bài toán quản lý đề thi của các trường THPT ............................ 51
Hình 3.10: Sơ đồ quy trình tổng quan hệ thống ................................................... 52
Hình 3.11: Sơ đồ quy trình tạo khóa RSA ........................................................... 53
Hình 3.12: Sơ đồ quy trình mã hóa văn bản bằng thuật toán AES ..................... 53
Hình 3.13: Sơ đồ quy trình mã hóa khóa theo thuật toán RSA ........................... 53
Hình 3.14: Sơ đồ quy trình giải mã khóa theo thuật toán RSA .......................... 54
Hình 3.15: Giao diện chính của chương trình ..................................................... 54
Hình 3.16: Giao diện tạo khóa RSA ................................................................... 54
Hình 3.17: Mã hóa văn bản bằng AES ................................................................ 55
Hình 3.18: Mã hóa khóa bằng RSA ..................................................................... 56
Hình 3.19: Giải mã khóa bằng RSA .................................................................... 56
Hình 3.20: Tạo khóa RSA tùy chọn ..................................................................... 56
Hình 3.21:Tạo khóa RSA tự động ....................................................................... 57
Hình 3.22:Lưu khóa RSA tự động thành tệp ....................................................... 57
Hình 3.23: Mã hóa nội dung văn bản ................................................................... 57
Hình 3.24: Mở tệp văn bản cần mã hóa ............................................................... 58
Hình 3.25: Thông báo mã hóa thành công. .......................................................... 58
Hình 3.26: Xem nội dung tệp được mã hóa ......................................................... 58
Hình 3.27: Mã hóa tệp *.* ................................................................................... 58
Hình 3.28: Chọn File cần mã hóa ........................................................................ 59
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-ix-
Hình 3.29: Thông báo kết quả mã hóa ................................................................. 59
Hình 3.30: Xem kết quả file đã mã hóa ............................................................... 59
Hình 3.31: Giải mã nội dung văn bản .................................................................. 60
Hình 3.32: Chọn File cần giải mã ........................................................................ 60
Hình 3.33: Thông báo kết quả giải mã ................................................................. 60
Hình 3.234: Xem nội dung tệp vừa giải mã ......................................................... 60
Hình 3.35: Giải mã File được mã hóa .................................................................. 61
Hình 3.36: Mở tệp cần giải mã ............................................................................ 61
Hình 3.37: Thông báo kết quả giải mã ................................................................. 61
Hình 3.38: Xem nội dung tệp vừa giải mã ........................................................... 62
Hình 3.39: Mã hóa khóa RSA .............................................................................. 62
Hình 3.40: Chọn File khóa cần mã hóa................................................................ 62
Hình 3.41: Kết quả mã hóa khóa ......................................................................... 63
Hình 3.42: Giải mã khóa RSA ............................................................................. 63
Hình 3.43: Mở tệp giải mã khóa RSA ................................................................. 63
Hình 3.44: Kết quả giải mã khóa RSA ................................................................ 64
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-1-
MỞ ĐẦU
Thế kỷ XXI là thế kỷ công nghệ thông tin. Công nghệ thông tin đã và đang
tác động trực tiếp đến mọi mặt hoạt động kinh tế xã hội trên thế giới. Thông tin có
vai trò hết sức quan trọng, vì vậy cần phải đảm bảo để thông tin không bị sai lệch,
không bị thay đổi, hay bị lộ trong quá trình truyền từ nơi gửi đến nơi nhận. Với sự
phát triển rất nhanh của công nghệ mạng máy tính, đặc biệt là mạng Internet, khối
lượng thông tin ngày càng được truyền nhận nhiều hơn.
Vấn đề khó khăn đặt ra là làm sao giữ được tính bảo mật của thông tin, thông
tin đến đúng được địa chỉ cần đến và không bị sửa đổi. Hậu quả sẽ khó lường nếu
như thư được gửi cho một người nhưng lại bị một người khác xem trộm và sửa đổi
nội dung bức thư trái với chủ ý của người gửi. Tệ hại hơn nữa là khi một hợp đồng
được ký, gửi thông qua mạng và bị kẻ xấu sửa đổi những điều khoản trong đó.
Người gửi thư bị hiểu nhầm vì nội dung bức thư bị thay đổi, còn hợp đồng bị phá vỡ
bởi những điều khoản đã không còn như ban đầu. Điều này gây ra những mất mát
cả về mặt tài chính và quan hệ, tình cảm, v.v... và còn có thể nêu ra rất nhiều tình
huống tương tự. Mã hoá thông tin là một trong các phương pháp có thể đảm bảo
được tính bảo mật của thông tin. Mã hoá, trong một mức độ nhất định, có thể giải
quyết các vấn trên; một khi thông tin đã được mã hoá, kẻ xấu rất khó hoặc không
thể giải mã để có được nội dung thông tin ban đầu.
Khi mã hóa, thông tin được biến đổi (được mã hóa) bằng thuật toán mã hóa
thông qua việc sử dụng “khóa”. Chỉ có người dùng có cùng “khóa” mới phục hồi lại
được thông tin ban đầu (giải mã). Do vậy “khóa” cần được bảo vệ nghiêm ngặt và
được truyền từ người gửi đến người nhận trên một kênh an toàn riêng sao cho người
thứ ba không thể biết được khóa. Phương pháp này được gọi là mã hóa bằng khóa
riêng hoặc mật mã khóa đối xứng. Có một số chuẩn thuật toán khóa đối xứng, ví dụ
như DES, AES, v.v… Người ta đã chứng minh được khả năng bảo mật cao của các
thuật toán đối xứng chuẩn nói trên và chúng đã được kiểm định qua thời gian. Tuy
nhiên, vấn đề nảy sinh với các thuật toán đối xứng là việc trao đổi khóa. Các bên
tham gia giao tiếp đòi hỏi được chia sẻ một bí mật là “khóa”, “khóa” cần được trao
đổi giữa họ qua một kênh thông tin an toàn. An toàn của thuật toán khóa đối xứng
phụ thuộc vào độ mật của khoá. Khóa thường có độ dài hàng trăm bit, tùy thuộc vào
thuật toán được sử dụng. Vì thông tin có thể trung chuyển qua các điểm trung gian
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-2-
nên không thể trao đổi khóa một cách trực tuyến và an toàn. Trong một mạng rộng
kết nối hàng trăm hệ thống, việc trao đổi khóa trở thành quá khó khăn và thậm chí
không thực tế.
Cho đến cuối những năm 1970, tất cả các quá trình truyền thông tin bảo mật
đều sử dụng hệ mật mã đối xứng. Điều này có nghĩa rằng một ai đó có đủ thông tin
(khóa) để mã hóa thông tin thì cũng có thông tin đủ để giải mã. Năm 1976 Diffe và
Hellman [5], [6] đã nêu định hướng phát triển mới cho các hệ thống mật mã bằng
việc phát minh hệ mật mã khóa công khai. Ý tưởng chính là sử dụng hàm một chiều
(one-way function) để mã hóa. Các hàm sử dụng để mã hóa thuộc một lớp các hàm
một chiều đặc biệt, chúng là một chiều nếu một số thông tin nhất định (khóa để giải
mã) được giữ bí mật. Nói một cách hình thức, hàm mã hóa khóa công khai là một
hàm ánh xạ các dãy tin (bản rõ) thành các dãy được mật mã hóa; bất cứ ai có khóa
công khai đều có thể thực hiện việc mã hóa này. Tuy nhiên việc tính toán hàm
nghịch đảo (hàm để giải mã thông tin được mã hóa thành các dãy tin ban đầu - bản
rõ) không thể thực hiện được trong một khoảng thời gian hợp lý mà không cần thêm
một số thông tin bổ sung, gọi là khóa riêng. Điều này có nghĩa rằng mọi người có
thể gửi thông tin đến một người nào đó bằng cách sử dụng cùng một khóa để mã
hóa bằng cách đơn giản là lấy khóa này tại một vị trí công khai. Người gửi không
cần phải thực hiện bất kỳ thỏa thuận bí mật với người nhận; người nhận không cần
có bất kỳ liên hệ trước nào với người gửi. Vì vậy có thể trao đổi thông tin một cách
bảo mật bằng cách sử dụng thuật toán khóa công khai mà không cần trao đổi khóa
một cách bí mật.
Trong hệ mật mã khóa công khai mỗi người dùng hoặc thiết bị tham gia vào
quá trình gửi nhận thông tin có một cặp khóa, một khóa công khai và một khóa
riêng, cùng với các quy tắc sử dụng khóa để thực hiện các hoạt động bảo mật dữ
liệu. Chỉ người dùng hoặc thiết bị biết khóa riêng của mình, còn khóa công khai
được phân phối đến tất cả người dùnghoặc thiết bị khác tham gia vào hệ thống. Vì
việc biết khoá công khai không ảnh hưởng tới sự an toàn của các thuật toán, có thể
dễ dàng trao đổi khoá công khai trực tuyến.
Thông tin cần bảo mật có thể được trao đổi trực tuyến bằng cách trao đổi
thông tin đã mã hóa và khóa công khai. Những người chỉ có quyền truy cập vào các
thông tin trao đổi công khai sẽ không thể tính toán để giải mã thông tin, trừ khi họ
có quyền truy cập và biết khóa riêng của của các bên giao tiếp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-3-
Các hệ mật mã khóa đối xứng đã được sử dụng từ khá lâu. Sự phát triển
tương đối muộn của các hệ mật mã khóa công khai xuất phát từ lý do là cho đến tận
những năm 1970 mật mã chỉ được sử dụng chủ yếu cho các mục đích quân sự và
ngoại giao và mật mã khóa đối xứng là thích hợp. Với việc mở rộng các ứng dụng
của CNTT trong đời sống và kinh tế, các nhu cầu mới về mật mã phát sinh. Không
giống như trong quân đội hay ngoại giao với phân cấp cứng nhắc và số người sử
dụng hạn chế, trong các ứng dụng kinh tế - xã hội, lượng dữ liệu được trao đổi lớn
gấp nhiều lần và số người sử dụng cũng tăng nhanh, lĩnh vực ứng dụng cũng phong
phú hơn nhiều. Vì vậy trong những năm gần đây hệ mật mã khóa công khai đã được
tập trung nghiên cứu một cách mạnh mẽ trên thế giới và nhiều kết quả mới đã đạt
được cũng như được áp dụng để giải quyết các vấn đề thực tiễn trong nhiều
lĩnh vực.
Mục đích của luận văn là trình bày các kết quả tìm hiểu được về hệ mật mã
khóa công khai, các thuật toán mã hóa và giải mã sử dụng trong các hệ mật mã khóa
công khai, đồng thời tìm hiểu khả năng ứng dụng hệ mật mã khóa công khai trong
quản lý đề thi trong các trường phổ thông.
Nội dung luận văn gồm 3 chương:
Chương I. TỔNG QUAN HỆ MẬT MÃ KHÓA CÔNG KHAI
Chương này trình bày các kiến thức tổng quan về các hệ mật mã nói chung
và hệ mật mã khóa công khai nói riêng, các yêu cầu về hệ mật mã khóa công khai
cũng như tính bảo mật của chúng.
Chương II. MỘT SỐ THUẬT TOÁN PHÂN PHỐI VÀ QUẢN LÝ KHÓA
Chương này đi sâu phân tích cơ chế hoạt động của một số hệ mật mã khóa
công khai đã được chấp nhận như các hệ chuẩn như RSA, ELGAMAL và RABIN.
Độ mật, hiệu suất thực hiện và ứng dụng của các hệ mật mã nói trên cũng được đề
cập và đánh giá.
Chương III. XÂY DỰNG ỨNG DỤNG THỬ NGHIỆM
Chương này đề cập đến việc xây dựng ứng dụng thử nghiệm để giải quyết
vấn đề quản lý và bảo mật đề thi trong hệ thống các trường phổ thông dựa vào các
thuật toán RSA và AES.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-4-
Chương 1
TỔNG QUAN HỆ MẬT MÃ KHÓA CÔNG KHAI
1.1. Khái niệm về hệ mật mã
1.1.1. Khái niệm chung về mật mã và hệ mật mã
Mật mã học là một lĩnh vực liên quan đến các kỹ thuật ngôn ngữ và toán học
nhằm đảm bảo an toàn thông tin. Về phương diện lịch sử, mật mã học gắn liền với
quá trình mã hóa; điều này có nghĩa là nó gắn với các cách thức để chuyển đổi
thông tin từ dạng này sang dạng khác nhưng ở đây là từ dạng thông thường có thể
nhận thức được thành dạng không thể nhận thức được, làm cho thông tin trở thành
dạng không thể đọc được nếu như không có các kiến thức bí mật. Quá trình mã hoá
được sử dụng chủ yếu để đảm bảo tính bí mật của các thông tin quan trọng, chẳng
hạn trong công tác tình báo, quân sự hay ngoại giao cũng như các bí mật về kinh tế,
thương mại. Trong những năm gần đây, lĩnh vực hoạt động của mật mã hoá đã được
mở rộng; mật mã hoá hiện đại cung cấp nhiều ưng dụng hơn là chỉ duy nhất giữ bí
mật và có một loạt các ứng dụng như: chứng thực khoá công khai, chữ ký số, bầu cử
điện tử hay tiền điện tử. Ngoài ra những người không có nhu cầu thiết yếu đặc biệt
về tính bảo mật cũng sử dụng các công nghệ mật mã hoá, thông thường được thiết
kế và tạo lập sẵn trong các cơ sở hạ tầng của công nghệ tính toán và liên lạc
viễn thông.
Mật mã học là một nghành có lịch sử từ hàng nghìn năm nay. Trong phần lớn
thời gian phát triển của mình (ngoại trừ vài thập kỉ trở lại đây), lịch sử mật mã học
chính là lịch sử của những phương pháp mật mã học cổ điển - các phương pháp mật
mã hoá với bút và giấy, đôi khi có hỗ trợ từ những dụng cụ cơ khí đơn giản. Vào
đầu thế kỉ 20, sự xuất hiện của các cơ cấu cơ khí và điện cơ, chẳng hạn như máy
ENIGMA, đã cung cấp những những cơ chế mật mã hoá phức tạp và hiệu quả hơn.
Sự ra đời và phát triển mạnh mẽ của ngành điện tử và máy tính trong những thập
niên gần đây đã tạo điều kiện để mật mã học phát triển nhảy vọt lên một tầm
cao mới.
Cho trước:
A là một tập hữu hạn các phần tử, được gọi là bảng chữ cái. Ví dụ A = {0,1}
(bảng chữ cái nhị phân). Lưu ý rằng một bảng chữ cái bất kỳ có thể được
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-5-
mã hóa vào bảng chữ cái nhị phân. Ví dụ, mỗi chữ của bảng chữ cái tiếng
Anh có thể được mã hóa như một dãy nhị phân chiều dài 5.
P là tập hợp các dãy chữ cái (các xâu) lấy từ A. Mỗi phần tử của P được
gọi là bản rõ.
C ký hiệu tập các dãy chữ cái lấy từ một bảng chữ cái nào đó, có thể trùng
hoặc khác bảng chữ cái A. C được gọi là tập hợp các bản mã, mỗi phần tử
của C được gọi là bản mã.
K là tập hữu hạn các phần tử, mỗi phần tử được gọi là khóa. Bản thân K
được gọi là không gian khóa.
Định nghĩa 1.1 Một hệ mật mã là một bộ năm (P,C,K,E,D), trong đó P là
một tập các bản rõ, C là một tập các bản mã, K là không gian khoá và E là tập các
song ánh {EK:PC)}, D là tập các song ánh {EK:CP)} thoả mãn các điều
kiện sau:
1. Với mỗi KK tồn tại duy nhất một song ánh EK E, EK:PC. EK được
gọi là quy tắc mã hóa tương ứng với khóa K.
2. Với mỗi KK tồn tại một một song ánh DKD, DK:CP. DK được gọi là
quy tắc giải mã tương ứng với khóa K.
3. Với mỗi KK tồn tại duy nhất một khóa kK sao cho Dk EK1 , nghĩa là
Dk EK P P với mọi bản rõ P P.
Để gửi bản rõ P, trước hết bản rõ P được mã hóa bằng EK để có bản mã C. Ở
nơi nhận C được giải mã bằng Dk và thu được bản rõ ban đầu P.
Các khóa K và k trong định nghĩa trên được gọi là cặp khóa và thường được
ký hiệu bằng (K; k). Lưu ý rằng có thể k K .
Hình 1.1: Sơ đồ hoạt động chung của hệ mật mã
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-6-
Giả sử bản rõ là P x1 , x2 , . . . , xn với số nguyên n 1 nào đó. Ở đây mỗi ký
hiệu của bản rõ xiA, 1 i n. Mỗi xi sẽ được mã hoá bằng quy tắc mã hóa EK với
khoá K được xác định trước đó: yi = EK(xi), 1 i n và bản mã nhận được
C y1 , y2 , . . . , yn sẽ được gửi. Khi nhận được y1 , y2 , . . . , yn , ta sẽ giải mã bằng
hàm giải mã Dk và thu được bản rõ ban đầu x1 , x2 , . . . , xn .
Rõ ràng hàm mã hoá phải là hàm đơn ánh (tức là ánh xạ 1-1), nếu không việc
giải mã sẽ không thực hiện được một cách tường minh. Nếu P = C thì mỗi hàm mã
hoá là một phép hoán vị. Nghĩa là nếu tập các bản mã và tập các bản rõ là đồng nhất
thì mỗi hàm mã hoá sẽ là một sự sắp xếp lại (hay hoán vị) các phần tử của tập này.
1.1.2. Phân loại các hệ mật mã
1.1.2.1. Hệ thống mật mã đối xứng
a. Định nghĩa
Mã hóa đối xứng là phương pháp mã mà trong đó các khóa dùng cho việc mã
hóa (khoá mã hoá) và giải mã (khoá giải mã) có quan hệ rõ ràng với nhau, nghĩa là
có thể dễ dàng tìm khóa này nếu biết khóa kia và ngược lại. Trong rất nhiều trường
hợp, khoá mã hoá và khoá giải mã là giống nhau.
Thuật toán này còn có nhiều tên gọi khác như thuật toán khoá bí mật, thuật
toán khoá đơn giản, thuật toán một khoá. Sự mã hoá và giải mã của thuật toán đối
xứng được biểu thị bởi:
EK P C
và
DK C P
Ban đầu, bản rõ được người gửi A mã hóa với khóa K. Sau đó bản mã được
gửi tới người nhận B. Khi nhận được bản mã, người B sử dụng khóa K giải mã để
thu được bản rõ. Do đó, nếu một người khác có được khóa K thì hệ thống mã hóa
này sẽ bị tấn công (Hình 1.2).
Hình 1.2: Sơ đồ hoạt động của mã hóa khóa đối xứng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-7-
Thuật toán này yêu cầu người gửi và người nhận phải thoả thuận thuật toán
mã hóa và khóa dùng cho quá trình mã hoá và giải mã trước khi bản rõ được mã hóa
và được gửi đi, và khoá này phải được cất giữ bí mật. Độ an toàn của thuật toán này
phụ thuộc vào khoá, nếu khoá bị lộ, bất kì người nào có khóa cũng có thể mã hoá và
giải mã. Việc trao đổi, thoả thuận về thuật toán được sử dụng trong việc mã hoá có
thể tiến hành một cách công khai, nhưng bước thoả thuận về khoá trong việc mã
hoá-giải mã và trao đổi khóa phải tiến hành bí mật và an toàn. Sau khi đã thỏa thuận
được thuật toán mã hóa, thống nhất được khóa dùng để mã hóa và giải mã, bên gửi
sẽ mã hoá bản rõ bằng cách sử dụng khoá bí mật đã thống nhất và gửi bản mã cho
bên nhận. Sau khi nhận được bản mã, bên nhận sẽ sử dụng chính khoá bí mật mà
hai bên đã thoả thuận để giải mã và khôi phục lại bản rõ.
Chúng ta có thể thấy rằng thuật toán mã hoá đối xứng sẽ rất có lợi khi được
áp dụng trong các cơ quan hay tổ chức đơn lẻ. Nhưng nếu cần phải trao đổi thông
tin với một bên thứ ba thì việc đảm bảo tính bí mật của khoá phải được đặt lên
hàng đầu.
Trong các mã hoá cổ điển, ví dụ như phương pháp mã hóa Ceaser Cipher thì
khoá chính là phép dịch ký tự, cụ thể là phép dịch 3 ký tự. Trong phương pháp mã
hoá hoán vị thì khóa nằm ở số hàng hay số cột mà chúng ta qui định. Khoá này có
thể được thay đổi tuỳ theo mục đích mã hoá, nhưng nó phải nằm trong một phạm vi
cho phép nào đó.
Mã hoá đối xứng có thể được phân thành hai loại:
Loại thứ nhất tác động trên bản rõ theo từng nhóm ký hiệu (chữ cái hoặc bit)
có độ dài (số các ký hiệu) bằng nhau. Từng nhóm này được gọi với một cái tên khác
là khối (block) và thuật toán được áp dụng gọi là mã hóa khối (Block Cipher). Theo
đó, từng khối dữ liệu có cùng độ dài trong bản rõ ban đầu được thay thế bằng một
khối dữ liệu khác. Đối với các thuật toán ngày nay thì kích thước chung của một
khối là 64 bit.
Loại thứ hai mã hoá bản rõ theo từng bit. Các thuật toán loại này được gọi là
mã hóa dòng (Stream Cipher). Các thuật toán mã hoá dòng này có tốc độ nhanh hơn
các thuật toán mã hoá khối và nó thường được áp dụng khi lượng dữ liệu cần mã
hoá chưa biết trước.
Một số thuật toán nổi tiếng trong mã hoá đối xứng là: DES, Triple DES
(3DES), RC4, AES… DES là một thuật toán được sử dụng rộng rãi nhất trên thế
giới. Với thuật toán DES (Data Encryption Standard), bản rõ được mã hoá theo từng
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-8-
khối 64 bit và sử dụng một khoá có độ dài 64 bit, nhưng thực tế thì chỉ có 56 bit là
thực sự được dùng để tạo khoá, 8 bit còn lại dùng để kiểm tra tính chẵn, lẻ. Hiện tại
DES không còn được đánh giá cao do kích thước của khoá quá nhỏ (56 bit), và dễ
dàng bị phá.
Triple DES (3DES) cải thiện độ mạnh của DES bằng quá trình mã hoá và
giải mã sử dụng 3 khoá. Khối 64-bits của bản rõ sẽ được mã hoá sử dụng khoá thứ
nhất. Sau đó, dữ liệu bị mã hóa được giải mã bằng việc sử dụng một khoá thứ hai.
Cuối cùng, sử dụng khoá thứ ba để mã hoá kết quả của quá trình trước đó:
C EK3 DK2 EK1 P
P DK1 EK2 DK3 C
AES (Advanced Encryption Standard): được sử dụng để thay thế cho DES.
Nó hỗ trợ độ dài của khoá từ 128 bit cho đến 256 bit.
Nhận xét:
Trong các giao dịch trên mạng, khóa K phải được truyền đi trên môi
trường này, do đó nó có thể bị lấy cắp. Để an toàn, việc bảo mật cho khóa
K cần phải được chú trọng. Thường phải dùng thêm các cơ chế và giải
thuật khác trong việc quản lý, trao đổi khóa giữa các đối tượng.
Không thể xác thực được nguồn gốc nội dung của bản rõ cũng như không
có tính chất không thể phủ nhận của chủ thể.
Khi số lượng khóa bí mật tăng lên, việc quản lý các khóa này trở nên
phức tạp và khó khăn khi một người phải giữ nhiều khóa bí mật để giao
dịch với nhiều đối tượng khác nhau.
Những nhược điểm trên dẫn đến hệ mật mã khóa đối xứng khó có thể áp
dụng một cách rộng rãi.
b. Các vấn đề đối với phương pháp mã hóa đối xứng
Phương mã hóa đối xứng đòi hỏi người mã hóa và người giải mã phải sử
dụng chung một khóa. Khi đó khóa phải được giữ bí mật tuyệt đối. Hệ mã hóa đối
xứng không an toàn nếu khóa bị lộ với xác suất cao. Trong hệ này, khóa phải được
gửi đi trên kênh an toàn. Vấn đề quản lý và phân phối khóa là khó khăn và phức tạp
khi sử dụng hệ mã hóa đối xứng. Người gửi và nhận phải luôn thống nhất với nhau
về khóa. Việc thay đổi khóa là rất khó và dễ bị lộ. Khuynh hướng cung cấp khoá dài
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-9-
và phải được thay đổi thường xuyên trong khi vẫn duy trì cả tính an toàn lẫn hiệu
quả chi phí sẽ cản trở rất nhiều tới việc áp dụng hệ mật mã này.
1.1.2.2. Hệ thống mật mã không đối xứng (mật mã khóa công khai)
a. Định nghĩa
Thuật toán mã hóa công khai là thuật toán được thiết kế sao cho khóa mã hóa
K khác so với khóa giải mã k và khóa giải mã không thể tính toán được từ khóa mã
hóa. Khóa mã hóa K gọi là khóa công khai (public key), khóa giải mã k được gọi là
khóa riêng (private key).
Hình 1.3. Sơ đồ hoạt động của mã hóa khóa không đối xứng
Đặc trưng nổi bật của hệ mật mã công khai là có thể gửi cả khóa công khai
và bản mã trên một kênh thông tin không an toàn.
Với hệ mật mã khóa công khai, người A sử dụng khóa công khai K B do
người B tạo để mã hóa thông điệp và gửi cho người B. Do biết được khóa riêng k B
nên người B có thể giải mã được thông điệp đã được mã hóa. Trong trường hợp
người thứ ba có được bản mã, nếu chỉ kết hợp với thông tin về khóa công khai K B
đã được công bố, cũng rất khó có khả năng giải mã được bản mã này trong khoảng
thời gian chấp nhận được do không biết được khóa riêng k B của B.
Khóa công khai K và khóa riêng k có quan hệ toán học với nhau theo nghĩa
từ khóa riêng có thể tính toán để suy ra được khóa công khai, nhưng để từ khóa
công khai suy ra khóa riêng sẽ rất phức tạp vì số lượng phép tính toán là rất nhiều,
dẫn đến việc giải mã không khả thi trong khoảng thời gian hợp lý (nội dung thông
tin còn có tác dụng) khi chiều dài của khóa đủ lớn.
Đây cũng là mấu chốt của vấn đề bảo mật và tấn công trong các hệ mã khóa
công khai. Đó cũng chính là vấn đề an toàn của hệ mã công khai. Nghiên cứu đưa ra
các giải pháp hỗ trợ làm tăng tính an toàn của các hệ mã này bằng cách cố gắng áp
dụng các thuật toán xử lý nhanh với số lớn. Từ đó có thể tăng chiều dài của khóa mà
vẫn đảm bảo yếu tố thời gian mã hóa và giải mã chấp nhận được.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-10-
b. Các điều kiện của một hệ mã hóa công khai
Việc tính toán cặp khóa công khai K và bí mật k dựa trên các điều kiện ban
đầu phải thực hiện được trong khoảng thời gian hợp lý, nghĩa là thực hiện trong thời
gian đa thức.
Người gửi A có được khóa công khai KB của người nhận B và có bản rõ P
cần gửi đi có thể dễ dàng tạo ra được bản mã C bằng cách mã hóa
C EKB ( P) EB ( P)
Công việc này cũng được thực hiện trong thời gian đa thức .
Người nhận B khi nhận được bản tin đã mã hóa C, với khóa bí mật kB có thể
giải mã trong thời gian đa thức.
1.2. Lý thuyết độ phức tạp
1.2.1. Khái niệm độ phức tạp của thuật toán
Khi thực hiện cùng một thuật toán trên nhiều máy tính với cấu hình khác
nhau ta sẽ thấy thời gian thực hiện thuật toán có thể khác nhau. Do đó không thể lấy
thời gian thực hiện của thuật toán trên một máy tính để đánh giá độ phức tạp của
thuật toán.
Độ phức tạp của một thuật toán được tính bằng số các phép tính cơ sở (đọc,
ghi, phép so sánh, phép cộng,...) máy tính thực hiện khi tiến hành thực hiện thuật
toán. Ngoài ra, số lượng phép tính còn phụ thuộc vào kích cỡ dữ liệu đầu vào của
thuật toán. Như vậy, độ phức tạp của thuật toán phải là một hàm số theo độ lớn của
đầu vào. Việc xác định chính xác hàm này có thể rất phức tạp, tuy nhiên khi biết cỡ
của chúng thì ta có thể có được một ước lượng chấp nhận được.
Độ phức tạp của một thuật toán thường được đo bằng số các phép tính bit.
Phép tính bit là một phép tính logic hay số học thực hiện trên các số 0 và 1. Để ước
lượng độ phức tạp của thuật toán, ta dùng khái niệm bậc O-lớn.
Định nghĩa 1.2. Giả sử f ( n ) và g ( n) là hai hàm xác định trên tập hợp các
số nguyên dương. Ta nói f ( n ) có bậc O-lớn của g ( n) , và viết f (n) O( g ( n))
hoặc f O ( g ) , nếu tồn tại một hằng số C > 0 sao cho với n đủ lớn ta có
0 f ( n) C .g ( n) .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
-11-
Định nghĩa 1.3. Một thuật toán được gọi là có độ phức tạp đa thức, hoặc có
thời gian đa thức, nếu số các phép tính cần thiết khi thực hiện thuật toán không vượt
quá O(log k n) , trong đó n là độ lớn của đầu vào, và k là số nguyên dương nào đó.
Nói cách khác, nếu đầu vào là các số m-bit thì thời gian thực hiện thuật toán
là O(md ) , tức là tương đương với một đa thức của m.
Các thuật toán với thời gian O n , 1 , được gọi là các thuật toán với
độ phức tạp mũ, hoặc thời gian mũ.
Nếu một thuật toán có độ phức tạp O ( g ) , thì cũng có thể nói nó có độ phức
tạp O ( h ) với mọi hàm h g . Tuy nhiên, ta luôn luôn cố gắng tìm ước lượng tốt
nhất có thể được.
Tồn tại những thuật toán có độ phức tạp trung gian giữa đa thức và mũ. Các
thuật toán đó được gọi là thuật toán dưới mũ.
Độ phức tạp không phải là tiêu chuẩn duy nhất để đánh giá thuật toán. Có
những thuật toán, về lý thuyết có độ phức tạp cao hơn một thuật toán khác, nhưng
khi sử dụng lại cho kết quả nhanh hơn.
Bảng dưới đây đưa ra các thông số về thời gian và số lượng phép toán trên
bit để thực hiện việc phân tích một số nguyên n ra thừa số nguyên tố áp dụng thuật
toán tốt nhất trên máy tính có tốc độ xử lý một triệu phép tính trên một giây:
Thuật toán này có độ phức tạp dưới mũ: exp
Số chữ số thập phân n
log n log log n
Số phép tính trên bit
Thời gian
50
1,4.1010
3,9 giờ
75
9,0.1012
104 ngày
100
2,3.1015
74 năm
200
1,2.1023
3,8.109 năm
300
1,5.1029
4,9.1015 năm
500
1,3.1039
4,2.1025 năm
Bảng 1.1. Thời gian phân tích số nguyên n ra thừa số nguyên tố
Với một thuật toán dưới mũ, thời gian làm việc với các số nguyên lớn vẫn
không khả thi. Do đó, với các ứng dụng xử lý số lớn, ta thường phải cố gắng biến
đổi để thu được một thuật toán có thời gian tính toán đa thức. Ý tưởng này sẽ được
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -
.PDF 
75 
5 
94 
