Luận văn Nâng cao chất lượng giấu tin và ứng dụng

85 trang yendo 5510

Download

Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Nâng cao chất lượng giấu tin và ứng dụng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

luan_van_nang_cao_chat_luong_giau_tin_va_ung_dung.pdf

Nội dung text: Luận văn Nâng cao chất lượng giấu tin và ứng dụng

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 được công bố trong bất kỳ công trình nào khác. Hà Nội, tháng 9 năm 2013 Tác giả luận văn Nguyễn Viết Phú i
LỜI CẢM ƠN Tôi xin chân thành cảm ơn các Thầy, Cô giáo trong Viện Toán Tin Ứng dụng và các cán bộ, nhân viên của Viện Đào tạo sau đại học, Trường Đại học Bách Khoa Hà Nội; các cán bộ, nhân viên của Viện Đào tạo Nhân lực Quốc tế đã luôn nhiệt tình và tạo mọi điều kiện tốt nhất cho tôi trong suốt quá trình học tập. 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 11A TOAN-HT – Trường Đại học Bách khoa Hà Nội đã luôn động viên, giúp đỡ và chia sẽ với tôi những kinh nghiệm trong học tập cũng như trong cuộc sống đời thường. Đặc biệt xin bày tỏ lòng biết ơn sâu sắc đến PGS.TS. Phan Trung Huy đã tận tình giúp đỡ tôi định hướng, hình thành, nghiên cứu và hoàn thà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 sai sót, khiếm khuyết. Tôi rất mong được sự đóng góp ý kiến của các thầy giáo, cô giáo và các đồng nghiệp. Hà Nội, 2013 Người thực hiện luận văn Nguyễn Viết Phú ii
MỤC LỤC DANH MỤC VIẾT TẮT vi DANH MỤC BẢNG BIỂU vii DANH MỤC HÌNH ẢNH viii MỞ ĐẦU 1 1. Mục đích của luận văn 2 2. Những đóng góp của luận văn 2 Chương 1. TỔNG QUAN VỀ GIẤU TIN TRONG ẢNH SỐ 3 1.1. Khái niệm giấu tin 3 1.2. Lịch sử giấu tin 3 1.3. Mô hình giấu tin cơ bản 4 1.4. Phân loại các kỹ thuật giấu tin 5 1.5. Các ứng dụng của kỹ thuật giấu tin 6 1.6. Giấu tin trong dữ liệu đa phương tiện 8 1.6.1. Giấu tin trong ảnh và các đặc trưng 8 1.6.1.1. Giấu tin trong ảnh 8 1.6.1.2. Các đặc trưng cơ bản 9 1.6.2. Giấu tin trong Audio 11 1.6.3. Giấu thông tin trong video 12 1.6.4. Tổng quan về ảnh số 12 Chương 2. MỘT SỐ PHƯƠNG PHÁP GIẤU TIN TRÊN ẢNH NHỊ PHÂN 19 2.1. Kỹ thuật giấu tin theo khối bít 19 2.1.1. Ý tưởng 19 2.1.2. Thuật toán giấu tin 19 2.1.3. Phân tích thuật toán 20 2.2. Tỷ lệ giấu tin tối đa 21 2.3. Kỹ thuật giấu tin Wu – Lee 22 iii
2.3.1. Thuật toán giấu tin 23 2.3.2. Phân tích thuật toán 25 2.3.3. Thí dụ minh họa thuật toán Wu-Lee 26 2.3.4. Một số nhận xét về thuật toán Wu-lee 27 2.4. Kỹ thuật giấu tin Chen – Pan – Tseng 28 2.4.1. Ý tưởng 29 2.4.2. Thuật toán CPT 29 2.4.3. Cách chứng minh về tính đúng đắn của thuật toán 31 2.4.4. Một số thí dụ minh họa thuật toán CPT 33 2.4.5. Phân tích thuật toán 36 Chương 3. NÂNG CAO CHẤT LƯƠNG GIẤU TIN BẰNG PHƯƠNG PHÁP MODULE 38 3.1. Một số phương giấu tin trong ảnh màu và ảnh đa cấp xám 38 3.1.1. Giấu tin trong ảnh màu và ảnh đa cấp xám 38 3.2. Phương pháp giấu tin theo module 42 3.2.1. Phương pháp module 42 3.2.2. Giấu tin sử dụng phương pháp Module 42 3.2.3. Giấu tin sử dụng tập 1-cơ sở 44 3.2.4. Giấu tin sử dụng tập 2-cơ sở 44 3.2.5. Một số sơ đồ giấu tin theo tiếp cận module trên Z3 45 3.2.5.1. Sơ đồ giấu tin trên ảnh xám 45 4 3.2.5.2. Sơ đồ giấu tin sử dụng module Z 4 trên ảnh nhị phân 48 3 3.2.6. Phương pháp giấu tin theo module Z 4 51 3 3.2.7. Thuật toán giấu tin trong ảnh xám theo module Z 4 52 6 3.2.8. Thuật toán giấu tin trong ảnh xám theo module Z 2 55 3.2.8.1. Thuật toán giấu tin B1 57 3.2.8.2. Thuật toán khôi phục B2 58 3.2.8.3. Giấu dữ liệu trong dãy các khối của ảnh nhị phân G 60 3.2.8.4. Kết quả thử nghiệm 61 iv
Chương 4. XÂY DỰNG CHƯƠNG TRÌNH ỨNG DỤNG 63 4.1. Thiết kế chương trình 63 4.1.1. Sơ đồ mức ngữ cảnh 63 4.1.2. Sơ đồ nhúng thông tin vào ảnh 63 4.1.3. Sơ đồ tách thông tin từ ảnh giấu tin 64 4.2. Chương trình giấu tin 64 4.2.1. Nhúng tin vào ảnh 64 4 4.2.1.1. Giấu tin trên ảnh nhị phân Z 4 66 3 4.2.1.2. Giấu tin trên ảnh xám Z 4 67 6 4.2.1.3. Giấu tin trên ảnh nhị phân Z 2 68 4.2.2. Tách thông tin từ ảnh 69 KẾT LUẬN 72 TÀI LIỆU THAM KHẢO 74 v
DANH MỤC VIẾT TẮT STT Nội dung Viết tắt 1 Least Significant Bit LSB 2 Bitmap BMP 3 Graphics Interchange Format GIF 4 Y.Chen, H.Pan, Y.Tseng CPT 5 CPT Extension CPTE vi
DANH MỤC BẢNG BIỂU Bảng 1-1. Minh hoạ cấu trúc tệp ảnh bitmap 15 Bảng 1-2. Ý nghĩa từng trường trong vùng Bitmap Header 16 Bảng 1-3. Ý nghĩa và giá trị các trường trong vùng Bitmap Infor 17 4 6 Bảng 3-1. So sánh tỷ lệ giấu tin giữa MSDR và các sơ đồ CPT, Z4 , Z2 62 vii
DANH MỤC HÌNH ẢNH Hình 1-1. Từ trái qua phải: Mặt nạ, văn bản, thông điệp được truyền bí mật trong văn bản 3 Hình 1-2. Lược đồ quá trình giấu tin mật 4 Hình 1-3. Lược đồ quá trình giải mã tin mật 5 Hình 1-4. Phân loại các kỹ thuật giấu tin 6 Hình 1-5. Ví dụ về ảnh màu 13 Hình 1-6.Ví dụ về ảnh đa cấp xám 14 Hình 1-7.Ví dụ về ảnh đen trắng 14 Hình 2-1. Minh hoạ thuật toán giấu tin của Wu-lee 26 Hình 2-2. Minh hoạ giữa thay đổi ngẫu nhiên và thay đổi có định hướng 28 Hình 2-3. Minh hoạ thuật toán CPT trường hợp thay đổi 1 bit 33 Hình 2-4. Minh hoạ quá trình giải mã thông tin đã giấu 34 Hình 2-5. Thí dụ minh hoạ trường hợp thay đổi hai bit 36 Hình 3-1. Minh họa kĩ thuật giấu LSB 40 Hình 4-1. Sơ đồ quan hệ trong hệ thống giấu tin 63 Hình 4-2. Sơ đồ nhúng tin mật và ảnh 63 Hình 4-3. Sơ đồ tách tin từ ảnh có giấu tin 64 Hình 4-4. Ảnh nhị phân Lenna.bmp 64 Hình 4-5. Tệp tin mật cần giấu 65 Hình 4-6. Giao diện chọn giải thuật nhúng tin mật 65 4 Hình 4-7. Giao diện nhúng dữ liệu vào ảnh trong giải thuật Z4 66 Hình 4-8. Thông báo nhúng dữ liệu thành công 66 viii
Hình 4.1. Thông báo các thông số sau khi nhúng dữ liệu thành công 77 Hình 4-10. Giao diện nhúng dữ liệu vào ảnh trong giải thuật 67 Hình 4-11. Thông báo các thông số sau khi nhúng dữ liệu thành công 68 Hình 4-12. Giao diện nhúng dữ liệu vào ảnh trong giải thuật 68 Hình 4-13. Thông báo các thông số sau khi nhúng dữ liệu thành công 69 Hình 4-14. Giao diện tách tin mật từ ảnh 69 Hình 4-15. Khôi phục tin trên ảnh nhị phân 70 Hình 4-16. Thông báo khôi phục tin trên ảnh nhị phân 70 Hình 4-17. Tệp dữ liệu được tách ra từ ảnh giấu tin 70 Hình 4-18. Tách tin trên 71 Hình 4-19. Tệp dữ liệu được tách ra từ ảnh giấu tin 71 ix
MỞ ĐẦU Ngày nay, cùng với sự phát triển mạnh mẽ của ngành khoa học công nghệ thông tin, mạng máy tính nói chung cũng như mạng internet đã tạo nên một môi trường mở và là phương tiện trao đổi thông tin quan trọng với mọi người. Với lượng thông tin được truyền qua mạng ngày càng nhiều thì nguy cơ dữ liệu bị truy cập trái phép cũng tăng lên. Vì vậy vấn đề bảo đảm an toàn và bảo mật thông tin cho dữ liệu truyền trên mạng là rất cần thiết. Để đảm bảo an toàn và bí mật cho một thông điệp truyền đi người ta thường dùng phương pháp truyền thống là mã hóa thông điệp theo một qui tắc nào đó đã được thỏa thuận trước giữa người gửi và người nhận. Tuy nhiên, phương thức này thường gây sự chú ý của đối phương về tầm quan trọng về nội dung của thông điệp. Thời gian gần đây đã xuất hiện một cách tiếp cận để truyền các thông điệp bí mật, đó là giấu các thông tin quan trọng trong những bức ảnh thông thường. Bề ngoài các bức ảnh có chứa thông tin mật cũng không có gì khác với ảnh số và được sử dụng phổ biến nên vô hiệu việc theo dõi, tấn công của đối phương. Mặt khác, dù các bức ảnh đó bị phát hiện ra là có chứa thông tin trong đó thì với các khóa có độ bảo mật cao thì việc tìm được nội dung của thông tin đó cũng rất khó có thể thực hiện được. Xét theo khía cạnh tổng quát thì giấu thông tin cũng là một hệ mã mật nhằm bảo đảm tính an toàn thông tin, nhưng phương pháp này ưu điểm là ở chỗ giảm được khả năng phát hiện được sự tồn tại của thông tin trong nguồn mang. Không giống như mã hóa thông tin là chống sự truy cập và sửa chữa một cách trái phép thông tin, mục tiêu của giấu thông tin là làm cho thông tin trộn lẫn với các điểm ảnh. Điều này sẽ đánh lừa được sự phát hiện của các tin tặc và do đó làm giảm khả năng bị giải mã. Kết hợp các kỹ thuật giấu tin với các kỹ thuật mã hóa ta có thể nâng cao độ an toàn cho việc truyền tin. 1
1. Mục đích của luận văn Giấu dữ liệu là một lĩnh vực rộng lớn, trong luận văn này chỉ trình bày các kỹ thuật giấu dữ liệu trong ảnh, giới thiệu các phương pháp nhằm nâng cao chất lượng giấu tin. Do khuôn khổ nghiên cứu, nội dung luận văn tập trung vào việc trình bày một số kỹ thuật giấu dữ liệu trong ảnh đã được công bố, sau đó giới thiệu các kỹ thuật giấu dữ liệu trong ảnh nhị phân và ảnh đa cấp xám theo tiếp cận module của nhóm tác giả PGS.TS. Phan Trung Huy[1], [14], [15] và xây dựng một chương trình giấu tin thực nghiệm thực hiện các thuật toán giấu tin , và . 2. Những đóng góp của luận văn - Luận văn cung cấp một cách nhìn tổng quát về giấu tin trên môi trường đa phương tiện. - Luận văn trình bày các phương pháp và chứng minh về tính đúng đắn của thuật toán Wu-Lee [4], CPT [5] với cách chứng minh sẽ giúp quá trình nghiên cứu thuật toán này trở nên dễ dàng hơn. - Trình bày ba thuật toán giấu tin trên ảnh nhị phân và ảnh đa cấp xám theo tiếp cận module của nhóm tác giả PGS.TS. Phan Trung Huy. - Xây dựng chương trình giấu tin thực nghiệm cài đặt các thuật toán theo tiếp cận module , , . 2
Chương 1. TỔNG QUAN VỀ GIẤU TIN TRONG ẢNH SỐ 1.1. Khái niệm giấu tin “Giấu 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. Giấu tin trong ảnh số là giấu các mẩu tin cũng là dạng số trong máy tính vào các tệp ảnh nhị phân sao cho không bị người ngoài phát hiện. 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.2. Lịch sử giấu tin Giấu tin bắt nguồn từ Hy Lạp, tiếng Hy Lạp gọi đó là Stenography có nghĩa là "dòng chữ bị che phủ". Mục đích cơ bản của giấu tin là nhúng mẩu tin mật vào một môi trường truyền tin bình thường sao cho người khác không thể phát hiện ra mẩu tin mật đó. 500 năm trước, một nhà toán học người Ý tên là Jérôme Cardan đã sáng tạo lại một phương thức văn bản bí mật cổ xưa của người Trung Quốc. Văn bản được làm như sau: một tờ giấy làm mặt nạ có nhiều lỗ thủng mà người gửi và người nhận đều biết, mặt nạ này sẽ được đặt trên một tờ giấy trắng và người gửi sẽ viết thông điệp bí mật qua các lỗ thủng trên mặt nạ sau đó vứt mặt nạ đó đi và điền phần còn lại vào tờ giấy trắng như tờ giấy này toàn các thông tin vô thưởng vô phạt (hình 1.1) Hình 1-1. Từ trái qua phải: Mặt nạ, văn bản, thông điệp được truyền bí mật trong văn bản 3
Ngày nay nghệ thuật giấu tin được nghiên cứu để phục vụ các mục đích tích cực như bảo vệ bản quyền, thủy vân số, hay phục vụ giấu các thông tin bí mật về quân sự và kinh tế. Sự phát triển của công nghệ thông tin đã tạo ra những môi trường giấu tin vô cùng tiện lợi và phong phú. Người ta có thể giấu tin trong các tệp ảnh, trong các tệp âm thanh, tệp văn bản. Cũng có thể giấu tin ngay trong các khoảng trống hay các phân vùng ẩn của môi trường lưu trữ như đĩa cứng, đĩa mềm. Các gói tin truyền đi trên mạng cũng là môi trường giấu tin quan trọng và ngay cả các tiện ích phần mềm cũng là môi trường lý tưởng để gài các thông tin quan trọng để xác nhận bản quyền. 1.3. Mô hình giấu tin cơ bản Hình 1-2. Lược đồ quá trình giấu tin mật Hình 1.2 biểu diễn mô hì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. 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à những chương trình thực hiện theo những 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 một số hệ mật mã. Đầu ra 4
của quá trình nhúng tin là phương tiện chứa đã được giấu tin. Các phương tiện chứa này có thể được phân phối trên mạng. Hình 1-3. Lược đồ quá trình giải mã tin mật Hình 1.3 mô tả quá trình giải mã thông tin đã được giấu trước đó. Đầu vào là phương tin có chứa tin giấu, qua một bộ giải mã tin (tương ứng với bộ nhúng tin) cùng với khóa sẽ được thực hiện việc giải mã thông tin. Đầu ra của quá trình là phương tiện chứa tin và thông tin mật đã giấu trước đó. Trong trường hợp cần thiết, thông tin lấy ra có thể được xử lý, kiểm định và so sánh với thông tin đã giấu ban đầu. 1.4. Phân loại các kỹ thuật giấu tin Kỹ thuật giấu tin nhằm mục đích đảm bảo an toàn và bảo mật thông tin ở hai khía cạnh. Một là bảo mật cho giữ liệu được đem giấu (embedded data), chẳng hạn như giấu tin mật: thông tin mật được giấu kỹ trong một đối tượng khác sao cho người khác không phát hiện được (steganography), hai là bảo mật cho chính đối tượng được dùng để giấu tin (host data), chẳng hạn như ứng dụng bảo vệ bản quyền, phát hiện xuyên tạc thông tin (watermarking) 5
Hai khía cạnh khác nhau này dẫn đến hai khuynh hướng kỹ thuật chủ yếu của giấu tin. Khuynh hướng thứ nhất là giấu tin mật (Steganography). Khuynh hướng này tập trung vào các kỹ thuật giấu tin sao cho thông tin giấu được càng nhiều càng tốt và quan trọng là người khác khó phát hiện được một đối tượng có bị giấu tin bên trong hay không. Khuynh hướng thứ hai là thuỷ vân số (watermarking). Khuynh hướng thuỷ vân số đánh giấu vào đối tượng nhằm khẳng định bản quyền sở hữu hay phát hiện xuyên tạc thông tin. Thuỷ vân số có miền ứng dụng lớn hơn, đòi hỏi độ bền vững cao của các thông tin cần giấu đối với các biến đổi thông thường của các tệp dữ liệu môi trường nên được quan tâm nghiên cứu nhiều hơn và thực tế đã có nhiều những kỹ thuật dành cho khuynh hướng này. Hình 1-4. Phân loại các kỹ thuật giấu tin Phạm vi ứng dụng của thủy vân đa dạng hơn, tùy theo mục đích của hệ thủy vân mà người ta lại chia thành các hướng nhỏ như thủy vân dễ vỡ và thủy vân bền vững. 1.5. Các ứng dụng của kỹ thuật giấu tin 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 tác giả gọi là thủy vân sẽ được nhúng vào trong các sản phẩm, thủy vân đó chỉ một mình chủ sở hữu hợp 6
pháp các sản phẩm đó có và được dùng làm minh chứng cho bản quyền sản phẩm. Giả sử có một sản phẩm dữ liệu dạng đa phương tiện như ảnh, âm thanh, video và cần được lưu thông trên mạng. Để bảo vệ các sản phẩm chống lại các hành vi lấy cắp hoặc làm nhái cần phải có một kỹ thuật để “dán tem bản quyền” vào sản phẩm này. Việc dán tem hay chính là việc nhúng thủy vân cần phải đảm bảo không để lại một ảnh hưởng đáng kể nào đến việc cảm nhậ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 với 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 là phá hủy sản phẩm. Xác thực thông tin hay phát hiện giả mạo: Một tập các thông tin sẽ được giấu trong phương tiện chứa sau đó được sử dụng để nhận biết xem dữ liệu trên phương tiện gốc đó có bị thay đổi không. Các 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ả các thủy vân hợp lệ hay xuyên tạc thông tin nguồn cũng cần đượ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 ứng dụng này là khả năng giấu 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 những ứng dụng này được sử dụng để nhận diện người gửi hay người nhận của một thông tin nào đó. Ví dụ các vân khác nhau sẽ được nhúng vào các bản sao khác nhau của thông tin gốc trước khi chuyển cho nhiều người. Với ứng dụng này thì yêu cầu là đảm bảo độ an toàn cao cho các thủy vân tránh sự xóa giấu vết trong khi phân phối. Kiểm soát sao chép: Các thủy vân trong trường hợp này được sử dụng để kiểm soát sao chép đối với các thông tin. Các thiết bị phát ra thủy vân thường được gắn sẵn vào trong các hệ thống đọc/ghi. Ví dụ như hệ thống quản lý sao chép DVD đã được ứng dụng ở Nhật. Các ứ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. 7
Giấu tin mật: Các thông tin giấu được trong trường hợp này càng nhiều càng tốt, việc giải mã để nhận được thông tin cũng không cần phương tiện chứa ban đầu. Các yêu cầu mạnh về chống tấn công của kẻ thù không cần thiết lắm thay vào đó là thông tin giấu phải đảm bảo tính không thể phát hiện. 1.6. Giấu tin trong dữ liệu đa phương tiện Kỹ thuật giấu tin đã được nghiên cứu và áp dụng trong nhiều môi trường dữ liệu khác nhau như trong dữ liệu đa phương tiện (text, image, audio, video), trong sản phẩm phần mềm và gần đây là những nghiên cứu trên môi trường cơ sở dữ liệu quan hệ. Trong các môi trường dữ liệu đó thì dữ liệu đa phương tiện là môi trường chiếm tỉ lệ chủ yếu trong các kỹ thuật giấu tin. 1.6.1. Giấu tin trong ảnh và các đặc trưng Giấu tin trong ảnh, hiện nay, là một bộ phận chiếm tỷ lệ lớn nhất trong các chương trình ứng dụng, các phần mềm, hệ thống giấu tin trong dữ liệu đa phương tiện bởi lượng thông tin được trao đổi bằng ảnh là rất lớn. Hơn nữa, giấu tin trong ảnh cũng đóng vai trò hết sức quan trọng trong hầu hết các ứng dụng bảo vệ an toàn thông tin như: xác thực thông tin, xác định xuyên tạc thông tin, bảo vệ bản quyền tác giả, điều khiển truy nhập, giấu tin mật Vì thế mà vấn đề này đã nhận được sự quan tâm rất lớn của các cá nhân, tổ chức, trường đại học, và viện nghiên cứu trên thế giới. 1.6.1.1. Giấu tin trong ảnh Thông tin sẽ được giấu cùng với dữ liệu ảnh nhưng chất lượng ảnh ít thay đổi và ít ai biết được bên trong bức ảnh đó mang những thông tin có ý nghĩa khác. Và ngày nay, khi ảnh số đã được sử dụng phổ biến, thì giấu tin đã đem lại rất nhiều những ứng dụng quan trọng trong trên nhiều lĩnh vực trong đời sống xã hội. Ví dụ như đối với các nước phát triển, chữ ký tay đã được số hóa và lưu trữ sử dụng như là hồ sơ cá nhân của các dịch vụ ngân hàng và tài chính, nó được dùng để xác nhận các thẻ tín dụng của người tiêu dùng. Thêm vào đó, lại có rất nhiều loại thông tin quan trọng cần được bảo mật, chúng rất dễ bị lấy cắp và bị thay đổi bởi các phần 8
mềm chuyên dụng. Phát hiện thông tin xuyên tạc đã trở nên vô cùng quan trọng và cấp thiết. Một đặc điểm của giấu tin trong ảnh đó là thông tin được giấu trong ảnh một cách vô hình, nó như là một cách truyền thông tin mật cho nhau mà người khác không thể biết được bởi sau khi giấu tin thì chất lượng ảnh gần như không thay đổi, đặc biệt đối với ảnh màu hay ảnh đa mức xám. 1.6.1.2. Các đặc trưng cơ bản Giấu tin trong ảnh chiếm vị trí chủ yếu trong các kỹ thuật giấu tin, vì vậy mà các kỹ thuật giấu tin phần lớn cũng tập trung vào các kỹ thuật giấu tin trong ảnh. Các phương tiện chứa khác nhau thì cũng sẽ có các kỹ thuật giấu khác nhau. Đối tượng ảnh là một đối tượng dữ liệu tĩnh có nghĩa là dữ liệu tri giác không biến đổi theo thời gian. 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 các kỹ thuật giấu tin trong ảnh thường chú ý tới các đặc trưng cơ bản sau đây: - Phương tiện có chứa dữ liệu tri giác tĩnh Dữ liệu gốc ở đây là dữ liệu 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 khác với dữ liệu âm thanh và dữ liệu băng hình vì khi ta nghe hay xem thì dữ liệu gốc sẽ thay đổi liên tục với tri giác của con người theo các đoạn, các bài hay các ảnh - Kỹ thuật giấu phụ thuộc ảnh Kỹ thuật giấu tin phụ thuộc vào các loại ảnh khác nhau. Chẳng hạn đối với ảnh đen trắng, ảnh xám hay ảnh màu ta cũng có những kỹ thuật riêng cho từng loại ảnh có những đặc trưng khác nhau. - 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ỏ 9
sao cho bằng mắt thường khó nhận ra được sự thay đổi đó vì có như thế thì mới đảm bảo được độ an toàn cho thông tin giấu. Rất nhiều các 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 về 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 xanh da trời kém nhất trong ba màu cơ bản. - Giấu 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 thực hiện công việc giấu tin sẽ được thực hiện trên dữ liệu của ảnh. Dữ liệu ảnh bao gồm phần header, bảng màu (có thể có) và dữ liệu ảnh. Do vậy mà kích thước ảnh trước và sau khi giấu tin là như nhau. - Đảm bảo chất lượng sau khi giấu tin Đây là một 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 được yêu cầu không bị biến đổi để có thể bị phát hiện dễ dàng so với ảnh gốc. Yêu cầu này dường như khá đơn giản đối với ảnh màu hoặc ảnh xám bởi mỗi điểm ảnh được biểu diễn bởi nhiều bit, nhiều giá trị và khi ta thay đổi một giá trị nhỏ nào đó thì chất lượng ảnh thay đổi không đáng kể, thông tin giấu khó bị phát hiện, nhưng đối với ảnh đen trắng mỗi điểm ảnh chỉ là đen hoặc trắng, và nếu ta biến đổi một bit từ trắng thành đen và ngược lại mà không khéo thì sẽ rất dễ bị phát hiện. Do đó, yêu cầu đối với các thuật toán giấu tin trong ảnh màu hay ảnh xám và giấu tin trong ảnh đen trắng là khác nhau. Trong khi đối với ảnh màu thì các 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 thì các thuật toán áp dụng cho ảnh đen trắng lại tập trung vào việc 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 giải mã 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ị 10
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 mà giấu tin trong ảnh có tác dụng nhận thực và phát hiện xuyên tạc thông tin. - Vai trò của ảnh gốc khi giải tin Các kỹ thuật giấu tin phải xác định rõ ràng quá trình lọc ảnh để lấy thông tin giấu cần đến ảnh gốc hay không cần. Đa số các kỹ thuật giấu tin mật thì thường không cần ảnh gốc để giải mã. Thông tin được giấu trong ảnh sẽ được mang cùng với dữ liệu ảnh, khi giải mã 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. 1.6.2. Giấu tin trong Audio - Kỹ thuật này phụ thuộc vào hệ thống thính giác của con người, sử dụng các âm thanh to cao tần để che giấu các âm thanh nhỏ, thấp. - Giấu thông tin trong audio mang những đặc điểm riêng khác với giấu thông tin trong các đối tượng đa phương tiện khác như ảnh, video, văn bản 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. Để đảm bảo yêu cầu này ta lưu ý rằng kỹ thuật giấu thông tin trong ảnh phụ thuộc vào hệ thống thị giác của con người – HSV (Human Vision System) còn kỹ thuật giấu thông tin trong audio lại phụ thuộc vào hệ thống thính giác HAS (Human Auditory System). - Khó khăn của việc giấu thông tin trong audio: Thứ nhất: Hệ thống thính giác của con người nghe được các tín hiệu ở các giải tần rộng và công suất lớn nên đó gây khó dễ đối với các phương pháp giấu tin trong audio. Nhưng tai con người lại kém trong việc phát hiện sự khác biệt các giải tần và công suất 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. Thứ hai: Đó 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. Giấu thông tin trong audio đòi hỏi yêu cầu rất cao về tính đồng bộ và tính an toàn của thông tin. Các phương pháp giấu 11
thông tin trong audio đều lợi dụng điểm yếu trong hệ thống thính giác của con người. 1.6.3. Giấu thông tin trong video - Ý tưởng cơ bản của phương pháp này là phân phối thông tin giấu giàn trải theo tần số của dữ liệu gốc. Cụ thể giấu cả âm thanh và hình ảnh vào video. Phương pháp này được đưa ra bởi Cox và được nhiều nhà nghiên cứu thử nghiệm dùng các hàm cosin riêng và các hệ số truyền sóng riêng để giấu tin và đem lại hiểu quả cao. 1.6.4. Tổng quan về ảnh số Một vài định dạng phổ biến cho file ảnh kĩ thuật số bao gồm BMP, GIF, PNG, JPG, Trong đồ họa máy tính BMP còn được biết đến với tên Windows bitmap, là một định tập tin hình ảnh phổ biến. Có 3 dạng ảnh số phổ biến: Ảnh nhị phân, ảnh đa mức xám, ảnh màu. Ảnh Bitmap Ảnh Bitmap là định dạng ảnh do Microsoft đề xuất, có phần mở rộng là BMP, loại ảnh này truyền tải, sử dụng rộng rãi trên máy tính, và các thiết bị điện tử khác. Ảnh bitmap được chia thành ba dạng: Ảnh đen trắng, ảnh đa mức xám và Ảnh màu. Ảnh màu : Không gian màu là những phương pháp định lượng màu sắc được thiết lập công thức một cách khoa học. Hệ thống không gian màu cho phép mỗi màu được xác định theo số học, bằng cách đó ta có thể chọn và lặp lại những màu nào đó thật chính xác. Bạn sẽ tiếp xúc với những không gian màu chính sau đây: HLS (sắc thái, quang độ và độ bão hòa), HSB (sắc thái, độ bão hòa và độ đậm nhạt), RGB (đỏ, lục, lam) và CYMK (xanh hóa học, vàng, tím sen, đen). CMYK là không gian màu được sử dụng trong công nghiệp in ấn và bị giới hạn bởi mức độ thể hiện của mực in và chất màu. Không gian RGB - hệ thống màu thường gặp nhất 12
trong nghệ thuật nhiếp ảnh số - sử dụng ánh sáng, do vậy cho ta phổ màu rộng hơn các chất màu CYMK. Đối tượng của luận văn này chỉ tập trung vào loại ảnh RGB, mỗi điểm ảnh gồm 3 thành phần màu đỏ (red), xanh lục (green), xanh dương (blue). Mỗi màu có giá trị từ 0 đến 255, nghĩa là mỗi điểm ảnh cần 24bits hay 3bytes để biểu diễn. Số lượng màu có thể của loại ảnh này lên tới 2563 màu khác nhau. Để tiết kiệm bộ nhớ với các ảnh có số lượng màu nhỏ hơn hoặc bằng 256 thì màu các điểm ảnh được lưu trữ dưới dạng bảng màu.Với ảnh có số màu lớn thì các điểm ảnh không tổ chức dưới dạng bảng màu, khi đó giá trị của các điểm ảnh chính là giá trị của các thành phần màu R,G,B. Với ảnh có số lượng màu lớn, tùy theo chất lượng ảnh mà quyết định số bit để biểu diễn cho mỗi màu thường là 24 bit, hoặc 32 bit . Với ảnh 24 bit mỗi thành phần màu được biểu diễn bởi một byte (8 bit). Hình 1-5. Ví dụ về ảnh màu Ảnh nhị phân là ảnh kỹ thuật số mà chỉ có hai giá trị có thể cho mỗi pixel. Thông thường hai màu sắc được sử dụng cho một ảnh nhị phân là đen và trắng (ảnh đen trắng), mặc dù có thể được sử dụng bất kỳ hai màu sắc khác. Có màu sắc được sử dụng cho đối tượng trong hình là màu nền trước khi phần còn lại của hình ảnh là màu nền. Ảnh đa mức xám: là ảnh mà mỗi điểm ảnh được biểu diễn bởi một giá trị và đó là cường độ sáng của điểm ảnh. 13
Hình 1-6.Ví dụ về ảnh đa cấp xám Ảnh nhị phân: là ảnh mà mỗi điểm ảnh được lưu giữ như là một bit (0 hoặc 1). Ngoài ra, ảnh nhị phân còn được gọi là ảnh màu đen trắng, ảnh đơn sắc. Ứng dụng chính của ảnh nhị phân được dùng theo tính logic để phân biệt đối tượng ảnh với nền hay để phân biệt điểm biên với điểm khác. Ảnh nhị phân thường được lưu trữ trong bộ nhớ như một ảnh bitmap, một mảng đóng gói các bit. Cấu trúc ảnh nhị phân được lưu trữ như một ảnh định dạnh bitmap hay định dạng IMG. Hình 1-7.Ví dụ về ảnh đen trắng Định dạng tệp ảnh bitmap Ảnh Bitmap được lưu trữ dưới dạng nhị phân, một tệp định dạng bitmap được chia thành các phần cơ bản như: phần tiêu đề file (BITMAP HEADER), 14
thông tin về ảnh (BITMAP INFOR), bảng màu (PALLETE Table) và vùng dữ liệu ảnh (DATA). Và thứ tự các phần của tệp ảnh được lưu trữ tuần tự trong bộ nhớ như trong hình Bảng 1.1 BITMAP HEADER BITMAP INFOR PALLETE Table DATA Bảng 1-1. Minh hoạ cấu trúc tệp ảnh bitmap  Ý nghĩa các phần trong tệp ảnh bitmap Bitmap Header: mô tả thông tin chung về File định dạng bitmap, độ dài của phần này được cố định với mọi file ảnh bitmap Bitmap Infor: mô tả thông tin về ảnh được lưu trữ, độ dài của phần này cũng cố định. Pallete Table: chính là bảng màu của ảnh bitmap, độ dài của phần này có thể bằng không (không có bảng màu) đối với ảnh đen trắng và ảnh màu có số lượng màu lớn hơn 256 màu. Data: Thông tin của từng điểm ảnh, độ dài của phần này phụ thuộc kích thước ảnh. Phần Data lưu trữ ảnh theo hướng từ dưới lên trên và từ trái qua phải.  Kích thước và giá trị các trường trong tệp ảnh bitmap Bitmap Header Phần bitmap header có độ dài cố định là: 14 byte, phần này dùng để mô tả thông tin chung về file như: Kiểu file, độ dài của tệp và một số thông tin liên quan đến tệp ảnh. 15
Ý nghĩa của từng trường được mô tả trong bảng 1.2 Offset (byte) Giá trị Ý nghĩa 1 ‘B’ Định danh kiểu file để các chương trình nhận dạng 2 ‘M’ 3 -> 6 Unsigned long Kích thước file 7 -> 10 Zero Reserved 11 -> 14 Unsigned long Địa chỉ phần dữ liệu ảnh Bảng 1-2. Ý nghĩa từng trường trong vùng Bitmap Header Trong phần Bitmap Header có mô tả thông tin về độ dài của file, thông tin này thực sự cần thiết đối với mọi chương trình. Nhưng qua quá trình thực nghiệm đối với một số file thì thông tin này lại không chính xác, và trong luận văn đưa ra cách tính kích thước file thông qua công thức: FileSize = Sizeof(Bitmap Header) + Sizeof(Bitmap Infor) + Sizeof(Pallete) + Sizeof(Data) (1.1) Địa chỉ vị (offset) của vùng dữ liệu có thể được xác định thông qua công thức: Địa chỉ vùng data = 54 + Sizeof(Pallete Table) (1.2) Đối với ảnh đen trắng và ảnh màu có số lượng màu lớn hơn 256 màu thì giá trị địa chỉ vùng data cố định là 54, vì các loại ảnh này không tổ chức bảng màu cho các điểm ảnh. Bitmap Infor Bitmap Infor dùng để mô tả thông tin về ảnh đang được lưu trữ trong file, kích thướcc của phần này cố định là 40 byte. 16
Ý nghĩa và giá trị của từng trường trong vùng Bitmap Infor được mô tả chi tiết trong Bảng 1.3 Offset Giá trị Ý nghĩa (byte) 1 -> 4 40 Số lượng byte của cùng Bitmap Infor 5->8 Unsigned long Độ rộng của ảnh tính theo Pixel 9 -> 12 Unsigned long Độ cao của ảnh tính theo Pixel 13-> 14 1 Number of Color Plans 15 -> 16 Unsigned integer Số bit để biểu diễn một điểm ảnh 17 -> 20 Unsigned long Kiểu nén 21 -> 24 Unsigned long Kích thước của ảnh tính theo Byte 25 -> 28 Unsigned long Độ phân giải của ảnh theo chiều ngang 29 -> 32 Unsigned long Độ phân giải của anh theo chiều ngang 33->36 Unsigned long Số lượng màu trong bảng màu 37 -> 40 Unsigned long Số màu quan trọng Bảng 1-3. Ý nghĩa và giá trị các trường trong vùng Bitmap Infor Pallete Table Bảng màu là tập các màu được sử dụng trong ảnh (ảnh 8 bit màu), mỗi một màu trong bảng màu được gọi là một Entry và được lưu trữ bởi 4 byte, mỗi thành phần màu được lưu trữ một byte còn một byte để dữ trữ (chứa dùng) và thứ tự lưu trữ là B, G, R, Reserved. Như vậy kích thước của bảng màu có thể được tính theo công thức: 17
Sizeof(Pallete Table) = (Number color) * 4 (1.3) Data Vùng dữ liệu ảnh là giá trị của các điểm ảnh, kích thước của vùng dữ liệu ảnh phụ thuộc vào độ rộng, chiều cao và kiểu ảnh. Với ảnh 8 bit màu thì kích thước vùng ảnh có thể được tính theo công thức (1.4), công thức (1.5) dùng để tính tích thươc vùng ảnh đổi với ảnh có số màu lớn hơn 256 màu. Sizeof(Data) = Width * Height (1.4) Sizeof(Data) = Width * Height * Bit_Number_of_Pixel (1.5) Với ảnh 8 bit màu giá trị của mỗi điểm ảnh trong vùng Data là chỉ số của màu trong bảng màu, chỉ số màu của điểm ảnh là một số nguyên có giá trị từ 0 đến 255 và được lưu trữ trong một byte, do vậy kích thước của vùng này được tính theo công thức (1.4). Như đã trình bày ở trên, với ảnh có số lượng màu lớn hơn 256 màu thì giá trị trong vùng Data chính là giá trị của các thành phần màu cơ bản, số lượng bit dùng để biểu diễn giá trị cho từng thành phần màu có thể sẽ khác nhau phụ thuộc vào chất lượng ảnh. Đối với ảnh 24 bit màu, mỗi thành phần màu được lưu trữ bởi 8 bit và thứ tự lưu trữ là B, G, R. 18
Chương 2. MỘT SỐ PHƯƠNG PHÁP GIẤU TIN TRÊN ẢNH NHỊ PHÂN Trong chương này, tập trung trình bày, phân tích, đánh giá, so sánh kết quả thực hiện của một số kỹ thuật giấu tin trên không gian ảnh nhị phân. Dựa trên sự phân tích, đánh giá hai kỹ thuật giấu tin của Wu-Lee và của Y.Chen, H.Pan, Y.Tseng, trong luận văn đưa ra một số nhận xét theo khía cạnh kỹ thuật và ứng dụng. Các nhận xét này sẽ là cơ sở để cải tiến, phát triển một số thuật toán giấu tin được trình bày trong chương tiếp theo. Dựa vào dự phân tích đánh giá kỹ thuật giấu tin của Y.Chen, H.Pan, Y.Tseng trong chương này, luận văn sẽ trình bày một phương pháp chứng minh về tính đúng đăn cho thuật toán giấu tin CPT. Với cách chứng minh, không những giúp người đọc dễ hiểu hơn, mà phương pháp chứng minh này còn chỉ ra được cận trên của quá trình lặp trong thuật toán. 2.1. Kỹ thuật giấu tin theo khối bít 2.1.1. Ý tưởng Đây có lẽ là kỹ thuật đơn giản nhất trong các kỹ thuật giấu tin theo hướng tiếp cận trên miền không gian ảnh. Ý tưởng cơ bản của thuật toán trong kỹ thuật này là chia ảnh gốc thành các khối nhỏ và trong mỗi khối nhỏ sẽ giấu một bít b (b = 0 hoặc b = 1). Thuật toán này được áp dùng cho ảnh đen trắng 2.1.2. Thuật toán giấu tin  Quá trình giấu tin .Tóm tắt thuật toán Input - Một ảnh nhị F - Dãy bít cần giấu b1 b2 bN Output 19
Ảnh nhị phân G được biến đổi từ F và G có chứa dãy bít b1 b2 bN Nội dung thuật toán Bước 1: Chia ảnh gốc F thành các ma trận điểm ảnh Fi có kích thước mxn. Để không mất tính tổng quát, chúng ta giả sử F luôn chia được thành N khối kích thước mxn Bước 2: Với mỗi khối Fi (i = 1,2, .,N) sẽ tiến hành giấu một bit bi (bi = 0 hoặc bi =1) bằng cách biến đổi Fi thành Gi sao cho Gi thỏa mãn bất biến sau: m n G( u , v ) mod 2 b | u 1 m , v 1 n (2.1)  i i u 1v 1 Bước 3: Kết hợp các khối Gi ta sẽ thu được ảnh G chứa dãy bít b1 b2 bN  Quá trình giải tin. Khi nhận được ảnh đã giấu tin, quá trình giải mã tin sẽ được thực hiện theo các bước sau đây. Chia ảnh thành các khối có kích thước giống kích thước khối đã sử dụng khi thực hiện giấu, đây chính là khoá để giải mã. Với mỗi khối việc giải tin theo quy tắc: đếm số bít 1 trong khối, nếu tổng số bít 1 là lẻ thì thu được bít 1, ngược lại thu được bít 0. Và cứ tiếp tục cho đến khi hết các khối đã giấu. Như vậy, sau khi xét hết các khối đã giấu ta thu được một chuỗi bit. Chuỗi bit này chính là thông tin đã giấu trong ảnh nhị phân. 2.1.3. Phân tích thuật toán Thuật toán giấu tin trong ảnh 2.1. là rất đơn giản. Sau khi nghiên cứu thuật toán này có thể đưa ra một số nhận xét và đánh giá sau đây. Tuỳ theo yêu cầu của việc giấu tin, việc chọn kích thước khối để giấu tin cần phải căn cứ vào kích thước ảnh và lượng thông tin cần giấu sao cho các thông tin được giấu giàn trải trên toàn ảnh. 20
Tuỳ theo mục đích của việc giấu tin và nhu cầu về lượng thông tin giấu ta sẽ chọn kích thước khối phù hợp. Kích thước khối càng lớn thì lượng thông tin có thể giấu càng thấp, đồng thời ảnh sau khi giấu tin cũng ít thay đổi ảnh gốc và ngược lại. Với thuật toán này, việc chia ảnh gốc thành các khối điểm ảnh có kích thước giống nhau là khá đơn giản. Tuy nhiên, để tăng tính an toàn cho thuật toán chúng ta có thể chia ảnh gốc thành các khối điểm ảnh có kích thước khác nhau và vị trí bắt đầu của mỗi khối theo một thuật toán xác định nào đó. Khi đó, để giải mã được tin đã giấu các thuật toán thám mã không những phải xác định kích thước của từng khối mà còn phải xác định vị trí bắt đầu của mỗi khối thay cho việc chỉ cần tìm kích thước của các khối như trong thuật toán giấu tin trong 2.1. Bản chất của cách thức giấu chẳng qua là một sự quy ước nào đó, nếu thoả mãn thì giấu bit 1, ngược lại thì giấu bit 0. Các khối ảnh sau khi giấu tin luôn thoả mãn một tính chất (bất biến) và tính chất này là cơ sở cho quá trình giải mã tin giấu. Sở dĩ ta thực hiện được điều này vì thông tin giấu chỉ có hai trường hợp, một là bit 1, hai là bit 0. Kỹ thuật trên sẽ gặp phải hiện tượng gây bất thường đối với ảnh sau khi giấu thông tin, đặc biệt là khi cần phải thay đổi giá trị của một phần tử trên khối ảnh một màu (toàn số 0 hoặc toàn số 1). Khi đó, bằng mắt thường chúng ta có thể dễ dàng nhận ra sự thay đổi của ảnh trước và sau khi giấu tin. Quá trình tách lấy thông tin đã giấu trong kỹ thuật này sử dụng khoá là kích thước của khối, không cần sử dụng ảnh gốc. 2.2. Tỷ lệ giấu tin tối đa Trong phần này, không mất tính tổng quát ta chỉ xét một ma trận F xác định có kích thước m×n của các điểm ảnh thuộc ảnh G. F được xét như là một tập hợp của các điểm ảnh, trong đó tùy tình huống, ta xem mỗi phần tử Fij (hoặc cặp (i,j))được xem như là một điểm ảnh, và cũng có thể xem như là màu của điểm ảnh. Đặt q = mn. Cho k là số nguyên > 1 thể hiện số mầu của các điểm ảnh Fij, đối với 21
ảnh nhị phân k=2, với ảnh mầu nói chung k>2. Việc thay đổi điểm ảnh Fij được hiểu là màu Fij được thay đổi thành mầu Fij’ với k cách khác nhau. Chúng ta xét các phương pháp mở rộng dựa trên CPT (CPTE schemes) là các phương phương pháp giấu tin trong một ma trận F bằng cách thay đổi nhiều nhất 2 phần tử thuộc F. Với F đã chọn, mỗi ma trận F’ sau khi có sự thay đổi các phần tử được gọi là một cấu hình. Vì mỗi phần tử có k-1 cách thay đổi, do đó ta có số cấu hình tối đa có được khi ta thay đổi một phần tử của F là (k-1).q, nếu chúng ta thay đổi 2 phần tử đồng thời thì sẽ thu được tối đa (k-1).q.(q-1)/2 cấu hình. Như vậy nếu ta thay đổi từ 0 đến 2 phần tử thì số cấu hình tối đa thu được là 1+(k-1).q+(k-1).q.(q-1)/2. Điều này có nghĩa là chúng ta có thể giấu nhiều nhất 2 R= log2(1+(k-1).q+(k-1) .q.(q-1)/2) bit mật trong F. Đối với trường hợp ảnh nhị phân ta có k=2, do vậy R = log2(1+q+q.(q-1)/2) = log2(1+q.(q+1)/2) . Ta gọi R là tỷ lệ giấu tin tối đa (MSDR) của các phương pháp giấu tin trên ảnh nhị phân dựa trên phương pháp CPT mở rộng. 2.3. Kỹ thuật giấu tin Wu – Lee Kỹ thuật giấu tin theo khối bit trong 2.1 thể hiện độ an toàn không cao với việc sử dụng duy nhất kích thước khối là khoá 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ể sẽ thay đổi giá trị của một bit trong các khối ảnh toàn màu đen hoặc toàn màu trắng. Điều này sẽ có thể dẫn tới sự bất thường ở vị trí thay đổi so với các vị trí lân cận trong khối. Thuật toán giấu thông tin trong ảnh đen trắng do M.Y.Wu và J.H.Lee [4] đưa ra trong một bài báo đăng tại Proceedings of international Symposium on Multimedia Information Processing 1999 đã 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 khoá K cho việc giấu tin và đưa thêm các điều kiện để thay đổi bit trong mỗi khối. 22
2.3.1. Thuật toán giấu tin Cho hai ma trận A và B cùng kích thước, ta định nghĩa một số phép toán trên ma trận như sau: Định nghĩa 2.2.1: Phép nhân  hai ma trận A, B cùng cỡ được định nghĩa: C = A  B, với Cij = Aij * Bij Thí dụ minh hoạ phép nhân hai ma trận nguyên kích thước 3x3 như sau: 1 0 1 1 1 1 1 0 1 0 1 1  1 1 0 0 1 0 0 1 1 3 4 0 0 4 0 Theo định nghĩa 2.2.1, nếu phép toán  được áp dụng trên hai ma trận nhị phân khi đó nó sẽ tương đương với phép toán and nhị phân thông thường. Định nghĩa 2.2.2: Phép đảo giá trị phần tử Ai,j (ký hiệu NOT (Aij )) được định nghĩa: Cij = NOT (Aij), vơi Cij = 1 nếu Aij = 0 và Cij = 0 nếu Aij=1 Định nghĩa 2.2.3: Phép SUM trên ma trận A kích thước mxn (ký hiệu m n SUM(A) ) được định nghĩa: s= SUM(A) =  Ai, j i 1j 1 Thí dụ minh hoạ về phép toán SUM trên ma trận nguyên kích thước 3x3 như sau: 1 0 1 SUM 0 1 3 8 1 0 1  Tư tưởng giấu tin của Wu - Lee Thuật toán giấu tin 2.2 được thể hiệu như sau: chia ảnh môi trường thành các khối điểm ảnh có cùng kích thước mxn. Với mỗi khối điểm ảnh F (ma trận điểm ảnh) có thể được giấu tối đa 1 bit b (b= 0 hoặc b = 1). Quá 23
trình giấu tin sẽ thực hiện biến đổi ma trận nhị phân F thành ma trận G nhưng giữa F và G chỉ khác nhau tối đa là một vị trí.  Tóm tắt thuật toán Input: - m,n là kích thước của ma trận gồm m hàng và n cột, giá trị m, n được giữ bí mật. - Fmxn là ma trận nhị phân và là ma trận môi trường để giấu tin - Kmxn là ma trận nhị phân khoá và giá trị của ma trận K phải được giữ bí mật - b là bít nhị phân cần giấu (b = 0 hoặc b = 1) Output: Nếu thuật toán thực hiện thành công, kết quả thu được là ma trận G được biến đổi tối đa một phần tử từ ma trận F và G thoả mãn hai bất biến sau: + 0 < SUM(G  K) < SUM(K) (2.2) + SUM(G  K) mod 2 = b (2.3) Theo đầu ra của thuật toán, khi nhận được G để kiểm tra ma trận G có giấu thông tin hay không chúng ta sẽ cần kiểm tra G có thoả mãn bất biến (2.2) hay không. Với bất biến (2.3) quá trình giải mã thông tin giấu trong ma trận G có thể dễ dàng xác định được G chứa giá trị bit đã giấu bằng 0 hay bằng 1 theo (2.4) b =SUM(G K) mod 2 (2.4)  Nội dung thuật toán Bước 1: đặt s = SUM(F K) Bước 2: if 0 < s < SUM(K) then // sẽ biến đổi F thành G thoả mãn bất biến 2.2 và 2.3 Xét các trường hợp sau: 24
Trường hợp 1 if s mod 2 = b then G = F // giấu mà không cần biến đổi Trường hợp 2 if s = SUM(K) -1 then - Chọn ngẫu nhiên phần tử (i,j) thoả Fi,j = 1 và Ki,j =1 - Fi,j = 0 - G = F Trường hợp 3 if s = 1 then - Chọn ngẫu nhiên phần tử (i,j) thoả Fi,j = 0 và Ki,j =1 - Fi,j = 1 - G = F Trường hợp 4 if (s >1) and (s <SUM(K) -1 ) then - Chọn ngẫu nhiên phần tử (i,j) thoả Ki,j =1 - Fi,j = NOT (Fi,j) - G = F 2.3.2. Phân tích thuật toán Thuật toán sử dụng K nhằm làm tăng độ mật cho thuật toán giấu tin, Nếu trước đây chỉ biết kích thước khối là mxn thì đối phương đã có thể dễ dàng giải mã được tin mật thông qua ảnh chứa tin, nhưng với thuật toán của Wu-Lee ngoài giá trị m,n các thuật toán thám mã còn phải xác định giá trị cụ thể của ma trận K. Do vậy, để tìm được ma trận khóa K khi đã biết m, n các thuật toán thám mã phải duyệt O(2m*n) trường hợp khác nhau. Theo định nghĩa phép toán , và bất biến (2.3) nên nội dung thuật toán Wu- Lee sẽ biến đổi F thành G sao cho SUM(G  K) cùng tính chẵn lẻ với b. Do vậy, nếu b không cùng tính chẵn lẻ với SUM(G  K) thì thuật toán sẽ thực hiện đảo giá 25
trị của phần tử Fi,j ứng với Ki,j = 1 để đạt được bất biến (2.3). Như vậy, khoá K được xem như một mặt nạ, tạo ra khung nhìn cho thuật toán. Điều kiện 0 <SUM(F K)< SUM(K) quy định, nếu mọi vị trí (i,j) của F tại các vị trí Ki,j = 1 mà Fi,j đều bằng không hoặc đều bằng một thì không nên giấu tin vì nếu thực hiện giấu dễ bị lộ khóa K. 2.3.3. Thí dụ minh họa thuật toán Wu-Lee Giả sử ta cần giấu dãy bit b1b2b3 = 011 vào một ảnh kích thước 6x6 với ma trận khóa K có kích thước 3x3 như trong hình vẽ. Ta chia ảnh F thành 4 khối ảnh nhỏ với mỗi khối kích thước là 3x3 ta thu được F1, F2, F3, F4. F1 F2 G1 G2 0 1 0 1 0 1 Giữ liệu cần giấu: b1b2b3 =011 0 0 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 F3 F4 K G3 G4 Hình 2-1. Minh hoạ thuật toán giấu tin của Wu-lee - Với F1, 0< SUM(F1  K) = 3 < SUM(K) nên thuật toán sẽ giấu b1 (b1=0) vào F1 bằng cách biến đổi F1 thành G1 sao cho SUM(G1  K) mod 2 = b1. Trong trường hợp này, SUM(F1  K) thoả T/h 4 tại Bước 3 trong thuật toán, do vậy chúng ta sẽ đảo giá trị tại phần tử (i,j) của F1 ứng với Ki,j = 1. Giải sử ta chọn phần tử (1,2) kết quả sẽ thu được như G1 - Vì SUM(F2  K) = 0 nên khối F2 sẽ không được dùng để giấu dữ liệu do vậy G2 = F2. 26
- Với F3, do F3 thoả mãn điều kiện 0< SUM(F3 K) = 3 < SUM(K), nên thuật toán sẽ thực hiện giấu b2 vào F3. Trong trường hợp này, ta thấy SUM(F3  K) mod 2 = 1 = b2 nên không cần biến đổi F3 và G3 bằng F3. - Với F4, 0< SUM(F4  K) = 4 <SUM(K) nên thuật toán sẽ thực hiện giấu bit b3 = 1 vào khối F4bằng cách biến đổi F4thành G4 thoả mãn tính chất (2) và (3). Do SUM(F4  K) = SUM(K) -1 nên chúng ta chọn ngẫu nhiên phần tử (i,j) mà F4(i,j) = 1 mà Ki,j = 1 và thay đổi F4(i,j) = 0.Giả sử ta chọn phần tử (3,3) kết quả sẽ thu được như G4. 2.3.4. Một số nhận xét về thuật toán Wu-lee Thứ nhất: ảnh môi trường để thực hiệ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 trắng (hoặc đen) thì tỉ lệ bit giấu được sẽ rất thấp. Thứ hai: Vì trong mỗi ma trận điểm ảnh F thuật toán chỉ biến đổi tối đa là một phần tử (từ 1 thành 0 hoặc từ 0 thành 1), do vậy nếu chọn m, n đủ lớn thì sự thay đổi này khó có thể nhận biết bằng mắt thường nhưng khả năng giấu của thuật toán lại giảm đáng kể. Thứ ba: Khi cần biến đổi ma trận F, thuật toán luôn thay đổi ngẫu nhiên một phần tử Fi,j ứng với Ki,j=1. Do vậy, trong một số trường hợp ảnh sau khi được giấu tin sẽ xuất hiện những điểm khác biệt so với ảnh gốc và dễ dàng phân biệt được bằng mắt thường. Do đó, để tăng tính che giấu cho thuật toán chúng ta nên chọn phần tử (i,j) có định hướng theo một tiêu chí nào đó. Xét ví dụ giấu bit 0 vào ma trận có kích thước 5x4 với các giá trị cụ thể như sau: 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 F= 1 0 1 0 K= 1 1 0 0 b = 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 27
Giải sử chọn ngẫu nhiên phần (1,4) để thay đổi ta thu được G và thay đổi trên biên (có định hướng) ta chọn phần tử (5,3) kết quả ta được G’. Trong trường hợp này, chúng ta thấy rằng khả năng che giấu của G’ cao hơn G giống như trong Hình 2.2. 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 G= 1 0 1 0 G’= 1 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 1 Hình 2-2. Minh hoạ giữa thay đổi ngẫu nhiên và thay đổi có định hướng 2.4. Kỹ thuật giấu tin Chen – Pan – Tseng Định nghĩa 2.3.1: Phép XOR hai ma trận nhị phân cùng cấp A và B (ký hiệu A  B) được định nghĩa: C = A  B với Cij = 1 nếu Aij Bij và Cij = 0 nếu Aij= Bij Thí dụ minh hoạ phép toán  thực hiện trên hai ma trận nhị phân kích thước 3x3 như sau 1 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 0 0  0 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 Định nghĩa 2.3.2: Ma trận W kích thước mxn được gọi là ma trận trọng số cấp r (2r <= m*n | r là một số nguyên) nếu mọi phần tử của W thoả mãn điều kiện r {Wi,j |i=1 m, j=1 n} = {1,2, ,2 -1} Thí dụ minh hoạ về ma trận trọng số cấp 3 (r = 3) với ma trận W như sau: 1 3 2 5 6 7 W 4 7 1 2 6 3 28
1 3 2 5 6 7 Nhưng với ma trận K lại không phải là ma trận trọng số cấp 3 vì 1 7 1 2 6 3 3 trong ma trận K không tồn tại phần tử (i,j) để Ki,j = 4, mà 4 {1,2, 2 -1} vậy {Ki,j |i=1 m, j=1 n} ≠ {1,2, ,2r-1} 2.4.1. Ý tưởng Thuật toán giấu tin của ba tác giả Y.Chen, H.Pan, Y.Tseng (CPT) [5] cũng áp dụng tư tưởng giấu tin theo khối bit nhưng mỗi khối có thể giấu được một dãy r bit (với 2r-1 ≤ m×n) bằng cách thay đổi nhiều nhất hai bit trong khối. Như vậy so với thuật toán giấu tin của Wu-Lee, thuật toán CPT có khả năng giấu rất cao, trong khi số bit cần thay đổi khá ít, do đó sẽ không ảnh hưởng đáng kể đến chất lượng ảnh sau khi giấu. Thuật toán CPT sử dụng một ma trận trọng số để giấu được một dãy nhiều bit vào trong mỗi khối, và ma trận trọng số này cũng chính là một thành phần bí mật cùng với ma trận khoá, do vậy độ an toàn của thuật toán CPT cao hơn của thuật toán giấu tin của Wu-Lee. 2.4.2. Thuật toán CPT  Tóm tắt thuật toán Để tiện cho việc trình bày, trong luận văn sẽ trình bày nội dung thuật toán CPT áp dụng cho một khối bit (ma trận nhị phân). Các phép toán sử dụng trong thuật toán này đều được hiểu theo nghĩa mod 2r Input: - Fm×n là ma trận nhị phân (khối điểm ảnh) và là môi trường dùng để giấu tin - r là số bit cần giấu vào ma trận F, r phải thỏa mãn điều kiện 2r≤m×n. - Km×n là ma trận nhị phân và là khóa bí mật để giải tin - Wm×n là ma trận trọng số cấp r, ma trận W được giữ bí mật - b1,b2, ,br là dãy bit nhị phân cần giấu 29
Output: Gọi b là giá trị thập phân của dãy b1,b2, ,br, G là ma trận sau khi đã giấu b vào F bằng cách biến đổi tối đa 2 phân tử trong ma trận F, khi đó G phải thoả mãn bất biến (2.5). SUM((G K)  W) mod 2r = b (2.5)  Nội dung thuật toán Bước 1: Tính T = FK Bước 2: Tính S = SUM(TW) Bước 3: Xây dựng tập: r Zα = {(i,j) | (Wi,,j=α và Ti,j = 0) hoặc (Wi,j=2 -α và Ti,j=1)} (2.6) Nhận thấy nếu đảo giá trị (thay 0 thành 1 hoặc thay 1 thành 0) của một phần tử Fi,j sẽ làm cho S tăng thêm α đơn vị. Bước 4: Gọi G là khối bit sau khi đã giấu b vào F, và S’= SUM((G  K) W). Bước này sẽ thực hiện giấu b bằng cách thay đổi tối đa hai bit trong F sao cho đạt được bất biến: S’ = b (mod 2r) (2.7) Bất biến (2.7) này cũng chính là cơ sở để khôi phục lại tin. - Tính d = b – S (mod 2r) Trường hợp 1 Nếu d = 0 thì b = S (mod 2r) nên đã đạt được bất biến (2.7) do đó trường hợp này giấu b vào F mà không cần phải biến đổi F Trường hợp 2 Nếu d 0 thì cần phải biến đổi F sao cho đạt được bất biến (2.7). Trong trường hợp này có hai khả năng: 30
Trường hợp 2.1 Nếu Zd Ø thì chọn (i,j) Zd rồi đảo giá trị phần tử Fi,j, khi đó theo định nghĩa (2.1) S sẽ tăng thêm d đơn vị do đó đạt được bất biến (2.7) Trường hợp 2.2 Nếu Zd = Ø thì tiếp tục xét Z2d, Z3d Chọn h là số tự nhiên đầu tiên thoả mãn Zhd Ø (xem nhận xét 2.1 bên dưới) + Chọn (i,j) Zhd và thay đổi bit Fi,j, khi đó theo (2.6) S tăng thêm một lượng là hd (2.8) + Chọn (u,v) Zd-hd và thay đổi Fu,v, khi đó theo (2.6) S tăng thêm một lượng là d-hd (Zd-hd Ø xem nhận xét 3.2 bên dưới) (2.9) Từ (2.8) và (2.9) suy ra cần thay đổi hai bit Fi,j và Fu,v của F để có thể giấu được r bit thông tin vào F. Nhận xét 2.1. Qua các bước thực hiện của thuật toán nhận thấy thuật toán sẽ luôn thực hiện được nếu tồn tại h thoả mãn Zhd Ø. Điều này sẽ được chứng minh trong mục tiếp theo. 2.4.3. Cách chứng minh về tính đúng đắn của thuật toán Nhận xét 3.1. Theo định nghĩa tập Zα và tính chất của ma trận trọng số W thì có thể suy ra: tập Z r 1 Ø. 2 Chứng minh Z r 1 Ø 2 Đặt α = 2r-1 thì giá trị α {1,2, ,2r-1} Theo tính chất của ma trận trọng số W, các phần tử của W cần thoả mãn: r {Wi,j |i=1 m, j=1 n} = {1,2, ,2 -1} Vì vậy phải tồn tại ít nhất một cặp (i,j) sao cho Wi,j = α . Mặt khác do T là ma trận nhị phân nên Ti,j có giá trị bằng 0 hoặc 1. Xét các trường hợp: - Nếu Ti,j = 0: Do Wi,j = α nên (i,j) thoả điều kiện thứ nhất trong (2.6), vậy (i,j) Zα 31
r-1 r - Nếu Ti,j = 1: Do Wi,j = α mà α = 2 = 2 – α nên (i,j) thoả điều kiện thứ hai trong (2.6), vậy (i,j) Zα Do đó tập Z r 1 Ø. 2 Nhận xét 3.2. nếu Zα = Ø thì Z -α Ø Chứng minh r Theo (2.6) định nghĩa về tập Zα = {(i,j) | (Wi,,j=α và Ti,j = 0) hoặc (Wi,j=2 -α và Ti,j=1)} Do Zα = Ø và theo định nghĩa 2.3.2 ma trận trọng số W luôn thoả mãn điều r kiện {Wi,j |i=1 m, j=1 n} = {1,2, ,2 -1}. Vì vậy, phải tồn tại một phần tử (u,v) để r (Wu,v = α và Tu,v = 1) hoặc (Wu,v = 2 - α và Tu,v = 0) Mà 2r - α = - α (mod 2r) = - α. Do đó, khi Zα = Ø sẽ tồn tại (u,v) để (Wu,v = - α và Tu,v = 0) (2.10) Từ (2.10) và (2.6), ta suy ra khi Zα = Ø thì Z -α Ø Vì h là số tự nhiên đầu tiên thoả mãn điều kiện Zhd Ø, suy ra Z( h - 1)d = Ø. Theo (2.10) khi Z( h - 1)d = Ø thì Zd-hd Ø, vì vậy phép chọn phần tử (u,v) trong (2.9) luôn thực hiện được. Nhận xét 3.3. Luôn tồn tại h sao cho hd = 2r-1 (mod 2r) Chứng minh. Trường hợp 1: Nếu d lẻ thì có thể biểu diễn d dưới dạng: d = 2t+1. Nhân cả 2 vế của biểu thức với 2r-1 ta có: 2r-1.d = 2r-1.2t+2r-1 suy ra 2r-1.d = t.2r+2r-1 = 2r-1 (mod 2r) Chọn h = 2r-1 ta có hd = 2r-1 Trường hợp 2: Nếu d chẵn và d chỉ chứa thừa số nguyên tố 2 thì có thể biểu diễn d dưới dạng: d = 2u (với u ≤ r-1). Xét các khả năng: + Nếu u = r-1 thì chọn h = 1 ta có hd =1.2r-1= 2r-1 + Nếu u < r-1 thì chọn h = 2(r-1)-u ta có hd = 2(r-1)-u.2u = 2r-1 32
Trường hợp 3: Nếu d chẵn và d chứa cả các thừa số nguyên tố khác 2 thì có thể biểu diễn d dưới dạng: d = (2t+1)2v (với 1 ≤ v < r-1) Chọn h = 2(r-1)-v ta có: hd = 2(r-1)-v (2t+1).2v = (2t+1)2r-1 = t.2r + 2r-1 = 2r-1 (mod 2r) Chứng minh tính đúng của thuật toán. Theo nhận xét 2.1: để chứng minh tính đúng của thuật toán cần chỉ ra tồn tại h sao cho Zhd Ø. Theo nhận xét 3.3 luôn tồn tại h sao cho hd = 2r-1 (mod 2r). Mặt khác theo Z r 1 hd nhận xét 3.1 tập 2 Ø do đó luôn tồn tại h sao cho Z Ø. Điều đó chứng tỏ thuật toán luôn thực hiện đúng. 2.4.4. Một số thí dụ minh họa thuật toán CPT  Thí dụ minh hoạ trường hợp thay đổi một bit Quá trình giấu tin: Giả sử cần giấu dãy bit 1011 vào ma trận điểm ảnh có kích thước 4x4 với các tham số đầu vào như hình 2.3 1 0 1 0 1 0 1 0 1 3 2 6 1 1 0 1 1 0 1 0 7 8 5 4 F = 0 1 0 1 K = 0 1 1 0 W = 12 11 9 10 0 0 1 0 1 0 1 1 12 14 15 3 0 0 0 0 0 0 0 0 F 1011 1 0 1 0 0 1 1 1 0 8 5 4 1 0 0 1 F K= 0 0 1 1 T W = 0 0 9 10 G = 0 1 0 1 1 0 0 1 12 0 0 3 0 0 1 0 T Hình 2-3. Minh hoạ thuật toán CPT trường hợp thay đổi 1 bit 33
- Tính s = SUM(T W ) = 51 - Đặt d = b - s (mod 2r) = 11 - 41 (mod 16) = 8 Vì d = 8 0, nên ta xây dựng tập r Zα = {(i,j) | (Wi,,j=α và Ti,j = 0) hoặc (Wi,j=2 -α và Ti,j=1)} Với α = d = 8, xét ma trận W ta thấy phần tử (2,2) thoả mãn điều kiện r (W2,2=2 - d và T2,2 = 1), suy ra Zd Ø. Do Zd Ø, theo thuật toán CPT chỉ cần đảo giá trị phần tử Fi,j |(i ,j) thuộc Zd. Chọn i =2 và j = 2 thực hiện phép đảo phần tử F2,2 ta sẽ được ma trận kết quả G như trong Hình 2.3. Quá trình giải mã: Giả sử khi nhận được ma trận G đã chứa thông tin cần giấu, với các giá trị trên Hình 2.4, để giải mã thông tin giấu trong G ta sẽ thực hiện tính theo bất biến b’ =SUM(T W) mod 2r  b’ = 43 mod 16  b’ = 11 = 1011(2) 1 0 1 0 1 0 1 0 1 3 2 6 G = 1 0 0 1 K = 1 0 1 0 W = 7 8 5 4 0 1 0 1 0 1 1 0 12 11 9 10 0 0 1 0 1 0 1 1 12 14 15 3 0 0 0 0 0 0 0 0 T = 0 0 1 1 TW= 0 0 5 4 0 0 1 1 0 0 9 10 1 0 0 1 12 0 0 3 G  K Hình 2-4. Minh hoạ quá trình giải mã thông tin đã giấu 34
 Thí dụ minh hoạ trường hợp thay đổi hai bit: Quá trình giấu tin: Giả sử cần giấu dãy bit 0100 vào ma trận điểm ảnh có kích thước 4x4 với các tham số đầu vào F, K, W thì đầu ra tương ứng sau khi kết thúc thuật toán là ma trận G như trong Hình 2.5. Quá trình giấu diễn ra như sau: - Tính: T = F K (kết quả như Hình 2.5) - Tính: s = SUM(T W ) = 59 - Đặt: d = b – s (mod 2r) = 4 – (59 mod 16) = 9 Vì d = 9 0, nên ta xây dựng tập r Zα = {(i,j) | (Wi,,j=α và Ti,j = 0) hoặc (Wi,j=2 -α và Ti,j=1)} Với α = d = 9, không tồn tại phần tử (i,j) để (Wi,,j=9 và Ti,j = 0) hoặc (Wi,j=7 và Ti,j=1), suy ra Zd = Ø. r + Xét Z2d: Với d = 9 và do phép toán mod 2 nên Z2d Z2. Do không tồn tại (i,j) để (Wi,,j=2 và Ti,j = 0) hoặc (Wi,j=14 và Ti,j=1) => Z2d Ø +Xét Z3d: với d = 9 ta có Z3d Ø vì tồn tại phần tử (3,2) để (W3,2 = 3d và T3,2 = 0). - Theo thuật toán, khi Zhd Ø (h là số tự nhiên đầu tiên thoả mãn) ta sẽ thay đổi giá trị hai phần tử Fi,j và Fu,v với (i,j) thuộc Zhd và (u,v) thuộc Z d-hd. + Chọn (i,j) = (3,2) và (u,v) = (2,1), sau khi đảo F3,2 và F2,1 ta sẽ được ma trận kết quả G như trong Hình 2.5 35
