KHOA CÔNG NGHỆ THÔNG TIN
ĐẠI HỌC THÁI NGUYÊN
NGUYỄN NGỌC TRUNG
CÁC THUẬT TOÁN TỐI ƢU HÓA
TRONG BẢO MẬT THÔNG TIN
CHUYÊN NGÀNH : KHOA HỌC MÁY TÍNH
MÃ SỐ : 60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC
PGS.TSKH. NGUYỄN XUÂN HUY
Thái Nguyên 03/2008
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
LỜI CẢM ƠN
Tôi xin gửi lời cảm ơn tới Khoa CNTT – ĐHTN, 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 chủ nhiệm khoa 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 PGS. TSKH Nguyễn Xuân Huy, 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 11 năm 2008
Nguyễn Ngọc Trung
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
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 Thầy giáo PGS. TSKH Nguyễn Xuân Huy.
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
Nguyễn Ngọc Trung
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
MỤC LỤC
Trang
LỜI CẢM ƠN
LỜI CAM ĐOAN
MỤC LỤC ...............................................................................................................................
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ..................................................................................
MỞ ĐẦU ............................................................................................................................... 1
CHƢƠNG 1 - LÝ THUYẾT MẬT MÃ ................................................................................ 6
1.1 MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ MÃ HÓA ......................................................... 6
1.2 LÝ THUYẾT ĐỘ PHỨC TẠP .................................................................................. 10
1.3 CƠ SỞ TOÁN HỌC CỦA MẬT MÃ ..................................................................... 13
CHƢƠNG 2 - NGHIÊN CỨU CƠ CHẾ HOẠT ĐỘNG CỦA HỆ MẬT KHÓA CÔNG
KHAI ................................................................................................................................... 20
2.1 GIỚI THIỆU VỀ HỆ MẬT VỚI KHÓA CÔNG KHAI ........................................... 20
2.2 HỆ MẬT MÃ KHÓA CÔNG KHAI RSA ................................................................ 22
2.3 HỆ MẬT MÃ KHÓA CÔNG KHAI RSA WITH CRT ............................................ 29
2.4 CƠ CHẾ HOẠT ĐỘNG CỦA RSA .......................................................................... 34
2.5 KHẢ NĂNG BỊ BẺ KHÓA CỦA HỆ MÃ CÔNG KHAI RSA ............................... 36
2.6 HỆ MẬT MÃ KHÓA CÔNG KHAI ELGAMAL .................................................... 40
CHƢƠNG 3 - MỘT SỐ GIẢI THUẬT XỬ LÝ SỐ HỌC ÁP DỤNG ĐỂ TỐI ƢU HÓA
QUÁ TRÌNH MÃ HÓA VÀ GIẢI MÃCỦA HỆ MÃ RSA ……………………………...41
3.1 PHÂN TÍCH CÁC PHÉP XỬ LÝ TOÁN HỌC TRONG HỆ MÃ RSA .................. 41
3.2 ỨNG DỤNG GIẢI THUẬT FAST FOURIER TRANSFORM TRONG XỬ LÝ
PHÉP NHÂN SỐ LỚN .................................................................................................... 45
3.1 CÀI ĐẶT THỬ NGHIỆM CÁC PHÉP TOÁN VỚI SỐ LỚN .............................. 53
CHƢƠNG 4: ỨNG DỤNG TRONG XÂY DỰNG HỆ MÃ RSA ..................................... 56
4.1 XÂY DỰNG HỆ MÃ RSA THỬ NGHIỆM ............................................................. 56
4.2 ĐÁNH GIÁ VÀ NHẬN XÉT KẾT QUẢ ................................................................. 59
CHƢƠNG 5 – KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .................................................. 60
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
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
CRT Chinese Remainder Theorem
DES Data Encryption Standard
RSA Rivest ShamirAdleman
GCD Great Comon Divisor
FFT Fast Fourier Transform
