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

MỞ ĐẦU

1. Lý do chọn đề tài

Các hệ mã công khai như RSA thực hiện tính toán với các số nguyên lớn hàng trăm chữ số. Độ phức tạp trong việc giải mã các hệ mã này tỉ lệ thuận với độ lớn của các số nguyên tham gia vào việc tạo khóa mã hóa và khóa công khai. Do đó để hệ mã an toàn, cần tăng kích thước của các số nguyên.
Mặt khác, khi kích thước của các số nguyên cần xử lý lớn thì thời gian xử lý của chương trình mã hóa cũng tăng lên.
Thông tin cần mã hóa ngày càng đa dạng và có khối lượng lớn, đòi hỏi hệ mã giảm thiểu thời gian xử lý.
Các công cụ và giải thuật nhằm bẻ khóa các hệ mật mã được cải tiến đòi hỏi hệ mã cần được nâng cấp tính bảo mật.
Tuy nhiên, việc nghiên cứu và triển khai các nâng cấp trong việc tối ưu hóa về mặt thuật toán trong các phép xử lý số học của các hệ mã còn hạn chế trong phạm vi các chương trình độc quyền.
Để hỗ trợ giải quyết các vấn đề trên, đề tài này tập trung vào việc xây dựng một số thuật toán tối ưu hóa nhằm tăng hiệu quả các phép tính toán thực hiện với số nguyên lớn.
Các kết quả của đề tài sẽ được ứng dụng trong việc hỗ trợ cho các phép xử lý số học của các hệ mã. Từ đó làm tăng tốc độ xử lý và tính bảo mật của các hệ mã.
Từ tính cấp thiết của vấn đề tối ưu hóa các hệ mã công khai, đồng thời được sự hướng dẫn và gợi ý của PGS.TSKH Nguyễn Xuân Huy tôi đã chọn đề tài cho luận văn tốt nghiệp Cao học ngành khoa học máy tính là:
“Các thuật toán tối ưu hóa trong bảo mật thông tin”.




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


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




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



DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ



Trang

Hình 1.1: Mô hình mã hóa khóa đối xứng . 7

Hình 1.2: Mô hình mã hóa khóa bất đối xứng . 10

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

Hình 3.1: Sơ đồ thực hiện giải thuật nhân nhanh sử dụng DFT. . 49

Hình 3.2: Giao diện thực hiện phép cộng. 54

Hình 3.3: Giao diện thực hiện phép nhân. 55

Hình 4.1: Giao diện chương trình mô phỏng hệ RSA. . 56

Hình 4.2 và 4.3: Giao diện thực hiện mã hóa và giải mã file văn bản. 57