Nghiên cứu phối hợp hai phương pháp nén và mã hóa thông tin

  • Số trang: 99 |
  • Loại file: PDF |
  • Lượt xem: 22 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ----------------------------- NGUYỄN QUÝ HÀO NGHIÊN CỨU PHỐI HỢP HAI PHƯƠNG PHÁP NÉN và MÃ HOÁ THÔNG TIN Ngành: Công nghệ thông tin Chuyên ngành: Truyền dữ liệu và mạng máy tính Mã số: 60 48 15 LUẬN VĂN THẠC SĨ NGÀNH CNTT Giảng viên hướng dẫn: PGS. TS TRỊNH NHẬT TIẾN HÀ NỘI, 11-2012 2 MỤC LỤC MỤC LỤC ........................................................................................................................................... 2 DANH MỤC CÁC BẢNG......................................................................................................................... 4 DANH MỤC CÁC HÌNH VẼ.................................................................................................................... 5 LỜI MỞ ĐẦU 6 Chương 1: MỘT SỐ KHÁI NIỆM CƠ BẢN ................................................................................... 8 1.1 CÁC ĐỊNH LÝ QUAN TRỌNG ................................................................................... 8 1.1.1 Định lý Euler ..................................................................................................................... 8 1.1.2 Định lý Fermat (hệ quả của định lý Euler) ....................................................................... 8 1.1.3 Định lý đồng dƣ Trung Quốc ........................................................................................... 8 1.1.4 Định lý Bezout .................................................................................................................. 9 1.2 MỘT SỐ THUẬT TOÁN ............................................................................................... 9 1.2.1 Thuật toán Euclidean ........................................................................................................ 9 1.2.2 Thuật toán Euclidean mở rộng ....................................................................................... 10 1.2.3 Thuật toán bình phƣơng và nhân.................................................................................... 11 1.2.4 Thuật toán xác suất kiểm tra số nguyên tố ..................................................................... 12 1/. Thuật toán Miller – Rabin............................................................................................... 12 1.3 KHÁI NIỆM ENTROPY .............................................................................................. 13 1.3.1 Định nghĩa Entropy......................................................................................................... 13 1.3.2 Tính chất của Entropy..................................................................................................... 14 Chương 2: PHƢƠNG PHÁP MÃ HOÁ ......................................................................................... 15 2.1 CÁC KHÁI NIỆM CƠ BẢN ........................................................................................ 15 2.1.1 Hệ mã hoá khoá đối xứng............................................................................................... 16 2.1.2 Hệ mã hoá khoá phi đối xứng......................................................................................... 16 2.1.3 Hệ mã hoá RSA .............................................................................................................. 17 2.1.3.1 Lịch sử hình thành hệ mã hoá RSA ................................................................................ 17 2.1.3.2 Hệ mã hoá RSA đầu tiên................................................................................................. 17 2.1.3.3 Định nghĩa hệ mã hoá RSA ............................................................................................ 18 2.2 CÁC CHUẨN KỸ THUẬT TRONG PKCS............................................................... 19 2.2.1 Tổng quan về PKCS và PKCS#1 v2.1 .......................................................................... 19 2.2.1.1 PKCS ............................................................................................................................... 19 2.2.1.2 PKCS#1 v2.1 ................................................................................................................... 19 2.2.2 Các ký hiệu trong PKCS#1 v2.1 .................................................................................... 20 2.2.3 Các kiểu khóa.................................................................................................................. 21 2.2.3.1 Khóa công khai RSA ....................................................................................................... 22 2.2.3.2 Khóa bí mật RSA............................................................................................................. 22 2.2.4 Cơ sở chuyển đổi dữ liệu I2OSP và OS2IP ................................................................... 23 2.2.4.1 Chuyển đổi dữ liệu I2OSP .............................................................................................. 24 2.2.4.2 Chuyển đổi dữ liệu OS2IP .............................................................................................. 24 2.2.5 Cơ sở của hệ mật mã....................................................................................................... 25 2.2.5.1 Cơ sở hệ mã hóa RSAEP................................................................................................ 25 2.2.5.2 Cơ sở hệ mã hóa – RSADP ............................................................................................ 26 2.2.6 Lƣợc đô mã hóa .............................................................................................................. 28 2.2.6.1 Tổng quan về lược đồ mã hóa ........................................................................................ 28 2.2.6.2 Các kỹ thuật hỗ trợ.......................................................................................................... 28 2.2.6.3 Lược đồ RSAES – OAEP............................................................................................... 29 2.2.7 Ý nghĩa của việc áp dụng EME - OAEP trƣớc khi mã hóa RSA ................................. 34 2.2.8 Vấn đề sinh khóa RSA ................................................................................................... 35 2.3 CHUẨN MÃ HÓA DỮ LIỆU TIÊN TIẾN – AES ..................................................... 37 3 2.3.1 Mục đích nghiên cứu chuẩn AES .................................................................................. 37 2.3.2 Tổng quan........................................................................................................................ 38 2.3.3 Các khái niệm cơ sở ........................................................................................................ 38 2.3.3.1 Input, Output, Key ........................................................................................................... 38 2.3.3.2 Byte .................................................................................................................................. 38 2.3.3.3 Ma trận trạng thái (State Matrix). .................................................................................. 39 2.3.3.4 Hộp thay thế S – Box và InvS – Box ............................................................................... 40 2.3.4 Đặc tả thuật toán.............................................................................................................. 41 2.3.4.1 Sinh khóa con .................................................................................................................. 41 2.3.4.2 Hoạt động mã hóa .......................................................................................................... 42 2.3.4.3 Hoạt động giải mã .......................................................................................................... 43 Chương 3: PHƢƠNG PHÁP NÉN DỮ LIỆU................................................................................ 44 3.1 TỔNG QUAN VỀ NÉN DỮ LIỆU.............................................................................. 44 3.1.1 Mã nén dữ liệu ................................................................................................................ 44 3.1.1.1 Nén dữ liệu, bít trung bình .............................................................................................. 44 3.1.1.2 Mã tổng và mã phân tách................................................................................................ 46 3.1.2 Định lý Shannon ............................................................................................................. 47 3.2 MÔ HÌNH THỐNG KÊ ................................................................................................ 51 3.2.1 Mô hình thống kê tĩnh..................................................................................................... 51 3.2.2 Mô hình thống kê động................................................................................................... 51 3.2.3 Một số mã nén cơ bản..................................................................................................... 52 3.2.3.2 Mã Huffman .................................................................................................................... 57 3.2.3.3 Lưu đồ giải mã Fanon, Shannon, Huffman ................................................................... 60 3.3 MÔ HÌNH TỪ ĐIỂN ..................................................................................................... 62 3.3.1 Giới thiệu ......................................................................................................................... 62 3.3.2 Kỹ thuật từ điển............................................................................................................... 62 3.3.2.1 Nguyên lý LZ ................................................................................................................... 62 3.3.2.2 Các thuật toán nén LZ .................................................................................................... 66 Chương 4: PHỐI HỢP HAI PHƢƠNG PHÁP NÉN VÀ MÃ HOÁ THÔNG TIN .................... 80 4.1 MÔ HÌNH PHỐI HỢP HAI PHƢƠNG PHÁP NÉN VÀ MÃ HOÁ THÔNG TIN 80 4.1.1 Về không gian lƣu trữ ..................................................................................................... 80 4.1.2 Vấn đề an ninh ................................................................................................................ 81 4.1.3 Vấn đề thời gian xử lý dữ liệu ........................................................................................ 82 4.2 Mô hình phối hợp hai phƣơng pháp nén và mã hoá dữ liệu.......................................... 82 4.3 CHƢƠNG TRÌNH THỬ NGHIỆM ............................................................................ 86 4.3.1 Mô tả chung .................................................................................................................... 86 4.3.2 Ý tƣởng cài đặt ................................................................................................................ 86 4.3.2.1 Ngôn ngữ lập trình .......................................................................................................... 86 4.3.2.2 Cấu trúc chƣơng trình ..................................................................................................... 87 4.3.3 Thực hiện......................................................................................................................... 92 4.3.4 Đánh giá .......................................................................................................................... 94 KẾT LUẬN ......................................................................................................................................... 98 TÀI LIỆU THAM KHẢO ........................................................................................................................ 99 4 DANH MỤC CÁC BẢNG STT Tên bảng Trang 1. Bảng 2.1: Thay thế dãy 4 bit sang cơ số 16 40 2. Bảng 2.2: Ma trận trạng thái khởi đầu 40 3. Bảng 3.1: Ví dụ về mã nén Shannon 57 4. Bảng 3.2: Mã hoá các kí tự trong xâu “go go gophers” theo mã Huffman 60 5. Bảng 3.3: Giải mã bản mã “00111010000” theo lƣu đồ giải mã Hình 3.8 62 6. Bảng 3.4: Quá trình nén xâu “bcabbcbccbababc” theo thuật toán LZ77 68 7. Bảng 3.5: Quá trình giải nén theo thuật toán LZ77bản mã bca[3,1,b][4,1,b][2,1,c][3,1a][2,2,b][5,1,””] 68 8. Bảng 3.6: Quá trình nén xâu “ aaabbabaabaaabab” bằng thuật toán LZ78 72 9. Bảng 3.7: Quá trình nén bằng thuật toán LZ78 bản mã “(0,a)(1,a)(0,b)(3,a)(4,a)(5,a)(4,b)” 73 10. Bảng 3.8: Quá trình nén xâu “aabababaaababb” bằng thuật toán LZW 79 11. Bảng 3.9: Quá trình giải nén bản mã “001352411” theo thuật toán LZW 80 12. Bảng 4.2: Bảng kết quả thử nghiệm đánh giá về mặt hiệu quả nén 96 13. Bảng 4.2: Bảng kết quả thử nghiệm đánh giá về mặt thời gian 97 5 STT 1. DANH MỤC CÁC HÌNH VẼ Tên bảng Hình 2.1: Nguy cơ bị tấn công khi truyền thông tin trên mạng máy tính Trang 16 17 4. 5. Hình 2.2: Mô hình truyền thông sử dụng hệ mã hoá khoá đối xứng [12] Hình 2.3: Mô hình truyền thông sử dụng hệ mã hoá khoá công khai [12] Hình 2.4: Sơ đồ mã hoá EME – OAEP [13] Hình 2.5: Tóm lƣợc quy trình xử lý RSAES – OAEP - ENCRYPT 6. 7. 8. 9. 10. Hình 2.6: Tóm lƣợc quy trình xử lý RSAES – OAEP – DECRYPT Hình 2.7: Sơ đồ kết hợp RSA và AES Hình 2.8: Hộp S –Box sử dụng trong quá trình mã hoá AES [14] Hình 2.9: Hộp InvS –Box sử dụng trong quá trình mã hoá AES [14] Hình 3.1: Quá trình nén dữ liệu 35 11. 12. Hình 3.2: Văn bản tổng Hình 3.3: Mã tổng 47 13. Hình 3.4: Mã hoá theo mô hình thống kê động 47 52 14. Hình 3.5: Giải mã hoá theo mô hình thống kê động 53 15. Hình 3.6: Quá trình tạo mã Fanno 5 16. Hình 3.7: Xây dựng mã Huffman 59 17. Hình 3.8: Lƣu đồ giải mã Fanon, Shanon, Huffman 61 18. Hình 3.9: Lƣợng tin 64 19. Hình 3.10: Quá trình thực hiện nén bằn mã LZ 66 20. Hình 3.11: Sơ đồ nén LZ78 70 21. Hình 3.12: Sơ đồ giải nén thuật toán LZ78 71 22. Hình 3.13: Sơ đồ nén dữ liệu thuật toán LZW 75 23. Hình 3.14: Sơ đồ giải nén dữ liệu thuật toán LZW 78 24. Hình 4.1: Luồng xử lý nén và mã hoá 82 25. Hình 4.2: Mô hình phối hợp hai phƣơng pháp nén và mã hoá thông tin 83 26. Hình 4.3: Nội dung tệp bản rõ 84 27. Hình 4.4: Nén tệp bằng phƣơng pháp LZW 84 28. Hình 4.5: Mã hoá tệp đã nén bằng LZW 85 29. Hình 4.6: Mã hoá tệp bản rõ bằng AES 85 2. 3. 30. HHình 4.7: Nén tệp tin sau khi mã hoá bằng AES 18 32 33 38 41 41 45 86 6 LỜI MỞ ĐẦU Quá trình lƣu trữ và truyền tải thông tin luôn luôn có 2 yếu tổ đƣợc quan tâm hàng đầu là: tính an toàn bảo mật và kích thƣớc của tệp tin. Đã có rất nhiều các phần mềm, các chƣơng trình đƣợc viết để giải quyết hai vấn đề đƣợc đặt ra. Tuy nhiên các phần mềm phần lớn chỉ quan tâm tới một trong hai yếu tố chỉ nén dữ liệu Winzar, Winzip, 7Zip… hoặc chỉ mã hoá nhƣ: Enterprise, TrueCrypt… tuy nhiên nếu chỉ nén dữ liệu kích thƣớc tệp tin đƣợc giảm nhƣng lại không bảo đảm tính an toàn thông tin. Ngƣợc lại nếu chỉ mã hoá chỉ đảm bảo tính an toàn nhƣng không giải quyết đƣợc vấn đề giảm dung lƣợng lƣu trữ hơn thế mã hoá tệp tin lớn tốn nhiều thời gian và băng thông để truyền tải cũng tăng theo. Trong khi đó nếu phối hợp cả hai quá trình trên sẽ đem lại rất nhiều lợi ích: giảm dung lƣợng lƣu trữ, giảm băng thông truyền tải, giảm thời gian mã hoá, tăng tính bảo mật cho tệp tin so với tệp tin chỉ mã hoá đơn thuần. Từ ý nghĩa thực tiễn quan trọng nêu trên là động lực để tôi nghiên cứu đề tài: “Nghiên cứu phối hợp hai phƣơng pháp nén và mã hoá thông tin”. Trong luận văn sẽ đề xuất mô hình và giải pháp phối hợp hai phƣơng pháp nén và mã hoá thông tin: sử dụng các thuật toán nén để nén dữ liệu sau đó dùng phƣơng pháp mã hoá đối xứng để mã hoá tệp tin sau, cuối cùng là dùng mã khoá khoá bất đối xứng RSA để mã hoá khoá chung của AES. Luận văn đƣợc trình bày theo cấu trúc sau: - - Chƣơng 1: trình bày cơ sở toán học đƣợc sử dụng trong quá trình nén và mã hoá thông tin gồm: các khái niệm, các định lý, định nghĩa và một số thuật toán cơ bản Chƣơng 2: trình bày về các thuật toán mã hoá: AES, RSA và các kỹ thuật có liên quan đƣợc sử dụng trong quá trình mã hoá. Chƣơng 3: trình bày về các phƣơng pháp nén: Fanno, Shanon, Huffman, Lzw… Chƣơng 4: trình bày về hƣớng nghiên cứu phối hợp các phƣơng pháp nén và mã hoá thông tin. Giải pháp thực hiện và đánh giá mô hình nghiên cứu. Ngoài ra còn trình bày về quá trình cài đặt chƣơng trình thử nghiệm mô hình phối hợp bằng ngôn ngữ lập trình C#.Net. Học viên: Nguyễn Quý Hào 7 LỜI CẢM ƠN Tôi xin chân thành cảm ơn PGS.TS Trịnh Nhật Tiến, thầy đã trực tiếp hƣớng dẫn, giúp đỡ tôi từ lúc nhận đề tài đến lúc hoàn thành luận văn tốt nghiệp này. Tôi xin chân thành cảm ơn tất cả các thầy cô giáo trong khoa Công nghệ thông tin - Trƣờng ĐH Công Nghệ - ĐH Quốc Gia Hà Nội, những ngƣời đã nhiệt tình giảng dạy, truyền đạt những kiến thức trong suốt thời gian tôi học tập tại trƣờng cũng nhƣ đóng góp những ý kiến quý báu, những định hƣớng chuẩn mực giúp tôi hoàn thành luận văn này. Cuối cùng tôi xin cảm ơn tất cả các bạn trong lớp đã góp ý, trao đổi hỗ trợ cho tôi trong suốt thời gian vừa qua. Tôi xin chân thành cảm ơn! Học viên: Nguyễn Quý Hào 8 Chương 1: MỘT SỐ KHÁI NIỆM CƠ BẢN 1.1 CÁC ĐỊNH LÝ QUAN TRỌNG 1.1.1 Định lý Euler Định lý: Cho a Z, m N, m > 1. Nếu UCLN (a, m) = 1 thì a (m) 1 (mod m) 1.1.2 Định lý Fermat (hệ quả của định lý Euler) Định lý: Cho a Z và k là một số nguyên tố khi đó ak Nếu UCLN(a, k) = 1 thì ak-1 a (mod k) 1 (mod k) 1.1.3 Định lý đồng dƣ Trung Quốc Định lý: Cho m1, m2, …, mr là các số nguyên tố cùng nhau từng đôi một nghĩa là UCLN(m1, m2) = 1 i, j = 1, 2, …, r ; i ≠ j. Giả sử a1, a2, … ar Z khi đó hệ phƣơng trình đồng dƣ x a1 (modm1 ) x a 2 (modm 2 ) .... x a r (modm r ) Có nghiệm duy nhất theo modulo M = m1m2, … mr là x = r ai M i y i trong đó i 1 Mi = M và yi = Mi-1 mod mi mi Ví dụ: Tìm nghiệm đồng dƣ của hệ phƣơng trình đồng dƣ: x 3(mod 2) x 6(mod 3) x 8(mod 7) Giải: M = 2 x 3 x 7 = 42 M1 =3 x 7 = 21; M2 = 2 x 7 = 14; M3 = 2 x 3 = 6 y1 = 21-1 mod 2 = 1; y2 = 14-1 mod 3 = 2; y3 = 6-1 mod 7 = 6 x = 3 x 21 x 1 + 6 x 14 x 2 + 8 x 6 x 6 =519 mod 42 = 15 9 1.1.4 Định lý Bezout Định lý: Cho a, b N, a > b + Tồn tại x, y 1; ta có: Z sao cho ax + by = UCLN(a, b) + Nếu a, b nguyên tố cùng nhau thì tồn tại x,y Z | ax + by = 1 + a, b nguyên tố cùng nhau khi và chi khi tồn tại x, y 1.2 MỘT SỐ THUẬT TOÁN 1.2.1 Thuật toán Euclidean Cơ sở số học của thuật toán: Cho a, b, d Z, d ≠ 0 nếu a  d và b  d thì a mod b  d Nội dung thuật toán: INPUT: r0, r1 N, r0 > r1 0 OUPUT: d = UCLN(r0, r1) Thuật toán: Bƣớc 1: Nếu r1 = 0 trả về d := r0, kết thúc thuật toán Nếu r1 ≠ chuyển sang bƣớc 2 Bƣớc 2: r := r0 mod r1; r0 := r1; r1 = r; quay lại bƣớc 1 Z | ax + by = 1 10 1.2.2 Thuật toán Euclidean mở rộng Cơ sở số học của thuật toán: trong thuật toán Euclidean tìm UCNL của hai số 0, ta thấy thuật toán là quá trình thực hiện chuỗi phép chia lấy phần dƣ nguyên r0 > r1 dễ dàng ta thấy UCLN(r0, r1) = UCLN(r1, r2) = UCLN(r2, r3) = … = UCLN(rm-1, rm) Với r2 = r0 mod r1 r3 = r1 mod r2 …. Dựa trên thuật toán Euclidean ngƣời ta mở rộng thuật toán trên để tính đƣợc số nghịch đảo theo modulo m trong vành Zm Xét dãy tuần tự các số nguyên t0, t1, … tm nhƣ sau: t0 = 0 t1 = 1 tj = (tj-2 – qj-1tj-1) mod r0, với j 2 Ta có kết quả quan trọng sau: Định lý: Với mọi j, 0 j 2 ta có rj tjr1 (mod r0) Nội dung thuật toán: INPUT: n, b N (n> b 0) OUTPUT: t = b-1 mod n Giả mã thuật toán: 1. n0 = n 2. b0 = b 3. t0 = 0 4. t = 1 5. q = n0 div b0 6. r = n0 – qb0 7. while r > 0 do 7.1 temp = t0 – qt 7.2 if temp 0 then temp = temp mod n 11 7.3 if temp < 0 then temp = n – ((-temp) mod n) 7.4 t0 = t 7.5 t = temp 7.6 n0 = b0 7.7 b0 = r q = n0 div b0 r = n0 – qb0 8. if b0 ≠ 1 then b không khả nghịch theo modulo n 9. else b-1 = t mod n 1.2.3 Thuật toán bình phƣơng và nhân Giả sử có các số nguyên x, b và n. Ta phải tính xb mod n. Thuật toán: “Bình phƣơng và nhân” sau đây sẽ giúp ta tính lũy thừa này khá đơn giản. Đây là một thuật toán quan trọng đƣợc sử dụng trong qui trình mã hóa cũng nhƣ giải mã của hệ mã hoá RSA Nội dung thuật toán: INPUT: x Zn , b Z, 0 < b < n, b: viết dƣới dạng nhị phân với k chữ số nhị phân b = b1b2…bk; bi = {0, 1} OUTPUT: số a = xb mod n Giả mã thuật toán: 1. 2. 3. 4. 5. 6. z=1 for i = 1 to k do z = z. z mod n if bi = 1 then z = z.x mod n a=z return a 12 1.2.4 Thuật toán xác suất kiểm tra số nguyên tố INPUT: một số nguyên dƣơng n OUPUT: n là hợp số Sau đây ta sẽ đi xem thuật toán Miller - Rabin giải quyết bài toán này 1/. Thuật toán Miller – Rabin Kiểm tra Miller: Giả sử n là một số nguyên dƣơng lẻ, khi đó ta biểu diễn đƣợc n – 1 = 2st với s là một số nguyên không âm, t là một số nguyên dƣơng lẻ. Ta nói n vƣợt qua đƣợc kiểm tra Miller cơ sở a (a 0 Z, a > 0) nếu at 1 (mod n) hoặc a 2 k t -1 (mod n) với k nào đó k < s. Mệnh đề: Nếu n là một số nguyên tố thì n vƣợt qua kiểm tra Miller cơ sở a, 0 < a < n Định nghĩa: Nếu n vƣợt qua Miller cơ sở a thì n đƣợc gọi là số nguyên tố giả cơ sở a Số nguyên dƣơng n > 1 đƣợc gọi là số giả nguyên tố mạnh cơ sở a nếu nó là hợp số và vƣợt qua đƣợc kiểm tra Miller cơ sở a Thuật toán Miller – Rabin INPUT: OUTPUT: n N, lẻ, N > 1 “n là nguyên tố” hoặc “n là hợp số” Nội dung thuật toán: Miller – Rabin – Test(n) 1. 2. 3. 4. 5. 6. 7. 8. Viết n – 1 = 2km (m lẻ) Chọn một số ngẫu nhiên a, 1 a n – 1 b: = am mod n if b = 1 then return “n là số nguyên tố rồi” và kết thúc for i = 0 to k – 1 do if b = n – 1 then return “n là số nguyên tố” và thoát b = b2 mod n Tra lời “n” là hợp số Mệnh đề: Thuật toán Miller – Rabin cho bài toán hợp số là thuật toán Monter – Carlo định hƣớng có. Nghĩa là câu trả lời “b là hợp số” luôn đúng. Câu trả lời “n là số nguyên tố” có xác suất sai không quá 1/4 13 Miller – Rabin – Test(n) Thuật toán Miller – Rabin với t lần thực hiện kiểm tra Miller: N, lẻ, n > 1, t N, số lần kiểm tra INPUT: n OUTPUT: “n là nguyên tố” hoặc “n là hợp số” 1. Viết n – 1 = 2km (m lẻ) 2. for i := 1 to t do 2.1 Chọn một số ngẫu nhiên a, 1 a n–1 2.2 test:= false 2.3 b: = am mod n 2.4 if b = 1 then test: = true else for i = 0 to k – 1 do if b = n – 1 then test:= true else b = b2 mod n 2.5 if test = false then return “n là hợp số” và thoát 3. return “n là số nguyên tố” Xác suất sai khi trả lời n là số nguyên tố không vƣợt quá (1/4) t 1.3 KHÁI NIỆM ENTROPY 1.3.1 Định nghĩa Entropy Định nghĩa. Độ bất định : Xét không gian mẫu = {w1, w2, w3, ..., wm} với xác suất của các sự kiện ngẫu nhiên cơ bản tƣơng ứng là p1, p2, p3, ..., pm. Entropy của không gian mẫu Ω sinh ra do phép thử ngẫu nhiên mà kết quả là một trong số các sự kiện của không gian mẫu Ω hay độ bất định của việc đoán nhận sự kiện ngẫu nhiên cơ bản xảy ra đƣợc ký hiệu H(Ω) là một số tính theo công thức sau: H(Ω) = m pi . log( pi ) i 1 Định lý: Có một số δ > 1 mà H( ) = m pi . log ( pi ) i 1 Giả sử chúng ta lấy việc đoán nhận sự kiện nào trong 2 sự kiện đồng xác suất làm đơn vị đo độ bất định thì khi đó H(2) = 1 vì thế log (2) = 1. Suy ra, = 2. Chúng ta có công thức H(k) = log2(k). 14 Độ bất định xác định không phụ thuộc vào việc chọn đơn vị để đo. Nếu chọn độ bất định của việc đánh số đề tức là đoán nhận 1 trƣờng hợp trong số 100 trƣờng hợp đồng khả năng làm đơn vị đo và nếu có một việc có độ bất định là 3, tức là H(k) = log100(k) = 3. Khi dùng đơn vị đo là việc đoán nhận một trƣờng hợp trong số 10 khả năng làm đơn vị thì chỉ số đo sẽ là 6, vì H(k) = log10(k) = 2.log100(k) = 6. Chính vì vậy mà chúng ta có thể chọn đơn vị đo bất kỳ, ví dụ δ = 2. m Sau này, chúng ta sẽ dùng công thức pi log 2 ( pi ) để tính độ bất định i 1 (entropy) cho một không gian mẫu Ω với xác suất các phần tử là p1, p2, p3, ..., pm. Lƣu ý, H( ) càng lớn thì việc đoán nhận sự kiện ngẫu nhiên cơ bản nào sẽ xảy ra càng khó (càng bất định). 1.3.2 Tính chất của Entropy Tính chất: a) Entropy là một đại lƣợng luôn luôn dƣơng hoặc bằng không H(Ω)≥ 0. b) Entropy bằng 0 khi có một sự kiện ngẫu nhiên cơ bản có xác suất bằng 1 và xác suất của tất cả các sự kiện ngẫu nhiên cơ bản còn lại bằng 0. Nghĩa là có một sự kiện ngẫu cơ bản luôn luôn xảy ra. Nhƣ vậy thì việc đoán nhận một kết quả xảy ra khi thực hiện một phép thử là không có ý nghĩa gì nữa. c) Entropy đạt giá trị cực đại khi xác suất của các sự kiện ngẫu nhiên cơ bản của không gian mẫu bằng nhau. Lúc đó độ bất định của việc đoán nhận một sự kiện ngẫu nhiên cơ bản nào đó xảy ra là lớn nhất. Định lý: Nếu Ω, Φ là hai không gian mẫu cùng có m phần tử và nếu Φ là đồng xác suất thì H(Ω) ≤ H(Φ). Dấu bằng xẩy ra khi và chỉ khi với mỗi sự kiện ngẫu nhiên cơ bản trong Ω có xác suất pi thì trong Ф cũng có một sự kiện ngẫu nhiên cơ bản có xác suất pi, tức là Ω cũng là không gian đồng xác suất. Nhƣ vậy, định lý khẳng định rằng entropy của không gian đồng xác suất là lớn nhất trong số các không gian mẫu có cùng số các sự kiện ngẫu nhiên cơ bản. Ví dụ: Ví dụ đơn giản để minh hoạ nhƣ sau: giả sử chúng ta tung con xúc sắc mà ở mặt 1 chúng ta gắn chì vào. Do khối lƣợng chì nặng nên đa số trƣờng hợp mặt 6 xuất hiện (mặt 6 đối diện với mặt 1). Vì thế việc đoán xem mặt nào xuất hiện trở nên dễ hơn. 15 Chương 2: PHƢƠNG PHÁP MÃ HOÁ 2.1 CÁC KHÁI NIỆM CƠ BẢN Trong một phạm vi hẹp, có thể hiểu nhiệm vụ cơ bản của mật mã học là nghiên cứu những phƣơng pháp cho phép hai ngƣời có thể truyền thông với nhau trên một kênh thông tin không an toàn, sao cho ngƣời thứ ba dù có thể lấy cắp đƣợc thông tin cũng không thể hiểu đƣợc nội dung những thông tin truyền đi đó. Thông điệp mà Alice muốn gửi tới Bob đƣợc gọi là bản rõ (plaintext), kí hiệu là x. Để bảo vệ thông tin Alice cần sử dụng một cơ chế để truyền bản rõ x sang một dạng biểu diễn khác – bản mã (ciphertext), đƣợc kí hiệu là y và gửi bản y. Bob sau khi nhận đƣợc bản mã y anh sử dụng một cơ chế để chuyển đổi bản mã y về bản rõ x. Công việc của Alice chuyển từ bản rõ x sang bản mã y đƣợc gọi là mã hóa (encryption), công việc ngƣợc lại của Bob chuyển đổi từ bản mã y sang bản rõ x đƣợc gọi là giải mã (decryption. Yêu cầu cơ bản nhất với mỗi hệ mã hoá là bảo đảm qui tắc mã hóa và giải mã phải có khả năng tính toán hiệu quả, đồng thời đối phƣơng khi có bản mã y, khả năng tìm ra bản rõ x hoặc khóa K là khó (rất khó thực hiện trong thời gian cho phép). Sau đây là định nghĩa một hệ mã hoá dƣới hình thức toán học: Định nghĩa: Một hệ mật mã là một bộ 5 (P, C, K, E, D) trong đó: 1. 2. 3. 4. P là một tập hợp hữu bạn các bản rõ có thể C là một tập hợp hữu hạn các bản mã có thể K, không gian khóa, là một tập hữu hạn các khóa có thể Với mỗi khóa k K, tồn tại một qui tắc mã hóa ek E và một qui tắc giải mã tƣơng ứng dk D, trong đó et: P C và dk : C P là các ánh xạ thỏa mãn dk(ek(x)) = x x P Hình 2.1 Nguy cơ bị tấn công khi truyền thông tin trên mạng máy tính 16 2.1.1 Hệ mã hoá khoá đối xứng Theo mô hình chung của các hệ mã hoá khoá đối xứng, Alice và Bob bí mật chọn khóa K, sau đó K đƣợc sử dụng cho quy tắc mã hóa cũng nhƣ giải mã. Theo phƣơng pháp mã hóa này thì khóa để mã hóa chính là khóa để giải mã hoặc trong một số hệ mật thì khóa để mã hóa và khóa để giải mã tuy khác nhau nhƣng dễ dàng tính đƣợc thành phần này khi đã biết thành phần kia. Từ đó mà các hệ mã hoá khoá đối xứng còn đƣợc gọi với tên khác là hệ mã hoá khóa bị mật, hay hệ mã hoá khóa đối xứng. Dƣới đây là mô hình truyền thông sử dụng hệ mã hoá khoá đối xứng Hình 2.2: Mô hình truyền thông sử dụng hệ mã hoá khoá đối xứng [12] 2.1.2 Hệ mã hoá khoá phi đối xứng Một hạn chế của một hệ mã hoá khoá đối xứng là nó yêu cầu việc truyền đi khóa K giữa Alice và Bob trên một kênh an toàn trƣớc khi bất kì thông điệp mã hóa nào đƣợc truyenf đi. Trên thực tế điều này rất khó thực hiện khi mà hai ngƣời ở xa nhau Từ mặt hạn chế của các hệ mã hoá khoá đối xứng đã phân tích ở trên, ngƣời ta nghiên cứu và đề xuất các hệ mã hoá công khai (hệ mã hoá bất đối xứng). Tƣ tƣởng chung của các hệ mã hoá khoá phi đối xứng là mỗi khóa K trong hệ mã hoá bao gồm hai thành phần: thành phần thứ nhất dành cho quá trình mã hóa, đƣợc gọi là khóa công khai và thành phần thứ hai dành cho quá trình giải mã, đƣợc gọi là khó bí mật (khóa riêng). Có thể hình dung Bob là ngƣời sẽ nhận các thông điệp bí mật từ những ngƣời khác, anh tìm một qui tắc mã hóa eK và một quy tắc giải mã tƣơng ứng dK. Bob công bố công khai khoá e K và giữ bí mật khoá dK. Sau đó Alice và những ngƣời khác có thể sử dụng eK để mã hoá các thông điệp trƣớc khi gửi tới Bob. Về mặt lý thuyết, Bob phải đảm bảo ngƣời khác không thể tìm ra dK tƣơng ứng từ eK trong thời gian thực. Ý tƣởng về hệ mã hoá công khai đƣợc Diffie và Hellman đề xuất vào năm 1976. Và sự hiện thực hoá đầu tiên của ý tƣởng này vào năm 1977 là công của Rivest, Shamir và Adleman họ là những ngƣời phát minh ra hệ mã hoá RSA 17 Hình 2.3: Mô hình truyền thông sử dụng hệ mã hoá khoá công khai [12] 2.1.3 Hệ mã hoá RSA 2.1.3.1 Lịch sử hình thành hệ mã hoá RSA RSA (Ron Rivers, Adi Shamir và Len Adleman) là một hệ mã hoá khoá phi đối xứng. Nó là thuật toán đầu tiên phù hợp với việc tạo ra chữ kí điện tử và đánh dấu một sự tiến bộ vƣợt bậc trong mật mã học. RSA đang đƣợc ứng dụng phổ biến trong giao dịch điện tử, đảm bảo an toàn với điều kiện độ dài đủ lớn. Thuật toán đƣợc mô tả lần đầu tiên vào năm 1977 tại Học viện công nghệ Massachusettes (MIT). Trƣớc đó, vào năm 1973, Clifford Cocks, một nhà toán học ngƣời Anh đã mô tả thuật toán tƣơng tự. Với khả năng tính toán tại thời điểm đó thì thuật toán này không khả thi và chƣa bao giờ đƣợc cài đặt thực nghiệm. Phát minh này chỉ đƣợc công bố năm 1977 vì đƣợc xếp vào loại tuyệt mật 2.1.3.2 Hệ mã hoá RSA đầu tiên 1/. Bài toán phân tích một số tự nhiên ra thừa số nguyên tố Các thuật toán mã hóa công khai hiện đại đƣợc nghiên cứu và đề xuất dựa trên việc nghiên cứu lý thuyết độ phức tạp của thuật toán và tính khó của các bài toán mà thuật toán tốt nhất đƣợc tìm ra là để giải quyết bài toán đó cũng không chấp nhận đƣợc trong thời gian thực với các máy tính hiện đại Thuật toán RSA là thuật toán mã hóa dựa trên tính khó của bài toán phân tích một số nguyên tố tự nhiên (đủ lớn) ra thừa số nguyên tố. Giả sử có n là một số tự nhiện n = p.q trong đó p, q là các số nguyên tố. Với n là số tự nhiên đủ lớn, có độ dài trên 100 chữ số thập phân, thì bài toán phân tích n ra thừa số nguyên tố (tức tìm p, q) chƣa 18 có thuật toán trong thời gian đa thức. Với các máy tính hiện đại thì chƣa thể giải quyết bài toán này trong thời gian thực 2/. Bộ số RSA Cho p, q là hai số nguyên tố khác nhau và n = p.q khi đó (n) = (p-1)(q-1). Lấy a thuộc Z (n) sao cho a khả nghịch. Giả sử b = a-1 mod (n) a/ Định nghĩa: Bộ các số (n, p, q, a, b) trong đó n, p, q, a, b đƣợc đề cập ở trên đƣợc gọi là bộ số RSA. Ta có tính chất quan trọng sau đây của bộ số RSA. b/ Định lý: Nếu (n, p, q, a, b) là các bộ số RSA thì x Zn ta có: xab mod n = x c/ Ứng dụng: Cho bộ số RSA (n, p, q, a, b), x Zn. Đặt y = xb mod n. Khi đó ta có cách tìm x từ y bởi công thức: x = ya mod n. Từ đó đƣa ra định nghĩa hệ mã hoá RSA. 2.1.3.3 Định nghĩa hệ mã hoá RSA Định nghĩa: Cho bộ số RSA (n, p, q, a, b) trong đó p, q là những số nguyên tố cỡ 512 bit hoặc lớn hơn. Hệ mã hoá RSA với khóa K = (n, p, q, a, b) là hệ mã hoá với P = C = Zn, qui tắc mã hóa và giải mã nhƣ sau: Qui tắc mã hóa: với mỗi x ek : Z n x P = Zn Zn y = xb mod n Qui tắc giải mã: dk: Zn y Trong đó: Zn x = ya mod n (n, b) là thành phần khóa công khai (p, q, a) là thành phần khóa bí mật 19 2.2 CÁC CHUẨN KỸ THUẬT TRONG PKCS 2.2.1 Tổng quan về PKCS và PKCS#1 v2.1 2.2.1.1 PKCS PKCS là viết tắt của Publick – Key Cryptography Standards, là một tập hợp các chuẩn trong mã hoá hóa công khai, đƣợc đánh thứ tự PKCS#1 tới PKCS #15. PKCS đƣợc phát triển bởi phòng thí nghiệm RSA (RSA Laboratories) – một bộ phận của Tổ chức an toàn dữ liệu RSA (RSA Data Security Inc), cùng sự hợp tác rộng rãi với các nhà phát triển các hệ thống an ninh, nhằm đẩy nhanh tốc độ triển khai các ứng dụng các hệ mã hoá khoá phi đối xứng. 2.2.1.2 PKCS#1 v2.1 Chuẩn PKCS#1 v2.1 đƣợc phòng thí nghiệm RSA công bố trong tài liệu PKCS#1 v2.1: RSA Cryptopraphy Standard, ngày 14/6/2002. Mục đích là đƣa ra các khuyến nghị trong việc cài hệ mã hoá công khai dựa trên cơ sở của thuật toán RSA. Chuẩn PKCS#1 v2.1 đề cập tới các vấn đề cơ bản sau: + Các cơ sở của hệ mã hoá + Lƣợc đồ mã hóa + Lƣợc đồ chữ ký số + Cú pháp ASN.1 để biểu diễn khóa và nhận dạng lƣợc đồ Điểm mới trong PKCS#1 v2.1 so với các phiên bản trƣớc ở sự dựa vào thuật toán RSA – đa nguyên tố (Multi prime RSA) và lƣợc đồ chữ ký RSASSA – PSS. Trong RSA – đa nguyên tố thể hiện ở modulo RSA n là tích của nhiều hơn hai số nguyên tố (trong các phiên bản trƣớc đó n tích của hai số nguyên tố n = p.q) 20 2.2.2 Các ký hiệu trong PKCS#1 v2.1 Biểu diễn bản mã dạng số nguyên, 0 c c n – 1 (là đầu ra của cơ sở mã hóa RSAEP và là đầu vào của cơ sở giải mã RSADP) bản mã, là một chuỗi octet (là đầu ra của C mã hóa RSAES – OAEP – DECRYPT). d số mũ RSA bí mật, sử dụng cho quá trình giải mã di số mũ CRT của ri, là một số nguyên dƣơng thỏa mã: e.di 1 (mod ( ri - 1)), di < ri – 1, i = 3, . . u. số mũ CRT của p, là một số nguyên dƣơng thỏa mãn: dP e.dP dQ số mũ CRT của q, là một số nguyên dƣơng thỏa mã: e.dQ e 1 (mod (p – 1)); dP< p – 1 1 (mod (q – 1)); dQ < q – 1 số mũ RSA công khai, sử dụng trong quá trình mã hóa EM thông điệp đã mã hóa, là một chuỗi octet (kết quả của quá trình áp dụng phƣơng thức độn EME – OAEP trên thông điệp M) emBit chiều dài tính theo số bit của một thông điệp đã đƣợc mã hóa EM emLen chiều dài tính theo số octet của một thông điệp đã đƣợc mã hóa EM GCD(. , .) WCLN của hai số nguyên không âm Hash hàm băm bảo mật hLen chiều dài đầu ra, tính theo octet của hàm băm Hash k chiều dài tính theo số octet của modulo RSA n K khóa bí mật RSA L nhãn sử dụng trong RSAES – OAEP, một chuỗi octet LCM (. , … , .) bội chung nhỏ nhất của các số nguyên không âm M biểu diễn thông điệp (bản rõ) dạng số nguyên, 0 m sở mã hóa RSAEP, và là đầu ra của cơ sở giải mã RSADP) n – 1 (là đầu vào của cơ M thông điệp, là một chuỗi octet (là đầu vào của hoạt động mã hóa RSAES – OAEP – ENCRYPT, và là đầu ra của hoạt động giải mã RSAES – OAEP – DECRYPT)
- Xem thêm -