Các thuật toán tối ưu hóa trong bảo mật thông tin
- 67 trang
- file .pdf
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
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
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
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
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
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”.
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
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ông
khai.
- 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ả.
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
- 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ên
lớn.
Ứng dụng thử nghiệm trong một hệ mã nhằm so sánh hiệu năng xử lý của
hệ 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ố.
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
- Đƣ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.
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
12
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.
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
13
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
Lịch sử của mật mã học đã có từ rất sớm, ban đầu con ngƣời cố gắng tìm một
cách để bảo vệ thông tin, tránh việc thông tin bị giải mã khi ngƣời khác có đƣợc
chúng. Các cách áp dụng đó thƣờng mang tính mẹo mực đơn giản và có thể dễ dàng
bị giải mã nếu thông tin về cách thức che giấu bị lộ hoặc bị suy đoán. Mật mã học
ban đầu đƣợc áp dụng nhiều trong lĩnh vực quân đội. Các phƣơng pháp mã hóa cổ
điển đã đƣợc áp dụng nhƣ Caesar, Playfair, …
Các hệ mật mã cổ điển đƣợc sử dụng nhiều nhƣng dần dần chúng bộc lộ một
hạn chế lớn. Do các cách mã hóa đều dựa trên phƣơng pháp mã khóa bí mật, khi gửi
bản mã đi thì cần phải gửi kèm theo cả cách giải mã. Bên cạnh đó, nếu cách mã hóa
là quen thuộc hoặc đơn giản thì ngƣời có đƣợc thông tin đã bị mã hóa có thể tiến
hành các cách để dò ra luật mã hóa để có đƣợc văn bản gốc.
Ngày nay cũng với sự trợ giúp của máy tính điện tử, các phƣơng pháp mã hóa
với khóa bí mật đƣợc sử dụng chung cho quá trình mã hóa và giải mã (hay còn gọi
là mã hóa cổ điển) có thể dễ dàng bị giải mã.
Sự cần thiết phải có các phƣơng pháp mã hóa an toàn hơn đã đƣợc đáp ứng
bằng việc áp dụng các kết quả nghiên cứu của toán học. Sự thay đổi về phƣơng
pháp mã hóa cũng nhƣ độ an toàn của các hệ mã mới đã đƣa lịch sử của mật mã học
sang trang mới. Các hệ mật mã với khóa mã đối xứng đã góp phần to lớn trong việc
củng cố vai trò của mật mã học trong các ứng dụng của con ngƣời. Đƣa mật mã đến
với cả các ứng dụng trong cuộc sống đời thƣờng của con ngƣời, mật mã không còn
chỉ đƣợc nhắc đến nhiều trong lĩnh vực quân sự. Ứng của mật mã học đã trở thành
một công cụ cần thiết cho mọi ngƣời, cần thiết cho các hoạt động thƣờng ngày.
Các phƣơng pháp mã hóa khác nhau có những ƣu, nhƣợc điểm khác nhau. Khi
sử dụng các phƣơng pháp mã hóa, ngƣời dùng sẽ cân nhắc để lựa chọn phƣơng
pháp mã hóa thích hợp nhất đối với mình. Có thể lựa chọn môi trƣờng cần phải an
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
14
toàn tuyệt đối bất kể thời gian và chi phí hoặc lựa chọn môi trƣờng lại cần giải pháp
dung hòa giữa bảo mật và chi phí.
Các mô hình mã hóa có chung một số thuật ngữ nhƣ sau:
Bản rõ: Là nội dung của thông điệp cần gửi đi và cần đƣợc bảo vệ an toàn. Nó
có thể là xâu các bít, các file văn bản, các file có cấu trúc.
Mã hoá: Là quá trình xử lý thông điệp cần bảo mật trƣớc khi gửi đi.
Bản mã: Là kết quả thu đƣợc khi mã hóa bản rõ theo qui trình mã hóa của
phƣơng pháp đang đƣợc chọn.
Giải mã: Là quá trình xử lý ngƣợc, tiến hành giải mã bản mã để thu lại bản rõ.
Ví dụ: Mã hóa văn bản có nội dung là “ABC” với luật mã là tịnh tiến vòng 1
đơn vị đối với mã ASCII của mỗi kí tự.
Vậy ta có:
Bản rõ: “ABC”
Mã hóa: Thực hiện mã hóa theo luật mã.
Biến đổi các kí tự thành các số theo mã ASCII của kí tự đó.
A 65, B 66, C 67
Thu đƣợc các mã mới sau khi tịnh tiến là: 66 - 67 - 68
Biến đổi các mã mới thành kí tự.
Bản mã: “BCD”.
Giải mã: Thu đƣợc bản rõ là “ABC”.
1.1.1. Khái niệm chung về mật mã
Hệ mật mã hiện đại thƣờng gồm 5 thành phần (P, C, K, E, D) trong đó:
P (Plaintext) tập hợp hữu hạn các bản rõ có thể (không gian các bản rõ).
C (Ciphertext) tập hợp hữu hạn các bản mã có thể (không gian các bản mã).
K (Key) tập hợp các bản khoá có thể.
E (Encrytion) tập hợp các qui tắc mã hoá có thể.
D (Decrytion) tập hợp các qui tắc giải mã có thể.
Nội dung cần mã hóa thể hiện dƣới dạng bản rõ (P). Ngƣời gửi sử dụng qui tắc
(E) và khóa (K) mã hoá bản rõ (P), kết quả thu đƣợc gọi là bản mã (EK(P) = C). Bả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
15
mã này đƣợc gửi đi trên một đƣờng truyền tới ngƣời nhận, sau khi nhận đƣợc bản
mã (C) ngƣời nhận sử dụng qui tắc (D) và khóa (K) giải mã nó để hiểu đƣợc nội
dung thông điệp gốc (DK(C) = P).
1.1.2. Những yêu cầu đối với hệ mật mã hiện đại
Hệ mật mã hiện đại cần đảm bảo đƣợc hai yêu cầu sau:
- Đảm bảo tính bảo mật.
- Đảm bảo tính xác thực.
Bảo mật: Ngăn không để ngƣời lạ thực hiện việc trích chọn, sửa đổi thông tin
từ các bản mã đƣợc gửi trên các kênh truyền phổ biến (thƣờng không an toàn).
Xác thực: Đảm bảo chỉ có ngƣời nhận đúng mới có thể giải mã nội dung bản
mã, đồng thời cũng đảm bảo ngƣời gửi không thể phủ nhận nội dung đã gửi.
1.1.3 Các phƣơng pháp mã hóa
1.1.3.1 Hệ thống mã hóa đối xứng
Cả hai quá trình mã hóa và giải mã của hệ thống mã hóa đối xứng đều sử
dụng chung một khóa bí mật. Do đó, khi bị mất khóa bí mật này thì tính bảo mật
của hệ mã bị phá vỡ.
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.1)
Bản mã
Bản rõ Mã hóa Giải mã Bản rõ
Khóa bí mật
Hình 1.1: Sơ đồ hoạt động của mã hóa khóa đối xứng
Các hệ mật mã nhƣ DES, 3DES-Triple DES đƣợc xây dựng trên phƣơng
pháp 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
16
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 hơ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.
- Nội dung của bản rõ không thể xác thực đƣợc nguồn gốc 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 cho công việc khi một ngƣời phải giữ nhiều khóa bí mật
khi 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ã với khóa mã đối xứng khó có thể áp
dụng rộng rãi. Trong nội dung của đề tài này, các phƣơng pháp mã hóa với khóa mã
công khai đƣợc nghiên cứu để thực hiện mục đích của đề tài.
1.1.3.2 Hệ thống mã hóa bất đối xứng
Hệ thống mã hóa bất đối xứng hay còn gọi là mã hóa với khóa công khai đã
đƣợc Martin Hellman, Ralph Merkle và Whitfield Diffie thuộc Đại học Stanford
giới thiệu vào năm 1976.
Hệ mã này đƣợc áp dụng các kết quả của toán học đã khắc phục đƣợc các hạn
chế của các phƣơng pháp mã hóa khóa đối xứng. Phƣơng pháp mã hóa bất đối xứng
sử dụng hai loại khóa trong cùng một cặp khóa: Khóa công khai (public key) đƣợc
công bố rộng rãi và sử dụng để mã hóa các thông điệp, khóa riêng (private key) chỉ
do chủ thể nắm giữ và đƣợc sử dụng để giải mã thông điệp đã đƣợc mã hóa bằng
khóa công khai.
Các lý thuyết toán học dựa trên cơ sở khai thác những ánh xạ f mà việc thực
hiện ánh xạ ngƣợc f -1 rất khó so với việc thực hiện ánh xạ f đƣợc sử dụng trong
các phƣơng pháp mã hóa này. Việc thực hiện ánh xạ ngƣợc f -1 chỉ tiến hành đƣợc
khi biết đƣợc khóa riê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
17
Bản mã
Bản rõ Mã hóa Giải mã Bản rõ
Khóa mã Khóa giải
Hình 1.2 Sơ đồ hoạt động của mã hóa khóa bất đối xứng
Khi thực hiện mã hóa bất đối xứng, ngƣời A sử dụng khóa công khai 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 nên B mới
có thể giải mã đƣợc thông điệp mà A đã mã hóa. Trong trƣờng hợp bản mã bị một
ngƣời thứ ba có đƣợc, nếu chỉ kết hợp với thông tin về khóa công khai đã đƣợ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 nắm đƣợc khóa riêng của B.
Khóa công khai và khóa riêng 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 lớn dẫn đến
thời gian thực hiện để giải mã là không khả thi 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. Đề tài này sẽ đề cập đến 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.
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 tiến hành chạy 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ẽ thu đƣợc thời gian thực hiện thuật toán khác nhau. Do đó ta 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.
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
18
Độ phức tạp của một thuật toán sẽ đƣợc tính bằng số các phép tính cơ sở máy
tính thực hiện khi tiến hành chạy thuật toán (các phép tính cơ sở: đọc, ghi, phép so
sánh). Ngoài ra, số lƣợng phép tính còn phụ thuộc vào kích cỡ đầ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ó đƣợc một ƣớc lƣợng chấp nhận đƣợc.
Độ phức tạp của một thuật toán đƣợ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ố một bit 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.1:
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) < Cg(n).
Định nghĩa 1.2:
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 kn),
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ũ.
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 để tránh hiểu sai về độ phức tạp thực sự của thuật toán.
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 thì 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.
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
19
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 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:
Giải thuật này có độ phức tạp dƣới mũ:
exp log n log log n .
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ố
Số phép tính
Số chữ số thập phân Thời gian
trên bit
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
Dễ nhận thấy rằng 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 áp dụng trong phần nghiên cứu của để tài để xử lý cho các phép toán số
học với số lớn trong các hệ mã hóa công khai.
1.2.2 Các bài toán khó tính toán và ứng dụng trong mật mã học
Một hệ mật phải cố gắng gây khó khăn cho ngƣời giải mã khi không biết khóa
giải nhƣng lại dễ dàng giải mã khi biết đƣợc khóa giải mã.
Một hệ mã nhƣ vậy sẽ có một thông tin “cửa sập” bí mật đƣợc chèn thêm vào
bài toán dựa trên tính khó khăn khi thực hiện nghịch đảo một hàm một chiều.
Định nghĩa 1.3:
Cho các tập hữu hạn S, T. Hàm f : S T đƣợc gọi là hàm một chiều (one-
way function) nếu nhƣ:
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
20
- Hàm f dễ tính toán, nghĩa là x S, có thể dễ dàng tính y = f(x).
- Hàm ngƣợc f -1(y) khó tính, nghĩa là cho y T thì khó tính đƣợc x = f -1(y).
Định nghĩa 1.4:
Hàm một chiều cửa sập (trapdoor one-way function) là hàm một chiều f đƣợc
thêm vào thông tin cửa sập (trapdoor information) để có thể dễ dàng tính x khi biết
bất kỳ y T thoả mãn x = f -1(y).
Ví dụ về hàm một chiều:
- f(p,q) = p*q, là hàm một chiều với p, q là các số nguyên tố lớn. Nhƣ vậy, ta
có thể thực hiện phép nhân p * q (độ phức tạp đa thức); nhƣng tính f -1 lại là bài toán
cực khó (bài toán phân tích ra thừa số nguyên tố - độ phức tạp mũ).
- fg ,N : x gx mod N là hàm một chiều. Thực vậy, phép tính gx mod N có độ
phức tạp đa thức; nhƣng tính f -1 lại là bài toán cực khó (bài toán logarithm rời rạc).
- fk ,N : x xk mod N là hàm một chiều, với N = pq, p và q là các số nguyên tố
lớn, kk’ 1(mod φ(N)). Thực vậy, phép tính xk mod N có độ phức tạp đa thức,
nhƣng tính f -1 lại cực khó. Tuy nhiên, nếu biết k’ có thể dễ dàng tính đƣợc f từ công
thức (xk)k’= x.
1.3 CƠ SỞ TOÁN HỌC CỦA MẬT MÃ
1.3.1. Hàm phi Euler
Định nghĩa 1.5
Cho n ≥1, đặt φ(n) là tập các số nguyên trong khoảng [1, n] nguyên tố cùng
nhau với n. Hàm φ nhƣ thế đƣợc gọi là hàm phi Euler.
* Tính chất của hàm phi Euler
1. Nếu p là số nguyên tố thì φ(n) = p – 1
2. Hàm phi Euler là hàm có tính nhân: Nếu gcd(m,n) = 1 thì φ(m.n) =
φ(m).φ(n). (trong đó gcd(m, n) là ký hiệu ƣớc số chung lớn nhất của m và n)
Nếu n = p1e1p2e2…pkek trong đó p1, p2, ..., pk là các thừa số nguyên tố của n thì:
1 1 1
φ(n) = n(1 - )(1 - )… (1 - )
p1 p2 pk
1.3.2. Lý thuyết đồng dƣ 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
ĐẠ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
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
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
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
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
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”.
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
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ông
khai.
- 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ả.
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
- 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ên
lớn.
Ứng dụng thử nghiệm trong một hệ mã nhằm so sánh hiệu năng xử lý của
hệ 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ố.
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
- Đƣ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.
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
12
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.
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
13
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
Lịch sử của mật mã học đã có từ rất sớm, ban đầu con ngƣời cố gắng tìm một
cách để bảo vệ thông tin, tránh việc thông tin bị giải mã khi ngƣời khác có đƣợc
chúng. Các cách áp dụng đó thƣờng mang tính mẹo mực đơn giản và có thể dễ dàng
bị giải mã nếu thông tin về cách thức che giấu bị lộ hoặc bị suy đoán. Mật mã học
ban đầu đƣợc áp dụng nhiều trong lĩnh vực quân đội. Các phƣơng pháp mã hóa cổ
điển đã đƣợc áp dụng nhƣ Caesar, Playfair, …
Các hệ mật mã cổ điển đƣợc sử dụng nhiều nhƣng dần dần chúng bộc lộ một
hạn chế lớn. Do các cách mã hóa đều dựa trên phƣơng pháp mã khóa bí mật, khi gửi
bản mã đi thì cần phải gửi kèm theo cả cách giải mã. Bên cạnh đó, nếu cách mã hóa
là quen thuộc hoặc đơn giản thì ngƣời có đƣợc thông tin đã bị mã hóa có thể tiến
hành các cách để dò ra luật mã hóa để có đƣợc văn bản gốc.
Ngày nay cũng với sự trợ giúp của máy tính điện tử, các phƣơng pháp mã hóa
với khóa bí mật đƣợc sử dụng chung cho quá trình mã hóa và giải mã (hay còn gọi
là mã hóa cổ điển) có thể dễ dàng bị giải mã.
Sự cần thiết phải có các phƣơng pháp mã hóa an toàn hơn đã đƣợc đáp ứng
bằng việc áp dụng các kết quả nghiên cứu của toán học. Sự thay đổi về phƣơng
pháp mã hóa cũng nhƣ độ an toàn của các hệ mã mới đã đƣa lịch sử của mật mã học
sang trang mới. Các hệ mật mã với khóa mã đối xứng đã góp phần to lớn trong việc
củng cố vai trò của mật mã học trong các ứng dụng của con ngƣời. Đƣa mật mã đến
với cả các ứng dụng trong cuộc sống đời thƣờng của con ngƣời, mật mã không còn
chỉ đƣợc nhắc đến nhiều trong lĩnh vực quân sự. Ứng của mật mã học đã trở thành
một công cụ cần thiết cho mọi ngƣời, cần thiết cho các hoạt động thƣờng ngày.
Các phƣơng pháp mã hóa khác nhau có những ƣu, nhƣợc điểm khác nhau. Khi
sử dụng các phƣơng pháp mã hóa, ngƣời dùng sẽ cân nhắc để lựa chọn phƣơng
pháp mã hóa thích hợp nhất đối với mình. Có thể lựa chọn môi trƣờng cần phải an
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
14
toàn tuyệt đối bất kể thời gian và chi phí hoặc lựa chọn môi trƣờng lại cần giải pháp
dung hòa giữa bảo mật và chi phí.
Các mô hình mã hóa có chung một số thuật ngữ nhƣ sau:
Bản rõ: Là nội dung của thông điệp cần gửi đi và cần đƣợc bảo vệ an toàn. Nó
có thể là xâu các bít, các file văn bản, các file có cấu trúc.
Mã hoá: Là quá trình xử lý thông điệp cần bảo mật trƣớc khi gửi đi.
Bản mã: Là kết quả thu đƣợc khi mã hóa bản rõ theo qui trình mã hóa của
phƣơng pháp đang đƣợc chọn.
Giải mã: Là quá trình xử lý ngƣợc, tiến hành giải mã bản mã để thu lại bản rõ.
Ví dụ: Mã hóa văn bản có nội dung là “ABC” với luật mã là tịnh tiến vòng 1
đơn vị đối với mã ASCII của mỗi kí tự.
Vậy ta có:
Bản rõ: “ABC”
Mã hóa: Thực hiện mã hóa theo luật mã.
Biến đổi các kí tự thành các số theo mã ASCII của kí tự đó.
A 65, B 66, C 67
Thu đƣợc các mã mới sau khi tịnh tiến là: 66 - 67 - 68
Biến đổi các mã mới thành kí tự.
Bản mã: “BCD”.
Giải mã: Thu đƣợc bản rõ là “ABC”.
1.1.1. Khái niệm chung về mật mã
Hệ mật mã hiện đại thƣờng gồm 5 thành phần (P, C, K, E, D) trong đó:
P (Plaintext) tập hợp hữu hạn các bản rõ có thể (không gian các bản rõ).
C (Ciphertext) tập hợp hữu hạn các bản mã có thể (không gian các bản mã).
K (Key) tập hợp các bản khoá có thể.
E (Encrytion) tập hợp các qui tắc mã hoá có thể.
D (Decrytion) tập hợp các qui tắc giải mã có thể.
Nội dung cần mã hóa thể hiện dƣới dạng bản rõ (P). Ngƣời gửi sử dụng qui tắc
(E) và khóa (K) mã hoá bản rõ (P), kết quả thu đƣợc gọi là bản mã (EK(P) = C). Bả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
15
mã này đƣợc gửi đi trên một đƣờng truyền tới ngƣời nhận, sau khi nhận đƣợc bản
mã (C) ngƣời nhận sử dụng qui tắc (D) và khóa (K) giải mã nó để hiểu đƣợc nội
dung thông điệp gốc (DK(C) = P).
1.1.2. Những yêu cầu đối với hệ mật mã hiện đại
Hệ mật mã hiện đại cần đảm bảo đƣợc hai yêu cầu sau:
- Đảm bảo tính bảo mật.
- Đảm bảo tính xác thực.
Bảo mật: Ngăn không để ngƣời lạ thực hiện việc trích chọn, sửa đổi thông tin
từ các bản mã đƣợc gửi trên các kênh truyền phổ biến (thƣờng không an toàn).
Xác thực: Đảm bảo chỉ có ngƣời nhận đúng mới có thể giải mã nội dung bản
mã, đồng thời cũng đảm bảo ngƣời gửi không thể phủ nhận nội dung đã gửi.
1.1.3 Các phƣơng pháp mã hóa
1.1.3.1 Hệ thống mã hóa đối xứng
Cả hai quá trình mã hóa và giải mã của hệ thống mã hóa đối xứng đều sử
dụng chung một khóa bí mật. Do đó, khi bị mất khóa bí mật này thì tính bảo mật
của hệ mã bị phá vỡ.
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.1)
Bản mã
Bản rõ Mã hóa Giải mã Bản rõ
Khóa bí mật
Hình 1.1: Sơ đồ hoạt động của mã hóa khóa đối xứng
Các hệ mật mã nhƣ DES, 3DES-Triple DES đƣợc xây dựng trên phƣơng
pháp 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
16
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 hơ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.
- Nội dung của bản rõ không thể xác thực đƣợc nguồn gốc 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 cho công việc khi một ngƣời phải giữ nhiều khóa bí mật
khi 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ã với khóa mã đối xứng khó có thể áp
dụng rộng rãi. Trong nội dung của đề tài này, các phƣơng pháp mã hóa với khóa mã
công khai đƣợc nghiên cứu để thực hiện mục đích của đề tài.
1.1.3.2 Hệ thống mã hóa bất đối xứng
Hệ thống mã hóa bất đối xứng hay còn gọi là mã hóa với khóa công khai đã
đƣợc Martin Hellman, Ralph Merkle và Whitfield Diffie thuộc Đại học Stanford
giới thiệu vào năm 1976.
Hệ mã này đƣợc áp dụng các kết quả của toán học đã khắc phục đƣợc các hạn
chế của các phƣơng pháp mã hóa khóa đối xứng. Phƣơng pháp mã hóa bất đối xứng
sử dụng hai loại khóa trong cùng một cặp khóa: Khóa công khai (public key) đƣợc
công bố rộng rãi và sử dụng để mã hóa các thông điệp, khóa riêng (private key) chỉ
do chủ thể nắm giữ và đƣợc sử dụng để giải mã thông điệp đã đƣợc mã hóa bằng
khóa công khai.
Các lý thuyết toán học dựa trên cơ sở khai thác những ánh xạ f mà việc thực
hiện ánh xạ ngƣợc f -1 rất khó so với việc thực hiện ánh xạ f đƣợc sử dụng trong
các phƣơng pháp mã hóa này. Việc thực hiện ánh xạ ngƣợc f -1 chỉ tiến hành đƣợc
khi biết đƣợc khóa riê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
17
Bản mã
Bản rõ Mã hóa Giải mã Bản rõ
Khóa mã Khóa giải
Hình 1.2 Sơ đồ hoạt động của mã hóa khóa bất đối xứng
Khi thực hiện mã hóa bất đối xứng, ngƣời A sử dụng khóa công khai 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 nên B mới
có thể giải mã đƣợc thông điệp mà A đã mã hóa. Trong trƣờng hợp bản mã bị một
ngƣời thứ ba có đƣợc, nếu chỉ kết hợp với thông tin về khóa công khai đã đƣợ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 nắm đƣợc khóa riêng của B.
Khóa công khai và khóa riêng 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 lớn dẫn đến
thời gian thực hiện để giải mã là không khả thi 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. Đề tài này sẽ đề cập đến 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.
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 tiến hành chạy 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ẽ thu đƣợc thời gian thực hiện thuật toán khác nhau. Do đó ta 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.
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
18
Độ phức tạp của một thuật toán sẽ đƣợc tính bằng số các phép tính cơ sở máy
tính thực hiện khi tiến hành chạy thuật toán (các phép tính cơ sở: đọc, ghi, phép so
sánh). Ngoài ra, số lƣợng phép tính còn phụ thuộc vào kích cỡ đầ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ó đƣợc một ƣớc lƣợng chấp nhận đƣợc.
Độ phức tạp của một thuật toán đƣợ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ố một bit 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.1:
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) < Cg(n).
Định nghĩa 1.2:
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 kn),
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ũ.
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 để tránh hiểu sai về độ phức tạp thực sự của thuật toán.
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 thì 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.
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
19
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 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:
Giải thuật này có độ phức tạp dƣới mũ:
exp log n log log n .
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ố
Số phép tính
Số chữ số thập phân Thời gian
trên bit
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
Dễ nhận thấy rằng 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 áp dụng trong phần nghiên cứu của để tài để xử lý cho các phép toán số
học với số lớn trong các hệ mã hóa công khai.
1.2.2 Các bài toán khó tính toán và ứng dụng trong mật mã học
Một hệ mật phải cố gắng gây khó khăn cho ngƣời giải mã khi không biết khóa
giải nhƣng lại dễ dàng giải mã khi biết đƣợc khóa giải mã.
Một hệ mã nhƣ vậy sẽ có một thông tin “cửa sập” bí mật đƣợc chèn thêm vào
bài toán dựa trên tính khó khăn khi thực hiện nghịch đảo một hàm một chiều.
Định nghĩa 1.3:
Cho các tập hữu hạn S, T. Hàm f : S T đƣợc gọi là hàm một chiều (one-
way function) nếu nhƣ:
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
20
- Hàm f dễ tính toán, nghĩa là x S, có thể dễ dàng tính y = f(x).
- Hàm ngƣợc f -1(y) khó tính, nghĩa là cho y T thì khó tính đƣợc x = f -1(y).
Định nghĩa 1.4:
Hàm một chiều cửa sập (trapdoor one-way function) là hàm một chiều f đƣợc
thêm vào thông tin cửa sập (trapdoor information) để có thể dễ dàng tính x khi biết
bất kỳ y T thoả mãn x = f -1(y).
Ví dụ về hàm một chiều:
- f(p,q) = p*q, là hàm một chiều với p, q là các số nguyên tố lớn. Nhƣ vậy, ta
có thể thực hiện phép nhân p * q (độ phức tạp đa thức); nhƣng tính f -1 lại là bài toán
cực khó (bài toán phân tích ra thừa số nguyên tố - độ phức tạp mũ).
- fg ,N : x gx mod N là hàm một chiều. Thực vậy, phép tính gx mod N có độ
phức tạp đa thức; nhƣng tính f -1 lại là bài toán cực khó (bài toán logarithm rời rạc).
- fk ,N : x xk mod N là hàm một chiều, với N = pq, p và q là các số nguyên tố
lớn, kk’ 1(mod φ(N)). Thực vậy, phép tính xk mod N có độ phức tạp đa thức,
nhƣng tính f -1 lại cực khó. Tuy nhiên, nếu biết k’ có thể dễ dàng tính đƣợc f từ công
thức (xk)k’= x.
1.3 CƠ SỞ TOÁN HỌC CỦA MẬT MÃ
1.3.1. Hàm phi Euler
Định nghĩa 1.5
Cho n ≥1, đặt φ(n) là tập các số nguyên trong khoảng [1, n] nguyên tố cùng
nhau với n. Hàm φ nhƣ thế đƣợc gọi là hàm phi Euler.
* Tính chất của hàm phi Euler
1. Nếu p là số nguyên tố thì φ(n) = p – 1
2. Hàm phi Euler là hàm có tính nhân: Nếu gcd(m,n) = 1 thì φ(m.n) =
φ(m).φ(n). (trong đó gcd(m, n) là ký hiệu ƣớc số chung lớn nhất của m và n)
Nếu n = p1e1p2e2…pkek trong đó p1, p2, ..., pk là các thừa số nguyên tố của n thì:
1 1 1
φ(n) = n(1 - )(1 - )… (1 - )
p1 p2 pk
1.3.2. Lý thuyết đồng dƣ 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