Tài liệu Nghiên cứu ứng dụng thủy ký bảo vệ bản quyền tài liệu số

TRƯỜNG …………………. KHOA………………………. -----[\ [\----- Báo cáo tốt nghiệp Đề tài: Nghiên cứu ứng dụng thủy ký bảo vệ bản quyền tài liệu số TÓM TẮT NỘI DUNG: Khóa luận trình bày về những kết quả đạt đƣợc trong nghiên cứu ứng dụng thủy vân số vào việc bảo vệ bản quyền tài liệu số hóa. Khóa luận đƣợc trình bày thành bốn chƣơng, với nội dung nhƣ sau: Chƣơng 1: tóm tắt các kiến thức cơ bản về bảo vệ an toàn dữ liệu, bảo mật thông tin cũng nhƣ tổng quan về thủy vân số trên các tài liệu số. Chƣơng 2: trình bày về thủy vân số trên ảnh số, cùng các thuật toán và các phép biến đổi, là nội dung quan trọng và có nhiều ứng dụng thực tiễn hiện nay. Chƣơng 2 có trình bày về các phép biến đổi và xử lý ảnh, rất quan trọng trong việc thực hiện thủy vân số đối với ảnh. Chƣơng 3: trình bày về thủy vân số trên các tài liệu đa phƣơng tiện khác, nhƣ trên các file audio hoặc video. Chƣơng 3 có trình bày một thuật toán thủy vân số trên audio sử dụng công nghệ trải phổ. Chƣơng 4: chƣơng trình thử nghiệm thuật toán thủy vân số trên ảnh. Cuối cùng là kết luận và hƣớng nghiên cứu tiếp theo. MỤC LỤC: MỞ ĐẨU ............................................................................................................ 1 Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN ............................................................. 3 1.1. KHÁI NIỆM TRONG TOÁN HỌC.......................................................... 3 1.1.1.Khái niệm trong số học. ...................................................................... 3 1.1.1.1. Tính chia hết, quan hệ đồng dƣ và số nguyên tố. ......................... 3 1.1.1.2. Không gian Zn và cấu trúc nhóm. ................................................ 4 1.1.1.3. Dãy số giả ngẫu nhiên. ................................................................ 5 1.1.2. Khái niệm độ phức tạp thuật toán. ...................................................... 5 1.2. KHÁI NIỆM MÃ HÓA. ........................................................................... 7 1.2.1. Hệ mã hóa. ......................................................................................... 7 1.2.2. Mã hóa khóa đối xứng. ...................................................................... 8 1.2.3. Mã hóa khóa công khai. ................................................................... 12 1.3. KHÁI NIỆM CHỮ KÝ SỐ. .................................................................... 15 1.3.1. Sơ đồ ký số: ..................................................................................... 15 1.3.2. Sơ đồ ký số RSA. ............................................................................. 16 1.4. MỘT SỐ CÔNG CỤ BẢO VỆ BẢN QUYỀN KHÁC. ........................... 17 1.4.1. Hàm băm. ........................................................................................ 17 1.4.2. Truy vết. .......................................................................................... 18 1.5. THỦY VÂN SỐ. .................................................................................... 19 1.5.1. Khái niệm thủy vân số. .................................................................... 19 1.5.1.1. Lịch sử thủy vân số. .................................................................. 19 1.5.1.2. Quá trình nghiên cứu thủy vân số. ............................................. 21 1.5.1.3. Một số hệ thống thủy vân. ......................................................... 24 1.5.2. Các ứng dụng của thủy vân số. ......................................................... 25 1.5.3. Các đặc tính của thủy vân. ............................................................... 26 1.5.4. Phân loại thủy vân............................................................................ 27 1.5.5. Quy trình thực hiện thủy vân. ........................................................... 28 Chƣơng 2. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN ẢNH ............ 29 2.1. CÁC ĐỊNH DẠNG ẢNH. ...................................................................... 29 2.1.1. Định dạng ảnh BMP......................................................................... 29 2.1.2. Định dạng ảnh PNG. ........................................................................ 31 2.1.3. Định dạng ảnh GIF. ......................................................................... 33 2.1.4. Định dạng ảnh JPEG. ....................................................................... 37 2.1.4.1. Kỹ thuật nén ảnh JPEG. ............................................................ 37 2.1.4.2. Mã hoá biến đổi DCT. ............................................................... 39 2.1.5. Định dạng ảnh JPEG2000. ............................................................... 47 2.1.6. Định dạng ảnh PGM. ....................................................................... 49 2.2. CÁC PHÉP BIẾN ĐỔI ẢNH. ................................................................. 50 2.2.1. Các toán tử không gian. .................................................................. 50 2.2.1.1. Toán tử tuyến tính. .................................................................... 50 2.2.1.2. Toán tử nhân chập. .................................................................... 51 2.2.1.3. Các kỹ thuật lọc số. ................................................................... 52 2.2.2. Các toán tử tần số............................................................................. 57 2.2.2.1. Phép biến đổi Fourier. ............................................................... 57 2.2.2.2. Phép biến đổi Cosine rời rạc...................................................... 59 2.2.2.3. Phép biến đổi sóng con rời rạc. ................................................. 60 2.3. CÁC THUẬT TOÁN THỦY VÂN TRÊN ẢNH. ................................... 61 2.3.1. Thuật toán giấu thủy vân vào các bit có trọng số thấp. ..................... 61 2.3.2. Thuật toán thủy vân ghép nối. .......................................................... 63 2.3.3. Thuật toán thủy vân ảnh trên miền DCT. ......................................... 64 2.3.4. Thuật toán thủy vân ảnh trên miền DWT. ........................................ 66 2.3.5. Thuật toán thủy vân sử dụng biến đổi Karhunen – Loeve. ................ 68 2.3.6. Thủy vân dễ vỡ. ............................................................................... 70 2.3.7. Thủy vân giòn. ................................................................................. 72 2.4. TẤN CÔNG THỦY VÂN. ..................................................................... 73 Chƣơng 3. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN CÁC TÀI LIỆU SỐ KHÁC ........................................................................................................ 75 3.1. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN AUDIO. .............. 75 3.1.1. Giới thiệu audio số. .......................................................................... 75 3.1.2. Tổng quan về thủy vân trên audio. ................................................... 76 3.1.2.1. Thủy vân dựa trên miền dữ liệu. ................................................ 76 3.1.2.2. Thủy vân dựa trên miền tần số: ................................................. 77 3.1.2.3. Thủy vân dựa trên miền thời gian thực. ..................................... 78 3.1.3. Một thuật toán thủy vân trên audio sử dụng kỹ thuật trải phổ. ......... 79 3.1.3.1. Mô hình giả lập hệ thính giác. ................................................... 79 3.1.3.2. Thuật toán thủy vân. .................................................................. 81 3.2. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN VIDEO. .............. 84 3.3. SỬ DỤNG THỦY VÂN SỐ BẢO VỆ BẢN QUYỀN PHẦN MỀM. ..... 85 CHƢƠNG IV: CHƢƠNG TRÌNH THỬ NGHIỆM. .......................................... 87 4.1. THỦY VÂN HIỆN. ................................................................................ 87 4.1.1. Microsoft Word 2007. ...................................................................... 87 4.1.2. Fast Watermark. ............................................................................... 90 4.1.3. Watermark Master. .......................................................................... 91 4.2. THỦY VÂN ẨN. .................................................................................... 92 4.2.1. Sử dụng chƣơng trình. ...................................................................... 92 4.2.2. Một số kết quả thử nghiệm. .............................................................. 95 4.2.3. Thử nghiệm các phép tấn công. ........................................................ 99 4.2.1.1. Phép co hình. ........................................................................... 99 4.2.1.2. Nén ảnh JPEG. ....................................................................... 101 4.2.1.3. Phép xoay ảnh. ........................................................................ 101 4.2.1.4. Phép cắt ảnh. ........................................................................... 102 4.2.1.5. Thực hiện thủy vân lên một ảnh đã đƣợc thủy vân. ................. 103 KẾT LUẬN ..................................................................................................... 104 PHỤ LỤC ....................................................................................................... 105 TÀI LIỆU THAM KHẢO ............................................................................... 107 DANH MỤC CÁC HÌNH VẼ TRONG KHÓA LUẬN: Hình 1. Sơ đồ hệ mã hóa DES ........................................................................... 10 Hình 2. Thủy vân trên đồng dollar của Mỹ ........................................................ 19 Hình 3. Số lƣợng các bài báo nghiên cứu về thủy vân số trong cơ sở dữ liệu của IEEE .......................................................................................................................... 23 Hình 4. Một số phƣơng pháp phân loại thủy vân tiêu biểu ................................. 27 Hình 5. Quy trình thực hiện thủy vân ................................................................ 28 Hình6. Sơ đồ khối một hệ thống nén ảnh điển hình ........................................... 38 Hình 7. Sơ đồ mã hóa và giải mã dùng biến đổi DCT ........................................ 39 Hình 8. Các bƣớc của quá trình mã hóa biến đổi DCT đối với một khối ............ 40 Hình 9. Ma trận lƣợng tử ................................................................................... 41 Hình 10. Cây mã Huffman. ............................................................................... 44 Hình 11. Bảng zigzag của các thành phần ảnh JPEG ......................................... 46 Hình 12. Lấy tổ hợp các điểm ảnh lân cận. ........................................................ 53 Hình 12. Biến đổi Fourier cho một tín hiệu........................................................ 57 Hình 13. Mô hình nhúng thủy vân của Cox. ...................................................... 64 Hình 14. Biến đổi DWT ba mức ........................................................................ 66 Hình 15. Thủy vân tín hiệu bằng điều biến cơ số thời gian. ............................... 78 Hình 16. Sự sai khác thời gian của tín hiệu gốc và tín hiệu đã nhúng thủy vân .. 78 Hình 17. Mô hình giả lập hệ thính giác. ............................................................. 79 Hình 18. Thành phần tín hiệu sau khi thủy vân. ................................................. 81 Hình 19. Sơ đồ tạo thủy vân .............................................................................. 81 Hình 20. Sơ đồ nhúng thủy vân. ........................................................................ 82 Hình 21. Sơ đồ tách thủy vân............................................................................. 83 Hình 22. Thủy vân hiện trên góc trái của hình ảnh truyền hình .......................... 84 Hình 23. Chọn chức năng Watermark trong Word 2007 .................................... 88 Hình 24. Cửa sổ Custom watermark. ................................................................. 89 Hình 26. Ví dụ chèn thủy vân bằng Microsoft Word 2007. ................................ 89 Hình 27. Giao diện phần mềm Fast Watermark. ................................................ 90 Hình 28. Giao diện phần mềm Watermark Master ............................................. 91 Hình 27. Các tham số của câu lệnh gen_cox_sig ............................................... 93 Hình 28. Ảnh lena ............................................................................................. 95 Hình 29. Ảnh sau khi đƣợc nhúng thủy vân bằng thuật toán Cox với tham số tạo thủy vân mặc định. ..................................................................................................... 96 Hình 30. So sánh ảnh trƣớc và sau khi nhúng thủy vân ...................................... 97 Hình 31. Ảnh sau khi đƣợc nhúng thủy vân bằng thuật toán của Corvi với tham số tạo thủy vân mặc định ........................................................................................... 98 Hình 32. Ảnh sau khi đã đƣợc nhúng thủy vân và thay đổi kích thƣớc. .............. 99 Hình 33. Ảnh sau khi phục hồi lại kích thƣớc gốc. .......................................... 100 Hình 34. Ảnh sau khi nén JPEG với chất lƣợng 10%. ...................................... 101 Hình 35. Ảnh nhúng thủy vân và bị cắt............................................................ 102 Hình 36. Ảnh sau khi đƣợc nhúng thêm thủy vân 2 lần liên tiếp. ..................... 103 DANH MỤC CÁC BẢNG BIỂU TRONG KHÓA LUẬN: Bảng 1. Cấu trúc định dạng ảnh BMP ................................................................ 29 Bảng 2. Định dạng tổng quát ảnh GIF ............................................................... 33 Bảng 3. Cấu trúc khối bản đồ màu tổng thể ảnh GIF ......................................... 34 Bảng 4. Cấu trúc bộ mô tả ảnh GIF ................................................................... 35 Bảng 5. Bảng tần suất ký tự. .............................................................................. 43 Bảng 6. Bảng từ mã gán cho các ký tự bởi mã hoá Huffman. ............................ 45 Bảng 7. So sánh một số định dạng ảnh nén. ....................................................... 48 BẢNG VIẾT TẮT THUẬT NGỮ: Từ viết tắt Thuật ngữ tiếng Anh Thuật ngữ tiếng Việt DFT Discrete Fourier Transform Biến đổi Fourier rời rạc DCT Discrete Cosine Transform Biến đổi Cosine rời rạc DWT Discrete Wavelet Transform Biến đổi sóng con rời rạc IDFT Inverse Discrete Fourier Transform PCA Pricipal Component Analysis Phân tích các thành phần quan trọng LSB Least Significant Bit Bit ít quan trọng nhất Biến đổi Fourier rời rạc ngƣợc LỜI CẢM ƠN Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành và sâu sắc nhất tới PGS.TS Trịnh Nhật Tiến, ngƣời thầy đã trực tiếp hƣớng dẫn tôi hoàn thành khóa luận này. Tôi cũng xin cảm ơn các thầy, cô giáo của Khoa Công nghệ Thông tin, Trƣờng Đại học Công nghệ, Đại học Quốc gia Hà Nội đã tận tình dạy dỗ, chỉ bảo tôi trong suốt những năm học ở trƣờng. Tôi xin gửi lời cảm ơn tới gia đình, chính là nguồn lực động viên tôi phấn đấu trong học tập và cuộc sống. Tôi cũng xin gửi lời cảm ơn tới các bạn sinh viên trong lớp K50CA, cũng nhƣ lớp K50 Các Hệ thống thông tin, Khoa Công nghệ Thông tin, Trƣờng Đại học Công nghệ, Đại học Quốc gia Hà Nội đã cho tôi một môi trƣờng rất tốt để học tập và nghiên cứu. Cuối cùng, tôi xin gửi lời cảm ơn tới PGS.TS Hà Quang Thụy, cũng nhƣ các anh chị trong phòng thí nghiệm SISLab, Trƣờng Đại học Công nghệ, đã dạy tôi rất nhiều điều quý giá về nghiên cứu khoa học. Hà Nội, ngày 10 tháng 5 năm 2009. MỞ ĐẨU Bƣớc vào thế kỷ XXI, loài ngƣời đã chứng kiến một cuộc bùng nổ thật sự, sau cuộc cách mạng phát minh ra máy tính điện tử, đó là Internet. Chỉ trong vòng có vài năm ngắn ngủi, Internet đã nhanh chóng len lỏi vào từng ngóc ngách của đời sống, và càng ngày càng đóng những vai trò quan trọng trong cuộc sống của con ngƣời. Từ khi loài ngƣời bƣớc ra khỏi thời kỳ công xã nguyên thủy, và chủ nghĩa cá nhân xuất hiện, thì nhu cầu bảo vệ dấu ấn cá nhân trong cộng đồng ngày càng trở nên bức bách. Các nghệ sỹ đua nhau sáng tạo ra những trƣờng phái mới, chỉ với mục đích làm cho tác phẩm của mình không bị lẫn lộn với những tác phẩm của ngƣời khác. Những ngƣời giàu có sẵn sàng bỏ ra nhiều triệu đô la, chỉ để sở hữu một chiếc điện thoại di động không có gì độc đáo về mặt tính năng nhƣng là duy nhất trên thế giới. Bƣớc vào thời kỳ kinh tế tri thức, khi tri thức ngày càng trở nên đắt giá, đồng thời với đó, các tài liệu đƣợc lƣu ở dạng số hóa ngày càng nhiều và phổ biến, thì vấn đề bảo vệ bản quyền cho tri thức của con ngƣời ngày càng trở nên quan trọng, bởi những đặc trƣng sau của tài liệu số: Dễ dàng sao chép: nhờ sự phát triển của máy vi tính, các tài liệu số hóa có thể đƣợc sao chép một cách đơn giản và nhanh chóng. Chỉ cần một vài thao tác đơn giản, nhƣ click chuột, một cuốn tiểu thuyết dày hàng nghìn trang, hay một tác phẩm trị giá nhiều triệu đô la của danh họa Picasso có thể đƣợc sao chép chỉ trong vài giây. Điều quan trọng hơn nữa là khi sao chép tài liệu số thì chất lƣợng bản sao chép đƣợc giữ nguyên so với bản gốc. Dễ dàng phát tán: những năm gần đây, Việt Nam chứng kiến cuộc chay đua về nâng cấp hạ tầng đƣờng truyền Internet giữa các nhà cung cấp dịch vụ. Điều này giúp cho khách hàng có đƣợc dịch vụ tốt hơn, nhƣng đồng nghĩa với đó là việc phát tán thông tin cũng nhƣ tài liệu qua mạng Internet càng trở nên dễ dàng hơn bao giờ hết. Ngày nay, chỉ sau vài phút tìm kiếm trên mạng, ngƣời sử dụng có thể dễ dàng tìm và tải về những bộ phim mới nhất còn chƣa đƣợc trình chiếu ở rạp. Cùng với đó, một ngƣời sử dụng bình thƣờng có thể trở thành một nguồn phát tán tài liệu cũng rất dễ dàng, thông qua các tin nhắn tức thời (IM – Instant Message), email hay các dịch vụ chia sẻ file trực tuyến (online file sharing service). Điều này có thể gây nên một hiệu ứng lan truyền nhƣ hiệu ứng virus, khiến tài liệu đƣợc phát tán nhanh và rộng khắp. Ví dụ, đoạn clip về Susan Boyle đƣợc đƣa lên mạng vào tháng 4.2009 vừa qua đã đạt đƣợc hơn 200 triệu ngƣời xem chỉ trong có 2 tuần. 1 Dễ dàng lƣu trữ: dung lƣợng ổ cứng ngày càng lớn, giá thành các thiết bị lƣu trữ ngày càng rẻ đã khiến cho việc lƣu trữ các tài liệu số hóa trở nên đơn giản hơn bao giờ hết. Một chiếc đĩa CD mà giờ đây ngày càng trở nên lỗi thời, đã có thể chứa hàng trăm cuốn sách điện tử. Một thiết bị nghe nhạc MP3 giá vài trăm nghìn đồng có thể lƣu đƣợc hàng vạn bài hát. Những ổ cứng với dung lƣợng lên tới hàng trăm GB, thậm chí hàng TB khiến cho một máy tính cá nhân dễ dàng biến thành một rạp chiếu phim. Tất cả những điều đó đã khiến cho việc lƣu trữ các tài liệu số hóa trở nên dễ dàng hơn bao giờ hết. Ở Việt Nam, tình hình vi phạm bản quyền vẫn đang diễn biến rất nghiêm trọng, mặc dù đã có sự cố gắng của nhiều cơ quan chức năng, cũng nhƣ của cộng đồng. Tình trạng sử dụng phần mềm không có bản quyền, download những file video lậu trên các trang web chia sẻ file, tìm nghe những album mới nhất trên những diễn đàn mà không muốn mua đĩa, v.v… là những hiện tƣợng hết sức phổ biến. Để đảm bảo cho nhu cầu giữ bí mật thông tin liên lạc cũng nhƣ đảm bảo an toàn dữ liệu, từ lâu con ngƣời đã phát minh ra một công cụ hết sức hiệu quả, đó là mã hóa. Mã hóa là một công cụ mạnh, và có lịch sử lâu đời, đã có nhiều kết quả nghiên cứu thành công và có ứng dụng rất lớn trong việc đảm bảo an toàn thông tin liên lạc. Tuy nhiên, mã hóa gặp phải một vấn đề rất lớn, đó là bản thân công cụ mã hóa không gắn liền với tài liệu đƣợc bảo vệ, mà chỉ nhƣ một dạng vỏ bọc (cover) của tài liệu mà thôi. Do đó, mã hóa không thể đƣợc sử dụng nhƣ là một công cụ an toàn để bảo vệ bản quyền tài liệu số khi phát hành trên mạng, vì sau khi kẻ gian đã giải mã đƣợc tài liệu, thì có toàn quyền đối với tài liệu đó. Thủy vân (watermarking) là một ứng dụng đã có từ lâu đời để bảo vệ bản quyền cho các cuốn sách. Tuy nhiên, thủy vân số (digital watermarking) lại là một lĩnh vực mới, đang nhận đƣợc nhiều sự quan tâm cũng nhƣ nghiên cứu của chuyên gia trên thế giới. Sử dụng thủy vân số có thể thay đổi và tác động vào chất lƣợng của tài liệu số nhƣ ý muốn, đồng thời với đó là thủy vân số có thể gắn liền với tài liệu, đảm bảo tài liệu đƣợc bảo vệ bản quyền cho tới khi bị hủy hoại. Trong nội dung khóa luận này, tôi xin tập trung trình bày những kết quả nghiên cứu đã đạt đƣợc trong việc ứng dụng thủy vân số để bảo vệ bản quyền tài liệu điện tử, đặc biệt là ảnh số. Ngoài ra khóa luận cũng trình bày những ứng dụng của thủy vân số trong việc bảo vệ bản quyền tài liệu một số file đa phƣơng tiện khác, nhƣ audio hay video, cũng là những vấn đề đang rất đƣợc quan tâm hiện nay. 2 Chƣơng 1: CÁC KHÁI NIỆM CƠ BẢN 1.1. KHÁI NIỆM TRONG TOÁN HỌC. 1.1.1.Khái niệm trong số học. 1.1.1.1. Tính chia hết, quan hệ đồng dư và số nguyên tố. 1/.Tính chia hết. Xét 2 số nguyên a và b. Ta gọi a chia hết cho b   số nguyên n thỏa mãn a=b*n. Khi đó a đƣợc gọi là bội số của b, b đƣợc gọi là ƣớc số của a. Ký hiệu a|b. a đƣợc gọi là chia cho b dƣ r   số nguyên k và r thỏa mãn a = k.b + r. Khi đó r gọi là số dƣ của phép chia a cho b. Xét dãy số (a1,a2, …, an). Nếu b là ƣớc số chung của tất cả các số trong dãy số trên, và tất cả các ƣớc số chung khác của dãy đều là ƣớc số của b, thì ta gọi b là ƣớc số chung lớn nhất của dãy. Ký hiệu b = USCLN (a1,a2, …, an) = gcd (a1,a2, …, an). Nếu b là bội số chung của tất cả các dãy trong dãy số trên, và tất cả các bội số chung khác của dãy đều là bội số của b, thì ta gọi b là bội số chung nhỏ nhất của dãy. Ký hiệu b = BSCNN (a1,a2, …, an) = lcm (a1,a2, …, an). Ta có: gcd (a, b) = 1  a và b nguyên tố cùng nhau. 2/.Quan hệ đồng dƣ. a và b đồng dƣ theo modulo n  (a - b)|r. Ký hiệu a  b (mod n). 3/.Số nguyên tố. Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Các số tự nhiên không phải là số nguyên tố thì gọi là hợp số. Số nguyên tố đóng một vai trò rất quan trọng trong lĩnh vực an toàn thông tin. 3 Số lƣợng các số nguyên tố là vô hạn, đồng thời cho đến nay ngƣời ta vẫn chƣa tìm ra đƣợc quy luật của dãy số nguyên tố. Số nguyên tố đã đƣợc nghiên cứu từ trƣớc Công nguyên. Hiện nay, đã có rất nhiều thuật toán đƣợc nghiên cứu nhằm xác định một số có phải là số nguyên tố hay không. Gần đây nhất, vào tháng 8 năm 2008, đã tìm ra số nguyên tố có gần 13 triệu chữ số, là một số nguyên tố dạng Mersenne. 1.1.1.2. Không gian Zn và cấu trúc nhóm. 1/.Không gian Zn và các phép tính cơ bản: Zn đƣợc định nghĩa là tập hợp các số tự nhiên nhỏ hơn n. Zn = {1, 2, … n - 1}. Zn* đƣợc định nghĩa là tập hợp các số tự nhiên nhỏ hơn n và nguyên tố cùng nhau với n. Zn* = {x|x  N, x < n, gcd (x, n) = 1}. Trong không gian Zn, các phép toán đều đƣợc thực hiện theo modulo n. Phép cộng, phép trừ và phép nhân đƣợc thực hiện bình thƣờng nhƣ trong không gian Z, tuy nhiên kết quả cuối cùng phải đƣợc tính lại theo modulo n. Phép chia trong không gian Zn liên quan tới khái niệm phần tử nghịch đảo. Phần tử nghịch đảo của a  Znđịnh nghĩa là b  Zn thỏa mãn a.b=1(mod n), ký hiệu b = a-1(mod n). Vì vậy, phép chia a cho b trong không gian Zn chỉ có nghĩa nếu b có phần tử nghịch đảo, bởi vì a/b = a.b-1. 2/.Cấu trúc nhóm: Nhóm là một bộ hai phần tử (G, *), trong đó G là tập hợp khác rỗng, * là phép toán hai ngôi thỏa mãn: - Tính kết hợp: (a * b) * c = a * (b * c)  a,b,c  G. - Tồn tại phần tử trung lập e  G thỏa mãn: e * x = x * e = e  x  G. -  x  G,  phần tử nghịch đảo x‟ của x thỏa mãn: x * x‟ = x‟ * x = e. 4 Nhóm con của nhóm (G, *) là nhóm (S, *) thỏa mãn: - S  G. - Phần tử trung lập e của G nằm trong S. - S khép kín đối với phép * và lấy nghịch đảo trong G. Nhóm đƣợc gọi là nhóm cyclic nếu nó đƣợc sinh ra từ một trong các phần tử của nó. Phần tử đó gọi là phần tử nguyên thủy. 1.1.1.3. Dãy số giả ngẫu nhiên. Khái niệm “ngẫu nhiên” đóng một vai trò hết sức quan trọng trong đời sống và trong lĩnh vực an toàn thông tin. Một dãy bit đƣợc coi là ngẫu nhiên hoàn toàn, tức là nếu ta biết toàn bộ các bit từ 0 tới bit n, thì ta cũng không có thêm thông tin gì để đoán nhận bit n+1 là 0 hay 1. Nhƣ vậy, ta không có cách nào đoán nhận một dãy bit là ngẫu nhiên hay không, vả lại, trong máy tính, ta bắt buộc phải sinh ra dãy bit theo một số hữu hạn các quy tắc nào đó, thì không thể coi là ngẫu nhiên đƣợc nữa. Vì vậy, trong thực tế, chúng ta chỉ có thể sử dụng các dãy số giả ngẫu nhiên (pseu-random number) mà thôi. Các chuỗi giả ngẫu nhiên đƣợc hiểu là, nếu ta biết các bit từ 0 tới n, thì vẫn “khó” đoán đƣợc bit n+1. Một số thuật toán sinh dãy số giả ngẫu nhiên nhƣ thuật toán sinh dãy giả ngẫu nhiên RSA, thuật toán Blum Blum Shud, v.v… 1.1.2. Khái niệm độ phức tạp thuật toán. Thuật toán đƣợc định nghĩa là một dãy hữu hạn các chỉ thị mô tả một quá trình tính toán nào đó. Một bài toán đƣợc gọi là “giải đƣợc” nếu tồn tại một thuật toán giải quyết bài toán đó. Ngƣợc lại bài toán gọi là “không giải đƣợc”. Tuy nhiên, không phải bài toán nào thuộc lớp bài toán “giải đƣợc” cũng có thể giải đƣợc trong thực tế. Do đó, ngƣời ta đƣa ra khái niệm chi phí để giải một bài toán, chi phí này liên quan mật thiết tới thuật toán giải bài toán đó, phụ thuộc vào bốn tiêu chí sau: 5  Thuật toán có dễ hiểu không.  Thuật toán có dễ cài đặt không.  Số lƣợng bộ nhớ cần sử dụng.  Thời gian thực hiện chƣơng trình. Trong các tiêu chí đó, tiêu chí thời gian thực hiện đƣợc đánh giá là quan trọng nhất. Độ phức tạp thời gian của thuật toán, thƣờng đƣợc hiểu là số các phép tính cơ bản mà thuật toán phải thực hiện, trong trƣờng hợp xấu nhất. Với cỡ dữ liệu đầu vào là n, thời gian thực hiện thuật toán là t(n) đƣợc gọi là tiệm cận tới hàm f(n) nếu với n đủ lớn thì tồn tại số c thỏa mãn t(n)  c.f(n). Nếu f(n) là một hàm đa thức thì thuật toán đƣợc gọi là có độ phức tạp thời gian đa thức. Hiện nay, hầu hết các bài toán giải đƣợc trong thực tế đều là các bài toán có độ phức tạp thời gian đa thức. Các bài toán có độ phức tạp số mũ thực tế là khó thể giải đƣợc (có thể mất nhiều triệu tới nhiều tỷ năm). Lý thuyết độ phức tạp tính toán là lý thuyết quan trọng của khoa học máy tính. Nó cũng là cơ sở cho các phép toán gần đúng và xấp xỉ, hiện đang có nhiều ứng dụng trong khoa học. Từ lý thuyết độ phức tạp tính toán, xuất hiện một khái niệm rất quan trọng trong lĩnh vực an toàn thông tin: hàm một phía và hàm một phía có cửa sập. Hàm một phía (one way function): hàm số y = f(x) đƣợc gọi là hàm một phía, nếu khi biết giá trị của x thì ta dễ dàng tính đƣợc giá trị của y, nhƣng ngƣợc lại, nếu biết giá trị của y, ta “khó” tính đƣợc giá trị của x. Hàm một phía có cửa sập (trapdoor one way function): hàm một phía có cửa sập là hàm một phía, mà nếu biết “cửa sập” thì ta có thể dễ dàng tính ra giá trị của x khi biết giá trị của y. 6 1.2. KHÁI NIỆM MÃ HÓA. 1.2.1. Hệ mã hóa. Mã hóa đƣợc hiểu là thay đổi hình dạng thông tin gốc, khiến ngƣời khác “khó” nhận ra, tức là giấu đi ý nghĩa của thông tin gốc. Hệ mã hóa đƣợc định nghĩa là bộ năm phần tử (P, C, K, E, D) trong đó:  P là tập hữu hạn các bản rõ có thể.  C là tập hữu hạn các bản mã có thể.  K là tập hữu hạn các khóa có thể.  E là tập các hàm mã hóa.  D là tập các hàm giải mã. Với khóa lập mã ke  K, có hàm lập mã eke  E, eke: P → C. Với khóa giải mã kd  K, có hàm giải mã dkd  D, dkd: C → P. Thỏa mãn: dkd(eke(x)) = x,  x  P. Năm 1949, Claude Shannon (1916 - 2001) đã đƣa ra khái niệm hệ mã hóa an toàn tuyệt đối. Theo Shannon, một hệ mã hóa đƣợc coi là an toàn tuyệt đối khi biết đƣợc bản mã sẽ không cung cấp thêm thông tin gì về bản rõ. Nói một cách khác, bản mã và bản rõ là độc lập với nhau. Thông thƣờng, khi nghiên cứu các hệ mã hóa, ngƣời ta coi rằng bản mã đƣợc truyền trên đƣờng truyền không an toàn, và thuật toán mã hóa đã đƣợc công khai. Căn cứ theo đặc trƣng của khóa, hiện nay mã hóa đƣợc chia làm hai loại mã hóa chính là mã hóa khóa đối xứng và mã hóa khóa công khai. 7 1.2.2. Mã hóa khóa đối xứng. Mã hóa khóa đối xứng là hệ mã hóa mà nếu biết đƣợc khóa lập mà thì ta dễ dàng tính đƣợc khóa giải mã, và ngƣợc lại. Hệ mã hóa khóa đối xứng còn đƣợc gọi là hệ mã hóa khóa bí mật, hay hệ mã hóa khóa riêng. Đặc trƣng của hệ mã hóa khóa đối xứng:  Khóa phải đƣợc thỏa thuận và giữ bí mật giữa hai bên truyền tin. Khóa phải đƣợc truyền trên kênh an toàn giữa hai bên truyền tin. Điều này làm phức tạp quá trình thiết lập khóa. Hơn nữa, nếu giữa hai bên truyền tin không có kênh an toàn nào thì không thể thiết lập đƣợc quá trình truyền tin.  Nếu bên tấn công biết đƣợc khóa giải mã thì hệ mã hóa sẽ không còn bí mật.  Tốc độ tính toán nhanh. Một số hệ mã hóa khóa đối xứng điển hình: Các hệ mã hóa khóa đối xứng đƣợc chia thành hai loại lớn, đó là mã hóa khóa đối xứng cổ điển và mã hóa khóa đối xứng hiện đại. Mã hóa khóa đối xứng hiện đại chủ yếu sử dụng các khối lƣợng tính toán lớn nhờ vào sức mạnh tính toán của máy tính. 1/.Hệ mã hóa dịch chuyển: Mã hóa dịch chuyển (shift cipher) là hệ mã hóa khóa đối xứng cổ điển nhất còn đƣợc biết cho tới nay. Mã hóa dịch chuyển mã hóa trên từng ký tự, hay còn đƣợc biết với cái tên mã hóa dòng (stream cipher). Bản mã là tập hợp các ký tự đã đƣợc mã hóa. Tập bản rõ và tập bản mã là giống nhau, là các chữ cái trong bảng chữ cái. Mã hóa dịch chuyển có khóa lập mã và khóa giải mã giống nhau, là một số trong Zn với n là số lƣợng các ký tự có thể của bảng chữ cái (với tiếng Anh thì n = 26, với tiếng Việt thì n = 89, v.v…). Hàm lập mã cho ký tự rõ x với khóa k nhƣ sau: ek(x) = (x + k) mod n. Hàm giải mã cho ký tự mã x‟ với khóa k nhƣ sau: ek(x‟) = (x „– k) mod n. Tƣơng truyền rằng, hệ mã hóa dịch chuyển với khóa k = 3 đã đƣợc Julius Caesar (100TCN – 44TCN) sử dụng để truyền tin trong quân đội. 8 Độ an toàn của hệ mã hóa dịch chuyển là thấp, bởi chỉ có (n - 1) khóa có thể. Hệ mã hóa dịch chuyển có thể dễ dàng bị phá bằng phƣơng pháp thủ công theo nguyên tắc “thử và sai”. 2/.Hệ mã hóa thay thế: Hệ mã hóa thay thế (subsitution cipher) cũng là hệ mã hóa từng ký tự. Tập bản rõ và tập bản mã cũng giống nhau, là tập các ký tự trong bảng chữ cái. Tập các khóa có thể có là mọi hoán vị của Zn, với n là số lƣợng ký tự trong bảng chữ cái. Hàm lập mã: ek(x) =  )x( . Hàm giải mã: ek(x) =  -1 )x( . Số lƣợng khóa của hệ mã hóa thay thế là n!, là một con số rất lớn (26! > 1026) so với các phƣơng pháp tấn công vét cạn cổ điển. Tuy nhiên hệ mã hóa thay thế thƣờng bị tấn công dựa vào phân tích đặc trƣng ngôn ngữ. 3/.Hệ mã hóa Vigerene: Hệ mã hóa Vigenere khác với hai hệ mã hóa trình bày ở trên vì nó là hệ mã hóa khối (block cipher), mã hóa từng khối ký tự liên tục có chiều dài cố định. P = C = K = (Zn)m. Bản rõ x = (x1,x2 … xm). Khóa k = (k1,k2 … km). Mã hóa: y = (y1,y2 … yn) = x + k = (x1 + k1, x2 + k2, …, xn + kn) với lƣu ý rằng các phép toán đƣợc thực hiện trong không gian Zn. Giải mã: x = y – k. Mã hóa Vigenere quan trọng, bởi vì mã hóa Vigenere là hệ mã hóa an toàn tuyệt đối theo định nghĩa của Shannon, nếu chiều dài khóa không nhỏ hơn chiều dài văn bản, và các phần tử của khóa là ngẫu nhiên và độc lập hoàn toàn. Ngoài ra, hệ mã hóa khóa đối xứng cổ điển còn một vài hệ mã hóa khác nhƣ hệ mã hóa Affine, mã hóa Hill, mã hóa hàng rào, mã hóa Playfair, v.v…. 4/.Hệ mã hóa DES: 9