Đề tài Phương pháp giấu tin theo khối ảnh

có giấu tin hay không và tính bền vững của thông tin sau khi giấu. Mục tiêu của bài tập lớn này là nghiên cứu phương pháp giấu tin theo khối ảnh. Tìm cách nâng cao hiệu quả giấu tin, giảm thiểu sự thay đổi ảnh sau khi được giấu tin so với ảnh gốc. Kết quả, trong bài tập này em đã cải tiến thuật toán giấu tin trong ảnh nhị phân, giảm thiểu sự thay đổi của ảnh giấu tin so với ảnh gốc và đã xây dựng chương trình ứng dụng thuật toán giấu tin trên ảnh nhị phân. CHƯƠNG 1: TỔNG QUAN VỀ GIẤU TIN TRONG ẢNH SỐ 1.1. Khái niệm về giấu tin trong ảnh số Giấu tin (information hiding): Là che giấu những thông tin cần bảo mật nhằm chỉ để một số người được biết và không cho những người khác biết. Giấu tin số (data hiding): Là giấu những thông tin số vào trong một đối tượng dữ liệu số khác (gọi là môi trường giấu tin) sao cho môi trường trước và sau khi giấu tin gần như không có sự khác biệt, đồng thời có thể khôi phục lại chính xác các thông tin đã giấu. Sự khác biệt chủ yếu giữa mã hoá thông tin và giấu tin số là mã hoá làm cho các thông tin hiện rõ là nó có được mã hoá hay không, còn với giấu tin số thì người ta sẽ khó biết được là có thông tin giấu bên trong hay không.  Môi trường giấu tin số có thể là bất kỳ đối tượng dữ liệu số nào như âm thanh, ảnh, video, văn bản, cơ sở dữ liệu, … trong đó môi trường ảnh số đã và đang được nhiều người quan tâm. Giấu thông tin trong ảnh hiện nay 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 đ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 thông tin trong ảnh cũng đóng vai trò hết sức quan trọng đối với hầu hết các ứng dụng bảo vệ an toàn thông tin như: nhận 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 cập, giấu thông tin mật... Giấu tin trong ảnh số là một phương pháp giấu tin mà thông tin giấu được đưa vào trong dữ liệu của file ảnh nhưng ít làm thay đổi ảnh cả về chất lượng ảnh và dung lượng file ảnh. Thông tin giấu được tách ra từ ảnh mang mà không cần ảnh gốc. Cơ sở của kỹ thuật giấu tin trong ảnh chủ yếu dựa vào bản chất hệ thống thị giác của con người, do khả năng cảm nhận về màu sắc của mắt người là hạn chế nên nhữnng thay đổi nhỏ về giá trị màu của điểm ảnh khó có thể phát hiện được bằng mắt. Các thành phần chính của một hệ giấu tin trong ảnh bao gồm: Bản tin mật (Secret Message): có thể là văn bản hoặc tệp ảnh hay bất kỳ một tệp nhị phân nào, vì quá trình xử lý chúng ta đều chuyển chúng thành chuỗi các bit. Ảnh phủ (hay ảnh gốc) (Cover Data): là ảnh được dùng để làm môi trường nhúng tin mật. Khoá bí mật K (Key): khoá viết mật tham gia vào quá trình giấu tin để tăng tính bảo mật Bộ nhúng thông tin (Embedding Algorithm): Những chương trình, thuật toán nhúng tin. Ảnh mang (Stego Data): là ảnh sau khi đã nhúng tin mật vào đó Kiểm định (Control) : Kiểm tra thông tin sau khi được giải mã. Mô hình của kỹ thuật giấu tin cơ bản được mô tả theo hai hình vẽ sau : Phương tiện chứa: (Audio,ảnh,video) Bộ nhúng thông tin Bản tin mật Khoá Phương tiện chứa đã giấu tin Phân loại Hình 1: Lược đồ chung cho quá trình giấu tin Hình vẽ trên biểu diễn quá trình giấu tin cơ bản. Phương tiện chứa bao gồm các đối tượng được dùng làm môi trường giấu tin như : text, audio, video, ảnh, bản tin mật là một lượng thông tin mang một ý nghĩa nào đó như ảnh, logo, đoạn van bản… tuỳ thuộc vào mục đích của người sử dụng . Thông tin sẽ được giấu vào trong phương tiện chứa nhờ một bộ nhúng, bộ nhúng là những chương trình, triển khai các thuật toán để giấu tin và được thực hiện với một khoá bí mật giống như các hệ mật mã cổ điển. Sau khi giấu tin, ta thu được phương tiện chứa bản tin đã giấu và phân phối sử dụng trên mạng. Phương tiện chứa (audio, ảnh, video) Bộ giải mã tin Bản tin mật Khoá Phương tiện chứa đã giấu tin Kiểm định mã tin Hình 2: Lược đồ cho quá trình giải mã Hình vẽ trên chỉ ra các công việc giải mã thông tin đã giấu. Sau khi nhận được đối tượng phương tiện chứa có giấu thông tin, quá trình giải mã được thực hiện thông qua bộ nhúng thông tin cùng với khoá của quá t rình nhúng. Kết quả thu được gồm phương tiện chứa gốc và bản tin mật đã được giấu. Bước tiếp theo bản tin mật thu được sẽ được xử lý kiểm định so sánh với thông tin giấu ban đầu. Sơ đồ phân loại trên (hình 1,2) được Fabien A. P. Petitcolas đề xuất năm 1999. 1.2. Các đặc tính của giấu tin trong ảnh: - Tính ẩn (tính vô hình) Khi quan sát ảnh mang bằng mắt thường không phát hiện được thông tin giấu và không gây nghi ngờ cho người xem. Tính ẩn phụ thuộc vào mức độ biến đổi của ảnh mang so với ảnh gốc trong quá trình giấu tin. - Tính bền vững Ảnh mang có thể phải chịu một số tác động nào đó từ bên ngoài như lọc ảnh, làm sắc nét, … dẫn đến mẩu tin tách được M’ # M. Tỉ lệ M’/M thể hiện tính bền vững của thuật toán giấu tin. - Dung lượng giấu tin Là tỉ lệ giữa số byte tối đa thông tin có thể giấu được so với kích thước của file ảnh (tính bằng byte). Cùng một thuật toán giấu tin với các file ảnh khác nhau có thể cho tỉ lệ khác nhau. Thông thường các phương pháp giấu tin trong ảnh đều cố làm tăng dung lượng giấu tin, tuy nhiên việc tăng dung lượng giấu tin sẽ ảnh hưởng tới các đặc tính khác như tính ẩn và tính bền vững. - Tính an toàn Là khả năng chống lại sự tấn công hoặc giả mạo từ bên ngoài. Một hệ giấu tin tốt phải đảm bảo tin mật không bị tấn công một cách có chủ đích trên cơ sở có những hiểu biết về phương pháp giấu tin như có ảnh mang, có ảnh mang và ảnh gốc, có bộ giải mã (nhưng chưa có khoá), … - Độ phức tạp tính toán Chủ yếu tính bằng số các phép toán thực hiện trong việc giấu tin và giải mã (tách tin). Yêu cầu về độ phức tạp tính toán tuỳ thuộc từng ứng dụng. 1.3. Phân loại kỹ thuật giấu tin trong ảnh Dựa vào các tiêu chí khác nhau, người ta có thể phân chia một cách tương đối thành các kỹ thuật giấu tin khác nhau. - Dựa vào mục đích giấu tin: + Watermarking (thủy vân, thủy ấn) quan tâm nhiều đến ứng dụng giấu các mẩu tin ngắn nhưng đòi hỏi độ bền vững lớn của thông tin cần giấu (trước các biến đổi thông thường của tệp dữ liệu môi trường) + Steganography lại quan tâm tới ứng dụng che giấu các bản tin đòi hỏi độ bí mật và dung lượng càng lớn càng tốt. - Dựa vào hướng tiếp cận của kỹ thuật giấu tin có chia làm hai loại: + Thứ nhất: tác động lên miền không gian ảnh, thay đổi trực tiếp giá trị của điểm ảnh (thường dùng với các file ảnh không nén hoặc nén không mất thông tin). + Thứ hai: khảo sát gián tiếp thông qua các kỹ thuật biến đổi khi nén ảnh (thường dùng với các file ảnh nén theo chuẩn có mất thông tin). - Dựa vào cấu trúc màu của ảnh gốc có thể phân thành ba loại: + Giấu tin trong ảnh nhị phân + Giấu tin trong ảnh đa cấp xám + Giấu tin trong ảnh màu - Ngoài ra dựa vào kỹ thuật thay đổi dữ liệu ảnh còn có thể chia thành các phương pháp khác như: phương pháp gài vào các bít có trọng số thấp (LSB); phương pháp mã khối bề mặt; phương pháp dựa trên bảng màu; phương pháp rải vào miền tần số; … 1.4. Ứng dụng kỹ thuật giấu tin trong ảnh Giấu tin trong ảnh số ngày càng được ứng dụng nhiều vào trong các lĩnh vực: liên lạc bí mật, bảo vệ bản quyền, điểm chỉ số, gán nhãn, điều khiển truy cập; … - Liên lạc bí mật Giấu tin trong ảnh rồi gửi đi trên mạng ít gây ra sự chú ý hơn so với sử dụng mật mã. Ngoài ra việc sử dụng công nghệ mã hoá có thể bị hạn chế và cấm sử dụng. Có thể dùng để liên lạc bí mật trong cả thương mại để gửi đi một bí mật thương mại hay trong quân sự, ngoại giao để gửi đi một bản vẽ hay một thông điệp nhạy cảm. - Bảo vệ bản quyền tác giả Một thông tin nào đó mang ý nghĩa quyền sở hữu tác giả (ví dụ như logo của công ty) được bí mật nhúng vào trong các sản phẩm để xác nhận quyền sở hữu khi bán hoặc phân phối sản phẩm, thêm vào đó có thể gán một nhãn thời gian để chống giả mạo. - Điểm chỉ số Thuỷ vân đượ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 đó trong ứng dụng phân phối sản phẩm. Dùng để xác định người nhận sản phẩm, về mặt nào đó nó có ý nghĩa như số xê-ri sản phẩm. - Gán nhãn Các chú giải, minh hoạ có thể được nhúng vào trong ảnh, khi đó nếu sao chép thông thường thì thông tin nhúng cũng được sao chép và chỉ có chủ ở hữu hoặc người được phép mới có thể tách ra được các chú giải này. - Điều khiển truy cập (copy control) Các thiết bị phát hiện thuỷ vân (ở đây sử dụng phương pháp phát hiện thuỷ vân đã giấu mà không cần thông tin gốc) được gán sẵn vào trong các hệ thống đọc ghi, tùy thuộc vào việc có thủy vân hay không để điều khiển (cho phép/cấm) truy cập. Ví dụ như hệ thống quản lí sao chép DVD đã được ứng dụng ở Nhật. CHƯƠNG II: KỸ THUẬT GIẤU TIN TRONG ẢNH NHỊ PHÂN 2.1. Kỹ thuật giấu tin theo khối bít Các phương pháp giấu tin trong ảnh nhị phân thường giấu tin theo khối bit và sử dụng các thuộc tính chẵn lẻ của các khối bit để khôi phục lại thông tin (thường sử dụng các phép toán AND, XOR, SUM để tính toán và biến đổi ảnh giấu tin). Ý 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). Định nghĩa các phép toán với ma trận: Cho hai ma trận nhị phân B1 và B2 cùng kích thước, ta biểu diễn phép AND: B1^B2 là một ma trận kết quả nhận được do lấy phép AND của từng phần tử tương ứng của hai ma trận. Tương tự ta biểu diễn phép XOR: B1 B2 là một ma trận kết quả nhận được do lấy phép XOR của từng phần tử tương ứng của hai ma trận. Cho một ma trận nguyên B, ta biểu diễn [B]i, j là phần tử thuộc hàng i và cột j của B, SUM (B) là tổng của tất cả các phần tử của ma trận B. 2.1.1 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 Ảnh nhị phân F’ được biến đổi từ F và F’ 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 1 bit bi (bi = 0 hoặc bi =1) bằng cách biến đổi Fi thành F’i sao cho F’i thỏa mãn bất biến sau: Bước 3: Kết hợp các khối F’i ta sẽ thu được ảnh F’ 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. 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. 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. Thuật toán Wu-Lee Là một thuật toán giấu tin khá phổ biến của M. Wu và J. Lee. Trong thuật toán Wu-Lee, môi trường giấu tin là một ảnh nhị phân (có thể được coi như một ma trận nhị phân - mỗi phần tử của ma trận là một bit) được chia ra thành các khối mxn bit, mỗi khối giấu được một bit thông tin bằng cách thay đổi nhiều nhất là một bit trong khối. Khóa K là một ma trận kích thước mxn. 2.2.1 Thuật toán Wu-Lee Bước 1: Chia ảnh F thành các ma trận nhỏ Fi kích thước mxn. Bước 2: Với mỗi Fi nhận được ở bước 1, kiểm tra điều kiện: 0< SUM (Fi ^ K) < SUM (K) có đúng hay không? Nếu đúng thì chuyển sang bước 3 để giấu một bit dữ liệu vào Fi, ngược lại thì không có dữ liệu nào được giấu vào Fi và Fi sẽ được giữ nguyên. Bước 3: Giấu bit b vào Fi: If (SUM (Fi ^ K) mod 2 = b) then Giữ nguyên Fi không đổi; Else if (SUM (Fi ^ K) = 1) then Chọn một bit [Fi] j, k bất kì thỏa: ([Fi] j, k = 0) mà [K] j, k =1); Thay [Fi] j, k = 1; Else if (SUM (Fi ^K) = SUM (K) – 1) then Chọn một bit [Fi] j, k bất kì thỏa: [Fi] j, k =1 mà [K]j,k =1; Thay [Fi] j, k = 0; Else Chọn một bit [Fi] j, k bất kì mà [K]j,k =1; Bổ sung [Fi] j, k; Else If Sau khi gắn dữ liệu thì Fi được chuyển thành Fi’ và giữ được tính chất bất biến sau đây: 0 < SUM (Fi’ ^ K) < SUM (K) è SUM (Fi’ ^ K) ≡ b (mod 2). 2.2.2 Ví 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 F’1 F’2 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 F’3 F’4 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 F’1 sao cho SUM(F’1 Ä K) mod 2 = b1. Trong trường hợp nà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ư F’1. - Vì SUM(F2 Ä K) = 0 nên khối F2 sẽ không được dùng để giấu dữ liệu do vậy F’2 = F2. - 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à F’3 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 F4 bằng cách biến đổi F4 thành F’4 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ư F’4. 2.2.3 Phân tích và đánh giá 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. Để 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à nội dung thuật toán Wu-Lee sẽ biến đổi F thành F’ sao cho SUM(F’ Ä 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(F’ Ä K) thì thuật toán sẽ thực hiện đảo giá trị của phần tử Fi,j ứng với Ki,j = 1 để đạt được bất biến. 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 0 hoặc đều bằng 1 thì không nên giấu tin vì nếu thực hiện giấu dễ bị lộ khóa K. Ưu điểm của thuật toán này là tương đối đơn giản. Nhược điểm của thuật toán này là tỷ lệ giấu tin thấp vì mỗi khối chỉ giấu được một bit thông tin, và độ an toàn chưa cao, nếu đối phương đã biết ảnh giấu tin sử dụng thuật toán WL thì chỉ cần xác định được m, n và ma trận khoá là sẽ tìm ra tin giấu. 2.3 Thuật toán Chen-Pan-Tseng Trên cơ sở phát triển ý tưởng của nhóm M.Y. WU và J.H. LEE, các tác giả Y.Y. Chen, H. Pan, Y. Tseng (Chen-Pan-Tseng) đề xuất một phương pháp giấu thông tin trong ảnh nhị phân, theo đó, ảnh được phân hoạch thành nhiều khối có cùng kích thước m×n. Với mỗi khối dữ liệu ảnh có thể giấu được tối đa r bit thông tin, với r ≤ [log2(mn+1)] bằng cách thay đổi không quá 2 bit trong khối dữ liệu ảnh. Thuật toán cần mặt nạ - khóa K có kích thước bằng khối ảnh và gồm các bit 0 hoặc 1 và ma trận trọng số W cũng có kích thước bằng khối ảnh sao cho các phần tử có giá trị phủ kín tập 2R =[1,...,2r-1] và cũng chỉ thuộc tập 2R. 2.3.1 Thuật toán Chen-Pan-Tseng Tóm tắt thuật toán 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 Output: Gọi b là giá trị thập phân của dãy b1,b2,...,br, F’ 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 đó F’ phải thoả mãn bất biến sau: SUM((F’K)W) mod 2r = b Nội dung thuật toán Trường hợp tổng quát: giá trị cần giấu là b [0,..., 2r-1] và ảnh để giấu tin là F, thuật toán giấu b vào F gồm 4 bước: Bước 1: Tính F’(i,j) = K(i,j) xor F(i,j), 1≤ i ≤ m, 1≤ j ≤ n. Bước 2: Tính s = ∑∑ F’ (i,j) W(i,j) Bước 3: Với mỗi w = 1, 2,...,2r-1, tính Sw = { (j,k): W(j,k) =w, F’(j,k) =0 hoặc W(j,k) =2r-w, F’(j,k) =1} Bước 4: Kí hiệu d = b - s (mod 2r) Đảo bit trong khối F để được F’ sao cho tổng s tính trong bước 2 tăng d đơn vị. Trường hợp 1: Nếu d = 0 thì b = S (mod 2r) nên đã đạt được bất biến 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. Trong trường hợp này có hai khả năng: Trường hợp 2.1: Nếu Sw Ø thì chọn (i,j) Sw rồi đảo giá trị phần tử Fi,j, khi đó S sẽ tăng thêm d đơn vị do đó đạt được bất biến. Trường hợp 2.2: Nếu Sw = Ø thì tiếp tục xét S2w, S3w, .... Chọn h là số tự nhiên đầu tiên thoả mãn ShwØ. + Chọn (i,j) Shw và thay đổi bit Fi,j, khi đó S tăng thêm hd. + Chọn (u,v) Sw-hw và thay đổi Fu,v, khi đó S tăng thêm w-hw. Theo trên 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. 2.3.2 Ví dụ minh họa thuật toán Chen-Pan-Tseng Ví dụ: ảnh gốc là F, khóa là K và ma trận trọng số W như sau: F1 F2 F3 F4 0 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 1 1 1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 F = W= K= Đầu tiên F được chia thành 4 ma trận con kích thước 4x4 là F1, F2 , F3 , F4. Ta có r ≤4, chọn r = 3 => có thể giấu được 12 bit. Cho B=001010000001, thực hiện giấu B vào trong F như sau: 1 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 F1 K F2 K F1’ F2’ F3 K F4 K F3 ’ F4 ’ 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 Hình 2.2. Kết quả biến đổi ảnh giấu tin theo thuật toán Chen-Pan-Tseng - Xét F1: SUM ((F1 K) W) ≡ 0 (mod 8).Vì dữ liệu cần giấu vào F1 là 001, phải tăng trọng số lên 1. Do [F1 K]2, 4 = 0 và [W]2, 4 = 1, đảo bit [F1]2,4 - Xét F2: SUM ((F2 K) W) ≡ 2 (mod 8), dữ liệu cần giấu vào là 010, trường hợp này không cần phải thay đổi F2. - Xét F3: SUM ((F3 K) W) ≡ 2 (mod 8), dữ liệu cần giấu là 000, phải tăng trọng số lên 6, tương ứng đảo bit [F3]4,4. - Xét F4: SUM ((F4 K) W) ≡ 4 (mod 8), dữ liệu cần giấu vào là 001, phải tăng trọng số lên 5. Trong F4 không có điểm nào thỏa mãn như vậy do đó cần thay đổi hai vị trí. Các khả năng có thể là S10 =S2 = {(2, 2)} hoặc S5-2 = S3 = {(1,3), (2,1), (3,2), (3,4)}. Trong ví dụ này ta chọn đảo bit [F4]2, 2 và [F4]3, 2. Kết quả cuối cùng như trong hình 2.2. Chen-Pan-Tseng đã chứng minh rằng để tăng tổng s trong bước 2 chỉ cần thay đổi không quá 2 bit trong khối F. Kết quả quan trọng được Chen-Pan-Tseng chứng minh là trong mỗi khối kích thước m×n có thể giấu được tối đa [log2(mn+1)] bit với độ an toàn khá cao. Có thể lựa chọn K và W từ: khả năng. 2.3.3 Phân tích và đánh giá 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à 2r < 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. Độ 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à: 2m*n Thuật toán Chen-Pan-Tseng sử dụng một ma trận trọng số nhằm 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 Chen-Pan-Tseng sẽ cao hơn của thuật toán Wu-Lee. 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. 2.4. Cải tiến thuật toán Chen-Pan-Tseng Những nghiên cứu trong bài tập này với thuật toán Chen-Pan-Tseng (CPT) chỉ ra có thể giấu r bit vào khối ảnh nhị phân F kích thước mxn với 2r £ mxn (r = [log2(mn+1)]) mà chỉ cần thay đổi không quá hai bit trong F. Cải tiến trong thuật toán này đề xuất ở đây là mở rộng được giá trị cần giấu là có thể giấu được giá trị b £ mn – 1. Chẳng hạn, với một khối có kích thước 10x17, thuật toán CPT chỉ có thể giấu được tối đa 7 bit, thuật toán mở rộng ở đây có thể giấu một số nguyên không âm có giá trị tối đa tới 169 mà mức độ ảnh hưởng là như nhau. 2.4.1 Một số phép toán giữa 2 số tự nhiên Định nghĩa phép toán XOR giữa 2 số tự nhiên: Cho 2 số tự nhiên a và b được biểu diễn dưới dạng chuỗi nhị phân gồm k bit như sau: a = a1a2…ak; b = b1b2…bk . Kí hiệu c = ab là kết quả phép toán XOR giữa 2 số tự nhiên a và b, trong đó c là một số tự nhiên mà khi biểu diễn dưới dạng chuỗi nhị phân gồm k bit, c = c1c2…ck, thì ci là kết quả phép toán XOR giữa 2 bit tương ứng ai và bi, ci = aibi (i = 1, 2, …, k). Tính chất của phép toán XOR: Dễ dàng nhận thấy phép toán XOR giữa 2 bit có các tính chất sau: aiai = 0 ai0 = 0ai = ai ai1 = 1ai = i (với i là bit đảo của ai) aibi = biai (aibi) ci = ai (bici) (với ai,bi,ci {0,1}) Dễ dàng chứng minh được phép toán XOR giữa 2 số tự nhiên cũng có các tính chất trên (trừ tính chất XOR với 1): aa = 0 (1) a0 = 0a = a (2) ab = ba (3) (ab) c = a (bc) (với a,b,c N) (4) Ngoài ra: a = a1a2…ak; b = b1b2…bk . thì c = ab = c1c2…ck ≤ 2k – 1 (với a,b N) (5) Phép nhân một số tự nhiên a với một bit w Dễ thấy với a N và bit w thì: a.w a.w = 0 (6) a.w a. = a (7) Giấu b vào dãy bit W Cho dãy nhị phân W = {w1, w2, ..., wn} k = [log2(n+1)] m = 2k – 1 => m ≤ n Đặt f(W) = 1.w1 2.w2 … m.wm => f(W) ≤ 2k – 1 (theo tính chất 5) d = f(W) b Xét f’(W) = f(W) d = f(W) (f(W) b) = (f(W) f(W)) b (theo tính chất 4) = 0 b (theo tính chất 1) = b (theo tính chất 2) Giả thiết b ≤ m => d = f(W) b ≤ 2k – 1 hay d ≤ m (theo tính chất 5) Mặt khác theo tính chất (6) và (7) ta có: f’(W) = f(W) d = f(W) (d.wdd.d) = 1.w1 2.w2 … dwd … n.wn (d.wd d.d) = 1.w1 2.w2 … (d.wdd.wd) (d+1).wd+1 … n.wn d.d = 1.w1 2.w2 … (d-1).wd-1 dd (d+1).wd+1 … n.wn = f(W’) với W’ là dãy nhị phân nhận được từ W sau khi đảo bít thứ d => f(W’) = b => có thể giấu được b trong dãy m bit W (b ≤ m) mà m ≤ n nên cũng giấu được b trong dãy n bit W. Mệnh đề: Cần thay đổi nhiều nhất 1 bit để giấu được [log2(n+1)] bit vào trong n bit Chứng minh: Đặt k = [log2(n+1)] và m = 2k – 1 => m ≤ n Theo lập luận ở trên, có thể giấu được b trong dãy n bit W nếu b ≤ m mà chỉ cần đảo bit thứ d trong dãy W (nếu d=0 thì không cần đảo bít nào) Vì b ≤ m nên chỉ cần k bit có thể biểu diễn được b ở dạng nhị phân b = b1b2…bk ≤ 2k – 1 => có thể giấu được k bit trong dãy n bit mà thay đổi nhiều nhất 1 bit. (điều phải chứng minh) 2.4.2 Thuật toán cải tiến CPT Đầu vào: Khối ảnh nhị phân F cỡ m×n, giá trị cần giấu b [0,..., 2r -1] (với r = [log2(mn+1)]) và khóa bí mật K gồm 2r -1 bit. Đầu ra: Khối ảnh nhị phân F’ cỡ m×n có chứa thông tin giấu b. Thuật toán Chuyển 2r -1 giá trị từ F vào W và xor với K for (int t = 0; t < 2r-1; t++) { i = t % m; j = t / m; W[t] = F[i,j]; } W = W K; Tính tổng XOR fW = 1.w1 2.w2 ... k.wk (với k = 2r – 1) Tính d = fW b Đảo bít thứ d trong W tức là thay đổi F(i,j) để được F’ F’[i,j] = F[i,j](i=1..m;j=1..n); i = d % m; j = d / m; F’[i,j