1 0 0 1 1 0 1 0 1 3 2 6 1 1 0 1 1 0 1 0 7 8 5 4 F = 0 1 0 1 K = 0 1 1 0 W = 12 11 9 10 0 0 1 0 1 0 1 1 12 14 15 3 0 0 1 1 0 0 2 6 1 0 0 1 0 1 1 1 0 8 5 4 1 1 0 1 T = 0 0 1 1 TW = 0 0 9 10 G = 0 0 0 1 1 0 0 1 12 0 0 3 0 1 1 0 FK Hình 2-5. Thí dụ minh hoạ trường hợp thay đổi hai bit Quá trình giải mã Để giải mã thông tin đã được giấu trong ma trận G chúng ta cần tính b’= SUM((GK)W) mod 2r, sau đó đổi giá trị b’ thành dãy nhị phân gồm r bit có giá trị tương ứng và đó chính là dãy bit đã được giấu. Ví dụ: với các ma trận W, K, G như trong hình 2.5 ta tính được thông tin giấu trong G như sau b’= SUM((G  K) W) mod 2r => b’ = 84 mod 16 = 4 = 0100(2) 2.4.5. Phân tích thuật toán Thuật toán có thể giấu được r bit vào trong một khối mxn với điều kiện là r 2 <mxn và chỉ cần thay đổi nhiều nhất là 2 bit trên một khối. Như vậy, thuật toán này đã có cải tiến rất lớn so với những thuật toán khác chỉ giấu được một bit vào mỗi khối 36
Độ an toàn của thuật toán cũng rất cao thông qua hai ma trận dùng làm khoá để giải tin đó là ma trận trọng số và ma trận khoá. Như vậy độ bảo mật của thuật toán là: mn r r mn (2r 1) Cr (2 1)! (2 1) 2m*n 2 1 Thuật toán này đương nhiên có thể áp dụng cho ảnh màu và ảnh đa cấp xám. Ta cũng sẽ sử dụng kỹ thuật chọn ra bit ít quan trọng nhất của mỗi điểm ảnh để xây dựng ma trận hai chiều các bit 0, 1 như trong thuật toán với ảnh đen trắng Nếu áp dụng tốt thuật toán này cho ảnh màu thì có thể nói thuật toán đã đạt được yêu cầu cơ bản của một ứng dụng giấu tin mật đó là đảm bảo tính ẩn của thông tin giấu, số lượng thông tin giấu cao. 37
Chương 3. NÂNG CAO CHẤT LƯƠNG GIẤU TIN BẰNG PHƯƠNG PHÁP MODULE 3.1. Một số phương giấu tin trong ảnh màu và ảnh đa cấp xám Kết quả thực nghiệm cho thấy việc sử dụng ảnh đen trắng làm ảnh môi trường đem lại hiệu quả rất thấp vì việc biến đổi điểm ảnh từ đen sang trắng hay trắng sang đen rất dễ tạo ra các nhiễu trên ảnh và dễ bị phát hiện bởi hệ thống thị giác của con người. Hơn nữa ảnh đen trắng cung cấp lượng dữ liệu tương đối nhỏ để thực hiện các thao tác giấu tin. Ví dụ như một bức ảnh đen trắng kích thước 300*300 pixel chỉ cung cấp cho ta một lượng dữ liệu vào khoảng 90 kilobytes (kB) trong khi một bức ảnh 24 màu kích thước tương ứng có thể cho tới 2000 kB. Hạn chế này được khắc phục bằng cách sử dụng ảnh màu và ảnh đa cấp xám làm ảnh môi trường. 3.1.1. Giấu tin trong ảnh màu và ảnh đa cấp xám Đối với việc chọn ảnh màu và ảnh đa cấp xám làm ảnh môi trường ta cần thực hiện thêm một bước xử lý nữa. Trước hết ta quan tâm tới khái niệm bit ít đặc trưng nhất (Least Significant Bit hay - LSB). LSB là bit có ảnh hưởng ít nhất tới việc quyết định màu sắc của mỗi điểm ảnh, vì vậy khi ta thay đổi bit ít đặc trưng nhất của một điểm ảnh thì màu sắc của điểm ảnh mới sẽ tương đối gần với điểm ảnh cũ. LSB của một điểm ảnh cũng tương tự như chữ số hàng đơn vị của một số tự nhiên, khi ta thay đổi giá trị của chữ số này thì chênh lệch giữa số cũ và số mới sẽ ít hơn khi ta thay đổi giá trị của chữ số hàng chục hoặc hàng trăm. Việc xác định LSB của mỗi điểm ảnh trong một bức ảnh phụ thuộc vào định dạng của ảnh và số bit màu dành cho mỗi điểm của ảnh đó. Quá trình giấu tin vào ảnh màu và đa cấp xám cũng tương tự như với ảnh đen trắng nhưng trước hết ta chọn từ mỗi điểm ảnh ra từ ít đặc trưng nhất để tạo thành một ảnh nhị phân gọi là ảnh thứ cấp. Sử dụng ảnh thứ cấp này như là ảnh môi trường để giấu tin, sau khi biến đổi ảnh thứ cấp ta trả nó lại ảnh ban đầu để thu được ảnh kết quả. 38
Ảnh màu và ảnh đa cấp xám cho hiệu quả cao hơn ảnh đen trắng vì việc thay đổi bit ít đặc trưng nhất trong những ảnh này dường như không làm thay đổi màu sắc của điểm ảnh trong việc thay đổi mỗi bit trong ảnh đen trắng làm cho điểm ảnh chuyển màu từ đen sang trắng hoặc ngược lại từ trắng sang đen do đó rất dễ bị phát hiện. Đối với ảnh 16 bit màu hoặc 24 bit màu việc xác định LSB tương đối đơn giản, tuy nhiên đối với ảnh nhỏ hơn hoặc bằng 8 bit màu (những ảnh có sử dụng bảng màu) thì rất phức tạp. Khó khăn này có thể khắc phục nếu ta sắp lại bảng màu cuả ảnh hoặc sử dụng những màu không dùng đến trong bảng màu của ảnh nhỏ hơn bằng 8 bit màu. 3.1.1. Ảnh đa cấp xám Đối với ảnh đa cấp xám, với 256 mức xám là phổ biến thì bảng màu của nó đã được thiết kế sẵn, tức là những cặp màu trong bảng màu có chỉ số chênh lệch càng ít thì càng giống nhau. Vì vậy đối với ảnh đa cấp xám bit LSB của mỗi điểm ảnh là bit cuối cùng của mỗi thành phần B, G, R của nó. Quá trình tách bit LSB của ảnh đa cấp xám và thay đổi các bit này bằng thuật toán giấu tin trong ảnh đen trắng sẽ làm chỉ số màu của điểm ảnh màu bị thay đổi tăng hoặc giảm 1 đơn vị, do đó điểm ảnh mới sẽ có độ sáng tối của ô màu liền trước hoặc liền sau ô màu của điểm ảnh cũ. Bằng mắt thường rất khó có thể nhận thấy sự thay đổi về độ sáng tối này.Thực nghiệm cho thấy ngay cả khi ta đảo toàn bộ các bit cuối của điểm ảnh trong một ảnh 8 bit cấp xám cũng không gây ra sự khác nhau nhiều. Vì vậy việc trong mỗi khối ảnh ta chỉ thay đổi nhiều nhất 2 điểm ảnh sẽ khiến khả năng phân biệt ảnh gốc và ảnh kết quả là rất khó khăn. 3.1.2. Phương pháp LSB Ý tưởng: Phương pháp LSB (Least Bit Significant) sẽ thay thế bit ít quan trọng nhất, thường là bit cuối của mỗi mẫu dữ liệu bằng bít thông tin mật. Như vậy 39
trên mỗi pixel của một ảnh BMP 24bpp có thể giấu được từ 1 đến 3 bit mật. Ví dụ mẫu 8 bit, bit cuối 0 được thay thế bởi bit thông tin mật 1: Hình 3-1. Minh họa kĩ thuật giấu LSB Ưu điểm của phương pháp này là dễ cài đặt và cho phép giấu dữ liệu nhiều. Có thể tăng thêm dữ liệu giấu bằng cách sử dụng hai bit LSB. Tuy nhiên cách làm này cũng làm tăng nhiễu trên đối tượng chứa dẫn đến đối phương dễ phát hiện và thực hiện các tấn công. Vì vậy dữ liệu chứa cần phải được chọn trước khi giấu sử dụng phương pháp này. Để tăng độ an toàn cho kỹ thuật này, ta sử dụng bộ sinh số ngẫu nhiên để sinh ra các vị trí các mẫu được chọn giấu chứ không phải các mẫu liên tục. Bộ sinh số này sử dụng một khóa bí mật K như một phần tử khởi tạo của bộ sinh số. Khóa K này được sử dụng trong cả quá trình giấu tin và giải tin. Lưu ý là phương pháp sinh số không tạo ra các giá trị trùng nhau để trường hợp một vị trí được giấu hai lần. 3.1.3. Phương pháp chẵn lẻ giấu tin trên ảnh chỉ số Trong mục này, chúng ta xem xét một hướng tiếp cận về giấu tin trên ảnh chỉ số, cụ thể là trên ảnh bitmap 8bpp: Phương pháp xác định tính chẵn lẻ và màu kế cận. Với ảnh chỉ số 8bpp thì mỗi điểm ảnh được lưu bằng một byte, byte này chứa giá trị là chỉ số màu trên bảng màu của điểm ảnh. Như vậy ý tưởng của phương pháp như sau: Cho G là một ảnh BMP 8bpp, gọi P là palette có 256 màu. Dưới dạng tập hợp ta có thể viết P x0, x 1 , , x 255. Trong đó mỗi phần tử xi được xem như một vector gồm 3 thành phần (Red, Green, Blue). Giả sử chúng ta đã xây dựng một hàm 40
2 khoảng cách d(,) xi x j với các cặp điểm (,)xi x j thuộc P . Hàm khoảng cách d nói chung cần phải thỏa mãn được các yêu cầu cơ bản: khi d(,) xi x j càng nhỏ thì cảm quan về sự “giống nhau” của xi với x j phải càng lớn. Yêu cầu đặt ra cần xác định hai hàm Next(): xj P P và hàm CPE: . E 0,1. Sao cho thỏa mãn: - d( x , next ( x )) càng nhỏ càng tốt trên toàn bộ miền P - C( x ) C ( next ( x )) 1 (điều này có nghĩa là màu x và màu Next(x) khác tính chẵn lẻ theo tiêu chuẩn C. Giả sử đã xác định một cặp hàm như vậy, ta có thể xây dựng sơ đồ giấu tin mật và giải mã lấy tin như sau: 3.1.3.1. Sơ đồ giấu tin mật Yêu cầu giấu một dãy bit mật b b0 b 1 bn trong ảnh G, bi thuộc E. Ở đây mỗi bi là một bit mật cần giấu. Ta xét trên từng dòng điểm ảnh W của ảnh G. Với mỗi điểm ảnh p thuộc dòng W có màu x, để thực hiện giấu bit bi , ta tính C(x). Có hai trường hợp xảy ra: - Nếu C() x bi thì điểm ảnh p đã mang thông tin bit bi , ta chuyển qua xét điểm ảnh p+1 kế tiếp để giấu bit bi 1 kế tiếp. - Nếu C() x bi , ta thay thế màu x của điểm ảnh p bằng màu Next(x). Khi đó do tính chất của cặp hàm Next, C ta có C( Next ( x )) bi . Điều này có nghĩa rằng màu mới tại điểm p là Next(x) sẽ mang giá trị bit mật bi thông qua hàm C. Qua sơ đồ này cặp hàm Next và C có thể kết hợp thành một ma trận khóa bí mật K của sơ đồ giấu tin để chỉ thám tin bị tấn công. 41
3.1.3.2. Sơ đồ giải mã lấy tin mật Với một ảnh G đã mang thông tin mật b. Ta duyệt qua lần lượt từng điểm ảnh p. Giá trị chẵn lẻ không phải xác định bởi bit cuối cùng trong dãy bit như trong phương pháp LSB của mỗi byte điểm ảnh mà được tính thông qua hàm C(x). 3.2. Phương pháp giấu tin theo module 3.2.1. Phương pháp module Xét một ảnh G, để đơn giản ta chỉ xét một khối các điểm ảnh F ={F1, ,FN} gồm N điểm ảnh của G và xem Fi là giá trị màu của điểm ảnh Fi. Cho k là một số nguyên k>1, việc thay đổi điểm ảnh Fi có nghĩa là ta sẽ thực hiện thay đổi màu Fi thành một màu mới Fi’ theo k-1 cách khác nhau, trong trường hợp ảnh màu ta cần có thêm điều kiện màu Fi’ có độ sai khác so với màu Fi nhỏ hơn một khoảng cách màu cho trước (điều kiện này đảm bảo màu được thay thế có sự cảm quan về mặt màu sắc so với màu cũ là gần giống nhau, mục đích để mắt người không nhận ra được sự thay đổi đó). 3.2.2. Giấu tin sử dụng phương pháp Module Một môđun (phải) trên vành Zq (hay Zq - module) là một nhóm aben cộng M với phần tử trung hòa là 0 và được trang bị phép nhân vô hướng, gán tương ứng mỗi cặp (m,k) thuộc M × Zq với một phần tử m.k thuộc M. Với Zq={0,1, ,q-1}, thỏa mãn một số tính chất mà ta sẽ được: P1) m.0 = 0; m.1=m; P2) m+n = n+m, với  m,n thuộc M. P3) m.(k+l) = m.k + m.l, với  m thuộc M, k, l thuộc Zq. Định nghĩa 1. Cho v là một số tự nhiên, v > 0, M là một Zq-module U ⊆ M- {0}, ta gọi U là một v-cơ sở của module M nếu với x M – {0}, x có thể được biểu diễn bởi một tổ hợp tuyến tính của nhiều nhất v phần tử thuộc U. 42
(Nghĩa là, tồn tại n phần tử u1,u2, ,un U, n≤v, n phần tử t1, t2, , tn Zq sao cho x = u1.t1+u2.t2+ +un.tn ). Cho một ảnh G, ký hiệu CG là tập các mầu của G, CG = {Cp: p ∈ G}, trong đó Cp là màu của điểm ảnh p. Giả sử rằng chúng ta có thể xây dựng được hàm Val: CG Zq và một ánh xạ đa trị Next: CG CG nhằm thay đổi màu của các điểm ảnh p, thỏa mãn các điều kiện sau: (2.1) c ∈ CG,  x ∈ Zq–{0}, tồn tại c’ Next(c) thỏa mãn Val (c’)=Val(c)+x (trong Zq) và c Next(c). (2.2) Đối với ảnh màu  c, c’∈ CG, c’ Next(c), c’ là một màu giống màu c về mặt cảm quan màu sắc được phân biệt bởi mắt người (với ảnh nhị phân ta không đề cập đến điều kiện này). Cho một v-cơ sở U ⊆ M-{0}, một khối F ={p1,p2, ,pN} gồm N điểm ảnh thuộc ảnh G, N ≥|U| (khi thực hiện giấu tin ta thường chọn khối F có số phần tử là |U|, khi đó tỷ lệ giấu tin đạt được sẽ là cao nhất), đặt S={1,2, ,N} và xây dựng một toàn ánh: (2.3) h: S U, h được gọi là ánh xạ trọng số. Với mỗi pi∈F, w=h(i) được gọi là trọng số của pi . Với module M được xem như là tập dữ liệu mật, phần tiếp theo sẽ giới thiệu phương pháp giấu một phần tử bất kỳ d ∈ M vào khối F bằng cách thay đổi màu của nhiều nhất v phần tử thuộc F. Phương pháp giấu tin sử dụng một v-cơ sở U, với v nhỏ, v=1 hay 2. Số màu có thể được thay đổi trong mỗi điểm ảnh là k-1=|Zq|-1, q thường chọn nhỏ để nâng cao chất lượng ảnh giấu tin. Số bit có thể giấu trong F là r = log2(|M|) . 43
3.2.3. Giấu tin sử dụng tập 1-cơ sở Cho U ⊆ M-{0}, U là tập 1-cơ sở của M. A1. Giấu phần tử bí mật d vào F Bước 1) Tính m = i∈S h(i).Val(pi), trong module M Bước 2) Trường hợp m = d: giữ nguyên F; Trường hợp d m, tính a = d – m, ta có 0 ≠ a ∈ M - Do U là 1-cơ sở của M do đó theo định nghĩa 1 sẽ tồn tại w ∈ U, t ∈ Zq– {0}, sao cho a = w.t, theo (2.3) h là một toàn ánh từ S vào U do đó ta luôn tìm được i ∈ S thỏa mãn h(i)=w, khi đó ta có h(i).t = a = d-m. - Thay đổi màu pi thành pi’ Next(pi) thỏa mãn Val(pi’) = Val(pi)+t ( trong Zq ). B1. Lấy lại phần tử bí mật d từ F Tính u = i ∈S h(i).Val(pi) (trong M), u chính là giá trị mật đã được giấu vào F (u=d). 3.2.4. Giấu tin sử dụng tập 2-cơ sở Cho U ⊆ M-{0}, U là tập 2-cơ sở của M. A2. Giấu phần tử bí mật d vào F Bước 1) Tính m = i ∈S h(i).Val(pi), trong module phải M. Bước 2) - Trường hợp m = d: giữ nguyên F; - Trường hợp d m: tính a = d –m, a ∈ M-{0}. Do U là tập 2-cơ sở của M, có 2 trường hợp xẩy ra: i) Tồn tại j ∈ S, t ∈ Zq–{0} thỏa mãn h(j).t = a =d-m. Theo điều kiện (2.1), ta sẽ tìm được pj’ Next(pj) thỏa mãn Val(pj’)=Val(pj)+t và thay đổi màu pj thành pj’. 44
ii) Nếu không tồn tại j như trên, với tính chất của U ta luôn tìm được 2 phần tử x, y S, tx, ty Zq–{0} sao cho d –m =a = h(x).tx+h(y).ty. Theo điều kiện (2.1), ta sẽ tìm được 2 màu px’, py’ thỏa mãn pi’ Next(pi), Val(px’)=Val(px)+tx và py’ Next(py), Val(py’) = Val(py) + ty,. Ta thay đổi màu px thành px’ và py thành py’. B2. Lấy lại phần tử bí mật d từ F Tính u = i ∈S h(i).Val(pi) (trong M), u chính là giá trị mật đã được giấu vào F (u=d). Tính đúng đắn của phương pháp. Việc chứng minh tính đúng đắn tổng quát của thuật toán giấu tin sử dụng v- cơ sở có thể suy ra từ tính chất (P1-P3) của module mà v=1,2 là trường hợp riêng, sẽ thể hiện rõ qua các ví dụ minh họa ở các phần sau. 3.2.5. Một số sơ đồ giấu tin theo tiếp cận module trên Trong phần này sẽ giới thiệu một số sơ đồ giấu tin cụ trên ảnh đa mức xám và nhị phân dựa trên phương pháp module. Các sơ đồ này sử dụng các v-cơ sở, v nhỏ, v=1 hay 2, của module M trên vành Z3. 3.2.5.1. Sơ đồ giấu tin trên ảnh xám Xét trường hợp ảnh 256 mức xám, mỗi điểm ảnh có màu C (mức xám) được biểu diễn bởi 8 bit, C sẽ nhận các giá trị trong tập P={0,1, ,255}. Để xây dựng sơ đồ giấu tin sử dụng tập 2-cơ sở hạn chế và Z3-module, ta cần xác định: Module phải M, một 2-cơ sở U, các hàm Val, Next và ánh xạ trọng số h. n Module phải M là tích đề các của Z3, M=Z3 Z3 Z3 =Z3 , mỗi phần tử x=(x1,x2, ,xn) M được biểu diễn bởi một dãy n-bit x = x1x2 xn với phép toán cộng (+) và nhân vô hướng (.) được xác định như sau: Với mỗi x = x1x2 xn, y = y1 yn M, k Z3, D1) x+y = z1z2 zn where zi=xi +yi mod 3, i=1, ,n . 45
D2) x.k= z1z2 zn where zi=xi.k (trong Z3). Hàm Val: P Z3 được xác định như sau, Val(C) = (C AND 3) mod 3, với C P, đặt x = C AND 3, 0≤ x ≤3, việc thay đổi màu C thành màu C’ được thực hiện tại 2 bit ít ý nghĩa x của C (2 bit cuối), cụ thể việc thay đổi giá trị bit cuối cùng của C được sẽ được màu C’=C XOR 00000001, thay đổi giá trị bit thứ 2 của C sẽ được C’=C XOR 00000010, thay đổi giá trị 2 bit cuối của C sẽ được C’=C XOR 00000011, khi đó Val(C’)= (C’ AND 3) mod 3. Như vậy Next(C)={ C XOR 00000001, C XOR 00000010, C XOR 00000011}. Ví dụ 1: C=7 sẽ có biễu diễn là 00000111, x=11, khi đó Val(C) = x mod 3 = 0 trong Z3, nếu ta cần thay đổi C sao cho Val(C) được thay bằng Val(C)+2=2 trong Z3, điều này có nghĩa là x được thay bằng x’=2, x’có biễu diễn 10, khi đó C được thay bằng C’= 00000110. Sơ đồ giấu tin 2-M3 n Cho một 2-cơ sở U  M –{0}, M = Z3 Z3 Z3 =Z3 . Giả sử F={C1, ,Cm} là một khối các điểm ảnh của G, trong đó |F|≥ |U|, khi đó ta có thể xây dựng một toàn ánh: h: S={1, , m}→U. Với d M là dữ liệu mật cần giấu trong F, ta xây dựng thuật toán giấu d trong F bằng cách thay đổi màu của nhiều nhất 2 điểm ảnh thuộc F như sau: Bước 1) Tính p =  i S h(i).v(Ci) trong M. Bước 2) So sánh p và d, có các trường hợp sau xẩy ra: a) Trường hợp p = d: giữ nguyên F. b) Trường hợp p ≠ d: Đặt x = d – p M –{0}, vì U là một 2-cơ sở của M, x sẽ được biểu diễn bởi tổ hợp tuyến tính của nhiều nhất 2 phần tử thuộc U, có 2 trường hợp xẩy ra: 46
i) Nếu x = u.t với u U, t Z3-{0}, ta tìm một điểm ảnh Ci F sao cho h(i)=u, tiếp đó thực hiện thay đổi màu Ci thành Ci’sao cho Val(Ci’) = Val(Ci)+t. ii) Nếu x = u.t + v.t’ với u, v U và t, t’ Z3-{0}, ta sẽ tìm được 2 điểm ảnh Ci, Cj F sao cho h(Ci) = u, h(Cj) = v, thực hiện thay đổi màu Ci, Cj thành Ci’, Cj’ sao cho Val(Ci’) = Val(Ci) + t, Val(Cj’) = Val(Cj) + t’. Khôi phục lại giá trị mật từ F Tính d = h( i ). v ( C ) trong M. CF j j Ví dụ 2: Xét Z3-module M= Z3 Z3 Z3 Z3 mỗi phần tử x M sẽ được biểu diễn bởi dãy 4-phần tử thuộc Z3. Tập U={1100, 1200, 1000, 0100, 0011, 0012, 0010, 0001} là một 2-cơ sở của M, đặt u1=1100, u2=1200, u3=1000, u4=0100, u5=0011, u6=0012, u7= 0010, u8=0001. Với mỗi khối F các điểm ảnh thỏa |F| ≥ |U|=8, chẳng hạn F={p1, ,p8}, p1=13, p2=65, p3=139, p4=211, p5=222, p6=173, p7= 25, p8=130, ta sẽ thực hiện giấu phần tử tùy ý d M vào khối F như sau. Biểu diễn nhị phân p1= 00001101 cho ta Val(p1) = 1, p2=01000001 với Val(p2) = 1, p3 = 10001011 với Val(p3) = 0, p4 = 11010011 với Val(p4) = 0, p5=11011110 với Val(p5) = 2, p6 =10111101 với Val(p6) = 1, p7= 00011001 với Val(p7)=1, p8= 10000010 với Val(p8)=2. Ta xây dựng toàn ánh h: S={1,2, ,8} → U với h(i) = ui. Giả sử rằng chúng ta cần giấu phần tử d = 2102 vào khối F. Tính p = i S h(i).Val(pi) =u1.1 + u2.1 + u3.0 + u4.0 + u5.2 + u6.1 + u7.1+ u8.2 = 1100 + 1200 + 0 + 0 + 0022 + 0012 + 0010 + 0002 = 2010. Ta có –p = 1020 trong M Vì p≠ d, ta tính m = d-p = 2102 + 1020 = 0122 trong M. Ta tìm được biểu diễn của m trong U như sau: m = u4.1+u5.2 (0122=0100.1+0011.2), như vậy ta cần thay đổi màu p4 thành p4’ sao cho Val(p4’) = Val(p4) + 1 = 1 trong Z3 và màu p5 thành màu p5’ sao cho Val(p5’) = Val(p5) + 2 = 1 47
trong Z3. Điều này có nghĩa là ta sẽ thay đổi 2 bit LSB của p4 là 11 thành 01, 2 bit LSB của p5 là 10 thành 01. Ta có màu mới p4’=11010001, p5’= 11011101 như vậy khối F sau khi có giấu tin có giá trị như sau: Fnew ={ 13, 65, 139, 219, 221, 173, 25, 130} Để nhận lại giá trị mật được giấu trong Fnew ta tính p = i S h(i).Val(pi) = u1.1 + u2.1 + u3.0 + u4.1 + u5.1 + u6.1 + u7.1+ u8.2 = 1100 + 1200 + 0 + 0100 + 0011+ 0012 + 0010 + 0002 = 2102 = d là giá trị mật đã được giấu vào khối F. 3.2.5.2. Sơ đồ giấu tin sử dụng module trên ảnh nhị phân Xét trường hợp ảnh nhị phân G, mỗi điểm ảnh sẽ có màu C được biểu diễn bởi 1 bit, C nhận các giá trị 0, 1. Ta ghép từng cặp điểm ảnh liên tiếp của G và xem mỗi cặp đó như một điểm ảnh màu (theo G). Để dễ phân biệt ta gọi ảnh được nhìn theo cách tiếp cận mới với mỗi điểm ảnh là một cặp điểm ảnh của G là G’ khi đó mỗi điểm ảnh C’ của G’ sẽ nhận giá trị trong tập P={(0,0), (0,1), (1,0), (1,1)} để đơn giản ta viết {00, 01, 10, 11}. Ta xây dựng module phải M và các phép toán cộng (+) và nhân vô hướng (.) như trong sơ đồ giấu tin trên ảnh xám (mục 2.2.1). Hàm Val được xác định như sau: Val: P Z3, Val(C’) = C’ mod 3 với C’ P Sơ đồ giấu tin 1-M3: n Cho tập 1-cơ sở hạn chế U  M –{0}, M = Z3 Z3 Z3 =Z3 . Giả sử F={C1, ,C2m} là một khối các điểm ảnh của G, trong đó |F|≥ 2.|U|. Cho K là một ma trận khóa nhị phân gồm 2.m phần tử tùy ý. Tính F’=F K = {C1’, ,C2m’}. Ghép cặp hai bit kề nhau thành một phần tử của tập T = {T1, ,Tm}, với Ti= C2i-1’C2i’, khi đó ta có thể xây dựng một toàn ánh: h: S={1, , m}→U. Với d M là dữ liệu mật cần giấu trong F, ta xây dựng thuật toán giấu d trong F bằng cách thay đổi màu của nhiều 48
nhất 1 điểm ảnh thuộc T (có nghĩa là sẽ thay đổi nhiều nhất 2 điểm ảnh thuộc F) như sau: Bước 1) Tính p =  i S h(i).Val(Ti) trong M. Bước 2) So sánh p và d, có các trường hợp sau xẩy ra: i) Trường hợp p = d: giữ nguyên F. ii) Trường hợp p ≠ d: Đặt x = d – p M –{0}, vì U là một 1-cơ sở của M, x sẽ được biểu diễn bởi tổ hợp tuyến tính của 1 phần tử thuộc U nghĩa là u U, t Z3 –{0}sao cho x = u.t ta tìm một điểm ảnh Ti T sao cho h(i)=u, tiếp đó thực hiện thay đổi màu Ti thành Ti’ sao cho Val(Ti’) = Val(Ti)+t. Thực hiện thay đổi màu C2i-1C2i thành C2i-1C2i XOR (T’ XOR T) Khôi phục lại giá trị mật từ F Tính F’=F K, xác định T dựa trên F’ Tính d = h( i ). Val ( T ) trong M. TT i i Ví dụ 3: Xét Z3-module M = Z3 Z3 mỗi phần tử x M sẽ được biểu diễn bởi dãy 2-phần tử thuộc Z3. Tập U={11,12,10,01} là một 1-cơ sở của M, đặt u1=11, u2=12, u3=10, u4=01. Mỗi khối F thỏa mãn yêu cầu |F| ≥ 2|U|=8, chẳng hạn F={1,0,0,1,0,1,1,1} gồm 8 phần tử, ta có thể thực hiện giấu phần tử d M tùy ý. Cho một ma trận khóa nhị phân K={0,1,0,1,1,1,1,0}. Trước hết tính F K = {1,1,0,0,1,0,0,1}, ghép cặp 2 bit một, ta có T={11, 00,10, 01}, đặt T1=11, T2=00, T3=10, T4=01. Ta xây dựng toàn ánh h: S={1,2,3,4} → U với h(i) = ui. Giả sử cần giấu giá trị d = 22 vào F. Tính p =  i S h(i).Val(Ti) = u1.0 + u2.0 + u3.2 + u4.1 = 10.2 + 01.1 = 20+01=21, -p = 12 49
Vì p≠ d, ta tính m = d-p = 22 + 12 = 01 trong M. Do m = u4.1, ta thay đổi màu T4 sao cho thành màu T4’ sao cho Val(T4’) = Val(T4) + 1 = 2, như vậy T4’=10. Ta có F7F8=11 sẽ được đổi thành (11 XOR (T4 XOR T4’)) =(11 XOR (01 XOR 10)) = 00. Như vậy khối điểm ảnh có giấu tin Fnew={1,0,0,1,0,1,0,0} Để nhận lại giá trị mật được giấu trong Fnew ta tính F newK = {1,0,0,1,0,1,0,0} {0,1,0,1,1,1,1,0}={1,1,0,0,1,0,1,0}, như vậy T={11, 00, 10, 10}, tính p =  i S h(i).Val(Ti) = u1.0 + u2.0 + u3.2 + u4.2 = 20+02=22 = d là giá trị cần tìm. Kết luận Phần này đã tìm hiểu, trình bày nội dung về lược đồ giấu tin mới dựa trên tiếp cận module: Sơ đồ giấu tin 2-M3 sử dụng các 2-cơ sở U và sơ đồ giấu tin 1-M3 sử dụng các 1-cơ sở của module trên vành Z3. Sơ đồ 2-M3 sử dụng giấu tin trong ảnh đa mức xám, theo ví dụ 2 ta thấy với mỗi khối điểm ảnh F gồm 8 phần tử, bằng cách thay đổi giá trị của nhiều nhất 2 điểm ảnh thuộc F, ta sẽ giấu được tập các giá trị từ 0 đến 2222 (theo hệ cơ số 3), theo cơ số 10 là các giá trị từ 0 đến 80, nghĩa là với sơ đồ 2-M3 mỗi khối 8 điểm ảnh có thể giấu được log281 = 6 bit mật. Sơ đồ 1- M3 minh họa sử dụng để giấu tin trong ảnh nhị phân, theo ví dụ 3, trong mỗi khối 8 điểm ảnh F bằng cách thay đổi giá trị của nhiều nhất 2 phần tử thuộc F, ta có thể giấu được các giá trị từ 0 đến 22 (theo hệ cơ số 3, 22=8 theo hệ cơ số 10), nghĩa là ta sẽ giấu được log29 = 3 bit trong F, bằng số bit giấu được theo phương pháp CPT. Nếu áp dụng sơ đồ 1-M3 cho ảnh đa mức xám theo cách như sơ đồ 2-M3, điều này tương đương với khả năng, trên một khối T có 4 điểm ảnh, thay màu 1 điểm có thể giấu 3 bit Các sơ đồ có thể kết hợp một khóa nhị phân K chọn ngẫu nhiên để tăng độ an toàn chống thám tin và có thể áp dụng cho cả ảnh đa mức xám hay nhị phân. Việc thay màu một điểm ảnh trên ảnh đa mức xám chỉ thực hiện trên 2 bit LSB nên không thể phát hiện bằng mắt. Số điểm ảnh thay đổi bé, cùng sự thay đổi màu ít, đảm bảo yếu tố chống thám tin cao cho các sơ đồ khi áp dụng thực tiễn. 50
Ngoài ra, nếu xem mỗi kênh màu R,G,B của ảnh màu 24bpp như 1 ảnh đa mức xám, ta có thể giấu tin mật trên cả 3 kênh nhờ các sơ đồ này. Bài toán nâng cao điều khiển chất lượng giấu tin cho ảnh nhị phân, hay mở rộng các sơ đồ giấu tin cho ảnh màu palette , vì thế được nghiên cứu mở rộng ngoài nội dung luận văn. 3.2.6. Phương pháp giấu tin theo module Trong G, với mỗi điểm ảnh trong khối F ta tính giá trị x = (C and 3), để có được hai bit LSB của C, và sau đó xác định v(C) = x, 0 ≤ x ≤ 3. Thay vì C, v(C) Z4 có thể được sử dụng như là giá trị mới của các điểm ảnh. Thay đổi 2 bit LSB x của C có thể gây ra thay đổi mới v(C). Thay đổi một màu trong C tương ứng một giá trị t trong Z4 có nghĩa rằng hai LSB v(C) trong C được thay thế bằng v(C) + t trong Z4. Ví dụ, C = 99 được biểu diễn ở dạng nhị phân là 01100011, chúng ta nhận được hai bit LSB x = 11 hoặc v(C) = x = 3 ở Z4. Nếu chúng ta cần thay đổi C để v(C) được thay thế bằng v(C) +2 = 1 trong Z4, điều này có nghĩa là x được thay thế bởi x’ = 1 với cách biểu diễn nhị phân x = 01, sau đó C được thay đổi thành C’ = 01.100.001. Ví dụ: Trong Z4-module M = (Z4 Z4 Z4) cho đơn giản với i, j, k Z4 chúng ta viết mỗi phần tử bằng chuỗi 3 – ký tự ijk thay vì một bộ 3 (i, j, k). M có U = {u1, u2, u3, u4, u5, u6} là một 2-cơ sở x, u1 = 001, u2 = 010, u3 = 011, u4 = 012, u5 = 100, u6 = 331. Đối với mỗi khối F có N điểm ảnh (256 mức xám), N ≥ 6 chúng ta có thể giấu bất kỳ d M như sau: Ví dụ, giả sử N = 6, F = {p1, , p6}, p1 = 13, p2 = 65, p3 = 139, p4 = 211, p5 = 222, p6 = 173 trong 256 mức xám. Đối với hệ nhị phân, chúng ta thấy: p1 = 00.001.101 với v(p1) = 1, p2 = 01.000.001 với v(p2) = 1, p3 = 10.001.011 có v(p3) = 3, p4 = 11.010.011 với v (p4) = 3, p5 = 1.101.110 có v (p5) = 2, p6 = 10.111.101 có v (p6) = 1. 51
Chúng ta chọn một hàm h: S = {1,2, , 6} → U được cho bởi h(i) = Ui. Giả sử chúng ta cần giấu dữ liệu bí mật d = ijk = (2, 1, 3) trong khối F. Ở bước 1, trong M ta tính: p =  i S h(i).v(pi) =u1.1+u2.1+u3.3+u4.3+u5.2+u6.1 =001+010+033+032+200+331= 123. Then –p = 321 in M Do p ≠ d, chúng ta tính m = d + (- p) = d - p = 213 + 321 = 130 trong M. Từ U thuộc a2 - cơ sở của M, chúng ta thấy m = u5.1 + u2.3, điều này chứng tỏ rằng các màu p5 thay đổi thành p5 ', như vậy v(p5') = v(p5) + 1 = 3, p2 đến p2', như vậy v(p2’) = v(p2) + 3 = 0 trong Z4. Để làm điều đó chúng ta thay đổi hai bit LSB của p5 là 10 11, hai bit LSB của p2 là 01 00. Tại p5 '= 1.101.111, p2' = 01.000.000 hoặc chúng ta có được khối cần giấu. Fnew ={ 13, 64, 139, 211, 223, 173} bằng cách thay đổi hai điểm ảnh trong F Khi giải mã, từ Fnew, chúng ta có được p =  i S h(i).v(pi) =u1.1+u2.0+u3.3+u4.3+u5.3+u6.1 =001+000+033+032+300+331= 213 = d, chính là dữ liệu mật mà chúng ta đã giấu. 3.2.7. Thuật toán giấu tin trong ảnh xám theo module Ý tưởng: Với mỗi tập F có 6 phần tử trên vành Z4 thực hiện lật tối đa 2 vị trí của F để giấu được 6 bit mật trên mỗi khối F . 3 Định nghĩa: Cho M  Z4 có dạng 3 M: { d ZZ4 | d ( d 1 , d 2 , d 3 ); di 4 }, với u, v M ta định nghĩa phép cộng u v và phép nhân u với 1 số r Z4 như sau: 52
u v (,,) u1 v 1 u 2 v 2 u 3 v 3 M r.(.,.,.) u r u1 r u 2 r u 3 M Thuật toán: - Input: Khối 6 điểm ảnh P = {p1, , p6} +) Khối F gồm 6 phần tử: FFFF {1 , 2 , , 6 } +) Khối khóa UUUU {1 , 2 , , 6 } +) d là số 6 bit mật cần giấu - Output: +) Khối 6 điểm ảnh đã sửa để giấu được d. Nội dung thuật toán: +) Tính khối F = {f1, , f6} ở đó fi = v(pi), i = 1 6. + Thuật toán giấu tin: 1) Từ khối P, tính khối F = {f1, , f6} ở đó fi = v(pi), i = 1 6. 2)Tính 3) Uses a) s = d: = P // Không thay đổi điểm ảnh nào. b) s ≠ d: B1: Tính x = d – s M B2) Tìm ui v để có t Z4 : x = ui.ti - Nếu tìm được, thay điểm ảnh pi bởi pi’ sao cho: 53
V(pi’) = v(pi) + t trong Z4 - Nếu không tìm được ui chuyển sang bước sau. B3) Tìm hai giá trị ui , uj v và t, t’ Z4 sao cho: x = ui.t + uj.t’ (trong M) và thay pi, pj sao cho : v(pi’) = v(pi) + t Z4 v(pj’) = v(pj) + t’ Z4 4) Return( ); // đã giấu d. + Thuật toán giải tin: - Input: đã giấu tin - Output: d M (d: dữ liệu mật) B1) Từ = { , , } tính = { , , }, I = 1 6. B2) Tính B3) Return(d); Ví dụ: Cho F được xác định như sau FFFFFFF {1 1, 2 2, 3 0, 4 1, 5 1, 6 0}, và UUUUUUU {1 (0,0,1); 2 (0,1,0); 3 (0,1,1); 4 (0,1,2); 5 (1,0,0); 6 (3,3,1)} Theo trên, ta tính được 54
6 PUFUUUU  i i 1 2 2 4 5 (0,0,1) (0,2,0) (0,1,2) (1,0,0) (1,3,3) i 1 3 Giả sử cần giấu tin mật d (2,3,1) Z4 , tính x d P (2,3,1) (1,3,3) (2,3,1) (3,1,1) (1,0,2) 2 U1 U 5 Ta thực hiện thay đổi F tại hai vị trí {,}FF1 5 ta được FF1' 1 2 1 2 3 FF5' 5 1 1 1 2 Cuối cùng ta có được khối F ' mới FFFFFFF' {1 ' 3, 2 2, 3 0, 4 1, 5 ' 2, 6 =0} Bước giải tin mật, ta thực hiện tính 6 P  Ui F i ' 3 U1 2 U 2 U 4 2 U 5 (2,3,1) d i 1 Kết thúc giải thuật, lấy lại tin mật thành công. 3.2.8. Thuật toán giấu tin trong ảnh xám theo module Trong phần này, ta giới thiệu một phương pháp sử dụng 2-cơ sở yếu trên module Z2. Đối với module M = trên trường Z2 , mỗi phần tử của nó được xem như là một số tự nhiên hoặc một chuỗi nhị phân hoặc vector 6 chiều. Hai cơ sở yếu của 12 phần tử được chi ra như sau: U = {11, 51, 55, 39, 30, 42, 1, 2, 4, 8, 16, 32} là các số tự nhiên, hoặc U ={w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12}, w1=001011, w2=110011, w3=110111, w4=100111, w5=011110, w6=101010, w7=000001, 55
w8=000010, w9=000100, w10=001000, w11= 010000, w12= 100000, biểu diễn dạng nhị phân. Với cơ sở này, ngoại trừ phần tử 61 với biểu diễn nhị phân là 111.101, tất cả các phần tử khác trong M có thể được trình bày như là một sự tổ hợp tuyến tính của nhiều nhất là 2 phần tử của U. Thuộc tính này giúp chúng ta có thể sử dụng hầu hết các khối nhị phân của 12 điểm ảnh, chúng ta có thể giấu 6 bit và chúng ta có thể sử dụng để xây dựng một sơ đồ giấu tin có sự kiểm soát chất lượng của ảnh giấu tin. w1 w8 w6 p1 p8 p6 k1 k8 k6 w9 w2 w10 p9 p2 p10 k9 k2 k10 U = S = K = w4 w11 w3 p4 p11 p3 k4 k11 k3 w7 w5 w12 p7 p5 p12 k7 k5 k12 Cùng một ý tưởng trong phương pháp được đưa ra bởi Tseng-Pan (2002), giả sử rằng chúng ta cần giấu D0 = b5b4b3b2b1 một chuỗi mật 5-bit trong S. Chúng ta có thể thêm một bit điều khiển b0= 1 như một LSB bit của D = b5b4b3b2b1b0 và chúng ta thử cố gắn giấu D trong S. Nếu không thành công, chúng ta lật b0 tới 0 và giấu bất kỳ chuỗi 6 - bit nào có b0 = 0 như của LSB trong S, để đánh giấu S là khối bị lỗi và không thể sử dụng để khai thác dữ liệu Các điều kiện và các dữ kiện sau đây là cần thiết cho tính đúng đắn và thành công của phương pháp này. Điều kiện 1. (điều kiện lẻ) Trong mỗi ma trận con 2 × 2 của U, có giá trị lẻ. Điều kiện 2. (điều kiện chẵn) Tương ứng với giá trị lẻ trong U là k1, k2, k3, k4, k6, k7 trong K thỏa mãn tổng k1 + k2 + k3 + k4 + k6 + k7 là một giá trị chẵn. Thực tế 1. Với điều kiện 2, trong trường hợp S có tất cả các giá trị là 0 hoặc 1 (giá trị - đơn), tổng [S,K] = 1≤ i ≤ 12 wi.(piki) luôn chẵn. 56
Thực tế 2. Ngoại trừ phần tử 61 = 1.111.012, bất kỳ phần tử nào trong M đều có thể được biểu tuyến tính nhiều nhất 2 phần tử của U. Thực tế 3. Trong trường hợp S không phải là giá trị - đơn bởi các điều kiện 1 và 2, người ta luôn luôn có thể tìm thấy một pi trong số 6 giá trị p1, p2, p3, p4, p6, p7 trong S mà pj ≠ pi, cả hai đều thuộc ma trận con 2 × 2 của S. Bây giờ, các bước giấu tin và giải tin của lược đồ mới có thể được trình bày như sau. 3.2.8.1. Thuật toán giấu tin B1 1) Tính D = D0 ×2+1= b5b4b3b2b11 (dạng biểu diễn nhị phân của phần tử trên M) 2) Tính ma trận nhị phân cùng cấp 4 x 3: T = SK; {T gồm các phần tử t1, ,t12 theo thứ với S và K}. 3) {Cố gắng giấu D vào S} Tính tổng của M: x = 1≤ i ≤ 12 wi.ti; 3.1) Trường hợp x = D: giữ nguyên S ; {S được xem là thành công và có chứa D0} 3.2) Trường hợp x ≠ D và y=Dx ≠111101; {thực hiện phép XOR bits tương đương với D-x trong M} 3.2.1) Tìm wi trong U thỏa mãn wi = y: - Nếu tồn tại wi và pi liền kề với pi, pj≠pi , pi, pj trên ma trận con cấp 2x2 của S, thì đảo pi bằng phép cách thực hiện1pi ; - Nếu không tồn tại wi và pi thỏa mãn điều kiện thì đến bước tiếp theo; 3.2.2) Tìm wi và wj trong U thỏa mãn 3 điều kiện sau: a) wi wj = y; 57
b) pi liền kề với pj và pj≠pi, trong ma trận con 2×2 của S; c) pk liền kề với pi và pl ≠pk, trong ma trận con 2×2 của S; - Đảo hai phần pi và pj Trong trường hợp không tìm thấy wi, wj và pi, pj, thì thực hiện bước tiếp theo 3.2.3) Đánh giấu khối S không thành công: a) Nếu x là số chắn thì giữ nguyên S và kết thúc b) Nếu x là số lẻ, tìm một phần tử pi trong 6 phần tử p1, p2, p3, p4, p6, p7 trong S cái mà liền kề với các phần tử khác trên mỗi khối con 2 × 2 của ma trân S, đảo pi và kết thúc 3.3) Trường hợp x≠ D và y = Dx =111101, giữ nguyên S và kết thúc. 4) Return(S); // S mới đã giấu d hoặc thất bại. 3.2.8.2. Thuật toán khôi phục B2 Gọi khối S là khối điểm ảnh được trích ra từ ảnh chứa tính mật. Chúng ta sẽ cố gắng tách dãy bít đã nhúng trong S theo thuật toán sau: Bước 1) Tính ma trận nhị phân T cấp 4 x 3: T = SK; Step 2) tính x = 1≤ i ≤ 12 wi.ti trên M; - Nếu x là số lẻ, thì trả lại dãy bít D = x div 2, loại bỏ bít thấp của x để được 5 bít tin mật - Nếu x là số chẵn, kết luận S không chứa tin mật. Chúng ta nhận thấy rằng, trong bước giấu tin ở mục 3.2), nếu trường hợp 3.2.3 (b) xảy ra, bởi Thực tế 2, chúng ta luôn luôn tìm thấy pi trong 6 giá trị p1, p2, p3, p4, p6, p7 trong S mà pj ≠ pi cả hai thuộc ma trận con 2 × 2 của S. 58
Do đó, chúng ta có thể dễ dàng suy luận đúng đắn của giải thuật bằng cách sử dụng điều kiện 1,2 trên Thực tế 1,2,3. Ví dụ 3.1. Cho 3 ma trận như sau: w1 w8 w6 0 p1 1 p8 0 p6 1 0 1 w9 w2 w10 1 1 1 1 1 1 w4 w11 w3 0 0 p11 1 K = 0 0 1 U = S = w7 w5 w12 0 1 1 0 0 0 Trong giai đoạn giấu, T=[SK] có 12 phần t1=1, t2=1, t3=1, t4=0, t5=0, t6=0, t7=0, t8=0, t9=0, t10=0, t11=1, t12=1. Vì vậy tổng x = 1≤ i ≤ 12 wi.ti =w1w2w3w11w12= 111111. Bây giờ, giả sử chúng ta cần phải giấu một chuỗi 5-bit D0 = 10110 in S: - Chúng ta mở rộng D0 tới D = 101101; - Vì x ≠ D và y = Dx =010010(2)=18 ≠ 61=111101(2), chúng ta không thể tìm thấy wi sao cho wi =18 trong U, Chúng ta tìm thấy w8= 2 và w11=16 trong U sao cho 216 = 18. - Sau đó, chúng ta lật p8 thành 0 và p11 thành 1 trong S, chúng ta sẽ có được S (mới) với p8=0 và p11 =1. Trong giai đoạn tách dữ liệu, chúng ta tính T= [SK] trong đó có 12 phần tử t1=1, t2=1, t3=1, t4=0,t5=0,t6=0, t7=0, t8=1, t9=0, t10=0, t11=0, t12=1. Sau đó, chúng ta tính: x = 1≤ i ≤ 12 wi.ti = w1w2w3w8w12= 101101. Vì x là số lẻ, thông báo rằng S là một khối được tách thành công, vì thế chúng ta có thể tách D0= x div 2 = 10110 như dữ liệu giấu ban đầu. 59
3.2.8.3. Giấu dữ liệu trong dãy các khối của ảnh nhị phân G Vì kích thước 4 × 3 là nhỏ, chúng ta có thể sử dụng một bộ K của 12 × 10 = 120 khóa nhị phân và chia K thành 10 ma trận nhị phân là K0, K1, , K9, mỗi ma trận đó đều có kích thước 4 × 3. Giả sử chúng ta cần phải giấu một dãy 5-bit các chuỗi D1, ,Dq trong một dãy các khối S1, , SN của ảnh nhị phân G. Chúng ta trình bày hai giai đoạn giấu và giải nén dữ liệu như sau. Bước giấu dữ liệu Bước 1) Đặt t = 0; j = 1; i = 1; Bước 2) Trong khi (While) (i q) thì Quay lại (G) là ảnh giấu dữ liệu Ngược lại, quay về (i-1) {thông báo trong G, chúng ta chỉ có thể giấu thành công một chỉ số i trong chuỗi D1, , Di, chứ không phải tất cả chuỗi D1, ,Dq } Bước tách dữ liệu Bước 1) Gán t = 0; j = 1; i = 1; Bước 2) Trong khi (While) (i <= q) và (j <= N) 2,1) Tách dữ liệu Di trong Sj theo thuật toán B2 bằng cách sử dụng ma trận khóa Kt; 2,2) Nếu tách khối Sj thành công, Di được lưu và gán i = i +1; j = j +1; t = (t +1) mod 10; 60
2,3) Nếu tách Sj là thất bại, gán j = j +1; Kết thúc (End while); Bước 3) Nếu (i> q) quay lại (chuỗi D1, ,Dq) là dữ liệu giấu Ngược lại, thông báo rằng G có thể không được sử dụng để tách dữ liệu trong tất cả các chuỗi D1, ,Dq và thoát. 3.2.8.4. Kết quả thử nghiệm Chúng tôi xây dựng một chương trình mà cho chúng ta nhiều 2- cơ sở yếu trong ứng dụng cho ảnh nhị phân và ảnh bảng màu (palette). Một số số 2-cơ sở yếu được chọn như sau. 1) U1= {11,51,55,42,30,45,1,2,4,8,16,32}, phần tử duy nhất 57 trong M không thể biểu diễn bởi U1 (bởi một tổng nhiều nhất là hai phần tử trong U). 2) U2= {11,51,55,39,30,29,1,2,4,8,16,32}, phần tử duy nhất 52 trong M không thể biểu diễn bởi U2. 3) U3= {11,51,61,39,30,42,1,2,4,8,16,32}, phần tử duy nhất 41 trong M không thể biểu diễn bởi U3. 4) U4= {11,51,61,42,30,45,1,2,4,8,16,32}, phần tử duy nhất 39 trong M không thể biểu diễn bởi U4. 5) U5= {11,51,55,46,41,29,1,2,4,8,16,32}, phần tử duy nhất 58 trong M không thể biểu diễn bởi U5. Theo mục 2.2 về tỷ lệ giấu tin tối đa (MSDR) của các phương pháp giấu tin trên ảnh nhị phân ta có bảng so sánh sau: 61
Bảng so sánh tỷ lệ giấu tin (số bit mật được giấu) lý tưởng R, của phương pháp CPT, phương pháp module lật 1 điểm trên cùng 1 khối ảnh nhị phân: Kích MSDR CPT Module Module thước của (khi lật khối F Khi lật Khi lật không quá Khi lật Khi lật Khi lật Khi lật (theo điểm không quá không quá 2 điểm) không quá không quá không quá không quá ảnh) 1 điểm 2 điểm 1 điểm 2 điểm 1 điểm 2 điểm 6 2 4 2 2 4 2 4 7 3 4 3 3 4 3 4 12 3 6 3 3 6 3 6 15 4 6 4 4 6 4 6 31 5 8 5 5 8 5 8 64 6 11 6 6 11 6 11 Bảng 3-1. So sánh tỷ lệ giấu tin giữa MSDR và các sơ đồ CPT, , Kết luận Đối với các ứng dụng thực tế, chúng ta cần phải kiểm soát chất lượng của hình ảnh có giấu tin, với 2- cơ sở yếu như đã đề cập ở trên, chúng ta có thể áp dụng cho ảnh nhị phân và ảnh bảng màu để giấu dữ liệu với chất lượng cao. Nội dung phần này trình bày phương pháp để giấu một số lượng lớn các bit trong ảnh với các khối nhỏ trong khi chất lượng có thể được kiểm soát như yêu cầu, với một tập hợp lớn của các khóa nhị phân cho các yêu cầu bảo mật, bằng cách áp dụng tính chất của module trên Z2. Trong tương lai chúng tôi sẽ mở rộng cho các định dạng hình ảnh khác hoặc trong âm thanh, video dựa trên cách tiếp cận module. 62
Chương 4. XÂY DỰNG CHƯƠNG TRÌNH ỨNG DỤNG 4.1. Thiết kế chương trình Trong phần này, chúng ta thiết kế chương trình giấu tin theo phương pháp module trên ảnh nhị phân và ảnh đa cấp xám. 4.1.1. Sơ đồ mức ngữ cảnh Trong hệ thống giấu tin, có hai đối tượng tương tác với hệ thống. Đó là người giấu tin và người giải mã (tách thông tin). Hình 4-1. Sơ đồ quan hệ trong hệ thống giấu tin 4.1.2. Sơ đồ nhúng thông tin vào ảnh Để nhúng thông tin vào ảnh, hệ thống cần có các đối tượng gồm: Ảnh gốc, khóa bảo mật và thông tin mật cần giấu. Hình 4-2. Sơ đồ nhúng tin mật và ảnh 63
4.1.3. Sơ đồ tách thông tin từ ảnh giấu tin Để tách thông tin từ ảnh có giấu tin mật, hệ thống cần có các đối tượng gồm: Ảnh chứa tin mật và khóa bảo mật. 4.2. Chương trình giấu tin Kết quả nổi bật của luận văn là đã ứng dụng được các giải thuật giấu tin theo phương pháp module để nâng cao chất lượng giấu tin. Hình 4-3. Sơ đồ tách tin từ ảnh có giấu tin 4.2.1. Nhúng tin vào ảnh Các bước sử dụng chương trình để thực hiện giấu một file văn bản “de thi van lop 10.txt” vào bức hình “lenna.bmp”. Hình 4-4. Ảnh nhị phân Lenna.bmp 64
Hình 4-5. Tệp tin mật cần giấu Các bước thực hiện như sau: - Bước 1: Chọn menu “Giấu tin mật”. - Bước 2: Chọn một trong các mục: Giấu tin trên ảnh nhị phân Giấu tin trên ảnh đa cấp xám Giấu tin trên ảnh đa cấp xám Hình 4-6. Giao diện chọn giải thuật nhúng tin mật 65
4 4.2.1.1. Giấu tin trên ảnh nhị phân Z4 4 Hình 4-7. Giao diện nhúng dữ liệu vào ảnh trong giải thuật Z4 - Bước 1: Chọn ảnh gốc. - Bước 2: Chọn tệp dữ liệu cần nhúng (giấu) - Bước 3: Chọn thư mục chứa ảnh giấu tin. - Bước 4: Chọn nút “Nhúng” để thực thi chương trình - Bước 5: Xem thông báo từ chương trình Hình 4-8. Thông báo nhúng dữ liệu thành công 66
Hình 4.9. Thông báo các thông số sau khi nhúng dữ liệu thành công 4.2.1.2. Giấu tin trên ảnh xám Các bước thực hiện tương tự như giấu tin trên ảnh nhị phân . Một số hình ảnh minh họa; Hình 4-10. Giao diện nhúng dữ liệu vào ảnh trong giải thuật 67
Hình 4-11. Thông báo các thông số sau khi nhúng dữ liệu thành công 4.2.1.3. Giấu tin trên ảnh nhị phân Các bước thực hiện tương tự như giấu tin trên ảnh nhị phân Một số hình ảnh minh họa; Hình 4-12. Giao diện nhúng dữ liệu vào ảnh trong giải thuật 68
Hình 4-13. Thông báo các thông số sau khi nhúng dữ liệu thành công 4.2.2. Tách thông tin từ ảnh Để tách thông tin từ ảnh chúng ta cần: Ảnh có giấu tin, khóa (tập cơ sở: phải trùng với tập cơ sở trong quá trình nhúng. - Bước 1: Chọn menu “Khôi phục tin mật” - Bước 2: Chọn giải thuật tương ứng - Trên ảnh nhị phân - Trên ảnh đa cấp xám - Trên ảnh đa cấp xám Một số hình ảnh minh họa: Hình 4-14. Giao diện tách tin mật từ ảnh 69
Hình 4-15. Khôi phục tin trên ảnh nhị phân Hình 4-16. Thông báo khôi phục tin trên ảnh nhị phân Hình 4-17. Tệp dữ liệu được tách ra từ ảnh giấu tin 70
Hình 4-18. Tách tin trên Hình 4-19. Tệp dữ liệu được tách ra từ ảnh giấu tin 71
KẾT LUẬN Với sự phát triển mạnh mẽ của Internet và các dịch vụ trên mạng, đặc biệt các giao dịch trực tuyến trên mạng như truyền tệp, thương mại điện tử, thanh toán qua mạng đang là một trong những nhu cầu thiết yếu của người dùng. Vì vậy vấn đề bảo mật thông tin và bảo vệ bí mật riêng tư cho người dùng nhất thiết cần được quan tâm đúng mực. Để bảo mật thông tin, che giấu thông tin là một phương thức được sử dụng khá phổ biến. Giấu thông tin số, phát hiện thông tin số ẩn giấu trong dữ liệu đa phương tiện đặc biệt là trong ảnh số đã trở thành một vấn đề được quan tâm nhiều trong thời gian qua và có thể được ứng dụng cho nhiều lĩnh vực khác nhau. Phương pháp giấu tin có thể được ứng dụng rộng rãi để giấu các thông tin như tin mật, chữ ký, nhãn thương hiệu để chứng minh sự hợp pháp của sản phẩm, bảo vệ bản quyền Trong luận văn: “Nâng cao chất lượng giấu tin và ứng dụng” tập trung vào một số phương pháp, kỹ thuật giấu tin trong ảnh số. Mục tiêu của luận văn là nghiên cứu, tìm hiểu, trình bày các phương pháp, kỹ thuật giấu tin trong ảnh số theo hướng tiếp cận module của nhóm tác giả Phan Trung Huy, qua đó xây dựng chương trình thử nghiệm giấu tin trong ảnh số. Các kết quả chủ yếu đã đạt được trong luận văn gồm: Nghiên cứu, trình bày các vấn đề cơ bản trong lĩnh vực giấu tin, mô hình giấu tin và các phương pháp, kỹ thuật giấu tin; Nghiên cứu tìm hiểu một số phương pháp, kỹ thuật giấu tin điển hình trong ảnh số; Nghiên cứu, trình bài một số phương pháp nâng cao chất lượng giấu tin theo tiếp cận module như , của nhóm tác giả Phan Trung Huy; Xây dựng chương trình dựa vào các giải thuật của các phương pháp module để nâng cao chất lượng giấu tin trong ảnh. Qua quá trình nghiên cứu tìm hiểu và thực hiện luận văn, tác giả đã nắm được những kiến thức cơ bản về giấu tin trong ảnh số và một số phương pháp, kỹ 72
thuật giấu tin trong ảnh số điển hình như Wu – Lee, CPT nắm được kiến thức cơ bản của các phương pháp tiếp cận module như , . Từ việc xây dựng chương trình ứng dụng, tác giả nhận thấy có nhiều khả năng ứng dụng khác nhau trong thực tế như giấu tin mật, bảo vệ bản quyền số, bảo vệ nhãn hiệu, bảo vệ chữ ký số với việc ứng dụng các phương pháp, kỹ thuật giấu tin trong ảnh số. Hướng phát triển tiếp của luận văn là có thể tiếp tục nghiên cứu tìm hiểu các phương pháp giấu tin theo tiếp cận module sử dụng các môi trường đa phương tiện khác. 73
TÀI LIỆU THAM KHẢO TIẾNG VIỆT [1]. Đỗ Văn Tuấn, Phạm Văn Ất: Một thuật toán giấu tin trong ảnh có bảng màu, Các công trình nghiên cứu khoa học, nghiên cứu triển khai CNTT-TT Số 8, 2012. [2]. Nhữ Bảo Vũ: Ứng Dụng Giấu Tin Trong Mã Hóa & Xác Thực, Đồ án tốt nghiệp, Đại Bách khoa Hà Nội, 2012. [3]. Nguyễn Văn Tảo, Một thuật toán giấu tin và áp dụng giấu tin mật trong ảnh, Tạp chí Khoa học & Công nghệ - Số 4(44) Tập 2, 2007. [4]. Ngô Thái Hà, Nghiên cứu kỹ thuật bảo vệ bản quyền các sản phẩm đồ họa vectơ, Luận văn thạc sĩ, ĐH Thái Nguyên, 2009. [5]. Nguyễn Thị Minh Ngọc, Nghiên cứu các phương pháp giấu tin trong ảnh số và xây dựng mô hình thử nghiệm giấu tin bảo vệ logo doanh nghiệp, Luận văn thạc sĩ, HV Công Nghệ Bưu Chính Viễn Thông, 2011. TIẾNG ANH [1]. Phan Trung Huy, Nguyen Hai Thanh: A new data hiding scheme for small blocks of twelve pixels on binary images by module approach, 2012. [2]. Phan Trung Huy, Nguyen Hai Thanh, Cheonshick Kim: Module Approach in Steganography, 2012 [3]. Phan Trung Huy, NguyenManh Thang: Hiding schemes based on modules over rings of characteristic 3, 2012. [4]. M.Y.Wu, J.H.Lee, Anovel data embedding method for two-color fascimile images, In Proceedings of international symposium on multimedia information processing. Chung-Li, Taiwan, R.O.C, 1998. [5]. Yu Yan Chen, Hsiang Kuang Pan and Yu Chee Tseng, A Secure Data Hiding Scheme for Two color Images, IEEE Symp.on Computer and Communication, 2000. 74
[6]. Yu Chee Tseng and Hsiang Kuang Pan, Secure and Invisible Data Hiding in 2-Color Images, INFOCOM 2001, 887 – 896. [7]. Phan Trung Huy, Vu Phuong Bac, Nguyen Manh Thang, Truong Duc Manh, Vu Tien Duc, Nguyen Tuan Nam, A New CPT Extension Scheme for High Data Embedding Ratio in Binary Images, the Proceedings of the 1st KSE. Inter. Conf. Hanoi 10/2009. 61-66. IEEE.CS. [8]. Christian Collberg, Clark Thomborson, on the Limits of Software Watermarking, Algorithms and Applications, IEEE signal processing magazine, 1997. [9]. Mohamed G. Gouda, Alex X. Liu, Lok M. Leung, Mohamed A. Alam, SPP: An Anti-phishing Single Password Protocol, Computer Networks, Volume 51, Number 13, pp. 3715-3726, 2007.Jürgen Bierbrauer and Jessica Fridrich, Constructing good covering codes for applications in Steganography, Transactions on Data Hiding and Multimedia Security III , Lecture Notes in Computer Science, 2008, Volume 4920/2008, 1-22. [10]. A. R. Calderbank and N. J. A. Sloane, “Inequalities for covering codes,” IEEE Transactions on Information Theory, vol. IT-34, pp. 1276–1280, Sept 1988. [11]. Y.Chen, H.Pan, Y.Tseng. A secret of data hiding scheme for two-color images. In IEEE symposium on computers and communications (2000). [12]. Romana Machado. EZStego[EB/OL] [13]. Fridrich, J., Du, R.: Secure Steganographic Methods for Palette Images. The 3rd Information Hiding Workshop, Lecture Notes in Computer Science. 1768, 47– 60 (2000). [14]. Phan Trung Huy, Hai Thanh Nguyen: On the Maximality of Secret Data Ratio in CPTE Schemes. ACIIDS (1) 2011, LNCS/LNAI series 2011. pp. 88-99. Springer. ISSN 0302-9743; ISBN 978-3-642-20038-0 ; 75