Các thuật toán tối ưu hóa trong bảo mật thông tin

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

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

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ệ ElGamal..............25

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..............28

Bảng 2.3: Tóm tắt các bước tạo khoá, mã hoá, giải mã của Hệ ElGamal..............42