Luận văn Nghiên cứu một số khả năng phát hiện tin giấu trong môi trường ảnh

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ MAI THÀNH HUYÊN NGHIÊN CỨU MỘT SỐ KHẢ NĂNG PHÁT HIỆN TIN GIẤU TRONG MÔI TRƯỜNG ẢNH Ngành : Công nghệ thông tin Chuyên ngành : Hệ thống thông tin Mã số : 60 48 05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. TRỊNH NHẬT TIẾN HÀ NỘI - 2009 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các dữ liệu, kết quả nêu trong luận văn là trung thực và chưa từng được công bố trong bất kỳ công trình nào khác. Hà nội, tháng 11 năm 2009 Tác giả luận văn Mai Thành Huyên LỜI CẢM ƠN Tôi xin chân thành cảm ơn các Thầy, Cô giáo trong khoa Công nghệ thông tin và các cán bộ, nhân viên các phòng Đào tạo Sau đại học, trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã luôn nhiệt tình giúp đỡ và tạo điều kiện tốt nhất cho tôi trong suốt quá trình học tập tại trường. Xin chân thành cảm ơn các anh, các chị và các bạn học viên lớp Cao học K12T3 - trường Đại học Công nghệ thuộc Đại học Quốc gia Hà Nội đã luôn động viên, giúp đỡ và nhiệt tình chia sẻ với tôi những kinh nghiệm học tập, công tác trong suốt khoá học. Đặc biệt tôi xin bày tỏ lòng biết ơn sâu sắc đến PGS.TS. Trịnh Nhật Tiến đã tận tình giúp đỡ tôi hình thành, nghiên cứu và hoàn chỉnh luận văn. Mặc dù đã có nhiều cố gắng, song do sự hạn hẹp về thời gian, điều kiện nghiên cứu và trình độ, luận văn không tránh khỏi những khiếm khuyết. Tôi chân thành mong nhận được sự đóng góp ý kiến của các thầy, cô giáo và đồng nghiệp gần xa. Hà Nội, tháng 11 năm 2009 Người thực hiện luận văn Mai Thành Huyên MỤC LỤC LỜI CAM ĐOAN ..............................................................................................................ii LỜI CẢM ƠN ...................................................................................................................iii MỤC LỤC..........................................................................................................................iv Chương 1. TỔNG QUAN VỀ GIẤU TIN TRONG ẢNH ...........................................1 1.1 MỘT SỐ KHÁI NIỆM CƠ BẢN ............................................................................1 1.1.1 Khái niệm giấu tin .......................................................................................1 1.1.2 Phân loại các kỹ thuật giấu tin .....................................................................1 1.1.3 Sơ lược về lịch sử giấu tin ...........................................................................2 1.1.4 Mô hình cơ bản của kỹ thuật giấu tin...........................................................3 1.1.5 Các ứng dụng của kỹ thuật giấu tin..............................................................5 1.2 GIẤU THÔNG TIN TRONG DỮ LIỆU ĐA PHƯƠNG TIỆN ...........................6 1.2.1 Giấu tin trong ảnh........................................................................................6 1.2.2 Giấu tin trong audio ....................................................................................6 1.2.3 Giấu tin trong video ....................................................................................7 1.2.4 Giấu tin trong văn bản .................................................................................7 1.3 NHỮNG ĐẶC TRƯNG VÀ TÍNH CHẤT CỦA GIẤU TIN TRONG ẢNH ......8 1.4 CÁC HƯỚNG TIẾP CẬN CỦA KỸ THUẬT GIẤU TIN TRONG ẢNH.........10 1.4.1 Tiếp cận trên miền không gian ảnh ............................................................10 1.4.2 Tiếp cận trên miền tần số ảnh ....................................................................10 1.5 MỘT SỐ PHƯƠNG PHÁP GIẤU TIN MẬT TRONG ẢNH ............................12 1.5.1 Giấu tin mật trong khối bit sử dụng tính chẵn lẻ của tổng số bit 1..............12 1.5.2 Kỹ thuật giấu tin Wu _ Lee .......................................................................17 1.5.3 Kỹ thuật giấu tin Yuan_Pan_Tseng ...........................................................23 1.6 KỸ THUẬT THỦY VÂN TRÊN ẢNH .................................................................32 1.6.1 Một số khái niệm cơ bản trong thủy vân số ...............................................32 1.6.2 Một số kỹ thuật thủy vân trên ảnh .............................................................36 Chương 2. MỘT SỐ KHẢ NĂNG PHÁT HIỆN ẢNH CÓ GIẤU TIN .................55 2.1 PHƯƠNG PHÁP PHÁT HIỆN ẢNH GIẤU TIN ..............................................55 2.1.1 Bài toán phân tích tin giấu.........................................................................56 2.1.2 Phân loại phương pháp phát hiện ảnh giấu tin ...........................................57 2.2 Cơ sở toán học ........................................................................................................58 2.2.1 Các khái niệm ...........................................................................................58 2.2.2 Các định lý ................................................................................................62 2.3 KỸ THUẬT PHÂN TÍCH CẶP GIÁ TRỊ ĐIỂM ẢNH......................................63 2.3.1 Khái niệm cặp giá trị .................................................................................63 2.3.2 Thuật toán PoV3 .......................................................................................64 2.4 KỸ THUẬT PHÂN TÍCH ĐỐI NGẪU ................................................................69 2.4.1 Các khái niệm ...........................................................................................69 2.4.2 Thuật toán RS (Regular – Singular)...........................................................71 2.5 KỸ THUẬT PHÂN TÍCH CẶP MẪU SPA .........................................................76 2.5.1 Các khái niệm ...........................................................................................76 2.5.2 Phát hiện giấu tin mật LSB nhờ kỹ thuật SPA ...........................................79 2.5.3 Phân tích kỹ thuật SPA..............................................................................81 2.5.4 Ước lượng độ chính xác của chiều dài thông điệp dấu theo SPA ...............84 2.6 KỸ THUẬT PHÂN TÍCH ĐỘ LỆCH CHUẨN ..................................................91 2.7 KỸ THUẬT THỐNG KÊ  – BÌNH PHƯƠNG MỘT BẬC TỰ DO ..............94 Chương 3. THỬ NGHIỆM ............................................................................................97 3.1 MÔI TRƯỜNG CÀI ĐẶT .....................................................................................97 3.2 MÔ HÌNH HỆ THỐNG ........................................................................................97 3.3 TẬP DỮ LIỆU ẢNH..............................................................................................99 3.4 KẾT QUẢ THỬ NGHIỆM KỸ THUẬT PoV3 .................................................101 KẾT LUẬN.....................................................................................................................107 TÀI LIỆU THAM KHẢO ............................................................................................108 1 Chương 1. TỔNG QUAN VỀ GIẤU TIN TRONG ẢNH Giấu tin là một lĩnh vực nghiên cứu rộng. Trong đó môi trường giấu tin phổ biến và được ứng dụng rộng rãi nhất là dữ liệu ảnh. Trong chương này luận văn bình bày tổng quan vấn đề giấu tin, các mô hình giấu tin, các ứng dụng của giấu tin, đồng thời đi sâu vào các kỹ thuật nhằm bảo mật thông tin được giấu. Hầu hết các kỹ thuật giấu tin mật đều tập trung giấu thông tin vào các bit ít quan trong nhất của mỗi điểm ảnh. Phần cuối chương trình bày các kỹ thuật đã được công bố gần đây như giấu tin theo khối bit sử dụng tính chẵn lẻ của tổng số bit 1 trong khối, kỹ thuật Wu_Lee, kỹ thuật Yang_Pan_Tseng. 1.1 MỘT SỐ KHÁI NIỆM CƠ BẢN 1.1.1 Khái niệm giấu tin “Giấu thông tin” gọi tắt là “Giấu tin”, tiếng Hi Lạp là “Steagnography”, tiếng Anh là “Cover Writing”. “Giấu thông tin” là một kỹ thuật nhúng (giấu) một lượng thông tin số nào đó vào trong một đối tượng dữ liệu số khác [2]. Kỹ thuật giấu tin nhằm hai mục đích: một là bảo mật cho dữ liệu được đem giấu, hai là bảo vệ cho chính đối tượng mang tin giấu. Hai mục đích khác nhau này dẫn đến hai kỹ thuật chủ yếu của giấu tin. Đó là giấu tin mật và thủy vân số. Nói chung giấu tin trong đa phương tiện là tận dụng “độ dư thừa” của phương tiện giấu để thực hiện việc giấu tin, mà người ngoài cuộc “khó” cảm nhận được có thông tin giấu trong đó. 1.1.2 Phân loại các kỹ thuật giấu tin Do kỹ thuật giấu tin số mới được hình thành trong thời gian gần đây, nên xu hướng phát triển vẫn chưa ổn định. Có nhiều cách phân loại khác nhau dựa trên những tiêu chí khác nhau. Theo Fabien A.P. Petitcolas đề xuất năm 1999, có thể chia lĩnh vực giấu tin thành hai hướng lớn, đó là giấu tin mật và thủy vân số [6]. Giấu tin mật với mục đích bảo toàn và bảo mật thông tin, tập trung vào các kỹ thuật giấu thông tin, sao cho người khác khó phát hiện việc có tin được giấu; hơn nữa nếu phát hiện có tin giấu thì giải tin cũng khó thực hiện. Bên cạnh đó cũng đặt ra vấn đề về lượng tin được giấu. Thủy vân số lại được chia thành hai hướng nhỏ là thủy vân dễ vỡ và thủy vân bền vững. Trong đó thủy vân dễ vỡ yêu cầu thông tin giấu sẽ bị sai lệch nếu có bất kỳ sự thay đổi vào trên môi trường chứa tin. Thủy vân bền vững quan tâm nhiều đến việc nhúng tin đòi hỏi độ bền cao trước các biến đổi thông thường trên môi trường chứa tin. 2 Hình 1.1 Phân loại các kỹ thuật giấu tin 1.1.3 Sơ lược về lịch sử giấu tin Từ “Steganography” bắt nguồn từ tiếng Hi Lạp. Từ “stegano” trong tiếng Hi Lạp có nghĩa là “covered”, còn “graphien” có nghĩa là “to write”. Như vậy, “steganography” có nghĩa là tài liệu được phủ “covered writing”. Các câu chuyện kể về kỹ thuật giấu thông tin được truyền qua nhiều thế hệ. Có lẽ những ghi chép sớm nhất về kỹ thuật giấu thông điệp thuộc về sử gia Hi Lạp Herodotus. Khi bạo chúa Hi Lạp Histiaeus bị vua Darius bắt giữ ở Susa vào thế kỷ thứ V trước Công nguyên, ông ta đã gửi một thông báo bí mật cho con rể của mình là Aristagoras ở Miletus. Histiaeus đã cạo trọc đầu một nô lệ tin cậy và xăm một thông điệp trên da đầu của anh ta. Khi tóc của người nô lệ mọc ra đủ dài thì người nô lệ được gửi tới Miletus. Một câu chuyện khác về thời Hi Lạp cổ đại cũng do Herodotus ghi lại. Môi trường để ghi văn bản chính là các viên thuốc được bọc trong sáp ong. Demeratus, một người Hi Lạp định báo cho Sparta rằng Xerxes định xâm chiếm Hi Lạp. Để tránh bị phát hiện, anh ta đã bóc lớp sáp ong ra khỏi các viên thuốc và khắc thông báo lên bề mặt các viên thuốc này, sau đó bọc lại các viên thuốc bằng một lớp sáp ong mới. Những viên thuốc mang tin mật đã ngụy trang được để cùng với các viên thuốc thông thường khác và lọt qua mọi sự kiểm soát một cách dễ dàng. Giấu thông tin Information hiding Giấu tin mật Steganography Thủy vân số Watermarking Thủy vân bền vững Robust Copyright Watermarking Thủy vân dễ vỡ Fragile watermarking Thủy vân ẩn Imperceptible watermarking Thủy vân hiện Visble watermarking 3 Mực không màu là phương tiện hữu ích cho bảo mật thông tin trong một thời gian dài. Người Romans cổ đã biết sử dụng những chất sẵn có như nước quả, nước tiểu và sữa viết các thông báo bí mật giữa các hàng văn tự thông thường. Khi được hơ nóng, những thứ mực này trở nên sẫm mầu và có thể đọc được. Mực không màu cũng vẫn còn được sử dụng gần đây, chẳng hạn trong chiến tranh thế giới thứ II [5]. Ý tưởng về che giấu thông tin đã có hàng ngàn năm trước nhưng kỹ thuật này được dùng chủ yếu trong quân đội và trong các cơ quan tình báo. Mãi cho tới vài thập niên gần đây, giấu tin mới nhận được sự quan tâm của các nhà nghiên cứu và các viện công nghệ thông tin với nhiều công trình nghiên cứu. Sự phát triển của thông tin số và mạng truyền thông (đặc biệt là mạng Internet) cùng với các kỹ thuật sao chép hoàn hảo, kỹ thuật chỉnh sửa, thay thế tinh vi đã và đang làm nảy sinh nhiều vấn đề nhức nhối về nạn ăn cắp bản quyền, xuyên tạc trái phép, lan truyền thông tin bất hợp pháp. 1.1.4 Mô hình cơ bản của kỹ thuật giấu tin Mô hình của kỹ thuật giấu tin được mô tả trong hình 1.2 và 1.3. Hình 1.2 Lược đồ chung cho quá trình giấu tin Bộ nhúng thông tin Khóa Thông tin cần giấu Phương tiện chứa tin (audio, ảnh, video,…) Phương tiện chứa đã được giấu tin Phân phối 4 Hình 1.2 biểu diễn quá trình giấu tin cơ bản. Trong đó, phương tiện chứa tin có thể bao gồm: văn bản, ảnh, audio, video… Thông tin cần giấu tùy theo mục đích của người sử dụng, nó có thể là các thông điệp, các logo, hình ảnh bản quyền… Thông tin được giấu vào trong phương tiện chứa tin nhờ môt bộ nhúng. Bộ nhúng là chương trình theo thuật toán giấu tin và được thực hiện với một khóa bí mật giống như trong hệ mật mã. Đầu ra của quá trình giấu tin là phương tiện chứa đã được giấu tin. Các phương tiện này có thể được phân phối trên mạng [7]. Hình 1.3 mô tả quá trình tách tin đã giấu từ môi trường giấu tin. Với đầu vào là phương tiện đã chứa tin giấu, một bộ tách tin (tương ứng với bộ nhúng) cùng với khóa sẽ thực hiện việc tách tin. Đầu ra của quá trình là phương tiện chứa tin và thông tin đã giấu. Trong trường hợp cần thiết, thông tin giấu lấy ra có thể được xử lý, kiểm định và so sánh với thông tin đã giấu ban đầu. Hình 1.3 Lược đồ cho quá trình tách tin Bộ tách tin Khóa Thông tin giấu Phương tiện chứa tin (audio, ảnh, video,…) Phương tiện chứa đã được giấu tin Kiểm định Phân phối Formatted: Left Deleted: giải mã Deleted: t 5 1.1.5 Các ứng dụng của kỹ thuật giấu tin 1.1.5.1 Ứng dụng của thủy vân số * Bảo vệ bản quyền tác giả Đây là ứng dụng cơ bản nhất của kỹ thuật thủy vân số. Một thông tin nào đó mang ý nghĩa quyền sở hữu gọi là thủy vân sẽ được nhúng vào trong sản phẩm. Thủy vân đó chỉ một mình người chủ sở hữu hợp pháp sản phẩm đó có, và được dùng làm minh chứng cho bản quyền sản phẩm. Yêu cầu kỹ thuật đối với ứng dụng này là thủy vân phải tồn tại bền vững cùng sản phẩm, muốn bỏ thủy vân này mà không được phép của người chủ sở hữu, thì chỉ có cách phá hủy sản phẩm [8]. * Xác thực thông tin hay phát hiện xuyên tạc thông tin Một thông tin sẽ được giấu trong phương tiện chứa, sau đó sử dụng để nhận biết xem phương tiện gốc đó có bị thay đổi hay không. Thủy vân nên được ẩn để tránh sự tò mò của kẻ thù, hơn nữa việc làm giả thủy vân hợp lệ hay xuyên tạc thông tin nguồn cũng được xem xét. Trong các ứng dụng thực tế, người ta mong muốn tìm được vị trí bị xuyên tạc cũng như phân biệt được các thay đổi. Yêu cầu chung đối với các ứng dụng là khả năng giấu thông tin cao và thủy vân không cần bền vững. * Giấu vân tay hay dán nhãn Thủy vân trong ứng dụng này được dùng để nhận diện người gửi hay người nhận của một thông tin nào đó. Yêu cầu của ứng dụng này là đảm bảo độ an toàn cao cho thủy vân. * Kiểm soát sao chép: Các thủy vân trong trường hợp này được dùng để kiểm soát sao chép đối với các thông tin. Thiết bị phát hiện ra thủy vân thường được gắn sẵn vào trong hệ thống đọc ghi. Ứng dụng loại này cũng yêu cầu thủy vân phải được đảm bảo an toàn, và cũng sử dụng phương pháp phát hiện thủy vân đã giấu mà không cần thông tin gốc. 1.1.5.2 Ứng dụng của giấu tin mật Thông tin giấu được trong trường hợp này càng nhiều càng tốt, việc tách tin để nhận được tin giấu cũng không cần phương tiện chứa ban đầu. Các yêu cầu mạnh về tính bền vững không cần thiết lắm, thay vào đó là thông tin giấu phải đảm bảo tính bí mật và giảm thời gian lưu thông trên đường truyền. 6 1.2 GIẤU THÔNG TIN TRONG DỮ LIỆU ĐA PHƯƠNG TIỆN 1.2.1 Giấu tin trong ảnh Hiện nay, giấu tin trong ảnh chiếm tỉ lệ lớn nhất trong hệ thống giấu tin. Bởi lẽ lượng thông tin được trao đổi bằng hình ảnh là rất lớn, hơn nữa chúng còn đóng vai trò quan trọng trong các ứng dụng an toàn thông tin như: xác thực thông tin, bảo vệ bản quyền tác giả, điều khiển truy cập, xác định xuyên tạc thông tin. Từ việc nghiên cứu kỹ thuật giấu tin trong ảnh số chuyển sang kỹ thuật giấu tin trong các phương tiện khác như audio, video, trong văn bản,… không có gì khó khăn về nguyên tắc. Chính vì lẽ đó, giấu tin trong ảnh đã và đang được nhiều tổ chức, các trường đại học, các viện nghiên cứu, các cá nhân quan tâm và đầu tư nghiên cứu [12]. Thông tin được giấu vào dữ liệu ảnh, nhưng chất lượng ảnh rất ít thay đổi và người ta khó có thể nhận thấy bằng mắt thường. Sau vụ khủng bố ngày 11 tháng 9 năm 2001 gây chấn động không chỉ nước Mĩ mà cả thế giới, có một số nhận định cho rằng chính trùm khủng bố quốc tế Osama Binladen đã dùng cách thức giấu thông tin trong ảnh để liên lạc với đồng bọn và chúng đã qua mặt được cục tình báo trung ương Mĩ và các cơ quan an ninh quốc tế. Sự việc này cho thấy việc nghiên cứu các vấn đề liên quan đến giấu tin trong ảnh càng trở nên quan trọng. 1.2.2 Giấu tin trong audio Giấu tin trong audio mang những đặc điểm riêng khác với giấu tin trong các đối tượng đa phương tiện khác. Một trong những yêu cầu cơ bản của giấu tin là đảm bảo tính chất ẩn của thông tin được giấu, đồng thời không làm ảnh hưởng đến chất lượng của dữ liệu gốc. Để đảm bảo yêu cầu này, kỹ thuật giấu tin trong audio phụ thuộc vào thính giác con người (HAS - Human Auditory System). HAS nghe được các tín hiệu ở dải tần rộng và công suất cao nhưng ngược lại cũng kém trong việc phát hiện sự khác biệt của các dải tần và công suất. Điều này có nghĩa là các âm thanh to, cao tần có thể che giấu được các âm thanh nhỏ, thấp một cách dễ dàng. Một vấn đề khó khăn nữa của giấu tin trong môi trường audio đó là kênh truyền tin. Kênh truyền hay băng thông chậm sẽ ảnh hưởng đến chất lượng thông tin sau khi giấu. Các phương pháp giấu tin trong audio thường lợi dụng điểm yếu trong hệ thống thính giác con người. 7 1.2.3 Giấu tin trong video Giấu tin trong video cũng được quan tâm phát triển và có nhiều ứng dụng như kiểm soát sao chép thông tin, xác thực thông tin và bảo vệ bản quyền tác giả. Một phương pháp giấu tin được đưa ra bởi Cox là phương pháp phân bố đều. Ý tưởng cơ bản của phương pháp là phân phối thông tin giấu dàn trải theo tần số dữ liệu gốc. Nhiều nhà nghiên cứu đã dùng những hàm cosin riêng và các hệ số truyền sóng riêng để giấu tin. Trong các thuật toán khởi nguồn thì thường các kỹ thuật cho phép giấu các ảnh vào trong video nhưng thời gian gần đây các kỹ thuật cho phép giấu cả âm thanh và hình ảnh vào video [6]. Ví dụ phương pháp của Swanson giấu được hai bit vào khối 8*8 [9]. Gần đây nhất là phương pháp của Mukherjee: giấu audio vào video sử dụng cấu trúc lưới đa chiều… Kỹ thuật giấu thông tin trong video áp dụng cả đặc điểm thị giác và thính giác của con người. Kỹ thuật giấu tin đang được áp dụng với nhiều môi trường không chỉ riêng với dữ liệu đa phương tiện. Gần đây đã có nghiên cứu giấu tin trong văn bản, cơ sở dữ liệu quan hệ và cơ sở dữ liệu XML, cho phép mở ra nhiều hướng nghiên cứu mới. 1.2.4 Giấu tin trong văn bản Trong việc trao đổi thông tin qua hệ thống máy tính, văn bản chiếm một tỷ lệ rất lớn so với các loại phương tiện chứa tin khác. Tuy vậy, giấu tin trong văn bản lại chưa được quan tâm nghiên cứu nhiều. Các nghiên cứu về giấu tin trong văn bản được chia thành hai hướng, thứ nhất là văn bản chứa là những văn bản được chụp lại và lưu trên máy như một ảnh nhị phân. Theo hướng này, kỹ thuật giấu tin được thực hiện như giấu tin trong ảnh nhị phân. Hướng thứ hai, phương tiện chứa sử dụng cho quá trình giấu tin được lưu dưới dạng văn bản. Theo hướng này, các kỹ thuật giấu tin cũng tiến hành như giấu tin trong ảnh bằng cách thay đổi một số ký tự tại một số vị trí trên văn bản mà không làm ảnh hưởng nhiều đến nội dung văn bản gốc. 8 1.3 NHỮNG ĐẶC TRƯNG VÀ TÍNH CHẤT CỦA GIẤU TIN TRONG ẢNH Giấu tin trong ảnh chiếm vị trí chủ yếu trong các kỹ thuật giấu tin. Đối tượng ảnh là một đối tượng dữ liệu tĩnh. Dữ liệu ảnh có nhiều định dạng, mỗi định dạng có những tính chất khác nhau, nên kỹ thuật giấu tin trong ảnh thường chú ý đến những đặc trưng và các tính chất cơ bản sau đây [2, 4]: Phương tiện chứa có dữ liệu tri giác tĩnh Dữ liệu gốc ở đây là dữ liệu ảnh tĩnh, dù đã giấu tin vào trong ảnh hay chưa thì khi ta xem ảnh bằng thị giác, dữ liệu ảnh không thay đổi theo thời gian. Điều này cũng tạo ra sự khác biệt lớn giữa kỹ thuật giấu tin trong ảnh với kỹ thuật giấu tin trong audio hay video. Kỹ thuật giấu phụ thuộc loại ảnh Kỹ thuật giấu tin phụ thuộc vào các loại ảnh khác nhau. Đối với ảnh đen trắng, ảnh xám hay ảnh màu, với mỗi loại ta lại có các kỹ thuật riêng phụ thuộc đặc trưng của ảnh. Kỹ thuật giấu tin lợi dụng tính chất hệ thống thị giác của con người Giấu tin trong ảnh ít nhiều cũng gây ra những thay đổi trên dữ liệu ảnh gốc. Dữ liệu ảnh được quan sát bằng hệ thống thị giác của con người nên các kỹ thuật giấu tin phải đảm bảo một yêu cầu cơ bản là những thay đổi trên ảnh phải rất nhỏ sao cho mắt thường khó nhận ra được sự thay đổi đó, để đảm bảo độ an toàn cho thông tin giấu. Rất nhiều kỹ thuật đã lợi dụng các tính chất của hệ thống thị giác để giấu tin chẳng hạn như mắt người cảm nhận sự biến đổi về độ chói kém hơn sự biến đổi về màu hay cảm nhận của mắt về màu da trời là kém nhất trong ba mầu cơ bản RGB. Giấu thông tin trong ảnh tác động lên dữ liệu ảnh nhưng không thay đổi kích thước ảnh Các thuật toán giấu tin sẽ được thực hiện trên dữ liệu của ảnh. Dữ liệu ảnh bao gồm cả phần đầu, bảng màu (có thể có hoặc không) và dữ liệu ảnh. Khi giấu thông tin, các phương pháp giấu đều biến đổi các giá trị của các bit trong dữ liệu ảnh, chứ không thêm vào hay bớt đi dữ liệu ảnh. Do vậy kích thước ảnh không thay đổi. 9 Đảm bảo chất lượng ảnh sau khi giấu Đây là yêu cầu quan trọng đối với giấu tin trong ảnh. Sau khi giấu tin bên trong, ảnh phải đảm bảo không bị biến đổi. Yêu cầu này dường như khá đơn giản đối với ảnh màu và ảnh đa cấp xám nhưng đối với ảnh đen trắng thì phức tạp hơn nhiều. Bởi vì ảnh đen trắng mỗi điểm ảnh chỉ là đen hoặc trắng, nếu ta biến đổi một bit đen thành trắng hoặc ngược lại thì có thể rất dễ bị phát hiện. Do đó yêu cầu đối với giấu tin trong ảnh màu hay ảnh đa cấp xám và trong ảnh đen trắng là khác nhau. Với ảnh màu thì thuật toán chú trọng vào việc làm sao giấu được càng nhiều thông tin càng tốt, với ảnh đen trắng thuật toán tập trung để làm thế nào thông tin giấu khó bị phát hiện nhất. Thông tin trong ảnh sẽ bị biến đổi nếu có bất cứ biến đổi nào trên ảnh Vì phương pháp giấu tin trong ảnh dựa trên việc điều chỉnh các giá trị của các bit theo một quy tắc nào đó, và khi tách tin sẽ theo các giá trị đó để tìm được thông tin giấu. Theo đó, nếu một phép biến đổi nào đó trên ảnh làm thay đổi giá trị của các bit thì sẽ làm cho thông tin giấu bị sai lệch. Nhờ đặc điểm này, giấu tin trong ảnh có thể xác thực và phát hiện xuyên tạc thông tin [2]. Vai trò của ảnh gốc khi giải tin Kỹ thuật giấu tin phải xác định rõ ràng quá trình lọc ảnh để lấy tin giấu có cần đến ảnh gốc hay không? Đa số các kỹ thuật giấu tin mật thường không cần ảnh gốc khi tách tin. Thông tin được giấu trong ảnh sẽ được mang cùng với dữ liệu ảnh, khi tách tin chỉ cần ảnh đã mang thông tin giấu mà không cần dùng đến ảnh gốc để so sánh, đối chiếu. 10 1.4 CÁC HƯỚNG TIẾP CẬN CỦA KỸ THUẬT GIẤU TIN TRONG ẢNH 1.4.1 Tiếp cận trên miền không gian ảnh Đây là hướng tiếp cận cơ bản và tự nhiên trong số các kỹ thuật giấu tin. Miền không gian ảnh là miền dữ liệu ảnh gốc, tác động lên miền không gian ảnh chính là tác động lên các điểm ảnh, thay đổi giá trị trực tiếp của các điểm ảnh. Đây là hướng tiếp cận tự nhiên bởi vì khi nói đến việc giấu tin trong ảnh người ta thường nghĩ ngay đến việc thay đổi giá trị các điểm ảnh nguồn. Một phương pháp phổ biến của hướng tiếp cận này là phương pháp tác động đến bit ít quan trọng nhất của mỗi điếm ảnh [1]. Ý tưởng cơ bản của phương pháp tác động đến bit ít quan trọng nhất (LSB - Least Significant Bit) của các điểm ảnh là chọn ra từ mỗi điểm ảnh các bit ít có ý nghĩa nhất về mặt tri giác để sử dụng cho việc giấu tin. Việc bit nào được coi là ít tri giác nhất và bao nhiêu bit có thể được lấy ra để thay thế đều phụ thuộc vào tính chất hệ thống thị giác của con người và nhu cầu về chất lượng ảnh trong các ứng dụng. Ví dụ với ảnh mầu, mỗi điểm ảnh được biểu diễn bằng 24 bit tương ứng với ba màu cơ bản RGB, mỗi màu 1 byte. Người ta sử dụng tính chất là mắt người cảm nhận về màu B kém hơn so với màu R và G. Vì thế người ta thường chọn bit cuối cùng trong 8 bit biểu diễn màu B của mỗi điểm ảnh để giấu tin. Thay đổi bit cuối cùng trong 8 bit biểu diễn màu B chỉ làm cho giá trị biểu diễn màu B tăng hoặc giảm đi 1 đơn vị. Như vậy, bit LSB trong ví dụ này là bit thứ 24 của mỗi điểm ảnh. Một số thuật toán muốn giấu nhiều thông tin hơn và chấp nhận chất lượng ảnh thấp hơn một chút có thể sử dụng bít cuối cùng của mỗi byte màu RGB làm bit LSB. Vậy có 3 bit LSB. Tuy nhiên, phương pháp này cũng có nhiều hạn chế, chẳng hạn như không đảm bảo được tính bền vững của thông tin giấu đối với các thao tác biến đổi như quay ảnh hoặc nén ảnh JPEG. 1.4.2 Tiếp cận trên miền tần số ảnh Trong một số trường hợp cách khảo sát trực tiếp ở trên cũng gặp phải khó khăn nhất định hoặc rất phức tạp và hiệu quả không cao, do đó ta có thể dùng phương pháp khảo sát gián tiếp thông qua các kỹ thuật biến đổi. Các biến đổi này làm nhiệm vụ chuyển miền biến số độc lập sang miền khác và như vậy tín hiệu và hệ thống rời rạc sẽ được biểu diễn trong miền mới với các biến số mới. 11 Mỗi cách biến đổi sẽ có những thuận lợi riêng, tùy từng trường hợp mà sử dụng biến đổi nào. Sau khi khảo sát, biến đổi xong các tín hiệu và hệ thống rời rạc trong miền các biến số mới này, nếu cần thiết có thể dùng các biến đổi ngược để đưa chúng về miền biến số độc lập. Phương pháp khảo sát gián tiếp sẽ làm đơn giản rất nhiều các công việc gặp phải khi dùng phương pháp khảo sát trực tiếp trong miền biến số độc lập tự nhiên. Hệ thống rời rạc cần khảo sát chính là không gian các điểm ảnh. Có nhiều phép biến đổi trong đó phổ biến là biến đổi Fourier DFT, biến đổi Cosin rời rạc DCT, biến đổi sóng nhỏ DWT… Đây là những phép biến đổi được sử dụng nhiều trong các kỹ thuật xử lý ảnh. Trong giấu tin, nó cũng được sử dụng, đặc biệt trong các kỹ thuật thủy vân. 12 1.5 MỘT SỐ PHƯƠNG PHÁP GIẤU TIN MẬT TRONG ẢNH 1.5.1 Giấu tin mật trong khối bit sử dụng tính chẵn lẻ của tổng số bit 1 1.5.1.1 Ý tưởng Đây là kỹ thuật đơn giản nhất trong các kỹ thuật giấu tin. Ý tưởng cơ bản của kỹ thuật này là chia một ảnh thành các khối nhỏ và trong mỗi khối nhỏ sẽ giấu một bit thông tin. Dựa vào tính chẵn lẻ của tổng số các bit 1 trong khối để qui định giấu bit 1 hay 0. Cụ thể sau khi giấu thì tổng số các bit 1 trong khối và bit cần giấu sẽ có cùng tính “chẵn lẻ”. Thuật toán này dùng cho ảnh đen trắng, ảnh mầu và ảnh đa cấp xám. Tuy nhiên, trong phần trình bày ở mục ngay sau đây sẽ minh họa thuật toán cho ảnh đen trắng, phần trình bày áp dụng thuật toán cho ảnh mầu và ảnh đa cấp xám sẽ được nói đến tiếp sau. 1.5.1.2 Thuật toán giấu tin Input: - Một file ảnh bitmap đen trắng FF - Một file thông tin cần giấu Fb - Một khóa K (đó là kích thước khối nhỏ) Output: - Một file ảnh F’ đã giấu tin. Thuật toán: 1) Tiền xử lý  Chuyển file thông tin cần giấu Fb sang dạng xâu nhị phân D=b1b2…bk.  Đọc header của ảnh (phần chứa thông tin ảnh), đọc bảng mầu, sau đó đọc toàn bộ dữ liệu ảnh vào một mảng hai chiều (ma trận) M để sử dụng cho việc giấu tin. 2) Quá trình giấu tin  Bước 1: Chia ma trận M thành các khối nhỏ Bi kích thước K = m x n  Bước 2: Giấu bit dữ liệu bi vào khối Bi. For each Bi if sum(Bi)  bi (mod 2) then giữ nguyên khối Bi. else B’i  đảo bit bất kì trong Bi. End; 13 Giải thích thuật toán: - Chia M thành các khối nhỏ có kích thước K. (K = m x n). Giả sử ảnh gốc ban đầu có kích thước M x N, ảnh gốc được chia thành các khối nhỏ, tổng số các khối nhỏ sẽ là k = (M x N)/ (m x n) khối. Vì là ảnh đen trắng nên mỗi khối là một ma trận hai chiều của các giá trị 0 và 1. - Giả sử cần giấu 1 bit dữ liệu b vào một khối B. Kí hiệu sum(B) là tổng số điểm ảnh đen (điểm ảnh có giá trị bằng 1) trong khối B. Kí hiệu x  y (mod z) hai số tự nhiên x và y đồng dư theo modulo z. Như vậy x  y (mod 2) cho biết x và y có cùng tính chẵn lẻ. Ta xét hai trường hợp sau: - Trường hợp thứ nhất: sum(B)  b (mod 2), khối B thỏa mãn tính chất để giấu bit dữ liệu b. Ta không cần thay đổi gì và xem như bit b đã được giấu. - Trường hợp thứ hai: sum(B) b (mod 2). Ta phải sửa khối B để đảo tính chẵn lẻ của sum(B). Dễ thấy ta chỉ cần đảo một bit bất kỳ trong B thì sum(B) sẽ tăng hoặc giảm 1 đơn vị. Gọi B’ là khối kết quả thu được từ khối B sau khi đã đảo một bit trong B. Ta có sum(B’)  b (mod 2). Thí dụ: Xét thí dụ dưới đây minh họa cho hai trường hợp trên. Cho khối B như sau 0 1 0 0 1 0 1 1 1 1 0 1 0 0 0 1 Khối B kích thước K = 4 x 4, sum(B) = 8. (a) Giả sử ta muốn giấu bit b = 1 vào khối B. Số lượng bít 1 trong khối B là 8, sum(B) = 8. Do đó sum(B) 1 (mod 2). Như vậy khối B không thỏa mãn yêu cầu. Để giấu bit 1 vào khối B ta thay đổi một bit bất kỳ trong khối, thường là thay đổi tại vị trí của bit thông tin rõ vào bít của khối tương ứng (nếu chúng trái dấu nhau) đổi bit 0 thành bít 1 hoặc bít 1 thành bít 0, ta thu được khối B’. Giả sử ta đổi như hình sau: 14 Hình 1.4. Thay đổi bit trong khối B Khi đó ta có sum(B’) = 7, do đó ta được sum(B’)  1 (mod 2). (b) Giả sử ta giấu bit b = 0 vào khối B. Ta có sum(B) = 8, nên sum(B)  0 (mod 2). Khối B được bảo toàn và bit dữ liệu b = 0 coi như đã được giấu. Trong thuật toán giấu tin này, khóa đơn giản chỉ là kích thước khối. K = m x n. Nếu biết kích thước của khối thì ta dễ dàng giải mã theo quy tắc sau. 3) Quá trình tách tin Input - F’ là ảnh đã được giấu dãy bit bí mật D - K là khóa bí mật, đó là kích thước khối nhỏ đã được xác định trước Output - F là file ảnh chứa tin đã được giấu - D là dãy bit bí mật đã giấu Các bước thực hiện - Đọc header ảnh để biết các thông tin về ảnh, đọc bảng mầu, đọc phần dữ liệu ảnh vào ma trận hai chiều M - Chia M thành các khối nhỏ với kích thước K. - Theo một thứ tự xác định trước, xét từng khối nhỏ B, giải tin theo quy tắc sau - Nếu tổng số các bit 1 là lẻ thì ta thu được bit giấu là 1 - Nếu tổng số các bit 1 là chẵn thì ta thu được các bit giấu là 0. Như vậy, sau khi xử lý hết các khối đã giấu ta thu được chuỗi bit đã giấu b’ Chuyển file xâu bit nhị phân sang file văn bản. 0 1 0 0 1 0 1 1 1 1 0 1 0 0 0 1 Khối B 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 Khối B’ 15 1.5.1.3 Phân tích thuật toán Thuật toán giấu tin trong ảnh dựa vào tính chẵn lẻ của tổng số bit 1 ở trên là rất đơn giản. Sau khi nghiên cứu thuật toán này ta có thể đưa ra một số nhận xét sau:  Việc chọn kích thước khối để giấu tin cần căn cứ vào kích thước ảnh và lượng tin cần giấu sao cho các thông tin giấu có thể giàn trải trên toàn ảnh. Ví dụ nếu ta có ảnh kích thước 512 x 512 pixel và có một lượng thông tin cần giấu là 100 kí tự. Như vậy, file thông tin nhị phân cần giấu là 100 x 8 = 800 bit. Ta có thể thấy để giấu hết thông tin cần ít nhất 800 khối, vậy thì kích thước khối ta có thể chia trên ảnh là (512x512)/800=327 (dư 544). Với cách tính này thì kích thước tối đa của một khối là 327. Chẳng hạn ta có thể chọn kích thước cho một khối 20x16, 30x15… Nên chọn khối có kích thước lớn vì như vậy trong trường hợp các khối bị thay đổi thì khoảng cách các bit bị biến đổi sẽ thưa hơn và làm cho ảnh sau khi giấu khó nhận biết hơn.  Với thuật toán này việc chọn khối khá đơn giản. Ta có thể bắt đầu từ khối đầu tiên và các khối tiếp theo một cách tuần tự. Tuy nhiên ta có thể làm khó thuật toán hơn bằng cách chọn ngẫu nhiên một khối chưa giấu tin ở mỗi lần giấu. Khi đó ta đã làm tăng độ an toàn của thuật toán vì khóa lúc đó còn bao gồm cả chỉ số khối đã giấu tin cho từng bit. Hoặc ta có thể thay đổi kích thước khối ở mỗi lần giấu. Chẳng hạn như lần thứ nhất có kích thước khối là 8x8, lần thứ hai là 8x12,… trong những trường hợp này thì khóa sẽ là kích thước khối ở mỗi lần giấu.  Bản chất của kỹ thuật giấu tin trong ảnh đen trắng đó là một quy ước nào đó dưới dạng một mệnh đề (tân từ) P. Nếu tân từ P được thỏa thì ứng với bit 1, ngược lại ứng với bit 0. Tân từ P trong thuật toán trên là sum(B)  b (mod 2). 1.5.1.4 Áp dụng thuật toán cho ảnh màu và ảnh đa cấp xám Nhược điểm cơ bản của phương pháp giấu tin vào ảnh đen trắng là tin giấu vào đó được rất ít. Nếu giấu nhiều thông tin thì ảnh sẽ thay đổi và người ta dễ dàng phát hiện ra sự có mặt của thông tin ẩn. Do đó khi giấu tin mật người ta thường chọn ảnh màu hoặc ảnh đa cấp xám. Với ảnh màu và ảnh đa cấp xám, mỗi điểm ảnh được biểu diễn bằng nhiều bít. Trong dãy các bít này có một bít được gọi là bít ít quan trọng nhất (LSB – Least Significant Bit). LSB là bit mà khi ta đảo giá trị của nó thì điểm màu chỉ bị thay đổi ít nhất. Thí dụ với ảnh đa cấp xám, mỗi mức xám g được biểu diễn bởi số nguyên không âm, thì mức xám g sẽ sai khác ít nhất so với hai mức xám liền kề là g–1 và g+1. Trong trường hợp này bít LSB chính là bit thấp nhất trong dạng biểu diễn nhị phân của g. Hầu hết các thuật toán giấu tin trên ảnh mầu hoặc ảnh đa cấp xám đều áp dụng gián tiếp thuật toán giấu tin trên ảnh đen trắng theo sơ đồ sau: 16  Bước 1: Tạo ảnh đen trắng F từ ảnh mầu Fc bằng một kỹ thuật nào đó. Chẳng hạn lấy từ mỗi điểm màu trong Fc một bít quan trọng nhất để làm một điểm ảnh cho F.  Bước 2: Giấu tin vào ảnh đen trắng F để thu được ảnh đen trắng F’.  Bước 3: Đưa lại các bit của F’ vào mỗi điểm ảnh màu tương ứng của Fc để thu được ảnh màu kết quả là F’c. Như vậy, thuật toán giấu tin trong ảnh đen trắng là cơ sở cho các thuật toán giấu tin nói chung. 17 1.5.2 Kỹ thuật giấu tin Wu _ Lee 1.5.2.1 Ý tưởng chính của thuật toán Kỹ thuật giấu tin theo khối bit sử dụng tính chẵn lẻ của tổng số bit 1 trong khối ở trên thể hiện độ an toàn không cao do chỉ có duy nhất kích thước khối là khóa cho quá trình giấu tin, đồng thời ảnh chứa thông tin giấu cũng dễ bị phát hiện do kỹ thuật có thể đảo bit trong khối ảnh toàn màu đen hoặc toàn màu trắng dẫn tới sự bất thường ở vị trí đảo so với các điểm lân cận trong khối. Thuật toán giấu tin trong ảnh đen trắng do M.Y.Wu và J.H.Lee đưa ra năm 1989 [11] đã khắc phục được phần nào những tồn tại nêu trên bằng cách đưa thêm khóa K cho việc giấu tin và các điều kiện để đảo bít trong mỗi khối. Định nghĩa 1.1: Gọi x và y là hai bit tùy ý, phép nhân bit kí hiệu là  trên hai bit x và y ; phép cộng loại trừ (còn gọi là phép XOR) kí hiệu là  trên hai bit x và y, được định nghĩa thông qua bảng dưới đây x y x  y x  y 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 Hình 1.5 Các phép toán  và  Với mỗi ma trận A, kí hiệu A[i,j] là phần tử trên hàng i, cột j của ma trận A. Hai phép toán trên cũng được mở rộng cho các dãy bit hoặc cho các ma trận bit. Định nghĩa 1.2: Hai ma trận A và B có cùng kích thước m x n ta định nghĩa A  B = C, trong đó C[i,j] = A[i,j]  B[i,j] A  B = C, trong đó C[i,j] = A[i,j]  B[i,j] 18 Định nghĩa 1.3: Phép nhân theo vị trí trên hai ma trận A và B (các phần tử là các số nguyên) có cùng kích thước như sau: A  B = C, trong đó C[i,j] = A[i,j] * B[i,j] Định nghĩa 1.4: Với ma trận số B ta định nghĩa sum(B) là tổng tất cả các phần tử của ma trận B. Nếu B là ma trận bit thì sum(B) chính là tổng số các bit 1 có trong B. Ý tưởng thuật toán Với mục tiêu là giấu được càng nhiều thông tin vào trong ảnh mà vẫn đảm bảo được chất lượng ảnh càng tốt, ý tưởng chính của thuật toán là chia ảnh ra thành các khối bằng nhau, tìm khối nào ít bị phát hiện nhất, giấu một bit thông tin vào khối đó. 1.5.2.2 Thuật toán 1) Quá trình giấu tin Input:  Ảnh nhị phân F  Khóa bí mật K  Xâu bit dữ liệu cần giấu D Output:  Một file ảnh F’ đã giấu tin bên trong. Cách thức thực hiện: Bước 1: Chia ảnh F thành các khối nhỏ Fi, mỗi khối có kích thước K (K = m x n). Bước 2: For each Fi If 0< sum(Fi  K) < sum(K) then Chuyển bước 3 để giấu thông tin vào khối Fi, Else giữ nguyên khối Fi. 19 Bước 3: Giả sử bit cần giấu vào khối Fi là b, thay đổi Fi như sau: if sum(Fi  K) mod 2 = b then giữ nguyên Fi else if sum(Fi  K) = 1 then chọn ngẫu nhiên một bit [j, k] thỏa đồng thời Fi[j, k] = 1 và K[j, k] = 1. Đảo giá trị của bit Fi[j, k] = 1 else if sum((Fi  K) = sum(K) – 1 then Chọn ngẫu nhiên một bit [j, k] thỏa Fi[j, k] = 1 và K[j, k] = 1. Đảo giá trị của bit Fi[j, k] = 0 else Chọn ngẫu nhiên một bit [j, k] mà K[j, k] = 1 Đảo giá trị của bit Fi[j, k] từ 1 thành 0 hoặc từ 0 thành 1. End if; Thí dụ: Giả sử ta cần giấu dãy bit D = “101” vào ảnh F có kích thước 8x8 và một ma trận khóa K có kích thước 4x4 như hình vẽ dưới đây. Ta chia ảnh F thành 4 khối nhỏ F1, F2, F3, F4, mỗi khối nhỏ sẽ có kích thước là 4x4. 20 (a) (b) F1 F2 F1K F2K 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 F3 F4 K F3K F4K F'1 F'2 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 (c) 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 0 1 0 1 0 1 F'3 F'4 Hình 1.6. Minh họa giấu dữ liệu D = “101” vào 4 khối ảnh nhị phân 21 - Với khối F1: Ta có b=1, sum(F1  K) = 5, suy ra sum(F1  K) mod 2 = 1. Ta giữ nguyên F1. Coi như bit đầu tiên đã được giấu trong F1. - Với khối F2: Ta có b=0,sum(F2  K) = 7, suy ra sum(F1  K) mod 2 = 1b. Nhưng sum(F1  K) = 7 = sum(K) -1 nên ta chọn ngẫu nhiên phần tử [4,2] để đảo bit trong khối F2 vì với phần tử này ta có F2[4,2] = 1 và K[4,2] = 1. Ta thu được khối F’2. Bằng cách đảo bít của F2[4,2] = 0. - Với khối F3: sum(F3  K ) = 8 = sum(K) nên ta không giấu được bit dữ liệu tiếp theo vào khối này. - Với khối F4, Ta có b=1, sum(F4  K) = 4, nên sum(F4  K) mod 2 = 0  b. Chọn ngẫu nhiên ô F4[3,1] ứng với K[3,1] = 1 đảo bit của F4[3,1] từ 0 thành 1 ta thu được khối F’4. - Kết quả được minh họa trên hình 1.6(c). 2) Quá trình tách tin Input - F’ là ảnh đã được giấu dãy bit bí mật D - K là ma trận khóa bí mật, kích thước m x n. Output - F là file ảnh chứa tin đã được giấu - D là dãy bit bí mật đã giấu Các bước thực hiện - Đọc header ảnh để biết các thông tin về ảnh, đọc bảng mầu, đọc phần dữ liệu ảnh vào ma trận hai chiều M - Chia M thành các khối nhỏ F’i với kích thước mxn. - For each F’i. if 0<sum(F’iK)<sum(K) then b=sum(F’iK) mod 2. Trong đó b là bít nhị phân đã được giấu. 22 1.5.2.3 Phân tích thuật toán Trong mục này ta phân tích khả năng đối phương phát hiện ảnh có giấu tin hoặc trong trường hợp xấu hơn, đối phương phát hiện được cả khóa bí mật K. Nếu có ảnh gốc F và ảnh đã giấu tin F’, bằng một thủ tục đối sánh đơn giản đối phương có thể phát hiện ra ảnh có giấu tin hay không. Nếu F = F’ thì ảnh không bị giấu tin, ngược lại F khác F’ thì ảnh có thể bị giấu tin. Trước hết chúng ta xem xét vấn đề khóa K. Việc chọn khóa K nhằm làm tăng độ mật của thuật toán. Nếu như trước đây chỉ biết kích thước của khối là m x n thì đối phương rất dễ khai thác được bản tin mật. Ở đây còn phải biết thêm giá trị cụ thể của khóa K. Phép toán FiK qui định thuật toán chỉ được phép sửa các bit trong khối Fi ứng với bit 1 trong khóa K. Như vậy khóa K được xem như một mặt nạ. Tuy nhiên, ta vẫn có thể thay phép toán  bởi phép toán khác, chẳng hạn phép toán . Tiếp theo chúng ta xét đến điều kiện 0 < sum(Fi K) < sum(K) qui định nếu khối Fi K toàn 0 hoặc giống như khóa K thì không được giấu tin để tránh bị lộ. Nếu một khối Fi toàn điểm trắng được truyền đi thì kẻ thù khi bắt được thông tin sẽ dễ dàng tìm được ra vị trí 1 của khóa K. Do vậy ta không dùng trường hợp sum(FiK) = 0 để giấu tin. Với trường hợp sum(Fi K) = sum(K) nếu Fi toàn điểm đen thì vị trí bít thay đổi cũng là vị trí mà bít tương ứng ở khóa K là 1. Để tránh hai trường hợp trên thuật toán đưa ra điều kiện: 0<sum(FiK)<sum(K) khi giấu một bit thông tin vào khối Fi. Nhưng cho dù thế đi chăng nữa thì vị trí tương ứng với bit bị thay đổi cũng tương ứng với bit ở vị trí đó trong khóa K có giá trị 1, và bit không bao giờ bị thay đổi tương ứng sẽ là bit 0 ở vị trí đó trong khóa K. Và như thế việc chọn khóa K như thế nào là một công việc hết sức quan trọng. Trong bước 3 chỉ thực hiện tối đa một phép đảo một bit của khối Fi để thu được khối F’i nhằm đảm bảo tính bất biến. Do việc giấu tin vào khối chỉ cần thay đổi tối đa một bit nên việc chọn bit nào trong Fi để đảo cần tuân thủ nguyên tắc: Nếu FiK có nhiều bit 1 thì chọn bit 1, ngược lại nếu FiK có quá ít bit 1 thì chọn bit 0. Nguyên tắc này làm giảm khả năng bit đảo bị phát hiện. Vì K là khóa bí mật nên thông tin đã được nhúng là bí mật. Thuật toán này làm thay đổi nhiều nhất một bit của khối Fi khi giấu một bit thông tin vào trong khối nên với một khối có kích thước m x n đủ lớn thì sự thay đổi của Fi là nhỏ. 23 Ảnh F được lựa chọn để giấu thông tin cũng phải được chọn kĩ càng. Nếu một ảnh có quá nhiều điểm đen hoặc điểm trắng thì tỉ lệ bit giấu được sẽ rất thấp. Thông thường người ta chọn ảnh gốc là các ảnh lạ, chẳng hạn ảnh cá nhân để giấu tin nhằm tăng độ bảo mật. Nói chung, thuật toán Wu_Lee vẫn chưa đạt được những yêu cầu cần thiết về khả năng giấu, độ an toàn thông tin cũng như chất lượng ảnh. Tuy nhiên đó là áp dụng đối với ảnh đen trắng, nếu ta áp dụng kỹ thuật này với ảnh màu và ảnh đa cấp xám thì sẽ thu được kết quả khả quan hơn. 1.5.3 Kỹ thuật giấu tin Yuan_Pan_Tseng 1.5.3.1 Ý tưởng chính của thuật toán Yu Yuan, Hsiang Kuang Pan và Yu Chee Tseng đã phát triển một kỹ thuật giấu tin mới trên cơ sở của thuật toán Wu_Lee. Kỹ thuật này sử dụng một ma trận khóa và một ma trận trọng số để giấu tin. Thuật toán đảm bảo được độ an toàn của thông tin giấu và cũng giấu được nhiều thông tin trong ảnh bằng cách chỉ thay đổi nhiều nhất 2 bit trong mỗi khối ảnh. Đối với ảnh đen trắng thì kỹ thuật này có nhược điểm là chất lượng ảnh chưa cao, dễ bị phát hiện. Định nghĩa 1.5: Khóa bí mật là một ma trận nhị phân có cùng kích thước mxn với kích thước của khối ảnh. Khóa được dùng một cách bí mật mà chỉ có người gửi và người nhận đích thực mới biết được. Định nghĩa 1.6: Ma trận W trọng số cấp r là một ma trận số nguyên có kích thước bằng kích thước của khối ảnh mxn và thỏa mãn các điều kiện sau: (i) W là ma trận số nguyên có các phần tử nằm trong khoảng giá trị (0,…,2r-1) với r là một số nguyên dương cho trước thỏa mãn 2r < mxn. (ii) Mỗi phần tử có giá trị từ 1 đến 2r -1 xuất hiện ít nhất một lần trong ma trận. Định nghĩa 1.7: Phép đảo bit (bitwise) là một phép biến đổi trên các bit nhị phân. Đảo bit b tương đương với phép biến đổi thay b bởi 1-b. 24 Định nghĩa 1.8: Với mỗi số nguyên dương p, ta xét tập các số dư trong phép chia cho p, Zp={0, 1, 2, …, p-1}. Trên Zp ta thực hiện các phép toán theo modulo p như sau: x, y  Zp: - Phép cộng: x+y (mod p) = (x +y) mod p - Phép lấy phần tử đối: -x (mod p) = p-x - Phép trừ: x – y (mod p) = (x+(p-y)) mod p - Phép nhân: x  y (mod p) = (x  y) mod p. Các phép toán dùng trong ma trận cũng giống như đã định nghĩa ở mục 1.5.2. Ý tưởng thuật toán Ý tưởng chính của thuật toán giấu tin Yuang_Pan_Tseng là sử dụng thêm một ma trận trọng số kết hợp với ma trận khóa K và để giấu được r bit dữ liệu vào một khối m x n nhưng chỉ thay đổi nhiều nhất hai bit dữ liệu trên khối [10]. 1.5.3.2 Thuật toán 1) Quá trình giấu tin Input: - F là một ma trận giá trị các điểm ảnh gốc dùng để giấu tin. - K là một ma trận khóa nhị phân có kích thước mxn. - r là số lượng bit cần giấu trong mỗi khối ảnh kích thước mxn. - D là xâu thông tin cần giấu gồm k*r bít, k là số khối ảnh giấu. - W là một ma trận trọng số r với các giá trị W[i,j] thuộc tập {1,2,…,2r-1} xuất hiện ít nhất một lần. Output: - Một file ảnh F’ đã giấu tin b. Thuật toán Bước 1: Chia ảnh F thành các khối nhỏ Fi có kích thước mxn, đặt p = 2r ; Với mỗi khối Fi thực hiện các bước biến đổi sau Bước 2: Tính T = FiK; P= TW; 25 Bước 3: Tính tổng s = sum(P) mod p; đặt b=b1b2…br; d = b – s (mod p); Bước 4: Với mỗi khối T : For each w  {1,2,…,2r-1} do Sw = {[j, k]  (W[j, k] = w  Ti[j, k] =0)  (W[j, k]=2r-w  Ti[j, k] =1)} Endfor; Bước 5: if d=0 then giữ nguyên Fi; Bước 6: if Sd   then Chọn phần tử [j, k] bất kì thuộc Sd và đảo bit Fi[j, k]; Bước 7: u=d; while (Su= ) do v = p – u; u = (u + d) mod p; endwhile; Bước 8: Chọn phần tử [j, k] bất kì thuộc Su và đảo bit Fi[j, k]; Chọn phần tử [j, k] bất kì thuộc Sv và đảo bit Fi[j, k]; End; 26 Thí dụ: Giả sử ta có một ma trận ảnh F8x8. Một ma trận khóa K4x4 và một ma trận trọng số W4x4. Ta giấu 12 bit sau D=001 000 010 001 vào trong ảnh F. Cho r = 3. Ban đầu chia F thành các khối ảnh F1, F2, F3, F4 có cùng kích thước 4x4. F1 F2 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 5 2 6 1 1 1 1 1 1 0 0 0 1 0 1 2 6 3 7 0 0 1 0 0 1 0 1 1 0 1 0 3 7 4 1 0 1 1 0 0 0 0 0 0 1 0 1 4 1 5 2 1 1 0 1 1 1 1 1 K W 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 F3 F4 Với r = 3, p = 2r =23 – 8. Như vậy đoạn bít 001 giấu vào khối F1, 000 giấu vào khối F2, 010 giấu vào khối F3 và 001 giấu vào khối F4. 27 Ta thực hiện phép tính FiK và (FiK)W trên mỗi khối đã chia và thu được kết quả như sau F1K F2K (F1K)W (F2K)W 0 1 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 3 7 2 0 3 0 0 1 0 1 0 1 1 0 0 7 0 1 0 7 4 0 0 1 1 1 0 0 0 0 0 1 5 2 0 0 0 0 1 1 0 0 1 0 1 0 1 5 0 0 1 0 2 0 1 0 0 0 1 0 1 0 2 0 0 0 2 0 3 0 0 0 0 1 1 1 1 0 0 0 0 1 3 7 4 0 1 0 1 1 0 0 0 0 4 0 5 2 0 0 0 0 F3K F4K (F3K)W (F4K)W Với mỗi khối T, để tiếp tục ta cần tính tập Sw với w=1, 2,…,7. Ta sử dụng một bảng S* ghi nhận các phần tử của các tập Sw. Phần tử trên ma trận S* được xác định như sau S*[j, k]=W[j, k] nếu T[j, k] = 0; S*[j, k]=p-W[j, k] nếu T[j, k] = 1. Sau đó từ bảng S*, ta xét nếu S*[j, k] = w thì ta có [j, k]  Sw. S*1 S*2 1 3 2 6 1 5 2 6 2 6 5 1 6 6 5 7 3 1 4 7 3 1 4 1 4 7 3 6 4 1 5 2 7 3 2 6 7 5 6 6 6 6 3 7 6 6 5 7 3 7 4 7 5 1 4 1 4 1 3 6 4 1 5 2 S*3 S*4 28 Chẳng hạn từ bảng trên ta xét khối S*1 và thu được các Sw (w =1, 2, …, 7) sau S1={[1,1]; [2,4]; [3,2]} S2={[1,3]; [2,1]} S3={[1,2]; [3,1]; [4,3]} S4={[3,3]; [4,1]} S5={[2,3]} S6={[1,4}; [2,2]; [4,1]} S7={[3,4]; [4,2]} Với khối F1: b = (001)2 = 1, Ta có s = sum(F1K)W) mod 8 = 31mod 8 =7; d = b-s (mod 8) = 1-7(mod 8) = 2  0. Sd=S2 ={[1,3]; [2,1]}  nên ta có thể chọn tùy ý một trong hai vị trí trong S2 để đảo bit. Ta chọn đảo bit ở F1[2,1] khi đó thu được F’1. Với khối F2: b = (000)2 = 0, Ta có s = sum(F2K)W) mod 8 = 16 mod 8 =0. d = b-s (mod 8) = 0-0 (mod 8) = 0. Giữ nguyên khối F2 và coi như đã giấu được đoạn bit này. Với khối F3: b = (010)2 = 2, Ta có s = sum(F3K)W) mod 8 = 20 mod 8 =4. d = b-s (mod 8) = 2-4 (mod 8) = 6  0. Sd=S6 ={[1,4]; [2,1]; [2,2]; [4,4]}  nên ta có thể chọn tùy ý một phần tử trong S2 để đảo bit. Ta chọn đảo bit ở F3[2,2] khi đó thu được F’3. Với khối F4: b = (001)2 = 1, Ta có s = sum(F3K)W) mod 8 = 22 mod 8 =6. d = b-s (mod 8) = 1-6 (mod 8) = 3  0. Sd=S3 =; u = d = 3; v = 8 – 3 = 5; u = 3 + 3 (mod 8) = 6 Su = S6={[1,3]; [1,4]; [2,1]; [2,2]}. Ta chọn đảo bít tại [1,4] Sv = S5 = {[1,2]; [2,3]; [3,1]; [4,3]}. Ta chọn đảo bit tại [4,3] 29 Vậy ảnh F’ thu được bằng cách ghép 4 khối F’1, F’2, F’3, F’4 như sau F’1 F’2 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 F’3 F’4 2) Quá trình tách tin Input - F’ là ảnh đã được giấu dãy bit bí mật D - K là ma trận khóa bí mật, kích thước mxn. - r là số lượng bit đã giấu ở mỗi khối - Ma trận trọng số W cấp r Output - F là file ảnh chứa tin đã được giấu - D là dãy bit bí mật đã giấu Thuật toán - Đọc header ảnh để biết các thông tin về ảnh, đọc bảng mầu, đọc phần dữ liệu ảnh vào ma trận hai chiều M - Chia M thành các khối nhỏ F’i với kích thước mxn. - Với mỗi khối nhỏ F’i. Tính b= sum((F’iK)W) mod 2r. Trong đó b là xâu nhị phân được tạo ra bởi r bit thông tin. 30 Thí dụ 2: Với phần thông tin đã được giấu như trong Thí dụ 1 ở trên. Với mỗi khối F’i ta thực hiện phép toán FiK)W thu được kết quả như sau: F'1K F'2K (F'1K)W (F'2K)W 0 1 0 0 0 0 0 0 0 5 0 0 0 0 0 0 1 0 1 1 1 0 1 0 2 0 3 7 2 0 3 0 0 1 0 1 0 1 1 0 0 7 0 1 0 7 4 0 0 1 1 1 0 0 0 0 0 1 5 2 0 0 0 0 1 1 0 0 1 0 1 1 1 5 0 0 1 0 2 6 1 1 0 0 1 0 1 0 2 6 0 0 2 0 3 0 0 0 0 1 1 1 1 0 0 0 0 1 3 7 4 0 1 0 1 1 0 0 1 0 4 0 5 2 0 0 5 0 F'3K F'4K (F'3K)W (F'4K)W Tiếp theo ta có các kết quả sau: sum((F’1K)W) mod 2r = 33 mod 8 = 1 tương ứng xâu 3 bit nhị phân 001 sum((F’2K)W) mod 2r = 16 mod 8 = 0 tương ứng xâu 3 bit nhị phân 000 sum((F’3K)W) mod 2r = 26 mod 8 = 2 tương ứng xâu 3 bit nhị phân 010 sum((F’4K)W) mod 2r = 33 mod 8 = 1 tương ứng xâu 3 bit nhị phân 001 Như vậy cuối cùng ta thu được xâu bít nhị phân đã giấu ban đầu là D=001000010001. 31 1.5.3.3 Phân tích thuật toán Với thuật toán giấu tin sử dụng ma trận trọng số W cấp rvà ma trận khóa K ở trên, ta có thể coi khóa K như một mặt nạ, khi đó ma trận T là ma trận nhị phân cho biết những phần tử tương ứng trong hai khối Fi và K là khác nhau hay không. Tổng s = sum(P) cho biết tổng các trọng số tại các phần tử khác nhau giữa khối Fi và K. d chính là điều kiện để giấu tin. d  Zp. Nếu d = 0 thì ta không làm gì cả và coi như dãy bit b đã được giấu vào khối Fi tương ứng. Ngược lại nếu d  0 thì thuật toán sẽ thực hiện từ bước 6 đến bước 8 với mục đích để đẳng thức sau thỏa mãn sum((FiK)W)  b1b2…br (mod 2) Đẳng thức trên gọi là bất biến của thuật toán giấu tin này. Thủ tục sửa hai vị trí trong một khối bất kỳ như sau: Trước hết cần tính các Sw (w=1, 2,…,2r -1) theo như bước 4 của thuật toán Sw = {[j,k]  (W[j,k] = w  Ti[j,k] =0)  (W[j,k]=2r-w  Ti[j,k] =1)} Như vậy Sw là tập các chỉ số [j,k] trong các khối thỏa các điều kiênh sau (i) Tại vị trí đó, ma trận trọng số W có giá trị w và các phần tử Fi[j,k]=K[j,k] (do M[j,k]=0) (ii) Tại vị trí đó, ma trận trọng số W có giá trị 2r-w và các phần tử Fi[j,k]K[j,k] (do M[j,k]=0). Nếu [j,k]  Sw thì ta đảo bit [j,k] trong khối đang xét, tức là thực hiện đổi bit 0 thành 1 hoặc bit 1 thành 0 và như vậy đại lượng s sẽ tăng lên w đơn vị tính theo modulo 2r. 32 1.6 KỸ THUẬT THỦY VÂN TRÊN ẢNH Tính năng an toàn và bảo mật thông tin của kỹ thuật giấu tin được thể hiện ở hai khía cạnh. Một là bảo vệ dữ liệu đem giấu, hai là bảo vệ chính đối tượng được sử dụng để giấu tin. Tương ứng với hai khía cạnh đó có hai khuynh hướng kỹ thuật là giấu tin mật và thủy vân số. Trong phần này, luận văn sẽ trình bày một số kỹ thuật thủy vân, cũng như giải pháp nâng cao độ an toàn cho thủy vân. 1.6.1 Một số khái niệm cơ bản trong thủy vân số 1.6.1.1 Khái niệm thủy vân số Thủy vân trên ảnh số là kỹ thuật nhúng một lượng thông tin số vào bức ảnh số sao cho người không được phép “khó” có thể lấy được thông tin ra khỏi ảnh, mà không phá hủy chính ảnh đó (ảnh gốc). Trong kỹ thuật thủy vân số, thông tin nhúng được gọi là thủy vân. Thủy vân có thể là một chuỗi các kí tự hay một hình ảnh nào đó. 1.6.1.2 Phân loại các kỹ thuật thủy vân Căn cứ những đặc trưng, tính chất của từng kỹ thuật thủy vân và khía cạnh ứng dụng những kỹ thuật đó, ta có thể chia các kỹ thuật thủy vân theo nhóm được mô tả trong hình 1.1 [27]. Thủy vân dễ vỡ là kỹ thuật nhúng thủy vân vào trong ảnh, sao cho sản phẩm sau khi phân phối trong môi trường mở, nếu có bất kỳ một phép biến đổi nào làm cho nó bị thay đổi, thì thủy vân đã giấu trong nó sẽ không còn nguyên vẹn như thủy vân gốc. Kỹ thuật thủy vân có tính chất này được dùng trong các ứng dụng xác thực thông tin và phát hiện xuyên tạc thông tin [2, 3]. Ngược lại với kỹ thuật thủy vân dễ vỡ là thủy vân bền vững. Kỹ thuật thủy vân bền vững thường được dùng trong các ứng dụng bảo vệ bản quyền. Trong những ứng dụng đó, thủy vân đóng vai trò là thông tin sở hữu của người chủ hợp pháp. Thủy vân được nhúng trong sản phẩm như một hình thức “dán tem” bản quyền. Trong trường hợp đó, thủy vân phải tồn tại bền vững cùng với sản phẩm nhằm chống lại việc tẩy xóa, làm giả hay biến đổi phá hủy thủy vân. Nếu muốn hủy bỏ thủy vân chỉ còn cách phá hủy sản phẩm. 33 Thủy vân bền vững lại được chia thành hai loại là thủy vân ẩn và thủy vân hiện. Thủy vân ẩn giống như giấu tin, yêu cầu tính ẩn cao, bằng mắt thường không thể thấy thủy vân. Thủy vân ẩn được ứng dụng trong bảo vệ bản quyền. Thủy vân hiện là loại thủy vân hiện ngay trên sản phẩm và người dùng có thể nhìn thấy được giống như những biểu tượng của một công ty, một sản phẩm, một kênh truyền hình,… Các thủy vân hiện trên ảnh thường dưới dạng chìm, mờ hoặc trong suốt để không gây ảnh hưởng đến chất lượng ảnh gốc. Đối với thủy vân hiện, thông tin bản quyền hiển thị ngay trên sản phẩm. 1.6.1.3 Mô hình hệ thống thủy vân Một mô hình hệ thống thủy vân tổng quát được xem xét theo hai quá trình là quá trình nhúng thủy vân và quá trình tách thủy vân [15]. Quá trình nhúng thủy vân được mô tả ở hình 1.7. Trong đó - Một bức ảnh I cần được bảo vệ (ảnh gốc I). - Thông tin thủy vân W (tùy mục đích bảo vệ, thông tin thủy vân có thể là chuỗi bit, văn bản hoặc ảnh). - Khóa K (có thể có hoặc không). - Một thuật toán trong hệ thống sẽ kết hợp giữa thông tin ảnh gốc I, thông tin thủy vân W và khóa K để tạo thành một bức ảnh mới gọi là ảnh đã nhúng thủy vân hay ảnh chứa thủy vân Iw. Hình 1.7. Mô hình quá trình nhúng thủy vân Quá trình tách thủy vân được mô tả trong hình 1.9. Trong quá trình phân phối, ảnh chứa thủy vân Iw có thể bị người dùng sử dụng một phép biến đổi nào đó để tấn công nhằm phá hủy thủy vân nếu có trong Iw. Các tấn công trên tạo ra I’w. Quá trình tách thủy vân từ ảnh I’w (I’w có thể trùng với Iw) như sau: Bộ nhúng thủy vân Thủy vân W Ảnh gốc I Khóa K Bộ nhúng thủy vân 34 - Ảnh chứa thủy vân I’w - Khóa K (đã sử dụng trong quá trình nhúng thủy vân) - Ảnh gốc I (tùy theo kỹ thuật, ảnh gốc có để được sử dụng hoặc không) - Việc tách thủy vân được thực hiện theo một thuật toán đã xác định. Kết quả là thông tin thủy vân W’ được tách từ I’w. - Thủy vân tách được W’ cần so sánh với thủy vân gốc, để đưa ra những kết luận phù hợp. Hình 1.8. Quá trình tách thủy vân 1.6.1.4 Các đặc trưng của một hệ thủy vân Hệ thủy vân số trên ảnh cũng là một loại giấu tin nên nó cũng có một số đặc điểm và tính chất giống với giấu tin mật trong ảnh. Ngoài ra, kỹ thuật thủy vân còn được phân biệt với giấu tin mật ở những đặc trưng sau đây: 1) Thủy vân có bị biến đổi hay không, khi có biến đổi trên ảnh chứa thủy vân Đối với thủy vân bền vững, yêu cầu thông tin thủy vân không bị thay đổi trước các tác động làm thay đổi thông tin trên ảnh chứa thủy vân. Ngược lại đối với thủy vân dễ vỡ, yêu vầu thông tin thủy vân sẽ bị thay đổi (vỡ) nếu có bất kỳ thay đổi nào trên ảnh chứa thủy vân. Bộ tách thủy vân Ảnh gốc I Ảnh chứa thủy vân I’w Khóa K Thủy vân tách W’ Kiểm định Thủy vân gốc W Kết luận 35 2) Thủy vân ẩn, thủy vân hiện Không giống như giấu tin mật với yêu cầu bắt buộc là thông điệp giấu phải ẩn bên trong ảnh sao cho mắt thường không thể phát hiện được, thủy vân số có hai loại là thủy vân ẩn và thủy vân hiện. Có loại thủy vân cho phép nhìn thấy được thông tin nhúng vào, có loại không nhìn thấy. Thủy vân hiện được dùng cho mục đích công bố công khai về quyền sở hữu. Thủy vân ẩn được dùng với mục đích gài bí mật thông tin xác nhận quyền sở hữu. 3) Tính chất bền vững Đây là tính chất quan trọng của thủy vân bền vững. Thủy vân phải chống lại được các phép biến đổi hay các tấn công lên ảnh chứa thủy vân. Thủy vân phải tồn tại cùng với sự tồn tại của ảnh chứa thủy vân là một tiêu chuẩn của hệ thủy vân này. 4) Thông tin được thủy vân Kiểu thủy vân hay dùng nhất là chuỗi kí tự. Chuỗi kí tự được nhúng trực tiếp lên ảnh mang những thông tin như tác giả, tiêu đề, ngày tháng hay thông tin bản quyền. Tuy nhiên, việc sử dụng chuỗi ký tự cũng có hạn chế là mỗi ký tự biểu diễn bằng nhiều bit, nếu như một bit bị lỗi thì sẽ làm sai cả ký tự, do đó chỉ cần một phép biến đổi đơn giản như phép nén ảnh cũng có thể làm cho thủy vân bị sai lệch rất nhiều. Người ta còn sử dụng thủy vân là ảnh để nhúng, khi đó ta sẽ có ảnh trong ảnh. Khi tách tin thì một số điểm ảnh gốc có thể sai nhưng hình tổng thể vẫn được giữ nguyên. Trong các loại thủy vân thì thủy vân ẩn và bền vững là được quan tâm nghiên cứu nhiều nhất, vì ý nghĩa ứng dụng lớn của nó như đã nói ở phần trên. Do vậy, hai tính chất quan trọng nhất của thủy vân mà các nhà nghiên cứu đang cố gắng đạt được là tính ẩn và tính bền vững. Nhưng đây lại là mấu chốt của sự phức tạp vì hai tính chất này mâu thuẫn nhau. Nếu như để đảm bảo tính ẩn, thủy vân phải được giấu trong những vị trí ít có ý nghĩa tri giác nhất, ít bị chú ý nhất thì ngược lại để đảm bảo tính bền vững, thủy vân phải chịu được những phép xử lí ảnh phổ biến như dịch chuyển ảnh hay nén ảnh, mà các phép biến đổi này lại làm mất đi những thông tin ít ý nghĩa tri giác nhất. 36 1.6.2 Một số kỹ thuật thủy vân trên ảnh Nghệ thuật của thủy vân số chính là lựa chọn công nghệ tùy theo ứng dụng. Có nhiều yếu tố liên quan đến việc lựa chọn giải pháp cho thủy vân như: bảo mật, yếu tố tri giác, độ bền vững, độ phức tạp, ta cần phải cân bằng giữa các yếu tố. Như trong chương một đã trình bày, có hai hướng tiếp cận của các kỹ thuật giấu tin nói chung và kỹ thuật thủy vân nói riêng đó là hướng tiếp cận trên miền không gian rời rạc các điểm ảnh và trong miền tần số ảnh. Đối với cách tiếp cận trên miền tần số ảnh ta có nhiều phép biến đổi khác nhau để chuyển từ miền tín hiệu rời rạc sang miền tần số như DFT, DCT, DWT. Trong chương này luận văn trình bày kỹ thuật thủy vân trên ảnh bằng cách tác động lên miền tần số ảnh thông qua phép biến đổi DCT. 1.6.2.1 Phép biến đổi cosin rời rạc Biến đổi coisin rời rạc DCT (Discrete Cosine Transform) do Ahmed và các đồng nghiệp đưa ra năm 1974. Từ đó nó được ứng dụng rộng rãi nhất là trong kỹ thuật xử lí ảnh số. Trong kỹ thuật thủy vân ảnh dựa trên miền tần số ảnh, thì phép biến đổi DCT được sử dụng nhiều nhất. Định nghĩa 1.9: Biến đổi DCT hai chiều tổng quát là biến đổi trên khối MxN được định nghĩa như sau                      1 0 1 0 2 )12(cos 2 )12(cos),()()(1),( M x N y N vy M uxyxfvCuC NM vuI  I(u,v) được gọi là hệ số DCT và là số thực. Định nghĩa 1.10: Phép biến đổi ngược IDCT được định nghĩa như sau: 1 1 0 0 ( ) ( ) (2 1) (2 1)( , ) ( , )cos cos 2 2 M N u v C u C v x u y vf x y I u v M NM N                     Trong đó      1 2 1 )(kc Nếu k=0 Nếu k > 0 37 Trên ảnh hai chiều, các khối thường sử dụng là 8x8, 16x16. (a) (b) (c) Hình 1.9. Phân chia ba miền tần số của khối ảnh 8x8 theo phép biến đổi DCT (a) miền tần số thấp (b) miền tần số giữa (c) miền tần số cao Đặc điểm của phép biến đổi DCT trên ảnh hai chiều: - Thể hiện đặc tính nội dung về tần số của thông tin ảnh. Hệ số góc trên là lớn và đặc trưng cho giá trị trung bình thành phần một chiều gọi là hệ số DC, các hệ số khác có giá trị nhỏ hơn biểu diễn cho các thành phần tần số cao theo hướng ngang và dọc gọi là hệ số AC. - Bản thân biến đổi DCT không nén được dữ liệu vì sinh ra 64 hệ số. - Theo nguyên lý chung, khi biến đổi chi tiết giữa các điểm ảnh càng lớn theo một hướng nào đó trong khối các điểm ảnh, hướng ngang, dọc hoặc theo đường chéo thì tương ứng theo các hướng đó, các hệ số biến đổi DCT cũng lớn. Tóm lại, DCT làm giảm độ tương quan không gian của thông tin trong khối ảnh. Điều đó cho phép biểu diễn thích hợp ở miền DCT do các hệ số DCT có xu hướng có phần dư thừa ít hơn. Hơn nữa, các hệ số DCT chứa thông tin về nội dung tần số không gian của thông tin trong khối. Nhờ các đặc tính tần số không gian của hệ thống nhìn của mắt người, các hệ số DCT có thể được mã hóa phù hợp, chỉ các hệ số DCT quan trọng nhất mới được mã hóa để chuyển đổi. Khối hệ số DCT có thể chia làm 3 miền: miền tần số thấp, miền tần số cao và miền tần số giữa. Miền tần số thấp chứa các thông tin quan trọng ảnh hưởng đến tri giác. Miền tần số cao thường không mang tính tri giác cao, khi nén JPEG thường loại bỏ thông tin trong miền này. 38 Trong các thuật toán thủy vân, miền hệ số DCT tần số cao thường không được sử dụng do nó thường không bền vững với các phép xử lý ảnh, hoặc nền ảnh JPEG. Miền tần số thấp cũng khó được sử dụng do một sự thay đổi dù nhỏ trong miền này cũng dẫn đến chất lượng tri giác của ảnh. Vì vậy, miền tần số ở giữa thường hay được sử dụng nhất và cũng cho kết quả tốt nhất. 1.6.2.2 Kỹ thuật thủy vân sử dụng phép biến đổi DCT 1) Ý tưởng Thuật toán dưới đây sử dụng phương pháp nhúng thủy vân trong miền tần số của ảnh, giải tần được sử dụng để chứa tín hiệu thủy vân là miền tần số ở giữa của các khối DCT 8x8. Trong đó, các khối DCT 8x8 là những khối ảnh cùng kích thước đã được chọn ra từ ảnh ban đầu và được áp dụng phép DCT để chuyển sang miền tần số. Mỗi bit tín hiệu thủy vân sẽ được nhúng trong một khối [8]. Trong thuật toán có sử dụng một số hàm tính toán sau: Max(x,y): hàm cho số lớn nhất trong hai số x và y. Min(x,y): hàm cho số nhỏ nhất trong hai số x và y. INT(x): là hàm lấy phần nguyên của số thực x. | x | : cho giá trị tuyệt đối của x. 2) Quá trình nhúng thủy vân Input - Thủy vân W: là một chuỗi các bit hoặc một ảnh nhị phân. - Ảnh F kích thước mxn. Output - Ảnh F’ đã nhúng thủy vân. Thuật toán: Bước 1: Ảnh F có kích thước mxn sẽ được chia thành (mxn)/64 khối 8x8, mỗi bit của thủy vân sẽ được giấu trong một khối Bk. Bước 2: Chọn một khối bất kì Bk và biến đổi DCT khối đó thu được kC . Ck = DCT(Bk) Bước 3: Chọn hai hệ số ở vị trí bất kì trong miền tần số ở giữa của khối kC , gọi hai hệ số đó là Ck[i,j] và Ck[p,q]. 39 Bước 4: Tính độ lệch d = | | Ck [i,j]| - | Ck[p,q]| | mod a. Trong đó a là một tham số thỏa a = 2(2t+1), với t là một số nguyên dương. Bước 5: Bit bk sẽ được nhúng vào khối Ck sao cho thỏa mãn bất biến sau:      12 12 td td Bước 6: Nếu d<2t+1 và bk = 1 thì trong hai hệ số DCT Ck[i,j] hoặc Ck[p,q] có giá trị tuyệt đối lớn hơn sẽ bị thay đổi để thỏa d≥2t + 1 theo công thức (1.6.1) hoặc (1.6.2): Max(|Ck[i,j]|, | Ck[p,q]|) + (INT(0.75a) - d) (1.6.1) Hệ số được chọn sẽ được cộng thêm một lượng là (INT(0.75a) - d) Min(|Ck[i,j]|, | Ck[p,q]|) – (INT(0.25a) + d) (1.6.2) Hệ số được chọn sẽ bị trừ đi một lượng là (INT(0.25a) + d) Bước 7: Nếu d≥ 2t + 1 và bk = 0 thì một trong hai hệ số DCT Ck[i,j] hoặc Ck[p,q] có giá trị tuyệt đối lớn hơn sẽ bị thay đổi để thỏa d<2t + 1 theo công thức (1.6.3) hoặc (1.6.4) như sau: Max(|Ck[i,j]|, |Ck[p,q]|) - (d – INT(0.25a)) (1.6.3) Hệ số được chọn sẽ bị trừ đi một lượng là (d – INT(0.25a). Min(|Ck[i,j]|, | Ck[p,q]|) + (INT(0.25a) – d) (1.6.4) Hệ số được chọn sẽ được cộng thêm một lượng là INT(0.25a) – d. Bước 8: Thực hiện phép biến đổi ngược IDCT đối với khối Ck. )(' kk CIDCTB  Bước 9: Ghép các khối ảnh 'kB để được ảnh chứa thủy vân F’. Nếu bk=1 Nếu bk= 0 40 Thí dụ (1.6.3.1.a): Giả sử ta cần giấu một bit thủy vân b =0 vào khối B 8x8 được cho dưới đây. Ta chọn a = 26 = 2(2x6 + 1), do đó t = 6. 33 84 66 58 15 159 183 146 28 75 15 37 161 157 136 134 29 59 44 65 192 166 144 139 B= 15 15 15 67 113 123 192 170 88 76 15 102 168 104 199 177 19 10 15 218 140 198 164 141 15 15 15 179 241 235 190 107 15 17 89 181 168 234 190 190 Biến đổi DCT(B) ta thu được khối C: Ta tính C[u, v] như sau: 7 7 0 0 1 (2 1) (2 1)( , ) ( ) ( ) ( , )cos cos 16 168 8 x y x u y vC u v C u C v B x y                    Trong đó:      1 2 1 )(kc Nếu k=0 Nếu k > 0 41 869 -439 -101 114 19 6 -61 -42 -110 65 143 -18 -78 -62 -2 38 31 -4 -37 -7 -67 8 55 -43 C = -8 28 23 -10 -2 57 -26 -56 -2 -3 109 -69 -33 41 6 9 -24 -27 -26 9 -29 33 6 -10 13 4 -8 -46 -13 33 38 -43 41 34 6 29 5 -31 -24 40 Trong miền tần số giữa của khối C, ta chọn hai hệ số bất kỳ là C[4, 2]=-18 và C[2, 5] = -3. Tính độ lệch d = | |-18| + |-3| | mod 26 = 21 mod 26 = 21. Với bit thủy vân b = 0 thì ta phải thay đổi một trong hai hệ số C[4, 2] =-18 hoặc C[2, 5] = -3 đã chọn để thu được d <2t+1. Vì C[4, 2]= -18 có giá trị tuyệt đối lớn hơn C[2, 5], theo công thức (1.6.3) ta tính giá trị mới của C[4, 21] là: C[4, 2] = C[4, 2] – (d - INT(0.25a)) = -18 – (21 – INT(0.25 x 26) = -33. 42 Khi đã thay đổi hệ số C[4, 2] = -33 ta thực hiện phép biến đổi ngược IDCT(C) và thu được khối B’: Tính B’[x,y] như sau: 7 7 0 0 ( ) ( ) (2 1) (2 1)'( , ) ( , ) cos cos 2 2u v C u C v x u y vB x y C u v M NM N                    Trong đó:      1 2 1 )(kc 30 85 70 60 13 155 183 149 26 76 18 39 160 154 136 137 27 60 46 66 190 164 144 141 B’= 14 15 16 67 113 122 192 171 89 76 14 102 169 105 199 176 20 9 13 217 141 200 164 140 18 15 12 177 243 238 190 105 18 17 85 179 170 238 191 187 Nếu k=0 Nếu k > 0 43 3) Quá trình tách thủy vân Input - Ảnh đã nhúng thủy vân F’. - Khóa K (nếu có). Output - Thủy vân đã nhúng W biểu diễn qua dãy bit bk. Thuật toán: Bước 1: Chia ảnh F’ đã nhúng thủy vân thành các khối 'kB . Bước 2: Biến đổi DCT các khối 'kB Bk = DCT( 'kB ) Bước 3: Lấy ra vị trí hai hệ số đã biến đổi Bk[i, j] và Bk[p, q] Bước 4: Tính d = | |Bk[i, j]| - |Bk[p, q]| | mod a với a=2(2t+1) đã chọn khi nhúng thủy vân. Bước 5: Nếu d≥2t+1 thì được bit bk=1 ngược lại bk=0 Bước 6: Ghép các bit bk tách được từ các khối để được thủy vân đầy đủ W. Thí dụ (1.6.3.1.b): Với khối B’ có được trong thí dụ (1.6.3.1.a), quá trình tách thủy vân như sau. Ta thực hiện phép biến đổi DCT của khối B’ để thu được khối B sau 869 -439 -101 114 19 6 -61 -42 -110 65 143 -33 -78 -62 -2 38 31 -4 -37 -7 -67 8 55 -43 B = -8 28 23 -10 -2 57 -26 -56 -2 -3 109 -69 -33 41 6 9 -24 -27 -26 9 -29 33 6 -10 13 4 -8 -46 -13 33 38 -43 41 34 6 29 5 -31 -24 40 44 Ta lấy ra hai hệ số B[4, 2] = -33 và B[2, 5] = -3. Tính độ lệch d = | |B[4, 2] – |B[2, 5]| | mod 26 = 10. Ta thấy d < 2t +1 = 13, vậy bit b = 0 đã được giấu vào khối. 4) Phân tích thuật toán Kích thước khối ảnh nêu trong kỹ thuật là 8x8, tuy nhiên có thể chọn kích thước khác nhau tùy theo kích thước từng ảnh gốc và kích thước thực tế của thủy vân. Việc chọn một cặp hệ số trong miền tần số giữa có thể được chọn cố định cho tất cả các khối trong quá trình nhúng thủy vân. Khi đó, thủy vân có thể rất dễ bị phát hiện thông qua việc thử lần lượt các cặp hệ số trong miền tần số giữa. Có thể làm tăng độ an toàn và khó bị phát hiện thủy vân bằng cách đưa ra một thuật toán có sử dụng khóa cho sự lựa chọn cặp hệ số trong miền tần số giữa cho từng khối DCT. Khi đó, vị trí của các cặp hệ số được chọn cho quá trình nhúng thủy vân trong từng khối sẽ được sử dụng phụ thuộc vào khóa của quá trình tách thủy vân. Trong kỹ thuật, quá trình tách thủy vân không cần sử dụng ảnh gốc. Tham số a trong kỹ thuật đóng vai trò như là hệ số tương quan giữa tính ẩn và tính bền vững của thủy vân. Khi tăng hệ số a lên thì độ sai lệch của thủy vân giảm đi và như vậy nó bền vững hơn. Tuy nhiên, nếu tăng a thì chất lượng ảnh sau khi giấu sẽ giảm. Điều này rất dễ hiểu vì a lớn, nghĩa là phân lớp khoảng cách hai hệ số lớn nên khoảng cách biến đổi của một hệ số để thỏa mãn điều kiện giấu lớn dẫn đến ảnh hưởng nhiều đến chất lượng ảnh. 45 1.6.2.3 Cải tiến kỹ thuật thủy vân sử dụng phép biến đổi DCT 1) Ý tưởng Kỹ thuật thủy vân ở trên phụ thuộc vào việc chọn cặp hệ số thuộc miền tần số giữa của khối biến đổi DCT để biến đổi, sao cho thỏa mãn điều kiện nhúng thủy vân. Các hệ số này được chọn cố định ở tất cả các khối hoặc chọn ngẫu nhiên. Tuy nhiên, các cách chọn đều có những hạn chế của nó. Thứ nhất, nếu chọn cố định các cặp hệ số thì việc dò tìm và gỡ thủy vân của những người sử dụng ảnh bất hợp pháp là khá dễ dàng và do đó hệ thống không đảm bảo an toàn cho thủy vân. Thứ hai, trong cả hai cách chọn đều dẫn đến khả năng phải biến đổi cặp hệ số cho phù hợp với điều kiện nhúng bit thủy vân tương ứng. Thao tác này dẫn đến chất lượng ảnh sau khi nhúng thủy vân bị ảnh hưởng đáng kể. Kỹ thuật sau đưa ra cách khắc phục các hạn chế trên bằng cách xác định các cặp hệ số trong miền tần số giữa thỏa mãn điều kiện nhúng thủy vân, việc biến đổi cặp hệ số chỉ diễn ra khi trong khối không có cặp hệ số nào thỏa mãn, điều này làm giảm đáng kể sự thay đổi giá trị các điểm ảnh. Hơn nữa trong các cặp hệ số đã tìm được thỏa mãn điều kiện nhúng, phương pháp chọn ngẫu nhiên cho từng khối làm tăng tính bí mật của thủy vân trong ảnh, việc phát hiện thủy vân khi không biết thông tin khóa là phức tạp. 2) Quá trình nhúng thủy vân Input - Thủy vân W: là một chuỗi các bit hoặc một ảnh nhị phân. - Một ảnh F kích thước mxn. Output - Ảnh đã nhúng thủy vân F’. - Khóa K để tách thủy vân. Thuật toán: Bước 1: Ảnh F có kích thước mxn sẽ được chia thành (mxn)/64 khối 8x8, mỗi bit của thủy vân sẽ được giấu trong một khối Bk. Bước 2: Chọn một khối bất kì Bk và biến đổi DCT khối đó thu được kC . Ck = DCT(Bk) 46 Bước 3: Trong miền tần số giữa của khối Ck. Xác định Ck[i, j] là phần tử nhỏ nhất Ck[p, q] là phần tử lớn nhất Bước 4: Gọi bit thủy vân cần nhúng là bk. if bk = 0 then maxk = [p, q]; mink = [i, j] else maxk = [i, j]; mink = [p, q]; endif; Bước 5: Khóa K =K  {maxk, mink} Bước 6: Tính d = Ck[p, q]-Ck[i, j] Bước 7: Với t nguyên dương chọn trước If d<t then Ck[p, q] = Ck[p, q] + (t - d)/2; Ck[i, j] = Ck[i, j] – (t - d)/2; Bước 8: Thực hiện phép biến đổi ngược IDCT 'kB = IDCT(Ck) Bước 9: Ghép các khối ảnh 'kB để được ảnh chứa thủy vân F’. Thí dụ 1.6.3.2.a Giả sử ta cần nhúng bit thủy vân b=0 vào khối B như trong thí dụ 1.6.3.1a. Quá trình nhúng thủy vân như sau: Biến đổi DCT(B) để thu được khối C như trong thí dụ 1.6.3.1a. Trong miền tần số giữa của C ta có: - Phần tử lớn nhất là C[2, 3] = 143 - Phần tử nhỏ nhất là C[2, 5] = -78 Theo bước 4 của thuật toán, với b = 0 thì max = [2, 3] và min =[2, 5]. Khóa K = {[2, 3]; [2, 5]} Độ lệch d = C[2, 3] - C[2, 5] = 143 – (-78) = 221. 47 Chọn t = 235, khi đó d < t. Ta thực hiện phép biến đổi sau: C[2, 3] = C[2, 3] + (t-d)/2 = 143 + (235-221)/2 = 150. C[2, 5] = C[2, 5] - (t-d)/2 = -78 – (235-221)/2 = -85. Khối C mới sẽ là 869 -439 -101 114 19 6 -61 -42 -110 65 150 -18 -85 -62 -2 38 31 -4 -37 -7 -67 8 55 -43 C = -8 28 23 -10 -2 57 -26 -56 -2 -3 109 -69 -33 41 6 9 -24 -27 -26 9 -29 33 6 -10 13 4 -8 -46 -13 33 38 -43 41 34 6 29 5 -31 -24 40 Thực hiện biến đổi ngược IDCT(C) ta thu được khối B’ như sau 34 86 67 55 12 160 185 146 28 77 16 35 159 157 138 135 29 60 44 63 190 167 145 139 B'= 15 15 15 66 113 123 192 170 88 76 14 102 169 104 199 177 19 8 15 220 142 198 163 141 15 14 15 181 243 234 188 107 14 16 88 184 171 234 188 190 48 3) Quá trình tách thủy vân Input - Ảnh đã nhúng thủy vân F’. - Khóa K để tách thủy vân. Output - Thủy vân W: là một chuỗi các bit. Thuật toán: Bước 1: Chia ảnh F’ đã nhúng thủy vân thành các khối 'kB . Bước 2: Biến đổi DCT các khối 'kB Bk = DCT( 'kB ) Bước 3: Đọc các hệ số tương ứng với các khối Bk trong các biến maxk và mink của khóa K. Bước 4: If Bk(maxk) - Bk(mink) >0 then bk = 0 else bk = 1 Bước 5: Ghép các bit bk để thu được thủy vân W. 49 Thí dụ 1.6.3.2.b: Thực hiện phép biến đổi ngược khối B’ đã có trong thí dụ 1.6.3.2.a ta thu được khối B. Khối B này thực chất là khối C đã mô tả trong thí dụ 1.6.3.2.a. Với Khóa K = {[1, 2]; [1, 4]} ta lấy ra hai hệ số B[1, 2] = 136 và B[1, 4] = -85. B[1,2] – B[1,4] = 136 – (-85) = 221>0 ta tách được bit thủy vân b = 0 đã nhúng. 4) Phân tích thuật toán Theo bước 3 và bước 4 của quá trình nhúng thủy vân vào từng khối Ck thì việc nhúng thủy vân luôn thỏa tính chất nếu bit cần nhúng là bit 0 thì Ck(max)>Ck(min), ngược lại nếu bit cần nhúng là bit 1 thì Ck(max)<Ck(min). Theo bước 6 của quá trình nhúng thủy vân, độ lệch giữa hai hệ số được chọn sau khi nhúng được đảm bảo tối thiểu là t, đồng thời công thức biến đổi hệ số trọng bước 5 cũng thể hiện khi độ lệch giữa hai hệ số được chọn còn nhỏ hơn t thì cả hai hệ số sẽ đều được biến đổi tăng và giảm một lượng bằng (t - d)/2. Về khoảng cách thì việc thay đổi này cũng tương đương với việc chỉ tăng (hoặc giảm) Ck[p, q] lên (t - d). Như vậy, hệ số bị thay đổi lớn, gây ảnh hưởng đến thị giác của ảnh chứa thủy vân. Với quá trình tách thủy vân không cần ảnh gốc, cũng không liên quan đến số nguyên dương t đã chọn trong quá trình nhúng thủy vân. 1.6.2.4 Giải pháp nâng cao độ an toàn cho thủy vân Trong quá trình nhúng thủy vân đã trình bày ở mục trên, các khối DCT sau khi nhúng luôn thỏa tính chất hai hệ số được chọn trong miền tần số giữa có độ lệch cao nhất. Điều này dẫn đến việc một người bất kỳ có thể dò tìm thủy vân bằng cách đọc vào các khối DCT rồi tìm ra cặp hệ số có độ lệch lớn nhất trong khối. Trong mục này trình bày giải pháp bổ sung cho kỹ thuật nhúng thủy vân ở trên để được hệ thủy vân có độ an toàn cao. 1) Quá trình nhúng thủy vân Input - Thủy vân W: là một chuỗi các bit hoặc một ảnh nhị phân. - Một ảnh F kích thước mxn. Output - Ảnh đã nhúng thủy vân F’. - Khóa K để tách thủy vân. 50 Thuật toán: Bước 1: Ảnh F có kích thước mxn sẽ được chia thành (mxn)/64 khối 8x8, mỗi bit của thủy vân sẽ được giấu trong một khối Bk. Bước 2: Chọn một khối bất kì Bk và biến đổi DCT khối đó thu được kC . Ck = DCT(Bk) Bước 3: Với mỗi khối Ck Gọi )(kMID = { kix }i =1,2,…,22 với xi thuộc vào miền tần số giữa của khối Ck. Gọi )(kDM là ma trận kích thước 22x22. Mỗi phần tử xác định như sau : k j k i k xxjiDM ],[)( trong đó kix và kjx là các phần tử của MID (k). Gọi TK là dãy gồm t phần tử trong DM có giá trị lớn hơn hoặc bằng  ( là hệ số dương đã chọn trước). Bước 4: If t = 0 then thực hiện bước 5 else Chọn ngẫu nhiên một số tự nhiên nt  [1, t] Tính cặp hệ số có độ lệch tương ứng bằng TK(nt). Xác định Ck[u,v] là phần tử nhỏ hơn trong cặp hệ số Ck[p,q] là phần tử lớn hơn trong cặp hệ số Thực hiện bước 6. Endif; 51 Bước 5: Trong miền tần số giữa của các khối Ck. Xác định Ck[u,v] là phần tử nhỏ nhất trong cặp hệ số Ck[p,q] là phần tử lớn nhất trong cặp hệ số Tính d = Ck[p,q] - Ck[u,v] If d< then Ck[p,q] = Ck[p,q] + (-d)/2; Ck[u,v] = Ck[u,v] – (-d)/2; Endif ; Bước 6: Gọi bit thủy vân cần nhúng là bk. if bk = 0 then maxk = [p,q]; mink = [u,v] else maxk = [u,v]; mink = [p,q]; endif; Bước 7: Khóa K = {maxk, mink} Bước 8: Thực hiện phép biến đổi ngược IDCT 'kB = IDCT(Ck) Bước 9: Ghép các khối ảnh 'kB để được ảnh chứa thủy vân F’. 52 Thí dụ 1.6.3.3.a: Giả sử ta có khối B và khối C =DCT(B) như trong thí dụ 1.6.3.1.a. MID là dãy gồm 22 phần tử thuộc miền tần số giữa của C theo một thứ tự nào đó. i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 MID(i) -7 -4 143 115 -3 27 -37 -18 18 -23 -2 22 -7 -78 7 12 -27 i 18 19 20 21 22 MID(i) 109 -10 -67 -62 -62 Ma trận độ lệch DM22x22 có các phần tử đối xứng nhau qua đường chéo chính như sau 0 3 150 122 4 34 30 11 25 16 5 29 0 71 14 19 20 116 3 60 55 55 0 147 119 1 31 33 14 22 19 2 26 3 74 11 16 23 113 6 63 58 58 0 28 146 116 180 161 125 166 145 121 150 221 136 131 170 34 153 210 205 205 0 118 88 152 133 97 138 117 93 122 193 108 103 142 6 125 182 177 177 0 30 34 15 21 20 1 25 4 75 10 15 24 112 7 64 59 59 0 64 45 9 50 29 5 34 105 20 15 54 82 37 94 89 89 0 19 55 14 35 59 30 41 44 49 10 146 27 30 25 25 0 36 5 16 40 11 60 25 30 9 127 8 49 44 44 0 41 20 4 25 96 11 6 45 91 28 85 80 80 0 21 45 16 55 30 35 4 132 13 44 39 39 0 24 5 76 9 14 25 111 8 65 60 60 0 29 100 15 10 49 87 32 89 84 84 0 71 14 19 20 116 3 60 55 55 0 85 90 51 187 68 11 16 16 0 5 34 102 17 74 69 69 0 39 97 22 79 74 74 0 136 17 40 35 35 0 119 176 171 171 0 57 52 52 0 5 5 0 0 0 53 Trường hợp 1: Giả sử với  =170, dãy TK được xây dựng từ DM (các phần tử trong ma trận DM ≥ 170 được đánh dấu trong bảng trên). i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 TK(i) 180 221 170 210 205 205 193 182 177 177 187 176 171 171 Số lượng phần tử trong TK là t = 14>0. Chọn ngẫu nhiên số nt  [1, 14], chẳng hạn nt = 7. Khi đó, cặp hệ số trong khối sẽ được chọn tương ứng với TK[7] = 193 = DM[4, 14]. Phần tử DM[4, 14] ứng với phần tử MID[4] và MID[14]. Từ đó ta có cặp hệ số ứng với MID[4] = 115 = C[1, 4] và MID[14] = -78 = C[2, 5]. Bit thủy vân cần nhúng là b = 0, khi đó Max = [1, 4], min = [2, 5]; Khóa K ={[1, 4], [2, 5]} Trong trường hợp này, ta có thể chọn một trong 14 cặp hệ số đương nhiên đã thỏa mãn điều kiện nhúng bit thủy vân mà không cần biến đổi. Trường hợp 2: Giả sử với  = 235, khi đó không tồn tại phần tử nào trong ma trận DM thỏa điều kiện lớn hơn hoặc bằng . Tức là t = 0. Ta thực hiện bước 5 trong thuật toán. Trong miền tần số giữa của khối C, chọn cặp hệ số C[p, q] = C[2, 3] = 143, C[u, v]= C[2, 5] = -78. Tính độ lệch d = C[2,3] – C[2,5] = 143 – (-78) = 221 Vì d <  =235 nên tính giá trị mới cho cặp hệ số đã chọn giống như trong thí dụ 1.6.3.2. Với bit thủy vân cần nhúng b=0, ta có khóa K ={max = [2, 3]; min = [2, 5]} Thực hiện phép biến đổi ngược IDCT với khối C, ta thu được khối B’. 2) Quá trình tách thủy vân Quá trình tách thủy vân được thực hiện như trong 1.6.3.2. 54 3) Phân tích thuật toán Thuật toán đưa ra một ma trận đô lệch nhằm tính giá trị độ lệch giữa các cặp hệ số thuộc miền tần số giữa của các khối DCT. Căn cứ vào sự so sánh các phần tử thuộc ma trận độ lệch với hệ số  để chọn ra những cặp hệ số không cần biến đổi đã thỏa mãn điều kiện giấu. Trong trường hợp ở khối hiện tại không có cặp hệ số nào thỏa mãn điều kiện giấu thì mới thay đổi hệ số. Trong trường hợp khối đang xét có nhiều hơn một cặp hệ số thỏa mãn điều kiện giấu thì thuật toán đưa ra chọn ngẫu nhiên một cặp để ghi nhận và sử dụng làm khóa cho quá trình tách thủy vân. Điều này làm tăng tính bí mật cho thủy vân. KẾT LUẬN Trong chương này luận văn đã trình bày sơ bộ về sự phát triển của các kỹ thuật giấu tin, các khái niệm ban đầu về giấu tin trong các môi trường đa phương tiện khác nhau. Trong đó đã đi sâu vào phân tích đánh giá các kỹ thuật giấu tin trong môi trường ảnh số như giấu tin trong khối bit sử dụng tính chẵn lẻ của tổng số bit 1 trong khối, giấu tin sử dụng ma trận khóa và ma trận trọng số. Mỗi phương pháp đều có những ưu nhược điểm nhất định từ đó đặt ra các yêu cầu về giấu tin sao cho thông tin được đảm bảo về độ an toàn của tin giấu đồng thời cũng giấu được nhiều thông tin trong ảnh nhất có thể. Người ta đã chứng minh được rằng: Nếu coi mỗi điểm của dữ liệu ảnh (ảnh màu hoặc ảnh đa cấp xám) là một pixel, mỗi pixel là một byte (8 bit) hoặc là một số tự nhiên từ 0 đến 255 thì để đảm bảo bí mật, số lượng các bit mà một thông điệp cần giấu so với tổng số các pixel ảnh không được vượt quá 12,5%. Nghĩa là một pixel ảnh không được giấu quá 1 bit dữ liệu mật. Đồng thời, trong chương này luận văn đã trình bày những khái niệm cơ bản của thủy vân, đồng thời nghiên cứu đánh giá một số kỹ thuật thủy vân trên miền tần số của ảnh sử dụng phép biến đổi DCT. Qua việc đánh giá những ưu điểm và hạn chế của từng kỹ thuật để đưa ra những cải tiến phù hợp nhằm góp phần xây dựng thủy vân đáp ứng được yêu cầu về tính ẩn và tính bền vững của thủy vân, phục vụ cho mục đích bảo vệ bản quyền. 55 Chương 2. MỘT SỐ KHẢ NĂNG PHÁT HIỆN ẢNH CÓ GIẤU TIN 2.1 PHƯƠNG PHÁP PHÁT HIỆN ẢNH GIẤU TIN Kể từ khi ra đời, giấu tin đã và đang làm tốt vai trò của nó trong nhiều lĩnh vực như bảo vệ thông tin an toàn trong quá trình trao đổi, bảo vệ bản quyền trong quá trình phân phối… Tuy nhiên giấu tin cũng nảy sinh nhiều vấn đề khác liên quan. Rõ ràng việc sử dụng các kỹ thuật để giấu tin không phải là bất hợp pháp song cũng có những trường hợp lợi dụng kỹ thuật giấu tin để thực hiện những hành vi bất hợp pháp như tuyên truyền những sản phẩm văn hóa không lành mạnh, truyền những thông tin về kế hoạch tấn công khủng bố, lúc đó hậu quả của nó thật nghiêm trọng. Có ý kiến cho rằng mạng lưới khủng bố Al-Qaida đã sử dụng hình thức liên lạc này để giao tiếp trong kế hoạch tấn công nước Mỹ ngày 11 tháng chín năm 2001. Chúng đã nhúng các thông điệp vào hình ảnh rồi đặt trên các bản tin hoặc trên các trang web công khai. Các tên khủng bố chỉ việc lấy hình ảnh về và trích các thông điệp ẩn bên trong. Và như vậy chúng đã có một kênh thông tin liên lạc “an toàn, hiệu quả” mà không gây bất kỳ sự nghi ngờ nào [24]. Từ sử dụng sai chức năng của giấu tin ở trên cũng đặt ra vấn đề làm thế nào để phát hiện được phương tiện chứa tin có tiềm ẩn bên trong các tin giấu hay không, và thông tin chứa trong đó là gì nhằm có thể hỗ trợ trong việc ngăn ngừa các thảm kịch xảy ra. Mặt khác việc nghiên cứu khả năng phát hiện thông tin ẩn cũng sẽ làm tăng mức độ an toàn cho kỹ thuật giấu tin, đăc biệt là kỹ thuật giấu tin mật. Trong chương này luận văn đề cập đến bài toán “nghiên cứu khả năng phát hiện ảnh giấu tin”. Mục tiêu của bài toán là phát hiện “có tồn tại tin giấu trong ảnh hay không?”. Trên thế giới đã có nhiều cách tiếp cận khác nhau để giải quyết cho bài toán phát hiện tin giấu. Trong luận văn này tôi sẽ trình bày một số kỹ thuật phát hiện sự tồn tại của tin giấu theo hướng tiếp cận sử dụng lý thuyết xác suất thống kê. 56 2.1.1 Bài toán phân tích tin giấu Phân tích tin giấu hay còn gọi là tấn công một hệ giấu tin (Steganalysis) là phương pháp để phát hiện, trích rút, phá hủy hay sửa đổi thông tin đã giấu. Việc phân tích được coi là thành công hay không còn tùy theo ứng dụng. Đối với việc liên lạc bí mật, việc phát hiện và chứng minh một ảnh có chứa tin mật được coi là thành công. Đối với bảo vệ bản quyền số hay chống giả mạo thì việc phân tích được coi là thành công nếu không chỉ phát hiện ra thủy vân mà còn phá hủy hay sửa đổi nó, nhưng không làm giảm chất lượng ảnh mang. Bài toán chúng ta xem xét ở đây là các ứng dụng trên hệ giấu tin mật. Nếu ta có rất ít (hoặc không có) các tri thức về các thuật toán giấu tin mật cũng như các tham số khác thì có hai vấn đề cần giải quyết đó là: Thứ nhất, phát hiện thông tin ẩn tiềm tàng trong các dữ liệu được quan sát. Thứ hai là lấy ra thông điệp ẩn đã giấu trong dữ liệu được quan sát. Cũng có khi bài toán đặt ra phải giải quyết cả hai công việc trên. Các kỹ thuật phân tích giấu tin mật hiện tại tập trung vào việc phát hiện ra sự có mặt hay không các thông điệp ẩn trong dữ liệu (ảnh) được quan sát. Bài toán trích chọn ra các thông điệp bí mật là bài toán khó hơn bài toán phát hiện, nhưng bài toán phát hiện làm tiền đề cho việc trích chọn. Như vậy, có thể xác định hai mục tiêu rõ ràng của bài toán phân tích trên hệ giấu tin mật là: Phân tích giấu tin bị động (Passive steganalysis): Phát hiện sự hiện diện hay không của thông điệp bí mật trong các dữ liệu được quan sát. Phân tích giấu tin chủ động (Active steganalysis): Trích chọn (có thể xấp xỉ) một phiên bản của thông điệp bí mật từ một phương tiện chứa tin. Trong khuôn khổ của luận văn này, các kỹ thuật trình bày tập trung vào giải quyết vấn đề phát hiện sự tồn tại của thông điệp bí mật bằng cách ước lượng chiều dài thông điệp đã giấu trên một ảnh quan sát. 57 2.1.2 Phân loại phương pháp phát hiện ảnh giấu tin Theo Fridrich et. al. các phương pháp phân tích giấu tin mật có thể gồm các loại sau: Phân tích trực quan, phân tích định dạng ảnh, phân tích thống kê [16, 22, 25]. Phân tích trực quan: Đây là phương pháp đơn giản nhất mặc dù kết quả thường không đáng tin cậy. Để phát hiện khả năng một ảnh có giấu tin hay không bằng việc phân tích ảnh một cách trực quan và tìm kiếm những “bất thường”. Nhiều phương pháp giấu tin mật, bao gồm cả giấu tin dựa trên LSB và phương pháp dựa trên DCT đều loại bỏ những biến dạng ở những vùng ảnh mịn hoặc thuần nhất một cách dễ nhận thấy. Thật vậy, việc thay đổi bảng mầu (của một ảnh mầu) dù nhỏ để giấu thông điệp bí mật có thể dẫn đến kết quả là sự thay đổi mầu sắc lớn trên ảnh gốc, đặc biệt là nếu ảnh gốc có chứa các mầu sắc khác nhau ở mức độ cao. Cũng bởi thực tế là với một ảnh mầu tự nhiên, sự thay đổi bit một trong các mầu là hiếm. Mặc dù các kỹ thuật phân tích trực quan là đơn giản nhưng chúng khó thực hiện một cách tự động và độ tin cậy của chúng vẫn rất đáng ngờ. Phân tích định dạng ảnh: Có nhiều định dạng tệp tin ảnh khác nhau như BMP, GIF, TIIF, JPEG. Mỗi loại có đặc điểm và cấu trúc định dạng tệp tin khác nhau. Do đó, khi thực hiện giấu tin, chẳng hạn giấu tin theo LSB, sẽ cho sự thay đổi trên ảnh kết quả ở các điểm ảnh là khác nhau. Và khi thực hiện phát hiện ảnh giấu tin cũng vậy. Chẳng hạn, với ảnh JPEG [1]: Ảnh JPEG sử dụng phép biến đổi DCT để biến đổi liên tiếp các khối điểm ảnh 8x8 vào ma trận 64 hệ số DCT. Bít LSB của các hệ số DCT được sử dụng như là các bít dư thừa mà ta sẽ giấu các các bit thông điệp ẩn vào trong đó. Sự thay đổi hệ số DCT đơn lẻ sẽ tác động lên tất cả 64 điểm ảnh. Vì lý do đó không thể áp dụng việc phân tích trực quan đối với loại ảnh này. Phân tích thống kê: Theo Plitzman và Westfeld, lý thuyết thống kê có thể áp dụng để phân tích thống kê các cặp giá trị (cặp giá trị điểm ảnh, cặp các hệ số DCT, cặp các chỉ số bảng mầu) để tìm sự khác biệt ở bít LSB. Trước khi giấu tin, trên ảnh chứa thông điệp (cover image), mỗi cặp hai giá trị là phân phối không đều. Sau khi giấu tin, giá trị trong mỗi cặp có xu hướng trở nên bằng nhau. Hơn nữa, nếu các kỹ thuật giấu tin mật giấu các bít thông điệp một cách tuần tự vào các điểm ảnh (hoặc các chỉ số bảng mầu hoặc các hệ số DCT) liên tiếp nhau, bắt đầu từ góc trên trái thì ta sẽ quan sát được sự thay đổi đột ngột trong các thống kê. Một số kỹ thuật thống kê sẽ được trình bày chi tiết ở phần cuối của chương này. 58 2.2 Cơ sở toán học 2.2.1 Các khái niệm Định nghĩa 2.1: Biến cố ngẫu nhiên (Biến cố). Sự kiện có thể xảy ra hoặc không thể xảy ra tùy thuộc vào kết quả của phép thử G được gọi là các biến cố ngẫu nhiên. Kí hiệu là A, B, …. Biến cố sơ cấp: là biến cố xảy ra khi và chỉ khi có một kết quả cụ thể trong số những kết quả của phép thử G. Kí hiệu là . Không gian mẫu: là tập hợp gồm tất cả các biến cố sơ cấp. Kí hiệu là  Định nghĩa 2.2: Xác suất của biến cố Giả sử  = {1, 2, …, k, …} là không gian mẫu đã cho. Mỗi biến cố sơ cấp k được gắn một trọng số pk = p(k) sao cho a. pk ≥ 0, với k ≥ 1. b. p1 + p2 + … + pk + … = 1 Khi đó với mỗi biến cố A  ta định nghĩa      Ak k k pAP   : )()( Số P(A) được gọi là xác suất của biến cố A. Định nghĩa 2.3: Đại số và -đại số, không gian đo, không gian xác suất Giả sử tập   . Kí hiệu P () là tập hợp gồm tất cả các tập con của tập . Lớp A  P() được gọi là một đại số nếu: a.   A b. A  A  A = \A  A. c. A, B  A  A B  A, A B  A. Lớp F  P() được gọi là -đại số nếu nó là đại số và ngoài ra d. từ An  F, n = 1, 2, … suy ra       11 , n n n n FAFA Cặp (, F) được gọi là một không gian đo. 59 Bộ ba (, F, P) là không gian xác suất với  là tập các biến cố sơ cấp; F là - đại số các tập con của ; P là xác suất trên F. Tập A  F được gọi là biến cố, P(A) là xác suất của biến cố A. Định nghĩa 2.4: Đại lượng ngẫu nhiên (biến ngẫu nhiên) Giả sử cho không gian xác suất (, A, P), và (R ,B, ) là không gian với độ đo . R là đường thẳng thực. B là không gian các tập Borel trên R.  là một độ đo trên R. Ánh xạ X :   R được gọi là đại lượng ngẫu nhiên (đ.l.n.n) hay còn gọi là biến ngẫu nhiên (b.n.n) nếu với mọi tập con B  B thì X-1(B) = { : X()  B} thuộc A. Tức là X(.) là hàm đo được đối với độ đo . - Đ.l.n.n rời rạc: Đ.l.n.n được gọi là rời rạc nếu tập hợp giá trị số mà nó có thể lấy hoặc hữu hạn hoặc vô hạn đếm được. - Đ.l.n.n liên tục: Đ.l.n.n được gọi là liên tục nếu tập hợp mọi giá trị số mà nó có thể lấy lấp đầy một khoảng nào đó của trục số. Định nghĩa 2.5: Hàm phân phối của một đ.l.n.n. Trong không gian xác suất (, A, P) cho một đ.l.n.n X. Ta gọi hàm số F(x)=P[X< x] là hàm phân phối của X, x  R. - Nếu X là đ.l.n.n rời rạc thì F(x) = P[X< x] =    xx i i xXP ][ - Nếu X là đ.l.n.n liên tục thì F(x) =   x dttf )( . Trong đó f(t) là hàm mật độ. Định nghĩa 2.6: Vectơ ngẫu nhiên n chiều (đ.l.n.n n chiều) Một vec tơ X  n chiều (X1, X2, ..., Xn) mà các thành phần Xi (1  i  n) của nó là các đ.l.n.n được gọi là một vecto ngẫu nhiên n chiều hay một đ.l.n.n n chiều. Định nghĩa 2.7: Hàm phân phối của đ.l.n.n n chiều Trong không gian xác suất (, A, P), hàm phân phối của đ.l.n.n X = (X1, X2, ..., Xn) là hàm số F(x1, x2, ..., xn) = P[X1 < x1, X2 < x2, …, Xn < xn] ở đó (x1, x2, ..., xn) Rn. 60 Định nghĩa 2.8: Hàm phân phối đồng thời liên tục Các đ.l.n.n X1, X2, ..., Xn được gọi là có phân phối đồng thời liên liên tục nếu phân phối đồng thời của X1, X2, ..., Xn là hàm liên tục trên Rn, nghĩa là tồn tại hàm f X1, X2, ..., Xn  0 trên Rn sao cho:        1 2 21 ...),...,,(...),...,,( 2121,...,,21 x x x nnXXXn n n dtdtdttttfxxxF Hàm f X1, X2, ..., Xn được gọi là hàm mật độ đồng thời của X1, X2, ..., Xn. Các đặc trưng của các đ.l.n.n Định nghĩa 2.9: Kì vọng và phương sai của đ.l.n.n Giả sử X là đ.l.n.n rời rạc nhận n giá trị x1, x2, …, xn với xác suất tương ứng là p1, p2, …, pn; tức là xác suất p{X = xk} = pk, k = 1,…, n và 1 1   n k kp . Kỳ vọng toán học của đ.l.n.n rời rạc X là    n k kk pxXE 1 .)( . Kỳ vọng của đ.l.n.n liên tục X với miền giá trị là đoạn [a,b] là một số xác định bởi  b a dxxxfXE )()( Phương sai của X được định nghĩa là 222 )()()( EXXEEXXEDX  Định nghĩa 2.10: Độ lệch chuẩn của đ.l.n.n X Độ lệch chuẩn của đ.l.n.n X, kí hiệu là X được xác định bằng DXX  . Trong đó DX là phương sai của X. Định nghĩa 2.11: Phân phối mũ. Đ.l.n.n X gọi là có phân phối mũ với tham số >0 nếu hàm mật độ của nó có dạng      0 )( xe xf  Hàm phân phối có dạng       0 1 )( xe xF  Nếu x ≥ 0 Nếu x ≥ 0 61 Định nghĩa 2.12: Phân phối Gamma. Đ.l.n.n X có phân phối Gamma với các tham số , p (, p >0) nếu hàm mật độ của nó có dạng 1 ( ) if x 0( ) 0 p p xx e f x p        Định nghĩa 2.13: Phân phối 2 (Khi-bình phương) với n bậc tự do Phân phối 2 (Khi-bình phương) với n bậc tự do, kí hiệu là 2(n), nếu hàm mật độ của nó có dạng                0 . 2. 2 1 )( 2 1 2 2 xn n exnxf Ta thấy phân phối 2(n) với n bậc tự do là trường hợp đặc biệt của phân phối Gamma với tham số  = ½ và p = n/2. Định nghĩa 2.14: Phân phối chuẩn Đ.l.n.n X được gọi là có phân phối chuẩn với kỳ vọng a, và phương sai 2 > 0 nếu hàm mật độ của nó có dạng: 2 2 2 )( 2 1)(   ax exf   với -  < x < + Định nghĩa 2.15: Phân phối nhị thức Giả sử X1, X2, …, Xn là một dãy các đ.l.n.n độc lập, có phân bố nhị thức (chỉ nhận các giá trị là 0 và 1 với xác suất tương ứng là p và q = 1-p) trong đó Xi  {A, A }, bây giờ ta gọi X là số lần xuất hiện của biến cố Xi = A với i = 1, …, n trong dãy khi đó xác suất để cho “X = k”, (k = 0, 1, …, n) sẽ là   knknk qpCkXP  với q = 1-p Phân phối này được gọi là phân bố nhị thức. Nếu x ≥ 0 trong đó    0 1)( dxexp xp 62 2.2.2 Các định lý Định lý 2.1: Nếu X1, X2, …, Xn là dãy các đ.l.n.n độc lập, mỗi Xi là một phân phối chuẩn N(ai, 2i ), i = 1, …, n. Khi đó, tổng X = X1 + X2 + …+ Xn là đ.l.n.n có phân phối chuẩn         n i i n i iaN 1 2 1 ,  . Trường hợp đặc biệt X1, X2, …, Xn độc lập cùng phân phối chuẩn N(a, 2) tổng X = X1 + X2 + …+ Xn có phân phối chuẩn N(na, n2). Định lý này đúng cho trường hợp X1, X2, …, Xn có phân bố nhị thức, phân phối Poisson, X2 và phân phối đa thức). Định lý 2.2: Giả sử X1, X2, …, Xn là dãy các đ.l.n.n độc lập, mỗi Xi có phân bố chuẩn N(ai, 2 i ), i = 1, …, n, khi đó đ.l.n.n       n i i ii aXY 1 2 2  có phân phối X2 với n bậc tự do. Định lý 2.3: Nếu Xi có phân phối chuẩn N(a, 2) với i = 1, …, n. thì     22 2 1 11 X n XXn i với n -1 bậc tự do. Định lý 2.4: Cho X1, X2, …, Xn là mẫu ngẫu nhiên độc lập được lấy từ đ.l.n.n X có phân bố xác suất bất kỳ và nếu tồn tại a = EX, 2 = DX với a, 2 là hai hằng số tùy ý thì naX   có phân bố tiệm cận phân bố chuẩn N(0, 1) khi n  . Trong đó    n i iXn X 1 1 Định lý 2.5: Giả sử ta làm các thí nghiệm một cách độc lập và trong mỗi thí nghiệm sự kiện A xuất hiện với xác suất p. Gọi m là số lần xuất hiện biến cố A trong n thí nghiệm. Khi đó đ.l.n.n n pp p n m X )1(    có phân bố tiệm cận chuẩn N(0, 1) khi n . 63 2.3 KỸ THUẬT PHÂN TÍCH CẶP GIÁ TRỊ ĐIỂM ẢNH 2.3.1 Khái niệm cặp giá trị Khái niệm về cặp giá trị (PoV - Pairs of Values) được Pfitzmann và Westfeld đưa ra. Cho một ảnh I. Gọi j là giá trị của điểm ảnh (pixel) trên ảnh I. Nếu I là ảnh đa cấp xám 8-bit thì j  [0,255]. Nếu j chẵn (j= 2i) thì sau phép lật bit giá trị của j là 2i+1, nếu j là lẻ (j = 2i+1) thì sau phép lật bit giá trị của j là 2i. Như vậy, nếu một giá trị điểm ảnh ở trong một cặp thì sau khi giấu tin giá trị của nó vẫn nằm trong một cặp có tính chất chẵn lẻ tương tự. PoV là một cặp hai giá trị điểm ảnh (2i, 2i+1) và hai giá trị trong cặp này chỉ sai khác nhau ở bit thấp nhất. Trong thuật toán trình bày dưới đây có liên quan đến khái niệm tần số xuất hiện của giá trị điểm ảnh j. Đó là số lần xuất hiện của giá trị điểm ảnh j trên ảnh. Kỹ thuật PoVs còn được gọi là phương pháp thống kê X2 (khi-bình phương – Chi-squared) và được áp dụng rất thành công đối với việc phát hiện giấu tin mật LSB một cách tuần tự [17, 20, 22, 23, 25, 26]. Có nhiều kỹ thuật PoV khác nhau như PoV2, PoV2r, PoV3. Trong đó PoV2 và PoV2r chỉ kiểm tra một tập con các điểm ảnh được chọn bởi người dùng. PoV2 kiểm tra phần trăm các điểm ảnh hiện tại (được chọn bởi người dùng) một cách tuần tự, bắt đầu từ góc trên trái của ảnh. PoV2r cũng kiểm tra một cách tuần tự phần trăm các điểm ảnh hiện tại được chọn bởi người dùng nhưng bắt đầu ở một điểm nào đó trên ảnh và sau đó thực hiện phép lật bit cho đến điểm cuối cùng được chọn. PoV3 kiểm tra mỗi tổng phần trăm các điểm ảnh từ 1% đến 100% và trả về xác suất của mỗi tập con các điểm ảnh trên ảnh kiểm tra. Các điểm ảnh cũng được kiểm tra một cách tuần tự, bắt đầu từ góc trên bên trái của ảnh. Thực tế PoV3 kiểm tra các nhóm điểm ảnh theo một trật tự nào đó. Mục dưới đây sẽ trình bày chi tiết kỹ thuật phát hiện tin giấu PoV3. 64 2.3.2 Thuật toán PoV3 Ý tưởng Với một ảnh I cần kiểm tra, trước tiên ta thống kê tần số của các giá trị điểm ảnh chẵn, lẻ có mặt trong ảnh I. Ta xác định xác suất giấu tin của ảnh thông qua việc áp dụng tiêu chuẩn phân phối 2 đối với tần số của các cặp PoV. Input - Ảnh I cần kiểm tra Output p: Xác suất giấu tin trong ảnh I Thuật toán Bước 1: Đọc vào ảnh I Bước 2: Đọc dữ liệu ảnh vào một ma trận Mmxn. Bước 3: Khởi tạo giá trị ban đầu cho vecto X, Y. For each k  [0, 127] X[k] = 0; Y[k] = 0; Bước 4: Tính X[k] là tần số xuất hiện của các điểm ảnh có giá trị chẵn trên ảnh; Tính Y[k] là tần số xuất hiện của các điểm ảnh có giá trị lẻ trên ảnh; Bước 5: Giả sử ta có N cặp PoV Với mọi k Nếu (X[k] + Y[k])  4 thì X[k] = Y[k] = 0 ; N = N-1 ; 65 Bước 6: For each k Z[k]= (X[k] + Y[k])/2; Bước 7: Giả sử ta có N cặp PoV, theo phương pháp thống kê Khi-bình phương với N-1 bậc tự do ta tính      127 0 2 2 1 ][ ])[][( k N kZ kZkX  (1) Bước 8: Tính p là xác suất của việc giấu tin dxxe N p N Nx N         2 1 0 1 2 1 2 2 1 ) 2 1(2 11  (2) Phân tích thuật toán Thông thường đối với ảnh kiểm tra là một ảnh đa cấp xám 8-bit ta có 256 mức xám khác nhau. Thuật toán xác định các cặp phần tử là các giá trị mức xám chẵn, lẻ nên số lượng các phần tử chẵn, lẻ như vậy có không quá 256/2=128 phần tử. Ta xây dựng hai vecto X(x0, x1, ..., xk), Y(y0, y1, ..., yk) để thống kê tần số xuất hiện của các điểm ảnh, với 0 k  127. Mỗi phần tử trong X sẽ lưu tần số xuất hiện các điểm ảnh chẵn (X[k] = 2k), mỗi phần tử trong Y sẽ lưu tần số xuất hiện các điểm ảnh lẻ (Y[k] = 2k+1) với 0 k  127. Ban đầu khởi tạo các phần tử trong X và trong Y đều bằng 0. Sau đó thuật toán thực hiện việc thống kê các giá trị mức xám có trong ảnh cần kiểm tra và tương ứng tăng giá trị của các phần tử trong X và Y. Gọi Zlà vectơ mỗi phần tử Z[k] là giá trị trung bình cộng của X[k] và Y[k]. Giả sử rằng ta có N cặp PoV, có k mức chẵn (lẻ) 0 k  127, nếu X[k] + Y[k]  4 thì X[k] = Y[k] = Z[k] = 0 và N = N–1. Nếu ảnh có chứa thông tin ẩn thì X[k] = Z[k] đối với mọi k, trong phương trình (1) 2 1NX sẽ bé và do đó tích phân    2 1 0 1 2 1 2 NX Nx dxxe sẽ bé và từ (2) suy ra xác suất p sẽ lớn. Ngược lại thì 2 1NX sẽ lớn suy ra xác suất p sẽ bé. Căn cứ vào sự lớn bé của xác suất p ta sẽ quyết định được ảnh có giấu tin hay không. Hơn nữa Westfeld và Pfitzmann còn khẳng định rằng nếu ít hơn 100% các điểm ảnh có chứa thông tin được giấu thì xác suất giấu tin sẽ giảm rõ rệt [23]. 66 Thí dụ: Giả sử ta có tệp tin ảnh CI12.bmp là một ảnh xám 8 bit như sau: Hình 2.1. Ảnh trước khi giấu tin Hình 2.2. Đồ thị xác suất giấu tin trên ảnh ở hình 2.1 Trước khi giấu tin, xác suất phát hiện ảnh có giấu tin theo kỹ thuật PoV là bằng 0 với mọi phần trăm điểm ảnh được kiểm tra. 67 Kỹ thuật giấu tin thực hiện trên ảnh ở hình 2.1 giấu các bit thông điệp vào bit LSB của mỗi điểm ảnh. Thông điệp được sinh ra một cách ngẫu nhiên. Độ dài thông điệp được nhập từ bàn phím bởi người dùng. Sau khi giấu 10%, 50%, 100% các điểm ảnh ta thu được tương ứng các tệp ảnh 10SI12.bmp, 50SI12.bmp, 100SI12.bmp. Tiến hành kỹ thuật PoV trên ba tệp tin ảnh này ta thu được xác suất giấu tin tương ứng trên hình 2.3 (a), (b), (c). (a) Xác suất sau khi giấu 10% 68 (b) Xác suất Sau khi giấu tin 50% (c) Xác suất phát hiện sau khi giấu 100% Hình 2.3. Đồ thị xác suất phát hiện ảnh có giấu tin. 69 2.4 KỸ THUẬT