Download miễn phí Luận văn Các thuật toán tối ưu hóa trong bảo mật thông tin



MỤC LỤC
Trang
LỜI CẢM ƠN
LỜI CAM ĐOAN
MỤC LỤC .
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .
MỞ ĐẦU . 1
CHưƠNG 1 - LÝ THUYẾT MẬT MÃ . 6
1.1 MỘT SỐ KHÁI NIỆM CƠ BẢN VỀ MÃ HÓA . 6
1.2 LÝ THUYẾT ĐỘ PHỨC TẠP . 10
1.3 CƠ SỞ TOÁN HỌC CỦA MẬT MÃ . 13
CHưƠNG 2 - NGHIÊN CỨU CƠ CHẾ HOẠT ĐỘNG CỦA HỆ MẬT KHÓA CÔNG KHAI . 20
2.1 GIỚI THIỆU VỀ HỆ MẬT VỚI KHÓA CÔNG KHAI . 20
2.2 HỆ MẬT MÃ KHÓA CÔNG KHAI RSA . 22
2.3 HỆ MẬT MÃ KHÓA CÔNG KHAI RSA WITH CRT . 29
2.4 CƠ CHẾ HOẠT ĐỘNG CỦA RSA . 34
2.5 KHẢ NĂNG BỊ BẺ KHÓA CỦA HỆ MÃ CÔNG KHAI RSA . 36
2.6 HỆ MẬT MÃ KHÓA CÔNG KHAI ELGAMAL . 40
CHưƠNG 3 - MỘT SỐ GIẢI THUẬT XỬ LÝ SỐ HỌC ÁP DỤNG ĐỂ TỐI ưU HÓA
QUÁ TRÌNH MÃ HÓA VÀ GIẢI MÃCỦA HỆ MÃ RSA .41
3.1 PHÂN TÍCH CÁC PHÉP XỬ LÝ TOÁN HỌC TRONG HỆ MÃ RSA . 41
3.2 ỨNG DỤNG GIẢI THUẬT FAST FOURIER TRANSFORM TRONG XỬ LÝ
PHÉP NHÂN SỐ LỚN . 45
3.1 CÀI ĐẶT THỬ NGHIỆM CÁC PHÉP TOÁN VỚI SỐ LỚN . 53
CHưƠNG 4: ỨNG DỤNG TRONG XÂY DỰNG HỆ MÃ RSA . 56
4.1 XÂY DỰNG HỆ MÃ RSA THỬ NGHIỆM . 56
4.2 ĐÁNH GIÁ VÀ NHẬN XÉT KẾT QUẢ . 59
CHưƠNG 5 – KẾT LUẬN VÀ HưỚNG PHÁT TRIỂN . 60


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-10-26-luan_van_cac_thuat_toan_toi_uu_hoa_trong_bao_mat_t.yebeqlBEzC.swf /tai-lieu/de-tai-ung-dung-tren-liketly-42439/
Để tải bản DOC Đầy Đủ xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung:

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 toá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 toá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 toán này đƣợc sử dụng trong
quá trình tạo khóa ở hệ mật mã RSA.
Thuật toá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: 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 toá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ã khoá đố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 toàn thế giới do tính an toàn và khả
năng ứng dụng của nó.
Độ an toà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 toá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 toán: Chủ yếu
đề cập đến sự phân tích các thuật toán và đặc biệt là số các bƣớc tính toán cần thiết
để phát hiện khóa bí mật. Từ đó xác định độ an toà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: Khoá 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ã khoá công khai
- Hệ mật mã khoá công khai dựa trên quan điểm hàm một chiều (one-way
function) và khoá 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
toá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 toá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ã khoá 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 (khoá 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 toán khó
nhƣ: bài toán logarithm rời rạc trong trƣờng hữu hạn Zp (hệ ElGamal) và bài toá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
toá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 toá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 toán mã hóa: E , thuật toá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 cô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 hay 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ã hoá 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ã hoá 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 toá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 toán khi biết khóa công khai và thông điệp R cần mã hoá
thành một bản mã tƣơng ứng C = E(KB,R).
- Ngƣời nhậ...

---