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

2. Mục đích và nhiệm vụ

 Mục tiêu

o Về học thuật:

Đề 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.

o Về phát triển và triển khai ứng dụng:

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 với số nguyên lớn trong 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ã.

 Nhiệm vụ

- Nghiên cứu các quá trình thực hiện mã hóa và giải mã của các hệ mã côngkhai.

- Tìm hiểu các thuật toán xử lý số học được dùng trong các hệ mã.

- Phát hiện các giải thuật tính toán cần tối ưu hóa.

- Thực hiện đưa ra giải pháp tối ưu hóa các giải thuật này.

- Ứng dụng trong một hệ mã cụ thể.

- So sánh với kết quả thực thi của hệ mã khi chưa thực hiện tối ưu hóa.

3. Phương pháp nghiên cứu

- Nghiên cứu dựa trên việc tìm hiểu các giải thuật xử lý với số nguyên lớn của các hệ mã. Cụ thể là hệ mã hóa RSA, từ kết quả nghiên cứu có được sẽ định hướng lựa chọn thuật toán nào cần tối ưu hóa.

- Thực hiện việc tối ưu hóa các giải thuật bằng cách tối ưu các phép xử lý với số học lớn. Thao tác này sử dụng kết hợp các phương pháp tính toán với số học nhằm tăng hiệu năng của từng bước xử lý.

- Thu thập các tài liệu đã xuất bản, các bài báo trên các tạp chí khoa học và các tài liệu trên mạng Internet có liên quan đến vấn đề đang nghiên cứu.

- Tìm hiểu, vận dụng và kế thừa các thuật toán và qui trình mã đã công bốkết quả.

- Thực nghiệm cài đặt ứng dụng để minh họa các vấn đề trình bày trong đề tài.

4. Đối tượng và phạm vi nghiên cứu

 Đối tượng nghiên cứu :

Các hệ mật mã khóa công khai, trong đó hệ mật mã RSA được sử dụng làm đối tượng nghiên cứu chính của đề tài nhằm phát hiện các phép xử lý toán học cần tối ưu. Từ các kết quả thu được bước đầu đề tài đưa ra một cách xây dựng thử nghiệm hệ mã RSA áp dụng các kết quả tối ưu hóa.

 Phạm vi nghiên cứu

Đề tài thực hiện việc tối ưu hóa với một số phép tính toán với số nguyênlớn.

Ứng dụng thử nghiệm trong một hệ mã nhằm so sánh hiệu năng xử lý củahệ mã trước và sau khi tối ưu.

Đề tài giới hạn trong phạm vi nghiên cứu để đưa ra giải pháp, việc triển khai ứng dụng thực tiễn cần có thêm các điều kiện về thời gian và quy mô.

5. Ý nghĩa khoa học và thực tiễn của luận văn

 Ý nghĩa khoa học

- Trình bày các kiến thức toán học cơ bản, lý thuyết độ phức tạp của thuật toán, các thuật toán thường dùng trong các hệ mật mã khoá công khai.

- Trình bày các phương pháp mật mã gồm: Phương pháp mã hoá khóa bí mật và phương pháp mã hoá khóa công khai. Với phương pháp mã hóa khóa công khai thì tập trung vào các thuật toán mã hóa RSA. Với phương pháp mã hóa khóa bí mật chỉ giới thiệu sơ lược để so sánh với phương pháp mã hóa khóa công khai.

- Tối ưu các phép xử lý số học với số nguyên lớn là một yêu cầu cần thiết trong việc xây dựng các hệ mã hóa có tốc độ xử lý và độ an toàn cao.

 Ý nghĩa thực tiễn

- Cài đặt hoàn chỉnh các giải thuật xử lý số học với số nguyên lớn cỡ hàng trăm chữ số.

- Đưa ra được chương trình thử nghiệm các giải thuật xây dựng được trong một hệ mã.

- Đưa ra kết quả so sánh hiệu năng xử lý của hệ mã trước và sau khi tối ưu.

6. Bố cục của luận văn

Mở đầu

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

2. Mục đích và ý nghĩa.

3. Phương pháp nghiên cứu.

4. Đối tượng và phạm vi nghiên cứu.

5. Ý nghĩa khoa học và thực tiễn của luận văn.

Chương 1: Nghiên cứu lý thuyết và thực tiển về mã hóa dữ liệu.

1.1 Một số khái niệm cơ bản về mã hóa.

1.2 Lý thuyết độ phức tạp của thuật toán.

1.3 Các phép xử lý số học cơ bản – Cơ sở toán học của mật mã.

Chương 2: Các thuật toán xử lý số học trong các hệ mã thông dụng.

2.1 Giới thiệu về hệ mật mã với khóa công khai.

2.2 Hệ mật mã công khai RSA.

2.3 Hệ mật mã công khai RSA with CRT.

2.4 Phân tích cơ chế hoạt động của hệ mã RSA.

2.5 Các phép xử lý số học trong hệ mã RSA.

2.6 Khả năng bị bẻ khóa của hệ mã công khai RSA.

2.7 Hệ mật mã khóa công khai ELGAMAL.

Chương 3: Tối ưu hóa một số giải thuật xử lý số học trong một hệ mã cụ thể.

3.1 Phân tích các giải thuật xử lý số học trong hệ mã RSA

3.2 Tối ưu hóa các giải thuật để xử lý với các số nguyên lớn.

Chương 4: Ứng dụng kết quả trong một hệ mã hóa cụ thể.

4.1 Xây dựng ứng dụng.

4.2 Kiểm nghiệm và so sánh kết quả đạt được trước và sau khi tối ưu hóa.

Chương 5: Kết luận.

5.1 Đánh giá và nêu ưu nhược điểm của đề tài.

5.2 Định hướng phát triển đề tài.

7. Đóng góp của luận văn

- Luận văn hệ thống các cơ sở lý thuyết cơ bản về hệ mật mã khóa công khai.

- Xây dựng chương trình thử nghiệm ứng dụng bảo mật và xác thực trong giảng dạy. Từ đó có thể mở rộng và hoàn thiện thêm một số chức năng để đưa vàoứng dụng trong thực tiễn.

MỤC LỤC

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