Tài liệu Luận văn 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
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...
67 trang |
Chia sẻ: hunglv | Lượt xem: 1308 | Lượt tải: 1
Bạn đang xem trước 20 trang mẫu tài liệu Luận văn Các thuật toán tối ưu hóa trong bảo mật thông tin, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
KHOA CƠNG NGHỆ THƠNG TIN
ĐẠI HỌC THÁI NGUYÊN
NGUYỄN NGỌC TRUNG
CÁC THUẬT TỐ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
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à hồ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 hồ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
3
LỜI CAM ĐOAN
Tơi xin cam đoan, tồ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
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Ở TỐ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Ý TỐ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 TỐ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
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
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 khố, mã hố, 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 khố, mã hố, 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
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
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 tố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 tồ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 tố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 tốn tối ƣu hĩa nhằm tăng hiệu quả các phép tính tố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 tố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
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 tốn tối ƣu hĩa nhằm
tăng hiệu quả các phép tính tố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 tố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 tố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 tố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 tố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 tố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
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ý tố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 tố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 tốn học cơ bản, lý thuyết độ phức tạp của thuật
tốn, các thuật tốn thƣờng dùng trong các hệ mật mã khố cơng khai.
- Trình bày các phƣơng pháp mật mã gồm: Phƣơng pháp mã hố khĩa bí mật
và phƣơng pháp mã hố 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 tố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 tồn cao.
Ý nghĩa thực tiễn
- Cài đặt hồ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
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 tốn.
1.3 Các phép xử lý số học cơ bản – Cơ sở tốn học của mật mã.
Chƣơng 2: Các thuật tố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
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à hồ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
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 đố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 tồn hơn đã đƣợc đáp ứng
bằng việc áp dụng các kết quả nghiên cứu của tốn học. Sự thay đổi về phƣơng
pháp mã hĩa cũng nhƣ độ an tồ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
14
tồ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 tồ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ã hố: 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 khố cĩ thể.
E (Encrytion) tập hợp các qui tắc mã hố 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ã hố 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
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 tồ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)
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.
Bản mã
Bản rõ Mã hĩa Giải mã Bản rõ
Khĩa bí mật
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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 tồ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 tố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 tố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
17
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ệ tốn học với nhau theo nghĩa từ
khĩa riêng cĩ thể tính tố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 tố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 tồ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 tồn của các hệ mã này bằng cách
cố gắng áp dụng các thuật tố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 tốn
Khi tiến hành chạy cùng một thuật tố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 tốn khác nhau. Do đĩ ta khơng thể lấy
thời gian thực hiện của thuật tốn trên một máy tính để đánh giá độ phức tạp của
thuật tốn.
Bản mã
Bản rõ Mã hĩa Giải mã Bản rõ
Khĩa mã Khĩa giải
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
Độ phức tạp của một thuật tố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 tốn (các phép tính cơ sở: đọc, ghi, phép so
sánh). Ngồ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
tốn. Nhƣ vậy, độ phức tạp của thuật tố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 tố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 tố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 tố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 tốn khơng vƣợt quá O(logkn),
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 tốn là
O(m
d), tức là tƣơng đƣơng với một đa thức của m.
Các thuật tốn với thời gian O(αn), α > 1, đƣợc gọi là các thuật tốn với độ
phức tạp mũ, hoặc thời gian mũ.
Một thuật tố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 tốn.
Tồn tại những thuật tốn cĩ độ phức tạp trung gian giữa đa thức và mũ. Các
thuật tốn đĩ đƣợc gọi là thuật tốn dƣới mũ.
Độ phức tạp khơng phải là tiêu chuẩn duy nhất để đánh giá thuật tốn. Cĩ
những thuật tốn, về lý thuyết thì cĩ độ phức tạp cao hơn một thuật tố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
19
Bảng dƣới đây đƣa ra các thơng số về thời gian và số lƣợng phép tố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 tố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ũ:
.logloglogexp nn
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ố chữ số thập phân
Số phép tính
trên bit
Thời gian
50 1,4.10
10
3,9 giờ
75 9,0.10
12
104 ngày
100 2,3.10
15
74 năm
200 1,2.10
23
3,8.10
9
năm
300 1,5.10
29
4,9.10
15
năm
500 1,3.10
39
4,2.10
25
năm
Dễ nhận thấy rằng với một thuật tố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 tốn cĩ thời gian tính tố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 tố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 tốn khĩ tính tố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 tố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
20
- Hàm f dễ tính tố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 tốn
cực khĩ (bài tốn phân tích ra thừa số nguyên tố - độ phức tạp mũ).
- fg ,N : x g
x
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 tốn cực khĩ (bài tốn logarithm rời rạc).
- fk ,N : x x
k
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Ở TỐ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 = p1
e1
p2
e2…pk
ek
trong đĩ p1, p2, ..., pk là các thừa số nguyên tố của n thì:
φ(n) = n(1 -
1
1
p
)(1 -
2
1
p
)… (1 -
pk
1
)
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
21
Định nghĩa 1.6
Cho a và b là các số nguyên, a đƣợc gọi là đồng dƣ với b theo modulo n, ký hiệu
là a b (mod n) nếu n chia hết (a-b). Số nguyên n đƣợc gọi là modulo của đồng dƣ.
* Tính chất của đồng dư: Cho a, a1, b, b1, c Z. Ta cĩ các tính chất sau:
i. a a(mod n) (phản xạ);
ii. Nếu a b(mod n)
b a(mod n) (đối xứng);
iii. Nếu a b(mod n), b c(mod n)
a c(mod n) (bắc cầu);
iv. Nếu a a1(mod n), b b1(mod n) a + b (a1 + b1)(mod n), ab (a1b1)
(mod n), a
n
(a1)
n(mod n), với mọi n Z.
Ta cĩ khái niệm lớp tƣơng đƣơng nhƣ sau: Lớp tƣơng đƣơng của một số
nguyên a là tập hợp các số nguyên đồng dƣ với a theo modulo n. Từ các tính chất i,
ii và iii ta thấy: Cho n cố định, các số đồng dƣ theo modulo n trong khơng gian Z đƣợc
xếp vào một lớp tƣơng đƣơng. Nếu a = qn + r, trong đĩ 0 ≤ r < n thì a r (mod n). Vì vậy
mỗi số nguyên a là đồng dƣ theo modulo n với duy nhất một số nguyên trong
khoảng [0, n-1] và đƣợc gọi là thặng dƣ nhỏ nhất của a theo modulo n, a và r cùng
thuộc một lớp tƣơng đƣơng. Do đĩ r cĩ thể đơn giản đƣợc sử dụng để thể hiện lớp
tƣơng đƣơng.
1.3.3. Khơng gian Zn
* Các định nghĩa trong khơng gian Zn
- Các số nguyên theo modulo n ký hiệu Zn là một tập hợp các số nguyên {0, 1, 2,
3,…, n - 1}. Các phép tốn cộng, trừ, nhân trong Zn đƣợc thực hiện theo modulo n.
- Cho aZn. Nghịch đảo nhân của a theo modulo n là một số nguyên x Zn
sao cho a*x 1(mod n). Nếu x tồn tại thì đĩ là giá trị duy nhất và a đƣợc gọi là khả
nghịch, nghịch đảo của a ký hiệu là a -1.
- Cho a, bZn. Phép chia của a cho b theo modulo n là tích của a và b
-1
theo
modulo n, và chỉ đƣợc xác định khi b cĩ nghịch đảo theo modulo n.
* Các tính chất trong khơng gian Zn
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
Cho a Zn, a cĩ nghịch đảo khi và chỉ khi a và n nguyên tố cùng nhau
(gcd(a,n) = 1), trong đĩ gcd(a,n) là ƣớc số chung lớn nhất của a và n.
Giả sử d = gcd(a,n). Phƣơng trình đồng dƣ ax b (mod n) cĩ nghiệm x nếu
và chỉ nếu b chia hết cho d, trong trƣờng hợp các nghiệm d nằm trong khoảng [0, n-
1] thì các nghiệm đồng dƣ theo modulo n/d.
1.3.4 Nhĩm nhân Z*n
* Các định nghĩa trong nhĩm nhân Z*n
- Nhĩm nhân của Zn ký hiệu là Z
*
n = {a Zn | gcd (a, n) = 1}. Nếu n là số
nguyên tố thì Z*n = {aZn | 1 ≤ a ≤ n-1}
- Cho aZn
*
. Bậc của a ký hiệu là ord(a) là số nguyên dƣơng t nhỏ nhất sao
cho a
t
≡ 1(mod n).
- Cho aZn
*
. Bậc của a ký hiệu là ord(a) là số nguyên dƣơng t nhỏ nhất sao
cho a
t
1 (mod n).
* Các tính chất trong Zn
*
- Cho số nguyên n ≥ 2 .
Định lý 1.1 (Euler)
Nếu a Zn
*
thì aφ(n) 1 (mod n).
Nếu n là tích của các số nguyên tố phân biệt và nếu r s(mod φ(n)) thì ar as
(mod n) với mọi số nguyên a. Nĩi cách khác, làm việc với các số theo modulo
nguyên tố p thì số mũ cĩ thể giảm theo modulo φ(n).
Định lý 1.2 (Fermat)
Cho p là số nguyên tố.
Nếu gcd(a, p) = 1 thì ap-1 1(mod p).
Nếu r s(mod(p-1)) thì ar as(mod p) với mọi số nguyên a.
a
p
a (mod p) với mọi số nguyên a.
1.3.5 Thặng dƣ
Định nghĩa 1.7
Cho aZn
*
, a đƣợc gọi là thặng dƣ bậc 2 theo modulo n hoặc căn bậc 2 theo
modulo n nếu tồn tại xZn
*
sao cho x
2
a(mod n). Nếu khơng tồn tại x thì a đƣợc
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
gọi là thặng dƣ khơng bậc 2 theo modulo n. Tập hợp các thặng dƣ bậc 2 theo
modulo n ký hiệu là Qn và tập hợp các thặng dƣ khơng bậc 2 theo modulo n ký
hiệu là ___
Q n.
Theo định nghĩa ta cĩ 0 Zn
*
nên 0 Qn và 0 ___Q n .
* Tính chất của thặng dư
Cho n là tích của 2 số nguyên tố p và q. Khi đĩ a Zn
*
là một thặng dƣ bậc 2
theo modulo n khi và chỉ khi a Qn và a ___Q n. Ta cĩ, |Qn| = |Qp|.|Qq| = (p-1)(q-1)/4
và | ___
Q n| = 3(p-1)(q-1)/4
1.3.6 Căn bậc modulo
Định nghĩa 1.8
Cho a Qn . Nếu a Zn
*
thoả mãn x2 a (mod n) thì x đƣợc gọi là căn bậc 2
của a theo modulo n.
* Tính chất (số căn bậc 2)
Nếu p là một số nguyên tố lẻ và a Qn thì a cĩ đúng 2 căn bậc 2 theo modulo p
Tổng quát hơn: cho n = p1
e1
p2
e2…pk
ek
trong đĩ pi là các số nguyên tố lẻ phân
biệt và ei ≥1. Nếu a Qn thì a cĩ đúng 2
k
căn bậc 2 theo modulo n.
1.3.7 Các thuật tốn trong Zn
Cho n là số nguyên dƣơng. Nhƣ đã nĩi ở trƣớc, các phần tử trong Zn đƣợc thể
hiện bởi các số nguyên {0, 1, 2,…, n-1}. Ta thấy rằng: nếu a, b Zn thì:
(a + b) mod n =
a + b nếu a + b <n
a + b – n nếu a + b ≥ n
Vì vậy, phép cộng modulo (phép trừ modulo) cĩ thể đƣợc thực hiện mà khơng
cần thực hiện các phép chia dƣ. Phép nhân modulo của a và b cĩ thể đƣợc thực hiện
bằng phép nhân thơng thƣờng a với b nhƣ các số nguyên bình thƣờng, sau đĩ lấy
phần dƣ của kết quả sau khi chia cho n. Phép tính nghịch đảo trong Zn cĩ thể đƣợc
thực hiện nhờ sử dụng thuật tốn Euclid mở rộng nhƣ mơ tả sau:
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24
* Thuật tốn tính nghịch đảo nhân trong Zn
Bài tốn phát biểu nhƣ sau: Cho a Zn, hãy tìm a
-1
mod n nếu cĩ.
Bƣớc đầu, dùng thuật tốn Euclid mở rộng sau để tìm các số nguyên x và y sao cho:
ax + ny = d với d = gcd(a,n).
Nếu d > 1 thì a-1 mod n khơng tồn tại. Ngƣợc lại, return (x).
* Thuật tốn Euclid mở rộng(N+={1,2,3,…,} là tập các số nguyên dương)
Algorithm Euclid
INPUT: a, b N+ ;
OUTPUT: x, y Z thoả ax + by = gcd(a, b)
Method
x := 0 ; y := 1 ;
u := 1 ; v := 0 ;
q := a div b ; r := a mod b ;
While r ≠ 0 do
a := b; b := r;
t := u ; u := x ; x := t – q * x ;
t := v ; v := y ; y := t – q * y ;
endwhile;
return (x, y) ;
end.
* Thuật tốn bình phương liên tiếp để tính số mũ modulo trong Zn.
Algorithm expmod
INPUT: a Zn , k N
k đƣợc biểu diễn dƣới dạng nhị phân gồm t bit: k = (k1, k2,…, kt)
OUTPUT: a
k
mod n
Method b := 1 ;
For i := 1 to t do
if ki = 1 then
b := (b * a) mod n;
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
25
endif
a := (a * a) mod n;
endfor;
return b;
end.
1.3.8 Thuật tốn kiểm tra tính nguyên tố
Ta thấy rằng, để kiểm tra tính nguyên tố của một số nguyên bằng phƣơng pháp
Monte Carlo (thuật tốn Miller-Rabin, Soloway-Strassen) đều cĩ tốc độ thực hiện
khá nhanh (khoảng O(n2), với n là số bit của số cần kiểm tra). Tuy nhiên, những
thuật tốn này khơng đƣa ra một kết luận chính xác về tính nguyên tố của con số,
mà luơn cĩ một xác suất sai sĩt. Nhƣ vậy để cĩ một sai số cực nhỏ chấp nhận đƣợc,
ta phải thực hiện thuật tốn kiểm tra nhiều lần. Vậy thì, với khoảng bao nhiêu số
nguyên dƣơng ngẫu nhiên (cĩ chiều dài xác định) thì cĩ thể tìm ra đƣợc một số
nguyên tố. Theo lý thuyết thì số các số nguyên tố nhỏ hơn N là: N/ln(N).
Giả sử ta chọn p là số nguyên cĩ chiều dài 512-bits, thì xác suất để số p
nguyên tố là 1/354. Mặt khác, do chúng ta chỉ quan tâm đến những số lẻ, nên xác
suất để p nguyên tố là 2/354 = 1/177. Vậy thì, trung bình khoảng 177 số lẻ ngẫu
nhiên sẽ cĩ 1 số nguyên tố.
Ngƣời ta đã cũng chứng minh đƣợc, thuật tốn Miller-Rabin dùng kiểm tra
tính nguyên tố của một số nguyên dƣơng lẻ với sai số nhiều nhất là 1/4. Nếu thực
hiện thuật tốn này t lần thì sai số nhiều nhất sẽ là 1/4t, để đảm bảo chắc chắn tính
nguyên tố cho số kiểm tra nên chọn số t > 20. Thuật tốn này đƣợc sử dụng trong
quá trình tạo khĩa ở hệ mật mã RSA.
Thuật tốn Miller-Rabin: Kiểm tra tính nguyên tố của một số dạng 2km+1
Input n > 2, n = 2
k
m + 1
Output [True, False] (True: n là số nguyên tố, False: n là hợp số)
1. Giả sử n = 2km + 1; ( với m lẻ)
2. Chọn số ngẫu nhiên a {2,..., n-1};
3. Tính b = am (mod n);
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
26
4. if (b 1 and b (n – 1)) Return True; /* n nguyên tố */
5. i = 1;
6. while (i < k and b (n – 1))
{ b = b
2
(mod n);
if (b = 1) Return False; /* n là hợp số */
i ++;
}
7. if (b! = (n – 1)) Return False; /* n hợp số */
8. Return True; /* n là số nguyên tố */
Thuật tốn: Kiểm tra tính nguyên tố của một số dạng 2km+1 với t lần thực hiện (t >
20)
Input n > 2, n = 2
k
m + 1
Output {True, False} (True: n là số nguyên tố, False: n là hợp số)
1. Giả sử n = 2km + 1;
2. For (j = 1; j t; j++)
{ Chọn số ngẫu nhiên a {2,.....,n-1}
Tính b = am mod n;
if (b = 1) continue; /* quay lại bƣớc 2*/.
i = 1;
while ((i < k) and (b n – 1))
{ b = b
2
mod n;
If (b = 1) Return False; /* n hợp số */
i = i + 1;
}
if (b (n –1)) Return False; /* n hợp số */
}
3. Return True; /* n là số nguyên tố */.
4.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
27
CHƢƠNG 2 - NGHIÊN CỨU CƠ CHẾ HOẠT ĐỘNG CỦA HỆ MẬT KHĨA
CƠNG KHAI
2.1 GIỚI THIỆU VỀ HỆ MẬT VỚI KHĨA CƠNG KHAI
Vào năm 1976, các nhà khoa học Whitfield Diffie, Martin Hellman và Ralph
Merkle tại Đại học Stanford giới thiệu ý tƣởng về hệ thống mật mã khĩa cơng khai,
cĩ thể khắc phục các nhƣợc điểm của phƣơng pháp mật mã khố đối xứng. Các
phƣơng pháp Diffie-Hellman của Martin Hellman và Whitfield Diffie đƣợc cơng
bố. Năm 1977 nhĩm tác giả Ronald Rivest, Adi Shamir và Leonard Adleman đã
cơng bố phƣơng pháp RSA, phƣơng pháp mã hĩa khĩa cơng khai RSA hiện đƣợc sử
dụng rất nhiều trong các ứng dụng mã hĩa và bảo mật thơng tin. RSA nhanh chĩng
trở thành chuẩn mã hĩa khĩa cơng khai trên tồn thế giới do tính an tồn và khả
năng ứng dụng của nĩ.
Độ an tồn của hệ thống mật mã mới này, khơng phải đƣợc đo bằng độ phức
tạp của các thuật tốn mã hĩa, mà nĩ dựa vào một khám phá mới vơ cùng quan
trọng trong ngành khoa học máy tính, đĩ là lý thuyết độ phức tạp tính tốn: Chủ yếu
đề cập đến sự phân tích các thuật tốn và đặc biệt là số các bƣớc tính tốn cần thiết
để phát hiện khĩa bí mật. Từ đĩ xác định độ an tồn của bất kỳ hệ mật mã khĩa
cơng khai nào.
Một hệ thống mật mã khĩa cơng khai sử dụng hai loại khĩa trong cùng một
cặp khĩa: Khố cơng khai (public key) đƣợc cơng bố rộng rãi và sử dụng trong
mã hĩa thơng tin, khĩa riêng (private key) sử dụng để giải mã thơng tin đã đƣợc
mã hĩa bằng khĩa cơng khai. Các phƣơng pháp mã hĩa này 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. Chỉ khi
biết đƣợc khĩa riêng thì mới cĩ thể thực hiện đƣợc ánh xạ f -1.
2.1.1 Các quan điểm cơ bản của hệ mật mã khố cơng khai
- Hệ mật mã khố cơng khai dựa trên quan điểm hàm một chiều (one-way
function) và khố cơng khai, để biến đổi một bản rõ thành bản mã với thời gian tính
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
28
tốn hợp lý. Nhƣng nếu muốn tính ngƣợc lại (inverse function) thì phải mất nhiều
thời gian và khĩ thực hiện đƣợc. Vì vậy, các thám mã rất khĩ cĩ thể tính tốn để thu
đƣợc bản rõ từ bản mã chặn đƣợc.
- Một quan điểm khác dùng trong hệ mật mã khố cơng khai, là thơng tin “cửa
sập” (trap door) mà hàm một chiều phải cĩ. Thơng tin bí mật (khố riêng) chỉ đƣợc
đƣa vào bởi ngƣời sở hữu cặp khĩa. Khi cĩ đƣợc thơng tin “cửa sập” thì cơng việc
giải mã sẽ trở nên dễ dàng.
- Các hệ mật mã khĩa cơng khai đƣợc xây dựng dựa trên những bài tốn khĩ
nhƣ: bài tốn logarithm rời rạc trong trƣờng hữu hạn Zp (hệ ElGamal) và bài tốn
phân tích một số nguyên lớn ra các thừa số nguyên tố (hệ RSA).
2.1.2 Hoạt động của hệ mật mã khĩa cơng khai
Đối với hệ thống mã hĩa khĩa cơng khai: Mỗi ngƣời sử dụng phải tạo riêng
cho mình một cặp khĩa. Trong đĩ, một khĩa cơng khai (public key) cùng với thuật
tốn mã hĩa E, đƣợc cơng bố rộng rãi tại thƣ mục dùng chung cho mọi ngƣời sử
dụng. Cịn lại là khĩa riêng (private key) cùng với thuật tốn giải mã D đƣợc giữ bí
mật bởi ngƣời sử dụng.
Nhƣ vậy, ngƣời A muốn gửi thơng điệp R đến cho ngƣời B (Hình 2.1).
Giả sử: Khĩa cơng khai của B là: KB , Khĩa riêng của B là: MB
Khĩa cơng khai của A là: KA , Khĩa riêng của A là: MA
Thuật tốn mã hĩa: E , thuật tốn giải mã: D
Ngƣời A tìm khĩa cơng khai KB của ngƣời B trong thƣ mục dùng chung và
tính C = E(KB, R), sau đĩ gửi bản mã C cho ngƣời B. Khi nhận bản mã C ngƣời B
sẽ giải mã dựa vào khĩa riêng MB của mình để tính R = D(MB, C).
2.1.3 Các mơ hình ứng dụng của hệ mật mã khĩa cơng khai.
Thơng qua từng lĩnh vực ứng dụng cụ thể mà ngƣời gửi sử dụng khĩa bí mật
của mình, khĩa cơng khai của ngƣời nhận hoặc cả hai để hình thành một số các ứng
dụng phù hợp nhƣ sau:
- Tính mật: Ngƣời gửi A thực hiện mã hĩa thơng điệp R bằng khĩa cơng khai
KB của ngƣời nhận B: C = E(KB,R). Cịn ngƣời nhận giải mã bằng khĩa riêng MB
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
29
của mình: R = D(MB, C). Vậy, cĩ duy nhất ngƣời B mới giải mã đƣợc thơng điệp,
điều này gọi là tính mật của hệ.
- Tính xác thực: Ngƣời gửi A thực hiện mã hĩa một thơng điệp R bằng khĩa
riêng MA: C = E(MA,R). Ngƣời nhận B giải mã bằng khĩa cơng khai KA của ngƣời
gửi A: R = D(KA,C). Nhƣ vậy chỉ cĩ duy nhất A là ngƣời cĩ khĩa riêng để mã hĩa,
cho nên thơng điệp nhận đƣợc là của A, điều này gọi là tính xác thực của hệ.
- Tính mật và xác thực: Ngƣời gửi A thực hiện mã hố thơng điệp hai lần, lần
thứ nhất sử dụng khĩa bí mật MA của mình E(MA,R), lần thứ hai sử dụng khĩa cơng
khai KB của ngƣời nhận B: C = E(KB,(E(MA,R))). Khi nhận bản mã, ngƣời nhận B
cũng thực hiện giải mã hai lần, đầu tiên dùng khĩa riêng MB của mình D(MB,C), sau
đĩ dùng khĩa cơng khai KA của ngƣời gửi A: R = D(KA,D(MB,C)). Nhƣ vậy chỉ
ngƣời gửi mới cĩ khĩa riêng để mã hố và cũng chỉ ngƣời nhận mới cĩ khĩa riêng
để giải mã, đây chính là tính mật và tính xác thực của hệ.
2.1.4 Các yêu cầu của hệ mật mã khĩa cơng khai
- Dễ tính tốn đối với các thành viên khi muốn tạo một cặp khĩa (khĩa cơng
khai và khĩa riêng).
- Ngƣời gửi dễ tính tốn khi biết khĩa cơng khai và thơng điệp R cần mã hố
thành một bản mã tƣơng ứng C = E(KB,R).
- Ngƣời nhận dễ tính tốn khi sử dụng khĩa riêng để giải mã bản mã C, khơi
phục lại thơng điệp ban đầu: R = D(MB, C).
- Đối với ngƣời thám mã, khi biết đƣợc khĩa cơng khai KB, muốn xác định
khĩa bí mật MB hoặc biết đƣợc khĩa cơng khai KB và bản mã C để khơi phục lại
thơng điệp R ban đầu: Điều này khơng thể tính tốn nổi.
2.2 HỆ MẬT MÃ KHĨA CƠNG KHAI RSA
Hệ mật RSA đƣợc xây dựng năm 1978 bởi ba tác giả R.L.Rivest, A.Shamir và
L.Adleman. Hệ mật RSA đƣợc thiết kế làm việc trên trƣờng số ZN, dựa trên cơ sở
độ khĩ giải của bài tốn phân tích số nguyên N lớn thành các thừa số nguyên tố p và
q khác nhau.
2.2.1 Bài tốn phân tích số nguyên
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
30
Bài tốn 2.1 (Bài tốn phân tích số nguyên):
Cho một số nguyên dƣơng N, tìm các thừa số nguyên tố pi của N để N = p1
e1
.
p2
e2
...pk
ek
, với pi là những số nguyên tố phân biệt và ei 1 là các số nguyên (với i =
1,..., k).
Ví dụ : Với N=12, ta cĩ N=22.3
1
Bài tốn này khĩ giải khi N là một số nguyên lớn, cĩ nhiều thuật tốn để giải bài
tốn này. Nhƣng hiện nay vẫn chƣa cĩ thuật tốn nào hiệu quả để phân tích số
nguyên N cĩ khoảng 232 chữ số thập phân (768-bits) trở lên.
Bài tốn 2.2 (Bài tốn RSA):
Cho số nguyên dƣơng N, N=p*q với p và q là các số nguyên tố phân biệt,
số nguyên e sao cho thỏa mãn gcd(e, (p – 1) * (q – 1)) = 1, và số nguyên c. Tìm một
số nguyên m sao cho me c (mod N).
Bài tốn RSA cũng cĩ độ khĩ tƣơng tự nhƣ bài tốn phân tích số nguyên,
nhƣng nĩ dễ dàng đƣợc giải nếu nhƣ biết đƣợc hai số nguyên tố p và q.
2.2.2 Định nghĩa các tập làm việc của hệ RSA
Tập các bản rõ (plaintext): P = ZN = {0, 1,…, N-1}.
Tập các bản mã (ciphertext): C = ZN = {0, 1,…, N-1}.
Tập các khĩa: K = {(n, p, q, e, d): N = p * q, e * d 1(mod φ(N))}
2.2.3 Quá trình tạo khố, mã hố và giải mã
a) Tạo khĩa:
Tạo hai số nguyên tố phân biệt p và q lớn, sao cho bài tốn phân tích thật sự
là khĩ giải (kích cỡ mỗi số khoảng 512 bits 1024 bits).
Tính N = p* q và φ(N) = (p – 1) * (q – 1).
Chọn một số nguyên ngẫu nhiên e sao cho 1 < e < φ(N) và gcd(e, φ(N)) = 1
Sử dụng thuật tốn Euclid mở rộng, để tính số nguyên d duy nhất, sao cho 0
< d < φ(N) và e * d 1 mod φ(N) (d là nghịch đảo của e modulo N)
Hai số (e, N) làm khĩa cơng khai, cịn (d, N) đƣợc giữ bí mật làm khĩa riêng.
Các số nguyên tố p, q sẽ bị xĩa khi kết thúc quá trình tạo khĩa.
b) Mã hĩa:
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
31
Giả sử để gửi thơng điệp M cho ngƣời B. Ngƣời A thực hiện nhƣ sau:
Lấy khĩa cơng khai của ngƣời nhận B: (e, N).
Biến đổi thơng điệp M thành những số nguyên Mi tƣơng ứng sao cho Mi <
N, (i = 1,…, k). Theo phép biến đổi sau:
- Biến đổi các ký tự trong thơng điệp M thành các số nguyên tƣơng ứng, thí dụ
theo qui tắc: Dấu cách 00, A 01, B 02,..., Z 26.
- Chia thơng điệp vừa biến đổi thành k nhĩm cĩ chiều dài bằng nhau, mỗi
nhĩm biểu diễn một số nguyên Mi {0,…, N – 1} (với 1 ≤ i ≤ k).
Thực hiện mã hĩa lần lƣợt cho từng số Mi Ci bằng cách:
Ci = Eke(Mi) = Mi
e
(mod N).
Tập các số nguyên {C1, C2,...,Ck} là bản mã để gửi đến ngƣời nhận B.
c) Giải mã:
Ngƣời nhận B thực hiện các bƣớc sau:
Thực hiện giải mã lần lƣợt từng số nguyên Ci Mi bằng cách:
Mi = D(Ci) = Ci
d
(mod N) với 0 ≤ Mi < N, (d là khố bí mật của B).
Thực hiện phép biến đổi ngƣợc lại từ các số Mi thành các chuỗi ký tự tƣơng
ứng để khơi phục lại nội dung thơng điệp M ban đầu.
Bảng 2.2: Tĩm tắt các bước tạo khố, mã hố, giải mã của Hệ RSA
Tạo khố: Tạo 2 số nguyên tố lớn p và q
* Tính N = p * q và Tính φ(N) = (p-1) * (q-1).
* Chọn 1< e < φ(N): gcd(φ(N), e) = 1.
* Tính d = e-1 mod φ(N) (dùng thuật tốn Euclid mở rộng).
Khĩa cơng khai: (e, N) Khĩa riêng: (d, N)
Mã hĩa: Khối bản rõ M < N
* Tính: C = Me mod N
* Gửi khối bản mã (số nguyên) C đến ngƣời nhận
Giải mã: Khối bản mã C < N
* Tính: M = Cd mod N
* Khơi phục lại khối bản rõ (số nguyên) M ban đầu
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
32
2.3.4 Tính đúng của quá trình giải mã
Từ: ed 1mod φ(N) φ(N) | (ed – 1).
φ(pq)| (ed – 1)
φ(p) * φ(q) | (ed – 1) (do p, q là các số nguyên tố)
φ(p) | (ed – 1) (1)
và φ(q) | (ed – 1) (2)
Từ (1) k Z: ed -1= k φ(p) = k (p-1) (p là số nguyên tố) (3)
Xét trƣờng hợp tổng quát với mọi số M Zn , khi nâng lũy thừa ed ta cĩ:
M
ed
M(ed –1) + 1 (mod p)
ed (M(ed-1)) * M (mod p) (4)
Từ (3) & (4) ed (Mk(p - 1)) * M (mod p) (5)
Vì p là số nguyên tố, vậy bất kỳ số M ZN cĩ hai trƣờng hợp: M nguyên tố cùng
nhau với p (nghĩa là gcd(M, p) = 1) hoặc M là bội số của p (nghĩa là gcd(M, p) = p).
Trường hợp 1: gcd (M, p) = 1
Vậy M p-1 1 (mod p) (định lý Fermat)
Từ: (5) Med (1)k M (mod p)
Med M (mod p) (6)
Trường hợp 2: Nếu gcd(M, p) = p M 0 (mod p). Đồng thời lũy thừa số
M lên một số nguyên bất kỳ, thì cũng chia hết cho p. Nghĩa là Med 0 (mod p ).
Vậy trƣờng hợp 2 cũng thỏa mãn phƣơng trình (6)
Với cách tính tƣơng tự với q, từ (2) Med M (mod q) (7)
Từ (6) & (7) Med M (mod pq) M (mod N).
Ví dụ 2.1 : Minh họa của hệ mật mã RSA
a) Tạo khĩa:
Chọn p và q là những số nguyên tố nhỏ với mục đích minh họa
Chọn hai số nguyên tố p = 41, q = 67;
Tính N = 47 * 61 = 2747 và φ(N) = (41- 1) * (67-1) = 2600 ;
Chọn e = 59 thỏa mãn gcd(e, φ(N)) = gcd(2600, 59) = 1;
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
33
Tìm phần tử nghịch đảo d = 179 (dùng thuật tốn Euclid mở rộng) ;
Cơng bố khĩa cơng khai là cặp số ( e = 49, N = 2747), cịn số d = 179 đƣợc
giữ làm khĩa riêng.
b) Mã hĩa: Giả sử nội dung cần mã hố là M = “MA HOA CONG KHAI ”
Biến đổi các ký tự của thơng điệp thành các số tƣơng ứng nhƣ sau:
M A H O A C O N G K H A I
13 01 00 08 15 01 00 03 15 14 07 00 11 08 01 09
Chia thơng điệp thành 8 khối, mỗi khối gồm 4 chữ số biểu diễn một số
nguyên Mi < N, với Mi {1301;0008;1501;0003;1514;0700;1108;0109}.
Mã hĩa lần lƣợt từng số Mi : Ci = Mi
59
( mod 2747) (8)
Mã hĩa số đầu tiên M1 = 1301 theo cách tính (8) ta cĩ:
C1 = M1
59
mod 2747 130159 mod 2747 = 2352.
Tiếp tục tính các số C2 ,...,C8 từ các số M2 ,..., M8 theo (8). Ta cĩ đƣợc kết quả ở
cột Ci là bản mã để gửi đến ngƣời nhận:
Khối 1 2 3 4 5 6 7 8
Mi 1301 0008 1501 0003 1514 0700 1108 0109
Ci=E(Mi) 2352 2537 1745 2733 1203 2651 0534 0454
c) Giải mã:
Thực hiện giải mã lần lƣợt từng số ở cột Ci (1≤ i ≤ 8)
Mi = Dkd(Ci) Ci
179
( mod 2747) (9)
Giải mã số đầu tiên C1 = 2352 theo cách tính (2.9) ta cĩ:
M1 = C1
179
mod 2747 = 2352
179
mod 2747 = 1301
Tiếp tục tính các số M2,..., M8 từ các số C2,...,C8 theo (9) ta cĩ bảng minh họa
các số Mi đƣợc giải mã từ các số Ci nhƣ sau:
Khối 1 2 3 4 5 6 7 8
Ci=E(Mi) 2352 2537 1745 2733 1203 2651 0534 0454
Mi 1301 0008 1501 0003 1514 0700 1108 0109
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
34
Thực hiện phép biến đổi ngƣợc từ các số Mi thành các chuỗi ký tự tƣơng ứng
để khơi phục lại thơng điệp gốc ban đầu M = "MA HOA CONG KHAI".
2.2.4 Chi phí thực hiện trong quá trình mã hĩa và giải mã
Chi phí cho quá trình mã hố:
Tính C = Me mod N, với số mũ e thƣờng đƣợc chọn cĩ dạng e = 2x + 1
(với xmax = 16) để phép tính lũy thừa modulo đƣợc thực hiện nhanh. Vì biểu diễn
nhị phân của những số dạng này chỉ cĩ hai bít giá trị 1 ở đầu và cuối. Nhƣ vậy quá
trình mã hĩa cĩ nhiều nhất là 16 phép tính bình phƣơng và 1 phép nhân, do đĩ tổng
chi phí của quá trình mã hĩa là: 17(2n2 + 2n) = 34(n2+n).
Chi phí cho quá trình giải mã:
Quá trình giải mã của hệ RSA, chỉ thực hiện phép tính M = Cd mod N, với
số mũ bí mật d thƣờng rất lớn (d N) để đảm bảo độ an tồn cho dữ liệu. Vì vậy chi
phí thực hiện giải mã của hệ RSA tƣơng đƣơng với chi phí để thực hiện phép tính
lũy thừa nhanh là: 3n3 + n2.
2.2.5 Đánh giá hệ mật mã khĩa cơng khai RSA
2.2.5.1 Độ an tồn
Hệ RSA đƣợc thiết kế dựa trên độ khĩ giải bài tốn phân tích ra thừa số
nguyên tố. Hầu hết các phƣơng pháp thám mã hệ RSA nhƣ tìm các thừa số p và q,
tìm φ(n), hay tìm khĩa riêng d… đều khĩ nhƣ bài tốn phân tích.
Sau đây, ta cĩ bảng chi phí thời gian cần thiết để phân tích những hệ mật mã
RSA cĩ kích cỡ số modulo N khác nhau, bằng những thuật tốn phân tích tốt nhất
hiện nay (Bảng 2.3). Ở đây chi phí tính tốn đƣợc tính bằng đơn vị MIPS-Years (đĩ
là số các phép tính đã hồn thành bởi một máy trong thời gian một năm, với tốc độ
khoảng 106 phép tính trên một giây, ta cĩ 1MIPS-Years 245 phép tính).
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
35
Bảng 2.3: Bảng chi phí thời gian cần thiết để phân tích các số nguyên N
Hệ RSA
Số chữ số
thập phân
Số
bits
Thuật
tốn
Năm
Chi phí
phân tích
(MIPS-Years)
RSA-129 129
426 MPQS 1994
5.000
RSA-130 130
430 GNFS 1996
1.000
RSA-140 140
465 GNFS 1999
2.000
RSA-155 155
512 GNFS 1999
8.000
RSA-576 174 576 GNFS 2003
13.000
Vào ngày 22/8/1999 một nhĩm các nhà nghiên cứu đã hồn thành việc phân
tích số N dùng trong hệ RSA-155 cĩ 155 chữ số thập phân (512-bits) bằng thuật
tốn General Number Field Sieve (GNFS). Sau một thời gian 7 tháng trên mạng
máy tính cĩ 300 workstation yêu cầu khoảng 8000 MIPS-Years.
Việc phân tích số nguyên N thành các thừa số nguyên tố p, q nhằm mục đích
bẻ gãy hệ mật mã RSA là điều khĩ cĩ thể tính tốn nổi, nếu nhƣ trong quá trình
thiết kế hệ RSA ta chọn số nguyên N lớn. Tuy nhiên, độ dài của số nguyên N là lớn
hay nhỏ cịn phụ thuộc vào mối liên hệ giữa tốc độ giải mã và độ an tồn của hệ
RSA. Số N sử dụng cho modulo RSA hiện nay phải cĩ ít nhất khoảng 232 chữ số
thập phân (768-bits) sẽ cho ta một độ an tồn đủ để chống lại những tấn cơng sử
dụng các kỹ thuật phân tích hiện nay. Trong thực tế, nếu trong quá trình thiết kế sử
dụng số N cĩ kích cỡ khoảng 1024-bits là rất an tồn, cĩ thể chống lại các kỹ thuật
phân tích hiện tại và các kỹ thuật khác phát triển trong tƣơng lai.
2.2.5.2 Hiệu suất thực hiện và ứng dụng
Tốc độ thực hiện của hệ RSA là một trong những điểm yếu so với các hệ mật
mã khĩa đối xứng. Vì các quá trình mã hĩa và giải mã của hệ RSA đều thực hiện
các phép tính cĩ các tốn hạng là những số nguyên cực lớn ( thơng thƣờng các phép
tốn này đều đƣợc xây dựng hay ”giả lập” lại).
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
36
Theo ƣớc tính, thực hiện mã hĩa và giải mã bằng hệ mật mã RSA chậm hơn
100 lần so với hệ mật mã khĩa đối xứng DES (bằng phần mềm). Và chậm hơn 1000
lần so với DES (bằng phần cứng). Vì lý do đĩ mà trên thực tế hệ mã khố cơng khai
RSA ít đƣợc dùng vào mục đích mã hĩa cho khối lƣợng dữ liệu lớn, mà chỉ thƣờng
đƣợc ứng dụng để mã hĩa khối dữ liệu nhỏ. Nhƣ vậy để khắc phục một phần nào đĩ
cho cơng việc mã hĩa và giải mã bằng hệ mật mã RSA đƣợc nhanh hơn thì chúng ta
nghiên cứu thêm hệ mật mã RSA WITH CRT nhƣ sau :
2.3 HỆ MẬT MÃ RSA WITH CRT
Ta thấy rằng, quá trình giải mã của hệ mật mã RSA cĩ độ phức tạp (M = Cd
mod N) phụ thuộc trực tiếp vào kích cỡ của các số nguyên d và N. Để cĩ thể giảm
đƣợc kích cỡ của hai số nguyên d và N và tăng tốc độ giải mã, chúng ta dựa vào
định lý đồng dƣ Trung hoa (CRT-Chinese Remainder Theorem) sau:
2.3.1 Định lý đồng dƣ Trung Hoa
Định lý đồng dƣ Trung Hoa (CRT) cho phép giảm số lần tính tốn của quá
trình giải mã ở hệ RSA, bằng cách thiết lập một ánh xạ giữa tập Z N và tích Đề-các
k
1i
niZ
, với N =
k
1i
in
và các số ni (1 i k) nguyên tố cùng nhau. Cho phép thực
hiện các phép tính lũy thừa modulo trên các trƣờng số Zni nhỏ hơn, thay vì phải tính
trực tiếp trên trƣờng số Z N lớn nhƣ cách tính trong hệ RSA chuẩn.
Định lý 2.2:(định lý đồng dƣ Trung Hoa)
Giả sử p1, p2,...., pk là các số nguyên dƣơng nguyên tố cùng nhau từng đơi
một (gcd(pi, pj) = 1, khi i j) và cho x1, x2,..., xk là các số nguyên. Khi đĩ hệ
phƣơng trình đồng dƣ sau đây:
x x1 (mod p1)
x x2 (mod p2)
x xk (mod pk)
cĩ duy nhất một nghiệm x ZN, N = p1.p2....pk đƣợc xác định nhƣ sau:
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
37
x =
k
1i
iii Nscx mod
(10)
Trong đĩ:
i
i
p
N
c
và
)p (mod i
1
ii cs
, i = 1, 2,…, k
Vậy, theo định lý đồng dƣ Trung Hoa, với bất kỳ số nguyên dƣơng x < N đều
cĩ thể biểu diễn dƣới dạng một bộ gồm k phần tử duy nhất [x1, x2,…, xk] và ngƣợc
lại, ở đây các xi là số dƣ của phép tính x mod pi (i = 1, 2…, k). Sự chuyển đổi số
nguyên x thành các số dƣ đƣợc thực hiện bởi phép rút gọn xi = x mod pi. Cịn sự
chuyển ngƣợc lại khĩ hơn, địi hỏi tính tốn liên quan đến cơng thức (10).
Hệ quả 2.1: Nếu số nguyên x khơng chia hết cho p, và n m mod (p – 1) thì xn
x
m
mod p.
Từ hệ quả trên, khi thực hiện phép tốn lũy thừa với modulo là một số
nguyên tố p thì số mũ cĩ thể đƣợc rút gọn mod (p – 1). Điều này cho phép thực hiện
quá trình giải mã của hệ RSA nhanh hơn, vì các số mũ cĩ kích cỡ nhỏ hơn.
Thuật tốn 2.1: Định lý đồng dư Trung Hoa tổng quát
Input [x1, x2,...., xk], [p1, p2,...., pk]
Output x (với x mod pi = xi với i =1, 2,..., k)
1. x = 0; N = p1;
2. For (i = 2; i k; i++) {N = N * pi;} /* N là tích các số pi */
3. For (i = 1; i k; i++) /* tính nghiệm x */
{ ci = (N/pi);
si = ci
-1
mod pi;
x = (x + si * ci * xi) mod N;
}
4. Return x;
Trƣờng hợp đặc biệt của định lý đồng dƣ Trung Hoa đƣợc áp dụng cho quá
trình giải mã ở hệ RSA, khi modulo N là tích của hai số nguyên tố p và q (N = p *
q). Do đĩ, mọi số nguyên M < N đều biểu diễn duy nhất qua một bộ gồm hai số
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
38
[Mp, Mq], thỏa mãn Mp = M mod p và Mq = M mod q. Cho nên ta cĩ thể giải mã
thơng điệp, bằng cách tính trƣớc hai số Mp và Mq rồi kết hợp chúng với cơng thức
(10). Trong đĩ Mp, Mq đƣợc tính nhờ vào hệ quả (2.1) nhƣ sau:
Mp = M mod p = (C
d
mod N) mod p = C
d
mod p (vì N = p * q)
= C
d mod p – 1
mod p = C
dp
mod p (với dp = d mod (p – 1).
Hơn nữa, dễ dàng thấy rằng bản mã C cũng cĩ thể rút gọn bởi mod p, trƣớc
khi tính Mp, Mq. Nhƣ vậy, kích cỡ các tốn hạng Cp = C mod p, Cq = C mod q, và dp
= d mod (p – 1), dq = d mod (q – 1), đều giảm đi một nữa. Vậy, ta cĩ cách tính Mp =
Cp
dp
mod p và Mq = Cq
dq
mod q.
Thuật tốn 2.2: Định lý đồng dư Trung Hoa với modulo N = p* q
Input Mp, Mq, p, q, N
Output M (sao cho M = Mp mod p và M = Mq mod q)
1. y = q-1 mod p;
2. M = y * q * Mp mod N;
3. y = p-1 mod q;
4. M = (M + y * p * Mq) mod N;
5. Return M;
2.3.2 Thuật tốn Garner
Thuật tốn Garner là một cải tiến hơn nữa về tốc độ giải mã so với thuật tốn
CRT vừa xét. Ở đây các bƣớc tính phần tử nghịch đảo đã bị loại bỏ, thuật tốn này
cũng tìm số nguyên M từ các số Mp = M mod p và Mq = M mod q. Ngồi ra thuật
tốn cịn cĩ tham số đầu vào: p’ = p-1 mod q đƣợc tính tốn trƣớc.
Thuật tốn 2.3: Thuật tốn Garner
Input Mp, Mq, p, q, (p’ = p
-1
mod q), N
Output M
1. V = (Mq – Mp) mod q;
2. V = V * p’ mod q;
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
39
3. M = V * p mod N;
4. M = M + Mp mod N;
5. Return M;
Phân tích chi phí thực hiện thuật tốn
Giả sử số N cĩ kích cỡ n-bits, và các số nguyên tố p, q cĩ kích cỡ n/2-bits.
Thuật tốn thực hiện một phép nhân của các số nguyên cĩ kích cỡ n/2-bits để tính V
tại (bƣớc 2) với chi phí 2(n/2)2+2(n/2) n2/2 + o(n2), và một phép nhân của số
nguyên cĩ kích cỡ n-bits để tính M ở (bƣớc 3) với chi phí 2n2 +2n 2n2 + o(n2).
Vậy chi phí của thuật tốn là: 5n2/2 + o(n2).
Ví dụ 2.3: Minh họa các bước thực hiện thuật tốn Garner
Cho hai số nguyên tố p = 47 và q = 61, các số dƣ Mp = 49 và Mq = 34, sử dụng
thuật tốn Garner, hãy tìm số nguyên M từ các số Mp và Mq.
Tính trƣớc: N = p * q = 2747 và p’ = p
-1
mod q = 47
-1
mod 61 = 13
b1: V = (Mq – Mp) mod q = (34 – 12) mod 61
= -12 mod 61 = 49 (vì 12+49 0 mod 61)
b2: V = V * p’ mod q = 49 *13 mod 61 = 27
b3: M = V * p mod N = 27 * 47 mod 2747 = 1269
b4: M = M + Mp mod N =1269 + 46 mod 2747 = 1315
2.3.3 Các quá trình tạo khố, mã hố và giải mã
Hệ mật mã RSA With CRT cĩ tốc độ thực hiện quá trình giải mã nhanh
hơn hệ RSA chuẩn rất nhiều. Trong phần này chỉ trình bày các bƣớc tính tốn thêm
vào cho quá trình tạo khĩa và quá trình giải mã nhờ vào định lý đồng dƣ Trung
Hoa, cịn quá trình mã hĩa thì hồn tồn giống với hệ RSA chuẩn.
2.3.3.1 Mơ tả các quá trình tạo khố và giải mã
a) Tạo khố:
Quá trình tạo khĩa cũng giống nhƣ hệ RSA chuẩn, nhƣng thêm các bƣớc sau:
- Tính dp = d mod (p – 1) và dq = d mod (q – 1).
- Tính phần tử nghịch đảo của p modulo q là: p’ = p-1 mod q.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
40
- Chọn (e, N) làm khố cơng khai, cịn (p, q, dp, dq, p’) làm khố riêng.
b) Giải Mã:
- Tính các số Mp= Cp
dp
mod p và Mq= Cq
dq
mod q với:
Cp = C mod p; Cq = C mod q
- Giải mã C để tìm M từ các số Mp và Mq nhờ vào thuật tốn Garner.
Thuật tốn 2.4
Input C, N, dp, dq, p, q, p’ = p
-1
mod q
Output M
1. Cp = C mod p;
2. Cq = C mod q;
3. Mp = Cp
dp
mod p;
4. Mq = Cq
dq
M mod q;
5. M = Garner(Mp, Mq, p, q, p’, N);
6. Return M;
2.3.3.2 Phân tích chi phí thuật tốn giải mã RSA_CRT
Giả sử số N sử dụng cho modulo RSA cĩ kích cỡ n-bits, và các số nguyên tố
p, q cĩ kích cỡ n/2-bits. Thuật tốn RSA_CRT thực hiện hai phép tính rút gọn
modulo tại (b1) và (b2) với số nguyên cĩ kích cỡ n-bits, và modulo cĩ kích cỡ n/2-
bits. Chi phí mỗi bƣớc là n2/2, tại (b3) và (b4) thực hiện hai phép tính lũy thừa
modulo với số nguyên cĩ kích cỡ n/2-bits, với mỗi bƣớc cĩ chi phí 3n3/8 + n2/4. Tại
(b5) thực hiện thuật tốn Garner để tìm M từ hai số Mp và Mq với chi phí đã tính là
5n
2/2. Vậy tổng chi phí của thuật tốn giải mã là: 3n3/4 + 7n2/2 + o(n2).
2.4 PHÂN TÍCH CƠ CHẾ HOẠT ĐỘNG CỦA HỆ MÃ RSA
2.4.1 Phân tích quá trình tạo khĩa:
Tạo hai số nguyên tố phân biệt p và q lớn, sao cho bài tốn phân tích thật sự
là khĩ giải
Tính N = p* q và φ(N) = (p – 1) * (q – 1).
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
41
Chọn một số nguyên ngẫu nhiên e sao cho 1 < e < φ(N) và gcd(e, φ(N)) = 1
Sử dụng thuật tốn Euclid mở rộng, để tính số nguyên d duy nhất, sao cho 0
< d < φ(N) và e * d 1 mod φ(N) (d là nghịch đảo của e modulo N)
Hai số (e, N) làm khĩa cơng khai, cịn (d, N) đƣợc giữ bí mật làm khĩa riêng.
Các số nguyên tố p, q sẽ bị xĩa khi kết thúc quá trình tạo khĩa.
Nhƣ vậy, mấu chốt để tăng tính an tồn của hệ mã RSA là ta cần thực hiện
đƣợc quá trình mã hĩa xuất phát từ các số nguyên tố p, q lớn.
2.4.2 Phân tích quá trình mã hĩa:
Giả sử để gửi thơng điệp M cho ngƣời B. Ngƣời A thực hiện nhƣ sau:
Lấy khĩa cơng khai của ngƣời nhận B: (e, N).
Biến đổi thơng điệp M thành những số nguyên Mi tƣơng ứng sao cho Mi <
N, (i = 1,…, k). Theo phép biến đổi sau:
- Biến đổi các ký tự trong thơng điệp M thành các số nguyên tƣơng ứng, thí dụ
theo qui tắc: Dấu cách 00, A 01, B 02,..., Z 26.
- Chia thơng điệp vừa biến đổi thành k nhĩm cĩ chiều dài bằng nhau, mỗi
nhĩm biểu diễn một số nguyên Mi {0,…, N – 1} (với 1 ≤ i ≤ k).
Thực hiện mã hĩa lần lƣợt cho từng số Mi Ci bằng cách:
Ci = Eke(Mi) = Mi
e
(mod N).
Tập các số nguyên {C1, C2,...,Ck} là bản mã để gửi đến ngƣời nhận B.
Ta thấy rằng quá trình mã hĩa phải thực hiện liên tiếp việc mã hĩa các số Mi
theo cơng thức: Ci = Eke(Mi) = Mi
e
(mod N).
Khi p và q lớn thì ta cĩ N = p*q rất lớn.
Trên lý thuyết, số e cĩ thể chọn chỉ cần thỏa mãn gcd(e, φ(N)) = 1, tuy nhiên
để tăng tính an tồn, số e thƣờng đƣợc sẽ là số lớn hơn Max(p,q) với Max(p,q) trả
về số lớn nhất giữa p và q.
Do đĩ, quá trình mã hĩa sẽ thực hiện với các số rất lớn nhƣng vẫn phải đảm
bảo thời gian thực hiện việc mã hĩa là đủ tốt.
Xuất phát từ các lí do trên, ta cần tác động vào quá trình mã hĩa bằng các thuật
tốn tốt để cĩ thể thỏa mãn các yêu cầu trên.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
42
2.4.3 Phân tích quá trình giải mã:
Ngƣời nhận B thực hiện các bƣớc sau:
Thực hiện giải mã lần lƣợt từng số nguyên Ci Mi bằng cách:
Mi = D(Ci) = Ci
d
(mod N) với 0 ≤ Mi < N, (d là khố bí mật của B).
Thực hiện phép biến đổi ngƣợc lại từ các số Mi thành các chuỗi ký tự tƣơng
ứng để khơi phục lại nội dung thơng điệp M ban đầu.
Quá trình giải mã cũng phải thực hiện việc tính tốn liên tiếp để tìm Mi theo
cơng thức: Mi = D(Ci) = Ci
d
(mod N), quá trình này cũng thực hiện trên các số lớn
vì ta cĩ d là số lớn. Do đĩ, quá trình giải mã cũng cần cĩ các tác động để đảm bảo
thời gian giải mã là chấp nhận đƣợc. Điều này cĩ ý nghĩa rất quan trọng vì hệ mã
RSA cĩ số lƣợng phép tính lớn, bên cạnh đĩ để cĩ thể thực hiện với các bản rõ cĩ
nội dung lớn thì ta phải giải quyết đƣợc vấn đề này.
Kết luận:
Trong thực tế, tốc độ mã hĩa và giải mã của RSA là rất chậm so với các hệ mã
khác. Điều này dẫn đến việc RSA chủ yếu đƣợc dùng để mã hĩa khĩa bí mật hoặc
các các bản rõ ngắn. Phần nội dung chính cần gửi sẽ đƣợc mã hĩa bằng một phƣơng
pháp mã hĩa khác cĩ tốc độ thực hiện nhanh hơn (Phƣơng pháp này thƣờng kém an
tồn hơn so với RSA). Ngƣời nhận sẽ giải mã bằng RSA để lấy khĩa bí mật rồi mới
tiến hành giải mã nội dung cần nhận.
Điều này đã dẫn đến những bất cập về ứng dụng RSA rộng rãi trong thực tế.
Giải quyết đƣợc mâu thuẫn giữa việc tăng tính an tồn và tăng thời gian thực hiện
mã hĩa là vấn đề cần đƣợc nghiên cứu để giải quyết.
2.5 KHẢ NĂNG BỊ BẺ KHĨA CỦA HỆ MÃ CƠNG KHAI RSA
2.5.1 Một số phƣơng pháp tấn cơng hệ mã RSA.
Bất cứ ai cũng cĩ thể tạo ra một hệ thống thơng tin mã hĩa cho riêng mình.
Nhƣng để cĩ một hệ thống an tồn và hiệu quả địi hỏi ngƣời thiết kế phải cĩ kiến
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
43
thức tốn học sâu sắc, cĩ kinh nghiệm về bảo mật và am hiểu các phƣơng pháp tấn
cơng.
• Brute-force attack: phƣơng pháp tấn cơng bằng cách thử tất cả những chìa
khĩa cĩ thể cĩ. Đây là phƣơng pháp tấn cơng thơ sơ nhất và cũng khĩ khăn nhất.
Theo lý thuyết, tất cả các thuật tốn mã hĩa hiện đại đều cĩ thể bị đánh bại bởi
brute-force nhƣng trong thực tiễn việc này chỉ cĩ thể thực hiện đƣợc trong thời gian
hàng triệu, thậm chí hàng tỉ năm. Vì thế cĩ thể coi một thuật tốn mã hĩa là an tồn
nếu nhƣ khơng cịn cách nào khác để tấn cơng nĩ dễ hơn là brute-force.
• Frequency analysis: thống kê tần suất, chỉ cĩ thể áp dụng đƣợc đối với các
thuật tốn cổ điển dùng phƣơng pháp thay thế, ví dụ phƣơng pháp Caesar. Để thực
hiện phƣơng pháp này ta cần một lƣợng văn bản đã mã hĩa đủ lớn để phép thống kê
đƣợc chính xác. Ngồi ra cịn phải biết ngơn ngữ sử dụng trong văn bản ban đầu,
nếu văn bản ban đầu là tiếng Anh thì nhiều khả năng kí tự xuất hiện nhiều nhất
trong văn bản đã mã hĩa là do chữ e mã hĩa thành.
• Differential cryptanalysis: Phƣơng pháp này do Eli Biham và Adi Shamir
tìm ra vào khoảng cuối những năm 1980, nĩ thƣờng đƣợc sử dụng để tấn cơng các
thuật tốn khối (block cipher). Phƣơng pháp này dựa trên việc phân tích những biến
đổi của hai văn bản gốc cĩ liên quan khi đƣợc mã hĩa bởi cùng một chìa.
• Tấn cơng dựa trên thời gian
Năm 1995, Paul Kocher mơ tả một dạng tấn cơng mới lên RSA: Khi kẻ tấn
cơng nắm đủ thơng tin về phần cứng thực hiện mã hĩa và xác định đƣợc thời gian
giải mã đối với một số bản mã lựa chọn thì cĩ thể nhanh chĩng tìm ra khĩa d. Dạng
tấn cơng này cĩ thể áp dụng đối với hệ thống chữ ký điện tử sử dụng RSA.
• Tấn cơng lựa chọn thích nghi bản mã
Năm 1981, Daniel Bleichenbacher mơ tả dạng tấn cơng lựa chọn thích nghi
bản mã (adaptive chosen ciphertext attack) đầu tiên cĩ thể thực hiện trên thực tế đối
với một văn bản mã hĩa bằng RSA. Văn bản này đƣợc mã hĩa dựa trên tiêu chuẩn
Public-Key Cryptography Standards #1 (PKCS #1), một tiêu chuẩn chuyển đổi bản
rõ cĩ khả năng kiểm tra tính hợp lệ của văn bản sau khi giải mã. Do những khiếm
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
44
khuyết của PKCS #1, Bleichenbacher cĩ thể thực hiện một tấn cơng lên bản RSA
dùng cho giao thức Secure Sockets Layer (tìm đƣợc khĩa phiên). Do phát hiện này,
các mơ hình chuyển đổi an tồn hơn nhƣ chuyển đổi mã hĩa bất đối xứng tối ƣu
(Optimal Asymmetric Encryption Padding) đƣợc khuyến cáo sử dụng. Đồng thời
phịng nghiên cứu của RSA cũng đƣa ra phiên bản mới của PKCS #1 cĩ khả năng
chống lại dạng tấn cơng nĩi trên.
• Phƣơng pháp sử dụng (n)
Giả sử ngƣời tấn cơng biết đƣợc giá trị (n). Khi đĩ việc xác định giá trị p, q
đƣợc đƣa về việc giải hai phƣơng trình sau
n = p q
Thay q = n/p, ta đƣợc phƣơng trình bậc hai
p, q chính là hai nghiệm của phƣơng trình bậc hai này. Tuy nhiên vấn đề phát
hiện đƣợc giá trị (n) cịn khĩ hơn việc xác định hai thừa số nguyên tố của n.
Ngồi ra cịn một số phƣơng pháp tấn cơng khác đƣợc sử dụng để tấn cơng hệ
mã RSA. Tuy nhiên, từ cơ sở tốn học của RSA, hầu hết các phƣơng pháp tấn cơng
đều chƣa thực sự hiệu quả. Các cố gắng bẻ khĩa RSA thành cơng đƣợc cơng bố đều
phải dựa trên sức mạnh kết hợp của nhiều máy tính thực và thực hiện trong khoảng
thời gian dài.
Tuy nhiên, để đảm bảo tính an tồn cao cho hệ mã RSA nĩi riêng và các hệ mã
cơng khai nĩi chung. Việc áp dụng các cải tiến nhằm tăng tính an tồn là cấp thiết.
2.5.2 Độ an tồn của hệ mã RSA.
Độ an tồn của hệ thống RSA dựa trên 2 vấn đề của tốn học: bài tốn phân
tích ra thừa số nguyên tố các số nguyên lớn và bài tốn RSA. Nếu 2 bài tốn trên là
khĩ (khơng tìm đƣợc thuật tốn hiệu quả để giải chúng) thì khơng thể thực hiện
11 qpn
012 npnnp
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
45
đƣợc việc phá mã tồn bộ đối với RSA. Phá mã một phần phải đƣợc ngăn chặn
bằng các phƣơng pháp chuyển đổi bản rõ an tồn.
Bài tốn RSA: Cho số nguyên dƣơng N là tích của hai số nguyên tố phân biệt
p và q (N = p * q), số nguyên e sao cho thỏa mãn gcd(e, (p – 1) * (q – 1)) = 1, và số
nguyên c. Tìm một số nguyên m sao cho me c (mod N).
Hiện nay phƣơng pháp triển vọng nhất giải bài tốn này là phân tích n ra thừa
số nguyên tố. Khi thực hiện đƣợc điều này, kẻ tấn cơng sẽ tìm ra số mũ bí mật d từ
khĩa cơng khai và cĩ thể giải mã theo đúng quy trình của thuật tốn. Nếu kẻ tấn
cơng tìm đƣợc 2 số nguyên tố p và q sao cho: n = p*q thì cĩ thể dễ dàng tìm đƣợc
giá trị (p-1)*(q-1) và qua đĩ xác định d từ e. Chƣa cĩ một phƣơng pháp nào đƣợc
tìm ra trên máy tính để giải bài tốn này trong thời gian đa thức (polynomial-time).
Tuy nhiên ngƣời ta cũng chƣa chứng minh đƣợc điều ngƣợc lại (sự khơng tồn tại
của thuật tốn).
Tại thời điểm năm 2005, số lớn nhất cĩ thể đƣợc phân tích ra thừa số nguyên
tố cĩ độ dài 663 bít với phƣơng pháp phân tán trong khi khĩa của RSA cĩ độ dài từ
1024 tới 2048 bít. Một số chuyên gia cho rằng khĩa 1024 bít cĩ thể sớm bị phá vỡ
(cũng cĩ nhiều ngƣời phản đối việc này). Với khĩa 4096 bít thì hầu nhƣ khơng cĩ
khả năng bị phá vỡ trong tƣơng lai gần. Do đĩ, ngƣời ta thƣờng cho rằng RSA đảm
bảo an tồn với điều kiện n đƣợc chọn đủ lớn. Nếu n cĩ độ dài 256 bít hoặc ngắn
hơn, nĩ cĩ thể bị phân tích trong vài giờ với máy tính cá nhân dùng các phần mềm
cĩ sẵn. Nếu n cĩ độ dài 512 bít, nĩ cĩ thể bị phân tích bởi vài trăm máy tính tại thời
điểm năm 1999.
Năm 1993, Peter Shor cơng bố thuật tốn Shor chỉ ra rằng: máy tính lƣợng tử
(trên lý thuyết) cĩ thể giải bài tốn phân tích ra thừa số trong thời gian đa thức. Tuy
nhiên, máy tính lƣợng tử vẫn chƣa thể phát triển đƣợc tới mức độ này trong nhiều
năm nữa.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
46
Nhƣ vậy, tính an tồn của phƣơng pháp RSA dựa trên cơ sở các máy tính tại
thời điểm hiện tại chƣa đủ khả năng giải quyết việc phân tích các số nguyên rất lớn
ra thừa số nguyên tố.
2.6 HỆ MẬT MÃ KHĨA CƠNG KHAI ELGAMAL
Vào năm 1985, Hệ mật mã khố cơng khai ElGamal đƣợc giới thiệu bởi T.
ElGamal. Độ an tồn của hệ này phụ thuộc vào độ khĩ giải bài tốn logarithm rời
rạc trong trƣờng số hữu hạn Zp. Vì vậy, số nguyên tố p cần phải đƣợc chọn sao cho
bài tốn logarithm là khĩ tính tốn. Trƣờng hợp đặc biệt để ngăn ngừa sự tấn cơng,
thì số nguyên tố p cần phải đƣợc chọn sao cho số (p - 1) cĩ ít nhất một thừa số
nguyên tố lớn q.
2.6.1 Bài tốn logarithm rời rạc
Định nghĩa 2.1: Một trƣờng hữu hạn là một trƣờng F chứa một số hữu hạn
các phần tử. Bậc của nhĩm F là số các phần tử tồn tại trong F .
Hình xxx: Đồ thị so sánh chi phí tấn cơng khĩa bí mật
và khĩa cơng khai
6
4
1
2
8
2
5
6
5
1
2
1
K
2
K
4
K
Độ dài mã khóa (bits)
C
h
i
p
h
í
1 2
1. Khĩa bí mật
2. Khĩa cơng khai
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
47
Định nghĩa 2.2: Cho Fq là một trƣờng hữu hạn, và một phần tử g Fq, định
nghĩa bậc (order) của g là số nguyên dƣơng m nhỏ nhất sao cho: gm 1(mod q), và
ký hiệu là:
Ordq(g) = m
Định nghĩa 2.3: Một phần tử sinh g của trƣờng hữu hạn Fq, nếu g cĩ bậc (q–
1);
Phát biểu tương đương: g là phần tử sinh (chính), nếu lũy thừa của g cĩ thể
sinh ra tất cả các phần tử khác khơng của Fq
*. Nghĩa là:
{g
x
: 0 ≤ x ≤ q – 2} = Fq
*
Định lý 2.1: Mỗi trƣờng hữu hạn đều cĩ phần tử sinh. Nếu g là một phần tử
sinh của Fq
*
thì gj là phần tử sinh nếu và chỉ nếu gcd(j, q –1) = 1. Vậy cĩ tổng cộng
φ(q – 1) phần tử sinh khác nhau của Fq
*
.
Định nghĩa 2.4: Cho G là một nhĩm vịng (cyclic) hữu hạn cĩ bậc n và g là
phần tử sinh của G. Logarithm rời rạc của y cơ số g, kí hiệu loggy là một số nguyên
duy nhất x, với 0 x n – 1 sao cho:
y = g
x
.
Bài tốn 2.1: Cho số nguyên tố p, một phần tử sinh g của Zp
*, và một phần
tử y Zp
*, tìm số nguyên x , 0 x p – 2 sao cho:
y = g
x
(mod p), (tìm x = loggy).
2.6.2 Định nghĩa các tập làm việc của hệ mật mã ElGamal
Tập các bản rõ M = Zp
*
= {1, 2,..., p-1}
Tập các bản mã C = Zp
* Zp
*
Tập các khố cơng khai Ke = {p} P Zp
* ( với P là tập các phần tử sinh)
Tập các khĩa riêng Kd = Zp - 1 = {1, 2,..., p – 2}
2.6.3 Quá trình tạo khố, mã hố, giải mã
a) Tạo khố:
Tạo số nguyên tố p lớn sao cho bài tốn logarithm rời rạc trong Zp là khĩ
giải và số p – 1 cĩ ít nhất một thừa số nguyên tố q lớn.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
48
Chọn số g Zp
*
là phần tử sinh. Các giá trị p và gthƣờng đƣợc sử dụng nhƣ
những tham số chung trong nhĩm.
Ngƣời sử dụng chọn ngẫu nhiên số x sao cho 0 < x < p – 2, và định nghĩa: K
= {(p, g, x,y y = gx (mod p)}.
Cơng bố bộ ba số nguyên (p, g, y) làm khố cơng khai, cịn số nguyên x đƣợc
giữ bí mật làm khĩa riêng.
b) Mã hố:
Mã hĩa thơng điệp M gửi cho B, thì ngƣời gửi A thực hiện các bƣớc nhƣ sau:
Dùng thuật tốn để chia thơng điệp M ra nhiều khối cĩ chiều dài cố định và
mỗi khối đƣợc biến đổi thành một số nguyên tƣơng ứng Mi < p, (i =1,.…, k).
- Biến đổi các ký tự của thơng điệp thành các số tƣơng ứng, thí dụ theo qui tắc:
Dấu cách 00, A 01, B 02,..., Z 26.
- Chia thơng điệp số vừa biến đổi thành r nhĩm số cĩ chiều dài bằng nhau, mỗi
nhĩm biểu diễn một số nguyên Mi < p với (1 i r).
Lấy khĩa cơng khai của ngƣời nhận B (p, g, y).
Chọn ngẫu nhiên một số nguyên k sao cho 0 k (p – 2).
Mã hố lần lƣợt từng số Mi với khĩa cơng khai của ngƣời nhận, bằng cách
tính: Ci = Eke(Mi) = (Ci1, Ci2), với Ci1 = g
k
mod p và Ci2 = Mi *y
k
mod p
Tập số {C1, C2,...,Cr}, với Ci = (Ci1, Ci2), i = 1,…, r là bản mã gửi cho B.
c) Giải mã:
Để giải mã bản mã {C1, C2,...,Cr }, ngƣời nhận B thực hiện các bƣớc nhƣ sau:
Giải mã lần lƣợt các cặp số Ci = (Ci1, Ci2), với 1 i r
Tính: Mi = DKd(Ci1, Ci2) = Ci2 * (Ci1
x
)
-1
mod p.
Kết quả thu đƣợc là tập các số nguyên lớn { M1, M2,..., Mr }. Biến đổi các số
nguyên Mi trở lại các chuỗi ký tự tƣơng ứng và khơi phục lại thơng điệp M.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
49
Bảng 2.1: Tĩm tắt các bước tạo khố, mã hố, giải mã của Hệ ElGamal
2.6.4 Tính đúng của quá trình giải mã
Ta cĩ: y = gx (mod p) (định nghĩa)
và C1 = g
k
mod p
C2 = M *y
k
mod p
DKd(C1, C2) = C2 * (C1
x
)
-1
mod p
= M * y
k
* ([g
k)-x mod p
= M * g
x
]
k
* ([g
k)-x mod p
= M * g
kx
* g
-kx
mod p
= M mod p
mà M < p, vậy DKd(C1, C2) = M mod p = M
2.6.5 Đánh giá độ an tồn và khả năng ứng dụng của hệ mật mã khĩa cơng
khai ElGamal
2.6.5.1 Độ an tồn
Để đảm bảo độ an tồn cho hệ ElGamal ngƣời thiết kế phải tạo số nguyên tố
Mã hố: Mã hố bản rõ M
* Chọn số ngẫu nhiên k: 1 k p – 2
* Tính C = Eke(M) = (C1, C2) với C1 = g
k
(mod p), C2 = M*y
k
(mod p)
Giải mã: Giải mã bản mã C
M = D(C) = Dkd(C1, C2) = C2 * (C1
x
)
-1
mod p
Tạo khố:
* Tạo số nguyên tố p lớn, sao cho bài tốn logarithm rời rạc trong Zp
* là
khĩ thực hiện.
* Chọn g Zp
*
là phần tử sinh.
* Chọn ngẫu nhiên số 0 < x < p – 2.
* Tính y = gx (mod p).
Khố cơng khai: (p, g, y) Khĩa riêng: ( x )
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
50
p lớn (khoảng 1024-bits), sao cho số p – 1 cĩ ít nhất một thừa số nguyên tố q lớn
nhằm ngăn ngừa sự tấn cơng của kỹ thuật Pohlig-Hellman. Ngồi ra số ngẫu nhiên k
khơng đƣợc sử dụng để mã hĩa nhiều hơn một thơng địêp. Vì nếu sử dụng k để mã
hố cho hai thơng điệp M và M’ với kết quả là (C1, C2) và (C1’, C2’) thì ta cĩ
C2(C2’) M(M’)
-1(mod p). Vậy nếu biết đƣợc M thì M’ cĩ thể tính tốn đƣợc dễ
dàng.
2.6.5.2 Khả năng thực hiện và ứng dụng
Phƣơng pháp tính tốn của hệ mã ElGamal rất phức tạp, vì địi hỏi nhiều
phép tính lũy thừa modulo trong quá trình mã hĩa và giải mã, nên cĩ hiệu suất thực
hiện kém. Do đĩ thƣờng khơng đƣợc ứng dụng trong những trƣờng hợp mã hĩa
khối lƣợng lớn dữ liệu. Tính chất khơng thể phủ nhận (non-repudiation) của hệ này
là cơ sở của các lƣợc đồ chứng thực và chữ ký điện tử (phiên bản sửa đổi của lƣợc
đồ chữ ký ElGamal là chữ ký DSA đƣợc dùng trong chuẩn chữ ký điện tử của NIST
ở Mỹ và cả thế giới).
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
51
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
3.1 PHÂN TÍCH CÁC PHÉP XỬ LÝ TỐN HỌC TRONG HỆ MÃ RSA
3.1.1 Xử lý với số nguyên lớn.
Trong quá trình tạo khĩa ta cần phải tạo ra hai số nguyên tố phân biệt p và q
lớn, sao cho bài tốn phân tích thật sự là khĩ giải.
Nhƣ vậy, để đảm bảo an tồn cho hệ mã RSA, giải thuật xử lý phải thực hiện
đƣợc với các số lớn hàng trăm chữ số.
3.1.2 Xử lý các phép tốn với số nguyên lớn.
3.1.2.1 Phép nhân với số nguyên lớn.
Để thực hiện đƣợc các phép tính tốn trong quá trình ta cần thực hiện đƣợc
các phép tốn đƣợc sử dụng.
Trong quá trình tạo khĩa, ta phải tính đƣợc N = p*q và φ(N) = (p–1)*(q–1).
Do đĩ chƣơng trình cần xử lý đƣợc phép nhân hai số p và q với p và q là các số
nguyên tố lớn.
3.1.2.2 Phép cộng – trừ số nguyên lớn.
Sử dụng trong các quá trình tính tốn, việc cài đặt tƣơng đối đơn giản khi đã tổ
chức đƣợc dữ liệu lƣu trữ cho các số hạng.
3.1.2.3 Phép tính lũy thừa với số nguyên lớn.
Quá trình giải mã của RSA cần tính M = Cd mod N, với số mũ bí mật d
thƣờng rất lớn (d N) để đảm bảo độ an tồn cho dữ liệu. Vì vậy chi phí thực hiện
giải mã của hệ RSA tƣơng đƣơng với chi phí để thực hiện phép tính lũy thừa nhanh
là: 3n3 + n2.
Do đĩ chƣơng trình cần phải xử lý đƣợc các phép tính lũy thừa nhanh.
Kết luận:
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
52
Về bản chất, phép lũy chính là phép nhân liên tiếp, sử dụng các tính chất đồng
dƣ, ta cĩ thể đƣa việc xử lý phép lũy thừa về phép nhân. Do đĩ, trong đề tài này đi
sâu vào việc xử lý phép nhân nhanh số nguyên với các số hạng là các số lớn.
Kết quả thực hiện sẽ được thử nghiệm với hai chương trình:
Chƣơng trình 1: Xử lý các phép tốn số học với số lớn
Thực hiện các phép tính số học: Cộng, trừ, nhân, lũy thừa với số lớn.
Đây là phần kết quả cơ bản của đề tài, về mặt lý thuyết, khi cài đặt thành
cơng các phép xử lý tốn học này ta hồn tồn cĩ thể áp dụng để xây dựng hệ
mã RSA.
Chƣơng trình 2: Hệ mã RSA thử nghiệm
Áp dụng các kết quả đã cĩ đƣợc trong việc xử lý các phép tốn số học
để bƣớc đầu xây dựng thử nghiệm một hệ mã RSA. Trong điều kiện cĩ hạn
của luận văn và sự phức tạp của hệ mã RSA, chƣơng trình chỉ dừng ở mức
thực nghiệm.
3.2 ỨNG DỤNG GIẢI THUẬT FAST FOURIER TRANSFORM
TRONG XỬ LÝ PHÉP NHÂN SỐ LỚN
3.2.1 Giới thiệu thuật tốn FFT
Cho hai số lớn X và Y với kích thƣớc lớn nhất là n-1, chúng cĩ thể đƣợc viết ở
dạng sau:
X = P(B), Y = Q(B)
Với B là cơ số (Thơng thƣờng B=10 hoặc là lũy thừa của 10). P và Q là hai đa
thức
P(z) =
n-1
j = 0
xj z
j
, Q(z) =
n-1
j = 0
yjz
j
.
Kết quả khi thực hiện nhân P(z) với Q(z) trong R(z), khi đĩ ta cĩ đƣợc tích
X.Y = R(B). Bằng cách sắp xếp lại theo hệ số của R(z) ta thu đƣợc kết quả của phép
nhân X với Y.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
53
Dựa trên lý thuyết này, ta áp dụng để thực hiện việc nhân hai đa thức cĩ bậc
nhỏ hơn n.
Một đa thức cĩ bậc nhỏ hơn m là duy nhất khi nĩ đƣợc tạo bởi các giá trị cụ
thể tại m điểm. Do đĩ, để tính tích R(z)= P(z).Q(z) ta cần đi tính các giá trị R(wk)
tại 2n điểm phân biệt ứng với mỗi wk, điều này cũng cĩ nghĩa là ta cần tính các giá
trị của P(wk) và Q(wk). Thuật tốn FFT là một gợi ý phù hợp với việc lựa chọn cho
wk căn của đơn vị.
wk = exp
2ik
2n
= k, = exp
2i
2n
Với cách lựa chọn này, các giá trị wk thỏa mãn hai thuộc tính sau:
Tập hợp các giá trị (P(w0),,P(w2n-1)) và (Q(w0),,Q(w2n-1)) cĩ thể tính
tốn đƣợc trong thời gian O(n logn).
Từ các giá trị R(wk) với i = 0,,2n-1, đa thức R(z) thu đƣợc trong thời
gian O(n logn).
Khi đĩ, hệ số thứ k kí hiệu là rk của R(z) thỏa mãn:
rk =
1
2n
T
wk
, T(z) =
2n-1
j = 0
R(wj) z
j
,
3.2.2 Biến đổi Fourier
Cho dãy A = (a0, a1,, a2n-1), tìm dạng biến đổi Fourier của dãy A.
Gọi F2n(A) là dạng biến đổi Fourier của A, khi đĩ F2n(A) đƣợc biểu diễn nhƣ sau:
F2n(A) = (b0, b1, , b2n-1), bk =
2n-1
j = 0
aj
jk
. (*)
Cuối cùng ta thu đƣợc R(z) bằng dạng biến đổi Fourier ngƣợc với các hệ số
R(j) đƣợc thể hiện trong cơng thức sau:
F
2n
(F2n(R)) = 2n R,
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
54
F
2n
(A) = (b0, b1, , b2n-1), bk =
2n-1
j = 0
aj
-jk
.
3.2.3 Biến đổi Fourier nhanh
Thuật tốn Fast Fourier Transform là phƣơng pháp để tìm ra dạng biến đổi
Fourier của dãy số A trong thời gian O(n logn). Cách này nhanh hơn với phƣơng
pháp truyền thống cần đến thời gian O(n2) với n là lũy thừa của 2.
bk =
2n-1
j = 0
aj
jk
=
n-1
j = 0
a2j (
2
)
jk
+ k
n-1
j = 0
a2j+1 (
2
)
jk
.
Nĩi cách khác, để tính tốn các hệ số bk của F2n(A), ta thực hiện các bƣớc
sau:
Định nghĩa 2 dãy con kích thƣớc n, A0 chứa các hệ số chẵn cịn A1 chứa các hệ
số lẻ.
A0 = (a0, a2, , a2n-2), and A1 = (a1,a3,,a2n-1).
Tìm các biến đổi Fourier
C = Fn(A0) = (c0,c1,,cn-1) and D = Fn(A1) = (d0,d1,,dn-1).
Từ đĩ suy ra biểu diễn Fourier của B = (b0,,b2n-1) = F2n(A) theo các cơng
thức sau:
bk = ck +
k
dk, bn+k = ck -
k
dk, 0 k < n.
3.2.3 Phép nhân số lớn áp dụng giải thuật FFT
3.2.3.1 Giải thuật
Phần này trình bày thuật tốn để thực hiện phép nhân hai số lớn với FFT.
Phƣơng pháp này đƣợc Schưnhage và Strassen đề xuất năm 1971 và cho tới nay đây
vẫn là phƣơng pháp nhân hai số lớn nhanh nhất.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
55
Cho n là lũy thừa của 2 và hai số nguyên lớn X và Y cĩ ít hơn n hệ số khi biểu
diễn ở dạng đa thức cơ số B.
X và Y cĩ dạng biểu diễn đa thức nhƣ sau:
X =
n-1
j = 0
xj B
j
, Y =
n-1
j = 0
yj B
j
.
Để tính Z=XY ta thực hiện các bƣớc sau :
Tìm dạng biến đổi Fourier X* của X với kích thƣớc 2n:
X
*
= (x0
*
,x1
*
,,x2n-1
*
) F2n(x0,x1,,xn-1,0,,0)
Tƣơng tự, ta tìm Y* là dạng biểu diễn Fourier của Y:
Y
*
= (y0
*
,y1
*
,,y2n-1
*
) F2n(y0,y1,,yn-1,0,,0).
Nhân các phần tử tƣơng ứng của X* với Y* rồi lƣu kết quả trong Z*
Z
*
= (z0
*
,z1
*
,,z2n-1
*
), zi
*
xi
*
yi
*
.
Biến đổi Fourier ngƣợc để tìm Z từ Z*
Z = (z0,z1,,z2n-1)
1
2n
F
2n
(Z
*
).
Đa thức Z chính là kết quả cần tìm của tích XY
Z =
2n-1
i = 0
zi B
i
Chú ý rằng X* là dạng biến đổi Fourier của dãy x0,,xn-1 với n số 0 đƣợc thêm vào
sau x0,,xn-1 và Y
*
là dạng biến đổi Fourier của dãy y0,,yn-1 với n số 0 đƣợc
thêm vào sau y0,,yn-1
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
56
3.2.3.1 Cài đặt giải thuật nhân nhanh
Thực hiện việc nhân nhanh số lớn sử dụng thuật tốn FFT áp dụng trong nhân
nhanh hai số lớn nhằm biến đổi rời rạc Fourier trong thời gian O(nlogn).
Giải thuật Discrete Fourier Transform (DFT) sẽ đƣợc áp dụng trong sơ đồ sau
để thực hiện phép nhân:
Thêm các số 0
[ a
0 , a 1 , a 2 ,..., a n -1 ] [ b 0 , b 1 , b 2 ,..., b n -1 ]
DFT DFT
[ a
0 , a 1 , a 2 ,..., a n -1 ,0,0,...,0] [ b 0 , b 1 , b 2 ,..., b n -1 ,0,0,...,0]
[ y
0 , y 1 , y 2 ,..., y 2 n -1 ] [ z 0 , z 1 , z 2 ,..., z 2 n -1 ]
Khối thực hiện
nhân
DFT ngƣợc
[ y
0 z 0 , y 1 z 1 ,..., y 2 n -1 z 2 n -1 ]
[ c
0 , c 1 , c 2 ,..., c 2 n -1 ]
Thêm các số 0
Sơ đồ 3.1: Thực hiện giải thuật nhân nhanh sử dụng DFT
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
57
3.2.3.1 Cài đặt thuật tốn FFT và DFT
Mơ phỏng thuật tốn FFT:
Cho dãy A cĩ chiều dài là m, w là căn nguyên thủy bậc m của đơn vị.
Kết quả đƣợc lƣu trong vector V
FFT(A, m, w,V)
{
if (m==1) return vector V = (a_0)
else {
A_even = (a_0, a_2, ..., a_{m-2})
A_odd = (a_1, a_3, ..., a_{m-1})
V_even = FFT(A_even, m/2, w^2)
//w^2 là căn nguyên thủy bậc m/2 của đơn vị.
V_odd = FFT(A_odd, m/2, w^2)
for (j=0; j < m/2; ++j) {
V[j] = V_even[j] + w^j*V_odd[j]
V[j+m/2] = V_even[j] - w^j*V_odd[j]
}
}
Thuật tốn Direct fourier transform
int DFT(int dir,int m,double *x1,double *y1)
{
long i,k;
double arg;
double cosarg,sinarg;
double *x2=NULL,*y2=NULL;
x2 = malloc(m*sizeof(double));
y2 = malloc(m*sizeof(double));
if (x2 == NULL || y2 == NULL)
return(FALSE);
for (i=0;i<m;i++) {
x2[i] = 0;
y2[i] = 0;
arg = - dir * 2.0 * 3.141592654 * (double)i / (double)m;
for (k=0;k<m;k++) {
cosarg = cos(k * arg);
sinarg = sin(k * arg);
x2[i] += (x1[k] * cosarg - y1[k] * sinarg);
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
58
y2[i] += (x1[k] * sinarg + y1[k] * cosarg);
}
}
/* Copy the data back */
if (dir == 1) {
for (i=0;i<m;i++) {
x1[i] = x2[i] / (double)m;
y1[i] = y2[i] / (double)m;
}
} else {
for (i=0;i<m;i++) {
x1[i] = x2[i];
y1[i] = y2[i];
}
}
free(x2);
free(y2);
return(TRUE);
}
Thuật tốn Fast Fourier Transform
X và Y là hay dãy số gồm 2m phần tử.
dir = 1 thực hiện chiều thuận của FFT.
dir = -1 thực hiện chiều ngƣợc của FFT.
*/
short FFT(short int dir,long m,double *x,double *y)
{
long n,i,i1,j,k,i2,l,l1,l2;
double c1,c2,tx,ty,t1,t2,u1,u2,z;
n = 1;
for (i=0;i<m;i++)
n *= 2;
i2 = n >> 1; /* Sử dụng phép dịch phải*/
j = 0;
for (i=0;i<n-1;i++) {
if (i < j) {
tx = x[i];
ty = y[i];
x[i] = x[j];
y[i] = y[j];
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
59
x[j] = tx;
y[j] = ty;
}
k = i2;
while (k <= j) {
j -= k;
k >>= 1;
}
j += k;
}
/* Thực hiện FFT */
c1 = -1.0;
c2 = 0.0;
l2 = 1;
for (l=0;l<m;l++) {
l1 = l2;
l2 <<= 1; /* Sử dụng phép dịch trái*/
u1 = 1.0;
u2 = 0.0;
for (j=0;j<l1;j++) {
for (i=j;i<n;i+=l2) {
i1 = i + l1;
t1 = u1 * x[i1] - u2 * y[i1];
t2 = u1 * y[i1] + u2 * x[i1];
x[i1] = x[i] - t1;
y[i1] = y[i] - t2;
x[i] += t1;
y[i] += t2;
}
z = u1 * c1 - u2 * c2;
u2 = u1 * c2 + u2 * c1;
u1 = z;
}
c2 = sqrt((1.0 - c1) / 2.0);
if (dir == 1)
c2 = -c2;
c1 = sqrt((1.0 + c1) / 2.0);
}
/* Thực hiện chiều thuận của FFT */
if (dir == 1) {
for (i=0;i<n;i++) {
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
60
x[i] /= n;
y[i] /= n;
}
}
return(TRUE);
}
Cơ số B đƣợc sử dụng khi áp dụng cài đặt là 2. Ta chọn cơ số này vì máy tính
biểu diễn thơng tin trong hệ cơ số 2. Việc tối ƣu hĩa trong cài đặt sẽ đƣợc thực hiện
với các phép dịch bit. Thuật tốn sẽ thực hiện rất nhanh do phép dịch bit cĩ tốc độ
thực hiện nhanh.
Bằng việc sử dụng các phép dịch bit, ta đã tối ƣu hĩa việc cài đặt thuật tốn
nhân nhanh so với cách cài đặt thơng thƣờng.
3.3 CÀI ĐẶT THỬ NGHIỆM CÁC PHÉP TỐN VỚI SỐ LỚN
Từ các kết quả phân tích, các thuật tốn số học đƣợc cài đặt thành chƣơng
trình để chạy thử nghiệm với các số lớn.
3.2.1 Xử lý phép cộng –trừ
Giải thuật cộng – trừ hai số nguyên lớn cĩ thể đƣợc thực hiện dễ dàng khi hai
số đã đƣợc tổ chức dữ liệu để biểu diễn.
Ví dụ 3.1:
Giả sử ta cần cộng hai số a, b đã đƣợc biểu diễn ở dạng chuỗi là Sa và Sb. Giải
thuật cộng hai số lớn cĩ thể đƣợc thực hiện nhƣ sau:
Bước 1: Đƣa hai số a, b về cùng độ dài N (Nếu độ dài của a và b là khác nhau)
bằng cách thêm các số 0 vào đầu của số cĩ độ dài nhỏ hơn. Ta đƣợc Sa và Sb cĩ
cùng độ dài N với N =Max[Length(Sa), Length(Sb)]
Bước 2: Gán giá trị Remem =0 (Remem là biến để nhớ số hàng chục của kết
quả (Sa[k] + Sb[k]), đảo ngƣợc Sa và Sb
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
61
Bước 3: Cộng từng vị trí tƣơng ứng của hai chuỗi Sa và Sb từ trái sang phải.
Lƣu kết quả mỗi bƣớc trong chuỗi Sc với Sc[k]= (Sa[k] + Sb[k]+Remem) mod 10,
Remem = (Sa[k] + Sb[k]) div 10. Gán Sc[N+1]=Remem
Bước 4:
Đảo ngƣợc Sc (Chỉ lấy từ vị trí 1 đến vị trí cuối cùng khác 0) ta thu đƣợc kết
quả trong Sc. (Chiều dài của Sc cĩ thể từ 0 đến N+1)
Giải thuật trên cĩ thể áp dụng tƣơng tự cho phép trừ, bên cạnh cách tổ chức dữ
liệu bằng chuỗi (Thƣờng gặp hạn chế vì chiều dài của chuỗi cũng cĩ giới hạn) ta cĩ
thể tổ chức dữ liệu sử dụng Stack.
Dễ thấy độ phức tạp của thuật tốn này luơn là O(n).
Cài đặt thử nghiệm:
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
62
3.2.2 Xử lý phép nhân
Cĩ nhiều giải thuật để thực hiện nhân nhanh hai số lớn. Ở đây ta sử dụng giải
thuật nhân nhanh ứng dụng giải thuật Fast Fourier Transform (FFT).
Giải thuật nhân nhanh hai số nguyên lớn với N chữ số cĩ thể thực hiện đƣợc
với độ phức tạp O(n ln(n)ln(ln(n))) khi áp dụng thuật tốn FFT.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
63
CHƢƠNG 4: ỨNG DỤNG TRONG XÂY DỰNG HỆ MÃ RSA
4.1 XÂY DỰNG HỆ MÃ RSA THỬ NGHIỆM
Giao diện chƣơng trình:
File văn bản rõ trƣớc khi mã hĩa
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
64
Giao diện thực hiện mã hĩa và giải mã file văn bản: (Hình 4.3 và 4.4)
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
65
Văn bản thu đƣợc sau mã hĩa:
Kết quả khi thực hiện quá trình giải mã:
4.2 ĐÁNH GIÁ VÀ NHẬN XÉT KẾT QUẢ
4.2.1 Chƣơng trình xử lý các phép tốn với số lớn:
Minh họa các thuật tốn cộng, nhân, lũy thừa nhanh với số lớn.
Thể hiện đƣợc các thơng số khi cần kiểm nghiệm nhân hai số lớn nhƣ:
- Tính chính xác của thuật tốn.
- Thời gian thực hiện (Tính bằng đơn vị thời gian) khi thực hiện với
nhiều phép nhân số lớn liên tục.
4.2.1 Chƣơng trình mơ phỏng hệ mã RSA:
Thực hiện quá trình thử nghiệm mã hĩa với các tham số
Chƣơng trình thử nghiệm với các bộ số p, q lớn và cho kết quả chính xác.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
66
CHƢƠNG V: KẾT LUẬN
CÁC KẾT QUẢ ĐẠT ĐƢỢC:
Đề tài bƣớc đầu đƣa ra giải pháp để xử lý các phép tốn số học với số lớn
trong các hệ mã cơng khai dựa trên cơ sở tốn học và tính tốn độ an tồn của các
hệ mã cơng khai.
Các kết quả nghiên cứu và ứng dụng bƣớc đầu đã thực hiện đƣợc mục đích của
đề tài. Bằng việc tối ƣu hĩa các phép xử lý tính tốn phức tạp trong hệ mã cơng khai
và minh chứng trong hệ mã cụ thể RSA. Giải thuật đƣợc áp dụng để tối ƣu hĩa phép
nhân là giải thuật xử lý cĩ độ phức tạp nhỏ nhất đƣợc biết đến cho tới thời điểm
hiện nay.
Chƣơng trình thử nghiệm đƣợc xây dựng nhằm chứng minh tính khả thi của
các kết quả nghiên cứu.
Chƣơng trình hồn thiện cần cĩ sự đầu tƣ nhiều hơn về mặt thời gian và cơng
sức. Đề tài cĩ thể tiếp tục phát triển để đem lại ứng dụng đáp ứng đƣợc yêu cầu thực
tế.
HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI
Các kết quả của đề tài cĩ thể đƣợc áp dụng trong nhiều hệ mã cơng khai khác
nhau và tiếp tục đƣợc cải tiến để cĩ đƣợc tốc độ thực thi tốt hơn.
Các kết quả cĩ thể đƣợc áp dụng trên nhiều hệ thống bảo mật, thực hiện trong
các giao dịch trên mạng, thực hiện tạo và xác thực chữ ký điện tử.
Bên cạnh đĩ, cần tối ƣu hơn nữa các phép tồn bằng các cài đặt đƣợc thử
nghiệm với các ngơn ngữ lập trình mạnh.
Tác giả mong muốn cĩ thể tiếp tục phát triển để đƣa các kết quả đã nghiên cứu
vào ứng dụng trong thực tế.
Số hĩa bởi Trung tâm Học liệu – Đại học Thái Nguyên
67
TÀI LIỆU THAM KHẢO
Tiếng Việt
[1]. Phan Đình Diệu (1999), Lý thuyết mật mã và an tồn thơng tin, Nxb Đại
Học Quốc Gia Hà Nội, Hà Nội.
[2]. Dƣơng Anh Đức, Trần Minh Triết (2005), Mã hĩa và ứng dụng, Nxb Đại
Học Quốc Gia TP Hồ Chí Minh, TP Hồ Chí Minh.
[3]. Phạm Huy Điển, Hà Huy Khối (2003), Mã hĩa thơng tin Cơ sở tốn học &
ứng dụng, Viện tốn học Hà Nội, Hà Nội.
[4]. Bùi Dỗn Khanh, Nguyễn Đình Thúc (2005), Giáo trình mã hĩa thơng tin
Lý thuyết & ứng dụng, Nxb Lao Động Xã Hội, TP Hồ Chí Minh.
[5]. PGS Hồ Thuần (2000), Giáo trình Lý thuyết mật mã và an tồn dữ liệu, Đại
học Bách Khoa Hà Nội, Hà Nội.
Tiếng Anh
[6]. Andreas V. Meier (2005), “The ElGamar Cryptosystems”
[7]. Deninis Luciano, Gordon Prichett (1978), From Caesar Ciphers To Public
Key Cryptosystems. (
[8]. RHUL M.Sc Advanced Cryptography, Week 7: Public Key Cryptography +
RSA, Spring 2004.
[9]. Dr Andreas Steffen (2000), Secure Network Communication Part II Public
Key Cryptography.
[10]. Dr Cunsheng Ding, HKUST Hong Kong (September 2004), The ElGamal
Public Key Cryptosystem.
http:/www.cs.ust.hk/faculty/cding/CSIT571/SLIDES/slide09.pdf
[11]. R.Rivest, MIT Laboratory for computer Science and RSA Data Security,
Inc. (April 1992), The MD5 Message – Digest Algorithm.
[12]. RSA Laboratories’ FAQ, RSA Security Inc.(
[13]. Ph.D William. Stallings (1999), Cryptography And Internetwork Security –
Principles And Practice, PRENTICE HALL.
[14]. Message Authentication, Hash Function, Digital Signature schemes.
[15].Tsuyoshi Takagi, Juniorprofessor (2003), Efficiency Comparison Of
Several RSA Variants.
Các file đính kèm theo tài liệu này:
- doc349.pdf